Institute for Interdisciplinary Information Sciences (IIIS)

home>Events>Upcoming Events>Institute Seminars

Partitioning Well-Clustered Graphs: Spectral Clustering Works!

Speaker: He Sun University of Bristol
Time: 2015-07-17 10:30-2015-07-17 11:30
Venue: FIT 1-203-5

Abstract:

We study the widely used spectral clustering algorithms, i.e. partition a graph into k clusters via (1) embedding the vertices of a graph into a low-dimensional space using the bottom eigenvectors of the Laplacian matrix, and (2) partitioning the embedded points via k-means algorithms. We show that, for a wide class of graphs, spectral clustering algorithms give 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, which is based on heat kernel embeddings and approximate nearest neighbor data structures.

This is based on the joint work with Richard Peng (MIT), and Luca Zanetti (University of Bristol). Part of the results appeared in COLT 2015.

Short Bio:

I am a tenured lecturer of Computer Science at the University of Bristol. Prior to that, I was a senior researcher at the Max Planck Institute for Informatics, an independent research group leader at the Cluster of Excellence on "Multimodal Computing and Interaction", Saarland University, and a research fellow at the Simons Institute for the Theory of Computing, UC Berkeley.

I obtained a BA from Fudan University (2005), and a PhD from Fudan University (2010). I won the President Medal of Fudan University in 2004, awarded to 2 out of 45,000 students that year. My thesis won Shanghai Distinguished Dissertation Award.

My main research is in algorithm's design and analysis. Specific topics that I have worked on include computational geometry, data streaming algorithms, distributed computing, algorithmic spectral graph theory.