# What Does the Gradient Tell When Attacking the Graph Structure

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 36 references that are in the map.
- First posted on arXiv 26 Aug 2022.

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

- [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)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [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)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (2020)
- [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)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (2021)
- [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)
- [Understanding and Improving Graph Injection Attack by Promoting Unnoticeability](https://mlsanity.com/paper/2202.08057/) (2022)
- [Transferring Robustness for Graph Neural Network Against Poisoning Attacks](https://mlsanity.com/paper/1908.07558/) (2019)
- [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)
- [How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implications](https://mlsanity.com/paper/2106.07767/) (2021)
- [Are Gradients on Graph Structure Reliable in Gray-box Attacks?](https://mlsanity.com/paper/2208.05514/) (2022)

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

- [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)

## Abstract (arXiv)

Recent research has revealed that Graph Neural Networks (GNNs) are susceptible to adversarial attacks targeting the graph structure. A malicious attacker can manipulate a limited number of edges, given the training labels, to impair the victim model's performance. Previous empirical studies indicate that gradient-based attackers tend to add edges rather than remove them. In this paper, we present a theoretical demonstration revealing that attackers tend to increase inter-class edges due to the message passing mechanism of GNNs, which explains some previous empirical observations. By connecting dissimilar nodes, attackers can more effectively corrupt node features, making such attacks more advantageous. However, we demonstrate that the inherent smoothness of GNN's message passing tends to blur node dissimilarity in the feature space, leading to the loss of crucial information during the forward process. To address this issue, we propose a novel surrogate model with multi-level propagation that preserves the node dissimilarity information. This model parallelizes the propagation of unaggregated raw features and multi-hop aggregated features, while introducing batch normalization to enhance the dissimilarity in node representations and counteract the smoothness resulting from topological aggregation. Our experiments show significant improvement with our approach.Furthermore, both theoretical and experimental evidence suggest that adding inter-class edges constitutes an easily observable attack pattern. We propose an innovative attack loss that balances attack effectiveness and imperceptibility, sacrificing some attack effectiveness to attain greater imperceptibility. We also provide experiments to validate the compromise performance achieved through this attack loss.