# BinarizedAttack: Structural Poisoning Attacks to Graph-based Anomaly Detection

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 53 references that are in the map.
- First posted on arXiv 18 Jun 2021.

## Builds on (most cited first, 15 of 15)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [GNNGuard: Defending Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2006.08149/) (2020)
- [Graph-based Anomaly Detection and Description: A Survey](https://mlsanity.com/paper/1404.4679/) (2014)
- [Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1](https://mlsanity.com/paper/1602.02830/) (2016)
- [Hiding Individuals and Communities in a Social Network](https://mlsanity.com/paper/1608.00375/) (2016)
- [Certifiable Robustness and Robust Training for Graph Convolutional Networks](https://mlsanity.com/paper/1906.12269/) (2019)
- [Transferring Robustness for Graph Neural Network Against Poisoning Attacks](https://mlsanity.com/paper/1908.07558/) (2019)
- [On the Decision Boundary of Deep Neural Networks](https://mlsanity.com/paper/1808.05385/) (2018)
- [DefenseVGAE: Defending against Adversarial Attacks on Graph Data via a Variational Graph Autoencoder](https://mlsanity.com/paper/2006.08900/) (2020)
- [Robust Collective Classification against Structural Attacks](https://mlsanity.com/paper/2007.13073/) (2020)

## Built on by (most cited first, 9 of 9)

- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [Reliable Representations Make A Stronger Defender: Unsupervised Structure Refinement for Robust GNN](https://mlsanity.com/paper/2207.00012/) (2022)
- [A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions](https://mlsanity.com/paper/2308.13821/) (2023)
- [FocusedCleaner: Sanitizing Poisoned Graphs for Robust GNN-based Node Classification](https://mlsanity.com/paper/2210.13815/) (2022)
- [A Fine-grained Chinese Software Privacy Policy Dataset for Sequence Labeling and Regulation Compliant Identification](https://mlsanity.com/paper/2212.04357/) (2022)
- [Coupled-Space Attacks against Random-Walk-based Anomaly Detection](https://mlsanity.com/paper/2307.14387/) (2023)
- [Cost Aware Untargeted Poisoning Attack against Graph Neural Networks,](https://mlsanity.com/paper/2312.07158/) (2023)
- [Robust Graph Contrastive Learning with Information Restoration](https://mlsanity.com/paper/2307.12555/) (2023)
- [Interactive Trimming against Evasive Online Data Manipulation Attacks: A Game-Theoretic Approach](https://mlsanity.com/paper/2403.10313/) (2024)

## Abstract (arXiv)

Graph-based Anomaly Detection (GAD) is becoming prevalent due to the powerful representation abilities of graphs as well as recent advances in graph mining techniques. These GAD tools, however, expose a new attacking surface, ironically due to their unique advantage of being able to exploit the relations among data. That is, attackers now can manipulate those relations (i.e., the structure of the graph) to allow some target nodes to evade detection. In this paper, we exploit this vulnerability by designing a new type of targeted structural poisoning attacks to a representative regression-based GAD system termed OddBall. Specially, we formulate the attack against OddBall as a bi-level optimization problem, where the key technical challenge is to efficiently solve the problem in a discrete domain. We propose a novel attack method termed BinarizedAttack based on gradient descent. Comparing to prior arts, BinarizedAttack can better use the gradient information, making it particularly suitable for solving combinatorial optimization problems. Furthermore, we investigate the attack transferability of BinarizedAttack by employing it to attack other representation-learning-based GAD systems. Our comprehensive experiments demonstrate that BinarizedAttack is very effective in enabling target nodes to evade graph-based anomaly detection tools with limited attackers' budget, and in the black-box transfer attack setting, BinarizedAttack is also tested effective and in particular, can significantly change the node embeddings learned by the GAD systems. Our research thus opens the door to studying a new type of attack against security analytic tools that rely on graph data.