# Phase Transition in Convex Relaxations for Graph Alignment

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 20 references that are in the map.
- First posted on arXiv 14 Jun 2026.

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

- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [Graph Matching: Relax at Your Own Risk](https://mlsanity.com/paper/1405.3133/) (2014)
- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [Sharp threshold for alignment of graph databases with Gaussian weights](https://mlsanity.com/paper/2010.16295/) (2020)
- [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 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)
- [Graph Alignment via Birkhoff Relaxation](https://mlsanity.com/paper/2503.05323/) (2025)

## Abstract (arXiv)

We study the graph alignment problem for correlated Gaussian Orthogonal Ensemble (GOE) matrices, where the goal is to recover a hidden vertex permutation given two correlated symmetric Gaussian matrices (A, B) with correlation 1/√1+σ2. While the maximum likelihood estimator is information-theoretically optimal, its computation, which reduces to a quadratic assignment problem, is intractable. Motivated by this, we analyze convex relaxations based on minimizing |AX - XB|F over the set of doubly stochastic matrices and the unit hypercube. We show that when the correlation parameter satisfies σ = o(n-1/2/log4 n), the solution of either relaxation (X^star) concentrates around the ground-truth permutation matrix (Pi^star), i.e., |X^star-Pi^star|F2 = o(n), implying recovery of all but a vanishing fraction of vertices after simple post-processing. Combined with existing lower bounds, our results precisely characterize that |X^star-Pi^star|F2 transitions from o(n) for σ = tildeo(n-1/2) to Omega(n) for σ = tildeOmega(n-1/2). In doing so, our analysis significantly tightens prior results and extends them beyond doubly stochastic relaxations.