TY - GEN

T1 - Partitioning Well-Clustered Graphs

T2 - Conference on Learning Theory

AU - Zanetti, Luca

AU - Sun, He

AU - Peng, Richard

PY - 2015/7/26

Y1 - 2015/7/26

N2 - 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.

AB - 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.

UR - https://arxiv.org/abs/1411.2021

M3 - Conference Contribution (Conference Proceeding)

VL - 40

SP - 1423

EP - 1455

BT - Proceedings of The 28th Conference on Learning Theory

PB - PMLR

Y2 - 3 July 2015 through 6 July 2015

ER -