Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm

arXiv:2412.16457v3 Announce Type: replace-cross 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 epsilon n * epsilon n principal minor of A,B, respectively. We propose an approximate message passing (AMP) type iterative algorithm that succeeds in polynomial time as long as the correlation rho between (A,B) is a non-vanishing constant and epsilon = oig( frac{1}{(log n)^{20}} ig). A key distinction from standard AMP is the introduction of a time-dependent matrix multiplication step within the iteration, which simultaneously enlarges the feature dimension and cancels the correlation during the iteration. The main methodological inputs for our result are the iterative random graph matching algorithm proposed in ite{DL22+, DL23+} and the spectral preprocessing procedure proposed in ite{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.

Source: arXiv cs.LG | 2026-06-09