# Geometric Algorithms for k-NN Poisoning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 23 references that are in the map.
- First posted on arXiv 21 Jun 2023.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning](https://mlsanity.com/paper/1712.03141/) (2017)
- [Recent Advances in Adversarial Training for Adversarial Robustness](https://mlsanity.com/paper/2102.01356/) (2021)
- [Certified Robustness to Label-Flipping Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.03018/) (2020)
- [Label Sanitization against Label Flipping Poisoning Attacks](https://mlsanity.com/paper/1803.00992/) (2018)
- [Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2012.03765/) (2020)
- [Poisoning the Unlabeled Dataset of Semi-Supervised Learning](https://mlsanity.com/paper/2105.01622/) (2021)
- [A black-box adversarial attack for poisoning clustering](https://mlsanity.com/paper/2009.05474/) (2020)
- [Suspicion-Free Adversarial Attacks on Clustering Algorithms](https://mlsanity.com/paper/1911.07015/) (2019)
- [Fairness Degrading Adversarial Attacks Against Clustering Algorithms](https://mlsanity.com/paper/2110.12020/) (2021)

## Abstract (arXiv)

We propose a label poisoning attack on geometric data sets against k-nearest neighbor classification. We provide an algorithm that can compute an varepsilon n-additive approximation of the optimal poisoning in n· 2^2O(d+k/varepsilon) time for a given data set X ∈ ℝd, where |X| = n. Our algorithm achieves its objectives through the application of multi-scale random partitions.