{"id":"777e2b25-eaec-40c5-813d-9fce22787a07","arxiv_id":"2502.00686","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Well-Connected Clusters (WCC), a simple cut-removal postprocessor, improves the accuracy of SBM community detection on non-bipartite synthetic benchmarks.","lead":"The paper finds that stochastic block model community detection often returns internally disconnected clusters, and proposes a fast post-processing step called WCC that repeatedly removes small edge cuts until each community is well-connected. It reports that WCC improves clustering accuracy on synthetic networks and scales to networks with millions of nodes.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Accuracy gain in Experiment 3 may be an artifact of benchmarks whose Leiden-derived ground truth enforces the same well-connectedness that WCC provides; without a control using non-well-connected ground truth, the central claim is not established.","rationale":"The paper's central claim is that WCC post-processing typically improves the accuracy of SBM clusterings, supported by Experiment 3 on LFR/RECCS synthetic networks. The load-bearing condition for that claim is that those synthetic benchmarks are unbiased tests of WCC. That condition is not met: the ground-truth partitions are produced from real networks clustered with Leiden, and Leiden guarantees well-connected communities—the exact property WCC enforces. Consequently, any method that merely splits SBM clusters along small cuts will systematically score better on these benchmarks, independent of whether WCC recovers the 'true' community structure. This is not an internal inconsistency, but it is a genuine correctness risk for the generalization claim. The paper's real-world results (Experiments 1, 2, and 4) remain valuable: the connectivity deficit of SBM clusterings is documented with a large network corpus, WCC's runtime is small relative to SBM, and the code is publicly available. However, Table A shows WCC reduces node coverage to 38% on large non-bipartite networks, making it especially important to verify that the benchmark's ground truth is representative rather than favorable. The reader's weakest assumption pinpoints this same benchmark-design issue, and the appropriate verdict remains CONDITIONAL rather than ACCEPT or REJECT.","tokens_in":16878,"tokens_out":5562,"duration_ms":60819,"concrete_test":"Generate a matched control set of synthetic networks with the same LFR/RECCS protocols but using the raw selected-SBM clusterings of the source real-world networks (which contain internally disconnected clusters) as ground truth, then compare ARI/NMI of SBM vs SBM+WCC. If WCC does not improve accuracy on these controls, the Experiment 3 improvement is specific to well-connected Leiden ground truth and the 'typically improves' claim fails to generalize; if WCC still improves, the bias concern is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central accuracy claim (Experiment 3) is evaluated only on synthetic networks whose ground-truth partitions are derived from Leiden clusterings of real networks: LFR networks use parameters obtained from real-world networks clustered with Leiden optimizing modularity or CPM, and RECCS networks use Leiden-CPM(0.01). Leiden is precisely the method that guarantees well-connected communities, and WCC's entire mechanism is to enforce well-connectedness by repeatedly removing small edge cuts. On such a benchmark, any internally disconnected SBM cluster is necessarily an error, and WCC is the treatment specifically designed to repair that error. Thus the comparison SBM vs SBM+WCC is systematically biased in WCC's favor: the ground truth is generated by a procedure with the same connectivity constraint that WCC imposes. This concern is supported by the real-world node coverage results in Table A: on non-bipartite networks, WCC reduces node coverage from 100% to 38% (large) and 48% (medium), and median cluster sizes drop to 3. The benchmark's ground-truth structure must therefore be quite different from the structure WCC produces on real networks. Without a benchmark whose ground truth is not constrained to be well-connected, the claim that WCC 'typically improves' SBM accuracy is not established outside this specific construction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the connectivity of communities found by Stochastic Block Models (SBMs) on 120 real-world networks, showing that SBMs frequently produce internally disconnected or poorly connected clusters, especially on bipartite and large networks. To address this, the authors propose Well-Connected Clusters (WCC), a post-processing technique that recursively removes small edge cuts until each cluster meets a user-specified well-connectedness threshold (default log10(n)), and compare WCC with two other post-processors (Connected Components and the Connectivity Modifier). Using synthetic LFR and RECCS networks whose ground truth is derived from Leiden clusterings of real networks, the authors report that WCC generally improves SBM clustering accuracy across NMI, ARI, AGRI, and RMI, and is computationally fast on networks with millions of nodes. The paper also offers a description-length analysis explaining why the degree-corrected SBM favors disconnected clusters.","tokens_in":17153,"tokens_out":5994,"duration_ms":57599,"significance":"If the accuracy claim holds, WCC is a simple, fast, and open-source post-processing step that SBM practitioners could apply to obtain well-connected clusters with improved accuracy on non-bipartite networks. The paper's empirical characterization of SBM cluster connectivity across 120 real networks is a useful contribution, and the runtime experiments (Experiment 4) demonstrate WCC's scalability to a network with about 14 million nodes. The description-length analysis (Fig 8, Table 1, Eq 2) provides a plausible mechanistic explanation for why SBMs prefer internally disconnected clusters. However, the central accuracy claim rests on synthetic benchmarks whose ground truth is generated by methods that enforce well-connectedness, which is exactly the property WCC imposes; this creates a systematic bias that must be addressed before the claim can be considered established.","major_comments":[{"comment":"The accuracy evaluation in Experiment 3 is based entirely on synthetic networks whose ground truth is derived from Leiden clusterings of real-world networks: LFR parameters come from networks clustered with Leiden optimizing modularity or CPM, RECCS uses Leiden-CPM(0.01), and the two LFR networks with a large proportion of disconnected ground-truth clusters were excluded from the study. Because Leiden guarantees well-connected communities, the benchmark ground truth is well-connected by construction, which is exactly the property WCC enforces. Consequently, any internally disconnected SBM cluster is automatically an error with respect to this ground truth, and WCC is the treatment designed to repair that error; the comparison SBM vs. SBM+WCC is therefore systematically biased in WCC's favor. To establish that WCC 'typically improves' accuracy, please add benchmarks whose ground truth is not constrained to be well-connected (e.g., LFR or RECCS networks generated from random partitions, from SBM models with disconnected blocks, or from the excluded LFR networks with disconnected ground truth), and report accuracy separately for well-connected versus disconnected ground-truth communities.","section":"Materials and methods: Synthetic networks; Experiment 3a (Fig 3)"},{"comment":"The real-world results in Table A show that WCC reduces node coverage from 100% to 48% on medium and 38% on large non-bipartite networks, with median non-singleton cluster sizes dropping to 3. This is a very different structure from the benchmark ground truth, whose communities are the much larger well-connected clusters produced by Leiden. If WCC fragments real SBM clusters to this degree, it is unclear whether accuracy gains on the synthetic benchmarks, whose ground truth consists of large well-connected communities, will transfer to real-world applications. Please discuss this discrepancy explicitly and, if possible, validate on a real-world network with known community labels, or at least report the distribution of accuracy contributions as a function of cluster size on the synthetic benchmarks.","section":"Experiment 2 (Table A; Fig A in S1 Appendix)"}],"minor_comments":[{"comment":"The abstract contains several typos: 'sh own' should be 'shown', 'an d' should be 'and', 'evalu ate' should be 'evaluate', 'pro pose' should be 'propose', and 'net works' should be 'networks'. Please proofread the entire manuscript.","section":"Abstract"},{"comment":"The caption reads 'lage-sized' instead of 'large-sized', and the same typo appears in other supplementary table captions. Please correct these.","section":"Table A caption (S1 Appendix)"},{"comment":"The caption states 'We show the contribution of − log p(e) term on the description lengths of CC-treated SBM clusterings,' but the box plot shows differences for all four description-length components. Please rephrase to describe the full set of components shown.","section":"Figure 8 caption"},{"comment":"The heatmap in Fig 3 reports normalized differences, but the underlying numeric accuracy scores (NMI, ARI, AGRI, RMI) are not provided as a table. A supplementary table with these values for each method and each synthetic network would improve reproducibility and allow readers to verify claims such as 'WCC always was neutral or beneficial for NMI and ARI.'","section":"Experiment 3a (Fig 3)"},{"comment":"The description-length analysis is restricted to the degree-corrected SBM and the CC treatment, while the recommended method is WCC. The explanation would be more compelling if the same component decomposition were reported for WCC and for the non-degree-corrected and planted-partition SBM variants, since these models are also used in the selected SBM clustering.","section":"Discussion (Eq 2)"}],"recommendation":"major_revision","confidential_remarks":"The benchmark-bias concern is the main issue. The paper's own real-world results (Table A) show that WCC fragments clusters substantially, which makes the synthetic benchmark results less convincing. The connectivity finding and the runtime experiments are solid, and the code is publicly available. I would not recommend rejection because the bias is fixable within the manuscript's scope: adding out-of-distribution benchmarks or substantially tempering the accuracy claim would address the concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Minhyuk and colleagues show that SBM clusterings of real-world networks are often internally disconnected, and that a simple post-processing step (WCC) can repair this. The real-world connectivity finding is well documented across 120 networks, and the description-length decomposition is a genuine mechanistic result: the -log p(e) term grows with the number of blocks, so SBM's objective actively prefers disconnected clusters. The code is available, and WCC is fast. That part of the paper is solid.\n\nThe soft spot is the accuracy claim. The synthetic benchmarks (LFR and RECCS) use ground truth derived from Leiden clusterings of real networks, and Leiden guarantees well-connected communities. WCC's mechanism is to enforce well-connectedness. So on these benchmarks, any internally disconnected SBM cluster is necessarily an error, and WCC is the treatment designed to fix exactly that. That is a real circularity, not a manufactured one. The paper even notes that Leiden never produces disconnected ground truth clusters (Discussion), which confirms the point. The real-world node coverage numbers make the worry concrete: WCC drops coverage from 100% to 48% (medium) and 38% (large), with median cluster sizes around 3. The structure WCC produces on real networks is very different from the large, well-connected ground truth clusters in the benchmarks. So the claim that WCC 'typically improves accuracy' is not yet established for arbitrary networks; it is established for benchmarks whose ground truth satisfies the same connectivity constraint WCC imposes.\n\nThe authors are honest about some of this—they report the coverage drops and don't hide the timeouts/OOMs. The fix is straightforward: include a benchmark where ground truth clusters can be internally disconnected, or use real networks with known community labels that are not necessarily well-connected. As it stands, the accuracy result is conditional, but the paper's other contributions (the connectivity finding, the description-length analysis, the fast open-source implementation) are worth publishing.\n\nI'd send this to a serious referee. It's a useful paper with a fixable flaw, not a trivial one.","headline":"Solid empirical study with a useful post-processing tool, but the headline accuracy claim needs a benchmark that does not share WCC's connectivity assumption.","tokens_in":17662,"tokens_out":3739,"would_cite":true,"duration_ms":34083,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Stochastic block models often return internally disconnected communities, and a simple post-processing step, Well-Connected Clusters (WCC), that repeatedly removes small edge cuts typically improves clustering accuracy and scales to…","keywords":["community detection","stochastic block models","well-connectedness","edge connectivity","graph clustering","post-processing","Leiden algorithm","synthetic benchmark networks"],"falsifier":"Generate synthetic networks whose ground-truth communities are deliberately allowed to be poorly connected or internally disconnected, or use real networks with curated ground truth that includes weakly connected communities, then run SBM and SBM+WCC: if the accuracy gains of WCC vanish or reverse on those benchmarks, the claimed improvement is an artifact of testing only against well-connected ground truth.","tokens_in":16719,"feed_emoji":"✂️","tokens_out":12216,"duration_ms":101976,"temperature":0.7,"pith_summary":"Community detection with stochastic block models (SBMs) is widely used, but the clusters it returns are not guaranteed to be internally connected. This paper establishes that SBM clusterings of real-world networks frequently contain internally disconnected and poorly connected communities, with the tendency worsening as networks grow, and derives why the model's own objective prefers such clusters. To repair this, the authors introduce Well-Connected Clusters (WCC), a post-processing step that repeatedly removes small edge cuts from any cluster that fails a user-set well-connectedness threshold until every cluster passes. On synthetic benchmarks modeled after real networks, applying WCC to SBM clusterings typically improves clustering accuracy, and the step adds only about an hour or two on networks with millions of nodes.","feed_headline":"SBM clusters fall apart; a cut-removal pass repairs them","feed_subtitle":"Post-processing with WCC splits clusters into well-connected pieces and lifts accuracy on synthetic benchmarks.","key_machinery":"The central object is the Well-Connected Clusters (WCC) post-processor, defined against a threshold for edge-connectivity: a cluster of $n$ nodes is well-connected when its minimum edge cut exceeds $\\log_{10}(n)$; the paper uses the VieCut algorithm to find those cuts. WCC takes an SBM clustering, and for any cluster failing the threshold, deletes the minimum cut so the cluster splits in two, iterating until every cluster passes. The second load-bearing mechanism is the description-length decomposition of the degree-corrected SBM, $DL(A,b) = -\\log p(A|b,e,k) - \\log p(k|b,e) - \\log p(b) - \\log p(e)$: the $-\\log p(e)$ term, which grows with the number of blocks, is what makes the model prefer disconnected clusters, and it is this objective that WCC avoids by operating only on the output clustering.","core_discovery":"The central claim is that stochastic block model community detection has a systematic tendency to return internally disconnected clusters, and that this failure is baked into the model's own objective. Under the degree-corrected SBM, the description-length score penalizes a large number of blocks $B$ through the $-\\log p(e)$ term, which grows as $O(\\log B)$; splitting a disconnected cluster into its connected pieces raises $B$ and inflates the description length, so the optimizer leaves clusters disconnected even though the model-likelihood terms prefer connected ones. The proposed remedy, WCC, bypasses the objective entirely: given a clustering and a threshold such as $\\log_{10}(n)$ for a cluster of $n$ nodes, it removes the smallest edge cut of any failing cluster, never re-clustering, until every cluster is well-connected. On synthetic LFR and RECCS networks with known ground truth, SBM+WCC is typically at least as accurate as untreated SBM and competitive with Leiden-CPM(0.001)+CM, while on the largest real networks WCC finishes in under two hours on top of an SBM run that takes tens of hours.","pith_inferences":["If the disconnection tendency is caused by the block-count penalty, then constraining the SBM search to connected clusterings (the paper's own suggested future direction) could capture most of WCC's benefit without a post-processing stage.","Because the benchmark ground truth comes from Leiden, which guarantees well-connected communities, a test on synthetic networks with deliberately weak or disconnected ground-truth communities would reveal whether WCC's accuracy gains persist when the target communities are themselves poorly connected.","The user-set threshold suggests a resolution-style sweep: raising it above $\\log_{10}(n)$ would return smaller, tighter clusters and lowering it would return larger ones, giving practitioners a knob between coarse and fine partitions.","The results are established only for non-bipartite networks; since the paper found nearly all SBM clusters on bipartite networks are disconnected, WCC's behavior there is untested."],"forward_implications":["SBM practitioners can safely add WCC as a fast post-step that guarantees every reported community meets the user's connectivity threshold, at a runtime cost of under two hours even for networks with roughly 14 million nodes.","On non-bipartite networks, SBM+WCC is generally competitive with, and on several model conditions more accurate than, Leiden-CPM(0.001)+CM across NMI, ARI, AGRI, and RMI on the tested LFR and RECCS benchmarks.","WCC costs node coverage: the fraction of nodes in non-singleton clusters falls from 100% to 48% on medium and 38% on large non-bipartite networks on average, a larger drop than the Connected Components baseline.","The description-length analysis implies that any SBM variant whose objective penalizes the number of blocks will tend to prefer internally disconnected clusters; removing the $-\\log p(e)$ term flips the preference in 59 of 71 degree-corrected SBM networks.","WCC is not always free: on one RECCS network it exceeded 256 GB of RAM and on one LFR network it exceeded the 72-hour limit, while CC and CM completed in both cases."],"supporting_citations":[{"why":"The prior study by the same group showing that graph-tool SBM clusterings of large networks are mostly disconnected; this paper extends it.","marker":"[4]"},{"why":"Supplies the $\\log_{10}(n)$ well-connectedness standard, the Connectivity Modifier baseline, and the 27 LFR networks used for benchmarking.","marker":"[6]"},{"why":"graph-tool, the implementation of SBM (degree-corrected, non-degree-corrected, and planted partition) used for every clustering in the study.","marker":"[5]"},{"why":"Defines well-connected communities and the Leiden algorithm used both as a comparison method and to produce benchmark ground truth.","marker":"[2]"},{"why":"The LFR generator that produced the synthetic networks with ground-truth communities.","marker":"[15]"},{"why":"The RECCS generator used to produce additional synthetic networks that preserve edge connectivity.","marker":"[13]"},{"why":"VieCut, the practical minimum-cut algorithm WCC relies on to find and remove small edge cuts.","marker":"[20]"},{"why":"The degree-corrected stochastic block model, one of the three SBM variants evaluated.","marker":"[17]"},{"why":"A prior observation that microcanonical SBM returns disconnected components, whose derivation of a block-count penalty this paper extends to the degree-corrected model.","marker":"[24]"}],"fun_headline_variants":["SBM clusters are disconnected; WCC reconnects them","WCC heals SBM's disconnected communities","Fix SBM with WCC: remove cuts for connectivity","SBM+WCC outdoes SBM on disconnected clusters"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The accuracy results assume that synthetic networks whose ground-truth communities come from Leiden clusterings are a fair test of a method whose entire mechanism is to enforce exactly the kind of well-connectedness Leiden guarantees.","fun_headline_variants_meta":{"raw":{"variants":["SBM clusters are disconnected; WCC reconnects them","WCC heals SBM's disconnected communities","Fix SBM with WCC: remove cuts for connectivity","SBM+WCC outdoes SBM on disconnected clusters"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000329,"raw_usage":{"total_tokens":1816,"prompt_tokens":907,"completion_tokens":909,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":842}},"tokens_in":523,"tokens_out":909,"duration_ms":8654,"temperature":1.0,"reasoning_tokens":842,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T18:05:50.672866+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Generate synthetic networks whose ground-truth communities are deliberately allowed to be poorly connected or internally disconnected, or use real networks with curated ground truth that includes weakly connected communities, then run SBM and SBM+WCC: if the accuracy gains of WCC vanish or reverse on those benchmarks, the claimed improvement is an artifact of testing only against well-connected ground truth.","supporting_citations":[{"cited_title":"Benchmark graphs for testing community detection algorithms","cited_arxiv_id":null,"evidence_quote":"The LFR generator that produced the synthetic networks with ground-truth communities."},{"cited_title":"Synthetic Netw orks That Preserve Edge Connectivity","cited_arxiv_id":null,"evidence_quote":"The RECCS generator used to produce additional synthetic networks that preserve edge connectivity."},{"cited_title":"Practical Minimum Cut Alg orithms","cited_arxiv_id":null,"evidence_quote":"VieCut, the practical minimum-cut algorithm WCC relies on to find and remove small edge cuts."},{"cited_title":"Stochastic blockmodels and community st ructure in networks","cited_arxiv_id":null,"evidence_quote":"The degree-corrected stochastic block model, one of the three SBM variants evaluated."},{"cited_title":"Well-connectedness and community detection","cited_arxiv_id":null,"evidence_quote":"Supplies the $\\log_{10}(n)$ well-connectedness standard, the Connectivity Modifier baseline, and the 27 LFR networks used for benchmarking."},{"cited_title":"From Louvain to Leiden: guaran teeing well-connected communities","cited_arxiv_id":null,"evidence_quote":"Defines well-connected communities and the Leiden algorithm used both as a comparison method and to produce benchmark ground truth."},{"cited_title":"Improved Community Detection using Stochastic Block Models","cited_arxiv_id":"2502.00686","evidence_quote":"A prior observation that microcanonical SBM returns disconnected components, whose derivation of a block-count penalty this paper extends to the degree-corrected model."}],"review_version":1}