Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions
Authors: Lukas Gosch
Simon Geisler
Daniel Sturm
Bertrand Charpentier
Daniel Zügner
Stephan Günnemann
Venue: NeurIPS 2023 poster (2023)
Keywords: adversarial training
adversarial examples
robust graph learning
graph machine learning
graph neural networks
graphs
TL;DR: We highlight and overcome fundamental limitations and pitfalls in adversarial training against graph structure perturbations and propose a new global attack aware of node-level perturbations constraints.

Abstract: Despite its success in the image domain, adversarial training did not (yet) stand out as an effective defense for Graph Neural Networks (GNNs) against graph structure perturbations. In the pursuit of fixing adversarial training  (1) we show and overcome fundamental theoretical as well as practical limitations of the adopted graph learning setting in prior work; (2) we reveal that flexible GNNs based on learnable graph diffusion are able to adjust to adversarial perturbations, while the learned message passing scheme is naturally interpretable; (3) we introduce the first attack for structure perturbations that, while targeting multiple nodes at once, is capable of handling global (graph-level) as well as local (node-level) constraints. Including these contributions, we demonstrate that adversarial training is a state-of-the-art defense against adversarial structure perturbations.

Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions
Lukas Gosch 1 Simon Geisler Daniel Sturm' Bertrand Charpentier',
Daniel Zügner! Stephan Günnemann'
Depaartment of Computer Science & Munich Data Science Institute
Technical University of Munich
Microsoft Research
{1. gosch,, s. s.geisler, da. sturm, s gug.nuneman)ettumm de deuegmer@nicrosoft.ccom
Abstract
Despite its success in the image domain, adversarial training did not (yet) stand out as an effective defense for Graph Neural Networks (GNNs) against graph structure perturbations. In the pursuit of fixing adversarial training (/) show and overcome fundamental theoretical as well as practical limitations the adopted graph learning setting in prior work; (2) we reveal that flexible GNNs based on Iearnable graph diffusion are able to adjust to ad adversarial perturbations, while the learned message passing scheme is naturally interpretable: (3) we introduce the first attack for structure perturbations that, while targeting multiple nodes at once, is capable of handling global (graph-level) as well as local (node-level) constraints, Including these contributions, we demonstrate that adversarial training is state-of- state-of-the-aae titthhe-rtt defense against adversarial structure perturbations)
1 Introduction
Adversarial training has weathered the test of time and stands out as one of the few effective measures against adversarial perturbations. While this is particularly true for numerical input data like images [ it is not yet established as an effective method to defend predictions of Graph Neural Networks (GNNs) against graph structure perturbations.
MLP
Although previous work reported some robustness
GCN
gains by using adversarial training in GNNs 2 3 closer inspection highlights two main shortcomings: (i) their learning setting leads to biased evaluation and (ii) the studied architectures seem to struggle to learn robust representations.
GCN
GPRGNN
10
25
GPRCNN
Perturbed Edges (global) [%6
(i) Learning setting. the previously studied trans- ductive learning settings (see T))le clean valida- tion and test nodes are known during training. Thus, perfect robusiness can be achieved by memorizing the training graph. This can lead false impression of robustness. Indeed, we find that the gains of the adversarial training approach from Xu et al. 2 largely stem from exploiting this flaw. Motivated by this finding, we revisit adversarial training for node classification under structure perturbations in fully inductive setting (i.e., validation/test nodes are excluded during training). Thus, our results do not suffer from the same evaluation pitfall and pertain to more challenging and realistic scenario.
Robust diffusion (GPRGNN) vs. GCN on (inductive) Cora-MI. We report ad- versarial training and standard training.
Figure 1:
Equal contribution.
Project page: https:///ww.c.. htt............d////aaaaaaraaaaa
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(it) GNN architectures. The studied GNNs like GCN A or APPNP [S] all seem to share the same fate as they have a limited ability to adjust their message passing to counteract adversarial perturbations. Instead, we propose to use flexible message-passing schemes based on learnable diffuusio. The main motivation behind this choice is the ability to approximate any spectral graph filter. Thus, adversarial training may choose the most robust filter that achieves a competitive training loss. Thereby, we significantly improve robustness compared to previous work, while yielding an interpretable message- passing scheme, and making the evaluation bias in the transductive setting (i) apparent.
More realistic perturbations. Inspecting robust diffusion indicates that previously studied perturbation sets 2 B are overly permissive and unrealistic. Prior work only constrained the global (graph-level) number of inserted and removed edges, despite studying node classification, where predictions are inherently local (node-level). As a result, commonly, an adversary has been allowed to add or remove a number of edges that exceeds the average node degree by 100 times or more, providing ample leeway for complete change of many node neighborhoods through rewiring. E.g.. on Cora-MIL 5% edge-changes correspond to 798 changes, but the average degree is 5.68. To prevent such degenerate perturbations [6]. we propose Locally constrained Randomized Block Coordinate Descent (LR-BCD), the first attack that, while targeting multiple nodes at once, is able to constrain both local perturbations per node and global ones. Even though local constraints are well-studied for attacks targeting single node 77.. surprisingly, there was no attack incorporating these for jointly attacking a set of nodes at once. Thus, LRBBCD fills an important gap in the literature, while being efficient and effective.
Addressing the aforementioned points, we substantially boost empirical and certifiable adversarial robustness up to the level of taate-of-the-art defenses for GNNs. For example, in Figure 1 we show a 4-fold increased robustness over standard training (measured in decline in accuracy after an attack).
We show theoretically and empirically that in the transductive learning setting previously studied for adversarial training, one can trivially achieve perfect robustness. We show that the full inductive setting does not have this limitation and, consequently, revisit adversarial training in this setting (see Section 2 (2) By leveraging more flexible GNN architectures based on learnable diffusion, we significantly improve upon the robustness under adversarial training (see Section B). (3) We implement more realistic adversaries for structure perturbations with a novel attack that constrains perturbations globally and locally for each node in the graph (see Section 4.
Contributions. (1)
2 Learning Settings: Transductive vs. Inductive Adversarial Training
we discuss the transductive learning setting and its shortcomings in contrast to inductive learning in the context of robust generalization. Following previous work, we focus on node classification and assume we are given an undirected training graph G = (X, A) consisting of n nodes of which m are labeled. By A E f0. 1|nxn we denote the adjacency matrix, by X E Rnxd the feature matrix, and by y E (I,...,C) C} the label of a node i, summarized for all nodes in the vector y.
We first give background on adversarial training and self-training. Then, in Section 2.1
Adversarial Training, Adversarial training optimizes the parameters of a GNN So on an adversarially perturbed input graph with the goal to increase robustness against test-time (evasion) attacks (i.e., attacks against the test graph after training). The objective during training is
371
arg min max GEB(S)
Σ ((fo()).. v4)
where f0()); is the GNN-prediction for node based on the perturbed graph G. is a chosen loss function, and BCG) is the set of allowed perturbed graphs given the clean graph G. As in previous work, we assume that an adversary maliciously changes the graph structure by inserting or deleting edges. Then, BGG) can be defined by restricting the total number of malicious edge changes in the graph to E Nz0 (called a global constraint) and/or restricting the total number of edge changes
in each neighborhood of node i A E Noo (called local constraints, see Section 4). Solving Equation (T) is difficult in practice. Thus, we approximate it with alternating first-order optimization, i.e., we approximately solve Equation (I) by training fa not on the clean graph G, but a perturbed one 9 that is newly crafted in each iteration through attacking the current model (see Algorithm B.2).
Self-training is an established supi-supe learning strategy g that leverages unlabeled nodes via pscudo-labeling and is applied by previous works on adversarial training for GNNs 2 3). For this, first

---

model for is trained regularly using the m labeled nodes, minimizing Σ;= new (final) model fo randomly initialized and trained on all nodes, using the known labels for the training nodes and pseudo-labels generated by for for the unlabeled nodes (see Algorithm B.3 Thus, including self-training Equation [T] changes to
(( (.). Thereafter,
arg min max GEB(C)
(.l()))
Σ (o) im++1
(2)
2.1 Transductive Setting
Transductive node classification is common and well-studied graph learning problem p 4 It aims to complete the node labeling of the given and partially labeled graph test time is accurately label the already known n m unlabeled nodes, i... to achieve minimal
G. More formally, the goal at
n
Co/1(fo) = Σ 1=m++
(fo())))) v.
This is in contrast to an inductive setting, where at test time a new (extended) graph G' (with labels y') is sampled conditioned on the training graph G. Then, the goal is to optimally classify the newly sam- pled nodes I in expectation over possible (g', -pairs, i.c. to minimize E E{Eeez lo/1 (fo()') s/)] That is, in transductive learning the nodes, but in an inductive setting, new unseen test nodes are sampled. For additional details on the inductive setting, Appendix [A]
unlabeled nodes known during training considered test
Many common graph benchmark datasets such as Cora, CiteSeer, or Pubmed [10 are designed for transductive learning. Naturally. this setting has been adopted as a starting point for many works on robust graph learning 77 2 [2]. including all of the adversarial training literature (see Section ( Here, the latter is concerned with defending against test-time (evasion) attacks in transductive node classification, i.c., it is assumed that after training an adversary can select a maliciously changed graph out the set of permissible perturbations B(G), with the goal to maximize misclassification:
Lado
max (G) i=m+1
Σ (o))
Since the adversary changes the graph at test time (i.e., the changes are not known during training), this, strictly speaking, corresponds adversarial. Now, the goal of adversarial training is to find parameters minimizing Ladv (So), corresponding to the optimal (robust) classifier under attack (1]
inductive setting [9]. where the only change considered
2.1.1 Theoretical Limitations
Defending against test-time (cvasion) attacks in a transductive setting comes with conceptual limita- tions. In the case of graph learning, the test nodes already known training time and the only change is adversarial. Hence, we can design a defense algorithm .A achieving perfect robustness without trading off accuracy through memorizing the (clean) training graph.
Formally, A takes a GNN So as input and returns a slightly modified model fo corresponding to So composed with a preprocessing routine (memory) that, during inference, replaces the perturbed graph & = (X,A) A) E B(g) with the clean graph = (X, A) known from training, resulting in fo( = (g). In other words, fe ignores every change to the graph including those the adversary. Trivially, this results in the same (clean) misclassification rate (fe) Lo/1 (fa) because fo and fo have the same predictions on the clean graph, but also perfect robustness, in the sense of Co/1 Lade(fo). the predictions are not influenced by the adversary. Thus, we can state:
Proposition 1. For transductive node classification, fo A(fo) is a perfectly robust version of an arbitrary GNN fo. in the sense of (Fo)(fo) = Lo/1(fo) Ladi (Jo).
However, what is probably most interesting about is that we can use it to construct an optimal solution to the otherwise difficult saddle-point problem ming Ladv(fo) ming maxgen(g) foy1 arising in adversarial training. Formally, we state (proof see Appendix C.I
3

---

Proposition 2. Assuming we solve the standard learning problem 6* = arg ming Loz1 (fo) and that E B(G). Then, fo- A(fo-) ) is an optimal solution to the saddle-point problem arising in (transductive) udversarial training, in the sense of Ladu(fo-) ming Ladu(Jo) S ming Lado (Jo)-
In other words, train time, from GNN fo- minimizing the clean error, we can construct perfectly robust classifier fo- minimizing the maximal misclassification rate under attack solely from memorizing the data available during training.
Note that in fully inductive setting due the expectation in the losses, neither Proposition nor Proposition]] 2arioon@@hoi hold, i.e. an optimal solution cannot be found through memorization (see Appendix Thus, inductive node classification does not suffer from the same theoretical limitations.
2.1.2 Empirical Limitations
Even though prior work did not achieve perfect robustness, we show below that the reported gains from adversarial training by Xu et al. (2) actually mostly stem from self-training, i.e., the "leakage" of information on the clean test nodes through labull--a Then, we close the gap between theory and practice and show that perfect robustness, while preserving clean accuracy, can be achieved empirically through adversarial training- effectively solving the learning setting in prior work.
Self-training is the (main) cause for robustness in transductive learning. In Figure 2 we compare the (robust) test accuracies of a GCN using different training schemes: (i) normal training, (ii) adversarial train- ing, (iii self-training, and (iv) pair- ing self- and adversarial training. In- deed, Figure Figure[]showe shows that the main ro- bustness gain actually stems from self- training and not adversarial training. Surprisingly. adversarial training with- out self- leff-training can even hurt robust- ness, while adversarial training paired with self-training only slightly in- creases robust test accuracy compared to using self-training alone. These re- sults are independent of the used ar- chitecture, dataset, or attack strength, as we show in Appendix C.2.2
Test Accuracy [9]]
Text Accuracy [%]]
90
20
70 as
B
Normal Adv. Trn.
8
GPRGNN
SelFTTm.
15
1
W! colf adv. tru.
GCN
Self. & Adv
welfs idv
1 Perturbed Edges [%)]
10
20
1
10 25 50 100
Perturbed Edges [%)
Figure 2: Robust test-
Figure 3: Adv. trained
accuracy of a GCN under different training schemes on Cora. Adversarial training uses PGD-attack (10% pert. edges). Most robustness gains are due to self-training.
GPRGNN following Xu et al. 2 achieves perfect robustness on Cora. GCN baseline uses the same adv. training sctup (training budget: 100% of edges).
Adversarial training causes overfitting. For transductive node classification, it is also empirically possible to achieve perfect robustness while maintaining clean test accuracy by combining self- with adversarial training and using more flexible, learnable diffusion model (GPRGNN) as introduced in Section In Figure 3 we show the test accuracy under severe perturbations for an adversarially trained GCN 22 and GPRGNN, both trained using a very strong adversary and pseudo-labels derived from self-training. The performance of the adversarially trained GCN reduces rapidly, while GPRGNN achieves (almost constant) perfect robustness. Since the pseudo-labels are derived from the clean graph, the clean graph leaked in the training process. This allows GPRGNN to mimic the behavior of an MLP and overfit to the pseudo-labels, i.e., memorize the (node-feature, has seen during training. In other words, it finds trivial solution to this learning setting, making its limitations evident similar to the theoretic solution discussed in Section 2.1.T In Appendix C.2. we show that we achieve perfect robustness not only if using the PGD attack as Xu et al. [2) but also for many different attacks.
(reudo-label)-pare
it
These findings question how to interpret the reported robustness gains of previous work, which all evaluate transductively and usually use self- training. Conceptually, being robust against test-time (evasion) attacks is most relevant if there can be a natural change the existing data. Only then is realistic to assume an adversary causing some of the change to be malicious and against which we want to be robust without losing our ability to generalize to new data. Therefore, in Section we revisit adversarial training in an inductive setting, avoiding the same evaluation pitfalls. Indeed, we find that using robust diffusion (see Section 3. we are not only capable of solving transductive robustness, but learn robustly generalize to unseen nodes far better than previously studied models.

---

3 Robust Diffusion: Combining Graph Diffusion with Adversarial Training
We propose to use learnable graph diffusion models able to approximate any graph filter in conjunction with adversarial training to obtain a robust diffusion.. The key motivation is to use more flexible GNN architectures for adversarial training than previous studies. We not only show that robust diffusion significantly outperforms other models used in previous work (see Section 55), but it also allows for increased interpetability as we can gain insights into the characteristics of such robustness-enhancing models from different perspectives.
In fixed message passing schemes of popular GNNs like GCN or APPNP, each layer can be interpreted as the graph convolution g & H V V H between fixed graph filter g(A) and the transformed node attributes are H (x using MLP fa. This convolution is defined w.r.t. the (diagonalized) eigenvalues A E RR and eigenvectors V E R of the Laplacian L' = D 1/2 D 1/2 with diagonal degree matrix D. Following the common reparametrization, instead of L', we the "normalized adjacency" L D A/AAA 1/2 or, depending the specific model, i = D 1/2 AD 1/2 where Á A+I I with node degrees D. Then, many spatial GNNs relate the K-order polynomial approximation (g(A)V H Σk L И with the K + diffusion coefficients y E R Many GNNs stack multiple convolutions and add point-wise non- non-linearities.
Crucially, GCN's or APPNP's graph filter g(A) is fixed (up to scaling). Specifically, we obtain an MLP with [1, 0, ...................... 0j. If using L, a GCN corresponds to Y [0, -0,10, OJ. and in APPNP Y are the Personalized PageRank coefficients.
Robust diffusion. In contrast to prior work on ro- do not solely parametrization of (A)). Instead, we learn the graph fil- ter, which corresponds to training diffusion coefficients y. This allows the model to adapt the graph diffusion to the adversarial perturbations seen during training, i.e., we learn a robust diffusion.
bust graph learning,
static
For this, the used architectures consist of two steps: (1) using an MLP to preprocess the node features, Le., H fo(X) where f are learnable parame- ters; and then, (2) using a learnable diffusion com- puting the logits. For the learnable diffusion, ploy GPRGNN [3] that uses the previously intro- duced monomial basis: softmax EK= TAk L Ht). Ad- ditionally, we study Chebyshev polynomials (see Cheb-
(a) Norm. adj. -L
(b) T (no adv. tr.)
em-
Netll [14) that are of interest due to their benefi- cial theoretical properties. ChebNetll can be expressed as softmax Σk= Ykk T. (L) with extra weight- ing factor w = 2/K-1 -1 Σラ= Te((z)). The Chebyshev L, and (L) = 2LT (L) (L). The Chebyshev
(c) T (wlo local con.)
(d) T (w/ local con.)
Figure 4: Robust diffusion (GPRGNN) on Karate Club where the edge (u. v) width en- codes the diffusion coefficient T.. learned during training. (a) we show the normal- ized adjacency matrix. The other plots show the robust diffusion transition matrix: (b) w/o adversarial training. (c) w/ adversarial training but w/o local constraints, and (d) w/ adversarial training and w/ local constraints.
basis given via To [)) = I, (L)
nodes zı cos m)) = 0,......... K for wk re- duce the so-called Runge phenomenon [14. Note, the resulting Chebyshev polynomial can be expressed in monomial basis (up to L vs. L) via expanding the (L) terms and collecting the powers L*.
Interpretability. While chaining multiple layers of a "fixed" convolution scheme (e.g. GCN) might allow for similar flexibility, with our choice of robust diffusion, we can gain insights about the learned robust representation from the (i) polynomial, (ii) spectral, and (iii) spatial perspective.
(i) Polynomial perspective. The coefficients 7 determine the importance of the respective k-hop neighborhood for the learned representations. To visualize Yk. we can always consider To to be positive, which is equivalent to flipping the sign of the processed features H. Additionally, we normalize the coefficients s.t. Ehi = since H also influences the scale. In Figure we give an example for the polynomial perspective (details are discussed in Section 5).
5

---

(ii) Spectral perspective. We solve for go (A) in the polynomial approximation V (A) H Ek ko= L 1 H to obtain a possible graph filter (A V E Yk ? VV. Following Balcilar K
al. 15], we study the spectral characteristics w.r.t. I- D-DDVA 122 Then. the diagonal entries of go (A) correspond to the (relative) magnitude of how signals of frequency À are present in the filtered signal. Vice versa, low value corresponds to suppression of this frequency. Recall, low frequencies correspond to the small eigenvalues and high to the large eigenvalues. In Figure 7 we show how adversarial training and the permissible perturbations affect the spectra of the learned graph filters.
(iii) Spatial perspective. Robust diffusion (monomial basis) can be summarized as softmax (TH) where T = Σ Thk L is the total diffusion matrix. The coefficient The indicates the diffusion strength between node u and node v. For example, we visualize the total diffusion matrix T in Figure on Karate Club [16] with different training strategies. Depending on the learning signal we give, GPRGNN is able to adjust its diffusion.
4 LR-BCD: Adversarial Attack with Local Constraints
Motivation for local constraints. The just-discussed interpretability of robust diffusion provides empirical evidence for the importance of local constraints. Specifically, from Figure 44 we see that GPRGNN adversarially trained without local constraints learns diffusion that almost ignores the graph structure. While this model is certainly very robust w.r.t. structure perturbations, it is not a very useful GNN since it cannot leverage the structure information anymore. In contrast, we show in Figure 4d that GPRGNN trained adversarially with local constraints results in a robust model that can still incorporate the structure information.
The local predictions in node classification yield an alternative motivation. In the absence of local constraints, an adversary typically has the power to rewire the entire neighborhood of many nodes. When attacking GNNs, we empirically observe that ma- jority of successfully attacked nodes are perturbed beyond their degree even for moderate global attack budgets (see Figure 5). That such perturbations are not reasonable is evident in the fact that studies on local attacks 7 [7). where the adversary targets a sin- gle node's ' prediction, do not consider perturbations (far) beyond the node degree. However, 5% attack budget on Cora-ML. allows changing 798 edges while the majority of nodes have degree less than three.
Nh. wir. edge
50
20
10
Node Degnne
Nodi Degres
Figure 5: Number of successfully attacked nodes by node degree and number of con- nected adversarial edges. We attack self- trained GCN with PR-BCD and global bud- gets 10% (left) and 25% (right) on Cora-ML and aggregate the results over three different data splits. We observe that a notable amount of nodes is perturbed beyond their degree.
Traditionally, adversarial changes are judged by no- ticeability [8] since unnoticeable changes do not alter the semantics. However, for graphs, manual inspection its content is often not feasible, and the concept of (un-) (un))noticeability is unclear. However, using generative graph models Gosch et al. (6] revealed that perturbations beyond the node degree most often do alter the semantics. Perturbations that alter semantics can pose a problem for adversarial training. Similar observations have been done in graph contrastive learning where perturbations that do not preserve graph semantic preservation have a direct effect on the achievable error bounds [19
Locally constrained Randomized Block Coordinate Descent (LR-BCD). We next introduce our LR-BCD attack; the first attack targeting multiple nodes at once while maintaining a local constraint for each node next to a global one. For this, we extend the so-called PR-BCD attack framework.
Projected Randomized Block Coordinate Descent (PR-BCD) 17 is a gradient-basst based attack framework applicable to a wide range of models. Its goals is to generate a perturbation matrix P E {0, 1 that is applied to the original adjacency matrix A to construct perturbed matrix À A + (I (I-2A) 2A) O P. where I is an all-one matrix and C the element- deiment-wise product. For undirected graphs, only the upper- triangular parts of all matrices are considered. To construct P in an efficient manner, PR-BCD relaxes P during the attack from (0, [ to [o, 1|mxx and employs an iterative process for T iterations. It consists of three repeating steps. (1) A random block of size b is sampled. That is, only b (non-contiguous) elements the perturbation matrix P,-1 are considered and all other elements set to zero. Thus, Pt-1 is sparse. (2) A gradient update w.r.t. the loss to compute relaxed perturbations

---

St is performed, i.e., St f P. where P are the previous perturbations, a,-1 is the learning rate, and VP.,,((P:-) are the perturbation gradients through the GNN. Finally, and most crucially (3) projection (g) ensures that the perturbations are permissible given the set of allowed perturbations Bg)), i.e. P. = (B(g) Now, the process starts again with (1), but all zero-elements in the block b (or at least 1/2 of the lowest-value block elements) are resampled. After T iterations, the perturbations Pr are discretized from [0, 1|mxm {0, ] to obtain the discrete A. Specifically, Pr is discretized via sampling, where the elements in Pr are used define Bernoulli distributions.
Global projection. As mentioned above, the projection ( of PR-BCD is the crucial step that accounts for the attack budget. Geisler et al. [77 develop an efficient projection for an adversary
implementing a global perturbation constraint, i.c., for (g)) = {Á E {0, 1|nX" || - Allo I A} with A Nzo- This is achieved by formulating the projection the following optimization problem
[a(S) = arg minp |P PP-a -SS
subject to
Eup 10
(5)
|| and the sum aggregating all elements of the matrix. (1) can be solved with the bisection method [17]. However, the projection II does not support limiting the number of perturbations per node, i.e., Σソ= Pio S ! where (1) E No is the vector of local budgets for each node. Indeed, extending the optimization problem above to include local constraints leads to the notoriously hard problem of Euclidean projection to polyhedra (20).
with Frobenius norm
A locally constrained global projection (LR-BCD) With the goal of an efficient attack including local constraints, we have to develop an alternative and scaleable projection strategy for B(g) {A e
{o, 1)mxn|| I - Allo A EA Asy) S A vi E [n]]}. Our novel projection P
T = (S) @ C* chooses the largest entries from the perturbation matrix S E R using C E [0, 1j and clipping operator [o.1) (s) E [0, 1), s.t. we obey global and local constraints. The optimal choices O can be calculated by solving a relaxed multi-dimeensinal knapsack problem:
C = arg max
Σ
S S C 1
subject to
Σ fg Pla <
C
Σ, P
1
Vi [m]
CE 1|
where p' II captures their value. Σx, Pi,, aggregate all elements in the matrix. The local constraint E, Pi S
[o. (S) O i.e., I]. represents the weights of the individual choices, while S
A constrain the perturbations in each neighborhood, with node-specific budgets A Even though this optimization problem has no closed-form solution, it can be readily approximated with greedy approaches [21]. The key idea is to iterate the non-zero entries in S in descending order and construct the resulting C' (or directly P) as follows: For each perturbation (u, v) related to Swe- check if the global A or local budgets A
(i.e., Pu.e = (o (Sww)) Otherwise, C = min A, A! ()). The final discretization is given by C" corresponding the solution of Equation (6) for ST, but changing the weight of each choice to 1 (i.e.. P' C), guaranteeing a binary solution due to the budgets being integer. We give the pseudo-code and more details in Appendix [3.4]
(1) and A!") are not yet exhausted. Then, C
Our projection yields sparse solutions as it greedily selects the largest entries in S until the budget is exhausted. Moreover, it is efficient. Its time complexity is O(b (o))))()) due to the sorting of the up to non-zero entries in the sparse matrix S. Its space complexity is (b). assuming we choose the block size b > A well as b > Thus, LR-BCD has the same asymptotic complexities as the purely global projection by Geisler et al. I7 (which we will from now on denote as PR-BCD).
Summary. We will now summarize our LR-BCD along the four dimensions proposed by Biggio and Roli [22]. (l) Attacker's goal: Although our focus is to increase the misclassification for the target nodes in node classification, we can apply LR-BCD to different node- and graph-level tasks depending on the loss choice. (2) Attacker's ''s knowledge: We assume perfect knowledge about the model and dataset, which is reasonable for adversarial training. (3) Attacker's capability: We propose
7

---

Table 1: Comparison on Citeseer of regularly trained models, the state-of-the-an SoftMedian GDC defense, and adversarially trained models (train 20%). The first line shows the robust accuracy [%] of a standard GCN and all other numbers represent the difference in robust accuracy achieved by various models in percentage points from this standard GCN. The best model is highlighted in bold and grey background marks our robust diffusion.
Model
trm.
eval,
Clean
LR-BCD
c-0.1
PR-BCD
LR-BCD
co0.25
PR-BCD
Certifiable accuracy / spurse smoothing addd.
Clean
GCN
72.0 2.
54.7 2.
51.7 2.8
44
=8
38.3 # 11.5
1.7
488 =
GAT
X
366117
34
1.5
-199
13
-14.
-1.7 1.7
-18 - 1,5
APPNP
+0.2 + 1.1
+.
+1. 1.4
120
+
+8.9 9.1
+31.2 1112:..4
+31. 6 6.4
GPRGNN
4.3
+1
43
499
1.
+17.9
+424 144
+1.3
=37
ChebNetll
2.2
+5.
+5
424.6
+556++12
=540=09
SoftMedian
+.
222
1.
24
+25.2 10.5
+60.3
+57.5
GCN
LR-BCD
122112
16
1.
+109111
13.1
.3.
+10.7
1 146
+13.1 3.1
PR-BCD
-00++19
+69+09
+,
+3
+5.8 2.4
+42++144 14.6
+10.1
55
+11,-44
GAT
PR-BCD
LR-BCD
-1.1
10
+8
+.
133
+..0
12.
-8.115.1
+218
1.
L48
110.1
-200
13.7
23.00
+14
-12
+10
+28
APPNP
LR-BCD
PR-BCD
02122
+.2122
1..1
-9
+..5
+21.7
+19.3
+9
1.2
GPRENN
LR-BCD
PR-BCD
-06-366
+157
+15. 3.6
+15.9 = 4.2
+136
+248
+23.2+43
+26.3 0433-50
+:3.9+443
+34.0
+32.9
+ 11.8
11.5
+69.0
+67.4
1.5
+689
+650
2.3
ChehNettf
LR-BCD
PR-BCD
+37 14
1.7
+1.. 16
+2
+11.5
+14.3
L1
1.2
16
116
+198 2.3
+160 19
+30.7
+31.5
13.2
12.7
+65.4
+62.3
4 2.6
19
+62.9 3.7
+598
- 2.5
to use threat model that constrains the number of edge perturbations globally well as locally for each node. (4) Attacker's 's strategy: LR-BCD extends PR-Bo FR-BCD by a projection incorporating local constraints. Most notably, we relax the unweighted graph during the attack to continuous values and leverage randomization for an efficient attack while optimizing over all possible n² edges.
5 Empirical Results
Inductive learning. All results in this section follow a fully inductive semi-supervised setting. That is, the training graph G does not include validation and test nodes. For evaluation, we then successively add the respective evaluation set. This way, we avoid the evaluation flaw of prior work since the model cannot achieve robustness via "memorizing" the predictions on the clean graph. We obtain inductive splits randomly, except for OGB arXiv [II], which comes with split. In addition to the commonly sampled 20 nodes per class for both (labeled) training and validation, we sample a stratified test set consisting of 10% of all nodes. The remaining nodes are used as (unlabeled) training nodes.
Setup. We study the citation networks Cora, Cora-ML, CiteSeer 23 Pubmed 24], and OGB arXiv [1I] Furthermore, WikiCS (25 which has significantly more heterogeneous neighborhoods as well the heterophilic dataset Squirrel (27) and (contextual) Stochastic Block Models (SBMs) (28 with heterophilic parametrization (see Appendix B.I. As models we choose GPRGNN, ChebNetll, GCN, APPNP, and GAT [29]. Further, we compare to the state-of-the-art evasion defenses Soft Median GDC [17 in the main part and GRAND (30] in Table D.6 We apply adversarial training (see Section and Appendix B using both PR-BCD that only constraints perturbations globally and our LR-BCD that also allows for local constraints. Moreover,
adversarial training in conjunction with self-training. Due to the inductive split, this does not bias results. We use the tanh margin attack loss of (17 and do not generate adversarial examples for the first 10 epochs (warm-up). We evaluate robust generalization on the test set using L/PR-BCD, which corresponds to adaptive attacks. Adaptive attacks are the gold standard in evaluating empirical robustness because they craft model-specific perturbations [31 3. We use to parametrize the global budget A- = [E Enea d relative to the degree d, for the set of targeted nodes A. We find that A = [d. a reasonable local budget for
all datasets but arxiv where we use A [d. We report averaged results with the standard error of the mean over three random splits. We use GTX 1080Ti (11 Gb) GPUs for all experiments but arXiv, for which we use V100 (40 GB). For details see Appendix B We discuss limitations in Appendix F and provide code at ftttttss//wwww cs. cit. tum. de/ daml adversarial- traalltgtrainnngn
Certifiable robustness. We use the model-agnostic randomized/sparse smoothing certificate of Bojchevski et al. [32 to also quantify certifiable robustness. Sparse smoothing creates a randomized
ensemble given a base model fo s.t. the majority prediction of the ensemble comes with guarantees. For the randomization, we follow Bojchevski al. [32] and uniformly drop edges with p- = 0.6 as well as add edges with p+ 0.01. Sparse smoothing then determines if a node-level prediction is
8

---

certified (does not change) for the desired deletion radius r- or addition radius r+- The guarantee holds in a probabilistic sense with significance level a. We report the "certified accuracy" ( r+ that is the average of correct and certifiable predictions over all nodes. We choose a = 5% and obtain 100,000 random samples. For simplicity, we report in the main part the certified accuracies y(r_ 0,r+ = 0), 7(5, 0). and (0, 3). See Appendix D.4 for more details and results.
Finding I: Adversarial training an effee- tive defense against structure perturbations. This is apparent from the results in Table [ where we compare the empirical and certifi- able robustness between the aforementioned models on Citeseer. Our ad advesarrially trained robust diffusion models GPRGNN and Cheb- Netll outperform the other baselines both in empirical and certifiable robustness. This in- cludes the state-of-the-art defense Soft Me- dian, which we outperform with a comfort- able margin. Thus, close the gap in terms of the efficacy of adversarial training in the image domain vs. structure perturbations. No-
Table 2: Robust accuracy [%] on further datasets. Attack types match for training (c = 0.2) and evalua- tion. Grey shading highlights our robust diffusion.
Model
Attack
Clean
e=0.1
e50.25
GCN
LR-BCD
PR-BCD
82.
+ 1.9
1.9
57.4 2.3
38.0 = 2:3
LR-BCD
83.5 2.6
648+223
570
1.5
GPRGNN
PR-BCD
LR-BCD
1.2
61. 1.8
768
466
74.1
1.4
7
69.0
GCN
PR-BCD
L.BECD
79.9
0.9
59.1 0.4
470-
M4. -07
GPRGNN
X
PR-BCD
LR-BCD
LR-BCD
81X
$1.8
1..4 0.9
& 1.0
1 1.00
69:4102
64.3
72.6111
1 0.6
700
$2.0
617-000
PR-BCD
79.9 1.3
71.9
1.0
tably, the increased robustness does not imply lower clean accuracy. For example, our LR- BCD adversarially trained GPRGNN achieves 1.7 percentage points higher clean accuracy than a GCN, while with an adaptive LR-BCD attack and 25% perturbed edges, we out- perform a GCN by 24.8 percentage points. This amounts to a clean accuracy of 73.7%
Polmmed
GCN
LR-BCD
PR-BCD
7..4+0.
5.0+0.5
393-12
528=14
GPRENN
X
PR-BCD
LI-EC
78.8
7XX
# 1.0
6LT
57.0 1.2
427=14
$40
LR-BCD
80.5
75.
1.0
74.7
PR-BCD
80.4
73.
68.8
SBM (heterou
GCN
LR-BCD
6.5
45.1
PR-BCD
62.0
49.2
47.1
GPRGNN
X
PR-BCD
LI-BCD
85.9
86.3
1.9
67.3
1.9
3930
55.6
4.1
LR-
85.5
721
1.7
670=
PR-BCD
09.0 4
Squired
GCN
PRABCD
LK-BCD
4..
41.9
1211 0.3
20
and perturbed accuracy of 70.1%. We show the empirical robustness gains of adversarial training on on the other datasets in Table 2 compared to a GCN and regularly trained GPRGNN. We show that robust diffusion con- sistently and substantially improves the robust- ness - not only on homophilic datasets but also under heterophily (SBM, Squirrel). We present more results and an ablation study in Appendix D
LR-BCD
40.0.200.6
29.8
+ 4.8
2.1
GPRGNN
PR-ECD
40.4+0.9
20.6
20.6
0.6
1.4
LR-BCD
17.8
341
333
PR-BCD
38.4 1.6
42
289-9.1
GCN
LR-ECD
154
WILIS
1.5
302
LR-BCD
1281111
328
197
GPRGNN
LR-BCD
PR-BCD
72.8 4 0.4
13.3
52.7 + L.0
61.1222
2.2
62.8
500 = 1.2
2.1
PR-BCD
73.2.10.2
60.0 1.9
54.1
141108
Finding II: Choose the set of permissible perturbations wisely! As argued already in Section 4
the right set of admissible permutations can guide the learned robust diffusion. Importantly, the set of
admissible perturbations is application specific. That is, depending on the choice, the resulting model might have different robustness characteristics w.r.t. different threat models. For example, in Table [ a LR-BCD adversarially trained GPRGNN is more robust to LR-BCD attacks than to model trained with PR-BCD, and vice versa. Importantly, the learned message passing is very different as the spectral analysis (Figure 7 reveals striking pattern. Adversarial training with PR- PR-BCD flipped the behavior from low-pass to high-pass if compared a regularly trained model. However, adversarial training with LR-BCD seems to preserve the general characteristic while using a larger fraction of the spectrum to enhance robustness. Note that such a filter (less integral Lipschitz) opposes the theoretical stability result of Gama et al. K3 Moreover, the polynomial coefficients (Figure (6) resulting from adversarial training without local constraints (Figure (6)) are very similar to coefficients that Chien et al. [13 associated with a non-informative graph structure. See Appendix D.2 for other datasets.
Finding III: Adversarial training with local constraints is efficient and scalable. We show in Figure 8 the results of an adversarially trained GPRGNN using LR-BCD with different relative budgets c. Adversarial training on arXiv requires less than 20 GB of RAM and an epoch takes approx. 10 seconds. In contrast, the globally constrained adversarial training of Xu et al. 2 would require multiple terabytes of RAM due to n² possible edge perturbations [17. We not only show that robust diffusion with LR-BCD is scalable, but also that it improves the robustness on arviv. That is, twice as many edge perturbations are required to push the accuracy below that of an MLP, comparing 10% to standard training.
9

---

Filter magn
1.0
regular
Text Accuraoy [36
70
Coeff
0.00
1h.
0.5
adv LR-BCD
tm.
6G
60
5%
0%
10%
10
10
adv PR-BCD
Index
Index A
Index
0
2
Eigenvalue A
111
Parturbed Edges (global) [S]]
(a) Regul. (b) w/ loc. (c) w/o I.
Figure 7: Respective spectral fil- ters of Figure 6 Low filter mag- nitude denotes suppression of the respective frequencies asso- ciated with eigenvalues X.
Figure 8: Acc. on arXiv un-
Figure 6: Learned coefficients Y for GPRGNN on Citeseer. We use
der adv. attack for GPRGNN with different training pert. strengths using LR-BCD.
e 20% in (b) and (c) for adv. trn.
6 Related Work
Table 3: Works on adversarial training for GNNs.
We next relate to prior work and refer to
Publication
Learning setting
Type of attack evasion (attribute) evasion (attribute)
Deng al.
Transductive
Appendix for more detail: (1) Learn-
Feng al.
35
Transductive
ing setting. Conceptual problems by re- membering training data are not unique
Jin and Zhang
33
Transductive
evasion (structure + attribute) evasion (structure)
Xu et al.
2
Transductive
to adversarial training and have been mentioned in Zheng al. 40 for graph
Xu et al. ())
Transducitve
evasion (structure)
Chen al.
Transductive
evasion (structure)
ei al.
(3
Transductive
evasion (structure attribute) evasion poisoning (structure)
injection attacks and by Scholten et al.
Guo et al.
Transductive
41 for certification. (2) Adversarial training for GNNs under structure perturbations have been studied in [2] 3 36439]. However, all prior works study transductive setting (see Table 3) hav- ing serious shortcomings for evasion attacks (see Section 2 Note that only Xu al. 2 study adversarial training for (global) structure perturbations in its literal sense, i.e., directly work on Equation (I. Further, we are the first study adversarial training in the inductive setting. (3) Lo- cal constraints have been studied for local attacks [7 42 12), i.c., if attacking single node's s prediction. They are also well-established for robustness certificates 43155 However, surprisingly, there is no global attack, i.e., attack targeting large set of node predictions at once, that incorporates local constraints. This even led prior work trying to naively and expensively apply local attacks for each node sequentially to generate locally constrained global perturbations [38] With LR-BCD, we finally close this gap. (4) GNN Architectures. The robust GNN literature strongly focuses on GCN and variants 7 17 49 38 50
8. GAT is perhaps the most flexible studied model [40] While robustness of GAT, in our experiments, an adversarial trained GAT is not more robust than GCN 4. A novel aspect of our work is that spectral filters, in the form of polynomials [14. [3), can learn significantly more robust representations, beating a state-of-the-ar graph defense. They also reveal insights about the learned robust representation.
adversarial training improves
7 Broader impact
We are convinced that the benefits outweigh the risks. Having the right tools hand can further the reliability of graph machine learning. Due to the more fine-grained perturbation models, researchers and practitioners and improve upon defending adversarial attacks. We firmly believe that transparent research into the vulnerabilities of models allows researchers and practitioners to understand potential problems and build strong defenses as also showcased in our paper. Moreover, due to the studied whitebox setup, our approaches are not directly applicable for real-world malicious actors.
8 Discussion and Conclusion
We show that the transductive learning setting in prior work on adversarial training for GNNs has fundamental limitations leading to a biased evaluation and trivial solution through memorization. Thus, we revisit adversarial training research on evasion attacks in the graph domain, in general, should focus on the inductive setting to avoid the conceptual limitations inherent to combining transductive learning with test-time attacks. Moreover, we employ more flexible GNNs than before that achieve substantial robustness gains through adversarial training and are interpretable. For more realistic perturbations, we develop LR-BCD the first global attack able to maintain local constraints.
fully inductive setting. Furthermore, we argue that future
10

---

Acknowledgments and Disclosure of Funding
This research was supported by the Helmholtz Association under the joint research school "Munich School for Data Science MUDS". Furthermore, this paper has been supported by the DAAD programme Konrad Zuse Schools of Excellence in Artificial Intelligence, sponsored by the German Federal Ministry of Education and Research, and the German Research Foundation, grant GU 1409/4-1.
References
[1] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
[2] Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Y Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. In IJCAI, 2019.
[3] Kaidi Xu, Sijia Liu, Pin-Yu Chen, Mengshu Sun, Caiwen Ding, Bhavya Kailkhura, and Xue Lin. Towards an efficient and general framework of robust training for graph neural networks. In ICASSP, 2020.
[4] Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[5] Johannes Gasteiger, Aleksandar Bojehevski, and Stephan Günnemann. Combining neural networks with personalized pagerank for classification on graphs. In ICLR, 2019.
[6] Lukas Gosch, Daniel Sturm, Simon Geisler, and Stephan Günnemann. Revisiting robustness in graph machine learning. In ICLR, 2023.
[7] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In KDD, 2018.
[8] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. AAAI, 2018
[9] Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien. Semi-Supervised Learning (Adap- tive Computation and Machine Learning). 2006.
[10] Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi suni--upereised learning with graph embeddings. In ICML, 2016.
[11] Weihua Hu, Matthias Fey, Marinka Zitmik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurlPS. 2020.
[12] Stephan Günnemann. Graph neural networks: Adversarial robustness. In Graph Neural Networks: Foundations, Frontiers, and Applications. 2022.
[13] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In ICLR, 2021.
[14] Mingguo He, Zhewei Wei, and Ji-Rong Wen. Convolutional neural networks on graphs with chebyshev approximation, revisited. In NeurlPS, 2022.
[15] Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks spectral perspective. In ICLR, 2021.
[16] W.W. Zachary. An information flow model for conflict and fission in small groups. Journal of Anhrropolgiccal Research, 1977.
[17] Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. In NeurIPS, 2021.
11

---

[18] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
[19] Puja Trivedi, Ekdeep Singh Lubana, Mark Heimann, Danai Koutra, and Jayaramn Thiagara- jan. Analyzing data-centric properties for graph contrastive learning. In NeurIPS, 2022.
[20] Stephen Wright and Benjamin Recht. First-order methods for constrained optimization. In Optimization for Data Analysis. 2022.
[21] H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. 2004.
[22] Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial machine learning. In ACM SIGSAC Conference on Computer and Communications Security, 2018.
[23] Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsu- pervised inductive learning via ranking. In ICLR, 2018.
[24] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al Magazine, 2008
[25] Péter Mernyei and Cätälina Cangea. Wiki-cs: A wikipedia- benchmark for graph neural networks. arXiv:2007.02900 2020.
[26] Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks, 2022.
[27] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we really making progress? In ICLR, 2023.
(28) Yash Deshpande, Andrea Montanari, Elchanan Mossel, and Subhabrata Sen. Contextual stochastic block models. NeurlPS, 2018.
[29] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
[30] Wenzheng Feng, Jie Zhang, Yuxiao Dong. Yu Han, Huanbo Luan, Qian Xu, Qiang Yang. Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. In NeurIPS, 2020.
[31] Felix Mujkanovic, Simon Geisler, Stephan Günnemann, and Aleksandar Bojchevski. Are defenses for graph neural networks robust? In NeurlPS, 2022.
[32] Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günneemann. Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In ICML, 2020.
[33] Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IEEE Trans. Signal Process., 2020.
[34] Zhijie Deng, Yinpeng Dong, and Jun Zhu. Batch virtual adversarial training for graph convolu- tional networks. In arXiv: 09192, 2019.
[35] Fuli Feng, Xiangnan He, Jie Tang, and Tat-Seng Chua. Graph adversarial training: Dynamically regularizing based on graph structure. IEEE Transactions on Knowledge and Data Engineering, 2019.
[36] Hongwei Jin and Xinhua Zhang. Latent adversarial training of graph convolution networks, In ICML Workshop on Learning and Reasoning with Graph-Structured Data, 2019.
[37] Jinyin Chen, Xiang Lin, Hui Xiong, Yangyang Wu, Haibin Zheng, and Qi Xuan. Smoothing adversarial training for gnn. IEEE Transactions on Computational Social Systems, 2021.
[38] Jintang Li, Jiaying Peng, Liang Chen, Zibin Zheng, Tingting Liang, and Qing Ling. Spectral adversarial training for robust graph neural network. In TKDE, 2022.
12

---

[39] Jiayan Guo, Shangyang Li, Yue Zhao, and Yan Zhang. Learning robust representation through graph adversarial contrastive learning. In Database Systems for Advanced Applications. 2022.
[40] Qinkai Zheng, Xu Zou, Yuxiao Dong, Yukuo Cen, Da Yin, Jiarong Xu, Yang Yang, and Jie Tang. Graph robustness benchmark: Benchmarking the adversarial robustness of graph machine learning. NeurIPS, 2021.
[41] Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, and Stephan Günnemann. Randomized pessage-intercepplee smoothing: Gray-box certificates for graph neural networks. In NeurlPS, 2022.
[42] Marcin Wanick, Tomasz Michalak, Talal Rahwan, and Michael Wooldridge. Hiding individuals and communities social network. Nature Human Behaviour, 2, 2018.
[43] Aleksandar Bojehevski and Stephan Günnemann. Certifiable robustness to graph perturbations. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, NeurlPS, 2019.
[44] Daniel Zügner and Stephan Günnemann. Certifiable robustness of graph convolutional networks under structure perturbations. In Rajesh Gupta, Yan Liu, Jiliang Tang, and B. Aditya Prakash, editors, KDD, 2020.
[45] Jan Schuchardt, Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günnemann. Col- lective robustness certificates: Exploiting interdependence in graph neural networks. In ICLR, 2021.
[46] Simon Geisler, Daniel Zügner, and Stephan Günnemann. Reliable graph neural networks via robust aggregation. NeurlPS, 2020.
[47] Daniel Züggner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In ICLR, 2019.
[48] Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. KDD, 2019.
[49] Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack graph structured data. In ICMI., 2018.
[50] Negin Entezari, Saba Al-Sayouri, Amirali Darvishzadeh, and Evangelos E. Papalexakis. All you need is low (rank): Defending against adversarial attacks on graphs. In WSDM, 2020.
[51] Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adver- sarial examples for graph data: Deep insights into attack and defense. In IJCAI, 2019.
[52] Xiang Zhang and Marinka Zitnik. Gnnguard: Defending graph neural networks against adver- sarial attacks. In NeurlPS, 2020.
[53] Yongqiang Chen, Han Yang, Yonggang Zhang, MA KAILI, Tongliang Liu, Bo Han, and James Cheng. Understanding and improving graph injection attack by promoting unnoticeability. In ICLR, 2022.
[54] Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günne- mann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In ICLR, 2022.
13

---

A
Inductive Setting
Here, we formally introduce the inductive cose-llassification problem and the arising paddle-point problem relevant for adversarial training in the graph domain. The formal presentation follows the setting of growing graph, ie., given a training graph & of size n with labels y ) m S n, we sample a new graph g' with k additional nodes from the underlying data data-generating distribution 'D conditioned on G, which we denote (g', ~ D(G, y), where y/' E ym includes (unknown) labels of the newly added nodes. The newly added nodes are collected in the set Z. However, as will be clear later, the given formulation general and comprises different inductive learning settings described at the end of this section.
For inductive node classification, we are now interested in the expected 0/ 1-loss on the newly added nodes, given as:
v())
(A.1)
RET
Now, assuming an adversary performing a test-time (evasion) attack, one can write the robust classification error
E Lado (g' (9'W/)>-(G.)))) GIe)())) iET
Lon (fo v())
(A.2)
with ((')) representing the set of possible perturbed graphs the adversary can choose from. In adversarial training, the goal now is to solve the following saddle-point problem:
min Ladv (fo)
(A.3)
9
Because of the expectations in the losses (compared the transductive setting defined by Equation and Equation (4) neither an optimal solution to the saddle point problem defined by Equation A..) nor a perfectly robust model achieving clean test accuracy as Proposition [aap achieved through
memorizing information from the training graph. Thus, inductive node classification represents learning setting without the pitfalls presented Section 2.1
The formulation comprises the setting of an evolving graph, which does not necessarily grow but changes the already existing nodes and graph structure over time, by including the indices of the nodes present at training in the set K.. Another inductive learning setting samples G' as a completely new graph independent of G, then the conditional sampling process reduces (g', v/) D.
B Experimental Details
This section summarizes the experimental setup, including datasets, models, attacks, and adversarial training. The code can be found at https: htaps://ww/y cs, cit. tum. de/daml/ adversarial-traan trainingg
B.1 Datsets
We perform experiments on the commonly used citation networks Cora, Cora-ML, Citeseer, Pubmed, and OGB arXiv; as well as WikiCS, Squirrel (with removed duplicates) and (C)SBMs. We always extract the largest connected component for all datasets.
For all datasets, except OGB arXiv and the heterophilic datasets, the data is split follows. In the transductive setting, we sample 20 nodes per class for both training and validation set. The remaining nodes constitute the test set. Similarly, in the inductive setting, we sample 20 nodes per class for both (labeled) training and validation set. Additionally, we sample a stratified test set consisting of 10% of all nodes. The remaining nodes are used as additional (unlabeled) training nodes. For OGB arXiv, we use the provided temporal split. For Squirrel, we use the version without duplicated nodes and the split both provided by Platonov et al. [27].
14

---

We parametrize the (C)SBMs following Gosch et al. [6]. In (C)SBM, the labels y are sampled uniformly from {0. 1). Then, the respective node features are sampled from d-dimensional Gaußian distribution N ((2y;
Ka F. We set α and K 1.5, resulting in regime, where graph structure is important for node classification [6]. Furthermore, the dimensionality d is set to 21. The connection probabilities between same-class nodes p and different-clase nodes q set to p = 0.15% and = 0.63%. (This can be understood as an "inverted" Cora fit, as the maximum likelihood fit Cora results in p 0.63% and q = 0.15%.) We use 80%/20% train/validation split on the nodes.
1)2, o1) with μ 2vd
B.2 Models
In the following, present the hyperparameters and architectural details for the models used in this work. The experimental configuration files including all hyperparameters will be made public upon acceptance.
GPRGNN: We fix the predictive part as two-layer MLP with 64 hidden units (256 for OGB arXiv), The transition matrix is the symmetric normalized adjacency with self-loops D 1/2 AD 1/2, while the diffusion coefficients are randomly initialized. A total of = 10 diffusion steps is considered. During training, the MLP dropout is fixed 0.2 and no dropout is applied to the adjacency. In contrast to Chien et al. [13, the diffusion coefficients are always learned with weight decay. This acts regularization and prevents the coefficients from growing indefinitely.
ChebNetl:: Similarly, we use a two-layer MLP for the features with 64 hidden units and K = 10. Following the authors Hc et al. 14. we use the shifted graph Laplacian without self-loops L 1/2 -D A/2 L then has eigenvalues in the range [-1, instead of [0, 2]. This shift the Chebyshev polynomial, however, does not affect
is required for the parametrization eigenvectors. During training, we apply dropout of 0.8 to the features and 0.5 to L to the propagation.
GAT: We use two layers with 64 hidden units and single attention head. During training we apply a dropout of 0.5 to the hidden units. No neighborhood dropout is applied.
GCN; We use a two-layer GCN with 64 hidden units. For OGB arXiv we increase to three layer architecture with 256 hidden units. During training. a dropout of 0.5 is applied.
APPNP: The structure of APPNP mirrors that of GPRGNN. A two-layer MLP with 64 hidden units (256 for OGB arXiv) encodes the node attributes. This is followed by generalized graph diffusion with transition matrix L = D-1/3 À D D1/2 and coefficient "K- = (1 - -x) K and n = a(1 - az)l for | K. As for GPRGNN, total of K 10 steps is done and the MLP dropout is fixed at 0.2, while no dropout is applied to the adjacency. The a is set to 0.1.
SoftMedian GDC: We follow the default configuration of Geisler et al. 17 and use a temperature of T = 0.2 for the SoftMedian aggregation with 64 hidden dimensions as well dropout of 0.5. The Personalized PageRank (PPR) diffusion coefficient is fixed to a = 0.15 and then a top k: = 64 sparsification is applied. In the attacks, the model is fully differentiable but the sparsification of the propagation matrix.
MLP: The MLP follows GPRGNN's prediction module. has two layers with 64 hidden units (256 for OGB arXiv) and is trained using dropout of 0.2 on the hidden layer.
Training parameters. We perform adversarial training described in Algorithm B.2 We train for maximum of 3000 epochs and optimize the model parameters using ADAM with learning rate le-2 and weight decay 1c-3. To avoid overfitting, we apply early stopping with a patience of 200 epochs. For early stopping, we attack all validation nodes with the training attack and consecutively evaluate the loss on all validation nodes w.r.t the resulting perturbed graph. Following insights from Geisler et al. [7]. the sanh-margin loss is chosen as both attack and training loss. To increase stability, the first ten epochs are performed without including adversarial examples.
Training attack parameters. During adversarial training, we run a total of 20 attack epochs without early stopping. For PGD and PR-BCD, we stick with the same learning rates as for evaluation. For I.R LR-BCD, we multiply the learning rate by 20 to account for the lower number of epochs. This helps to obtain sparser solution where local constraints accounted for.
15

---

B.3 Attacks
For evaluating the robustness GNNs, we use the following attacks and hyperparameters. Following insights from Geisler et al. [1]] the lanh-margin loss is chosen as attack objective.
PGD 3 We optimize for 400 epochs. In epoch we use learning rate of 0.1 A/VI, where A is the global budget (see Section
We closely follow the setup from Geisler et al. [7 We use a block size of 500.000 (3.000.000 for OGB arXiv) and perform 400 epochs. Afterwards, the best epoch's 's state is recovered and 100 additional epochs with decaying learning rate and without block resampling are performed. Additionally, we scale the learning rate w.r.t. A and the block size, as suggested by Geisler et al. 17
PR-BCD [7
LR-BCD: We use a block size of 500.000 (3.000.000 for OGB arXiv) and perform 400 epochs. We scale the learning rate w.r.t. A and the block size, identical to PR-BCD. The local budget is always chosen as
FGSM 177 The FGSM attack greedily perturbs single edge each epoch. No hyperparameters are needed.
B.4 Projection of LR-BCD
We next give the pseudo-code for our LR-BCD in Algorithm B. To improve performance, only iterate edges that violate local budget. Edges that only impact the global budget are handled separately. Additionally, we stop Algorithm B. early if the global budget is exhausted.
Note that the algorithm represents the implementation for undirected graphs
Algorithm B.1 LRRBCD Projection with local and global constraints
Input: Upper triangular perturbations R=*" budgets A E N. (1) E N"
Output: projected gradients P = (S)
P < 0
|| sparse matrix of shape
S (S) idx + argsort(triu(S), 'desc', 'indices")
for (u, v) in idx do
if S u, O A
S. 0 then Return end if
An, + min (A, ( (U) )
if Au, 2 Su,e then
Pu,e f- Su,w
A + A Su,v
A@ + A!
(I) Su,
A ( <- A!! (1) Su,
end if
end for
B.5 Adversarial training
In adversarial training, we solve the following objective
m
arg min max Σ ((fo())..))) GEB(g)
(B.1)
where m the number of labeled nodes and & the clean training graph and is the chosen (surrogate) loss. Since Equation (I) is a challenging (typically) non-convex bi-level optimization problem, we approximate it with alternating first-order optimization. In other words, we train fo not on the clean graph G but on adversarially perturbed graphs & that are crafted in each iteration. This process is represented by Algorithm B.2
16

---

Algorithm B.2 Adversarial Training
Training/validation graph Gi/u. training/validation labels yi/u- GNN Sag adversary A. epochs E. warm-up epochs W, loss f, learning rate
Input:
Output: GNN fa-
emin
for / = to W do
0: 6- 1 + a* Vo, ((
end for
for
1 W E do
G. + A(fa 11 (.(),
8: -- 81- *** Voi-1 ((So, (91), yc)
Go + A(for ye)
if min >
then
mmin + e(So, (9v).
+-00 01
end if end for
B.6 Self-Training
For self-training, first pscudo-labels are generated using Algorithm B.3 trained on the expanded label set.
Then, new, final GNN is
Algorithm B.3 Self-Training
Input: Graph G, labels y", GNN fe. epochs E
Output: Expanded labels fo- train(fo.S G. y²)
train an initial GNN
y [a- (9)
predict pseudo labels for all unlabeled nodes |/ return union
- U
C Transductive Setting
C.1 Proof of Proposition 2
Before proving Proposition note that the assumption G E BB()) in Proposition natural and usually fulfilled in practice. This is the idea behind choosing perturbation model B(G) is to include all graphs, which are close under some notion to the clean graph G. As a result, all common change the graph if would not increase misclassificcation, i.e., G E B(G) holds. Now, we restate Proposition 2 for convenience:
perturbation model choices [12] allow the adversary
Proposition 2. Assuming we solve the standard learning problem 0* = arg ming Lo/1(Ja) and that G B(g). Then, fo- = A(fo-) ) is optimal solution to the saddle-point problem arising in (transductive) adversarial training, in the sense of Ladv (fe)) ming Cadv(fe) I ming Lodv (fo).
Proof. Assuming & E B(G) leads to the following lower bound on the adversarial misclassification rate: Lo/1(fo < (fo), valid for all f. This implies (i) ming Lay (fo) I ming Lado (fo) Now, assuming arg ming Lay1 (fo) given and using our modified learning algorithm fo., we obtain
Lado(ffe)) min (fo) I min (fo)
The first equality follows from Lodo (fo.) f = Lo.1(fo) = Lo/1 (fo.) = ming (fa)(fo) and then, using (fe) Lo/1 (Fo) Lodv (fo) results ming Loj1 (fa) ming Lado (fo). The last inequality follows from (i). This shows the optimality of for w.r.t. the saddle-point problem.
17

---

C.2 Empirical Limitations
C.2.1 Adversarial Training Causes Overfitting
shows that GPRGNN adversarially trained (robust diffusion) with on Cora (with self-training) is (almost) perfectly robust against wide range of attacks, not only PGD. Similar results hold for other common transductive benchmark datasets such as Cora-ML (Table C.2 or Citeseer (Table
Table CTT
Table C.1: GPRGNN's test-accuracy [%] under attack Cora. This robust diffusion has been adversarially trained with e (with self-training) and shows (almost) perfect robustness against wide range of attacks.
Perturbed Edges [%]]
0
5
25
50
100
PGD FGSM
82.0+1.5
81.8+1.4
81.8+1.4
81.8+14
81.8+1.4
81.7+1.4
81.7+1.3
82,0+1.5
81.8+1.4
81.8+1.4
81.7+1.3
81.3+1.2
81.0+1.1
80.6+1.0
GreedyRBCD
82.0+1.5
81.8+1.4
81.8+1.4
81.7+1.3
81,4+1.2
81.0+.11
80.7+1.1
PRBCD
82.0+1.5
81.8+1.4
81.8+1.4
81.7+1.4
81.6+1.3
81.5+1.3
81.4+1.2
Table C.2: GPRGNN's test-accuracy [%] under attack on Cora-ML. This robust diffusion has been adversarially trained with c (with self-training) and shows (almost) perfect robustness against wide range of attacks.
Perturbed Edges [%]
0
5
25
50
100
PGD DICE
81.8+1.9
81.8+1.9
81.8+1.9
81.8+1.9
81.8+1.9
81.7+1.9
81.7+1.9
81.8+1.9
81.8+1.9
81.8+1.9
81.8+1.9
81.8+1.9
81.8+1.9
81.8+1.9
FGSM
81.8+1.9
81.8+2.0
81.7+1.9
81.6+2.0
81.5+2.0
81.2+2.0
80.9+2.0
GreedyRBCD
81.8+1.9
81.8+1.9
81.7+1.9
81.6+1.9
81.5+1.9
81.2+2.0
81.042.0
PRBCD
81,8+1.9
81.8+1.9
81.8+1.9
81.8+1.9
81,7+1.9
81.6+1.9
81.5+1.9
Table C.3: GPRGNN's test-accuracy [%] under attack on Citeseer. This robust diffusion has been adversarially trained with e (with self-training) and shows (almost) perfect robustness against wide range of attacks.
Perturbed Edges [%]
0
5
25
50
100
PGD DICE
71.8+0.9
71.8+0.9
71.8+0.9
71.8+0.9
71.7+0.9
71.8+0.8
71.8+0.9
71.8+0.9
71.8+0.9
71.8+0.9
71.8+0.9
71.8+0.9
71.8+0.9
71.9+0.9
FGSM GreedyRBCD
71.8+0.9
71.8+0.9
71.740.9
71.7+0.9
71.5+0.9
71.3+1.0
71.0+1.0
71.8+0.9
71.++0.9
71.740.9
71.740.9
71.5+0.9
71.3+0.9
71.0+10
PRBCD
71.8+0.9
71.8+0.9
71.8+0.9
71.740.9
71.740.9
71.740.9
71.440.9
C.2.2 Self- Self-Training as the (Main) Cause for Robustness
Figure C.l shows that self-training is the major cause for robustness not only for GCN but also for other architectures. Figure C.2 highlights that this phenomenon also occurs given different attack strengths in the adversarial training. Figure C.3 shows that these results are not only constrained to the Cora dataset.
18

---

6/1
R5
Test Accuracy [%6]
60
Test Accuracy [96]
Test Accuracy [96]
80
76-
75
75
20
83
60
8
55
Normal Tmm.
R5
Normal Trn.
Normal Trn.
50
S0
Adv. Trn.
Adv. Trn.
SelF-rm
SelF
Adv.
25
10
25
10
25
Perturbed Edges [%6]
Perturbed Edges
1%)]
Perturbed Edges [%]
(a) GCN
(b) APPNP
(c) Robust Diffuusion (GPRGNN)
Figure C.1: Training different architectures with different training schemes on (transductive) Cora
with global training budget of e 0.1 (10% perturbed edges) and using self-training.
Test Accuracy [%6]
Test Accuracy [9%]
Test Accuracy [%)]
70
70
20
68
85
88 %0
60
8 &
Normal Trm.
Normal Trn. Adv. Trn.
Normal Trn. Adv. Trn.
+
Adv. Trn.
45
Self & Adv.
Self & Adv.
Selli & Adv.
40
Perturbed Edges (76]
Perturbed Edges [%6]
Perturbed Edges [%6
(a) GCN
(b) APPNP
(c) Robust Diffusion (GPRGNN)
Figure C.2: Training different architectures with different training schemes on (transductive) Cora
with global training budget of 0.05 (5% perturbed edges) and using self-training.
73
Text Accuracy [96]
Accuracy [%6]
Test Accuracy [96] 6
65
&
5G
50
50
50 ds
48
Normal Tem.
45
Narmal Trn.
Normal Trn.
40
T.
Self Tra.
Self Trn.
Sclf Trn.
25
25
Perturbed Edges 1%6]
Perturbed Edges [%6
Perturbed Edges [%6]
(a) GCN
(b) APPNP
(c) Robust Diffusion (GPRGNN)
Figure C.3: Training different architectures with different training schemes (transductive) Citeseer
with global training budget of 0.1 (10% perturbed edges) and using self-training.
D Additional Inductive Results
Here, we present additional results for adversarial training in the inductive setting. supplement the results of the main part with results on other datasets well as more extensive results for Citeseer.
D.1 Test Accuracy
Table D.I supplements Table and additionally shows the results of the investigated models for an adversary with c = 5% and using only self-training without adversarial training. Thereby, we ablate the effects of self-training and adversarial training the achieved robustness and highlight, that self-training alone already significantly increases robustness, but combining both methods achieves the best results.
Table [ and Table show analogous results for Cora and Cora-MI,, respectively and Table D.4 for Pubmed. They again show that robust diffusion achieves the highest robustness values. Table D.5
19

---

Table D.I: Comparison on Citeseer of regularly trained models, the tfate-of-thh-arr art SoftMedian GDC defense, self- seff-traindd models and adversarially trained models (train 20%). The first line shows the robust accuracy [%] of a standard GCN and all other numbers represent the difference in robust accuracy achieved by various models in percentage points from this standard GCN. The best model is highlighted in bold.
Model
Self-
Ads.
Aveval - tr..
LR-BCD
PR-BCD
LR-BCD
PR-BCD
LR-BCD
PR-BCD
trn.
Clean
0=5%
c=10%
c=25%
GCN
X
72.0 =
62.5 =
39.3
$4.7 28
51.7
45.3
38.0
GAT
X
-3.6 -36=1.7
:3.224
-0.6
33
+0.5 40.:33
15.9433
2.3773
2.
GPRGNN
K
12.2
+2.0 3.3
+3.1
14.2 27
+3.6
+5.5
+
ChebNetll
K
+1.1 =
44.0
434=25
+5.8 255
24
+10.4 2.6
+7.6+
MoftMedian
+9.5
GCN
+1.1 09
+30 0.020.1
+34
+64
+3.1 03
+9.2
+1.3
GAT
X
40.2 -
40.8 2.5
44.8 - 2.7
+1.6 -
+5.+337
6.77
+0.0
GPRGNN
+1.7 =
+7.3
+72
+132
+10,9 2 3.7
+18,4
+19.6
ChebNetll
102 1.7
+2. + 0.9
13.
1.5
+7.
22
+6,9 +
+12.0
10.4 2.3
+7.8
PR-BCD
+0,
+14
+2.5
0.9
+63
0.
+5.3
+8.6
+5.8
GAT
LR-BCD
+0. 1.6
11. = 2.0
+5.1
2.7
+5.9
+9.0 3.0
+844
+13.1 3.5
PR-BCD
APPNP
LR-BCD
-08
+22
=30
+76=16
+3.6 19
+11.1
+8.3 3.6
PR-BCD
-02 = 222
+22
1.2
+3.1
+6.2
+5.
+9.0
+6.5
LR-BCD
481
36
+136+33
+24.8 42
PR-BCD
+06
+8.1
+103334
+150 36
+159
+23,2
+26,3
ChebNetll
LR-BCD
+3.7 1 L4
+6.7 2 0.8
+84 L.
+11.
16
+11.5 11
+16.4
19
+16.0
PR-BCD
434
47.0
4132-22
+14.3
12
shows the results for arVvv. The training split in training is not applicable. Adversarial training improves the robustness the investigated models on most occasions. A learnable, robust diffusion is particularly effective for small c, while fixating the diffusion can advantageous for large e. This most likely explained by the different structure of this large-scale graph compared the other benchmark graphs, indicated by adversaries with 1% or 2% being already very effective and corresponding to a large number adversarial edges.
is fully labeled and hence, self-
In Table D.6, we additionally compare the performance using the DICE and PGD attacks. Moreover, we show that our adversarial training approach a more effective defense than GRAND 30 against LR-BCD.
Table D.2: Comparison on Cora of regularly trained models, the state-of-the-ar SoftMedian GDC defense, self-trained models and adversarially trained models (train 20%). The first line shows the robust accuracy [%]] of a standard GCN and all other numbers represent the difference in robust accuracy achieved by various models in percentage points from this standard GCN. The best model is highlighted in bold.
Model
Self-
Adv.
A. eval.
LR-BCD
PR-BCD
LR-BCD
PR-BCD
LR-BCD
PR-BCD
trm.
A. trn.
c=10%
2=25%
GCN
X
79,9 4 0.9
67.5 1:
66.7 2 0.8
60.8 0.2
59.1 111000 0.4
47.9 1.8
44,1 4 0.7
-110.9
-18223
APPNP
+1.6 1: 0.1
+
+2.2
+24 1.7
+2.7 0.9
+7. 1:
+3.1
GPRGNN
+2.0 1.2
+7.4 +.0
44.0
088
+8.5 0.1
+5.3 1.0
+138
+7.9
ChebNetlI
SoftMedian
-2.9
+3.8
1.2
1..611.11
+5.9
+148 2.7
+10.4
GCN
+0.6111 1.0
+3.
02
+3.1112
+3.21006
03
+16103
2.7
APPNP
+2.0 0.9
+5.3
14.0
0.8
48.2 1,4
+6.1 1.0
+13.4
+7.1 +.08
GPRGNN
+2.8 = 1.0
+8.2
+6.7 02
+,20
+3
-19.7 24
+16.7 3.0
GCN
LK-BCD
0.7
+1.111
+4
+3.7066
+3.12033
-10. 2.1
+3,1122
PR-BCD
1.
+3.1
+2.3
+6210.8
13
+8.7 1:
+5.0 0.7
GAT
PR-BCD
-2.1
0.7
+5
106
+5.1
17.6199
+3.
+14,5 4.0
APPNP
LR-BCD
+.18.1111
1.2
+39
+85104
+6.8
-14.7 2.7
+8.111 12
LR-BCD
+2.62202
+62
+01104
12
+11.0000
-221123
+168 15
GPRGNN
PR-BCD
+00++06
181+11
+8.1-04
13
1228107
+22.1 +4
ChebNetll
LR-BCD
PR-BCD
+5
-6.7196
+3
-12170
+8204
-2267
+12262
+5
+18248
+6.7 14
+117 133
-100058
+7.611
+6.4
20

---

Table D.3: Comparison on Cora-ML of regularly trained models, the state-of-the-arr SoftMedian GDC defense, eeffntraine models and adversarially trained models (train c = 20%). The first line shows the robust accuracy [%] of a standard GCN and all other numbers represent the difference in robust accuracy achieved by various models in percentage points from this standard GCN. The best
model highlighted in bold.
Model
Self-
Adv.
A. eval.
Art.
Clean
LR-BCD
(=5%
PR-BCD
LR-BCD
c=10%
PR-BCD
LR-BCD
c=25%
PR-BCD
GCN
X
82.5 199
6..0
2.5
2.
18.5 1.6
38.0 2.3
GAT
3.1221
4.3.211
-1.3221
4.0
214
49
APPNP
+3.
+2.3+13
+08
+4.+-11
GPRGNN
40.91:00
+5.0088
+2
0.
+1.3 05
+8.6
+86
ChehNetlI
.0.2 0.5
1.7
+.7
1..0
+2
+7.0
+6.3 2.1
Softeeiian
-0.8 L.0
+7.7 19
+..
+10.7
1.44
+9.
+17.0
0.6
+17.4
00770.7
20
1.6
#6.1
+3
+1.3
+6.307
GAT
X
-3.6
28
3.7
-6
-1.3
-17.0
3.8
-2. -20 3.1
APENP
+14107 0.7
+5.8 200
+.6
1.7
0.
+10.1
0.5
+7.7
GPRGNN
+10.7
ChelNetHI
+18+003
+8.0
149
49.9 +22
+6.2
+108
+10.1 2.3
GCN
LR-BCD
+.220077
+3.5
03
+10.3 0.
MIZIIA
GAT
LR-BCD
-2
143+19
+18+14
17.0
+7.2
+10.7
0.1
+169
PR-BCD
1.0
2.
+13
+5.0
+:00
+4.8 26
+5.5 2 1.4
+130 1.5
LR-RCD
+..7+14
PR-BCD
+0
1.
1.7
1..6
+6.0
+134
+3.6
GPRGNN
LR-BCD
+0.
2.7
+.76
+13.1 11
+25.9 3.4
+2288
PR-BCD
-0.0
+3
+10.7
+182
4.
+16.1
1.11:99
+28.2 3.6
+310 +
ChebNedl
PR-BCD
+1.1 04
+8.3
200
46.3
+109
+13.1 1.7
+8.9 + 0.9
+15.1 +
+15.1 + 1.1
Table D.4: Comparison on Pubmed of regularly trained models, self-trained models and adversarially trained models (train 20%). The first line shows the robust accuracy [%] of standard GCN and all other numbers represent the difference in robust accuracy achieved by various models in percentage points from this standard GCN. The best model is highlighted in bold.
Model
Self- trn.
Adv.
A. eval.
LR-BCD
PR-BCD
LR-BCD
PR-BCD
LR-BCD
PR-BCD
Cleun
c45%
c=10%
c=25%
GCN
X
77.4 =
64.3
62.2
60.4 0.
54.0
0.5
5288
39.3
GAT
X
-3.0 + 1.7
-5.6 4.5
-1.5 1.5+28
-10.3 6.65
-09 +
-148 +
491661
APPXP
10.5 0
+1.9
+.
0.1
12.5 +
12.4
GPRGNN
X
+1.4
+1.3
+28 1.2
+0.7 2.1
43.0
+1.2
+34
GCN
+1.8++0.9
43.411
1.4
440+15
14.1 0.6
+5.1+1.7
+2.
GAT
APPNP
1.17
+5.5 1.5113
-5.7
+6.1
+6.7 1:
+7.3
+6.0
GPRGNN
+1.7
16.0 +0 1.5
+56 0.9
16.6 + 1.8
+7.8 1.4
+9.0 2.9
+11.5 115+-22
GCN
LR-BCD
PR-BCD
+1.1 1.6
15.8
.4.4
+6.8 +.9
+50+
+88
+5.3 +.3
GAT
LR-BCD
-0.1
4,00
+.
+8.2
+84+11
+130
APENP
LR-BCD
PR-BCD
+2.6 1.3
12.-14
+7.8 1 18
169
+7.5 1.9
+69
+8.5 1.2
19.115
+9.
188
+12. 20
111.2
+9.1
+88
GPRGNN
LR--CD
1.
+12.
49.9
+,54+17
+2
PR-BCD
+3.0
+13.6
+132210
+16.7
+19.0
+23.5
+29.5
Table D.5: Comparison on OGB-arXiv of regularly trained models and adversarially trained models (train 5%). All numbers in %. The best model highlighted in bold. In general, adversarial training is effective in increasing adversarial robustness.
Model
Ads. A. evall....
Clean
LR-BCD
c=1%
PR-BCD
LR-BCD
<=2%
PR-BCD
LR-BCD
co5%
PR-BCD
LR-BCD
c=10%
PR-BCD
5..0
52.7.00
4691
71.9
63.9-02
648
0.3
$4.
02
50
APPNP
PR-BCD
LR-BCD
0.12001
0.4
63.
6
62.5 0.
632-0.
59,8 = 0.3
60.4 0.1
6.1
59.0
56.5 0.2
55.4 0.2
5.222..
$2.0
5.020.
0.
44
5.4101
GPRGNN
LR-BCD
703-02
709::00
644
638
63.
0.1
61.1 =
59.8 0.1
$5.
$5.5
52.0
$3.4
527
53.5-00.1
444+0.1
484:1001
D.2 Learned Diffusion Coefficients
shows the learned coefficients for GPRGNN on Citeseer, Cora, Cora-MI_ and Pubmed. The results for Citeseer are the ones reported in Figure given again for reference. The observation that including local constraints during adversarial training leads to robust model leveraging the
Figure D.I
21

---

Table D.6: Further adversarial attacks on Citeseer and additional GRAND defense. The LR-BCD results also used --BCCD during the adversarial training. For PGD and DICE, we perform adversarial training with PR-BCD match the set of admissible perturbations.
Áttack evaluation
Adv.
Clean
c=0.25
trn.
X
72.0
1.6
$3.2 + 1,9
41.7 + 2.8
GCN
72.0
59.3
LR-BCD
ModLMedian GDC
12.9 4: 0.8
62.6
4 1.0
57.1 4-
GRAND
14.6 2.4
65.7
3.3
39.7
GPRGNN
14.1
58.0
1.0
49.1 1.11
67.8
2.8400 0.8
64.6 1.2
GCN
73.4
57.9
46.43.1
PGD
1..2
63.2
57.
GPRGNN
73.7 14744:06
67.6
1.2
64.8 1.3
GCN
13.4
71.8
1.5
68.8
DICE
GPRGNN
0..
73.8
7..9
73.7 1: 0.6
73.7 +
1.0
73.1
Coeff.
0.25
Coeff.
0.25
0.00
0.00
10
10
Index
Index
Index
Index
Index
Index
(a) Citeseer
(b) Cora
Coeff. %
0.25
I Linaog
Coeff.
0.00
Mumifi
0.00
10
10
10 Index
Index
Index
Index
Index k
Index
(c) Cora-ML
(d) Pubmed
Figure D.1: Learned robust diffusion (GPRGNN) coefficients 7 for different datasets. For each dataset, left figure represents standard training, middle figure represents LR-BCD (adv. training w/ local constraints), right figure PR-BCD (adv. training w/o local constraints). For adversarial training, 20% is used.
general graph structure in a robust way compared to training with global constraints only is general all datasets. Training only with global constraints, for node classification, the information in the graph other than the node's ' own features are suppressed, as only and 72 and, to a lesser extent, 74 are pronounced. These mainly correspond to information about the original node itself. as the information about itself propagates to its neighbor and back in 2-hops and similar for the second-hop neighbors. However, information from 7/ with odd suppressed through being set close to zero.
A spectral analysis as carried out in Figure 7 can be found for Cora and Cora-ML (and Citeseer for reference) in Figure D.2 The behavior that PR-BCD training leads high-pass behavior is consistent across datasets.
22

---

Filter magn
1.0
regular
Filter magn.
1.0
regular
Filter magn.
1.0
regular
0.5
adv LR-BCD
0.5
0.3
BR-BCD
LR-BCD
adv trn. PR-BCD
adv trn. PR-BCD
adv Irn.
PR.BCD
Eigenvalue
Eigenvalue
Eigenvalue
Citeseer
(h) Cora
Cora-MI.
Figure D.2: Spectral filters corresponding to Figure D. for Citeseer, Cora and Cora-ML. Low filter magnitude denotes suppression of the respective frequencies associated with eigenvalue
D.3 Comparison of PR-BCD and LR-BCD
0.67
LOACO
0.75
0.60
0.50
Feturaed Eogas Sp2201 [S] Pertaibed Ergus igobed (S)
Pertuted Coges (2M000 (5)
(a) GPRGNN
APPNP
(c) GCN
Figure D.3: Comparison of PR-BCD and LR-BCD on Cora-MI. The x-axis gives the relative global
budget. The local budget (if considered) for each node u of degree d,, A [d,//]. The models are learned using self- tif-itraning. Results are aggregated over three different data splits.
Figure D33 compares the efficacy of PR-BCD to LR-BCD on Cora-MI. For a fair comparison, as the admissible perturbations B(G) are inherently different for both attacks, also consider LR-BCD with an unlimited local budget. In this case, LR-BCD's projection defaults to greedily picking the valuud perturbations until the global budget is met. We observe that LR-BCD w/o local constraints performs similar to PR-BCD. This suggests that the chosen greedy approach is suitable. Additionally including local constraints, the attack efficacy reduces. Still, even with local constraints, LR-BCD is able to recover adversarial examples that significantly reduce classification performance.
D.4 Certified Accuracy
Table D.7 shows certified accuracies for Citeseer against extended set of perturbations compared to Table T.b Table[D99she show analogous results for the benchmark graphs Cora and Cora-ML, respectively. On all datasets, highest certifiable accuracy is achieved through robust diffusion.
Table D.7: Comparison of certifiable accuracies for different perturbations Citeseer of regularly trained models, the state-of-the-aar SoftMedian GDC defense, and adversarially trained models (train 20%). The first line shows the certifiable accuracy [%] of standard GCN and all other numbers represent the difference certifiable accuracy achieved by various models in percentage points from this standard GCN. The best model is highlighted in bold.
Ads.
accuracy /spare smoothing
tm..
Clean
add.
25.2
14.0
-IS1
-17 0.4
13.0
APENP
+26.2
+31.8
-31.2
-316-440
GPRGNN
434.6
442.5
-4244
4
436.6
441.3
ChehNetll
424.6
+45.5
+55. 1.3
+369
4
4510 U1
SotlMedian
10.5
4.7.4.40
#60.1
1.
4.0.6.3..0
+50.3
GCN
PR-ECD
-113+33
3.5
462
LR-ECD
+.4
+..2444.
PR-ECD
45.
+1.9
+12
+2
48
03
+419 0.9
APENP
LR-ECD
PR-BCD
1.1.7
119.3.14.6
+1..4
-410124
1.
+38.9
+40.2
+4L1
2.2
GPRGNN
PR-BCD
LR-BCD
1340-173
132.9.75
+55.5
+353
+688
+69 L9
-674
15
+667 158
+458 59
18
+3..6.3.
+89 1
+8.
ChoNNell
LR-BCD
PR-BCD
+307 132
+31.
-1151127 12.
+52
+512
+65.4
16
19
+6.8
1.60
+56.1
+53.115
4 2.7
23

---

Table D.8: Comparison of certifiable accuracies for different perturbations on Cora of regularly trained models, the state-of-the- -hrtthe-rtt SoftMedian GDC defense, and udversarially trained models (train e = 20%). The first line shows the certifiable accuracy [%] standard GCN and all other numbers represent the difference in certifiable accuracy achieved by various models in percentage points from this standard GCN. The best model is highlighted in bold.
Model
Adv.
trb.
Training attack
Clean
1 add.
add.
3ddd.
Certiliable accurncy
4 4add.
sporse smoothing del.
del.
5 del.
del.
GCN
30.9 1 0.2
199 3.2
129.1.4 4.1
123
1.41
1:7
237
2.2.
1.4.1.3
155 1.4.1
132
GAT
4.8
-33 2.0
123
113
2:33
33
2.64
114153
135 4.0
123
4.0
APPNP
-26.4 1.2
+304
29. 5.2
-289
1.33
+303
2.5
+294
2.2
+305
4.1
+28. 1.2.2
+29.
GPRGNN
-20.6
2.4
+256
1.11
+253 6.3
-254
1.1
+22.0
4.0
+242
4.9
+263
6.6.
+254
1.2.
+25
6.4
ChebNeell
X
-328
+40.
+462 1.8
-16. 1.88
+324-144
+38.
1.2.2
+421 1.1
+42.
1.8
+46. 1.8.1
SeftMidiin
-36.0
1.2
+16.
4.6
4.555.5.9
-519138
1.34
+125
+470
+192
1.57
+6141662
GCN
PR-BCD
LR
+13.7
14.3 2.25
6.2.
+79 4.5.
155 3.
2.0
131.666
17267
3.3 1.5
2.7 1.0.
2:233
+106
163 2.0
1.1.1
143 3.0
033 4.9
+0. 0.6
2.61
2.0
GXT
V
PR-ECD
LR-BCD
+64 1.4
+06++00.
+1. 7.4
+94++111
+122+
-4 1.5
-12.1 +-188
.4. 1.6
+34+1111
-24+ 1.0
46. 2.0
148 +4.7
+107 +.5
.29+
+12.
.5. +.00
+-1.7
+12.0
-66 1.6
1.7
APPNP
V
PR-ECD
LR-BCD
-31.5
-25.3 4:35
<31. #61
33
266
+30
.366
-302 2.69
+353 1:45
+374
+32.5 4:0
426. +:5
<35A 1.7
+30
+3711
+36.9 1411
:304411.
+36. 4.77
+295
=71
GPRGNN
V
PR-BCD
LR-BCD
+45.5
-433 1.0.
07
+55.7
+314
1.
+619
:346 4.9
+62. 15
1592149
+68
+59.1
1.3
1:30
+52.1
+48. 2.3
+568
+525 1388
+525
+59.5
+338
3.
1.45
+61.7
+3L.3
15.1
1.37
ChebNetll
PR-BCD
LR-BCD
-248 +.28
-27.1 2.0
434.
+333
6.1
+45
+386 7.8
+365
+39.1 470
+8.7
+44.7 3.3
+309
6339
2 3.6
3.1
+365 6.8
+363
+36.5 +13
+38. 7.7
+38.1
+38.3 #.2
+55.
Table D.9: Comparison certifiable accuracies for different perturbations on Cora-ML of regularly trained models, the state-of-ue the-art SoftMedian GDC defense, and ad adversarially trained models (train c 20%). The first line shows the certifiable accuracy [%] of a standard GCN and all other numbers represent the difference in certifiable accuracy achieved by various models in percentage points from this standard GCN. The best model is highlighted in bold.
Model
Adv.
tmn.
Training attack
Clean
1 add.
udd.
uddd.
Certillable accuracy sporse smoothing 4udd.
del.
del.
5 del.
7 del..
GCN
X
976++00.
23.6 + 2.1
96
88 +.7
38 +-222
19.9
0.8
19.5 2.9
14.3 4.1
10.1 + 3.8
GAT
X
12.114.1
366
1:61:44 4.4
28
4:33
3.3
76
0.4
4.8
23 1.5
5.1.6.1
APINP
X
-17.3 1.5
+26.1
1.3
1.4.5.3.
-338 1:33
=38911200
+219 1.0.
+290 2.1
+32. 1:35
+3
GPRGNN
1:14
+320
1.8
1.:11.2
1386
+39.1
1.1.7
-292
2.2
+34.5 1.7
+.3.6.1..00
+378 1:29
CheNNetT
X
-225-1112
-003
6.6
-5166192
-52. 1.9
-553
9:7.1
-359
4.4.
-438 7.75
-480-1..
+514
SofMedian
-356-+004
-467
5.1
+570++7.
+577
-603
+-50
-413 +-8
+
+538 +.79
+569 769
GCN
V
PR-BCD
LR-BCD
-119144
+111
115119
+.331443
113
+2817.1
+2. 1.1.1
+0.7 133
1.
+3. 1:511
+0. 1.6
+.331.5.3
166132
133
+20.169
+1113355
+28 1.33
GAT
V
LR-BCD
FR-ECD
.3.02:66
1.1111111
+56 1.4
6.
+6.7 1044
+11.7..4
+7.4 10.4
-116611.7
1.6. +102
+0.6 1.0.
.8.1 4:43
-09174
+8.8128
+108 1.588
42.1 1:..6
+6.2 10.5
+11117
APPNP
V
LR-ECD
FR-BCD
1.5
0.5
+327
1.8
1
-38611111
+38.3
1:9
<30. 1.8
+293 1.00
+34.1
+360
+36.3 1:10
+37.1 1:88
+380 133
1.5
GPRGNN
V
LR-BCD
PR-BCD
-424
-111 1.4
16
+329
+36.0 16
1.8
+09. 32
+649113
-70.3 -701-12
-651 1:0
+749
+68.1
1.8
1.8
+999 1.06
-996 25
+36.1125 126
-68.
+610111
1.
+99 1.1.
16:1133
ChelNetll
PR-BCD
LR-ECD
-396 19
-36.7 2 1.2
27
+493
3.8
6622
+6301.4
+65.
+66.
139
1.5
6457 0.08
+339
+532
+546
+58.7 2.1.
1582100
+61.7 6.5
158
E Further Related Work
Defenses on Graphs. Next adversarial training, previous works proposed defenses based on smoothing [32) preprocessing the graph structure 55. or using robust model structures 46 48
For an extended survey, we refer Günnemann 12
Attacks on Graphs. Generally, one distinguishes evasion attacks, perturbing the graph after training 2 [7] and poisoning attacks, perturbing the graph before training 7 47). Further, one differenti- ates global attacks perturbing multiple node predictions at once [17 from local (targeted) attacks perturbing a single node's prediction 77]. Attacks can perturb the nodes attributes (7), the edge structure 47 49 [7]. or insert malicious nodes [53]. An adversarial attack should not change the true classes (unnoticeability) [8]. For certain applications, like combinatorial optimization, might be known how the true label is affected by perturbation. For example, Geisler et al. (54) study such adversarial attacks (& training) for GNNs for combinatorial optimization. However, in the context of node classification, this relationship is fuzzier. For example, Zügner et al. [7] define an attack that preserves the global degree distribution, or Gosch et al. (6) analyzes semantic preservation in synthetic graphs and show that changing more edges than the degree of nodes is usually never unnoticeable. In this work, we focus on evasion attacks on the edge structure, aiming globally attacking node predictions with realistic local constraints enforcing unnoticeability.
24

---

Limitations
This work focuses on adversarial robustness against structure perturbations for node classification. While this is the most studied and prevalent case in previous works (see Günnemann [[2] and Table B). there are many other interesting graph learning tasks or extended settings, out of scope for this work, for which robustness and adversarial training schemes could be of interest, as e.g.. link prediction, node feature perturbations or graph injection. Conceptually, the adversarial training procedure and LR-BCD attack can also be applied to the aforementioned tasks long the model remains differentiable.
On another note, while we finally put into the hands of practitioners a global attack method aware of local constraints, there is clear strategy on how determine the optimal local budget. Indeed, these have to be set application dependent by domain experts. For example, Gosch et al. [6] leverage knowledge about the data generating distribution determine budgets that correspond semantic- preserving perturbations. However, in most real-world applications, we lack knowledge about the data generating distribution. As a result, also use the different interpretability aspects of robust diffusion to collect additional evidence and insights into the learned message passing (see Section 5
In Section we report the asymptotic complexity of our LR-BCD attack. In Section S
we detail the
used hardware for the adversarial training experiments and report the computational cost in terms of runtime as well as memory on the arXiv graph, consisting of I 70k nodes.
25


Reviews:
[{"review_id": "n4sc9lS0DN", "reviewer": "Reviewer_ZTec", "summary": "The paper aims to fix adversarial training in graph neural networks (with respect to perturbations) by revealing limitations in prior work (from theoretical insufficiencies to experiment flaws), proposing a novel attack scheme and a superior architecture (robust diffusion) that makes adversarial training a leading defense method against such attacks.", "questions": "- What is the intuition behind the \"diffusion\" nomenclature?", "limitations": "The authors have not addressed the potential negative societal impact of robust diffusion, and a short analysis in discussion may help.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Paper is well written and easy to understand.\n- Strong theoretical analysis supported by elegant intuition and solid experimental results.\n- High-quality claim is supported by code artifacts.", "weaknesses": "- Readers unfamiliar with adversarial perturbations may have a hard time understanding the paper, which may warrant a short paragraph explaining the threat model for both numerical data and graph-structured data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for the positive feedback!\n\n## W1: Introducing adversarial perturbations\n\n>Readers unfamiliar with adversarial perturbations may have a hard time understanding the paper, which may warrant a short paragraph explaining the threat model for both numerical data and graph-structured data.\n\nWe thank the reviewer for the valuable suggestion and we will address this in the revision of the paper.\n\n\n## Q1: Graph diffusion\n\n>What is the intuition behind the \"diffusion\" nomenclature?\n\nA polynomial of the normalized adjacency matrix / Laplacian is generally referred to as a graph diffusion (e.g., see Eq. 1 in [T]). The most intuitive take on it is perhaps via the view of the heat kernel, which generalizes the heat equation to a discretized manifold represented by the graph. Then, the heat diffuses over the graph. We will add an explanation to make the nomenclature clear to the reader.\n\n\n## L1: Societal impact\n\n> The authors have not addressed the potential negative societal impact of robust diffusion, and a short analysis in discussion may help.\n\nWe expect the societal impact to be similar to other works on adversarial robustness, where we think the benefits outway the risks. Concretely, we allow for more fine-grained perturbation models for machine learning practitioners. Having the right tools at hand can further the reliability of graph machine learning and, thus, have a positive societal impact as long as applied ethically. Given your feedback, we will add an *Ethical Statement* to our revised manuscript."}, {"review_id": "Z1VLr0cckJ", "reviewer": "Reviewer_zNuu", "summary": "This paper focuses on adversarial training techniques for Graph Neural Networks (GNNs) in the context of inductive semi-supervised learning. It addresses the shortcomings of previous approaches in graph learning: perfect robustness is possible for transductive learning setting under evasion attack. The authors propose a more adaptable GNN model equipped with a learnable robust diffusion mechanism, capable of accommodating adversarial perturbations. Furthermore, the paper introduces a novel method for attacking GNNs by perturbing their structures, which consider local constraints in global attack settings. The study demonstrates the efficacy of adversarial training as a defensive strategy for GNNs and offers valuable insights into the field of adversarial learning for GNNs.", "questions": "- Curious how to apply adversarial training under poisoning attack settings. it is okay if this is out of the scope of this paper.\n- How would the adversarial trained model generalize to other types of attacks? Are the proposed robust diffusion model able to defend other types of attacks? E.g., gray-box/black-box attacks, poisoning attacks.\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper provides a comprehensive summary of existing research and knowledge on adversarial training techniques for Graph Neural Networks (GNNs).\n\n- The authors elaborate the limitations of previous approaches in graph learning settings, particularly emphasizing the challenges associated with transductive learning settings for evasion attacks. It also introduces a more realistic fully inductive setting.\n\n- The authors propose a new adversarial training method combining a learnable graph diffusion, with discussion on the interpretability of the learned robust representation. Based on the revealed importance of local constrained, they further proposed an attack method LR-BCD, extending previous PR-BCD attack with a projection incorporating local constraints.\n\n- The paper presents extensive empirical evidence demonstrating the robustness of the proposed adversarial training techniques and the proposed attack method. \n\n- The paper offers interesting insights for the community regarding the role of local constraints in adversarial training for GNNs. \n", "weaknesses": "- Limited to evasion attack, should clarify this in a early stage of presentation\n- Better presentation if the authors shorten section 2.1 and section 2.1.1, which introduce commonly-used settings and quite obvious propositions, and add more model framework details and training details in the main text.\n\nMinor issue:\n- the abbreviation GPRGNN is quite confusing while just appears with no explanation in the intro section", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for the positive review!\n\n## W1: Clarifying the evasion attack scenario in the beginning\n\n>Limited to evasion attack, should clarify this in a early stage of presentation\n\nThank you for pointing this out! Currently, we clarify this in line 67 (Section 2). In a revised manuscript, we plan to include this information directly in the introduction.\n\n## W2: Shorten Section 2.1 and 2.1.1\n>Better presentation if the authors shorten section 2.1 and section 2.1.1, which introduce commonly-used settings and quite obvious propositions, and add more model framework details and training details in the main text.\n\nWe do think that it is important to formally introduce and distinguish adversarial robustness in the transductive and inductive learning setting. Although the theoretical finding is intuitive to grasp once one reviews the learning settings properly, it is directional for the field as the resulting issue with a flawed evaluation in the transductive setting was not generally known (nor is trivial). This is evident by the fact that (i) the first and so far most cited work on adversarial training for robust graph learning [A] suffers from the aforementioned evaluation flaw as well as their follow-up work [O] and (ii) all adversarial training works use the transductive setting (see Table 2).\n\n## M1: GPRGNN abbreviation in introduction\n>the abbreviation GPRGNN is quite confusing while just appears with no explanation in the intro section\n\nWe thank the reviewer for pointing this out! We will explain the abbreviation in a revised version of the manuscript.\n\n\n## Q1: Poisoning\n\n>Curious how to apply adversarial training under poisoning attack settings. it is okay if this is out of the scope of this paper.\n\nAdversarial training is foremost a defense against evasion threat models and is usually not studied in combination with poisoning. Thus, we see poisoning as out of scope for this work. However, recently, there have been a few works (not in the graph domain), investigating the effects of adversarial training given poisoned data [R]. Thus, we see this as a very interesting direction for future work. \n\n## Q2: Other attacks\n\n>How would the adversarial trained model generalize to other types of attacks? E.g., gray-box/black-box attacks, poisoning attacks.\n\nNote that gray-box or black-box attacks are usually weaker than white-box attacks (i.e., attacks having complete knowledge of the data / model / weights). As one is usually most interested in the worst-case performance of a model [X], we foremost study the white-box attacks L/PR-BCD. However, for the rebuttal, we have now **added two additional attacks**: the black-box attack DICE [Q], and the white-box attack PGD [A]. You can find their performance in the pdf accompanying the rebuttal.\n\nMoreover, we study the generalization to weaker and stronger perturbations throughout our experiments by varying the attack budgets (see, e.g., $\\epsilon$ in Table 1). Furthermore, we compare perturbation models w/ and w/o local constraints as well as cross-evaluations using one for adversarial training and the other for test-time evaluation in Table 1 (and §D.1). We also assess the impact on certifiable robustness via randomized smoothing in Table 1 (and §D.1). As argued above, poisoning attacks are out of scope for this work.\n\n"}, {"review_id": "NXL2rey2pr", "reviewer": "Reviewer_fJD8", "summary": "This paper shows fundamental limitations of transductive adversarial training of GNNs for node classification and advocates that adversarial training of GNNs should be in an inductive setting. Therefore, this paper proposes a more flexible message-passing scheme using learnable diffusion to gain robust representations under adversarial training, and uses additional local constraints for structural perturbation and an efficient attack (LR-BCD) that contains both local and global perturbations.", "questions": "1. Please clarify how L/PR-BCD corresponds to adaptive attacks.\n2. Please justify how the additional local constraints could preserve graph semantics.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper studies an important problem on the GNN adversarial robustness and provides some interesting observations and insights on this topic. In particular, the analysis and discussions of theoretical and empirical limitations of adversarial training in GNN transductive learning are insightful and useful for the community.\n\nThe proposed robust diffusion framework for adversarial training appears efficient in a fully inductive GNN setting with flexible GNN architectures and refined local/global topology perturbations.", "weaknesses": "1. The technical contributions of the work seem a bit limited. It appears the proposed method is a combination of existing works, although it is a simple yet effective solution. The claimed novelty lies in the handling of the new local constraints with LR-BCD, but it does not seem to be technically different from PR-BCD. In addition, there is a lack of theoretical justification why the new projection imposes sensible global and local constraints.\n\n2. Given the limited technical contributions of the methodologies, I would like to see more extensive experimental evaluations of the proposed framework. More evaluations on other homophilic and heterophilic datasets with more powerful adversarial attacks (e.g., adaptive attacks [1]) under inductive setting should be conducted to demonstrate the universality of the proposed methods. In addition, the comparison with other robust GNN models (e.g., ProGNN [2], GRAND [3], GARNET [4]).\n\n    [1] Felix Mujkanovic, Simon Geisler, Stephan Günnemann, and Aleksandar Bojchevski. Are defenses for graph neural networks robust? NeurIPS’22.\n    [2] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. SIGKDD’22.\n    [3] Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural network for semi-supervised learning on graphs. ICML’21.\n    [4] Deng et al. GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networks. LoG'22.\n\n3. Some minor points:\n* It does not seem the equation (2) correctly reflects the principles of self-training, because theta’ appears predefined in the expression, while it is actually trained from labelled data.\n* In Equation-(5), the sum operation in the constraint is not well defined.\n* The authors may want to make the title more specific to better reflect the focus of this work, avoiding potential misleading and vagueness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for the constructive feedback and for noting that we study an important problem while giving interesting observations and insights useful for the community.\n\n## W1 (a): Technical novelty\n\nWe appreciate the reviewer recognizing our effective solution to implementing local constraints. LR-BCD *technically* and *non-trivially* extends PR-BCD, as  PR-BCD does extend PGD [A, B]. We show that including local constraints results in a challenging optimization problem (see Eq. 6 and [C]) and we propose an efficient solution algorithm. This projection step is the *main technical challenge* in these algorithms and **neither** PR-BCD **nor** PGD could handle such constraints. Thus, we introduce the *first* global attack with this ability. \n\nWe want to stress that local constraints are widely used in the local attacks [E, Q, U] and certificates literature [K, V]. The lack of such a global attack even led to prior work trying to naively and expensively apply local attacks for each node sequentially to generate locally constrained global perturbation [W]. Thus, if it would not have been technically challenging, most certainly, at least one of the global attacks would have included them [A, B, F, G, H, I, J]. Therefore, this is a clear contribution to the field.\n\nImportantly, novelty is not only derived from the new attack. Regarding test-time attacks in a transductive setting as studied by Xu et al. (2018) [A] and a wide range of other robustness works [B,D,E,K] including all works on adversarial training (see §6) - we achieve practically *perfect robustness*. Prior work did not achieve this, they did not even come close. Furthermore, we use our results to empirically and theoretically reveal the evaluation flaw in the transductive setting and overcome it by moving to a more realistic and challenging inductive setting. This is important and directional for the field as the resulting issue was not generally known. In the more realistic inductive setting, we then, without bells and whistles, achieve state-of-the-art robustness via adversarial training.\n\n\n## W1 (b)/Q2: Sensibility of global and local constraints and semantic preservation.\n\nOur projection can deal with any (local or global) budget constraints of interest for a particular dataset. Concretely, our projection method can deal with arbitrary perturbation sets $\\mathcal{B}(A) = \\\\{\\tilde{A}\\ \\in \\\\{0,1\\\\}^{n\\times n} |\\ \\lVert\\tilde{A}-A\\rVert_0 \\le \\Delta\\ \\land\\ \\lVert\\tilde{A}_i-A_i\\rVert_0\\le\\Delta_i^{(l)}\\ \\text{for all nodes}\\ i\\\\}$, where $A_i$ denotes the $i-$th row of the adjacency $A$ and $\\Delta$ & $\\Delta_i^{(l)}$ denote the global and local attack budgets. This is the most general form of the most commonly used structure thread model [D]. Handling it was **not** possible before (see above).\n\nThe concrete global and local budget choices, modeling semantic preservation, are application specific and possibly derived from domain knowledge. The sensibility of local constraints is evident by their pervasive use in the local attack [E, Q, U] and certificate literature [K, V]. Furthermore, even small global budgets (e.g., 5% of total edges) result in hundreds of adversarial edges, while for most real-world graphs, the average node degree is very small (e.g., 5.68 on Cora-ML). Figure 5 in §4 shows that successfully attacked nodes by PR-BCD usually have more adversarial edge insertions/deletions than original clean edges and hence, can be seen as completely rewired. This is not only intuitively problematic but Gosch et al. (2023) [B] prove on random graph models that this almost certainly changes the semantics (most likely node labels), whereas smaller changes often do not (see their Table 2). Possible degenerate effects of a fatally strong attack that can completely rewire any individual node are emphasized in Figure 4c where GPRGNN trained using PR-BCD learns to entirely disregard the graph structure. However, Figure 4d shows that with local constraints, graph structure is still leveraged but now, for more robust predictions. \n\n## W2: More datasets, attacks, and new defense\n\nAs requested by the reviewer, we now investigate more datasets, baselines, and attacks. We refer to the meta-comment and attached pdf for the additional experimental results, demonstrating the universality of our methods. \n\nNote that we did not include ProGNN or GARNET as they are defenses against poisoning and hence, not applicable to our work.\n\n\n## W3-1: On Eq. 2\n\nEq. 2 represents the adversarial training objective after self-training has already occurred. This is explained in lines 80-81, where we define the self-training step as happening before using Eq. 2 and yielding $\\theta'$ through training from the labeled data. We will try to make this more prominent in a revised version of the manuscript.\n\n## W3-2: Sum operation in Eq. 5\n\nWe define the sum operation as summing over all elements of the matrix directly below Eq. (5) in line 287 (& line 300 for Eq. 6). We will revise this in the revision of this paper.\n\n## W3-3: Title\n\nGiven the feedback, we consider to alter the title to *Adversarial Training for Graph Neural Networks: Pitfalls, Solutions and New Directions* and are open to suggestions.\n\n## Q1: L/PR-BCD are adaptive attacks\n\nAn adaptive attack is white-box, i.e., has perfect knowledge about the model, the parameters, and the data, including all defensive measures [X]; as is the case with L/PR-BCD. Note that adversarial training only concerns the training phase and is not an active defense during inference. Furthermore, L/PR-BCD - as being gradient-based and fully white-box - may adapt to the adversarially trained weights. In our attached pdf, we now also compare to other attacks to demonstrate the efficacy and adaptiveness of L/PR-BCD. Additionally, we evaluate certified robustness (see Table 1), where we show to significantly increases provable robustness, which is **independent** of any particular attack.\n"}, {"review_id": "NtFMGpkz4V", "reviewer": "Reviewer_bw8r", "summary": "This paper presents a comprehensive analysis of the transductive setting, highlighting the limitations of achieving perfect robustness solely by memorizing the clean graph. The authors argue that the observed improvements in robustness from previous adversarial training methods stem from unintentional leakage of information about the clean test nodes. To address this issue, the authors explore the inductive setting, which mitigates these drawbacks. They propose a defense mechanism by combining GPRGNN and ChebNetⅡ with adversarial training, effectively countering both globally and locally constrained attacks. For the implementation of the locally constrained attack, the authors develop an approximate solution to a relaxed multi-dimensional knapsack problem. The experimental results presented in the paper showcase the efficacy of the proposed attack and defenses.", "questions": "1.\tOn homophilous graphs, a high-pass filter is likely to decrease accuracy. Figure 8 indicates that adversarial training transforms the GNN into a high-pass filter. However, why does this not result in a trade-off between accuracy and robustness? Can you provide some possible analyses?\n\n\n2.\tCan the authors provide more examples of information leakage in the transductive setting? As far as I know, this is not common.\n\nOverall, this paper is intriguing and attempts to address some of the key challenges in graph adversarial attacks. If the authors address my concerns well, I am willing to consider raising the score.\n", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tIt is meaningful to discuss the adversarial training on graph models, as this is still an open problem.\n2.\tI highly value the investigation conducted in the section dedicated to locally constrained attacks, and I find the implementation of LR-BCD to be inherently rational.\n3.\tExperiments are sufficient enough to demonstrate the efficacy of the proposed methods.\n\n", "weaknesses": "1.\tThe primary concern with this work lies in the disparity between the initial analysis and the subsequent defense method design. Although the analysis extensively examines the limitations of transductive settings, there is a noticeable absence of a correlation with the utilization of an adaptive spectral GNN to enhance robustness. The motivation of the proposed defense is not very clear, and it is a combination of existing methods. While adaptively assigning weights to local neighborhoods can be an effective strategy for improving robustness, it appears to be unrelated to the previous discussions on the flaws of transductive settings and adversarial training.\n\n2.\tThe authors claim that GPRGNN offers interpretability, but Section 3 primarily focuses on presenting the learned message passing weights and filter kernels of GPRGNN. While this aligns with the intuition of enhancing GNN robustness by incorporating high-frequency information and higher-order neighborhoods, it remains challenging to argue that this alone qualifies as interpretability.\n\n3.\tThe discussion of graph adversarial attacks in the transductive setting remains valuable. On one hand, many methods in the transductive setting do not involve leakage of clean local structures of test nodes, and conventional adversarial training does not include a self-training module. On the other hand, in real-world scenarios, memorizing the graph is not certainly feasible because the structure and labels of graph nodes can be dynamically changing. In fact, even without the addition of new nodes to the graph, the defense cannot classify the current nodes based on the remembered graph structure. For example, in graph-based spammer or fraud detection, benign users and fraudulent users can switch roles as time goes on. \n\n4.\tThe theoretical part of this work, Section 2.1.1 and Appendix C.1, seems to be needless and trivial. It is evident that in evasion attacks, accuracy will not be affected if clean graphs are used for testing.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for the constructive review!\n\n## W1: Relationship of transductive and inductive learning with robust graph diffusion\n\nThe use of adaptive spectral GNNs is **directly connected** to the discussion on the flaw of the transductive setting. With our refined model choice, we achieve *perfect robustness* in the transductive setting (see §2.1.2) and make this flaw apparent. Revealing the evaluation flaw and solving the setting stands in stark contrast to prior work and are important contributions on their own (see also our answer to W3).\n\nHowever, the main motivation for our model choice is the ability to approximate any spectral graph filter. Thus, adversarial training may choose the most robust graph filter that achieves a competitive training loss. Our empirical evaluation shows that such a flexible architecture is key to achieving state-of-the-art robustness via adversarial training (also in the appropriate inductive setting). We make this point in the introduction but will make it and its connection to the evaluation flaw (§2) more prominent in a revised version. \n\n## W2: Interpretability of robust graph diffuison\n\nIn the seminal work [L], Murdoch et al. \n> define interpretable machine learning as the **extraction of relevant knowledge** from a machine-learning model concerning relationships either contained in data or **learned by the model**. Here, we view knowledge as being relevant **if it provides insight for a particular audience into a chosen problem**.\n\nWe provide three perspectives that meet this definition, i.e., provide valuable insights into the learned characteristics for machine learning researchers or practitioners. We will clarify in the revised revision that this is what we mean by interpretability.\n\nThe (i) polynomial and (ii) spectral perspective are examining a global property of the learned model. Thus, in contrast to, e.g., a GCN, it is much easier to understand how the robust graph diffusion achieves the enhanced robustness.\n\nMoreover, the (iii) spatial perspective also yields local explanations and is more closely related to GNN explanation methods like GNNExplainer [M]. For example, the $v$-th row $\\mathbf{T}_v$ of the diffusion matrix $\\mathbf{T}$ (see line 232) will yield the influence of the transformed node features of $u \\in \\\\{1, 2, \\dots, n\\\\}$ on the prediction for node $v$ (see also Figure 4). \n\n## W3: Differences and importance of transductive & inductive learning\n\n> The discussion of graph adversarial attacks in the transductive setting remains valuable. [...] in real-world scenarios, [...] can be dynamically changing. [...]\n\nThis is a great point highlighting why our work is crucial for the field. We agree that robustness in the transductive setting is important. However, in combination with an evasion threat model, one needs to be cautious as it poses the risk that \"a defense\" exploits the availability of the clean test nodes (and their structure) at training time as happened in prior work on adversarial training [A, O]. This can yield a perfectly robust, yet not useful model.\n\nWe also agree about dynamic changes in many real-world scenarios. However, this *does not fit* the definition of transductive learning (see §2.1 and [N]), where the test data has to be known at training time. All changes after training constitute an inductive setting (see §A) and we have discussed exactly the proposed scenario in §A lines 541-543. Being inductive it is not sufficient to memorize the available data as is precisely our point in §2.1.1. (lines 126-128).\n\nWe think it is important to sensitize the field to the existent evaluation flaw and advocate for adopting learning settings and benchmark datasets better capturing the relevant robustness scenarios.\n\n## W4: Motivation for theoretical analysis\n\nAlthough the theoretical findings are intuitive to grasp once one reviews the learning setting properly, it is directional for the field as the implications are not generally known (nor trivial). This is evident by the fact that all adversarial training works do use this setup (see Table 2). While it might be fine to study transductive evasion as a worst-case setting, where all inductive changes are adversarial, it is problematic to exploit the availability of the clean data at training time as done by Xu et al. [A, O] or [P, S].\n\n## Q1: Accuracy-robustness tradeoff\n\nIndeed, we observe an accuracy-robustness tradeoff. E.g., a regularly trained GPRGNN on Citeseer (Table 1) has the best clean accuracy ($74.2$%) and is a low pass, followed by adv. training with LR-BCD ($73.7$%), which is still a low pass but allows for more high-frequency components. GPRGNN trained with PR-BCD mainly is a high-pass filter allowing low-frequencies only to pass damped achieving the lowest clean accuracy ($72.6$%). Similar behavior can be observed on our other datasets (see §D.1). This can be explained as the adversarial connections between dissimilar (different class) nodes distort homophily and make high-frequency information more important for robust generalization. While having only a global constraint (PR-BCD) allows for an excessive amount of adversarial edges per node (see Figure 5), local constraints (LR-BCD) mainly preserve the optimal filter characteristics. \n\n## Q2: Information leakage\n\nWe focus on adv. training for graph learning, here the first and so far most cited work [A] suffers from the mentioned evaluation flaw as well as their follow-up work [O]. In this setup, the predictions on the clean test nodes are leaked by using self-training (see §2.1.2). For many other defenses it is not clear to what extent the information leakage is exploited. However, there are works where the information leakage might play a role, like in the contemporary work on a causal defense [S] (Fig. 3 shows that the clean/original graph is used during training) or VAT [P]. To avoid reporting biased robustness scores, it would be important to study evasion defenses inductively.\n\n"}]

Author rebuttal:
We thank the reviewers for the constructive feedback and for acknowledging that our work is intriguing and addresses key challenges (bw8r), is insightful and useful for the community (fjD8 & zNuu), as well as provides a theoretical analysis that is supported by elegant intuition (ZTec). 

We addressed all questions and important comments by the reviewers. We now include **additional experimental results**  as requested by reviewers fJD8 and zNuu (see attached pdf):

* We added **three more datasets** (one homophilic and two heterophilic).
* We added **two more attacks**, the powerful adaptive PGD attack [A] and the classic benchmark attack DICE [Q].
* We added the GRAND defense as a **new baseline defense**.

We are confident to have addressed all concerns of the reviewers and if there are remaining open questions, we are happy to engage in further discussions.

Below, we collect all references used in our rebuttal:


[A] Xu et al. "Topology attack and defense for graph neural networks: An optimization perspective.", IJCAI, 2019\
[B] Geisler et al. "Robustness of graph neural networks at scale.", NeurIPS, 2021 \
[C] Kellerer et al. "Multidimensional Knapsack Problems.", Knapsack Problems. Springer, Berlin, Heidelberg, 2004\
[D] Günnemann S. "Adversarial robustness.", Graph Neural Networks: Foundations, Frontiers, and Applications, 2022\
[E] Zügner et al. "Adversarial Attacks on Neural Networks for Graph Data.", SIGKDD, 2018\
[F] Zügner et al. "Adversarial attacks on graph neural networks via meta learning.", ICLR, 2019\
[G] Wu et al. "Adversarial examples for graph data: Deep insights into attack and defense.", IJCAI, 2019\
[H] Hussain et al. "Structack: Structure-based Adversarial Attacks on Graph Neural Networks.", HT, 2021\
[I] Zhan et al. "FHA: Fast Heuristic Attack Against Graph Convolutional Networks.", DS 2021\
[J] Yang et al. "Derivative-free optimization adversarial attacks for graph convolutional networks.", PeerJ Comput., 2021\
[K] Bojchevski et al. "Efficient Robustness Certificates for Discrete Data.", ICML, 2020\
[L] Murdoch et al. "Definitions, methods, and applications in interpretable machine learning.", PNAS, Vol. 116, No. 44, 2019\
[M] Ying et al. "GNNExplainer: Generating Explanations for Graph Neural Networks.", NeurIPS, 2019\
[N] Chapelle et al. "Semi-Supervised Learning", Adaptive Computation and Machine Learning, 2006\
[O] Xu et al. "Towards an efficient and general framework of robust training for graph neural network", ICASSP, 2020\
[P] Deng et al. "Batch Virtual Adversarial Training for Graph Convolutional Networks", arXiv:1902.09192, 2019\
[Q] Waniek et al. "Hiding individuals and communities in a social network.", Nature Human Behaviour, 2018\
[R] Wen et al. "Is Adversarial Training Really a Silver Bullet for Mitigating Data Poisoning?", ICLR, 2023\
[S] Tao et al. "IDEA: Invariant Causal Defense for Graph Adversarial Robustness", arXiv:2305.15792, 2023\
[T] Gasteiger et al. "Diffusion Improves Graph Learning", NeurIPS, 2019\
[U] Li et al. "Adversarial Attack on Large Scale Graph", TKDE, 2021\
[V] Zügner et al. "Certifiable Robustness and Robust Training for
Graph Convolutional Networks", SIGKDD, 2019\
[W] Li et al. "Spectral adversarial training for robust graph neural network.", TKDE, 2022\
[X] Mujkanovic et al. "Are Defenses for Graph Neural Networks Robust?", NeurIPS, 2022

Meta-review: The reviewers appreciate the authors' contributions to elucidating an important existing limitation on the definition and setting of GNN adversarial robustness under the transductive setting. However, in order to avoid potential confusion, I would encourage the authors to better distinguish the term/notation of "algorithm" and "model". The difference in classic learning problems might be blurred, but I do believe it's worth differentiating in this paper -- $f_\theta(G)$ is supposed to be a GNN model that takes a graph $G$ as input, along with the node features, and then output the label prediction for all the nodes. Thus, the model parameter refers to $\theta$ only, and it is unclear how one can encode the clean graph $G$ observed during training into the model parameter $\theta$. In contrast, the learning algorithm can output both a model $f_\theta$ and the clean graph $G$, and then use the clean graph $G$ during inference under the transductive setting.  

That being said, I share with the reviewers' opinion that this paper is a still good contribution to the community to clarify the limitation under the transductive setting, and I would encourage the authors to address the reviewers' comments and submit a revised version of the paper when preparing for the camera-ready version.
Decision: Accept (poster)