清华大学交叉信息研究院

Partitioning Well-Clustered Graphs: Spectral Clustering Works!

演讲人： He Sun University of Bristol
时间： 2015-07-17 10:30-2015-07-17 11:30
地点：FIT 1-203-5
内容：

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.

个人简介:

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.