Robust random graph matching in Gaussian models via vector approximate message passing

Abstract

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 n * 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 between (A,B) is a non-vanishing constant and = o( 1( n)^20 ). The main methodological inputs for our result are the iterative random graph matching algorithm proposed in DL22+, DL23+ and the spectral cleaning procedure proposed in 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.

Tasks

Reproductions