Adversarial Attack on Graph Structured Data

By Hanjun Dai, Tian Tian, Xin Huang, L. Wang, Jun Zhu, Le Song. 2018

894 citations recorded by the source corpus.

Deep learning on graph structures has shown exciting results in various applications. However, few attentions have been paid to the robustness of such models, in contrast to numerous research work for image or text adversarial attack and defense. In this paper, we focus on the adversarial attacks that fool the model by modifying the combinatorial structure of data. We first propose a reinforcement learning based attack method that learns the generalizable attack policy, while only requiring prediction labels from the target classifier. Also, variants of genetic algorithms and gradient methods are presented in the scenario where prediction confidence or gradients are available. We use both synthetic and real-world data to show that, a family of Graph Neural Network models are vulnerable to these attacks, in both graph-level and node-level classification tasks. We also show such attacks can be used to diagnose the learned classifiers.

Subfields: Artificial Intelligence, Sociology and Political Science, Graph Learning, Safety, Robustness & Interpretability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

In Graph Learning

In Safety, Robustness & Interpretability

Citations in the corpus

Scaling Laws for Reward Model Overoptimization (2022, methodology): “…demonstrated the existence of adversarial examples in all kinds of neural networks [Szegedy et al., 2013, Lin et al., 2017, Ebrahimi et al., 2018, Dai et al., 2018], and proposed methods to measure and increase neural network robustness [Gu and Rigazio, 2014, Zheng et al., 2016, Carlini et al.,…”
Attacking Graph-based Classification via Manipulating the Graph Structure (2019, methodology): “, existing studies [7,8,12,18,19,21,27,30, 31,37,38,40,43,46,49,51–53,56,60,61,67,68,70] on adversarial machine learning mainly focused on machine learning for non-graph data, with only a few studies [15,16,59,74] as exceptions. In particular, Chen et al. [15] proposed an attack against graph-based ”
Adversarial Attack and Defense on Graph Data: A Survey (2018, methodology): “to the model and make the model inaccurate when using the modified information [8], [28], [145].”
Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective (2019, background): “[Dai et al., 2018] studied test-time non-targeted adversarial attacks on both graph classification and node classification.”
Gradient-based Adversarial Attacks against Text Transformers (2021, background): “While the most prominent data modality by far is image, adversarial examples can be constructed for speech (Carlini and Wagner, 2018) and graphs (Dai et al., 2018; Zügner et al., 2018) as well.”
All You Need Is Low (Rank): Defending Against Adversarial Attacks on Graphs (2020, background): “In another study, Dai et al. [11] proposed a reinforcement learning based attack that generates structure perturbations with full or limited information about the target classifier.”
Deep Learning on Graphs: A Survey (2018, neutral): “…of graphs via random walks O ð M Þ No Adversarial Attack Nettack [128] Targeted attacks of graph structures and node attributes O ð Nd 20 Þ Yes Dai et al. [129] Targeted attacks of graph structures O ð M Þ No Zugner and Gunnemann [130] Non-targeted attacks of graph structures O ð N 2 Þ No”
Finding Global Homophily in Graph Neural Networks When Meeting Heterophily (2022, background): “, 2019), the adversarial attack and defense (Dai et al., 2018; Zhu et al., 2019), and the model explainability (Vu & Thai, 2020; Shan et al.”
Graph Information Bottleneck (2020, neutral): “Also, GNN’s reliance on message passing over the edges of the graph also makes it prone to noise and adversarial attacks that target at the graph structure [15,16].”
Subgraph Federated Learning with Missing Neighbor Generation (2021, background): “However, as GNNs leverage the homophily of nodes in both node features and link structures to conduct the inference, they are vulnerable to the perturbation on graphs [13, 14, 15].”
Generalizable Adversarial Attacks Using Generative Models (2019, methodology): “Note that we do not compare against the graph attack framework of Dai et al. [6], since that work modiﬁes the adjacency matrix of the graph, whereas we modify node features only.”
Graph Structure Learning for Robust Graph Neural Networks (2020, background): “RL-S2V [10] employs reinforcement learning to generate adversarial attacks.”
Graph Contrastive Learning with Augmentations (2020, methodology): “The experiments are performed on synthetic data to classify the component number in graphs, facing the RandSampling, GradArgmax and RL-S2V attacks following the default setting in [60].”
Adversarial Examples on Graph Data: Deep Insights into Attack and Defense (2019, methodology): “Dai et al. [Dai et al. , 2018] brieﬂy introduces a defense method by dropping some edges during the training.”
Graph Random Neural Networks for Semi-Supervised Learning on Graphs (2020, methodology): “agation process and then makes the prediction by using the simple multilayer perceptron (MLP) model. The motivation for random propagation is to address the nonrobustness issue faced by existing GNNs [11, 53, 54]. This process is coupled with the DropNode and propagation steps. In doing so, Grand na”
A Comprehensive Survey on Graph Anomaly Detection With Deep Learning (2021, background): “In addition to all ANOS ND, ED, SGD, and GD techniques reviewed above, it is worth mentioning that perturbed graphs, which adversarial models generate to attack graph classiﬁcation algorithms or GNNs [149], [150], [151], can also be regarded as (intensional) anomalies.”