Adversarial Weight Perturbation Improves Generalization in Graph Neural Networks
Authors: Yihan Wu
Aleksandar Bojchevski
Heng Huang
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph neural networks
Adversarial weight perturbation

Abstract: There is growing theoretical and empirical evidence that flatter local minima tend to improve generalization. An efficient and effective technique for finding such minima is Adversarial Weight Perturbation (AWP). The main idea is to minimize the loss w.r.t. a bounded worst-case perturbation of the model parameters by (approximately) solving an associated min-max problem. Intuitively, we favor local minima with a small loss in a neighborhood around them. The benefits of AWP, and more generally the connections between flatness and generalization, have been extensively studied for i.i.d. data such as images. In this paper we initiate the first study of this phenomenon for graph data. Along the way, we identify a vanishing-gradient issue with all existing formulations of AWP and we propose Weighted Truncated AWP (WT-AWP) to alleviate this issue. We show that regularizing graph neural networks with WT-AWP consistently improves both natural and robust generalization across many different graph learning tasks and models.

Under review as a conference paper at ICLR 2022
ADVERSARIAL WEIGHT PERTURBATION IMPROVES GENERALIZATION IN GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
A lot of theoretical and empirical evidence shows that the flatter local minima tend to improve generalization. As an emerging technique to efficiently and effec- tively find such minima, Adversarial Weight Perturbation (AWP) minimizes the loss W.E.f. bounded worst-case perturbation of the model parameters by (approx- imately) solving an associated min-max problem, i.e. favoring local minima with a small loss in a neighborhood around them. The benefits of AWP, and more gen- erally the connections between flatness and generalization, have been extensively studied for i.idd. data such as images. In this paper, we initiate the first study of this phenomenon for non-i.i.d graph data. Along the way, we first derive a generaliza- tion bound for non-i..d. graph classification tasks, then we identify vanishing- gradient issue with all existing formulations of AWP and we propose new Weighted Truncated AWP (WT-AWP) to alleviate this issue. We show that regu- larizing graph neural networks with WT-AWP consistently improves both natural and robust generalization across many different graph learning tasks and models.
INTRODUCTION
Simply minimizing the standard cross-entropy loss for highly non-convex and non-linear models such as (deep) neural networks is not guaranteed to obtain solutions that generalize well, especially for today's overparamatrized networks. The key underlying issue is that these models have many dif- ferent local minima which can have wildly different generalization properties despite having nearly the same performance on training and validation data. Naturally, there is rich literature that studies the properties of well-behaving local minima, as well as the design choices that improve our chances of finding them (Stutz et al.) 202T). The notion of flatness which measure how quickly the loss changes in neighbourhood around a given local minimum has been empirically shown to correlate with generalization among a variety of different measures (Jiang et al. 2019). In addition, general- ization bounds based the PAC-Bayes framework (McAllester 1999; Foret et al. (021) provide theoretical insights that corroborate the mounting empirical data. Since the evidence implies that flatter minima tend to generalize better, the obvious question is how to efficiently find them.
Not only do flat minima improve generalization from the training to the test data, i.c. the clean accu- racy (Foret al. 2021 Zheng al. 2021 Kwon et al. (022), but they also improve generalization to adversarial examples, T.e. the robust accuracy (Wu et al. 2020aa Stutz et al. (002]. Improving ad- versarial robustness important, especially for models deployed in safety-critical domain or models deployed in the real-world, since most standard (undefended) models are vulnerable to adversarial attacks. Attackers can easily craft deliberate and unnoticeable input perturbations that change the prediction of the classifier. Flat minima show higher resistance to such adversarially perturbed in- puts while maintaining good clean accuracy (Stutz al., 202T).
Among the variety of techniques for finding flat minima Adversarial Weight Perturbation (AWP) (Wu et al. 2020a), and the closely-related (adaptive) sharpness-awar minimization (Foret et al. 2021 K won et al. 2021) and adversarial model perturbation (Zheng et al. (021), seems to be quite effective in practice. The key idea is to minimize the loss w.r.t. a bounded worst-case perturbation of the model parameters, i.e. minimize a local notion of sharpness. The benefits of this approach, and more generally the correlation between flatness and (clean/robust) generalization, have been extensively studied for i.i.d. data such images. In this paper we study this phenomenon for graph data for the first time. Concretely, we analyze and improve the robustness of Graph Neural Networks (GNNs) which have become fundamental building block (in addition to CNNs and RNNs)

---

Under review as a conference paper at ICLR 2022
Blindly applying existing weight perturbation techniques to GNNs is unfortunately not effective in practice due to a vanishing- have higher norm which in turn leads to saturation in the last layer where that logits for one class are on a significantly larger scale compared to the rest. Even though this limitation plagues all formulations of AWP, for both GNNs and other models (e.g. ResNets), it has gone unnoticed so far. To address it we propose Weighted Truncated Adversarial Weight Perturbation (WT-AWP) where rather than directly minimizing the (robust) AWP loss we use it as regularizer in addition to the standard cross- rross-entropy loss. Moreover, we propose to abstain from perturbation in the last layer(s) of the network for a more fine-grained control of the training dynamics. These two modifications are simple, but necessary and effective. With our resulting formulation the models can obtain useful gradient signals for training even when the perturbed weights have a high norm, mitigating the gradient-vanishing issue. Furthermore, we theoretically study the AWP learning objective and show its invariance for local extrema. We can summarize our contributions as follows:
issue. Intuitively, the adversarially perturbed weights tend to
We provide theoretical analysis of AWP non-i..d. graph data and identify vanishing- gradient issue that plagues all previous AWP variants. Based on this analysis we propose Weighted Truncated Adversarial Weight Perturbation (WT-AWP) that mitigates this issue.
We study for the first time the connections between flatness and generalization for Graph Neural Networks. We show that GNNs trained with our WT-AWP formulation have si- multancously improved natural and robust generalization. The improvement is statistically significant and consistent across tasks (node-level and graph-level classification) and across models (standard and robustness- aware GNNs). All this negligible computational cost.
2 BACKGROUND AND RELATED WORK
Adversarial Weight Perturbation for Images. AWP is motivated by the connection between the flatness of the loss landscape and model generalization. Given learning objective L(-) and an im- age classification model with parameters 0, the generalization gap (Wu et al., 2020a). also named the sharpness term (Foret et al. (02T), which measures the worst-case flatness of the loss land- scape, is defined by [max] م 0 8) L())]. This gap is known to control PAC-Bayes generalization bound (Neyshabur et al. 2017). with a smaller gap implying better generalization. The AWP objective optimizes the generalization gap and the loss function simultaneously via ming[(mac مp L(0+5) L()) + L(O) = ming max L(0 + 5). Providing further the- oretical justification for the effectiveness of the AWP, ZZeng al. (2021) prove that this objective favors solutions corresponding to flatter local minima assuming that the loss surface can be approxi- mated an inverted Gaussian surface. Relatedly, they show that AWP penalizes the gradient-norm.
Keskar et al. 2016) show that large- batch training may reach sharp minima, however GNNs usually use small batch size. In some cases we can rescale the weights achieve arbitrarily sharp minima that also generalize well (Dinh et al. 2017). Investigating this issue for GNNs is out of our scope.
GNNs, Graph attacks, and Graph defenses. Graph Neural Networks (GNNs) are emerging as a fundamental building block. They have achieved spectacular results on variety of graph learning tasks across many high-impact domains (see survey (Wu et al., 2020bb). Despite their success, has been demonstrated that GNNs suffer from evasion attacks at test time ZZügnnrr et al. 20188) and poi- soning attacks at training time Zügner and Günnemann] 2019). Mcanwhile, a scries of methods have been developed to improve their robustness. For example, GCNJaccard (Wu al., 2019) drops dis- similar edges in the graph, as it found that attackers tend to add edges between nodes with different features. GCNSVD (Entezari et al., 2020 replaces the adjacency matrix with its low-rank approxi- mation motivated by the observation that mostly the high frequency spectrum of the graph is affected by the adversarial perturbations. We also have provable defenses that provide robustness certificates (Bojchevski et al., (020). Both heuristic defenses (e.g. GCNJaccard and GCNSVD) and certificates are improved with our WT-AWP, For an overview of attacks and defenses see Sun et al. 2018).
ADVERSARIAL WEIGHT PERTURBATION ON GRAPH NEURAL NETWORKS
To simplify the exposition we focus the remi-supervised node classification task. Nonetheless, in Sec.55.8 we show that AWP also improves graph-level classification. Let G = (A, X) be a given (at- tributed) graph where A is the adjacency matrix and X contains the node attributes. Let 1 be the set
2

---

Under review as a conference paper at ICLR 2022
of all nodes. Normally optimize ming Lusin (0: A, X), where Luain = =Eve Evey.n. ((fo(A, X), yo), is GNN parametrized by weights 0 = (01.... 0x), Ye is the ground-truth label for node v, and ( is some loss function (e.g. cross-entropy) applied to each node in the training set Virain C V.
In AWP we first find the worst-case weight perturbation 8* 60()) that maximizes the loss. Then minimize the loss with the perturbed weights. The worst-case perturbation for a given @ is defined as
8 (0)
arg
max S(
Luain (0 + X),
{5)
where p(0) is the strength of perturbation. Then the AWP learning objective
min
max
Luiin(( 10++00 6; X) min Luain ( + 8 (0); AX)
(2)
(ō) || 11l.::llpppp...m pptt)
Since the PAC-Bayes bound proposed by McAAlesterr (999)) only holds for i.i.d. training tasks and semi-supervised node classification is non-i.id. task, analysis in Wu al. (2020a) and Foret al. (202T) could not be naturally extended to node classification tasks. We derived a new generalization bound for node classification tasks on GNNs based on the uub-group generalization MM 2021).
Theorem 1. (informal). Let Lua A, X) be the loss on all nodes, including the unseen test nodes. is bounded by the adversarially weight perturbed loss on the training nodes as follows:
Latr (0; X) (
max
Lirain ( + A, + 0
The formal version, the details for h(), and the proof are in Appendix E This bound justifies the use of AWP since the perturbed loss on training nodes bounds the standard loss on all nodes. Moreover, as 1(110]] ||2//|////// (0)) is monotonously decreasing with p(0). increasing the perturbation strength can make the bound Bq. 3 sharper, i.e. the resulting AWP objective should lead better generalization.
Since finding the optimal perturbation (Eq. 1b is intractable, we approximate it with one-step pro- jected gradient descent as in previous work (Wu et al. 2020a Foret et al. 2021 Zheng et al. 2021
8* (0) == B(())) Luain X)),
(4)
where B(p(O)) is an la ball with radius p(0) and (.)p(e)()) is a projection operation, which
projects the perturbation back to the surface (p(()) when the perturbation is out of the ball. The maximum perturbation norm p(0) could either be constant (Foret et al. 2021 Zheng et al. 2021
or layer dependent (Wu et al. 2020a).. We specify a layer- norm constraint p(0) == p
because the scales of different layers in a neural network vary greatly. With the approximation
8* (0), the definition of the final AWP learning objective is given by
min Laup (0) :- Lurain 0 + IIB(((O)) (V Vo Lemain (0; A, A,
(5)
If Lurain (0; X)) smooth enough, V (0 X) 0 when 0- is local extremum. In this case Lawp (0) = Lieain (0; A, X). A natural question is whether 0* will also be the extremum of
(wwp(()) (0)
? We show that Tump (0) keeps the local extremum of Turain (0; A, X) unchanged.
Theorem 2. (Invariant of local minimum and maximum) With the AWP learning objective in Eq.
and for continuous Iurain (0; A, X), V (0; A, X), Ag Tamain (0; A, ). if l" is a local mini-
mum of Luaan (0; ; A, X) and the Hessian matrix Ae Liraia (0 A, X e. is positive definite, O" is also a local minimum of Lawp(0)
The proof is provided in Appendix A The exact gradient of this new objective is
(6) Since V (0) includes second and higher order derivative of 6, which are computationally expen- sive, they are omitted during training, obtaining the following approximate gradient of the AWP loss
VoLumin ( +++ 50) A. = VoLunin A, () + T A,
0+8-(0) (4.4))++-000
Vo (0; A, (le-)-())
Foret et al. (20TT) show the models trained with the exact gradient (Eq. 6 have almost the same performance model trained with the estimated first-order gradient (Eq. 7h.
3

---

Under review as a conference paper at ICLR 2022
1.0
100
1.0
1.0
1.0
0.8
0.5
0.8
0.8
-0,05
0.8
0.005
0.6
0.6
0.6
0.0
00,000
00.000
0.4
0.4
0.4
-0.005
0.5
0.2
0.2
-0.005
0.2
-0.010
-1.0
0.0
0.0
0.0
0.0
0.0
0.0
0.5
(a) Vanilla GCN
(b) AWP
0.5
(c) AWP 1.5
(d) AWP 2.5
Figure I: Compare AWP models on linearly separable dataset with different perturbation strengths
p. The accuracy of models (a) (d) is 0.97, 0.97, 0.69, and 0.48 respectively. The face color of each node shows its prediction score and the border color shows its ground truth label. Grey lines connect the node with its nearest neighbours in the graph. For large values of p the model unable to learn.
4 WEIGHTED TRUNCATED AWP
In this section we discuss the theoretical limitations of existing AWP methods on GCN, and illustrate them empirically on a toy dataset. We also propose two approaches to improve AWP. Our improved AWP works well on both toy data and on real-world GNN benchmarks across many tasks and models. We also show that similar problems also exist for multi-layer perceptrons (see Appendix
4.1 THE VANISUING-GRADIINN ISSUE OF AWP
Consider GCN 1 o(A(.. ,...).,,, with softmax activation at the output layer, where Å the graph Laplacian given by Á D-1/2(A IN)D-1/2, DH (A IN).g. The perturbed model is ú o A(...(A (W1 (V))) +8x)). Since the norm of each perturbation 6, could be as large as Will2. . in the worst case the norm of each layer is (p + 1) W. and thus the model will have exploding logit values when p is large. After feeding large logits into the softmax layer, the output will approximate a one-hot encoded vector, because the difference between the entries of the logits may also be large. In this case the gradient will be close to 0 and the weights will not be updated. Notice, although in practice the number of GCN layers is always less than 3, still observe the vanish gradient issue in both toy datasets and GNN benchmarks.
To verify our conclusion, we train a 2-layer GCN network with hidden dimension 64, which is common setting for GCNs. on linearly separable dataset. The dataset con- tains 2 classes 1-1, and each class has 100 nodes. We apply k-nearest neighbor (k: 3) to obtain the adjacency matrix, and use the position of the nodes as the features. The number of training epochs is 200. We use 10% nodes for training, 10% for validating and the rest 80% for test- ing. InfFig. we values. Models with AMP crash quickly when increased from 0.5 2.5. When p = 0.5, the classification accuracy 0.97, which is nearly the same as the vanilla model, but when p= 2.5, the classification accuracy is 0.51, which 1.5
10
0.8
0.6
AWP rho-1.5
0.4
AWP 2.5
we show the trained classifiers for different p
325
150
Figure 2: Learning curves for GCN and GCN+AWP with different p.
is the same as a random guess. Besides, when and 2.5, the loss of AWP method almost constant dur- ing training (ig.. 2) and the prediction score (Fig. I(c) Fig. I(d) is around 0. This indicates that the weights are barely updated during training. So with the AWP objective, we cannot select large
Yet, discussed in Sec.. 3 we prefer larger values of p since they lead to tighter bound (Eq. and are more like to generalize better. As we shown next, our suggested improvements fix this issue.
4.2 TRUNCATED AWP AND WEIGHTED AWP
Intuition for WT-AWP. The vanishing gradient is mainly due the exploding of the logit values, which is caused by perturbing all layers in the model. Thus, a natural idea is to only apply AWP on certain layers to mitigate the issue. This it the truncated AWP. Another idea is to provide second
4

---

Under review as a conference paper at ICLR 2022
1.0
1.0
1,0
0.
0.005
0.5
03
0.5
05
03
35
0.6
9.6
0.6
50 0.4
0.003
98
90
0,4
05
-0.005
05
0.2
-0.
-05
(a) Vanilla model
(b) AWP
(c) T-AWP
(d) W-AWP, 0 (c) WT-AWP, 0=0.5
Figure 3: Linearly separable dataset, / 2.5. The accuracy of models (a) to (d) is 0.97, 0.51, 0.96, and 0.98 respectively. The face color of each node shows its prediction score and the border color shows the ground-truth label. Grey lines connect the node with its nearest neighbours in the graph.
Algorithm 1 Weighted Truncated Adversarial Weight Perturbation
Input: Graph G' = (A, X); model parameters 0 [0(aup); ((m)] with and without AWP; number of epochs NN; loss function Luain' perturbation strength p. AWP weight X; learning rate a.
Initialize weight Oo:
for / E I:N do Compute the loss for training nodes: Lurai (6:-1;
Compute the approximating weight perturbation for @ ((uup); (( via Eq. 4
Compute the approximating gradient for 0:
g= XVo Turain ( A, ()) 0, 1+18-(0/=7")) + (1 - X) Jarain (0; A, X) 0
Update the weight via 0, = 0, ag
end return ON
source of valid gradients which we do by adding the the vanilla loss Lusin (0: A, X) the AWP loss. Even when the AWP loss suffers from the vanishing gradient issue, the vanilla loss is not affected.
Definition 1. (Truncated AWP) We split the model parameters into two parts 0
[((awp) θ (normal)), and we only perform AWP on glawp), The Truncated AWP objective is
min Lunin (0 + ((aup)) (0 ((aup)) ((lau)))) ),0]; X)).
(
where 8(awp)) (@(awp) == 11 ((((((aw)) ) V ((owp) Linan (0 ((aw)); A,
Recall in Sec. 2 the AWP objective is the unweighted combination of the regular loss function L()) and the sharpness term maxs<; (0 + 8) L(O)]. The weight perturbation in this term can lead to vanishing gradients as we discussed in Sec. 4.1 Therefore, another way to deal with this issue is to assign a smaller weight À to the sharpness term in the AWP objective. The weighted combination is [A ( + 6) L(0)] + L())] = [A max L( + 8) + (1-A)L(0))
Definition 2. (Weighted AWP) Given a weight À E [0, 1] the Weighted AWP objective is
min (a 0 + (0): A, X) + (1 L A,
We compare these two improvements with AWP and natural training on linearly separable dataset using the same setup as in |Sec. 4.1 Fig. illustrates the trained models with = 2. In Fig. 3(b) can that the model with AWP objective suffers from vanishing gradients and it fails to learn anything useful. The models with Truncated (O
first layer and @(normal) = last layer) Fig. 3(C) and Weighted AWP FFgg. 3(e) work well and have relatively good performance (96% and 98% accuracy respectively). Besides, comparing to the vanilla model (Fig. 3(a)), they both have a significantly smoother decision boundary.
In order obtain more powerful approach against the vanishing-gradies issue, we combine Trun- cated AWP and Weighted AWP, into a Weighted Truncated Adversarial Weight Perturbation (WT- AWP). The details of WT-AWP are shown in Algorithm (description in Sec. B.I). WT-AWP has two important parameters À and p. We will study how they influence model performance in Sec. 5.7
In Fig. 3(c) we perturb only the first-layer. Perturbing only the second layer instead performs similarly.
5

---

Under review as a conference paper at ICLR 2022
5 EXPERIMENTAL EVALUATIONS
We conduct comprehensive experiments to show the effect of our WT-AWP on the natural and robustness performance of different GNNs for both node classification and graph classification tasks.
Training frameworks and setup. We utilize the open-source libraries Pytorch-Geometric (Fey and Lenssen 2019) and Deep-Robust (Li al.) 2020) for evaluation clean and robust node classi- fication performance respectively. To achieve fair comparison we keep the same training settings for all models. We report the mean and standard deviation over 20 different train/val/test splits and 10 random weight initializations. See Sec. D.4 for further details and for the training hyperparameters.
Datasets. We use three benchmark datasets, including two citation networks. Cora and Citeseer (Sen et al. 2008), and one blog dataset Polblogs (Adamic and Glance| (2005). We treat all graphs as undirected and only select the largest connected component (more details and statistics
See. D.3)
Baseline models and attacks. We aim to evaluate the impact of our WT-AWP on natural and ro- bust node classification tasks. We train three vanilla GNNs: GCN (Kipf and Welling/ 2017). GAT (Veličković et al. 2018), and PPNP [Klicpera et al. 2018), and four graph defense methods: RGCN (Zhu et al., 2019 GCNJaccard (wu et al.) 2019). GCNSVD (Entezari et al. 2020), and Sim- pleGCN Uin et al. 202T). For detailed baseline descriptions see Seec. D. To generate the adversar- ial perturbations, we apply three methods including: DICE (Waniek et al. 2018), PGD (Xu et al.
2019). and Metattack Züggerr and Günnemann 2019). For discussion of the attacks see Sec. D.2
Certified robustness. We obtain provable guarantees for our models using a black-box (sparse) randomized smoothing certificate (Bojehevski et al., (2020). We report the the certified accuracy, i.e. the percentage of nodes guaranteed to be correctly classified, given an adversary that can delete up to ra edges or add up to Ta edges to graph (similarly for the node features). See See/ D.8 for details.
Settings for WT-AWP. All baseline models have a 2-layer structure. When applying the WT-AWP objective, we only perform weight perturbation on the first layer i.c. we assign (lawp) = first last layer. For generating the weight perturbation we use 1-step PGD as discussed in Sec. 3 In the ablation study Secc. 5.7] we also apply 5-step PGD to generate weight perturbation, in which we utilize SGD optimizer with learning rate 0.2 and update the perturbation for 5 steps, and finally the perturbation is projected on the l2 ball ((p(O)).
layer and @inormat)
5.1 CLEAN ACCURACY
We evaluate the clean accuracy of node classification tasks for different GNNs and benchmarks. The baseline methods include GCN, GAT, and PPNP We use a 2-layer structure (input-hidee outpe))) for these three models. For GCN and PPNP, the hidden dimensionality is 64; for GAT, we use 8 heads with size 8. We choose K 10, a = 0.1 in PPNP. We also find that the hyperparameters (A. p) of WT-AWP are more related the dataset than the backbone models. We use (A 0.7, p 1) for all three baseline models on Cora, (A = 0.7, = 2.5) on Citeseer, and (A = 0.3, p = 1) for GCN, (A 0.3, p 2) for GAT and PPNP on Polblogs. Table 1 show our results, WT-AWP clearly improves the accuracy of all baseline models, while having smaller standard deviations. Note, we do not claim that these models are state of the art, but rather that WT-AWP provides consistent and statistically significant (two-sided t-test, < 0.001) improvements over the baseline models. These results support our claim that WT-AWP finds local minima with better generalization properties.
5.2 AVERAGE OF GRADIENT NORM IN THE INPUT SPACE
To estimate the smoothness of the loss landscape around the adjacency matrix A and the node at- tributes X, we compute the average norm of the gradient of Luman (0; A, X) w.r.t. A and X. We compare vanilla GCN model with GCN+WT-AWY (A 0.5, = 1) model on Cora and Cite- seer. We train 10 models with different random initializations. For each model we randomly sample 100 noisy inputs around A and X, and we average the gradient norm for these noisy inputs. When comparing models trained with and without WT-AWP, we keep everything else fixed, including the random initialization, to isolate the effect of WT-AWP. In Fig. 4] we can observe that in most cases (37 out of 40) the models trained with WT-AWP have both better accuracy and smaller average gra- dient norm, i.e. are smoother. This provides evidence that WT-AWP can help find flatter minima.
Note, cannot apply WT-AWP RGCN the weights are modeled by distributions.

---

Under review as a conference paper at ICLR 2022
Table 1: Clean accuracy comparison. We report the average and the standard deviation across 200 experiments per model (20 random splits x 10 random initializations). WT-AWP consistently out- perform the standard models on all benchmarks. The improvements are statistically significant ac- cording to a two-sided t-test at significance level of p < 0.001.
Approachs GCN
Cora
Citeseer
Polblogs
84.14 0.61
73.44 1.35
95.04 0.66
85.16 0.44
74.48 # 1.04
94.93 = 0
GAT
14.13
73.71 # 1.23
-TT-WT-WWP
85.13 0.51
74.73 # 1.07
95.12 0.48
PPNP
85.56 + 0.46
74.50 = 1.06
95.18 = 0.42
PPNP-WT-AWP
86.13 0.43
75.64 + 0.95
95.36 + 0.37
DC 10017
00M-W11000
CCN-NTTUU
0.12
50
013
45
030
3.0
Aastaged
034
2.0
0.38
35
012
3.4
036
20
008
Acuumay
Accunacy
(a) Cora adj. matrix
(b) Cora node feat. (c) Citeseer adj. matrix
(d) Citeseer node feat.
Figure 4: Comparison of the averaged gradient norm w.r.t. the adjacency matrix and the node features for GCN models with and without WT-AWP on Cora and Citeseer. Each connected pair of points refers to GCN and a GCN+WT-AWP model trained with the same data split and initialization.
5.3 VISUALIZAATION OF Loss LANDSCAPE
GCN
We train GCN, GCN+AWP (p- = 0.1) and GCN+WT-AWP (A =0.5, p 0.5) models with the same initialization, and we compare their loss landscapes. The accuracy is 83.55% for GCN, 84.21 % for ACP+ and 85.51% % for GCN+WT- AWP. Similar to Stutz et al. 202T). Fig. 3 shows the loss land- scape a randomly chosen direction u in weight space, i.e. we plot ( + a u; A, X) for different steps a. We generate 10 random directions u and show the average loss. The loss landscape of GCN+AWP is slightly smoother than the vanilla GCN, because of the small perturbation strength o = 0.1. GCN+WT-AWP is flatter (and more accurate) than both of them due to the larger perturbation strength = 0.5. This provides further evidence for the effectiveness of WT-AWP.
ACN+ GCN+ AWP
Adjusted loss
-0.5
0.5
Step size
Figure 5: Loss landscape.
5.4 ROBUST ACCURACY WITH POISONING ATTACKS
Next we show that our WT-AWP can improve existing defense methods against graph poisoning attacks. We select two poisoning attacks: PGD and Metattack (Zügner and Günnemann, 2019), with a 5% adversarial budget. The baseline models are vanilla GCN, and three GCN-b graph-defens models: GCNJaccard, GCNSVD, and SimpleGCN. For all attack and defense methods, we apply the default hyperparameter settings in [i et al. 22020), which re-implements the corresponding models with the same hyperparameters as the original works. We use Cora, Citeseer, and Polblogs as the benchmark datasets. Note that GCNJaccard does not work on Polblogs as it requires node features. Table 10 in the appendix shows the hyperparameters (A, p) we select for all WT-AWP models.
none of the defense methods have dominant performance across bench- marks. More importantly. our WT-AWP consistently improves the robust accuracy for both vanilla and robust models. We also evaluate the models against the DICE poisoning attack in Sec. C.2, and again the results demonstrate that WT-AWP adds meaningful improvement over the baselines.
As we can see in Table 2
7

---

Under review as a conference paper at ICLR 2022
Table 2: Robust accuracy under PGD and Metattack poisoning attacks, with a 5% adversarial budget.
We report the average and the standard deviation across 200 experiments per model (20 random splits 10 random initializations). Our WT-AWP loss improves over all (vanilla and robust) baselines.
All results expect the one marked with * are statistically significant at p < 0.05 according to t-test.
Natural Ace
Acc with 5% PGDattack
Ace with 5% Metattack
Models
Cora
Citeseer
Polbbogs
Cora
Chesser
Polblogs
Cora
Citeseer
Polblogs
GCN
L.19
1.27
72.04 1.60
2.63
1,93
79.74
+WT-WW
84.66 0.53
74.01
1.11
95.20 0.61
K2.66
1.07
73.73
1.23
85.73 4.11
79.05
1.73
70.50 1665
80.72 1.25
GCNascard
0.73
73.09
1.20
NIA
80.65 4 1.14
72.05
1.76
NIA
7
69.62 1.87
NIA
+WT-AWP
x3.55
74.10 1.04
NIA
a0.1
73.85
1.38
NIA
80.23 a 1.38
71.22 + 1.44
N/A
SimPGCN
0.
74.05 + 1,28
94.77 0.95
80.71
1.33
75.61
1.39
82,42
78.00 1.81
72.52 1.72
76.66 1,80
4WT-AWP
03737+0.74
74.36 + 1,09
94.85
0.91
83.49 = 0..78
74.43 1,14
82.68 +.82
79.76+ 1.76
72.95 1.43
77.68 + 2.41
GUNSVD
77.63-00.63
68.57 # 1.54
94.08 # 0.59
76,83 = 1.42
68.08 = 1.98
3208
76.28 1.15
67.34 + 1.93
91.76 1.19
+WT-AWP
79.05
71.12
91.13
78.50
71.43
70.65
1.28
RGCN
03
71.69 4 1.35
95.15 0.46
78.47 1.10
68.81 2.32
8.562
+7.70 1.69
69.05 a 1,90
79.48 1,16
Table 3: Robust accuracy under evasion attacks of different strength. We report the average and the standard deviation across 200 experiments per model (20 random splits x 10 random initializations). Our WT-AWP loss always improves the robustness of the baseline models.
Perturbation strength
5%
10%
Attacks
Models
Cora
Citeseer
Polblogs
Cora
Citeseer
Polblogs
GCN
82.83 + 0.87
71.85 # 1,31
91.27 = 0.98
81.87 = 0.94
71.17 = 1,50
87.47 # 1.17
DICE
WW--WWP
84.01 0.59
73.84 1.10
91.45 0.86
82.93 0.64
73.14 1.25
87.70 0.97
GCN
79.92 + 0.62
70.50 # 1.35
79.41 0.76
77.17 = 0.74
68.49 = 1.39
72.90 = 0.73
PGD
WT-AWP
81.00 = 0.56
70.69 # 1.45
80.70 # 0.90
77.87 = 0.64
68.96 + 1,30
75.11 1.03
5.5
ROBUST ACCURACY WITH EVASION ATTACKS
Next we show that WT-AWP also improves existing defense methods against graph evasion attacks. We select two evasion attacks, DICE and PGD, with perturbation strengths of 5% and 10%. The baseline model is GCN and perform experiments
three benchmarks: Cora, Citescer, and Pol- blogs, For the PGD attack the hyperparameters (A, p) are (0.5, 0.5) for all datasets. For the DICE attack we (0.5, 0.5) for Cora, (0.7, 2) for Citeseer, and (0.3, 1) for Polblogs. Taale 3 shows the experimental results. WT-AWP again meaningfully improves the robustness of GCN under both PGD and DICE evasion attacks.
5.6 CERTIFIED ROBUSTNESS
In this subsection, we measure the certified robustness of GCN and GCN+WT-AWP on the Cora dataset with sparse randomized smoothing (Bojchevski et al. 2020). We use À 0.5, p 1 as the hyperparameters for the WT-AWP models. We plot the certified accuracy S(r,, ra) for different addition Ta and deletion тa radii. In Fig. 6 we see that compared to vanilla GCN training, our WT-AWP loss significantly increases the certified accuracy w.z. feature perturbations for all radii, while maintaining comparable performance when certifying perturbations of the graph structure.
For additional results see Sec. C.3
0.8
GCN GCN+WT-AWP
GCN GCN+WT-AWP
Acc. S(ra. ra)
0.6
Acc. stra.ra)
0.4
0.4
0.2
0.2
0.0
0.0
10
15
0
5
10
15
(dotted)) ry(solid)
rdootted,), ra(solid)
(a) Node feature perturbations
(b) Graph structure perturbations
Figure 6: Robustness guarantees on Cora. WT-AWP improves the certificate for node features.
8

---

Under review as a conference paper at ICLR 2022
Table 4: Hyperparameter sensitivity study for X and p on the Cora dataset for GCN base model.
sensiiiiiii
WT-AWP
p= 0.05
p= 0.1
p= 0.5
p=
p p= 2.5
p= 5
À 0.1
84.15 0.60
14.15=000)
84.51 = 0.48
84.58 = 0.52
84,50 0.51
$
À 0.3
84.10
84.13 0.58
84.76 0.51
84,91 = 0.46
64.77 0.46
84.64 0.47
À = 0.5
84.11
0.61
84.93 0.49
85.06
0..9
84.67 + 0.49
X = 0.7
84.13
8..1
85.00 # 0,46
0.49
84.66 + 0.49
A 1.0
04.1
84.23
82.45 1.98
60.29 1.94
29.19 29.11
AWP
84.16
84.23
41.19 1.23
29.18
29.18 2.02
0.02
W-AWP
84.12
84.20 + 0.66
84.63 = 0.51
84.32 # 0.65
$3,98
83.62 + 1.27
Table 5: Ablation study with X and p on WT-AWP, where the weight perturbation is calculated with 5 5-step PGD. The backbone model is GCN and the benchmark is Cora.
WT- (5 step)
p 0.05
p= = 0.1
0,5
p = 2.5
p 5
A 0.1
84.19 0.60
84.17
84,45 # 0.51
84.50 + 0150
84.39 = 0.52
84.41 # 0.54
À == 0.3
84.12 # 0.58
84.15 0.63
84.65 + 0.54
84.81
# 0.47
84.70 = 0.50
84.55 + 01.5
À 0.5
84.10 0.59
84.11 1 0.62
84.77 0.53
84.90
0.50
84.82 + 0.47
84.64 + 0.52
A 0.7
84.12 0.61
84.11
84,86 + 0.49
84.99
= 0.48
84.89 0.51
84.64 + 0.52
A 1.0
84.11 # 0.62
0.63
72.18 1.48
32.55 # 6.80
29.18 = 0.03
29.18 + 0.00
5.7 ABLATION AND HYPERPARAMETER SENSITIVITY STUDY
We compare the performance of GCN+WT-AWP on the Cora dataset for different À and values. We also compare GCN+WT-AWP with GCN+AWP under different perturbation sizes p. Table 4 llists the results. The accuracy of GCN+WT-AWP first increases with À and P and then slightly decreases. Truncated AWP a special case for À (since the (1-X) term disappears Ing.q. 9 and it does not perform well, especially for larger Similarly, WT-AWP outperforms the vanila AWP that suffers from the ranishing-gradies issue. Weighted but not truncated AWP with = 0.5 (last row) is also worse than WT-AWP, although in general weighting seems to be more important than truncation. These results justify the decision to combine our proposed weighted and truncated AWP methods.
We also generate perturbations as in Eq. 4/but with multi-step PGD. We repeat the above experiment with applying 5-step PGD for WT-AWP. As shown in Table 5] the performance of 5-step WT-AWP is similar to the 1-step WT--AWP, the accuracy of both models first increases with À and p. and then decreases. The optimal hyperparameters (h,p) p) are p = 1 = 0.7. Since 5-step PGD offers no benefits and 1-step PGD is faster, we suggest this as the default setting when applying WT-AWP.
5.8 GRAPH CLASSIFICATION
Finally, we conduct experiments on graph classification tasks with three benchmark datasets: Pro- tein, IMDB-Binary and IMDB-Multi. Detailed description is in [Scc. D.9 Table 6 shows the ex- perimental results. Generally, WT-AWP improves the accuracy with a large margin. Besides, the variance of the accuracy of GCN+WT-AWP across different random seeds is significantly smaller than the vanilla GCN, which indicates that WT-AAPP is also more stable. Note, we do not claim that our models are state the art, but rather that WT-AWP provides consistent improvements.
Table 6: Performance of WT-AWP graph classification tasks, the backbone is GCN.
Proteins
MMDB-Binary
IMDB- Multi
GCN
75.05 + 1.40
72,40 + 2.73
55.53 1.33
GCN+WT-AWP
76.48 # 0.49
75.80 1.17
57.26 0.63
6 CONCLUSION
We proposed a new adversarial weight perturbation method, WT-AWP, and we evaluated on graph neural networks. We showed that our WT-AWP can improve the regularization of GNNs by finding flat local minima. We conducted extensive experiments to validate our method. In all empirical results, WT-AWP consistently improves the performance of GNNs tasks including node classification, graph defense, and graph classification. Further exploring the connections between flat minima and generalization in GNNs is promising research direction.
wide range of graph learning

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
All datasets, baseline models, and general training settings are listed at the beginning of For specific tasks include the detailed settings in the corresponding sections. For example, the de- tailed model structure and hyperparameter settings for GCN clean accuracy is discussed in Sec.. 5.1 We will make our code available to the reviewers via an anonymous link posted on OpenReview as suggested by the guidelines.
ETHICS STATEMENT
In this paper we design new regularization method that can improve the robustness of graph neural networks again adversarial attacks. Making GNNs more robust have positive negative broader impacts depending on the application and the domain. While we observed that WT-AWP improves both clean and robust generalization, we did not study whether these improvements come at cost to e.g. the fairness of the model, or whether they introduce certain biases in the model.
REFERENCES
L. A. Adamic and N. Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery, pages 36-43, 2005.
A. Bojehevski, J. Klicpera, and S. Günnemann. Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference on Machine Learning, pages 1013, PMLR, 2020.
L. Dinh, R. Pascanu, S. Bengio, and Y. Bengio. Sharp minima can generalize for deep nets. In International Conference on Machine Learning, pages 1019-1028. PMLR, 2017.
N. Entezari, S. A. Al-Sayouri, A. Darvishzadeh, and E. E. Papalexakis. All you need is low (rank) defending against adversarial attacks on graphs. Proceedings of the 13th International Confer- ence on Web Search and Data Mining, pages 169-177, 2020.
M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
P. Foret, A. Kleiner, H. Mohahi, and B. Neyshabur. Sharpness-awan minimization for efficiently improving generalization. ICIR, 2021.
Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio. Fantastic generalization measures and where to find them. arXiv preprint arXiv: 1912.0211 2019.
W. Jin, T. Derr, Y. Wang, Y. Ma, Liu, and J. Tang. Node similarity preserving graph convolutional networks. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pages 148-156, 2021.
N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P. T. P. Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609.00 04836, 2016.
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. ICLR, 2017.
Klicpera, A. Bojchevski, and S. Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. ICLR, 2018
J. Kwon, J. Kim, H. Park, and I. K. Choi. Asam: Adaptive sharpness-aware minimization for scale- invariant learning of deep neural networks. arXiv preprint arXiv:2102. /6000, 2021.
Y. Li, W. Jin, H. Xu, and J. Tang. Deeprobust: A pytorch library for adversarial attacks and defenses. arXiv preprint (rXX::2005.06/49 2020.
Ma, J. Deng, and Q Mei. Subgroup generalization and faimesss of graph neural networks. arXiv preprint arXiv: 106. /5535, 2021.
10

---

Under review as a conference paper at ICLR 2022
D. A. McAllester. Pac-bayesian model averaging. In Proceedings of the twelfth annual conference on Computational learning theory, pages 164-170, 1999.
B. Neyshabur, S. Bhojanapalli, D. McAllester, and N. Srebro. Exploring generalization in deep learning. NIPS, 2017.
Sen, Namata, M. Bilgie, L. Getoor, Galligher, and T. Eliassi-Rad. Collective classification in network data, Al magazine, 29(3):93-93, 2008.
O. Shehur, M. Mumme, A. Bojchevski, and S. Günnemann. Pitfalls of graph neural network evalu- ation. arXiv preprint arXiv:1811.05860 2018.
D. Stutz, M. Hein, and B. Schiele. Relating adversarially robust generalization to flat minima. arXiv preprint arXiv: 104.04488, 04448, 2021.
L. Sun, Dou, Yang, Wang. P. S. Yu, He, and B. Li. Adversarial attack and defense on graph data: A survey, arXiv preprint arXiv:18/2.10553 10528, 2018.
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention net- works. ICLR, 2018.
M. Waniek, T. P. Michalak, M. Wooldridge, and T. Rahwan. Hiding individuals and communities in social network. Nature Human Behaviour, 2(2):139-147, 2018.
D. Wu, S.-T. Xia, and Y. Wang, Adversarial weight perturbation helps robust generalization. NIPS, 2020a.
H. Wu, C. Wang. Y. Tyshetskiy, A. Docherty, K. Lu, and L. Zhu. Adversarial examples graph data: Deep insights into attack and defense, arXiv preprint arXiv:/905 000000610, 2019.
Z. Wu, Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip. A comprehensive survey on graph neural networks. IEEE transactions neural networks and learning systems, 32(1):4 24, 2020b.
K. Xu, H. Chen, S. Liu, P.-Y. Chen, T.-W. Weng, M. Hong, and X. Lin. Topology attack and defense for graph neural networks: An optimization perspective. arXiv preprint 1906:::906.042111 14, 2019.
P. Yanardag and S. Vishwanathan. Deep graph kernels. In Proceedings of the 2 ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365-1374, 2015.
Y. Zheng. R. Zhang, and Y. Mao. Regularizing neural networks via adversarial model perturbation. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 81 1166-8165, 2021.
D. Zhu, Z. Zhang, P. Cui, and W. Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Dis- covery & Data Mining, pages 1399-1407, 2019.
D. Züggnrr and S. Günnemann. Adversarial attacks on graph neural networks via meta learning. ICLR, 2019.
D. Zügner, A. Akbarnejad, and Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings the 24th ACM SIGKDD International Conference Knowledge Discov- ery & Data Mining, pages 2847-2856, 2018
11

---

Under review as a conference paper at ICLR 2022
Supplementary Material
A PROOFS
Proof. Theorem 2) We only show the proof with local minimums, the proof with local maximum is analogous. For case of calculation we denote Lunin (0; A, X) by L(0). We need to show a) Vo VoL(0+ (0) 0, and b) A. VoT( o. positive definite.
a) Since l is local minimum of L, we have VoL(0)le- = 0, thus
VeL(O VoL(0))
(I - vot(0)00
(10)
- ((=)
b)
Vo VoL()))) Vol(! + (0l1++AAA20))o444++000000000
Vo (
+ + (1===44000))000000000=====000000 AOL(O))) (II)
(7 (4++
Because (I AoL(0))le- and AoL(0))e- positive definite matrices, and Vo(VoL + VoL(O)) 0x = (I + - ( (0) (I + AeL(O)) is symmetric, Vo
VOL 0.. positive definite. Thus 0 is also the local minimum of L(0 VoL(O)).
B VANISHING-GRADIENT ISSUE OF AWP ON MLP
In this section we show that the vanishing-gradien issue also happens in multi-layer perceptrons. Consider MLP (.. with softmax activation at the output layer. The per- turbed model is be large as pl Wsllz- in the worst case the norm of each layer is (p+ D||W:lls and thus the model will have exploding logit values when p is large. After feeding large logits into the softmax layer, the output will approximate one-hot encoded vector, because the difference between the entries of the logits will also be large. The gradient will be close to 0 and the weights will not be updated.
) X))). Since the norm of each perturbation ó; could
To verify our conclusion we train 3-layer linear network with W; 1100 106
2x20100 W. W E R 100x2 on a linearly separable dataset, the number of training epochs is 2000. Fig. 7 we show the trained classifiers with different p. find that models with AWP are crushed quickly when p increased from 0.2 to 0.25. When p 0.25, the value of loss function remains un- changed during training and the prediction score is around 0, which indicates the weights are almost not updated during training. So with the AWP objective, cannot select large p.
17%
05
130
0n
(a) Natural model
(b) AWP ==
(c) AWP p = 0.2 (d) AWP p = 0.23
(e) AWP p 0.25
Figure 7: Comparing AWP models on linearly separable dataset with different p values.
We repeat the experiment using the same 3-layer linear network on a 2d moons dataset and perform the weight perturbation only the first two layers. Fig. Illustrrae the trained models with p 0.4.
12

---

Under review as a conference paper at ICLR 2022
0-
033
0.0
0.30
03
030
0.0
0.50
0.35
4.2
A35
425
0.0
0.0
06
-1.00
-0.75
0.00
D.6
-0.75
-1.00
0.0
1.0
-0.75
-1.00
000
07
-0.7
-1.00
(a) Natural model
(b) AWP
(c) T-AWP
(d) W-AWP, =
Figure 8: Model comparison on the two moons dataset, p = 0.4
In Fig. 8(b) we can see the model suffers from vanishing gradients, while the model with truncated AWP works well (Fig. 8(c)). Besides, comparing to the overfitted natural model (Fig. 8(a). the truncated AWP model has a smoother decision boundary. We also remove the weight perturbation on the middle the first layer and train the model correspondingly, the results
similar to Fig. 8(c)
As Fig. 8(d) shows, the model with the weighted AWP objective is able to learn the representation of the input data, and the decision boundary is also smoother than the nature model in Fig. 8(a)
B. DESCRIPTION OF ALGORITHM
In the WT-AWP algorithm Algorithm we apply a numerical optimizer such as Adam to the WT-AWP objective
LwT-Awr(O). = [A (f (((au))
((lau)) (plawp), ), 0]: X) + A) Trrain (0; A, X)]
Since in our empirical experiments the GNNs always have 2-layer structure, we assign (awp as the first layer and guormal as the last layer. Then the perturbation 8lawp)> (first layer) is computed via Eq. (4). Next the gradient 9 of LWT-AN AWP calculated with Eq. (6).
g XV Lurain (0; A, X) 10-1+10000//"" + V) Vaninn (0; A, X))o,
Finally we update the weight via fg = 02-1 - ag.
C ADDITIONAL EXPERIMENTS
C.I LEARNING CURVES AND GENERALIZATION GAP DURING TRAINING
In this part, we train GCN, GCN+AWP (p 0.1) and GCN+WT-AWP (A 0.5, p 0.5) models with the same random initialization and compare their learning curves, and generalization gap. The accuracy is 0.8355 for GCN, 0.8421 for GCN+AWP, and 0.8551 for GCN+ Fig. 9a) illustrates the learning curve of vanilla loss Turain (0 A, X) during training. The loss of all three models converges well. The final value of GCN+WT-AWS believe it is because GCN+WT-ANS generalization gap during training. Because we use a large perturbation bound p in GCN+ its generalization gap fluctuates more and decrease slower compared to the gap of GCN+ The fluctuation is due to the exploding logit problem AWP with large P value. When happens, the regular loss included in WT-AWP minimize (but not completely eliminate) its influence. Despite the fluctuation, the generalization gap of GCN+WT-AWP decreases with time as well.
larger than the rest two models. We finds different (flatter) local minimum. Fig. 9b) shows the
C.2 ROBUST ACCURACY WITH POISONING DICE ATTACK
We conduct additional experiments on poisoning the graph with DICE attacks. The general model settings are the same Sec. 5.4 The WT-AWP hyperparameters (A, p) shown in Table 8 Table 7 illustrates the experimental results. The models that achieve best performance on given dataset are all based WT-AWP. Besides, WT--AWP also consistently boost the performance of the baselines.
13

---

Under review as a conference paper at ICLR 2022
0.30
3.0
GCN
GCN+ AWW
0.25
SWW+AWP
2.5
GCN+ WT-AWP
Generation gap
0.20
2.0
Loss
0.15
0.10
0.05
0.5
0.00
0.0
0
50
100
150
200
50
100
150
200
Epochs
Epochs
Learning curves
(b) Generalization gap
Figure 9: Learning Curves and Generalization Gap During Training.
Table Robust accuracy with 5% poisoning DICE attacks. We report the average and the standard deviation across 200 experiments per model (20 random splits x 10 random initializations).
Natural Ace.
Acc. with 5% DICE attack
Approachs
Cora
Citeseer
Polblogs
Cora
Citeseer
Polbiogs
GCN
83.73 + 0.71
73.03
1.19
95.06 # 0.68
82,60 0.76
71.89 + 1.17
90.13 # 0.82
+WT-AWP
84.66 # 0.53
74.01
1.11
95.20 = 0.61
83.87 0.62
73,68 +1.06
90.31 + 0.79
GCNJaceard
0.73
73.09
1.20
N/A
81.55
72.22 + 1.22
N/A
+WT-AWP
0.60
74.10 1.04
N/A
82,86 0.73
73,95 + 1.04
N/A
SimPGCN
0.68
74.05
1.28
94.67 # 0.95
82.11
73.53 + 1.23
89.57 1.06
+WT-AWP
74.26 1.09 0.74
94.85 = 0.91
8373
73.89 + 1.08
90.13 1.03
GCNSVD
0.63
68.57 + 1.54
94.08 + 0.59
0.991
67.27 + 1.67
90.80 + 0.88
+WT-AWP
71.12 1.42 0.508
77.51
70.30 + 1.22 1.22
91.11 0.76
RGCN
83.29
71.69 1.35
82.02 0.445
70.18 + 1.38
90.03 0.67
14

---

Under review as a conference paper at ICLR 2022
GCN GCN+WT-AWP
GCN GCN+WT-AWD
0.6
0.6
Acc. a( ra)
Acc. Stra. rd)
0.4
0.4
0.0
0.0
5
10 15
5
10
15
ra(dotted), (sosiid))
ra(dotted), ra(solid)
(a) Node feature perturbations
(b) Graph structure perturbations
Figure 10: Certified adversarial robustness the Citeseer dataset.
Table 8: Hyperparameters of WT-AWP for poisoning DICE attacks
(), p) GCN
Cora
Citeseer
Polblogs
GCNJaccard (0.5, 0.5)
(0.7, 2)
(0.3, 1)
GCNSVD
SimPGCN (0.1, 0.5)
(0.5, 0.1) (0.5,
C.3 CERTIFIED ROBUSTNESS ON CITESEER DATASET
We measure the certified robustness of GCN and GCN+WT-AWP with randomized smoothing (Bo- jehevski et al. 2020) on the Citeseer dataset. We use À = 0.5, p as the hyperparameters for WT-AWP models. We plot the certified accuracy S(ra,ra) w.r.t Ta and ra- As seen Fig. 10 comparing with the vanilla GCN, WT-AWP significantly increases the certified accuracy for pertur- bations to the node features for radii, while having comparable performance for certification of the graph structure.
D EXPERIMENTAL DETAILS
D.1 DESCRIPTION BASELINE MODELS
We aim to evaluate the impact of our WT-AWP on natural and robust node classification tasks, thus we utilize the well-known graph neural networks and graph defense methods baseline. We first train the baseline models and compare their performance with the baseline models trained with WT-AWP objective (if applicable). The baseline GNN models include:
GCN (Kipf and Welling, 2017): one of the most representative graph convolution neural networks. Currently it can still achieve SOTA on different graph learning tasks.
2018): utilizes multi-head attention mechanism to learn different weights for each node and neighbor node without requiring the spectral decomposition.
GAT (Veličković et al.
2018): improves the GCN propagation scheme based the personalized Pagerank. This approach generates predictions from each node's own features and propagates these predictions using an adaptation of personalized PageRank.
PPNP (Klicpera et al.
RGCN (Zhu et al. 2019): applies the Gaussian distribution to model the node representations. This structure is expected to absorb effects of adversarial attacks. also penalizes nodes with large variance with an attention mechanism. Notice, the WT-AWP cannot be applied RGCN,
as the weights of RGCN are modeled by distributions. We can regard RGCN as another model inspired by PAC-Bayes theorem,
models the objective E8-N(0. [Q 8: A. X)), which also bounded Taa (0; A, X) according PAC-Bayes theorem.
15

---

Under review as a conference paper at ICLR 2022
GCNJaccard (Wu al. 2019): is graph defense method based GCN. It pre-proeeee processessss the graph by deleting edges, which connect nodes with a small Jaccard similarity of features, because attackers prefer connecting nodes with dissimilar features. This method only works on graph with node features. For example it cannot work on Polblogs because the node features unavailable.
GCNSVD (Entezari al.) 2020): is graph defense method based GCN, which focuses on defending nettack Zügner et al. (2018). Since nettack is a high-rank attack, GCN-SVD pre- processes the perturbed graph with its low-rank approximation. straightforward extend it to non-targeted and random attacks.
SimpleGCN (Jin et al., 2021): utilizes similarity preserving aggregation to integrate the graph structure and the node features, and employs self-supervised learning capture the similarity between node features. Notice SimpleGCN is not specifically designed for graph defense, and we find it also has good performance under the poisoning attacks, thus we add this method as another graph defense baseline.
D.2 DESCRIPTION GRAPH ATTACK METHODS
Generally speaking, there are two types of the adversarial attacks node classification tasks: test- time attack (evasion) and train-time attack (poisoning). In both types of attacks we first generate perturbed adjacency matrix based victim model, and then in evasion attacks test it directly on the victim model, and poisoning attacks we train new model with the perturbed adjacency matrix. For generating the adversarial perturbations, apply three methods:
DICE (Waniek et al. 2018): is baseline attack method (delete internally, connect externally). each perturbation, we randomly choose whether to insert or remove an edge. Edges are only removed between nodes from the same classes, and only inserted between nodes from different classes.
PGD (Xu al. 2019):
calculates the gradient of the adjacency matrix, and the gradient serves probabilistic vector, then random sampling is applied for generating near-optimal binary perturbation based on this vector.
Metattack (Zügner and Günnemann 2019): : was proposed to generate poisoning attacks based meta-learning. It has an approximate version A-Metattack. our experiments, we apply the original Metattack.
D.3 DATASETS STATISTICS
Cora and Citeseer (Sn et al. 2008 are citation datasets commonly used for evaluating GNNs. Polblogs (Adamic and Glance political blog. In Table 9 we provide the statistics for each graph. We preprocess the graph and only use the largest connected component.
2005) is another common benchmark dataset where each node is
Table 9: Dataset Statistics
Datasets
Cora
Citeseer
Polblogs
#Nodes
2708
3327
1222
#Edges
5429
4732
16714
#Fcatures
1433
3703
N/A
#Classes
7
6
2
D.4 TRAINING SETUP
Optimization hyperparameters. We use the Adam optimizer with a learning rate 0.01 and weight decay of 0.0005. All models are trained for 200 epochs with no weight scheduling. We add a dropout layer with rate p 0.5 after each GNN layer during training. We apply early stopping and the optimal model selected with its performance on the validation set. The test set is never touched during training.
16

---

Under review as a conference paper at ICLR 2022
Train/val/test split. The evaluation procedures of GNNs node classification tasks have suffered overfitting bias from using a single train-test split. Shchur et al. (2018) showed that different splits could significantly affect the performance and ranking of models. In all our experiments
node classification tasks, we apply the split setting in Zügner and Günnemann) (019)), which utilizes 10% samples for training, 10% samples for validating, and 80% samples for testing. We generate 20 random splits and for each split we train 10 models with different random initialization. We report the mean and standard deviation of the accuracy of the 200 random models in our results.
D.5 SETTINGS OF THE AVERAGE OF GRADIENT NORM
For the results in Sec. we generate noise AA, 2x from Gaussian distribution ((A,o² and [(X, I)) then calculate the l2 norm of the loss gradient IIV Luraia (0; A, X) \=)A==a ll and ||V x Lunin (0; A, A== ll2.
our experiments we choose a = 0.0005, because we expect the perturbed input to be close to the clean input.
D.6 SETTINGS OF VISUALIZATION LOsS LANDSCAPE
we generate random direction from Gaussian distribution and perform 12 normalization, it is equal to randomly selecting a direction on the l2 unit ball. As seen in Fig. (a) there is a large gap between the final loss value of WT-AWP and vamilla GCN, have to parallel move the loss landscape of WT-AWP and GCN to the same level for making comparison. The experiments performed Cora, similar results also hold for other datasets.
For the results in Sec. 5.3
D.7 HYPERPARAMETERS (A, p) FOR POISONING ATTACKS
Table 10: Hyperparameters of WT-AWP for poisoning PGD attack and Metattack of Sec. 5.4
(X.
Cora
Citeseer
Polblogs
GCN
GCNJaccard (0.7, 0.5)
(0.7, 2)
(0.5, 0.5)
GCNSVD
(0.3, 2) Metattack
SimPGCN (0.3, 0.5)
(0.5, 0.1)
(0.5, 0.5) PGD
D.8 RANDOMIZED SMOOTHING
Following Bojchevski et al. (2020). we create smoothed versions of our GNN models by randomly perturbing the adjacency matrix (or the node features) and predicting the majority vote for the randomly-perturlon samples. We denote with Pa the probability of flipping an entry from i.c. adding an edge or feature, and with pa the probability of flipping an entry from to 0, i.e. deleting an edge or a feature. In all experiments, for the certification of node features we generate random perturbations with Pa 0.01, Pa 0.6, and for perturbing the adjaceney matrix Pa = 0.001, Pa = 0.4. We consider the prediction of the smoothed GNN for a given node correct and only if it correct and certifiably robust. This means the prediction of the node does change for any perturbation within the radius (i.e. for any ra deletions or ra additions).
1,
D.9 GRAPH CLASSIFICATION
Table 11: Dataset Statisties.
Datasets
Proteins
IMDB-B
IMDB-M
#Nodes (max)
620
136
89
#Nodes (avg)
39.06
19.77
13.00
#Graphs
1113
1000
1500
#Classes
2
2
3
17

---

Under review as a conference paper at ICLR 2022
Datasets. We three popular graph classification datasets, including bioinformaties dataset Proteins, and two social network datasets IMDB-Binary and IMDB-Multi (Yanardag and Vish- wanathan 2013) for evaluation. The details are shown in Table II
Settings. We use 80% samples for training, 10% samples for validating and the rest 10% for testing. The baseline model is two-layer GCN with 16 hidden dimension and global mean pooling layer after the second graph convolution layer. A linear read-out layer is attached to the output of the GCN generate predictions. We apply the same training settings for GCN and GCN+WT-AWR We train both models for 200 epoches with the Adam optimizer, learning rate 0.01 and weight decay 0.0005. The best model selected with only the validation accuracy. For each of GCN and GCN+WT- AWP we take 10 random initialization and report the average accuracy and standard deviation. The hyperparameters (X, p) of WT-AWP (0.3, 0.5) for Proteins, (0.05, 0.1) for IMDB-M and (0.5, 0.1) for IMDB-B.
D.10 NORM OF GRADIENT DURING TRAINING
In this experiment train vanilla GCN, GCN+AWP with p 0.1, GCN+WT-AWP with À 0.5, p = on Cora and plot the relative gradient norm | 0||2 during training. Both AWP and WT-AWP have small relative gradient norm compared to GCN when epoch is larger than 100.
GCN
0.012
WT AWP
gradlent norm
0.010
0.008
0.006
0.004
0.002
0.000
25
50
75
100 Epochs
125
150
175
200
Figure 11: Norm of Gradient during training.
D.11 ABLATION STUDY OF THE PERTURBED LAYER
Since in all experiment above only perturb the first layer of GNN with WT-AWP, provide experimental results corresponds to perturb only the second layer with WT-AWP. The backbone is GCN and the benchmark Cora. As Table 12 shows. skipping the first layer in WT-AWP methods have worse performance than skipping the last layer.
Table 12: Ablation study with À and P WT-AWP, where only AWP on the last layer. The backbone model GCN and the benchmark is Cora.
WT-AWP (last layer)
p 0.05
== 0.1
== 0.5
==
== 2.5
p=
À 0.1
84,09 + 0.62
0.66
84.18 + 0.60
83.87 = 0.85
81.40 1.92
65.34
À 0.3
84.14 0.58
0.58
84.12
84.14
82,30
33,50 1.48
2..08
0.5
84.13 4 0.66
8..10
84,08 0.77
78.00
29.18
0.00
29.18
À 0.7
8..12
8..14
83.74
67.37
0.00
29.18
À 1.0
84.20 1.20000.2
0.65
82.80 + 1.04
29.18
29.18
29.18
18

---

Under review as a conference paper at ICLR 2022
E GENERALIZATION BOUND ON GNN NODE CLASSIFICATION
Theorem 3. (generalization bound) Assuming Laut (a A, X) I Ez=N(1.,)) Lau + 2; X)), for any set of training nodes Virain from Vall, Vm > Vd, with probability at least 1 - 5, we have
Lan (0; A, A) <
[Lrrain (0 +0+0 8; X)] + 1181225
max
m
c
m
a yd/2
d
(12)
1 NNo
1 1 dlog(1 +
m²110
+ In
3 1
+ O(K -aal)
dp²
8
where d is the number of parameters in the GNN, K is the number of groundtruth labels, fall is fixed constant w.r.t. Vall. Nu is the volume of Verain-
We use the assumption in Foret et al. 2021), Lan (0; A) S. (o,- (0 + 2; A,), which means that adding Gaussian perturbation should not decrease the test error.
Proof. Our proof is motivated by the subgroup generation bound on node classification tasks (Ma al. 2021 and the intuition of theorem in Foret et al. (2021).
Lemma 1. (PAC-Bayes bound node classification tasks (Ma et al 202 For any set of training
nodes Verain from Vall. for any subgroup of nodes Vm. C Valt. for any prior distribution P, with probability at least 5, for any distribution we have
3 +0(em) (13) 1 (Dki(Q)P)+ +
Eg ol A, X)] S Lenan (0; X)]
VNo
where No is the volume of the training Verains K is the total number of classes, em is constant depend on the subgroup Vm-
If we take Vm Vaul in Lemma
we have
3 + +K=+ (14)
Ea (0; A, x)] S E. o mmmin (0; A, A,) + VNo (mx (21P)) In
Assume both P and Q Gaussian distributions with diagonal covariance matrix, ie. P, N (u ozla))))) Qi ~ (p Ia)), where d is the dimension of 0, we have
a2 d + d
[KI( = log d
_ + of
Up
Hg
2
(15)
Take By = 0, Mp 0, we expect the KL-divergence DKI(Q11P) be small as possible w.r.t. dp-
Lemma 2. (Foret et al. 2021 Take 24 = 001pp = 0. There exist pre-defined op such that
1 DKl(
|00
1 + dog((1 +
(16)
do?
Thus we have the generalization bound
Ee-g| Lnn (0; A,X)] < En 2 Umain (0; A, X)]
1
||01
(17)
+
1 dlog(1
+ In
+ ((Kall)
NNo
do² 4
4
19

---

Under review as a conference paper at ICLR 2022
As Q No0, ) consider NO diag(og)),
have =
(N and
"v
Eaw @ (0; A, X)] = E2 Lurii (0 + z; A, X)]. Thus we have Vm >
Eg 2 Lirain (8: XX]
= Luain (0 + 2 A, X)]
2
= E Luain (0 + Ax);
la <
ml
[[[
12 S m)
Og
4q
2
x 112 m))
+ E, Luain (0 + 2; A, X)I
112
m
P(I
(18)
0q
09
< max Smm,
LLrain (0 + 6; A, X [[]
2 S m)
+ F(I
12 > m)
0g
K max 1 Sma,
LLraii (0 + 6; A, X ) + P(| bg
12 m)
As 2. NO, Ia), by Chernoff bound chi-squred distribution we have when m Vd.
m1 c P(I 112 > m. S 0q
m²
5012
(19)
Thus
E Tarain (0; X)] S
max
[Tuaii (0 + 5; A, X)] + m --- -
) )d/2
m²
(20)
16lasmma
combining it with Eq. 17 and denote 0g p/m we have
m
c m² ya12
(O; A,
S max 100
Lraain (0 8; A, X)]
d
(21)
1
1
+ d dlog(1 + m² 10113
3
v No
2
dp2
In
+
+ +((eat)))
20


Reviews:
[{"review_id": "gkHybJcv4NX", "reviewer": "Reviewer_DWF4", "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": "This paper focuses on extending AWP to GNN. This paper analyzes the vanishing-gradient issue existing in AWP and gives a more detailed theoretical proof. The experimental part of this article is comprehensive, and the experimental results also verify the advantages of the proposed method.\n\nHowever, there still exist some insufficiency and confusing places.\n\n1, What is the term h in equation(3). The statements said h is a monotonously increasing function. Where is it from?\n\n2, The paper utilized comprehensive experiments to show the efficiency when facing attacks, but no analysis and theoretical proof for this advantage. I think the source of the advantage in handling attacks is worth clarification. Especially, in Table 2, some experimental results under attacks are even better than the natural setting.\n\n3, Figure1 and Figure3 are blurred. I can not distinguish face color and border color. It is recommended to use vector graphics.\n\n4, The sentence on Page 5 footnotes \"Perturbing only the second layer instead performs similarly.\" is confusing for me.\n", "summary_of_the_paper": "The paper designed and tested WT-AWP, a new adversarial weight perturbation approach, on graph neural networks. They demonstrated that by locating flat local minima, our WT-AWP can improve the regularization of GNNs. They carried out comprehensive tests to verify the method. WT-AWP reliably increases GNN performance on a wide range of graph learning tasks, including node classification, graph defense, and graph classification.", "summary_of_the_review": "The paper is well-organized and has comprehensive experiments to defense its method. However, some statements and equations are not clear enough. The illustrations and figures are not meticulous. I hope the authors can further polish the paper in detail.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RWgiUhPcUSR", "reviewer": "Reviewer_MYVq", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths:**\nThe line of work concerning adversarial weight perturbations is interesting and significant, as it is one of a few locations where the nascent theory of deep networks can provide easy tweaks to training that improve generalization. Identifying a problem with the current approach (even on MLPs) is valuable and significant, and ample evidence is presented to suggest the vanishing gradient problem is actually what is occurring. The proposed solutions are simple and easy to implement. The experimentation is thorough: while the improvements provided by AWP are very minor (less than a percent in some instances), it is yet another easy and cheap trick to ever-so-slightly boost the performance of a network. \n\n**Weaknesses:**\nFirst, while it is an important insight to notice the vanishing gradient, the proposed remedies (weight truncation and weighted AWP) are natural and not particularly novel. These are likely the first things that one would try to mitigate the observed problems with AWP and don't represent a great stride forward in the field. Similarly, it is not particularly surprising that the benefits of AWP as evidenced in MLPs carry over to GNNs: not enough motivation or evidence is presented to make this seem surprising or unexpected. Third, Theorem 1 is trivial. If the definition of Ltrain is to be the one that only performs a single first-order step, then of course the gradient evaluated at a minimum is going to be zero: the interesting question here is how the true AWP loss (eq2) relates to the standard training loss. This theorem doesn't add add anything to the story. \n\n**Questions:**\n- One of my complaints is about the novelty of contribution re: GNNs vs MLPs. Did I miss this, or is there simply a much more pronounced effect of the gradient-vanishing phenomenon in GNNS than MLPs? \n- How much do the gradient norms (with respect to the weights) actually change when training under AWP vs WT-AWP vs standard training?", "summary_of_the_paper": "The authors extend the line of work related to adversarial weight perturbations: first showing that a vanishing gradient issue in standard AWP can hinder training. To remedy this, some natural tweaks are applied to AWP. The authors then focus on using AWP to train graph neural networks, demonstrating a minor boost in both clean and robust accuracy. \n", "summary_of_the_review": "This is an interesting line of work, and the pointing out of (and subsequent fixing of) the gradient-vanishing phenomenon in AWP is a valuable contribution. Past this, none of the results are strikingly novel or groundbreaking. I think this is a borderline paper, tending towards rejection, but could be convinced to boost my score slightly if I've misunderstood something. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RI2I8L-IUr", "reviewer": "Reviewer_2WEe", "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": "Strengths:\n- The paper is generally clearly structured and written; the toy example visualizations are nice and the algorithm helps understanding.\n- An interesting problem/question is addressed: how to effectively use AWP/sharpness-aware minimization for graph neural networks.\n- It is also nice to show that the optimum does not change with AWP training.\n- Experiments for clean and robust accuracy with several models are conducted. Besides mean, standard deviation is reported which is nice to judge the improvement.\n- The approach improves across the board, even though improvement is small at times.\n- Analysis in terms of flatness (gradients and visualization) and ablation studies are provided.\n\nWeaknesses:\n- In the introduction, the authors state the i.i.d assumption as an important criteria for existing flatness approaches. However, it is not discussed when this becomes relevant. As far as I am aware, the i.i.id assumption does not play an important role in related discussion/papers. Could the authors comment on that? As I understand the paper, the main point is to see how these approaches work in non i.i.d settings such as node classification, but the paper does not really theoretically discuss this issue.\n- One paper that could be included in related work as it is quite related:\n\n[a] https://arxiv.org/abs/1609.04836\n\n- Also a discussion of scale-invariance and the criticism of [b] is missing (this should be handled as in Stutz et al., but it would be interesting at least to say why this generalizes to the GCNs considered)\n\n[b] https://arxiv.org/pdf/1703.04933.pdf \n\n- Notation-wise, the main sections could be improved by making explicit that a per-layer neighborhood B is used from the beginning. Currently, this is made clear in Eq. (4) while Eq. (1) to (3) suggest that all parameters are appended.\n- Also, are the GCN baselines equipped with biases in addition to the weights? If so, are biases and weights treated as separate layers (as in Stutz et al.)?\n- In terms of contributions, the theoretical contributions (mainly Thm 1) and methodological contributions seem a bit limited. Although I have not seen Thm 1 in other papers (which makes it refreshing to actually see it), I found that the result is very intuitive and the proof is also quite straight-forward. The techniques employed to improve AWP also seem very specific to graph problems where larger \\rho are used than for vision problems. Thus, I see the contributions mostly in verifying this approach on graph data.\n- Regarding the vanishing gradient problem: I am having difficulties understanding why \\rho has to be chosen as large as done throughout the toy example and the experiments. Stutz et al. And Wu et al. Consider very small \\rho of 0.5% (=0.005 or lower). Obviously these are much deeper networks and not graph neural networks. I am wondering if the authors could give more details on why a large \\rho is needed. Is it because of the 2-layer structure or the architecture differences?\n- The two proposed approaches do actually not improve performance on the toy example. While I understand that it is meant for illustration purposes, I believe it is badly chosen. I see that without truncation and weighting the accuracy is very bad, but shouldn’t you show that you can improve over the baseline of 98% and not be stuck at 95%? Did you try optimizing hyper-parameters, or is it a problem where TW-AWP just does not help (which would be interesting!)?\n- Regarding 5.2, I am not entirely convinced that the gradient norm is the best indicator of flatness exactly because of the scale-invariance argumentation of Stutz et al.: Can the authors comment on that? I guess that the used GCNs do not use batch normalization (I have not seen BN used for graph neural networks before), but scale-invariance is a problem as described in [b]. Also, Fig. 4 (c) and (d) has some outliers that are not really explained.\n- Table 2 is hard to read and very small.\n- Some ablation that I find missing: ablation regarding layers. Which layer to skip? Obviously, the networks are two-layer networks, but I would find it very interesting whether it is always the last layer to skip (also in deeper networks) or always the first layer to perturb (also in deeper networks).", "summary_of_the_paper": "The authors propose a variant of adversarial weight perturbations / sharpness aware minimization for graph (convolutional) neural networks for node and graph classification. In particular, they make two adjustments: “truncating”, i.e., limiting the weight perturbation to specific layers, and weighting the sharpness aware loss with the regular loss during training.", "summary_of_the_review": "I appreciate this paper in terms of applying AWP to graph neural networks and showing how it needs to be adapted to work well. Methodological contributions are small, however, and improvements vary across datasets and cases. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-YzVlROXSg_", "reviewer": "Reviewer_gQzb", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strengths: I am satisfied with the numerical experiments in section 5, although they largely follows the routes of existing work. \n\nWeaknesses: I will point the weaknesses by sections.\n\nSection 3: i) The theoretical results are very incremental based on existing works e.g., Wu et al., 2020a, which can be easily derived or directly used. ii) the AWP algorithm listed here is the same as Wu et al., 2020a (only add a letter A).\n\nSection 4: i) After I read the paper thoroughly twice, I do not see how you assign $\\theta^{(awp)}$ and $\\theta^{(normal)}$, which is very important. If you have that in your paper, first let me know where I can find it, second move that to section 4 and explain it. It is unacceptable not having it in section 4. ii) Do not have theory or even intuition about T-AWP and W-AWP. In my perspective, how you justify your algorithms is very important, which is much important than the so called \"theoretical\" results in Section 3. You can even save the space in section 3 for you to defend your algorithms in section 4. I believe what I point out here should be your novelty for this paper. At least, please, add some good intuitions for your algorithms (I will add points if you do that.) iii) Please add the WT-AWG result in Figure 3.\n\nSummary: Good: experiments; Weak: i) too incremental and lack of novelty; ii) do not provides theoretical/intuitive explanation of the proposed algorithms.\n\n\n\n\n\n", "summary_of_the_paper": "This work studies how AWP improves the GNN, mainly at the generalization aspect. The authors first derive several theoretical results that can be easily derived from the existing works on CNN, e.g., Wu et al., 2020a and Foret et a;., 2021 in section 3.. In section 4, the authors show that if they directly apply large $\\rho$ as suggested by (3), they will encounter the gradient vanishing phenomenon during the training. Based on this phenomenon, the authors propose two ways to solve this. One is truncated AWP, the other is weighted AWP. Then, the authors conduct simple experiments using Vanilla GCN, GCN+AWP, GCN+TAWP, GCN+WAWP, where Vanilla perform the best whereas GCN+TAWP, GCN+WAWP have smoother decision boundary. And they decide to combine T+W with AWP (to be frank, I do not know why they do not add experiment result of WT-AWP here.) In section 5, the authors conduct a lot of experiments like clean accuracy, robust accuracy, etc, which follow the existing works.\n\nThe contribution as I can see is that the authors are the first ones to conduct extensive experiments using AWP on graph dataset. However, I do not see other contributions listed by the authors, which I will explain later in the main review.", "summary_of_the_review": "This is work i) is quite incremental compared to the existing works, ii) does not explain/justify/describe the algorithms well. I do not think this paper is good enough for ICLR.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers a variant of adversarial weight perturbations / sharpness aware minimization for graph (convolutional) neural networks for node and graph classification. In particular, they make two adjustments: “truncating”, i.e., limiting the weight perturbation to specific layers, and weighting the sharpness aware loss with the regular loss during training. The reviewers found that the theoretical justifications (characterization of vanishing gradient and understanding of non-iid setting which was added during rebuttal) are interesting, but several reviewers also found the solution/empirical results not convincing enough. I recommend the authors to either shift the focus to the theoretical results or to strengthen the empirical results (and their connections with theory) following the comments of the reviewers.
Decision: Reject