COLT 2026 paper proves sharp phase transition for graph alignment
The precise threshold for solving graph alignment with convex relaxations is now known.
Graph alignment—recovering a hidden vertex permutation between two correlated graphs—is fundamental in network science but computationally hard in the worst case. In this paper, Massoulié et al. study a planted version using correlated Gaussian Orthogonal Ensemble (GOE) matrices, where the goal is to align two symmetric Gaussian matrices A and B with correlation 1/√(1+σ²). The maximum likelihood estimator reduces to a quadratic assignment problem, which is intractable. Instead, they analyze two convex relaxations: minimizing ‖AX - XB‖_F over the set of doubly stochastic matrices or over the unit hypercube.
The authors prove that when σ is small (specifically, σ = o(n^{-1/2}/log^4 n)), the optimal solution X* of either relaxation concentrates around the true permutation matrix Π*, with squared Frobenius error o(n). This implies that after simple post-processing, all but a vanishing fraction of vertices can be correctly matched. Moreover, they show that this condition is tight: when σ is larger (Ω(n^{-1/2})), the error becomes Ω(n), meaning no meaningful recovery. This sharp phase transition significantly tightens prior bounds and extends them beyond doubly stochastic relaxations. The work provides a precise theoretical characterization of when convex methods succeed for graph alignment, with implications for spectral algorithms and network analysis.
- Convex relaxations for graph alignment (doubly stochastic or hypercube) succeed when σ = o(n^{-1/2}/log^4 n).
- The squared Frobenius error transitions from o(n) to Ω(n) at the threshold σ ~ n^{-1/2}.
- Paper accepted at COLT 2026, tightens previous results and extends to more general relaxations.
Why It Matters
Provides a precise criterion for when graph alignment can be solved efficiently via convex optimization.