揭示图对齐凸松弛解的相变现象，明确可恢复性边界。
Phase Transition in Convex Relaxations for Graph Alignment
- 用双重随机矩阵和超立方体约束的凸松弛求解图对齐问题。
- 当噪声参数σ < n⁻¹/²/log⁴n时，解与真实置换矩阵的误差平方为o(n)。
- 首次精确刻画恢复相变点，适合理论学习者和算法设计者参考。
我们研究相关高斯正交系综（GOE）矩阵下的图对齐问题，目标是在两个相关对称高斯矩阵 (A, B) 中恢复隐藏的顶点置换。最大似然估计虽信息论最优，但计算等价于难解的二次分配问题。为此，我们分析基于最小化‖AX - XB‖F 的凸松弛方法，约束在双重随机矩阵集和单位超立方体上。当相关参数满足σ = o(n⁻¹/²/log⁴n)时，任一松弛解X⋆在范数意义下集中在真实置换矩阵Π⋆附近，即‖X⋆ - Π⋆‖F² = o(n)，经简单后处理可恢复几乎所有顶点。结合已有下界，结果精确刻画了‖X⋆ - Π⋆‖F² 从σ = ᵒ̃(n⁻¹/²) 时的o(n) 跳变为 σ = Ω̃(n⁻¹/²) 时的Ω(n)。该分析显著收紧并拓展了此前结果，超越双重随机松弛范畴。
原文摘要 · Abstract (English)
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+σ^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}/\log^4 n)$, the solution of either relaxation $(X^\star)$ concentrates around the ground-truth permutation matrix $(Π^\star)$, i.e., $\|X^\star-Π^\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-Π^\star\|_F^2$ transitions from $o(n)$ for $σ= \tilde{o}(n^{-1/2})$ to $Ω(n)$ for $σ= \tildeΩ(n^{-1/2})$. In doing so, our analysis significantly tightens prior results and extends them beyond doubly stochastic relaxations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。