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

Jul 16, 2026

Upload by Skyler

Graph matching is studied under the correlated Erdős–Rényi (ER) graph pair model, where an initial ER base graph is generated and then two correlated ER graphs are formed by independent edge subsampling. A rank-based matching algorithm is proposed with n^2+o(1) time complexity that achieves almost exact recovery with high probability for λ=(log n)^α+o(1) (α∈(0,1)) and s in (√cOtter,1]. The method uses local tree correlation tests, avoids explicit threshold computation, and relies on a new analysis for diverging-degree regimes.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages62

Reading Time2 h 36 min

Abstract

I. Introduction

II. Related Work

A. Information-theoretic limits and polynomial-time algorithms for CER(n,λ,s)

1 arXiv :2607 .09087v 1 [ cs .DS] 10 Jul 2026 Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests Jiale Cheng∗ , Ziao Wang∗ and Lei Ying Abstract This paper studies graph matching under the correlated Erds–Rnyi (ER) graph pair model. This model first samples an ER(n, ~~λ~~ns ) base graph, whose edges are then independently subsampled twice with probability s to produce two correlated ER(n, ~~λ~~n) graphs. We propose a graph matching algorithm that has n2+o(1) time complexity and achieves almost exact recovery with high probability under the assumptions λ = (log n)α+o(1) for some α ∈ (0 , 1) and s ∈ ( √COtter , 1], where COtter ≈ 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 (nc (s) ), where c(s) → ∞ as s approaches √COtter 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. I. INTRODUCTION Graph matching, also known as network alignment or noisy graph isomorphism, is the problem of recovering the latent correspondence between the vertices of two correlated graphs. A classical motivation for the problem comes from social network deanonymization [1, 2], where one attempts to identify the user correspondence between an anonymized social network (e.g. Twitter) and a reference social network (e.g. LinkedIn) for which the user identities are publicly available. Similar correspondence-recovery applications appear in various other fields including bioinformatics [3], computer vision [4], and natural language processing [5] . In general, the standard optimization formulation of graph matching can be viewed as a special case of the quadratic assignment problem (QAP) [6], which is known to be NPhard to solve or even approximate [7] . This worst-case computational barrier has motivated a line of work studying graph matching assuming some random graph generative models such as the correlated Erds–Rnyi graph pair model [8] . Under the correlated Erds–Rnyi graph pair model, denoted by CER(n,λ, s), a base Erds–Rnyi graph with n vertices is first generated where edges between vertex pairs are generated independently with probability ~~λ~~ns . Two Erds–Rnyi graphs, both with marginal distribution ER(n,λ/n), are then subsequently generated by independently subsampling each edge in the base graph with probability s, the edge correlation parameter. The goal is to find the latent vertex correspondence between the two graphs without observing their true identities. ∗ Jiale Cheng and Ziao Wang contributed equally to this work. Jiale Cheng is with the Department of Electrical and Computer Engineering, University of Michigan, Ann Arbor, MI 48109, USA ([email:jlcheng@umich.edu](email:jlcheng@umich.edu)). Ziao Wang is with the Department of Electrical and Computer Engineering, University of Michigan, Ann Arbor, MI 48109, USA (email: [ziaow@umich.edu](ziaow@umich.edu)) . Lei Ying is with the Department of Electrical and Computer Engineering, University of Michigan, Ann Arbor, MI 48109, USA (email: [leiying@umich.edu](leiying@umich.edu)). Parameter s Fig. 1: Comparison of the time-complexity exp

FAQs

What is the correlated Erdős–Rényi (CER) graph pair model used in this work?

A base ER(n, λ/n) graph is generated and each edge is independently subsampled twice with probability s to produce two correlated ER graphs with marginal distribution ER(n, λ/n). The correlation is induced by subsampling the same base edges.

What recovery guarantee does the proposed algorithm provide?

The algorithm achieves almost exact recovery with high probability, meaning the vertex correspondence is recovered for all but a vanishing fraction of vertices in the almost exact recovery regime.

How does the algorithm differ from threshold-based approaches?

It uses rank-based local tree correlation tests to match vertex pairs without computing an explicit threshold, which the paper notes is computationally difficult to obtain. It further couples the rank-based performance with a threshold-based analysis to prove the result.

Jul 16, 2026

Upload by Skyler