# A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2019.

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

- [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](https://mlsanity.com/paper/2205.14855/) (2022)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Adversarially robust clustering with optimality guarantees](https://mlsanity.com/paper/2306.09977/) (2023)
- [A provable initialization and robust clustering method for general mixture models](https://mlsanity.com/paper/2401.05574/) (2024)
- [Clustering with Uniformity- and Neighbor-Based Random Geometric Graphs](https://mlsanity.com/paper/2501.06268/) (2025)
- [Towards Robust Nonlinear Subspace Clustering: A Kernel Learning Approach](https://mlsanity.com/paper/2501.06368/) (2025)
- [SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search](https://mlsanity.com/paper/2506.03657/) (2025)
- [Individual-heterogeneous sub-Gaussian Mixture Models](https://mlsanity.com/paper/2604.05337/) (2026)
- [A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation](https://mlsanity.com/paper/2609.09211/) (2026)

## Abstract (arXiv)

We consider the problem of clustering datasets in the presence of arbitrary outliers. Traditional clustering algorithms such as k-means and spectral clustering are known to perform poorly for datasets contaminated with even a small number of outliers. In this paper, we develop a provably robust spectral clustering algorithm that applies a simple rounding scheme to denoise a Gaussian kernel matrix built from the data points and uses vanilla spectral clustering to recover the cluster labels of data points. We analyze the performance of our algorithm under the assumption that the "good" data points are generated from a mixture of sub-gaussians (we term these "inliers"), while the outlier points can come from any arbitrary probability distribution. For this general class of models, we show that the misclassification error decays at an exponential rate in the signal-to-noise ratio, provided the number of outliers is a small fraction of the inlier points. Surprisingly, this derived error bound matches with the best-known bound for semidefinite programs (SDPs) under the same setting without outliers. We conduct extensive experiments on a variety of simulated and real-world datasets to demonstrate that our algorithm is less sensitive to outliers compared to other state-of-the-art algorithms proposed in the literature.