@inproceedings{2775,
  title = {Limits of Spectral Clustering},
  journal = {Advances in Neural Information Processing Systems 17: Proceedings of the 2004 Conference},
  booktitle = {Advances in Neural Information Processing Systems 17},
  abstract = {An important aspect of clustering algorithms is whether the partitions constructed on finite samples converge to a useful clustering of the whole data space as the sample size increases. This paper investigates this question for normalized and unnormalized versions of the popular spectral
  clustering algorithm. Surprisingly, the convergence of unnormalized spectral clustering is more difficult to handle than the normalized case. Even though recently some first results on the convergence of normalized spectral clustering have been obtained, for the unnormalized case
  we have to develop a completely new approach combining tools from numerical integration, spectral and perturbation theory, and probability. It turns out that while in the normalized case, spectral clustering usually converges to a nice partition of the data space, in the unnormalized case
  the same only holds under strong additional assumptions which are not always satisfied. We conclude that our analysis gives strong evidence for the superiority of normalized spectral clustering. It also provides a basis
  for future exploration of other Laplacian-based methods.},
  pages = {857-864},
  editors = {Saul, L. K., Y. Weiss, L. Bottou},
  publisher = {MIT Press},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Cambridge, MA, USA},
  month = jul,
  year = {2005},
  slug = {2775},
  author = {von Luxburg, U. and Bousquet, O. and Belkin, M.},
  month_numeric = {7}
}