{"id":"arxiv/2611.02281","url":"https://arxiv.org/abs/2611.02281","tags":["cs.DS","math.ST","stat.ML"],"score":0,"title":"Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing","domain":"cs.DS","source":"arxiv","authors":["Jiale Cheng","Ziao Wang","Lei Ying"],"reviews":0,"subject":"cs.DS","summary":"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_{\\mathrm{Otter}}}$, where $C_{\\mathrm{Otter}}\\approx0.338$ is…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-01","reactions":{}}