Partitioning Well-Clustered Graphs: Spectral Clustering Works!

Abstract

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 using the bottom eigenvectors of the Laplacian matrix, and (2) grouping the embedded points into k clusters via k-means algorithms. We show that, for a wide class of graphs, spectral clustering gives a good approximation of the optimal clustering. While this approach was proposed in the early 1990s and has comprehensive applications, prior to our work similar results were known only for graphs generated from stochastic models. We also give a nearly-linear time algorithm for partitioning well-clustered graphs based on computing a matrix exponential and approximate nearest neighbor data structures.

A preliminary version of this paper appeared in COLT'15; the full version is to appear in SIAM Journal on Computing

Cited by in corpus (15)

• Nearly-Linear Time Spectral Graph Reduction for Scalable Graph Partitioning and Data Visualization
• Diffusion Operator and Spectral Analysis for Directed Hypergraph Laplacian
• Transfer operators on graphs: Spectral clustering and beyond
• Temporal Human Action Segmentation via Dynamic Clustering
• Convex Programming Based Spectral Clustering
• Approximate Spectral Clustering: Efficiency and Guarantees
• Higher-Order Spectral Clustering of Directed Graphs
• Distributed Graph Clustering by Load Balancing
• Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs
• An SDP Primal-Dual Approximation Algorithm for Directed Hypergraph Expansion and Sparsest Cut with Product Demands
• Robust spectral clustering using LASSO regularization
• Generalizing the Hypergraph Laplacian via a Diffusion Process with Mediators
• Average Sensitivity of Spectral Clustering
• Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs
• Distribution free optimality intervals for clustering