# Simple KNN-Based Outlier Detection Achieves Robust Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 52 references that are in the map.
- First posted on arXiv 8 May 2026.

## Builds on (most cited first, 16 of 16)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding](https://mlsanity.com/paper/1711.01323/) (2017)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [Approximation Schemes for Clustering with Outliers](https://mlsanity.com/paper/1707.04295/) (2017)
- [Adapting k-means algorithms for outliers](https://mlsanity.com/paper/2007.01118/) (2020)
- [Fast Noise Removal for k-Means Clustering](https://mlsanity.com/paper/2003.02433/) (2020)
- [Structural Iterative Rounding for Generalized k-Median Problems](https://mlsanity.com/paper/2009.00808/) (2020)
- [Improved Bi-point Rounding Algorithms and a Golden Barrier for k-Median](https://mlsanity.com/paper/2210.13395/) (2022)
- [Clustering What Matters: Optimal Approximation for Clustering with Outliers](https://mlsanity.com/paper/2212.00696/) (2022)
- [Clustering What Matters in Constrained Settings](https://mlsanity.com/paper/2305.00175/) (2023)

## Abstract (arXiv)

Being robust to the presence of outliers is crucial for applying clustering algorithms in practice. In the textitrobust k-Means problem (i.e., k-Means with outliers), the goal is to remove z outliers and minimize the k-Means cost on the remaining points. Despite the close connection between robust k-Means and outlier detection, both theoretical and empirical understanding of the effectiveness of textitclassic outlier detection heuristics for robust k-Means remains limited. In this paper, we prove that under a practical assumption on the optimal cluster sizes, simply removing points with large K-Nearest-Neighbor distances achieves performance comparable to prior work in terms of approximation guarantees: it yields a constant-factor reduction from robust k-Means to standard k-Means, without introducing additional centers or discarding extra outliers, as is commonly required by existing approaches. Empirically, experiments on real-world datasets show that our method outperforms or matches several more sophisticated algorithms in terms of clustering cost and runtime. These results demonstrate that simple KNN-based heuristics can be surprisingly effective for robust clustering, highlighting new opportunities to bridge techniques from outlier detection and clustering.