Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Multiway partitioning of well-clustered graphs (SPOILER ALERT: spectral clustering works!)
Speaker:Luca Zanetti
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 13 January 2015
Duration:30 Minutes
Building:E1 4
Partitioning a graph into several pieces such that each piece is better connected on the inside than towards the outside is an important problem in algorithm design, and has comprehensive applications in various areas of Computer Science, e.g. Machine Learning, and Computer Vision.

A popular approach to deal with this problem is Spectral Clustering: (1) Embed the vertices of a graph into a low-dimensional space using the top/bottom eigenvectors of the graph’s Laplacian/adjacency matrix. (2) Partition embedded points via k-means algorithms. (3) Group graph’s vertices according to the output of k-means algorithms.

Such approach was introduced in the early 1990s. Despite wide applications and surprisingly good performances, a rigorous theoretical analysis of this approach was missing for more than 25 years, apart from analysis of toy examples or some specific restricted random models.

In this talk, I will present our recent work giving the first rigorous analysis of the above framework. Our study to this framework also leads to an almost-linear time algorithm for partitioning a graph.

Joint work with Richard Peng and He Sun.

Name(s):Luca Zanetti
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Luca Zanetti, 01/12/2015 03:02 PM
  • Luca Zanetti, 12/03/2014 02:41 PM
  • Luca Zanetti, 12/03/2014 02:40 PM -- Created document.