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:A Note on Spectral Clustering
Speaker:Pavel Kolev
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 29 March 2016
Duration:30 Minutes
Building:E1 4
Spectral clustering is a popular and successful approach for partitioning the nodes of a graph into clusters for which the ratio of outside connections compared to the volume (sum of degrees) is small. In order to partition into $k$ clusters, one first computes an approximation of the first $k$ eigenvectors of the (normalized) Laplacian of $G$, uses it to embed the vertices of $G$ into $k$-dimensional Euclidean space $\R^k$, and then partitions the resulting points via a $k$-means clustering algorithm. It is an important task for theory to explain the success of spectral clustering.

Peng et al. (COLT, 2015) made an important step in this direction. They showed that spectral clustering provably works if the gap between the $(k+1)$-th and the $k$-th eigenvalue of the normalized Laplacian is sufficiently large. They prove a structural and an algorithmic result. The algorithmic result needs a considerably stronger gap assumption and does not analyze the standard spectral clustering paradigm; it replaces spectral embedding by heat kernel embedding and $k$-means clustering by locality sensitive hashing.

We extend their work in two directions. Structurally, we improve the quality guarantee for spectral clustering by a factor of $k$ and simultaneously weaken the gap assumption. Algorithmically, we show that the standard paradigm for spectral clustering works. Moreover, it even works with the same gap assumption as required for the structural result.

Name(s):Pavel Kolev
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Pavel Kolev, 03/09/2016 04:58 PM
  • Pavel Kolev, 02/02/2016 12:22 PM -- Created document.