{"id":"55562c91-19a0-4104-a5b2-3a3702c86dc1","arxiv_id":"2411.10290","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A new benchmark suite and dataset shows that correlation clustering and ParHAC outperform the modularity-based methods commonly found in popular graph clustering libraries.","lead":"PCBS is an open-source suite of eleven parallel graph clustering algorithms plus benchmarking tools. It compares them across community detection, embedding classification, dense subgraph mining, and near-duplicate detection, and reports that correlation clustering and hierarchical agglomerative clustering give the best quality on most tasks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"NGrams 'high-resolution' labels are thresholded versions of the same embedding similarities used as edge weights, so the fourth-task ranking (ParHAC best) is partly an artifact of label construction rather than evidence of general clustering quality.","rationale":"The paper's central empirical claim has two parts: (1) PCBS is faster than existing systems, and (2) correlation clustering is best on three tasks and ParHAC on the fourth. Part (1) is supported by direct timing comparisons and public, reproducible code. Part (2) rests on four task evaluations. Three of those tasks use class labels or density objectives that are independent of graph construction; the NGrams task does not, because the same dot-product similarities that define edge weights also define the positive labels. The reported threshold robustness in Figure 13 shows stability across nearby thresholds but does not remove the circularity: all tested thresholds are still functions of the same embedding similarity. Consequently, the fourth-task ranking is a test of similarity-threshold recovery, and the specific ParHAC-versus-Affinity margin (0.83 versus 0.82) is too small to support a general qualitative conclusion about which algorithm is best for high-resolution clustering. This is a real limitation, but it does not overturn the benchmark contribution or the community-detection, vector-embedding, and dense-subgraph findings; it should be disclosed as a limitation or addressed with an independent label source. The reader's CONDITIONAL verdict already captures this, and I see no reason to move it. I do not treat the missing multiple-seed runs as equally load-bearing, since LP and SLPA are not the top-performing methods in the headline result.","tokens_in":31364,"tokens_out":5389,"duration_ms":53539,"concrete_test":"Re-evaluate the NGrams task against an independent ground truth: either human-annotated near-duplicate pairs or labels generated from a different embedding model (e.g., a sentence-transformer) while keeping the graph constructed from the original gecko embeddings. Recompute Table 9; if ParHAC-0.01 and Affinity no longer lead, the fourth-task best-algorithm claim is an artifact of the self-referential label construction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The NGrams task in Section 3.5 is the only task supporting the claim that ParHAC, not correlation clustering, is the best algorithm, and its ground truth is generated from the same quantity that defines the graph's edge weights. Per Section C.1, the graph is an exact 50-nearest-neighbor graph on text embeddings with edge weights given by dot-product similarity, and the 96,000 labels are sampled pairs from similarity buckets that are marked positive exactly when the same dot product exceeds 0.92. Precision and recall in Section 3.5 are computed on these pairs. A clustering that places high-weight neighbors in one cluster therefore recovers the label-generation rule rather than an independently established notion of near-duplication. This is visible in Table 9: threshold-only Connectivity achieves AUC 0.77, nearly tied with Correlation at 0.77, and only 0.06 below ParHAC-0.01's 0.83. The claim that ParHAC obtains the best quality on the fourth task thus rests on a task whose target is partially defined by the input signal the weighted algorithms consume. This does not invalidate the other three task results or the benchmark suite, but it does weaken the headline summary that the best algorithm on each task was identified.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces PCBS, a benchmark suite that packages eleven parallel graph clustering algorithms, a set of quality metrics, and an evaluation harness, together with new weighted graph datasets derived from embeddings and a new NGrams near-duplicate dataset with ground-truth labels. The authors compare PCBS implementations against NetworKit, Neo4j, TigerGraph, and SNAP across four tasks: community detection, vector embedding clustering, dense subgraph partitioning, and high-resolution clustering. They report that PCBS is substantially faster than the baselines on most workloads, that correlation clustering obtains the highest quality on three of the four tasks, and that ParHAC is best on the high-resolution NGrams task. The manuscript also includes a comparative study of modularity-optimization implementations and an appendix with additional datasets and scalability experiments.","tokens_in":31688,"tokens_out":4814,"duration_ms":47257,"significance":"If the results hold, PCBS is a useful community resource for benchmarking scalable graph clustering: the code and datasets are released, the experimental configuration is described in detail, and the evaluation spans a broad collection of real and synthetic graphs. The paper also contributes a new large-scale text-similarity graph with many ground-truth labels. The speed comparisons are transparently scoped (hardware, thread counts, and configuration files are given), and the authors make the comparison methodology reusable. However, the headline algorithm-ranking conclusions are weakened by a circular ground-truth construction in the NGrams task and by an overstatement of the dense-subgraph-partitioning results; these issues affect the central claim that the best algorithm on every task has been identified.","major_comments":[{"comment":"The NGrams ground-truth labels are generated by thresholding the same dot-product embedding similarities that define the edge weights of the 50-nearest-neighbor graph: pairs with similarity above 0.92 are labeled as belonging to the same cluster. This makes the high-resolution task partially a test of whether an algorithm can recover the label-generation threshold, not an independent measure of near-duplicate detection quality. The point is visible in Table 9, where the threshold-only Connectivity algorithm achieves AUC 0.77, tied with Correlation at 0.77 and only 0.06 below ParHAC-0.01 at 0.83. The Section 1 claim that ParHAC is the best algorithm on the fourth task is therefore not established as evidence of general clustering quality. Please re-generate the labels from an independent signal (e.g., human annotations, lexical overlap, or a different embedding model), or explicitly re-frame this task as a threshold-recovery sanity check and adjust the summary accordingly.","section":"Section 3.5 / Appendix C.1"},{"comment":"Label Propagation and SLPA are nondeterministic; Section 3.1 states that \"the resulting clusterings can be different because of non-determinism in thread scheduling and randomization,\" yet all reported AUC and Pareto-frontier values are single-run measurements without multiple seeds or variance information. This is especially relevant in Table 5, where LP and SLPA receive AUC 0.00 on YouTube, Orkut, and Friendster; a few unlucky runs could materially change these table entries. Please report results averaged over multiple seeds with error bars or a sensitivity analysis for all nondeterministic algorithms, or clearly justify the single-run methodology.","section":"Section 3.1 and Tables 5-7"},{"comment":"The Key Results claim that \"correlation clustering obtains the highest quality on three out of four tasks\" is not supported for the dense subgraph partitioning task. Section 3.4 states that modularity clustering produces denser clusters when the number of clusters is small and that correlation clustering only produces denser clusters when the number of clusters is very large. This is a task-dependent tradeoff, not a clear win for correlation clustering. Please revise the summary and Section 3.4 to reflect this mixed result, and provide per-task summary tables that make the basis of any \"best algorithm\" claim explicit.","section":"Section 3.4 vs. Section 1 Key Results"}],"minor_comments":[{"comment":"The NGrams AUC data appears in both Table 7 and Table 9 with identical content; one of these tables should be removed or renumbered.","section":"Tables 7 and 9"},{"comment":"In the label-generation description, \"among all embeddings whose similarity to x belongs to [s, s+1)\" should presumably read \"[s, s+0.01)\" to match the bucket definition stated in the preceding bullet; as written, the interval spans 0.24 rather than 0.01.","section":"Appendix C.1"},{"comment":"The abstract contains a grammatical error: \"algorithms that not included in many popular graph clustering toolkits\" should be \"algorithms that are not included in many popular graph clustering toolkits.\"","section":"Abstract"},{"comment":"The SCAN structural similarity formula would benefit from an extra pair of parentheses or a displayed equation; the current inline rendering of the square-root denominator is easy to misread.","section":"Section 2.3.2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript fits the PVLDB experimental/benchmark track and is likely to be a useful contribution once the NGrams label circularity and the overstatement in the summary are addressed. The authors' own prior implementations are used for several top-performing algorithms, but the paper does compare against independent baselines and releases code; the main risk is not conflict of interest but the strength of the claims drawn from the current experiments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis is a genuine contribution. It is the first systematic comparison of parallel graph clustering algorithms on both quality and running time, it ships an eleven-algorithm unified library (PCBS), and it adds a new large ground-truth dataset (1.27M short texts, 96k labeled pairs) that the community can reuse. Code and data are public, the experimental setup is described in detail, and the comparisons against NetworKit, Neo4j, TigerGraph, and SNAP are extensive. The headline findings — correlation clustering and ParHAC often beat modularity and the simpler methods, and PCBS is substantially faster than the database baselines — are supported by the tables and Pareto frontiers. Credit where earned: the authors implement several algorithms that are not in other toolkits and compare them fairly across a wide parameter sweep.\n\nThe soft spots are real but localized. The NGrams labels are generated by thresholding the same embedding dot products used as edge weights (Appendix C.1), so the \"high-resolution\" task is partly defined by the very signal the weighted algorithms consume. The stress-test note is right: Connectivity, which is just thresholding, gets AUC 0.77, nearly tied with Correlation and only 0.06 behind ParHAC-0.01's 0.83. That does not invalidate the other three tasks — community detection, embedding clustering on kNN graphs with class labels, and density-based partitioning are independent of the label construction — but it does mean the claim that ParHAC is best on the fourth task is weaker than the abstract suggests. The authors should either add an independent evaluation for the near-duplicate task or prominently caveat the label construction.\n\nA second, minor issue: LP and SLPA are nondeterministic and the paper reports single runs with no variance. Some quality differences on the smaller datasets are likely within run-to-run noise. This is less concerning because the main ranking is driven by large gaps on large graphs.\n\nOverall the central empirical argument holds up. The benchmark suite and dataset are reproducible, the comparisons are honest, and the conclusion that correlation clustering deserves a place in standard toolkits is worth taking seriously. This paper deserves serious peer review. I would send it to referees with a request to have the authors address the NGrams labeling circularity and add variance information for stochastic algorithms.\n\nRecommendation: engage with this work; cite it if you do systems or graph clustering benchmarking.","headline":"A genuinely useful benchmark suite and dataset, with one real methodological soft spot in the NGrams task that should be fixed or heavily caveated before publication.","tokens_in":32161,"tokens_out":1977,"would_cite":true,"duration_ms":19067,"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":"A benchmark of eleven parallel graph clustering algorithms finds correlation clustering leading on three of four tasks and a hierarchical method leading on the fourth—both types of method absent from many popular toolkits.","keywords":["graph clustering","parallel algorithms","benchmark suite","correlation clustering","hierarchical agglomerative clustering","community detection","vector embeddings","near-duplicate detection"],"falsifier":"Re-label the NGrams pairs using an independent source of near-duplicate truth—for example, labels from a different embedding model or human judgments—and rerun the benchmark on the same 50-nearest-neighbor graph; if ParHAC and affinity clustering no longer top the precision-recall AUC table, the high-resolution result is an artifact of label construction. A second check is to run label propagation and SLPA with many random seeds and compare their quality spread with the observed differences between algorithms.","tokens_in":31124,"feed_emoji":"📊","tokens_out":11526,"duration_ms":96221,"temperature":0.7,"pith_summary":"The paper introduces the ParClusterers Benchmark Suite (PCBS), a benchmark suite that bundles eleven parallel graph clustering algorithms with quality metrics and configuration tools, and runs them on unweighted real-world graphs, weighted k-nearest-neighbor graphs built from vector embeddings, synthetic graphs, and a new 1.27-million-vertex text-similarity graph. Its central claim is that correlation clustering delivers the best quality on three of the four tasks—community detection, vector-embedding clustering, and dense subgraph partitioning—while ParHAC, a hierarchical agglomerative method, delivers the best quality on the fourth, high-resolution near-duplicate clustering. It also claims the PCBS implementations are much faster than the clustering functions of widely used graph libraries and databases, for example 32.5x faster than a popular graph database and 4.54x faster than a leading graph library on a 4.8-million-vertex social graph. The suite's purpose is to make such quality-versus-runtime comparisons standardized and reusable, so that practitioners can choose an algorithm for a task rather than for a toolkit.","feed_headline":"Correlation clustering tops 3 of 4 tasks in new benchmark","feed_subtitle":"An 11-algorithm suite finds the best methods are missing from most popular graph toolkits.","key_machinery":"The load-bearing machinery is the LambdaCC objective, a single parameterized objective that interpolates between modularity and correlation clustering through vertex weights and a resolution parameter; the paper's parallel Louvain-style local-search-and-contraction optimizer maximizes it, so one implementation covers both algorithm families. Around this sit the other central mechanisms: ParHAC's approximate agglomerative clustering, whose dendrogram can be cut at any resolution to give clusterings at many granularities, and the benchmark methodology itself, which sweeps a Cartesian product of parameter settings and reports Pareto frontiers of precision versus recall and of F0.5 score versus runtime. The Pareto frontiers are what let the paper rank algorithms across tasks rather than at a single default parameter.","core_discovery":"The paper's core discovery is that the best-quality algorithms are not the ones most toolkits ship. Correlation clustering, implemented through the LambdaCC objective with a parallel Louvain-style optimizer, achieves the highest precision-recall area under the curve on community detection, vector-embedding clustering, and dense subgraph partitioning, while ParHAC, an approximate parallel hierarchical agglomerative clustering algorithm, achieves the highest AUC on the high-resolution task of finding near-duplicate short texts. Modularity clustering, the best commonly available method in existing toolkits, is rarely better. The same experiments show the PCBS implementations are consistently faster than corresponding implementations in other libraries and databases, which the paper attributes to theoretically efficient algorithms, careful engineering, and an efficient parallel graph framework.","pith_inferences":["Editorial inference: The NGrams ground truth is generated by thresholding the same embedding dot-product similarities that define the graph's edge weights, so the high-resolution ranking may partly reflect the label construction; re-running with independently derived labels would test that.","Editorial inference: The paper reports single runs for the nondeterministic label propagation and SLPA algorithms, so their close rankings may change under run-to-run variance; multi-seed reporting would quantify that.","Editorial inference: Because the benchmark separates quality and runtime, it suggests the notion of the 'best' algorithm is task-dependent, and the same suite could be extended to domain-specific metrics such as cluster diameter or triangle density for dense-subgraph applications."],"forward_implications":["If correlation clustering truly leads on three tasks, toolkit maintainers now have a concrete reason to ship a scalable correlation clustering implementation.","If ParHAC's advantage on high-resolution clustering holds, near-duplicate detection on large text corpora can be produced from a single dendrogram cut instead of many thresholded runs.","The measured speed gaps imply that quality-oriented clustering at billion-edge scale is practical on one multicore machine rather than requiring a graph database.","The Pareto-frontier methodology implies that future algorithm evaluations should report quality across a range of resolutions, since single-parameter comparisons can miss which method wins each operating point."],"supporting_citations":[{"why":"Supplies the parallel correlation clustering implementation that PCBS benchmarks and that wins three tasks.","marker":"[64]"},{"why":"Supplies the approximate parallel hierarchical agglomerative clustering (ParHAC) that wins the high-resolution task.","marker":"[29]"},{"why":"Defines the LambdaCC objective that unifies modularity and correlation clustering in one framework.","marker":"[74]"},{"why":"Supplies the parallel affinity clustering implementation used in the embedding and high-resolution tasks.","marker":"[28]"},{"why":"Supplies the geometrically decaying threshold schedule used to improve affinity clustering quality.","marker":"[53]"},{"why":"Supplies the parallel graph processing framework and primitives that underpin the PCBS implementations.","marker":"[27]"},{"why":"Supplies the parallel graph library whose clustering implementations are the main speed baseline.","marker":"[68]"},{"why":"Supplies the graph database whose clustering runtimes are compared and found much slower.","marker":"[5]"},{"why":"Supplies the unweighted real-world graphs and ground-truth communities used in the community detection task.","marker":"[44]"}],"fun_headline_variants":["Benchmark: Best graph clustering algorithms missing from top toolkits","Correlation clustering wins in new parallel benchmark","ParClusterers benchmark shows toolkit gap: best methods absent","Top graph clustering methods not in popular toolkits, new suite finds","New benchmark: correlation clustering beats common toolkit options"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The high-resolution task's ground-truth labels come from thresholding the same embedding similarities that define the graph's edge weights, so the ranking on that task assumes those similarities are the right notion of truth rather than a construction artifact.","fun_headline_variants_meta":{"raw":{"variants":["Benchmark: Best graph clustering algorithms missing from top toolkits","Correlation clustering wins in new parallel benchmark","ParClusterers benchmark shows toolkit gap: best methods absent","Top graph clustering methods not in popular toolkits, new suite finds","New benchmark: correlation clustering beats common toolkit options"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000199,"raw_usage":{"total_tokens":1340,"prompt_tokens":883,"completion_tokens":457,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":499,"completion_tokens_details":{"reasoning_tokens":376}},"tokens_in":499,"tokens_out":457,"duration_ms":4430,"temperature":1.0,"reasoning_tokens":376,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T19:45:56.090260+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-label the NGrams pairs using an independent source of near-duplicate truth—for example, labels from a different embedding model or human judgments—and rerun the benchmark on the same 50-nearest-neighbor graph; if ParHAC and affinity clustering no longer top the precision-recall AUC table, the high-resolution result is an artifact of label construction. A second check is to run label propagation and SLPA with many random seeds and compare their quality spread with the observed differences between algorithms.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the graph database whose clustering runtimes are compared and found much slower."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the unweighted real-world graphs and ground-truth communities used in the community detection task."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the parallel correlation clustering implementation that PCBS benchmarks and that wins three tasks."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the approximate parallel hierarchical agglomerative clustering (ParHAC) that wins the high-resolution task."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the LambdaCC objective that unifies modularity and correlation clustering in one framework."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the parallel affinity clustering implementation used in the embedding and high-resolution tasks."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the geometrically decaying threshold schedule used to improve affinity clustering quality."},{"cited_title":"Blelloch, and Julian Shun","cited_arxiv_id":null,"evidence_quote":"Supplies the parallel graph processing framework and primitives that underpin the PCBS implementations."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the parallel graph library whose clustering implementations are the main speed baseline."}],"review_version":1}