Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing
Abstract
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 λ 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>√(COtter), where COtter≈0.338 is Otter's tree-counting constant, and every λ=ω(1) with λ=(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, λs≥(1+ε)log n for a constant ε>0, a seeded completion step recovers the permutation exactly. In both cases, the time complexity of the algorithm is n2+o(1) with high probability, whereas previous polynomial-time algorithms with the same guarantees either have a time-complexity bound whose exponent goes to ∞ as s approaches √(COtter) from above, or apply only when s is close to $1$.
Related
- Quantitative Universality of Approximate Message Passing for Rank-One Quadratic Sensing
- Kurdyka-Łojasiewicz-based convergence analysis with approximate weakly convex subdifferentials: bundle, quadratic penalty, and moving balls approximation methods
- Matrix-Free Moment-Matching Method for Reduced-Order Modeling of Quadratic-Bilinear Descriptor Systems with Multiple Inputs
- The exact dimensional threshold for Spearman rank-correlation compatibility
- Fluctuations of the quadratic matching cost on the flat torus: dimensions five and higher
BibTeX
@misc{cheng2026nearquadratic,
title = {{Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing}},
author = {Jiale Cheng and Ziao Wang and Lei Ying},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02281},
eprint = {2611.02281},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02281},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing
AU - Jiale Cheng
AU - Ziao Wang
AU - Lei Ying
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.02281
UR - https://arxiv.org/abs/2611.02281
AB - 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 λ 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>√(C_Otter), where C_Otter≈0.338 is Otter's tree-counting constant, and every λ=ω(1) with λ=(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, λs≥(1+ε)log n for a constant ε>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 ∞ as s approaches √(C_Otter) from above, or apply only when s is close to $1$.
ER -