The geometry of kernelized spectral clustering

Abstract

Clustering of data sets is a standard problem in many areas of science and engineering. The method of spectral clustering is based on embedding the data set using a kernel function, and using the top eigenvectors of the normalized Laplacian to recover the connected components. We study the performance of spectral clustering in recovering the latent labels of i.i.d. samples from a finite mixture of nonparametric distributions. The difficulty of this label recovery problem depends on the overlap between mixture components and how easily a mixture component is divided into two nonoverlapping components. When the overlap is small compared to the indivisibility of the mixture components, the principal eigenspace of the population-level normalized Laplacian operator is approximately spanned by the square-root kernelized component densities. In the finite sample setting, and under the same assumption, embedded samples from different components are approximately orthogonal with high probability when the sample size is large. As a corollary we control the fraction of samples mislabeled by spectral clustering under finite mixtures with nonparametric components.

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

References in corpus (5)

• Consistency of spectral clustering
• Pseudo-likelihood methods for community detection in large sparse networks
• Empirical graph Laplacian approximation of Laplace--Beltrami operators: Large sample results
• Data spectroscopy: Eigenspaces of convolution operators and clustering
• Cluster Forests

Cited by in corpus (13)

• Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss
• Learning by Unsupervised Nonlinear Diffusion
• Efficient Solvers for Sparse Subspace Clustering
• Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence
• Robust and efficient multi-way spectral clustering
• Two-sample Test of Community Memberships of Weighted Stochastic Block Models
• Diffusion $K$-means clustering on manifolds: provable exact recovery via semidefinite relaxations
• Spectral Embedding Norm: Looking Deep into the Spectrum of the Graph Laplacian
• A Tale of Two Bases: Local-Nonlocal Regularization on Image Patches with Convolution Framelets
• Testing For Global Covariate Effects in Dynamic Interaction Event Networks
• The decomposition of the higher-order homology embedding constructed from the $k$-Laplacian
• Bayesian Nonparametric Graph Clustering
• Laplacian Mixture Modeling for Network Analysis and Unsupervised Learning on Graphs