Multiway partitioning of well-clustered graphs (SPOILER ALERT: spectral clustering works!)

A popular approach to deal with this problem is Spectral Clustering: (1) Embed the vertices of a graph into a low-dimensional space using the top/bottom eigenvectors of the graph’s Laplacian/adjacency matrix. (2) Partition embedded points via k-means algorithms. (3) Group graph’s vertices according to the output of k-means algorithms.

Such approach was introduced in the early 1990s. Despite wide applications and surprisingly good performances, a rigorous theoretical analysis of this approach was missing for more than 25 years, apart from analysis of toy examples or some specific restricted random models.

In this talk, I will present our recent work giving the first rigorous analysis of the above framework. Our study to this framework also leads to an almost-linear time algorithm for partitioning a graph.

Joint work with Richard Peng and He Sun.

http://arxiv.org/abs/1411.2021