Revisiting Robustness in Graph Machine Learning
Authors: Lukas Gosch
Daniel Sturm
Simon Geisler
Stephan Günnemann
Venue: ICLR 2023 poster (2023)
Keywords: graph neural networks
adversarial robustness
label propagation
node-classification
stochastic block models
Bayes classifier
non-i.i.d. data
graph learning
graphs
robustness

Abstract: Many works show that node-level predictions of Graph Neural Networks (GNNs) are unrobust to small, often termed adversarial, changes to the graph structure. However, because manual inspection of a graph is difficult, it is unclear if the studied perturbations always preserve a core assumption of adversarial examples: that of unchanged semantic content. To address this problem, we introduce a more principled notion of an adversarial graph, which is aware of semantic content change. Using Contextual Stochastic Block Models (CSBMs) and real-world graphs, our results suggest: $i)$ for a majority of nodes the prevalent perturbation models include a large fraction of perturbed graphs violating the unchanged semantics assumption; $ii)$ surprisingly, all assessed GNNs show over-robustness - that is robustness beyond the point of semantic change. We find this to be a complementary phenomenon to adversarial examples and show that including the label-structure of the training graph into the inference process of GNNs significantly reduces over-robustness, while having a positive effect on test accuracy and adversarial robustness. Theoretically, leveraging our new semantics-aware notion of robustness, we prove that there is no robustness-accuracy tradeoff for inductively classifying a newly added node. 

Published as a conference paper at ICLR 2023
REVISITING ROBUSTNESS IN GRAPH MACHINE LEARNING
Lukas Gosch, Daniel Sturm, Simon Geisler, Stephan Günnemann Department of Computer Science & Munich Data Science Institute Technical University of Munich (1.gosch, da sturm, 8 g.eesrer,, s s.guennemann)et.mm
ABSTRACT
Many works show that node-level predictions of Graph Neural Networks (GNNs) are unrobust to small, often termed adversarial. changes to the graph structure. However, because manual inspection of a graph is difficult, it is unclear if the studied perturbations always preserve a core assumption of adversarial examples: that of unchanged semantic content. To address this problem, we introduce a more principled notion of an adversarial graph, which is aware semantic con- tent change. Using Contextual Stochastic Block Models (CSBMs) and real-world nodes the prevalent perturba-
graphs, our results uncover: i) for a majority tion models include large fraction of perturbed graphs violating the unchanged semantics assumption; úi) surprisingly, all assessed GNNs show rvbr-robust that is robustness beyond the point of semantic change. We find this to be complementary phenomenon to adversarial examples and show that including the label-structure of the training graph into the inference process of GNNs signif- icantly reduces over-robustness, while having a positive effect on test accuracy and adversarial robustness. Theoretically, leveraging our new semantics-aware notion of robustness, we prove that there is no robustness-ccuuacy tradeoff for inductively classifying a newly added node."
INTRODUCTION
Graph Neural Networks (GNNs) are seen as state of the art for various graph learning tasks (Hu al.. 2020; 2021). However, there strong evidence that GNNs are unrobust to changes to the underlying graph (Zügner et al., 2018; Geisler et al., 2021). This has led to the general belief that GNNs can be easily fooled by adversarial examples and many works trying to increase the robustness of GNNs through various defenses (Günnemann, 2022). Originating from the study of deep image classifiers (Szegedy et al., 2014), an adversarial example has been defined as a small perturbation, usually measured using fp-norm, which does not change the semantic content (i.e. category) of an image, but results in a different prediction. These perturbations are often termed unnoticeable relating human observer for whom normal and an adversarially perturbed image nearly indistinguishable (Goodfellow et al., 2015; Papernot et al., 2016). However, compared to visual tasks, it is difficult to visually inspect (large-scale) graphs. This has led to fundamental question:
What constitutes a small, semantics-preserviie perturbation to a graph?
The de facto standard in the literature is to measure small changes to the graph's structure using the fn-pseudonorm (Zheng et al., 2021; Günnemann, 2022). Then, the associated threat mod- els restrict the total number of inserted and deleted edges globally in the graph and/or locally node. However, if the observation of semantic content preservation for these kind of per- turbation models transfers the graph domain can be questioned: Due to the majority of low- degree nodes in real-world graphs, small fo-norm restrictions still allow to completely remove significant number of nodes from their original neighbourhood. Only few works introduce mea- sures beyond f--ormm restrictions. In particular, it was proposed to additionally use different global graph properties as a proxy for unnoticeability, such as the degree distribution (Zügner et al., 2018), 8), degree assortativity (Li et al., 2021), or other homophily metrics (Chen et al., 2022). tum. www.ttmmm.eeeeeeee de/daml /revi s tinn- robustness/
Projecc page: https: / wwwww/ww.ccc

---

Published as a conference paper at ICLR 2023
While these are important first steps, the exact relation between preserving certain graph prop- erties and the graph's 's semantic content (e.g., node-categories) is unclear (see Appendix B). For instance, one can completely rewire the graph by iteratively interchanging the endpoints of two randomly selected edges and preserve the global degree distribution. As result, cur- rent literature lacks a principled understanding in their employed no- tions of smallness as well as robustness stud- ies using threat models only including provable semantics- semantics-preserving perturbations to a graph.
Average Structure Perturbations until CNN.Prodiction Changes
Seructure Perturbations
Semandic
100
Boudary
Changed
GCN
semantiv ties
SGC
10-
APPNP
GAT
Preserved
CAllva
semantics
GrGpSAGE
Node Degres
of crimantics-preservatiie
Figure I: Average degree-dependent node- classification robustness. Semantic boundary in- dicates when the semantics (i.e., the most likely class) of a node of a given degree changes on av- erage. Data from CSBM graphs². All GNNs show robustness beyond the point of semantic change.
We bridge this gap by being the first to di- rectly address the problem of exactly measur- ing (node-level) semantic content preservation in a graph under structure perturbations. Surprisingly. using Contextual Stochastic Block Models (CSBMs), this leads us to discover novel phenomenon: GNNs show strong robustness beyond the point of semantic change (see Figure 1). This does not contradict the existence of adversarial examples for the same GNNs. Related to the small degree of nodes, we find that common perturba- tion sets include both: graphs which are truly adversarial as well as graphs with changed semantic content. Our contributions are:
1. We define semantics-awart notion of adversarial robustness (Section 3) for node-level predic- tions. Using this, we introduce a novel concept into the graph domain: over-robustness that is (un- wanted) robustness against admissible perturbations with changed semantic content (i.e., changed ground-truth truth labels).
2. Using CSBMs, we find: i) common perturbations sets, next to truly adversarial examples, include a large fraction of graphs with changed semantic content (Section 5.1); ti) all examined GNNs show significant over-robustness to these graphs (Section 5.2) and we observe similar patterns on real- world datasets (Section 5.2.1). Using fn-norm bounded adversaries on CSBM graphs, we find a considerable amount of a conventional adversarial robustness to be in fact over-robustness.
3. Including the known label-structrre through Label Propagation (LP) (Huang al., 2021) into the inference process of GNNs significantly reduces over-robustness with no negative effects on test accuracy or adversarial robustness (Section 5.2) and similar behaviour on real-world graphs
4. Using semantic awareness, we prove the existence of model achieving both, optimal robustness and accuracy in classifying an inductively sampled node (Section 4. I), i.e., no robustness-accuracy tradeoff for non-i.i.d. data setting.
2 PRELIMINARIES
Let n be the number of nodes and d the feature dimension. We denote the node feature matrix X E Raxd the (symmetric) adjacency matrix A (0, 1) 1)nxm, and the node labels y {0, 1)" of which yr E 13'. / < n are known. We assume a graph has been sampled from a graph data generating distribution D,, denoted as A, D,. We study inductive node classification (Zheng al., 2021). Due to the non-i.i.d data generation, a node-clann ciads--lssifierr ff may depend its decision on the whole known graph (X, A. VL). As a result, we write fXX A, yL)v to denote the classification of node v. All GNNs covered in this work are function f(X, A) only depending on the node features X and adjacency matrix A. list of the used symbols and abbreviations can be found in Appendix A.
Label Propagation. We use label spreading (Zhou et al., 2004), which builts classifier f(A. vr. by taking the row-wise arg max of the iterate Ft oD 112 AD 1/2 Fr + (1 a)Y, with D being the diagonal degree matrix; Y E Raxe with Y.₁ = if < l and vf = j. otherwise Y,, = 0: and a E [0, 1.. Similar to Huang et al. (2021), we combine IPP and GNNs by replacing the zero-rows for > 1 in Y with GNN oofippredictions, effectively forming a function f(X, AL)).
CCBMMs parametrized as outlined in Section 5 using K 1.5 and weak attack.
2

---

Published as a conference paper at ICLR 2023
Ad Adversarial Robustness. We study (inductive) evasion attacks, that is an adversary A can produce perturbed graph (X, A) E A) given the clean data (X, A) with the goal to fool given node-classifier f(X, A, yr), + f(X, A, yr., on nodes v. The perturbation set B A) collects all admissible perturbed graphs, defined by the threat model. We focus on direct structure attacks (Zügner et al., 2018). This means A can remove or add most A E N edges for a target node v.
Data Model. We leverage Contextual Stochastic Block Models (CSBMs) (Deshpande et al., 2018) to generate synthetic graphs with analytically tractable distributions. It defines edge probabilities p between same-class nodes and between different-class nodes and node-features are drawn from a Gaussian mixture model. Sampling from a CSBM can be written as an iterative process over nodes E [n]: 1) Sample label y/i Ber ( (Bernoulli distribution). 2) Sample feature vector X,, 19: ~ ((2 T)μ, oI) with μ E Rd a E R. 3) For all j E [m],] < i sample A ~ Ber(p) Y: By and A Ber(g) otherwise, and set A., = A,, We denote this (X, A. y) CSBM To inductively add m nodes, one repeats the above process for = n n 1........ m. Fountoulakis et e.n."" (2022) show that depending on the distance of the means d(( d(,,4, f1). one can separate an easy regime, where a linear classifier ignoring A can perfectly separate the data and hard regime, defined by d(-p, 11) = Ko, with 0 K S O(Vlog where this is not possible. CSBMs are commonly used to study transductive tasks. Understanding the sampling process as an iteration extends their application to inductive node classification. For an alternative we call Contextual Barabási-Allan Model with Community Structure (CBA) see Appendix C. Appendix D discusses the model choices.
3 REVISITING ADVERSARIAN PERTURBATIONS
Given a clean graph (X, A. yy. and target node v. The perturbation set B(X, A) comprises all possible (perturbed) graphs (X, A). which can be chosen by an adversary A, with the goal to change the prediction of node classifier f. i.e., f(X, A, UL)s # f(x, yL)e. The prevalent works implicitly assume that every A) E B(X, A) preserves the node-level semantic content of the clean graph, i.e., the original ground-truth label of c. If we would have an oracle Qt which tells us the semantic content the known graph encodes about this assumption can be made explicit by writing 12(X, A, y1), ?(X, A, yL).. Usually, we do not have access to such an oracle. However, we can try to model its behaviour by introducing a reference or base node classifier g. Then, the idea is to use g to indicate semantic content change and thereby, define the semantic boundary (see Figure 1). Exemplary, 9 could be derived from knowledge about the data generating process. We do so in Section 4 and 5, where
the (Bayes) optimal classifier for CSBMs g. Note that labels themselves are often generated following a base classifier. Exemplary, this can be humans labelling selected nodes in graph to generate dataset for (semi-) supervised learning- Using reference classifier as proxy for semantic content enables us to make refined definition of an adversarial graph, which makes the unchanged- semanties assumption explicit:
Definition 1. Let f be a node classifier and a reference node classifier. Then the perturbed graph (X, E B(X, A) chosen by an adversary A is said to be adversarial for f at node w.r.t. the reference classifier if the following conditions are satisfied:
i. f(X, A, vt) = 9XX, A, Vt) i. 9(X mn. = -9(gg, A,,,,,A,,,,,,, yr).
(correct clean prediction)
(perturbation preserves semantics)
tii. A # 9(X, A. VL)
(node classifier changes prediction)
Definition 1 says that perturbed graph (X, A) E B(X, A) only then is adversarial, if (X, A) does not only change the prediction of the node classifier I (iii), but also lets the original label unchanged (ii). The first constraint (i) stems from the fact that if f and y disagree on the clean graph at node this should represent a case of misclassification captured by standard error metrics such as accuracy.
Suggala et al. (2019) use the concept of reference classifier to, in similar spirit, define semantics- aware adversarial perturbations for i.dd. data, with a focus on the image domain. However, what has not been considered is that the reference classifier allows to characterize the exact opposite behaviour of an adversarial example: a classifier f does not change its prediction for perturbed graph (X, A) even though the semantic content has changed. As this would mean that f is robust beyond the point of semantic change, we call this behaviour over-robustness:
3

---

Published as a conference paper at ICLR 2023
Definition 2. Let f be node classifier and g a reference node classifier: Then the perturbed graph AX E B(X, A) chosen by adversary A is said to be over-robust example for node w.r.t the reference classifier g if the following conditions are satisfied:
i. f(x,A, uL)e = g(XX,(XX0 A, yL)o
(correct clean prediction)
ii. gX, A1)) (X, A, y
(perturbation changes semantics)
ii. f(X,A, vL). = g(x, A, yt).
(node classifier stays unchanged)
If there exists such an over-robust example, we call f over-robust at node w.r.t. 9.
Definition is of particular interest in the graph domain, where perturbation sets B(X, A) often include graphs (X,A) A). which allow significant changes to the neighbourhood structure of v, but do not allow easy manual content inspection. Indeed, Section shows that all assessed GNNs are over-robust for common choices of B(X, A) for many test nodes e in CSBM graphs. A similar phenomenon for image data has been discussed by Tramèr et al. (2020a).
Now, let contrast over- to adversarial robustness. In Figure 2a the decision boundary of classifier fol- lows the one of base classifier except for the dotted line. The dashed area between f and g is a region of over-robustness for the blue class and of adversarial examples for the red class. In practice, the extent of the perturbation sets B-) is bounded. As result, us- ing adversarial examples, is only possible to measure the right boundary of the dashed area (see Figure 2b). The concept of over-robustness allows us to addition- ally measure the left boundary and hence, provides more complete picture of the robustness of f. Note that the blue points, using conventional adversarial ro- bustness, are judged robust in the whole of BB() even though their true class changed. Semantic-aware ad- versarial robustness allows to (correctly) cut off B(-) at the decision boundary of
B(a)
(a)
(b)
Figure 2: a) Decision boundary of classi- fier follows base classifier g except for the dotted line. b) Finite perturbation sets ((-) intersect only from one side with the dashed area. Over- and adversarial robust- ness are needed characterize robustness.
Contrary Figure 2a, region of over-robust examples cannot always be identified as region of adversarial examples for different data points. Denote g = (X, A) and collect all over-robust examples in set (G, B(G) and adversarial examples in it follows from Definition and 2 that Bo v) n B v) = Now, we find that in general, for given over-robust example G B(G) one can't 't always find a corresponding clean graph G' * G not in B(G) for which 9 is an adversarial example. It suffices to look at the case of I being constant: Proposition 1. Given J is conslant classifier, then B (G, v) is empty for every possible graph G.
(A v) B(G). Note that
This follows f can never fulfill both, item (i) and item (iii) in Definition 1. However, over-robust examples for f may exists. Every example in B()) will be over-robust, for which g changes its label for node This also shows that over-robustness can differentiate two classifiers, which have the same adversarial robustness, but one has learned a better decision boundary, while the other has not. We further develop other interesting conceptual cases in Appendix E.
4 BAYES CLASSIFIER AS REFERENCE CLASSIFIER
In the following, we derive Bayes optimal classifier to use a reference classifier g. Using the Bayes decision rule as is a natural choice, because, as shown below, it provides us with the information, if another class is now more likely based the true data generating distribution and hence, is the closest we can get to semantic content returning oracle Ω (see Section 3).
Assume that want to learn inductive node-classifier f on given, fully labeled graph (X, A,y) ~ D, with n nodes. We will focus on the most simple case classifying an induc- tively sampled node. We denote the conditional distribution over graphs with an inductively added
4

---

Published as a conference paper at ICLR 2023
node as D(X. A. v). Then, the target node corresponds to the newly sampled, n n 1-th node. How well our classifier f generalizes to the newly added node is captured by the expected 0/ 0/1-loss of f:
E (X.,V (((.A.))))((.A.)))) / (V6, S(X', A v))]
(1)
To derive Bayes optimality, we have to find an optimal classifier f for u, depending on (X','', y), minimizing (1). The following theorem shows that, similar to inductive classification for i.id. data, I" should choose the most likely class based on the seen data (Proof in Appendix F.1):
Theorem 1. The Bayes optimal classifier, minimizing the expected 0/ 0/1-loss (1), is f A ,), arg (0.1) Ply/ X', . A', y)-
4.1 ROBUSTNESS- ACCOSACY TRADEOFF
We show that given a Bayes optimal reference classifier g. our robustness notions (Definition 1 and 2) imply that optimal robustness, i.e., the non-existence of adversarial and over-robust examples for f. is possible while preserving good generalization in the sense of (1). Our argumentation for the non-i.i.d. graph data case takes inspiration from Suggala et al. (2019)'s study for i.i.d. data. In the following, we assume we are given a graph G' sampled from D(G, y). where G = (X, A) represents 1-th (inductively added) node. First, observe from Definition 1 that a graph 0 E B(G') is an adversarial example, iff g('', y). g(G', y) and fo/1 (f(g', g(' (() foz1 (f(',)) g(', ()),)))) = 1. In analogy to the generalization error (1), we define the adversarial generalization enror:
fully labeled training graph with nodes and labels y. Let v refer to the
Definition Let J be node classifier and g a reference node classifier. Assume G' is itself in B(G"). Then the expected adversarial 0/ 1-loss for an inductively added target node is defined as the probability that a conditionally sampled graph can be adversarially perturbed:
{an ((I'.)))) - lojz v).(((.)...9''.... (0o.) mhoe
E (9' (C)
max J (BB' s(C w).=g(G'.
(2)
From Definition it follows that a graph ğ' E B(g) is an over-robust example, iff f(ğ', y) f( ,y) and Eoy1 (g(5', yy). f v).) lo y)u f(g' .))) 1. Thus, we define:
Definition 4. Let f be a node classifier and g a reference node classifier. Assume G' is itself in B(G'). Then the expected over-robust 0/1-loss for an inductively added larget node defined as the probability that a conditionally sampled graph can be perturbed to be an over-robust example:
{ (ooz J (('',9))) loy1 (o( [(9"(
E (G' (('.)) (()(.)))(GG.))
max
(3)
g'EB(g") 1(0" /)
We denote the expected adversarial 0/1-loss as Lggd (J.g), and the expected over-robust 0/1-loss as Lgver gf. Minimizing only one of the robust objectives and disregarding the standard loss (1), may not yield sensible classifier. Exemplary, the adversarial loss (2) achieves its minimal value of 0 for a constant classifier. Therefore, we collect them in an overall expected robustness loss term:
Lgg (f.g).- Ai (f.g), + A (f.g).
(4)
where X 2 0 and A2 2 0 define how much weight we give to the adversarial and the over-robust loss. Now, want to find node-classifier I with small robust and standard loss. Denoting the expected 0/1-loss (1) as (g (f) this leads us to optimize the following objective:
arg min Lg + X (5.9). jER
(5)
where À 2 defines a tradeoff between standard accuracy and robustness and 71 represent a set of admissible functions, e.g. defined by chosen class of GNNs. Now, the following holds:
Theorem 2. Assume a set of admissible functions H. which includes a Bayes optimal classifier Bayes and let the reference classifier g be itself a Bayes optimal classifier. Then, any minimizer f E H (5) is a Bayes optimal classifier.
5

---

Published as a conference paper at ICLR 2023
Proof see Appendix F.2.1. Theorem 2 implies that minimizing both, the standard and robust loss for any À 2 O, always yields a Bayes optimal classifier. Therefore, optimizing for robustness does not tradeoff accuracy of the found classifier by (5) and hence, establishes that classifying an inductively tradeoff. Theorem 2 raises the important
sampled node does not suffer from a robustness-accuran question if common GNNs define function classes HGNN expressive enough to represent Bayes classifier for (1) and hence, can achieve optimal robustness. Theorem 3 in Appendix F.2.2 shows that only being minimizer for the robust loss Lgy (f, g) does not imply good generalization.
RESULTS
Using Contextual Stochastic Block Models (CSBMs) we measure the extent
Accuracy (Bayes)
of semantic content violations in common threat models (Section 5.1). Then, study werrrobusttnss in CSBMs (Section 5.2) and real-world graphs (Sec-
K
X
(X, A)
0.1 50.8%
89.7%
tion 5.2.1). In CSBMs, we use the Bayes optimal classifier (Theorem 1), de- noted g. to measure semantic change. The robustness of the Bayes classifier
0.5 59.0%
90.3%
1.0 68.4%
91.7%
defines the maximal meaningful robustness achievable (see Section 3). For re-
1.5 76.5%
93.1%
sults using the Contextual Barabási-Albes Model with Community Structure (CBA), we refer to Appendix I.
2.0 83.4%
94.7%
3.0 92.6%
97.4%
4.0 97.5%
99.0%
Experimental Setup. We sample training graphs with n 1000 nodes from a CSBM p.p.q in the hard regime (Section 2). Each element of the class mean vector j E Rd is set to Ko/2vá resulting in distance between the class means of Ka. We set a = 1 and vary K from close to no discriminative fea- tures K 0.1 to making structure information unnecessary K 5 (see Table 1). We choose p= 0.63 0.63% and = 0.15% resulting in the expected number of same-class and different-class edges for a given node to fit CORA (Sen et al., In2 2008). Following Fountoulakis et al. (2022), we set d= |n/In² (n)] 21. We use an 80% /20 train/validation split on the nodes. As usual in the in- ductive setting, we remove the validation nodes from the graph during training. At test time, we inductively sample 1000 times an additional node conditioned on the training graph. For each K, we sample 10 different training graphs.
5.0 99.3%
99.8%
Table 1: Mean ac-
curacy of the Bayes optimal classifier on test nodes v with (X, A) and with- out (X) structure information.
Models and Attacks. We study a wide range of popular GNN architectures: Graph Convolutional Networks (GCN) (Kipf & Welling, 2017), Simplified Graph Convolutions (SGC) (Wu et al., 2019a), Graph Attention Networks (GAT) (Veličković et al., 2018), GATv2 (Brody et al., 2022), APPNP (Gasteiger et al., 2019), and GraphSAGE (Hamilton et al., 2017). Furthermore, we study a simple Multi-Layer Perceptron (MLP) and Label Propagation (LP) (Zhou et al., 2004). The combination of a model with IP (Huang et al., 2021) is denoted by Model+ (see Section 2). To find adversarial examples, we employ the established attacks Nettack (Zügner et al., 2018), DICE (random addition of different-class edges) (Wanick et al., 2018), GR-BCD (Geisler et al., 2021) and SGA (Geisler al., 2021). Furthermore, we employ f--stron:: Connect to the most distant different-class nodes in feature space using f--norm. To find over-robust examples, we use a "weak" attack, which we call fz-weak: Connect to the closest different-clat nodes in Eg-norm. Theorem in Appendix F.3 shows that a strategy to change, with least structure changes, the true most likely class on CSBMs, i.e., an "optimal attack" against the Bayes classifier g, is given by (arbitrarily) disconnecting same-class edges and adding different-class edges to the target node. Therefore, the attacks DICE, fz-strong, and E2-weak have the same effect on the semantic content of graph. We investigate perturbation sets (.)+) (-) with local budgets A from 1 up to the degree (deg) of node 2, similarly to Zügner et al. (2018). Further details, including the hyperparameter settings can be found in Appendix H.
Robustness Metrics. To analyse the robustness of varying models across different graphs, we need to develop comparable metrics summarizing the robustness properties of a model f on a given graph. First, to correct for the different degrees of nodes, we measure the adversarial robustness of f (w.rt. g) at node e relative to v's degree and average over all test nodes V'3
Robustness v)
R(f g)
(6)
V
VE
deg(v)
Excluding degree 0 nodes. This is one limitation of this metric, however, these are very rare in the generated CSBM graphs and non-existing in common benchmark datasets such CORA.

---

Published as a conference paper at ICLR 2023
where 9 represents the Bayes classifier and hence, Robustness(ffis g, g.v) refers to the (minimal) number of semantics aware structure changes f is robust against (Definition 1). Exemplary. R)f.g) 0.5 would mean that on average. node predictions are robust against changing 50% of the neighbourhood structure. Using the true labels y instead of a reference classifier in (6), yields the conventional (degree-corrected) adversarial robustness, unaware of semantic change, which we denote R(f) == R(f. y). To measure over-robustness, we measure the fraction of conventional adversarial robustness R(f)) which cannot be explained by semantic-preserving robustness R(f. g): Rover R(f.g) R(f). Exemplary, Rover 0.2 means that 20% of the measured robust- ness is robustness beyond semantic change. In Appendix G we present a metric for semantic aware adversarial robustness and how to calculate an overall robustness measure using the harmonic mean.
5.1 EXTENT OF SEMANTIC CONTENT CHANGE IN COMMON PERTURBATION MODELS
We investigate how prevalent perturbed graphs with changed semantic content are for com- mon perturbation model choices. We denote the perturbation set allowing local budget of A edge perturbations as (-).) Table 2 shows the fraction of test nodes, for which we find per- turbed graphs in (-) with changed ground truth labels. Surprisingly, even for very mod- est budgets, if structure matters (K < 3), this fraction significant. Exemplary, for K=1.0 and (-), we find perturbed graphs with changed semantic content for 99.4 99.4% of the tar- get nodes. This establishes for CSBMs, a neg- the
Threat Models
K
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
(1(()
14.3
11.2
9.1
6.8
4.4
1.9
0.8
0.2
Bz(.)
35.9
31.2
25.7
19.8
14.1
6.2
2.2
0.7
Ba(.)
58.5
53.8
46.8
38.2
28.8
14.3
5.1
1.7
Ba(.)
76.5
73.0
66.6
58.1
47.0
25.7
9.8
3.4
Baeg
75.7
60.0
55.4
49.1
39.6
21.9
9.0
3.2
Bager( ())
100
100
99.4
92.9
80.5
51.7
24.8
9.1
Table 2: Percentage (%) of test nodes for which perturbed graphs in (-) violate semantic con- tent preservation. Calculated by connecting A dif- ferent class nodes (fa-weak) to every target node. For K>4.0 structure is necessary for good generalization (Table 1). Results using other at- tacks are similar (see Appendix J.3). Standard de- viations are insignificant and hence, omitted.
ative answer to a question formulated introduction: If structure matters, does com- pletely reconnecting a node preserve its seman- tic content? Similar to CSBMs, nodes in real- world graphs have mainly low-degree (Figure 12 in Appendix J.1). This provides evidence that similar conclusion could be drawn for certain real-world graphs. The examined B3 (-) subsume all threat models against edge-perturbations employing the fo-norm to measure small changes to the graph's 's structure, as we investigate the lowest choices of local budgets possible" and for these al- ready find a large percentage of perturbed graphs, violating the semantics preservation assumption.
Values in Table are lower bounds on the prevalence of graphs in B-(+) with changed semantic content. We calculate these values by connecting A different- nodes (fg-weak) to every target node and hence, the constructed perturbed graphs 9 are at the boundary of (.).). Then, we count how many č have changed their true most likely class using the Bayes classifier g. Thus, exemplary, a classifier f robust against (.) for CSBMs with 1=1.0, / classifies the found graphs the boundary of B.(.) wrong in 47% of cases. Therefore, f shows high over-robustness Rover
5.2 -VER-ROBUSTNESS OF GRAPH NEURAL NETWORKS
Section 5.1 establishes the existence of perturbed graphs with changed semantic content in common threat models. Now, we examine how much of the measured robustness of common GNNs can actually be attributed to over- over-robustness (Rover), i.e., to robustness beyond semantic change. As qualitative example, we study local budget of the degree of the target nodes Ba results on other perturbation sets can be found in Appendix J.4. Figure 3a shows the over-robustness of GNNs when attacking their classification of inductively added nodes. For K S the graph structure is relevant in the prediction (see Table 1). We find that in this regime, significant amount of the measured robustness of all GNNs can be attributed to over-robustness. Exemplary, 30.3% of the conventional adversarial robustness measurement of GCN for K = 0.5 turns out to be over-
'Global budgets again result in local dodge-peturrbttions however, now commonly allowing for way stronger perturbations than (.)++(()) to individual nodes. The number of allowed perturbation is usually set to small one- two-digit percentage of the total numher of edges in the graph. For CORA with 5278 edges, relative budget of 5% leads budget of 263 edge-changes, which can be distributed in the graph without restriction.
7

---

Published as a conference paper at ICLR 2023
Over-Robuste Wer-Robustness Rowa
1.0
0.4
0.8
0.3
GATvZ
GraplSACE
0.2
MLP+LD
GCN+IP
0.1
APPNF+LP
800's LP
GAIV2-LP
0.00
GOpbNAGR-TP
GAT+LP
0.1
2.0
3.0
4.0
1.0
2.0
4.0
5.0
(a) Local Budget A: Degree Node
(b) No Budget Restriction.
Figure 3: Fraction of Robustness beyond Semantic Change (Attack: f2-weak; Plot with Standard Er- ror). (a) large part of the measured robustness against B can be attributed over-robustness. (b) Applying week without budget restriction until it changes classifiers prediction. Note that over-robustness can be significantly reduced by label propagation and for (b) that some over-robust models, especially for high K, show high adversarial robustness (Appendix J.6).
robustness. LP achieves the lowest Rover and Rover significantly reduces when applied on top of a GNN. Exemplary, GCN+LP for K = 0.5 drops to Rover = 20.9%. Adding LP does not decrease test-accuracy (Appendix J.2) and often increases adversarial robustness as long as structure matters (see Figure 15 in Appendix J...
MI.P achieves maximal robustness. Thus, for attacks choosing perturbations independent of the attacked model, it provides an upper bound on the measurable over-robustness for particular node, as the complete budget will be exhausted without flipping an MIP's prediction. Exemplary, we measure 43% over-robustness for K = =.1 using weak. This means that for perfectly robust classifier against Begg for CSBM graphs with K = 0.1, 43% of measured conventional adversarial robustness against 22-weak is undesirable over-robustness. Note that all GNNs are close to this upper bound. Stronger attacks such as Nettack or GR-BCD still show that a significant part of the measured robustness is over-robustness (see Appendix J.5). Exemplary. Nettack performs strongest against SGC and GCN. However, for a GCN at K 0.5, still 11.4% of the measured robustness is fact over-robustness. An MLP for Nettack for 2 still shows 19.2% Rover, indicating that we can expect model robust against Nettack in B.)g(-) to have high Rover, For bounded perturbation sets Ba() (-), maximal over-robustness necessarily decreases if K increases, as the more informative features are, the more structure changes it takes to change the semantic content (i.e., the Bayes decision). Thus, less graphs in (-) have changed semantics (also see Table 2).
As positive take-away for robustness measurements on real-world graphs, we find that if the at- tack strong enough, robustness rankings derived from conventional adversarial robustness are consistent with using semantic-awand adversarial robustness (Appendix J.6.1 and J.6.5). However, the attack is weak, semantic-awareness awareness can significantly change robustness rankings (Appendix J.6.2 and J.6.3). For high K, some GNNs show high (semantics-aware) adversarial robustness (Ap- pendix 1.6.1) additional to high Rover, Interestingly. structure matters, the best harmonic mean robustness is in general achieved by MLP+LP (Appendix J.6), which also has the best non-trivial adversarial robustness, while achieving competitive test-accuracies. For Figure 3b, we apply 4-- weak without budget restriction until changes model's prediction. As a result, find that all GNNs (but not LP) have extensive areas of over-robustness in input space (compare to Figure 5 in Appendix E).
5.2. EVER-ROBUSTNESS ON WORLD GRAPHS
Table 2 shows that only few perturbations can change the semantic-content graph encodes about a target node. Additionally, structure matters (K < 3), the Bayes decision on CSBMs changes on average after at most changing as many edges as the target node's degree. This is visualized in Figure measured for K=1.5 and for other K in Figure 31 in Appendix J.8. It is challenging to derive ref- erence classifier for real-world datasets and hence, directly measure over-robustness. However, can investigate the degree-dependens robustness of GNNs and see if we similarly find high robust- ness beyond the degree of nodes. Figure 4 shows that majority of test node predictions of GCN on
8

---

Published as a conference paper at ICLR 2023
(inductive) Cora-ML (Bojchevski & Günnemann, 2018) are robust beyond their degree, by several multiples. The median robustness for degree nodes, lies at over 10 structure changes. Figure 30
in Appendix J.7 shows a similar plot for CSBMs. Results are obtained by applying a variant of fz-weak on a target node v. However, as Cora-ML is multi-class dataset, we ensure all in- serted edges connect to the same class C, which is different to
Structure Perturbations until
ECCN-Prediction Changes
90
80
the class of The vulnerability of a GCN to adversarial attacks likely stems from the lower quartile of robust node classifica- tions in Figure We conjecture rer-rooust for the upper quartile of highly robust node classifications. In Appendix K we show that combining the GCN with LP significantly reduces the upper extent of its robustness while achieving similar test accu- racy and show similar results on other real-world datasets.
70
60
50
Structure
30
40
20-
10
3
5
Node Digree
Figure 4: (Inductive) Cora-ML.
6 RELATED WORK
We now briefly discuss the most important related work and refer to Appendix for an extended dis- cussion. Semantics-aware adversarial robustness was theoretically studied by Suggala et al. (2019). Similarly, their work shows no (adversarial) abbustness-accuraa tradeoff, postulated among others by Tsipras et al. (2019). However, they only discuss i.i.d. data and focus on the image domain. A notion of overstability was investigated by Jia & Liang (2017) in natural language processing. How- ever, their studied perturbations still preserve the ground-truth answers predict by models. Tramèr et al. (2020a) discussed over-robustness under the name of invariance-based adversarial examples for the image domain. They did not use the concept of reference classifier, but used humans labeling oracle. To the best of our knowledge, we are the first to study a notion of over-robustness for graphs, and a robustness-accuracy tradeoff for non-i.i.d. data. For graphs, Dai et al. (2018) note the possibility of measuring semantics with a gold standard classifier and generate semantic- semantic-preserving preserving perturbations for graph classification on Erdös-Rénn Rényi graphs. Although no work has explicitly ad- dressed semantic content preservation for node classification, Zügner et al. (2018) proposed to ap- proximate unnoticeability by preserving the degree distribution; Li et al. (2021) introduced a metric for degree assortativity, but did not restrict perturbations; Chen et al. (2022) proposed node- and edge-centric homophily metric, but focused on adding malicious nodes instead of edges.
7 DISCUSSION AND CONCLUSION
We have shown that common threat models on CSBMs include many graphs with changed semantic content. As result, (full) conventional robustness leads to sub-optimal generalization and robust- ness beyond the point of semantic change. But we also found that the same threat models include truly adversarial examples. This dichotomy is caused by the low-degrees of nodes and the brittle- ness of their class membership to a few edges. Thus, it needs both notions, adversarial and over- robustness for a complete picture of robustness in graph learning. As real-world graphs also contain mainly low-degree nodes, this calls for more caution when applying fo-norm restricted threat mod- els. These thread models should not be an end to. but the start of an investigation into realistic pertur- bation models and works thinking about unnoticeability are positive directions into this endeavour. On CSBMs significant part of conventional robustness of GNNs is in fact over-robustness (with similar patterns on real-world graphs). This raises the question what kind of robustness do defenses improve on in GNNs?
Applying label propagation on top of GNN predictions has shown to be a simple way to reduce over-robustness while not harming generalization or adversarial robustness. Therefore, LP can be seen as defense against an attack, where the adversary overtakes a clean node (e.g., social media user) and, with its malicious activity, tries to stay undetected. This shows that not including the known labels in their predictions can be a significant limitation of GNNs. As visually inspecting graphs is difficult, synthetic graph generation models have proved to be an important tool to further principled understanding of graph attacks and defenses. Concluding, using semantics-awee aware bustmess, we have shown that for inductively classifying a newly sampled node, optimal robustness is achieveable, while maintaining high accuracy.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
The authors want to thank Bertrand Charpentier, Yan Scholten, Marten Lienen and Nicholas Gao for valuable discussions. Furthermore, Jan Schuchardt, Filippo Guerranti, Johanna Sommer and David Lüdke for feedback to the manuscript. This paper has been supported by the DAAD programme Konrad Zuse Schools Excellence Artificial Intelligence, sponsored by the German Federal Ministry of Education and Research, and the German Research Foundation, grant GU 1409/4-1.
REPRODUCIBILITY STATEMENT
The source code, together will all experiment configuration files of all our experi- ments can be found on the project page: https: /wwww CS cit tum /damm/ wwv.sitinggrobbstneee
Furthermore, we detail our hyperparameter search procedure and all searched through values of all our models and attacks in Appendix H. Details on the parametriza- tion of the used CSBMs can be found in Section 5, We performed all experiments trying to control the randomness much possible. We set random seeds and ensure no outlier phenomena by averaging over multiple seeds (including generating multiple CSBM graphs for each CSBM param- cterization) as detailed in Section 5 and Appendix H. The experimental setup of our real-world graph experiments is outlined Appendix H.1.
ETHICS STATEMENT
Robustness is an important research direction for the reliability of machine learning in real-world applications. A rigorous study counteracts possible exploits by real-world adversaries. We think that the benefits of our work outweigh the risks and see direct negative implications. However, there remains the possibility non-benign usage. Specifically, perturbations that are over-robust are likely less noticeable in comparison prior work. To mitigate this risk and other threats originating from unrobustness, we urge practitioners to assess their model's robustness (at best trying to include domain knowledge to go beyond 4o-norm perturbations and closer truly realistic threat models).
REFERENCES
Emmanuel Abbe. Community detection and stochastic block models: Recent developments. Journal of Machine Learning Research, 18(177):1 2018
Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1):47-97, 2002.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-of-distribution generalization. In International Conference on Machine Learning (ICML), 2021.
N. Binkiewiez, J. Vogelstein, and K. Rohe. Dovariate-assistee spectral clustering. Biometrika, 104(2):361-377, 2017.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsuper- vised inductive learning via ranking. In International Conference Learning Representations (ICLR), 2018
Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günnemann. Efficient robustness certifi- cates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference Machine Learning (ICML). 2020.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In Interna- tional Conference on Learning Representations (ICLR), 2022.
Jinyin Chen, Yangyang Wu, Xuanheng Xu, Yixian Chen, Haibin Zheng, and Qi Xuan. Fast gradient attack network embedding, arXiv: / 00091809.2222 02797, 2018.
10

---

Published as a conference paper at ICLR 2023
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 International Conference Learning Representations (ICLR), 2022.
Aaron Clauset, Cosma Rohilla Shalizi, and M. E. Newman. Power-law distributions in empirical data. SIAM Review, 6164),661-703, 2009.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International Conference Machine Learning (ICML), 2018.
Yash Deshpande, Andrea Montanari, Elchanan Mossel, and Subhabrata Sen. Contextual stochastic block models. In Neural Information Processing Systems (NeurIPS), 2018
Negin Entezari, Saba A. Al-Sayouri, Amirali Darvishzadeh, and Evangelos E. Papalexakis. All you need is low (rank): Defending against adversarial attacks graphs. In International Conference on Web Search and Data Mining ( (WSDM), 2020.
Kimon Fountoulakis, Amit Levi, Shenghao Yang. Aseem Baranwal, and Aukosh Jagannath. Graph attention retrospective. arXiv:2202.130600 2022.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemmnn. Combining neural networks with personalized pagerank for classification on graphs. In International Conference on Learning Representations (ICLR), 2019.
Simon Geisler, Daniel Zügner, and Stephan Günnemann. Reliable graph neural networks via robust aggregation. In Neural Information Processing Systems (NeurlPSS) 2020.
Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. In Neural Information Processing Systems (NeurIPS), 2021.
Simon Geisler, Johanna Sommer, Jan Schuchardt, Alcksandar Bojchevski, and Stephan Günnemann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In International Conference on Learning Representations (ICLR), 2022.
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Yoshua Bengio and Yann LeCun (eds.), International Conference Learning Representations (ICLR), 2015.
Stephan Günnemann. Graph Neural Nenworks: Adversarial Robustness, pp. 149-176. Springer
Nature Singapore, 2022.
Bruce Hajek and Suryanarayana Sankagiri. Community recovery in preferential attachment graph. IEEE Transactions on Information Theory, 65(11))6853-666 -67444 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gamett (eds.), Neural Information Processing Systems (NeurIPS), 2017.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference and Prediction. Springer, 2 edition, 2009.
Dan Hendrycks, Nicholas Carlini, John Schulman, and Jacob Steinhardt. Unsolved Problems in ML Safety. ar arXiv:2109.1 3916, 2021.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning graphs. arXiv:2005.00687, 2020.
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovee. Ogb-lsc: A large-scale challenge for machine learning on graphs. 103.::2003.044300 2021.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label prop- agation and simple models out-performn graph neural networks. International Conference on Learning Representations (ICLR), 2021.
11

---

Published as a conference paper at ICLR 2023
Robin Jia and Percy Liang. Adversarial examples for evaluating reading comprehension systems. In Conference on Empirical Methods Natural Language Processing (EMNLP), 2017.
Jonathan Jordan. Geometric preferential attachment in non-uniform metric spaces. Electronic Jour- nal of Probability, 18:1 15, 2013.
Brian Karrer and M. E. J. Newman. Stochastic blockmodels and community structure in networks. Physical Review E, 83(1), 2011.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference Learning Representations (ICLR), 2017.
Jay Lee, Manzil Zaheer, Stephan Günnemann, and Alex Smola. Preferential Attachment in Graphs with Affinities. In International Conference Artificial Intelligence and Statistics (AISTATS), 2015.
Chunguang Li and Philip K Maini. An evolving network model with community structure. Journal of Physics A: Mathematical and General, 38(45):9741, 2005.
Jintang Li, Tao Xie, Chen Liang, Fenfang Xie, Xiangnan He, and Zibin Zheng. Adversarial attack on large scale graph. IEEE Transactions on Knowledge and Data Engineering, 35:82-95, 2021.
Felix Mujkanovic, Simon Geisler, Aleksandar Bojchevski, and Stephan Günnemann. Are defenses for graph neural networks robust? In Neural Information Processing Systems (NeurIPS), 2022.
M. Newman. Mixing patterns networks. Physical Review E, 67(2), 2003.
John Palowitch, Anton Tsitsulin, Brandon Mayer, and Bryan Perozzi. Graphworld: Fake graphs bring real insights for gnns. Conference on Knowledge Discovery and Data Mining (KDD), 2022.
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as defense to adversarial perturbations against deep neural networks. In IEEE Symposium on Security and Privacy, 2016.
Jan Schuchardt, Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Collective robustness certificates: Exploiting interdependence in graph neural networks. In International Conference on Learning Representations (ICLR), 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data articles. Al Magazine, 29:93-106, 2008.
Arun Sai Suggala, Adarsh Prasad, Vaishnavh Nagarajan, and Pradeep Ravikumar. Revisiting ad- versarial risk. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations (ICL.), 2014.
Florian Tramèr, Jens Behrmann, Nicholas Carlini, Nicolas Papernot, and Jörn- Hennik Jacobsen. Fundamental tradeoffs between invariance and sensitivity adversarial perturbations. In Inter- national Conference on Machine Learning (ICMI), 2020a.
Florian Tramèr, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. In Neural Information Processing Systems (NeurIPS), 2020b.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In International Conference on Learning Representa- fions (ICIR). 2019.
12

---

Published as a conference paper at ICLR 2023
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liô, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.
Marcin Wanick, Tomasz Michalak, Talal Rahwan, and Michael Wooldridge. Hiding individuals and communities in a social network. Nature Human Behaviour, 2, 2018.
Felix Wu, Amauri Souza, Tianyi Zhang. Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In International Conference on Machine Learning (ICML), 2019a.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples for graph data: Deep insights into attack and defense. In International Joint Conference Artificial Intelligence (ICCAI) 2019b.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. In Interna- tional Joint Conference on Artificial Intelligence (IJCAI), 2019.
Kaidi Xu, Sijia Liu, Pin-V Yu Chen, Mengshu Sun, Caiwen Ding, Bhavya Kailkhura, and Xue Lin. Towards efficient and general framework of robust training for graph neural networks. In International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020.
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 learn- ing. Neural Information Processing Systems (NeurIPS) Track on Datasets and Benchmarks, 2021.
Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In Neural Information Processing Systems (NeurIPS), 2004.
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Conference on Knowledge Discovery and Data Mining (KDD), 2019.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference on Learning Representations (ICLR), 2019a.
Daniel Zügner and Stephan Günnemann. Certifiable robustness and robust training for graph con- volutional networks. Conference on Knowledge Discovery and Data Mining (KDD), 2019b.
Daniel Zügner,, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Conference Knowledge Discovery and Data Mining (KDD), 2018.
A
LIST OF SYMBOLS AND ABBREVIATIONS
[n] A A A
Set [I,...,n] Adversary
Adjacency matrix
Perturbed adjacency matrix
A'
Adjacency matrix of graph with an inductively added node
A'
Perturbed adjacency matrix of graph with an inductively added node Transpose of matrix A i-th row of matrix A
AT
ALe
AJ
Element of matrix A in i-th and j-th column Almost everywhere
a.e
B(X, A), B(.)
Perturbation set (possible perturbed graphs for given clean graph)
B-(+)
Perturbation set allowing A e N edge changes Perturbation set (-) with A degree of the target node Set of adversarial examples for node and clean graph g
Bdeg (.)
(G)
13

---

Published as a conference paper at ICLR 2023
(G
Set of over-robust examples for node and clean graph Bernoulli distribution
Ber
Bin
Binomial distribution
CBA
Contextual Barabási-Albert model with community structure Contextual stochastic block model
CSBM
d
Feature dimension
D
Data generating distribution
D(X, A,
Conditional distribution over graphs with an inductively added node
deg(v)
Degree of node
Investigated node classifier, e.g. a GNN
f
Bayes optimal classifier and/or classifier minimizing some loss Bayes optimal classifier
Bayes Prob
Harmonic mean between 1 Rover and Radv
g
Reference node classifier (see Section 3)
g
The graph without labels, i.e. AX
G G'
Perturbed graph without labels, i.e. A)
Sampled graph with an inductively added node without labels Perturbed graph with an inductively added node without labels Function class, i.e. of possible considered node classifiers Indicator function, 1 if cond evaluates to true, otherwise 0 Distance between the class means in CSBM / CBA in units 0/1-loss
H
I(cond)
K
fo/1
lp
p-norm
Lf)(f)
Expected 0/1-loss of node (see Equation 1)
Ggy (f.g)v
Expected adversarial 0/1-loss of node v (see Equation 2)
Lov (S:9)
Expected over-robust 0/1 0/1-loss of node (see Equation 3) Expected robust loss of node v (see Equation 4)
L (f.g)v
LP
Label propagation
The degree each newly added node in CBA should have Class mean vector in a CSBM CBA
p
Number of nodes
N(v)
Neighbourhood of node e Connection probability between same-class nodes in CSBM Connection probability between different-class nodes in a CSBM
P
R(f.9)
Degree-corrected, semantic-aware adversarial robustness of f w.r.t. g Degree-coree Pegree-corrected classic adversarial robustness of f (= R(f. y)).
R(f)
Note: R(g) represents the maximal achievable semantic- aware robust- ness w.r.t. g-
Rover
Fraction of R())) not explained by semantic-aware robustness R(J.9)
Radv
Fraction of R(g) achieved by semantic-aware robustness R(f.g)
a
Variance of the node features in CSBM CBA node in the graph. Usually, the target node. Semantic-conee content returning oracle Affinity CBA between classes ei and C2 Feature matrix
Ω
Weyez
X
X
Perturbed feature matrix
Feature matrix a graph with an inductively added node Perturbed feature matrix of a graph with an inductively added node Complete label vector of given graph (possibly unknown) Complete label vector of a graph with an inductively added node (pos- sibly unknown)
y'
Label of node
Known label vector of given graph
Table 3: List of most important symbols and abbreviations used in this work.
14

---

Published as a conference paper at ICLR 2023
B WHY GLOBAL GRAPH PROPERTIES DO NOT PRESERVE SEMANTIC CONTENT
Here we provide formal arguments, why the employed global graph properties and metrics by Zügnnrr et al. (2018), Li et al. (2021) and Chen et al. (2022) do not necessarily preserve or cor- relate with the semantic content in a graph. In Appendix B.I, we discuss the degree distribution preservation proposed by Zügner et al. (2018). Empirical results showing that preserving degree distribution has no effect on the over-robustness can be found in Appendix I. Appendix B.2 focus on degree assortativity proposed by Li et al. (2021) and Appendix B.3 on other homophily metrics proposed by Chen et al. (2022).
B.1 DEGREE DISTRIBUTION PRESERVATION
Assume we are given undirected graph. Choose two arbitrary edges = (i.j) and e2 = (u, v) from the set of edges in the graph. Without loss of generality, we assume < j and u < and binary classification. Now, we replace these two edges with (i, and (u,j). Because deg(i), (jg deg(u) and deg(v) are unchanged, the above procedure preserves the degree dis- tribution in the graph.
Assume now that we choose as edges e only same-class edges of class and of e2 only same-class edges of class 1. By repeating the above procedure for all possible (e1, e-)--airs we effectively rewiring& a homophilic graph until it becomes heterophilic, while preserving its degree distribution. Given structure is relevant for the semantics, this can't preserve semantics real-world graphs. For CSBMs and CBAs Theorem and Theorem prove that this rewiring is theoretically most effective to change the semantic content the graph encodes about its nodes. Similar arguments be made for different edges choices preserving the degree distribution but completely changing the original semantic content, e.g. to change different-class edges same-class edges repeating randomly choosing edge-pairs until the original graph structure has been completely destroyed.
Empirical results showing that preserving degree distribution has no effect on the over-robustness can be found in Appendix I. We also want to note that Zügner et al. (2018) requires the graphs to follow power-law degree distribution. However, not all graphs in practice satisfy this criterion (Clauset et al., 2009).
B.2 DEGREE ASSORTATIVITY
Degree assortativity, similarly to the degree distribution, can be orthogonal measure to semantic content preservation. This is as it too only depends on the degree of the nodes and hence, we derive perturbation scheme preserving the degrees of the incident nodes, provable preserving degree assortativity, but changing the semantic content.
Without loss of generality, coefficient (Li et al., 2021; Newman, 2003) is defined using the so called degree mixing matrix M. Mr represents the fraction of edges, connecting degree nodes with degree j nodes. For undirected graphs, M.j is symmetric and satisfies Eij Mr, = and E; Mi. = a. Degree assortativtiy is then defined as
again assume undirected graph. Then, the degree assortativity
r(a) Eiy ij(Mss - af)
0²
where a. denotes the standard deviation of the degree distribution a.
Now, choose two arbitrary edges e₁ (v1, U2) and and deg(v2) = deg(uz). If we replace these two edges with (Vi, uz) and (u,, 02), we preserve the degrees of the original nodes and hence the degree distribution a, the degree counts, as well as Mr,j- Therefore, r(a) stays unchanged. This perturbation scheme can be seen as a special case of the one defined in Appendix B.1. Li al. (2021) defines metric to measure unnoticeability, the expected (normalized) change in degree assortativity by a perturbation scheme, which they call Degree Assortativity Change (DAC). Because the above proposed perturbation scheme does not
(w1, u2) fulfilling deg(e)) = deg(un)
15

---

Published as a conference paper at ICLR 2023
change r(a), it has DAC of O. However, if 6j represents same-class edge for class 0 and eg a same-class edge for class 1, of which there will be many for lower degree connections such as degree nodes with degree 2 nodes or degree 2 nodes with degree 2 nodes, this perturbation scheme significantly rewires the graph by reducing homophily and increasing heterophily. This again is provably most effective perturbations
change the semantic content CSBMs/CBAs by Theorem 4/Thcorem 5. Note that DAC can be non-zero for semantic preserving operations on CSBMs/CBAs, exemplary when ej and e2 are same-class edges, both of the same class, but connecting nodes of different degrees.
shown
While Li et al. (2021) propose to measure an attacks effect on unnoticeability based on degree assortativity change, it does not propose to restrict the perturbation set through degree assortativity preservation or similar. Furthermore, is unclear, if one wants to preserve degree assortativity, what sensible values for the preservation would be. All attacks investigated by Li et al. (2021) show small DAC, i.e. on the order of a few percentage points assortativity change at most while being very effective attacks. For most datasets, exemplary Cora Pubmed, degree assortativity changes by less than 1%.
B.3 OTHER HOMOPHILY METRICS
Chen al. (2022) propose two homophily metrics for graph injection attacks, edge-centric ho- mophily and node-centric homophily. They argue that edge-centric homophily has several short- comings and focus their attention on node-centric homophily. Therefore, we do the same here. Node-centric homophily of a node u is defined as
hu = (anm(ra,xa))aa
JEN(u) Vddde X,:
(8)
where sim(-) is a similarity metric and chosen by (Chen et al., 2022) to be the cosine similarity.
Chen et al. (2022) analyse node-centric homophily changes when adding malicious nodes into the graph (graph injection attacks, GIA) and when adding/removing edges (graph modification attacks, GMA- representing the scenario studied in this work). For adding/removing edges, they similarly to our work, study an inductive evasion setting and use an attack which chooses to add/remove those edges having the largest effect on the attack loss based the gradient of the relaxed adja- cency matrix. Especially, they create perturbed graphs by applying either graph injection or graph modification attacks. They observe that GIA significantly changes the homophily distribution of graph given by Equation 8, while GMA has only very slight effects on the measured homophily distribution. Especially, GIA produces significant tail in the homophily distribution not seen in the original graph, which can be avoided by restricting the node-centric homophily change to not sur- pass certain thresholds. However, GMA does not produce these tails in the homophily distribution and hence, it is not clear how node-centric homophily can be effectively leveraged for preserving semantic content for GMAs. Therefore, node-centric homophily is a highly relevant and interesting metric for GIAs but its applicability to GMAs is limited.
Note that for node-centric homophily, is not as trivial as for the other graph properties to derive an attack preserving the metric. Especially, node-centric homophily is not a global but a local property and dependent on the continuous node features instead of the discrete node degrees. Therefore, informally show that our employed fe-weak attack, given limited budget, approximatively preserves the node-centric homophily with high probability for our synthetic graph models, while changing the semantic content of a node. Note that the feature distributions on CSBMs/CBAs, being a GauBian mixture model, overlap". Without loss of generality, we assume a binary classification setting with node u having class Assuming homophily, Equation 8 will result with a probability greater 0.5 in an average closer to the mean fcature vector of class 0 than class 1. If the number of nodes in the graph increases. there will, with high probability, be nodes of class with node features more likely based on class 0, i.e. more closer to the mean feature vector of class 0 than class in feature space. Most nodes have low degree and hence, they change their semantic content
Thiis is due to homophily and a majority nodes being low degree the real-world graph (Figure 8) and synthetic graphs (Figure 6).
'Nte that otherwise, the graph structure would not be necessary to separate the classes.
16

---

Published as a conference paper at ICLR 2023
by connecting only to few different class node (see Appendix J.8). If we now employ the Eg- weak attack, i.c. connect a target node of class to the closest nodes in feature space of class 1, given the graph is large enough, node-centric homophily will not significantly change into the direction of the mean of class 1, as we will with high probability find enough nodes closer to the mean of class than 1 to change the semantic content of the target node, before have to include nodes with features having a large effect on the node-centric homophily. Because semantic content for low-degree nodes often changes after or 2 edge insertions, can be argued that the node-centric homophily measure for fz-weak attack will not change significantly, before we already have measured significant over-robustnesss, given the graph is large enough.
C CONTEXTUAL BARABÁSI-ALBERT MODEL WITH COMMUNITY STRUCTURE
We use the Barabási-Albes model with community structure (Hajek & Sankagiri, 2019; Jordan, 2013) as (tractable) graph generation model generating a power-law degree distribution and ex- tend it with node features sampled from a Gaußian mixture distribution. In line with the CSBM, we call the resulting model Contextual Barabási-Allert Model with Community Structure (CBA).
Compared to CSBM, it requires the following additional parameters:
m: The degree of each added node (number of edges to insert with each added node).
Wpar;; The affinity between labels y; and yj. The affinity must be provided for each possible label pair and we collect the individual terms in the affinity matrix w. This replaces the parameters p, q in CSBM.
Furthermore, our initial graph consists of single node with self-loop. We implicitly assume that each added node also has one self-loop. Technically, we do not record the self-loops in the adjacency matrix and degree counts but just add them for the sampling probability calculation (see below). Thus, the resulting graph has no self-loops. Sampling from a CBA can now be written as the following iterative process over nodes =2. 2....,
1. Sample label y/: Ber(1/2) (Ber denoting the Bernoulli distribution).
2. Sample feature vector X,,lys N((2): 1)p, oI) with j E RRd. a R.
(1 (1+Ry)owm))
3. Choose m neighbours with probability p." = - (1+kmm Joney In other words, the neighbours are sampled from multinomial distribution. a node got sampled more than then we set As,, Note that this implies P[A.. 1/y] = 1 P(A,, = 0/y] = 1--Bin(O (0/mm p,m ())). (Bin denoting the binomial distribution). Furthermore, for all j < i, we set Aij = Aj.i-
once, i.c. Aij
We denote the above process process (X, A, v) CBA m. Inductively adding n'' nodes can be performed by repeating the above process for i n n ..... easy and hard regime for learning made by Fountoulakis al. (2022) is only based on the fact that the node features are sampled from GauBian mixture distribution and does not making use of how the graph structure generated. Hence, the observation for CSBM carries to a CBA.
n +n'. +,... Note that a separation into an
D ON THE CHOICES OF GRAPH GENERATION MODELS
There has been a recent trend in using synthetic graph models to generated principled insights into GNNs (see related work in Appendix L). As graph generation model choice, particularly prevalent are the contextual stochastic block model (CSBM) and the degree-corrected stochastic block model (DCSBM). First, we talk about limitation of CSBMs and we outline why the DCSBM is not applicable to the setting studied in our work. Secondly, we give an argument why we choose a CSBM compared to alternative graph models, in particular preferential attachment models.
The (C)SBM allows to generate graphs with same-class edge probabilities p and different-class edges probabilities q, which can be fitted to real-world graphs, such that generated nodes have in
17

---

Published as a conference paper at ICLR 2023
expectation equal (average) same-class degree different-class degree the real-world graph and they allow to configure the degree of homophily or heterophily. One shortcoming of stochastic block models is that they do not produce power-law degree distribution, which is often observed in practice. As a result, Karrer & Newman (2011) introduced a degree-corrected stochastic block model, which allows to fit its expected degree distribution to arbitrary empirical distributions found in real-world graphs. However, to correctly parametrize a DCSBM, one needs knowledge of the expected degrees of all individual nodes in the graph in advance. Then, its theoretic guarantees only hold for a graph of prespecified size and it does not define an iterative growth process. Thereby, its principled applicability is limited transductive learning' not matching our setting of inductive node classification. Classic stochastic block models, including the CSBM, do not suffer from this limitation, as a new node can added inductively with connection probabilities p and g, making CSBMs applicable for our study of inductive node classification.
Stochastic block models have a long history of study in the statistics and machine learning literature (Abbe, 2018) and are the canonical graph generation models to study tasks such community de- tection or clustering. This and their extension (CSBM) with node features sampled from a Gaußian mixture model (Binkiewicz et al., 2017; Deshpande et al., 2018), make them an appealing first choice of study for the graph neural network community compared to alternative models outlined below. Hence, (C)SBMs have been used the model of choice by many previous related work, among others by Fountoulakis et al. (2022); Baranwal et al. (2021) and Palowitch et al. (2022).
A well-known alternative type of graph generation models, which result in power-law degree dis- tribution, are based on preferential attachment of which the Barabási-Alberr (BA) model (Albert & Barabási, 2002) is a widely used instantiation. However, the BA and most of its later variations, do not show community structure making them not applicable to study node classification tasks. Indeed, we are not aware of any works using preferential attachment models to further our under- standing of graph neural networks and there are only few works which extent classical preferential attachment models to exhibit community structure. Notably, Hajek & Sankagiri (2019) investigate the properties of a classical BA model implanted with community structure, initially conceived in more general setting by Jordan (2013). Other works combining preferential attachment with com- munity structure are Li & Maini (2005) and Lee et al. (2015). For our work, we choose the model from Hajek & Sankagiri (2019) and, similarly to the CSBM, extend it with node features sampled from a Gaußian mixture distribution (CBA). We choose this model, it is based the classical BA model and compared to the work of Li & Maini (2005), is more concise and principled, with less additionally added parameters following more closely the original BA model, and enjoying deeper mathematical theory. Furthermore, compared to the work of Lee et al. (2015) it does not require to define a similarity function between individual nodes.
Note that all preferential attachment models with community structure suffer from having to fix the node degree of newly added nodes in advance and that higher degrees are only observed for the earlier nodes in the graph, making newly sampled nodes less representative of the whole graph compared SBM models. Because of these reasons, we think that using the above preferential attachment models with community structure can provide interesting additional information for the (inductive) study of GNNs, but cannot substitute for using CSBMs.
Furthermore, note that even though CSBM does not produce a power-law degree distribution, it still fulfills the important property that a majority of nodes have low degree and its degree distri- bution visually is not dissimilar to what we find in real-world graph (compare with Figure 12). Furthermore, Clauset et al. (2009) show that not all graphs in the real-world follow a power-law degree distribution.
"In DCSBM edges are sampled from Poison distribution allowing multi-edges in the graphs. This has to he corrected to fit many real-world graphs but in doing one violates the exact matching of the expected degree distribution to real-world graph.
18

---

Published as a conference paper at ICLR 2023
E CONCEPTUAL DIFFERENCES BETWEEN OVER- AND ADVERSARIAL ROBUSTNESS
Figure 5a shows the decision boundary of classifier f following the one of base classifier except for the dotted line. The dashed region between f's and g's decision boundary is a region of over-robustness for the blue class and region of adversarial examples for the red class.
Low Data Likelinood
9
B(o)
B(a)
(a)
(b)
(c)
(d)
Figure 5: Conceptual differences between over- and adversarial robustness. a) The decision bound- ary of classifier / follows the one of base classifier except for the dotted line. b) Finite perturba- tion budgets induce bounded perturbation sets B(-) intersecting only from one side with the dashed area. c) The red class is not seen because it lies in low data likelihood region. d) Zoomed: A node whose perturbation set includes a region adversarial and over-robust examples.
Note that in Figure 5b, using the classical concept of adversarial robustness, perturbed examples of blue datapoints crossing the decision boundary of y but still in B(-) will be judged adversari- ally robust. Therefore, they may be used to provide a learning signal for f to further solidify its insensitive decision boundary. Using our refined concept of adversarial robustness, the set of potentially adversarial examples B-)) is (correctly) cut off at the decision boundary of g.
In Figure 5a it is assumed that datapoints on both sides of the decision boundary have been sam- pled. This may be likely if every datapoint in the input space has a comparable sampling probability. However, practice there are regions of high and low data likelihood and hence, it could be that dat- apoints on one side of the dashed regions have not been sampled as exemplified in Figure 5c). There, result, only the
dashed line indicates the transition from high to low data likelihood area. concept of over-robustness can capture the misbchaviour of the classifier f. The reverse scenario is also possible in which only the examples the right class are sampled and the left class is in a low likelihood region. Indeed, in our results (see Section 5.2), there are some cases where both high adversarial and over-robustness, exactly fitting the scenario visualized in Figure 5c. Note that it makes sense robustify classifier even against low-likelihood events in safety-critical scenarios correct behaviour for unusual or rare events is crucial (Hendrycks et al., 2021).
measure
intricate case. Disregarding the base classifier g would lead wrongly interpreting every example above the decision boundary of f as adversarial. With our refined no- tions, it is possible correctly identify the adversarial region above f until g, the over-robust region as below the decision boundary of f but right of g and the correctly classified area in the top-right.
Figure 5d zooms in to
PROOFS
F.I BAYES CLASSIFIER
We proof Theorem by deriving the base classifier for multi-class node classification with C classes. Theorem then follows as special case by setting C' - 2. We restate Theorem for multiple classes:
Theorem 1.
The Bayes optimal classifier, minimizing the expected 0/ 0/1-loss (1), is fX''', A' Al,)) = argmaz Ply X A', y).
je (O.....CC-1)
19

---

Published as a conference paper at ICLR 2023
Proof. Lets denote by æ-, all elements of vector except the i-th one. First, note that D(X, A. from which we sample (X', ,A,y'') defines conditional joint distribution"
A' X.A. v) P(V,IX' A', X,A, v) A'', P/ A', P[X', A', X, A, P'V,XX' A P A.
(9)
where the first line follows from the basic definition of conditional probability, the second lines from the definition of the inductive sampling scheme (i.e., y/_,, y. and X' and A' containing X and A), and the third line from Plyl X, A, y] 1. Thus, we can rewrite the expected loss (1) with respect to these probabilities as
E (/ A A. 1o/1l/61 (X))A,,))))
oy (X /oo//////./oo/ f(X' A' v)ol]
(10)
=EXAAXXAV
Σ
(k/ J(X', A', ,)))) Ply! = k| A',y)
(11)
The following argument is adapted from Hastie et al. (2009). Equation (11) is minimal for a classifier f", if it is (point- (point-wise) minimal for every (X', y), This means
(',
argmin jE(o....CC-I1
Roz1 (k. -PP. k|X', Al
argmin SE(O....C-1)
T[k 0) Ply/ = A|X', A',y)
argmar SE(0....C-1)
Ilk 5] Ply = ,''''A''' A',w)
(12)
km
argmar (E(0...CC-1)
Ply x A',
(13)
where line (13) follows from fact that in the sum of line (12), there can only be one non-zero term. Equation (13) tells us that the optimal decision to choose the most likely class. Due to ('''' = argmar P[p|'', A', vl minimizing (11) it also minimizes the expected loss (1) (o(1).)
and hence, is Bayes optimal classifier.
F.2 ROBUSTNESS-ACCURAN TRADEOFF
F.2.1 THEOREM 2
For the proofs of Theorem and Theorem 3, we assume that the of cases where the two classes are equiprobable has measure zero. This is a mild assumption for instance satisfied in contextual stochastic block models.
For convenience we restate Theorem 2:
Theorem 2. Assume set of admissible functions H. which includes a Bayes optimal classifier Bayes and let the reference classifier g itself a Bayes optimal classifier. Then, any minimizer f E H (5) is a Bayes optimal classifier.
'Note that actually deal with discrete-contimuous joint distribution.
20

---

Published as a conference paper at ICLR 2023
Proof. The proof strategy is mainly adapted from Suggala et al. (2019). Let Bayes H. and be Bayes optimal classifiers. Assume f is minimizer of (5). Further, assume that (g', , y) disagrees with ( yy for a set of graphs g' ~ D(G. y) with non-zero measure. Note that a Bayes optimal classifier follows the decision rule arg max Ply, = 5|9', y] (see Theorem I). $E(0,1)
We assume that the set of cases where there are two more maximal, equiprobable classes has measure zero. Then, the Bayes Decision rule unique on the support of D(G.y). Therefore, Bayes y) g(g', y) a.e
We will show that the joint expected loss (5) is strictly larger for f than J Bayes We start by showing that the standard expected loss (f Lg Bages
(f Lg (faayss) E (G' (()..)))((.)))) ( (o// ())) - f0/1 Bayea (g': .y)))
Egiig. wl (Wb. (" .v)) ) la/1 (W'r f Bayes (G', y),)]]
(14)
EggiG..
E w.T # (((",,)))) -yglo' au [T F B'ayes (I' .v))]]]
(15)
Egig.
[Ply +
yl Ply, * fnayes v) yl1
(16)
(17)
Line 14 follows from rewriting the conditional joint distribution defined by D(G, y) (see Equation (9)). Line 15 follows from the definition of the fo/1-lost and the linearity of expectation. The last line 17 follows from the Bayes optimal classifier being defined as a pointwise minimizer of the prob- ability terms in line (16) and the initial assumption of f (G', y), disagrecing with Bayer (9', y), for a set of graphs with non-zero measure.
Now, we investigate the expected robust 0/1- lossss for f and fayees- Because the decision rule defined by equals the one of Bayes a.e., it follows that:
Lggh ( (BBayes g)v
E ((
max C'EB(G')
M)) g(9', 9('") lo/i(f(ğ', vV. 9 .8),) - (o
9(8 -))==((''.)
0
and similarly:
(fBayes: g)e G.y
E (G''))))D(Ga))))
max
6o/zlol"',n) ((G'.)))) vv, v)m))
('eB(G') 1(0.)).=1(''..
Because the expected adversarial and over-robust 0/1- 0lo-losses are non-negative, i.e. Lgd (S.9). 2 and Laver (f.g) 0 any H. follows that Ly (g)) Lg (f Bayes g)v. Therefore,
Lo X2g (f", g). > Lg.y g) + X (fBayes: g)e
This is a contradiction with fz being minimizer of (5). Therefore, (g' ,y), must equal B'ayyee (g', yy), a.e and hence, (G' y) is Bayes optimal classifier.
21

---

Published as a conference paper at ICLR 2023
F.2.2 THEOREM
Here we investigate what happens, we would only optimize for minimal L (f (f.g). d1 Lg (f. g), + Ag (ffg).. Will we also find a classifier, which has not only small robust but also small standard loss? Theorem 3 below establishes that this does not hold in general. Thus, being a minimizer for the robust loss Lg (f-g).. i.e., achieving optimal robustness (low over- and high adversarial robustness) does imply achieving minimal generalization error. Theorem 3 showcases that the concepts of over- and adversarial robustness do not interchange with standard accuracy.
Theorem 3. Assume H. is a set of all measurable functions. Let Bayes be a Bayes optimal classifier and let the base classifier g also be a Bayes optimal classifier. Then, there exists a function Frab. E H minimizing the robust loss Lggh 9)v and satisfying
Lo > Lo
Proof. We assume that the of cases where the two classes equiprobable has measure zero To prove this result, we define a node-classifier [('", y). == Bayes (9', (9', y). We will first show that f(G', y) has minimal expected adversarial 0/1-loss and later show the same for the expected over-robust 0/lsloss.
The adversarial loss G.y (S,g)u takes the expectation over
(lo1( 9('' w)v) wu)
max O'EB(G')
(18)
"l9 =0(0' w).
Now, note that the second term in equation (18) ( 9(' v)v) is by definition of f. Furthermore, because we maximize (18) over graphs with g( v) = = y)e. the first term ( ,y), (G', v)).) = ( v).. (("',y),) and hence, is always by definition of f. As Because Lggh/ (S g), non-negative, f achieves minimal adversarial
result, Lg (S, g). loss.
Now look at the expected over-robust 0/1-loss Lgg (S,9). It takes the expectation
max g'EB(g')
( vo) f(G', v))) Eays (o(g',
9).)
(19)
1( 3). f(0' -)
Here again, the second term (o/1' ()). "(",, v))) as established above. However, because in the set of graphs we are optimizing over f(G y)u = f('' y).. follows that the first term in (19) lo/1l v).. fg'' v))) = (9)1' v). f(ğ', v)r) and thus, by definition f, is 1. As a result, Lgw (f.g). 0. Again, because Lgger (F.g). v is non-negative, achieves minimal over-robust loss.
Therefore, we have established that f achieves optimal robustness. i.c. Lggh (f. y) 0.
Now will show that Lg La Raiesssi
Lg
Le Dongess
11//2 ((9', - l0/1 Bager (G,
(Q) (D'GG)
120/1 (V/. (G',)))~(G..)))
E
SBayes (S': .1))))) lo/1 (Ner Soo.s (9' v).))
[ 10 [['' # #1- fBayes(S (g', y)o] - Ey.lo'. [1yl' + fBayes (S' Egggg. [E [TV6' BBayes (g'. v)oo 1 [T''s # fBayes (G', (20)
Eggis,
Eoyja [P[v/ |aayes (g', v)) vl Ply', * f (G', ve)ol'
0
22

---

Published as a conference paper at ICLR 2023
Line (20) follows from the fact of binary classes. The last line follows again from the definition of the Bayes classifier and assuming that the set of cases where the two classes are equiprobable classes has measure zero.
F.3 OPTIMAL ATTACK ON CSBMS
Theorem 4. Given a graph generated by CSBM. The minimal number of structure changes to change the Bayes classifier (Theorem for a target node u is defined by iteratively: i) connecting to another node with Yo +f Yu ii) dropping connection another node with Yo Vu.
Proof. Assume (X' A',)), CSBM (X, A, with < p (homophily assumption). Recall 1.p. the Bayes decision y argmaageto.. Ply! = A', y]. We want to prove which structure perturbations result in a minimally changed adjacency matrix Ä', as measured using the no-norm but for which
Vnew = argmaz Ply/ 0 X A F
(21)
(c
Therefore, we want change
Plu y A a Ply' =1 1 A',''
(22)
Ply = y" X
Ply. = y/ X A v/1
(23)
To achieve this, first note that we can rewrite Equation (22) using Bayes theorem:
F A 3o V. X, A. y) Ply X A.
P A X, A, y)
P P 1 1 y²" X, A, y) Pla =1 -1------ 1,
(24)
P 0,: A X, A.
- P. y" X, A. vl P
L.. IIV.
y² N,X, A
(25)
where in Equation 24 we use (A,.) A and Equation 25 follows from Ply = y Ply x A, y] = 2 by definition of the sampling process. Now, we take the logarithm of both sides in (25) and call the fog-difference A:
A(A') = log P 0121 A U' = X, A, y] Pp A,, = -,, A, (26)
Clearly, Equation 25 is equivalent to
A(A') 2
(27)
Using the properties of the sampling process of a CSBM (see Section 2), we can rewrite
P[X., A...v -", x." w) P 1/ y²1
P.AA -y",a)
(28)
-| wu' =v-
II
IP(A,,, =" .
(29)
and therefore
23

---

Published as a conference paper at ICLR 2023
PIX 111 = yy
A = log P 1VV = =1- y-
Pog =V" yEl log P(A n, n, = --" ,:l)
(30)
REID)(()
A.(A))
Now, achieve (23),
find those structure perturbations, which lead to A(A') the fastest (i.e., with least changes). First, note that the first term in Equation 30 does not depend on the adjacency matrix and hence, can be ignored. The second term shows that the change in A(A') induced by adding or removing an edges (u, is additive and independent of adding or removing another edge (e,j). Denote by (' the adjacency matrix constructed by removing (adding) edge (u, u) from A/ (v, u) is (not) already the graph. We define the change potential of node as A. = (A'((m))
(A(A)). Then, we only need find those nodes u with maximal change potential AA. = (A)(() A.(A') and A. < 0 and disconnect (connect) them in decreasing order of A until ((A') < 0. We will now show that any node u has maximal negative change potential, who either satisfies y/- = y. and A or ii) Yo * y. and A O.
To prove this, make case distinction the existence of (u, u) in the unperturbed graph and the class of Yu:
Case A 0:
We distinguish two subcases:
M/. + y=:
We can write
A log P(A b,u 1 1, y", ,", log P(A b, 1ly', ,", Vul
log [A 0ly/, y,, yul log P(A 0/1, 3² yul
log q logp log(1 q) log p)
(31)
0
(32)
Equation 31 follows from the sampling process of the CSBM. Equation 32 follows from < ps implying log q log p and log(1 q) logg1 p)
ii) y+
We can write
Á log log log(1 p) + log(1 - q) > 0
(33)
where the last > follows similarly from q < p.
Case A 1:
i) ya A y yy::
We write
A log P(A U, = 0/y/, = y" v.] log P/A v. = 0/8// = 1 ,,,
log P(A = =1ly' -"", vm] log TP A = 1/1/ = - 3² Uw]
logp - log - -log(1 - + log 9) > 0
(34)
where Equation 34 follows by the insight, that A, the same as for case A = except multiplied with -1.
24

---

Published as a conference paper at ICLR 2023
ii yu yr
We can write
Â, log q log log(1 9) + log(1 p) <
(35)
where the first equality follows from the insight, that A. is again the same for case A except multiplied with -1. The last follows again from < p.
The theorem follows from the fact that only the cases where we add edge to a node of different class, or drop an edge to a node with the same class have negative change potential and the fact, that both cases have the same change potential.
F.4 OPTIMAL ATTACK ON CBA
Theorem Given a graph generated by CBA. The minimal number of structure changes to change the Bayes classifier (Theorem for a target node is defined by iterativel:: i) connecting to another node with yo # Yu, or ii) dropping a connection another node with Ye = Vu-
Proof. For this proof, we assume homophily, i.e. the affinity between same class nodes Wywa. i.e., if Yu. = is bigger than between different class nodes, i.e. if * Ye- We denote the same class affinity as p and different class affinity as y. Now, the proof follows the proof of Theorem 4 until Equation 27. Then, the proof strategy is similar to the one for Theorem 4, but has to be adapted to the specificities the CBA.
Using the properties of the sampling process of a CBA (see Section C), we can rewrite
P[X A.. x 1/ w4 P(A = ,²,
(36)
= PP e. we = -y1 II Pl = =,"
(37)
kE(N][(u)
Note that if < v, P(AA, y" yy = P(A us 31 ,1...., V6. = y²1 and if u, PIA 104 = Vo -"" ,",....," .9). In the following, for a more concise presentation, we write P P(A = y², y] in general to include both cases.
ol = P(A v.a 191..........................1.. ll,,,
Therefore
P 1// = y²
A(A') log
P
11 = yd
Σ
(log (AA = -" log ( = 1- y² v1))
(38)
A,(A.)
Now, achieve (23), want to find those structure perturbations, which lead to A(A') 0 the fastest (i.e., with least changes). First, note that the first term in Equation 30 does not depend on the adjacency matrix and hence, be ignored. The second term shows that the change in A(A') induced by adding or removing an edges (v, i) is additive and independent of adding or removing another edge (v,j). J). Denote by A'(u) the adjacency matrix constructed by removing (adding) edge (v. u) from A' if (v,u) is (not) already the graph. We define the change potential of node (A').. Then, we only need find those nodes u with maximal change (A())) and Å,, < and disconnect (connect) them decreasing order of A until ((A') < 0. We will now show that any node u has maximal negative change potential, who either satisfies i) y/- ya and A 1 or ii) yu * y. and A A, 0.
as Á, : A, (A'(w))
potential A = AA, (A'(A())))
25

---

Published as a conference paper at ICLR 2023
To prove this, make distinction the existence of (v, u) in the unperturbed graph and the class of yu. Furthermore, without loss of generality, we assume u < v.
Case A R,u 0:
We distinguish two subcases:
1) Yo + ys:
Now, write
A. log P(A U. = 1ly' = 1 , log P(A 11/66 = - y2 ,
log P(A 0ly/ y y) + Pog.PAA,,,..o 0l8/ 1 - y 8l
(39)
log P[A 2,u 1ly1.................. ................................ V/ y"] log P(A 1/31,... 36 y'1
log PAA Olv1, ,., y"] + log (P(A 0ly1 ........,. ,.
yr]
=log
Bin (0)m. p/ (v'2 = y/ v²)) - log Bin 00/m, p/ (1)) - y² w*)]
log Bin (0)m. (u/o = yy" + log Bin (0)m, p (0) (3/ = 1 =1-y")
Where the last line follows from the definition of the sampling process of the CBA. Bin (0)m. plu (v', = =v") denotes the probability of the event under binomial distribution with the success probability (0) (v's y²) depending on the class of v/A Pu is also dependent on the other classes y/, Ve-1 however, these do not change, hence we omit to explicitly mention the dependence.
(v)
Now, using the properties of the binomial distribution, we can write
A_ = log(p!") (b,, = =y") - loglp!! (u's = 11 y²)]
log[11 -1(") (v', =y')] log(1 (1.. yy))
(1 + kin)
(1 + kw)P
logl
logl
Em 1, m (1 + km Waygem + + kedg
E 2m 1,mp (1 + km Weonn + (1 + kwlp
2--1 L,mp (1 + kim Way. ym
Em= 1, (1 + km Wayy mm
logl
logl
12
1.m (1 kim Wayee + (1 ku)g
>0-1 1.mph (1 + km Jais Nom + (1 kin)
log
log
(40)
<
0
(41)
The second line follows from the definition of the sampling process of the CBS and denoting the same class affinity p and the different class affinity as q. Equation 40 follows from splitting up the division multiplication in the log-terms and simplifying. The last equation follows from g < p.
Note that if a > v, the sampling probabilities change to p. (v6 =y),, yielding the same result.
ii) yu y/
Now we can write
log ( 0,0 1ly6, y²,y) log P(A 1ly6, yy
log PP [PA 0ly'. = """"." vl log [A 0l1/ -²'
(42)
log log
>
0
(43)
the second line follows from recognizing that Equation 42 leads to the exact same equations as case except for interchanging p and q. The last > follows similarly from q < p-
26

---

Published as a conference paper at ICLR 2023
Case A 1: i) yo + ys:
We can write
A P/A n,a 0lp/ y. P/A = =Oyy - y
log P(A o, 1ly' yy, y) P/A 1ly/ 32 yl
(44)
logp logq
where Equation 44 follows by the insight, that it equals Equation 39 multiplied by -1 ii yo = y+
We can write
A log n.a 0lb/ y.,") P = =0yy -y
log TP (PA n, 1/96 = y log P(A,, = 1/16 1/
(45)
log q log <
where the result follows from recognizing that Equation 45 equals Equation 42 except multiplied with- -.
The theorem follows from the fact that only the where add edge to node of different class, or drop an edge to a node with the same class have negative change potential and the fact, that both cases have the same change potential.
G ROBUSTNESS METRICS
We restate the degree corrected robustness of a classifier f w.r.t a reference classifier g:
1
(obustness(f.g.e)
R(f.9)
(46)
IV
deg(v)
BEV"
Using the true labels y instead of reference classifier in (46), one measure the maximal achievable robustness (before semantic content changes) as R(g) = R(g. y). i.e. the semantic boundary. Note that We measure adversarial robustness as the fraction of optimal robustness R(g) achieved: Radv R(f. g) R(g). Again, to correctly measure gade the identical attack is performed to measure R(f.9) and R(g).
exactly compute R(g) due knowledge of the data generating process.
model f can have high adversarial- but also high over-robustness (see Section 3). To have a metric, which truly shows complete picture of the robustness properties of model, we take the harmonic mean of Radv and the percentage of how much robustness legitimate Rever) and define an
Fi-robustness score: (. 2 -o--oosrry Ruaee Only model showing perfect adversarial
Rove) Radv
robustness and no over-rebus achieves FT 1.
Note that using Prob = (1 + 822 (1- R1-R, Radu
32(1 Rover) neaav neav with 3 0, one can weight the importance of
over- versus adversarial examples with Rade being 8-times as important (1 Rover).
27

---

Published as a conference paper at ICLR 2023
H EXPERIMENT DETAILS
Datasets. We use Contextual Stochastic Block Models (CSBMs) and Contextual Barabási-Albert Model with Community Structure (CBA). The main setup is described in Section 5. The experimen- tal setup for the CBA follows the one for CSBMs outline in Section 5, except for setting m = 2, i.e. to two, resulting similar average node degree
the number of edges for newly sampled node to CORA (see Table 4). Furthermore, instead of p and q, CBA has affinity terms Wyay, one for same-class nodes, which we set to the average same-class node degree in CORA (see Table 4) and one for diffcrent-class nodes, which we analogously set to the average different-class node degree in CORA.
Table 4 summarizes some dataset statistics and contrasts them with CORA. The reported values are independent K, hence we report the average across sampled CSBM graphs for one K.
Average Node Degree
Average Sume-Class
Average Different-Clan
Dataset
# Nodes
Edges
Features
Classes
Node Degree
Node Degree
CSBM
1,000
1,964:123
21
2
3.9320.05
3,18:0007 3.174:0.33
0.74:0.04
CBA
1,000
196814
3.94=0.01
0.7740.03
CORA
2,708
5,278
1,433
3.90
3.16
0.74
Table 4: Dataset statistics
Figure 6a shows that CSBM and CBA graphs mainly contain low-degree nodes.
CSBM (CORA-Fit)
CBA (CORA-Fit)
600
175
500
Number Nodes
150
Number Nodes
125
100
0
8
10
12
10
14
Node Degree
Node Degree
(a)
(b)
Figure 6: (a) Degree distribution of a CSBM graph as parametrized in Section 5 (n = 1000). (b)
Degree distribution CBA parametrized as described Appendix H.
Graph Neural Networks and Label Propagation (LP). We perform extensive hyperparameter search for LP and MIP and each GNN model for each individual and choose, for each K, the on 10 graphs sampled from the respective CSBM CBA.
average best performing hyperparamters For the MODEL+LP variants of our models, we use the individually best performing hyperparame- ters the model and LP. Interestingly, we find that very different hyperparameters are optimal for different choices of the parameters from the respective model papers successful on the benchmark real-world datasets, don't work well for some choices of K, especially low K when structure is very important but features not so.
defining parameter K. We also find that using the default
We train all model for 3000 epochs with patients of 300 epochs using Adam (Kingma & Ba, 2015) and explore learning rates [0.1, 0.01, 0.001] and weight decay [0.01, 0.001, 0.001] and additionally for
MLP: We use (Hidden)-Layer MLP and test hidden dimensions [32, 64, 128, 256] and dropout [0.0, 0.3, 0.5]. We employ the ReLU activation function.
LP: We use iterations and test a the range between 0.00 and 1.00 step sizes of 0.05. LP is the only method having the same hyperparameters all CSBMs, as it is independent of K.
28

---

Published as a conference paper at ICLR 2023
SGC: We explore [1,2.3, 4, number of hops and additionally, learning rate of 0.2. We investigate dropouts of [0, 0.3, 0.5]. SGC was the most challening to train for low K.
GCN: We use two layer (ReLU) GCN with 64 filters and dropout [0.0, 0.5]
GAT: We use two layer GAT with 8 heads and 8 features per head with LeakyReLU having negative slope of 0.2. We test dropout [0.0, 0.3, 0.6] and neighbourhood dropout [0.0, 0.3, 0.6].
GATv2: We use the best performing hyperparameters of GAT.
APPNP: We use 64 hidden layers, K = 10 iterations, dropout [0.0, 0.3, 0.6] and [0.0, 0.3, 0.5] and test in [0.05, 0.1, 0.2). Interestingly, the higher K, we observe higher performing better.
Further details, such the best performing hyperparameters, be found in the released exper- iment configuration files and source code. Exemplary, the (averaged) validation accuracies on the CSBM graphs can be in Figure 7.
Validation accuracy
1.
SGC
0.9
Accuracy
GAIv2
GAT
GraphSAGE
LP
MLP+1P
0.7
GEN-IP
APENP LP
0.0
GAIv24LP
SCC+LP
CP
0.5
1.0
1,5
2.0
3.0
GEaDSAGGE4P
K
Figure 7: Validation accuracies of the best performing hyperparameters of the different models CSBMs. Note that GNNs for low K (high-structure relevance) underperform pure LP.
Attacks.
Nettack attacks a surrogate SGC model to approximately find maximal adversarial edges. As surrogate model, instead of using direct SGC implementation in the models section, use a 2-layer GCN with the identity function as non-linearity and 64 filters and found trains easier on K 0.1 and hence, provides better adversarial examples for K 01 than direct SGC implementation. For higher K, differences are neglectable. We use the same hyperparamter search outlined for the conventional GCN, For the experiments on CSBMs, we remove the power-law degree distribution test, as CSBM does not follow power-law distribution.
DICE randomly disconnects d edges from the test node v to same-class nodes and connects b edges from v to different-class nodes. For given local budget A, set = 0 and b = A.
GRBCD is Greedy gradient-based attack that does not require materializing the dense adja- cency matrix due to its use of Randomized Block Coordinate Descent. During the attack, relaxes the edge weights from (0, to [0, 1] and then discretises the result at the end. Thus, we can forrigltt attack all models that are differentiable w.r.t. the edge weights (GCN, APPNP). For GAT and GATv2 we softly mask edges based on their weight prior to the atten- tion's 's softmax activation. Most importantly, since we avoid any surrogate model we can consider GRBCD to be adaptive attack that crafts model-specific adversarial examples.
SGA, similar to Nettack, attacks surrogate SGC model. However, it chooses malicious edge based on the gradient signal obtained from relaxing the adjacency matrix. Furthermore, it re- stricts the space of possible edges insert based on the K-hop neighbourhood of target node. As surrogate SGC model, we use the same 2-layer linearized GCN as in Nettack.
Ez-weak connects a node to its most-similar different class nodes in feature space (using & norm).
f2-strong, in analogy to be-weak, connects target node to ist most-dissimilar different class nodes feature space (using fo-norm).
Further details, such as the best performing hyperparameters, can be found in the released experi- ment configuration files and source code.
29

---

Published as a conference paper at ICLR 2023
H.1 WORLD GRAPHS
This section covers datasets, models and evaluation procedure for our real-world graph results re- ported in Section 5.2.1 and Appendix K.
Datasets. To explore potential over-robustness on real-world graphs the citation networks Cora (Sen et al., 2008), Cora-ML (Bojchevski & Günnemann, 2018), Citeseer (Sen et al., 2008), Pubmed (Sen et al., 2008) and ogbn-arxiv (Hu et al., 2020) are selected. We extract the largest connected component for Cora ML, Citeseer and Pubmed. Table 5 provides an overview over the most important dataset characteristics. Figure 8 visualizes the degree distributions up to degree 25 for agbnnarxiv and up to degree 15 for all other datasets.
We investigate supervised learning setting, similar to the setting the CSBM and CBA graphs as well as a semi-supervised learning setting more common in practice. In the supervised learning setting, for all datasets except ogbn-arxiv, 40 nodes per class are randomly selected as validation and test nodes. The remaining nodes are selected as labeled training set. For ogbn-arxiv, the by Hu et al. (2020) provided temporal split is chosen. Following the inductive approach used in Section 5 for CSBMs, model optimization is performed using the subgraph spanned by all training nodes. Early stopping uses the subgraph spanned by all training and validation nodes based on the validation loss. The sumi-super learning setting follows the commonly employed learning scenario with having access to only a small amount of labeled nodes during training (see e.g. Geisler et al. (2021)), but again splitting inductively. Here, 20 nodes per class are randomly selected as labeled training and validation nodes. Additionally, 40 nodes per class are sampled as test nodes. The remaining nodes are selected as unlabeled training set. Model optimization is again performed inductively using the subgraph spanned by all labeled- and unlabeled training nodes. Early stopping is done w.r.t. all validation nodes and uses the subgraph spanned by the labeled- and unlabeled training and validation nodes.
Average Node Degree
Average Same-Class
Average Different-Clas
Dataset
Nodes
Edges
# Features
# Classes
Node Degree
Node Degree
Cora-ML 2,810
15,962
2.879
5.68
4.46
1.22
Cora 2,708
5,278
1,433
7
3,90
3.16
0.74
Citeseer 2,110
7,336
3,703
6
3.48
2.56
0.92
Pubmed
19.717
44.324
500
4.50
3.61
0.89
ogbn-arxiv
169,343
1,157,799
128
40
13.67
8.95
4.73
Table 5: Dataset statistics
Model Architectures. We evaluate the robustness of Graph Convolutional Networks (GCN), Label Propagation (LP), and GCN followed by LP post-processing (GCN+LP). The GCN architecture and optimization scheme follow Geisler et al. (2021). The GCN has two layers with 64 filters. For ogbn-arxiv three layers with 256 filters are chosen. During training, a dropout of 0.5 is applied. We optimize the model parameters for maximum of 3000 epochs using Adam (Kingma & Ba, 2015) with learning rate 0.01 and weight decay 0.001. For ogbn-arxiv, no weight decay is applied. LP uses the normalized adjacency as transition matrix and is always performed for ten iterations. This mirrors related architectures like APPNP (Gasteiger et al., 2019). We additionally choose a = 0.7 by grid-search over {0.1, 0.3, 0.5, 0.7, 0.9) on Cora-ML. For GCN+LP, should be noted that LP is applied as a post-processing routine at test-time only. It is not included during training.
Evaluating Degree-Depending Robustness. We investigate degree-dependent robustness of GNNs by following a similar strategy as the &2-weak attack on CSBMs. However, real-world datasets are multi-class. Therefore, we ensure to only connect the target nodes to nodes of one selected class. More concretely, let v be a correctly classified test node with label c². We investigate for each class c * c*, how many edges we can connect to v, until the model's prediction changes and denote this number (c).). The attack then works as follows: First, we project the high-dimensional feature vectors into lower dimensional space by applying the first weight matrix of the GCN', Then, iteratively add edges connecting to the most similar nodes (after projection) in & &g-norm and evaluate after how many insertions the model's prediction changes. We evaluate for a maximum of 128 edge insertions. We present the results for the class achieving lowest robustness, i.e. smallest.
For oghn-arxiv, this projection is omitted as the GCN's filter size is larger than the initial attribute dimen-
sion.
30

---

Published as a conference paper at ICLR 2023
Cora-ML
Citeseer
Number of Nodes
400
300
300
200
200
100
8 Degree
Degree
(a) Cora-ML.
(h) Citeseer
CORA
Pubmed
500
8000
Number Nodes
400
6000
2000
100
6
10
Node Degree
Node Degree
(c) Cora
(d) Pubmed
oglon-anxiv
17500
Number Nodess
25000
32500
30000
2500
20
15
20
25
Node Degree
(e) ogbn-arxiv
Figure 8: Degree distribution by dataset.
(v(v), and the results for the class achieving highest robustness, i.e. largest Ne(v). To save on computation, for ogbn-arxiv, not all test nodes are evaluated. Instead, we sample 1500 nodes from the set while enforcing the same proportion of classes as the full test set. Additionally, the above scheme is not applied for every class + ct. We instead compute the average f2-distance of each class's closest deg(v) nodes target node and evaluate (v(v) for the nearest and farthest class.
I RESULTS USING CBAS
I.1 EFFECTS OF DEGREE PRESERVATION ON OVER-ROOUSTTR
Using CBAs we explore if degree preservation can reduce the measured over-robustness. Note that compared CSBMs, CBAs degree distribution follows power-law and hence, Nettacks test for
31

---

Published as a conference paper at ICLR 2023
power-law degree distribution preservation can be employed. For this analysis, focus the following models: GCN, APPNP, GAT, LP, MLP as well as their +LP variants. Figure compares the measured over-robustness of Nettack without employing the power-law degree distribution test (left figures), i.e. without degree preservation with employing the power-law degree preserving distribution test (right figures). We find that there is close to difference in the measured over- robustness. Figure 9 explores the perturbation budgets (-)g(-) and B2 The same result, that preserving the degree distribution has close no effect, can be seen for the other perturbation sets 11(-) B²(-), (-) and (-(-) in Figure 10. Interestingly, for K = 0.1 preserving the degree distribution increases the measured over-robustness for GCN (eeg() ()) chosen (Fig. 9a and 9b).
Note that for K = 0.1, the measured over-robustness is less than for K = 0.5. This can be explained by the fact that for K = 0.1 the surrogate SGC model attacked (as well as the all other models) achieve only slightly better performance than random guessing as the learning problem relays heavily on the structure of the graph and only very slightly on the node features. Therefore, Nettack often proposes add edges which preserve the semantic content but still fool the models, effectively reducing the measured over-robustness. Also note, that the CBA parametrized using 2, Bdeg(-) equals (-) and (-) equals (a(+) for most target nodes.
0:35
MLP CCN
0.55
MLP GCN GAT
0.30
GAT
0.
GUNLEP APENP-EP
GON APPNP-T.
000
0.20
0.15
0.16
0.06
0.00
0.00
0.00
(a) Bdeg (-), Nettack w/o power-law test
(b) Bdeg (-), Nettack with power-law test
0.70
MLP
0.70
MLP APPNP GAT
0.50
APENP
0.50
GAT
0.40
GON+LP GAT+LP
0.10
GUN-LP
APPNP-LP
0.10
0.10
0.00
2.0
(c) B2 Nettack
w/o Nettack
pawer-law test (d) 22 Nettack with power-law test
Figure 9: The measured over-robustness with perturbation model employing a test for degree preservation compared to the measured over-robustness for perturbation model not employing test for degree preservation. Concretely, Nettack with and without power-law degree distribution test for varying local budgets is employed. Degree preservation has close to effects the measured over-robustness. Plots with standard error.
32

---

Published as a conference paper at ICLR 2023
GCN
0.25
GUN
APPNP
APPNP GAT DP
0.20
LP
GAT
0.20
GUNALP
0.15
APPNP+LP
0.15
APPNE-LP
GAT LP
GAT-LP
0.10
0.00
0.80
0.1
0.3
1.0
1.5
2.0
3.0
4.0
5.0
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
K
K
(a) Bj (+), Nettack w/o power-law test
(b) B (.). Nettack with power-law test
0.35
0.35
GCN
GCN
0.300
APPNP
0.30
APPNP GAT LP GCN-LP
GAT
0.25
LP
0.25
GCN-LP
0.20
GAT-LP
GAT+LP
0.15
0.18
0.10
0.10
0.00
0.00
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
K
K
(c) (-),), Nettack w/o power-law test
(d) (-). Nettack with power-law test
APPNP
0.50
APPNP GAT
GON
GAT
0.10
LP
0.40
UP
GON LPP
CON LP
GAT-LP
GAT-LI
0.20
0.20
0.10
0.10
0.00
0.00
0.1
0.5
3.0
1.5
2.0
3.0
4.0
5.0
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
K
K
(c) (-).), Nettack w/o power-law test
(f) (a(-). Nettack with power-law test
0.70
MGP
0.70
MLP
0.60
GCN
APPNP
0.60
GUN
APPNP
GAT
GAT
L,
0.40
GCN-LP
APPNP+LP
GCN-LP
APPNP LP
CAT LI"
CATAL
0.30
0.30
0.20
0.20
0.10
0.10
0.00
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.3
0.1
0.5
1.0
1.5
2.0
3.0
1.0
5.0
(g) Ba(-), Nettack w/o pawer-law test
(h) Ba(+), Nettack with power-law test
Figure 10: The measured over-robustness with a perturbation model employing test for degree preservation compared to the measured over-robustness for perturbation model not employing test for degree preservation. Concretely, Nettack with and without power-law degree distribution test for varying local budgets is employed. Degree preservation has close to effects the measured over-robustness. Plots with standard error.
I.2 OVER-ROBUSTNERR ON CBAS
Figure 11 shows that the measured over-robustness of the models on CBA graphs is comparable to the measurements on CSBM graphs (see Figure 3a.
33

---

Published as a conference paper at ICLR 2023
Over-robustness:: Rower
MLP APPNP
0.4
0.3
GCN+LP
APPNP
0.2
CATI
0.0
0.1
0.5
2.0
3.0
4.0
5.0
K
Figure 11: Over-Robustness Rober measured using week on CBA graphs with a budget of the degree of the target node. Plot with standard error.
FURTHER RESULTS USING CSBMs
J.1 DEGREF DISTRIBUTION CSBM CORA
Note that degrees in CSBM do not follow power-law distribution. However, they are similar in different sense to common benchmark citation networks. The goal of this section is to show that the large majority of nodes in both graphs have degrees 2, 3, 4 or 5. Low degree nodes are more pronounced in CORA than CSBMs.
CSBM (CORA-Fit)
CDRA
600
Number of Nodes
400
Number of Nodes
300
300
200
200
100
8
10
14
0
10
14
Node
Node
(a) Graph sampled from CSBM, using n 2708
CORA contains mainly low degree nodes, Plot as CORA. Note that the graph structure is of a CSBM at node degree 15. independent of the but only dependent on p.g which have been set to fit CORA. Plot cut at node de- gree 155.
Figure 12: Degree distribution of the used CSBMs vs CORA, both distribution show that the graphs mainly contain low-degree nodes. This even more pronounced in CORA than CSBMs.
J.2 TEST-ACCURACY ON CSBM
This section summaries the detailed performance of the different models on the CSBMs.
34

---

Published as a conference paper at ICLR 2023
Test Accuracy
MLP Classileer
1.0
GCN
SGC
APPNP
GAT
GATv2
GraphSAGE
LP
MLP+LP
GCN-LP
APPNP+LP
SGC+LP
GATV2-LP
0.5
GraphSAGE+LP
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
Figure 13: Test accuracy of models test nodes on the CSBMs.
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
Bayes Classifier (BC)
89.7 %
90.3%
91.7% %
93.1 %
94.7% %
97.4% %
99.0 %
99.8%
BC (Features Only)
50.8%
59.0%
68.4%
76.5%
83.4%
92.6%
97.5%
99.3%
BC (Structure Only)
89.8%
89.8%
89.8%
89.8%
89.8%
89.8%
89.8%
89.8%
MLP
50.4%
57.2%
64.6%
74.3%
83.0%
85.3%
96.6%
99.0%
GCN
64.6%
71.5%
81.2%
87.3%
90.8%
94.0%
95.3%
96.0%
SGC
61.3%
73.5%
82.9%
87.9%
91.5%
94.3%
95.3%
96.2%
APPNP
74.6%
76.7%
82.4%
87.7%
91.8%
96.4%
97.0%
95.5%
GAT
70.0%
77.6%
80.8%
85.2%
89.6%
93.7%
95.0%
95.5%
GATv2
72.8%
76.7%
81.5%
86.1%
90.7%
95.3%
98.1%
99.3%
GraphSAGE
66.2%
70.6%
79.9%
86.0%
89.8%
95.4%
97.9%
99.4%
LP
89.2%
89.2%
89.2%
89.2%
89.2%
89.2%
89.2%
89.2%
MLP+LP
86.6%
88.8%
89.3%
91.3%
93.1%
93.2%
98.4%
99.3%
GCN+LP
85.6%
86.1%
87.6%
89.8%
91.5%
93.2%
94.3%
94.7%
APPNP+LP
85.0%
86.3%
88.4%
89.6%
93.3%
95.9%
96.5%
95.0%
SGC+LP
88.1%
87.0%
88.0%
90.4%
92.0%
93.7%
94.4%
95.0%
GATv2+LP
85.0%
86.4%
88.0%
89.6%
92.2%
95.6%
98.4%
99.2%
GAT+LP
86.0%
86.7%
88.2%
89.7%
91.2%
93.3%
94.3%
94.7%
GraphSAGE+LP 85.5%
86.4%
88.1%
90.2%
92.4%
95.4%
97.9%
99.3%
Table Average test accuracies the models on the sampled test nodes on the CSBMs. Standard deviations rarely exceeds 1% and never 2% and hence, is omitted for brevity.
J.3 EXTENT OF SEMANTIC CONTENT CHANGE IN COMMON PERTURBATION MODELS
The extent of semantic content change looks similar for the other attacks Nettack (Table 7), DICE (Table 8), SGA (Table 9) and fz-strong (10) to Table 2 (fz-weak).
Values are caleulated by attacking an MLP with these respective attacks. As an MLP has perfect robustness, the attacks will exhaust their complete budget in trying to change the MLP's prediction without achieving success. other words, given any perturbation budget A, we construct maxi- mally perturbed graph with A edge changes and measure, in what fraction of cases, this graph has changed semantic content. do not include GR-BCD, as is not model agnostic and attacking an MLP with GR-BCD because all gradients w.r.t. the adjacency matrix random selection of edges, making similar to but weaker compared to DICE. However, the re- sults in Appendix J.5 indicate that GR-BCD would result in similar high fraction of graphs with changed semantic content if it would be able to use up its complete budget A, as it shows similar over-robustness the other attacks, when attacking other models than MLP.
is equivalent to
35

---

Published as a conference paper at ICLR 2023
Nettack:
Furthermore, for K = 0.1 the SGC uses by Nettack has only mediocre test-aceuracy due to features not being very informative. Therefore, Nettack sometimes proposes to add same-class edges or remove different-class edges.
Threat Models K=0.1 K00.5
K=10
K=2. K=1.5
K=3.0
K=4.0 K K-5.0
(.(-)
10.6
9.7
9.1
6.8
4.4
1.9
0.7
0.2
B2(-)
23.5
24.7
24.8
19.8
14.1
6.2
2.2
0.7
B3
35.7
41.0
43.6
38.1
28.8
14.2
4.9
1.6
(a(-)
47.3
55.0
61.2
57.5
46.8
25.1
9.2
3.2
Baeg (-)
45.4
42.9
50.0
47.6
39.4
21.9
8.9
3.1
Bdcg+2())
63.9
73.7
90.1
89.8
79.6
50.2
23.6
8.6
Table 7: Percentage (%) of nodes for which we find perturbed graphs (-)-) violating semantic content preservation, i.e. with changed ground truth labels. Calculated by adding or dropping A edges suggested by Nettack every target node. Note that for K=4.0 and K=5.0 structure not necessary for good generalization (Table 1). Standard deviations are insignificant and hence, omitted.
DICE:
Threat Models K=0.1 K=0.5
K=1.0
K=1.5
K=2.0
K=3.0
K=4.0
K=5.0
(.(.)
14.9
10.9
9.0
6.2
4.3
2.1
0.6
0.2
B2()
36.8
31.4
26.2
19.7
13.8
6.4
2.0
0.6
Bg(
58.6
52.9
46.4
37.7
28.8
13.9
5.0
1.3
(x(-)
77.1
72.6
66.6
57.0
45.8
25.8
9.6
2.9
Baegl Bugge2 (.)
76.6
58.9
55.6
48.9
38.5
22.1
8.7
2.8
100.0
100.0
99.2
92.2
79.9
50.8
24.0
8.2
Table 8: Percentage (%) of nodes for which we find perturbed graphs B- violating semantic
content preservation, i.e. with changed ground truth labels. Calculated by randomly connecting A different-class nodes (DICE) to every target node. Note that for K=4.0 and K-5.0 structure not necessary for good generalization (Table 1). Standard deviations are insignificant and hence, omitted.
SGA:
Threat Models K=0.1 K=0.5
K=1.0
K=13
K=2.0
K=3.0 K K=4.0
K K55.0
(.(-)
14.2
11.3
9.3
6.6
4.6
1.7
0.8
0.2
B2(-)
36.1
32.5
26.1
19.8
14.2
5.6
2.2
0.6
By()
59.3
54.2
47.2
38.2
28.8
13.5
5.0
1.7
Ba(-)
76.4
73.5
66.8
58.1
46.8
24.3
9.6
3.4
Baog (-)
73.6
61.7
56.2
49.0
40.0
20.9
8.9
3.2
Bdog+2())
100.0
99.9
99.3
92.8
80.0
50.2
24.6
9.1
Table 9: Percentage (%) of nodes for which find perturbed graphs in (-)-) violating semantic
content preservation, i.e. with changed ground truth labels. Calculated by randomly connecting A different-class nodes (SGA) every target node. Note that for K=4.0 and K=5.0 structure is not necessary for good generalization (Table 1). Standard deviations are insignificant and hence, omitted.
f2-strong:
36

---

Published as a conference paper at ICLR 2023
Threat Models K=0.1 K05.5
1=100
1=15 K=20
330.0
K=4.0 K 550
(.(-)
14.5
11.1
9.4
6.7
4.4
1.9
0.8
0.2
B2
35.9
30.9
25.8
19.8
14.1
6.2
2.2
0.7
By(
58.6
53.7
46.9
38.1
28.8
14.5
5.0
1.7
(a(-)
76.5
73.0
66.7
58.0
47.0
25.9
9.7
3,4
Bdeg (-)
77.3
59.6
55.9
49.0
39.6
22.0
8.9
3.2
B
100.0
100.0
99.4
92.9
80.5
51.8
24.7
9.1
Table 10: Percentage (%) of nodes for which we find perturbed graphs in (-(+) violating semantic content preservation, i.c with changed ground truth labels. Calculated by randomly connecting A different-class nodes (fg-strong) to every target node. Note that for K=4.0 and K=5.0 structure not necessary for good generalization (Table I). Standard deviations are insignificant and hence, omitted.
J.4 EWER-ROBUSTNESS RESULTS FOR OTHER PERTURBATION SETS
Figure 14 shows the measured over-robustness using lz-weak for the perturbation sets (-).), (.), (-). (-) and (-e For completeness, Baeg (-) include in Figure 14. All perturbation sets show significant over-robustness.
MIP
0.85
MLP
ATPINE
0.90
ARUNN
0.35
EAT
0.25
CATLO
0.90
LP Milteaa
0.10
APPNE-SPP
0.33
0.05
GAT-1P
GAT-UP
GraplE
GopASAGG
0.1
0.5
1.01
1.5
2.0
3.01
4.00
5.1
0.1
01.5
1.00
1.55
2.1
5.0
4.00
5.0
K
KC
Bi(-); Attack: &g-w
(b) B3(-); Attack: l2-weak
0.50
GCN
GCA
01.00
0.50
GAS
0.40
0.30
Griple AGE
GoPESAGE
0.80
LP
0.20
GCN TP
GCN IP
0.30
ACE
CogeAAGE LP
0.00
0.00
K
(c) Ba(); Attack: Eg-weak
(d) B-(-): Attack: Lz-weak
MPP
MLP
+ APPND
0.50
APPNE
DATH
0.60
EATss
MLP-1PP
MLP-1P
ASHNE-EP
0.30
ARUNES
GAT 12
0.10
CA
GopANAGE
1.0
1.6
2.0
3.0
4.0
5.0
0.1
0.5
1.0
1.5
2.0
3.0
4.0
K
K
(:e Attack: &e-w
(1) Baeg+a (-); Attack: &z-weak
Figure 14: Over-robustness Hover, i.c. the fraction of robustness beyond semantic change for dif- ferent perturbation sets (.).). (Attack: lz-weak; Plots with Standard Error). A significant part of the measured robustness for every perturbation set can be attributed to over-robustness. The larger A, the larger the share over-robustness.
37

---

Published as a conference paper at ICLR 2023
J.5
DETAILED WVER-ROBUSTNESS RESULTS FOR Bdeg())
l- 2e-we:::
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
MLP
43.1%
35.6%
30.7%
25.5%
19.3%
9.9%
3.8%
1.3%
GCN
35.3%
30.3%
25.7%
19.8%
14.1%
5.2%
1.6%
0.4%
SGC
37.4%
29.6%
23.9%
20.1%
14.1%
5.2%
2.3%
0.6%
APPNP
32.5%
30.1%
24.3%
19.6%
16.8%
7.0%
2.4%
0.9%
GAT
33.3%
29.2%
26.6%
21.2%
15.7%
7.3%
2.9%
0.9%
GATv2
33.0%
29.4%
26.6%
21.2%
16.1%
7.5%
2.9%
0.9%
GraphSAGE
36.7%
32.3%
26.8%
22.2%
16.9%
8.3%
3.3%
1.2%
LP
16.0%
13.7%
11.3%
8.9%
6.7%
3.0%
1.0%
0.3%
MLP+LP
21.4%
14.8%
15.2%
14.4%
13.1%
6.6%
2.5%
0.9%
GCN+LP
23.5%
20.9%
19.3%
15.2%
10.3%
3.7%
1.2%
0.3%
APPNP+LP
24.5%
22.0%
18.2%
14.8%
11.7%
4.4%
1.6%
0.5%
SGC+LP
19.1%
18.2%
17.3%
14.8%
9.9%
3.8%
1.5%
0.4%
GATv2+LP
25.1%
20.8%
18.2%
15.7%
11.1%
5.1%
2.2%
0.6%
GAT+LP 21.5%
20.5%
17.3%
14.4%
10.8%
4.9%
1.9%
0.6%
GraphSAGEALP
23.9%
21.2%
18.6%
15.8%
12.5%
5.6%
2.3%
0.9%
Rover measured using 2z-weak (see also Figure 3a with budget of the degree of the target node. Standard deviations never exceed 1% except for MLP+LP at K = 0.1 which has standard deviation of 3%.
Table 11:
Nettack:
Table shows that over-robustness is not only occurring for weak attacks. Especially, the MLP results show that if would have classifier perfectly robust against Nettack in the bounded per- turbation set, for all K < (where structure matters), this would result high rvcr-robustsess.
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
MIP
26.5%
26.4% 4%
28.4%
25.0%
19.2%
9.9%
3.8%
1.3%
GCN
13.5%
11.4%
6.0%
2.4%
0.8%
0.1%
0.0%
0.0%
SGC
7.7%
4.6%
2.9%
1.4%
0.4%
0.1%
0.1%
0.0%
APPNP
11.9%
10.1%
9.0%
3.8%
1.4%
0.1%
0.6%
0.6%
GAT
9.7%
15.1%
12.7%
11.0%
5.4%
3.3%
1.6%
0.5%
GATv2
14.0%
12.4%
13.3%
13.8%
8.8%
5.1%
2.7%
0.8%
GraphSAGE
14.6%
17.7%
15.7%
12.3%
9.9%
4.8%
2.1%
0.7%
LP
5.4%
5.4%
5.6%
5.4%
4.2%
1.9%
0.6%
0.2%
MLP+LP
9.4%
6.9%
10.2%
9.6%
10.1%
5.0%
1.7%
0.6%
GCN+LP
4.5%
3.6%
2.0%
1.1%
0.5%
0.2%
0.1%
0.1%
APPNP+LP
8.5%
5.6%
3.1%
2.1%
0.3%
0.1%
0.4%
0.3%
SGC+LP
1.0%
1.1%
1.1%
0.5%
0.2%
0.1%
0.1%
0.0%
GATv2+LP 8.9%
6.3%
6.3%
5.2%
5.3%
3.1%
1.7%
0.5%
GAT+LP 6.5%
6.8%
4.4%
3.7%
2.3%
1.3%
0.7%
0.3%
GraphSAGE+LP 7.7%
7.4%
7.1%
4.8%
4.1%
1.7%
0.8%
0.4%
Table 12: Over- Wobr-Robss Rover measured using Nettack with budget of the degree of the target node. Standard deviations rarely exceed 1% notably for MLP at 0.1 with 4.8% and MLP+LP at K 0.1 at 3%.
DICE:
Table 13 shows, as for Nettack, that over-robustness is not only occurring for weak attacks. Es- pecially, the MLP results show that if we would have a classifier perfectly robust against DICE in the bounded perturbation set, for all K < (where structure matters), this would result in high over-robustness.
38

---

Published as a conference paper at ICLR 2023
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
MLP
43.6%
35.0%
30.8%
25.0%
18.8%
10.0%
3.5%
1.1% %
GCN
34.0%
29.2%
23.2%
16.8%
11.1%
3.4%
0.9%
0.3%
SGC
37.2%
28.9%
21.3%
16.5%
10.7%
3.3%
0.9%
0.2%
APPNP
31.1%
27.8%
22.7%
17.2%
13.6%
4.3%
1.7%
0.8%
GAT
32.9%
27.9%
25.7%
19.2%
13.1%
5.7%
2.2%
0.7%
GATv2
31.2%
27.8%
23.6%
18.7%
13.5%
6.6%
2.4%
0.8%
GraphSAGE
34.7%
29.9%
24.7%
19.4%
14.6%
7.0%
2.6%
0.9%
LP
16.0%
13.4%
10.8%
8.7%
6.4%
2.7%
0.9%
0.3%
MLP+LP
20.8%
14.7%
15.3%
14.5%
12.9%
6.9%
2.4%
0.8%
GCN+LP
21.9%
20.0%
17.0%
12.5%
8.2%
2.5%
0.8%
0.3%
APPNP+LP
23.4%
20.1%
15.9%
13.2%
8.7%
2.7%
1.1%
0.5%
SGC+LP 18.5%
17.6%
15.3%
11.9%
7.6%
2.6%
0.8%
0.2%
GATv2+LP
22.7%
19.5%
15.7%
13.3%
8.7%
4.6%
1.8%
0.6%
GAT+LP 21.9%
18.9%
15.6%
12.3%
8.9%
3.5%
1.5%
0.5%
GraphSAGEALP
22.8%
19.2%
16.0%
12.4%
9.5%
4.2%
1.7%
0.7%
Table 13:
Reeer measured using DICE with a budget of the degree of the target node. Standard deviations are insignificant and removed for brevity.
SGA:
Table 14 shows, for Nettack, that over-robustness is only occurring for weak attacks. Es- pecially, the MLP results show that if we would have classifier perfectly robust against SGA in the bounded perturbation set, for all K (where structure matters), this would result in high over-robustness.
0.1
0.5
1.0
1.5
2.0
3,0
4.0
5.0
MLP
42.3%
36.4%
31.2%
25.4%
19.5%
9.2%
3.8%
1.3%
GCN
23.4%
16.9%
7.3%
3.2%
1.1%
0.1%
0.1%
0.0%
SGC
20.0%
8.4%
4.3%
1.8%
0.4%
0.0%
0.1%
0.0%
APPNP
25.1%
18.5%
10.9%
5.9%
3.5%
0.6%
0.1%
0.0%
GAT
31.2%
26.6%
18.4%
16.7%
9.4%
4.5%
2.1%
0.9%
GATv2
33.8%
25.0%
18.8%
16.9%
11.4%
6.8%
2.8%
0.8%
GraphSAGE
34.1%
28.5%
22.5%
17.8%
12.8%
6.3%
2.4%
0.9%
LP
8.3%
7.7%
6.3%
5.6%
4.0%
1.9%
0.6%
0.2%
MLP+LP
11.2%
9.9%
10.1%
9.3%
12.2%
4.6%
1.9%
0.6%
GCN+LP
8.7%
6.2%
2.9%
1.3%
0.6%
0.1%
0.1%
0.0%
APPNP+LP
16.5%
12.4%
7.0%
3.5%
1.7%
0.4%
0.1%
0.1%
SGC+LP
3.8%
2.6%
1.1%
0.4%
0.2%
0.2%
0.1%
0.0%
GATv2+LP
21.8%
17.4%
8.6%
10.8%
5.5%
4.3%
1.6%
0.4%
GAT+LP 19.4%
16.6%
6.9%
7.3%
4.3%
2.0%
1.1%
0.4%
GraphSAGE+LP
17.6%
15.9%
12.9%
9.8%
6.2%
3.2%
1.1%
0.1% 11
Table 14: Robustness Rover measured using SGA with budget of the degree of the target node. Standard deviations are insignificant and removed for brevity.
GR-BCD:
Table 14 shows how much robustness of the GNNs, when using GR-BCD as an attack, is actually over-robustness. GR-BCD is not applicable to all investigated GNNs in the study as explained in Appendix However, for the models GR-BCD shows significant over-robustness. However, GR-BCD shows the least over-robus compared to the other attacks, indicated that its model- dependent attack strategy makes it better adapted to measure true adversarial robustness compared model-agnostic attacks.
39

---

Published as a conference paper at ICLR 2023
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
GCN
11.9%
7.6%
3.9%
1.4%
0.6%
0.1%
0.1%
0.0%
APPNP
17.3%
13.1%
7.6%
5.0%
1.6%
0.1%
0.6%
0.6%
GAT
10.0%
9.2%
6.6%
3.7%
2.1%
0.7%
0.1%
0.1%
GATv2
10.0%
8.8%
6.5%
4.5%
2.7%
1.0%
0.4%
0.1%
GCN+LP
3.0%
1.9%
1.0%
0.6%
0,4%
0.2%
0.1%
0.1%
APPNP+LP
10.5%
6.6%
3.9%
2.3%
0.3%
0.1%
0.4%
0.3%
GATv2+LP 6.0%
4.1%
2.7%
2.3%
1.6%
0.8%
0.3%
0.1%
GAT+LP 5.1%
4.0%
2.7%
1.9%
1.4%
0.7%
0.2%
0. 1.1%
Table 15: Over- Rover measured using GR-BCD with budget of the degree of the target node. Standard deviations are insignificant and removed for brevity.
J.6 ADVERSARIAL- RESULTS FOR Bäeg (-)
We investigate Nettack (Appendix J.6.1), DICE (Appendix J.6.2), SGA (Appendix J.6.3), lg-strong (Appendix J.6.4) and GR-BCD (Appendix J.6.5). If not mentioned otherwise, error bars refer the standard error.
J.6.1 NETTACK
Nettack, next to GR-BCD and SGA, is the strongest attack we employ, hence, it is good heuristic measure (semantic-awaan adversarial robustness Rodu (see Appendix G) and conventional, non- semantics aware, adversarial robustness R(f) (see Section 5). Figure 15 shows that surprisingly, MLP+LP has highest adversarial robustness, if structure matters K s 3.
Adversarial Robustness: Radv
1.0
MLP
GCN
SGC
0.8
APPNP
GAT
Rady
GATv2
0.6
GraphSAGE
LP
MLP+LP
0.4
GCN
APPNP+LR
SGC+LP
0.2
GATv2+
GAT+LP
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
GraphSAGE+LP
K
Figure 15: Semantic Aware Robustness Rade measured using Nettack.
Figure shows that similar, albeit slightly less accurate adversarial robustness measurements are obtained by not including the semantic awareness. Rankings can indeed change, but only if these models are already very close regarding Rade
The harmonic mean of Rodv and Rower (see Metric-Section G) shows complete picture of the robustness of the analysed models. To measure Rover we use weak. Note that no GNN achieves top placements using this ranking, but the best models, depending the amount of feature infor- mation, are LP, MLP+LP and MLP.
40

---

Published as a conference paper at ICLR 2023
Classic Adversarial Robustness: R
1.0
MLP
GCN
SGC
0.8
APPNP
GAT
GATv2
R
0.6
GraphSAGE
LP
MLP+LP
0.4
GCN+LP
APPNP+LP
0.2
SGC+LP
GATv2+LP
GAT+LP
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
GraphSAGE+LP
K
Figure 16: Conventional (Degree-Correcee Robustness R(f) measured using Nettack.
Harmonic Mean of Rover and Radv
MLP
0.90
SGC
APPNP
GAT
0.70
GATv2
GraphSAGE
0.60
LP
MLP+LP
GCN-LP
APPNP+LP
0.40
SCC+LP
0.30
GATv2+LP
GAT+LP
0.1
0.5
1.0
1,5
2.0
3.0
4.0
5.0
GraphSAGE+LP
K
Figure 17: The harmonic mean of Radv and Rover using weak.
Rover, with Rade measured using Nettack and
J.6.2 DICE
DICE, as just randomly connecting to different class nodes, turns out to be very weak attack similar to leek. Hence, its adversarial robustness counts differ significantly from the stronger Nettack. Here, measure significant difference between true (semantic-awaid presented in Figure 18 and conventional adversarial robustness as shown in Figure 19. Indeed, a conventional robustness measurement claims that LP is always the least robust method by signifi- cant margins. however, correcting for semantic change uncovers that LP actually is the most robust method for K 0.5 and has competitive robustness for K 1 (even until K 1.5 looking overall robustness 20). We find that with DICE we measure significantly higher over-robustness (Section J.5). Therefore, having a weak attack can result in significantly different picture of the true compared to conventional adversarial robustness. This gives us insights for applying attacks on real-world graphs, calling for the importance of always choosing a strong, best adaptive attack (Tramèr et al., 2020b; Mujkanovic et al., 2022), if we want to gain insights into the true robustness of a defense and not be "fooled" by over-robust behaviour.
adversarial robustness as
The harmonic mean of Radv and Roeer (Figure 20 shows complete picture of the robustness of the analysed models. Note that again no GNN achieves top placements using this ranking, but the best models, depending the amount of feature information, are LP, MLP+LP and ML.P
41

---

Published as a conference paper at ICLR 2023
Adversarial Robustness: Radv
1.0
MLP
GCN
SGC
0.9
APPNP
GAT
Radv
GATv2
0.8
GraphSAGE
LP
MLP+LP
0.7
GCN+LP
APPNP+LP
SGC+LP
0.6
GATv2+LP
GAT+
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
GraphSAGE+LP
K
Figure 18: Semantic Aware Robustness Rade measured using DICE.
Classic Adversarial Robustness: R
1.0
MLP
GCN
SGC
0.9
APPNP
GAT
GATv2
R
0.8
GraphSAGE
LP
MLP+LP
0.7
GCN+LP
APPNP+LP
SGC+LP
0.6
GATv2+LP
GAT+LP
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
GraphSAGE++L
K
Figure 19: Conventional (Degree-
(Degree-Correeted) Corrected) Robustness R measured using DICE.
Harmonic Mean of Rover and Radv
1.00
MLP
GCN
SGC
APPNP
0.90
GAT
GraphSAGE
LP
0.80
MLP+LP
GCN+LP
APPNP+LP
SGC+LP
0.70
GATv2+LP
GAT+LP
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
GmapiSAGE+LP
K
Figure 20: The harmonic mean Radv and Rower with Rade measured using DICE and Rower
using weak.
J.6.3 SGA
Albeit slightly weaker, measure similar behaviour for SGA compared to Nettack, which can be explained as both use a SGC surrogate model. Figure again shows that MLP+LP has highest adversarial robustness, if structure matters K < 3.
42

---

Published as a conference paper at ICLR 2023
Adversarial Robustness: Radv
1.0
MLP
GCN
0.9
SGC
0.8
APPNP
GAT
GATv2
0.6
GraphSAGE
LP
0.5
MLP+LP
0.4
GCN+LP
APPNP+LP
0.3
SGC+LP
GATv2+LP
0.2
GAT+
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
GraphSAG++LP
K
Figure 21: Semantic Aware Robustness Rede measured using SGA.
Figure 22 shows that because SGA is weaker than Nettack that similar to DICE robustness rankings are different using conventional adversarial robustness.
Classic Adversarial Robustness: R
1.0
MLP
GCN
SGC
0.8
APPNP
GAT
GATv2
R
0.6
GraphSAGE
LP
MLP+LP
0.4
GCN+LP
APPNP +LP
SGC+LP
0.2
GATv2+LP
GAT+LP
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
GraphSAGE+IP
Figure 22: Conventional (Degree-Corrected) Robustness Rg measured using SGA.
The harmonic mean of Rade and Rover (Figure 23) shows complete picture of the robustness of the analysed models. Note that as with Nettack and DICE, no GNN achieves top placements using this ranking, but the best models, depending on the amount of feature information, are LP, MLP+LP and MLP.
43

---

Published as a conference paper at ICLR 2023
Harmonic Mean of Rover and Radv
1.00
MLP
GCN
0.90
SGC
APPNP
GAT
GATv2
Frob
GraphSAGE
LP
MLP+LP
GCN+LP
4PPNP+LP
SGC+LP
GATv2+LP
GAT+LP
0.1
0.5
1.0
2.0
4.0
GragSSAGE+LP
K
Figure 23: The harmonic mean of Rodu and Rover, with Rade measured using SGA and Rover using weak.
J.6.4 22-STRONG
We measure similar behaviour for f2-strong compared to DICE, except that it performs way stronger against SGC and GCN, these models are probably most effected by having neighbours with significantly different node features. Figure 21 shows semantic-awan adversarial robustness.
A Adversarial Robustness: Radv
1.0
MLP
GCN
0.9
SGC
APPNP
0.8
GAT
GATv2
Radv
0.7
GraphSAGE
LP
0.6
MLP+LP
GCN+LP
0.5
APPNP LP
SGC+LP
0.4
GATv2+LP
GAT+LP
0.5
1.0
3.0
4.0
5.0
GraphSAGE+IP
K
Figure 24: Semantic Aware Robustness Rade measured using &y-strong.
Figure 25 shows adversarial robustness measurements not including the semantic awareness. b-- strong seems suboptimal to distinguish different models for low K. Compared the similar DICE, it ranks MLP+LP high for K 2 1.0.
The harmonic mean of Rade and Rover (Figure 26 shows a complete picture of the robustness of the analysed models. Note that as with Nettack, DICE and SGA, no GNN achieves top placements using this ranking, but the best models, depending on the amount of feature information, are L.P. MI.P+IP and MIP.
44

---

Published as a conference paper at ICLR 2023
Classic Adversarial Robustness: R
1.0
MLP
GCN
0.9
SGC
APPNP
0.8
GAT
GATv2
R
0.7
GraphSAGE
LP
0.6
MLP+LP
GCN+LP
0.5
APPNP+LP
SGC+LP
0.4
GATv2+LP
GAT+LP
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
GraphSAGE+LP
K
Figure 25: Conventional (Degree- (orreeed))))))ed) Robustness R(f) measured using strstnn.
Harmonic Mean of Rover and Radv
1.00
MLP
SGC
0.90
APPNP
GAT
GATv2
F1
0.80
GrapASAGE
LP
MLP+LP
0.70
GCN-LP
APPNP+LP
SGC+LP
0.60
GATv2+LP
GAT+LP
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
GraphSAGE+LP
K
Figure 26: The harmonic mean of Rade and Rover with Rado measured using 22-strong and Rover using we-w
J.6.5 GR-BCD
Figure 21 shows semantic-aware adversarial robustness of GR-BCD, GR-BCD is one of the strongest attacks we test, especially by taking the gradient w.rt. the actually attacked model in- stead of using surrogate model, it adapts each individually. Because it is such strong attacks, the semantic-aware adversarial robustness seems similar to the conventional adversarial robustness in Figure 28 and the harmonic mean in in Figure 29. However, semantic-aware adversarial robust- ness and the harmonic mean show that adding LP as postprocessing has a slightly higher effect than conventionally measurable.
GR-BCD provides strong evidence, that strong, adaptive attack results in low over-robustness and hence, classic adversarial robustness is good proxy for semantic-awan aware adversarial robustness and the over-all all robustness measured using the harmonic mean.
45

---

Published as a conference paper at ICLR 2023
Adversarial Robustness: Radv
1.0
GCN
APPNP
GAT
0.8
GATv2
GCN+LP
Radv
0.6
GATv2+LP
APPNP+LP
GAT+LP
0.2
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
K
Figure 27: Semantic Aware Robustness Rade measured using GR-BCD.
Classic Adversarial Robustness: R
1.0
GCN
APPNP
GAT
0.8
GATv2
GCN+LP
APPNP+LP
0.6
R
GATv2+LP
GA
0.4
0.2
0.1
0.5
1.0
1.5
2.0
3.0
4.0
5.0
K
Figure 28: Conventional (Degree-Corrected) Robustness R(f) measured using GR-BCD.
Harmonic Mean of Rove and Radv
1.00
GCN
APPNP
0.90
GAT
GATy2
GCN+LP
0.70
APPNP+LP
GATv2+LP
GAT+LP
0.50
0.80
0.20
3.0
4.0
Figure 29: The harmonic mean of Rade and Rover with Radv measured using strong and Rover using GR-BCD.
J.7 STRUCTURE PERTURBATIONS UNTIL GCN-PREDICTION CHANGES ON CSBMS
Figure 30 shows that CSBM with K 1.5, where GCN already shows significant over- robustness (see Figure 3b), the GCN less strongly robustness as on Cora-ML (compare to Figure 4).
46

---

Published as a conference paper at ICLR 2023
Structure Perturbations until
GCN-Predction Changes
100
90
00
50
40
30
Node Degree
Figure 30: Robustness of GCN predictions CSBMs with K 1.5 as shown in Figure 1.
J.8 AVERAGE ROBUSTNESS BAYES CLASSIFIER
Figure J.8 shows that the average robustness of the Bayes classifier increases with K and is linear in the degree of the node. Furthermore, if structure matters (K < 3), average robustness rarely exceeds the degree of a node.
Average
Bayes
K=0.1
K-0.5
K=1.0
K=1.5
10
Robustness
Km5.0
7- K=4.0
Degree
Figure 31: Average Robustness of the Bayes classifier on CSBMs.
K FURTHER RESULTS ON REAL- WORLD GRAPHS
In this section, we show all results obtained real-world graphs following the experimental setup described in Section H. The results for the fully supervised learning setting, which is more closer to theoretic investigation, learning setting, which is more common in practice, are outline in Appendix K.2
outlined in Appendix K.I. The results for the semi-supervised
K.1 SUPERVISED LEARNING SETTING
Table visualizes model performance on the test set. GCN and GCN+LP achieve comparable accuracy while I.P accuracy is slightly lower.
47

---

Published as a conference paper at ICLR 2023
Model Dataset
GCN
GCN+LP
LP
Citeseer
69.4 + 1.75
69.5 + 1.62
6.15
Cora-ML
87.1 2.12
86.7 1.80
84.0
Cora
2.02
87.8 17.81.77
8 2.26
Pubmed
85.3 + 2.26
1.3
ogbn-arxiv
70.2 + 0.65
71.3 + 0.61
70.0 1.21
Table 16: Test accuracy mean and standard deviation over different data splits.
Figure 33 visualizes the robustness per node degree when applying the 22-weak attack as described in H.1 Cora-ML, Citeseer, Cora and Pubmed. The results for ogb-arxiv presented in Figure 32. For each dataset, the mean minimal and maximal per-class robustness is depicted. The results are similar for all datasets. In general, robustness increases with increasing node degree. For all datasets and node degrees, GCN shows significant robustness to the structural changes, most pronounced on Pubmed (Figure 33h). The mean (maximal per-class) robustness always multiple of the considered node degree. I.P is considerably less robust, while achieving similar test accuracy (Table 16). In general, less than half of the perturbations needed for GCNs suffice change the LP's prediction. Combining GCN with label propagation significantly and consistently reduces the robustness compared GCN while again, preserving test accuracy (Table 16).
Figure 34 shows the distribution of maxeyle Ne(v) by degree of In contrast Figure 33, the robustness each node visualized individually. The median robustness GCN significantly higher than that of GCN+LP which in turn is higher than that of LP. The difference between lower and upper quartile (IQR) is comparatively large for GCN, smaller for GCN+LP, and smallest for LP. Moreover, observe that GCN has the largest amount of highly robust predictions. Applying LP to the GCN output drastically reduces the number and robustness such outliers.
In conclusion, smoothing the GCN output using label propagation reduces the mean and median robustness, variance of robustness and decreases the number of highly robust predictions. There- fore, we conjecture that pairing GNNs with LP successfully combats over-robustness real-world graphs.
GCN
GC (a 0.7)
LP (a 0.7)
10
10
max Nc(0)
min Nclv)
20
11
13
1
10
11
13
15
Node Degree
Node Degree
(b) Maximal robustness, ogbn-arxiv
(c) Minimal robustness, ogbn-arxiv
Figure 32: Mean robustness per node degree. Error bars indicate the standard error of the mean over five model initializations.
48

---

Published as a conference paper at ICLR 2023
GCN
GCN+LP (a 0.7)
LP (a 0.7)
12
10
max Mg(0)
min Nctv)
25
5
Node Degree
Node Degree
(b) Maximal robustness, Cora-ML
(c) Minimal robustness, Cora-ML
max Ng(4)
min Mctv)
15
Node Degree
Node Degree
(d) Maximal robustness, Citeseer
(e) Minimal robustness, Citeseer
10
25
max Nel))
min Neto)
8
15
2
Node Degree
Degree
(f) Maximal robustness, Cora
Minimal robustness, Cora
120
100
max N.IV)
min N.VV)
80
Node Degree
Node Degree
(h) Maximal robustness, Pubmed
Minimal robustness, Pubmed
Figure 33: Mean robustness per node degree. Error bars indicate the standard error of the eight data splits.
49

---

Published as a conference paper at ICLR 2023
120
120
120
max (eto)
ITax Nc(0)
100
100
60
60
max
20
Node Degree
Node Degree
Node Degree
(a) Cora-ML, GCN
(b) Cora-ML, GCN+LP
(c) Cora-ML, LP
120
120
120-
1.00
max (eM)
100
100
max
86
8
20
20-
Node Degree
Node Degret
Node Degree
(d) Citeseer, GCN
(e) Citeseer, GCN+LP
(I) Citeseer, LP
120
120
120
100
ITO Ne60)
100
100
max
80
60
60
40
20
20
20
0
Node Degree
Node Degree
Node Degree
(g) Cora, GCN
(h) Cora, GCN+LP
(i) Cora, LP
120
120
120
max (,(0)
100
max Ncc0)
100
100
80
60
max
40
20
20
0
Node Degren
Node Degrne
Nade Degroo
Pubmed, GCN
(k) Pubmed, GCN+LP
(l) Pubmed, LP
120
120
120
100
max Re(0))
100
100
80
80
60
60
40
20
20
12131415
Degree
Node Dogree
Degree
(m) ogbn-arxiv, GCN
(n) ogbn-arxiv, GCN+LP
(0) ogbn-arxiv, LP
Figure 34: Distribution of maximal (per-class) node robustness by node degree. Results are aggre- gated over different data splits. The box captures the lower quartile (Q1) and upper quartile (Q3) of the data. The whiskers are placed Q1 1.5 IQR and Q3 1.5 IQR, where IQR Q3 Q1 is the interquartile range.
K.2 SEMI-SUPERVISED LEARNING SETTING
Table 17 visualizes model performance on the test set. GCN and GCN+LP achieve comparable accuracy. Because of the low labeling rate (see Table 18), label propagation does not work stand-alone classification algorithm, achieving accuracies similar to chance. For completeness, we have still included LP robustness results in the following figures.
Figure 35 visualizes the robustness per node degree when applying the we-k attack. Compared to the supervised learning setting, the mean robustness considerably higher for all models. For GCN,
50

---

Published as a conference paper at ICLR 2023
Model
GCN
GCN+LP
LP
Dataset
Citeseer
66.5 + 2.41
66.5 2.15
Cora-ML
83.5 + 1.79
24.0
15.1 4.99
Cora
82.3 + 1.42
8
13.0
Pubmed
76.7 = 2.29
76.9 2.91
37.5 = 8.85
Table 17: Model test accuracy and standard deviation over different data splits
Training (labeled)
Training (unlabeled)
Nodes
Validation
Test
Dataset
Citeseer
5.69
77.25
5.69
11.37
Cora-ML
4.98
80.07
4.98
9.96
Cora 5.17
79.32
5.17
10.34
Pubmed
0.30
98.78
0.30
0.61
Table 18: Percentage of training, validation and test nodes per dataset for the semi-supervised set- ting.
nodes of degree one have an average maximal (per-class) robustness of above 40 on all evaluated datasets. The robustness of GCN and GCN+LP shows relationship similar the supervised learn- ing setting. In general, GCN is more robust and additional smoothing with LP reduces the robustness while leaving the test accuracy unchanged (Table 17). Note that the LP results do not yield inter- pretable information, due to LP not working as a standalone classifier and have only been included completeness. Figure provides strong evidence, that pairing GNNs with IPP significantly re- duces over-robustness real-world graphs in the realistic semi-supervised learning scenario with small labeling rates.
Figure 36 shows the distribution of maxeyee (u(v) by degree of c. The median robustness of both GCN and GCN+LP higher when compared to the supervised learning setting. However, again GCN+LP significantly reduces the very high robustness of GCN, while achieving similar test accuracy (Table 17). Note that we only investigated node-level robustness until 128 edge insertions. On Pubmed, most predictions seem to be more robust than 128 edge insertions. However, adding LP as post-processing, still lets the whiskers and lower quartiles the box-plot start earlier as without adding LP for most node degrees. In general, the interquartile range (IQR) of both GCN and GCN+LP is noticeable larger when comparing to the supervised learning setting. At the same time, the IQR of GCN+LP again lower than that of GCN.
In conclusion, smoothing the GCN output using label propagation reduces the mean and median robustness well as the variance of the robustness for the semi-supervised learning setting. There- fore, the results are consistent with the supervised learning setting. Thus, as pointed out above, they provide strong evidence, that pairing GNNs with LP significantly reduces over-robustness on real-world graphs in the semi-supervised learning scenario often found in practice.
51

---

Published as a conference paper at ICLR 2023
GCN
GCN+LP (a 0.7)
LP (a 0.7)
40
33
30
min Nclv)
max
80
20
13
16
5
Node Degree
Node Degree
(b) Maximal robustness, Cora-ML
(c) Minimal robustness, Cora-ML
100
40
90
N:(v)
80
min Nclv)
30
70
Degree
Node Degree
(d) Maximal robustness, Citeseer
(c) Minimal robustness, Citeseer
120
100
min Nclv)
89
15
max
Degree
Degree
(f) Maximal robustness, Cora
(g) Minimal robustness, Cora
100
100
max NAVV
min NAVI
80
Node Degree
Node Degree
(h) Maximal robustness, Pubmed
Minimal robustness, Pubmed
Figure 35: Mean robustness per node degree. Error bars indicate the standard error of the mean over eight data splits.
52

---

Published as a conference paper at ICLR 2023
120
120
120
max McM
100
80
80
max
60
60
60
40
40
2
Node Degree
Node Degree
Degree
(a) Cora-MI, GCN
(b) Cora-MI,, GCN+LP
(c) Cora-MI,, LP
120
120
120
max Nctr)
max NMM
80
60
60
60
40
40
Node Degree
Node Degree
Node Degree
(d) Citeseer, GCN
(c) Citeseer, GCN+LP
(l) Citeseer, LP
120
120
120
mas Mgve)
mat Ne(v)
100
80
60
60
40
40
2
Node Degree
Node Degree
Node Degree
(g) Cora, GCN
(h) Cora, GCN+LP
(1) Cora, I.P
120
120
120
max (e(o))
mat N:00
100
80
60
60
40
2
Node Degren
Node Degree
Node Degree
(j) Pubmed, GCN
(k) Pubmed, GCN+LP
(1) Pubmed, LP
Figure 36: Distribution of maximal (per-class) node robustness by node degree. Results are aggre- gated over eight data splits. The box captures the lower quartile (QI) and upper quartile (Q3) of the data. The whiskers are placed at QI 1.5 IQR and Q3 + 1.5 IQR, where IQR = Q3 -Q1 the interquartile range.
53

---

Published as a conference paper at ICLR 2023
L ADDITIONAL RELATED WORK
We see us related to works using synthetic graph models to generate principled insights into GNNs. Notably, Fountoulakis et al. (2022) show that non-trivially CSBMs settings (hard regime), GATs, with high probability, can't 't distinguish same-class edges from different-class edges and degenerate GCNs. Baranwal al. (2021) study GCNs on CSBMs and find graph convolutions extent the lin- ear separability of the data. Palowitch et al. (2022) generate millions of synthetic graphs to explore the performance of common GNNs on graph datasets with different characteristics to the common benchmark real-world graphs. However, their studied degree-corrected SBM is fundamentally lim- ited to transductive learning.
Regarding the bigger picture in robust graph learning, all works measuring small changes to the graph's ss structure using the fo-norm can be seen as related. This is a large body of work and includes but is not limited to i) the attack literature such (Zügner al., 2018; Dai et al., 2018; Waniek et al., 2018; Chen et al., 2018; Zügner & Günnemann, 2019a; Geisler et al., 2021); ii) various defenses ranging from detecting attacks (Wu et al., 2019b; Entezari et al., 2020), proposing new robust layers and architectures (Zhu et al., 2019; Geisler et al., 2020) to robust training schemes (Zügner & Günnemann, 2019b; Xu et al., 2019; 2020); iii) robust certification (Bojchevski et al., 2020; Schuchardt et al., 2021). An overview of the adversarial robustness literature on GNNs is given by Günnemann (2022). Zheng al. (2021) provide a graph robustness benchmark.
Regarding sound perturbations models, distantly related is also the work of Geisler et al. (2022), which apply GNNs combinatorial optimization tasks and therefore, can describe how the pertur- bations change or preserve the label and thereby, semantics.
54


Reviews:
[{"review_id": "dkwMiyZx6d", "reviewer": "Reviewer_b2Ux", "summary": "", "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": "", "summary_of_the_paper": "This paper discusses the semantics-preserving adversarial attack in graph. Based on CSBMs, the constructed graphs show over-robustness of GNNs. The authors also prove that GNN+LP could be one way to reduce the over-robustness.", "summary_of_the_review": "The concept of semantic-preserving perturbation and over-robustness of GNNs are interesting and attractive. The theoretical analysis based on these concepts is also sufficient. However, the authors lack more discussion with the unnoticeable perturbations mentioned in Introduction and the attack algorithm set in the experiment is relatively small.", "strength_and_weaknesses": "S1: Revisiting classic graph adversarial attacks from a semantic-preserving angle is novel and interesting.\nS2: This paper leverages the synthetic graphs based on CSBMs and Bayes classifiers as reference classifiers to formulate the concept of over-robustness if the perturbation unnecessarily changes the semantics.\nS3: The robustness-accuracy tradeoff is also discussed in inductive settings based on the constructed graphs and reference classifiers.\n\nW1: Some works which propose the notion of unnoticeable perturbations mentioned in Introduction lack further comparison in the following part of this paper. whether these unnoticeable perturbations are semantic-preserving or not is unknown, at least from an experimental perspective.\nW2: It would be better if more realistic datasets are discussed in this paper. Besides, when the CSBMs violates the real graph construction also needed more discussion.\nW3: The attack algorithms used in the Results sections are targeted attacks. I wonder whether the untargeted attack like MetaAttack will also cause the same over-robustness.\nW4: There are some typos in this paper, e.g., structure using is miswritten as structureusing in page 1, APPNP has no reference in page 6 section 5.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Is3unQQpkn5", "reviewer": "Reviewer_2ZaK", "summary": "", "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": "", "summary_of_the_paper": "The authors introduced a principled notion to be aware of semantic content change of an adversarial graph by  Contextual Stochastic Block Models (CSBMs). The experimental results showed for a majority of nodes the prevalent perturbation models include a large fraction of perturbed graphs violating the unchanged semantics assumption and all assessed GNNs show over-robustness - that is robustness beyond the point of semantic change. ", "summary_of_the_review": "I incline to accept this paper, because of its novelty.", "strength_and_weaknesses": "Strength:\nThe authors revisted the robustness of graph neural network, and proposed a method to detect the semantic content change of an adversarial graph, which is interesting and meaningful. The presentation is good, and easy to follow. The experimental results demonstrated the effectiveness of the proposed method.\n\nWeakness:\n1) It is expected to give more details about Figure 1.\n\n2) There are two many symbols in the paper. I suggest the authors give a table to summary these symbols for reader understanding.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8BiyBseD8X6", "reviewer": "Reviewer_bUiK", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "The paper studies the robustness of machine learning models for node prediction problems. It is well-known that GNN models are sensitive to small perturbations in the graph structure. However, it is difficult to justify which perturbations are semantically-preserved for graph-like input (which is easier for images as humans are often considered robust judgers). The authors used CSBMs to generate synthetic graphs with which the optimal Bayes classifier is derivable and then used it as the reference classifier for semantic changes. Using the Bayes classifier, the authors introduce a notion of over-robustness: the prediction of the studied classifier is not changed for a perturbed graph (which is generally known as adversarial robustness), but the prediction of the reference classifier does. They then showed that there is no inherent trade-off between semantic-aware robustness and test accuracy, similar to Suggala et al. (2019) work. Empirically, they show that most GNN models suffer from over-robustness, and using Label Propagation on top of GNNs does alleviate them.", "summary_of_the_review": "My initial impression of this paper is positive; thus, I lean towards acceptance of this paper.", "strength_and_weaknesses": "Overall, the results of this paper could bring more insight into the current understanding of adversarial robustness for GNNs. The main result that indicates no robustness-accuracy tradeoff for inductively classifying a newly added node is interesting, even though a similar result is introduced by Suggala et al. (2019). This work focuses on non-i.i.d data instead of i.i.d. data in Suggala et al. \n\nThe study of over-robustness seems to be appealing. However, there is a concern about its practicality, as it requires the optimal (reference) classifier. Most of the analyses in this paper are on synthetic graphs. The results in Section 5.2.1 are not very significant to me. The authors should discuss how over-robustness could be avoided in real-world applications.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster