{"id":"832e21a5-a4e5-4726-abe2-662a857192eb","arxiv_id":"2607.09087","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A rank-based local-tree correlation algorithm recovers all but O(n/log n) vertex correspondences in correlated Erdős–Rényi graphs with λ=(log n)^{α+o(1)} and s>√C_Otter in n^{2+o(1)} time.","lead":"Two correlated random graphs can now be matched almost exactly in near-quadratic time across a wide correlation range, improving on earlier polynomial algorithms with degree-dependent exponents. The method ranks the similarity of local tree neighborhoods instead of using a hard-to-compute threshold.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3 hinges on transferring [29, Lemma B.1] moment bounds to a regime where both μ and k diverge; the paper does not re-derive this transfer, so a hidden dependence on bounded μ or k would collapse Theorems 1–2.","rationale":"The reader's weakest assumption identifies exactly the same point: the proof imports moment bounds from [29] and applies them where both the mean degree and the testing depth grow with n. I concur that this is the least secure link in the chain. The rest of the argument — the reduction from RBAlign to TBAlign, the acyclicity and degree-concentration lemmas, the Neyman–Pearson passage, and the time-complexity accounting — appears internally consistent and carefully executed. However, because Proposition 3, Theorem 3, and therefore Proposition 1 all depend on Lemma 11 being valid with uniform constants in the diverging regime, the central claim is conditional on that external lemma being transferable. The paper does not provide the proof of Lemma 11, only a citation, and the regime is explicitly outside the one where the cited work was previously applied. This does not mean the result is wrong; it means the correctness of the main theorem is contingent on a verification that the manuscript does not supply. I therefore recommend CONDITIONAL rather than unconditional ACCEPT: the result should be accepted only after the uniformity of Lemma 11 in μ and k is confirmed, either by reproducing [29, Lemma B.1] or by an independent derivation. The agreement is 'agree' because the reader's weakest assumption coincides with the load-bearing concern identified here.","tokens_in":57803,"tokens_out":39526,"duration_ms":361270,"concrete_test":"Independently re-derive Lemma 11's three moment bounds (106)–(108) for X_{k+1} from the Poisson branching process without invoking [29], in the regime μ = (log n)^{α+o(1)}, k up to d = (log n)^γ, with F_k an arbitrary subset of Z_k × Z_k satisfying Q(F_k) ≤ e^{d̄-k}C_1^{-1}. If the derived constants 36 and 13, or the variance prefactor 1+s^2, turn out to depend on k or μ, check whether the iterative inequality in Lemma 5 still holds at k = d − l. A concrete finite-n verification would be to simulate the auxiliary test Φ at n = 10^4, α = 0.5, γ = 0.8: compute F_k recursively and measure Q(F_{d-l}) and P(F_{d-l}); an observed deviation from the Proposition 3 bounds at large k would indicate the transfer fails.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim rests on Proposition 1, which uses Theorem 3 to obtain the threshold θ* and the auxiliary test Φ. Theorem 3 in turn rests on Proposition 3, whose proof is an induction using Lemma 5. Lemma 5's type-I and power bounds use Lemma 11, stated as the three moment bounds (106)–(108) and attributed to [29, Lemma B.1]. The paper explicitly says the baseline and boosting analysis 'follow the results established in [29]' but does not prove or adapt those bounds to the diverging regime. In the actual application, μ = λ = (log n)^{α+o(1)} diverges and the induction runs for all k up to d = (log n)^γ, with both α and γ in (0,1). If the constants 36 and 13 in (108), or the variance bound (107), degrade with k or μ — for example, if [29] proved them only for fixed μ or under an additional concentration condition — then the step Q(F_{k+1}) ≤ e^{d̄-k-1}C_1^{-1} and the lower bound P(F_{k+1}) ≥ max{1−10/(μs)−50Q(F_k)/s^2, 0.4} can fail. Once F_{d-l} no longer satisfies Proposition 3, the matching step in Φ loses its type-I and power guarantees, the Neyman–Pearson argument in Appendix A-F cannot produce θ*, and Proposition 1 — and therefore RBAlign's almost exact recovery — collapses. This is a genuine transfer-of-technique assumption, not an internal inconsistency: if [29, Lemma B.1] is indeed uniform in μ and k, the proof goes through, but that uniformity is precisely the part the manuscript does not establish.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies graph matching under the correlated Erdős–Rényi model CER(n,λ,s) with λ=(log n)^{α+o(1)}, α∈(0,1), and s∈(√C_Otter,1]. It proposes RBAlign, a rank-based algorithm built on local tree likelihood-ratio tests. The main claims (Theorems 1 and 2) are that RBAlign outputs a matrix with at least n−O(n/log n) correctly and uniquely matched vertices with probability 1−O(exp(−½(log n)^{α/2})), and runs in n^{2+o(1)} time with probability 1−o(e^{−n}). The proof route is: construct a threshold-based algorithm TBAlign; prove that a threshold θ* exists via an infeasible auxiliary tree-correlation test Φ and the Neyman–Pearson lemma; then couple the rank-based algorithm to TBAlign.","tokens_in":58261,"tokens_out":20776,"duration_ms":197893,"significance":"If the main theorems are correct, this is a substantial advance: it is the first algorithm with almost quadratic time achieving almost exact recovery in the sub-logarithmic degree regime, improving on the chandelier-counting algorithm whose exponent diverges as s approaches √C_Otter. The paper also contributes a new analysis of tree correlation tests in a diverging-degree regime, which may be of independent interest. The rank-based formulation that avoids computing an explicit threshold is conceptually elegant, and the paper is unusually detailed: it includes explicit complexity accounting, a construction of the tie-breaking map f, and machine-checkable-style appendices. These strengths are real. However, two load-bearing points are not fully established as written: the transfer of moment bounds from [29] to the diverging regime, and the tie-breaking comparison in the coupling lemma.","major_comments":[{"comment":"Proposition 3 and hence Theorem 3 rest on the three moment bounds (106)–(108) in Lemma 11, stated for 'any k≥1 and μ>1' and attributed to [29, Lemma B.1]. The application requires μ=λ=(log n)^{α+o(1)} and k up to d=(log n)^γ, both diverging, while the manuscript itself describes [29] as a constant-degree analysis. The paper does not prove these bounds nor does it point to the precise statement in [29] that covers this uniformity. The induction in Lemma 5 and the choice of σ_k in (38) depend on the constants 36 and 13 in (108) not degrading with k and μ. If the cited lemma was proved only for fixed μ or under extra conditions, the auxiliary test Φ, the Neyman–Pearson step, and hence Theorems 1–2 collapse. Please supply a proof of Lemma 11 in the diverging regime or an exact citation to the uniform version in [29].","section":"§V and Appendix B-D, Lemma 11"},{"comment":"The coupling argument compares GreedyMatching at θ_e and θ* by monotonicity in the threshold, but the two algorithms use different tie-breaking sets at equal likelihood ratios. When θ_e=θ*, the rank-prefix available to RBAlign is {L>θ*} ∪ {L=θ*, f≤f_{k_e}}, whereas TBAlign accepts {L>θ*} ∪ {L=θ*, f>κ*}. These sets are not nested: an edge with L=θ* and f<κ* can be accepted by RBAlign but rejected by TBAlign. Thus the claimed implication M_RB(u,v)=1 ⇒ M_TB(u,v)=1 is not established, and this implication is used to bound the number of incorrect rows in Theorem 1. The gap can likely be closed by choosing the target so that termination occurs strictly above θ*, or by using a strict-threshold version of TBAlign whose per-edge power is the same up to O((log n)^{−α/4}), but as written the proof is incomplete.","section":"§IV-D, Lemma 1"}],"minor_comments":[{"comment":"The text says 'Rank all the entries in L_d'; this should be the matrix L, not the likelihood-ratio function L_d.","section":"Algorithm 2, line 9"},{"comment":"In the proof of (96), the base case k=0 is misstated: φ_0(1/(3μ^{l-1})) = 1/(3μ^{l-1}), not 1/(3μ^{l-k}) + (k−1)/(3μ^{l-k+1}). The induction is understandable but should be cleaned up.","section":"Appendix B-B, Lemma 7 proof"},{"comment":"The tie-breaking map f is constructed to take values in [0,1), while Theorem 3 and the main text say [0,1]. This is immaterial but should be made consistent.","section":"Appendix F"},{"comment":"The notation L_d(t,~t) is used for both the likelihood ratio and, in Algorithm 2, for the matrix of all likelihood ratios. Please disambiguate to avoid confusion.","section":"Section IV-A"}],"recommendation":"major_revision","confidential_remarks":"The paper has a strong, novel contribution and the overall architecture of the proof is convincing in most places. However, the two issues in the major comments are load-bearing for the central claim. The first—uniformity of Lemma 11 in μ and k—may be easily resolved if [29, Lemma B.1] indeed covers diverging parameters, but the manuscript must make this explicit. The second—the tie-breaking gap in Lemma 1—is a proof-level flaw that likely requires a small but real patch to the coupling argument. I therefore recommend major revision rather than acceptance at this stage. If the authors can supply the missing transfer proof and repair the coupling lemma, the paper would be a strong candidate for acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a careful look. The paper gives an n^{2+o(1)} algorithm (RBAlign) that achieves almost exact recovery for CER(n,λ,s) with λ=(logn)^{α+o(1)}, α∈(0,1), s∈(√C_Otter,1], closing a real complexity gap left by chandelier counting. That is the main result, and it appears correct in structure.\n\nThe genuinely new pieces are the rank-based matching rule (avoids computing the infeasible likelihood threshold) and the analysis of tree correlation tests in the diverging-degree regime, where both mean degree and depth grow. The coupling of RBAlign to the threshold-based TBAlign (Lemma 1) is clean, the complexity accounting is explicit, and the appendices are detailed and internally consistent. The existence of the threshold is proven via an auxiliary, computationally infeasible test and the Neyman-Pearson lemma — that's an analytic device, so non-constructiveness is fine.\n\nThe one soft spot is the transfer of moment bounds. Theorem 3, and hence Proposition 1, rests on Lemma 11, which is stated as \"[29, Lemma B.1]\" and asserts uniform bounds for any k≥1 and μ>1. The paper explicitly says the baseline and boosting analysis follow [29], and it does not re-derive the uniformity in the regime where μ=(logn)^{α+o(1)} and k up to (logn)^γ both diverge. If the original lemma was proved only for fixed μ or bounded k, the induction in Lemma 5 would fail, and with it the auxiliary test, the threshold existence, and the final recovery guarantee. This is a genuine presentation gap, not an observed contradiction — but the authors should be asked to either include a proof of Lemma 11 that covers the diverging regime or explicitly verify that the [29] proof is uniform.\n\nMinor: the τ=(logn)^t degree cap and d=(logn)^γ depth keep the local trees of size n^{o(1)}, which is what makes the n^{2+o(1)} bound work; the cost is that the algorithm's complexity is n^{2+o(1)} rather than O(n^2), which is acceptable.\n\nOverall, this is a serious within-field result. The right audience is anyone working on correlated random graphs or tree correlation tests. It deserves a full peer review; the main thing I'd ask the referee to check is Lemma 11's provenance.","headline":"The first almost-quadratic-time algorithm for almost exact recovery in the correlated ER regime; main proof hinges on a cited moment-bound lemma whose diverging-regime uniformity should be checked.","tokens_in":58797,"tokens_out":4070,"would_cite":true,"duration_ms":39351,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","68Q25","62F03"],"pacs":[],"model":"deepseek-v4-flash","headline":"A rank-based algorithm using local tree correlation tests recovers all but O(n/log n) vertices of correlated Erdős–Rényi graph pairs in n^{2+o(1)} time when the correlation exceeds the tree-counting threshold.","keywords":["graph matching","correlated Erdős–Rényi graph pair","almost exact recovery","near-quadratic time","local tree correlation tests","rank-based matching","diverging-degree regime","tree-counting threshold"],"falsifier":"Simulate RBAlign on CER(n,λ,s) with n=10^5, α=0.5, and s=0.6; if the number of correctly and uniquely matched vertices is not at least n−Cn/log n for a fixed constant C with probability close to 1, the claimed coupling fails.","tokens_in":57673,"feed_emoji":"🌲","tokens_out":6050,"duration_ms":60661,"temperature":0.7,"pith_summary":"This paper tackles graph matching: recovering the hidden correspondence between vertices of two random graphs built from the same base graph. It proves that in the correlated Erdős–Rényi model with average degree (log n)^{α+o(1)}, a rank-based algorithm can correctly label all but O(n/log n) vertices in n^{2+o(1)} time, whenever the edge correlation is above the tree-counting threshold √C_Otter ≈ 0.581. The key move is to avoid computing an explicit likelihood threshold, which is hard, and instead sort all candidate local-tree pairs by their likelihood ratios and greedily match in that order. A sympathetic reader should care because this is the first almost-quadratic-time algorithm for almost exact recovery in this regime; earlier methods had running-time exponents that blow up as the correlation approaches the threshold.","feed_headline":"Rank-based tree tests match graphs almost exactly in near-quadratic time","feed_subtitle":"New algorithm sidesteps explicit thresholds and recovers all but O(n/log n) vertices in correlated random graphs.","key_machinery":"The engine is the local tree likelihood ratio L_d between the correlated and independent Poisson Galton–Watson tree-pair distributions. For each directed edge, RBAlign extracts the depth-d tree neighborhood with degree bound τ, builds a bipartite witness graph between the neighborhoods of candidate vertex pairs, and declares a match when greedy matching finds three edges whose likelihood ratios clear the current rank threshold—the 3-dangling-tree criterion. The proof additionally constructs an auxiliary correlation test with iterative boosting that is statistically tractable but computationally infeasible; the likelihood-ratio optimality lemma transfers its type-I and power guarantees to the","core_discovery":"Under the CER(n, λ, s) model with λ = (log n)^{α+o(1)}, α ∈ (0,1), and s ∈ (√C_Otter, 1], the RBAlign algorithm outputs a matching matrix with at least n − O(n/log n) correct unique row entries with probability 1 − O(exp(−½(log n)^{α/2})), and runs in n^{2+o(1)} time with probability 1 − o(e^{−n}). The proof first establishes the existence of a threshold θ* for a threshold-based counterpart TBAlign, then couples the rank-based algorithm to TBAlign so that every match it accepts is also accepted by the threshold-based version, and shows it terminates with the right number of matched rows. Along the way, the paper supplies a new analysis of local tree correlation tests in the diverging-degree","pith_inferences":["The threshold-free ranking principle suggests a template for other graph-matching models where likelihood ratios are computable but thresholds are analytically inaccessible.","If the transferred moment bounds survive, the leftover O(n/log n) unmatched vertices could likely be cleaned up by a local search, since the proof already isolates vertex degeneracies as the only obstruction in this regime.","The existence proof relies on a computationally infeasible auxiliary test, leaving open whether the promised threshold can be approximated in practice without re-examining the full space of tree pairs.","Optimizing the parameters τ=(log n)^t and d=(log n)^γ could push the regime toward α closer to 1 or reduce the n^{o(1)} runtime factor."],"forward_implications":["This is the first almost-quadratic-time algorithm achieving almost exact recovery in the diverging-degree sparse regime, with a running-time exponent independent of the correlation s.","The rank-based formulation removes the need to compute an explicit threshold, which was the computational bottleneck in previous tree-correlation methods.","The new diverging-degree analysis of tree correlation tests extends a previously constant-degree-only technique to settings where both mean degree and depth grow with n.","The coupling between rank-based and threshold-based algorithms shows that any future improvement in threshold existence transfers automatically to the implementable rank-based variant.","The error probability 1 − O(exp(−½(log n)^{α/2})) is stronger than any polynomial failure bound, so the guarantee is highly robust for large n."],"fun_headline_variants":["Rank-based graph matching hits near-quadratic time with almost exact recovery","Matching correlated graphs: rank-based algorithm sidesteps thresholds","Almost exact recovery in near-quadratic time via rank-based tree tests","Rank-based graph matching: nearly exact, nearly quadratic","Tree-correlation tests without thresholds achieve near-perfect graph match"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The argument treats moment inequalities previously proved for fixed mean degree as still valid when both the mean degree μ=(log n)^{α+o(1)} and the tree depth k=(log n)^γ grow with n; if those inequalities degrade in this joint-growth regime, the auxiliary test, the existence of the threshold, and the coupling to the rank-based algorithm all collapse.","fun_headline_variants_meta":{"raw":{"variants":["Rank-based graph matching hits near-quadratic time with almost exact recovery","Matching correlated graphs: rank-based algorithm sidesteps thresholds","Almost exact recovery in near-quadratic time via rank-based tree tests","Rank-based graph matching: nearly exact, nearly quadratic","Tree-correlation tests without thresholds achieve near-perfect graph match"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001611,"raw_usage":{"total_tokens":6345,"prompt_tokens":931,"completion_tokens":5414,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":675,"completion_tokens_details":{"reasoning_tokens":5326}},"tokens_in":675,"tokens_out":5414,"duration_ms":33600,"temperature":1.0,"reasoning_tokens":5326,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T07:43:37.698861+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate RBAlign on CER(n,λ,s) with n=10^5, α=0.5, and s=0.6; if the number of correctly and uniquely matched vertices is not at least n−Cn/log n for a fixed constant C with probability close to 1, the claimed coupling fails.","supporting_citations":[],"review_version":3}