University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Partitioning Well-Clustered Graphs: Spectral Clustering Works!

Partitioning Well-Clustered Graphs: Spectral Clustering Works!

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact info@newton.ac.uk.

SNAW01 - Graph limits and statistics

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 andapproximate nearest neighbor data structures.

Based on joint work with Richard Peng (Georgia Institute of Technology), and Luca Zanetti (University of Bristol).

Reference:  http://arxiv.org/abs/1411.2021

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity