GNNGuard: Defending Graph Neural Networks against Adversarial Attacks

Present work. Here, we introduce GNNGuard ¹¹1Code and datasets are available at https://github.com/mims-harvard/GNNGuard. , an approach that can defend any GNN model against a variety of training-time attacks that perturb graph structure (Figure 1). GNNGuard takes as input an existing GNN model. It mitigates adverse effects by modifying the GNN’s neural message passing operators. In particular, it revises the message passing architecture such that the revised model is robust to adversarial perturbations while at the same time the model keeps it representation learning capacity. To this end, GNNGuard develops two key components that estimate neighbor importance for every node and coarsen the graph through an efficient memory layer. The former component dynamically adjusts the relevance of nodes’ local network neighborhoods, prunes likely fake edges, and assigns less weight to suspicious edges based on network theory of homophily [16]. The latter components stabilizes the evolution of graph structure by preserving, in part the memory from a previous layer in the GNN.

Adversarial attacks in continuous and discrete space. Adversarial attacks on machine learning have received increasing attention in recent years [14, 26, 27]. The attackers add small perturbations on the samples to completely alter the output of the machine learning model. The deliberately manipulated perturbations are often designed to be unnoticeable. Modern studies have shown that machine leaning models, especially deep neural networks, are highly fragile to adversarial attacks [13, 28, 29]. The majority of existing works focus on grid data or independent samples [30] whilst a few work investigate adversarial attack on graphs.

Adversarial attacks on graphs. Based on the goal of the attacker, adversarial attacks on graphs [31, 32] can be divided into poisoning attacks\contourwhitepoisoning attacks (e.g., Nettack [8]) that perturb the graph in training-time and evasion attacks\contourwhiteevasion attacks (e.g., RL-S2V [32]) that perturb the graph in testing-time. GNNGuard is designed to improve robustness of GNNs against poisoning attacks. There are two types of poisoning attacks: a targeted attack and a non-targeted attack [33]. The former deceives the model to misclassify a specific node (i.e., target node) [8] while the latter degrades the overall performance of the trained model [30]. The targeted attack can be categorized into direct targeted attack where the attacker perturbs edges touching the target node and the influence targeted attack where the attacker only manipulates edges of the target node’s neighbors. Nettack [8] generates perturbations by modifying graph structure (i.e., structure attack) and node attributes (i.e., feature attack) such that perturbations maximally destroy downstream GNN’s predictions. Bojcheshki et al. [34] derive adversarial perturbations that poison the graph structure. Similarly, Zügner et al. [30] propose a non-targeted poisoning attacker by using meta-gradient to solve bi-level problem. In contrast, our GNNGuard is a defense approach that inspects the graph and recovers adversarial perturbations.

Defense on graphs. While deep learning on graphs has shown exciting results in a variety of applications [6, 23, 35, 36, 37], little attention has been paid to the robustness of such models, in contrast to an abundance of research for image (e.g., [38]) and text (e.g., [39]) adversarial defense. We briefly overview the state-of-the-art defense methods on graphs. GNN-Jaccard [17] is a defense approach that pre-processes the adjacency matrix of the graph to identify the manipulated edges. While GNN-Jaccard can defend targeted adversarial attacks on known and already existing GNNs, there has also been work on novel, robust GNN models. For example, RobustGCN [19] is a novel GNN that adopts Gaussian distributions as the hidden representations of nodes in each convolutional layer to absorb the effect of an attack. Similarly, GNN-SVD [18] uses a low-rank approximation of adjacency matrix that drops noisy information through an SVD decomposition. Tang et al. [20] improve the robustness of GNNs against poisoning attack through transfer learning but has a limitation that requires several unperturbed graphs from the similar domain during training. However, all these approaches have drawbacks (see Section 4.3) that prevent them from realizing their potential for defense to the fullest extent. For instance, none of them consider how to defend heterophily graphs against adversarial attacks. GNNGuard eliminates these drawbacks, successfully defending targeted and non-targeted poisoning attacks on any GNN without decreasing its accuracy.

Background on graph neural networks. Graph neural networks learns compact, low-dimensional representations, i.e., embeddings, for nodes such that representation capture nodes’ local network neighborhoods as well as nodes’ features [6, 3, 40]. The learned embeddings can be used for a variety of downstream tasks [3]. Let $\bm{h}_{u}^{k}\in\mathbb{R}^{D_{k}}$ denote the embedding of node $u$ in the $k$-th layer of GNN, $k=\{1,\dots,K\}$. The $D_{k}$ stands for the dimension of $\bm{h}_{u}^{k}$. Note that $\bm{h}^{0}_{u}=\bm{x}_{u}$. The computations in the $k$-th layer consist of a message-passing function Msg, an aggregation function Agg, and an update function Upd. This means that a GNN $f$ can be specified as $f=(\textsc{Msg},\textsc{Agg},\textsc{Upd})$ [6, 36]. Given a node $u$ and its neighbor $v\in\mathcal{N}_{u}$, the messaging-passing function Msg specifies what neural message $\bm{m}_{uv}^{k}$ needs to be propagated from $v$ to $u$. The message is calculated by $\bm{m}_{uv}^{k}=\textsc{Msg}(\bm{h}_{u}^{k},\bm{h}_{v}^{k},\bm{A}_{uv}),$ where Msg receives node embeddings of $u$ and $v$ along with their connectivity information $e_{uv}$. This is followed by the aggregation function Agg that aggregates all messages received by $u$. The aggregated message $\hat{\bm{m}}^{k}_{u}$ is computed by $\hat{\bm{m}}^{k}_{u}=\textsc{Agg}(\{\bm{m}_{uv}^{k};v\in\mathcal{N}^{*}_{u}\})$. Lastly, the update function Upd combines $u$’s embedding $\bm{h}^{k}_{u}$ and the aggregated message $\hat{\bm{m}}_{u}^{k}$ to generate the embedding for next layer as $\bm{h}_{u}^{k+1}=\textsc{Upd}(\bm{h}_{u}^{k},\hat{\bm{m}}_{u}^{k})$. The final node representation for $u$ is $\bm{h}_{u}^{K}$, i.e., the output of the $K$-th layer.

Background on poisoning attacks. Attackers try to fool a GNN by corrupting the graph topology during training [41]. The attacker carefully selects a small number of edges and manipulates them through perturbation and rewiring. In doing so, the attacker aims to fool the GNN into making incorrect predictions [20]. The attacker finds optimal perturbation $\bm{A}^{\prime}$ through optimization [30, 8]:

where $\bm{y}$ denotes ground-truth labels, $\mathcal{L}_{\textrm{attack}}$ denotes the attacker’s loss function, and $\mathcal{L}_{\textrm{predict}}$ denotes GNN’s loss. The $\Theta^{*}$ refers to optimal parameters and $f(\bm{A}^{\prime},\bm{X};\Theta^{*})$ is prediction of $f$ with parameters $\Theta^{*}$ on the perturbed graph $\bm{A}^{\prime}$ and node features $\bm{X}$. To ensure that attacker perturbs only a small number of edges, a budget $\Delta$ is defined to constrain the number of perturbed edges: $||\bm{A}^{\prime}-\bm{A}||_{0}\leqslant\Delta$ and $\mathcal{P}^{\mathcal{G}}_{\Delta}$ are perturbations that fit into budget $\Delta$. Let $\mathcal{T}$ be target nodes that are intended to be mis-classified, and let $\mathcal{A}$ be attacker nodes that are allowed to be perturbed. We consider three types of attacks. (1) Direct targeted attacks.\contourwhiteDirect targeted attacks. The attacker aims to destroy prediction for target node $u$ by manipulating the incident edges of $u$ [8, 17]. Here, $\mathcal{T}=\mathcal{A}=\{u\}$. (2) Influence targeted attacks.\contourwhiteInfluence targeted attacks. The attacker aims to destroy prediction for target node $u$ by perturbing the edges of $u$’s neighbors. Here, $\mathcal{T}=\{u\}$ and $\mathcal{A}=\mathcal{N}^{*}_{u}$. (3) Non-targeted attacks.\contourwhiteNon-targeted attacks. The attacker aims to degrade overall GNN classification performance [30, 42]. Here, $\mathcal{T}=\mathcal{A}=\mathcal{V}_{\textrm{test}}$ where $\mathcal{V}_{\textrm{test}}$ denotes the test set.

Datasets. We test GNNGuard on four graphs. We use two citation networks with undirected edges and binary features: Cora [48] and Citeseer [49]. We also consider a directed graph with numeric node features, ogbn-arxiv [50], representing a citation network of CS papers published between 1971 and 2014. We use a Disease Pathway (DP) [51] graph with continuous features describing a system of interacting proteins whose malfunction collectively leads to diseases. The task is to predict for every protein node what diseases the protein might cause. Details are in Appendix D.

Setup. (1) Generating adversarial attacks.\contourwhiteGenerating adversarial attacks. We compare our model to baselines under three kinds of adversarial attacks: direct targeted attack (Nettack-Di [8]), influence targeted attack (Nettack-In [8]), and non-targeted attack (Mettack [30]). In Mettack, we set the perturbation rate as $20\%$ (i.e., $\Delta=0.2E$) with ‘Meta-Self’ training strategy. In Nettack-Di, $\Delta=\hat{N}_{u}^{0}$. In Nettack-In, we perturb 5 neighbors of the target node and set $\Delta=\hat{N}_{v}^{0}$ for all neighbors. In the targeted attack, we select 40 correctly classified target nodes (following [8]): 10 nodes with the largest classification margin, 20 random nodes, and 10 nodes with the smallest margin. We run the whole attack and defense procedure for each target node and report average classification accuracy. (2) GNNs.\contourwhiteGNNs. We integrate GNNGuard with five GNNs (GCN [3], GAT [21], GIN [7], JK-Net [22], and GraphSAINT [23]) and present the defense performance against adversarial attacks. (3) Baseline defense algorithms.\contourwhiteBaseline defense algorithms. We compare GNNGuard to three state-of-the-art graph defenders: GNN-Jaccard [17], RobustGCN [19], and GNN-SVD [18]. Hyperparameters and model architectures are in Appendix E.

Impacts on graph ML research. Graphs are universal structures of real-world complex systems. Because of strong representation learning capacity, GNNs have brought success in areas, ranging from disease diagnosis [10] and drug discovery [35] to recommendation system [55]. However, recent studies found that many GNNs are highly vulnerable to adversarial attacks [56]. Adversarial attackers inject imperceptible changes into graphs, thereby fooling downstream GNN classifiers into making incorrect predictions [9]. While there is a rich body of literature on adversarial attacks and defense on non-graph data (e.g., text [39], and images [56]), much less is known about graphs. In an effort towards closing this gap, this paper introduces GNNGuard, a powerful GNN defender that can be straightforwardly integrated into any existing GNN. Because GNNGuard works with any GNN model, its impact on graph ML research is potentially more substantial than that of introducing another, albeit presumably more robust, GNN model.

A variety of impactful application areas. GNNGuard can be used in a wide range of applications by simply integrating GNNGuard with a GNN model of user choice that is most suitable in a particular application, as we demonstrate in this paper. Further positive impacts of GNNGuard include the following. First, we envision that GNNGuard will help users (e.g., governments, companies, and individuals) avoid potential losses that are caused by misjudgments made by attacked GNNs (e.g., in the face of a massive attack on a financial network) [9]. Second, it would be interesting to explore the possibility of deploying GNNGuard for key GNN applications in biomedical domain, where, for example, a GNN diagnostics system could predict false diagnosis if it was trained on the attacked knowledge graph [57]. Finally, our model has implications for fairness and explainability of GNNs [36]), which is key to increase users’ trust in GNN predictions. Lastly, GNNGuard can be used for debugging GNN models and understanding of black-box GNN optimization.

The need for thoughtful use of GNNGuard. It is possible to think of a situation where one would use GNNGuard to get insights into black-box GNN optimization and then use those insights to improve existing attack algorithms, thereby identifying and potentially exploiting new, currently unknown vulnerabilities of GNNs. Because of this possibility and the fact that GNNs are becoming increasingly popular in real-world ML systems, it is important to conduct research to get insights into possible attacks and defense of GNNs.