# Scalable Varied-Density Clustering via Graph Propagation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 46 references that are in the map.
- First posted on arXiv 5 Aug 2025.

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

- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Towards K-means-friendly Spaces: Simultaneous Deep Learning and Clustering](https://mlsanity.com/paper/1610.04794/) (2016)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [DBSCAN++: Towards fast and scalable density clustering](https://mlsanity.com/paper/1810.13105/) (2018)
- [Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds](https://mlsanity.com/paper/1706.02803/) (2017)
- [Density Level Set Estimation on Manifolds with DBSCAN](https://mlsanity.com/paper/1703.03503/) (2017)
- [Faster DBSCAN via subsampled similarity queries](https://mlsanity.com/paper/2006.06743/) (2020)
- [Fast Density-Peaks Clustering: Multicore-based Parallelization Approach](https://mlsanity.com/paper/2207.04649/) (2022)
- [The SpectACl of Nonconvex Clustering: A Spectral Approach to Density-Based Clustering](https://mlsanity.com/paper/1907.00680/) (2019)
- [Faster DB-scan and HDB-scan in Low-Dimensional Euclidean Spaces](https://mlsanity.com/paper/1702.08607/) (2017)

## Abstract (arXiv)

We propose a novel perspective on varied-density clustering for high-dimensional data by framing it as a label propagation process in neighborhood graphs that adapt to local density variations. Our method formally connects density-based clustering with graph connectivity, enabling the use of efficient graph propagation techniques developed in network science. To ensure scalability, we introduce a density-aware neighborhood propagation algorithm and leverage advanced random projection methods to construct approximate neighborhood graphs. Our approach significantly reduces computational cost while preserving clustering quality. Empirically, it scales to datasets with millions of points in minutes and achieves competitive accuracy compared to existing baselines.