@article{4403,
  title = {Consistency of Spectral Clustering},
  journal = {Annals of Statistics},
  abstract = {Consistency is a key property of statistical algorithms when the data
  is drawn from some underlying probability distribution.  Surprisingly,
  despite decades of work, little is known about consistency of most
  clustering algorithms.  In this paper we investigate consistency of
  the popular family of spectral clustering algorithms, which clusters
  the data with the help of eigenvectors of graph Laplacian matrices. We
  develop new methods to establish that for increasing sample size,
  those eigenvectors converge to the eigenvectors of certain limit
  operators. As a result we can prove that one of the two major classes
  of spectral clustering (normalized clustering) converges under very
  general conditions, while the other (unnormalized clustering) is only
  consistent under strong additional assumptions, which are not always
  satisfied in real data.  We conclude that our analysis provides strong
  evidence for the superiority of normalized spectral clustering.},
  volume = {36},
  number = {2},
  pages = {555-586},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  month = apr,
  year = {2008},
  slug = {4403},
  author = {von Luxburg, U. and Belkin, M. and Bousquet, O.},
  month_numeric = {4}
}