# The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering

arXiv: https://arxiv.org/abs/2411.10290 · HTML: https://mlsanity.com/paper/2411.10290/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 68 references that are in the map.
- First posted on arXiv 15 Nov 2024.

## Builds on (most cited first, 20 of 20)

- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [A Comparative Analysis of Community Detection Algorithms on Artificial Networks](https://mlsanity.com/paper/1608.00763/) (2016)
- [Demystifying Graph Databases: Analysis and Taxonomy of Data Organization, System Designs, and Graph Queries](https://mlsanity.com/paper/1910.09017/) (2019)
- [Scalable motif-aware graph clustering](https://mlsanity.com/paper/1606.06235/) (2016)
- [Minimum adjusted Rand index for two clusterings of a given size](https://mlsanity.com/paper/2002.03677/) (2020)
- [Scalable Hierarchical Agglomerative Clustering](https://mlsanity.com/paper/2010.11821/) (2020)
- [Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering](https://mlsanity.com/paper/1712.05825/) (2017)
- [GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra](https://mlsanity.com/paper/2103.03653/) (2021)
- [Scalable Community Detection via Parallel Correlation Clustering](https://mlsanity.com/paper/2108.01731/) (2021)
- [Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time](https://mlsanity.com/paper/2106.05610/) (2021)
- [Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable](https://mlsanity.com/paper/1805.05208/) (2018)
- [Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth](https://mlsanity.com/paper/2206.11654/) (2022)
- [TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs](https://mlsanity.com/paper/2308.03578/) (2023)
- [Engineering Parallel Algorithms for Community Detection in Massive Networks](https://mlsanity.com/paper/1304.4453/) (2013)
- [Parallel Index-Based Structural Graph Clustering and Its Approximation](https://mlsanity.com/paper/2012.11188/) (2020)
- [ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms](https://mlsanity.com/paper/2008.03909/) (2020)
- [Parallel Graph Decompositions Using Random Shifts](https://mlsanity.com/paper/1307.3692/) (2013)
- [Comparison and Benchmark of Graph Clustering Algorithms](https://mlsanity.com/paper/2005.04806/) (2020)
- [A Randomized Concurrent Algorithm for Disjoint Set Union](https://mlsanity.com/paper/1612.01514/) (2016)

## Abstract (arXiv)

We introduce the ParClusterers Benchmark Suite (PCBS) -- a collection of highly scalable parallel graph clustering algorithms and benchmarking tools that streamline comparing different graph clustering algorithms and implementations. The benchmark includes clustering algorithms that target a wide range of modern clustering use cases, including community detection, classification, and dense subgraph mining. The benchmark toolkit makes it easy to run and evaluate multiple instances of different clustering algorithms, which can be useful for fine-tuning the performance of clustering on a given task, and for comparing different clustering algorithms based on different metrics of interest, including clustering quality and running time. Using PCBS, we evaluate a broad collection of real-world graph clustering datasets. Somewhat surprisingly, we find that the best quality results are obtained by algorithms that not included in many popular graph clustering toolkits. The PCBS provides a standardized way to evaluate and judge the quality-performance tradeoffs of the active research area of scalable graph clustering algorithms. We believe it will help enable fair, accurate, and nuanced evaluation of graph clustering algorithms in the future.