Robustness of Graph Neural Networks at Scale
Authors: Simon Geisler
Tobias Schmidt
Hakan Şirin
Daniel Zügner
Aleksandar Bojchevski
Stephan Günnemann
Venue: NeurIPS 2021 Poster (2021)
Keywords: Adversarial Robustness
Graph Neural Networks
Scalability
Adversarial Defenses
Adversarial Attacks

Abstract: Graph Neural Networks (GNNs) are increasingly important given their popularity and the diversity of applications. Yet, existing studies of their vulnerability to adversarial attacks rely on relatively small graphs. We address this gap and study how to attack and defend GNNs at scale. We propose two sparsity-aware first-order optimization attacks that maintain an efficient representation despite optimizing over a number of parameters which is quadratic in the number of nodes. We show that common surrogate losses are not well-suited for global attacks on GNNs. Our alternatives can double the attack strength. Moreover, to improve GNNs' reliability we design a robust aggregation function, Soft Median, resulting in an effective defense at all scales. We evaluate our attacks and defense with standard GNNs on graphs more than 100 times larger compared to previous work. We even scale one order of magnitude further by extending our techniques to a scalable GNN.

Robustness of Graph Neural Networks at Scale
Simon Geisler, Tobias Schmidt, Hakan Şirin,
Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann
Department of Informatics Technical University of Munich
{geisler, schmidtt, sirin, zuegnerd, bojchevs, guennemann]@in. tum,
Abstract
Graph Neural Networks (GNNs) are increasingly important given their popularity and the diversity of applications. Yet, existing studies of their vuinerability adversarial attacks rely on relatively small graphs. We address this gap and study how attack and defend GNNs at scale. We propose two sparsity- aware first-order optimization attacks that maintain an efficient representation despite optimizing over number of parameters which is quadratic in the number of nodes. We show that common surrogate losses are not well-suited for global attacks on GNNs. Our alternatives double the attack strength. Moreover, improve GNNs' reliability we design a robust aggregation function, Soft Median, resulting in an effective defense at all scales. We evaluate attacks and defense with standard GNNs graphs more than 100 times larger compared to previous work. We even scale one order of magnitude further by extending our techniques scalable GNN.
Introduction
The evidence that Graph Neural Networks (GNNs) are not robust adversarial perturbations is com- pelling [4 20) [50] However, the graphs in previous robustness studies are tiny. This worrying, given that GNNs are already deployed in many real-world Internet-scale applications 5 44
PGD PR-BCD
Menory
Tecls 100
For example,
Products
GB
PubMed 63 (19,717 nodes) is often considered to be a large-scale graph and around 20 of memory is required for attack based on its dense adjacency matrix. Such memory requirements are impractical and limit advancements of the field. In this work, we set the foundation for the holistic study of adversarial robustness of GNNs at scale. We study graphs with up to III million nodes for local attacks (i.e. attack- ing a single node) and 2.5 million nodes for global at- tacks (i.e. attacking all nodes at once). As turns out, GNNs scale also highly vulnerable to adversarial attacks. In Fig. provement of memory efficiency of our attack over a popular prior work for attacking a GNN globally. Analogous attacks, our effective defense scales graphs with 111 million nodes and beyond.
10a
10F
#Edges
Figure 1: GPU memory consumption for global attack with Projected Gradient Descent (PGD) 43 its quadratic extrapolation, and our Projected Randomized Block Coordinate Descent (PR-BCD) S 3) Both yield simi- lar adversarial accuracy. Beyond attacks, our defense $ 4) also scales to these graphs.
show the substantial im-
Scope. We focus on adversarial robustness w.r.t. structure attacks on GNNs for node classification
max
((f)(A,X)
(1)
Á st. | A-A-AA <l
with loss function L (or its surrogate L'), budget A, and fixed model parameters 6. The GNN
fo( A, X) is applied to graph G = (A, X) with node attributes X Rexd, the adjacency matrix
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

A E {0.1)** and m edges. We focus on evasion (test time) attacks, but our methods can be used in poisoning (train time) attacks [49] We distinguish between local attacks on a single node and global attacks that target a large fraction of nodes with shared budget A. We study white-box attacks since they have the most powerful threat model and can be used to understand the robustness w.r.t. "worst-case noise" of a model, as well as to assess the efficacy of defenses. For these reasons white-box attacks are important and practical from the perspective of a defender.
Broader impact. Since we enable the study of robustness at scale, which previously was practically infeasible, an adversary can potentially abuse our attacks. The risk is minimized given that we assume perfect knowledge about the graph, model, and labels. Nonetheless, our findings suggest that one should be careful when deploying GNNs, and highlight that further research is needed. To mitigate this risk, we must be able to evaluate it. We also propose a scalable defense that shows strong performance empirically but we urge practitioners to consider potential trade-offs, e-g. improving robustness at the expense of accuracy for different groups of users.
Contributions. We address three major challenges hindering the study of GNNs' adversarial robust- ness at scale and propose viable solutions including an extensive empirical evaluation: (I) Previous losses are not well-suited for global attacks on GNNs; (2) Attacks on GNNs scale quadratically in the number of nodes or worse; (3) Similarly, previous robust GNNs are typically not scalable.
(1) Surrogate loss. We study the limitation of state- of-the-rrt surrogate losses for attacking the 40 in S 2 Especially in combination with small/realistic budgets A and on large graphs, previous surrogate losses lead to weak attacks. In particular, Cross Entropy (CE) or the widely used Carlini- Carlini-Wagner loss K 3 are weak surrogates for such global attacks. Our novel losses that overcome these limitations easily improve the strength of the attack by 100% on common datasets. For larger graphs, this gap even becomes more significant.
accuracy of a GNN over all nodes R 1 17
27 41
(2) Attacks. Attacks solving discrete optimization problem easily become computationally infeasi- ble because of the vast amount of potential adjacency matrices (O(2"))) )). An approximate solution can be found with first-order optimization but then still optimize over quadratic number of parameters (n²). There is no trivial way to sparsify existing attacks as we need to represent each edge explicitly to obtain its gradient (i.e. space complexity O(n²)). Nevertheless, we overcome this limitation and propose two strategies to apply first-order optimization without the burden of a dense adjacency matrix. S 3 describe how add/remove edges between existing nodes based on Randomized Block Coordinate Descent (R-BCD) at an additional memory requirement of O (A)) Due to the limited scalability of traditional GNNs, also consider the case where we attack PPRGo [ scalable GNN. Here, we even obtain an algorithm with constant complexity in the nodes n.
(3) Defense. We propose Soft Median in 4 computationally efficient, robust, differentiable aggregation function inspired by Geisler et al. [8] differentiable sorting B1]. Using our Soft Median we observe similar robustness to [18], but with significantly lower memory footprint, which enables us to defend GNNs at scale.
by taking advantage of recent advancements in
2 Surrogate Losses for Global Attacks
During training and in first-order attacks, we ideally wish to optimize a target metric which is often discontinuous (e.g. accuracy and 0/1 loss Lo/1). However, for gradient- based optimization we commonly substitute the actual target loss by a surrogate L' Rs L (e.g. cross entropy for Lo/1). In the context of i...d. samples (e.g. images), a single example is attacked in isolation with its own budget, which is similar to a local attack for GNNs. When a single node's 's prediction is attacked, it is often sufficient to maximize the cross entropy for the attacked nodc/image (untargeted attack): CE p) = - log(pe-). ). where y is the label and p is the vector of confidence scores.
49 maximize the average CE to attack all nodes with a combined budget A. However, a loss like CE can be ineffective, particularly when the number of nodes is large in comparison to the budget 4/n + O. While experimenting on large graphs, we often observed that the CE loss increases even though the accuracy does not decline (see S B). As we can see in Fig. 2] this is due to CE's bias towards nodes that have a low confidence score. With CE and a sufficiently small budget A & n we primarily attack nodes that are already misclassified, which means that the classification margin dé minezee Po- Pe is already negative.
Many global attacks for GNNs R
2

---

All modes
All nodes
Class. margin
(clean)
(clean)
-1.0 S s S -0.67
All. modes (clean)
Alt. modes
-07 < e -0.33
(clean)
-0.3 < v 0.00
Anr. nodes
Alt. nodes (pert.)
0.0 -2 y 0:38
(pert.)
0.3 0.07
0.D
0.5
1.0
0.0
0.5
1.0
0.7 e. 1.00
Frequency
Frequency
(a) Loss: cross entropy
(b) Loss: tanh margin
Figure 2: Margin i of test nodes vs. attacked nodes, before ("clean"" and after perturbation ("per- turbed"".. We attack the PubMed graph (Table T) and a single-layer GCN with one percent of edges = 0.01) as budget. In stark contrast the tanh margin (b), the CE loss (a) spends lot of its budget on misclassified nodes (i.e. v < 0). See $ B for more variants and details.
Global attack. In contrast attacking a single image/node, a global attack on a GNN has to (I) keep house with the budget A and (2) find edges that degrade the overall accuracy maximally (i.e. target "fragile" nodes). Without additional information, intuitively, one would first attack low-confidence nodes close to the decision boundary. Hence, the surrogate loss should have minimal (maximally negative) gradient
+ 0+ (i.e. approaching & - from & 2 0). Moreover, if we solely want to lower the accuracy, then we can stop attacking a node once it is misclassified
Definition A surrogate loss L' for global attacks (I) should only incentivize perturbing nodes that correctly classified: 8c' f02- ly<c 0 and (II) should favour nodes close the decision boundary: 8C' /0z. 1wv < 86' /0z y, for any 0 < th < 1/1.
Since Eq. is general a discrete and non-convex optimization problem that is often NP-complete D 3. 38
we propose to study the surrogate loss under the subsequent simplifying assumptions. Note that in an actual attack other influences (e.g. node degree) are still considered while solving the optimization problem. Assumption 1: The set of attacked nodes is independent (their receptive fields do not overlap). Particularly on large graphs with small budgets, 4/n - O, deciding which node to attack becomes increasingly local decision since the receptive field becomes insignificant in comparison to the rest of the graph. Assumption 2: The budget required to change the prediction of node i depends (only) the margin: A, 9(1 (1x+))) for some increasing and non-negative function g(-). That is, the larger the margin Vú the harder it is to attack node i. As stated in Proposition I with these assumptions,
optimizer with surrogate loss compliant with Definition is also optimizing the 0/1 loss Coy1 (for proof see $ B.4.
Proposition 1 Let L' be the surrogate for the 0/1 loss Lu/1 used to attack a node classification algo- rithm fo A, X) with a global budget Suppose we greedily altack nodes in order of Jax,- (wo) S ac' /8z-- (1b1) S ... < 3c' /ax. (wi) until the budget is exhausted A < E1+1 A, Under Assumptions 1 & 2, we then obtain the global optimum of max A.. Alo foz1 (A, if L' has the properties (I) 0c /az/ li-co and (II) 8c' /0=/ Wwo < aL' /az-. byr for any 0 < vo < 11.
Even under the simplifying Assumptions 1 & 2, the Cross Entropy (CE) is not guaranteed to obtain the global optimum. The (CE) violates property (I) and in the worst case only perturbs nodes that are already misclassified (see Fig. 2). The Carlini-Wagner (CW) K [ loss CW min( minnmaxecyer 2, Z 0) violates property (II). is also not guaranteed to obtain the global optimum, i.e. CW loss lacks focus on nodes close to the decision boundary. In the worst case, attack with CW spends all budget on confident withsu flipping a single one.
We propose the Masked Cross Entropy MCE = 1 Eiev+ - log(p!") which fulfills both proper- ties by only considering correctly classified nodes V and, hence, reaches the global optimum under the stated assumptions. Empirically, for greedy gradient-based attack the MCE comes with gains of more than 200% in strength (see Fig. 6). Surprisingly, if we apply MCE to a Projected Gradient Descent (PGD) attack, we observe hardly any improvement over CE. We identify two potential reasons for that. The first is due to the learning dynamics of PGD. Suppose a misclassified node does
We simply write p fe X) omitting that belongs to specific node, i.e. Pe of node i. We also overload this with the logits/ / pre- pof-sof activation as fo X). See $ for overview of the notation.
3

---

not receive any weight in the gradient update, now if the budget is exceeded after the update it is likely to be wown-weighted. This can lead to nodes that oscillate around the decision boundary (for more details see $ B). A similar behavior occurs for to the Carlini-Wagner loss in e.g. Fig. B. (e).
In Definition 2 we relax properties (I)(II) and propose to overcome these limitations via enforcing confidently misclassified nodes, i.c. we want the attacked nodes to be at "safe" distance from the decision boundary. We propose the tanh of the margin in logit space, i.e. lanh margin = tanh maxefee* & zc.) ). It obeys Definition 2 and its effectiveness is apparent from Fig. For the empirical evaluation see /S 5 and for more results as well as details on all selected losses see S B In the appendix we also study further losses to deepen the understanding about the required properties. Additionally, in B.5] we give an alternative Proposition I for a relaxed Assumption 2 s.t. E[A,|vi] = s(kb,))
Definition 2 A surrogate loss L' for global attacks that encourages confident misclassification (A) should saturate lim L' < oo and (B) should favor points close to the decision boundary: oc' a 10z- lio < 06' /0// lbs < 0 for any vo < 11 < <1or or
<
1 <
voo < O.
3 Scalable Attacks
Beginning with [14 500, many adversarial attacks on the graph structure have been proposed. As discussed, brasee attacks such as (9] 41 49 50 aim for lower computational cost by approximating the corresponding discrete optimization problem. However, they optimize all possible entries in the dense adjacency matrix A which comes with quadratic space complexity ((n²). Since previous attacks come with limited scalability (c.g. see Fig. D. GNNs robustness on larger graphs is largely unexplored. First, we propose family of attacks that does not require a dense adjacency matrix and comes with linear complexity w.r.t. the budget A. Then, we further improve the complexity of our attack for scalable GNN called PPRGo
[
Related work. Li al. 26 evaluate their local adversarial attack SGA only on a graph with around 200k nodes and SGA is specifically designed for Simplified Graph Convolution (SGC) 400 Note that a two-layer SGC identical to Nettack's ' surrogate model. We consider arbitrary Graph Neural Networks and we even scale our global attack to graph ten times larger. With PPRGo we even outscale them by factor 500. Feng et al. [17 partition the graph to lower the attack's 's memory footprint but still have time complexity of (n ). Dai et al. [4] scale their reinforcement learning approach to a graph for financial transactions with 2.5 million nodes. In contrast to our work, they scale their local attack only using a tiny budget A of single edge deletion and only need to consider the receptive field of a single node. We scale our local attack to 11 1M nodes and allow large budgets A.
Large scale optimization. In some big data use cases, the cost to calculate the gradient towards all variables can be prohibitively high. For this reason, coordinate descent has gained importance in machine learning and large-scale optimization [39] Nesterov 22 proposed (and analyzed the convergence of) Randomized Block Coordinate Descent (R-BCD). In R-BCD only a subset (called block) of variables is optimized at time and, hence, only the gradients towards those variables are required. In many cases, this allows for a lower memory footprint and in some settings even converges faster than standard methods [30).
For clarity, we model the perturbations P E (0, 13"m explicitly (P,j = denotes an edge flip):
PE(0.1)mxx ΣPSA L(Jo(A @ P, P))
max
Here, @ stands for element-wise exclusive or and A denotes the edge budget (i.e. the number of altered entries in the perturbed adjacency matrix). Naively, applying R-BCD to optimize towards the dense adjacency matrix would only save some computation on obtaining the respective gradient. It still has a space complexity of 2n²) on top of the complexity of the attacked model because we still have to store up to n² parameters. Note that the Lu perturbation constraint with limited budget A implies that the solution will be sparse. We build upon this fact and in each epoch, in survival-of- the-fittest manner, we keep that part of the search space which is "promising" and resample the rest. Despite the differences, we simply call our approach Projected Randomized Block Coordinate Descent (PR-BCD) and provide the pseudo code Algo. I (a preliminary version appeared in 19). On top of the GNN, PR-BCI comes with space complexity of (()) where b is the block size (number of coordinates) since everything can be implemented efficiently with sparse operations. We typically choose A to be fraction of m and b > A, thus, in practice, we have linear overhead.

---

Vasilla GCN
Vanilla GDC
Media GDC
Algorithm 1 Projected Randomized Block
Coordinate Descent (PR-BCD)
0.75
Block size
1: Input: Gr. (A, X), lab. y. GNN fo(-), loss L.
Accuracy
Accuracy 0.6
2.0E 06
106
2: Parameter: budget A, block size b, epochs E
1,05 07
& Eres, heuristic lo(... ..... ). learning rate a
0.65
n² 3: Draw w/o replacement (0, 1,...,,... 13
4: Initialize zeros for pa E R²'
0.60
10 10a
108t
500
1000
5: for t E ( b3} do
Block size
Epochs C
6: y So θ X)
P: f 1-- are p
(a) Cora MT (n = 2.8k)
(b) arviv (n 1704)
8: Projection + 11 [eppeemoolli (p:)
Figure 3: Influence of block size on PR-BCD
9:
i. 4- i.-1
(dashed Lg PGD [X) with tanh margin loss and
10:
if S Ere. then maskes. + h(p:) P: Pr[maskess] + Resample à. (maskres
é = 0.1. (a) shows adv. accuracy with three-sigma
11:
error over five seeds. We resample Exes. 50
12:
13:
epochs and then fine-tune 250. (b) shows adv.
14:
P ~ Bermoulli(ps) P
accuracy over epochs with E b const.
15:
Return A P
PR-BCD. For Lo-norm PGD we relax the discrete edge perturbations P from {0, ()(xx)) to [0, 1](xx)) as proposed by Xu et al.
[3 Each entry of P denotes the probability for flipping it. In each epoch we only look at a randomly sampled, non-contiguous block of P of size b (line 3, line 10-13) and additionally ignore the diagonal elements (i.e. self-loops). If using an undirected graph, the potential edges are restricted to the upper/lower triangular n X n matrix. In each epoch t E {1,2,... J. p is added to / subtracted from the discrete edge weight (line 6). Note, we overload @ s.t. A, @ Pij = Aij + Pij if Ai = O and A. Pij otherwise. We use and P interchangeably while only corresponds to the current subset/block of P.,- After each gradient update (line 7), the projection Dic I A and that p E [0, 1] (line 8). In the end we draw b sample s.t. P {0, 1] (mxx)) via Bernoullipp) (line 14).
[[[[[ernoulli(p) S (p) adjusts the probability mass such that [[Bemoulli(p)
The projection Hg/Bemoulli p) (p) likely results in many zero elements, but is not guaranteed to be sparse (for details see $ C.I.p If has more than 50% non-zero entries, we remove the entries with the lowest probability mass such that 50% of the search space is resampled. Otherwise, we resample all zero entries in p. However, one also might apply more sophisticated heuristic h(p) which we leave for future work (see line 1 11). After Eres. epochs we fine-tune p. i.e. we stop resampling and decay the learning rate as in 4K) We also employ early stopping for both stages (1 S Eres and / >> Eres. with the epoch 1) such that we take the result of the epoch with highest loss L.
Block size b. With growing n it is unrealistic that cach possible entry of the adjacency matrix was part of at least one random search space of size, the number of mutually exclusive chunks of the perturbation matrix grows with ( and this would imply a quadratic runtime. However, as evident in randomized black-box box attacks (37, is not necessary to test every possible edge to obtain an effective attack. In Fig. 3 (a), we analyze the influence of the block size on the adversarial accuracy. On small datasets and over a wide range of block sizes b, our method performs comparably (or sometimes even better) to its dense equivalent.
As is apparent, with a constant search space
For larger graphs, we observe that the block size has stronger influence on the adversarial accuracy, However, as shown in Fig. 3 (b), one might increase the number of epochs for an improved attack strength. This indicates that PR-BCD successfully identifies the harmful edges to keep.
GR-BCD. As alternative to PR-BCD, we propose Greedy R-BCD (GR-BCD) which greedily flips the entries with the largest gradient in the block so that after E iterations the budget is met. It is even a little bit more scalable it does not require b > A (see C.2 for details such as the pscudo code).
Limitations. We solely propose approximate attacks that do not provide any guarantee on how well they approximate the actual optimization problem and, hence, only provide an upper bound on e.g. the adversarial accuracy. We also recommend monitoring the relaxation error. One could use certificates to get the respective lower bound, provided they were scalable enough. Even sparse smoothing 44 might be too slow since we need many forward passes. As our attacks rely on the gradient they also require that the victim model is (approximately) differentiable. Otherwise, the
5

---

approximation can become inappropriate. Moreover, we are limited by the scalability of the attacked GNN we discuss next. For the theoretical complexities of all studied attacks, we refer to [
Scalable GNNs. Up to now, we implicitly assumed that we have enough memory to obtain the predictions and gradient towards the edges. GNNs that typically process the whole graph "at once", are inherently limited in their scalability. Our PR-BCD attack is even applicable when operating at those limits (see experiments on Products in S 5).
To push the limits further, we now consider more scalable GNNs. Some notable scalable GNNs either sample subgraphs [ or, such as PPRGo [3] simplify the message passing operation. Next, we extend our PR-BCD
local attack on PPRGo with constant complexity including the (Soft Median) PPRGo (we introduce the Soft Median in S 4)
PPRGo.To scale to massive graphs effectively, we need to obtain sublinear/constam complexity w.r.t. the number of nodes. This severely restricts the possibilities of how one might approach a
global attack and is the reason why we now focus on local attacks (i.e. attacking single node i). For an L--aaer message passing GNN we need to recursively compute the I--hop neighborhood to obtain the prediction of a single node. This makes difficult obtain a sublinear space complexity (here including the GNNe-especially if one considers arbitrary edge insertions. In contrast, PPRGo [ leverages the Personalized Page Rank (PPR) matrix II a(I (1=a) -1 (row normalization) to reduce the number of explicit message passing steps to one (with feat. encoder Senc):
p = softmax [AGG [II fanc (xx)) V [v)
(3)
Differentiable PPR Update. For local attack PPRGo, we require differentiable update of the respective PPR Scores for an edge perturbation on a weighted graph. We achieve this using the Sherman-Morrison formula through closed-form rank-one update of row of the PPR matrix:
II VII 1+ +II
I. = II
(4)
where = a and, with degree matrix D. v= = (Dx + (A) A,, This suffices to attack incoming edges of a node and since everything differentiable (0C"/ap) do not need a surrogate model (common practice 226 36 50)) In C.3) we give details on the derivation and show how we can leverage the fact that PPRGo uses a top-k spars-ifa PPR matrix to obtain constant complexity ((bk) (assuming b < n and k < n). With A < b. our approach comes with no restriction on how we can insert or remove incoming edges of specific node. Other approaches such as
14 2
gain scalability via restricting the set of admissible nodes for edge perturbations.
4 Scalable Defense
To complete the robustness picture we now shift focus to defenses. Unfortunately, we are not aware of any defense that scales to graphs significantly larger than PubMed. Thus, we propose novel, scalable defense based on a robust message- message-passing aggregation, relying on recent advancements in differentiable sorting [T Our Soft Median not only comes with the best possible breakdown point of 0.5 but also can have a lower error than its hard equivalent for finite perturbations (see S D.3). Moreover, Soft Median performs similarly to the recent Soft Medoid [18], but comes with better computational complexity w.r.t. the neighborhood size, lower memory footprint, and enables us to scale to bigger graphs. We can also use this aggregation neatly in the PPRGo architecture resulting in the first defense that scales to massive graphs with over IIIM nodes (see Eq.
Background. We typically have the message passing framework of a GNN:
h (!)) (AGO(() { (Ap.. ( (uEN(
with neighborhood (e) N(v) Uv including the node itself, the I-th layer message passing aggre- gation ()) embedding (1) normalized adjacency matrix A, weights W and activation (!))
Related Work. Following Günnemann 20 we classify defenses into three categories: (1) pre-
4x 29 and (3) modifications of the architec- A6. 48) All these previous defenses were not evaluated on graphs substantially larger than PubMed. Note GNNGuard 46 was only evaluated on a subset of arXiv, covering 20% of the nodes and 6% of the edges. Even though our attacks lend themselves well for adversarial
processing 16
22
(2) training procedure I0C
ture 11 18
23
42

---

training but we leave it for future work due to the overhead during training. Instead, we build the observation of Geisler al. [8] that common aggregations (e.g. sum or mean) in Eq. are known to be non-robust. They propose a differentiable robust aggregation for AGG and call it Soft Medoid. It is a continuous relaxation of the Medoid and requires the row/column sum over the distance matrix of the embedding of the nodes in the neighborhood. Hence this operation has a quadratic complexity w.r.t. the neighborhood size and comes with a sizable memory overhead during training and inference.
Soft Median, Intuitively, the Soft Median is a weighted mean where the weight for each instance is determined based on the distance to the dimension -iies median T. This way, instances far from the dimension-wir wise median are filtered out. We define the Soft Median as
(6) with the distances G. = a - x.: and number of dimensions d. We use X as well as X inter- changeably. For single dimension, this closely resembles the soft sorting operator as proposed in [31] for the central element and can be understood as a soft version of the median. To apply it to median which can be computed efficiently for
MSootMMeiinn (X) = softmax (-e/Tvi) = X R arg mil || - -x'll,
multivariate inputs, we rely on the dimension practical choices of d. In contrast to the Soft Medoid, we do not require the distances between all input instances which makes the Soft Median much more efficient. Assuming d is sufficiently small, the Soft Median scales linearly with the number of inputs |N (v)l-
The temperature. The temperature parameter T controls the steepness of the weight distribution between the neighbors. In the extreme case as T - 0 we recover the instance which is closest the dimension-wise Median (i.e. arg m Median is equivalent to the sample mean. We observe a similar empirical behavior as Geisler et al. IS and we decide on temperature value in our experiments by grid search.
ex || - x' (). In the other extreme case T + co, the Soft
Breakdown point. For any finite T, our proposed Soft Median has the best possible breakdown point of 0.5 as we state formally in Theorem (for proof see SS D.I. Note that despite the lower complexity compared Soft Medoid, we maintain the same breakdown point:
Theorem Let X = fxI...., },} be a collection of points in Rd with finite coordinates and temperature T E [0, 0o). Then the Soft Median location estimator Eq. 64 has the finite sample
breakdown point of e" (JUSoft Median, X) = 1/ (asympt. lim 6" "SofMMddian
X) = 0.5).
We define the weighted Soft Median PwsM(X a) Cs o a) X
Weighted sum
Soft Medood
Soft Median
(7)
1.0
Relative La error
where s is the softmax weight of 6 obtained using the weighted dimension-wise Median, C normalizes s.t. Σ 8 soa- = Σ a, o is the element- wise multiplication, and a the edges weights Similarly to 18, we recover the message pass- ing operation of GCN 24 for T + 0c.
0.15
0.9
0.10
0.8
La
0.05
0.7
0.0
0.1
0.2
0.0
0.1
0.2
Empirical robustness. The optimal breakdown point only assesses worst-case perturbations. Therefore, in Fig. 4 we analyze the L2 distance in the latent space after the first message passing operation for clean vs. perturbed graph. Empirically the Soft Median has 20% lower error than the weighted sum of a GCN (we call it sum since the weights do not sum up to 1). While here the Soft Medoid seems to be more robust, this is not consistent with the adversarial accuracy values in S 5. Interestingly, the Soft Median can outperform its hard equivalent in terms of the finite error
Fract. pert. edges e
Fract. pert, edges e
(a) absolute bias
(b) relative bias
Figure 4: Empirical bias B(c) for the second layer of GCN with GDC preproc. 25 network under PGD attack with 1.2 distance We use = 0.2 and relative budget of 0.25.
show in D.3
Limitations. Our Soft Median has the best possible breakdown point which is a (well-established) indicator for robustness but does not prove adversarial robustness. As for most defenses, ours can provide a false sense of robustness. If possible, use attacks and certification techniques to verify the application-specine
efficacy. Similar to the Soft Medoid in [8] 52) we show that the Soft Median can improve the certified robustness in B D.4 Naturally, our Soft Median also comes with higher cost than e.g. a naive summation despite having the same asymptotic complexity. Nevertheless, the overhead seems to be reasonable as we show our experiments and combination with PPRGo one can mitigate the slightly higher memory requirements with smaller batch size.
7

---

Empirical Evaluation
In the following, we present our exper- iments (consisting of approx. 2,500 runs) to show the efficacy and seal- ability of our methods on the six graphs detailed in TTall Attacks: We benchmark
Table I: Dataset summary. For the dense adjacency matrix we assume 4 bytes per entry. We represent the sparse (COO) matrix via two 8 byte integer pointers and 4 bytes float value per edge. We highlight configurations above 30 GB.
GR- BRD and PR-BCD against PGD 43 greedy
Dataset
#Nodes
Size (dense)
Size (sparse)
Cora ML
2.8 k
35.88 MB
168.32 kB
FGSM (similar to Dai et al. [14]) as
Citeseer 28
3.3
43.88 MB
94.30 kB
well as DICE [37]. Defenses: Be- sides regular/vanilla GNNs
PubMed 33
19.7
1.56 GB
1.77 MB
arXiv 21
169.3
114.71 GB
23.32 MB
pare our Soft Median GDC/PPRGo
Products 21
2.4 M
23.99
2,47 GB
with Soft Medoid GDC GCN [6), RGCN 4S. and Jaccard
[ SVD
Papers 100M
21
111.1 M
49.34 PB
32.31 GB
GCN AD. For the Soft Median, follow Soft Medoid GDC [8] and diffuse the adjacency matrix with PPR/GDC 25 and use PPRGo's 's efficient implementation to calculate the PPR scores. For the OGB datasets we use the public splits and otherwise sample 20 nodes per class for training/validation We typically report the average over three random seeds/splits and the 3-sigma error of the mean. The full setup and details about baselines are given in For supplementary material including the code and configuration see httpps:/vvet htt///wwww.. in. tum. de/ daml haannllrrouussee trobustteesssss... of gnns at scale
Time and memory cost. We want to stress again that most of the baselines barely scale PubMed using a common 11GB GeForce GTX 1080 Ti (as we do). We only use a 32GB Tesla V100 for the experiments on Products with a full-batch GNN, since three-layer GCN requires roughly 30 GB already during training. Extrapolating the overhead on PubMed to the largest dataset, Papers 100M, traditional attacks and defenses would require roughly 1 exabyte (1018 bytes) while for ours 11 GB suffice. Our attacks and defenses are also reasonably fast. On arXiv (170 k nodes), we train for 500 epochs and run the global PR-BCD attack for 500 epochs. The whole training and attacking procedure requires less than 2 minutes, Moreover, one epoch on Papers 100M with the local PR-BCD attack takes less than 10 seconds. See F2 for further details and
E for theoretical complexities.
Surrogate Loss.
We illustrate the losses in Fig. 5, where we clustered the losses in three groups. (1)
incentivizing low margins: Cross Entropy CE and margin. (2) focusing on high-confidence nodes:
Carnini-Wagner CW, the (neg.) CE of the most-likely. non-target class NCE, and ELU Margin. (3) focusing on nodes close the decision boundary: MCE (ours) and tanh margin (ours). In Fig. 6 we see that the losses of category (3), or equivalently obeying the properties of Definition Definition 2] superior the other losses. For example, with MCE and FGSM the accuracy drops twice as much as with CE. A detailed discussion and mathematical formulation of all losses can be found in $ Additionally, we report further experiments backing our claims and discuss the losses' properties in more detail. Subsequently, we use MCE for greedy attacks and tanh margin otherwise.
Robustness w.r.t. global attacks. In Table global attacks on the small dataset Cora ML since most baselines do not scale much further. Our attacks as strong as their dense equivalents despite being much more scalable. In Fig. 7
present the experimental results for proposed
CE
margin
CW
NCE
elu margin
MCE
tanh margin
0.8
0.8
Adv. accurncy
sccuracy
Surrogate loss
0.7
0.7
0.6
0.6
0.5
0.5
0.1
-1
-1
0
1
-1
0
Frac. edges
Frac. edges
Logit margin max,zee Eet
(a) GR-BCD
(b) PR-BCD
Figure 5: Losses for the binary case. The losses are Figure 6: Attacking GCN Pubmed. The
grouped via their basic properties (see text).
lower the ady. accuracy the better the loss.
8

---

Table 2: Comparing attacks (transfer from Vanilla GCN) and defenses. We show the adversarial accuracy for c = 0.1 on Cora ML. and the clean test accuracy (last column). We only highlight the strongest defense as the attacks perform similarly. Our approaches are underlined. See F33 for more datasets, budgets, and adaptive/direct attacks.
Attack
FGSM
GR-BCI)
PGD
PR-BCD
Acc.
Soft Median GDC
0.769 0.002
0.765 + 0.001
0.758
0.002
0.752 + 0.002
0.824
0.002
Soft Median PPRGo
0.778 0.001
0.781 + 0.002
0.769
0.001
0.770 + 0.001
0.821
0.001
Vanilla GCN
0.641 + 0.003
0.622 1 0.003
0.662
0.003
0.645 + 0.002
0.827 0.003
Vanilla GDC
0.672 0.005
0.677 + 0.005
0.679
0.002
0.674 + 0.004
0.842 0.003
Vanilla PPRGo
0.724 0.003
0.726 + 0.002
0.002
0.704
0.001
0.700 + 0.002
0.826 0.002
Soft Medoid GDC
0.773 0.005
0.775 + 0.003
0.759
0.003
0.761 + 0.003
0.819 0.002
SVD GCN
0.751 + 0.007
0.755 + 0.006
0.719
0.005
0.724 + 0.006
0.781 0.005
Jaccard GCN
0,661 + 0.002
0.664 + 0.001
0.673
0.002
0.667
= 0.003
0.818 + 0.003
RGCN
0.654 + 0.007
0.665 + 0.005
0.671 0.007
0.664 + 0.004
0.819 + 0.002
Soft Median GDC
Vanilla GCN
Vanilla PPRGo
Soft Median PPRGo
Vanilla GDC
Soft Medoid GDC
Adv. accuracy
Adv. accuracy
Adv. accuracy
0.75
0.6
0.7
0.70
0.6
0.4
0.65
0.5
0.2
0.00
0.05
0.10
0.00
0.05
0.10
0.00
0.05
0.10
Frac. edges
Frac. edges
Frac. edges
(a) Pubmed
(b) Xrviv
(c) Products
Figure 7: PR-BCD (DICE dashed) on the large datasets (transfer) where the adversarial accuracy denotes the accuracy after attacking with budget A = em.
compare our PR-BCD attack on all baselines that fit into memory or can be trained within 24 hours on the bigger datasets. On the large products dataset, it suffices to perturb roughly 2% of the edges to push the accuracy below 60%, i.e. reaching the performance of an MLP 2TI. We conclude that GNNs on large graphs are indeed not robust (see also S F.5 Our defense Soft Median GDC and Soft Median PPRGo are consistently among the best models tested over all scales. For example with e 0.1, the accuracy of a Vanilla GCN drops by an absolute 20% while for the Soft Median PPRGo we only lose 5%. To fit our Soft Median GDC on Products into memory, we had reduce the number of hidden dimensions in comparison to its baselines. However, note that even a Vanilla GCN requires almost the entire memory of the 32 GB GPU. Despite the small sacrifice in clean accuracy, we already outperform most baselines for budget of > 0.01. We also faced similar scaling limitations for the Soft Medoid GDC baseline on arXiv. This highlights the lower memory requirements for our Soft Median. In $ F.3
present more exhaustive results and adaptive/direct attacks supporting the robustness of our detense but highlighting the importance of adaptiveness.
we compare the results of our local PR-BCD with Nettack on Cora ML (undirected). We define the budget A, = ed, and select the nodes for each budget s.t. A, 2 1. Similarly to Zügner et al. [50]. we apply the attack only to the 10 nodes with highest confidence, 10 with lowest, and 20 random nodes (all correctly classified). For more datasets and budgets see $ F.4 Our attack seems to be slightly stronger than Nettack on all architectures and budgets. Nettack and PR-BCD use a different strategy to make the original combinatorial optimization problem feasible (see S T). Nettack uses a linearized surrogate model to sclect the adversarial edges. Evidently, this leads to a weaker attack compared to relaxing the optimization problem as we proposed with PR-BCD. On the large datasets Products and Papers 100M (directed), we outperform the simple DICE baseline substantially, We compare to DICE since Nettack is not scalable enough. In comparison to the small datasets, the Vanilla GCN/PPRGo are extremely fragile
Robustness w.r.t. local attacks. In Fig. 8

---

Table 3: Attack success rate PR-BCD (ours) and SGA (26 on a Vanilla GCN and Vanilla SGC 40
The stronger attack is bold. For poisoning we retrain on the perturbed graph of an evasion attack.
Attack
PR-BCD
SGA 0.50
Frac. edges A. = rd.
0.25
0.50
1.00
0.25
1.00
Citeseer Cora ML
evasion
0.38 + 0.04
0.65 + 0.04
0.96 = 0.02
0.36
0.04
0.51
0.05
0.82
0.03
GCN
poisoning
0,46 1: 0.05
0.79 1 0.04
0.97 0.02
0.47
0.64
0.04
0.95
0.02
SGC
evasion
0,45 1: 0.05
0.57 1 0.05
0.97 = 0.02
0.37 0.04
0.43
0.05
0.95 1: 0.02
poisoning
0.50 + 0.05
0.66 0.04
0.96 0.02
0.47
0.05
0.62 0.04
0.97 0.01
GCN
evasion
0,42 +: 0.05
0.66 0.04
0.85 0.03
0.34
0.04
0.50 0.05
0.72 0.04
poisoning
0.53 + 0.05
0.78 + 0.04
0.94 0.02
0.54 0.05
0.76 0.04
0.93 0.02
evasion
0.39 + 0.04
0.62 :: 0,04
0.91
0.03
0.35 1:5:000 0.04
0.55 - 0.05
0.85 0.03
SGC
poisoning
0.49 + 0.05
0.77 - 0,04
0,92 0.03
0.49 + 0.05
0.74 0.04
0.97 1 0.01
arXiv
GCN
evasion
0.92 1: 0.03
1,00 : 0,00
1,00
0.00
0.38 0.05
0.90 0.03
0.98 0.01
poisoning
0.82 1 0.03
0.99 +: 0.01
1.00
+ 0.00
0.52 1 0.05
0.82 0.04
0.98 1 0.01
SGC
evasion
0.91 = 0.03
0.97 = 0.01
1.00
= 0,00
0.83 + 0.04
0.94 = 0.02
0.94 + 0.02
poisoning
0.91 + 0.03
0.97 + 0.01
1.00
+ 0.00
0.83 + 0.04
0.94 + 0.02
0.94 + 0.02
and much lower budgets A, suffice to flip almost every node's prediction. Our proposed defense Soft Median PPRGo on the other hand remains similarly robust as the small datasets. On Papers 100M with A; = 0.25, the Soft Median PPRGo reduces the attacker's 's success rate from around 90% just 30% (90% vs. % on Products with A, = 0.5).
PR-BCD
Soft Modian PPRCI
Netlock
Vanilla PPRGo
DICE
Vanilla GCN
1.0
Adv. margin
0.5
In Table 3. we compare to the SGA attack of Li et al. 226 that transfers the attacks from a SGC 10 sur- rogate. With our PR-BCD we attack the respective model directly. We follow SGA and obtain a poison- ing attack by applying the perturbations of an evasion attack to the graph before training. Our PR-BCD clearly dominates SGA-even on SGC. This demon- strates how generally applicable our PR-BCD is with- any modifications. We hypothesize that PR-BCD is stronger since, in contrast to SGA, it does not con- strain the edge perturbations to be within subgraph. Moreover, the large gap for GCN highlights the im- portance of adaptive attacks (i.e. no surrogate). Also in terms of scalability, we find PR-BCD to be supe- rior, even though SGA is efficient on graphs up the size of Xiv. However, on products, we observe that for SGC message passing steps we sometimes require more than 11 Gb and s 4 we typically require more than 32 Gb. However, our PR-BCD with PPRGo scales to graphs 2 magnitudes larger (Pa- pers100M) and requires less than GB (see S F.2]
-1.0
0.25
1.0
Frac, edges c, A. cd2
(a) Cora MI.
1.0
Adv. margin
-0.5
-1.0
0.25
Frac, edges e, A, ed.
(b) Products (left) & Papers 100M (right)
Figure 8: Adversarial classification margins ti of the attacked nodes. In (a), we com- pare local PR-BCD attack with Net- tack 500 on (undirected) Cora ML. In (b), we show the results on the (directed) large- scale datasets Products (2.5 million nodes) and Papers 100M (111 million nodes), respec- tively. Our Soft Medoid PPRGo resists the attacks much better than the baselines.
Conclusion
We study the adversarial robustness of GNNs at scale. We tackle all three of the identified challenges: (1) we introduce surrogate losses for global attacks that can double the attack strength, (2) we principally scale first-order attacks that optimize over the quadratic number of possible edges, and (3) we propose a scalable defense using our novel Soft Median which differentiable as well as provably robust. We show that our attacks and defenses are practical by scaling to graphs of up to 111 million nodes. In some settings our defense reduces the attack's success rate from around 90 to I %. Most importantly, our work enables the assessment of robustness for massive-scale applications with GNNs.
10

---

Acknowledgments and Disclosure of Funding
This research was supported by the Helmholtz Association under the joint research school "Munich School for Data Science MUDDS.
References
[1] M. Andriushchenko and M. Hein. Provably robust boosted decision stumps and trees against adversarial attacks. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019.
[2] A. Bojchevski and S. Günnemann. Deep Gaussian embedding of graphs: Unsupervised inductive learning via ranking. 6th International Conference on Learning Representations, ICLR, 2018.
[3] A. Bojchevski and S. Günneeann.. Certifiable Robustness to Graph Perturbations. Neural Information Processing Systems, NeurlPS, 2019.
[4] A. Bojchevski, J. Klicpera, and S. Günnemann. Efficient Robustness Certificates for Graph Neural Networks via Sparsity-Awer Randomized Smoothing. 37th International Conference on Machine Learning, ICMI., 2020.
[5] A. Bojchevski, J. Klicpera, B. Perozzi, A. Kapoor, M. Blais, B. Rózemberczki, M. Lukasik, and Günnemann. Scaling Graph Neural Networks with Approximate PageRank. International Conference on Knowledge Discovery and Data Mining, KDD, 2020.
[6] N. Carlini and D. Wagner. Towards Evaluating the Robustness of Neural Networks. IEEE Symposium on Security and Privacy, 2017.
[7] Chen, T. Ma, and C. Xiao. FASTGCN: Fast learning with graph convolutional networks via importance sampling. 6th International Conference on Learning Representations, ICLR, 2018.
[8] Chen, Y. Wu, X. Xu, Y. Chen, H. Zheng, and Q. Xuan. Fast gradient attack on network embedding. arXiv: 027977 2018.
[9] J. Chen, Y. Chen, H. Zheng, S. Shen, S. Yu, D. Zhang, and Q. Xuan. MGA: Momentum Gradient Attack Network. IEEE Transactions Computational Social Systems, 2020.
[10] J. Chen, X. Lin, H. Xiong, Y. Wu, H. Zheng, and Q Xuan. Smoothing Adversarial Training for GNN. IEEE Transactions on Computational Social Systems, 2020.
[11] L. Chen, J. Li, Q. Peng, Y. Liu, Z. Zheng, and C. Yang. Understanding Structural Vulnerability in Graph Convolutional Networks. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, Montreal, Canada, Aug. 2021. International Joint Conferences on Artificial Intelligence Organization.
[12] T. Chen, B. Xu, C. Zhang, and C. Guestrin. Training Deep Nets with Sublinear Memory Cost. arXiv preprint arXiv: KXV:1664400177 2016
[13] W. L. Chiang. Y. Li, X. Liu, S. Bengio, S. Si, and C. J. Hsieh. Cluster-GCN: An efficient algorithm for training deep and large graph convolutional networks. International Conference on Knowledge Discovery and Data Mining, KDD, 2019.
[14] H. Dai, H. Li, T. Tian, H. Xin, L. Wang, Z. Jun, and S. Le. Adversarial attack on graph structured data. 35th International Conference on Machine Learning, ICML, 2018.
[15] D. Donoho and P. J. Huber. The notion of breakdown point. In A Festschrift For Erich L. Lehmann. Wadsworth Statist./rrobab Ser., Wadsworth, Belmont, CA, 1983, 1983.
[16] N. Entezari, S. A. Al-Sayouri, A. Darvishzadeh, and E. E. Papalexakis. All you need is Low (rank): Defending against adversarial attacks on graphs. International Conference on Web Search and Data Mining, WSDM, 2020.

---

[17] B. Feng, Y. Wang, X. Li, and Y. Ding. Scalable Adversarial Attack on Graph Neural Networks with Alternating Direction Method of Multipliers. arXiv:2009.10233 [cs, stat], Sept. 2020. arXiv: 2009.10233.
[18] S. Geisler, D. Zügner, and S. Günnemann. Reliable Graph Neural Networks via Robust Aggregation. Neural Information Processing Systems, NeurIPS, (NeurIPS), 2020.
[19] S. Geisler, D. Zligner, A. Bojchevski, and S. Günneemann. Attacking Graph Neural Networks Scale. Deep Learning for Graphs al AAAI Conference on Artificial Intelligence, 2021.
[20] S. Günnemann. Graph neural networks: Adversarial robustness. L. Wu, P. Cui, J. Pei, and
L.. Zhao, editors, Graph Neural Networks: Foundations, Frontiers, and Applications, chapter 8. Springer, Singapore, 2021.
[21] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and Leskovec. Open Graph Benchmark: Datasets for Machine Learning Graphs. 2020.
[22] M. Jin, H. Chang, W. Zhu, and S. Sojoudi. Power up! Robust Graph Convolutional Network against Evasion Attacks based Graph Powering, AAAI Conference Artificial Intelligence. 2019.
[23] W. Jin, T. Derr, Y. Wang, Y. Ma, Z. Liu, and J. Tang. Node Similarity Preserving Graph Convolutional Networks. WSDM 2021 Proceedings of the 14th ACM International Conference on Web Search and Data Mining, 2021.
[24] N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. 5th International Conference on Learning Representations, ICLR, 2017.
[25] Klicpera, S. Weißenbbrger, and S. Günnemann. Diffusion Improves Graph Learning. Neural Information Processing Systems, NeurlPS, 2019.
[26] J. Li, T. Xie, L. Chen, Xie, X. He, and Z. Zheng. Adversarial attack on large scale graph. IEEE Transactions on Knowledge & Data Engineering, 2021.
[27] J. Ma, S. Ding, and Q. Mei. Towards More Practical Adversarial Attacks Graph Neural Networks. Neural Information Processing Systems, NeurIPS, (NeurlPS), 2020.
[28] A. K. McCallum, K. Nigam, J. Rennie, and K. Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 2000.
[29] Y. Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Optim., 22, 2012.
[30] Y. Nesterov and S. Stich. Efficiency of accelerated coordinate descent method on structured optimization problems. Siam J. Optim., 27, 2017.
[31] S. Prillo and J. Martin Eisenschlos. SoftSort: A Continuous Relaxation for the argsort Operator. 37th International Conference on Machine Learning, ICML, 119, 2020.
[32] J. Schuchardt, A. Bojchevski, J. Klicpera, and S. Günnemann. Collective robustness certificates. 9th International Conference on Learning Representations, ICLR, 2021.
[33] P. Sen, G. M. Namata, M. Bilgic, L.. Getoor, B. Gallagher, and T. Eliassi-Rad. Collective classification in network data. Al Magazine, 2008
[34] O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann. Pitfalls of Graph Neural Network Evaluation. / [cs, stat], June 2019, arXiv: 1811.05868.
[35] X. Tang, Li, Y. Sun, H. Yao, P. Mitra, and S. Wang. Transferring robustness for graph neural network against poisoning attacks. Conference Web Search and Data Mining, WSDM, 2020.
[36] Wang, M. Luo, F. Suya, Li, Z. Yang, and Q Zheng. Scalable attack on graph data by injecting vicious nodes. Data Mining and Knowledge Discovery, 34(5), 2020.
12

---

[37] M. Waniek, T. P. Michalak, M. J. Wooldridge. and T. Rahwan. Hiding individuals and commu- nities in social network. Nature Human Behaviour, 2(2), 2018.
[38] L. Weng, H. Zhang, H. Chen, Z. Song, C.-J. Hsich, L. Daniel, D. Boning, and I. Dhillon. Towards Fast Computation of Certified Robustness for ReLU Networks. In 35th International Conference on Machine Learning, ICML, July 2018.
[39] S. J. Wright. Coordinate Descent Algorithms. Mathematical Programming. 151, 2015.
[40] Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinherger. Simplifying Graph Convolutional Networks. In 36th International Conference on Machine Learning, ICML, May 2019.
[41] H. Wu, C. Wang. Tyshetskiy, A. Docherty, K. Lu, and L. Zhu. Adversarial examples for graph data: Deep insights into attack and defense. IJCAI International Joint Conference on Artificial Intelligence, 2019-Augus, 2019.
[42] T. Wu, H. Ren, P. Li, and J. Leskovee. Graph Information Bottleneck. Neural Information Processing Systems, NeurlPS, (NeurIPS), 2020.
[43] K. Xu, H. Chen, S. Liu, P. Y. Chen, T. W. Weng, M. Hong. and X. Lin. Topology attack and defense for graph neural networks: An optimization perspective. IJCAI International Joins Conference on Artificial Intelligence, 2019-Augus, 2019.
[44] R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec. Graph convo- lutional neural networks for web-scale recommender systems. International Conference on Knowledge Discovery and Data Mining, KDD, 2018.
[45] H. Zhang, T.-W. Weng, P.-Y. Chen, C.-J. Hsieh, and Daniel. Efficient Neural Network Robustness Certification with General Activation Functions. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2018
[46] X. Zhang and M. Zitnik. GNNGuard: Defending Graph Neural Networks against Adversarial Attacks. Neural Information Processing Systems, NeurIPS, (NeurIPS), 2020.
[47] Y. Zhang, S. Pal, M. Coates, and D. Ustebay. Bayesian Graph Convolutional Neural Networks for Semi-Supervised Classification. AAAI Conference on Artificial Intelligence, 33, 2019.
[48] D. Zhu, P. Cui, Z. Zhang, and W. Zhu. Robust graph convolutional networks against adversarial attacks. International Conference on Knowledge Discovery and Data Mining, KDD, 2019.
[49] D. Zügner and S. Günnemann. Adversarial attacks on graph neural networks via meta learning. 7th International Conference on Learning Representations, ICLR, 2019.
[50] D. Zügner, A. Akbareejad and S. Günnemann. Adversarial attacks neural networks for graph data, International Conference on Knowledge Discovery and Data Mining, KDD, 2018.
13


Reviews:
[{"review_id": "eOUYqvyuU7V", "reviewer": "Reviewer_hJTe", "summary": "This paper studies adversarial attack and defense of GNNs at scale. The authors investigate the relationship between surrogate losses and accuracy, and scalable attack and defense algorithms. Some theoretical intuitions and extensive empirical evaluation are provided to support the claims.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength\n- Overall, this paper is clearly-written. While this paper wraps a lot of content, the high-level overview in the Introduction makes it easier for the reader to parse the content.\n- As far as I know, adversarial attack and defense for large-scale GNNs have not been well-explored and this is an interesting topic. \n- I find the analysis of the surrogate losses very interesting. The insight that the loss should guide the attack to focus on the correctly-classified boundary points could be helpful for the development of future attack methods.\n- This paper has an extensive empirical evaluation.\n\n\nWeakness\n- The proposed attack is a white-box attack assuming almost everything (labels, gradients, etc) is available to the attacker. A white-box attack under the large-scale setup is rarely practical, which makes the proposed attack method less interesting.\n- The assumption 2 is very unrealistic. The budget needed to flip the prediction of a node depends on the node features and its neighborhoods. Assumption 2 (and the proof of Proposition 1) assumes a uniform function g across all nodes. This is impossible, even approximately. With that said, while the significance of Proposition 1 is weakened due to the unrealistic assumption, the two properties defined in Definition 1 are still intuitively desirable.\n- A table summarizing the theoretical computation complexity of the proposed methods and previous methods will be helpful.\n\nAdditional questions\n- The study of surrogate losses does not seem to be relevant to the scale of GNNs. Is there anything that I missed?\n- Could you elaborate on the reasons why MCE does not work well for PGD?\n- Property (II) and property (B) essentially indicate a \"diminishing-return\" for the decrease of loss when the margin grows larger. This seems to align with the results in [22]. However, in A.2 the authors state that they mismatch. Could you elaborate more on the reasons? Also, the authors mention in A.2 that \"our analysis suggests that the CW loss should be effective once the budget is large enough\", but I did not find the relevant analysis. Could you point out where it is located?\n\nMinor suggestions\n- The naming of \"budget-aware\" loss in Definition 1 is a little bit confusing, since the definition itself does not involve the budget. Losses of this type favor correctly-classified boundary points, and has a diminishing slope when going further from the boundary. A more straightforward name such as \"diminishing-slope\" loss would be more informative. \n- A typo: line 124, the subscript n should be i.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper has a good discussion on limitations and societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "M9nCcpvgMoI", "reviewer": "Reviewer_9yU5", "summary": "This paper studies the robustness of graph neural networks on a massive scale compared to the existing robustness work that focuses on smaller graphs, in terms of three perspectives: surrogate loss, attack, and defense. \n- The firstly proposed surrogate loss can be used to enhance the strength of adversarial attacks.\n- The authors propose the scalable attack method for large graphs, which is implemented with sparse operations for reducing space complexity by considering a subset of entire adjacency elements when optimizing networks.\n- Lastly, the authors propose the scalable yet robust function for aggregating neighboring information on graph neural networks, which is adopted from the previous Soft Medoid method for the scalable purpose.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n- Compared to existing robustness studies that mostly deal with smaller graphs, this paper provides valuable insights on robustness of large-scale graphs. Interestingly, the proposed attack methods can attack entire 2 million nodes at once. Also, the defense method can reduce the strength of attacks on large and even small graphs, while requiring minimal complexities. I believe this large-scale robustness framework is a good contribution to the graph neural network community, and can bring interesting follow-up work on a real-world scale.\n- This paper is well written and well polished, and especially most of the claims are supported with empirical results. Also, a theoretical definition of the global optimum of surrogate loss, and the proposed loss function under this theoretical ground are technically strong.\n- While this paper focuses on large-scale graphs, the proposed surrogate loss can be further used for general purposes, since it shows good performances on even small graphs.\n- The authors provide a well-structured source code.\n\n### Weaknesses\n- While the authors claim that the proposed Masked Cross Entropy and tanh Margin losses improve the strength of attacks more on larger graph cases, the empirical results do not support this. First of all, the results of surrogate loss in Figure 6 are obtained by the smallest graph in the paper. Also, additional experiments in the supplementary file (Figure 15) show that existing losses, such as NC and elu Margin, are more effective compared to the proposed losses on some datasets (CoraML and Citeseer with FGSM and arXiv ML with PR-GCN).\n- Regarding defense, while the proposed Soft Median coupled with PPRGo clearly shows good robustness performances, the Soft Median coupled with GDC is generally weak compared to the baseline, Soft Medoid coupled with GDC. I agree with effective scalability of the authors' method, but it would be better to clearly discuss the result and reason of degenerating performances of authors' one.\n\n### Related work\n- I am curious about why the authors do not experimentally compare their method against the existing large-scale adversarial attack method [1]. While Li et al. [1] only consider local attacks, it could be directly compared with the authors' local adversarial attack method in the Robustness w.r.t. local attacks paragraph of Section 5.\n\n### Clarity\n- I am confused about the relationship between density, perturbation, and margin in section 2 associated with figure 2. It would be better to have few explicit sentences for explaining the intrinsic meaning of the figure.\n- In figure 3 (b), the block size is most small for 1.0E+07. Is it correct?\n- It is hard to understand equation 6. There are no details on $\\pi$ function, encoder, and combination of PPRGo. It would be better to more formally explain it in the supplementary file, if there is a space issue.\n\n### Typo\n- In figure 8, the caption indicates (d), (e), and (f), while the actual figure only includes two sub-figures: (a) and (b).\n\n[1] Li et al. Adversarial attack on large scale graph, arXiv 2020.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors clearly outline the limitations and potential societal impact of their work, and I am completely satisfied with them.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}, {"review_id": "K4OIl3rnnkb", "reviewer": "Reviewer_P3zQ", "summary": "The contributions of the paper: \n\n1) study the drawbacks of cross-entropy loss in the global attack of GNNs and propose alternative losses;\n\n2) propose a scalable attacking algorithm based on the randomized block gradient descent algorithm. It also introduces a heuristic to enforce sparse adjacent matrix and avoid the computation on dense matrix;\n\n3) propose a more efficient defense method based on an existing method, Soft Medoid.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1. The major focus of this paper is to study the adversarial robustness of GNNs on a larger scale. This is important since most of the existing attack and defense methods for GNNs are limited to very small data. \n\n2. The instigation and discussion on the ineffective of CE loss in the global attack of GNNs are interesting. It points out that attacking methods based on CE loss might waste attacking budgets, which provides useful insight for the development of stronger attacking methods. \n\n3. The proposed scalable attacking method seems quite efficient and experiments support its effective and efficiency.\n\nWeakness:\n\n1. The author doesn't provide a sufficient explanation for the proposed tanh Margin loss so that this loss design is unclear. Moreover, it is unclear why PGD algorithm doesn't improve over CE. The explanation due to the learning dynamics of PGD and independence assumption  (line 129-133) are confusing and vague. It is better to make it more precise and clear.\n\n2. The proposed attacking algorithm is a bit heuristic and doesn't provide any theoretical justification.\n\n3. It is hard to understand the scalable defense in Section 4. The proposed Soft Median method is based on Soft Medoid but the paper doesn't provide sufficient detail to demonstrate the idea. Therefore, it is unclear how the proposed method improves the efficiency of Soft Medoid. In particular, note that the dimension-wise median has been explored and showed to be worse than Soft Medoid in Soft Medoid paper, which should be discussed. The idea of the differentiable relaxation of the median is unclear.\n\n4. Some important related works are missing. For example, it is stated that the authors are not aware of any defense that scales to graphs significantly larger than PubMed. However, the defense on datasets such as obgn-arxiv and DP has been explored in the paper \"GNNGUARD: Defending Graph Neural Networks against Adversarial Attacks\", which needs to be discussed and even compared.\n\nOverall, the paper provides insightful investigations on the attacking and defense of GNNs. The proposed methods push the research in this area to a much larger scale, which is a very important direction. However, the writing can be significantly improved to make every part more precise and clear.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "FzjO7HyGbV", "reviewer": "Reviewer_CQeL", "summary": "This paper addresses the problem of adversarial robustness for GNN regarding attack and defense on large graphs up to 100 million nodes. In terms of attack, they show that existing attack methods are weak for large graphs. To address this, they introduce the Masked Cross Entropy (MCE) which only considers correctly classified nodes on the attack. In addition, they also tackle the issue of handling large graphs which should be scaled with quadratic space complexity of adjacency matrix, and introduce the Projected Randomized Block Coordinate Descent (PR-BCD) based on Bernoulli sampling. In terms of defense, the authors propose the Soft median with differentiable relaxation of the Median. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality\n====\nIn this paper, the authors tackle the problem of GNN robustness in a large graph, which is important for GNN robustness but not addressed so far. This paper first points out the problem of existing attacks with their weakness in a large graph and suggests a theoretically guaranteed method with improved surrogate loss and scalable optimization method. This paper also provides the cue of scalable defense for a large graph.\n\nQuality\n====\nThe method sound convincing and the theoretical foundation seems solid. There are diverse comprehensive analyses that are helpful to understand the claim of the paper. The experimental setup covers the diverse sizes of graphs ranging from 2.8k to 111M against various attack and defense methods. \n\nSignificance\n====\nIn experiments, they show that their attack and defenses are reasonably fast and require much less memory that can cover sufficiently large graphs like Papers 100M. In quantitative analysis, they show that the proposed attack significantly drops the performance against other margin losses in Figure 6 and Table 2 and the proposed Soft Median defense resists the attacks much better than the baselines.\n\nClarity\n====\nThe problem and method are generally well-motivated and clear. However, the overall presentation is disappointing. \n- In methodology sections (Section 2,3,4), subsections are rarely used and most topics are divided by only paragraph and bold title. It makes the paper looks fuzzy. \n- There is no abstractive description of the overall methods. I suggest authors add the comprehensive figure to outline the entire method to help authors better understand the overall methods.\n- The caption of Figure 7 is insufficient and Figure 7 is not referenced in the main paper.\nI think most of the presentation issues are due to the page limit of the main paper. I hope it will be more clarified in revision.\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The presentation quality can be improved in revision, as noted in the Clarity section of the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}, {"review_id": "1kQpjQay5_Q", "reviewer": "Reviewer_1HMw", "summary": "The paper studies adversarial attacks against graph neural networks as well as adversarial robustness at scale. \nThe authors first propose two first-order optimization attacks, i.e., PR-BCD and GR-BCD. The authors then propose an empirical scalable defense based on soft median aggregation. Both attacks and defenses are evaluated on benchmark datasets and show their effectiveness. \n\nStrengths\n+The studied problem is important\n+Propose a novel attack loss function\n+Evaluation is extensive\n\nWeaknesses\n-The paper studies white-box attacks\n-Algorithm details are unclear\n-The proposed defense is empirical", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "—-Threat model\n\nThe paper studies white-box attacks, which is not practical from my perspective. \n\n—Algorithm details\n\nFrom Figure 2, both tanh margin and cross entropy spend a lot of budgets on misclassified nodes. What’s the takeaway of Figure 2? \n\nIs Assumption 1 satisfied when performing global attacks, as they aim to reduce the performance of all nodes and could largely perturb the graph (given enough budget) which involves a substantial number of nodes? \n\nWhat’s the key difference between the proposed PR-BCD attack in Algorithm 1 and the optimization-based attack in [36]? \n\nPR-BCD needs to sort the probability mass before removing entries with the lowest probability mass. Sorting a huge vector is time-consuming. How could this sorting be scalable to huge graphs?    \n\nHow is the PPR matrix calculated in huge graphs, as it needs to compute the inverse of a huge matrix? \n  \nWhat’s $\\pi(v)_u$ in Eqn (6)? \n\nMy main concern is that the proposed soft median based defense is empirical and does not have theoretical guarantees. As the paper mainly focuses “robustness” of GNNs, I doubt that empirical defenses provide a false sense of robustness.\n\n\n\n—Evaluation\n \nThe term “perturbed accuracy” makes me confused.  \n\nNo global attack results on Papers 100M. \n\n\n—Other comments: \n\nIn conclusion,  … our novel Soft Median which is differentiable as well as provably robust. => This is inaccurate.  \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitations of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles the adversarial robustness of large-scale GNNs, which is practically important but has been overlooked. The authors provide a novel observation that the conventional cross-entropy (and Carlini-Wagner) loss guides the attacker to attack nodes that are already misclassified when attacking large GNNs, which results in the waste of the computing budget. Then, the authors show that under certain assumptions, a budget-aware loss can achieve the optimal solution, and propose a realization of such surrogate loss, Masked Cross Entropy (MCE), which only considers correctly classified samples, and thus is more efficient. The authors further propose scalable attacks and a scalable defense mechanism which modifies the aggregation function in the message passing framework. The experimental validation of the proposed attacks and the defenses show that they are indeed effective, and efficient in terms of computation and memory cost. 

The following are the pros and cons of the paper mentioned in the initial reviews.

Pros
- The tackled problem of ensuring robustness of a large-scale GNNs against adversarial attacks, is an important yet unexplored problem. 
- The study of the drawbacks of the cross-entropy loss when attacking GNNs is both novel and interesting.
- The proposed surrogate loss, Masked Cross Entropy, is both novel and effective for attacking large-scale GNNs, and has a potential to be further explored for other adversarial defense problems. 
- The proposed attack and the defense methods are efficient and scalable, which makes the model practical.
- The paper is well-written and is accompanied with well-structured source code. 

Cons

- The proposed attack and the defense methods are heuristic and lack theoretical justification. 
- The assumption of white-box attack for large-scale GNNs is impractical.
- The assumption on the expected budget required to ensure the optimality of the solution with the budget-aware loss is unrealistic.
- The effectiveness of the proposed attacks are shown on a small-scale graph.
- Lack of discussion and experimental comparison against relevant baselines, such as Li et al. 20, which also considers defense against adversarial attacks on large graphs.  
- Missing memory and time complexities of the different types of attacks. 

While the initial reviews were a bit split, during the discussion period, the reviewers and the authors actively engaged in very thorough, constructive discussions. This cleared away many of the concerns from the reviewers, and the reviewers unanimously agreed to accept the paper at the end. The authors convinced the reviewers that the assumption of white-box attack is reasonable in the defender’s point of view, and acknowledged the reviewers’ arguments that the black-box attack could be more practical when considering the tradeoff between clean and robust accuracy. The authors provided a more detailed explanation of the assumption, asymptotic time and memory complexities, and detailed discussion and experimental comparison against Li et al. 20. The lack of strict theoretical guarantees for the proposed attacks and the defenses are not critical, as their effectiveness have been verified with extensive empirical analysis.

In sum, this is a strong paper that tackles a novel and practical problem, analyzes the problem with an existing approach, and proposes an effective solution backed up with both theoretical and empirical analysis, which makes it a clear accept. I praise the authors and the reviewers for their constructive and active discussions, and advise the authors to incorporate them into the revision, as well as the new results they provided in the responses. 
Decision: Accept (Poster)