Robust random graph matching in Gaussian models via vector approximate message passing
This addresses a robust version of graph matching for theoretical computer science and network analysis, with incremental improvements in handling adversarial perturbations.
The paper tackles the problem of robust random graph matching between correlated Gaussian Wigner matrices with adversarial perturbations, proposing a vector approximate message passing algorithm that succeeds in polynomial time for non-vanishing correlation and perturbations up to size o(1/(log n)^20).
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\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.