Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model

Abstract

Graph matching aims at finding the vertex correspondence between two unlabeled graphs that maximizes the total edge weight correlation. This amounts to solving a computationally intractable quadratic assignment problem. In this paper we propose a new spectral method, GRAph Matching by Pairwise eigen-Alignments (GRAMPA). Departing from prior spectral approaches that only compare top eigenvectors, or eigenvectors of the same order, GRAMPA first constructs a similarity matrix as a weighted sum of outer products between all pairs of eigenvectors of the two graphs, with weights given by a Cauchy kernel applied to the separation of the corresponding eigenvalues, then outputs a matching by a simple rounding procedure. The similarity matrix can also be interpreted as the solution to a regularized quadratic programming relaxation of the quadratic assignment problem. For the Gaussian Wigner model in which two complete graphs on $n$ vertices have Gaussian edge weights with correlation coefficient $1-{\sigma }^2$, we show that GRAMPA exactly recovers the correct vertex correspondence with high probability when $\sigma =O(\frac{1}{\log n})$. This matches the state of the art of polynomial-time algorithms, and significantly improves over existing spectral methods which require $\sigma$ to be polynomially small in $n$. The superiority of GRAMPA is also demonstrated on a variety of synthetic and real datasets, in terms of both statistical accuracy and computational efficiency. Universality results, including similar guarantees for dense and sparse Erdős-Rényi graphs, are deferred to the companion paper.

References in corpus (9)

• Emergence of scaling in random networks
• De-anonymizing Social Networks
• Seeded graph matching for correlated Erdős-Rényi graphs
• Exact alignment recovery for correlated Erdős-Rényi graphs
• Eigenvectors distribution and quantum unique ergodicity for deformed Wigner matrices
• Efficient random graph matching via degree profiles
• Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality
• On the Rate of Convergence to the Marchenko--Pastur Distribution
• On the Structure and Efficient Computation of IsoRank Node Similarities

Cited by in corpus (7)

• Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality
• 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
• Random Graph Matching with Improved Noise Robustness