{"id":"arxiv/2607.09087","url":"https://arxiv.org/abs/2607.09087","tags":["cs.DS","math.ST","stat.ML"],"score":0,"title":"Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests","domain":"cs.DS","source":"arxiv","authors":["Jiale Cheng","Ziao Wang","Lei Ying"],"reviews":0,"subject":"cs.DS","summary":"This paper studies graph matching under the correlated $\\text{Erdős-Rényi}$ (ER) graph pair model. This model first samples an $\\mathrm{ER}(n,\\fracλ{ns})$ base graph, whose edges are then independently subsampled twice with probability $s$ to produce two correlated $\\mathrm{ER}(n,\\fracλ{n})$ graphs. We propose a graph matching algorithm that has $n^{2+o(1)}$ time complexity and achieves almost exact recovery with high probability under the assumptions $λ=(\\log n)^{α+o(1)}$ for some $α\\in(0,1)$ and $s\\in(\\sqrt{C_{\\mathrm{Otter}}},1]$, where $C_{\\mathrm{Otter}}\\approx 0.338$ is Otter's…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-10","reactions":{}}