Consistency of spectral clustering

By Ulrike von Luxburg, Mikhail Belkin, Olivier Bousquet. 2008

423 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/517f2ba2c0ce79d33eea1a6bf1a4a196d9fe0fd9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Limit theorems for eigenvectors of the normalized Laplacian for random graphs (2016, background): “For previous consistency results of X̆ as an estimator for X̃ in various random graphs models, the reader is referred to [34, 35, 43] among others.”
ABX-Discriminability Measures and Applications. (Mesures de discriminabilité ABX et applications) (2016, background): “Existing results include consistency of the ideal solution of K-means clustering (which is unfortunately computationally intractable), a weaker notion of consistency for single-linkage clustering and consistency of spectral clustering [17].”
Geometry on Probability Spaces (2009, methodology): “This construction is in [22], except that we have replaced their positive weighting function by a Mercer kernel.”
Introduction to Semi-Supervised Learning (2009, background): “Some theoretical analysis of graph-based learning can be found in [91, 178, 195], and applications in [73, 78, 111, 102, 136, 138, 139].”
Graph Laplacians and their Convergence on Random Neighborhood Graphs (2006, background): “• The eigenfunctions of the Laplacian ∆s can be seen as the limit partioning of spectral clustering for the normalized graph Laplacian (however, a rigorous mathematical proof has not been given yet, see von Luxburg et al. (2007) for a convergence result for fixed h).”
Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics (2016, background): “…component analysis (Anderson, 2003; Johnstone and Lu, 2009; Cai et al., 2013, 2015b), canonical correlation analysis (Hotelling, 1936; Hardoon et al., 2004; Gao et al., 2014, 2015), community detection (von Luxburg et al., 2008; Rohe et al., 2011; Balakrishnan et al., 2011; Lei and Rinaldo, 2015).”
Finding and Leveraging Structure in Learning Problems (2012, background): “[von Luxburg et al., 2004] and references therein) have shown various forms of asymptotic convergence for the Laplacian of a graph constructed from random samples drawn from a distribution on or near a manifold.”
Convergence of Laplacian Eigenmaps (2006, methodology): “That result follows readily from the previous work in [11] together with the analysis of the essential spectrum of Lt.”
Analyzing the Harmonic Structure in Graph-Based Learning (2013, background): “In spectral clustering, the eigenvectors of the normalized graph Laplacian are more desired than thos e of the un-normalized one [20, 21].”
$\Gamma$-convergence of graph Ginzburg-Landau functionals (2012, neutral): “spired by [5] specically. We like to point out that there is also a substantial literature on the convergence of graph Laplacians and their eigenvalues and eigenvectors to continuum limits. See e.g. [40, 36, 12, 41, 13, 57, 43] and references therein. The techniques used and the kind of results obta”
Neural Operator: Learning Maps Between Function Spaces (2021, background): “…the graph approximations of Nyström type (Belongie et al., 2002) provide a consistent way of connecting different grid or data structures arising in computational methods and understanding their continuum limits (Von Luxburg et al., 2008; Trillos and Slepčev, 2018; Trillos et al., 2020).”