Abstract
We revisit the theoretical performances of Spectral Clustering, a classical algorithm for graph partitioning that relies on the eigenvectors of a matrix representation of the graph. Informally, we show that Spectral Clustering works well as long as the smallest eigenvalues appear in groups well separated from the rest of the matrix representation's spectrum. This arises, for example, whenever there exists a hierarchy of clusters at different scales, a regime not captured by previous analyses. Our results are very general and can be applied beyond the traditional graph Laplacian. In particular, we study Hermitian representations of digraphs and show Spectral Clustering can recover partitions where edges between clusters are oriented mostly in the same direction. This has applications in, for example, the analysis of trophic levels in ecological networks. We demonstrate that our results accurately predict the performances of Spectral Clustering on synthetic and real-world data sets.
| Original language | English |
|---|---|
| Title of host publication | Learning on Graphs Conference 2025 |
| Number of pages | 24 |
| DOIs | |
| Publication status | E-pub ahead of print - 28 Nov 2025 |
| Event | The Fourth Learning on Graphs Conference - https://logconference.org/, Phoenix, USA United States Duration: 10 Dec 2025 → … |
Conference
| Conference | The Fourth Learning on Graphs Conference |
|---|---|
| Country/Territory | USA United States |
| City | Phoenix |
| Period | 10/12/25 → … |
Keywords
- spectral clustering
- graph clustering
Fingerprint
Dive into the research topics of 'An Improved and Generalised Analysis of Spectral Clustering'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS