# Compressive Spectral Clustering

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2016.

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

- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions](https://mlsanity.com/paper/2105.03714/) (2021)
- [Feature Affinity Assisted Knowledge Distillation and Quantization of Deep Neural Networks on Label-Free Data](https://mlsanity.com/paper/2302.10899/) (2023)
- [A Primer on Temporal Graph Learning](https://mlsanity.com/paper/2401.03988/) (2024)
- [Learning Optimal Graph Filters for Clustering of Attributed Graphs](https://mlsanity.com/paper/2211.04634/) (2022)
- [Spectral Clustering via Orthogonalization-Free Methods](https://mlsanity.com/paper/2305.10356/) (2023)
- [Free Lunch for Efficient Textual Commonsense Integration in Language Models](https://mlsanity.com/paper/2305.15516/) (2023)
- [On consistency of constrained spectral clustering under representation-aware stochastic block model](https://mlsanity.com/paper/2203.02005/) (2022)
- [Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering](https://mlsanity.com/paper/2207.14589/) (2022)
- [PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms](https://mlsanity.com/paper/2412.13592/) (2024)
- [Quantitative Error Feedback for Quantization Noise Reduction of Filtering over Graphs](https://mlsanity.com/paper/2506.01404/) (2025)
- [Random Wavelet Features for Graph Kernel Machines](https://mlsanity.com/paper/2602.15711/) (2026)

## Abstract (arXiv)

Spectral clustering has become a popular technique due to its high performance in many contexts. It comprises three main steps: create a similarity graph between N objects to cluster, compute the first k eigenvectors of its Laplacian matrix to define a feature vector for each object, and run k-means on these features to separate objects into k classes. Each of these three steps becomes computationally intensive for large N and/or k. We propose to speed up the last two steps based on recent results in the emerging field of graph signal processing: graph filtering of random signals, and random sampling of bandlimited graph signals. We prove that our method, with a gain in computation time that can reach several orders of magnitude, is in fact an approximation of spectral clustering, for which we are able to control the error. We test the performance of our method on artificial and real-world network data.