# Are Gradients on Graph Structure Reliable in Gray-box Attacks?

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 31 references that are in the map.
- First posted on arXiv 7 Aug 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [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)
- [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)
- [A Survey on Knowledge Graph-Based Recommender Systems](https://mlsanity.com/paper/2003.00911/) (2020)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [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)
- [A Survey of Adversarial Learning on Graphs](https://mlsanity.com/paper/2003.05730/) (2020)
- [Attacking Graph Convolutional Networks via Rewiring](https://mlsanity.com/paper/1906.03750/) (2019)
- [MCNE: An End-to-End Framework for Learning Multiple Conditional Network Representations of Social Network](https://mlsanity.com/paper/1905.11013/) (2019)
- [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, 10 of 10)

- [Improving the Transferability of Adversarial Samples by Path-Augmented Method](https://mlsanity.com/paper/2303.15735/) (2023)
- [Extracting Low-/High- Frequency Knowledge from Graph Neural Networks and Injecting it into MLPs: An Effective GNN-to-MLP Distillation Framework](https://mlsanity.com/paper/2305.10758/) (2023)
- [Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debias](https://mlsanity.com/paper/2304.00010/) (2023)
- [Safety in Graph Machine Learning: Threats and Safeguards](https://mlsanity.com/paper/2405.11034/) (2024)
- [Adversarial Attacks and Defenses in Machine Learning-Powered Networks: A Contemporary Survey](https://mlsanity.com/paper/2303.06302/) (2023)
- [What Does the Gradient Tell When Attacking the Graph Structure](https://mlsanity.com/paper/2208.12815/) (2022)
- [Everything Perturbed All at Once: Enabling Differentiable Graph Attacks](https://mlsanity.com/paper/2308.15614/) (2023)
- [Debiased Graph Poisoning Attack via Contrastive Surrogate Objective](https://mlsanity.com/paper/2407.19155/) (2024)
- [RIDA: A Robust Attack Framework on Incomplete Graphs](https://mlsanity.com/paper/2407.18170/) (2024)
- [SoK: Systematic analysis of adversarial threats against deep learning approaches for autonomous anomaly detection systems in SDN-IoT networks](https://mlsanity.com/paper/2509.26350/) (2025)

## Abstract (arXiv)

Graph edge perturbations are dedicated to damaging the prediction of graph neural networks by modifying the graph structure. Previous gray-box attackers employ gradients from the surrogate model to locate the vulnerable edges to perturb the graph structure. However, unreliability exists in gradients on graph structures, which is rarely studied by previous works. In this paper, we discuss and analyze the errors caused by the unreliability of the structural gradients. These errors arise from rough gradient usage due to the discreteness of the graph structure and from the unreliability in the meta-gradient on the graph structure. In order to address these problems, we propose a novel attack model with methods to reduce the errors inside the structural gradients. We propose edge discrete sampling to select the edge perturbations associated with hierarchical candidate selection to ensure computational efficiency. In addition, semantic invariance and momentum gradient ensemble are proposed to address the gradient fluctuation on semantic-augmented graphs and the instability of the surrogate model. Experiments are conducted in untargeted gray-box poisoning scenarios and demonstrate the improvement in the performance of our approach.