# PAC-Bayesian Adversarially Robust Generalization Bounds
for Graph Neural Network

Tan Sun  Junhong Lin

###### Abstract

Graph neural networks (GNNs) have gained popularity for various graph-related
tasks. However, similar to deep neural networks, GNNs are also vulnerable to
adversarial attacks. Empirical studies have shown that adversarially robust
generalization has a pivotal role in establishing effective defense algorithms
against adversarial attacks. In this paper, we contribute by providing
adversarially robust generalization bounds for two kinds of popular GNNs,
graph convolutional network (GCN) and message passing graph neural network,
using the PAC-Bayesian framework. Our result reveals that spectral norm of the
diffusion matrix on the graph and spectral norm of the weights as well as the
perturbation factor govern the robust generalization bounds of both models.
Our bounds are nontrivial generalizations of the results developed in (Liao et
al., 2020) from the standard setting to adversarial setting while avoiding
exponential dependence of the maximum node degree. As corollaries, we derive
better PAC-Bayesian robust generalization bounds for GCN in the standard
setting, which improve the bounds in (Liao et al., 2020) by avoiding
exponential dependence on the maximum node degree.

statistical learning theory, robust generalization bounds, PAC-Bayesian
analysis

##  1 Introduction

Graph neural network (GNN) (Scarselli et al., 2009) has developed rapidly in
recent years, due to the excellent performance in a variety of applications
with the graph-structure data. Generally, GNNs are neural networks that
combine local aggregation of node features and non-linear transformations to
predict the node-level labels or graph-level labels, in semi-supervised
learning (Kipf & Welling, 2017) and supervised learning (Pan et al., 2015,
2016; Zhang et al., 2018; Ying et al., 2018), respectively. With the rapid
development of GNN, there is an increasing interest in understanding the
generalization (Scarselli et al., 2018; Verma & Zhang, 2019; Du et al., 2019;
Garg et al., 2020; Liao et al., 2020; Esser et al., 2021; Ju et al., 2023) and
other theoretical properties of GNN.

Szegedy et al. (2013) and Goodfellow et al. (2015) reveal that deep neural
network (DNN) can be easily fooled by adversarial input samples and that
adversarial training can improve the generalization of DNN. GNN also has a
similar neural network structure and can be vulnerable to adversarial attacks
on graph data. Previous work focuses on how to attack on GNN (Dai et al.,
2018; Zügner et al., 2018; Bojchevski & Günnemann, 2019; Zügner et al., 2020;
Liu et al., 2019) and how to defend GNN against adversarial attacks (Zhang &
Zitnik, 2020; Wu et al., 2019; Entezari et al., 2020; Zhu et al., 2019; Tang
et al., 2020), but the theoretical analysis is relatively limited.

A recent line of work discusses the generalization of GNN in the standard
(non-adversarial) setting, and derive certain bounds on complexity notations
including Vapnik–Chervonenkis (VC) dimension and Rademacher complexity that
are used to characterize the generalization error, i.e., the disparity between
the performance on training and test datasets of a model. Specifically,
Scarselli et al. (2018) derive an upper bound of order
$\mathcal{O}(p^{4}n^{2})$ for the VC dimension of GNNs with sigmoid
activations, where $p$ is the number of parameters and $n$ is the number of
nodes. Verma & Zhang (2019) derive a generalization bound for single-layer
graph convolutional neural network (GCN) by analyzing the algorithmic
stability of stochastic gradient descent, where the bound depends on the
number of algorithm iterations and the largest absolute eigenvalue of the
graph convolution filter. Du et al. (2019) consider an infinitely wide multi-
layer GNN trained by gradient descent based on neural tangent kernels (Jacot
et al., 2018), and derive a generalization bound for this particular model.
These two results are constrained to specific settings and do not apply to
other scenarios. Garg et al. (2020) present the pioneering data-dependent
generalization bounds for GNNs employing Rademacher complexity, with a scaling
factor of $\mathcal{O}\left(hd^{l}\sqrt{l\log\left(hd\right)}\right)$. Here,
$d$ is the maximum degree of the graph, while $h$ and $l$ denote the width and
depth of the network, respectively.

In light of the earlier analysis, obtaining generalization bounds for GNNs
using complexity notations could be challenging, even in the standard setting.
Consequently, some studies have shifted their focus to the PAC-Bayesian
framework. Based on the PAC-Bayesian framework, Liao et al. (2020) provide
generalization bounds for GCN and message passing graph neural network
(MPGNN), where the bounds scale as
$\mathcal{O}\left(ld^{\frac{l-1}{2}}\sqrt{h\log(lh)}\right)$ and
$\mathcal{O}\left(ld^{l-2}\sqrt{h\log(lh)}\right)$ respectively. Recently, Ju
et al. (2023) derive generalization bounds of order
$\mathcal{O}\left(l\left\|P_{G}\right\|_{2}^{l-1}\sqrt{h}\right)$ for MPGNN.
The key idea of their analysis is to measure the stability of GNN against
noise perturbations using Hessians, and requires that the nonlinear
activations and the loss functions are twice-differentiable, Lipschitz-
continuous and their first-order and second-order derivatives are both
Lipschitz-continuous, which thus does not apply to the commonly used ReLU
activation. Here, $\left\|P_{G}\right\|_{2}$ is the spectral norm of the GNN’s
feature diffusion matrix $P_{G}$ on the graph $G$, and varies between
different models. Particularly, $\left\|P_{G}\right\|_{2}$ is less than 1 for
GCN and can be less than $d$ for MPGNN.

In seeking to grasp the constrained robust generalization abilities of GNNs in
the adversarial setting, in this paper, we provide adversarially robust
generalization bounds for two kinds of popular GNNs, GCN (Kipf & Welling,
2017) and MPGNN (Dai et al., 2016; Jin et al., 2019), using PAC-Bayesian
framework. Our result reveals that spectral norm of the diffusion matrix on
the graph, spectral and Frobenius norm of the weights, as well as the
perturbation factor govern the robust generalization bounds of both models.
Our bounds for GCN complement the findings in the standard setting for DNN in
(Neyshabur et al., 2017), as well as the results for GCN in (Liao et al.,
2020). All the bounds of these studies have the same spectrally-normalized
term of the weights and the dependencies on both depth and width:

$l\sqrt{h\log(lh)}\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}^{2}\sum_{i=1}^{l}\frac{\left\|W_{i}\right\|_{F}^{2}}{\left\|W_{i}\right\|_{2}^{2}}.$

To our knowledge, our derived PAC-Bayesian adversarially robust generalization
bounds may be the first kind for GNN in the adversarial robustness settings.
Even in the standard setting, our bounds improve the bounds in (Liao et al.,
2020) from $\mathcal{O}\left(ld^{\frac{l-1}{2}}\sqrt{h\log(lh)}\right)$ to
$\mathcal{O}(l\sqrt{h\log(lh)})$ for GCN, and
$\mathcal{O}\left(ld^{l-2}\sqrt{h\log(lh)}\right)$ to
$\mathcal{O}(l\left\|P_{G}\right\|_{2}^{l-2}\sqrt{h\log(lh)})$ for MPGNN,
avoiding the exponential dependence on the maximum degree $d$ of the graph.
Meanwhile, our results remove the extra first-order and second-order
Lipschitz-continuous assumptions in (Ju et al., 2023) for MPGNN, exhibiting
comparable tightness on the dependency on the depth, width and maximum degree.
In the context of adversarial robustness, the derived generalization bounds
incorporate an additional factor $\epsilon$ that represents the intensity of
the perturbation and is in general unavoidable.

To achieve the results, we follow the PAC-Bayesian framework (McAllester,
2003; Neyshabur et al., 2017) with necessary modification in the adversarial
setting, and relate the robust generalization error on a prior distribution of
models to that on a single model by adding random perturbation (that results
in a small perturbed robust margin loss) to the single model parameters. We
then proceed with the proof by constructing suitable prior distribution and
random perturbations, combining with novel concise techniques, which are
related to the Frobenius norm (instead of the spectral norm or the maximum
rows’ vector $2$-norm used in the previous literature) of the node
representations and related inequalities, to well estimate the sensitivity of
the robust margin loss concerning the model parameters and to meet the
challenging of avoiding the exponential dependence of the maximum degree.

Notations. We define some notations for the following analysis. Let $[k]$ be
the set of first $k$ positive integers, i.e., $[k]=\\{1,\dots,k\\}$,
$\bm{1}_{n}\in\mathbb{R}^{1\times n}$ be an all-one vector, and
$\mathbbm{1}\\{\cdot\\}$ be the indicator function. For a vector $x$,
$\left\|x\right\|_{p}$ denotes the vector $p$-norm. For a matrix $A$,
$\left\|A\right\|_{p}$ denotes the operator norm induced by the vector
$p$-norm, and $\left\|A\right\|_{F}$ denotes the Frobenius norm.

The rest of the paper are organized as follows. In Section 2, we briefly
review some other related works. In Section 3, we present the problem setup
and the main results. We outline the proof techniques in Section 4. Finally,
we discuss the limitations and some open problems in Section 5.

##  2 Related Work

Generalization Bounds. Classical results rely on complexity notions of neural
networks to regulate generalization bounds, employing measures such as VC-
dimension as seen in (Anthony & Bartlett, 2009), or Rademacher complexity as
discussed in (Bartlett & Mendelson, 2002). Norm-margin-based generalization
bounds are developed using Rademacher complexity for fully-connected neural
network in (Neyshabur et al., 2015; Bartlett et al., 2017; Golowich et al.,
2018). Neyshabur et al. (2015) establish a generalization bound with an
exponential dependence $2^{l}$ on the network depth $l$ using Frobenius norms
of parameters. Bartlett et al. (2017) showed a margin based generalization
bound that depends on spectral norm and $1$-norm of the layers of the
networks, reducing the dependence on depth. Golowich et al. (2018) provide
bounds on their Rademacher complexity assuming norm constraints on the
parameter matrix of each layer, refining the dependency on depth to
$\sqrt{l}$. Neyshabur et al. (2017) establish a PAC-Bayesian framework to
bound the generalization gap for fully-connected neural network, where the
bound depends on the product of the spectral norm of the weights in each layer
as well as the Frobenius norm of the weights. As mentioned above, the
generalization bounds on GNN are derived using different tools such as VC-
dimension (Scarselli et al., 2018), stability analysis (Verma & Zhang, 2019),
Rademacher complexity (Garg et al., 2020) and PAC-Bayesian analysis (Liao et
al., 2020; Ju et al., 2023).

Adversarial Attack and Defense. Zügner et al. (2018) focus on the adversarial
attacks against GCN and provide an algorithm to generate adversarial
perturbations targeting on the node features and the graph structures. Dai et
al. (2018) propose a reinforcement learning based attack method for
adversarial attacks against GNN by modifying the structures of the graph.
Zügner et al. (2020) develop a general attack on the training procedure of GCN
using meta-gradients. Bojchevski & Günnemann (2019) propose a principled
strategy for adversarial attacks on unsupervised node embeddings. There are
also some researches focusing on the defense methods. Wu et al. (2019) provide
a defense method by pre-processing the adjacency matrix of the graph. The
methods in (Zhu et al., 2019; Entezari et al., 2020) defend against attacks by
absorbing or dropping the noise information. Tang et al. (2020) use transfer
learning to improve the robustness of GNN. Zhang & Zitnik (2020) develop a
general algorithm to defend against a variety of training-time attacks that
perturb the graph structure.

Adversarial Generalization in DNN. A line of work presents the adversarially
robust generalization bounds on DNNs using Rademacher complexity (Khim & Loh,
2018; Yin et al., 2019; Awasthi et al., 2020; Gao & Wang, 2021; Xiao et al.,
2022). Khim & Loh (2018) derive robust generalization bounds for linear and
neural network via Rademacher complexity of a transformed function. Yin et al.
(2019) established generalization bounds for both linear models and one-
hidden-layer neural networks based on the surrogate loss introduced in
(Raghunathan et al., 2018) considering vector-$\infty$-norm-additive
perturbation. Awasthi et al. (2020) give upper and lower bounds for Rademacher
complexity of linear hypotheses with vector-$r$-norm-additive perturbation for
$r\geq 1$, and also provide upper bounds on Rademacher complexity of one
hidden layer neural networks, directly applying to the original network. Gao &
Wang (2021) and Farnia et al. (2019) show robust generalization bounds for
DNNs, considering specific attacks. Xiao et al. (2022) and Mustafa et al.
(2022) employ two different techniques, respectively, to calculate the
covering number that can be used to estimate the Rademacher complexity, for
adversarial function classes of DNNs. Further, Xiao et al. (2023) present a
robust generalization bound on DNN using PAC-Bayesian framework.

##  3 Adversarially Robust Generalization Bounds

In this section, we first introduce the problem setup for multi-class graph
classification problem with GCN and MPGNN, and preliminary results on PAC-
Bayesian analysis. We then present our main results: improved generalization
bounds in standard settings and adversarially robust generalization bounds for
GCN and MPGNN. Finally, we compare our results with existing results.

###  3.1 Preliminaries

####  3.1.1 Problem Setup

We consider a multi-class graph classification problem, in which, given an
undirected graph $G$, we would like to classify it into one of $K$ classes.
Specifically, the sample $z=(G,y)\in\mathcal{Z}$ consists of a graph $G$ and a
label $y\in\mathcal{Y}=\\{1,\dots,K\\}$. Each graph $G=(X,A)$ has a feature
matrix $X\in\mathcal{X}\subseteq\mathbb{R}^{n\times h_{0}}$ and an adjacency
matrix $A\in\mathcal{G}\subseteq\mathbb{R}^{n\times n}$, where each row of $X$
is the feature vector of a node, $n$ is the number of nodes and $h_{0}$ is the
input feature dimension. The classification model $f$ maps the graph $G$ to a
$K$-dimension vector, and we take the index of the maximum element in $f(G)$
as the output $\hat{y}=\arg\max_{i\in[K]}f(G)_{i}$, where $f(G)_{i}$ is $i$-th
element of $f(G)$. We assume that the training set $S=\\{z_{1},\dots,z_{m}\\}$
with $m$ samples that are independent and identically distributed from an
unknown data distribution $\mathcal{D}$, and that the classification model is
from the hypothesis class $\mathcal{H}$.

We focus on two kinds of GNN, GCN and MPGNN, which are the most popular
variants of GNN. For simplicity, we define the model parameterized by $w$ as
$f_{w}\in\mathcal{H}:\mathcal{X}\times\mathcal{G}\rightarrow\mathbb{R}^{1\times
K}$, where $w$ is the vectorization of all model parameters.

GCN. An $l$-layer ($l>1$ otherwise the model is trivial) GCN can be defined
as,

$\displaystyle H_{k}$
$\displaystyle=\sigma_{k}\left(P_{G}H_{k-1}W_{k}\right),\ k\in[l-1],$
$\displaystyle H_{l}$ $\displaystyle=\frac{1}{n}\bm{1}_{n}H_{l-1}W_{l},$ (1)

where $H_{k}\in\mathbb{R}^{n\times h_{k}},k\in[l-1]$ are the node
representations in each layer, $H_{l}\in\mathbb{R}^{1\times K}$ is the
readout, and $W_{k}\in\mathbb{R}^{h_{k-1}\times h_{k}},k\in[l]$ are the
parameters in the $k$-th layer. And we let $H_{0}=X$. The matrix
$P_{G}\in\mathbb{R}^{n\times n}$ is related to the graph structure and
$\sigma_{k}(\cdot),k\in[l-1]$ are some element-wise non-linear mappings.
Practically, for GCN, we take $P_{G}$ as the Laplacian of the graph, defined
as $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$, where $\tilde{A}=A+I$ and
$\tilde{D}=\mathrm{diag}\left(\sum_{j=1}^{n}\tilde{A}_{ij},i\in[n]\right)$ is
the degree matrix of $\tilde{A}$. Throughout of this paper, for GCN, $P_{G}$
is taken as the Laplacian $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$, and the
non-linear mappings are chosen as ReLU, that is,
$\sigma_{k}(x)=\max(0,x),\forall k\in[l-1]$.

MPGNN. There are several variants of MPGNN (Dai et al., 2016; Gilmer et al.,
2017; Jin et al., 2019) and we introduce the models stated in (Garg et al.,
2020) which are popular in the generalization analysis of GNN. The $l$-layer
($l>1$ otherwise the model is trivial) MPGNN can be defined as,

$\displaystyle
H_{k}=\phi_{k}\left(XU_{k}+\rho_{k}\left(P_{G}\psi_{k}\left(H_{k-1}\right)W_{k}\right)\right),\
k\in[l-1],$ $\displaystyle H_{l}=\frac{1}{n}\bm{1}_{n}H_{l-1}W_{l},$ (2)

where $H_{k}\in\mathbb{R}^{n\times h_{k}},k\in[l-1]$ are the node
representations in each layer, $H_{l}\in\mathbb{R}^{1\times K}$ is the
readout, $W_{k}\in\mathbb{R}^{h_{k-1}\times h_{k}},k\in[l]$ and
$U_{k}\in\mathbb{R}^{h_{0}\times h_{k}},k\in[l-1]$ are the parameters in the
$k$-th layer. Here we let $H_{0}=0$. Several common designs for $P_{G}$ would
be the adjacency matrix, the normalized adjacency matrix or the Laplacian of
the graph. $\phi_{k},\rho_{k},\psi_{k}:\mathbb{R}^{n\times
h}\rightarrow\mathbb{R}^{n\times h},k\in[l-1]$ are element-wise non-linear
mappings, e.g., ReLU and Tanh. In MPGNN, if we take $U_{1}$ as identity
matrix, $U_{k},2\leq k\leq l-1$ as zero matrices and $\rho_{k},\psi_{k}$ as
identity mappings, then we could get a GCN model with $l-1$ layers.

As defined above, we denote
$w=vec\left(\left\\{W_{k}\right\\}_{k=1}^{l}\right)$ and
$w=vec\left(\left\\{W_{k}\right\\}_{k=1}^{l},\left\\{U_{k}\right\\}_{k=1}^{l-1}\right)$
in different settings for GCN and MPGNN, respectively. Here, for a set of
matrices, $vec(\cdot)$ is the vectorization of the set, which is the stack of
columns for all matrices in the set.

Margin Loss. Given a GNN $f$, we focus on the generalization gap to evaluate
the generalization performance of the model. For the multi-class
classification problem, we can use the multi-class margin loss to define the
generalization gap (Bartlett et al., 2017). First, we define the margin
operator of the true label $y\in[K]$ given $G\in\mathcal{X}\times\mathcal{G}$
for a GNN model $f_{w}$ as

$\displaystyle
M\left(f_{w}\left(G\right),y\right)=f_{w}\left(G\right)_{y}-\max_{j\neq
y}f_{w}\left(G\right)_{j}.$

And for the convenience of the following analysis, we define the margin
operator of a pair of two classes $(i,j)$ given
$G\in\mathcal{X}\times\mathcal{G}$ for a GNN model $f_{w}$ as

$\displaystyle
M\left(f_{w}\left(G\right),i,j\right)=f_{w}\left(G\right)_{i}-f_{w}\left(G\right)_{j},\
i,j\in[K].$

The margin operator reflects the gap between the output for the true label and
other labels. With this, the model classifies the graph correctly if and only
if the margin operator is larger than zero. We expect the model to classify
the graph correctly with a confidence, and hence, for a margin $\gamma>0$, we
define the expected margin loss of the model $f_{w}$ over the data
distribution $\mathcal{D}$ as the probability that the margin operator is less
than the margin, that is,

$\displaystyle
L_{\mathcal{D},\gamma}\left(f_{w}\right)=\mathbb{P}_{(G,y)\sim\mathcal{D}}\left\\{M\left(f_{w}\left(G\right),y\right)\leq\gamma\right\\}.$

The empirical margin loss over the dataset $S$ is defined as

$\displaystyle\hat{L}_{S,\gamma}\left(f_{w}\right)=\frac{1}{m}\sum_{(G,y)\in
S}\mathbbm{1}\left\\{M\left(f_{w}\left(G\right),y\right)\leq\gamma\right\\}.$

Thus, the generalization error of a model $f_{w}$ can be defined as the gap
between the expected loss and the empirical loss,
$L_{\mathcal{D},0}\left(f_{w}\right)-\hat{L}_{S,\gamma}\left(f_{w}\right)$.

Similarly, for adversarial setting, we can define the robust margin loss.
Adversarial examples are usually generated from an attack algorithm. Given $G$
and $f_{w}$, let $\delta_{w}(G)$ be the output set of an attack algorithm,
which contains the adversarial samples of $G$ with respect to $f_{w}$. As the
margin is expected to be larger, we choose the adversarial sample
$G^{*}=\mathop{\arg\inf}\limits_{G^{\prime}\in\delta_{w}(G)}M\left(f_{w}\left(G^{\prime}\right),y\right)\in\delta_{w}(G)$
which minimizes the margin operator. With this, we can define the robust
margin operator of the true label $y$ given $G$ for the GNN model $f_{w}$ as

$\displaystyle RM\left(f_{w}\left(G\right),y\right)$
$\displaystyle=\inf_{G^{\prime}\in\delta_{w}(G)}M\left(f_{w}\left(G^{\prime}\right),y\right)$
$\displaystyle=\inf_{G^{\prime}\in\delta_{w}(G)}\left(f_{w}\left(G^{\prime}\right)_{y}-\max_{j\neq
y}f_{w}\left(G^{\prime}\right)_{j}\right).$

And similarly, we define the robust margin operator of a pair of two classes
$(i,j)$ given $G\in\mathcal{X}\times\mathcal{G}$ for a model $f_{w}$ as

$\displaystyle RM\left(f_{w}\left(G\right),i,j\right)$
$\displaystyle=\inf_{G^{\prime}\in\delta_{w}(G)}\left(f_{w}\left(G^{\prime}\right)_{i}-f_{w}\left(G^{\prime}\right)_{j}\right).$

For margin $\gamma>0$, the expected robust margin loss of the model $f_{w}$
over the data distribution $\mathcal{D}$ is defined as

$\displaystyle
R_{\mathcal{D},\gamma}\left(f_{w}\right)=\mathbb{P}_{(G,y)\sim\mathcal{D}}\left\\{RM\left(f_{w}\left(G\right),y\right)\leq\gamma\right\\},$

and the empirical robust margin loss over the dataset $S$ is defined as

$\displaystyle\hat{R}_{S,\gamma}\left(f_{w}\right)=\frac{1}{m}\sum_{(G,y)\in
S}\mathbbm{1}\left\\{RM\left(f_{w}\left(G\right),y\right)\leq\gamma\right\\}.$

With this, the robust generalization error of a model $f_{w}$ can be defined
as the gap between the robust expected loss and the robust empirical loss,
$R_{\mathcal{D},0}\left(f_{w}\right)-\hat{R}_{S,\gamma}\left(f_{w}\right)$.

####  3.1.2 Background of PAC-Bayesian Analysis

PAC-Bayesian analysis (McAllester, 2003) provides probability approximation
correct (PAC) bound for generalization errors. In particular, the purpose of a
learning process is to provide a posterior distribution $Q$ of a parameterized
predictor $f_{w}$ over the hypothesis class $\mathcal{H}$, which minimizes the
expected margin loss with respect to the data distribution $\mathcal{D}$,

$\displaystyle L_{\mathcal{D},\gamma}\left(Q\right)=\mathbb{E}_{w\sim
Q}\left[L_{\mathcal{D},\gamma}\left(f_{w}\right)\right].$

Since the true distribution of the data is unknowable, we define the empirical
margin loss with respect to the data sample $S$,

$\displaystyle\hat{L}_{S,\gamma}\left(Q\right)=\mathbb{E}_{w\sim
Q}\left[\hat{L}_{S,\gamma}\left(f_{w}\right)\right].$

PAC-Bayesian analysis provides guarantees for the gap between the expected and
empirical loss. Following (McAllester, 2003), we present the subsequent
theorem with respect to the robust margin loss, defined as

$\displaystyle R_{\mathcal{D},\gamma}\left(Q\right)=\mathbb{E}_{w\sim
Q}\left[R_{\mathcal{D},\gamma}\left(f_{w}\right)\right],$

and

$\displaystyle\hat{R}_{S,\gamma}\left(Q\right)=\mathbb{E}_{w\sim
Q}\left[\hat{R}_{S,\gamma}\left(f_{w}\right)\right].$

######  Theorem 3.1 (McAllester (2003)).

Let $P$ be a prior distribution over $\mathcal{H}$ that is independent of the
training set. Then for any $\delta\in(0,1)$, with probability at least
$1-\delta$ over the choice of the training set $S=\\{z_{1},\dots,z_{m}\\}$
independently sampled from $\mathcal{D}$, for all distributions $Q$ over
$\mathcal{H}$ and any $\gamma>0$, we have

$\displaystyle
R_{\mathcal{D},\gamma}\left(Q\right)\leq\hat{R}_{S,\gamma}\left(Q\right)+\sqrt{\frac{KL\left(Q\|P\right)+\log(2m/\delta)}{2(m-1)}}.$

Here $KL\left(Q\|P\right)$ is the KL-divergence between two distributions. The
result in the theorem holds for any given prior distribution $P$ (that is
independent from the training set) and all posterior distributions $Q$.
Therefore, we can construct specific priors and posteriors so that we can work
out the bound. Additionally, the result is related to quantities defined on
distribution over models, while many learning processes learn a single model.
Hence, in order to apply Theorem 3.1 to a single model $f_{w}$, we construct a
posterior distribution $Q$ by adding random perturbations $\Delta w$ to the
learned parameters $w$, where $w$ is considered to be fixed and $\Delta w$ is
drawn from a known distribution. We have the following lemma, which relates
the loss on a distribution $Q$ with the loss on a single model.

######  Lemma 3.2.

Let
$f_{w}\left(G\right):\mathcal{X}\times\mathcal{G}\rightarrow\mathbb{R}^{K}$ be
any model with parameters $w$, and $P$ be any distribution on the parameters
that is independent of the training data. For any $w$, we construct a
posterior $Q(w+\Delta w)$ by adding a random perturbation $\Delta w$ to $w$,
s.t.,

$\displaystyle\mathbb{P}_{\Delta w}\Bigg{\\{}\max_{i,j\in[K],\atop
G\in\mathcal{X}\times\mathcal{G}}\big{|}RM\left(f_{w+\Delta
w}(G),i,j\right)-RM\left(f_{w}(G),i,j\right)\big{|}<\frac{\gamma}{2}\Bigg{\\}}\geq\frac{1}{2}.$

Then, for any $\gamma,\delta>0$, with probability at least $1-\delta$ over the
choice of the training set $S=\\{z_{1},\dots,z_{m}\\}$ independently sampled
from $\mathcal{D}$, for any $w$, we have,

$\displaystyle
R_{\mathcal{D},0}\left(f_{w}\right)\leq\hat{R}_{S,\gamma}\left(f_{w}\right)+\sqrt{\frac{2KL\left(Q\|P\right)+\log(8m/\delta)}{2(m-1)}}.$

Here, the KL is evaluated with that $w$ is treated as fixed while $\Delta w$
is random, i.e. the distribution of $Q$ is the distribution of $\Delta w$
shifted by $w$.

Neyshabur et al. (2017) provide the lemma to give a margin-based
generalization bound derived from the PAC-Bayesian bound. Liao et al. (2020)
improve the lemma and present the lemma in a two-side form. Both of the above
lemmas are proposed in the standard settings. We present Lemma 3.2 of the two-
side form with the robust margin loss in the adversarial settings. We provide
the proof sketch of Lemma 3.2 in Section 4 while the proof details of Theorems
3.1 and 3.2 will be given in Sections A.2.1 and A.2.2, respectively.

###  3.2 Main Results

In this part, we first introduce some necessary assumptions and then present
our main results on generalization bounds for GNN.

First, we make the following common assumption for the graph data, which also
appears in the literature and is easily validated on real-world data.

######  Assumption 3.3.

For any graph $G=(X,A)\in\mathcal{X}\times\mathcal{G}$, the node features are
contained in a spectral norm ball with radius $B$, that is,
$\left\|X\right\|_{2}\leq B$.

We then introduce the following two assumptions which are related to the
models.

######  Assumption 3.4.

For both GCN and MPGNN models, the maximum layer width is $h$, that is
$h_{k}\leq h,\forall k\in[l]\cup\\{0\\}$.

######  Assumption 3.5.

For any model $f_{w}\in\mathcal{H}$ of MPGNN defined in Equation 2, the weight
matrices in different layers are uniformly bounded, that is
$\left\|W_{k}\right\|_{2}\leq M_{2},\forall k\in[l]$ and
$\left\|U_{k}\right\|_{2}\leq M_{1},\forall k\in[l-1]$. The mappings
$\phi_{k},\rho_{k},\psi_{k},k\in[l-1]$ are all $L$-Lipschitz and centered at
zero, that is $\phi_{k}(0)=\rho_{k}(0)=\psi_{k}(0)=0,\forall k\in[l-1]$.

Motivated by practical designs (Gilmer et al., 2017; Jin et al., 2018), in the
above we consider MPGNN models with $W_{k}$ and $U_{k}$ sharing the same norm
upper bounds for each $k$.

####  3.2.1 Generalization Bounds for GCN

We now present the improved generalization bounds for GCN in standard setting.

######  Theorem 3.6 (Generalization Bounds for GCN).

Under Assumptions 3.3 and 3.4, for any $\delta,\gamma>0$, with probability at
least $1-\delta$, over the choice of a training set
$S=\\{z_{1},\dots,z_{m}\\}$ independently sampled from $\mathcal{D}$, for any
$w$, we have

$\displaystyle
L_{\mathcal{D},0}\left(f_{w}\right)\leq\hat{L}_{S,\gamma}\left(f_{w}\right)+\mathcal{O}\left(\sqrt{\frac{B^{2}l^{2}h\log(lh)\Phi(f_{w})+\log(ml/\delta)}{\gamma^{2}m}}\right),$

where
$\Phi(f_{w})=\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}^{2}\sum_{i=1}^{l}\frac{\left\|W_{i}\right\|_{F}^{2}}{\left\|W_{i}\right\|_{2}^{2}}$.

Theorem 3.6 shows that the generalization bound of GCN does not grow with the
maximal degree of the graph.

For the robust case, we consider an $\epsilon$-attack ($\epsilon>0$), where
given a sample $G=(X,A)$, the attack sample
$G^{\prime}=(X^{\prime},A^{\prime})$ satisfies that
$\left\|X^{\prime}-X\right\|_{2}\leq\epsilon$ and $A^{\prime}$ can be any
adjacency matrix.

######  Theorem 3.7 (Robust Generalization Bounds for GCN).

Under Assumptions 3.3 and 3.4, consider the $\epsilon$-attack with
$\epsilon>0$, for any $\delta,\gamma>0$, with probability at least $1-\delta$
over the choice of a training set $S=\\{z_{1},\dots,z_{m}\\}$ independently
sampled from $\mathcal{D}$, for any $w$, we have

$\displaystyle
R_{\mathcal{D},0}\left(f_{w}\right)\leq\hat{R}_{S,\gamma}\left(f_{w}\right)+\mathcal{O}\left(\sqrt{\frac{(B+\epsilon)^{2}l^{2}h\log(lh)\Phi(f_{w})+\log(ml/\delta)}{\gamma^{2}m}}\right),$

where
$\Phi(f_{w})=\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}^{2}\sum_{i=1}^{l}\frac{\left\|W_{i}\right\|_{F}^{2}}{\left\|W_{i}\right\|_{2}^{2}}$.

The above generalization bound in the adversarial setting is as tight as the
bound in Theorem 3.6 for the standard setting up to the $\epsilon$ factor of
attack, which is in general unavoidable.

For the GCN model, we take $P_{G}$ as the Laplacian of the graph. As the
spectral norm of the Laplacian is less than one, the bound due to the graph
architecture $\|P_{G}\|^{l}$ raised in our proof can be well controlled and we
thus get a bound that is independent on the maximum degree $d$ of the graph.

####  3.2.2 Generalization Bounds for MPGNN

We now provide the adversarially robust generalization bounds for MPGNN.

######  Theorem 3.8 (Robust Generalization Bounds for MPGNN).

Under Assumptions 3.3 to 3.5, consider the $\epsilon$-attack ($\epsilon>0$).
For any $\delta,\gamma>0$, with probability at least $1-\delta$ over the
choice of a training set $S=\\{z_{1},\dots,z_{m}\\}$ independently sampled
from $\mathcal{D}$, for any $w$, the following results hold:
if $\tau=1$, then

$\displaystyle
R_{\mathcal{D},0}\left(f_{w}\right)\leq\hat{R}_{S,\gamma}\left(f_{w}\right)+\mathcal{O}\left(\sqrt{\frac{(l+1)^{4}\Psi_{0}\Psi_{1}(f_{w})+\log(m/\delta)}{\gamma^{2}m}}\right),$

if $\tau\neq 1$, then

$\displaystyle
R_{\mathcal{D},0}\left(f_{w}\right)\leq\hat{R}_{S,\gamma}\left(f_{w}\right)+\mathcal{O}\left(\sqrt{\frac{l^{2}\Psi_{0}\Psi_{2}(f_{w})+\log(m(l+1)/\delta)}{\gamma^{2}m}}\right).$

Here, $\tau=L^{3}M_{2}\max_{\mathcal{D}}\\{\left\|P_{G}\right\|_{2}\\}$,
$\xi=LM_{1}M_{2}\frac{\tau^{l-1}-1}{\tau-1},$
$\zeta=\min\left(\left\\{\left\|W_{k}\right\|_{2}\right\\}_{k=1}^{l},\left\\{\left\|U_{k}\right\|_{2}\right\\}_{k=1}^{l-1}\right)$,
$|w|_{2}^{2}=\sum_{i=1}^{l}\left\|W_{i}\right\|_{F}^{2}+\sum_{i=1}^{l-1}\left\|U_{i}\right\|_{F}^{2}$,
$\Psi_{0}=(B+\epsilon)^{2}h\log(lh),$

$\displaystyle\Psi_{1}(f_{w})$
$\displaystyle=\max\left\\{\zeta^{-6},(LM_{1}M_{2})^{3}\right\\}|w|_{2}^{2},$
$\displaystyle\Psi_{2}(f_{w})$
$\displaystyle=\max\left\\{\zeta^{-1},\xi^{1/l}\right\\}^{2l+2}|w|_{2}^{2}.$

In the above results, the bounds vary for two typical settings of $\tau$. The
generalization bound for $\tau\neq 1$ scales as
$\mathcal{O}\left(\left\|P_{G}\right\|_{2}^{l-2}l\sqrt{h\log(lh)}\right)$. In
practice, $P_{G}$ is usually chosen as the adjacency matrix $A$ of the graph,
where $\|P_{G}\|$ is less than the maximum degree $d$ of the graph.

###  3.3 Comparison

We compare our results with some existing bounds in the standard settings. For
generalization bounds from both models, we will focus on the dependency on the
depth $l$ and width $h$ as well as maximum degree $d$ of the graph.

For GCN in standard settings, Liao et al. (2020) derive PAC-Bayesian
generalization bounds of order
$\mathcal{O}\left(d^{\frac{l-1}{2}}l\sqrt{h\log(lh)}\right)$, under exactly
the same set-up and assumptions in Theorem 3.6 of this paper. Our derived
bounds from Theorem 3.6 scale as $\mathcal{O}\left(l\sqrt{h\log(lh)}\right)$.
The latter is tighter than the former with a factor of the maximum degree $d$,
which is usually much larger than $1$ in practice.

For MPGNN in standard settings, the Rademacher complexity bound in (Garg et
al., 2020) scales as $\mathcal{O}\left(h\sqrt{l\log(hd)}\right)$. For PAC-
Bayesian framework, the bound in (Liao et al., 2020) scales as
$\mathcal{O}\left(d^{l-2}l\sqrt{h\log(lh)}\right)$, and the bound in (Ju et
al., 2023) scales as
$\mathcal{O}\left(\left\|P_{G}\right\|_{2}^{l-1}l\sqrt{h}\right)$, while our
bound scales as
$\mathcal{O}\left(\left\|P_{G}\right\|_{2}^{l-2}l\sqrt{h\log(lh)}\right)$.
Note that (Ju et al., 2023) requires that the nonlinear activations and the
loss functions are twice-differentiable, Lipschitz-continuous and their first-
order and second-order derivatives are both Lipschitz-continuous, which thus
does not apply to the commonly used ReLU activation. When $P_{G}$ is chosen as
the adjacency matrix $A$ of the graph, it has been shown that for any
undirected graph, the spectral norm of $P_{G}$ is less than the maximum degree
$d$. See Section A.1 for a proof.

##  4 Proof Techniques

In this section, we show the key difficulties of the proofs and present our
proof technique of Theorem 3.7. The proof techniques of Theorems 3.6 and 3.8
are similar, and their proof details will be given in Sections A.3 and A.4.

The first key of the proof is Lemma 3.2, which relates the robust margin loss
$R_{\mathcal{D},\gamma}\left(Q\right)$ on a distribution $Q$ in Theorem 3.1
with the loss $R_{\mathcal{D},0}\left(f_{w}\right)$ on a single model $f_{w}$
in Theorem 3.7. Lemma 3.2 is of the two-side form with the robust margin loss
in the adversarial settings, following from (Neyshabur et al., 2017; Liao et
al., 2020) in the standard setting with modifications. Its proof sketch is
given as follows and the proof detail is attached in Section A.2.2.

###### Proof Sketch of Lemma 3.2.

Using $Q(w+\Delta w)$, we construct a new distribution $\tilde{Q}$ such that
for $\tilde{w}\sim\tilde{Q}$, and for any
$i,j\in[K],G\in\mathcal{X}\times\mathcal{G}$,

$\displaystyle\left|RM\left(f_{\tilde{w}}\left(G\right),i,j\right)-RM\left(f_{w}\left(G\right),i,j\right)\right|\leq\frac{\gamma}{2}.$

With the above equation, from the definition of the robust margin loss, we can
show that $R_{\mathcal{D},0}\left(f_{w}\right)\leq
R_{\mathcal{D},\frac{\gamma}{2}}\left(f_{\tilde{w}}\right)$ and
$\hat{R}_{S,\frac{\gamma}{2}}\left(f_{\tilde{w}}\right)\leq\hat{R}_{S,\gamma}\left(f_{w}\right)$.
Using Theorem 3.1,

$\displaystyle R_{\mathcal{D},0}\left(f_{w}\right)$
$\displaystyle\leq\mathbb{E}_{\tilde{w}}\left[R_{\mathcal{D},\frac{\gamma}{2}}\left(f_{\tilde{w}}\right)\right]$
$\displaystyle\leq\mathbb{E}_{\tilde{w}}\left[\hat{R}_{S,\frac{\gamma}{2}}\left(f_{\tilde{w}}\right)\right]+\sqrt{\frac{KL\left(\tilde{Q}\|P\right)+\log(2m/\delta)}{2(m-1)}}$
$\displaystyle\leq\hat{R}_{S,\gamma}\left(f_{w}\right)+\sqrt{\frac{KL\left(\tilde{Q}\|P\right)+\log(2m/\delta)}{2(m-1)}}.$

From the definitions of KL-divergence and $\tilde{Q}$,

$\displaystyle KL\left(\tilde{Q}\|P\right)\leq 2KL\left(Q\|P\right)+2\log(2).$

Then, the proof can be finished with direct calculations. ∎

The second key difficulty is to well estimate the change in the robust margin
operator with a perturbation on the parameters, adopting the spectral norm of
$P_{G}$ rather than the maximum degree $d$. The estimating can be divided into
two steps. The first step is to bound the change in the output of the model
with the perturbation. We present the following lemma which shows that the
change can be bounded by the norm of the parameters without dependence on the
degree of the graph.

######  Lemma 4.1.

Let $f_{w}\in\mathcal{H}$ be a GCN model with $l$ layers. For any $w$, any
perturbation $\Delta w=vec\left(\left\\{\Delta
W_{i}\right\\}_{i=1}^{l}\right)$ such that for all $i\in[l]$, $\left\|\Delta
W_{i}\right\|_{2}\leq\frac{1}{l}\left\|W_{i}\right\|_{2}$, for any
$G=(X,A)\in\mathcal{X}\times\mathcal{G}$, the change in the output of GCN is
bounded as

$\displaystyle\left\|f_{w+\Delta
w}\left(G\right)-f_{w}\left(G\right)\right\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{n}}e\left\|X\right\|_{F}\left\|P_{G}\right\|_{2}^{l-1}\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)\sum_{i=1}^{l}\frac{\left\|\Delta
W_{i}\right\|_{2}}{\left\|W_{i}\right\|_{2}}$ $\displaystyle\leq
eB\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)\sum_{i=1}^{l}\frac{\left\|\Delta
W_{i}\right\|_{2}}{\left\|W_{i}\right\|_{2}}.$

###### Proof Sketch.

We can bound the 2-norm of the change in the output of the model for a
perturbation $\Delta w$ on the parameters $w$ as,

$\displaystyle\left\|f_{w+\Delta
w}\left(G\right)-f_{w}\left(G\right)\right\|_{2}\lesssim\left\|H_{l-1}^{\prime}-H_{l-1}\right\|_{F}+\left\|H_{l-1}\right\|_{F},$

where $a\lesssim b$ indicates that $a$ is less than $b$ up to some constants.

In order to avoid a dependence on the degree of the graph, we use the spectral
norm of $P_{G}$, which is less then $1$ for GCN, and we use basic inequality
related to Frobenius norm to get an iteration relationship on the node
presentation in each layer, that is,

$\displaystyle\left\|H_{j}\right\|_{F}$
$\displaystyle\leq\left\|P_{G}\right\|_{2}\left\|H_{j-1}\right\|_{F}\left\|W_{j}\right\|_{2}$
$\displaystyle\leq\left\|X\right\|_{F}\left\|P_{G}\right\|_{2}^{j}\prod_{i=1}^{j}\left\|W_{i}\right\|_{2},\
j\in[l-1],$

and an iteration on the change in node presentation,

$\displaystyle\left\|H_{j}^{\prime}-H_{j}\right\|_{F}$
$\displaystyle\leq\left\|P_{G}\right\|_{2}\left\|H_{j-1}^{\prime}-H_{j-1}\right\|_{F}\left\|W_{j}+\Delta
W_{j}\right\|_{2}+\left\|P_{G}\right\|_{2}\left\|H_{j-1}\right\|_{F}\left\|\Delta
W_{j}\right\|_{2}$
$\displaystyle\leq\left\|X\right\|_{F}\left\|P_{G}\right\|_{2}^{j}\left(\prod_{i=1}^{j}\left\|W_{i}\right\|_{2}\right)\sum_{i=1}^{j}\frac{\left\|\Delta
W_{i}\right\|_{2}}{\left\|W_{i}\right\|_{2}}\left(1+\frac{1}{l}\right)^{j-i},$

where $H_{l-1}^{\prime}$ is the node representation of the $l-1$ layer of
$w+\Delta w$. Combining, we can prove the result. ∎

The second step is to bound the change in the robust margin operator using
Lemma 4.1.

######  Lemma 4.2 (Perturbation Bound for GCN).

Under Assumptions 3.3 and 3.4, consider the $\epsilon$-attack ($\epsilon>0$),
for any $w$ and any perturbation $\Delta w=vec\left(\left\\{\Delta
W_{i}\right\\}_{i=1}^{l}\right)$ such that for all $i\in[l]$, $\left\|\Delta
W_{i}\right\|_{2}\leq\frac{1}{l}\left\|W_{i}\right\|_{2}$. The change in the
robust margin operator is bounded as

$\displaystyle\left|RM\left(f_{w+\Delta
w}\left(G\right),i,j\right)-RM\left(f_{w}\left(G\right),i,j\right)\right|\leq
2e(B+\epsilon)\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)\sum_{i=1}^{l}\frac{\left\|\Delta
W_{i}\right\|_{2}}{\left\|W_{i}\right\|_{2}}.$

###### Proof Sketch.

By the definition of the robust margin loss,

$\displaystyle\left|RM\left(f_{w+\Delta
w}\left(G\right),i,j\right)-RM\left(f_{w}\left(G\right),i,j\right)\right|$
$\displaystyle=\left|\inf\limits_{G^{\prime}\in\delta_{\tilde{w}}(G)}M\left(f_{\tilde{w}}\left(G^{\prime}\right),i,j\right)-\inf\limits_{G^{\prime}\in\delta_{w}(G)}M\left(f_{w}\left(G^{\prime}\right),i,j\right)\right|$
$\displaystyle\leq\max\left\\{\left|M\left(f_{\tilde{w}}\left(G(\tilde{w})\right),i,j\right)-M\left(f_{w}\left(G(\tilde{w})\right),i,j\right)\right|,\right.$
$\displaystyle\qquad\left.\left|M\left(f_{\tilde{w}}\left(G(w)\right),i,j\right)-M\left(f_{w}\left(G(w)\right),i,j\right)\right|\right\\},$

where
$G(w)=\mathop{\arg\inf}_{G^{\prime}\in\delta_{w}(G)}M\left(f_{w}\left(G^{\prime}\right),i,j\right)$
and $\tilde{w}=w+\Delta w$. Then, we bound each term in the maximum by the
2-norm of the change of the output,

$\displaystyle\left|M\left(f_{\tilde{w}}\left(G(\tilde{w})\right),i,j\right)-M\left(f_{w}\left(G(\tilde{w})\right),i,j\right)\right|\leq
2\left\|f_{\tilde{w}}\left(G\right)-f_{w}\left(G\right)\right\|_{2}.$

Combining the above, we can prove the result. ∎

The proof detail can be found in Section A.3.1.

Finally, the key to prove Theorem 3.7 using Lemmas 3.2 and 4.2, is to
construct suitable prior and posterior distributions satisfying the conditions
in the lemmas. We provide the proof sketch here and the detail is presented in
Section A.3.2.

###### Proof Sketch of Theorem 3.7.

Let $\beta=\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)^{1/l}$. We
normalize the parameters as
$\tilde{W_{i}}=\frac{\beta}{\left\|W_{i}\right\|_{2}}W_{i}$. By the
homogeneity of ReLU, we can verify that the terms appear in the bound stay the
same after applying the normalization. Therefore, without loss of generality,
we assume that for all $i\in[l]$, $\left\|W_{i}\right\|_{2}=\beta$.

Consider the prior distribution $P=\mathcal{N}(0,\sigma^{2}I)$ and the random
perturbation $\Delta w\sim\mathcal{N}(0,\sigma^{2}I)$, where the variance
$\sigma^{2}$ will be set based on some approximation $\tilde{\beta}$ of
$\beta$. And the approximation $\tilde{\beta}$ is chosen from the centering
points to a cover set which covers the meaningful range of $\beta$.

Firstly, we fix $\tilde{\beta}$ and consider $\beta$ satisfying
$\left|\beta-\tilde{\beta}\right|\leq\frac{\beta}{l}$. To make sure that the
condition in Lemma 3.2 holds, with Lemma 4.2, we set
$\sigma=\frac{\gamma}{4e^{2}(B+\epsilon)\tilde{\beta}^{l-1}l\sqrt{2h\log(4lh)}}$.
The requirement $\left\|\Delta
W_{i}\right\|_{2}\leq\frac{1}{\ell}\left\|W_{i}\right\|_{2},i\in[l]$ in Lemma
4.2 is satisfied if $\frac{\gamma}{4e(B+\epsilon)}\leq\beta^{l}$, which will
be confirmed later.

Then, by calculating the KL term in Lemma 3.2 as

$\displaystyle
KL\left(Q\|P\right)\leq\mathcal{O}\left(\frac{(B+\epsilon)^{2}l^{2}h\log(lh)}{\gamma^{2}}\Phi(f_{w})\right),$

we have that for any fixed $\tilde{\beta}$, with probability at least
$1-\delta$ over $S$, for all $w$ such that
$\left|\beta-\tilde{\beta}\right|\leq\frac{1}{l}\beta$, the bound holds.

Finally, we consider multiple choices of $\tilde{\beta}$ so that for any
$\beta$, we can bound the generalization in the similar form. We only need to
consider $\beta$ in the following range:

$\displaystyle\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}\leq\beta\leq\left(\frac{\gamma\sqrt{m}}{2(B+\epsilon)}\right)^{1/l},$

since otherwise the bound holds trivially as
$R_{\mathcal{D},0}\left(f_{w}\right)\leq 1$ by definition. Note that the lower
bound above also ensures the required condition in Lemma 4.2. A sufficient
condition for $\left|\beta-\tilde{\beta}\right|\leq\frac{1}{l}\beta$ would be
$\left|\beta-\tilde{\beta}\right|\leq\frac{1}{l}\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}$.
Consider a covering set centered at
$C=\left\\{\tilde{\beta}_{1},\dots,\tilde{\beta}_{|C|}\right\\}$ with radius
$\frac{1}{l}\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}$, where $|C|$ is
the size of the set. To ensure
$|\beta-\tilde{\beta}|\leq\frac{1}{l}\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}\leq\frac{1}{l}\beta$,
the minimal size of $C$ could be
$|C|=\frac{l}{2}\left(m^{\frac{1}{2l}}-1\right)$. Therefore, with a union
bound, we have that, with probability larger than $1-\delta$ over $S$, for all
$w$, the bound holds. ∎

For Theorem 3.6, we modify Lemma 3.2 to the form of standard settings and then
we can get the standard generalization bounds on GCN. For Theorem 3.8, similar
to Lemma 4.1, we present the lemma of the change in the output of MPGNN models
and then we can prove the theorem. Additionally, since the activation
functions of MPGNN can be non-homogeneous, we use a different technique to
define the $\beta$ in the proof. The proofs of Theorems 3.6 and 3.8 can be
found in Sections A.3.2 and A.4.2.

##  5 Discussion

In this paper, we present adversarially robust generalization bounds for two
kinds of GNNs, GCN and MPGNN. Our results in adversarial settings complement
the bounds in standard settings. And our results for GCN improve the bounds in
(Liao et al., 2020) by avoiding the dependency on the maximum degree.

Our results are limited to graph classification problem, and can not be
generalized to node classification problem, in which the samples are not
independent. We use Gaussian prior and posterior distributions in the
analysis, while alternative distributions could be considered. Additionally,
in the analysis, we do not consider the optimization algorithm that has an
impact on the leaned parameters. This paper leads to a few interesting
problems for future work: (i) Would the analysis still work for other kinds of
GNNs, or other kinds of networks? (ii) How the optimization algorithms like
SGD impact the generalization of GNNs?

## Acknowledgments

This work was supported in part by the National Key Research and Development
Program of China under grant number 2021YFA1003500. I

## References

  * Anthony & Bartlett (2009) Anthony, M. and Bartlett, P. L.  _Neural network learning: Theoretical foundations_.  Cambridge University Press, 2009.
  * Awasthi et al. (2020) Awasthi, P., Frank, N., and Mohri, M.  Adversarial learning guarantees for linear hypotheses and neural networks.  In _International Conference on Machine Learning_ , pp. 431–441. PMLR, 2020.
  * Bartlett & Mendelson (2002) Bartlett, P. L. and Mendelson, S.  Rademacher and gaussian complexities: Risk bounds and structural results.  _Journal of Machine Learning Research_ , 3(Nov):463–482, 2002.
  * Bartlett et al. (2017) Bartlett, P. L., Foster, D. J., and Telgarsky, M. J.  Spectrally-normalized margin bounds for neural networks.  In _Advances in Neural Information Processing Systems_ , volume 30, 2017.
  * Bojchevski & Günnemann (2019) Bojchevski, A. and Günnemann, S.  Adversarial attacks on node embeddings via graph poisoning.  In _Proceedings of the 36th International Conference on Machine Learning_ , pp. 695–704. PMLR, 2019.
  * Dai et al. (2016) Dai, H., Dai, B., and Song, L.  Discriminative embeddings of latent variable models for structured data.  In _Proceedings of The 33rd International Conference on Machine Learning_ , pp. 2702–2711. PMLR, 2016.
  * Dai et al. (2018) Dai, H., Li, H., Tian, T., Huang, X., Wang, L., Zhu, J., and Song, L.  Adversarial attack on graph structured data.  In _Proceedings of the 35th International Conference on Machine Learning_ , pp. 1115–1124. PMLR, 2018.
  * Du et al. (2019) Du, S. S., Hou, K., Salakhutdinov, R. R., Poczos, B., Wang, R., and Xu, K.  Graph neural tangent kernel: Fusing graph neural networks with graph kernels.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019.
  * Entezari et al. (2020) Entezari, N., Al-Sayouri, S. A., Darvishzadeh, A., and Papalexakis, E. E.  All you need is low (rank) defending against adversarial attacks on graphs.  In _Proceedings of the 13th International Conference on Web Search and Data Mining_ , pp. 169–177, 2020.
  * Esser et al. (2021) Esser, P., Chennuru Vankadara, L., and Ghoshdastidar, D.  Learning theory can (sometimes) explain generalisation in graph neural networks.  In _Advances in Neural Information Processing Systems_ , volume 34, pp. 27043–27056. Curran Associates, Inc., 2021.
  * Farnia et al. (2019) Farnia, F., Zhang, J. M., and Tse, D.  Generalizable adversarial training via spectral normalization.  In _Proceedings of the 7th International Conference on Learning Representations_ , 2019.
  * Gao & Wang (2021) Gao, Q. and Wang, X.  Theoretical investigation of generalization bounds for adversarial learning of deep neural networks.  _Journal of Statistical Theory and Practice_ , 15(2):51, 2021.
  * Garg et al. (2020) Garg, V., Jegelka, S., and Jaakkola, T.  Generalization and representational limits of graph neural networks.  In _Proceedings of the 37th International Conference on Machine Learning_ , pp. 3419–3430. PMLR, 2020.
  * Gilmer et al. (2017) Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E.  Neural message passing for quantum chemistry.  In _International Conference on Machine Learning_ , pp. 1263–1272. PMLR, 2017.
  * Golowich et al. (2018) Golowich, N., Rakhlin, A., and Shamir, O.  Size-independent sample complexity of neural networks.  In _Proceedings of the 31st Conference On Learning Theory_ , pp. 297–299. PMLR, 2018.
  * Goodfellow et al. (2015) Goodfellow, I. J., Shlens, J., and Szegedy, C.  Explaining and harnessing adversarial examples.  In _Proceedings of the 3rd International Conference on Learning Representations_ , 2015.
  * Jacot et al. (2018) Jacot, A., Gabriel, F., and Hongler, C.  Neural tangent kernel: Convergence and generalization in neural networks.  In _Advances in Neural Information Processing Systems_ , volume 31, 2018.
  * Jin et al. (2018) Jin, W., Barzilay, R., and Jaakkola, T.  Junction tree variational autoencoder for molecular graph generation.  In _International Conference on Machine Learning_ , pp. 2323–2332. PMLR, 2018.
  * Jin et al. (2019) Jin, W., Yang, K., Barzilay, R., and Jaakkola, T.  Learning multimodal graph-to-graph translation for molecular optimization.  In _International Conference on Learning Representations_ , 2019.
  * Ju et al. (2023) Ju, H., Li, D., Sharma, A., and Zhang, H. R.  Generalization in graph neural networks: Improved PAC-bayesian bounds on graph diffusion.  In _Proceedings of The 26th International Conference on Artificial Intelligence and Statistics_ , pp. 6314–6341. PMLR, 2023.
  * Khim & Loh (2018) Khim, J. and Loh, P.-L.  Adversarial risk bounds via function transformation.  _arXiv preprint arXiv:1810.09519_ , 2018.
  * Kipf & Welling (2017) Kipf, T. N. and Welling, M.  Semi-supervised classification with graph convolutional networks.  In _International Conference on Learning Representations_ , 2017.
  * Liao et al. (2020) Liao, R., Urtasun, R., and Zemel, R.  A PAC-bayesian approach to generalization bounds for graph neural networks.  In _International Conference on Learning Representations_ , 2020.
  * Liu et al. (2019) Liu, X., Si, S., Zhu, J., Li, Y., and Hsieh, C.-J.  A unified framework for data poisoning attack to graph-based semi-supervised learning.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019.
  * McAllester (2003) McAllester, D.  Simplified PAC-bayesian margin bounds.  In _Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings_ , pp. 203–215. Springer, 2003.
  * Mustafa et al. (2022) Mustafa, W., Lei, Y., and Kloft, M.  On the generalization analysis of adversarial learning.  In _International Conference on Machine Learning_ , pp. 16174–16196. PMLR, 2022.
  * Neyshabur et al. (2015) Neyshabur, B., Tomioka, R., and Srebro, N.  Norm-based capacity control in neural networks.  In _Conference on Learning Theory_ , pp. 1376–1401. PMLR, 2015\.
  * Neyshabur et al. (2017) Neyshabur, B., Bhojanapalli, S., and Srebro, N.  A pac-bayesian approach to spectrally-normalized margin bounds for neural networks.  _arXiv preprint arXiv:1707.09564_ , 2017.
  * Pan et al. (2015) Pan, S., Wu, J., Zhu, X., Zhang, C., and Philip, S. Y.  Joint structure feature exploration and regularization for multi-task graph classification.  _IEEE Transactions on Knowledge and Data Engineering_ , 28(3):715–728, 2015.
  * Pan et al. (2016) Pan, S., Wu, J., Zhu, X., Long, G., and Zhang, C.  Task sensitive feature exploration and learning for multitask graph classification.  _IEEE Transactions on Cybernetics_ , 47(3):744–758, 2016.
  * Raghunathan et al. (2018) Raghunathan, A., Steinhardt, J., and Liang, P.  Certified defenses against adversarial examples.  _arXiv preprint arXiv:1801.09344_ , 2018.
  * Scarselli et al. (2009) Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G.  The graph neural network model.  _IEEE Transactions on Neural Networks_ , 20(1):61–80, 2009.
  * Scarselli et al. (2018) Scarselli, F., Tsoi, A. C., and Hagenbuchner, M.  The vapnik–chervonenkis dimension of graph and recursive neural networks.  _Neural Networks_ , 108:248–259, 2018.
  * Szegedy et al. (2013) Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R.  Intriguing properties of neural networks.  _arXiv preprint arXiv:1312.6199_ , 2013.
  * Tang et al. (2020) Tang, X., Li, Y., Sun, Y., Yao, H., Mitra, P., and Wang, S.  Transferring robustness for graph neural network against poisoning attacks.  In _Proceedings of the 13th International Conference on Web search and Data Mining_ , pp. 600–608, 2020.
  * Tropp (2012) Tropp, J. A.  User-friendly tail bounds for sums of random matrices.  _Foundations of Computational Mathematics_ , 12:389–434, 2012.
  * Verma & Zhang (2019) Verma, S. and Zhang, Z.-L.  Stability and generalization of graph convolutional neural networks.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pp. 1539–1548, 2019.
  * Wu et al. (2019) Wu, H., Wang, C., Tyshetskiy, Y., Docherty, A., Lu, K., and Zhu, L.  Adversarial examples for graph data: deep insights into attack and defense.  In _Proceedings of the 28th International Joint Conference on Artificial Intelligence_ , pp. 4816–4823, 2019.
  * Xiao et al. (2022) Xiao, J., Fan, Y., Sun, R., and Luo, Z.-Q.  Adversarial rademacher complexity of deep neural networks.  _arXiv preprint arXiv:2211.14966_ , 2022.
  * Xiao et al. (2023) Xiao, J., Sun, R., and Luo, Z.-Q.  PAC-bayesian adversarially robust generalization bounds for deep neural networks.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Yin et al. (2019) Yin, D., Kannan, R., and Bartlett, P.  Rademacher complexity for adversarially robust generalization.  In _International Conference on Machine Learning_ , pp. 7085–7094. PMLR, 2019.
  * Ying et al. (2018) Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W., and Leskovec, J.  Hierarchical graph representation learning with differentiable pooling.  In _Advances in Neural Information Processing Systems_ , volume 31, 2018.
  * Zhang et al. (2018) Zhang, M., Cui, Z., Neumann, M., and Chen, Y.  An end-to-end deep learning architecture for graph classification.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Zhang & Zitnik (2020) Zhang, X. and Zitnik, M.  GNNGuard: Defending graph neural networks against adversarial attacks.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 9263–9275. Curran Associates, Inc., 2020.
  * Zhu et al. (2019) Zhu, D., Zhang, Z., Cui, P., and Zhu, W.  Robust graph convolutional networks against adversarial attacks.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pp. 1399–1407, 2019.
  * Zügner et al. (2020) Zügner, D., Borchert, O., Akbarnejad, A., and Günnemann, S.  Adversarial attacks on graph neural networks: Perturbations and their patterns.  _ACM Transactions on Knowledge Discovery from Data (TKDD)_ , 14(5):1–31, 2020.
  * Zügner et al. (2018) Zügner, D., Akbarnejad, A., and Günnemann, S.  Adversarial attacks on neural networks for graph data.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pp. 2847–2856. Association for Computing Machinery, 2018.

##  Appendix A Proofs

###  A.1 Basic Results

######  Proposition A.1.

For any matrix $A\in\mathbb{R}^{n\times m},B\in\mathbb{R}^{m\times p}$, we
have,

$\displaystyle\left\|AB\right\|_{F}\leq\left\|A\right\|_{F}\left\|B\right\|_{2}.$

###### Proof.

Let $x_{i}^{\top},a_{i}^{\top},i\in[n]$ be the $i$-th row of $AB$ and $A$,
respectively, then we have,

$\displaystyle\left\|AB\right\|_{F}^{2}$
$\displaystyle=\sum_{i=1}^{n}\left\|x_{i}^{\top}\right\|_{2}^{2}=\sum_{i=1}^{n}\left\|a_{i}^{\top}B\right\|_{2}^{2}\leq\sum_{i=1}^{n}\left\|a_{i}^{\top}\right\|_{2}^{2}\left\|B\right\|_{2}^{2}=\left\|A\right\|_{F}^{2}\left\|B\right\|_{2}^{2}.\qed$

######  Proposition A.2.

For any undirected graph $G=(V,E)$ with $n$ nodes, let
$A\in\mathbb{R}^{n\times n}$ be the adjacency matrix,
$D=\mathrm{diag}(D_{1},\dots,D_{n})$ be the degree matrix, and
$d=\max_{i\in[n]}\left\\{D_{i}\right\\}$ be the maximum degree, where
$D_{i}=\sum_{j=1}^{n}A_{ij},i\in[n]$. Then we have,

  1. (i)

$\left\|A\right\|_{2}\leq d$;

  2. (ii)

$\left\|\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\right\|_{2}\leq 1$, where
$\tilde{A}=A+I$ and
$\tilde{D}=\mathrm{diag}\left(\tilde{D}_{1},\dots,\tilde{D}_{n}\right)=\mathrm{diag}\left(\sum_{j=1}^{n}\tilde{A}_{ij},i\in[n]\right)$.

###### Proof.

For (i), by the definition of spectral norm, we have

$\displaystyle\left\|A\right\|_{2}=\max_{\left\|x\right\|_{2}=1}x^{\top}Ax=\max_{\left\|x\right\|_{2}=1}\sum_{(i,j)\in
E}x_{i}x_{j}\leq\max_{\left\|x\right\|_{2}=1}\sum_{(i,j)\in
E}\frac{x_{i}^{2}+x_{j}^{2}}{2}\leq\max_{\left\|x\right\|_{2}=1}d\sum_{i\in
V}x_{i}^{2}=d.$

For (ii), let $\tilde{E}=E\cup\\{(i,i)|i\in V\\}$ be the egde set associated
with the adjacency matrix $\tilde{A}$. By the definition of spectral norm, we
have

$\displaystyle\left\|\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\right\|_{2}$
$\displaystyle=\max_{\left\|x\right\|_{2}=1}x^{\top}\left(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\right)x=\max_{\left\|x\right\|_{2}=1}\sum_{(i,j)\in\tilde{E}}\frac{x_{i}x_{j}}{\sqrt{\tilde{D}_{i}\tilde{D}_{j}}}$
$\displaystyle\leq\max_{\left\|x\right\|_{2}=1}\sum_{(i,j)\in\tilde{E}}\left(\frac{x_{i}^{2}}{2\tilde{D}_{i}}+\frac{x_{j}^{2}}{2\tilde{D}_{j}}\right)\leq\max_{\left\|x\right\|_{2}=1}\sum_{i\in
V}x_{i}^{2}=1.\qed$

###  A.2 Results of PAC-Bayesian Analysis

####  A.2.1 Proof of Theorem 3.1

Following (Xiao et al., 2023), we provide the proof for the PAC-Bayesian
results with the robust margin loss. First, we need the following lemma.

######  Lemma A.3.

Let $X$ be a random variable satisfying $\mathbb{P}(X\geq\epsilon)\leq
e^{-2m\epsilon^{2}}$ and $\mathbb{P}(X\leq-\epsilon)\leq e^{-2m\epsilon^{2}}$,
where $m\geq 1$ and $\epsilon>0$, we have

$\displaystyle\mathbb{E}\left[e^{2(m-1)X^{2}}\right]\leq 2m.$

###### Proof.

If $m=1$, the inequality holds trivially. We consider $m>1$. By the definition
of expectatin, we have

$\displaystyle\mathbb{E}\left[e^{2(m-1)X^{2}}\right]$
$\displaystyle=\int_{0}^{\infty}\mathbb{P}\left(e^{2(m-1)X^{2}}\geq
u\right)\mathrm{d}u$
$\displaystyle=\int_{0}^{\infty}\mathbb{P}\left(X^{2}\geq\frac{\log
u}{2(m-1)}\right)\mathrm{d}u$
$\displaystyle=\int_{0}^{\infty}\mathbb{P}\left(X\geq\sqrt{\frac{\log
u}{2(m-1)}}\right)\mathrm{d}u+\int_{0}^{\infty}\mathbb{P}\left(X\leq-\sqrt{\frac{\log
u}{2(m-1)}}\right)\mathrm{d}u.$
$\displaystyle\int_{0}^{\infty}\mathbb{P}\left(X\geq\sqrt{\frac{\log
u}{2(m-1)}}\right)\mathrm{d}u$
$\displaystyle=\int_{0}^{1}\mathbb{P}\left(X\geq\sqrt{\frac{\log
u}{2(m-1)}}\right)\mathrm{d}u+\int_{1}^{\infty}\mathbb{P}\left(X\geq\sqrt{\frac{\log
u}{2(m-1)}}\right)\mathrm{d}u$ $\displaystyle\leq
1+\int_{1}^{\infty}\mathbb{P}\left(X\geq\sqrt{\frac{\log
u}{2(m-1)}}\right)\mathrm{d}u$ $\displaystyle\leq
1+\int_{1}^{\infty}e^{-2m\frac{\log u}{2(m-1)}}\mathrm{d}u$
$\displaystyle=1+\left(-(m-1)u^{-\frac{1}{m-1}}\Big{|}_{1}^{\infty}\right)$
$\displaystyle=m.$

Similarly, we have

$\displaystyle\int_{0}^{\infty}\mathbb{P}\left(X\leq-\sqrt{\frac{\log
u}{2(m-1)}}\right)\mathrm{d}u$ $\displaystyle\leq m.$

Combing the above analysis, we obtain the desired result. ∎

###### Proof of Theorem 3.1.

For any function $u(h)$ defined on $\mathcal{H}$, we have

$\displaystyle\mathbb{E}_{h\sim Q}\left[u(h)\right]$
$\displaystyle=\mathbb{E}_{h\sim Q}\left[\log e^{u(h)}\right]$
$\displaystyle=\mathbb{E}_{h\sim Q}\left[\log
e^{u(h)}+\log\frac{Q}{P}+\log\frac{P}{Q}\right]$
$\displaystyle=KL\left(Q\|P\right)+\mathbb{E}_{h\sim
Q}\left[\log\left(\frac{P}{Q}e^{u(h)}\right)\right]$ $\displaystyle\leq
KL\left(Q\|P\right)+\log\mathbb{E}_{h\sim
Q}\left[\frac{P}{Q}e^{u(h)}\right]\qquad(\mbox{Jensen's inequality})$
$\displaystyle=KL\left(Q\|P\right)+\log\mathbb{E}_{h\sim
P}\left[e^{u(h)}\right].$

For $h\in\mathcal{H}$, denote
$\Delta(h)=R_{\mathcal{D},\gamma}\left(h\right)-\hat{R}_{S,\gamma}\left(h\right)$
and $u(h)=2(m-1)\Delta(h)^{2}$. We have

$\displaystyle 2(m-1)\left[\mathbb{E}_{h\sim
Q}\left[\Delta(h)\right]\right]^{2}$ $\displaystyle\leq
2(m-1)\mathbb{E}_{h\sim Q}\left[\Delta(h)^{2}\right]\qquad(\mbox{Jensen's
inequality})$ $\displaystyle\leq KL\left(Q\|P\right)+\log\mathbb{E}_{h\sim
P}\left[e^{2(m-1)\Delta(h)^{2}}\right].$ (3)

Since $R_{\mathcal{D},\gamma}\left(h\right)\in[0,1]$, based on Hoeffding’s
inequality, for any $\epsilon>0$, we have

$\displaystyle\mathbb{P}_{S}\left(\Delta(h)\geq\epsilon\right)\leq
e^{-2m\epsilon^{2}},$
$\displaystyle\mathbb{P}_{S}\left(\Delta(h)\leq-\epsilon\right)\leq
e^{-2m\epsilon^{2}}.$

Hence, based on Lemma A.3, we have

$\displaystyle\mathbb{E}_{S}\left[e^{2(m-1)\Delta(h)^{2}}\right]\leq 2m\ $
$\displaystyle\Rightarrow\ \mathbb{E}_{h\sim
P}\left[\mathbb{E}_{S}\left[e^{2(m-1)\Delta(h)^{2}}\right]\right]\leq 2m$
$\displaystyle\Leftrightarrow\ \mathbb{E}_{S}\left[\mathbb{E}_{h\sim
P}\left[e^{2(m-1)\Delta(h)^{2}}\right]\right]\leq 2m.$

Based on Markov’s inequality, we have

$\displaystyle\mathbb{P}_{S}\left(\mathbb{E}_{h\sim
P}\left[e^{2(m-1)\Delta(h)^{2}}\right]\geq\frac{2m}{\delta}\right)\leq\frac{\delta\mathbb{E}_{S}\left[\mathbb{E}_{h\sim
P}\left[e^{2(m-1)\Delta(h)^{2}}\right]\right]}{2m}\leq\delta.$ (4)

Combining Equations 3 and 4, we have that with probability at least $1-\delta$
over $S$,

$\displaystyle
R_{\mathcal{D},\gamma}\left(Q\right)-\hat{R}_{S,\gamma}\left(Q\right)$
$\displaystyle=\mathbb{E}_{h\sim
Q}\left[R_{\mathcal{D},\gamma}\left(h\right)-\hat{R}_{S,\gamma}\left(h\right)\right]$
$\displaystyle\leq\sqrt{\frac{KL\left(Q\|P\right)+\log\mathbb{E}_{h\sim
P}\left[e^{2(m-1)\Delta(h)^{2}}\right]}{2(m-1)}}$
$\displaystyle\leq\sqrt{\frac{KL\left(Q\|P\right)+\log(2m/\delta)}{2(m-1)}}.\qed$

####  A.2.2 Proof of Lemma 3.2

###### Proof of Lemma 3.2.

For any $w$ and random perturbation $\Delta w$, let $w^{\prime}=w+\Delta w$.
Let

$\displaystyle\mathcal{S}_{w}=\left\\{w^{\prime}\mid\max_{i,j\in[k],\atop
G\in\mathcal{X}\times\mathcal{G}}\left|RM\left(f_{w^{\prime}}\left(G\right),i,j\right)-RM\left(f_{w}\left(G\right),i,j\right)\right|\leq\frac{\gamma}{2}\right\\}.$

Let $q$ be the probability density function over the parameters $w^{\prime}$.
We construct a new distribution $\tilde{Q}$ over predictors $f_{\tilde{w}}$,
where $\tilde{w}$ is restricted to $S_{w}$ with the probability density
function

$\displaystyle\tilde{q}(\tilde{w})=\frac{1}{Z}\begin{cases}q(\tilde{w}),&\tilde{w}\in
S_{w},\\\ 0,&\tilde{w}\in S_{w}^{c}.\end{cases}$

Here $Z=\mathbb{P}\left\\{w^{\prime}\in S_{w}\right\\}\geq\frac{1}{2}$ and
$S_{w}^{c}$ is the complement set of $S_{w}$. By the definition of
$\tilde{Q}$, for $\tilde{w}\sim\tilde{Q}$, we have

$\displaystyle\max_{i,j\in[k],\atop
G\in\mathcal{X}\times\mathcal{G}}\left|RM\left(f_{\tilde{w}}\left(G\right),i,j\right)-RM\left(f_{w}\left(G\right),i,j\right)\right|\leq\frac{\gamma}{2}.$
(5)

Recall that

$\displaystyle R_{\mathcal{D},0}\left(f_{w}\right)$
$\displaystyle=\mathbb{P}_{(G,y)\sim\mathcal{D}}\left\\{RM\left(f_{w}\left(G\right),y\right)\leq
0\right\\},$

and

$\displaystyle R_{\mathcal{D},\frac{\gamma}{2}}\left(f_{\tilde{w}}\right)$
$\displaystyle=\mathbb{P}_{(G,y)\sim\mathcal{D}}\left\\{RM\left(f_{\tilde{w}}\left(G\right),y\right)\leq\frac{\gamma}{2}\right\\}.$

From Equation 5, we have

$\displaystyle RM\left(f_{\tilde{w}}\left(G\right),y,j\right)\leq
RM\left(f_{w}\left(G\right),y,j\right)+\frac{\gamma}{2}.$

Then, by the definition of robust margin operator, we have

$\displaystyle RM\left(f_{\tilde{w}}\left(G\right),y\right)$
$\displaystyle=\inf_{G^{\prime}\in\delta_{\tilde{w}}(G)}\left(f_{\tilde{w}}\left(G^{\prime}\right)_{y}-\max_{j\neq
y}f_{\tilde{w}}\left(G^{\prime}\right)_{j}\right)$
$\displaystyle=\inf_{G^{\prime}\in\delta_{\tilde{w}}(G)}\inf_{j\neq
y}\left(f_{\tilde{w}}\left(G^{\prime}\right)_{y}-f_{\tilde{w}}\left(G^{\prime}\right)_{j}\right)$
$\displaystyle=\inf_{j\neq
y}\inf_{G^{\prime}\in\delta_{\tilde{w}}(G)}\left(f_{\tilde{w}}\left(G^{\prime}\right)_{y}-f_{\tilde{w}}\left(G^{\prime}\right)_{j}\right)$
$\displaystyle=\inf_{j\neq y}RM\left(f_{\tilde{w}}\left(G\right),y,j\right)$
$\displaystyle\leq\inf_{j\neq
y}RM\left(f_{w}\left(G\right),y,j\right)+\frac{\gamma}{2}$
$\displaystyle=RM\left(f_{w}\left(G\right),y\right)+\frac{\gamma}{2}.$

Therefore, we have

$\displaystyle RM\left(f_{w}\left(G\right),y\right)\leq 0\ \Rightarrow\
RM\left(f_{\tilde{w}}\left(G\right),y\right)\leq\frac{\gamma}{2}.$

Since it holds for any sample
$(G,y)\in\mathcal{X}\times\mathcal{G}\times\mathcal{Y}$, we can get

$\displaystyle R_{\mathcal{D},0}\left(f_{w}\right)\leq
R_{\mathcal{D},\frac{\gamma}{2}}\left(f_{\tilde{w}}\right).$ (6)

Similarly, recall that

$\displaystyle\hat{R}_{S,\frac{\gamma}{2}}\left(f_{w}\right)=\frac{1}{m}\sum_{(G,y)\in
S}\mathbbm{1}\left\\{RM\left(f_{\tilde{w}}\left(G\right),y\right)\leq\frac{\gamma}{2}\right\\},$

and

$\displaystyle\hat{R}_{S,\gamma}\left(f_{w}\right)=\frac{1}{m}\sum_{(G,y)\in
S}\mathbbm{1}\left\\{RM\left(f_{w}\left(G\right),y\right)\leq\gamma\right\\}.$

From Equation 5, we have

$\displaystyle RM\left(f_{w}\left(G\right),y,j\right)\leq
RM\left(f_{\tilde{w}}\left(G\right),y,j\right)+\frac{\gamma}{2}.$

Then, by the definition of robust margin operator, we have

$\displaystyle RM\left(f_{w}\left(G\right),y\right)$
$\displaystyle=\inf_{G^{\prime}\in\delta_{w}(G)}\left(f_{w}\left(G^{\prime}\right)_{y}-\max_{j\neq
y}f_{w}\left(G^{\prime}\right)_{j}\right)$
$\displaystyle=\inf_{G^{\prime}\in\delta_{w}(G)}\inf_{j\neq
y}\left(f_{w}\left(G^{\prime}\right)_{y}-f_{w}\left(G^{\prime}\right)_{j}\right)$
$\displaystyle=\inf_{j\neq
y}\inf_{G^{\prime}\in\delta_{w}(G)}\left(f_{w}\left(G^{\prime}\right)_{y}-f_{w}\left(G^{\prime}\right)_{j}\right)$
$\displaystyle=\inf_{j\neq y}RM\left(f_{w}\left(G\right),y,j\right)$
$\displaystyle\leq\inf_{j\neq
y}RM\left(f_{\tilde{w}}\left(G\right),y,j\right)+\frac{\gamma}{2}$
$\displaystyle=RM\left(f_{\tilde{w}}\left(G\right),y\right)+\frac{\gamma}{2}.$

Therefore, we have

$\displaystyle
RM\left(f_{\tilde{w}}\left(G\right),y\right)\leq\frac{\gamma}{2}\ \Rightarrow\
RM\left(f_{w}\left(G\right),y\right)\leq\gamma,$

which indicates that

$\displaystyle\mathbbm{1}\left\\{RM\left(f_{\tilde{w}}\left(G\right),y\right)\leq\frac{\gamma}{2}\right\\}\leq\mathbbm{1}\left\\{RM\left(f_{w}\left(G\right),y\right)\leq\gamma\right\\}.$

Since it holds for any sample
$(G,y)\in\mathcal{X}\times\mathcal{G}\times\mathcal{Y}$, we can get

$\displaystyle\hat{R}_{S,\frac{\gamma}{2}}\left(f_{\tilde{w}}\right)\leq\hat{R}_{S,\gamma}\left(f_{w}\right).$
(7)

Now, with probability at least $1-\delta$ over the choice of a training set
$S=\\{z_{1},\dots,z_{m}\\}$ independently sampled from $\mathcal{D}$, we have,

$\displaystyle R_{\mathcal{D},0}\left(f_{w}\right)$
$\displaystyle\leq\mathbb{E}_{\tilde{w}}\left[R_{\mathcal{D},\frac{\gamma}{2}}\left(f_{\tilde{w}}\right)\right]$
$\displaystyle(\mbox{\lx@cref{creftype~refnum}{eq:ppf-bound-lm-2}})$
$\displaystyle\leq\mathbb{E}_{\tilde{w}}\left[\hat{R}_{S,\frac{\gamma}{2}}\left(f_{\tilde{w}}\right)\right]+\sqrt{\frac{KL(\tilde{Q}\|P)+\log(2m/\delta)}{2(m-1)}}$
$\displaystyle(\mbox{\lx@cref{creftype~refnum}{thm:mcallester}})$
$\displaystyle\leq\hat{R}_{S,\gamma}\left(f_{w}\right)+\sqrt{\frac{KL(\tilde{Q}\|P)+\log(2m/\delta)}{2(m-1)}}.$
$\displaystyle(\mbox{\lx@cref{creftype~refnum}{eq:ppf-bound-lm-3}})$

Note that

$\displaystyle KL\left(Q\|P\right)$ $\displaystyle=\int_{\tilde{w}\in
S_{w}}Q\log\frac{Q}{P}d\tilde{w}+\int_{\tilde{w}\in
S_{w}^{c}}Q\log\frac{Q}{P}d\tilde{w}$ $\displaystyle=\int_{\tilde{w}\in
S_{w}}\frac{QZ}{Z}\log\frac{QZ}{PZ}d\tilde{w}+\int_{\tilde{w}\in
S_{w}^{c}}\frac{Q(1-Z)}{1-Z}\log\frac{Q(1-Z)}{P(1-Z)}d\tilde{w}$
$\displaystyle=Z\int_{\tilde{w}\in
S_{w}}\frac{Q}{Z}\log\frac{Q}{ZP}d\tilde{w}+\int_{\tilde{w}\in S_{w}}Q\log
Zd\tilde{w}$ $\displaystyle\ \ +(1-Z)\int_{\tilde{w}\in
S_{w}^{c}}\frac{Q}{1-Z}\log\frac{Q}{(1-Z)P}d\tilde{w}+\int_{\tilde{w}\in
S_{w}^{c}}Q\log(1-Z)d\tilde{w}$
$\displaystyle=ZKL\left(\tilde{Q}\|P\right)+(1-Z)KL\left(\bar{Q}\|P\right)-H(Z),$

where $\bar{Q}=\frac{Q}{1-Z}$ and $H(Z)=-Z\log Z-(1-Z)\log(1-Z)$. Since $H(z)$
is nonincreasing on $[\frac{1}{2},1)$, we have $0\leq H(Z)\leq\log(2)$. Since
KL is always positive, we have

$\displaystyle KL\left(\tilde{Q}\|P\right)$
$\displaystyle=\frac{1}{Z}\left[KL\left(Q\|P\right)-(1-Z)KL\left(\bar{Q}\|P\right)+H(Z)\right]$
$\displaystyle\leq 2KL\left(Q\|P\right)+2\log(2).$

Hence, with probability at least $1-\delta$ over the choice of a training set
$S=\\{z_{1},\dots,z_{m}\\}$ independently sampled from $\mathcal{D}$,

$\displaystyle R_{\mathcal{D},0}\left(f_{w}\right)$
$\displaystyle\leq\hat{R}_{S,\gamma}\left(f_{{w}}\right)+\sqrt{\frac{KL(\tilde{Q}\|P)+\log(2m/\delta)}{2(m-1)}}$
$\displaystyle\leq\hat{R}_{S,\gamma}\left(f_{{w}}\right)+\sqrt{\frac{2KL\left(Q\|P\right)+2\log
2+\log(2m/\delta)}{2(m-1)}}$
$\displaystyle=\hat{R}_{S,\gamma}\left(f_{{w}}\right)+\sqrt{\frac{2KL\left(Q\|P\right)+\log(8m/\delta)}{2(m-1)}}.\qed$

###  A.3 Results of GCN

####  A.3.1 Proof of Perturbation Bound for GCN

###### Proof of Lemma 4.1.

We denote the node representation in $j$-th ($j\leq l$) layer as

$\displaystyle f_{w}^{j}(G)=H_{j}=\sigma_{j}\left(P_{G}H_{j-1}W_{j}\right),\
j\in[l-1],$ $\displaystyle
f_{w}^{l}(G)=H_{l}=\frac{1}{n}\bm{1}_{n}H_{l-1}W_{l}.$

Adding perturbation $\Delta w$ to the parameter $w$, that is, for the $j$-th
($j\leq l$) layer, the perturbed parameters are $W_{j}+\Delta W_{j}$ and
denote $H_{j}^{\prime}=f_{w+\Delta w}^{j}(G),j\in[l]$.

Upper Bound on the Node Representation. For any $j<l$,

$\displaystyle\left\|H_{j}\right\|_{F}$
$\displaystyle=\left\|\sigma_{j}\left(P_{G}H_{j-1}W_{j}\right)\right\|_{F}$
$\displaystyle\leq\left\|P_{G}H_{j-1}W_{j}\right\|_{F}$
$\displaystyle\leq\left\|P_{G}H_{j-1}\right\|_{F}\left\|W_{j}\right\|_{2}$
$\displaystyle\leq\left\|P_{G}\right\|_{2}\left\|H_{j-1}\right\|_{F}\left\|W_{j}\right\|_{2},$

where the first inequality holds since $\sigma_{j}$ is 1-Lipschitz and
$\sigma_{j}(0)=0$, and the second and the last ones hold by Proposition A.1.
Then, using the relationship iteratively and $H_{0}=X$, we have

$\displaystyle\left\|H_{j}\right\|_{F}$
$\displaystyle\leq\left\|P_{G}\right\|_{2}^{j}\left\|H_{0}\right\|_{F}\prod_{i=1}^{j}\left\|W_{i}\right\|_{2}$
$\displaystyle\leq\left\|X\right\|_{F}\left\|P_{G}\right\|_{2}^{j}\prod_{i=1}^{j}\left\|W_{i}\right\|_{2}.$
(8)

Upper Bound on the Change of Node Representation. For any $j<l$,

$\displaystyle\left\|H_{j}^{\prime}-H_{j}\right\|_{F}$
$\displaystyle=\left\|\sigma_{j}\left(P_{G}H_{j-1}^{\prime}(W_{j}+\Delta
W_{j})\right)-\sigma_{j}\left(P_{G}H_{j-1}W_{j}\right)\right\|_{F}$
$\displaystyle\leq\left\|P_{G}H_{j-1}^{\prime}(W_{j}+\Delta
W_{j})-P_{G}H_{j-1}W_{j}\right\|_{F}$
$\displaystyle=\left\|P_{G}\left(H_{j-1}^{\prime}-H_{j-1}\right)(W_{j}+\Delta
W_{j})+P_{G}H_{j-1}\Delta W_{j}\right\|_{F}$
$\displaystyle\leq\left\|P_{G}\left(H_{j-1}^{\prime}-H_{j-1}\right)(W_{j}+\Delta
W_{j})\right\|_{F}+\left\|P_{G}H_{j-1}\Delta W_{j}\right\|_{F}$
$\displaystyle\leq\left\|P_{G}\right\|_{2}\left\|H_{j-1}^{\prime}-H_{j-1}\right\|_{F}\left\|W_{j}+\Delta
W_{j}\right\|_{2}+\left\|P_{G}\right\|_{2}\left\|H_{j-1}\right\|_{F}\left\|\Delta
W_{j}\right\|_{2},$ (9)

where the first inequality holds since $\sigma_{j}$ is 1-Lipschitz and
$\sigma_{j}(0)=0$, and the last one holds by Proposition A.1. Simplify the
notations in Equation 9 as $\left\|H_{j}^{\prime}-H_{j}\right\|_{F}\leq
a_{j-1}\left\|H_{j-1}^{\prime}-H_{j-1}\right\|_{F}+b_{j-1}$ where
$a_{j-1}=\left\|P_{G}\right\|_{2}\left\|W_{j}+\Delta W_{j}\right\|_{2}$ and
$b_{j-1}=\left\|P_{G}\right\|_{2}\left\|H_{j-1}\right\|_{F}\left\|\Delta
W_{j}\right\|_{2}$. With $H_{0}^{\prime}-H_{0}=X-X=0$, we have,

$\displaystyle\left\|H_{j}^{\prime}-H_{j}\right\|_{F}$
$\displaystyle\leq\sum_{k=0}^{j-1}b_{k}\left(\prod_{i=k+1}^{j-1}a_{i}\right)$
$\displaystyle=\sum_{k=0}^{j-1}\left\|P_{G}\right\|_{2}\left\|H_{k}\right\|_{F}\left\|\Delta
W_{k+1}\right\|_{2}\left(\prod_{i=k+1}^{j-1}\left\|P_{G}\right\|_{2}\left\|W_{i+1}+\Delta
W_{i+1}\right\|_{2}\right)$
$\displaystyle=\sum_{k=0}^{j-1}\left\|P_{G}\right\|_{2}^{j-k}\left\|H_{k}\right\|_{F}\left\|\Delta
W_{k+1}\right\|_{2}\left(\prod_{i=k+2}^{j}\left\|W_{i}+\Delta
W_{i}\right\|_{2}\right).$

With Equation 8, we have

$\displaystyle\left\|H_{j}^{\prime}-H_{j}\right\|_{F}$
$\displaystyle\leq\sum_{k=0}^{j-1}\left\|P_{G}\right\|_{2}^{j-k}\left(\left\|P_{G}\right\|_{2}^{k}\left\|X\right\|_{F}\prod_{i=1}^{k}\left\|W_{i}\right\|_{2}\right)\left\|\Delta
W_{k+1}\right\|_{2}\left(\prod_{i=k+2}^{j}\left\|W_{i}+\Delta
W_{i}\right\|_{2}\right)$
$\displaystyle\leq\left\|X\right\|_{F}\sum_{k=0}^{j-1}\left\|P_{G}\right\|_{2}^{j}\left(\prod_{i=1}^{k}\left\|W_{i}\right\|_{2}\right)\left\|\Delta
W_{k+1}\right\|_{2}\left(\prod_{i=k+2}^{j}\left(1+\frac{1}{l}\right)\left\|W_{i}\right\|_{2}\right)$
$\displaystyle=\left\|X\right\|_{F}\sum_{k=0}^{j-1}\left\|P_{G}\right\|_{2}^{j}\left(\prod_{i=1}^{k+1}\left\|W_{i}\right\|_{2}\right)\frac{\left\|\Delta
W_{k+1}\right\|_{2}}{\left\|W_{k+1}\right\|_{2}}\left(\prod_{i=k+2}^{j}\left(1+\frac{1}{l}\right)\left\|W_{i}\right\|_{2}\right)$
$\displaystyle=\left\|X\right\|_{F}\left\|P_{G}\right\|_{2}^{j}\left(\prod_{i=1}^{j}\left\|W_{i}\right\|_{2}\right)\sum_{k=0}^{j-1}\frac{\left\|\Delta
W_{k+1}\right\|_{2}}{\left\|W_{k+1}\right\|_{2}}\left(1+\frac{1}{l}\right)^{j-k-1}$
$\displaystyle=\left\|X\right\|_{F}\left\|P_{G}\right\|_{2}^{j}\left(\prod_{i=1}^{j}\left\|W_{i}\right\|_{2}\right)\sum_{k=1}^{j}\frac{\left\|\Delta
W_{k}\right\|_{2}}{\left\|W_{k}\right\|_{2}}\left(1+\frac{1}{l}\right)^{j-k},$
(10)

where the last inequality holds since $\left\|W_{i}+\Delta
W_{i}\right\|_{2}\leq\left\|W_{i}\right\|_{2}+\left\|\Delta
W_{i}\right\|_{2}\leq\left(1+\frac{1}{l}\right)\left\|W_{i}\right\|_{2}$ by
the assumption that $\left\|\Delta
W_{i}\right\|_{2}\leq\frac{1}{l}\left\|W_{i}\right\|_{2}$.

Final Bound on the Readout Layer.

$\displaystyle\left\|H_{l}^{\prime}-H_{l}\right\|_{2}$
$\displaystyle=\left\|\frac{1}{n}\bm{1}_{n}H_{l-1}^{\prime}(W_{l}+\Delta
W_{l})-\frac{1}{n}\bm{1}_{n}H_{l-1}W_{l}\right\|_{2}$
$\displaystyle=\left\|\frac{1}{n}\bm{1}_{n}\left(H_{l-1}^{\prime}-H_{l-1}\right)(W_{l}+\Delta
W_{l})+\frac{1}{n}\bm{1}_{n}H_{l-1}\Delta W_{l}\right\|_{2}$
$\displaystyle\leq\left\|\frac{1}{n}\bm{1}_{n}\left(H_{l-1}^{\prime}-H_{l-1}\right)(W_{l}+\Delta
W_{l})\right\|_{2}+\left\|\frac{1}{n}\bm{1}_{n}H_{l-1}\Delta
W_{l}\right\|_{2}$
$\displaystyle\leq\left\|\frac{1}{n}\bm{1}_{n}\right\|_{2}\left\|\left(H_{l-1}^{\prime}-H_{l-1}\right)\left(W_{l}+\Delta
W_{l}\right)\right\|_{2}+\left\|\frac{1}{n}\bm{1}_{n}\right\|_{2}\left\|H_{l-1}\Delta
W_{l}\right\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{n}}\left\|H_{l-1}^{\prime}-H_{l-1}\right\|_{F}\left\|W_{l}+\Delta
W_{l}\right\|_{2}+\frac{1}{\sqrt{n}}\left\|H_{l-1}\right\|_{F}\left\|\Delta
W_{l}\right\|_{2}.$

Using Equations 8 and 10, we have

$\displaystyle\left\|H_{l}^{\prime}-H_{l}\right\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{n}}\left\|W_{l}+\Delta
W_{l}\right\|_{2}\left\|X\right\|_{F}\left\|P_{G}\right\|_{2}^{l-1}\left(\prod_{i=1}^{l-1}\left\|W_{i}\right\|_{2}\right)\sum_{k=1}^{l-1}\frac{\left\|\Delta
W_{k}\right\|_{2}}{\left\|W_{k}\right\|_{2}}\left(1+\frac{1}{l}\right)^{l-k-1}$
$\displaystyle\quad+\frac{1}{\sqrt{n}}\left\|\Delta
W_{l}\right\|_{2}\left\|P_{G}\right\|_{2}^{l-1}\left\|X\right\|_{F}\prod_{i=1}^{l-1}\left\|W_{i}\right\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{n}}\left\|X\right\|_{F}\left\|P_{G}\right\|_{2}^{l-1}\left[\left\|W_{l}+\Delta
W_{l}\right\|_{2}\left(\prod_{i=1}^{l-1}\left\|W_{i}\right\|_{2}\right)\sum_{k=1}^{l-1}\frac{\left\|\Delta
W_{k}\right\|_{2}}{\left\|W_{k}\right\|_{2}}\left(1+\frac{1}{l}\right)^{l-k-1}+\left\|\Delta
W_{l}\right\|_{2}\prod_{i=1}^{l-1}\left\|W_{i}\right\|_{2}\right]$
$\displaystyle=\frac{1}{\sqrt{n}}\left\|X\right\|_{F}\left\|P_{G}\right\|_{2}^{l-1}\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)\left[\frac{\left\|W_{l}+\Delta
W_{l}\right\|_{2}}{\left\|W_{l}\right\|_{2}}\sum_{k=1}^{l-1}\frac{\left\|\Delta
W_{k}\right\|_{2}}{\left\|W_{k}\right\|_{2}}\left(1+\frac{1}{l}\right)^{l-k-1}+\frac{\left\|\Delta
W_{l}\right\|_{2}}{\left\|W_{l}\right\|_{2}}\right]$
$\displaystyle\leq\frac{1}{\sqrt{n}}\left\|X\right\|_{F}\left\|P_{G}\right\|_{2}^{l-1}\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)\left[\left(1+\frac{1}{l}\right)\sum_{k=1}^{l-1}\frac{\left\|\Delta
W_{k}\right\|_{2}}{\left\|W_{k}\right\|_{2}}\left(1+\frac{1}{l}\right)^{l-k-1}+\frac{\left\|\Delta
W_{l}\right\|_{2}}{\left\|W_{l}\right\|_{2}}\right]$
$\displaystyle=\frac{1}{\sqrt{n}}\left\|X\right\|_{F}\left\|P_{G}\right\|_{2}^{l-1}\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)\left(1+\frac{1}{l}\right)^{l}\left[\sum_{k=1}^{l-1}\frac{\left\|\Delta
W_{k}\right\|_{2}}{\left\|W_{k}\right\|_{2}}\left(1+\frac{1}{l}\right)^{-k}+\frac{\left\|\Delta
W_{l}\right\|_{2}}{\left\|W_{l}\right\|_{2}}\left(1+\frac{1}{l}\right)^{-l}\right]$
$\displaystyle\leq\frac{e}{\sqrt{n}}\left\|X\right\|_{F}\left\|P_{G}\right\|_{2}^{l-1}\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)\sum_{k=1}^{l}\frac{\left\|\Delta
W_{k}\right\|_{2}}{\left\|W_{k}\right\|_{2}},$

where the last inequality holds since $1\leq\left(1+\frac{1}{l}\right)^{l}\leq
e$. ∎

Then we present the following lemma which contains the results of Lemma 4.1 in
adversarial settings and the results in the standard settings.

######  Lemma A.4.

Under Assumptions 3.3 and 3.4, for any $w$ and any perturbation $\Delta
w=vec\left(\left\\{\Delta W_{i}\right\\}_{i=1}^{l}\right)$ such that for all
$i\in[l]$, $\left\|\Delta
W_{i}\right\|_{2}\leq\frac{1}{l}\left\|W_{i}\right\|_{2}$, the change in the
margin operator is bounded as

$\displaystyle\left|M\left(f_{w+\Delta
w}\left(G\right),i,j\right)-M\left(f_{w}\left(G\right),i,j\right)\right|\leq
2eB\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)\sum_{i=1}^{l}\frac{\left\|\Delta
W_{i}\right\|_{2}}{\left\|W_{i}\right\|_{2}}.$

Further, consider the $\epsilon$-attack ($\epsilon>0$), the change in the
robust margin operator is bounded as

$\displaystyle\left|RM\left(f_{w+\Delta
w}\left(G\right),i,j\right)-RM\left(f_{w}\left(G\right),i,j\right)\right|\leq
2e(B+\epsilon)\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)\sum_{i=1}^{l}\frac{\left\|\Delta
W_{i}\right\|_{2}}{\left\|W_{i}\right\|_{2}}.$

###### Proof.

For any $i,j\in[K]$, by the definition of margin operator, we have

$\displaystyle\left|M\left(f_{w+\Delta
w}\left(G\right),i,j\right)-M\left(f_{w}\left(G\right),i,j\right)\right|$
$\displaystyle\leq\left|f_{w+\Delta
w}\left(G\right)_{i}-f_{w}\left(G\right)_{i}\right|+\left|f_{w+\Delta
w}\left(G\right)_{j}-f_{w}\left(G\right)_{j}\right|$ $\displaystyle\leq
2\left\|f_{w+\Delta w}\left(G\right)-f_{w}\left(G\right)\right\|_{2}.$

By Propositions A.2 and 4.1, we have

$\displaystyle\left|M\left(f_{w+\Delta
w}\left(G\right),i,j\right)-M\left(f_{w}\left(G\right),i,j\right)\right|$
$\displaystyle\leq
2e\left\|X\right\|_{2}\left\|P_{G}\right\|_{2}^{l-1}\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)\sum_{i=1}^{l}\frac{\left\|\Delta
W_{i}\right\|_{2}}{\left\|W_{i}\right\|_{2}}$ $\displaystyle\leq
2eB\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)\sum_{i=1}^{l}\frac{\left\|\Delta
W_{i}\right\|_{2}}{\left\|W_{i}\right\|_{2}}.$

Further, let

$\displaystyle G(w)$
$\displaystyle=\mathop{\arg\inf}_{G^{\prime}\in\delta_{w}(G)}\left(f_{w}\left(G^{\prime}\right)_{i}-f_{w}\left(G^{\prime}\right)_{j}\right)=\mathop{\arg\inf}_{G^{\prime}\in\delta_{w}(G)}M\left(f_{w}\left(G^{\prime}\right),i,j\right),$

and $X(w)$ is the corresponding node features matrix. Denoting
$\tilde{w}=w+\Delta w$, we have

$\displaystyle\left|RM\left(f_{\tilde{w}}\left(G\right),i,j\right)-RM\left(f_{w}\left(G\right),i,j\right)\right|$
$\displaystyle=\left|\inf_{G^{\prime}\in\delta_{\tilde{w}}(G)}M\left(f_{\tilde{w}}\left(G^{\prime}\right),i,j\right)-\inf_{G^{\prime}\in\delta_{w}(G)}M\left(f_{w}\left(G^{\prime}\right),i,j\right)\right|$
$\displaystyle=\left|M\left(f_{\tilde{w}}\left(G(\tilde{w})\right),i,j\right)-M\left(f_{w}\left(G(w)\right),i,j\right)\right|$
$\displaystyle\leq\max\left\\{\left|M\left(f_{\tilde{w}}\left(G(\tilde{w})\right),i,j\right)-M\left(f_{w}\left(G(\tilde{w})\right),i,j\right)\right|,\right.$
$\displaystyle\qquad\qquad\left.\left|M\left(f_{\tilde{w}}\left(G(w)\right),i,j\right)-M\left(f_{w}\left(G(w)\right),i,j\right)\right|\right\\}$
$\displaystyle\leq
2e\max\left\\{\left\|X(\tilde{w})\right\|_{2},\left\|X(w)\right\|_{2}\right\\}\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)\sum_{i=1}^{l}\frac{\left\|\Delta
W_{i}\right\|_{2}}{\left\|W_{i}\right\|_{2}}$ $\displaystyle\leq
2e(B+\epsilon)\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)\sum_{i=1}^{l}\frac{\left\|\Delta
W_{i}\right\|_{2}}{\left\|W_{i}\right\|_{2}},$

where the first inequality holds since, by the definition of $G(w)$,

$\displaystyle
M\left(f_{\tilde{w}}\left(G(\tilde{w})\right),i,j\right)-M\left(f_{w}\left(G(w)\right),i,j\right)\leq
M\left(f_{\tilde{w}}\left(G(w)\right),i,j\right)-M\left(f_{w}\left(G(w)\right),i,j\right),$
$\displaystyle
M\left(f_{w}\left(G(w)\right),i,j\right)-M\left(f_{\tilde{w}}\left(G(\tilde{w})\right),i,j\right)\leq
M\left(f_{w}\left(G(\tilde{w})\right),i,j\right)-M\left(f_{\tilde{w}}\left(G(\tilde{w})\right),i,j\right),$

and the last inequality holds from Assumption 3.3 and the definition of
$\epsilon$-attack. ∎

####  A.3.2 Proof of Generalization bounds for GCN

We prove Theorem 3.7 and the proof of Theorem 3.6 is similar by replacing the
adversarial settings with the standard settings.

###### Proof of Theorem 3.7.

Let $\beta=\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)^{1/l}$. We
normalize the weights as
$\tilde{W}_{i}=\frac{\beta}{\left\|W_{i}\right\|_{2}}W_{i}$. Due to the
homogeneity of ReLU, we have $f_{w}=f_{\tilde{w}}$. We can also verify that
$\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}=\prod_{i=1}^{l}\left\|\tilde{W}_{i}\right\|_{2}$
and
$\frac{\left\|W_{i}\right\|_{F}}{\left\|W_{i}\right\|_{2}}=\frac{\left\|\tilde{W}_{i}\right\|_{F}}{\left\|\tilde{W}_{i}\right\|_{2}}$,
i.e., the terms appear in the bound stay the same after applying the
normalization. Therefore, without loss of generality, we assume that the norm
is equal across layers, i.e., $\forall i,\left\|W_{i}\right\|_{2}=\beta$.

Consider the prior distribution $P=\mathcal{N}(0,\sigma^{2}I)$ and the random
perturbation $\Delta w\sim\mathcal{N}(0,\sigma^{2}I)$. Note that the $\sigma$
of the prior and the perturbation distributions are the same and will be set
according to $\beta$. More precisely, we will set the $\sigma$ based on some
approximation $\tilde{\beta}$ of $\beta$ since the prior distribution $P$ can
not depend on any learned weights directly. The approximation $\tilde{\beta}$
is chosen from a covering set which covers the meaningful range of $\beta$.
For now, let us assume that we have a fixed $\tilde{\beta}$ and consider
$\beta$ which satisfies $|\beta-\tilde{\beta}|\leq\frac{1}{l}\beta$. Note that

$\displaystyle|\beta-\tilde{\beta}|\leq\frac{1}{l}\beta$
$\displaystyle\Rightarrow\left(1-\frac{1}{l}\right)\beta\leq\tilde{\beta}\leq\left(1+\frac{1}{l}\right)\beta$
$\displaystyle\Rightarrow\left(1-\frac{1}{l}\right)^{l-1}\beta^{l-1}\leq\tilde{\beta}^{l-1}\leq\left(1+\frac{1}{l}\right)^{l-1}\beta^{l-1}$
$\displaystyle\Rightarrow\left(1-\frac{1}{l}\right)^{l-1}\beta^{l-1}\leq\tilde{\beta}^{l-1}\leq\left(1+\frac{1}{l}\right)^{l}\beta^{l-1}$
$\displaystyle\Rightarrow\frac{1}{e}\beta^{l-1}\leq\tilde{\beta}^{l-1}\leq
e\beta^{l-1},$

where the last two inequalities hold since
$\left(1-\frac{1}{l}\right)^{l-1}\geq\frac{1}{e}$ and
$\left(1+\frac{1}{l}\right)^{l}\leq e$. Indeed, using inequalities $\ln(x)\leq
x-1,x>0$ and $\ln(x)\geq 1-\frac{1}{x},x>0$, we can show that
$l\ln\left(1+\frac{1}{l}\right)\leq 1$ and
$(l-1)\ln\left(1-\frac{1}{l}\right)\geq(l-1)\left(1-\frac{1}{1-\frac{1}{l}}\right)=-1$.

From (Tropp, 2012), for $\Delta W_{i}\in\mathbb{R}^{h_{i-1}\times h_{i}}$ and
$\Delta W_{i}\sim\mathcal{N}(0,\sigma^{2}I)$, we have

$\displaystyle\mathbb{P}\left\\{\left\|\Delta W_{i}\right\|_{2}\geq
t\right\\}\leq(h_{i-1}+h_{i})\exp\left(-\frac{t^{2}}{2\sigma^{2}\max(h_{i-1},h_{i})}\right)\leq
2h\exp\left(-\frac{t^{2}}{2h\sigma^{2}}\right).$

Taking a union bound, we have

$\displaystyle\mathbb{P}\left(\bigcap_{i=1}^{l}\left\\{\left\|\Delta
W_{i}\right\|_{2}<t\right\\}\right)$
$\displaystyle=1-\mathbb{P}\left(\bigcup_{i=1}^{l}\left\\{\left\|\Delta
W_{i}\right\|_{2}\geq t\right\\}\right)$ $\displaystyle\geq
1-\sum_{i=1}^{l}\mathbb{P}\left\\{\left\|\Delta W_{i}\right\|_{2}\geq
t\right\\}$ $\displaystyle\geq
1-2lh\exp\left(-\frac{t^{2}}{2h\sigma^{2}}\right).$

Setting $2lh\exp\left(-\frac{t^{2}}{2h\sigma^{2}}\right)=\frac{1}{2}$, we have
$t=\sigma\sqrt{2h\log(4lh)}$. This implies that

$\displaystyle\mathbb{P}\left(\bigcap_{i=1}^{l}\left\\{\left\|\Delta
W_{i}\right\|_{2}<\sigma\sqrt{2h\log(4lh)}\right\\}\right)$
$\displaystyle\geq\frac{1}{2}.$

Plugging this bound into Lemma A.4, we have that with probability at least
$\frac{1}{2}$ over $\Delta w$,

$\displaystyle\left|R\left(f_{w+\Delta
w}\left(G\right),i,j\right)-R\left(f_{w}\left(G\right),i,j\right)\right|$
$\displaystyle\leq
2e(B+\epsilon)\left(\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\right)\sum_{i=1}^{l}\frac{\left\|\Delta
W_{i}\right\|_{2}}{\left\|W_{i}\right\|_{2}}$
$\displaystyle=2e(B+\epsilon)\beta^{l}\sum_{i=1}^{l}\frac{\left\|\Delta
W_{i}\right\|_{2}}{\beta}$ $\displaystyle\leq
2e(B+\epsilon)\beta^{l-1}l\sigma\sqrt{2h\log(4lh)}$ $\displaystyle\leq
2e^{2}(B+\epsilon)\tilde{\beta}^{l-1}l\sigma\sqrt{2h\log(4lh)}\leq\frac{\gamma}{2},$

where we set
$\sigma=\frac{\gamma}{4e^{2}(B+\epsilon)\tilde{\beta}^{l-1}l\sqrt{2h\log(4lh)}}$
to get the last inequality. Note that Lemma A.4 also requires $\left\|\Delta
W_{i}\right\|_{2}\leq\frac{1}{l}\left\|W_{i}\right\|_{2},\forall i\in[l]$. The
requirement is satisfied if $\sigma\leq\frac{\beta}{l\sqrt{2h\log(4lh)}}$,
which in turn can be satisfied if

$\displaystyle\frac{\gamma}{4e^{2}(B+\epsilon)\tilde{\beta}^{l-1}l\sqrt{2h\log(4lh)}}\leq\frac{\beta}{l\sqrt{2h\log(4lh)}}.$
(11)

Note that $\frac{\gamma}{4e(B+\epsilon)}\leq\beta^{l}$ is a sufficient
condition of Equation 11. We will see how to satisfy this condition later.

We now compute the KL term in the PAC-Bayes bound in Lemma 3.2. As defined
above, for a fixed $w$, the prior distribution $P=\mathcal{N}(0,\sigma^{2}I)$,
the posterior distribution $Q$ is the distribution of $\Delta w$ shifted by
$w$, that is, $Q=\mathcal{N}(w,\sigma^{2}I)$. Then we have,

$\displaystyle KL\left(Q\|P\right)$
$\displaystyle=\frac{1}{2}w^{\top}\left(\sigma^{2}I\right)^{-1}w=\frac{\left\|w\right\|_{2}^{2}}{2\sigma^{2}}$
$\displaystyle=\frac{16e^{4}(B+\epsilon)^{2}\tilde{\beta}^{2l-2}l^{2}2h\log(4lh)}{2\gamma^{2}}\sum_{i=1}^{l}\left\|W_{i}\right\|_{F}^{2}$
$\displaystyle\leq\mathcal{O}\left(\frac{(B+\epsilon)^{2}\beta^{2l}l^{2}h\log(lh)}{\gamma^{2}}\sum_{i=1}^{l}\frac{\left\|W_{i}\right\|_{F}^{2}}{\beta^{2}}\right)$
$\displaystyle\leq\mathcal{O}\left((B+\epsilon)^{2}l^{2}h\log(lh)\frac{\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}^{2}}{\gamma^{2}}\sum_{i=1}^{l}\frac{\left\|W_{i}\right\|_{F}^{2}}{\left\|W_{i}\right\|_{2}^{2}}\right).$

From Lemma 3.2, fixing any $\tilde{\beta}$, with probability $1-\delta$ over
$S$, for all $w$ such that $|\beta-\tilde{\beta}|\leq\frac{1}{l}\beta$, we
have,

$\displaystyle
R_{\mathcal{D},0}\left(f_{w}\right)\leq\hat{R}_{S,\gamma}\left(f_{w}\right)+\mathcal{O}\left(\sqrt{\frac{(B+\epsilon)^{2}l^{2}h\log(lh)\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}^{2}\sum_{i=1}^{l}\frac{\left\|W_{i}\right\|_{F}^{2}}{\left\|W_{i}\right\|_{2}^{2}}+\log(m/\delta)}{\gamma^{2}m}}\right).$
(12)

Finally, we need to consider multiple choices of $\tilde{\beta}$ so that for
any $\beta$, we can bound the generalization error like Equation 12. First, we
only need to consider values of $\beta$ in the following range,

$\displaystyle\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}\leq\beta\leq\left(\frac{\gamma\sqrt{m}}{2(B+\epsilon)}\right)^{1/l},$
(13)

since otherwise the bound holds trivially as
$R_{\mathcal{D},0}\left(f_{w}\right)\leq 1$ by definition. If
$\beta^{l}<\frac{\gamma}{2(B+\epsilon)}$, then for any $G$ and any
$i,j\in[K],$

$\displaystyle\left|RM\left(f_{w}\left(G\right),i,j\right)\right|$
$\displaystyle=\left|\inf_{G^{\prime}\in\delta_{w}(G)}M\left(f_{w}\left(G^{\prime}\right),i,j\right)\right|=\left|M\left(f_{w}\left(\hat{G}\right),i,j\right)\right|$
$\displaystyle=\left|f_{w}\left(\hat{G}\right)_{i}-f_{w}\left(\hat{G}\right)_{j}\right|\leq
2\left|f_{w}\left(\hat{G}\right)_{i}\right|$ $\displaystyle\leq
2\left\|f_{w}\left(\hat{G}\right)\right\|_{2}=2\left\|\frac{1}{n}\bm{1}_{n}H_{l-1}^{*}W_{l}\right\|_{2}\leq
2\left\|\frac{1}{n}\bm{1}_{n}\right\|_{2}\left\|H_{l-1}^{*}W_{l}\right\|_{F}$
$\displaystyle\leq\frac{2}{\sqrt{n}}\left\|H_{l-1}^{*}\right\|_{F}\left\|W_{l}\right\|_{2}\leq
2(B+\epsilon)\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}\qquad(\mbox{using
\lx@cref{creftype~refnum}{eq:pf-gcn-pert-bound-1}})$
$\displaystyle=2(B+\epsilon)\beta^{l}<2(B+\epsilon)\frac{\gamma}{2(B+\epsilon)}=\gamma,$

where
$\hat{G}=\arg\inf_{G^{\prime}\in\delta_{w}(G)}M\left(f_{w}\left(G^{\prime}\right),i,j\right)$
and $H_{l-1}^{*}$ is the corresponding node representation. Therefore, by the
definition, we always have $\hat{R}_{S,\gamma}\left(f_{w}\right)=1$ when
$\beta<\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}$.

Alternatively, if $\beta^{l}>\frac{\gamma\sqrt{m}}{2(B+\epsilon)}$, the term
inside the big-O notation in Equation 12 would be

$\displaystyle\sqrt{\frac{(B+\epsilon)^{2}l^{2}h\log(lh)\prod\limits_{i=1}^{l}\left\|W_{i}\right\|_{2}^{2}\sum\limits_{i=1}^{l}\dfrac{\left\|W_{i}\right\|_{F}^{2}}{\left\|W_{i}\right\|_{2}^{2}}+\log(m/\delta)}{\gamma^{2}m}}$
$\displaystyle\geq\sqrt{\frac{l^{2}h\log(lh)}{4}\sum_{i=1}^{l}\dfrac{\left\|W_{i}\right\|_{F}^{2}}{\left\|W_{i}\right\|_{2}^{2}}}$
$\displaystyle\geq\sqrt{\frac{l^{2}h\log(lh)}{4}}\geq 1,$

where we use the facts that
$\left\|W_{i}\right\|_{F}\geq\left\|W_{i}\right\|_{2}$ and we typically choose
$h\geq 2$ and $l\geq 2$ in practice. Note that the lower bound in Equation 13
ensures that Equation 11 holds which in turn justifies the applicability of
Lemma A.4.

Consider a covering set centered at
$C=\left\\{\tilde{\beta}_{1},\dots,\tilde{\beta}_{|C|}\right\\}$ of the
interval in Equation 13 with radius
$\frac{1}{l}\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}$, where $|C|$ is
the size of the set. To make sure that
$|\beta-\tilde{\beta}|\leq\frac{1}{l}\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}\leq\frac{1}{l}\beta$,
the minimal size of $C$ should be

$\displaystyle|C|=\frac{\left(\frac{\gamma\sqrt{m}}{2(B+\epsilon)}\right)^{1/l}-\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}}{\frac{2}{l}\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}}=\frac{l}{2}\left(m^{\frac{1}{2l}}-1\right).$

For a $\tilde{\beta}_{i}\in C$, we denote the event that Equation 12 holds for
$|\beta-\tilde{\beta}|\leq\frac{1}{l}\beta$ as $E_{i}$. Therefore, the
probability of the event that Equation 12 holds for any $\beta$ satisying
Equation 13 is

$\displaystyle\mathbb{P}\left(\bigcap_{i=1}^{|C|}E_{i}\right)=1-\mathbb{P}\left(\bigcup_{i=1}^{|C|}\bar{E}_{i}\right)\geq
1-\sum_{i=1}^{|C|}\mathbb{P}\left\\{\bar{E}_{i}\right\\}\geq 1-|C|\delta,$

where $\bar{E}_{i}$ denotes the complement of $E_{i}$. Hence, let
$\delta^{\prime}=|C|\delta$, then we have that, with probability
$1-\delta^{\prime}$ and for all $w$,

$\displaystyle L_{\mathcal{D},0}\left(f_{w}\right)$
$\displaystyle\leq\hat{L}_{S,\gamma}\left(f_{w}\right)+\mathcal{O}\left(\sqrt{\frac{(B+\epsilon)^{2}l^{2}h\log(lh)\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}^{2}\sum_{i=1}^{l}\frac{\left\|W_{i}\right\|_{F}^{2}}{\left\|W_{i}\right\|_{2}^{2}}+\log(m/\delta)}{\gamma^{2}m}}\right)$
$\displaystyle=\hat{L}_{S,\gamma}\left(f_{w}\right)+\mathcal{O}\left(\sqrt{\frac{(B+\epsilon)^{2}l^{2}h\log(lh)\prod_{i=1}^{l}\left\|W_{i}\right\|_{2}^{2}\sum_{i=1}^{l}\frac{\left\|W_{i}\right\|_{F}^{2}}{\left\|W_{i}\right\|_{2}^{2}}+\log(ml/\delta^{\prime})}{\gamma^{2}m}}\right).\qed$

###  A.4 Results of MPGNN

####  A.4.1 Proof of Perturbation Bound for MPGNN

######  Lemma A.5.

Assume that for any MPGNN model $f_{w}\in\mathcal{H}$ with $l$ layers. For any
$w$ such that $\left\|U_{i}\right\|_{2}\leq M_{1},\forall
i\in[l-1],\left\|W_{i}\right\|_{2}\leq M_{2},\forall i\in[l]$ and any
perturbation $\Delta w=vec\left(\left\\{\Delta
W_{i}\right\\}_{i=1}^{l}\right)$ such that
$\eta=\max\left(\left\\{\frac{\left\|\Delta
U_{i}\right\|_{2}}{\left\|U_{i}\right\|_{2}}\right\\}_{i=1}^{l-1},\left\\{\frac{\left\|\Delta
W_{i}\right\|_{2}}{\left\|W_{i}\right\|_{2}}\right\\}_{i=1}^{l}\right)\leq{1\over
l},\forall i\in[l]$, for any $G=(X,A)\in\mathcal{X}\times\mathcal{G}$, the
change in the output of MPGNN is bounded as

$\displaystyle\left\|f_{w+\Delta
w}\left(G\right)-f_{w}\left(G\right)\right\|_{2}$
$\displaystyle\leq\begin{cases}e\eta
LM_{1}M_{2}\left\|X\right\|_{2}(l+1)^{2},&\tau=1,\\\ e\eta
lLM_{1}M_{2}\left\|X\right\|_{2}\dfrac{\tau^{l-1}-1}{\tau-1},&\tau\neq
1,\end{cases}$

where $\tau=L^{3}M_{2}\left\|P_{G}\right\|_{2}$.

###### Proof.

We denote the node representation in $j$-th layer as

$\displaystyle f_{w}^{j}(G)=H_{j}=\phi_{j}\left(E_{j}\right),\
E_{j}=XU_{j}+\rho_{j}\left(F_{j}\right),\
F_{j}=P_{G}\psi_{j}\left(H_{j-1}\right)W_{j},\ j\in[l-1],$ $\displaystyle
f_{w}^{l}(G)=H_{l}=\frac{1}{n}\bm{1}_{n}H_{l-1}W_{l}.$

Adding perturbation $\Delta w$ to the weights $w$, i.e., for the $j$-th layer,
the perturbed weights are $W_{j}+\Delta W_{j}$ or $U_{j}+\Delta U_{j}$ and
denote $H_{j}^{\prime},\ E_{j}^{\prime},\ F_{j}^{\prime}$ as the perturbed
term respectively.

Upper Bound on the Node Representation. For any $j<l$,

$\displaystyle\left\|F_{j}\right\|_{F}$
$\displaystyle=\left\|P_{G}\psi_{j}\left(H_{j-1}\right)W_{j}\right\|_{F}$
$\displaystyle\leq\left\|P_{G}\right\|_{2}\left\|\psi_{j}\left(H_{j-1}\right)\right\|_{F}\left\|W_{j}\right\|_{2}$
$\displaystyle\leq LM_{2}\left\|P_{G}\right\|_{2}\left\|H_{j-1}\right\|_{F},$

where the first inequality holds by Proposition A.1, and the last one holds by
the assumption, the Lipschitzness of $\psi_{j}$ with $\psi_{j}(0)=0$. Then we
have, for any $j<l$,

$\displaystyle\left\|H_{j}\right\|_{F}$
$\displaystyle=\left\|\phi_{j}\left(E_{j}\right)\right\|_{F}\leq
L\left\|XU_{j}+\rho_{j}\left(F_{j}\right)\right\|_{F}$ $\displaystyle\leq
L\left\|XU_{j}\right\|_{F}+L\left\|\rho_{j}\left(F_{j}\right)\right\|_{F}$
$\displaystyle\leq
L\left\|X\right\|_{F}\left\|U_{j}\right\|_{2}+L^{2}\left\|F_{j}\right\|_{F}$
$\displaystyle\leq
LM_{1}\left\|X\right\|_{F}+L^{3}M_{2}\left\|P_{G}\right\|_{2}\left\|H_{j-1}\right\|_{F}.$

Denoting
$\kappa=LM_{1}\left\|X\right\|_{F},\tau=L^{3}M_{2}\left\|P_{G}\right\|_{2}$,
by applying the relationship iteratively and $H_{0}=0$, we have, for $j<l$,

$\displaystyle\left\|H_{j}\right\|_{F}$
$\displaystyle\leq\kappa+\tau\left\|H_{j-1}\right\|_{F}$
$\displaystyle\leq\tau^{j}\left\|H_{0}\right\|_{F}+\sum_{i=0}^{j-1}\kappa\tau^{j-1-i}=\sum_{i=0}^{j-1}\kappa\tau^{j-1-i}$
$\displaystyle=\begin{cases}\kappa j,&\tau=1,\\\
\kappa\dfrac{\tau^{j}-1}{\tau-1},&\tau\neq 1.\\\ \end{cases}$ (14)

Upper Bound on the Change of Node Representation. For any $j<l$,

$\displaystyle\left\|F_{j}^{\prime}-F_{j}\right\|_{F}$
$\displaystyle=\left\|P_{G}\psi_{j}\left(H_{j-1}^{\prime}\right)\left(W_{j}+\Delta
W_{j}\right)-P_{G}\psi_{j}\left(H_{j-1}\right)W_{j}\right\|_{F}$
$\displaystyle=\left\|P_{G}\left[\psi_{j}\left(H_{j-1}^{\prime}\right)-\psi_{j}\left(H_{j-1}\right)\right]\left(W_{j}+\Delta
W_{j}\right)+P_{G}\psi_{j}\left(H_{j-1}\right)\Delta W_{j}\right\|_{F}$
$\displaystyle\leq\left\|P_{G}\left[\psi_{j}\left(H_{j-1}^{\prime}\right)-\psi_{j}\left(H_{j-1}\right)\right]\left(W_{j}+\Delta
W_{j}\right)\right\|_{F}+\left\|P_{G}\psi_{j}\left(H_{j-1}\right)\Delta
W_{j}\right\|_{F}$
$\displaystyle\leq\left\|P_{G}\right\|_{2}\left\|\psi_{j}\left(H_{j-1}^{\prime}\right)-\psi_{j}\left(H_{j-1}\right)\right\|_{F}\left\|W_{j}+\Delta
W_{j}\right\|_{2}+\left\|P_{G}\right\|_{2}\left\|\psi_{j}\left(H_{j-1}\right)\right\|_{F}\left\|\Delta
W_{j}\right\|_{2}$ $\displaystyle\leq
L\left(1+\eta\right)M_{2}\left\|P_{G}\right\|_{2}\left\|H_{j-1}^{\prime}-H_{j-1}\right\|_{F}+L\eta
M_{2}\left\|P_{G}\right\|_{2}\left\|H_{j-1}\right\|_{F},$

where the second inequality holds from Proposition A.1 and the last one holds
by the assumption and the Lipschitzness of $\psi_{j}$ with $\psi_{j}(0)=0$.
Then we have, for any $j<l$,

$\displaystyle\left\|H_{j}^{\prime}-H_{j}\right\|_{F}$
$\displaystyle=\left\|\phi_{j}(E_{j}^{\prime})-\phi_{j}(E_{j})\right\|_{F}$
$\displaystyle\leq L\left\|\left[X\left(U_{j}+\Delta
U_{j}\right)+\rho_{j}\left(F_{j}^{\prime}\right)\right]-\left[XU_{j}+\rho_{j}\left(F_{j}\right)\right]\right\|_{F}$
$\displaystyle=L\left\|X\Delta
U_{j}+\rho_{j}\left(F_{j}^{\prime}\right)-\rho_{j}\left(F_{j}\right)\right\|_{F}$
$\displaystyle\leq L\left\|X\Delta
U_{j}\right\|_{F}+L\left\|\rho_{j}\left(F_{j}^{\prime}\right)-\rho_{j}\left(F_{j}\right)\right\|_{F}$
$\displaystyle\leq L\left\|X\right\|_{F}\left\|\Delta
U_{j}\right\|_{2}+L^{2}\left\|F_{j}^{\prime}-F_{j}\right\|_{F}$
$\displaystyle\leq L\eta
M_{1}\left\|X\right\|_{F}+L^{3}\left(1+\eta\right)M_{2}\left\|P_{G}\right\|_{2}\left\|H_{j-1}^{\prime}-H_{j-1}\right\|_{F}+L^{3}\eta
M_{2}\left\|P_{G}\right\|_{2}\left\|H_{j-1}\right\|_{F}$
$\displaystyle=\tau(1+\eta)\left\|H_{j-1}^{\prime}-H_{j-1}\right\|_{F}+\kappa\eta+\tau\eta\left\|H_{j-1}\right\|_{F}.$

We consider different values of $\tau$. If $\tau=1$, we have

$\displaystyle\left\|H_{j}^{\prime}-H_{j}\right\|_{F}$
$\displaystyle\leq(1+\eta)\left\|H_{j-1}^{\prime}-H_{j-1}\right\|_{F}+\kappa\eta+\kappa\eta(j-1)\qquad(\mbox{By
\lx@cref{creftype~refnum}{eq:pf-lem-pert-f-mpgnn-1}})$
$\displaystyle=(1+\eta)\left\|H_{j-1}^{\prime}-H_{j-1}\right\|_{F}+\kappa\eta
j$
$\displaystyle\leq\sum_{i=0}^{j-1}\kappa\eta(i+1)\left(1+\eta\right)^{j-i-1}$
$\displaystyle\leq\kappa\eta\left(1+\frac{1}{l}\right)^{j}\sum_{i=0}^{j-1}(i+1)\left(1+\frac{1}{l}\right)^{-i-1}=\kappa\eta\left(1+\frac{1}{l}\right)^{j}\sum_{i=1}^{j}i\left(1+\frac{1}{l}\right)^{-i}$
$\displaystyle=\kappa\eta\left(1+\frac{1}{l}\right)^{j}\left(1+\frac{1}{l}\right)^{-1}\frac{1-(j+1)\left(1+\frac{1}{l}\right)^{-j}+j\left(1+\frac{1}{l}\right)^{-j-1}}{\left(1-\left(1+\frac{1}{l}\right)^{-1}\right)^{2}}$
$\displaystyle=\kappa\eta\frac{\left(1+\frac{1}{l}\right)^{j+1}-(j+1)\left(1+\frac{1}{l}\right)+j}{\left(\left(1+\frac{1}{l}\right)-1\right)^{2}}$
$\displaystyle\leq\kappa\eta l^{2}\left(1+\frac{1}{l}\right)^{j+1}=\kappa\eta
l(1+l)\left(1+\frac{1}{l}\right)^{j}.$ (15)

If $\tau\neq 1$, we have

$\displaystyle\left\|H_{j}^{\prime}-H_{j}\right\|_{F}$
$\displaystyle\leq\tau(1+\eta)\left\|H_{j-1}^{\prime}-H_{j-1}\right\|_{F}+\kappa\eta+\tau\eta\left\|H_{j-1}\right\|_{F}$
$\displaystyle\leq\tau(1+\eta)\left\|H_{j-1}^{\prime}-H_{j-1}\right\|_{F}+\kappa\eta+\kappa\eta\tau\frac{\tau^{j-1}-1}{\tau-1}\qquad(\mbox{By
\lx@cref{creftype~refnum}{eq:pf-lem-pert-f-mpgnn-1}})$
$\displaystyle=\tau(1+\eta)\left\|H_{j-1}^{\prime}-H_{j-1}\right\|_{F}+\kappa\eta\frac{\tau^{j}-1}{\tau-1}$
$\displaystyle\leq\sum_{i=0}^{j-1}\kappa\eta\left(\frac{\tau^{i+1}-1}{\tau-1}\right)\tau^{j-i-1}(1+\eta)^{j-i-1}$
$\displaystyle\leq\frac{\kappa\eta\tau^{j}}{\tau-1}\left(1+\frac{1}{l}\right)^{j}\sum_{i=0}^{j-1}\left(1-\tau^{-i-1}\right)\left(1+\frac{1}{l}\right)^{-i-1}$
$\displaystyle\leq\frac{\kappa\eta\tau^{j}}{\tau-1}\left(1+\frac{1}{l}\right)^{j}\sum_{i=1}^{j}\left(1-\tau^{-i}\right).$
(16)

Final Bound on the Readout Layer.

$\displaystyle\left\|H_{l}^{\prime}-H_{l}\right\|_{2}$
$\displaystyle=\left\|\frac{1}{n}\bm{1}_{n}H_{l-1}^{\prime}(W_{l}+\Delta
W_{l})-\frac{1}{n}\bm{1}_{n}H_{l-1}W_{l}\right\|_{2}$
$\displaystyle=\left\|\frac{1}{n}\bm{1}_{n}\left(H_{l-1}^{\prime}-H_{l-1}\right)(W_{l}+\Delta
W_{l})+\frac{1}{n}\bm{1}_{n}H_{l-1}\Delta W_{l}\right\|_{2}$
$\displaystyle\leq\left\|\frac{1}{n}\bm{1}_{n}\left(H_{l-1}^{\prime}-H_{l-1}\right)(W_{l}+\Delta
W_{l})\right\|_{2}+\left\|\frac{1}{n}\bm{1}_{n}H_{l-1}\Delta
W_{l}\right\|_{2}$
$\displaystyle\leq\left\|\frac{1}{n}\bm{1}_{n}\right\|_{2}\left\|\left(H_{l-1}^{\prime}-H_{l-1}\right)\left(W_{l}+\Delta
W_{l}\right)\right\|_{2}+\left\|\frac{1}{n}\bm{1}_{n}\right\|_{2}\left\|H_{l-1}\Delta
W_{l}\right\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{n}}\left\|H_{l-1}^{\prime}-H_{l-1}\right\|_{F}\left\|W_{l}+\Delta
W_{l}\right\|_{2}+\frac{1}{\sqrt{n}}\left\|H_{l-1}\right\|_{F}\left\|\Delta
W_{l}\right\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{n}}(1+\eta)M_{2}\left\|H_{l-1}^{\prime}-H_{l-1}\right\|_{F}+\frac{1}{\sqrt{n}}\eta
M_{2}\left\|H_{l-1}\right\|_{F}.$

If $\tau=1$, combining Equations 14 and 15, we have

$\displaystyle\left\|H_{l}^{\prime}-H_{l}\right\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{n}}(1+\eta)M_{2}\left\|H_{l-1}^{\prime}-H_{l-1}\right\|_{F}+\frac{1}{\sqrt{n}}\eta
M_{2}\left\|H_{l-1}\right\|_{F}$
$\displaystyle\leq\frac{1}{\sqrt{n}}(1+\eta)\eta
lM_{2}\kappa(1+l)\left(1+\frac{1}{l}\right)^{l-1}+\frac{1}{\sqrt{n}}\eta(l-1)\kappa
M_{2}$ $\displaystyle\leq\frac{1}{\sqrt{n}}\eta l(1+l)\kappa
M_{2}\left(1+\frac{1}{l}\right)^{l}+\frac{1}{\sqrt{n}}\eta(l-1)\kappa M_{2}$
$\displaystyle=\frac{1}{\sqrt{n}}\kappa\eta
M_{2}\left(1+\frac{1}{l}\right)^{l}\left(l(1+l)+(l-1)\left(1+\frac{1}{l}\right)^{-l}\right)$
$\displaystyle\leq\frac{1}{\sqrt{n}}e\kappa\eta M_{2}\left(l+l^{2}+l-1\right)$
$\displaystyle\leq\frac{1}{\sqrt{n}}e\kappa\eta M_{2}(l+1)^{2}.$

If $\tau\neq 1$, combining Equations 14 and 16, we have

$\displaystyle\left\|H_{l}^{\prime}-H_{l}\right\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{n}}(1+\eta)M_{2}\left\|H_{l-1}^{\prime}-H_{l-1}\right\|_{F}+\frac{1}{\sqrt{n}}\eta
M_{2}\left\|H_{l-1}\right\|_{F}$
$\displaystyle\leq\frac{1}{\sqrt{n}}(1+\eta)M_{2}\frac{\kappa\eta\tau^{l-1}}{\tau-1}\left(1+\frac{1}{l}\right)^{l-1}\sum_{i=1}^{l-1}\left(1-\tau^{-i}\right)+\frac{1}{\sqrt{n}}\eta
M_{2}\kappa\frac{\tau^{l-1}-1}{\tau-1}$
$\displaystyle\leq\frac{1}{\sqrt{n}}\kappa\eta\tau^{l-1}M_{2}\left(1+\frac{1}{l}\right)^{l}\left(\sum_{i=1}^{l-1}\frac{1-\tau^{-i}}{\tau-1}+\frac{1-\tau^{1-l}}{\tau-1}\left(1+\frac{1}{l}\right)^{-l}\right)$
$\displaystyle\leq\frac{1}{\sqrt{n}}\kappa\eta\tau^{l-1}M_{2}\left(1+\frac{1}{l}\right)^{l}\left(\sum_{i=1}^{l-1}\frac{1-\tau^{-i}}{\tau-1}+\frac{1-\tau^{-(l-1)}}{\tau-1}\right)$
$\displaystyle\leq\frac{1}{\sqrt{n}}\kappa\eta\tau^{l-1}M_{2}\left(1+\frac{1}{l}\right)^{l}l\frac{1-\tau^{-(l-1)}}{\tau-1}$
$\displaystyle\leq\frac{1}{\sqrt{n}}e\kappa\eta
lM_{2}\frac{\tau^{l-1}-1}{\tau-1}.$

Therefore,

$\displaystyle\left\|f_{w+u}\left(G\right)-f_{w}\left(G\right)\right\|_{2}=\left\|H_{l}^{\prime}-H_{l}\right\|_{2}$
$\displaystyle\leq\begin{cases}e\eta
LM_{1}M_{2}\left\|X\right\|_{2}(l+1)^{2},&\tau=1,\\\ e\eta
lLM_{1}M_{2}\left\|X\right\|_{2}\dfrac{\tau^{l-1}-1}{\tau-1},&\tau\neq 1.\\\
\end{cases}\qed$

######  Lemma A.6.

Under Assumptions 3.3 to 3.5, for any $w$ such that
$\left\|U_{i}\right\|_{2}\leq M_{1},\forall
i\in[l-1],\left\|W_{i}\right\|_{2}\leq M_{2},\forall i\in[l]$ and any
perturbation $\Delta w=vec\left(\left\\{\Delta
W_{i}\right\\}_{i=1}^{l}\right)$ such that
$\eta=\max\left(\left\\{\frac{\left\|\Delta
U_{i}\right\|_{2}}{\left\|U_{i}\right\|_{2}}\right\\}_{i=1}^{l-1},\left\\{\frac{\left\|\Delta
W_{i}\right\|_{2}}{\left\|W_{i}\right\|_{2}}\right\\}_{i=1}^{l}\right)\leq{1\over
l},\forall i\in[l]$, the change in the margin operator is bounded as

$\displaystyle\left|M\left(f_{w+\Delta
w}\left(G\right),i,j\right)-M\left(f_{w}\left(G\right),i,j\right)\right|\leq\begin{cases}2e\eta
LBM_{1}M_{2}(l+1)^{2},&\tau=1,\\\ 2e\eta
lLBM_{1}M_{2}\dfrac{\tau^{l-1}-1}{\tau-1},&\tau\neq 1,\end{cases}$

where $\tau=L^{3}M_{2}\left\|P_{G}\right\|_{2}$. Further, consider the
$\epsilon$-attack ($\epsilon>0$), the change in the robust margin operator is
bounded as

$\displaystyle\left|RM\left(f_{w+\Delta
w}\left(G\right),i,j\right)-RM\left(f_{w}\left(G\right),i,j\right)\right|\leq\begin{cases}2e\eta
L(B+\epsilon)M_{1}M_{2}(l+1)^{2},&\tau=1,\\\ 2e\eta
lL(B+\epsilon)M_{1}M_{2}\dfrac{\tau^{l-1}-1}{\tau-1},&\tau\neq 1.\end{cases}$

###### Proof.

Let

$\displaystyle\mathcal{C}=\begin{cases}e\eta LM_{1}M_{2}(l+1)^{2},&\tau=1,\\\
e\eta lLM_{1}M_{2}\dfrac{\tau^{l-1}-1}{\tau-1},&\tau\neq 1.\end{cases}$

For any $i,j\in[K]$, by the definition of margin operator, we have

$\displaystyle\left|M\left(f_{w+\Delta
w}\left(G\right),i,j\right)-M\left(f_{w}\left(G\right),i,j\right)\right|$
$\displaystyle\leq\left|f_{w+\Delta
w}\left(G\right)_{i}-f_{w}\left(G\right)_{i}\right|+\left|f_{w+\Delta
w}\left(G\right)_{j}-f_{w}\left(G\right)_{j}\right|$ $\displaystyle\leq
2\left\|f_{w+\Delta w}\left(G\right)-f_{w}\left(G\right)\right\|_{2}.$

By Propositions A.2 and A.5, we have

$\displaystyle\left|M\left(f_{w+\Delta
w}\left(G\right),i,j\right)-M\left(f_{w}\left(G\right),i,j\right)\right|$
$\displaystyle\leq 2\left\|X\right\|_{2}\mathcal{C}\leq 2B\mathcal{C}.$

Further, let

$\displaystyle G(w)$
$\displaystyle=\mathop{\arg\inf}_{G^{\prime}\in\delta_{w}(G)}\left(f_{w}\left(G^{\prime}\right)_{i}-f_{w}\left(G^{\prime}\right)_{j}\right)=\mathop{\arg\inf}_{G^{\prime}\in\delta_{w}(G)}M\left(f_{w}\left(G\right),i,j\right),$

and $X(w)$ is the corresponding node features matrix. Denoting
$\tilde{w}=w+\Delta w$, we have

$\displaystyle\left|RM\left(f_{\tilde{w}}\left(G\right),i,j\right)-RM\left(f_{w}\left(G\right),i,j\right)\right|$
$\displaystyle=\left|\inf_{G^{\prime}\in\delta_{\tilde{w}}(G)}M\left(f_{\tilde{w}}\left(G\right),i,j\right)-\inf_{G^{\prime}\in\delta_{w}(G)}M\left(f_{w}\left(G\right),i,j\right)\right|$
$\displaystyle=\left|M\left(f_{\tilde{w}}\left(G(\tilde{w})\right),i,j\right)-M\left(f_{w}\left(G(w)\right),i,j\right)\right|$
$\displaystyle\leq\max\left\\{\left|M\left(f_{\tilde{w}}\left(G(\tilde{w})\right),i,j\right)-M\left(f_{w}\left(G(\tilde{w})\right),i,j\right)\right|,\right.$
$\displaystyle\qquad\qquad\left.\left|M\left(f_{\tilde{w}}\left(G(w)\right),i,j\right)-M\left(f_{w}\left(G(w)\right),i,j\right)\right|\right\\}$
$\displaystyle\leq
2\max\left\\{\left\|X(\tilde{w})\right\|_{2},\left\|X(w)\right\|_{2}\right\\}\mathcal{C}$
$\displaystyle\leq 2(B+\epsilon)\mathcal{C},$

where the first inequality holds since, by the definition of $G(w)$,

$\displaystyle
M\left(f_{\tilde{w}}\left(G(\tilde{w})\right),i,j\right)-M\left(f_{w}\left(G(w)\right),i,j\right)\leq
M\left(f_{\tilde{w}}\left(G(w)\right),i,j\right)-M\left(f_{w}\left(G(w)\right),i,j\right),$
$\displaystyle
M\left(f_{w}\left(G(w)\right),i,j\right)-M\left(f_{\tilde{w}}\left(G(\tilde{w})\right),i,j\right)\leq
M\left(f_{w}\left(G(\tilde{w})\right),i,j\right)-M\left(f_{\tilde{w}}\left(G(\tilde{w})\right),i,j\right),$

and the last inequality holds from Assumption 3.3 and the definition of
$\epsilon$-attack. ∎

####  A.4.2 Proof of Generalization bounds for MPGNN

###### Proof of Theorem 3.8.

We consider the cases of different values of $\tau$.

Case $\tau\neq 1$ Let $\beta=\max\left\\{\frac{1}{\zeta},\xi^{1/l}\right\\}$,
where
$\zeta=\min\left(\left\\{\left\|U_{i}\right\|_{2}\right\\}_{i=1}^{l-1},\left\\{\left\|W_{i}\right\|_{2}\right\\}_{i=1}^{l}\right)$
and $\xi=LM_{1}M_{2}\dfrac{\tau^{l-1}-1}{\tau-1}$. Consider the prior
distribution $P=\mathcal{N}(0,\sigma^{2}I)$ and the random perturbation
distribution $u\sim\mathcal{N}(0,\sigma^{2}I)$. Note that the $\sigma$ of the
prior and the perturbation distributions are the same and will be set
according to $\beta$. More precisely, we will set the $\sigma$ based on some
approximation $\tilde{\beta}$ of $\beta$ since the prior distribution $P$ can
not depend on any learned weights directly. The approximation $\tilde{\beta}$
is chosen to be a cover set which covers the meaningful range of $\beta$. For
now, let us assume that we have a fix $\tilde{\beta}$ and consider $\beta$
which satisfies $|\beta-\tilde{\beta}|\leq\frac{1}{l+2}\beta$. Note that this
also implies

$\displaystyle|\beta-\tilde{\beta}|\leq\frac{1}{l+2}\beta$ $\displaystyle\
\Rightarrow\
\left(1-\frac{1}{l+2}\right)\beta\leq\tilde{\beta}\leq\left(1+\frac{1}{l+2}\right)\beta$
$\displaystyle\ \Rightarrow\
\left(1-\frac{1}{l+2}\right)^{l+1}\beta^{l+1}\leq\tilde{\beta}^{l+1}\leq\left(1+\frac{1}{l+2}\right)^{l+1}\beta^{l+1}$
$\displaystyle\ \Rightarrow\
\left(1-\frac{1}{l+2}\right)^{l+1}\beta^{l+1}\leq\tilde{\beta}^{l+1}\leq\left(1+\frac{1}{l+2}\right)^{l+2}\beta^{l+1}$
$\displaystyle\ \Rightarrow\ \frac{1}{e}\beta^{l+1}\leq\tilde{\beta}^{l+1}\leq
e\beta^{l+1}.$

Denoting $\Delta W_{i}\in\mathbb{R}^{h_{i-1}\times h_{i}},\Delta
U_{i}\in\mathbb{R}^{h_{0}\times h_{i}}$ as $\Delta W$, from (Tropp, 2012), for
$\Delta W\sim\mathcal{N}(0,\sigma^{2}I)$, we have

$\displaystyle\mathbb{P}\left\\{\left\|\Delta W\right\|_{2}\geq t\right\\}\leq
2h\exp\left(-\frac{t^{2}}{2h\sigma^{2}}\right).$

Taking a union bound, we have

$\displaystyle\mathbb{P}\left(\bigcap_{i=1}^{l-1}\left\\{\left\|\Delta
U_{i}\right\|_{2}<t\right\\}\cap\bigcap_{i=1}^{l}\left\\{\left\|\Delta
W_{i}\right\|_{2}<t\right\\}\right)$
$\displaystyle=1-\mathbb{P}\left(\bigcup_{i=1}^{l-1}\left\\{\left\|\Delta
U_{i}\right\|_{2}\geq t\right\\}\cup\bigcup_{i=1}^{l}\left\\{\left\|\Delta
W_{i}\right\|_{2}\geq t\right\\}\right)$ $\displaystyle\geq
1-\sum_{i=1}^{l-1}\mathbb{P}\left\\{\left\|\Delta U_{i}\right\|_{2}\geq
t\right\\}-\sum_{i=1}^{l}\mathbb{P}\left\\{\left\|\Delta W_{i}\right\|_{2}\geq
t\right\\}$ $\displaystyle\geq
1-2(2l-1)h\exp\left(-\frac{t^{2}}{2h\sigma^{2}}\right).$

Setting $2(2l-1)h\exp\left(-\frac{t^{2}}{2h\sigma^{2}}\right)=\frac{1}{2}$, we
have $t=\sigma\sqrt{2h\log(4(2l-1)h)}$. This implies that

$\displaystyle\mathbb{P}\left(\max\left(\left\\{\left\|\Delta
U_{i}\right\|_{2}\right\\}_{i=1}^{l-1},\left\\{\left\|\Delta
W_{i}\right\|_{2}\right\\}_{i=1}^{l}\right)<t\right)\geq\frac{1}{2},$

and thus,

$\displaystyle\mathbb{P}\left(\max\left(\left\\{\frac{\left\|\Delta
U_{i}\right\|_{2}}{\left\|U_{i}\right\|_{2}}\right\\}_{i=1}^{l-1},\left\\{\frac{\left\|\Delta
W_{i}\right\|_{2}}{\left\|W_{i}\right\|_{2}}\right\\}_{i=1}^{l}\right)<\dfrac{t}{\zeta}\right)\geq\frac{1}{2}.$

Plugging this bound into Lemma A.6, we have that with probability at least
$\frac{1}{2}$ over $\Delta w$,

$\displaystyle\left|R\left(f_{w\Delta
w}\left(G\right),i,j\right)-R\left(f_{w}\left(G\right),i,j\right)\right|$
$\displaystyle\leq
2el(B+\epsilon)LM_{1}M_{2}\dfrac{\tau^{l-1}-1}{\tau-1}\frac{t}{\zeta}$
$\displaystyle\leq 2el(B+\epsilon)\beta^{l+1}t$ $\displaystyle\leq
2e^{2}l(B+\epsilon)\tilde{\beta}^{l+1}\sigma\sqrt{2h\log(4(2l-1)h)}\leq\frac{\gamma}{2},$

where we set
$\sigma=\frac{\gamma}{4e^{2}l(B+\epsilon)\tilde{\beta}^{l+1}\sqrt{2h\log(4(2l-1)h)}}$
to get the last inequality. Note that Lemma A.6 also requires $\forall
i\in[l],\left\|\Delta
W_{i}\right\|_{2}\leq\frac{1}{l}\left\|W\right\|_{2},\left\|\Delta
U_{i}\right\|_{2}\leq\frac{1}{l}\left\|U\right\|_{2}$. The requirement is
satisfied if $\sigma\leq\frac{1}{\zeta l\sqrt{2h\log(4(2l-1)h)}}$ which in
turn can be satisfied if

$\displaystyle\frac{\gamma}{4e^{2}l(B+\epsilon)\tilde{\beta}^{l+1}\sqrt{2h\log(4(2l-1)h)}}\leq\frac{1}{\beta
l\sqrt{2h\log(4(2l-1)h)}},$ (17)

and one of the sufficient conditions for this is
$\frac{\gamma}{4e(B+\epsilon)}\leq\beta^{l}$. We will see how to satisfy this
condition later.

We now compute the KL term in the PAC-Bayes bound in Lemma 3.2. As defined
above, for a fixed $w$, the prior distribution $P=\mathcal{N}(0,\sigma^{2}I)$,
the posterior distribution $Q$ is the distribution of $\Delta w$ shifted by
$w$, that is, $Q=\mathcal{N}(w,\sigma^{2}I)$. Then we have,

$\displaystyle
KL\left(Q\|P\right)=\frac{\left\|w\right\|_{2}^{2}}{2\sigma^{2}}$
$\displaystyle=\frac{16e^{4}l^{2}(B+\epsilon)^{2}\tilde{\beta}^{2l+2}2h\log(4(2l-1)h)}{2\gamma^{2}}\left(\sum_{i=1}^{l-1}\left\|U_{i}\right\|_{F}^{2}+\sum_{i=1}^{l}\left\|W_{i}\right\|_{F}^{2}\right)$
$\displaystyle\leq\mathcal{O}\left(\frac{(B+\epsilon)^{2}\beta^{2l+2}l^{2}h\log(lh)}{\gamma^{2}}\left(\sum_{i=1}^{l-1}\left\|U_{i}\right\|_{F}^{2}+\sum_{i=1}^{l}\left\|W_{i}\right\|_{F}^{2}\right)\right).$

From Lemma 3.2, fixing any $\tilde{\beta}$, with probability $1-\delta$ and
for all $w$ such that $|\beta-\tilde{\beta}|\leq\frac{1}{l+2}\beta$, we have,

$\displaystyle
R_{\mathcal{D},0}\left(f_{w}\right)\leq\hat{R}_{S,\gamma}\left(f_{w}\right)+\mathcal{O}\left(\sqrt{\frac{(B+\epsilon)^{2}\beta^{2l+2}l^{2}h\log(lh)\left\|w\right\|_{2}^{2}+\log(m/\delta)}{\gamma^{2}m}}\right).$
(18)

Finally, we need to consider multiple choices of $\tilde{\beta}$ so that for
any $\beta$, we can bound the generalization error like Equation 18. First, we
only need to consider values of $\beta$ in the following range,

$\displaystyle\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}\leq\beta\leq\left(\frac{\gamma\sqrt{m}}{2(B+\epsilon)}\right)^{1/l},$
(19)

since otherwise the bound holds trivially as
$R_{\mathcal{D},0}\left(f_{w}\right)\leq 1$ by definition. To see this, if
$\beta^{l}<\frac{\gamma}{2(B+\epsilon)}$, then for any $G$ and any
$i,j\in[K]$, we have,

$\displaystyle\left|RM\left(f_{w}\left(G\right),i,j\right)\right|$
$\displaystyle=\left|\inf_{G^{\prime}\in\delta_{w}(G)}M\left(f_{w}\left(G^{\prime}\right),i,j\right)\right|=\left|M\left(f_{w}\left(\hat{G}\right),i,j\right)\right|$
$\displaystyle=\left|f_{w}\left(\hat{G}\right)_{i}-f_{w}\left(\hat{G}\right)_{j}\right|\leq
2\left|f_{w}\left(\hat{G}\right)_{i}\right|$ $\displaystyle\leq
2\left\|f_{w}\left(\hat{G}\right)\right\|_{2}=2\left\|\frac{1}{n}\bm{1}_{n}H_{l-1}^{*}W_{l}\right\|_{2}\leq
2\left\|\frac{1}{n}\bm{1}_{n}\right\|_{2}\left\|H_{l-1}^{*}W_{l}\right\|_{F}$
$\displaystyle\leq\frac{2}{\sqrt{n}}\left\|H_{l-1}^{*}\right\|_{F}\left\|W_{l}\right\|_{2}\leq
2(B+\epsilon)LM_{1}M_{2}\dfrac{\tau^{l-1}-1}{\tau-1}\qquad(\mbox{using
\lx@cref{creftype~refnum}{eq:pf-lem-pert-f-mpgnn-1}})$ $\displaystyle\leq
2(B+\epsilon)\beta^{l}\leq 2(B+\epsilon)\frac{\gamma}{2(B+\epsilon)}=\gamma,$

where
$\hat{G}=\arg\inf_{G^{\prime}\in\delta_{w}(G)}M\left(f_{w}\left(G^{\prime}\right),i,j\right)$
and $H_{l-1}^{*}$ is the corresponding node representation. Therefore, by the
definition, we always have $\hat{L}_{S,\gamma}\left(f_{w}\right)=1$ when
$\beta^{l}<\frac{\gamma}{2(B+\epsilon)}$.

Alternatively, if $\beta^{l}>\frac{\gamma\sqrt{m}}{2(B+\epsilon)}$, the term
inside the big-O notation in Equation 18 would be

$\displaystyle\sqrt{\frac{(B+\epsilon)^{2}\beta^{2l+2}l^{2}h\log(lh)\left\|w\right\|_{2}^{2}+\log(m/\delta)}{\gamma^{2}m}}$
$\displaystyle\geq\sqrt{\frac{l^{2}h\log(lh)\left(\left\|w\right\|_{2}^{2}/\zeta^{2}\right)+\log(m/\delta)}{4}}\geq
1,$

where the first inequality holds since $\beta^{2}\geq\zeta^{2}$ and the last
inequality holds since

$\displaystyle\left\|w\right\|_{2}^{2}\geq\min\left(\left\\{\left\|U_{i}\right\|_{F}^{2}\right\\}_{i=1}^{l-1},\left\\{\left\|W_{i}\right\|_{F}^{2}\right\\}_{i=1}^{l}\right)\geq\zeta^{2},$

and we typically choose $h\geq 2$ in practice and $l\geq 2$.
And note that the lower bound in Equation 19 ensures that Equation 17 holds
which in turn justifies the applicability of Lemma A.6.

Consider a covering set centered at
$C=\left\\{\tilde{\beta}_{1},\dots,\tilde{\beta}_{|C|}\right\\}$ of the
interval in Equation 19 with radius
$\frac{1}{l+2}\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}$, where $|C|$ is
the size of the set. To make sure that
$|\beta-\tilde{\beta}|\leq\frac{1}{l+2}\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}\leq\frac{1}{l+2}\beta$,
the minimal size of $C$ should be

$\displaystyle|C|=\frac{\left(\frac{\gamma\sqrt{m}}{2(B+\epsilon)}\right)^{1/l}-\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}}{\frac{2}{l+2}\left(\frac{\gamma}{2(B+\epsilon)}\right)^{1/l}}=\frac{l+2}{2}\left(m^{\frac{1}{2l}}-1\right).$

For a $\tilde{\beta}_{i}\in C$, we denote the event that Equation 18 holds for
$|\beta-\tilde{\beta}|\leq\frac{1}{l}\beta$ as $E_{i}$. Therefore, the
probability of the event that Equation 18 holds for any $\beta$ satisfying
Equation 19 is

$\displaystyle\mathbb{P}\left(\bigcap_{i=1}^{|C|}E_{i}\right)=1-\mathbb{P}\left(\bigcup_{i=1}^{|C|}\bar{E}_{i}\right)\geq
1-\sum_{i=1}^{|C|}\mathbb{P}\left\\{\bar{E}_{i}\right\\}\geq 1-|C|\delta,$

where $\bar{E}_{i}$ denotes the complement of $E_{i}$. Hence, let
$\delta^{\prime}=|C|\delta$, then we have that, with probability
$1-\delta^{\prime}$ and for all $w$,

$\displaystyle R_{\mathcal{D},0}\left(f_{w}\right)$
$\displaystyle\leq\hat{R}_{S,\gamma}\left(f_{w}\right)+\mathcal{O}\left(\sqrt{\frac{(B+\epsilon)^{2}\beta^{2l+2}l^{2}h\log(lh)\left\|w\right\|_{2}^{2}+\log(m/\delta)}{\gamma^{2}m}}\right)$
$\displaystyle\leq\hat{R}_{S,\gamma}\left(f_{w}\right)+\mathcal{O}\left(\sqrt{\frac{(B+\epsilon)^{2}\max\left\\{\zeta^{-1},\xi^{1/l}\right\\}^{2l+2}l^{2}h\log(lh)\left\|w\right\|_{2}^{2}+\log(m(l+2)/\delta^{\prime})}{\gamma^{2}m}}\right),$

where
$\zeta=\min\left(\left\\{\left\|U_{i}\right\|_{2}\right\\}_{i=1}^{l-1},\left\\{\left\|W_{i}\right\|_{2}\right\\}_{i=1}^{l}\right)$,
$\xi=LM_{1}M_{2}\dfrac{\tau^{l-1}-1}{\tau-1}$.

Case $\tau=1$ We now prove the case of $\tau=1$, which is similar to the case
of $\tau\neq 1$. Note that this case happens rarely in practice. We only
include it for the completeness of the analysis. Again let
$\beta=\max\left\\{\frac{1}{\zeta},\sqrt{LM_{1}M_{2}}\right\\}$. For now, let
us assume that we have a fix $\tilde{\beta}$ and consider $\beta$ which
satisfies $|\beta-\tilde{\beta}|\leq\frac{1}{4}\beta$. Note that this also
implies $\frac{1}{e}\beta^{3}\leq\tilde{\beta}^{3}\leq e\beta^{3}$. Based on
Lemma A.6, we have with probability at least $\frac{1}{2}$ over $\Delta w$,

$\displaystyle\left|R\left(f_{w+\Delta
w}\left(G\right),i,j\right)-R\left(f_{w}\left(G\right),i,j\right)\right|$
$\displaystyle\leq 2e(l+1)^{2}(B+\epsilon)LM_{1}M_{2}\frac{t}{\zeta}$
$\displaystyle\leq 2e(l+1)^{2}(B+\epsilon)\beta^{3}t$ $\displaystyle\leq
2e^{2}(l+1)^{2}(B+\epsilon)\tilde{\beta}^{3}\sigma\sqrt{2h\log(4(2l-1)h)}\leq\frac{\gamma}{2},$

where we set
$\sigma=\frac{\gamma}{4e^{2}(l+1)^{2}(B+\epsilon)\tilde{\beta}^{3}\sqrt{2h\log(4(2l-1)h)}}$
to get the last inequality. Note that Lemma A.6 also requires $\forall
i\in[l],\left\|U_{i}\right\|_{2}\leq\frac{1}{l}\left\|W_{i}\right\|_{2}$. The
requirement is satisfied if $\sigma\leq\frac{1}{\zeta
l\sqrt{2h\log(4(2l-1)h)}}$ which in turn can be satisfied if

$\displaystyle\frac{\gamma}{4e^{2}(l+1)^{2}(B+\epsilon)\tilde{\beta}^{3}\sqrt{2h\log(4(2l-1)h)}}\leq\frac{1}{\beta
l\sqrt{2h\log(4(2l-1)h)}},$ (20)

and one of the sufficient conditions is
$\frac{l\gamma}{4e(B+\epsilon)(l+1)^{2}}\leq\beta^{2}$. We will see how to
satisfy this condition later.

We now compute the KL term in the PAC-Bayes bound in Lemma 3.2. As defined
above, for a fixed $w$, the prior distribution $P=\mathcal{N}(0,\sigma^{2}I)$,
the posterior distribution $Q$ is the distribution of $\Delta w$ shifted by
$w$, that is, $Q=\mathcal{N}(w,\sigma^{2}I)$. Then we have,

$\displaystyle
KL\left(Q\|P\right)=\frac{\left\|w\right\|_{2}^{2}}{2\sigma^{2}}$
$\displaystyle=\frac{16e^{4}(l+1)^{4}(B+\epsilon)^{2}\tilde{\beta}^{6}2h\log(4(2l-1)h)}{2\gamma^{2}}\left(\sum_{i=1}^{l-1}\left\|U_{i}\right\|_{F}^{2}+\sum_{i=1}^{l}\left\|W_{i}\right\|_{F}^{2}\right)$
$\displaystyle\leq\mathcal{O}\left(\frac{(B+\epsilon)^{2}\beta^{6}(l+1)^{4}h\log(lh)}{\gamma^{2}}\left(\sum_{i=1}^{l-1}\left\|U_{i}\right\|_{F}^{2}+\sum_{i=1}^{l}\left\|W_{i}\right\|_{F}^{2}\right)\right).$

From Lemma 3.2, fixing any $\tilde{\beta}$, with probability $1-\delta$ and
for all $w$ such that $|\beta-\tilde{\beta}|\leq\frac{1}{4}\beta$, we have,

$\displaystyle
R_{\mathcal{D},0}\left(f_{w}\right)\leq\hat{R}_{S,\gamma}\left(f_{w}\right)+\mathcal{O}\left(\sqrt{\frac{(B+\epsilon)^{2}\beta^{6}(l+1)^{4}h\log(lh)\left\|w\right\|_{2}^{2}+\log(m/\delta)}{\gamma^{2}m}}\right).$
(21)

Finally, we need to consider multiple choices of $\tilde{\beta}$ so that for
any $\beta$, we can bound the generalization error like Equation 21. First, we
only need to consider values of $\beta$ in the following range,

$\displaystyle\sqrt{\frac{\gamma}{2(B+\epsilon)l}}\leq\beta\leq\sqrt{\frac{\gamma\sqrt{m}}{2(B+\epsilon)l}},$
(22)

since otherwise the bound holds trivially as
$R_{\mathcal{D},0}\left(f_{w}\right)\leq 1$ by definition. To see this, if
$\beta^{2}<\frac{\gamma}{2(B+\epsilon)l}$, then for any $(X,A)$ and any
$i,j\in[K]$, we have,

$\displaystyle\left|RM\left(f_{w}\left(G\right),i,j\right)\right|$
$\displaystyle=\left|\inf_{G^{\prime}\in\delta_{w}(G)}M\left(f_{w}\left(G^{\prime}\right),i,j\right)\right|=\left|M\left(f_{w}\left(\hat{G}\right),i,j\right)\right|$
$\displaystyle=\left|f_{w}\left(\hat{G}\right)_{i}-f_{w}\left(\hat{G}\right)_{j}\right|\leq
2\left|f_{w}\left(\hat{G}\right)_{i}\right|$ $\displaystyle\leq
2\left\|f_{w}\left(\hat{G}\right)\right\|_{2}=2\left\|\frac{1}{n}\bm{1}_{n}H_{l-1}^{*}W_{l}\right\|_{2}\leq
2\left\|\frac{1}{n}\bm{1}_{n}\right\|_{2}\left\|H_{l-1}^{*}W_{l}\right\|_{F}$
$\displaystyle\leq\frac{2}{\sqrt{n}}\left\|H_{l-1}^{*}\right\|_{F}\left\|W_{l}\right\|_{2}\leq
2(B+\epsilon)(l-1)LM_{1}M_{2}\leq 2(B+\epsilon)(l-1)\beta^{2}$
$\displaystyle\leq 2(B+\epsilon)(l-1)\frac{\gamma}{2(B+\epsilon)l}\leq\gamma,$

where
$\hat{G}=\arg\inf_{G^{\prime}\in\delta_{w}(G)}M\left(f_{w}\left(G^{\prime}\right),i,j\right)$
and $H_{l-1}^{*}$ is the corresponding node representation. Therefore, by the
definition, we always have $\hat{R}_{S,\gamma}\left(f_{w}\right)=1$ when
$\beta^{2}<\frac{\gamma}{2(B+\epsilon)l}$.

Alternatively, if $\beta^{2}>\frac{\gamma\sqrt{m}}{2(B+\epsilon)l}$, the term
inside the big-O notation in Equation 21 would be

$\displaystyle\sqrt{\frac{(B+\epsilon)^{2}\beta^{6}(l+1)^{4}h\log(lh)\left\|w\right\|_{2}^{2}+\log(m/\delta)}{\gamma^{2}m}}$
$\displaystyle\geq\sqrt{\frac{(l+1)^{4}h\log(lh)\beta^{2}\left\|w\right\|_{2}^{2}+\log(m/\delta)}{4l^{2}}}\geq
1,$

where the last inequality holds since

$\displaystyle\left\|w\right\|_{2}^{2}\geq\min\left(\left\\{\left\|U_{i}\right\|_{F}^{2}\right\\}_{i=1}^{l-1},\left\\{\left\|W_{i}\right\|_{F}^{2}\right\\}_{i=1}^{l}\right)\geq\zeta^{2},$

and we typically choose $h\geq 2$ in practice and $l\geq 2$.
And note that the lower bound in Equation 22 ensures that Equation 20 holds
which in turn justifies the applicability of Lemma A.6.

Consider a covering set
$C=\left\\{\tilde{\beta}_{1},\dots,\tilde{\beta}_{|C|}\right\\}$ of the
interval in Equation 22 with radius
$\frac{1}{4}\sqrt{\frac{\gamma}{2(B+\epsilon)l}}$, where $|C|$ is the size of
the set. To make sure that
$|\beta-\tilde{\beta}|\leq\frac{1}{4}\sqrt{\frac{\gamma}{2(B+\epsilon)l}}\leq\frac{1}{4}\beta$,
the minimal size of $C$ should be

$\displaystyle|C|=\frac{\sqrt{\frac{\gamma\sqrt{m}}{2(B+\epsilon)l}}-\sqrt{\frac{\gamma}{2(B+\epsilon)l}}}{\frac{2}{4}\sqrt{\frac{\gamma}{2(B+\epsilon)l}}}=2\left(m^{\frac{1}{4}}-1\right).$

For a $\tilde{\beta}_{i}\in C$, we denote the event that Equation 21 holds for
$|\beta-\tilde{\beta}|\leq\frac{1}{l}\beta$ as $E_{i}$. Therefore, the
probability of the event that Equation 21 holds for any $\beta$ satisfying
Equation 22 is

$\displaystyle\mathbb{P}\left(\bigcap_{i=1}^{|C|}E_{i}\right)=1-\mathbb{P}\left(\bigcup_{i=1}^{|C|}\bar{E}_{i}\right)\geq
1-\sum_{i=1}^{|C|}\mathbb{P}\left\\{\bar{E}_{i}\right\\}\geq 1-|C|\delta,$

where $\bar{E}_{i}$ denotes the complement of $E_{i}$. Hence, then we have
that, with probability $1-\delta$ and for all $w$,

$\displaystyle L_{\mathcal{D},0}\left(f_{w}\right)$
$\displaystyle\leq\hat{L}_{S,\gamma}\left(f_{w}\right)+\mathcal{O}\left(\sqrt{\frac{(B+\epsilon)^{2}\beta^{6}(l+1)^{4}h\log(lh)\left\|w\right\|_{2}^{2}+\log(m|C|/\delta)}{\gamma^{2}m}}\right)$
$\displaystyle\leq\hat{L}_{S,\gamma}\left(f_{w}\right)+\mathcal{O}\left(\sqrt{\frac{(B+\epsilon)^{2}\max\left\\{\zeta^{-6},\left(LM_{1}M_{2}\right)^{3}\right\\}(l+1)^{4}h\log(lh)\left\|w\right\|_{2}^{2}+\log(m/\delta)}{\gamma^{2}m}}\right).\qed$