Partitioning Well-Clustered Graphs with k-Means and Heat Kernel

We study a suitable class of well-clustered graphs that admit good k-way partitions and present the first almost-linear time algorithm for with almost-optimal approximation guarantees partitioning such graphs. A good k-way partition is a partition of the vertices of a graph into disjoint clusters (subsets) S_1,…, S_k, such that each cluster is better connected on the inside than towards the outside. This problem is a key building block in algorithm design, and has wide applications in community detection and network analysis.

Key to our result is a theorem on the multi-cut and eigenvector structure of the graph Laplacians of these well-clustered graphs. Based on this theorem, we give the first rigorous guarantees on the approximation ratios of the widely used k-means clustering algorithms. We also give an almost-linear time algorithm based on heat kernel embeddings and approximate nearest neighbor data structures.