  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.
