Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality
This work provides theoretical guarantees for graph matching in noisy, sparse networks, which is incremental as it extends prior Gaussian results to more general models.
The authors extended the GRAMPA spectral graph matching algorithm to prove universality of exact recovery guarantees for correlated Erdős-Rényi graphs, showing it recovers vertex correspondence with high probability when noise is sufficiently small, specifically for edge correlation coefficient 1-σ² with σ ≲ 1/polylog(n) and average degree at least polylog(n).
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-σ^2$ and average degree at least $\operatorname{polylog}(n)$, we show that GRAMPA exactly recovers the latent vertex correspondence with high probability when $σ\lesssim 1/\operatorname{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.