{"id":"9383561e-0723-4539-9be6-6de2e28077af","arxiv_id":"2412.02704","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A heuristic combining 2-club edge deletion with vertex splitting achieves the best F-score among tested methods on overlapping LFR benchmark graphs.","lead":"This paper presents a graph clustering method that lets one data point belong to several clusters at once, and it relaxes the usual requirement that all members of a cluster be directly connected. The authors report better cluster quality than three established algorithms on a standard synthetic benchmark, but they do not release code or statistical error bars.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The LFR F-score advantage of 2CCEDVS over ClusterONE (0.9159 vs 0.8874) is reported as an average with no variance, per-instance data, or paired significance test, and the benchmark/instance setup is under-specified; the claimed 'notable effectiveness' is therefore not statistically established.","rationale":"The reader's CONDITIONAL verdict already flags missing error bars and code, but its stated weakest assumption is the random-walk ordering proxy. I agree that proxy is unmotivated (the claim in Sec. 3 that 'the 8th power is enough to reach the stationary vector' is not generally true, and no mixing bound for H_v is given), but that is a design rationale rather than the deciding evidence. The load-bearing point is that the decisive quantitative result, Table 3's F-score advantage, is presented as a bare mean over an undocumented instance set with no statistical characterization. If the advantage is within run-to-run noise, the central claim fails regardless of whether the random-walk ordering is sensible. The paired Wilcoxon test I propose settles this directly; if the authors provide code/instances and the gap is significant, the CONDITIONAL verdict should move toward ACCEPT. This is why I recommend UNCHANGED rather than REJECT: the concern requires the missing statistical/reproducibility evidence, which the CONDITIONAL verdict already requests.","tokens_in":10627,"tokens_out":12009,"duration_ms":109781,"concrete_test":"Run a paired LFR experiment with at least 30 instances per parameter setting (fixed seeds; specified n, average degree, max degree, pout, on, om), computing F-score for 2CCEDVS and ClusterONE on identical instances, and apply a Wilcoxon signed-rank test to the per-instance F-score differences. If p >= 0.05 or the median 2CCEDVS advantage is below 0.02, the claimed superiority over ClusterONE is not established and the central effectiveness claim should be weakened.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim (Sec. 1 and Sec. 5) is supported mainly by Table 3, where 2CCEDVS has mean F-score 0.9159 on the LFR benchmark versus 0.8874 for ClusterONE (MCL 0.7789, 2CCED 0.6675, KaPoCE 0.5959). Sec. 4.2 states only that 'multiple graphs' were generated by varying pout from 0 to 0.12 and vertex count from 50 to 200; no number of instances, seeds, overlap parameters (on, om), per-instance scores, standard deviations, or paired tests are given. The F-score gap is 0.0285, which is small relative to the stochasticity of the LFR generator and the tiny graphs (137 vertices average). Without evidence that the gap is reproducible and significant, the claim of 'notable effectiveness' is not supported. Reproducibility is further blocked by Algorithm 2's under-specification: when only one unassigned vertex remains, the line 'add an unassigned max degree one to X' cannot be executed; cost(bestCluster) is undefined for the empty cluster; and process(bestCluster) does not specify how split copies enter the assigned set. No code or benchmark instances are released, so Table 3 cannot be independently checked.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a new formulation of overlapping correlation clustering, 2CCEDVS (2-Club Cluster Edge Deletion with Vertex Splitting), in which clusters must have diameter at most two after edge deletions and vertices may be cloned to belong to multiple clusters. It presents two heuristics, Algorithm 1 for 2CCED and Algorithm 2 for 2CCEDVS, and evaluates them against MCL, ClusterONE, and KaPoCE on four biological gene-function networks (Table 2) and on an extended LFR overlapping benchmark (Table 3). The authors report that 2CCEDVS achieves the best average F-score (0.9159) on the LFR benchmark, ahead of ClusterONE (0.8874), and competitive intra- and inter-cluster distances on the biological networks, and they conclude that the model is notably effective for overlapping correlation clustering.","tokens_in":10907,"tokens_out":7495,"duration_ms":63529,"significance":"If the empirical claim holds, the paper would make a useful contribution: it combines a meaningful relaxation of cluster editing (diameter-2 clusters rather than cliques) with vertex splitting, and it compares against strong external baselines on external benchmarks without fitting parameters to the test data. The LFR comparison and biological network tables provide concrete evidence for the approach. The main significance is currently limited by the absence of statistical support, the incomplete pseudocode, and the lack of released code or generated instances, all of which prevent independent verification of the central claim.","major_comments":[{"comment":"The central claim of 'notable effectiveness' (stated in Section 1 and repeated in Section 5) is not statistically established. The table reports only average F-score values; Section 4.2 does not state the number of LFR instances, the random seeds, the overlap parameters (on, om), or the per-instance scores. The reported advantage of 2CCEDVS over ClusterONE is 0.9159 versus 0.8874, a gap of 0.0285, while the graphs are small (average 137 vertices). Without standard deviations, per-instance data, or a paired significance test, the observed gap could be within stochastic variation of the generator. Please provide this information or weaken the conclusion accordingly.","section":"Section 4.2, Table 3"},{"comment":"The pseudocode is not executable as written and cannot be used to reproduce Table 3. In Algorithm 1, 'add_s_club' is never defined and the cluster-update logic conflates vertices and clusters. In Algorithm 2, line 4 ('add an unassigned max degree one to X') cannot be executed when only one unassigned vertex remains; cost(bestCluster) is undefined because bestCluster is initialized to the empty set; and process(bestCluster) does not specify how a split copy is added to the assigned set or how the edited graph is updated. Please define the missing subroutines and state the termination and output conventions precisely.","section":"Section 3, Algorithms 1 and 2"},{"comment":"The ordering heuristic rests on an unverified assumption about the random walk. The text asserts that the 8th power of the transition matrix is 'enough to reach the stationary vector,' but no proof, convergence criterion, or sensitivity analysis is provided; for a periodic random walk, the 8th power need not be close to stationarity, and the graph H_v with added weighted arcs need not be irreducible. Because the cluster construction depends entirely on this ordering and on the 'cheapest prefix' rule, the empirical F-score advantage could depend on these ad-hoc choices. Please add a sensitivity analysis over the power parameter and prefix rule, or justify these choices theoretically.","section":"Section 3, Algorithm 2"},{"comment":"Reproducibility is currently blocked by missing artifacts. No code, generated LFR instances, or per-instance results are released; Section 4.2 only says 'multiple graphs' were generated, and the link provided points to the generic LFR benchmark repository rather than the exact instances used. This prevents independent checking of the averages in Table 3. Please release the implementation and benchmark instances, or include a complete per-instance table with seeds and parameter settings.","section":"Section 4"},{"comment":"The biological-network evaluation is difficult to interpret because the paper does not define how average intra- and inter-cluster distances are computed, does not state whether higher or lower values are preferable, and reports a single run per algorithm with no variance. For example, on bio-CE-GT the 2CCEDVS inter-cluster distance is 3.24 versus 3.74-3.78 for the other algorithms; if larger inter-cluster distance indicates better separation, this is not 'competitive' as claimed in Section 4.3. Please clarify the definitions and either temper the claim or provide repeated-run statistics.","section":"Section 4.1, Table 2"}],"minor_comments":[{"comment":"The sentence 'In some cases, without allowing data elements to belong to more than one cluster each, makes it hard to achieve any clustering via classical partition-based methods' is ungrammatical and should be revised.","section":"Abstract and Section 1"},{"comment":"The phrase 'branching on each path of length whose endpoints are at distance three' is missing the intended path length; please fix the typo.","section":"Section 2"},{"comment":"The phrase 'the number of edges of vertices from 50 to 200' should presumably read 'the number of vertices from 50 to 200'.","section":"Section 4.2"},{"comment":"The 'Graph Properties' columns are not algorithm-specific and are placed in the same table as per-algorithm results; consider separating the benchmark statistics into a distinct table or caption.","section":"Table 3"},{"comment":"The while loop over a sorted score dictionary is redundant because the for loop over score already visits each vertex; please clarify the intended control flow.","section":"Algorithm 1"},{"comment":"The sentence 'Benchmarks show that for the same program, C and C++ are faster than Java and Java is many times faster than Python' is awkward; consider rephrasing to 'benchmark comparisons show...'","section":"Section 4.3"}],"recommendation":"major_revision","confidential_remarks":"The paper's main contribution is the empirical evaluation, so the missing statistical detail and the incomplete pseudocode are central rather than cosmetic. I would not reject on novelty grounds; the vertex-splitting plus 2-club combination is a reasonable new model. Releasing code and generated benchmark instances would substantially increase the value of the paper for the community."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a heuristic-plus-experiments paper for 2CCEDVS, a problem variant defined by the same group in the companion paper [35]. The genuinely new piece here is the practical heuristic itself — random-walk-based vertex ordering with a prefix-cost selection — and the first reported comparison against MCL, ClusterONE, and KaPoCE. That is incremental but real, and the experiments cover both synthetic LFR graphs and real biological networks. Credit where it is due: the authors are unusually candid, explicitly saying the LFR result was surprising and calling for further scrutiny. That honesty is welcome.\n\nThe soft spots are not fatal but they are real and mostly centered on the central claim. The paper says the evaluation “clearly show[s] the notable effectiveness” of 2CCEDVS, yet Table 3 reports only mean F-scores over some unspecified number of LFR instances. No per-instance scores, no standard deviations, no paired significance test. The average graph has 137 vertices, and the gap to ClusterONE is 0.0285. Given LFR stochasticity, the claim is plausible but not established. The biological-network results are more descriptive; inter-cluster distances are close across algorithms, and the intra-cluster distance results are attributed to known trade-offs between quality metrics. Those are secondary.\n\nThe reproducibility problems are also real. Algorithm 2 has under-specified lines: “add an unassigned max degree one to X” is not executable when one vertex remains, cost(bestCluster) is undefined when bestCluster is empty, and process(bestCluster) does not state how split copies enter the assigned set. The 8th power in the random walk is justified only by a remark about the stationary vector, which is not quite a full argument. None of this is a load-bearing flaw in the heuristic’s concept, but it blocks independent verification. No code or benchmark instances are released, so Table 3 cannot be checked.\n\nWho is this for? Researchers working on overlapping correlation clustering or graph-editing heuristics. If the authors release code and instances and add basic statistical care, this could become a useful baseline. It deserves a serious referee, and I would send it out, but I would expect major revision: fix the pseudocode, release artifacts, report per-instance results with variance and significance, and soften the “notable effectiveness” phrasing until the evidence supports it. My own verdict would be conditional, not reject.","headline":"Plausible heuristic for a problem variant this group defined in a companion paper, but the headline empirical claim rests on averages without variance, significance, or released artifacts.","tokens_in":11444,"tokens_out":1447,"would_cite":false,"duration_ms":16528,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that allowing vertex splitting in 2-club cluster edge deletion produces a heuristic that outperforms the best-known correlation clustering algorithms on overlapping benchmark networks.","keywords":["correlation clustering","vertex splitting","2-club","cluster editing","overlapping communities","graph editing heuristic","LFR benchmark","random walk ordering"],"falsifier":"A concrete test: generate LFR graphs with average number of communities per vertex at 3 or higher and mixing parameter up to 0.5, run 2CCEDVS and ClusterONE, and check whether 2CCEDVS's F-score remains the highest; if ClusterONE wins, the claimed effectiveness is specific to low-overlap settings.","tokens_in":10401,"feed_emoji":"🕸️","tokens_out":9047,"duration_ms":75238,"temperature":0.7,"pith_summary":"The paper tries to establish that correlation clustering with overlapping clusters works better when clusters are relaxed from cliques to 2-clubs (diameter at most two) and vertices are allowed to be cloned through splitting. It introduces a heuristic, 2CCEDVS, that grows clusters from a vertex by ranking its closed 2-neighborhood with an eighth-power random-walk transition matrix and picking the cheapest prefix that forms a 2-club under a cost that deletes single outgoing edges and splits high-degree boundary vertices. The paper reports that on the extended LFR benchmark, 2CCEDVS attains the highest F-score (0.9159) among MCL, ClusterONE, KaPoCE and its own 2CCED variant. On four biological networks it produces competitive intra-cluster distances and the smallest inter-cluster distances in most cases. The significance is that overlapping, distance-based clusters can be found without requiring the number of clusters or hyperparameter tuning.","feed_headline":"Vertex splitting tops overlapping clustering benchmark","feed_subtitle":"The 2-club edge-deletion heuristic beat MCL, ClusterONE, and KaPoCE on LFR networks with ground-truth overlap.","key_machinery":"The pivotal construction is the 2-club with vertex splitting, denoted 2CCEDVS: a graph is edited into a disjoint union of 2-clubs, where each 2-club is a set of vertices with pairwise distance at most two, and a vertex may be split so that different copies inherit different parts of its neighborhood, making overlap possible. The heuristic's engine is the random-walk ordering in Algorithm 2: for each candidate vertex $v$, form the transition matrix of a random walk on the closed 2-neighborhood of $v$, with additional weighted arcs from distance-2 vertices back to $v$ reflecting neighbors outside the neighborhood; take the 8th power of this matrix applied to the unit vector at $v$; order vertices by decreasing resulting probability. Then the algorithm scans prefixes of this order that form a 2-club, computes the cluster cost as the sum over vertices of (0 for outdegree 0, 1 edge deletion for outdegree 1, one split for outdegree $>1$) divided by cluster size, and selects the prefix minimizing cost. This cost-guided prefix selection is what converts the local spectral ordering into an actual cluster.","core_discovery":"The central claim is that the 2CCEDVS model—turn the graph into a disjoint union of 2-clubs using edge deletions and vertex splittings—yields better overlapping clusters than existing correlation clustering approaches. The paper's heuristic realizes this by repeatedly selecting an unassigned vertex, ordering the vertices in its closed 2-neighborhood by the stationary-like vector obtained after eight steps of a random walk, and then evaluating every prefix that is a 2-club with a cost function that charges 0 for vertices with no outside neighbors, 1 for deleting a single edge, and one split for vertices with multiple outside neighbors; the cheapest prefix becomes a cluster. In the extended LFR benchmark (average 137 vertices, 1150 edges, up to 1.93 communities per vertex), 2CCEDVS obtains F-score 0.9159, ahead of ClusterOne (0.8874), MCL (0.7789), 2CCED (0.6675), and KaPoCE (0.5959). On four biological networks, 2CCEDVS is second best in intra-cluster distance and generally best in inter-cluster distance, while KaPoCE, which optimizes for cliques, has the smallest intra-cluster distance but the worst F-score on LFR. The paper interprets these results as evidence that the relaxed 2-club model combined with vertex splitting is a more realistic and effective formulation of correlation clustering with overlap.","pith_inferences":["An implication the paper does not explore: the 8th-power random-walk ordering may be replaceable by simpler local scores, such as degree or common-neighbor counts; if those matched the F-score, the method would reduce to a cheap greedy rule.","The benchmark's average overlap is modest (1.30 communities per vertex, max 1.93); on datasets with genuinely high overlap (3+ memberships per vertex), the per-split cost may make 2CCEDVS overly conservative and lower its F-score relative to ClusterONE.","The cost function normalizes by cluster size, which favors larger clusters; on LFR graphs with skewed community size distributions this could bias precision/recall, suggesting a testable variant that normalizes by perimeter instead of size.","If the heuristic were reimplemented in C++ or GPU, the speed comparison would change materially; the paper's Python timings are not directly comparable to C/C++ baselines."],"forward_implications":["If the empirical claim holds, overlapping community detection can be performed without user-specified cluster counts or parameter tuning, and with higher F-score than flow-based (MCL), cohesiveness-based (ClusterONE), or clique-editing (KaPoCE) methods on LFR networks.","The success of 2CCED over KaPoCE supports the broader thesis that relaxing clusters from cliques to bounded-diameter subgraphs is not only more flexible but also produces better solutions to the same editing task.","Vertex splitting, previously used only with clique editing, is shown to be an effective operation for generating overlap, making it a candidate component for other graph-modification clustering problems.","Because the cost function handles outdegree 0/1/>1 uniformly, the same heuristic extends to weighted graphs and to s-clubs with s > 2 with no change to the algorithm structure."],"supporting_citations":[{"why":"Defines 2CCEDVS and proves it NP-hard and FPT, providing the problem studied by the heuristic.","marker":"[35]"},{"why":"Defines 2-Club Cluster Edge Deletion and establishes its NP-hardness, the base problem the paper relaxes.","marker":"[12]"},{"why":"Introduces correlation clustering, the objective that the new model reformulates.","marker":"[6]"},{"why":"Formulates clustering as graph modification (cluster editing), the framework the paper modifies.","marker":"[7]"},{"why":"Markov Clustering (MCL) is one of the baseline algorithms for overlapping correlation clustering in the experiments.","marker":"[32]"},{"why":"ClusterONE is the main overlapping-community baseline and supplies the cohesiveness measure and the biological network context.","marker":"[20]"},{"why":"KaPoCE is the state-of-the-art heuristic for Cluster Editing and the clique-based baseline that 2CCED outperforms.","marker":"[33]"},{"why":"The extended LFR benchmark generator provides the synthetic graphs with ground-truth overlap used for F-score evaluation.","marker":"[43]"},{"why":"Introduces Cluster Editing with Vertex Splitting, the operation that 2CCEDVS adapts to 2-clubs.","marker":"[24]"}],"fun_headline_variants":["2-club edge-deletion beats MCL and ClusterONE on overlapping clusters","Vertex splitting yields better overlapping clusters than MCL","2CCEDVS heuristic: edge deletions and cloning for overlapping clusters","2-club split heuristic leads F-score on overlapping LFR"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that ordering vertices by the eighth power of the random-walk transition matrix over the closed 2-neighborhood, then taking the cheapest prefix that forms a 2-club, yields clusters close to the true overlapping structure, and that the ordering remains a good proxy when graph size, overlap, and mixing parameters change; no sensitivity analysis is reported for the power or the prefix rule.","fun_headline_variants_meta":{"raw":{"variants":["2-club edge-deletion beats MCL and ClusterONE on overlapping clusters","Vertex splitting yields better overlapping clusters than MCL","2CCEDVS heuristic: edge deletions and cloning for overlapping clusters","2-club split heuristic leads F-score on overlapping LFR"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00065,"raw_usage":{"total_tokens":3050,"prompt_tokens":1080,"completion_tokens":1970,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":696,"completion_tokens_details":{"reasoning_tokens":1898}},"tokens_in":696,"tokens_out":1970,"duration_ms":13079,"temperature":1.0,"reasoning_tokens":1898,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:21:00.979025+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete test: generate LFR graphs with average number of communities per vertex at 3 or higher and mixing parameter up to 0.5, run 2CCEDVS and ClusterONE, and check whether 2CCEDVS's F-score remains the highest; if ClusterONE wins, the claimed effectiveness is specific to low-overlap settings.","supporting_citations":[{"cited_title":"On the Complexity of 2-club Cluster Editing with Vertex Splitting","cited_arxiv_id":"2411.04846","evidence_quote":"Defines 2CCEDVS and proves it NP-hard and FPT, providing the problem studied by the heuristic."},{"cited_title":"On editing graphs in to 2-club clusters","cited_arxiv_id":null,"evidence_quote":"Defines 2-Club Cluster Edge Deletion and establishes its NP-hardness, the base problem the paper relaxes."},{"cited_title":"Correlatio n clustering","cited_arxiv_id":null,"evidence_quote":"Introduces correlation clustering, the objective that the new model reformulates."},{"cited_title":"Cluster graph mo dification problems","cited_arxiv_id":null,"evidence_quote":"Formulates clustering as graph modification (cluster editing), the framework the paper modifies."},{"cited_title":"Graph clustering by flow simulation","cited_arxiv_id":null,"evidence_quote":"Markov Clustering (MCL) is one of the baseline algorithms for overlapping correlation clustering in the experiments."},{"cited_title":"Detect ing overlapping protein complexes in protein-protein interaction networks","cited_arxiv_id":null,"evidence_quote":"ClusterONE is the main overlapping-community baseline and supplies the cohesiveness measure and the biological network context."},{"cited_title":"Pace solver de- scription: Kapoce: A heuristic cluster editing algorithm","cited_arxiv_id":null,"evidence_quote":"KaPoCE is the state-of-the-art heuristic for Cluster Editing and the clique-based baseline that 2CCED outperforms."},{"cited_title":"Benchmark graphs for testing community detection algorithms","cited_arxiv_id":null,"evidence_quote":"The extended LFR benchmark generator provides the synthetic graphs with ground-truth overlap used for F-score evaluation."},{"cited_title":"Cluster editing with vertex splitting","cited_arxiv_id":null,"evidence_quote":"Introduces Cluster Editing with Vertex Splitting, the operation that 2CCEDVS adapts to 2-clubs."}],"review_version":1}