Back to Search
Start Over
Spectral Graph Matching and Regularized Quadratic Relaxations I Algorithm and Gaussian Analysis.
- Source :
- Foundations of Computational Mathematics; Oct2023, Vol. 23 Issue 5, p1511-1565, 55p
- Publication Year :
- 2023
-
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 - σ 2 , we show that GRAMPA exactly recovers the correct vertex correspondence with high probability when σ = O (1 log n) . This matches the state of the art of polynomial-time algorithms and significantly improves over existing spectral methods which require σ 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 a companion paper. [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 :
- 172754587
- Full Text :
- https://doi.org/10.1007/s10208-022-09570-y