# Towards Robust and Scalable Density-based Clustering via Graph Propagation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 48 references that are in the map.
- First posted on arXiv 1 May 2026.

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

- [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)
- [Ultra-Scalable Spectral Clustering and Ensemble Clustering](https://mlsanity.com/paper/1903.01057/) (2019)
- [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)
- [Automatic topography of high-dimensional data sets by non-parametric Density Peak clustering](https://mlsanity.com/paper/1802.10549/) (2018)
- [Consistent procedures for cluster tree estimation and pruning](https://mlsanity.com/paper/1406.1546/) (2014)
- [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)

## Abstract (arXiv)

We present textitCluProp, a novel framework that reimagines varied-density clustering in high-dimensional spaces as a label propagation process over neighborhood graphs. Our approach formally bridges the gap between density-based clustering and graph connectivity, leveraging efficient propagation mechanisms from network science to mitigate the parameter sensitivity inherent in traditional density-based methods. Specifically, we introduce a deterministic density-based propagation strategy to ensure scalable neighborhood identification. The framework is agnostic to the choice of distance metric and exhibits superior performance on large-scale data, processing millions of points in minutes while consistently outperforming existing baselines in accuracy.