A Tighter Analysis of Spectral Clustering, and Beyond

Peter Macgregor, He Sun
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:14717-14742, 2022.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-macgregor22a, title = {A Tighter Analysis of Spectral Clustering, and Beyond}, author = {Macgregor, Peter and Sun, He}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {14717--14742}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/macgregor22a/macgregor22a.pdf}, url = {https://proceedings.mlr.press/v162/macgregor22a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T A Tighter Analysis of Spectral Clustering, and Beyond %A Peter Macgregor %A He Sun %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-macgregor22a %I PMLR %P 14717--14742 %U https://proceedings.mlr.press/v162/macgregor22a.html %V 162 %X 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.
APA
Macgregor, P. & Sun, H.. (2022). A Tighter Analysis of Spectral Clustering, and Beyond. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:14717-14742 Available from https://proceedings.mlr.press/v162/macgregor22a.html.

Related Material