# Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debias

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 35 references that are in the map.
- First posted on arXiv 29 Mar 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [BERT-ATTACK: Adversarial Attack Against BERT Using BERT](https://mlsanity.com/paper/2004.09984/) (2020)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Adversarial Examples: Attacks and Defenses for Deep Learning](https://mlsanity.com/paper/1712.07107/) (2017)
- [Session-based Recommendation with Graph Neural Networks](https://mlsanity.com/paper/1811.00855/) (2018)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Adversarial Attacks and Defenses in Images, Graphs and Text: A Review](https://mlsanity.com/paper/1909.08072/) (2019)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [Tactics of Adversarial Attack on Deep Reinforcement Learning Agents](https://mlsanity.com/paper/1703.06748/) (2017)
- [Self-supervised Learning on Graphs: Contrastive, Generative,or Predictive](https://mlsanity.com/paper/2105.07342/) (2021)
- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (2021)
- [Improving Adversarial Transferability via Neuron Attribution-Based Attacks](https://mlsanity.com/paper/2204.00008/) (2022)
- [Hiding Individuals and Communities in a Social Network](https://mlsanity.com/paper/1608.00375/) (2016)
- [Towards More Practical Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2006.05057/) (2020)
- [A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Models](https://mlsanity.com/paper/1908.01297/) (2019)
- [GraphMixup: Improving Class-Imbalanced Node Classification on Graphs by Self-supervised Context Prediction](https://mlsanity.com/paper/2106.11133/) (2021)
- [Attacking Graph Convolutional Networks via Rewiring](https://mlsanity.com/paper/1906.03750/) (2019)
- [Exploiting Sentiment and Common Sense for Zero-shot Stance Detection](https://mlsanity.com/paper/2208.08797/) (2022)
- [Node Injection Attacks on Graphs via Reinforcement Learning](https://mlsanity.com/paper/1909.06543/) (2019)
- [AEON: A Method for Automatic Evaluation of NLP Test Cases](https://mlsanity.com/paper/2205.06439/) (2022)
- [Are Gradients on Graph Structure Reliable in Gray-box Attacks?](https://mlsanity.com/paper/2208.05514/) (2022)
- [Surrogate Representation Learning with Isometric Mapping for Gray-box Graph Adversarial Attacks](https://mlsanity.com/paper/2110.10482/) (2021)

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

- [A General Black-box Adversarial Attack on Graph-based Fake News Detectors](https://mlsanity.com/paper/2404.15744/) (2024)
- [Simple and Efficient Partial Graph Adversarial Attack: A New Perspective](https://mlsanity.com/paper/2308.07834/) (2023)
- [Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2312.03979/) (2023)
- [Collective Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2403.01423/) (2024)
- [Graph Defense Diffusion Model](https://mlsanity.com/paper/2501.11568/) (2025)
- [Everything Perturbed All at Once: Enabling Differentiable Graph Attacks](https://mlsanity.com/paper/2308.15614/) (2023)
- [Revisiting Edge Perturbation for Graph Neural Network in Graph Data Augmentation and Attack](https://mlsanity.com/paper/2403.07943/) (2024)
- [Debiased Graph Poisoning Attack via Contrastive Surrogate Objective](https://mlsanity.com/paper/2407.19155/) (2024)
- [Momentum Gradient-based Untargeted Attack on Hypergraph Neural Networks](https://mlsanity.com/paper/2310.15656/) (2023)
- [AGSOA:Graph Neural Network Targeted Attack Based on Average Gradient and Structure Optimization](https://mlsanity.com/paper/2406.13228/) (2024)
- [RIDA: A Robust Attack Framework on Incomplete Graphs](https://mlsanity.com/paper/2407.18170/) (2024)
- [SFR-GNN: Simple and Fast Robust GNNs against Structural Attacks](https://mlsanity.com/paper/2408.16537/) (2024)
- [On the Adversarial Robustness of Graph Neural Networks with Graph Reduction](https://mlsanity.com/paper/2412.05883/) (2024)
- [AHSG: Adversarial Attack on High-level Semantics in Graph Neural Networks](https://mlsanity.com/paper/2412.07468/) (2024)
- [Graph-Aware Stealthy Poison-Text Backdoors for Text-Attributed Graphs](https://mlsanity.com/paper/2603.20339/) (2026)
- [Let Prompts Bridge Defense Knowledge: Transferable Graph Purification via Vulnerability-Aware GPL](https://mlsanity.com/paper/2608.29054/) (2026)

## Abstract (arXiv)

It has become cognitive inertia to employ cross-entropy loss function in classification related tasks. In the untargeted attacks on graph structure, the gradients derived from the attack objective are the attacker's basis for evaluating a perturbation scheme. Previous methods use negative cross-entropy loss as the attack objective in attacking node-level classification models. However, the suitability of the cross-entropy function for constructing the untargeted attack objective has yet been discussed in previous works. This paper argues about the previous unreasonable attack objective from the perspective of budget allocation. We demonstrate theoretically and empirically that negative cross-entropy tends to produce more significant gradients from nodes with lower confidence in the labeled classes, even if the predicted classes of these nodes have been misled. To free up these inefficient attack budgets, we propose a simple attack model for untargeted attacks on graph structure based on a novel attack objective which generates unweighted gradients on graph structures that are not affected by the node confidence. By conducting experiments in gray-box poisoning attack scenarios, we demonstrate that a reasonable budget allocation can significantly improve the effectiveness of gradient-based edge perturbations without any extra hyper-parameter.