# Suspicion-Free Adversarial Attacks on Clustering Algorithms

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

## Key facts

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

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

- [Robust Fair Clustering: A Novel Fairness Attack and Defense Framework](https://mlsanity.com/paper/2210.01953/) (2022)
- [Resilient Machine Learning for Networked Cyber Physical Systems: A Survey for Machine Learning Security to Securing Machine Learning for CPS](https://mlsanity.com/paper/2102.07244/) (2021)
- [Fair Clustering Using Antidote Data](https://mlsanity.com/paper/2106.00600/) (2021)
- [Fairness Degrading Adversarial Attacks Against Clustering Algorithms](https://mlsanity.com/paper/2110.12020/) (2021)
- [On the Robustness of Deep Clustering Models: Adversarial Attacks and Defenses](https://mlsanity.com/paper/2210.01940/) (2022)
- [Implications of Distance over Redistricting Maps: Central and Outlier Maps](https://mlsanity.com/paper/2203.00872/) (2022)
- [Geometric Algorithms for k-NN Poisoning](https://mlsanity.com/paper/2306.12377/) (2023)
- [Adversarial Robustness on Image Classification with k-means](https://mlsanity.com/paper/2312.09533/) (2023)
- [Sonic: Fast and Transferable Data Poisoning on Clustering Algorithms](https://mlsanity.com/paper/2408.07558/) (2024)
- [Systems-Theoretic and Data-Driven Security Analysis in ML-enabled Medical Devices](https://mlsanity.com/paper/2506.15028/) (2025)
- [Bilevel Models for Adversarial Learning and A Case Study](https://mlsanity.com/paper/2510.25121/) (2025)

## Abstract (arXiv)

Clustering algorithms are used in a large number of applications and play an important role in modern machine learning-- yet, adversarial attacks on clustering algorithms seem to be broadly overlooked unlike supervised learning. In this paper, we seek to bridge this gap by proposing a black-box adversarial attack for clustering models for linearly separable clusters. Our attack works by perturbing a single sample close to the decision boundary, which leads to the misclustering of multiple unperturbed samples, named spill-over adversarial samples. We theoretically show the existence of such adversarial samples for the K-Means clustering. Our attack is especially strong as (1) we ensure the perturbed sample is not an outlier, hence not detectable, and (2) the exact metric used for clustering is not known to the attacker. We theoretically justify that the attack can indeed be successful without the knowledge of the true metric. We conclude by providing empirical results on a number of datasets, and clustering algorithms. To the best of our knowledge, this is the first work that generates spill-over adversarial samples without the knowledge of the true metric ensuring that the perturbed sample is not an outlier, and theoretically proves the above.