mlsanityData to 7 Oct 2026

BinarizedAttack: Structural Poisoning Attacks to Graph-based Anomaly Detection

arXiv 2106.09989 ↗First posted 18 Jun 2021cs.LG cs.CRcited by 8

Not on the map. Why?

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.

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

Builds on

15 of 53 references.

References · 15

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2015Distilling the Knowledge in a Neural Networkcited by 10,076
  3. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 395
  4. 2020Graph Structure Learning for Robust Graph Neural Networkscited by 368
  5. 2017Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Rankingcited by 332
  6. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
  7. 2020GNNGuard: Defending Graph Neural Networks against Adversarial Attackscited by 195
  8. 2014Graph-based Anomaly Detection and Description: A Surveycited by 182
  9. 2016Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1cited by 102
  10. 2016Hiding Individuals and Communities in a Social Networkcited by 77
  11. 2019Certifiable Robustness and Robust Training for Graph Convolutional Networkscited by 59
  12. 2019Transferring Robustness for Graph Neural Network Against Poisoning Attackscited by 58
3 more
  1. 2018On the Decision Boundary of Deep Neural Networkscited by 11
  2. 2020DefenseVGAE: Defending against Adversarial Attacks on Graph Data via a Variational Graph Autoencodercited by 10
  3. 2020Robust Collective Classification against Structural Attackscited by 3

Built on by

Cited by year

Citing papers per year: 2022: 4; 2023: 4.

8 papers.

  1. 2022Trustworthy Graph Neural Networks: Aspects, Methods and Trendscited by 88
  2. 2022Reliable Representations Make A Stronger Defender: Unsupervised Structure Refinement for Robust GNNcited by 34
  3. 2023A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directionscited by 15
  4. 2022FocusedCleaner: Sanitizing Poisoned Graphs for Robust GNN-based Node Classificationcited by 7
  5. 2022A Fine-grained Chinese Software Privacy Policy Dataset for Sequence Labeling and Regulation Compliant Identificationcited by 3
  6. 2023Coupled-Space Attacks against Random-Walk-based Anomaly Detectioncited by 2
  7. 2023Cost Aware Untargeted Poisoning Attack against Graph Neural Networks,cited by 1
  8. 2023Robust Graph Contrastive Learning with Information Restorationcited by 0