# Scalable and Effective Conductance-based Graph Clustering

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 35 references that are in the map.
- First posted on arXiv 22 Nov 2022.

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

- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [p-Norm Flow Diffusion for Local Graph Clustering](https://mlsanity.com/paper/2005.09810/) (2020)
- [Capacity Releasing Diffusion for Speed and Locality](https://mlsanity.com/paper/1706.05826/) (2017)
- [Efficient Estimation of Heat Kernel PageRank for Local Clustering](https://mlsanity.com/paper/1904.02707/) (2019)
- [Flow-Based Algorithms for Local Graph Clustering](https://mlsanity.com/paper/1307.2855/) (2013)
- [A Simple and Strongly-Local Flow-Based Method for Cut Improvement](https://mlsanity.com/paper/1605.08490/) (2016)

## Built on by (most cited first, 2 of 2)

- [PSNE: Efficient Spectral Sparsification Algorithms for Scaling Network Embedding](https://mlsanity.com/paper/2408.02705/) (2024)
- [Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach](https://mlsanity.com/paper/2412.10789/) (2024)

## Abstract (arXiv)

Conductance-based graph clustering has been recognized as a fundamental operator in numerous graph analysis applications. Despite the significant success of conductance-based graph clustering, existing algorithms are either hard to obtain satisfactory clustering qualities, or have high time and space complexity to achieve provable clustering qualities. To overcome these limitations, we devise a powerful textitpeeling-based graph clustering framework textitPCon. We show that many existing solutions can be reduced to our framework. Namely, they first define a score function for each vertex, then iteratively remove the vertex with the smallest score. Finally, they output the result with the smallest conductance during the peeling process. Based on our framework, we propose two novel algorithms textitPConcore and PConde with linear time and space complexity, which can efficiently and effectively identify clusters from massive graphs with more than a few billion edges. Surprisingly, we prove that PConde can identify clusters with near-constant approximation ratio, resulting in an important theoretical improvement over the well-known quadratic Cheeger bound. Empirical results on real-life and synthetic datasets show that our algorithms can achieve 5~42 times speedup with a high clustering accuracy, while using 1.4~7.8 times less memory than the baseline algorithms.