Consistency of spectral clustering

Abstract

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.

Published in at http://dx.doi.org/10.1214/009053607000000640 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• On the discrete spectrum of non-analytic matrix-valued Friedrichs model

Cited by in corpus (149)

• Spectral clustering and the high-dimensional stochastic blockmodel
• Uncovering latent structure in valued graphs: A variational approach
• NetLSD: Hearing the Shape of a Graph
• Continuum limit of total variation on point clouds
• Horseshoes in multidimensional scaling and local kernel methods
• An Analysis of the Convergence of Graph Laplacians
• Spectral clustering based on local linear approximations
• Data spectroscopy: Eigenspaces of convolution operators and clustering
• Delay-coordinate maps and the spectra of Koopman operators
• Operator-theoretic framework for forecasting nonlinear time series with kernel analog techniques
• Schroedinger Eigenmaps for the Analysis of Bio-Medical Data
• Topological consistency via kernel estimation
• Koopman analysis of the long-term evolution in a turbulent convection cell
• Koopman spectra in reproducing kernel Hilbert spaces
• Universally consistent vertex classification for latent positions graphs
• Role of normalization in spectral clustering for stochastic blockmodels
• The geometry of kernelized spectral clustering
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Cryo-EM reconstruction of continuous heterogeneity by Laplacian spectral volumes
• Foundations of a Multi-way Spectral Clustering Framework for Hybrid Linear Modeling
• Cluster Forests
• On information plus noise kernel random matrices
• Learning by Unsupervised Nonlinear Diffusion
• Multiway Spectral Clustering: A Margin-Based Perspective
• Rademacher Complexity Bounds for a Penalized Multiclass Semi-Supervised Algorithm
• Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
• Kernel-based Prediction of Non-Markovian Time Series
• Spectral Convergence of the connection Laplacian from random samples
• Consistency of Cheeger and Ratio Graph Cuts
• Consensus Formation in First-Order Graphon Models with Time-Varying Topologies
• Continuum Limit of Lipschitz Learning on Graphs
• Manifold learning with arbitrary norms
• Connection graph Laplacian methods can be made robust to noise
• A Geometric Heat-Flow Theory of Lagrangian Coherent Structures
• Spectral Clustering for Multiple Sparse Networks: I
• Indo-Pacific variability on seasonal to multidecadal timescales. Part I: Intrinsic SST modes in models and observations
• Spectral Convergence Rate of Graph Laplacian
• Extraction and Prediction of Coherent Patterns in Incompressible Flows through Space-Time Koopman Analysis
• Uniform Convergence Rates for Lipschitz Learning on Graphs
• Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics
• Convergence of the Point Integral method for Poisson equation on point cloud
• A Graph Framework for Manifold-valued Data
• Graph eigenvectors, fundamental weights and centrality metrics for nodes in networks
• Clustering Financial Time Series: How Long is Enough?
• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
• The Normalized Graph Cut and Cheeger Constant: from Discrete to Continuous
• The embedding dimension of Laplacian eigenfunction maps
• Inference for graphs and networks: Extending classical tools to modern data
• Localized Fourier Analysis for Graph Signal Processing
• Higher-order Connection Laplacians for Directed Simplicial Complexes
• General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers
• On the convergence of maximum variance unfolding
• Consistent spectral approximation of Koopman operators using resolvent compactification
• Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation
• Spectral Convergence of Graph Laplacian and Heat Kernel Reconstruction in $L^{\infty }$ from Random Samples
• Quantum mechanics and data assimilation
• Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learning
• When Locally Linear Embedding Hits Boundary
• Molecular aggregation in liquid water: Laplace spectra and spectral clustering of H-bonded network
• Spatiotemporal pattern extraction by spectral analysis of vector-valued observables
• Manifold Regularization for Locally Stable Deep Neural Networks
• Diffusion $K$-means clustering on manifolds: provable exact recovery via semidefinite relaxations
• A Cheeger Cut for Uniform Hypergraphs
• Model-free consistency of graph partitioning
• On Nonlinear Dimensionality Reduction, Linear Smoothing and Autoencoding
• Fast communication-efficient spectral clustering over distributed data
• Covariate Regularized Community Detection in Sparse Graphs
• Some remarks on MCMC estimation of spectra of integral operators
• Joint Association Graph Screening and Decomposition for Large-scale Linear Dynamical Systems
• Local Regularization of Noisy Point Clouds: Improved Global Geometric Estimates and Data Analysis
• How the result of graph clustering methods depends on the construction of the graph
• From random walks to distances on unweighted graphs
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Operator norm convergence of spectral clustering on level sets
• Consistent Semi-Supervised Graph Regularization for High Dimensional Data
• Uniform bounds for invariant subspace perturbations
• Strong Consistency of Prototype Based Clustering in Probabilistic Space
• Posterior Consistency of Semi-Supervised Regression on Graphs
• Laplacian-Based Dimensionality Reduction Including Spectral Clustering, Laplacian Eigenmap, Locality Preserving Projection, Graph Embedding, and Diffusion Map: Tutorial and Survey
• A continuum limit for the PageRank algorithm
• Spectral decomposition of atomic structures in heterogeneous cryo-EM
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Consistency of semi-supervised learning algorithms on graphs: Probit and one-hot methods
• Consistency of archetypal analysis
• Comparing Graph Spectra of Adjacency and Laplacian Matrices
• Next Waves in Veridical Network Embedding
• Spectral Graph Complexity
• Strong Consistency of Reduced K-means Clustering
• Hydrodynamic limit of the Symmetric Exclusion Process on a compact Riemannian manifold
• Nonlocal $p$-Laplacian Variational problems on graphs
• Hypothesis Testing for Equality of Latent Positions in Random Graphs
• CAST: A Correlation-based Adaptive Spectral Clustering Algorithm on Multi-scale Data
• Convergence of Graph Laplacian with kNN Self-tuned Kernels
• When are recommender systems useful?
• Variational limits of k-NN graph based functionals on data clouds
• Out-of-sample Extension for Latent Position Graphs
• Uncertainty quantification in graph-based classification of high dimensional data
• Consistency between ordering and clustering methods for graphs
• On clustering levels of a hierarchical categorical risk factor
• Data-driven discovery of quasiperiodically driven dynamics
• On the optimality of kernels for high-dimensional clustering
• Fast Landmark Subspace Clustering
• Error Bounds of the Invariant Statistics in Machine Learning of Ergodic Itô Diffusions
• Conditional expectation using compactification operators
• On minimal variations for unsupervised representation learning
• Spectral Convergence of Symmetrized Graph Laplacian on manifolds with boundary
• Large sample spectral analysis of graph-based multi-manifold clustering
• Product Manifold Learning
• Cutoff for exact recovery of Gaussian mixture models
• Spectral Embedding Norm: Looking Deep into the Spectrum of the Graph Laplacian
• Diffuse to fuse EEG spectra -- intrinsic geometry of sleep dynamics for classification
• Convergence of Hierarchical Clustering and Persistent Homology Methods on Directed Networks
• Think globally, fit locally under the Manifold Setup: Asymptotic Analysis of Locally Linear Embedding
• Spectral Ranking using Seriation
• Parallel Markov Chain Monte Carlo via Spectral Clustering
• Large algebraic connectivity fluctuations in spatial network ensembles imply a predictive advantage from node location information
• Certifying Global Optimality of Graph Cuts via Semidefinite Relaxation: A Performance Guarantee for Spectral Clustering
• Automatic Region-wise Spatially Varying Coefficient Regression Model: an Application to National Cardiovascular Disease Mortality and Air Pollution Association Study
• Discriminative Learning of Similarity and Group Equivariant Representations
• Multilinear objective function-based clustering
• Topologically penalized regression on manifolds
• Graph connection Laplacian and random matrices with random blocks
• Entropic Optimal Transport in Random Graphs
• On the Universality of Graph Neural Networks on Large Random Graphs
• Impact of regularization on spectral clustering under the mixed membership stochastic block model
• Behavior of Graph Laplacians on Manifolds with Boundary
• Validating Clustering Frameworks for Electric Load Demand Profiles
• An information-geometric approach to feature extraction and moment reconstruction in dynamical systems
• Spectral Clustering with Smooth Tiny Clusters
• Discussion of "Geodesic Monte Carlo on Embedded Manifolds"
• Weighted Cheeger and Buser Inequalities, with Applications to Clustering and Cutting Probability Densities
• Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs
• Unsupervised Learning of GMM with a Uniform Background Component
• Distributional limits of graph cuts on discretized grids
• Unified Statistical Theory of Spectral Graph Analysis
• PDE-Inspired Algorithms for Semi-Supervised Learning on Point Clouds
• Connecting Spectral Clustering to Maximum Margins and Level Sets
• A Nonparametric Approach to High-dimensional k-sample Comparison Problems
• Streaming Belief Propagation for Community Detection
• Analysis of the spectral symbol function for spectral approximation of a differential operator
• co-BPM: a Bayesian Model for Divergence Estimation
• Spiked Laplacian Graphs: Bayesian Community Detection in Heterogeneous Networks
• Seeing the Forest from the Trees in Two Looks: Matrix Sketching by Cascaded Bilateral Sampling
• Spectral properties of kernel matrices in the flat limit
• A survey on spectral embeddings and their applications in data analysis
• Distribution free optimality intervals for clustering