Spectral Graph Matching and Regularized Quadratic Relaxations: Algorithm and Theory

Graph matching, also known as network alignment, aims at recovering the latent vertex correspondence between two unlabeled, edgecorrelated weighted graphs. To tackle this task, we propose a spectral method, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), which first constructs a similarity matrix as a weighted sum of outer products between all pairs of eigenvectors of the two graphs, and then outputs a matching by a simple rounding procedure. For a universality class of correlated Wigner models, GRAMPA achieves exact recovery of the latent matching between two graphs with edge correlation 1 -1/polylog(n) and average degree at least polylog(n). This matches the state-of-theart guarantees for polynomial-time algorithms established for correlated Erdős-Rényi graphs, and significantly improves over existing spectral methods. The superiority of GRAMPA is also demonstrated on a variety of synthetic and real datasets, in terms of both statistical accuracy and computational efficiency.