mlsanityData to 14 Oct 2026

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

arXiv 2208.05514 ↗First posted 7 Aug 2022cs.CR cs.LGcited by 10

Not on the map. Why?

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.

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

20 of 31 references.

References · 20

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  3. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  4. 2017Inductive Representation Learning on Large Graphscited by 6,320
  5. 2017Axiomatic Attribution for Deep Networkscited by 3,384
  6. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
  7. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 397
  8. 2017Adversarial Examples: Attacks and Defenses for Deep Learningcited by 351
  9. 2018Adversarial Attack on Graph Structured Datacited by 301
  10. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
  11. 2019Adversarial Attacks and Defenses in Images, Graphs and Text: A Reviewcited by 237
  12. 2019Topology Attack and Defense for Graph Neural Networks: An Optimization Perspectivecited by 196
8 more
  1. 2020A Survey on Knowledge Graph-Based Recommender Systemscited by 170
  2. 2018Adversarial Attack and Defense on Graph Data: A Surveycited by 167
  3. 2022Improving Adversarial Transferability via Neuron Attribution-Based Attackscited by 93
  4. 2016Hiding Individuals and Communities in a Social Networkcited by 77
  5. 2020A Survey of Adversarial Learning on Graphscited by 42
  6. 2019Attacking Graph Convolutional Networks via Rewiringcited by 32
  7. 2019MCNE: An End-to-End Framework for Learning Multiple Conditional Network Representations of Social Networkcited by 31
  8. 2021Surrogate Representation Learning with Isometric Mapping for Gray-box Graph Adversarial Attackscited by 4

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 5; 2024: 3; 2025: 1.

10 papers.

  1. 2023Improving the Transferability of Adversarial Samples by Path-Augmented Methodcited by 36
  2. 2023Extracting Low-/High- Frequency Knowledge from Graph Neural Networks and Injecting it into MLPs: An Effective GNN-to-MLP Distillation Frameworkcited by 24
  3. 2023Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debiascited by 16
  4. 2024Safety in Graph Machine Learning: Threats and Safeguardscited by 11
  5. 2023Adversarial Attacks and Defenses in Machine Learning-Powered Networks: A Contemporary Surveycited by 5
  6. 2022What Does the Gradient Tell When Attacking the Graph Structurecited by 2
  7. 2023Everything Perturbed All at Once: Enabling Differentiable Graph Attackscited by 2
  8. 2024Debiased Graph Poisoning Attack via Contrastive Surrogate Objectivecited by 2
  9. 2024RIDA: A Robust Attack Framework on Incomplete Graphscited by 1
  10. 2025SoK: Systematic analysis of adversarial threats against deep learning approaches for autonomous anomaly detection systems in SDN-IoT networkscited by 0