그래프 정렬(Graph Alignment)을 위한 볼록 완화(Convex Relaxations)에서의 상전이(Phase Transition)

우리는 상관관계가 있는 가우시안 직교 앙상블 (Gaussian Orthogonal Ensemble (GOE)) 행렬에 대한 그래프 정렬 (graph alignment) 문제를 연구합니다. 이 문제의 목표는 상관관계가 $1/\sqrt{1+σ^2}$인 두 개의 상관된 대칭 가우시안 행렬 $(A, B)$가 주어졌을 때, 숨겨진 정점 치환 (vertex permutation)을 복구하는 것입니다. 최대 우도 추정량 (maximum likelihood estimator)은 정보 이론적으로 최적이지만, 이차 할당 문제 (quadratic assignment problem)로 귀결되는 그 계산 과정은 다루기 어렵습니다 (intractable). 이에 착안하여, 우리는 이중 확률 행렬 (doubly stochastic matrices) 집합과 단위 하이퍼큐브 (unit hypercube) 상에서 $|AX - XB|_F$를 최소화하는 것에 기반한 볼록 완화 (convex relaxations)를 분석합니다. 상관관계 파라미터가 $\sigma= o(n^{-1/2}/\log^4 n)$을 만족할 때, 두 완화 방식 중 어느 것이든 그 해 $(X^\star)$는 실제 정답 치환 행렬 (ground-truth permutation matrix) $(Π^\star)$ 주변으로 집중됨을 보여줍니다. 즉, $|X^\star-Π^\star|_F^2 = o(n)$이며, 이는 간단한 후처리 (post-processing)를 거친 후 소멸하는 비율을 제외한 모든 정점을 복구할 수 있음을 의미합니다. 기존의 하한 (lower bounds)과 결합하여, 우리의 결과는 $|X^\star-Π^\star|_F^2$가 $\sigma= \tilde{o}(n^{-1/2})$일 때 $o(n)$에서 $\sigma= \tilde{\Omega}(n^{-1/2})$일 때 $\Omega(n)$으로 전이됨을 정확하게 규명합니다. 이 과정에서 우리의 분석은 기존 결과들을 크게 강화하며, 이중 확률 완화 (doubly stochastic relaxations)를 넘어 그 범위를 확장합니다.