Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests

• URL: http://arxiv.org/abs/2607.09087v2
• Date: Tue, 14 Jul 2026 16:07:44 GMT
• Title: Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests
• Abstract summary: This paper studies graph matching under the correlated $textErds-Rényi$ (ER) graph pair model.<n>We propose a graph matching algorithm that has $n2+o(1)$ time complexity and achieves almost exact recovery.
• Score: 27.444325804941773
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 tree-counting constant. This is the first algorithm with almost quadratic time complexity in this regime of $λ$, while the best known result in this regime is the chandelier-counting algorithm with time complexity $O(n^{c(s)})$, where $c(s)\rightarrow \infty$ as $s$ approaches $\sqrt{C_\mathrm{Otter}}$ from above. The proposed algorithm is based on local tree correlation tests. It uses a rank-based algorithm to match the vertex pairs instead of threshold-based rules in the literature. This avoids the need of computing an explicit threshold, which is computationally difficult to obtain. To prove the almost exact recovery result, we establish a new analysis of tree correlation tests in the diverging-degree regime, where both the mean degree and the tree depth grow with $n$. Based on this new result, we establish the existence of a threshold for a threshold-based graph matching algorithm via local tree correlation tests. Finally, we couple the performance of the rank-based algorithm with the threshold-based algorithm to show almost exact recovery.

Related papers

• High-Dimensional Procrustes Matching via Tree Counts [5.464035038606368]
  Procrustes matching problem asks us to recover the unknown permutation of $[n]$ that aligns the two sets.<n>We show that exact recovery is possible when $2 gtrsim maxlog n/d,sqrtlog n/n$.<n>We also carry out a low-degree advantage calculation, which suggests that condition $2 > sqrt$ is necessary for any tree-counting algorithm.
  arXiv  Detail & Related papers  (2026-07-09T14:33:47Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  We present two quantum algorithms that produce the normalized solution $|xrangle$ of linear system $Ax=| b rangle$ to accuracy $$ with complexity independent of the condition number $=lVert A-1rVert$.<n>Our filtering-based solver is extremely simple with a favorable runtime prefactor.
  arXiv  Detail & Related papers  (2026-07-08T17:49:40Z)
• Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
  This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank computation.<n>We show that the time complexity of such localized methods is upper bounded by $mintildemathcalO(R2/epsilon2), tildemathcalO(m)$ to obtain an $epsilon$-approximation of the PPR vector.
  arXiv  Detail & Related papers  (2025-10-09T09:47:40Z)
• A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation [12.869436542291144]
  We propose an efficient algorithm for matching two correlated ErdHos--R'enyi graphs with $n$ whose edges are correlated through a latent correspondence. Our algorithm has running time and succeeds to recover the latent matching as long as the edge correlation is non-vanishing.
  arXiv  Detail & Related papers  (2023-06-01T00:58:50Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach [9.13755431537592]
  In this paper, we reduce the complexity of approximating the correlation clustering problem from $O(mtimesleft( 2+ alpha (G) right)+n)$ to $O(m+n)$ for any given value of $varepsilon$ for a complete signed graph. Our approach gives the same output as the original algorithm and makes it possible to implement the algorithm in a full dynamic setting.
  arXiv  Detail & Related papers  (2023-01-01T10:57:36Z)
• Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
  We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each. This is the first graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs.
  arXiv  Detail & Related papers  (2022-09-25T20:00:28Z)
• Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
  Kawarabayashi and Thorup gave a near-trivial time deterministic algorithm for minimum cut in a simple graph $G = (V,E)$. We give a near-linear time randomized algorithm to find the $(1+varepsilon)$-KT partition of a weighted graph.
  arXiv  Detail & Related papers  (2021-11-02T05:26:10Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
  arXiv  Detail & Related papers  (2021-06-16T03:34:14Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  We propose a new algorithm for graph matching under probabilistic models. Our algorithm recovers the underlying matching with high probability when $alpha le 1 / (log log n)C$. This improves the condition $alpha le 1 / (log n)C$ achieved in previous work.
  arXiv  Detail & Related papers  (2021-01-28T02:39:27Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.