# Distributed Graph Clustering and Sparsification

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2017.

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

- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [Hierarchical Clustering: O(1)-Approximation for Well-Clustered Graphs](https://mlsanity.com/paper/2112.09055/) (2021)
- [Fast and Simple Spectral Clustering in Theory and Practice](https://mlsanity.com/paper/2310.10939/) (2023)
- [Fast Approximation of Similarity Graphs with Kernel Density Estimation](https://mlsanity.com/paper/2310.13870/) (2023)
- [On Learning the Structure of Clusters in Graphs](https://mlsanity.com/paper/2212.14345/) (2022)
- [Dynamic Spectral Clustering with Provable Approximation Guarantee](https://mlsanity.com/paper/2406.03152/) (2024)
- [Spectral Toolkit of Algorithms for Graphs: Technical Report (2)](https://mlsanity.com/paper/2407.07096/) (2024)
- [Coreset Spectral Clustering](https://mlsanity.com/paper/2503.07227/) (2025)
- [Online Sparsification of Bipartite-Like Clusters in Graphs](https://mlsanity.com/paper/2508.05437/) (2025)

## Abstract (arXiv)

Graph clustering is a fundamental computational problem with a number of applications in algorithm design, machine learning, data mining, and analysis of social networks. Over the past decades, researchers have proposed a number of algorithmic design methods for graph clustering. Most of these methods, however, are based on complicated spectral techniques or convex optimisation, and cannot be directly applied for clustering many networks that occur in practice, whose information is often collected on different sites. Designing a simple and distributed clustering algorithm is of great interest, and has wide applications for processing big datasets. In this paper we present a simple and distributed algorithm for graph clustering: for a wide class of graphs that are characterised by a strong cluster-structure, our algorithm finishes in a poly-logarithmic number of rounds, and recovers a partition of the graph close to optimal. One of the main components behind our algorithm is a sampling scheme that, given a dense graph as input, produces a sparse subgraph that provably preserves the cluster-structure of the input. Compared with previous sparsification algorithms that require Laplacian solvers or involve combinatorial constructions, this component is easy to implement in a distributed way and runs fast in practice.