A Unified Framework for Data Poisoning Attack to Graph-based Semi-supervised Learning

Abstract

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).

NeurIPS 2019 camera-ready

Cited by in corpus (11)

• GNNGuard: Defending Graph Neural Networks against Adversarial Attacks
• Rethinking the Trigger of Backdoor Attack
• Graph Structure Learning for Robust Graph Neural Networks
• Poisoning Attack against Estimating from Pairwise Comparisons
• Poisoning the Unlabeled Dataset of Semi-Supervised Learning
• Poisoning and Backdooring Contrastive Learning
• Towards Security Threats of Deep Learning Systems: A Survey
• Better Safe Than Sorry: Preventing Delusive Adversaries with Adversarial Training
• AN-GCN: An Anonymous Graph Convolutional Network Defense Against Edge-Perturbing Attack
• Algorithms and Hardness for Linear Algebra on Geometric Graphs
• Certified Robustness of Graph Classification against Topology Attack with Randomized Smoothing