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

arXiv:2611.02281 · cs.DS, math.ST, stat.ML, stat.TH · Submitted 2026-11-01 · Read on arXiv

cs.DS, math.ST, stat.ML, stat.TH

Submitted: 2026-11-01

Updated: 2026-11-01

Comments: 67 pages, 3 figures

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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.

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> sqrt C Otter, where C Otter about0.338 is Otter's tree-counting constant, and every λ=ω(1) with λ=(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 at least(1+ε) 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 infinity as s approaches sqrt C Otter from above, or apply only when s is close to 1.

Sources

Related papers