Partitioning Well-Clustered Graphs: Spectral Clustering Works!

Richard Peng, He Sun, Luca Zanetti

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…