# Fast and Simple Spectral Clustering in Theory and Practice

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 35 references that are in the map.
- First posted on arXiv 17 Oct 2023.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [The Impact of Random Models on Clustering Similarity](https://mlsanity.com/paper/1701.06508/) (2017)
- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [Spectral Clustering via the Power Method -- Provably](https://mlsanity.com/paper/1311.2854/) (2013)
- [Distributed Graph Clustering and Sparsification](https://mlsanity.com/paper/1711.01262/) (2017)
- [Improved Analysis of Spectral Algorithm for Clustering](https://mlsanity.com/paper/1912.02997/) (2019)
- [Spectral Toolkit of Algorithms for Graphs: Technical Report (1)](https://mlsanity.com/paper/2304.03170/) (2023)

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

- [Riemannian Optimization on Relaxed Indicator Matrix Manifold](https://mlsanity.com/paper/2503.20505/) (2025)
- [Clustering by Mining Density Distributions and Splitting Manifold Structure](https://mlsanity.com/paper/2408.10493/) (2024)
- [TANGO: Clustering with Typicality-Aware Nonlocal Mode-Seeking and Graph-Cut Optimization](https://mlsanity.com/paper/2408.10084/) (2024)
- [State Space Models for Extractive Summarization in Low Resource Scenarios](https://mlsanity.com/paper/2501.14673/) (2025)
- [Coreset Spectral Clustering](https://mlsanity.com/paper/2503.07227/) (2025)

## Abstract (arXiv)

Spectral clustering is a popular and effective algorithm designed to find k clusters in a graph G. In the classical spectral clustering algorithm, the vertices of G are embedded into ℝk using k eigenvectors of the graph Laplacian matrix. However, computing this embedding is computationally expensive and dominates the running time of the algorithm. In this paper, we present a simple spectral clustering algorithm based on a vertex embedding with O(log(k)) vectors computed by the power method. The vertex embedding is computed in nearly-linear time with respect to the size of the graph, and the algorithm provably recovers the ground truth clusters under natural assumptions on the input graph. We evaluate the new algorithm on several synthetic and real-world datasets, finding that it is significantly faster than alternative clustering algorithms, while producing results with approximately the same clustering accuracy.