hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Learning, cs.LG
Abstract:
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_i\}_{i=1}^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.
