A Unified Framework for Data Poisoning Attack to Graph-based Semi-supervised Learning
This work addresses security vulnerabilities in graph-based semi-supervised learning, which is incremental as it builds on existing attack methods by unifying them into a framework.
The authors tackled the problem of data poisoning attacks in graph-based semi-supervised learning by proposing a unified framework and specialized algorithms for efficient attacks, achieving results such as flipping two labeled data points to degrade model performance to random guess levels (around 50% error) on MNIST binary classification.
In this paper, we proposed a general framework for data poisoning attacks to graph-based semi-supervised learning (G-SSL). In this framework, we first unify different tasks, goals, and constraints into a single formula for data poisoning attack in G-SSL, then we propose two specialized algorithms to efficiently solve two important cases --- poisoning regression tasks under $\ell_2$-norm constraint and classification tasks under $\ell_0$-norm constraint. In the former case, we transform it into a non-convex trust region problem and show that our gradient-based algorithm with delicate initialization and update scheme finds the (globally) optimal perturbation. For the latter case, although it is an NP-hard integer programming problem, we propose a probabilistic solver that works much better than the classical greedy method. Lastly, we test our framework on real datasets and evaluate the robustness of G-SSL algorithms. For instance, on the MNIST binary classification problem (50000 training data with 50 labeled), flipping two labeled data is enough to make the model perform like random guess (around 50\% error).