EUVIMEDEUVIMED entdecken
Crossref

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

Zhangsong Li

IEEE Transactions on Information Theory · 2026-08 · 72 (8) · 6093-6111

DOI: 10.1109/tit.2026.3702566 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-08. Verfasst von Zhangsong Li. Die Arbeit nennt 81 Literaturangaben. Gefördert von: National Key Research and Development Program of China, NSFC Key Program.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 = o\left ({ \tfrac {1}{(\log n)^{20}}}\right)$ . 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 Ding and Li (2025) and the spectral preprocessing procedure proposed in Ivkov and Schramm (2025). 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.

Förderung

  • National Key Research and Development Program of China
  • NSFC Key Program

Zitieren

APA

Li, Z. (2026). Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm. IEEE Transactions on Information Theory, 72(8), 6093-6111. https://doi.org/10.1109/tit.2026.3702566

Vancouver

Li Z. Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm. IEEE Transactions on Information Theory. 2026;72(8):6093-6111. doi:10.1109/tit.2026.3702566

BibTeX
@article{Li2026,
  author = {Li, Zhangsong},
  title = {Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm},
  journal = {IEEE Transactions on Information Theory},
  year = {2026},
  volume = {72},
  number = {8},
  pages = {6093--6111},
  doi = {10.1109/tit.2026.3702566}
}
Kostenlos starten →