Exact recovery for seeded graph matching
Nicolas Fraiman, Michael Nisenzon · 2026
Read Exact recovery for seeded graph matching by Nicolas Fraiman, Michael Nisenzon (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-06832.txt.
Description
Nicolas Fraiman and Michael Nisenzon study graph matching when almost all of the answer is already given. Two correlated networks share a hidden correspondence between their vertices, and all but a vanishing fraction of those correspondences are revealed as seeds. The question is when the remaining matches can be recovered exactly and efficiently.
For correlated stochastic block models, the authors prove that polynomial-time recovery succeeds whenever a simple inequality holds, linking the network density, the edge retention rate, and the fraction of unrevealed vertices. The condition smoothly bridges the fully seeded case and the classic unseeded threshold. Below the same threshold, recovery is impossible even in principle. Both a simple neighborhood-overlap rule and a relaxed optimization method achieve the bound, giving the first tight characterization of this nearly seeded regime.
Catalog record
| CREATOR | Nicolas Fraiman, Michael Nisenzon |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-06832