Adversarial Examples on Graph Data: Deep Insights into Attack and Defense

Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lü, Liming Zhu

Abstract

Graph deep learning models, such as graph convolutional networks (GCN) achieve remarkable performance for tasks on graph data. Similar to other types of deep models, graph deep learning models often suffer from adversarial attacks. However, compared with non-graph data, the discrete features, graph connections and different definitions of imperceptible perturbations bring unique challenges and opportunities for the adversarial attacks and defenses for graph data. In this paper, we propose both attack and defense techniques. For attack, we show that the discreteness problem could easily be resolved by introducing integrated gradients which could accurately reflect the effect of perturbing certain features or edges while still benefiting from the parallel computations. For defense, we observe that the adversarially manipulated graph for the targeted attack differs from normal graphs statistically. Based on this observation, we propose a defense approach which inspects the graph and recovers the potential adversarial perturbations. Our experiments on a number of datasets show the effectiveness of the proposed methods.

Introduction

Graph Convolutional Networks (GCNs) have become a cornerstone for node classification tasks in domains ranging from social networks to e-commerce. However, these models inherit the vulnerabilities of deep learning: small, "imperceptible" changes to the input graph can lead to incorrect predictions. Attacking graphs presents unique challenges due to the discrete nature of edges and features—one cannot simply apply small continuous perturbations. Furthermore, the structural dependencies in graphs allow adversarial "pollution" to spread from a single malicious node to its neighbors.

Methods

Attack: Integrated Gradients (IG)

Standard gradient-based attacks often struggle with the binary nature of graph data, as vanilla gradients may fail to capture the global impact of flipping an edge or feature. To overcome this, we employ Integrated Gradients (IG). By integrating gradients along a path from a baseline (e.g., an empty graph) to the actual input, we obtain a more robust importance score for each potential perturbation. This allows for a more potent attack strategy, such as IG-JSMA, which can efficiently identify the most impactful edges to flip.

Integrated Gradients visualization showing the importance of edges (red lines) connecting to a target node (red star).

Defense: Jaccard Similarity Pruning

A key observation in our study is that adversarial attacks often rely on adding edges between nodes that are statistically dissimilar. By connecting a target node to a neighbor with a completely different feature set, the attacker disrupts the GCN's local aggregation process.

We propose a defense mechanism based on Jaccard similarity. By calculating the similarity between the features of connected nodes and pruning edges that fall below a certain threshold, we can effectively "clean" the graph before training or inference. This statistical check is highly effective because adversarial edges stand out significantly from the natural distribution of the graph.

The distribution of Jaccard similarity in an attacked graph shows a significant spike at zero, indicating that many adversarial edges connect highly dissimilar nodes.

Key Results

  • Attack Potency: In evaluations on the CORA dataset, the IG-JSMA attack achieved a 100% success rate in fooling the model, compared to 96% for standard JSMA.
  • Defense Effectiveness: Applying Jaccard pruning under an FGSM attack restored model accuracy from near 0% to 62.5% on the CORA dataset.
  • Efficiency: The defense is highly scalable, with a computational complexity of $O(N)$ relative to the number of edges, making it suitable for large-scale real-world graphs.

Conclusion

This research highlights the vulnerability of GCNs to structural perturbations and introduces a powerful attack framework using Integrated Gradients. Conversely, we show that simple statistical properties, like Jaccard similarity, can be leveraged to build robust defenses. Future work will focus on adaptive attacks and extending these defense principles to graphs without explicit node features.

Summary updated

Abstract

Graph deep learning models, such as graph convolutional networks (GCN) achieve remarkable performance for tasks on graph data. Similar to other types of deep models, graph deep learning models often suffer from adversarial attacks. However, compared with non-graph data, the discrete features, graph connections and different definitions of imperceptible perturbations bring unique challenges and opportunities for the adversarial attacks and defenses for graph data. In this paper, we propose both attack and defense techniques. For attack, we show that the discreteness problem could easily be resolved by introducing integrated gradients which could accurately reflect the effect of perturbing certain features or edges while still benefiting from the parallel computations. For defense, we observe that the adversarially manipulated graph for the targeted attack differs from normal graphs statistically. Based on this observation, we propose a defense approach which inspects the graph and recovers the potential adversarial perturbations. Our experiments on a number of datasets show the effectiveness of the proposed methods.
BibTeX
@misc{wu2019adversarial,
  author = {Huijun Wu and Chen Wang and Yuriy Tyshetskiy and Andrew Docherty and Kai Lü and Liming Zhu},
  title = {{Adversarial Examples on Graph Data: Deep Insights into Attack and Defense}},
  year = {2019},
  eprint = {1903.01610},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1903.01610},
}
Figure