Material Detail

Cheeger Cuts and p-Spectral Clustering

Cheeger Cuts and p-Spectral Clustering

This video was recorded at Machine Learning Summer School (MLSS), Chicago 2009. Spectral clustering has become in recent years one of the most popular clustering algorithm. In this talk I discuss a generalized version of spectral clustering based on the second eigenvector of the graph p-Laplacian, a non-linear generalization of the graph Laplacian. The clustering obtained for 1<=2 can be seen as an interpolation of the relaxation of the normalized cut (p=2) and the Cheeger cut (p=1). However, the main motivation for p-spectral clustering is the fact, that one can show that the cut value obtained by thresholding the second eigenvector of the p-Laplacian converges towards the optimal Cheeger cut as p tends to 1. I will also present an efficient implementation which allows to do p-spectral clustering for large scale datasets.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.