Consistency of spectral clustering
Open accessAbstract
Consistency is a key property of all statistical procedures analyzing randomly sampled data. 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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Clustering is fraught with ambiguities, including arbitrariness of threshold choices and lack of robustness.
“Although clustering is clearly a very important part of data analysis, the ways in which it is formulated and implemented are fraught with ambiguities.In particular, the arbitrariness of various threshhold choices and lack of robustness are difficulties one confronts.”
From Topology and data (2009) · cites this paper as [43]
The Introduction describes clustering as widely used and says its consistency guarantees are unsatisfactory. The discussion following Proposition 24 shows that unnormalized spectral clustering can fail and that its reliability can be difficult to assess. These passages support the general concern about reliability, but they do not identify arbitrary threshold choices as a difficulty or establish a lack of robustness for clustering generally; no page numbers are available in our copy. (LLM, conf=0.82)
Experimental — accuracy not yet measuredFunctoriality provides the right general mathematical framework for addressing ambiguities in clustering.
“Much of current research efforts are focused in this direction (see, e.g., [43] and [39]), and functoriality provides the right general mathematical framework for addressing them.”
From Topology and data (2009) · cites this paper as [43]
The Introduction discusses questions about whether clustering algorithms converge, and Section 5.2 constructs operators for analyzing spectral clustering. Neither passage addresses functoriality or presents it as a framework for resolving ambiguities in clustering; searches for those concepts found no supporting passage in our copy. (LLM, conf=0.76)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
The Elements of Statistical Learning
Hastie, T., Friedman, J., & Tibshirani, R. (2001) · Springer Series in Statistics · doi:10.1007/978-0-387-21606-5 · Cited by 24,162 · see citing works
Perturbation Theory for Linear Operators
Kato, T. (1995) · Classics in mathematics · doi:10.1007/978-3-642-66282-9 · Cited by 16,360 · see citing works
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,842 · see citing works
Rudin, W. (1973) · Cited by 13,708 · see citing works
Jain, A. K., Murty, M. N., & Flynn, P. J. (1999) · ACM Computing Surveys · doi:10.1145/331499.331504 · Cited by 13,532 · see citing works
A tutorial on spectral clustering
von Luxburg, U. (2007) · Statistics and Computing · doi:10.1007/s11222-007-9033-z · Cited by 10,519 · see citing works
On Spectral Clustering: Analysis and an algorithm
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2001) · Cited by 8,159 · see citing works
Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
Belkin, M., & Niyogi, P. (2003) · Neural Computation · doi:10.1162/089976603321780317 · Cited by 7,562 · see citing works
Self-citationChung, F. (1996) · Regional conference series in mathematics · doi:10.1090/cbms/092 · Cited by 5,918 · see citing works
Weak Convergence and Empirical Processes
van der Vaart, A. W., & Wellner, J. A. (1996) · Springer Series in Statistics · doi:10.1007/978-1-4757-2545-2 · Cited by 5,014 · see citing works
Algebraic connectivity of graphs
Fiedler, M. (1973) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1973.101168 · Cited by 4,049 · see citing works
Learning with Local and Global Consistency
Zhou, D., Bousquet, O., Lal, T. N., Weston, J., & Schölkopf, B. (2003) · MPG.PuRe (Max Planck Society) · Cited by 3,856 · see citing works
Self-citationSemi-supervised learning using Gaussian fields and harmonic functions
Zhu, X., Zoubin Ghahramani, A., & Lafferty, J. (2003) · Cited by 3,509 · see citing works
Convergence of Stochastic Processes.
Robinson, P. M., & Pollard, D. (1985) · Economica · doi:10.2307/2553898 · Cited by 2,239 · see citing works
Convergence of Stochastic Processes
Pollard, D. (1984) · Springer series in statistics · doi:10.1007/978-1-4612-5254-2 · Cited by 1,859 · see citing works
Co-clustering documents and words using bipartite spectral graph partitioning
Dhillon, I. S. (2001) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/502512.502550 · Cited by 1,726 · see citing works
Partitioning Sparse Matrices with Eigenvectors of Graphs
Pothen, A., Simon, H. D., & Liou, K.-P. (1990) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0611030 · Cited by 1,703 · see citing works
Random Walks on Graphs: A Survey
Lovász, L. (2001) · Cited by 1,420 · see citing works
New spectral methods for ratio cut partitioning and clustering
Hagen, L., & Kahng, A. B. (1992) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.159993 · Cited by 1,303 · see citing works
The Numerical Treatment of Integral Equations
Baker, C., & Taylor, R. L. (1979) · Journal of Applied Mechanics · doi:10.1115/1.3424708 · Cited by 1,190 · see citing works
THE LAPLACIAN SPECTRUM OF GRAPHS y
Mohar, B. (1991) · Cited by 1,119 · see citing works
A Lower Bound for the Smallest Eigenvalue of the Laplacian
Cheeger, J. (2015) · Princeton University Press eBooks · doi:10.1515/9781400869312-013 · Cited by 995 · see citing works
A min-max cut algorithm for graph partitioning and data clustering
Ding, C. H. Q., He, X., Hongyuan Zha, B., Gu, M., & Simon, H. D. (2002) · Proceedings · doi:10.1109/icdm.2001.989507 · Cited by 850 · see citing works
Uniform Central Limit Theorems
Dudley, R. M. (1999) · Cambridge University Press eBooks · doi:10.1017/cbo9780511665622 · Cited by 808 · see citing works
Semi-Supervised Learning on Riemannian Manifolds
Belkin, M., & Niyogi, P. (2004) · Machine Learning · doi:10.1023/b:mach.0000033120.25363.1e · Cited by 803 · see citing works
Self-citationStoer, M., & Wagner, F. (1997) · Journal of the ACM · doi:10.1145/263867.263872 · Cited by 742 · see citing works
Segmentation using eigenvectors: a unifying view
Weiss, Y. (1999) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.1999.790354 · Cited by 729 · see citing works
Lower Bounds for the Partitioning of Graphs
Donath, W. E., & Hoffman, A. J. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.175.0420 · Cited by 669 · see citing works
A Random Walks View of Spectral Segmentation.
Meilă, M., & Shi, J. (2001) · Cited by 628 · see citing works
Spectral Approximation of Linear Operators
Chatelin, F. (2011) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970678 · Cited by 520 · see citing works
An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
Hendrickson, B., & Leland, R. W. (1995) · SIAM Journal on Scientific Computing · doi:10.1137/0916028 · Cited by 486 · see citing works
Strong Consistency of $K$-Means Clustering
Pollard, D. (1981) · The Annals of Statistics · doi:10.1214/aos/1176345339 · Cited by 467 · see citing works
Cluster Kernels for Semi-Supervised Learning
Chapelle, O., Weston, J., & Schölkopf, B. (2002) · Cited by 457 · see citing works
Spectral partitioning works: planar graphs and finite element meshes
Spielman, D. A., & Teng, S. (1996) · doi:10.1109/sfcs.1996.548468 · Cited by 410 · see citing works
On clusterings-good, bad and spectral
Kannan, R., Vempala, S., & Veta, A. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892125 · Cited by 377 · see citing works
Learning Eigenfunctions Links Spectral Embedding and Kernel PCA
Bengio, Y., Delalleau, O., Roux, N. L., Paiement, J.-F., Vincent, P., & Ouimet, M. (2004) · Neural Computation · doi:10.1162/0899766041732396 · Cited by 345 · see citing works
The covering number in learning theory
Zhou, D. (2002) · Journal of Complexity · doi:10.1006/jcom.2002.0635 · Cited by 325 · see citing works
Expander flows, geometric embeddings and graph partitioning
Arora, S., Rao, S. B., & Vazirani, U. V. (2004) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1007352.1007355 · Cited by 294 · see citing works
Alpert, C. J., & Yao, S.-Z. (1995) · Proceedings - ACM IEEE Design Automation Conference · doi:10.1145/217474.217529 · Cited by 205 · see citing works
Consistency of Single Linkage for High-Density Clusters
Hartigan, J. A. (1981) · Journal of the American Statistical Association · doi:10.1080/01621459.1981.10477658 · Cited by 195 · see citing works
A Few Notes on Statistical Learning Theory
Mendelson, S. (2003) · Lecture notes in computer science · doi:10.1007/3-540-36434-x_1 · Cited by 163 · see citing works
A spectral algorithm for envelope reduction of sparse matrices
Barnard, S. T., Pothen, A., & Simon, H. D. (1995) · Numerical Linear Algebra with Applications · doi:10.1002/nla.1680020402 · Cited by 160 · see citing works
On the Quality of Spectral Separators
Guattery, S., & Miller, G. L. (1998) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479896312262 · Cited by 152 · see citing works
Random Matrix Approximation of Spectra of Integral Operators
Koltchinskii, V. I., Evarist Gine, M., & Evarist Gine, M. (2000) · Bernoulli · doi:10.2307/3318636 · Cited by 151 · see citing works
The Effect of the Input Density Distribution on Kernel-based Classifiers
Williams, C. K. I., & Seeger, M. (2000) · Cited by 140 · see citing works
Problems of learning on manifolds
Niyogi, P., & Belkin, M. A. (2003) · Cited by 124 · see citing works
Self-citationBousquet, O., Chapelle, O., & Hein, M. (2003) · Cited by 116 · see citing works
Self-citationAn improved spectral bisection algorithm and its application to dynamic load balancing
Driessche, R. V., & Roose, D. (1995) · Parallel Computing · doi:10.1016/0167-8191(94)00059-j · Cited by 90 · see citing works
The minimax distortion redundancy in empirical quantizer design
Bartlett, P. L., Linder, T., & Lugosi, G. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.705560 · Cited by 87 · see citing works
Higher eigenvalues and isoperimetric inequalities on Riemannian manifolds and graphs
Chung, F., Grigor'yan, A. A., & Yau, S. (2000) · Communications in Analysis and Geometry · doi:10.4310/cag.2000.v8.n5.a2 · Cited by 76 · see citing works
The numerical solutions of the eigenvalue problem for compact integral operators
ATKINSON, K. E. (1967) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1967-0220105-3 · Cited by 68 · see citing works
Berger, E. (2001) · Bulletin of the London Mathematical Society · doi:10.1017/s0024609301239289 · Cited by 67 · see citing works
Spectral Clustering and Kernel PCA are Learning EigenfunctionsPreprint
Bengio, Y., Vincent, P., Paiement, J.-F., Delalleau, O., Ouimet, M. C., & Roux, N. L. (2004) · RePEc: Research Papers in Economics · Cited by 44 · see citing works
Asymptotics of Spectral Projections of Some Random Matrices Approximating Integral Operators
Koltchinskii, V. I. (1998) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-8829-5_11 · Cited by 39 · see citing works
On the Eigenspectrum of the Gram Matrix and Its Relationship to the Operator Eigenspectrum
Shawe-Taylor, J. S., Williams, C., Cristianini, N., et al. (2002) · Lecture notes in computer science · doi:10.1007/3-540-36169-3_4 · Cited by 38 · see citing works
Consistency of Single Linkage for High-Density Clusters
Hartigan, J. A. (1981) · Journal of the American Statistical Association · doi:10.2307/2287840 · Cited by 37 · see citing works
Statistical Learning with Similarity and Dissimilarity Functions
Ulrike Von Luxburg, A. (2004) · MPG.PuRe (Max Planck Society) · Cited by 26 · see citing works
The Numerical Solution of the Eigenvalue Problem for Compact Integral Operators
ATKINSON, K. E. (1967) · Transactions of the American Mathematical Society · doi:10.2307/1994601 · Cited by 22 · see citing works
Ben-David, S. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27819-1_29 · Cited by 21 · see citing works
On the spectral properties of the matrix-valued Friedrichs model
Abdullaev, Z. I., & Lakaev, S. N. (1991) · Advances in Soviet mathematics · doi:10.1090/advsov/005/01 · Cited by 15 · see citing works
On the discrete spectrum of the nonanalytic matrix-valued Friedrichs model
Ikromov, I. A., & Sharipov, F. (1998) · Functional Analysis and Its Applications · doi:10.1007/bf02465757 · Cited by 13 · see citing works
An Approach to Data Reduction and Clustering with Theoretical Guarantees
Niyogi, P., & Karmarkar, N. K. (2000) · Cited by 6 · see citing works
Anthony, M. (2002) · Cited by 6 · see citing works
On the discrete spectrum of non-analytic matrix-valued Friedrichs modelPreprint
Ikramov, I. A., & Sharipov, F. (1995) · arXiv (Cornell University) · doi:10.48550/arxiv.funct-an/9502004 · Cited by 1 · see citing works
Flagged first, then by citations
Research works printed but not linked: 2
- [38]38. Morgan Kaufmann, San Francisco, CA.
- [52]52. Morgan Kaufmann, San Francisco.
Cited by
Sorted by citations
Carlsson, G. (2009) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-09-01249-x · Cited by 2,302 · see citing works
Comparison of algorithms for ultrasound image segmentation without ground truth
Sikka, K., & Deserno, T. M. (2010) · SPIE Proceedings · doi:10.1117/12.844504 · Cited by 4 · see citing works
- Authors
- von Luxburg, U., Belkin, M., & Bousquet, O.
- Affiliations
- University of Chicago (US)
- Max Planck Society (DE)
- Venue
- The Annals of Statistics
- Publisher
- Institute of Mathematical Statistics
- Published
- 2008-04-01
- Volume
- 36
- Issue
- 2
- Pages
- 555-586
- ISSN
- 0090-5364 (ISSN-L)
- 2168-8966
- OpenAlex
- W2002276939
- Cited by
- 540
- References
- 64
- Citations by year
- 2026: 15 · 2025: 22 · 2024: 32 · 2023: 25 · 2022: 25 · 2021: 52 · 2020: 43 · 2019: 43 · 2018: 34 · 2017: 21 · 2016: 32 · 2015: 25 · 2014: 25 · 2013: 27 · 2012: 25
- FWCI
- 41.68
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- The Annals of Statistics (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- Project Euclid (Cornell University) (submittedVersion)
- Max Planck Institute for Plasma Physics (submittedVersion)
- MPG.PuRe (Max Planck Society) (submittedVersion)
- MPG.PuRe (Max Planck Society) (submittedVersion, other-oa)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Clustering Algorithms Research
- Physical Sciences › Mathematics › Statistics and Probability › Statistical Methods and Inference
- Physical Sciences › Computer Science › Artificial Intelligence › Bayesian Methods and Mixture Models
- Keywords
- spectral clustering, consistency, graph Laplacian, eigenvector convergence, limit operators, random sampling, large-sample asymptotics
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
