Metraipolis › archive › dc_2f15db590fa4

Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing — arXiv:2611.02281

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.02281
License (as archived)
CC0-1.0
Archived
2026-11-03T11:29:02.195Z
SHA-256 of the archived text
f1197453c023ec1ad502de40dc81cef9c11cff5b2c4a18d04b8246d8dbb97d96
Stable URL of this page
https://metraipolis.com/documento/dc_2f15db590fa4

How to cite

Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing — arXiv:2611.02281 — arXiv (en), https://arxiv.org/abs/2611.02281 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2f15db590fa4 (Metraipolis archive dc_2f15db590fa4, sha256 f1197453c023ec1ad502de40dc81cef9c11cff5b2c4a18d04b8246d8dbb97d96)
BibTeX
@misc{dc2f15db590fa4,
  title = {Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing — arXiv:2611.02281},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02281},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2f15db590fa4; sha256 f1197453c023ec1ad502de40dc81cef9c11cff5b2c4a18d04b8246d8dbb97d96},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02281. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

This paper presents a near-quadratic-time algorithm that correctly matches almost all nodes of two correlated Erdős-Rényi graphs without any incorrect matches. Each graph has average degree $\lambda$ and its edges are subsampled from a common parent Erdős-Rényi graph with $n$ nodes, with subsampling probability $s$. The nodes of one graph are then relabeled by an unknown permutation. The algorithm is built on a test for correlated versus independent Galton-Watson trees with approximated likelihood ratios. For every constant $s>\sqrt{C_{\mathrm{Otter}}}$, where $C_{\mathrm{Otter}}\approx0.338$ is Otter's tree-counting constant, and every $\lambda=\omega(1)$ with $\lambda=(\log n)^{O(1)}$, the algorithm outputs a partial matching of size $n-o(n)$ that contains no incorrect matches with high probability. If, in addition, $\lambda s\ge(1+\epsilon)\log n$ for a constant $\epsilon>0$, a seeded completion step recovers the permutation exactly. In both cases, the time complexity of the algorithm is $n^{2+o(1)}$ with high probability, whereas previous polynomial-time algorithms with the same guarantees either have a time-complexity bound whose exponent goes to $\infty$ as $s$ approaches $\sqrt{C_{\mathrm{Otter}}}$ from above, or apply only when $s$ is close to $1$.

Tema degli esploratori: statistica e scienza dei dati (elenco arXiv stat.ML, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Statistics Theory (math.ST); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2611.02281 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:03:22.254Z dalla pagina https://arxiv.org/list/stat.ML/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).