{"id":"665f6103-7ec7-45a5-ad3b-27e1918454b5","arxiv_id":"2412.02796","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For any fixed K, exact community recovery from K edge-correlated stochastic block models is characterized by a two-part inequality combining graph matchability and single-graph community signal.","lead":"This paper finds the exact amount of shared information needed to perfectly recover communities from K correlated social or biological networks, even when no two networks can be aligned exactly. The result reveals a region where adding a third or K-th network makes perfect recovery possible, although any K-1 networks alone cannot.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The general-K impossibility proof (Theorem 2) is omitted in Section 8, so the claimed if-and-only-if threshold for all constant K is not currently established; the missing MAP-based proof for K≥4 must be supplied.","rationale":"The paper has real substance: the K=3 proof is detailed, the k-core machinery is coherent, and Lemma 7.4's intersection exponent matches the proposed threshold. However, the advertised contribution is the precise threshold for any constant K, and that requires Theorem 2 for all K. Section 8 explicitly omits the proof, and the sketched substitutions are not a checkable argument. This is exactly the kind of missing support that should be flagged, and it is what keeps the central claim from being fully established. I do not claim the theorem is false; I claim the strongest claim is currently unverified for K≥4. The reader's CONDITIONAL verdict is therefore appropriate, so I recommend no change. The concrete test is to reconstruct the K=4 impossibility proof; if it succeeds, conditional acceptance is justified, and if it fails, the paper would need revision or a weakened claim.","tokens_in":53772,"tokens_out":13002,"duration_ms":143914,"concrete_test":"Complete the omitted Section 8 proof for K=4. Specifically: derive the posterior of π*12 conditional on A, B_2, B_3, B_4, σ*_2, S*, π*12([n]\\S*), and {π*_ij : i,j∈{2,3,4}}; verify the analogue of Lemma 6.14 reduces to D_2 (√(p_{1000}q_{0000}/(p_{0000}q_{1000})))^{ν_+(π)-ν_-(π)} 1(π∈A*); then prove analogues of Lemmas 6.7 and 6.8 with θ = 1 - s(1-(1-s)^3)T_c(a,b) - s(1-s)^3 D_+(a,b) and show the second-moment bound gives Var ≤ n^{2θ-3δ}. If the calculation goes through, the concern is resolved; if not, the general-K threshold in Theorem 2 is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the exact if-and-only-if threshold for every constant K, but Theorem 2 is only proved for K=3. Section 8 contains no real proof: it says the proof follows by generalizing the K=3 argument and then states 'we omit the details.' What remains is a list of substitutions (replace (2s^2-s^3) by s(1-(1-s)^{K-1}) and s(1-s)^2 by s(1-s)^{K-1}) plus the assertion that analogues of Lemmas 6.7, 6.8, 6.14, and 6.17 hold. This is not a routine gap: the K-graph MAP analysis requires a K-way posterior over (A,B_2,...,B_K), a correct definition of the analogue of S*, and a new variance estimate for the bad-set sum. Section 8 also refers back to condition (6.1) rather than the general condition (1.11), further indicating the general converse has not been written out. If any analogue fails for K≥4, the matching term in threshold (1.9) would not be tight, so the if-and-only-if statement would be unsupported. The achievability side and the K=3 impossibility are substantial, but the general-K converse is the load-bearing missing piece.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies exact community recovery and exact graph matching from K edge-correlated stochastic block models with two balanced communities, in the logarithmic-degree regime. The main results are Theorems 1–4: for any constant K, exact community recovery is claimed to be possible exactly when the union-graph divergence (1-(1-s)^K)D_+(a,b) exceeds 1 and the combined matching-and-recovery expression s(1-(1-s)^{K-1})T_c(a,b)+s(1-s)^{K-1}D_+(a,b) exceeds 1; exact graph matching is claimed to be possible exactly when s(1-(1-s)^{K-1})T_c(a,b)>1. The achievability proof uses pairwise 13-core matchings, a metagraph criterion to split vertices into 'good' and 'bad' sets, and majority-vote cleanup; the converse uses MAP-type arguments. The K=3 case is worked out in full detail in Sections 5 and 6, and the positive direction for general K is presented in Section 7. The general-K impossibility proof, however, is only sketched in Section 8.","tokens_in":54072,"tokens_out":13920,"duration_ms":129408,"significance":"If valid, the threshold answers the open question from Gaudio, Racz, and Sridhar and identifies a region where K graphs jointly enable exact community recovery even though no K-1 graphs do and no pairwise matching is exactly recoverable. The paper contains no fitted parameters, and the main technical quantities are explicit functions of a, b, s, and K. The k-core intersection bounds (Lemmas 4.7 and 7.4) are the key new technical content and appear plausible for K=3 and for the positive direction for general K. The K=3 converse in Section 6 is substantial and detailed. However, the claimed if-and-only-if characterization for all constant K is not currently established, because the converse for K≥4 is omitted rather than proved.","major_comments":[{"comment":"The proof of Theorem 2 for general K is not present. The section states that the proof follows by generalizing the K=3 argument and then says 'we omit the details,' listing only formal substitutions such as replacing (2s^2-s^3) by s(1-(1-s)^{K-1}) and s(1-s)^2 by s(1-s)^{K-1}. It also refers back to condition (6.1), which is the K=3 condition, rather than to the general condition (1.11). Since Theorem 2 provides the converse half of the if-and-only-if threshold (1.7), the main theorem is not established for K≥4 without a complete argument. The missing work is not merely notational: the K-way posterior over (A,B_2,...,B_K), the correct analogue of the set S*, and the variance estimate for the bad-set sum must be written out.","section":"Section 8"},{"comment":"The impossibility proof for Theorem 4 invokes [16, Theorem 1] with the condition stated as s(1-(1-s)^{K-1})<1. The theorem being invoked has the condition s_1 s_2 T_c(a,b)<1 for impossibility of exact graph matching, so the displayed inequality is missing the T_c(a,b) factor. As written, the contradiction step does not follow; the correct condition is s(1-(1-s)^{K-1})T_c(a,b)<1.","section":"Section 9.2"},{"comment":"The proof of Theorem 3 relies on the bad-vertex count tending to zero, but the text says 'When 1 - s(1-(1-s)^{K-1})T_c(a,b) > 1', which cannot hold for positive s; the intended condition is s(1-(1-s)^{K-1})T_c(a,b)>1, equivalently 1 - s(1-(1-s)^{K-1})T_c(a,b)<0. In addition, the statement of Lemma 7.6 omits the exponent 1 in the bound and writes n^{-s(1-(1-s)^{K-1})T_c(a,b)+o(1)} instead of n^{1-s(1-(1-s)^{K-1})T_c(a,b)+o(1)}. These are likely typos, but because they occur in the proof of a main theorem they should be corrected.","section":"Section 9.1 and Lemma 7.6"}],"minor_comments":[{"comment":"The statement of Lemma 7.7 assumes (1-(1-s)^3)D_+(a,b)>1+2ε|log(a/b)|, while the proof and the surrounding general-K argument use (1-(1-s)^K); the exponent 3 should be replaced by K.","section":"Section 7.4, Lemma 7.7"},{"comment":"The proof says 'degree of vertex v in the graph G1 ∨ G3 . . .∨ GL'; the intended union is over the first L graphs, so the notation should be G1∨G2∨...∨GL or an explicit statement that the indexing is over the L chosen graphs.","section":"Section 7.3, proof of Lemma 7.4"},{"comment":"The definition of the inter-community vertex pairs uses the symbol E^+(σ) for both intra-community and inter-community sets; the second occurrence should be E^-(σ).","section":"Section 1.6"},{"comment":"The statement and proof index the unmatched sets inconsistently: Lemma 4.7 states |F*_ij ∩ F*_jk|, while the proof writes |F*_12 ∩ F*_23| = |F*_21 ∩ F*_23| = |F*_12 ∩ F*_13|. The sets should be explicitly pulled back to a common vertex set, presumably that of G1, so that the intersection is well defined.","section":"Lemma 4.7 and surrounding text"}],"recommendation":"major_revision","confidential_remarks":"The paper is a strong candidate for a theory journal if the general-K converse can be supplied. The K=3 proof is detailed, and the achievability side for general K is credible. The main obstacle is Section 8, where the proof of Theorem 2 for K≥4 is omitted; this is the load-bearing missing piece for the if-and-only-if claim. Please also require the authors to correct the T_c(a,b) factor in Section 9.2 and the related sign/index typos in Section 9.1 and Lemma 7.6."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this is the first paper I know that gives a sharp threshold for exact community recovery from K correlated SBMs for K>=3, and the phase diagram it uncovers is real: for every K>=3 there are parameters where K graphs succeed even though any K-1 fail and no pair can be exactly matched. Second, the general-K converse is not actually in the paper. Section 8 sketches it and says \"we omit the details.\" That is a load-bearing omission, not a stylistic one.\n\nWhat the paper does well: the K=3 recovery algorithm and its proof are detailed and plausible. The key technical contribution, controlling intersections of bad sets from pairwise k-core matchings (Lemmas 4.7 and 7.4), is genuinely new and is what makes the majority-vote cleanup work. The graph-matching threshold for general a,b is also new, and the concurrent ER-case overlap with Ameen and Hajek is disclosed honestly. The paper builds on the authors' prior two-graph work, but those are established results, not circular assumptions.\n\nThe soft spots, in proportion.\n\n1. The general-K impossibility proof (Theorem 2 for K>=4) is missing. Section 8 lists substitutions and asserts analogues of Lemmas 6.7, 6.8, 6.14, 6.17 hold, then says \"we omit the details.\" This is not a routine gap. The K-graph MAP analysis requires a K-way posterior, a correct definition of the analogue of S*, and new variance estimates. The section even refers back to condition (6.1) rather than the general condition (1.11). So the advertised if-and-only-if threshold for every constant K is unsupported as written. This is the clear referee issue.\n\n2. Section 9.2 has a typo: the impossibility condition is stated as s(1-(1-s)^{K-1}) < 1, dropping the factor T_c(a,b). The intended inequality is clearly s(1-(1-s)^{K-1})T_c(a,b) < 1. This is an easy fix but makes that paragraph unreadable until corrected.\n\n3. Minor: the efficient-algorithm discussion is appropriately cautious, but the paper's headline claims are information-theoretic only.\n\nOverall: the K=3 results are substantial and likely correct, and the general-K achievability is plausible. But the central if-and-only-if claim for all constant K is not currently established. Who is this for? Researchers in community detection and graph matching. It deserves a serious referee, but the referee should insist on the full general-K impossibility proof, or a revised statement that limits the theorems to K=3. If the proof can be supplied, this is a strong paper.","headline":"Sharp multi-graph community recovery threshold for K>=3 is likely right, but the general-K impossibility proof is asserted, not supplied, so the if-and-only-if claim is not yet established as written.","tokens_in":54567,"tokens_out":2421,"would_cite":true,"duration_ms":26106,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","62H30"],"pacs":[],"model":"deepseek-v4-flash","headline":"Exact community recovery from a constant number of correlated networks is characterized by two sharp inequalities, and for K≥3 extra graphs can succeed where any K−1 fail.","keywords":["correlated stochastic block models","exact community recovery","graph matching","k-core matching","information-theoretic threshold","multiple correlated networks","phase transition"],"falsifier":"For $K=3$, $s=0.2$, $a=16$, $b=1$, estimate the number of vertices missed by the true 13-core matchings in both $(G_1,G_2)$ and $(G_1,G_3)$. The proof requires this intersection to grow no faster than $n^{1-s(1-(1-s)^2)T_c(a,b)+o(1)}=n^{0.388+o(1)}$; an observed exponent clearly above $0.388$ would break the majority-vote cleanup and refute the claimed threshold.","tokens_in":53615,"feed_emoji":"🕸️","tokens_out":9981,"duration_ms":93482,"temperature":0.7,"pith_summary":"This paper determines the exact information-theoretic threshold for recovering two latent communities from a constant number K of correlated networks. Each network is an edge-subsampled, independently permuted copy of one stochastic block model, and the communities are planted before the copies are made. The result is a pair of strict inequalities: the union graph must be identifiable, and a weighted combination of a graph-matching term and a community-recovery term must exceed one. For every K≥3 the second inequality can hold even when no pairwise latent matching is exactly recoverable, so several graphs genuinely add information. This answers the open K-graph question raised by the two-graph analysis.","feed_headline":"Extra correlated networks widen exact-community recovery range","feed_subtitle":"With three or more graphs, communities can be recovered even when no two graphs can be exactly matched.","key_machinery":"The load-bearing object is the pairwise $k$-core matching with $k=13$: for each pair of graphs, take the permutation whose intersection graph has the largest 13-core, and match only the vertices in that core. Each such matching misses about $n^{1-s^2T_c(a,b)+o(1)}$ vertices. For $K$ graphs a vertex is called good when the graph whose edges are its pairwise matchings connects all $K$ graphs, and bad otherwise. The central estimate, Lemmas 4.7 and 7.4, bounds the intersection of the bad sets $F^*_{ij}$ over cross pairs by $n^{1-s(1-(1-s)^{K-1})T_c(a,b)+o(1)}$, and this exponent is exactly what the cleanup majority vote needs. The argument also uses the Łuczak expansion to show vertices outside the cores have only weakly connected neighborhoods.","core_discovery":"With $K$ correlated SBMs, each marginally $\\mathrm{SBM}(n, s a \\log n/n, s b \\log n/n)$, exact community recovery is possible if and only if $(1-(1-s)^K)D_+(a,b)>1$ and $s(1-(1-s)^{K-1})T_c(a,b)+s(1-s)^{K-1}D_+(a,b)>1$, where $D_+(a,b)=(\\sqrt a-\\sqrt b)^2/2$ and $T_c(a,b)=(a+b)/2$. The first condition is the union-graph threshold: it is what would suffice if all latent vertex alignments were known. The second condition is the new content for $K\\ge 3$. Its matching term uses pairwise 13-core matchings, whose error sets are controlled by intersection size $n^{1-s(1-(1-s)^{K-1})T_c(a,b)+o(1)}$, and its recovery term uses edges that appear only in the first graph, giving the factor $s(1-s)^{K-1}$. The same machinery gives the sharp exact graph matching threshold $s(1-(1-s)^{K-1})T_c(a,b)>1$.","pith_inferences":["A likely general principle: when several partial pairwise alignments are aggregated, the relevant error term is the intersection of their failure sets, not their union; this may transfer to other joint recovery problems such as multiple-community SBMs or attributed graphs.","The paper leaves open whether the $K$-graph threshold can be met in polynomial time; if a polynomial-time partial $k$-core matching is found at these densities, the recovery algorithm becomes efficient.","Under the alternative construction $G'_i=G_0\\vee H_i$ with independent $H_i$, thresholds will generally differ for $K\\ge 3$, and the same question is naturally posed there.","A direct testable prediction: algorithms that first build a partial matching per pair and then majority-vote on the induced union graph should succeed exactly in the claimed regime; failures would show up first as bad-set intersections exceeding the bound."],"forward_implications":["For every $K\\ge 3$ there is a parameter region where exact community recovery is possible with $K$ graphs although it is impossible with $K-1$ graphs and no latent matching is exactly recoverable.","Exact graph matching from $K$ graphs is possible exactly when $s(1-(1-s)^{K-1})T_c(a,b)>1$, which is strictly weaker for $K>2$ than the two-graph matching threshold.","When the true alignments are known, condition (1.8) alone suffices; without them, the matching term $s(1-(1-s)^{K-1})T_c(a,b)$ is the price of not knowing the alignments.","The threshold interpolates cleanly from the single-graph threshold $sD_+(a,b)>1$ to the fully aligned union-graph threshold $(1-(1-s)^K)D_+(a,b)>1$ as the matching information improves.","Each additional graph weakens the effective matching exponent from $s^2T_c$ toward $sT_c$, which is why several graphs help even when pairwise matchings fail."],"supporting_citations":[{"why":"The two-graph exact recovery threshold and MAP analysis this paper extends; the open question answered here, and several technical lemmas are reused.","marker":"[24]"},{"why":"Establishes the single- vs two-graph matching threshold and the necessary union condition (1.8), the baseline both theorems build on.","marker":"[43]"},{"why":"Introduced k-core matchings, the partial-matching estimator used as the engine in the recovery algorithm.","marker":"[15]"},{"why":"Supplies the almost-exact single-SBM labeling and control of misclassified vertices used in the first cleanup step.","marker":"[37]"},{"why":"The Luczak expansion technique adapted to prove that vertices outside the k-core have weakly connected neighborhoods.","marker":"[29]"},{"why":"The asymmetric-subsampling impossibility theorem used to prove the K-graph exact graph matching converse.","marker":"[16]"},{"why":"The single-graph exact recovery threshold $D_+(a,b)=1$ underlying the union-graph condition.","marker":"[2]"}],"fun_headline_variants":["K correlated graphs beat K−1 even without exact matching","More graphs recover communities even if no pair matches","Exact community recovery with K correlated graphs","No exact match needed: K graphs improve recovery"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof stands on the claim that the small sets of vertices left unmatched by pairwise matchings do not overlap much across different pairs; if those overlaps were materially larger than the stated bound, the cleanup majority vote would fail and the claimed threshold could not be reached.","fun_headline_variants_meta":{"raw":{"variants":["K correlated graphs beat K−1 even without exact matching","More graphs recover communities even if no pair matches","Exact community recovery with K correlated graphs","No exact match needed: K graphs improve recovery"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000602,"raw_usage":{"total_tokens":2836,"prompt_tokens":997,"completion_tokens":1839,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":613,"completion_tokens_details":{"reasoning_tokens":1779}},"tokens_in":613,"tokens_out":1839,"duration_ms":14412,"temperature":1.0,"reasoning_tokens":1779,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:06:11.715341+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $K=3$, $s=0.2$, $a=16$, $b=1$, estimate the number of vertices missed by the true 13-core matchings in both $(G_1,G_2)$ and $(G_1,G_3)$. The proof requires this intersection to grow no faster than $n^{1-s(1-(1-s)^2)T_c(a,b)+o(1)}=n^{0.388+o(1)}$; an observed exponent clearly above $0.388$ would break the majority-vote cleanup and refute the claimed threshold.","supporting_citations":[{"cited_title":"Gaudio, M","cited_arxiv_id":null,"evidence_quote":"The two-graph exact recovery threshold and MAP analysis this paper extends; the open question answered here, and several technical lemmas are reused."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the single- vs two-graph matching threshold and the necessary union condition (1.8), the baseline both theorems build on."},{"cited_title":"Cullina, N","cited_arxiv_id":null,"evidence_quote":"Introduced k-core matchings, the partial-matching estimator used as the engine in the recovery algorithm."},{"cited_title":"Mossel, J","cited_arxiv_id":null,"evidence_quote":"Supplies the almost-exact single-SBM labeling and control of misclassified vertices used in the first cleanup step."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Luczak expansion technique adapted to prove that vertices outside the k-core have weakly connected neighborhoods."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The single-graph exact recovery threshold $D_+(a,b)=1$ underlying the union-graph condition."}],"review_version":1}