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

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

## Key facts

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

## Built on by (most cited first, 30 of 31)

- [Poisoning and Backdooring Contrastive Learning](https://mlsanity.com/paper/2106.09667/) (2021)
- [Wild Patterns Reloaded: A Survey of Machine Learning Security against Training Data Poisoning](https://mlsanity.com/paper/2205.01992/) (2022)
- [Graph-based Semi-supervised Learning: A Comprehensive Review](https://mlsanity.com/paper/2102.13303/) (2021)
- [Better Safe Than Sorry: Preventing Delusive Adversaries with Adversarial Training](https://mlsanity.com/paper/2102.04716/) (2021)
- [Poisoning the Unlabeled Dataset of Semi-Supervised Learning](https://mlsanity.com/paper/2105.01622/) (2021)
- [A Hard Label Black-box Adversarial Attack Against Graph Neural Networks](https://mlsanity.com/paper/2108.09513/) (2021)
- [Model Inversion Attacks against Graph Neural Networks](https://mlsanity.com/paper/2209.07807/) (2022)
- [Robust Mid-Pass Filtering Graph Convolutional Networks](https://mlsanity.com/paper/2302.08048/) (2023)
- [Poisoning Attack against Estimating from Pairwise Comparisons](https://mlsanity.com/paper/2107.01854/) (2021)
- [Analysis of Label-Flip Poisoning Attack on Machine Learning Based Malware Detector](https://mlsanity.com/paper/2301.01044/) (2023)
- [It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness](https://mlsanity.com/paper/2303.09767/) (2023)
- [Spear and Shield: Adversarial Attacks and Defense Methods for Model-Based Link Prediction on Continuous-Time Dynamic Graphs](https://mlsanity.com/paper/2308.10779/) (2023)
- [Robust Semi-Supervised Learning in Open Environments](https://mlsanity.com/paper/2412.18256/) (2024)
- [Minimum Topology Attacks for Graph Neural Networks](https://mlsanity.com/paper/2403.02723/) (2024)
- [Exact Certification of (Graph) Neural Networks Against Label Poisoning](https://mlsanity.com/paper/2412.00537/) (2024)
- [Task and Model Agnostic Adversarial Attack on Graph Neural Networks](https://mlsanity.com/paper/2112.13267/) (2021)
- [GUAP: Graph Universal Attack Through Adversarial Patching](https://mlsanity.com/paper/2301.01731/) (2023)
- [Adversarial Robustness in Unsupervised Machine Learning: A Systematic Review](https://mlsanity.com/paper/2306.00687/) (2023)
- [Practicable Black-box Evasion Attacks on Link Prediction in Dynamic Graphs -- A Graph Sequential Embedding Method](https://mlsanity.com/paper/2412.13134/) (2024)
- [Everything Perturbed All at Once: Enabling Differentiable Graph Attacks](https://mlsanity.com/paper/2308.15614/) (2023)
- [Are Your Models Still Fair? Fairness Attacks on Graph Neural Networks via Node Injections](https://mlsanity.com/paper/2406.03052/) (2024)
- [Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations](https://mlsanity.com/paper/2503.18503/) (2025)
- [Sparse but Strong: Crafting Adversarially Robust Graph Lottery Tickets](https://mlsanity.com/paper/2312.06568/) (2023)
- [Explainability-Based Adversarial Attack on Graphs Through Edge Perturbation](https://mlsanity.com/paper/2312.17301/) (2023)
- [On the Robustness of Graph Reduction Against GNN Backdoor](https://mlsanity.com/paper/2407.02431/) (2024)
- [RIDA: A Robust Attack Framework on Incomplete Graphs](https://mlsanity.com/paper/2407.18170/) (2024)
- [Adverseness vs. Equilibrium: Exploring Graph Adversarial Resilience through Dynamic Equilibrium](https://mlsanity.com/paper/2505.14463/) (2025)
- [Rethinking Backdoor Data Poisoning Attacks in the Context of Semi-Supervised Learning](https://mlsanity.com/paper/2212.02582/) (2022)
- [Adversary-Robust Graph-Based Learning of WSIs](https://mlsanity.com/paper/2403.14489/) (2024)
- [EDN: A Novel Edge-Dependent Noise Model for Graph Data](https://mlsanity.com/paper/2506.11368/) (2025)

## Abstract (arXiv)

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 ℓ2-norm constraint and classification tasks under ℓ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).