arXiv Machine Learning
Jun 16

Phase Transition in Convex Relaxations for Graph Alignment

arXiv:2606. 15581v1 Announce Type: cross 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}$.

By Laurent Massouli\'e, Sushil Mahavir Varma, Louis Vassaux, Ir\`ene Waldspurger