A concentration of measure approach to correlated graph matching

Farhad Shirani, Siddharth Garg, Elza Erkip

Research output: Contribution to journalArticlepeer-review


The graph matching problem emerges naturally in various applications such as Web privacy, image processing and computational biology. In this article, graph matching is considered under a stochastic model, where a pair of randomly generated graphs with pairwise correlated edges are to be matched such that given the labeling of the vertices in the first graph, the labels in the second graph are recovered by leveraging the correlation among their edges. The problem is considered under various settings and graph models. In the first step, the Correlated Erdös-Rényi (CER) graph model is studied, where all edge pairs whose vertices have similar labels are generated based on identical distributions and independently of other edges. A matching scheme called the typicality matching scheme is introduced. The scheme operates by investigating the joint typicality of the adjacency matrices of the two graphs. New results on the typicality of permutations of sequences lead to necessary and sufficient conditions for successful matching based on the parameters of the CER model. In the next step, the results are extended to graphs with community structure generated based on the Stochastic Block Model (SBM). The SBM model is a generalization of the CER model where each vertex in the graph is associated with a community label, which affects its edge statistics. The results are further extended to matching of ensembles of more than two correlated graphs. Lastly, the problem of seeded graph matching is investigated where a subset of the labels in the second graph are known prior to matching. In this scenario, in addition to obtaining necessary and sufficient conditions for successful matching, a polynomial time matching algorithm is proposed.

Original languageEnglish (US)
Article number9344632
Pages (from-to)338-351
Number of pages14
JournalIEEE Journal on Selected Areas in Information Theory
Issue number1
StatePublished - Mar 2021


  • Attributed graphs
  • Correlated graphs
  • Data privacy
  • Graph alignment
  • Graph matching
  • Graph theory
  • Information theory
  • Network theory
  • Permuted sequences
  • Typicality matching

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Media Technology
  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'A concentration of measure approach to correlated graph matching'. Together they form a unique fingerprint.

Cite this