{"id":"e35ea7a7-2df6-4406-a22a-273a2e33c53a","arxiv_id":"2412.02661","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A polynomial-time algorithm matches two correlated stochastic block models of logarithmic average degree almost exactly for s^2 > 0.338, and exactly whenever s^2(a+b)/2 > 1.","lead":"Researchers give a fast algorithm for recovering the hidden matching between two correlated networks that have two communities, in the sparse regime where each node has about log(n) connections. The algorithm works when the edge correlation squared exceeds about 0.338, and it also gives exact matching at the information-theoretic limit when that limit is reached, which resolves an open problem.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Abstract overclaims exact matching by omitting the s^2 > alpha condition; Theorem 1.1 itself is consistent, but the advertised 'whenever information-theoretically possible' is false.","rationale":"The reader's strongest concern was Lemma 3.6, the approximate independence and inverse-polynomial decay of bad vertices in the Mossel-Neeman-Sly community recovery output. I reviewed that lemma and its applications in Proposition 4.4 and Lemma 11.1. The joint bound in Lemma 3.6 is derived from the independence of edge indicators after conditioning on the community labels and excluding the vertex set S, so it does not require an unproven independence of error events; the later applications only need upper bounds on the probability that a specified set of vertices is bad, which Lemma 3.6 provides. The proof of Proposition 4.4 multiplies probabilities of complementary events, but this is only used as an upper bound and can be replaced by the one-sided bound without changing the argument. The claimed o(n^{-epsilon'}) in Lemma 11.1 is stronger than what the displayed inequalities justify, since n^{D+(a,b,s,epsilon)/D} is sub-polynomial, not polynomial; however, the actual needed bound o(1/log n) follows from the same inequalities and condition (4.3), so this is a fixable overstatement rather than a flaw in the central argument. The one concrete discrepancy that affects the paper's advertised central claim is the abstract's omission of the s^2 > alpha condition in the exact matching statement. Theorem 1.1 is accurate as stated, but the abstract and the claimed resolution of the Racz-Sridhar open problem are broader than what is proven. Since the reader's CONDITIONAL verdict already identifies this presentation issue, my stress-test does not change the verdict.","tokens_in":71402,"tokens_out":16808,"duration_ms":174725,"concrete_test":"Verify the abstract's claim against the theorem statement by testing the parameter point (a,b,s) = (100,1,0.2): compute s^2 = 0.04 < alpha and s^2(a+b)/2 = 2.02 > 1. The information-theoretic threshold for exact matching is satisfied, yet Theorem 1.1's hypotheses fail because s^2 < alpha. Search the paper for any efficient-algorithm result covering this regime; none exists, and Section 1.5 conjectures that no efficient algorithm should exist when s^2 < alpha. This settles that the abstract overclaims exact matching 'whenever information-theoretically possible.'","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract states that the paper gives an efficient algorithm for exact graph matching 'whenever this is information-theoretically possible,' and that it resolves the open problem of Racz and Sridhar. However, the information-theoretic threshold for exact matching in correlated SBMs is s^2(a+b)/2 > 1, while Theorem 1.1(b) requires both s^2 >= alpha + epsilon and s^2(a+b)/2 > 1. These conditions are not equivalent: for example, with (a,b,s) = (100,1,0.2), we have s^2 = 0.04 < alpha (approximately 0.338), yet s^2(a+b)/2 = 2.02 > 1, so exact matching is information-theoretically possible by the results of Racz and Sridhar, but Theorem 1.1 provides no efficient algorithm. The paper contains no other theorem covering s^2 < alpha; Section 1.5 explicitly conjectures hardness in this regime. Thus the abstract's 'whenever' overstates the proven result and the claimed resolution of the open problem is conditional on s^2 > alpha. This does not invalidate Theorem 1.1, but it changes the advertised contribution and must be corrected. The same issue propagates to Theorem 1.2 and the community recovery application, which inherit the s^2 > alpha condition.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies graph matching on correlated stochastic block models (CSBMs) with two balanced communities in the logarithmic average degree regime. Its main result, Theorem 1.1, gives a polynomial-time algorithm that, when s^2 >= alpha + eps, correctly matches all but a vanishing fraction of vertices, and when additionally s^2(a+b)/2 > 1, outputs the exact latent permutation. The algorithm combines community recovery (Mossel–Neeman–Sly), signed chandelier subgraph counts (Mao–Wu–Xu–Yu), and a seeded matching step. The paper also derives an application to exact community recovery from multiple correlated graphs (Theorem 1.2). The proofs are extensive, with explicit moment, variance, and probability bounds for two parameter regimes separated by whether single-graph exact community recovery is possible.","tokens_in":71692,"tokens_out":12736,"duration_ms":118304,"significance":"If the technical claims are correct, this is a substantial contribution: it provides the first efficient graph matching algorithm for logarithmic-degree correlated SBMs, reaching the information-theoretic threshold for exact matching in the regime s^2 > alpha, and it makes progress on an open problem of Rácz and Sridhar. The proof is unusually detailed and self-contained, including explicit chandelier parameter choices, moment calculations for approximately centered adjacency matrices, and a seeded matching analysis. The paper honestly discusses the conjectured information-computation gap at s^2 = alpha and the limitations of the approach.","major_comments":[{"comment":"The abstract states that the paper gives an efficient algorithm for exact graph matching 'whenever this is information-theoretically possible' and that it positively resolves the open problem of Rácz and Sridhar. This overstates the proven result. Theorem 1.1(b) requires both s^2 >= alpha + eps and s^2(a+b)/2 > 1, whereas the information-theoretic threshold from [57] is s^2(a+b)/2 > 1 alone. For example, with (a,b,s) = (100,1,0.2), we have s^2 = 0.04 < alpha = 0.338 while s^2(a+b)/2 = 2.02 > 1, so exact matching is information-theoretically possible but Theorem 1.1 provides no algorithm. Section 1.5 itself conjectures hardness in the regime s^2 < alpha. The abstract and the opening paragraph of Section 1.2 should be corrected to state the s^2 > alpha condition and to qualify the claimed resolution of the open problem as conditional on that condition; the same caveat applies to the 'Tightness' paragraph on page 5, which should not imply that exact matching holds for all s^2 > alpha.","section":"Abstract and Section 1.2"}],"minor_comments":[{"comment":"The condition in Lemma 6.1 is written as 'a+b/2 >= 1 + eps' and the proof says 'a+b/2 >= 1 + eps'. This should be '(a+b)/2 >= 1 + eps', consistent with the average degree (p+q)/2 = ((a+b)/2) log n / n used in the proof.","section":"Lemma 6.1 and Theorem 2.7"},{"comment":"The algebra after inequality (10.1) is hard to follow: the bound contains an n^N factor that is later cancelled by the n^{-N} from (rho sigma_eff^2)^N, but the cancellation is not shown. Please spell out the steps so that the final o(mu/n^2) conclusion is transparent.","section":"Section 10, proof of Proposition 4.4, case (b)"},{"comment":"The asymptotic formula for alpha_D is garbled: it should read alpha_D = alpha + C alpha^D + o(alpha^D) rather than 'alpha_D = alpha + Calpha D + o(alphaD)'. The condition for K alpha^D -> 0 follows from D >= C' log K with C' > 1/log(1/alpha), but the current notation obscures this.","section":"Lemma 2.3"},{"comment":"The line 's^2 >= alpha + eps iff rho^2 >= alpha + eps_prime' is an asymptotic equivalence (since rho = (1 + Theta(log n/n)) s), not an exact equivalence for fixed n. It would be clearer to state that the former condition implies the latter for sufficiently large n.","section":"Section 4.3, proof of Theorem 2.5"}],"recommendation":"major_revision","confidential_remarks":"The core technical work appears sound and the paper is likely publishable after the advertised contribution is stated accurately. The main issue is the abstract's overclaim about resolving the Rácz–Sridhar open problem 'whenever information-theoretically possible' without the s^2 > alpha condition; this is a load-bearing presentation issue because it changes the nature of the claimed resolution. I checked the concern about Lemma 3.6 raised during review: the independence claim in its proof is justified because, conditioned on sigma*, the edge indicators are independent and the sums for different vertices in S involve disjoint edge sets. The paper's length and density are justified by the technical content."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main point: this is a real technical advance and probably right, but the advertised \"whenever information-theoretically possible\" is false as written. The theorem itself is honest: Theorem 1.1(b) requires both s^2(a+b)/2 > 1 and s^2 >= alpha + epsilon. The abstract and intro drop the second condition and claim to resolve the Racz-Sridhar open problem. The stress-test example is correct: with a=100, b=1, s=0.2, exact matching is information-theoretically possible, but s^2 < alpha and Theorem 1.1 gives no algorithm. Section 1.5 even conjectures hardness below alpha, so the authors know the limitation. This is a presentational overclaim, not a hole in the proof's core, but it should be fixed before publication.\n\nWhat is genuinely new: this is the first polynomial-time graph matching algorithm for two-community logarithmic-degree correlated SBMs with unknown community labels. The paper takes the Mao-Wu-Xu-Yu chandelier machinery and adapts it to centered subgraph counts under estimated community labels. The new technical work is handling the estimation error from approximate centering, with moment bounds that separate true and fake pairs. The approximate-independence Lemma 3.6 is the load-bearing new part: if error events at different vertices are more correlated than claimed, the Regime II variance bounds and the thresholding argument break. I cannot find a demonstrated error in it, but it is exactly where a referee should push. The proof is extensive and the parameter conditions are stated carefully.\n\nSoft spots in proportion: the abstract overclaim is the biggest issue and should be corrected. The dependence on Lemma 3.6 is a genuine fragility, not a manufactured one, but it may well be resolvable. Minor: Algorithm 1 is quasi-polynomial, though Algorithm 4 fixes that; the exact recovery application inherits the s^2 > alpha condition, which is worth stating clearly. The citation pattern is sound; the self-cited community recovery results are used as inputs, not as the target conclusion.\n\nWho this is for: researchers in average-case graph matching and community recovery. It deserves a serious referee and likely acceptance after the abstract is fixed and Lemma 3.6 is checked carefully. I would cite it if I worked in this area.","headline":"Solid theorem, overclaimed abstract: exact matching is proved only under s^2 > alpha, not literally whenever information theory allows.","tokens_in":72203,"tokens_out":2411,"would_cite":true,"duration_ms":29211,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","68R10","68W20","62H30"],"pacs":[],"model":"deepseek-v4-flash","headline":"For correlated two-community stochastic block models with logarithmic average degree, a polynomial-time algorithm matches all but a vanishing fraction of vertices correctly when the squared edge correlation exceeds α≈0.338, and matches…","keywords":["graph matching","correlated stochastic block models","chandelier subgraph counts","exact community recovery","information-computation gap","Otter constant","logarithmic average degree","random graph alignment"],"falsifier":"Simulate the community-recovery step in the regime sD+(a,b)<1 and estimate, for a fixed set S of O(log n) vertices, the probability that every vertex of S is misclassified; finding that this probability is not O($n^{{-|S|(sD+(a,b)-ε|log(a/b)|)}}$) for arbitrarily small ε,δ>0 would violate Lemma 3.6 and undo the variance bound that supports almost-exact matching.","tokens_in":71208,"feed_emoji":"🔗","tokens_out":8532,"duration_ms":85903,"temperature":0.7,"pith_summary":"This paper claims that the vertex correspondence between two correlated two-community stochastic block models can be recovered by a polynomial-time algorithm in the logarithmic-average-degree regime whenever the squared edge correlation exceeds Otter's tree-counting constant α≈0.338. In that regime the algorithm matches all but a vanishing fraction of vertices correctly with high probability; if in addition s²(a+b)/2>1, which is the information-theoretic threshold for exact matching, it recovers the full latent permutation exactly. The result resolves the previously open problem of whether efficient exact graph matching is possible whenever information-theoretic exact matching is possible. The proof carries the chandelier-counting strategy for correlated random graphs over to community-structured graphs, and its main technical work is controlling the estimation errors that arise because the community partition cannot be exactly recovered from a single graph in the relevant parameter regimes. A direct application is an efficient algorithm for exact community recovery from two correlated graphs in regimes where a single graph provably cannot achieve it.","feed_headline":"Two correlated community networks can now be matched efficiently","feed_subtitle":"The first polynomial-time method reaches exact recovery at the information-theoretic threshold.","key_machinery":"The paper's central object is a chandelier, a rooted tree built from L branches, each a path of M edges (the wire) ending in a distinct rooted tree of K edges (the bulb), with all bulbs pairwise non-isomorphic, at most R rooted automorphisms, and maximum degree at most D. Signed subgraph counts count rooted copies of each chandelier in the approximately centralized adjacency matrix, where the expected edge probability is subtracted using a community-label estimate. The signature vector stacks these counts over the full chandelier family; the similarity score is the automorphism-weighted inner product of two signatures. The family is sized so that true-pair scores concentrate around μ=|T| n^N ρ^N $σ_eff^{{2N}}$ while fake-pair scores have mean o(μ) and variance o(μ²/n²), which is what lets a simple threshold separate correct from incorrect matches. A final seeded matching step uses common-neighbor counts under the partial matching to reach the exact permutation.","core_discovery":"The central claim is that, for two correlated balanced two-community stochastic block models on n vertices with p=a log n/n and q=b log n/n, the unknown vertex permutation π* can be recovered by a polynomial-time algorithm whenever the squared edge correlation s² exceeds α≈0.338. The algorithm first runs an almost-exact community-recovery routine on each graph to estimate the latent labels, centers each adjacency matrix by subtracting the estimated p/q edge probabilities, and computes a signature of signed subgraph counts of chandeliers rooted at each vertex. The weighted inner product of two signatures has expectation (1+o(1))μ for true correspondences and o(μ) for false ones, with variance small enough to threshold correctly on (1−o(1))n vertices; a seeded common-neighbor step then upgrades the partial matching to the exact permutation whenever s²(a+b)/2>1, which is the information-theoretic threshold. This positively resolves the open problem of efficient exact graph matching in this model and yields, as a black-box application, efficient exact community recovery from two correlated graphs in regimes where a single graph cannot achieve it.","pith_inferences":["Because the chandelier size N is Θ(log n/ε), the runtime exponent in the polynomial bound grows as ε shrinks; near the threshold the algorithm is polynomial but practically slow, a cost the paper does not quantify.","The entire score-separation analysis rests on the approximate independence of community-recovery errors, so the natural way to attack the result is to test the joint distribution of misclassification events; a correlation structure stronger than inverse-polynomial independence would break the variance computation before any other step.","The same signature-counting scheme should extend to degree-corrected or k-community block models as long as a community-recovery subroutine provides inverse-polynomial, approximately independent error rates, although the paper only conjectures the k-community extension."],"forward_implications":["For any two distinct positive community densities a and b, almost-exact graph matching is polynomial-time once s²≥α+ε for any ε>0.","Exact graph matching is achieved efficiently at the same threshold where information-theoretic exact matching first becomes possible, namely s²(a+b)/2>1.","Exact community recovery from two correlated graphs becomes efficiently possible in regimes where exact recovery from a single graph is information-theoretically impossible.","The same matching algorithm yields efficient exact community recovery from K correlated graphs above the corresponding threshold.","The regime s²<α is left open and is conjectured to be computationally hard, giving a conjectured information-computation gap."],"supporting_citations":[{"why":"Supplies the chandelier-counting signatures, the similarity-score thresholding argument, and the seeded matching step that this paper generalizes to correlated SBMs.","marker":"[41]"},{"why":"Supplies the almost-exact community-recovery algorithm used to estimate labels and to approximately center the adjacency matrices.","marker":"[47]"},{"why":"Establishes the information-theoretic exact-matching threshold s²(a+b)/2=1 for correlated SBMs and poses the efficient-algorithm open problem resolved here.","marker":"[57]"},{"why":"Provides the inverse-polynomial per-vertex error rates for community recovery and the correlated-SBM exact-community-recovery threshold used in the application.","marker":"[25]"},{"why":"Introduces Otter's constant α and the growth rate (α+o(1))^{-K} of unlabeled rooted trees, which fixes the usable size of the chandelier family.","marker":"[55]"},{"why":"Supplies the entrywise spectral method used inside the community-recovery subroutine to obtain almost-exact partitions.","marker":"[3]"}],"fun_headline_variants":["First efficient algorithm to match correlated community graphs","Exact graph matching achieved efficiently at theoretical limit","Polynomial-time matching for correlated stochastic block models","Efficient solution to open problem in graph matching","Correlated SBM graphs matched exactly in polynomial time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the community-recovery estimate misclassifies different vertices almost independently, with each misclassification probability inverse-polynomial in n; if the misclassification events are correlated more strongly than the paper's Lemma 3.6 allows, the variance of the similarity score is no longer negligible against its squared mean and the thresholding proof collapses.","fun_headline_variants_meta":{"raw":{"variants":["First efficient algorithm to match correlated community graphs","Exact graph matching achieved efficiently at theoretical limit","Polynomial-time matching for correlated stochastic block models","Efficient solution to open problem in graph matching","Correlated SBM graphs matched exactly in polynomial time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000708,"raw_usage":{"total_tokens":3217,"prompt_tokens":997,"completion_tokens":2220,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":613,"completion_tokens_details":{"reasoning_tokens":2149}},"tokens_in":613,"tokens_out":2220,"duration_ms":15035,"temperature":1.0,"reasoning_tokens":2149,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:12:16.125580+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the community-recovery step in the regime sD+(a,b)<1 and estimate, for a fixed set S of O(log n) vertices, the probability that every vertex of S is misclassified; finding that this probability is not O($n^{{-|S|(sD+(a,b)-ε|log(a/b)|)}}$) for arbitrarily small ε,δ>0 would violate Lemma 3.6 and undo the variance bound that supports almost-exact matching.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the chandelier-counting signatures, the similarity-score thresholding argument, and the seeded matching step that this paper generalizes to correlated SBMs."},{"cited_title":"Consistency thresholds for the planted bisection model","cited_arxiv_id":null,"evidence_quote":"Supplies the almost-exact community-recovery algorithm used to estimate labels and to approximately center the adjacency matrices."},{"cited_title":"R´ acz and Anirudh Sridhar","cited_arxiv_id":null,"evidence_quote":"Establishes the information-theoretic exact-matching threshold s²(a+b)/2=1 for correlated SBMs and poses the efficient-algorithm open problem resolved here."},{"cited_title":"R´ acz, and Anirudh Sridhar","cited_arxiv_id":null,"evidence_quote":"Provides the inverse-polynomial per-vertex error rates for community recovery and the correlated-SBM exact-community-recovery threshold used in the application."},{"cited_title":"The Number of Trees","cited_arxiv_id":null,"evidence_quote":"Introduces Otter's constant α and the growth rate (α+o(1))^{-K} of unlabeled rooted trees, which fixes the usable size of the chandelier family."},{"cited_title":"Entrywise eigenvector analysis of random matrices with low expected rank.The Annals of Statistics, 48(3):1452–1474, 2020","cited_arxiv_id":null,"evidence_quote":"Supplies the entrywise spectral method used inside the community-recovery subroutine to obtain almost-exact partitions."}],"review_version":1}