Training-time Attacks Against K-nearest Neighbors

Abstract

Nearest neighbor-based methods are commonly used for classification tasks and as subroutines of other data-analysis methods. An attacker with the capability of inserting their own data points into the training set can manipulate the inferred nearest neighbor structure. We distill this goal to the task of performing a training-set data insertion attack against \(k\)-Nearest Neighbor classification (\(k\)NN). We prove that computing an optimal training-time (a.k.a. poisoning) attack against \(k\)NN classification is NP-Hard, even when \(k = 1\) and the attacker can insert only a single data point. We provide an anytime algorithm to perform such an attack, and a greedy algorithm for general \(k\) and attacker budget. We provide theoretical bounds and empirically demonstrate the effectiveness and practicality of our methods on synthetic and real-world datasets. Empirically, we find that \(k\)NN is vulnerable in practice and that dimensionality reduction is an effective defense. We conclude

Stats

• citations1
• S2 citations—
• github stars0
• HF likes0
• heat score2.26
• arxiv keyvartanian2022training

Related papers

• An Adaptive Nearest Neighbor Rule For Classification (2019)0.00
• A Two-stage Active Learning Algorithm For \(k\)-nearest Neighbors (2022)0.00
• A Theory-based Evaluation Of Nearest Neighbor Models Put Into Practice (2018)0.00
• Distributionally Robust Weighted \(k\)-nearest Neighbors (2020)0.00
• Exploiting Pre-trained Models For Drug Target Affinity Prediction With Nearest Neighbors (2024)3.58
• Minimax Rate Optimal Adaptive Nearest Neighbor Classification And Regression (2019)8.35
• On Convergence Of Nearest Neighbor Classifiers Over Feature Transformations (2020)0.00
• Minimax Optimal Algorithms With Fixed-\(k\)-nearest Neighbors (2022)0.00