REVIEW 2 major objections
A rank-based local tree-correlation matcher recovers almost all vertices of correlated ER graphs in almost quadratic time for sparse degrees that grow as a fractional power of log n.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · grok-4.5
2026-07-15 09:40 UTC pith:JWJIFYH5
load-bearing objection First claimed n^{2+o(1)} almost-exact recovery for polylog-degree correlated ER matching via rank-based tree tests, but the whole result hangs on an unchecked diverging-degree separation analysis. the 2 major comments →
Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
A rank-based algorithm that matches vertices by the relative ranks of their local tree-correlation scores achieves almost exact recovery with high probability in n^{2+o(1)} time under the correlated ER model when λ = (log n)^{α+o(1)} for α ∈ (0,1) and s ∈ (√C_Otter, 1], the first almost-quadratic-time algorithm for this regime.
What carries the argument
Local tree correlation tests: for each candidate vertex pair the algorithm counts the number of rooted trees of carefully chosen depth that appear in the neighborhoods of both vertices; a rank-based rule then matches pairs by the ordering of these scores instead of comparing them to an explicit numerical threshold.
Load-bearing premise
The new separation analysis for tree-correlation scores continues to hold when both the average degree and the tree depth grow with n, so that a usable (though possibly non-constructive) threshold still exists and the rank-based procedure can be coupled to it.
What would settle it
For concrete parameters λ = (log n)^{1/2} and s = 0.7, compute the fraction of unmatched vertices produced by the rank-based tree-correlation algorithm on many independent n-vertex instances; if that fraction fails to tend to zero as n o ∞, the almost-exact recovery claim is false.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript studies graph matching in the correlated Erdős–Rényi model (base ER(n, λ/(n s)) with independent edge retention probability s). It proposes a rank-based algorithm that matches vertices via local tree-correlation statistics and claims almost-exact recovery with high probability in n^{2+o(1)} time whenever λ = (log n)^{α+o(1)} for some α ∈ (0,1) and s ∈ (√C_Otter, 1], where C_Otter ≈ 0.338 is Otter’s constant. The argument proceeds by first establishing a new separation analysis for tree-correlation tests in the regime where both mean degree and tree depth diverge with n, then asserting the existence of a threshold for a classical threshold-based matcher, and finally coupling the rank-based procedure to that threshold-based matcher.
Significance. If the claimed separation and coupling hold, the result would be the first almost-quadratic-time algorithm achieving almost-exact recovery in the intermediate-sparsity window λ = (log n)^{α+o(1)}. Prior work in the same regime (chandelier counting) incurs a polynomial exponent that diverges as s ↓ √C_Otter; an n^{2+o(1)} algorithm would therefore constitute a genuine complexity improvement while remaining information-theoretically near-optimal with respect to Otter’s constant. The rank-based formulation, which avoids explicit threshold computation, is also of practical interest. These strengths, however, rest entirely on the new diverging-degree tree-correlation analysis, which cannot be inspected from the abstract alone.
major comments (2)
- The abstract’s almost-exact-recovery claim for the rank-based algorithm is not self-contained: it first requires a uniformly positive separation between the distributions of the local tree-correlation statistic on true versus false pairs under the simultaneous regime λ = (log n)^{α+o(1)} and tree depth ω(1). Only after that separation is established does the paper assert existence of a threshold for a classical threshold-based matcher; the rank-based procedure is then coupled to the latter. Because both mean degree and depth diverge, standard fixed-degree/fixed-depth concentration and moment calculations no longer apply directly; any error terms that grow with λ or depth could erase the separation above the Otter threshold. The abstract asserts that a “new analysis” supplies the needed separation but supplies neither the statement of the separation lemma nor the error-control arguments.
- Even granting the separation, the coupling argument that transfers almost-exact recovery from the (non-constructive) threshold-based matcher to the rank-based algorithm must control the probability that the ranking induced by the tree-correlation scores differs from the threshold decision on a non-vanishing fraction of vertices. The abstract gives no quantitative statement of this coupling (e.g., how the rank gaps relate to the separation width, or how many false pairs can outrank true pairs). This step is essential for the final high-probability claim and likewise cannot be assessed from the abstract alone.
Circularity Check
No significant circularity: asymptotic recovery claim under external correlated-ER model; rank-based guarantee obtained by coupling to a threshold-based matcher whose existence rests on a new (non-circular) separation analysis.
full rationale
The abstract presents a purely theoretical derivation under the externally defined correlated Erdős–Rényi generative model. There is no parameter fitting to data, no free constant tuned so that a recovery rate is forced, and no quantity that is defined in terms of the algorithm’s own output and then re-presented as a prediction. The load-bearing chain is: (i) a new concentration/separation analysis of local tree-correlation statistics when both mean degree λ and tree depth diverge, (ii) existence of a threshold for a classical threshold-based matcher implied by that separation, and (iii) a coupling argument that transfers almost-exact recovery from the threshold-based matcher to the proposed rank-based procedure. None of these steps reduces by construction to its own input; each is a probabilistic claim that must be proved. Because only the abstract is available, residual self-citation risk cannot be audited, but nothing in the visible text exhibits self-definitional circularity, fitted-input-as-prediction, or load-bearing uniqueness imported solely from the authors’ prior work. The skeptic’s concern about the new analysis is a correctness-risk issue (whether the separation remains positive), not a circularity issue. Hence the circularity score is minimal.
Axiom & Free-Parameter Ledger
axioms (3)
- domain assumption Correlated ER pair generated by independent edge subsampling with probability s from a common ER(n,λ/(ns)) base graph.
- domain assumption Local tree neighborhoods of growing depth remain sufficiently tree-like and their correlation statistics concentrate enough to separate true pairs from false pairs when λ and depth both diverge.
- standard math Otter’s tree-counting constant C_Otter ≈ 0.338 is the correct combinatorial threshold for the growth of unlabeled trees.
read the original abstract
This paper studies graph matching under the correlated $\text{Erd\H{o}s-R\'{e}nyi}$ (ER) graph pair model. This model first samples an $\mathrm{ER}(n,\frac{\lambda}{ns})$ base graph, whose edges are then independently subsampled twice with probability $s$ to produce two correlated $\mathrm{ER}(n,\frac{\lambda}{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 $\lambda=(\log n)^{\alpha+o(1)}$ for some $\alpha\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 $\lambda$, 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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.