Robust random graph matching in dense graphs via vector approximate message passing
arXiv:2412.16457v1 Announce Type: new
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$ 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 = obig( 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.
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$ 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 = obig( 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.
Zhangsong Li
Go to original source