Defending against adversarial attacks on graph neural networks via similarity property

Abstract

Graph Neural Networks (GNNs) are powerful tools in graph application areas. However, recent studies indicate that GNNs are vulnerable to adversarial attacks, which can lead GNNs to easily make wrong predictions for downstream tasks. A number of works aim to solve this problem but what criteria we should follow to clean the perturbed graph is still a challenge. In this paper, we propose GSP-GNN, a general framework to defend against massive poisoning attacks that can perturb graphs. The vital principle of GSP-GNN is to explore the similarity property to mitigate negative effects on graphs. Specifically, this method prunes adversarial edges by the similarity of node feature and graph structure to eliminate adversarial perturbations. In order to stabilize and enhance GNNs training process, previous layer information is adopted in case a large number of edges are pruned in one layer. Extensive experiments on three real-world graphs demonstrate that GSP-GNN achieves significantly better performance compared with the representative baselines and has favorable generalization ability simultaneously.

Keywords

Graph neural network adversarial attack defense similarity property

1. Introduction

Graph is a ubiquitous form in a variety of applications such as social networks [9,25], bioscience [4,20], finance [19], knowledge graph [21], traffic networks [1], etc. With the aim to learn effective representations of graphs and get great performance of downstream works, Graph Neural Networks (GNNs) are designed to put into practice and witnessed fabulous success in representation learning of graphs [14,23,30]. The main principle of GNNs is the neural message passing mechanism, which can propagate neural information along graph edges. Optimizing this mechanism helps GNNs to generate useful representations on downstream tasks [27].

Although promising performances have been achieved in various tasks, recent studies have shown that GNNs are susceptible to adversarial attacks [10,16,26]. In other words, the performance of GNNs can be decreased via attackers’ deliberately designed small perturbations. The lack of robustness of GNN models can lead to severe consequences. For example, in a credit score system, fraudsters can evade detection by exploiting massive transactions with high-credit users as the model usually assumes clients associated with high-credit customers are trustworthy. Hence, developing robust GNN models to defend against adversarial attacks is a crucial issue. The majority of existing adversarial attacks on graph data damage the graph topology by adding a few edges to contaminate the neighborhoods of nodes while models are training simultaneously. This type of attacks are called poisoning attacks [32]. Therefore, we aim to defend against poisoning adversarial attacks on graph in this work.

One method to design an effective defense algorithm is to clean the perturbed graph by removing the adversarial edges [17,24]. The challenge from this perspective is what criteria we should follow to clean the perturbed graph. It is well known that real world graphs often share certain properties. Similarity property is one of these properties, which is of significance to graphs. For instance, in a citation network, two connected publications often share similar topics [12]. But adversarial attacks can damage this property easily. Figure 1 and Table 1 demonstrate the attribute change in graphs via perturbations. Specifically, we apply the state-of-the-art graph poisoning attack, nettack [32], to perturb the graph data and visualize the properties change before and after nettack on Cora, Cora_ml and Citeseer. Figure 1 illustrates that adversarial edges tend to connect nodes with low node feature similarity. We also observe that nodes with low structure are mostly connected because most nodes connected with adversarial attacks have no common neighbors, as shown in Table 1. It is easy to observe that adversarial perturbations are mainly concentrated on node-pairs with low graph similarity property. Thus, graph similarity property has the potential to serve as the effective tool to clean the perturbed data.

Fig. 1.

Nodes similarity change by adversarial edges.

Table 1

The proportion of structural similarity of node pairs connected by adversarial edges

Datasets	Common neighbors

	0	1	2	⩾3
Cora	0.81	0.14	0.03	0.02
Cora_ml	0.76	0.15	0.04	0.05
Citeseer	0.83	0.11	0.06	0

In this paper, we aim to exploit graph similarity property to design robust graph neural networks. In essence, we are faced with two challenges: (1) how to learn clean graph structure from poisoned graph data guided by similarity property; and (2) how to stabilize GNN training process while a large amount of edges being pruned. To solve these two challenges, we propose a general framework, Graph Similarity Property GNN (GSP-GNN), which can defend against adversarial attacks and get a clean and robust graph structure from a perturbed graph. The method mitigates negative effects by pruning adversarial edges via the similarity of node feature and graph structure. It can also stabilize and enhance GNNs training process via previous layer information in case a large number of edges are pruned in one layer. Extensive experiments on a variety of real-world graphs demonstrate that our proposed model can defend against different types of adversarial attacks and outperforms the state-of-the-art defense methods.

The rest of the paper is organized as follows: In Section 2, we review some of the related work. In Section 3, we introduce notations and formally define the problem. We explain our proposed framework in Section 4 and report our experimental results in Section 5. Finally, we conclude the work and introduce future work in Section 6.

2. Related works

In this chapter, we briefly describe related work on adversarial attacks and defense for graph data.

2.1. Adversarial attacks for GNNs

In recent years, it has been proved that deep neural networks (DNNs) are susceptible to adversarial attacks [3,28]. As the extension of DNNs to graphs, there is no doubt that GNNs inherit this vulnerability [8]. In general, based on the attacker’s goal, adversarial attacks on graphs can be divided into poisoning attack that perturbs the graph in training-time and evasion attack that perturbs the graph in testing-time [5]. GSP-GNN is designed to defend against poisoning attacks in this paper. Moreover, there are two types of poisoning attack: targeted attack and non-targeted attack [15]. Targeted attack investigates how the prediction of an individual target node changes under perturbations. For example, nettack [32] injects perturbations on graph to attack the targeted nodes, which leads GNNs to make wrong prediction. Bojcheshki et al. [2] derive adversarial perturbations that poison the graph structure and node embeddings. Non-targeted attack can degrades the overall performance of the trained model. To perturb the graph globally, metattack [33] is designed to use meta-gradient to generates global perturbations.

2.2. Defense for GNNs

As extensive works have suggested the vulnerability of GNNs, plenty of algorithms have been designed to promote the robustness of GNN models. But this research has just started recently. RGCN [31] is designed to absorb the effects of poisoned changes via modeling Gaussian distributions as hidden layers, which can escalate the robustness of GCN. According to nettack results, Entezari et al. [7] propose GCNSVD that preprocess the graph with its low-rank approximations, which drops noisy information through an SVD decomposition. Zhang et al. [29] propose GNNGuard to detect and quantify the relationship between the graph structure and node features, and exploit it to mitigate negative effects of the poisoning attack. Pro-GNN [11], a jointly learning framework, can simultaneously learn a structural graph and a robust GNN model from the poisoned graph. Wu et al. [22] have found that attackers tend to connect to nodes with different features, by which they propose to remove links between dissimilar nodes as a defense. PA-GNN [17] leverages a penalized aggregation mechanism to restrict the negative impact of perturbed edges.

However, the current methods lack generalization ability, which reduces the practicability of these algorithms. Different from the aforementioned defense methods, GSP-GNN eliminates the negative effects on graphs via similarity property and can also achieve practicability simultaneously.

3. Problem statement

Before introducing the problem, we first introduce some preliminaries to aid in understanding the problem.

Let $G = (V, E)$ be a graph, where $V = {v_{1}, v_{2}, \dots, v_{N}}$ is the set of nodes and $E$ is the set of edges. The edges are used to describe the relations between nodes, which can be also represented by an adjacency matrix $A \in R^{N \times N}$ where $A_{i j}$ indicates the existence of an edge between nodes $v_{i}$ and $v_{j}$ . We use $N_{i}$ to indicate the closed neighbor set of node $v_{i}$ including the node itself and $N_{i}^{*}$ denote the open neighbor set of $v_{i}$ excluding the node $v_{i}$ . In addition, we use $X = {x_{1}, x_{2}, \dots, x_{N}} \in R^{N \times D}$ to indicate the node feature matrix with dimension D where $x_{i}$ is the feature vector of the node $v_{i}$ . Thus, a graph can also be denoted as $G = (A, X)$ . According to the common node classification setting, there is only a small part of nodes $V_{L} = {v_{1}, v_{2}, \dots, v_{l}}$ associated with corresponding labels $Y_{L} = {y_{1}, y_{2}, \dots, y_{l}}$ .

We mainly focus on Graph Convolutional Network (GCN) [12] in this work. For GCN, initially, $H^{(0)} = X$ . The GCN model follows the rule to aggregate the neighbors’ features: $\begin{matrix} (1) & H^{(l)} = σ ({\tilde{D}}^{- 1 / 2} \tilde{A} {\tilde{D}}^{- 1 / 2} H^{(l - 1)} W^{(l)}), \end{matrix}$ where $H^{(l)}$ is the output of the l-th layer of GCN, $W^{(l)}$ is the weight matrix of the l-th layer, σ is the activation function such as RELU, $\tilde{A} = A + I$ , and $\tilde{D}$ is the diagonal matrix of $\tilde{A}$ with ${\tilde{D}}_{i i} = \sum_{j} {\tilde{A}}_{i j}$ .

Given a graph $G = (A, X)$ and the partial labels $Y_{L}$ , the aim of node classification for GNN is to learn a function $f_{θ}$ that can make right predictions on the unlabeled nodes. The objective function can be formulated as: $\begin{matrix} (2) & min_{θ} L_{GNN} (A, X, θ, Y_{L}) = \sum_{v_{i} \in V_{L}} ℓ (f_{θ} {(A, X)}_{i}, y_{i}), \end{matrix}$ where θ is the parameter of $f_{θ}$ , $f_{θ} {(A, X)}_{i}$ is the prediction of node $v_{i}$ , and $ℓ (\cdot, \cdot)$ is the loss function. A two-layer GCN can be implemented by $f_{θ} (A, X)$ as follows: $\begin{matrix} (3) & f_{θ} (A, X) = softmax (\hat{A} σ (\hat{A} X W^{(1)}) W^{(2)}), \end{matrix}$ where $θ = {W^{(1)}, W^{(2)}}$ , $\hat{A} = {\tilde{D}}^{- 1 / 2} (A + I) {\tilde{D}}^{- 1 / 2}$ .

With the aforementioned notations and definitions, the problem we aim to study can be stated as follows:

Given $G = (A, X)$ and some partial node label $V_{L}$ with A poisoned by adversarial edges and feature matrix X, a clean and robust GNN model is expected to achieve and promote the node classification accuracy for candidate nodes with unknown labels under poisoned settings.

4. The proposed method

4.1. The overall architecture

The architecture of GSP-GNN is shown in Fig. 2. The method is composed of two components: graph similarity property and stability of training. As a number of poisoning attacks often lead to adding fake edges between nodes that have different similarity [10,22], GSP-GNN first measures graph similarity of node feature and topology structure via Jaccard similarity and common neighbors, respectively, then computes the two metric values to remove the edges with lower values. Moreover, to ensure GNN training process in case many edges are pruned in one layer, the information of previous layer is used to update the current GNN layer training. In the following subsections, we will give the details of the proposed framework.

Fig. 2.

Overall framework of GSP-GNN. Our method firstly clean poisoned graph via similarity property, then use defense coefficient to further weaken negative effects, e.g., $ω_{j m}^{(k)}$ strengthen the connecting nodes while $ω_{i j}^{(k)}$ and $ω_{i k}^{(k)}$ weaken the connecting nodes. Finally, the clean graph can be get effectively by GSP-GNN.

4.2. Utilizing graph similarity property

4.2.1. Utilizing graph structure property

It is evident that adversarial attacks can modify the structure of graphs to lower the performance of GNNs [34]. In order to remove the perturbed edges from the perturbed graph, we utilize the structure similarity attribute of the graph. Common Neighbor (CN) [6] is an excellent metric of this property because it is a classical algorithm in network topology to compute similarity. The core of this algorithm is that given two nodes, the similarity they own is proportional to the number of common neighbors. Hence, CN is often used to evaluate the structural similarity between node pairs. The structural similarity between node $v_{i}$ and node $v_{j}$ can be defined as: $\begin{matrix} (4) & N_{i j} = | N_{i} \cap N_{j} | . \end{matrix}$ For computation, $N_{i j}$ is able to be represented by adjacency matrix A as follows: $\begin{matrix} (5) & T_{i j}^{(k)} = A_{i}^{(k)} {(A_{j}^{(k)})}^{T}, \end{matrix}$ where $A_{i}^{(k)}$ means the i-th column of adjacent matrix A in the k-th layer of GNN, $T_{i j}^{(k)}$ denotes the structural similarity of node $v_{i}$ and node $v_{j}$ in the k-th layer of GNN.

4.2.2. Utilizing node feature property

According to recent works, poisoning attacks generally tend to attack the nodes with different features [29]. Therefore, node feature similarity can also be an effective tool for GNN to eliminate negative effects. Because the features of the datasets in this paper are bag-of-words, we use Jaccard similarity to denote the metric of feature similarity. To this end, the similarity of node $v_{i}$ and node $v_{j}$ in the k-th layer can be quantified as follows: $\begin{matrix} (6) & S_{i j}^{(k)} = \frac{M_{11}^{(k)}}{M_{01}^{(k)} + M_{10}^{(k)} + M_{11}^{(k)}}, \end{matrix}$ where $M_{11}^{(k)}$ is the number of features where both nodes $v_{i}$ and $v_{j}$ have a value of 1. $M_{01}^{(k)}$ denotes the feature number where the value of the feature is 0 in $v_{i}$ but 1 in $v_{j}$ . Meanwhile, $M_{10}^{(k)}$ is the amount of features which have a value of 1 in $v_{i}$ but 0 in $v_{j}$ . We normalize the similarity $S_{i j}^{(k)}$ with the open neighbor set $N_{i}^{*}$ of node $v_{i}$ . The normalization of node feature similarities is shown as: $\begin{matrix} (7) & μ_{i j}^{(k)} = \{\begin{matrix} S_{i j}^{(k)} / \sum_{j \in N_{i}^{*}} S_{i j}^{(k)} \times {\tilde{N}}_{i}^{(k)} / ({\tilde{N}}_{i}^{(k)} + 1) & if i \neq j \\ 1 / ({\tilde{N}}_{i}^{(k)} + 1) & if i = j, \end{matrix} \end{matrix}$ where ${\tilde{N}}_{i}^{(k)} = \sum_{j \in N_{i}^{*}} ‖ S_{i j}^{(k)} ‖_{0}$ . With the normalization above, we can specify the similarity of the node to itself.

It is obvious that the value of the edges under adversarial attack can be small from Eq. (7). Thus, GSP-GNN adopt the metric to prune edges to reduce the bad effects of poisoned nodes in GNN. Specifically, the method calculates edge cutting score for $e_{i j}$ through a non-linear transformation as $σ (μ_{i j}^{(k)} W^{(k)})$ .

Then, based on the similarity analysis above, we define a function that indicates removing adversarial edges via two similarities where P, K are hyperparameters. $\begin{matrix} (8) & Φ_{P, K} (σ (μ_{i j}^{(k)} W^{(k)})) = \{\begin{matrix} 0, & meaning the edge should be cut if σ (μ_{i j}^{(k)} W^{(k)}) ⩽ P, T_{i j}^{(k)} ⩽ K, \\ 1, & otherwise. \end{matrix} \end{matrix}$

Note that our utilizing graph similarity property process is different from that of GCNJaccard [22] in two aspects: (1) Our method normalize node feature similarity as an importance weight, which represents the contribution of node $v_{j}$ towards node $v_{i}$ in the GNN’s passing of neural messages in the poisoned graph, further indicating the necessity and of node feature similarity utilizing; (2) We employ CN as similarity metric to remove adversarial edges, enhancing our method accuracy in mitigating adversarial effects and lowering the probability to remove edges with small value in a clean graph.

4.3. Stabilizing GNN training process

We can get a new graph through cutting node-pair edges meanwhile GNN is training. But this process may damage the stability of GNN if a huge amount of edges get pruned in a single GNN layer. To stabilize GNN, we use the information from the previous layer to update the next GNN layer. The stabilizing process is defined as follows: $\begin{matrix} (9) & ω_{i j}^{(k)} = δ ω_{i j}^{(k - 1)} + (1 - δ) {\tilde{μ}}_{i j}^{(k)}, \end{matrix}$ where $ω_{i j}^{(k)}$ represents defense coefficient for edge $e_{i j}$ in the k-th layer, δ is a coefficient that specifies the retention of information from the previous layer and ${\tilde{μ}}_{i j}^{(k)}$ is defined as follows: $\begin{matrix} (10) & {\tilde{μ}}_{i j}^{(k)} = μ_{i j}^{(k)} Φ_{P, K} (σ (μ_{i j}^{(k)} W^{(k)})) . \end{matrix}$ It should be noted that coefficient $δ \in [0, 1]$ is a learnable parameter and δ is set to $δ = 0$ in the first GNN layer indicating $ω_{i j}^{0} = {\tilde{μ}}_{i j}^{0}$ . Our method can strengthen the connectivity of nodes with higher defense coefficient and weaken the connectivity of nodes with a lower defense coefficient. Moreover, the GNN training can be stabilized via these operations simultaneously.

5. Experiments

In this section, we mainly evaluate the performance of GSP-GNN against different adversarial attacks. To be specific, we aim to answer the following questions:

How does GSP-GNN perform compared to the state-of-the-art defense approaches under various adversarial attacks?

How is the generalization performance of GSP-GNN on other GNN models?

How do different components affect the performance of GSP-GNN?

How do the hyper parameters deployed in our work affect the defense performance?

Before presenting our experimental results and observations, we first introduce the experimental settings.

5.1. Experimental settings

5.1.1. Datasets

We validate our work on three publicly available datasets, i.e., Cora, Citeseer and Cora_ml according to [24,32]. We select the largest connected components of each graph in all experiments. The statistics of the datasets are shown in Table 2.

Table 2
Statistics of the largest connected component of the datasets

Nodes Edges Classes Features

Cora 2485 10138 7 1433

Cora_ml 2810 15692 7 2478

Citeseer 2120 7385 6 3703

	Nodes	Edges	Classes	Features
Cora	2485	10138	7	1433
Cora_ml	2810	15692	7	2478
Citeseer	2120	7385	6	3703

5.1.2. Baselines

We compare our model with state-of-the-art GNNs and defense models to evaluate the effectiveness. The following methods are implemented by the Pytorch adversarial learning library DeepRobust [13]:

GCN [12]: There exist a number of different Graph Convolutional Networks (GCN), and we chose the most representative one [12].

GAT [18]: Graph Attention Netowork (GAT) is composed of attention layers which can learn different weights to different nodes in the neighborhoods.

RGCN [31]: RGCN adopts Gaussian distributions as the hidden representations of nodes in every convolutional layer, when it also absorbs the negative effects caused by adversarial perturbations.

GCNSVD [7]: This is a preprocessing method that can vaccinate GCN with the low-rank approximation of the perturbed graph, which aim to defend high-rank attack such as nettack.

GCNJaccard [22]: GCNJaccard preprocesses the attacked graph by eliminating the edges between nodes with low feature similarity. This approach only works on the nodes with features.

GNNGuard [29]: GNNGuard is a general scalable graph defense framework, which can prune likely fake edges and assign less weight to suspicious edges.

5.1.3. Parameters settings

We randomly split the dataset from each graph as: 10% training, 10% validation, and 80% test. For each experiment, we record the average performance of 20 runs. The hyperparameters of all the models are tuned based on the loss and accuracy on validation set. For GCN, GAT and GNNGuard, we adopt the default parameter setting in the original works. For RGCN, the number of hidden units is set from ${16, 32, 64}$ . For GCNJaccard, the threshold of Jaccard similarity to eliminate edges is randomly selected from ${0.02, 0.04, 0.06, 0.08, 0.1}$ . For GCNSVD, the reduced rank of the poisoned datasets is randomly chosen from ${5, 10, 15, 50, 100, 200}$ .

5.2. Defense performance

In this subsection, with the aim to answer the first question, we evaluate our model on a node classification task against three types of attacks, i.e., non-targeted attack, targeted attack and random attack. For non-targeted attack and targeted attack introduced in Section 2.1, we adopt metattack and nettack, respectively.

Metattack [33]: Metattack is a representative non-targeted attack, which generates poisoning attacks by meta-learning.

Nettack [32]: This targeted attack aims to attack several specific nodes by changing the number of their neighbours.

Random Attack [11]: The fake edges are randomly injected into the graph, which can also be regarded as augmenting random noise to the clean dataset.

We first use the attack method to poison the graph, then train GSP-GNN and baselines on the poisoned graph to evaluate the node classification accuracy achieved by these algorithms.

Table 3
Node classification performance (Accuracy ± Std) under metattack

Dataset Ptb Rate (%) GCN GCNSVD GCNJaccard RGCN GAT GNNGuard GSP-GNN

Cora 0 80.50 ± 0.40 72.52 ± 3.58 78.66 ± 1.42 83.55 ± 0.25 81.57 ± 1.62 77.14 ± 1.23 80.66 ± 0.35

5 76.97 ± 0.86 72.56 ± 3.60 77.27 ± 1.94 75.84 ± 0.44 76.87 ± 2.63 75.14 ± 0.50 79.68 ± 0.70

10 71.09 ± 1.08 63.79 ± 1.51 74.21 ± 1.27 67.26 ± 0.63 73.13 ± 1.87 73.52 ± 1.02 79.83 ± 0.62

15 65.92 ± 1.08 67.59 ± 1.79 70.98 ± 1.22 63.96 ± 0.73 65.06 ± 2.35 71.28 ± 1.16 78.41 ± 0.62

20 54.11 ± 2.04 60.04 ± 2.71 73.18 ± 1.09 53.83 ± 0.71 51.93 ± 1.57 72.55 ± 2.05 77.34 ± 0.35

25 49.96 ± 2.40 54.46 ± 4.25 68.41 ± 4.88 51.46 ± 0.83 49.16 ± 3.76 69.51 ± 1.96 75.65 ± 0.78

Cora_ml 0 85.54 ± 0.13 80.51 ± 3.76 81.84 ± 3.31 86.05 ± 0.23 85.54 ± 0.70 76.44 ± 0.72 86.22 ± 0.27

5 81.87 ± 0.25 79.96 ± 3.00 81.56 ± 1.52 83.21 ± 0.37 83.55 ± 0.71 75.94 ± 0.94 83.07 ± 0.15

10 77.33 ± 0.59 77.86 ± 2.18 78.76 ± 1.34 78.60 ± 0.47 80.19 ± 0.32 75.45 ± 0.55 81.63 ± 0.24

15 74.92 ± 0.73 71.67 ± 19.86 78.13 ± 1.09 76.03 ± 0.28 78.60 ± 1.12 76.17 ± 0.67 80.90 ± 0.19

20 73.16 ± 0.75 77.22 ± 1.36 76.60 ± 1.16 74.97 ± 0.17 76.83 ± 0.87 75.44 ± 0.33 78.91 ± 0.22

25 69.71 ± 0.81 76.00 ± 1.06 75.23 ± 2.16 71.68 ± 0.23 74.47 ± 0.69 75.40 ± 0.46 78.79 ± 0.28

Citeseer 0 71.75 ± 0.42 69.01 ± 0.83 70.66 ± 0.58 72.00 ± 0.56 72.86 ± 0.79 68.69 ± 1.60 71.34 ± 0.89

5 70.56 ± 0.66 68.24 ± 0.54 70.73 ± 0.69 70.70 ± 0.60 72.01 ± 1.02 69.72 ± 1.04 72.12 ± 0.59

10 67.61 ± 0.80 68.78 ± 0.92 69.75 ± 0.81 67.94 ± 0.24 70.20 ± 1.24 69.09 ± 1.82 70.53 ± 0.64

15 63.43 ± 1.37 66.37 ± 2.06 69.53 ± 0.97 64.12 ± 0.93 68.23 ± 0.63 66.84 ± 1.75 69.70 ± 1.24

20 56.62 ± 1.83 61.85 ± 4.25 68.43 ± 1.96 55.92 ± 0.92 60.91 ± 0.00 68.22 ± 2.01 68.87 ± 1.12

25 55.60 ± 2.33 62.83 ± 2.27 68.07 ± 2.08 57.66 ± 0.82 60.83 ± 0.71 66.65 ± 1.32 68.49 ± 0.80

Dataset	Ptb Rate (%)	GCN	GCNSVD	GCNJaccard	RGCN	GAT	GNNGuard	GSP-GNN
Cora	0	80.50 ± 0.40	72.52 ± 3.58	78.66 ± 1.42	83.55 ± 0.25	81.57 ± 1.62	77.14 ± 1.23	80.66 ± 0.35
5	76.97 ± 0.86	72.56 ± 3.60	77.27 ± 1.94	75.84 ± 0.44	76.87 ± 2.63	75.14 ± 0.50	79.68 ± 0.70
10	71.09 ± 1.08	63.79 ± 1.51	74.21 ± 1.27	67.26 ± 0.63	73.13 ± 1.87	73.52 ± 1.02	79.83 ± 0.62
15	65.92 ± 1.08	67.59 ± 1.79	70.98 ± 1.22	63.96 ± 0.73	65.06 ± 2.35	71.28 ± 1.16	78.41 ± 0.62
20	54.11 ± 2.04	60.04 ± 2.71	73.18 ± 1.09	53.83 ± 0.71	51.93 ± 1.57	72.55 ± 2.05	77.34 ± 0.35
25	49.96 ± 2.40	54.46 ± 4.25	68.41 ± 4.88	51.46 ± 0.83	49.16 ± 3.76	69.51 ± 1.96	75.65 ± 0.78
Cora_ml	0	85.54 ± 0.13	80.51 ± 3.76	81.84 ± 3.31	86.05 ± 0.23	85.54 ± 0.70	76.44 ± 0.72	86.22 ± 0.27
5	81.87 ± 0.25	79.96 ± 3.00	81.56 ± 1.52	83.21 ± 0.37	83.55 ± 0.71	75.94 ± 0.94	83.07 ± 0.15
10	77.33 ± 0.59	77.86 ± 2.18	78.76 ± 1.34	78.60 ± 0.47	80.19 ± 0.32	75.45 ± 0.55	81.63 ± 0.24
15	74.92 ± 0.73	71.67 ± 19.86	78.13 ± 1.09	76.03 ± 0.28	78.60 ± 1.12	76.17 ± 0.67	80.90 ± 0.19
20	73.16 ± 0.75	77.22 ± 1.36	76.60 ± 1.16	74.97 ± 0.17	76.83 ± 0.87	75.44 ± 0.33	78.91 ± 0.22
25	69.71 ± 0.81	76.00 ± 1.06	75.23 ± 2.16	71.68 ± 0.23	74.47 ± 0.69	75.40 ± 0.46	78.79 ± 0.28
Citeseer	0	71.75 ± 0.42	69.01 ± 0.83	70.66 ± 0.58	72.00 ± 0.56	72.86 ± 0.79	68.69 ± 1.60	71.34 ± 0.89
5	70.56 ± 0.66	68.24 ± 0.54	70.73 ± 0.69	70.70 ± 0.60	72.01 ± 1.02	69.72 ± 1.04	72.12 ± 0.59
10	67.61 ± 0.80	68.78 ± 0.92	69.75 ± 0.81	67.94 ± 0.24	70.20 ± 1.24	69.09 ± 1.82	70.53 ± 0.64
15	63.43 ± 1.37	66.37 ± 2.06	69.53 ± 0.97	64.12 ± 0.93	68.23 ± 0.63	66.84 ± 1.75	69.70 ± 1.24
20	56.62 ± 1.83	61.85 ± 4.25	68.43 ± 1.96	55.92 ± 0.92	60.91 ± 0.00	68.22 ± 2.01	68.87 ± 1.12
25	55.60 ± 2.33	62.83 ± 2.27	68.07 ± 2.08	57.66 ± 0.82	60.83 ± 0.71	66.65 ± 1.32	68.49 ± 0.80

5.2.1. Against non-targeted adversarial attack

To evaluate the node classification performance of these different methods against non-targeted adversarial attack, we use metattack and keep all the default parameter settings in the authors’ original implementation. The perturbation rate is varied from 0 to 25% with a step size of 5%. All the experiments are conducted 20 times and the average accuracy with standard deviation are shown in Table 3. The best accuracy on node classification is highlighted in bold. From Table 3, several observations are derived as follows:

GSP-GNN consistently outperforms other methods under different perturbation rates. At 5% perturbation rate on the Cora dataset, our model only improves GCN by over 3%. However, at 25% perturbation rate on the three datasets, GCN performs poorly but our model improves it by nearly 26%, 9%, and 13%, respectively. In other words, the variation in our model’s performance is small, indicating that GSP-GNN is more stable when faced with adversarial attacks.

Although GCNJaccard also employs Jaccard similarity to get a clean graph, the performance of GCNJaccard drops rapidly, especially on Cora dataset. This is because the perturbed graph via simple preprocessing is not enough to recover the complex intrinsic graph structure from adversarial perturbations. The experimental results are also consistent with our discussion on comparison between GSP-GNN and GCNJaccard in Section 4.2.2. Moreover, the performance of GNNGuard is also worse than our model’s accuracy at each perturbation rate. The reason is that with the help of graph structure similarity, our model can outperform GNNGuard.

Fig. 3.

Results of different models under nettack.

5.2.2. Against targeted adversarial attack

In this experiment, we adopt nettack as the targeted-attack method and keep its default parameter settings in its original implementation. The perturbation number of each targeted node is set from 1 to 5 with a step size of 1. Nodes in the test set whose degree larger than 10 are set as target nodes. The node classification accuracy on target nodes is shown in Fig. 3. According to this figure, we can observe that as the number of perturbation raises, the performance of GSP-GNN is better than other methods on the attacked target nodes in most cases. For instance, on Cora_ml at 5 perturbation per targeted node, GSP-GNN improves vanilla GCN by 16% and also outperforms other defense baselines. This also shows that GSP-GNN can resist the targeted adversarial attack.

Fig. 4.

Results of different models under random attack.

Table 4

The generalization ability results under metattack

Datasets	GNN model	Ptb Rate(%)

		0	5	10	15	20	25
Cora	GCN	80.50 ± 0.40	76.97 ± 0.86	71.09 ± 1.08	65.92 ± 1.08	54.11 ± 2.04	49.96 ± 2.40
	GSP-GCN	83.47 ± 0.74	79.76 ± 0.45	79.74 ± 0.41	77.98 ± 0.51	77.56 ± 0.72	76.81 ± 0.28
	GAT	78.67 ± 1.62	76.87 ± 2.63	73.13 ± 1.87	65.06 ± 2.35	51.93 ± 1.57	49.16 ± 3.76
	GSP-GAT	80.57 ± 1.79	78.43 ± 2.50	78.92 ± 2.48	79.64 ± 2.38	80.84 ± 1.98	76.27 ± 1.53
	RGCN	79.92 ± 0.25	75.84 ± 0.44	67.26 ± 0.63	63.96 ± 0.73	53.83 ± 0.71	51.46 ± 0.83
	GSP-RGCN	81.55 ± 0.64	79.00 ± 0.58	78.60 ± 0.33	77.28 ± 0.41	77.58 ± 0.42	75.23 ± 0.72
Citeseer	GCN	71.75 ± 0.42	70.56 ± 0.66	67.61 ± 0.80	63.43 ± 1.37	56.62 ± 1.83	55.60 ± 2.33
	GSP-GCN	73.45 ± 0.45	72.54 ± 0.21	72.96 ± 0.35	72.38 ± 0.34	71.56 ± 0.21	70.60 ± 0.54
	GAT	72.86 ± 0.79	72.01 ± 1.02	70.20 ± 1.24	68.23 ± 0.63	60.91 ± 0.00	60.83 ± 0.71
	GSP-GAT	82.38 ± 1.11	81.75 ± 1.06	81.90 ± 1.05	81.11 ± 1.94	81.43 ± 1.24	78.89 ± 1.43
	RGCN	72.00 ± 0.56	70.70 ± 0.60	67.94 ± 0.24	64.12 ± 0.93	55.92 ± 0.92	57.66 ± 0.82
	GSP-RGCN	70.33 ± 1.00	69.61 ± 1.00	70.40 ± 0.84	69.53 ± 1.22	68.20 ± 0.93	68.17 ± 0.92

5.2.3. Against random attack

We evaluate how GSP-GNN performs under different ratios of random noises from 0% to 100% with a step size of 20%. The results are reported in Fig. 4. The figure demonstrates that GSP-GNN outperforms all other baselines and successfully defends against random attack. Thus, with observations shown before, we can get a conclusion that GSP-GNN is able to defend various types of adversarial attacks.

Fig. 5.

The generalization ability results under nettack.

Fig. 6.

The generalization ability results under random attack.

5.3. Generalization performance of GSP-GNN

In this subsection, we mainly discuss the generalization ability of GSP-GNN. To demonstrate that our proposed defense method is generic to other GNNs, we generalize our proposed method into GCN, GAT and RGCN, and test their node classification accuracy, respectively. We evaluate the experiments on Cora and Citeseer datasets under metattack, nettack and random attack settings. We name the new reconstructed GNN model as “GSP-model”. The results are shown in Table 4, Fig. 5 and Fig. 6. From the outcomes, the generalized model achieves better performances than the original models. For instance, on Citeseer dataset, GSP-GCN, GSP-GAT and GSP-RGCN all not only outperforming GCN, GAT and RGCN by a larger margin under netattack setting, respectively, but the former three models show better stability than the latter three methods simultaneously. A similar situation can be observed on Cora dataset under metattack. The reason is that our model can clean the negative effect via similarity of graph structure and node feature, stabilizing GNN with previous layer information while training. Thus, the classification accuracy of our new models on test datasets has gained remarkable improvement compared with the original models, which further demonstrates the generalization ability of our defense method.

5.4. Ablation study

Fig. 7.

Classification performance of GSP-GNN variants.

To analyse what roles the different components in our model to defend against adversarial attacks, we conduct an ablation study and answer the third question in this subsection.

We create three model variants: GSP-GNN-a, GSP-GNN-b and GSP-GNN-c. GSP-GNN-a indicates the method only using previous layer information, GSP-GNN-b only uses pruning via similarity and GSP-GNN-c only uses jaccard similarity. For example, GSP-GNN-c denotes that we just calculate the similarity of node feature and control the effect of other components to zero simultaneously. We report results on Cora and Cora_ml under metattack and similar situations can be observed in other situations. The results are shown in Fig. 7. According to this figure, we can observe that GSP-GNN-a does not surpass too much than GCN under small perturbations. However, when the perturbation becomes large, this variant outperforms vanilla GCN especially on Cora dataset because GSP-GNN-a can exploit the previous layer information to stabilize model training and defense performance. Moreover, GSP-GNN-b and GSP-GNN-c perform much better than GCN. It should be noted that GSP-GNN-c outperforms all other variants except GSP-GNN, which suggests that it is of great significance to exploit node feature similar to reduce the impact of adversarial attacks. From the above observations, diverse components play different roles in defending adversarial attacks and these components can all enhance the performance of our model. Hence, GSP-GNN can outperform state-of-the-art baselines by incorporating these components consistently.

Fig. 8.

Results of parameter analysis on Cora dataset.

5.5. Parameters analysis

We analyse the sensitivity of hyper-parameters K and P for GSP-GNN to answer the fourth question, where K and P denote structure similarity threshold and node feature similarity threshold, respectively. In this experiment, we alter the values of K and P to see how they affect the performance of GSP-GNN. For detail, we vary K from 0 to 2 while P remains unchanged and vary P from 0 to 0.20 while K is constant. We only report the results on Cora dataset at 5 perturbations per targeted node by nettack and at 25% perturbation rate by metattack because similar conclusions can be made in other settings.

The performance change of GSP-GNN is illustrated in Fig. 8. As we can see if the appropriate values for these two hyper-parameters are chosen, the accuracy of our model can be boosted. More specifically, with the K value improving while the performance of GSP-GNN decreasing, this is because the graph structure becomes more sparse. In other words, if the value of K is higher, there is more possibility to prune normal and important edges in the graph. It is worth noting that appropriate value of P can also greatly increase the model’s performance but too large or too small value of P will hurt the performance. This experiment result is also identical with the observations in Table 1 and Fig. 1. Accordingly, small value of K and suitable P value can help improve our model’s performance.

6. Conclusion

In this paper, we first observe graph structure similarity and node feature similarity of three datasets attacked by representative attack – nettack, and find that adversarial perturbations are mainly concentrated on the node-pairs with low graph similarity property. Based on this observation, we introduce a novel defense approach, GSP-GNN. The proposed GSP-GNN employs the graph similarity property as an effective tool to prune adversarial edges. Meanwhile, it adopts the information of the previous layer to stabilize GNN so as to enhance the robustness of the model. A large number of experiments have been conducted on three real datasets to verify that GSP-GNN outperforms current defense algorithms under adversarial attacks. Moreover, we also show the proposed GSP-GNN is generic to other GNN models in node classification tasks through experiments. Inspired by the achievement of graph similarity property, we plan to explore more graph properties such as low-rank and sparse to further improve the robustness of GNNs.

Footnotes

Acknowledgements

This work is supported in part by the National Natural Science Foundation of China (61662079, 11761070, U1703262) and the Xinjiang Natural Science Foundation (2021D01C078).

References

Bai ,

Yao ,

S.S.

Kanhere ,

Wang ,

Liu and

Yang , Spatio-temporal graph convolutional and recurrent networks for citywide passenger demand prediction, in: Proceedings of the 28th ACM International Conference on Information and Knowledge Management, 2019, pp. 2293–2296. doi:10.1145/3357384.3358097.

Bojchevski and

Günnemann , Adversarial attacks on node embeddings via graph poisoning, in: International Conference on Machine Learning, PMLR, 2019, pp. 695–704.

Cao ,

Chen ,

Yao ,

Wang and

W.E.

Zhang , Adversarial attacks and detection on reinforcement learning-based interactive recommender systems, in: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, 2020, pp. 1669–1672. doi:10.1145/3397271.3401196.

C.W.

Coley ,

Jin ,

Rogers ,

T.F.

Jamison ,

T.S.

Jaakkola ,

W.H.

Green ,

Barzilay and

K.F.

Jensen , A graph-convolutional neural network model for the prediction of chemical reactivity, Chemical science 10(2) (2019), 370–377. doi:10.1039/C8SC04228D.

Dai ,

Li ,

Tian ,

Huang ,

Wang ,

Zhu and

Song , Adversarial attack on graph structured data, in: International Conference on Machine Learning, PMLR, 2018, pp. 1115–1124.

Dehmamy ,

A.-L.

Barabási and

Yu , Understanding the representation power of graph neural networks in learning graph topology, in: Proceedings of the 33rd International Conference on Neural Information Processing Systems, Curran Associates Inc., 2019.

Entezari ,

S.A.

Al-Sayouri ,

Darvishzadeh and

E.E.

Papalexakis , All you need is low (rank) defending against adversarial attacks on graphs, in: Proceedings of the 13th International Conference on Web Search and Data Mining, 2020, pp. 169–177. doi:10.1145/3336191.3371789.

Geisler ,

Zügner and

Günnemann , Reliable graph neural networks via robust aggregation, Advances in Neural Information Processing Systems 33 (2020), 13272–13284.

W.L.

Hamilton ,

Ying and

Leskovec , Inductive representation learning on large graphs, in: Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017, pp. 1025–1035.

10.

Jin ,

Li ,

Xu ,

Wang ,

Ji ,

Aggarwal and

Tang , Adversarial attacks and defenses on graphs: A review, a tool and empirical studies, SIGKDD Explor. Newsl. 22(2) (2021), 19–34.

11.

Jin ,

Ma ,

Liu ,

Tang ,

Wang and

Tang , Graph structure learning for robust graph neural networks, in: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020, pp. 66–74.

12.

T.N.

Kipf and

Welling , Semi-supervised classification with graph convolutional networks, arXiv, 2016.

13.

Li ,

Jin ,

Xu and

Tang , Deeprobust: A pytorch library for adversarial attacks and defenses, arXiv, 2020.

14.

Li ,

Tarlow ,

Brockschmidt and

Zemel , Gated graph sequence neural networks, arXiv, 2015.

15.

Liu ,

Si ,

Zhu ,

Li and

C.-J.

Hsieh , A unified framework for data poisoning attack to graph-based semi-supervised learning, in: Proceedings of the 33rd International Conference on Neural Information Processing Systems, Curran Associates Inc., 2019.

16.

Pham ,

Pham and

Dang , Graph adversarial attacks and defense: An empirical study on citation graph, in: 2020 IEEE International Conference on Big Data (Big Data), IEEE, 2020, pp. 2553–2562. doi:10.1109/BigData50022.2020.9377988.

17.

Tang ,

Li ,

Sun ,

Yao ,

Mitra and

Wang , Transferring robustness for graph neural network against poisoning attacks, in: Proceedings of the 13th International Conference on Web Search and Data Mining, 2020, pp. 600–608. doi:10.1145/3336191.3371851.

18.

Velickovic ,

Cucurull ,

Casanova ,

Romero ,

Lio and

Bengio , Graph attention networks, Stat 1050 (2017), 20.

19.

Wang ,

Lin ,

Cui ,

Jia ,

Wang ,

Fang ,

Yu ,

Zhou ,

Yang and

Qi , A semi-supervised graph attentive network for financial fraud detection, in: 2019 IEEE International Conference on Data Mining (ICDM), 2019, pp. 598–607. doi:10.1109/ICDM.2019.00070.

20.

Wang ,

S.T.

Flannery and

Kihara , Protein docking model evaluation by graph neural networks, Frontiers in Molecular Biosciences 8 (2021), 402.

21.

Wang ,

Liu ,

Fan ,

Sun and

P.S.

Yu , Dskreg: Differentiable sampling on knowledge graph for recommendation with relational gnn, in: Proceedings of the 30th ACM International Conference on Information & Knowledge Management, 2021, pp. 3513–3517.

22.

Wu ,

Wang ,

Tyshetskiy ,

Docherty ,

Lu and

Zhu , Adversarial examples for graph data: Deep insights into attack and defense, in: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, 2019, pp. 4816–4823.

23.

Wu ,

Pan ,

Chen ,

Long ,

Zhang and

S.Y.

Philip , A comprehensive survey on graph neural networks, IEEE transactions on neural networks and learning systems 32(1) (2020), 4–24. doi:10.1109/TNNLS.2020.2978386.

24.

Xiao ,

Li and

Su , A lightweight metric defence strategy for graph neural networks against poisoning attacks, in: International Conference on Information and Communications Security, Springer, 2021, pp. 55–72. doi:10.1007/978-3-030-88052-1_4.

25.

Xiao ,

Pei ,

Xiao ,

Yao and

Liu , MutualRec: Joint friend and item recommendations with mutualistic attentional graph neural networks, Journal of Network and Computer Applications 177 (2021), 102954. doi:10.1016/j.jnca.2020.102954.

26.

Xu ,

Ma ,

H.-C.

Liu ,

Deb ,

Liu ,

J.-L.

Tang and

A.K.

Jain , Adversarial attacks and defenses in images, graphs and text: A review, International Journal of Automation and Computing 17(2) (2020), 151–178. doi:10.1007/s11633-019-1211-x.

27.

Xu ,

Hu ,

Leskovec and

Jegelka , How powerful are graph neural networks? arXiv, 2018.

28.

Zhang ,

Guo ,

Tu and

Zhang , Graph alternate learning for robust graph neural networks in node classification, Neural Computing and Applications (2022), 1–13.

29.

Zhang and

Zitnik , GNNGuard: Defending graph neural networks against adversarial attacks, Advances in Neural Information Processing Systems 33 (2020), 9263–9275.

30.

Zhang ,

Cui and

Zhu , Deep learning on graphs: A survey, IEEE Transactions on Knowledge and Data Engineering 34(1) (2022), 249–270. doi:10.1109/TKDE.2020.2981333.

31.

Zhu ,

Zhang ,

Cui and

Zhu , Robust graph convolutional networks against adversarial attacks, in: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019, pp. 1399–1407. doi:10.1145/3292500.3330851.

32.

Zügner ,

Akbarnejad and

Günnemann , Adversarial attacks on neural networks for graph data, in: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018, pp. 2847–2856.

33.

Zügner and

Günnemann, Adversarial Attacks on Graph Neural Networks via Meta Learning, in: International Conference on Learning Representations, 2019.

34.

Zügner and

Günnemann , Certifiable robustness of graph convolutional networks under structure perturbations, in: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020, pp. 1656–1665. doi:10.1145/3394486.3403217.

Defending against adversarial attacks on graph neural networks via similarity property

Abstract

Keywords

1. Introduction

2.1. Adversarial attacks for GNNs

2.2. Defense for GNNs

3. Problem statement

4. The proposed method

4.1. The overall architecture

4.2.1. Utilizing graph structure property

4.2.2. Utilizing node feature property

4.3. Stabilizing GNN training process

5. Experiments

5.1. Experimental settings

5.1.1. Datasets

Table 2 Statistics of the largest connected component of the datasets Nodes Edges Classes Features Cora 2485 10138 7 1433 Cora_ml 2810 15692 7 2478 Citeseer 2120 7385 6 3703

5.1.3. Parameters settings

5.2. Defense performance

5.4. Ablation study

6. Conclusion

Footnotes

Acknowledgements

References

Table 2
Statistics of the largest connected component of the datasets

Nodes Edges Classes Features

Cora 2485 10138 7 1433

Cora_ml 2810 15692 7 2478

Citeseer 2120 7385 6 3703