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

**Authors:** Xuanqing Liu, Si Si, Xiaojin Zhu, Yang Li, Cho-Jui Hsieh  
**arXiv:** [1910.14147](https://arxiv.org/abs/1910.14147)  
**Date:** 2019-10-30  
**Summary page:** https://www.summarizepaper.com/en/paper/1910.14147v1/

## Key points

- The paper presents a unified framework for data poisoning attacks in graph-based semi-supervised learning (G-SSL)
- Two specialized algorithms are introduced to address critical scenarios: poisoning regression tasks under $\ell_2$-norm constraint and classification tasks under $\ell_0$-norm constraint
- For poisoning regression tasks, the authors tackle it as a non-convex trust region problem and demonstrate that their gradient-based algorithm can effectively identify the globally optimal perturbation
- Addressing classification tasks under $\ell_0$-norm constraint presents an NP-hard integer programming challenge, which is overcome by a probabilistic solver proposed by the authors
- Experiments on real datasets show that even flipping two labeled data points in a binary classification problem using MNIST data can significantly reduce model performance
- The study contributes valuable insights into enhancing the security and reliability of G-SSL models against data poisoning attacks, offering practical solutions for safeguarding machine learning systems

## Summary

The paper "A Unified Framework for Data Poisoning Attack to Graph-based Semi-supervised Learning" by Xuanqing Liu, Si Si, Xiaojin Zhu, Yang Li, and Cho-Jui Hsieh presents a comprehensive framework for conducting data poisoning attacks in graph-based semi-supervised learning (G-SSL). This framework unifies various tasks, goals, and constraints into a single formula. The authors introduce two specialized algorithms designed to efficiently address two critical scenarios: poisoning regression tasks under $\ell_2$-norm constraint and classification tasks under $\ell_0$-norm constraint. For the former case of poisoning regression tasks, the authors tackle it as a non-convex trust region problem. They demonstrate that their gradient-based algorithm can effectively identify the globally optimal perturbation with careful initialization and update schemes. In contrast, addressing classification tasks under $\ell_0$-norm constraint presents an NP-hard integer programming challenge. To overcome this complexity, the authors propose a probabilistic solver that outperforms traditional greedy methods significantly. Furthermore, the researchers validate their framework by conducting experiments on real datasets to assess the robustness of G-SSL algorithms. For instance, in a binary classification problem using MNIST data with 50 labeled samples out of 50,000 training instances, simply flipping two labeled data points is enough to reduce model performance to chance levels (around 50% error rate). This study contributes valuable insights into enhancing the security and reliability of graph-based semi-supervised learning models against data poisoning attacks. The proposed framework and algorithms offer practical solutions for safeguarding machine learning systems from malicious manipulations in real-world applications.