# A Simple Approach to Automated Spectral Clustering

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 75 references that are in the map.
- First posted on arXiv 23 Jul 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Fast Bayesian Optimization of Machine Learning Hyperparameters on Large Datasets](https://mlsanity.com/paper/1605.07079/) (2016)
- [Deep Subspace Clustering Networks](https://mlsanity.com/paper/1709.02508/) (2017)
- [Large-scale Multi-view Subspace Clustering in Linear Time](https://mlsanity.com/paper/1911.09290/) (2019)
- [Neural Network with Unbounded Activation Functions is Universal Approximator](https://mlsanity.com/paper/1505.03654/) (2015)
- [Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit](https://mlsanity.com/paper/1507.01238/) (2015)
- [Robust and Efficient Subspace Segmentation via Least Squares Regression](https://mlsanity.com/paper/1404.6736/) (2014)
- [Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering](https://mlsanity.com/paper/1605.02633/) (2016)
- [Subspace Clustering by Block Diagonal Representation](https://mlsanity.com/paper/1805.09243/) (2018)
- [Self-Supervised Convolutional Subspace Clustering Network](https://mlsanity.com/paper/1905.00149/) (2019)
- [Structured Graph Learning for Scalable Subspace Clustering: From Single-view to Multi-view](https://mlsanity.com/paper/2102.07943/) (2021)
- [Pseudo-supervised Deep Subspace Clustering](https://mlsanity.com/paper/2104.03531/) (2021)
- [Robust subspace clustering](https://mlsanity.com/paper/1301.2603/) (2013)
- [Neural Collaborative Subspace Clustering](https://mlsanity.com/paper/1904.10596/) (2019)
- [Noisy Sparse Subspace Clustering](https://mlsanity.com/paper/1309.1233/) (2013)
- [Stochastic Sparse Subspace Clustering](https://mlsanity.com/paper/2005.01449/) (2020)
- [Polynomial Matrix Completion for Missing Data Imputation and Transductive Learning](https://mlsanity.com/paper/1912.06989/) (2019)
- [Large-Scale Subspace Clustering via k-Factorization](https://mlsanity.com/paper/2012.04345/) (2020)
- [Shape Interaction Matrix Revisited and Robustified: Efficient Subspace Clustering with Corrupted and Incomplete Data](https://mlsanity.com/paper/1509.02649/) (2015)
- [Selective Pseudo-label Clustering](https://mlsanity.com/paper/2107.10692/) (2021)
- [A Unified Framework for Representation-based Subspace Clustering of Out-of-sample and Large-scale Data](https://mlsanity.com/paper/1309.6487/) (2013)
- [Learnable Subspace Clustering](https://mlsanity.com/paper/2004.04520/) (2020)

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

- [DiffCut: Catalyzing Zero-Shot Semantic Segmentation with Diffusion Features and Recursive Normalized Cut](https://mlsanity.com/paper/2406.02842/) (2024)
- [Riemannian Optimization on Relaxed Indicator Matrix Manifold](https://mlsanity.com/paper/2503.20505/) (2025)
- [Laplacian-based Cluster-Contractive t-SNE for High Dimensional Data Visualization](https://mlsanity.com/paper/2207.12214/) (2022)
- [Deep Graph-Level Clustering Using Pseudo-Label-Guided Mutual Information Maximization Network](https://mlsanity.com/paper/2302.02369/) (2023)
- [Neural Normalized Cut: A Differential and Generalizable Approach for Spectral Clustering](https://mlsanity.com/paper/2503.09260/) (2025)
- [Spectral Clustering for Discrete Distributions](https://mlsanity.com/paper/2401.13913/) (2024)
- [CLUBench: A Clustering Benchmark](https://mlsanity.com/paper/2605.29933/) (2026)
- [SPARK: Stochastic Propagation via Affinity-guided Random walK for training-free unsupervised segmentation](https://mlsanity.com/paper/2602.00516/) (2026)
- [GRACE: LLM-Grounded Semantic Metric Spaces for Scalable Mixed-Data Clustering](https://mlsanity.com/paper/2608.07881/) (2026)
- [Automatic depth-based local center clustering via β-integrated local depth and adaptive grouping](https://mlsanity.com/paper/2609.26748/) (2026)

## Abstract (arXiv)

The performance of spectral clustering heavily relies on the quality of affinity matrix. A variety of affinity-matrix-construction (AMC) methods have been proposed but they have hyperparameters to determine beforehand, which requires strong experience and leads to difficulty in real applications, especially when the inter-cluster similarity is high and/or the dataset is large. In addition, we often need to choose different AMC methods for different datasets, which still depends on experience. To solve these two challenging problems, in this paper, we present a simple yet effective method for automated spectral clustering. First, we propose to find the most reliable affinity matrix via grid search or Bayesian optimization among a set of candidates given by different AMC methods with different hyperparameters, where the reliability is quantified by the textitrelative-eigen-gap of graph Laplacian introduced in this paper. Second, we propose a fast and accurate AMC method based on least squares representation and thresholding and prove its effectiveness theoretically. Finally, we provide a large-scale extension for the automated spectral clustering method, of which the time complexity is linear with the number of data points. Extensive experiments of natural image clustering show that our method is more versatile, accurate, and efficient than baseline methods.