# PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 48 references that are in the map.
- First posted on arXiv 18 Dec 2024.

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

- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [Spectrally approximating large graphs with smaller graphs](https://mlsanity.com/paper/1802.07510/) (2018)
- [Graph Coarsening with Preserved Spectral Properties](https://mlsanity.com/paper/1802.04447/) (2018)
- [Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models](https://mlsanity.com/paper/1310.4378/) (2013)
- [Graph coarsening: From scientific computing to machine learning](https://mlsanity.com/paper/2106.11863/) (2021)
- [Compressive Spectral Clustering](https://mlsanity.com/paper/1602.02018/) (2016)
- [Spectral Clustering via the Power Method -- Provably](https://mlsanity.com/paper/1311.2854/) (2013)
- [A smart local moving algorithm for large-scale modularity-based community detection](https://mlsanity.com/paper/1308.6604/) (2013)
- [Approximating Spectral Clustering via Sampling: a Review](https://mlsanity.com/paper/1901.10204/) (2019)
- [Scalable Spectral Clustering with Nystrom Approximation: Practical and Theoretical Aspects](https://mlsanity.com/paper/2006.14470/) (2020)
- [Deep Multilevel Graph Partitioning](https://mlsanity.com/paper/2105.02022/) (2021)

## Abstract (arXiv)

Clustering the nodes of a graph is a cornerstone of graph analysis and has been extensively studied. However, some popular methods are not suitable for very large graphs: e.g., spectral clustering requires the computation of the spectral decomposition of the Laplacian matrix, which is not applicable for large graphs with a large number of communities. This work introduces PASCO, an overlay that accelerates clustering algorithms. Our method consists of three steps: 1-We compute several independent small graphs representing the input graph by applying an efficient and structure-preserving coarsening algorithm. 2-A clustering algorithm is run in parallel onto each small graph and provides several partitions of the initial graph. 3-These partitions are aligned and combined with an optimal transport method to output the final partition. The PASCO framework is based on two key contributions: a novel global algorithm structure designed to enable parallelization and a fast, empirically validated graph coarsening algorithm that preserves structural properties. We demonstrate the strong performance of 1 PASCO in terms of computational efficiency, structural preservation, and output partition quality, evaluated on both synthetic and real-world graph datasets.