In this paper, we focus on the matching recovery problem between a pair of correlated Gaussian Wigner matrices with a latent vertex correspondence. We are particularly interested in a robust version of this problem such that our observation is a perturbed input $(A+E,B+F)$ where $(A,B)$ is a pair of correlated Gaussian Wigner matrices and $E,F$ are adversarially chosen matrices supported on an unknown $\epsilon n * \epsilon n$ principle minor of $A,B$, respectively. We propose a vector approximate message passing (vector AMP) algorithm that succeeds in polynomial time as long as the correlation $\rho$ between $(A,B)$ is a non-vanishing constant and $\epsilon = o\big( \tfrac{ 1}{ (\log n)^{ 20}} \big)$. The main methodological inputs for our result are the iterative random graph matching algorithm proposed in \cite{ DL22+, DL23+} and the spectral cleaning procedure proposed in \cite{ IS24+}. To the best of our knowledge, our algorithm is the first efficient random graph matching type algorithm that is robust under any adversarial perturbations of $n^{ 1-o(1)}$ size.
Categories: stat.ML cs.DS cs.LG math.PR math.ST stat.TH
