Back to Search
Start Over
Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality.
- Source :
- Foundations of Computational Mathematics; Oct2023, Vol. 23 Issue 5, p1567-1617, 51p
- Publication Year :
- 2023
-
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 a 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 polylog (n) , we show that GRAMPA exactly recovers the latent vertex correspondence with high probability when σ ≲ 1 / 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 16153375
- Volume :
- 23
- Issue :
- 5
- Database :
- Complementary Index
- Journal :
- Foundations of Computational Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 172754589
- Full Text :
- https://doi.org/10.1007/s10208-022-09575-7