Phase Transition in Convex Relaxations for Graph Alignment

Laurent Massoulié, Sushil Mahavir Varma, Louis Vassaux, Irène Waldspurger
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4999-5020, 2026.

Abstract

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/\sqrt{1+\sigma^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 $\sigma = o(n^{-1/2}/\log^4 n)$, the solution of either relaxation ($X^\star$) concentrates around the ground-truth permutation matrix ($\Pi^\star$), i.e., $\|X^\star - \Pi^\star\|_F^2 = 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\|_F^2$ transitions from $o(n)$ for $\sigma = \tilde{o}(n^{-1/2})$ to $\Omega(n)$ for $\sigma = \tilde{\Omega}(n^{-1/2})$. In doing so, our analysis significantly tightens prior results and extends them beyond doubly stochastic relaxations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-massoulie26a, title = {Phase Transition in Convex Relaxations for Graph Alignment}, author = {Massouli\'e, Laurent and Varma, Sushil Mahavir and Vassaux, Louis and Waldspurger, Ir\`ene}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {4999--5020}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/massoulie26a/massoulie26a.pdf}, url = {https://proceedings.mlr.press/v336/massoulie26a.html}, abstract = {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/\sqrt{1+\sigma^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 $\sigma = o(n^{-1/2}/\log^4 n)$, the solution of either relaxation ($X^\star$) concentrates around the ground-truth permutation matrix ($\Pi^\star$), i.e., $\|X^\star - \Pi^\star\|_F^2 = 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\|_F^2$ transitions from $o(n)$ for $\sigma = \tilde{o}(n^{-1/2})$ to $\Omega(n)$ for $\sigma = \tilde{\Omega}(n^{-1/2})$. In doing so, our analysis significantly tightens prior results and extends them beyond doubly stochastic relaxations.} }
Endnote
%0 Conference Paper %T Phase Transition in Convex Relaxations for Graph Alignment %A Laurent Massoulié %A Sushil Mahavir Varma %A Louis Vassaux %A Irène Waldspurger %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-massoulie26a %I PMLR %P 4999--5020 %U https://proceedings.mlr.press/v336/massoulie26a.html %V 336 %X 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/\sqrt{1+\sigma^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 $\sigma = o(n^{-1/2}/\log^4 n)$, the solution of either relaxation ($X^\star$) concentrates around the ground-truth permutation matrix ($\Pi^\star$), i.e., $\|X^\star - \Pi^\star\|_F^2 = 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\|_F^2$ transitions from $o(n)$ for $\sigma = \tilde{o}(n^{-1/2})$ to $\Omega(n)$ for $\sigma = \tilde{\Omega}(n^{-1/2})$. In doing so, our analysis significantly tightens prior results and extends them beyond doubly stochastic relaxations.
APA
Massoulié, L., Varma, S.M., Vassaux, L. & Waldspurger, I.. (2026). Phase Transition in Convex Relaxations for Graph Alignment. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:4999-5020 Available from https://proceedings.mlr.press/v336/massoulie26a.html.

Related Material