# 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 effectively find such minima, Adversarial Weight Perturbation (AWP) minimizes the
loss w.r.t. a bounded worst-case perturbation of the model parameters by (approximately) 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 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 non-i.i.d. graph data. Along the way, we first derive a generalization bound for non-i.i.d. graph classification tasks, then we identify a vanishinggradient issue with all existing formulations of AWP and we propose new
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.

1 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 different local minima which can have wildly different generalization properties despite having nearly
the same performance on training and validation data. Naturally, there is a 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., 2021). The notion of flatness which measure how quickly the loss
changes in a 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, generalization bounds based on the PAC-Bayes framework (McAllester, 1999; Foret et al., 2021) 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.e. the clean accuracy (Foret et al., 2021; Zheng et al., 2021; Kwon et al., 2021), but they also improve generalization
to adversarial examples, i.e. the robust accuracy (Wu et al., 2020a; Stutz et al., 2021). Improving adversarial robustness is 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 inputs while maintaining good clean accuracy (Stutz et al., 2021).

Among the variety of techniques for finding flat minima Adversarial Weight Perturbation (AWP)
(Wu et al., 2020a), and the closely-related (adaptive) sharpness-aware minimization (Foret et al.,
2021; Kwon et al., 2021) and adversarial model perturbation (Zheng et al., 2021), 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 as 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 a fundamental building block (in addition to CNNs and RNNs).


-----

Blindly applying existing weight perturbation techniques to GNNs is unfortunately not effective in
practice due to a vanishing-gradient issue. Intuitively, the adversarially perturbed weights tend to
have a higher norm which in turn leads to a 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 a regularizer in addition to the
standard cross-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:

-  We provide a theoretical analysis of AWP on non-i.i.d. graph data and identify a vanishinggradient 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 simultaneously 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 at a 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 a learning objective L(·) and an image classification model with parameters θ, the generalization gap (Wu et al., 2020a), also named
the sharpness term (Foret et al., 2021), which measures the worst-case flatness of the loss landscape, is defined by [max **_δ_** _ρ L(θ + δ)_ _L(θ)]. This gap is known to control a 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
minθ[(max **_δ_** _ρ L(θ + δ)_ _L(θ)) + L(θ)] = minθ max_ **_δ_** _ρ L(θ + δ). Providing further the-_
_||_ _||≤_ _−_ _||_ _||≤_
oretical justification for the effectiveness of the AWP, Zheng et al. (2021) prove that this objective
favors solutions corresponding to flatter local minima assuming that the loss surface can be approximated as 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 a small batch size. In some cases we can rescale the weights to 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 a variety of graph learning
tasks across many high-impact domains (see survey (Wu et al., 2020b)). Despite their success, it has
been demonstrated that GNNs suffer from evasion attacks at test time (Z¨ugner et al., 2018) and poisoning attacks at training time (Z¨ugner and G¨unnemann, 2019). Meanwhile, a series of methods have
been developed to improve their robustness. For example, GCNJaccard (Wu et al., 2019) drops dissimilar 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 approximation 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., 2020). 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).

3 ADVERSARIAL WEIGHT PERTURBATION ON GRAPH NEURAL NETWORKS

To simplify the exposition we focus on the semi-supervised node classification task. Nonetheless, in
Sec. 5.8 we show that AWP also improves graph-level classification. Let G = (A, X) be a given (attributed) graph where A is the adjacency matrix and X contains the node attributes. Let V be the set


-----

of all nodes. Normally we optimize minθ Ltrain(θ; A, X), where Ltrain = _v_ train _[l][(][f][θ][(][A][,][ X][)][, y][v][)][,]_

_∈V_
_f is a GNN parametrized by weights θ = (θ1, ..., θk), yv is the ground-truth label for node v, and l_
is some loss function (e.g. cross-entropy) applied to each node in the training set[P] train .
_V_ _⊂V_

In AWP we first find the worst-case weight perturbation δ[∗](θ) that maximizes the loss. Then we
minimize the loss with the perturbed weights. The worst-case perturbation for a given θ is defined as

**_δ[∗](θ) := arg_** max (1)
**_δ_** **_δi_** 2 _ρ(θi),i_ [k] _[L][train][(][θ][ +][ δ][;][ A][,][ X][)][,]_
_{_ _| ||_ _||_ _≤_ _∈_ _}_

where ρ(θ) is the strength of perturbation. Then the AWP learning objective is

min max (2)
**_θ_** **_δ_** **_δi_** 2 _ρ(θi),i_ [k] _[L][train][(][θ][ +][ δ][;][ A][,][ X][) = min]θ_ _[L][train][(][θ][ +][ δ][∗][(][θ][);][ A][,][ X][)][.]_
_{_ _| ||_ _||_ _≤_ _∈_ _}_

Since the PAC-Bayes bound proposed by McAllester (1999) only holds for i.i.d. training tasks and
semi-supervised node classification is a non-i.i.d. task, analysis in Wu et al. (2020a) and Foret et al.
(2021) could not be naturally extended to node classification tasks. We derived a new generalization
bound for node classification tasks on GNNs based on the sub-group generalization (Ma et al., 2021).
**Theorem 1. (informal). Let Lall(θ; A, X) be the loss on all nodes, including the unseen test nodes.**
_It is bounded by the adversarially weight perturbed loss on the training nodes as follows:_

_Lall(θ; A, X)_ max 2[/ρ][(][θ][)][2][)] (3)
_≤_ **_δ_** **_δi_** 2 _ρ(θi),i_ [k] _[L][train][(][θ][ +][ δ][;][ A][,][ X][) +][ h][(][||][θ][||][2]_
_{_ _| ||_ _||_ _≤_ _∈_ _}_

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 h(||θ||2[2][/ρ][(][θ][)][2][)][ is monotonously decreasing with][ ρ][(][θ][)][, increasing the perturbation strength][ ρ][ can]
make the bound in Eq. 3 sharper, i.e. the resulting AWP objective should lead to better generalization.

Since finding the optimal perturbation (Eq. 1) is intractable, we approximate it with a one-step projected gradient descent as in previous work (Wu et al., 2020a; Foret et al., 2021; Zheng et al., 2021),

**_δˆ[∗](θ) := ΠB(ρ(θ))(_** **_θLtrain(θ; A, X)),_** (4)
_∇_

where B(ρ(θ)) is an l2 ball with radius ρ(θ) and ΠB(ρ(θ))(·) is a projection operation, which
projects the perturbation back to the surface of B(ρ(θ)) when the perturbation is out of the ball. The
maximum perturbation norm ρ(θ) could either be a constant (Foret et al., 2021; Zheng et al., 2021)
or layer dependent (Wu et al., 2020a). We specify a layer-dependent norm constraint ρ(θ) := ρ **_θ_** 2
_||_ _||_
because the scales of different layers in a neural network vary greatly. With the approximation
**_δˆ[∗](θ), the definition of the final AWP learning objective is given by_**

min (5)
**_θ_** _[L][awp][(][θ][) :=][ L][train][(][θ][ + Π][B][(][ρ][(][θ][))][(][∇][θ][L][train][(][θ][;][ A][,][ X][));][ A][,][ X][)][,]_

If Ltrain(θ; A, X) is smooth enough, ∇θLtrain(θ; A, X) = 0 when θ[∗] is a local extremum. In this
case Lawp(θ) = Ltrain(θ; A, X). A natural question is whether θ[∗] will also be the extremum of
_Lawp(θ)? We show that Lawp(θ) keeps the local extremum of Ltrain(θ; A, X) unchanged._
**Theorem 2. (Invariant of local minimum and maximum) With the AWP learning objective in Eq. 5,**
_and for continuous Ltrain(θ; A, X), ∇θLtrain(θ; A, X), ∆θLtrain(θ; A, X), if θ[∗]_ _is a local mini-_
_mum of Ltrain(θ; A, X) and the Hessian matrix ∆θLtrain(θ; A, X)|θ∗_ _is positive definite, θ[∗]_ _is also_
_a local minimum of Lawp(θ)._

The proof is provided in Appendix A. The exact gradient of this new objective is

_∇θLtrain(θ + δ[ˆ][∗](θ); A, X) = ∇θLtrain(θ; A, X)|θ+ˆδ[∗](θ)_ [+][ ∇][θ][ ˆ]δ[∗](θ)∇θLtrain(θ; A, X)|θ+ˆδ[∗](θ) [(6)]

Since ∇θδ[ˆ][∗](θ) includes second and higher order derivative of θ, which are computationally expensive, they are omitted during training, obtaining the following approximate gradient of the AWP loss

**_θLtrain(θ; A, X)_** **_θ+ˆδ[∗](θ)_** (7)
_∇_ _|_

Foret et al. (2021) show the models trained with the exact gradient (Eq. 6) have almost the same
performance as model trained with the estimated first-order gradient (Eq. 7).


-----

|Col1|1.|
|---|---|
||1 0 0|
|||

|Col1|0 0|
|---|---|
|||

|Col1|0 0|
|---|---|
|||

|Col1|0 0 0|
|---|---|
|||
|||


1.0 1.0

0.8 0.5

0.6

0.0

0.4

0.2 0.5

0.0 1.0

0.0 0.5 1.0


1.0

0.8 0.5

0.6

0.0

0.4

0.2 0.5

0.0

0.0 0.5 1.0


1.0 1.0

0.010

0.8 0.005 0.8

0.005

0.6 0.6

0.000 0.000

0.4 0.4

0.005

0.2 0.005 0.2

0.010

0.0 0.0

0.0 0.5 1.0 0.0 0.5 1.0


(a) Vanilla GCN


(b) AWP ρ = 0.5


(c) AWP ρ = 1.5


(d) AWP ρ = 2.5


Figure 1: Compare AWP models on a linearly separable dataset with different perturbation strengths
_ρ. The accuracy of models (a) to (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 ρ the model is 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 B).

4.1 THE VANISHING-GRADIENT ISSUE OF AWP

Consider a GCN ˆy = σ( A[ˆ](...( AXW[ˆ] 1)...)Wn) with a softmax activation at the output layer, where
**_Aˆ is the graph Laplacian given by_** **_A[ˆ] := D[−][1][/][2](A + IN_** )D[−][1][/][2], Dii = _j[(][A][ +][ I][N]_ [)][ij][. The]

perturbed model is ˆy = σ( A[ˆ](...( AX[ˆ] (W1+δ1)))...(Wn+δn)). Since the norm of each perturbation
**_δi could be as large as ρ||Wi||2, in the worst case the norm of each layer is[P] (ρ + 1)||Wi||2, and_**
thus the model will have exploding logit values when ρ 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,
we 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 a common setting for
GCNs, on a linearly separable dataset. The dataset contains 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 testing. In Fig. 1 we show the trained classifiers for different ρ
values. Models with AMP crash quickly when ρ increased
from 0.5 to 2.5. When ρ = 0.5, the classification accuracy
is 0.97, which is nearly the same as the vanilla model, but

Figure 2: Learning curves for GCN and

when ρ = 2.5, the classification accuracy is 0.51, which

GCN+AWP with different ρ.

is the same as a random guess. Besides, when ρ = 1.5
and 2.5, the loss of AWP method is almost constant during training (Fig. 2) and the prediction score (Fig. 1(c) and Fig. 1(d)) is around 0. This indicates that
the weights are barely updated during training. So with the AWP objective, we cannot select a large
_ρ. Yet, as we discussed in Sec. 3, we prefer larger values of ρ since they lead to a tighter bound (Eq. 3)_
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 to 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 a second


-----

1.0 1.0

0.8 0.5

0.6

0.0

0.4

0.2 0.5

0.0 1.0

0.0 0.5 1.0

(a) Vanilla model




1.0

0.8 0.5

0.6

0.0

0.4

0.2 0.5

0.0

0.0 0.5 1.0

(d) W-AWP, λ=0.5


1.0

0.8 0.5

0.6

0.0

0.4

0.2 0.5

0.0

0.0 0.5 1.0

(e) WT-AWP, λ=0.5


1.0 1.0

0.8 0.005 0.8 0.5

0.6 0.6

0.000 0.0

0.4 0.4

0.2 0.005 0.2 0.5

0.0 0.0

0.0 0.5 1.0 0.0 0.5 1.0


(b) AWP


(c) T-AWP


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 θ = [θ[(][awp][)]; θ[(][n][)]] with and without AWP; number**
of epochs N ; loss function Ltrain; perturbation strength ρ, AWP weight λ; learning rate α.
Initialize weight θ0;
**for t ∈** _1:N do_

Compute the loss for training nodes: Ltrain(θt−1; A, X)
Compute the approximating weight perturbation for θt[(]−[awp]1 [)]: **_δ[ˆ][∗](θt[(]−[awp]1_** [)]) via Eq. 4
Compute the approximating gradient for θ:
_g = λ∇θLtrain(θ; A, X)|θt−1+[ˆδ[∗](θt[(]−[awp]1_ [)]),0] [+ (1][ −] _[λ][)][∇][θ][L][train][(][θ][;][ A][,][ X][)][|][θ][t][−][1]_
Update the weight via θt = θt 1 _αg_
_−_ _−_

**end**
**return θN**

source of valid gradients which we do by adding the the vanilla loss Ltrain(θ; A, X) to 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 θ_ =

[θ[(][awp][)], θ[(][normal][)]], and we only perform AWP on θ[(][awp][)]. The Truncated AWP objective is

min **_δ[(][awp][)][∗](θ[(][awp][)]), 0]; A, X),_** (8)
**_θ_** _[L][train][(][θ][ + [ˆ]_

_where_ **_δ[ˆ][(][awp][)][∗](θ[(][awp][)]) := ΠB(ρ(θ(awp)))(_** **_θ(awp)_** _Ltrain(θ[(][awp][)]; A, X))._
_∇_

Recall in Sec. 2, the AWP objective is the unweighted combination of the regular loss function L(θ)
and the sharpness term maxδ≤ρ[L(θ + δ) − _L(θ)]. 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

[λ maxδ _ρ[L(θ + δ)_ _L(θ)] + L(θ)] = [λ maxδ_ _ρ L(θ + δ) + (1_ _λ)L(θ)]._
_≤_ _−_ _≤_ _−_

**Definition 2. (Weighted AWP) Given a weight λ ∈** [0, 1] the Weighted AWP objective is

min **_δ[∗](θ); A, X) + (1_** _λ)Ltrain(θ; A, X)]_ (9)
**_θ_** [[][λL][train][(][θ][ + ˆ] _−_

We compare these two improvements with AWP and natural training on a linearly separable dataset
using the same setup as in Sec. 4.1. Fig. 3 illustrates the trained models with ρ = 2. In Fig. 3(b)
we can see that the model with AWP objective suffers from vanishing gradients and it fails to learn
anything useful. The models with Truncated AWP[1] (θ[(][awp][)] = first layer and θ[(][normal][)] = last layer)
(Fig. 3(c)) and Weighted AWP (Fig. 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 to obtain a more powerful approach against the vanishing-gradient issue, we combine Truncated AWP and Weighted AWP, into a Weighted Truncated Adversarial Weight Perturbation (WTAWP). The details of WT-AWP are shown in Algorithm 1 (description in Sec. B.1). WT-AWP has
two important parameters λ and ρ. We will study how they influence model performance in Sec. 5.7.

1In Fig. 3(c) we perturb only the first-layer. Perturbing only the second layer instead performs similarly.


-----

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 et al., 2020) for evaluation clean and robust node classification 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 in Sec. 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ˇckovi´c et al., 2018), and PPNP (Klicpera et al., 2018), and four graph defense methods: RGCN
(Zhu et al., 2019)[2], GCNJaccard (Wu et al., 2019), GCNSVD (Entezari et al., 2020), and SimpleGCN (Jin et al., 2021). For detailed baseline descriptions see Sec. D.1. To generate the adversarial perturbations, we apply three methods including: DICE (Waniek et al., 2018), PGD (Xu et al.,
2019), and Metattack (Z¨ugner and G¨unnemann, 2019). For a 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 (Bojchevski 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 rd edges or add up to ra edges to graph (similarly for the node features). See Sec. 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.e. we assign θ[(][awp][)] = first
layer and θ[(][normal][)] = last layer. For generating the weight perturbation we use a 1-step PGD as
discussed in Sec. 3. In the ablation study Sec. 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 B(ρ(θ)).

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-hidden-output)
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, α = 0.1 in PPNP. We also find that the hyperparameters (λ, ρ) of
WT-AWP are more related to the dataset than the backbone models. We use (λ = 0.7, ρ = 1) for
all three baseline models on Cora, (λ = 0.7, ρ = 2.5) on Citeseer, and (λ = 0.3, ρ = 1) for GCN,
(λ = 0.3, ρ = 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, p < 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 attributes X, we compute the average norm of the gradient of Ltrain(θ; A, X) w.r.t. A and X. We
compare a vanilla GCN model with GCN+WT-AWP (λ = 0.5, ρ = 1) model on Cora and Citeseer. 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 gradient norm, i.e. are smoother. This provides evidence that WT-AWP can help us find flatter minima.

2Note, we cannot apply WT-AWP to RGCN as the weights are modeled by distributions.


-----

Table 1: Clean accuracy comparison. We report the average and the standard deviation across 200
experiments per model (20 random splits × 10 random initializations). WT-AWP consistently outperform the standard models on all benchmarks. The improvements are statistically significant according to a two-sided t-test at a significance level of p < 0.001.

Approachs Cora Citeseer Polblogs

GCN 84.14 ± 0.61 73.44 ± 1.35 95.04 ± 0.66
GCN+WT-AWP 85.16 ± 0.44 74.48 ± 1.04 95.26 ± 0.51

GAT 84.13 ± 0.79 73.71 ± 1.23 94.93 ± 0.51
GAT+WT-AWP 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**

(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 a GCN and a GCN+WT-AWP model trained with the same data split and initialization.

5.3 VISUALIZATION OF LOSS LANDSCAPE

We train GCN, GCN+AWP (ρ = 0.1) and GCN+WT-AWP
(λ = 0.5, ρ = 0.5) models with the same initialization, and
we compare their loss landscapes. The accuracy is 83.55%
for GCN, 84.21% for GCN+AWP, and 85.51% for GCN+WTAWP. Similar to Stutz et al. (2021), Fig. 5 shows the loss landscape in a randomly chosen direction u in weight space, i.e. we
plot Ltrain(θ + α · u; A, X) for different steps α. We generate
10 random directions u and show the average loss. The loss
landscape of GCN+AWP is slightly smoother than the vanilla

Figure 5: Loss landscape.

GCN, because of the small perturbation strength ρ = 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.

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¨ugner and G¨unnemann, 2019), with
a 5% adversarial budget. The baseline models are vanilla GCN, and three GCN-based graph-defense
models: GCNJaccard, GCNSVD, and SimpleGCN. For all attack and defense methods, we apply the
default hyperparameter settings in Li et al. (2020), 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 (λ, ρ) we select for all WT-AWP models.

As we can see in Table 2, none of the defense methods have dominant performance across benchmarks. 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.


-----

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 a t-test.

Natural Acc Acc with 5% PGDattack Acc with 5% Metattack

Models Cora Citeseer Polblogs Cora Citeseer Polblogs* Cora Citeseer Polblogs

GCN 83.73 ± 0.71 73.03 ± 1.19 95.06 ± 0.68 81.26 ± 1.27 72.04 ± 1.60 85.18 ± 2.63 78.61 ± 1.66 69.20 ± 1.93 79.74 ± 1.05
+WT-AWP **84.66 ± 0.53** 74.01 ± 1.11 **95.20 ± 0.61** 82.66 ± 1.07 73.73 ± 1.23 **85.73 ± 4.17** 79.05 ± 1.73 70.50 ± 1.65 80.72 ± 1.25

GCNJaccard 82.42 ± 0.73 73.09 ± 1.20 N/A 80.65 ± 1.14 72.05 ± 1.76 N/A 78.96 ± 1.54 69.62 ± 1.87 N/A
+WT-AWP 83.55 ± 0.60 74.10 ± 1.04 N/A 82.12 ± 0.91 73.85 ± 1.38 N/A **80.23 ± 1.38** 71.22 ± 1.44 N/A

SimPGCN 82.99 ± 0.68 74.05 ± 1.28 94.67 ± 0.95 80.71 ± 1.33 73.61 ± 1.39 82.42 ± 3.14 78.60 ± 1.81 72.52 ± 1.72 76.66 ± 1.80
+WT-AWP 83.37 ± 0.74 **74.26 ± 1.09** 94.85 ± 0.91 **83.49 ± 0.78** **74.43 ± 1.14** 82.68 ± 4.82 79.76 ± 1.76 **72.95 ± 1.43** 77.68 ± 2.41

GCNSVD 77.63 ± 0.63 68.57 ± 1.54 94.08 ± 0.59 76.83 ± 1.42 68.08 ± 1.98 82.84 ± 3.05 76.28 ± 1.15 67.34 ± 1.93 91.76 ± 1.19
+WT-AWP 79.05 ± 0.58 71.12 ± 1.42 94.13 ± 0.59 78.50 ± 0.89 71.43 ± 1.46 82.97 ± 3.57 77.61 ± 1.08 70.65 ± 1.28 **92.28 ± 0.98**

RGCN 83.29 ± 0.63 71.69 ± 1.35 95.15 ± 0.46 78.47 ± 1.10 68.81 ± 2.32 85.62 ± 1.51 77.70 ± 1.69 69.05 ± 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 × 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
+WT-AWP **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 we perform experiments on three benchmarks: Cora, Citeseer, and Polblogs. For the PGD attack the hyperparameters (λ, ρ) are (0.5, 0.5) for all datasets. For the DICE
attack we use (0.5, 0.5) for Cora, (0.7, 2) for Citeseer, and (0.3, 1) for Polblogs. Table 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, ρ = 1 as
the hyperparameters for the WT-AWP models. We plot the certified accuracy S(ra, rd) for different
addition ra and deletion rd radii. In Fig. 6, we see that compared to vanilla GCN training, our
WT-AWP loss significantly increases the certified accuracy w.r.t. feature perturbations for all radii,
while maintaining comparable performance when certifying perturbations of the graph structure.
For additional results see Sec. C.3.

(a) Node feature perturbations (b) Graph structure perturbations

Figure 6: Robustness guarantees on Cora. WT-AWP improves the certificate for node features.


-----

Table 4: Hyperparameter sensitivity study for λ and ρ on the Cora dataset for a GCN base model.

|WT-AWP|ρ = 0.05 ρ = 0.1 ρ = 0.5 ρ = 1 ρ = 2.5 ρ = 5|
|---|---|
|λ = 0.1 λ = 0.3 λ = 0.5 λ = 0.7 λ = 1.0|84.15 ± 0.60 84.15 ± 0.61 84.51 ± 0.48 84.58 ± 0.52 84.50 ± 0.51 84.54 ± 0.49 84.10 ± 0.62 84.13 ± 0.58 84.76 ± 0.51 84.91 ± 0.46 84.77 ± 0.46 84.64 ± 0.47 84.11 ± 0.64 84.09 ± 0.61 84.93 ± 0.49 85.06 ± 0.49 84.94 ± 0.45 84.67 ± 0.49 84.13 ± 0.59 84.15 ± 0.64 85.00 ± 0.46 85.16 ± 0.44 84.99 ± 0.49 84.66 ± 0.49 84.12 ± 0.69 84.23 ± 0.64 82.45 ± 1.98 60.29 ± 1.94 29.51 ± 0.91 29.19 ± 0.13|
|AWP W-AWP|84.16 ± 0.68 84.23 ± 0.68 41.19 ± 1.23 29.18 ± 0.07 29.18 ± 0.02 29.18 ± 0.02 84.12 ± 0.66 84.20 ± 0.66 84.63 ± 0.51 84.32 ± 0.65 83.98 ± 0.93 83.62 ± 1.27|



Table 5: Ablation study with λ and ρ on WT-AWP, where the weight perturbation is calculated with
5-step PGD. The backbone model is GCN and the benchmark is Cora.

|WT-AWP (5 step)|ρ = 0.05 ρ = 0.1 ρ = 0.5 ρ = 1 ρ = 2.5 ρ = 5|
|---|---|
|λ = 0.1 λ = 0.3 λ = 0.5 λ = 0.7 λ = 1.0|84.19 ± 0.60 84.17 ± 0.59 84.45 ± 0.51 84.50 ± 0.50 84.39 ± 0.52 84.41 ± 0.54 84.12 ± 0.58 84.15 ± 0.63 84.65 ± 0.54 84.81 ± 0.47 84.70 ± 0.50 84.55 ± 0.55 84.10 ± 0.59 84.11 ± 0.62 84.77 ± 0.53 84.90 ± 0.50 84.82 ± 0.47 84.64 ± 0.52 84.12 ± 0.61 84.11 ± 0.63 84.86 ± 0.49 84.99 ± 0.48 84.89 ± 0.51 84.64 ± 0.52 84.11 ± 0.62 84.18 ± 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 ρ. Table 4 lists
the results. The accuracy of GCN+WT-AWP first increases with λ and ρ and then slightly decreases.
Truncated AWP is a special case for λ = 1 (since the (1−λ) term disappears in Eq. 9) and it does not
perform well, especially for larger ρ. Similarly, WT-AWP outperforms the vanilla AWP that suffers
from the vanishing-gradient 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 ρ, and then
decreases. The optimal hyperparameters (λ, ρ) are ρ = 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: Protein, IMDB-Binary and IMDB-Multi. Detailed description is in Sec. D.9. Table 6 shows the experimental 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-AWP is also more stable. Note, we do not claim that
our models are state of the art, but rather that WT-AWP provides consistent improvements.

Table 6: Performance of WT-AWP on graph classification tasks, the backbone is GCN.

Proteins IMDB-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 it 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 on a wide range of graph learning
tasks including node classification, graph defense, and graph classification. Further exploring the
connections between flat minima and generalization in GNNs is a promising research direction.


-----

REPRODUCIBILITY STATEMENT

All datasets, baseline models, and general training settings are listed at the beginning of Sec. 5. For
specific tasks we include the detailed settings in the corresponding sections. For example, the detailed 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 a new regularization method that can improve the robustness of graph neural
networks again adversarial attacks. Making GNNs more robust can have positive or 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 a 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. Bojchevski, J. Klicpera, and S. G¨unnemann. Efficient robustness certificates for discrete data:
Sparsity-aware randomized smoothing for graphs, images and more. In International Conference
_on Machine Learning, pages 1003–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. In 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. Mobahi, and B. Neyshabur. Sharpness-aware minimization for efficiently
improving generalization. ICLR, 2021.

Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio. Fantastic generalization measures
and where to find them. arXiv preprint arXiv:1912.02178, 2019.

W. Jin, T. Derr, Y. Wang, Y. Ma, Z. 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.04836, 2016.

T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. ICLR,
2017.

J. Klicpera, A. Bojchevski, and S. G¨unnemann. 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 scaleinvariant learning of deep neural networks. arXiv preprint arXiv:2102.11600, 2021.

Y. Li, W. Jin, H. Xu, and J. Tang. Deeprobust: A pytorch library for adversarial attacks and defenses.
_arXiv preprint arXiv:2005.06149, 2020._

J. Ma, J. Deng, and Q. Mei. Subgroup generalization and fairness of graph neural networks. arXiv
_preprint arXiv:2106.15535, 2021._


-----

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.

P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad. Collective classification
in network data. AI magazine, 29(3):93–93, 2008.

O. Shchur, M. Mumme, A. Bojchevski, and S. G¨unnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868, 2018.

D. Stutz, M. Hein, and B. Schiele. Relating adversarially robust generalization to flat minima. arXiv
_preprint arXiv:2104.04448, 2021._

L. Sun, Y. Dou, C. Yang, J. Wang, P. S. Yu, L. He, and B. Li. Adversarial attack and defense on
graph data: A survey. arXiv preprint arXiv:1812.10528, 2018.

P. Veliˇckovi´c, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. ICLR, 2018.

M. Waniek, T. P. Michalak, M. J. Wooldridge, and T. Rahwan. Hiding individuals and communities
in a 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 on graph
data: Deep insights into attack and defense. arXiv preprint arXiv:1903.01610, 2019.

Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip. A comprehensive survey on graph neural
networks. IEEE transactions on 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 arXiv:1906.04214, 2019.

P. Yanardag and S. Vishwanathan. Deep graph kernels. In Proceedings of the 21th 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 on Computer Vision and Pattern Recognition, pages
8156–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¨ugner and S. G¨unnemann. Adversarial attacks on graph neural networks via meta learning.
_ICLR, 2019._

D. Z¨ugner, A. Akbarnejad, and S. G¨unnemann. Adversarial attacks on neural networks for graph
data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discov_ery & Data Mining, pages 2847–2856, 2018._


-----

## Supplementary Material


A PROOFS

_Proof. (Theorem 2) We only show the proof with local minimums, the proof with local maximum is_
analogous. For ease of calculation we denote Ltrain(θ; A, X) by L(θ). We need to show a) ∇θL(θ +
_∇θL(θ))|θ∗_ = 0, and b) ∆θL(θ + ∇θL(θ))|θ∗ is positive definite.

a) Since θ[∗] is a local minimum of L, we have **_θL(θ)_** **_θ∗_** = 0, thus
_∇_ _|_

_∇θL(θ + ∇θL(θ))|θ∗_ = (I + ∆θL(θ[∗]))∇θL(θ)|θ∗+∇θ _L(θ)|θ∗_ (10)
= (I + ∆θL(θ[∗])) **_θL(θ)_** **_θ∗_** = 0
_∇_ _|_

b)

_∇θ(∇θL(θ + ∇θL(θ)))|θ∗_ = ∇θ[(I + ∆θL(θ))∇θL(θ + ∇θL(θ))]|θ∗
= ∇θ(I + ∆θL(θ))|θ∗ _∇θL(θ)|θ∗+∇θ_ _L(θ)|θ∗_ (11)
+ (I + ∆θL(θ))|θ∗ ∆θL(θ)|θ∗+∇θ _L(θ)|θ∗_ (I + ∆θL(θ))[T] _|θ∗_

= (I + ∆θL(θ)) **_θ[∗]_** ∆θL(θ) **_θ[∗]_** (I + ∆θL(θ))[T] **_θ[∗]_**
_|_ _|_ _|_

Because (I + ∆θL(θ)) **_θ∗_** and ∆θL(θ) **_θ∗_** are positive definite matrices, and **_θ(_** **_θL(θ +_**
_|_ _|_ _∇_ _∇_
_∇θL(θ)))|θ∗_ = (I + ∆θL(θ))|θ∗ ∆θL(θ)|θ∗ (I + ∆θL(θ))[T] _|θ∗_ is symmetric, ∇θ(∇θL(θ +
_∇θL(θ)))|θ∗_ is positive definite. Thus θ[∗] is also the local minimum of L(θ + ∇θL(θ)).

B VANISHING-GRADIENT ISSUE OF AWP ON MLP

In this section we show that the vanishing-gradient issue also happens in multi-layer perceptrons.
Consider an MLP ˆy = σ(Wn(...(W1X))) with a softmax activation at the output layer. The perturbed model is ˆy = σ(((Wn+δn)(...((W1+δ1)X))). Since the norm of each perturbation δi could
be as large as ρ **_Wi_** 2, in the worst case the norm of each layer is (ρ+1) **_Wi_** 2, and thus the model
_||_ _||_ _||_ _||_
will have exploding logit values when ρ 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 will also be large. The gradient will be close to 0 and the weights will not be updated.

To verify our conclusion we train a 3-layer linear network with W1 _∈_ R[2][×][100], W2 _∈_
In Fig. 7 we show the trained classifiers with differentR[100][×][100], W3 ∈ R[100][×][2] on a linearly separable dataset, the number of training epochs is 2000. ρ. We find that models with AWP are crushed
quickly when ρ increased from 0.2 to 0.25. When ρ = 0.25, the value of loss function remains unchanged during training and the prediction score is around 0, which indicates the weights are almost
not updated during training. So with the AWP objective, we cannot select a large ρ.

(a) Natural model (b) AWP ρ = 0.1 (c) AWP ρ = 0.2 (d) AWP ρ = 0.23 (e) AWP ρ = 0.25

Figure 7: Comparing AWP models on a linearly separable dataset with different ρ values.

We repeat the experiment using the same 3-layer linear network on a 2d moons dataset and perform
the weight perturbation only on the first two layers. Fig. 8 Illustrates the trained models with ρ = 0.4.


-----

(a) Natural model (b) AWP (c) T-AWP (d) W-AWP, λ = 0.9

Figure 8: Model comparison on the two moons dataset, ρ = 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 or the first layer and train the model correspondingly, the results are 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.1 DESCRIPTION OF ALGORITHM 1

In the WT-AWP algorithm (Algorithm 1) we apply a numerical optimizer such as Adam to the
WT-AWP objective

_LW T_ _AW P (θ) = [λLtrain(θ + [δ[ˆ][(][awp][)][∗](θ[(][awp][)]), 0]; A, X) + (1_ _λ)Ltrain(θ; A, X)]_
_−_ _−_

Since in our empirical experiments the GNNs always have a 2-layer structure, we assign θ[awp] as the
first layer and θ[normal] as the last layer. Then the perturbation _δ[ˆ][(][awp][)][∗]_ (first layer) is computed via
Eq. (4). Next the gradient g of LW T _AW P is calculated with Eq. (6)._
_−_

_g = λ∇θLtrain(θ; A, X)|θt−1+[ˆδ[∗](θt[(]−[awp]1_ [)]),0] [+ (1][ −] _[λ][)][∇][θ][L][train][(][θ][;][ A, X][)][|][θ][t][−][1]_

Finally we update the weight via θt = θt 1 _αg._
_−_ _−_

C ADDITIONAL EXPERIMENTS

C.1 LEARNING CURVES AND GENERALIZATION GAP DURING TRAINING

In this part, we train GCN, GCN+AWP (ρ = 0.1) and GCN+WT-AWP (λ = 0.5, ρ = 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+WT-AWP. Fig. 9(a)
illustrates the learning curve of vanilla loss Ltrain(θ; A, X) during training. The loss of all three
models converges well. The final value of GCN+WT-AWP is larger than the rest two models. We
believe it is because GCN+WT-AWP finds a different (flatter) local minimum. Fig. 9(b) shows the
generalization gap during training. Because we use a large perturbation bound ρ in GCN+WT-AWP,
its generalization gap fluctuates more and decrease slower compared to the gap of GCN+AWP. The
fluctuation is due to the exploding logit problem in AWP with a large ρ value. When it happens, the
regular loss included in WT-AWP can minimize (but not completely eliminate) its influence. Despite
the fluctuation, the generalization gap of GCN+WT-AWP decreases with time as well.

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 as Sec. 5.4. The WT-AWP hyperparameters (λ, ρ) are shown in Table 8. Table 7
illustrates the experimental results. The models that achieve best performance on a given dataset are
all based on WT-AWP. Besides, WT-AWP also consistently boost the performance of the baselines.


-----

(a) Learning curves (b) Generalization gap

Figure 9: Learning Curves and Generalization Gap During Training.

Table 7: Robust accuracy with 5% poisoning DICE attacks. We report the average and the standard
deviation across 200 experiments per model (20 random splits × 10 random initializations).

Natural Acc. Acc. with 5% DICE attack

Approachs Cora Citeseer Polblogs Cora Citeseer Polblogs

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

GCNJaccard 82.42 ± 0.73 73.09 ± 1.20 N/A 81.55 ± 0.86 72.22 ± 1.22 N/A
+WT-AWP 83.55 ± 0.60 74.10 ± 1.04 N/A 82.86 ± 0.73 **73.95 ± 1.04** N/A

SimPGCN 82.99 ± 0.68 74.05 ± 1.28 94.67 ± 0.95 82.11 ± 0.70 73.53 ± 1.23 89.57 ± 1.06
+WT-AWP 83.37 ± 0.74 **74.26 ± 1.09** 94.85 ± 0.91 83.30 ± 0.73 73.89 ± 1.08 90.13 ± 1.03

GCNSVD 77.63 ± 0.63 68.57 ± 1.54 94.08 ± 0.59 76.25 ± 0.91 67.27 ± 1.67 90.80 ± 0.88
+WT-AWP 79.05 ± 0.58 71.12 ± 1.42 94.13 ± 0.59 77.51 ± 0.77 70.30 ± 1.22 **91.11 ± 0.76**

RGCN 83.29 ± 0.63 71.69 ± 1.35 95.15 ± 0.46 82.02 ± 0.73 70.18 ± 1.38 90.03 ± 0.67


-----

(a) Node feature perturbations (b) Graph structure perturbations

Figure 10: Certified adversarial robustness on the Citeseer dataset.

Table 8: Hyperparameters of WT-AWP for poisoning DICE attacks


(λ, ρ) Cora Citeseer Polblogs

GCN
GCNJaccard (0.5, 0.5) (0.7, 2) (0.3, 1)
GCNSVD

SimPGCN (0.1, 0.5) (0.5, 0.1) (0.5, 1)

C.3 CERTIFIED ROBUSTNESS ON CITESEER DATASET

We measure the certified robustness of GCN and GCN+WT-AWP with randomized smoothing (Bojchevski et al., 2020) on the Citeseer dataset. We use λ = 0.5, ρ = 1 as the hyperparameters for
WT-AWP models. We plot the certified accuracy S(ra, rd) w.r.t. ra and rd. As seen in Fig. 10,
comparing with the vanilla GCN, WT-AWP significantly increases the certified accuracy for perturbations to the node features for all radii, while having comparable performance for certification of
the graph structure.

D EXPERIMENTAL DETAILS

D.1 DESCRIPTION OF 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 as 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): is one of the most representative graph convolution neural
networks. Currently it can still achieve SOTA on different graph learning tasks.

-  GAT (Veliˇckovi´c et al., 2018): utilizes multi-head attention mechanism to learn different
weights for each node and its neighbor node without requiring the spectral decomposition.

-  PPNP (Klicpera et al., 2018): improves the GCN propagation scheme based on the personalized
Pagerank. This approach generates predictions from each node’s own features and propagates
these predictions using an adaptation of personalized PageRank.

-  RGCN (Zhu et al., 2019): applies the Gaussian distribution to model the node representations.
This structure is expected to absorb effects of adversarial attacks. It also penalizes nodes with
large variance with an attention mechanism. Notice, the WT-AWP cannot be applied to RGCN,
as the weights of RGCN are modeled by distributions. We can regard RGCN as another model
inspired by PAC-Bayes theorem, as it models the objective Eδ (0,σI)[Ltrain(θ + δ; A, X)],
_∼N_
which also bounded Lall(θ; A, X) according to PAC-Bayes theorem.


-----

-  GCNJaccard (Wu et al., 2019): is a graph defense method based on GCN. It pre-processes
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
are unavailable.

-  GCNSVD (Entezari et al., 2020): is a graph defense method based on GCN, which focuses
on defending nettack Z¨ugner et al. (2018). Since nettack is a high-rank attack, GCN-SVD preprocesses the perturbed graph with its low-rank approximation. It is straightforward to 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 to 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 OF GRAPH ATTACK METHODS

Generally speaking, there are two types of the adversarial attacks on node classification tasks: testtime attack (evasion) and train-time attack (poisoning). In both types of attacks we first generate a
perturbed adjacency matrix based on a victim model, and then in evasion attacks we test it directly
on the victim model, and in poisoning attacks we train a new model with the perturbed adjacency
matrix. For generating the adversarial perturbations, we apply three methods:

-  DICE (Waniek et al., 2018): is a baseline attack method (delete internally, connect externally).
In 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 et al., 2019): calculates the gradient of the adjacency matrix, and the gradient serves
as a probabilistic vector, then a random sampling is applied for generating a near-optimal binary
perturbation based on this vector.

-  Metattack (Z¨ugner and G¨unnemann, 2019): was proposed to generate poisoning attacks based
on meta-learning. It has an approximate version A-Metattack. In our experiments, we apply the
original Metattack.

D.3 DATASETS STATISTICS

Cora and Citeseer (Sen et al., 2008) are citation datasets commonly used for evaluating GNNs.
Polblogs (Adamic and Glance, 2005) is another common benchmark dataset where each node is a
political blog. In Table 9 we provide the statistics for each graph. We preprocess the graph and only
use the largest connected component.

Table 9: Dataset Statistics

|Datasets|Cora Citeseer Polblogs|
|---|---|
|#Nodes #Edges #Features #Classes|2708 3327 1222 5429 4732 16714 1433 3703 N/A 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 no early stopping and the
optimal model is selected with its performance on the validation set. The test set is never touched
during training.


-----

**Train/val/test split. The evaluation procedures of GNNs on 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 on node
classification tasks, we apply the split setting in Z¨ugner and G¨unnemann (2019), 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. 5.2 we generate noise zA, zX from Gaussian distribution N (A, σ[2]I) and
_N_ (X, σ[2]I), then calculate the l2 norm of the loss gradient ||∇ALtrain(θ; A, X)|A=zA _||2 and_
**_X_** _Ltrain(θ; A, X)_ **_A=zA_** 2. In our experiments we choose σ = 0.0005, because we expect the
_||∇_ _|_ _||_
perturbed input to be close to the clean input.

D.6 SETTINGS OF VISUALIZATION OF LOSS LANDSCAPE

For the results in Sec. 5.3, we generate a random direction u from a Gaussian distribution and
perform l2 normalization, it is equal to randomly selecting a direction on the l2 unit ball. As seen in
Fig. 9(a), there is a large gap between the final loss value of WT-AWP and vanilla GCN, we have to
parallel move the loss landscape of WT-AWP and GCN to the same level for making comparison.
The experiments are performed on Cora, similar results also hold for other datasets.

D.7 HYPERPARAMETERS (λ, ρ) FOR POISONING ATTACKS

Table 10: Hyperparameters of WT-AWP for poisoning PGD attack and Metattack of Sec. 5.4

(λ, ρ) 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-perturbed samples. We denote with pa the probability of flipping an entry from 0 to 1,
i.e. adding an edge or a feature, and with pd the probability of flipping an entry from 1 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, pd = 0.6, and for perturbing the adjacency matrix we use
_pa = 0.001, pd = 0.4. We consider the prediction of the smoothed GNN for a given node correct if_
and only if it is correct and certifiably robust. This means the prediction of the node does not change
for any perturbation within the radius (i.e. for any rd deletions or ra additions).

D.9 GRAPH CLASSIFICATION

Table 11: Dataset Statistics.

|Datasets|Proteins IMDB-B IMDB-M|
|---|---|
|#Nodes (max) #Nodes (avg) #Graphs #Classes|620 136 89 39.06 19.77 13.00 1113 1000 1500 2 2 3|


-----

**Datasets. We use three popular graph classification datasets, including one bioinformatics dataset**
Proteins, and two social network datasets IMDB-Binary and IMDB-Multi (Yanardag and Vishwanathan, 2015) for evaluation. The details are shown in Table 11.

**Settings. We use 80% samples for training, 10% samples for validating and the rest 10% for testing.**
The baseline model is a two-layer GCN with 16 hidden dimension and a global mean pooling layer
after the second graph convolution layer. A linear read-out layer is attached to the output of the GCN
to generate predictions. We apply the same training settings for GCN and GCN+WT-AWP. We train
both models for 200 epoches with the Adam optimizer, learning rate 0.01 and weight decay 0.0005.
The best model is selected with only the validation accuracy. For each of GCN and GCN+WTAWP we take 10 random initialization and report the average accuracy and standard deviation. The
hyperparameters (λ, ρ) of WT-AWP is (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 we train a vanilla GCN, GCN+AWP with ρ = 0.1, GCN+WT-AWP with λ =
0.5, ρ = 1 on Cora and plot the relative gradient norm ||∇θ||2/||θ||2 during training. Both AWP
and WT-AWP have small relative gradient norm compared to GCN when epoch is larger than 100.

0.010

0.008

0.006

gradient norm

0.004

0.002

0.000

|Col1|GCN|
|---|---|
||AWP|
||WT-AWP|
|||
|||
|||
|||
|||


25 50 75 100 125 150 175 200

Epochs


Figure 11: Norm of Gradient during training.

D.11 ABLATION STUDY OF THE PERTURBED LAYER


Since in all experiment above we only perturb the first layer of GNN with WT-AWP, we provide
experimental results corresponds to perturb only the second layer with WT-AWP. The backbone is
GCN and the benchmark is 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 ρ on WT-AWP, where we only use AWP on the last layer. The
backbone model is GCN and the benchmark is Cora.


|WT-AWP (last layer)|ρ = 0.05 ρ = 0.1 ρ = 0.5 ρ = 1 ρ = 2.5 ρ = 5|
|---|---|
|λ = 0.1 λ = 0.3 λ = 0.5 λ = 0.7 λ = 1.0|84.09 ± 0.62 84.13 ± 0.60 84.18 ± 0.60 83.87 ± 0.85 81.40 ± 1.92 65.34 ± 6.41 84.14 ± 0.58 84.12 ± 0.64 84.14 ± 0.69 82.30 ± 1.47 33.50 ± 1.48 29.18 ± 0.00 84.13 ± 0.60 84.10 ± 0.63 84.08 ± 0.77 78.00 ± 3.16 29.18 ± 0.00 29.18 ± 0.00 84.12 ± 0.62 84.14 ± 0.64 83.74 ± 0.84 67.37 ± 5.01 29.18 ± 0.00 29.18 ± 0.00 84.20 ± 0.62 84.19 ± 0.65 82.80 ± 1.04 29.18 ± 0.02 29.18 ± 0.00 29.18 ± 0.00|


-----

GENERALIZATION BOUND ON GNN NODE CLASSIFICATION


**Theorem 3. (generalization bound) Assuming Lall(θ; A, X)** Ez (0,Σ)[Lall(θ + z; A, X)], for
_≤_ _∼N_
_any set of training nodes Vtrain from Vall, ∀m >_ _√d, with probability at least 1 −_ _δ, we have_

_Lall(θ; A, X)_ max _d )[d/][2]_
_≤_ _δ_ 2 _ρ[[][L][train][(][θ][ +][ δ][;][ A, X][)] + (]_ _[m]d [2]_ _[e][1][−]_ _[m][2]_
_||_ _||_ _≤_

(12)

+ _√1N0_ 12 1 + d log(1 + _[m][2]dρ[||][θ][2][||]2[2]_ ) + ln [3]δ [+ 1]4 [+ Θ(][K][ ·][ ϵ][all][)] _._

   


_where d is the number of parameters in the GNN, K is the number of groundtruth labels, ϵall is a_
_fixed constant w.r.t. Vall, N0 is the volume of Vtrain._

We use the assumption in Foret et al. (2021), Lall(θ; A, X) Ez (0,Σ)[Lall(θ + z; A, X)], which
_≤_ _∼N_
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_
et al., 2021) and the intuition of theorem 1 in Foret et al. (2021).

**Lemma 1. (PAC-Bayes bound node classification tasks (Ma et al., 2021)) For any set of training**
_probability at leastnodes Vtrain from V 1 −all, for any subgroup of nodesδ, for any distribution Q we have Vm ⊂Vall, for any prior distribution P, with_

1
Eθ [Lm(θ; A, X)] Eθ [Ltrain(θ; A, X)] + (DKL( ) + ln [3]
_∼Q_ _≤_ _∼Q_ _√N0_ _Q||P_ _δ_ [+ 1]4 [+ Θ(][Kϵ][m][))][ (13)]


_where N0 is the volume of the training set Vtrain, K is the total number of classes, ϵm is a constant_
_depend on the subgroup_ _m._
_V_

If we take Vm = Vall in Lemma 1, we have

1
Eθ [Lall(θ; A, X)] Eθ [Ltrain(θ; A, X)] + (DKL( ) + ln [3]
_∼Q_ _≤_ _∼Q_ _√N0_ _Q||P_ _δ_ [+ 1]4 [+ Θ(][Kϵ][all][))][ (14)]


Assume both and are Gaussian distributions with diagonal covariance matrix, i.e. _i_
_N_ (µp, σp[2][I][d][}][)] P[,][ Q][i] _[∼N] Q[(][µ][q][, σ]q[2][I][d][}][)][, where][ d][ is the dimension of][ θ][, we have]_ _P_ _∼_


_d log_ _σ[σ]qp[2][2]_ _−_ _d + d_ _[σ]σqp[2][2]_ + || _[µ][p][ −]σp_ _[µ][q]_ _||2[2]_


DKL( ) = [1]
_Q||P_ 2


(15)


Take µq = θ, µp = 0, we expect the KL-divergence DKL(Q||P) to be as small as possible w.r.t. σp.

**Lemma 2. (Foret et al., 2021) Take µq = θ, µp = 0. There exist pre-defined σp such that**


1 + d log(1 + 2 ) (16)

_[||]dσ[θ][||]q[2][2]_




DKL( )
_Q||P_ _≤_ [1]2

Thus we have the generalization bound


Eθ [Lall(θ; A, X)] Eθ [Ltrain(θ; A, X)]
_∼Q_ _≤_ _∼Q_

+ 1 1 1 + d log(1 + 2 ) + ln [3] (17)
_√N0_ 2 _[||]dσ[θ][||]q[2][2]_ _δ_ [+ 1]4 [+ Θ(][Kϵ][all][)]

   


-----

As (θ, diag _σq[2][}][)][, consider][ z]_ (0, diag _σq[2][}][)][, we have]_ _σzq_ (0, Id) and
_Q_ _∼_ _N_ _{_ _∼_ _N_ _{_ _∼_ _N_

Eθ [Ltrain(θ; A, X)] = Ez[Ltrain(θ + z; A, X)]. Thus we have _m > 0_
_∼Q_ _∀_

Eθ [Ltrain(θ; A, X)]
_∼Q_
= Ez[Ltrain(θ + z; A, X)]

= Ez[Ltrain(θ + z; A, X) _[z]_ 2 _m]P(_ _[z]_ 2 _m)_
_| ||_ _σq_ _||_ _≤_ _||_ _σq_ _||_ _≤_

+ Ez[Ltrain(θ + z; A, X) _[z]_ 2 > m]P( _[z]_ 2 > m)) (18)
_| ||_ _σq_ _||_ _||_ _σq_ _||_

max 2 _m) + P(_ _[z]_ 2 > m).
_≤_ _||δ||2≤mσq[[][L][train][(][θ][ +][ δ][;][ A, X][)]][P][(][||][ z]σq_ _||_ _≤_ _||_ _σq_ _||_

max 2 > m).
_≤_ _||δ||2≤mσq[[][L][train][(][θ][ +][ δ][;][ A, X][)] +][ P][(][||][ z]σq_ _||_


As


_z_

_σq_ _√d,_

_[∼N]_ [(0][, I][d][)][, by Chernoff bound of chi-squred distribution we have when][ m >]

P( _[z]_ 2 > m) ( _[m][2]_ _d )[d/][2]_ (19)
_||_ _σq_ _||_ _≤_ _d [e][1][−]_ _[m][2]_


Thus

Eθ [Ltrain(θ; A, X)] max _d )[d/][2],_ (20)
_∼Q_ _≤_ _δ_ 2 _mσq[[][L][train][(][θ][ +][ δ][;][ A, X][)] + (]_ _[m]d [2]_ _[e][1][−]_ _[m][2]_
_||_ _||_ _≤_

combining it with Eq. 17 and denote σq = ρ/m we have


_Lall(θ; A, X)_ max _d )[d/][2]_
_≤_ _δ_ 2 _ρ[[][L][train][(][θ][ +][ δ][;][ A, X][)] + (]_ _[m]d [2]_ _[e][1][−]_ _[m][2]_
_||_ _||_ _≤_

(21)

1 1 1 + d log(1 + _[m][2][||][θ][||]2[2]_ ) + ln [3] _._
_√N0_ 2 _dρ[2]_ _δ_ [+ 1]4 [+ Θ(][Kϵ][all][)]

   


-----

