Spectral Alignment of Correlated Gaussian matrices
Preprint
Abstract
In this paper we analyze a simple spectral method (EIG1) for the problem of matrix alignment, consisting in aligning their leading eigenvectors: given two matrices $A$ and $B$, we compute $v_1$ and $v'_1$ two corresponding leading eigenvectors. The algorithm returns the permutation $\hat{\pi}$ such that the rank of coordinate $\hat{\pi}(i)$ in $v_1$ and that of coordinate $i$ in $v'_1$ (up to the sign of $v'_1$) are the same. We consider a model of weighted graphs where the adjacency matrix $A$ belongs to the Gaussian Orthogonal Ensemble (GOE) of size $N \times N$, and $B$ is a noisy version of $A$ where all nodes have been relabeled according to some planted permutation $\pi$, namely $B= \Pi^T (A+\sigma H) \Pi $, where $\Pi$ is the permutation matrix associated with $\pi$ and $H$ is an independent copy of $A$. We show the following zero-one law: with high probability, under the condition $\sigma N^{7/6+\epsilon} \to 0$ for some $\epsilon>0$, EIG1 recovers all but a vanishing part of the underlying permutation $\pi$, whereas if $\sigma N^{7/6-\epsilon} \to \infty$, this method cannot recover more than $o(N)$ correct matches. This result gives an understanding of the simplest and fastest spectral method for matrix alignment (or complete weighted graph alignment), and involves proof methods and techniques which could be of independent interest.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Efficient random graph matching via degree profilesProbability Theory and Related Fields, 2020
- Eigenvectors of random matrices: A surveyJournal of Combinatorial Theory, Series A, 2016
- Rigidity of eigenvalues of generalized Wigner matricesAdvances in Mathematics, 2012
- Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm2010
- Global alignment of multiple protein interaction networks with application to functional orthology detectionProceedings of the National Academy of Sciences, 2008
- THIRTY YEARS OF GRAPH MATCHING IN PATTERN RECOGNITIONInternational Journal of Pattern Recognition and Artificial Intelligence, 2004
- Correlation Functions, Cluster Functions, and Spacing Distributions for Random MatricesJournal of Statistical Physics, 1998
- The quadratic assignment problem: A survey and recent developments1994
- The spectrum edge of random matrix ensemblesNuclear Physics B, 1993