Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality

Abstract

We analyze a new spectral graph matching algorithm, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), for recovering the latent vertex correspondence between two unlabeled, edge-correlated weighted graphs. Extending the exact recovery guarantees established in the companion paper for Gaussian weights, in this work, we prove the universality of these guarantees for a general correlated Wigner model. In particular, for two Erdős-Rényi graphs with edge correlation coefficient $1-{\sigma }^2$ and average degree at least $\mathrm{polylog}(n)$, we show that GRAMPA exactly recovers the latent vertex correspondence with high probability when $\sigma \lesssim 1/\mathrm{polylog}(n)$. Moreover, we establish a similar guarantee for a variant of GRAMPA, corresponding to a tighter quadratic programming relaxation of the quadratic assignment problem. Our analysis exploits a resolvent representation of the GRAMPA similarity matrix and local laws for the resolvents of sparse Wigner matrices.

References in corpus (2)

• Efficient random graph matching via degree profiles
• Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model

Cited by in corpus (10)

• Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model
• Testing network correlation efficiently via counting trees
• Impossibility of Partial Recovery in the Graph Alignment Problem
• Sharp threshold for alignment of graph databases with Gaussian weights
• Testing correlation of unlabeled random graphs
• Graph Matching with Partially-Correct Seeds
• Correlation detection in trees for planted graph alignment
• The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph match
• Exact Matching of Random Graphs with Constant Correlation
• Random Graph Matching with Improved Noise Robustness