Spectral graph matching and regularized quadratic relaxations

Abstract:
Graph matching aims at finding the vertex correspondence that maximally aligns the edge sets of two given graphs. This task amounts to solving a computationally intractable quadratic assignment problem (QAP). We propose a new spectral method, which computes the eigendecomposition of the two adjacency matrices and returns a matching based on the pairwise alignments between all eigenvectors of the first graph with all eigenvectors of the second. Each alignment is inversely weighted by the gap between the corresponding eigenvalues. This spectral method can be equivalently viewed as solving a regularized quadratic programming relaxation of the QAP. We show that for a correlated Erdos-Renyi model, this method finds the exact matching with high probability if the two graphs differ by at most a 1/polylog(n) fraction of edges, both for dense graphs and for sparse graphs with at least polylog(n) average degree. The proposed algorithm matches the state of the art of polynomial-time algorithms based on combinatorial ideas, and exponentially improves the performance of existing spectral methods that only compare top eigenvectors or eigenvectors of the same order. The analysis exploits local laws for the resolvents of sparse Wigner matrices. The superiority of this new spectral method is also demonstrated on a variety of datasets, in terms of both matching accuracy and computational efficiency.

Based on joint work with Zhou Fan (Yale), Cheng Mao (Georgia Tech), and Jiaming Xu (Duke). Preprints available at https://arxiv.org/abs/1907.08880 and https://arxiv.org/abs/1907.08883.