# Understanding the Generalization Performance of Spectral Clustering Algorithms

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 52 references that are in the map.
- First posted on arXiv 30 Apr 2022.

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

- [SpectralNet: Spectral Clustering using Deep Neural Networks](https://mlsanity.com/paper/1801.01587/) (2018)
- [A variational approach to the consistency of spectral clustering](https://mlsanity.com/paper/1508.01928/) (2015)
- [Spectral Convergence of the connection Laplacian from random samples](https://mlsanity.com/paper/1306.1587/) (2013)
- [The geometry of kernelized spectral clustering](https://mlsanity.com/paper/1404.7552/) (2014)
- [Consistency of Cheeger and Ratio Graph Cuts](https://mlsanity.com/paper/1411.6590/) (2014)

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

- [Generalization Performance of Ensemble Clustering: From Theory to Algorithm](https://mlsanity.com/paper/2506.02053/) (2025)
- [Eigenvalue-based Incremental Spectral Clustering](https://mlsanity.com/paper/2308.10999/) (2023)
- [Enhancing VICReg: Random-Walk Pairing for Improved Generalization and Better Global Semantics Capturing](https://mlsanity.com/paper/2506.18104/) (2025)
- [Feature Incremental Clustering with Generalization Bounds](https://mlsanity.com/paper/2603.21590/) (2026)

## Abstract (arXiv)

The theoretical analysis of spectral clustering mainly focuses on consistency, while there is relatively little research on its generalization performance. In this paper, we study the excess risk bounds of the popular spectral clustering algorithms: relaxed RatioCut and relaxed NCut. Firstly, we show that their excess risk bounds between the empirical continuous optimal solution and the population-level continuous optimal solution have a O(1/√n) convergence rate, where n is the sample size. Secondly, we show the fundamental quantity in influencing the excess risk between the empirical discrete optimal solution and the population-level discrete optimal solution. At the empirical level, algorithms can be designed to reduce this quantity. Based on our theoretical analysis, we propose two novel algorithms that can not only penalize this quantity, but also cluster the out-of-sample data without re-eigendecomposition on the overall sample. Experiments verify the effectiveness of the proposed algorithms.