# Approximating Spectral Clustering via Sampling: a Review

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jan 2019.

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

- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Consistency and Diversity induced Human Motion Segmentation](https://mlsanity.com/paper/2202.04861/) (2022)
- [Generalizing Graph Transformers Across Diverse Graphs and Tasks via Pre-training](https://mlsanity.com/paper/2407.03953/) (2024)
- [Graph Federated Learning for CIoT Devices in Smart Home Applications](https://mlsanity.com/paper/2212.14395/) (2022)
- [Understanding the Basis of Graph Convolutional Neural Networks via an Intuitive Matched Filtering Approach](https://mlsanity.com/paper/2108.10751/) (2021)
- [Clustering large 3D volumes: A sampling-based approach](https://mlsanity.com/paper/2303.04188/) (2023)
- [PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms](https://mlsanity.com/paper/2412.13592/) (2024)
- [Deterministic Coreset for Lp Subspace](https://mlsanity.com/paper/2601.00361/) (2026)
- [Clustering as Approximation by Constrained Projectors: Theory and Guarantees](https://mlsanity.com/paper/2608.29102/) (2026)

## Abstract (arXiv)

Spectral clustering refers to a family of unsupervised learning algorithms that compute a spectral embedding of the original data based on the eigenvectors of a similarity graph. This non-linear transformation of the data is both the key of these algorithms' success and their Achilles heel: forming a graph and computing its dominant eigenvectors can indeed be computationally prohibitive when dealing with more that a few tens of thousands of points. In this paper, we review the principal research efforts aiming to reduce this computational cost. We focus on methods that come with a theoretical control on the clustering performance and incorporate some form of sampling in their operation. Such methods abound in the machine learning, numerical linear algebra, and graph signal processing literature and, amongst others, include Nystr"om-approximation, landmarks, coarsening, coresets, and compressive spectral clustering. We present the approximation guarantees available for each and discuss practical merits and limitations. Surprisingly, despite the breadth of the literature explored, we conclude that there is still a gap between theory and practice: the most scalable methods are only intuitively motivated or loosely controlled, whereas those that come with end-to-end guarantees rely on strong assumptions or enable a limited gain of computation time.