A Concentration of Measure Approach to Correlated Graph Matching

Farhad Shirani, Siddharth Garg, Elza Erkip

TL;DR

This paper introduces an information-theoretic framework for correlated graph matching, the process of identifying corresponding nodes across different networks. By treating graph matching as a "decoding" problem and leveraging concentration of measure principles, the authors derive the fundamental limits (necessary and sufficient conditions) for successful matching across various models, including those with community structures and pre-matched "seeds."

What Problem Does This Paper Address?

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 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:

  1. Correlated Erdős-Rényi (CER) graphs: Where edges are generated independently but are correlated across the two graphs.
  2. Stochastic Block Models (SBM): Where nodes belong to "communities," and connection probabilities depend on community membership.
  3. Graph Ensembles: Matching more than two graphs simultaneously.
  4. Seeded Matching: Where a small subset of node correspondences is already known.

Methods

The authors propose a strategy called Typicality Matching (TM). This approach draws a direct analogy to Shannon’s channel coding theorem in information theory:

  • The Analogy: 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).
  • Joint Typicality: 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."
  • Concentration of Measure: The authors derive new mathematical bounds on the probability that a random permutation of a sequence will appear jointly typical with another. These bounds are the engine that allows them to prove when the TM strategy will succeed or fail as the number of nodes ($n$) grows toward infinity.

Datasets

As a theoretical information theory paper, the authors do not use real-world datasets. Instead, they evaluate their framework using stochastic graph models:

  • Correlated Erdős-Rényi (CER) Model: The standard benchmark for graph matching.
  • Stochastic Block Model (SBM): Used to simulate graphs with realistic community structures.
  • Erasure Model: A specific case of CER where edges in one graph are randomly "erased" in the other.

Key Insights and Ideas

  • Graph Matching as Decoding: The most powerful insight is framing the combinatorial problem of graph matching as a statistical decoding problem. This 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 is a technical "aha moment" showing 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 Matters: By extending the results to the SBM, the paper shows that knowing community memberships (e.g., "these nodes are all in the same department") significantly changes the conditions required for successful matching.
  • Seeded Efficiency: While general typicality matching is computationally hard (NP-hard), the authors show that having a small number of "seeds" (pre-matched nodes) allows for a polynomial-time algorithm that still achieves reliable matching.

Key Results

  • Tight Conditions: The paper provides necessary and sufficient conditions for "almost all" nodes to be matched correctly.
  • Erasure Model Improvement: 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, specifically improving upon results from prior literature (e.g., Cullina et al.).
  • SBM Achievability: They characterized the "achievable region" for graphs with community structures, showing how community-based edge statistics can be leveraged to improve matching accuracy.
  • Seeded Algorithm: They proposed the Seeded Typicality Matching (STM) algorithm and proved it succeeds with high probability if the number of seeds is large enough to overcome the "noise" of the graph's randomness.

Limitations and Future Work

  • Computational Complexity: The general TM strategy involves searching through all possible permutations ($n!$), which is computationally impossible for large graphs. The authors address this via the seeded version, but unseeded, low-complexity matching remains a challenge.
  • Exact vs. Partial Matching: This paper focuses on "almost all" matching (matching a fraction $1-o(1)$ of nodes). Some applications require "exact" matching (every single node), which requires stricter conditions.
  • Dynamic Graphs: The models used are static. Real-world networks evolve over time, and extending this concentration of measure approach to dynamic, time-varying graphs is a suggested path for future research.

Summary updated

Abstract

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.
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},
}

Loading related content...

Figure