Improved Achievability and Converse Bounds for Erd\H{o}s-R\'enyi Graph Matching

Problem

• The problem is to recover the entire vertex correspondence between correlated ER graphs after one graph’s labels are randomly permuted.The paper studies the information-theoretic conditions for exact recovery with unbounded computational resources.Source: §1 · p. 1

Main contribution

• For sparse, significantly correlated graphs, the new achievability and converse bounds differ by a factor of two and establish threshold scaling with graph correlation.The achievability bound improves on Pedarsani and Grossglauser.Source: §1 · p. 1

Prior result

• Pedarsani and Grossglauser established that exact deanonymization requires average degree at least Ω(log n).Their result established the threshold’s scaling dependence on the number of vertices.Source: §1 · p. 1

Motivation

• Structural data generated by internet services motivates studying when graph correspondences can be recovered.The paper notes that combining data sources creates trade-offs between analysis and privacy.Source: §1 · p. 1
• Learning a correspondence can expose sensitive user information when another network identifies users.The paper also notes that matching networks can improve estimates of an underlying network by combining noisy or incomplete sources.Source: §1 · pp. 1–2

Prior foundations

• Pedarsani and Grossglauser were the first to study information-theoretic conditions for deanonymization.Subsequent work considered extensions and variants of the problem.Source: §2 · p. 2

Alternative graph models

• Ji et al. studied deanonymization under the configuration model, which can represent degree distributions with heavier upper tails than sparse ER graphs.The passage contrasts the configuration model with ER graphs’ rapidly decaying degree tails [1, 2].Source: §2 · p. 2

Seed information

• Ji et al. derived sufficient conditions for complete or near-complete deanonymization using seed information.They considered information from seed-to-other-vertex edges and from all edges, and determined threshold dependence on the number of seeds.Source: §2 · p. 2

Seed-based algorithms

• Narayanan and Shmatikov [8] introduced seed-based graph matching followed by growing the match and evaluated it empirically on social-network graphs.The passage notes that the graph-matching growth step can scale efficiently.Source: §2 · p. 2

Percolation algorithms

• Yartseva and Grossglauser found a sharp seed-count threshold for percolation matching to cover every vertex, and Kazemi et al. [6] extended the algorithm.The intersection of the graphs plays an important role in the analysis.Source: §2 · p. 2

Imperfect overlap

• Kazemi et al. [7] found that imperfect overlap between graph vertex sets has a relatively mild information-theoretic penalty.The passage presents this regime as a robustness test for deanonymization procedures.Source: §2 · p. 2

3.1 Notation

• Graphs use the canonical vertex set [n], and permutations of [n] form the group S[n] under function composition.The canonical labeling also encodes a graph through its adjacency matrix.Source: §3.1 · p. 2

3.2 The Deanonymization Problem

• The deanonymization problem hides G_a’s labels with a random permutation and asks whether that permutation can be recovered exactly with high probability.An achievability result gives an estimator that succeeds with high probability; a converse bounds exact-recovery probability for any estimator.Source: §3.2 · p. 3

3.3 Correlated Erd˝os-Rényi Graphs

• In the ER(n,p) model, each vertex pair receives an i.i.d. joint edge state for G_a and G_b, defining the graphs’ marginal edge probabilities.The joint state is specified by the four possible presence-or-absence outcomes.Source: §3.3 · p. 3
• The subsampling model constructs G_a and G_b as independent random subgraphs of a shared ER graph, with s_a and s_b controlling their correlation.The passage states that this model is equivalent to the paper’s ER(n,p) parameterization.Source: §3.3 · p. 3
• The subsampling model covers i.i.d. graph pairs with nonnegative correlation, while the broader ER model can also represent negatively correlated graphs.The paper primarily studies the sparse regime, where both marginal edge probabilities tend to zero.Source: §3.3 · p. 3

4. RESULTS

• Theorem 1 provides a deanonymizer that succeeds with probability 1 −o(1), and its achievability result applies for all regimes of p.Source: §4 · p. 3
• In the sparse, significantly correlated regime, Theorem 2 gives high-probability achievability and impossibility bounds whose gap is a factor of 2.The achievability is nearly tight in this regime.Source: §4 · pp. 3–4
• The achievability bound improves on Pedarsani and Grossglauser [9], with a more significant improvement as correlation decreases and s decreases.Source: §4 · p. 4

4.1 Perfect Correlation Limit

• At perfect correlation, a nontrivial automorphism group prevents exact recovery with high probability; Theorem 2’s converse is tight, while its achievability bound is off by a factor of 2.The automorphism group determines whether recovery is possible in this limit.Source: §4.1 · p. 4

4.2 MAP Estimation

• The MAP estimator minimizes error and, because anonymizing permutations are equiprobable, is also the maximum-likelihood estimator.Its structure informs both the achievability and converse bounds.Source: §4.2 · p. 4
• The matching-quality difference d(π) compares a permutation’s match to the identity match, and its expected value depends on the number of fixed points, not nontrivial cycle lengths.Source: §4.2 · p. 5

5. PROOF OF ACHIEVABILITY

• Conditioned on the permutation-induced edge disagreement r, Lemma 3 gives a generating function for the matching-score change, which Lemma 4 uses to bound its tails.Source: §5 · p. 6

5.1 Cycle combinatorics

• Cycle combinatorics evaluates the permutation-distance generating function by decomposing the induced edge permutation into cycles.Theorem 4 expresses the result using the cycle counts of the permutation.Source: §5.1 · p. 6

5.2 Proof of Theorem 1

• The proof groups permutations by the number of moved vertices and applies a union bound to establish Theorem 1's achievability condition.It bounds the worst-case permutation in each group.Source: §5.2 · pp. 7–8

• Every automorphism of the graph intersection gives a permutation whose matching score is no worse than the true correspondence.Source: §6 · pp. 8–9
• Isolated vertices in the intersection provide automorphisms, and their abundance makes its automorphism group grow in the sparse regime.Permuting isolated vertices preserves the graph.Source: §6 · p. 8
• Any estimator succeeds with probability at most 2ε_n in the regime covered by the converse.Source: §6 · p. 9

• The negative-correlation analysis uses nearly the same approach as the positive-correlation analysis, despite the graphs sharing fewer edges.Source: §7 · p. 9
• Much higher edge density is required for deanonymization of sparse negatively correlated graphs than in the positive-correlation case.Source: §7 · p. 9
• For (Ga, Gb) ∼ ER(n, p) with p11 = 0, if p01p10 ≤ log n−ω(1), then with probability 1−o(1), there are ω(1) vertex pairs u,v with |Na(u)∩Nb(v)|=|Na(v)∩Nb(u)|=0.Source: §7 · p. 9
• For such a pair, swapping the vertices leaves the matching-score difference at zero, and the converse bounds every deanonymizer's success by o(1).Source: §7 · p. 9

• For sparse, significantly correlated graphs, the achievability and converse bounds differ by a factor of two and establish threshold dependence on correlation.Source: §8 · p. 10
• In sparse negatively correlated graphs, substantially higher edge density is required for deanonymization because comparable negative correlation levels are impossible.Source: §8 · p. 10
• Improving positive-correlation achievability to match the converse is identified as the most obvious next step.The perfect-correlation limit suggests the converse bound is tight.Source: §8 · p. 10
• The paper studies exact recovery; which partial-deanonymization metrics are practically relevant and tractable remains open.Source: §8 · p. 10