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

arXiv: https://arxiv.org/abs/1907.08880 · HTML: https://mlsanity.com/paper/1907.08880/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jul 2019.

## Built on by (most cited first, 13 of 13)

- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Testing network correlation efficiently via counting trees](https://mlsanity.com/paper/2110.11816/) (2021)
- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [Impossibility of Partial Recovery in the Graph Alignment Problem](https://mlsanity.com/paper/2102.02685/) (2021)
- [Random Graph Matching with Improved Noise Robustness](https://mlsanity.com/paper/2101.11783/) (2021)
- [The feasibility of multi-graph alignment: a Bayesian approach](https://mlsanity.com/paper/2502.17142/) (2025)
- [The graph alignment problem: fundamental limits and efficient algorithms](https://mlsanity.com/paper/2404.12418/) (2024)
- [Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation](https://mlsanity.com/paper/2305.19666/) (2023)
- [Statistical Limits for Testing Correlation of Hypergraphs](https://mlsanity.com/paper/2202.05888/) (2022)
- [A Spectral Framework for Evaluating Geodesic Distances Between Graphs](https://mlsanity.com/paper/2406.10500/) (2024)
- [Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm](https://mlsanity.com/paper/2412.16457/) (2024)
- [Covariate-assisted graph matching](https://mlsanity.com/paper/2512.11761/) (2025)
- [Sharp Statistical Thresholds for Attributed Gaussian Graph Matching](https://mlsanity.com/paper/2603.23305/) (2026)

## Abstract (arXiv)

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(frac1log 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 ErdHos-R'enyi graphs, are deferred to the companion paper.