# Graph Alignment via Birkhoff Relaxation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 34 references that are in the map.
- First posted on arXiv 7 Mar 2025.

## Builds on (most cited first, 16 of 16)

- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Graph Matching: Relax at Your Own Risk](https://mlsanity.com/paper/1405.3133/) (2014)
- [Spectral Graph Matching and Regularized Quadratic Relaxations II: ErdHos-R'enyi Graphs and Universality](https://mlsanity.com/paper/1907.08883/) (2019)
- [Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope](https://mlsanity.com/paper/1904.05814/) (2019)
- [From tree matching to sparse graph alignment](https://mlsanity.com/paper/2002.01258/) (2020)
- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [Exact Matching of Random Graphs with Constant Correlation](https://mlsanity.com/paper/2110.05000/) (2021)
- [Sharp threshold for alignment of graph databases with Gaussian weights](https://mlsanity.com/paper/2010.16295/) (2020)
- [Random Graph Matching with Improved Noise Robustness](https://mlsanity.com/paper/2101.11783/) (2021)
- [Correlation detection in trees for planted graph alignment](https://mlsanity.com/paper/2107.07623/) (2021)
- [Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm](https://mlsanity.com/paper/1403.7721/) (2014)
- [Spectral Alignment of Graphs](https://mlsanity.com/paper/1602.04181/) (2016)
- [Spectral Alignment of Correlated Gaussian matrices](https://mlsanity.com/paper/1912.00231/) (2019)
- [Graph Matching via convex relaxation to the simplex](https://mlsanity.com/paper/2310.20609/) (2023)
- [On the Exactness of SDP Relaxation for Quadratic Assignment Problem](https://mlsanity.com/paper/2408.05942/) (2024)

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

- [Sharp Statistical Thresholds for Attributed Gaussian Graph Matching](https://mlsanity.com/paper/2603.23305/) (2026)
- [Phase Transition in Convex Relaxations for Graph Alignment](https://mlsanity.com/paper/2606.15581/) (2026)

## Abstract (arXiv)

We consider the graph alignment problem, wherein the objective is to find a vertex correspondence between two graphs that maximizes the edge overlap. The graph alignment problem is an instance of the quadratic assignment problem (QAP), known to be NP-hard in the worst case even to approximately solve. In this paper, we analyze Birkhoff relaxation, a tight convex relaxation of QAP, and present theoretical guarantees on its performance when the inputs follow the Gaussian Wigner Model. More specifically, the weighted adjacency matrices are correlated Gaussian Orthogonal Ensemble with correlation 1/√1+σ2. Denote the optimal solutions of the QAP and Birkhoff relaxation by Pi^star and X^star respectively. We show that |X^star-Pi^star|F2 = o(n) when σ = o(n-1.25) and |X^star-Pi^star|F2 = Omega(n) when σ = Omega(n-0.5). Thus, the optimal solution X^star transitions from a small perturbation of Pi^star for small σ to being well separated from Pi^star as σ becomes larger than n-0.5. This result allows us to guarantee that simple rounding procedures on X^star align 1-o(1) fraction of vertices correctly whenever σ = o(n-1.25). This condition on σ to ensure the success of the Birkhoff relaxation is state-of-the-art.