# Coreset Spectral Clustering

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

## Key facts

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

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

- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds](https://mlsanity.com/paper/1706.02803/) (2017)
- [Coresets for Clustering in Excluded-minor Graphs and Beyond](https://mlsanity.com/paper/2004.07718/) (2020)
- [Fast and Accurate k-means++ via Rejection Sampling](https://mlsanity.com/paper/2012.11891/) (2020)
- [Distributed Graph Clustering and Sparsification](https://mlsanity.com/paper/1711.01262/) (2017)
- [Refining a k-nearest neighbor graph for a computationally efficient spectral clustering](https://mlsanity.com/paper/2302.11296/) (2023)
- [Fast and Simple Spectral Clustering in Theory and Practice](https://mlsanity.com/paper/2310.10939/) (2023)
- [Coresets for Kernel Clustering](https://mlsanity.com/paper/2110.02898/) (2021)
- [Fast Approximation of Similarity Graphs with Kernel Density Estimation](https://mlsanity.com/paper/2310.13870/) (2023)
- [Mini-Batch Kernel k-means](https://mlsanity.com/paper/2410.05902/) (2024)

## Abstract (arXiv)

Coresets have become an invaluable tool for solving k-means and kernel k-means clustering problems on large datasets with small numbers of clusters. On the other hand, spectral clustering works well on sparse graphs and has recently been extended to scale efficiently to large numbers of clusters. We exploit the connection between kernel k-means and the normalised cut problem to combine the benefits of both. Our main result is a coreset spectral clustering algorithm for graphs that clusters a coreset graph to infer a good labelling of the original graph. We prove that an α-approximation for the normalised cut problem on the coreset graph is an O(α)-approximation on the original. We also improve the running time of the state-of-the-art coreset algorithm for kernel k-means on sparse kernels, from tildeO(nk) to tildeO(n· min k, davg), where davg is the average number of non-zero entries in each row of the n× n kernel matrix. Our experiments confirm our coreset algorithm is asymptotically faster on large real-world graphs with many clusters, and show that our clustering algorithm overcomes the main challenge faced by coreset kernel k-means on sparse kernels which is getting stuck in local optima.