{"id":"60426a6a-c9d2-4b59-af8b-0cb13751deab","arxiv_id":"2507.10262","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A systematic empirical comparison of 14 cohesive subgraph models shows truss-based and combined models find denser subgraphs, while core-based models return larger, more interpretable ones.","lead":"This paper benchmarks 14 existing cohesive subgraph models on synthetic and real-world networks, plus a community search task. It gives practitioners a map of which models produce dense, small, or interpretable subgraphs for different network settings.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Table 6's parameter grids are not calibrated across model families, so the headline rankings may be artifacts of threshold choice rather than intrinsic model properties.","rationale":"The reader's weakest assumption already identifies Table 6 as load-bearing, and I agree. The concern is not about whether the models are implemented correctly or whether the field consensus is violated; it is about whether the experimental design can separate model properties from threshold choices. The paper's own limitation statement in Section 4.1 admits untuned/null results, and the figures aggregate over q settings without showing which cells are missing. A conditional verdict is appropriate: the benchmark idea is useful and the qualitative claims are plausible, but they are not yet robustly supported. I would keep the reader's CONDITIONAL verdict; no new objection changes it. If the proposed calibration check flipped the ranking, the appropriate verdict would be REJECT or UNVERDICTED; if it preserved the ranking, ACCEPT would be justified. Since the check has not been run, UNCHANGED is the honest recommendation.","tokens_in":28073,"tokens_out":4025,"duration_ms":48919,"concrete_test":"Rerun the synthetic and real-world comparisons with output-calibrated parameter choices: for each model family, select thresholds so that the returned subgraphs have matched size (e.g., the same number of nodes as the k-core output at k=3) or matched average density, and then compare cohesion metrics at those matched operating points. If truss/combined models no longer dominate on cohesion, the headline rankings are artifacts of Table 6. As a secondary check, rerun the q1–q4 figures with any model-dataset cell that returns null explicitly marked and excluded only in a sensitivity analysis; if conclusions vanish when nulls are dropped, the reporting gap matters.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central ranking — truss/combined models are more cohesive, core models are larger and more interpretable, SCAN wins community search — is inferred by comparing model families under the hand-picked grids in Table 6. The grids are not placed on any common scale: k-core runs at k=3,5,7,9; k-truss at k=4,6,8,10; (k,p)-core at (3,0.2)...(3,0.8); SCAN at (3,0.2)...(3,0.8); Alphacore at alpha=0.2...0.8. Nothing in the paper establishes that q1 for one model corresponds to q1 for another in any comparable sense of 'cohesiveness level.' Consequently, the observation that truss-based outputs are denser/smaller could simply mean the k-truss thresholds selected were relatively stricter than the k-core thresholds. This is not a theoretical inconsistency, but it is a load-bearing experimental-design assumption: if the grids were shifted (e.g., k-core at 10,12,14,16 vs k-truss at 3,4,5,6), the family-level ordering could reverse. The paper explicitly concedes in Section 4.1 that some results are untuned or null and not reported, so missing q values further bias family comparisons: a model that returns null at high q is silently absent from the 'more cohesive' end of the ranking while another model's large subgraph is included. The conclusion that one family is intrinsically more cohesive is therefore not established by the presented data.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper presents an experimental benchmark of fourteen existing cohesive subgraph discovery models on simple undirected unweighted graphs. The models are organized into five families (core-based, triangle-based, clique-based, connected-component-based, and other), and are evaluated on twenty LFR synthetic graphs, twelve real-world networks, seven evaluation metrics, and a community-search downstream task. The paper's headline conclusions are that truss-based and combined models produce more cohesive subgraphs, core-based models produce larger and more interpretable subgraphs, and graph-clustering approaches such as SCAN perform best for community search. The authors also release unified implementations of the algorithms.","tokens_in":28396,"tokens_out":3923,"duration_ms":49985,"significance":"If the benchmark is reliable, this is a useful service contribution to the cohesive-subgraph community: it brings fourteen models under one implementation, covers a wide range of network scales and synthetic configurations, and attempts a task-based comparison rather than a purely structural one. The public code and the transparency about null results are commendable. However, the central comparative claims rest on hand-chosen parameter grids whose cross-model comparability is not established, and several metric formulas in Section 4.1 are garbled as typeset, so the quantitative basis for the rankings needs substantial repair before the conclusions can be taken at face value. The contribution is still valuable as a broad qualitative survey, but the 'first comprehensive evaluation' framing should be softened unless the authors can document the absence of comparable prior benchmarks.","major_comments":[{"comment":"The parameter grids in Table 6 are not placed on any common scale, and this is load-bearing for the family-level rankings. For example, k-core runs at k=3,5,7,9 while k-truss runs at k=4,6,8,10, and (k,p)-core and SCAN use ratio thresholds at fixed k. Nothing in the paper establishes that q1 for one model corresponds to q1 for another in a comparable sense of 'cohesiveness level.' The observation that truss-based outputs are denser and smaller could simply mean that the selected truss thresholds were relatively stricter than the selected core thresholds. The paper itself concedes in Section 4.1 that 'some of our experimental results may not have been well-tuned or may not have been reported in cases where the algorithm returned null results,' which introduces a selection bias: a model that returns null at high q is silently absent from the cohesive end of the ranking. I recommend reporting the full result matrix including nulls, and adding a sensitivity analysis or a threshold-matching procedure (for example, matching outputs by size or density across model families) before drawing intrinsic-comparison conclusions.","section":"Section 4.1, Table 6"},{"comment":"Several metric formulas are garbled as typeset, which is serious because these metrics are the basis for all quantitative conclusions. The Cut Ratio formula is written as 1 - sum_{i in H, j in \\bar H} 1 / (|V[H]| * |V[G\\H]|), which as written has no clearly defined summand and is dimensionally wrong; the standard cut ratio should be the size of the edge cut divided by |V[H]| * |V[G\\H]|. The Inverse Conductance formula is written as 1 - sum_{i in H, j in \\bar H} 1 / min(d_H, d_{\\bar H}), which again omits the number of crossing edges and the correct volume denominators. The local-level Modularity expression l_c/|E| - d_c^2/(4|E|^2) does not match the standard Newman-Girvan modularity and is not derived or justified. The authors should provide correct, unambiguous formulas for every metric, preferably in a table with a reference to the standard definition.","section":"Section 4.1, Global-level evaluation metrics"},{"comment":"The synthetic experiments use only one LFR instance per parameter combination: for each of the five parameter types, four values are tested, but there is no replication across seeds and no error bars or variance reporting in Figures 18-24. Given that the qualitative claims are about differences between model families, a single instance per setting cannot establish that observed gaps are not due to LFR sampling noise. The authors should either generate multiple LFR realizations per parameter point and report means with variance, or explicitly state that the figures show single-instance behavior and restrict the conclusions to those instances.","section":"Section 4.2, Synthetic networks and Table 4"},{"comment":"The community-search evaluation treats every node in every identified cohesive subgraph as a query node and then measures NMI, ARI, and F1 on Karate and Polblogs. This protocol is fragile: on a 34-node graph and a 1,224-node graph, the scores are averaged over many overlapping queries, and the paper itself notes that a high accuracy score 'does not always indicate a good model for community search' because it may leave little room for improvement. The claim that SCAN 'performs best' for community search therefore needs a clearer baseline: what is the performance of simply returning the entire graph, and what is the performance of a dedicated community-search algorithm initialized by these cohesive subgraphs? Without such a baseline, the downstream-task conclusion is not yet supported.","section":"Section 4.2.4 and Section 4.3.2, Community search"}],"minor_comments":[{"comment":"The sentence 'The notation decomposition is the process that obtaining information about all cohesive subgraphs in a graph' is ungrammatical and should be rewritten; also define 'decomposition' and 'computation' explicitly before contrasting them.","section":"Section 2"},{"comment":"The Mahalanobis depth formula in Definition 21 is typeset with a stray superscript and an unclear covariance-matrix symbol: '(x - mu_F)^T -1 sum_F (x - mu_F)' should be '(x - mu_F)^T Sigma_F^{-1} (x - mu_F)' with Sigma_F defined as the covariance matrix.","section":"Section 3.1, Equation (1)"},{"comment":"The sentence 'with k = 3, the entire graph is returned by the k-truss returns the whole graph' contains a duplicated verb and should be corrected.","section":"Section 3.2, Example 5"},{"comment":"The colors are described as 'green-coloured and pick-coloured'; 'pick' should be 'pink', and the figure should be legible in grayscale if the journal version does not guarantee color printing.","section":"Section 3.5, Example 11"},{"comment":"The text says 'we utilise the global metrics which are presented in Table 4.1', but there is no Table 4.1; the metrics are described in Section 4.1, not in a numbered table.","section":"Section 4.3.1"},{"comment":"The arXiv PDF retains ACM conference-formatting placeholders such as 'Conference acronym XX, June 03-05, 2018, Woodstock, NY' and a DOI placeholder; these should be cleaned up before public dissemination as a journal article.","section":"Throughout"},{"comment":"The synthetic graph types are described clearly, but the default values (N=1,000, average degree=20, max degree=200, mu=0.2, t1=2, t2=1) are stated only in the caption of Table 4; consider making them part of the main text so the experimental design is self-contained.","section":"Section 4.1, Table 4"}],"recommendation":"major_revision","confidential_remarks":"The paper is a useful benchmark and the authors have done a substantial implementation service, but the central comparative claims are currently not robust to the parameter-grid choice and to the exclusion of null results. I would not reject: the issues are fixable with additional experiments and corrected formulas. I would also ask the editor to weigh whether the 'first comprehensive evaluation' claim needs moderation, since the paper does not survey prior benchmark efforts in enough depth to establish uniqueness."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a genuine first. The paper benchmarks 14 established cohesive subgraph models on 12 real-world graphs and 20 LFR synthetic graphs, with seven metrics and a community-search task. That is a useful contribution even though no new model is proposed. The qualitative conclusions — truss/combined models yield denser, smaller subgraphs; core-based models are larger and more interpretable; SCAN wins community search — are plausible and broadly supported by the figures. The paper also does a decent job of describing each model with worked examples, and it includes an honest limitations paragraph (Section 4.1) conceding that some results are untuned or missing due to null outputs.\n\nThe soft spots are real but mostly fixable. The load-bearing issue, as you noted, is Table 6: the parameter grids are not placed on any common scale. k-core runs at k=3,5,7,9; k-truss at k=4,6,8,10; SCAN at (3,epsilon) and (5,epsilon); and so on. Nothing establishes that q1 for one family is comparable to q1 for another in terms of 'cohesiveness level.' So the family-level ranking — truss more cohesive, core larger — could partly reflect where the thresholds were placed rather than intrinsic model properties. The paper's own admission of null results and untuned settings makes this worse, because a model that returns nothing at high q is silently dropped from the 'more cohesive' end of the comparison. I agree this is the central weakness, and it is not resolved by the current analysis.\n\nSecondary issues: the metric formulas in Section 4.1 are garbled in places (the cut-ratio and inverse-conductance expressions as typeset do not look like correct definitions), so a reader cannot reproduce the metrics from the text alone. There are no error bars or variance information on the synthetic experiments, even though LFR generation is stochastic. The paper promises public source code but the arXiv version gives no link. That matters for a benchmark paper.\n\nNone of this is fatal. The benchmark idea is sound, the coverage is broad, and the qualitative story is likely in the right direction. But the paper does not fully establish that its rankings are driven by model properties rather than threshold choices. That is a fixable experimental-design gap, not a theoretical inconsistency.\n\nWho gets value: researchers choosing a cohesive subgraph model for a downstream task, and newcomers wanting a map of the area. It deserves serious refereeing; the right outcome is a major revision that recalibrates or at least defends the parameter grids, adds code and error bars, and fixes the metric definitions.","headline":"A genuinely useful first benchmark of 14 cohesive subgraph models, with a load-bearing parameter-calibration flaw that a serious revision can fix.","tokens_in":28840,"tokens_out":2220,"would_cite":true,"duration_ms":25134,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims the first systematic evaluation of 14 cohesive subgraph models, finding that truss-based models are denser, core-based models are larger and more interpretable, and SCAN performs best on community search.","keywords":["cohesive subgraph discovery","k-core","k-truss","community search","graph clustering","benchmark evaluation","social network analysis"],"falsifier":"Re-run the same 14 models on the same datasets with per-dataset parameter tuning, for instance choosing each model's thresholds to maximize modularity or community-search accuracy on held-out ground truth, and check whether the qualitative ranking still holds: truss and combined models denser, core models larger, SCAN best for community search. If the ordering flips by dataset, the uniform-grid choice was the load-bearing decision.","tokens_in":27897,"feed_emoji":"🕸️","tokens_out":6951,"duration_ms":70014,"temperature":0.7,"pith_summary":"This paper is a systematic experimental comparison of 14 cohesive subgraph models on simple undirected and unweighted graphs, using synthetic and real-world networks and a community search task. The authors try to establish that model families have predictable tradeoffs: truss-based and combined core-and-truss models return denser, more cohesive subgraphs; core-based models return larger, easier-to-interpret subgraphs; and for community search, graph clustering models such as SCAN give the most accurate communities. They also argue that for downstream tasks, truss-based or combined approaches are the safer lower-bound initialization, while core-based approaches leave room for improvement. If these findings hold, they give practitioners a grounded way to choose a model by application rather than by familiarity.","feed_headline":"14-model benchmark: truss densest, SCAN best for search","feed_subtitle":"Core models give bigger, clearer subgraphs; truss models give tighter ones. Choose by task.","key_machinery":"The argument is carried by a unified evaluation harness rather than by a single theorem. Fourteen algorithms are brought into one codebase with a common interface, and a default parameter grid (Table 6) assigns each model four cohesiveness levels so that every model is scored on the same thresholds. Quality is measured by seven metrics—average degree, cut ratio, clustering coefficient, edge density, inverse conductance, average connected component size, and modularity—computed in two ways: locally, averaging over each connected component, and globally, treating all returned nodes as one subgraph. Synthetic graphs are generated by varying five structural parameters, and real graphs range from 34 to roughly 4 million nodes, grounding the comparison in both controlled and natural settings. This machinery turns qualitative model categories (core, triangle, clique, connected-component, and other) into measurable rankings.","core_discovery":"On its own terms, the paper claims to provide the first comprehensive evaluation of 14 existing cohesive subgraph models, all implemented in one project and run on 12 real-world networks plus 20 synthetic benchmark graphs with varied generative parameters. Across seven evaluation metrics computed at local and global levels, the experimentally supported finding is that truss-based models (k-truss, k-tripeak) and combined models (k-core-truss, (k,s)-core) consistently produce more cohesive subgraphs than core-based models, while core-based models (k-core and variants) produce larger subgraphs that are easier for users to interpret. The paper also reports that Alphacore and SCAN produce more cohesive results, and that for the community search downstream task, graph clustering algorithms such as SCAN perform best, with Alphacore, k-distance clique, k-core, and (k,s)-core giving comparable accuracy. A final recommendation is that when a cohesive subgraph model is used only as an initial solution, truss-based or combined approaches are the preferred lower bound, whereas core-based approaches are suitable when there is room for downstream refinement.","pith_inferences":["The same experimental harness could be extended to weighted, directed, signed, bipartite, or hypergraph settings; the core-versus-truss trade-off would likely reappear, but the specific rankings would need recalibration.","A testable extension is to compare model rankings on a larger set of ground-truth community datasets with per-dataset tuned parameters, to see whether SCAN's community-search advantage persists outside the two datasets used here.","The local-versus-global evaluation split suggests that any single-number benchmark can be misleading; rankings on edge density or conductance can change simply by averaging per component instead of aggregating, so future benchmarks should report both.","The interpretability-versus-cohesion framing points toward a design space of hybrid models that interpolate between degree and support constraints, where the paper's comparison could serve as the baseline."],"forward_implications":["If the findings hold, users who value interpretability should start with core-based models such as k-core or (k,p)-core.","Users who value cohesion should prefer truss-based or combined models such as k-truss, k-tripeak, k-core-truss, or (k,s)-core.","For community search initialization, graph clustering models such as SCAN give the most accurate starting communities, while truss-based or combined models are the recommended lower-bound initial solution.","Ratio-based models such as SCAN and (k,p)-core behave differently as network size grows, so conclusions drawn on small graphs should not be assumed to transfer to million-node networks.","Parameter selection remains the main practical obstacle; the paper's uniform grid shows rankings but does not remove the need for per-dataset tuning."],"supporting_citations":[{"why":"Supplies the synthetic benchmark generator used for the five types of controlled networks.","marker":"[24]"},{"why":"Supplies the global-level community scoring metrics used to evaluate real-world networks.","marker":"[8]"},{"why":"Provides the graph-library implementations used for k-core, k-truss, k-ECC, and k-VCC baselines.","marker":"[18]"},{"why":"Provides the Karate network with ground-truth communities used in the community search evaluation.","marker":"[48]"},{"why":"Provides the Polblogs network with ground-truth communities used in the community search evaluation.","marker":"[1]"},{"why":"Defines the k-core model, a central core-based baseline.","marker":"[34]"},{"why":"Defines the k-truss model, a central triangle-based baseline.","marker":"[10]"},{"why":"Defines SCAN, the graph clustering model that performs best on community search in the paper's experiments.","marker":"[46]"},{"why":"Defines k-core-truss, a combined core-and-truss model the paper evaluates.","marker":"[26]"},{"why":"Defines (k,s)-core, a combined core-and-truss model the paper evaluates.","marker":"[50]"}],"fun_headline_variants":["Truss models yield tighter subgraphs, core models clearer","14 subgraph models benchmarked: truss for cohesion, core for size","Cohesive subgraph models: truss tighter, core interpretable","SCAN best for community search in cohesive subgraph test"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The comparison's fairness rests on one hand-picked parameter grid (Table 6) being applied uniformly to all datasets, and the paper itself concedes that some results may not be well-tuned or may be missing when an algorithm returned nothing.","fun_headline_variants_meta":{"raw":{"variants":["Truss models yield tighter subgraphs, core models clearer","14 subgraph models benchmarked: truss for cohesion, core for size","Cohesive subgraph models: truss tighter, core interpretable","SCAN best for community search in cohesive subgraph test"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000604,"raw_usage":{"total_tokens":2796,"prompt_tokens":898,"completion_tokens":1898,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":514,"completion_tokens_details":{"reasoning_tokens":1825}},"tokens_in":514,"tokens_out":1898,"duration_ms":17060,"temperature":1.0,"reasoning_tokens":1825,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:35:15.950146+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the same 14 models on the same datasets with per-dataset parameter tuning, for instance choosing each model's thresholds to maximize modularity or community-search accuracy on held-out ground truth, and check whether the qualitative ranking still holds: truss and combined models denser, core models larger, SCAN best for community search. If the ordering flips by dataset, the uniform-grid choice was the load-bearing decision.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the synthetic benchmark generator used for the five types of controlled networks."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the global-level community scoring metrics used to evaluate real-world networks."},{"cited_title":"2008.Exploring network structure, dynamics, and function using NetworkX","cited_arxiv_id":null,"evidence_quote":"Provides the graph-library implementations used for k-core, k-truss, k-ECC, and k-VCC baselines."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Karate network with ground-truth communities used in the community search evaluation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Polblogs network with ground-truth communities used in the community search evaluation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the k-core model, a central core-based baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the k-truss model, a central triangle-based baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines SCAN, the graph clustering model that performs best on community search in the paper's experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines k-core-truss, a combined core-and-truss model the paper evaluates."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines (k,s)-core, a combined core-and-truss model the paper evaluates."}],"review_version":1}