Partitioning Well-Clustered Graphs: Spectral Clustering Works!

Luca Zanetti, He Sun, Richard Peng

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

14 Citations (Scopus)
9 Downloads (Pure)


In this paper we study variants of the widely used spectral clustering that partitions a graph into $k$ clusters by (1) embedding the vertices of a graph into a low-dimensional space using the bottom eigenvectors of the Laplacian matrix and (2) grouping the embedded points into $k$ clusters via $k$-means algorithms. We show that, for a wide class of graphs, spectral clustering gives a good approximation of the optimal clustering. While this approach was proposed in the early 1990s and has comprehensive applications, prior to our work similar results were known only for graphs generated from stochastic models. We also give a nearly linear time algorithm for partitioning well-clustered graphs based on computing a matrix exponential and approximate nearest neighbor data structures.
Original languageEnglish
Title of host publicationProceedings of The 28th Conference on Learning Theory
Number of pages33
Publication statusPublished - 26 Jul 2015
EventConference on Learning Theory - Paris, France
Duration: 3 Jul 20156 Jul 2015

Publication series

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


ConferenceConference on Learning Theory


Dive into the research topics of 'Partitioning Well-Clustered Graphs: Spectral Clustering Works!'. Together they form a unique fingerprint.

Cite this