Partitioning Well-Clustered Graphs: Spectral Clustering Works!

Richard Peng, He Sun, Luca Zanetti
Proceedings of The 28th Conference on Learning Theory, PMLR 40:1423-1455, 2015.

Abstract

In this work we study the widely used \emphspectral clustering algorithms, i.e. partition a graph into k clusters via (1) embedding the vertices of a graph into a low-dimensional space using the bottom eigenvectors of the Laplacian matrix, and (2) partitioning embedded points via k-means algorithms. We show that, for a wide class of \emphwell-clustered graphs, spectral clustering algorithms can give a good approximation of the optimal clustering. To the best of our knowledge, it is the \emphfirst theoretical analysis of spectral clustering algorithms for a wide family of graphs, even though such approach was proposed in the early 1990s and has comprehensive applications. We also give a nearly-linear time algorithm for partitioning well-clustered graphs, which is based on heat kernel embeddings and approximate nearest neighbor data structures.

Cite this Paper

BibTeX
@InProceedings{pmlr-v40-Peng15, title = {Partitioning Well-Clustered Graphs: Spectral Clustering Works!}, author = {Peng, Richard and Sun, He and Zanetti, Luca}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {1423--1455}, year = {2015}, editor = {Grünwald, Peter and Hazan, Elad and Kale, Satyen}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Peng15.pdf}, url = {https://proceedings.mlr.press/v40/Peng15.html}, abstract = {In this work we study the widely used \emphspectral clustering algorithms, i.e. partition a graph into k clusters via (1) embedding the vertices of a graph into a low-dimensional space using the bottom eigenvectors of the Laplacian matrix, and (2) partitioning embedded points via k-means algorithms. We show that, for a wide class of \emphwell-clustered graphs, spectral clustering algorithms can give a good approximation of the optimal clustering. To the best of our knowledge, it is the \emphfirst theoretical analysis of spectral clustering algorithms for a wide family of graphs, even though such approach was proposed in the early 1990s and has comprehensive applications. We also give a nearly-linear time algorithm for partitioning well-clustered graphs, which is based on heat kernel embeddings and approximate nearest neighbor data structures.} }
Endnote
%0 Conference Paper %T Partitioning Well-Clustered Graphs: Spectral Clustering Works! %A Richard Peng %A He Sun %A Luca Zanetti %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Peng15 %I PMLR %P 1423--1455 %U https://proceedings.mlr.press/v40/Peng15.html %V 40 %X In this work we study the widely used \emphspectral clustering algorithms, i.e. partition a graph into k clusters via (1) embedding the vertices of a graph into a low-dimensional space using the bottom eigenvectors of the Laplacian matrix, and (2) partitioning embedded points via k-means algorithms. We show that, for a wide class of \emphwell-clustered graphs, spectral clustering algorithms can give a good approximation of the optimal clustering. To the best of our knowledge, it is the \emphfirst theoretical analysis of spectral clustering algorithms for a wide family of graphs, even though such approach was proposed in the early 1990s and has comprehensive applications. We also give a nearly-linear time algorithm for partitioning well-clustered graphs, which is based on heat kernel embeddings and approximate nearest neighbor data structures.
RIS
TY - CPAPER TI - Partitioning Well-Clustered Graphs: Spectral Clustering Works! AU - Richard Peng AU - He Sun AU - Luca Zanetti BT - Proceedings of The 28th Conference on Learning Theory DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Peng15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 40 SP - 1423 EP - 1455 L1 - http://proceedings.mlr.press/v40/Peng15.pdf UR - https://proceedings.mlr.press/v40/Peng15.html AB - In this work we study the widely used \emphspectral clustering algorithms, i.e. partition a graph into k clusters via (1) embedding the vertices of a graph into a low-dimensional space using the bottom eigenvectors of the Laplacian matrix, and (2) partitioning embedded points via k-means algorithms. We show that, for a wide class of \emphwell-clustered graphs, spectral clustering algorithms can give a good approximation of the optimal clustering. To the best of our knowledge, it is the \emphfirst theoretical analysis of spectral clustering algorithms for a wide family of graphs, even though such approach was proposed in the early 1990s and has comprehensive applications. We also give a nearly-linear time algorithm for partitioning well-clustered graphs, which is based on heat kernel embeddings and approximate nearest neighbor data structures. ER -
APA
Peng, R., Sun, H. & Zanetti, L.. (2015). Partitioning Well-Clustered Graphs: Spectral Clustering Works!. Proceedings of The 28th Conference on Learning Theory, in Proceedings of Machine Learning Research 40:1423-1455 Available from https://proceedings.mlr.press/v40/Peng15.html.

Related Material