A Concentration of Measure Approach to Correlated Graph Matching

Farhad Shirani, Siddharth Garg, Elza Erkip

Abstract

The graph matching problem emerges naturally in various applications such as web privacy, image processing and computational biology. In this paper, 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"{o}s-R'enyi (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 polytime matching algorithm is proposed.

Introduction

In an era of overlapping social networks, "anonymizing" data by simply removing names is often insufficient. If an attacker has access to a public, labeled graph (like Twitter) and an anonymized graph (like a leaked medical database), they can "match" the nodes based on the patterns of connections (edges). This is the graph matching problem.

The graph matching problem: identifying node correspondences between a labeled graph (left) and an unlabeled correlated graph (right).

The core challenge is determining exactly how much correlation is required between two graphs to recover the correct node labels. While previous work focused on specific cases, this paper seeks a unified framework to characterize the fundamental limits of matching for various models, including Correlated Erdős-Rényi (CER) graphs, Stochastic Block Models (SBM), and graph ensembles.

Methodology: Typicality Matching

The authors propose a strategy called Typicality Matching (TM). This approach draws a direct analogy to Shannon’s channel coding theorem in information theory. Think of the first graph as a "codeword" and the second graph as a "noisy version" that has been randomly permuted (the nodes were shuffled).

In information theory, two sequences are "jointly typical" if their combined statistics match what we expect from their underlying joint distribution. The TM strategy searches for a node permutation that makes the adjacency matrices of the two graphs look "jointly typical." The authors derive new mathematical bounds on the probability that a random permutation of a sequence will appear jointly typical with another, leveraging concentration of measure principles to prove when the TM strategy will succeed as the number of nodes ($n$) grows toward infinity.

Notation used in the mathematical formulation of the graph matching problem.

Key Insights and Results

  • Graph Matching as Decoding: Framing the combinatorial problem of graph matching as a statistical decoding problem allows the use of entropy and mutual information to define "achievable regions" for matching.
  • The "1/2" Factor: The authors highlight a specific coefficient (1/2) in their error exponents. This technical insight shows that the correlation between edges in a graph is an "$n$-letter" correlation, which behaves differently than standard independent sequences in information theory.
  • Community Structure and Seeds: By extending results to the SBM, the paper shows that knowing community memberships significantly changes the conditions for success. Furthermore, while general matching is NP-hard, the authors show that having a small number of "seeds" (pre-matched nodes) allows for a polynomial-time algorithm (Seeded Typicality Matching) that still achieves reliable matching.
  • Tight Conditions: The paper provides necessary and sufficient conditions for "almost all" nodes to be matched correctly. For the edge erasure model, the authors proved that their TM strategy succeeds even when the edge probability $p_n$ is lower than previously established thresholds.

Limitations and Future Work

While the TM strategy provides theoretical limits, its computational complexity remains a challenge for unseeded graphs due to the search through $n!$ permutations. Additionally, this paper focuses on "almost all" matching (matching a fraction $1-o(1)$ of nodes) rather than "exact" matching. Future research may extend this concentration of measure approach to dynamic, time-varying graphs to better reflect real-world network evolution.

Summary updated

Abstract

The graph matching problem emerges naturally in various applications such as web privacy, image processing and computational biology. In this paper, 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\"{o}s-R\'enyi (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 \textit{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 polytime matching algorithm is proposed.
BibTeX
@article{shirani2021concentration,
  author = {Farhad Shirani and Siddharth Garg and Elza Erkip},
  title = {{A Concentration of Measure Approach to Correlated Graph Matching}},
  journal = {IEEE J. Sel. Areas Inf. Theory},
  year = {2021},
  url = {https://openreview.net/forum?id=W_VGnSVUJP},
}
Figure