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

• URL: http://arxiv.org/abs/2411.10290v1
• Date: Fri, 15 Nov 2024 15:47:32 GMT
• Title: The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering
• Authors: Shangdi Yu, Jessica Shi, Jamison Meindl, David Eisenstat, Xiaoen Ju, Sasan Tavakkol, Laxman Dhulipala, Jakub Łącki, Vahab Mirrokni, Julian Shun,
• Abstract summary: ParClusterers Benchmark Suite (PCBS) is a collection of highly scalable parallel graph clustering algorithms and benchmarking tools. PCBS provides a standardized way to evaluate and judge the quality-performance tradeoffs of the active research area of scalable graph clustering algorithms.
• Score: 15.047567897051376
• License:
• Abstract: 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.

Related papers

• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  We devise an efficient algorithm that recovers clusters using the observed labels. We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• GLCC: A General Framework for Graph-level Clustering [5.069852282550117]
  This paper studies the problem of graph-level clustering, which is a novel yet challenging task. We propose a general graph-level clustering framework named Graph-Level Contrastive Clustering (GLCC) Experiments on a range of well-known datasets demonstrate the superiority of our proposed GLCC over competitive baselines.
  arXiv  Detail & Related papers  (2022-10-21T11:08:10Z)
• A framework for benchmarking clustering algorithms [2.900810893770134]
  Clustering algorithms can be tested on a variety of benchmark problems. Many research papers and graduate theses consider only a small number of datasets. We have developed a framework whose aim is to introduce a consistent methodology for testing clustering algorithms.
  arXiv  Detail & Related papers  (2022-09-20T06:10:41Z)
• Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
  We propose a novel attributed graph clustering network, namely Self-supervised Contrastive Attributed Graph Clustering (SCAGC) In SCAGC, by leveraging inaccurate clustering labels, a self-supervised contrastive loss, are designed for node representation learning. For the OOS nodes, SCAGC can directly calculate their clustering labels.
  arXiv  Detail & Related papers  (2021-10-15T03:25:28Z)
• Graph Contrastive Clustering [131.67881457114316]
  We propose a novel graph contrastive learning framework, which is then applied to the clustering task and we come up with the Graph Constrastive Clustering(GCC) method. Specifically, on the one hand, the graph Laplacian based contrastive loss is proposed to learn more discriminative and clustering-friendly features. On the other hand, a novel graph-based contrastive learning strategy is proposed to learn more compact clustering assignments.
  arXiv  Detail & Related papers  (2021-04-03T15:32:49Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)
• Comparison and Benchmark of Graph Clustering Algorithms [6.106697372971535]
  We benchmarked more than 70 graph clustering programs to evaluate their runtime and quality performance. Our work is capable to not only supply a start point for engineers to select clustering algorithms but also could provide a viewpoint for researchers to design new algorithms.
  arXiv  Detail & Related papers  (2020-05-10T22:54:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.