Partitioning Well-Clustered Graphs: Spectral Clustering Works!
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
Text
Peng et al. "Partitioning Well-Clustered Graphs: Spectral Clustering Works!." Annual Conference on Computational Learning Theory, 2015. doi:10.1137/15M1047209Markdown
[Peng et al. "Partitioning Well-Clustered Graphs: Spectral Clustering Works!." Annual Conference on Computational Learning Theory, 2015.](https://mlanthology.org/colt/2015/peng2015colt-partitioning/) doi:10.1137/15M1047209BibTeX
@inproceedings{peng2015colt-partitioning,
title = {{Partitioning Well-Clustered Graphs: Spectral Clustering Works!}},
author = {Peng, Richard and Sun, He and Zanetti, Luca},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2015},
pages = {1423-1455},
doi = {10.1137/15M1047209},
url = {https://mlanthology.org/colt/2015/peng2015colt-partitioning/}
}