A Tighter Analysis of Spectral Clustering, and Beyond

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This work studies the classical spectral clustering algorithm which embeds the vertices of some graph G=(V_G, E_G) into R^k using k eigenvectors of some matrix of G, and applies k-means to partition V_G into k clusters. Our first result is a tighter analysis on the performance of spectral clustering, and explains why it works under some much weaker condition than the ones studied in the literature. For the second result, we show that, by applying fewer than k eigenvectors to construct the embedding, spectral clustering is able to produce better output for many practical instances; this result is the first of its kind in spectral clustering. Besides its conceptual and theoretical significance, the practical impact of our work is demonstrated by the empirical analysis on both synthetic and real-world data sets, in which spectral clustering produces comparable or better results with fewer than k eigenvectors.
Original languageEnglish
Title of host publicationProceedings of the 39th International Conference on Machine Learning
EditorsKamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, Sivan Sabato
Number of pages26
Publication statusPublished - 23 Jul 2022
EventThe 39th International Conference on Machine Learning, 2022 - Baltimore, United States
Duration: 17 Jul 202223 Jul 2022
Conference number: 39

Publication series

NameProceedings of Machine Learning Research
ISSN (Electronic)2640-3498


ConferenceThe 39th International Conference on Machine Learning, 2022
Abbreviated titleICML 2022
Country/TerritoryUnited States
Internet address


Dive into the research topics of 'A Tighter Analysis of Spectral Clustering, and Beyond'. Together they form a unique fingerprint.

Cite this