# The geometry of kernelized spectral clustering

arXiv: https://arxiv.org/abs/1404.7552 · HTML: https://mlsanity.com/paper/1404.7552/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2014.

## Built on by (most cited first, 13 of 13)

- [Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss](https://mlsanity.com/paper/2106.04156/) (2021)
- [The SSL Interplay: Augmentations, Inductive Bias, and Generalization](https://mlsanity.com/paper/2302.02774/) (2023)
- [EMP-SSL: Towards Self-Supervised Learning in One Training Epoch](https://mlsanity.com/paper/2304.03977/) (2023)
- [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](https://mlsanity.com/paper/2205.14855/) (2022)
- [Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithms](https://mlsanity.com/paper/2307.05750/) (2023)
- [A Multiscale Environment for Learning by Diffusion](https://mlsanity.com/paper/2102.00500/) (2021)
- [The decomposition of the higher-order homology embedding constructed from the k-Laplacian](https://mlsanity.com/paper/2107.10970/) (2021)
- [Large sample spectral analysis of graph-based multi-manifold clustering](https://mlsanity.com/paper/2107.13610/) (2021)
- [Recovery Guarantees for Kernel-based Clustering under Non-parametric Mixture Models](https://mlsanity.com/paper/2110.09476/) (2021)
- [Minimalistic Unsupervised Learning with the Sparse Manifold Transform](https://mlsanity.com/paper/2209.15261/) (2022)
- [Understanding the Generalization Performance of Spectral Clustering Algorithms](https://mlsanity.com/paper/2205.00281/) (2022)
- [Clustering dynamics on graphs: from spectral clustering to mean shift through Fokker-Planck interpolation](https://mlsanity.com/paper/2108.08687/) (2021)
- [A Poincar'e Inequality and Consistency Results for Signal Sampling on Large Graphs](https://mlsanity.com/paper/2311.10610/) (2023)

## Abstract (arXiv)

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.