Adversarial Robust Generalization of Graph Neural Networks
Authors: Chang Cao
Han Li
Yulong Wang
Rui Wu
Hong Chen
Venue: ICML 2025 poster (2025)
Keywords: Adversarial Learning
Graph Neural Networks
Primary area: theory->learning_theory
TL;DR: We establish an adversarial generalization bound of general GNNs via covering number analysis.

Abstract: While Graph Neural Networks (GNNs) have shown outstanding performance in node classification tasks, they are vulnerable to adversarial attacks, which are imperceptible changes to input samples. Adversarial training, as a widely used tool to enhance the adversarial robustness of GNNs, has presented remarkable effectiveness in node classification tasks. However, the generalization properties for explaining their behaviors remain not well understood from the theoretical viewpoint. To fill this gap, we develop a high probability generalization bound of general GNNs in adversarial learning through covering number analysis. We estimate the covering number of the GNN model class based on the entire perturbed feature matrix by constructing a cover for the perturbation set. Our results are generally applicable to a series of GNNs. We demonstrate their applicability by investigating the generalization performance of several popular GNN models under adversarial attacks, which reveal the architecture-related factors influencing the generalization gap. Our experimental results on benchmark datasets provide evidence that supports the established theoretical findings.

Adversarial Robust Generalization of Graph Neural Networks
Chang Cao Han Li
Yulong Wang" 12 Rui Wu Hong Chen 12
Abstract
susceptibility of GNNs adversarial attacks in node clas- sification tasks. These attacks are deliberately designed by the attackers to mislead the graph model's prediction, which significantly deteriorates the performance and applicabil- ity of GNNs in security-related domains (Zhang & Zitnik, 2020; Finkelshtein et al., 2022; Liu et al., 2023). Therefore, it crucial to enhance the adversarial robustness of GNNs for node classification tasks.
While Graph Neural Networks (GNNs) have shown outstanding performance in node classi- fication tasks, they are vulnerable to adversarial attacks, which are imperceptible changes to in- put samples. Adversarial training, a widely used tool to enhance the adversarial robustness of GNNs, has presented remarkable effectiveness in node classification tasks. However, the general- ization properties for explaining their behaviors remain not well understood from the theoretical viewpoint. To fill this gap, we develop a high probability generalization bound of general GNNs in adversarial learning through covering number analysis. We estimate the covering number of the GNN model class based on the entire perturbed feature matrix by constructing a cover for the per- turbation set. Our results are generally applicable to a series of GNNs. We demonstrate their ap- plicability by investigating the generalization per- formance of several popular GNN models under adversarial attacks, which reveal the architecture- related factors influencing the generalization gap. Our experimental results on benchmark datasets provide evidence that supports the established the- oretical findings.
One principal approach to learning robust models is adver- sarial training, which has proven to be powerful defense against adversarial attacks (Bai et al., 2021). Its core mech- anism is a min-max optimization problem by incorporating the adversarial samples that maximize the classification error into the training minimize the classification error (Goodfellow et al., 2014: 1: Madry al., 2019). The empirical advancements of adversarial training in the literature (Wang et al., 2020; Lin et al., 2023) prompt numerous studies to develop relevant theoretical analysis. However, generaliza- tion analysis in adversarial learning presents more obstacles as compared to its -on-aaveralaial counterpart, i.e., the non- smoothness of adversarial loss caused by the maximization operation in the min-max process (Bai et al., 2021). Previ- ous works mitigate the negative impact of hon-smoothness via restricted assumptions about losses or model functions (Awasthi et al., 2020; Gao & Wang, 2021; Xiao et al., 2022), or controlling the adversarial perturbation set (Mustafa et al., 2022). Since the aforementioned works are confined to non- graph data, this raises question of whether adversarial generalization can be extended graph learning.
1. Introduction
As powerful architectures for processing complex graph- structured data, GNNs have shown excellent performance in certain security scenarios (Yan et al., 2023), such malware detection (Liu et al., 2023; Gu et al., 2024), intrusion detec- tion (Zhou et al., 2021; Tran & Park, 2024), and blockchain (Cai et al., 2023; Seo et al., 2024). Despite their tremen- dous success, Zügner et al. (2018) first demonstrate the
Unlike non-graph data, each node in GNNs aggregates messages from its neighbor nodes through the message- passing mechanism. This causes the accessibility of pre- dictors to unlabeled samples in the test set during training (Oono & Suzuki, 2020), which results in the invalidation of previous analytical methods based on inductive learning (Günnemann, 2022: Mustafa al.. 2022). The informa- tion interaction of nodes also leads to the correlation of perturbations between different nodes, making the adver- sarial perturbation set of graph data different from that of non-graph data.
'College of Informatics, Huazhong Agricultural University, Wuhan 430070, China 'Engineering Research Center of Intelli- gent Technology for Agriculture, Ministry of Education, China Hoorizon Robotics, Haidian District, BeiJing 100190, China. Cor- respondence to: Han Li <lihan 125 @ mail. mai..hzau.eduu czu......
To overcome these difficulties, we explore the adversarial generalization of GNNs transductive settings by assessing the complexity of the adversarial loss function class through
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Adversarial Robust Generalization of Graph Neural Networks
Table I. Summary of generalization analysis of GNNs (m-number of training data, u-number of test data).
Reference
Under Attack
Learning Mode
Analysis Tool
Convergence Rate
Verma and Zhang (2019)
No
Inductive
Uniform stability
((1/vm)
Zhou and Wang (2021)
No
Inductive
Uniform stability
O
Garg et al. (2020)
No
Inductive
Rademacher complexity
O(1/vm)
Oono and Suzuki (2020)
No
Transductive
Rademacher complexity
O (max (1/xx(11/ (1/ym,
Esser et al. (2021)
No
Transductive
Rademacher complexity
O (max (1/ 1//mm//mm..mmmmm 1/
Tand and Liu (2023)
No
Transductive
Rademacher complexity
((11m + +1 1/u) +
Sun et al. (2024)
No
Transductive
PAC-Bayes
O m)
Ours
Yes
Transductive
Covering number
O (1/ Vmm 1/vu))
covering number. Our analysis exhibits broad applicabil- ity across wide range of GNNs and losses. Our findings provide theoretical support for the empirical success of ad- versarial training and offer valuable insights for training robust GNNs that generalize well. The key contributions are as follows.
views by adding perturbations to the input, thereby facilitat- ing adversarial training on the encoder. Kone et al. (2022) introduce Free Large-scale Adversarial Augmentation on Graph (FLAG), which augments node features for better performance under attack by iteratively adding gradient- based adversarial perturbations during training. Deng et al. (2023) propose Batch Virtual Adversarial Training (B (BVT)), which promotes output smoothness of GNNs by applying virtual adversarial perturbations to the nodes. Due to the effectiivnness of these empirical works in overcoming the vulnerability of GNNs against adversarial attacks, it is cru- cial to provide theoretical support for these advancements.
We derive the first proo-prbbbbilitt generalization bound of general GNNs in adversarial learning. Our analysis focuses on controlling the covering number of the whole feature matrix affected by the perturba- tion set, thereby achieving the complexity estimate of the adversarial loss. This addresses the key obstacles of extending the adversarial generalization to graph learning, caused by interactions between perturbations.
Generalization analysis of GNNs. Verma and Zhang (2019) first apply uniform stability on one-layer GCN to derive generalization bound. Zhou and Wang (2021) ex- tend their work to multi-layer GCNs and show a exponen- tially dependency of generalization on the number of lay- ers. Through the lens of Rademacher complexity, Garg et al. (2020) establish the first data-dependent generaliza- tion bound of message-passing passing GNNs; Oono and Suzuki (2020) provide generalization and optimization guarantees via boosting theory, and focus on a specific type of multi- scale GNNs; Esser et al. (2021) establish the generalization bound of GNNs in the semi-supervised transductive setting and demonstrate the effectiveness of residual connections in improving generalization of GNNs; Tang and Liu (2023) derive high probability bounds of several popular GNNs, including both linear and non-linear models. Moreover, Sun et al. (2024) develop a PAC-Bayesian bound for GNNs, which incorporates the interplay in the message passing mechanism. Table summarizes the related works on gen- eralization analysis of GNNs. Though the above studies cannot be directly extended to adversarial settings due to the maximization over the adversarial loss, they provide valu- able insights into the adversarial generalization analysis.
We conduct a comprehensive analysis on several pop- ular GNNs and derive the covering number bound of each perturbed GNN model. Our results indicate the relation between the adversarial perturbations and graph-based predictors, revealing the role of some GNN-related factors for reducing adversarial gener- alization, such as appropriate model architecture selec- tion, weight norm normalization, etc..
Based on our theoretical findings, we analyze and com- pare the key factors influencing generalization capabil- ity in adversarial learning, which is confirmed in our experimental evidence.
2. Related Work
Adversarial training on GNNS. To enhance the adversarial robustness of GNNs, Chen et al. (2020a) introduce Smooth- ing Adversarial Training (SAT), which improves GNNs' ro- bustness by reducing the amplitude of adversarial gradients. Jaeckle and Kumar (2021) propose a novel method called AdvGNN, which efficiently generates adversarial exam- ples by combining elements from both optimization-bart based attacks and generative methods. Yang, Zhang and Yang (2021) develop Graph Adversarial Self-supervised Learning (GASSL), which can automatically generate challenging
3. Preliminary
Given an undirected graph G = (A, with n nodes. where A paxn is the adjacency matrix and X
2

---

Adversarial Robust Generalization of Graph Neural Networks
(1...... Ø.] E Raxd contains n node features with d di- mensions. We consider transductive learning in our analy- sis, where the unlabeled test samples are available during training. Let S = {2; = (z), be the set of in- stances, where æ E X, E y and = E 2 = X x y A labeled training set Sm with size m is selected from randomly. The goal of transductive learning to pre- diet the labels of the samples in the test set Su, where m The empirical error over the training set Sm is denoted by Rf)
Nevertheless, measuring the complexity of Ladv directly is difficult due to the maximum operation on the adversarial loss function. By introducing statistical learning tools, we overcome this problem through the lens of covering number, which defined as follows.
Definition 3.1. (Mustafa et al., 2022) Let (A, D) be a metric space. Given a positive real number e, we say that C' C A is an (e, D) of A if
Di=1 {(fi(A X, W), and the population risk over the test set S,, is denoted by RA, (f) = + Dim++ ((f( X, W).k)) where W is the learning parameters, f F X + R" represents the out- put function with f-(.) denoting the prediction of each node feature 3,, and é E C FF + R is the loss function.
sup inf D(a, Se. aEA GEC
The covering number of A is the minimum cardinality of any subset that covers AA at scale e, denoted as M e). Given the dataset S, a function class & taking values in a real vector space, and an l, metric with p oc, we denote by (G, llco, S) the (c, ||- )-ooeerig number of the set G
However, by perturbing the imput samples and maximizing the loss, the adversary can mislead the classifier to make erroneous predictions (Huang et al., 2016). Given noise space B- = {ō: |00 < 0}. for any 8 E B, we assume that a set of adversarial nodes are generated from the neighbor As = {X ( ã;
ig 9}.
4. Main Results
x; + 8). The adversary create the worst case perturbation 8" E B from
In this section, we first investigate the complexity of the adversarial loss function class via covering number and derive general adversarial generalization bound of GNNs. Then we analyze the adversarial generalization properties of several classical GNNs.
X
arg max X, XEAr
where X"
| x and p = 2; + 8" To train a robust model, the goal of adversarial training is to minimize the following adversarial empirical risk
4.1. Generalization Analysis Over Adversarial Risk
To establish the generalization guarantee, we first make some mild assumptions that are easy to satisfy.
Rm (f) Σ max ())(A,X.W), XEAs
Assumption 4.1. For the model function ff and any node 2;, assume the following inequality holds for any d E B
which measures the performance of the predictor f under adversarial attacks defined above. To better understand the robust generalization of the model, we define the adversarial population risk
[f((8) f:(0')ll>= < K2 - 8'
8'
Assumption 4.2. For the loss function é and any node x;, assume the following inequality holds for any
R = Σ
max ((A(A, W),
((((())) ((IO) v:)l S C(IA(() M.))ooo.
1=M+1 XEAr
Remark 4.3. Assumption 4.1 1. is readily satisfied by a wide range of attacks (Awasthi al., 2020; Fan et al., 2021). where the Lipschitz constant K is determined by specific model architectures. Assumption 4.2 is mild assumption that can be satisfied by some common losses, such as cross- entropy loss and hinge loss.
which measures the ability of f to generalize unseen ad- versarial samples. In this paper, we focus on the adversarial generalization gap, which is denoted by
Gen (f) = RRm (f) Ru, (f)..
Results from learning theory (Bartlett & Mendelson, 2002) indicate that the generalization gap can be bounded by as- sessing the complexity of the adversarial loss class. Fol- lowing previous studies (Bartlett et al., 2017; Mustafa al., 2022), we provide the definition below
Then, we quantify the covering number of the adversarial loss class Ladv in an infinite space by presenting Lemma 4.4 as follows.
Lemma 4.4. Suppose Assumptions 4.1 and 4.2 hold. For any 8 E B, we define the loss class
Ladv := {z, + max XEAr
Lass == ((z,, 8) - [ ((A W) FEF)
3

---

Adversarial Robust Generalization of Graph Neural Networks
and the extended dataset S {1x 8, v.))) : E [m], 8 E CB}. where Cg is an (2 || -cover of B and X = [ + +o..... Cn + 0). The following inequality holds
m+ (m+a- mntt-1/2)[10- 1/2 mmaz(m)))) and co > 5.05. For any
f FEF, with probability of at least 1 1- 8, we have
4
24C
Gen(f) SQm,a + inf RS0
+ m +
vm + u
(Coouu -100 S) S &V((Lii 2. 2-1 -lo,
30K1 )
a "N(F, e, 1loo. S)de).
log
Remark 4.5. Lemma 4.4 enables us control the com- plexity of the adversarial loss class by the complexity of a constructed loss class, which is a finite discrete version of the former. Notably, we use | in the covering num- ber of Ladv. as the functions in Lade involve a maximum operation over B. This operation is eliminated in Late by controlling the complexity of the perturbation set, where each element in Lais is a function.
where Qm, = qooQi v min(m, w) + 2 2:02 In g. and
1 > 0 is a constant.
Remark 4.9. Theorem 4.8 establishes a GNN-dependent adversarial generalization bound in the context of transduc- tive inference. The term Qm,. inherently exhibit monotonic decrease at a rate of O (maxx /mm
1 ! V }) (Oono & Suzuki,
By utilizing a constructed finite loss class, the difficulty in measuring adversarial generalization caused by maxi- mization over the adversarial loss is solved. However, the interplay between the perturbed nodes introduces a further difficulty in the complexity estimate of Lais on 3, which is also the key challenge in measuring adversarial general- ization of GNNs, compared with previous works (Farnia & Ozdaglar, 2021; Mustafa et al., 2022). To address this issue, we split the task of estimating the complexity of the perturbed GNNs function class F on S by utilizing the con- structed perturbation cover set CB. We begin with fixing the perturbation 8 E Cg, and define the corresponding GNNs function class follows
2020; Esser et al., 2021). Compared with the non-robust generalization gap of GNNs (Tang & Liu, 2023), this bound remains another additional difficulty, i.e. the complexity es- timate of the perturbed model function class F. Considering the perturbed node features combined with the constructed perturbation d.. we conduct a comprehensive analysis of N N(F e, || ll S) for various GNNs, and the explicit char- acterizations will be discussed in the next section. Besides, we can observe that the perturbation budget 0 significantly impairs the capability of GNNs to generalize, which high- lights the importance of analyzing the factors influencing GNNs' adversarial robustness under theoretical guidance.
4.2. Adversarial Generalization Gap for GNNs
F = ((.; 8c) + (A W):8 E Cs).
In this part, for different GNNs, we derive the upper bounds of their covering number NVF, c, l| |l S) and Lipschitz constant K f. Three representative GNNs, including GCN, GCNII, and APPNP, are selected for analysis. To establish the generalization gap, we make some necessary assump- tions for L-layer GNNs first.
where X_ = [ + 8 ,,....,,y + 8c). Then, we step to the following lemma bound the covering number of Lais on S.
Lemma 4.6. Given the function classes fass and F be defined above. Suppose Assumptions 4.1 and 4.2 hold. The following inequality holds
Assumption 4.10. For the activation function a-(-) of layer E [1, T.) and any vector æ. assume the following inequality holds
(C (.1. 5 60CcK f NI 20,11 11.1oo.. S).
[1x((x) or (z0) S p:ll0 - x' a'1loo.
Remark 4.7. Lemma 4.6 overcomes the key difficulty of estimating the covering number of the finite adversarial loss class Laig on S by additionally incorporating the fixed perturbation & E Cg into analysis. We find that the spe- cial mechanism of GNNs induces the interaction between the perturbed nodes, compared with neural networks, thus resulting in additional term affected by the GNNs archi- tecture and perturbation budget.
Assumption 4.11. For any input feature æi, assume that |asl|a 5 b holds.
Assumption 4.12, For the weight matrix W -W where W, xdd1 (dg = d and dr. = (2],, assume that WWlloo S w, holds.
Remark 4.13. Many commonly used activation functions satisfy Assumption 4.10, such as Sigmoid, Tanh, and ELU (Exponential Linear Unit). Assumption 4.1 1 can be satisfied by applying a normalization operation on the input feature, which is demonstrated to help reduce the generalization gap (Verma & Zhang, 2019; Tang & Liu, 2023). The require- ment that learning weights remain bounded during training
Now we can obtain the adversarial generalization gap below.
Theorem 4.8. Suppose Assumptions 4.1 and 4.2 hold. Let F : Raxd + Rn be the GNNs function class taking values 4.. Let Q1 : m Q2 =
4

---

Adversarial Robust Generalization of Graph Neural Networks
in Assumption 4.12 is commonly observed in generalization analysis (Garg et al., 2020; Cong et al., 2021).
improved propagation scheme based on personalized PageRank. This approach constructs simple model that utilizes large and adjustable neighborhood for node classi- fication, which avoids the poor performance of GCN caused by more aggregation steps or more layers. The output func- tion of a L-layer APPNP model is
Next, we analyze the upper bounds of the generalization error of the following model, respectively.
GCN. Kipf and Welling (2016) propose an efficient layer- wise propagation rule to learn node-level representations, which encodes the node features in a way useful for semi- supervised classification learning. The output function of a L-layer GCN model
[(A, W)
or. Tr A 0 (W 1- 111 1-2
where ((A) - (11 (1->)) (4))
X, W)
K is the aggregation hop and y is probability, which is designed to adjust the size of the neighborhood influencing each node.
(000 -0000--000))..010((1111111111111 ()(())XW.)) W.).
where (AA E Rux= is the graph filter. Three types of filters are introduced in this paper, such as the unnormalized filter with self-loops g (AA = A + I (Xu et al., 2018), the symmetric normalized filter (A) = (D- - I) [A + T) + r)-1/2 (Kipf& & Welling, 2016), and the random walk filter ((A) = (D 1)- (A+ I) (Zhang et al., 2019).
Proposition 4.16. With probability of at least 1 - 6, the following inequality holds
4
Gen(f) SQmaa +
m m u
T2C₂ Vm+u
(VdOKAPPNP- - -ubgr II p:wr) [=1
L-1
DE RRXn is the degree matrix of graph G, where Dū- Ei=1 Ag-
where 9 = [1)(o) S >1 + ((1-7)9) and KAPPNr = Ceupa. I PEWr- Quna is as stated in Theorem 4.8. The defimitions bf g and are the same in Proposition 4.14.
KK-1 ((1 - >)9)* + 2
Proposition 4.14. With probability of at least - 8, the following inequality holds
4
Gfn 5Qm.+ + m +
72C₂
I (Vil + obgi. II pews):
Remark 4.17. Compared to the generalization gap of GCN, the main difference of the bound in Proposition 4. 16 lies in the treatment of graph filters. We find that the probability 7 E (0, 1) is set as small number, and the graph filter g( A) is symmetric normalized, which yields that 9 S 9 S gf (Gasteiger et al., 2018). Therefore, APPNP could achieve a better generalization performance than GCN. Moreover, as a higher probability y could improve the convergence speed and benefit the generalization, such a large size of the neighborhood would lead to a rapid performance degrada- tion (Gasteiger al., 2018). The neighborhood structures vary across different types of graphs (Grover & Leskovec, 2016; Abu-EI-Haija et al., 2020), which has a significant impact on the selection of the parameter 7. Hence, it is crucial to carefully adjust the parameters "y and K to guar- antee a trade-off between the generalization behavior and representation ability.
+ Vm+ +
where y (l)( KOeN = Ceg IT pewsr b= b + /d0, and v ...x(d,,........) Qm,u is as stated in Theorem 4.8.
Remark 4.15. It's clear that the perturbation budget f in the first term dd0 KGEN would deteriorate the generalization performance of GCN, where a higher dimensional feature could exacerbate this adverse effect. Thus, smaller perturbation budget 0 could reduce the dependence of ad- versarial generalization on d. Moreover, for the unnormal- ized filter, for fixed i E [n] and any j E [n]. we have (l)() S amaz + 1, where dmaa denotes the maximum degrees. For the symmetric normalized filter and random walk filter, [A) S V(ddaa + 1)/(dmms + 1). where dmin denotes the minimum degrees. This motivates apply- ing normalized graph filters with an appropriate number of layers to achieve the generalization ability, which is consis- tent with the empirical findings (Kipf& & Welling, 2016; Li et al., 2018). Furthermore, the Lipschitz constant Pt = is usually satisfied while the activation function is selected properly. Thus, we can mitigate the performance loss caused by the product of weight constraints by applying regulariza- tion to the weights.
GCNIL Although combing the shallow graph neural net- works and deep propagation, Chen et al. (2020b) consider APPNP losing the powerful expression ability of deep non- linear architectures. GCNII is proposed to alleviate the over- smoothing in the deep graph model by using two simple techniques, initial residual connection and identity mapping, which enables GCN to express the high-order polynomial filter with arbitrary coefficients. For I [1...., L 1). the propagation process
APPNP. Considering the limitations of the propagation pro- cedure for node classification, Gasteiger et al. (2018) derive
H' ar ( (1-(((1))))))) ((0-)))(A)H²+- + + (o
5

---

In this section, we propose an adversarial training algorithm to learn robust GNNs based on our theoretical findings, and Adversarial Robust Generalization of Graph Neural Networks
Table 2. Details of the adopted datasets.
Dataset
Nodes
Edges
Features
Classes
Training
Validation
Test
Citeseer
3327
9104
3703
20 per class
500
1000
Cora
2708
10556
1433
77
20 per class
500
1000
Pubmed
19717
88648
500
3
20 per class
500
1000
DBLP
17716
105734
1639
20 per class
30 per class
Rest
CS 18333
163788
6805
15
20 per class
30 per class
Rest
CoraFull
19793
126842
8710
70
20 per class
30 per class
Rest
where Hº oo(XWo)) o). de (W,)
(1- +WW.)
Algorithm Train a robust graph model
and a, , E (0, 1). The output function of a L-layer GCNII
1: Input: Graph G, dataset S, perturbation budget 0, regu- larization parameter X, initialization Wo, learning rate
model is fA,, W) = = LL).
7). number of iterations T.
Proposition 4.18. With probability of at least 8, the
2: while 1. < T do
following inequality holds
3:
S S 0.
Gen(f) S Qm,u +
4:
for i = 1,2..
do
m + u
5:
For the input matrix X; = [ri,t) kn.t) perturb
72Cr
X, + X, + A(X,, A,
(Vd0 + vbg Σ T3 II prw));
vm +u
6: For each node in X, = [a1. kn append {( vi, to S. and choose samples ran- domly to the training set Sm,e. end for
(=j
where ii < 3
Burr and
1.
KoCNn Cepouo
((11a))))
II
pewer
Define new objective L(W..) vn Ex,, {(Ex((A X, W), Vr,r) + Aeloo, For all E [m], update W; using SGD:
5=1
(=h-j
1. T; =2 =2
((1 a))) (11 aAA),
W W + Wt, 14a-177 -V.L..........
1=0
10: end while
11: Output: WT
Ap uo a)1
II pe t=p-j
Qma is as stated in Theorem 4.8. The definitions of 6, g and v are the same as in Proposition 4. 14.
validate our theoretical results by evaluating the effect of several factors.
Remark 4.19. According to Proposition 4.18, the perfor- mance of GCNII is mainly related to the choice of a and 3. a is usually set as a small number to avoid the performance drop if we stack many layers, as the final representation of each node retains at least fraction of from the input feature (Chen et al., 2020b). However, it is noteworthy that the impact of and L on generalization is closely relevant to (g(A)) ol. A deep model with smaller a and an unnor- malized filter would lead to worse generalization. Moreover, 3 ensures at least the same performance between a deep model and its shallow version (He et al., 2016). By setting 3 relatively small and imposing regularization on the weight can obtain a small weight norm, which is particularly useful to avoid overfitting as well as enhance the generalization.
Experimental Setup. We adopt six benchmark datasets provided by PyToorch Geometric, including Citeseer, Cora, Pubmed, DBLP, CS, and CoraFull (see Table 2 for more details). We evaluate the performance of three popular GNN models: GCN, GCNII, and APPNP. Let A be gradient- based attack algorithm (e.g.. PGD, BIM, Mettack). We present our robust learning method in Algorithm 1. During the training procedure, adversarial examples are generated by PGD algorithm (Bottou, 2010) with step size of 0/128, where 0 is the perturbation budget. We set training iterations T as 200 and use cross-entropy loss for training. SGD is adopted for optimization with its learning rate 7) set by 0.05 and a weight decay of 1e-3. The regularization parameter is fixed to 0. The generalization gap approximated by the following accuracy gap based on adversarial training
5. Experiments
Jadversarial train accuracy -auuuuccyyaavesariaaaa adversarial test accuracy|,
which is the absolute difference between the accuracy on
6

---

Adversarial Robust Generalization of Graph Neural Networks
q:0
Geveralzzaiin C
q:0 q00.0
q-0
q0000
00.00
Geneaalizatoon Cap
q=000
0=000
Gonvalizztion
0.23
0.38
0.36
Figure 1. The generalization gap for different adversarial perturbations with increased number of layers L (on Cora).
Citeseer
Pubredd
CoraFull
g-6.1
g--01
9-011
9-0.3
Genrrllizaiin Gapp
Cebartlittioon Gap
g-05
Ceneraliation
0.5-
0.30
(a) Experiments of adversarial training for APPNP
Puhree
CoraFull
-0.
Generlizaain CHRR
m0.
m0
-0.3
P048
-003
Ganer albaattoonn Cap
0.55
Ganzallzztion
0.30-
0.30
0.88
0.00
0006
0/D4
0.08
0.000
0006
(b) Experiments of adversarial training for GCNII
Figure 2. The generalization gap for different hyper-parameter y in APPNP and in GCNII with increased perturbations A.
Clieseer
Pubned
CoraFull
Geveraltzatonn Gap Gap
Gap
Generaiization Gap
0L40
APPN
GCNI
0.32
GCNI
GUNI
0.30
0.44
0.80
0.20
600
00066
0.000
0U026
6100
[M03
GU166
04024
Figure 3, The generalization gap for different GNN models with increased perturbations 6.
GCN
APPNP
CONI
Gavralizaton
0.35
(24)/C44))
diczeeiiiiiinnn Gap
(3-4 (p44)
Genralizatonn Cap
0.35
(3+ Pia 400>a)
(D4b (w40)
0.32
0.32
0.30
0.20
0.000
0.008
0.066
0424
0.000
0.088
0.86
0.26
0.000
0.088
0001
01144
Figure 4. The generalization gap for different graph filters g (A) with increased perturhations 0 (on Cora).

---

Adversarial Robust Generalization of Graph Neural Networks
d
0.30
Gearalizzalon Gap
Gazralization aabraalzatoon Cap
Geuzralization
0.24-
0.24
n.2-
0.00
Figure 5. The generalization gap for different input feature dimension df with increased perturbations 0 (on Cora).
APPNP
GCNI
=0
-0
=0.1
Gezzalizedim Cop
-0.
Dentrallattonn Gap
-0.1
Generalictionn
I.24.
0.31
0.3
60066
Figure The generalization gap for different regularization parameter with increased perturbations (on Cora).
training and test data.
I) and (D + 1)= own better gener- alization performance than the unnormalized filter A + I.
We repeat each experiment 10 times and report the mean value and standard deviation for output. For more detailed model configuration and experimental results (including results of other datasets, other attack methods, and other influencing factors assessment), please refer to Appendix F.
Feature dimension. As shown in Figure 5, it clear that the generalization error with a lower input feature has a better generalization performance, which is consistent with our theoretical analysis as stated in Proposition 1.
Number of layers. For GCN, Figure reveals that the gap increases as the model gets deeper, which aligns with our theoretical results. And affected by the superposition of the increased nonlinear operations, APPNP performs worse with the higher model depth. However, as stated Propo- sition 4.18, the parameter could adjust the proportion of parameters in deeper layers. The generalization gap of GC- NII presents a slow decreasing trend, which demonstrates its superior performance in a deep version.
Regularization parameter. Our theoretical results show that the product of the norm weights deteriorates the gener- alization, especially when we stack more layers. Figure demonstrates that norm regularization facilitates the adver- sarial generalization of GNNs.
6. Conclusion
In this paper. we establish an adversarial generalization bound of GNNs in the context transductive learning, providing theoretical support to the empirical advancements of adversarial training. Our approach is modular and easily applicable to a wide range of GNN models. We further showcase our results of generalization analysis on three representative cases (GCN, APPNP, and GCNII), which are validated in our experimental results.
Model architecture. According to Proposition 4.16, rel- atively bigger 7 could help reduce the adversarial gener- alization gap, especially when [l)( of the unnormal- stated in
ized filter is much bigger than 1. Similarly, Proposition 4. 18,, little bigger benefits the adversarial generalization in deep GCNII model. Figure 2 shows the results of different hyper-parameed GCNII, which exhibit a similar trend. Moreover, Figure? 3 shows that GCNII and APPNP have a smaller generalization gap than GCN, which demonstrates the effectiveness of the improved model architectures.
in APPNP and in
In future work, we consider extending our result to an opti- mistic fast-rate bound for smooth assumption of the loss. As the graph topology is vulnerable to adversarial attacks (Li al., 2022), adversarial generalization analysis against structural perturbations will be future exploration. The detailed discussions about the extension of our work to topology attacks are included in Appendix E.
Graph filter. The theoretical results demonstrate that the unnormalized filter hurts the adversarial generalization due to the exponential dependence on model depth. As is shown in Figure 4, the two normalized filters (D 1/
8

---

Adversarial Robust Generalization of Graph Neural Networks
Impact Statement
Cong, W., Ramezani, M., and Mahdavi, M. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34: 9936 9936-9949, 2021.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Deng. Z., Dong, Y., and Zhu, Batch virtual adversarial training for graph convolutional networks. Al Open, 73-79, 2023.
Acknowledgments
This work was supported by the National Natural Sci- ence Foundation of China (under Grant Nos. 62276111 62076041, 62376104, 12426512), and the Open Research Fund of Engineering Research Center of Intelligent Technol- ogy for Agrieulture, Ministry of Education (No. ERCITA- KF002).
EI- Yaniv, R. and Pechyony, D. Transductive rademacher complexity and its applications. Journal of Artificial Intelligence Reseurch, 35:193-234, 2009.
Esser, P., Chennuru Vankadara, L., and Ghoshdastidar, D. Learning theory can (sometimes) explain generalisation in graph neural networks. Advances in Neural Informa- tion Processing Systems, 34:27043 -20066,,27666.- 2021.
References
Fan, L., Liu, S., Chen, P.-Y., Zhang, G., and Gan, C. When does contrastive learning preserve adversarial robustness from pretraining to finetuning?, 2021. URL https:
Abu-EI-Haija, S., Kapoor, A., Perozzi, B., and Lee, J. N-gen: Multi-scale graph convolution for semi-supervised node classification. In uncertainty in artificial intelligence, pp. 841-851, PMLR, 2020.
/ //arxivv.o.. ort.//rggs///... hatp//ass//111111 211/. 01124.
Farnia, and Ozdaglar, A. Train simultaneously, generalize better: Stability of gradient- based minimax learners. In International Conference on Machine Learning, pp. 3174 3185. PMLR, 2021.
Awasthi, P., Frank, N., and Mohri, M. Adversarial learn- ing guarantees for linear hypotheses and neural net- works, 2020. URL 2004. 13617.
//tpxvaaxvvv///////a//e/////aa org/ /bs/
Finkelshtein, B., Baskin, C., Zheltonozhskii, E., and Alon, U. Single-node attacks for fooling graph neural networks. Neurocomputinng 513:1-12, 2022.
Bai, T., Luo, J., Zhao, J., Wen, B., and Wang, Q. Recent advances in adversarial training for adversarial robustness. arXiv preprint arXiv:2102.0133:
2021.
Gao, Q. and Wang, X. Theoretical investigation of gener- alization bounds for adversarial learning of deep neural networks. Journal of Statistical Theory and Practice, 15 (2):51, 2021.
Bartlett, P. L. and Mendelson, S. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-44 482, 2002.
Bartlett, L., Foster, D. J., and Telgarsky, M. Spectrally- normalized margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Garg, V., Jegelka. S., and Jaakkola, T. Generalization and representational limits of graph neural networks. In In- ternational Conference on Machine Learning, pp. 3419- 3430. PMLR, 2020.
Bottou, L.. Large-scale machine learning with stochastic gradient descent. Proc. of COMPSTAT, 01 2010. doi: 7-1199978--770--2644
Gasteiger, J., Bojchevski, A., and Günnemann, S. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint
2018.
Cai, J., Liang, W., Li, X., Li, K., Gui, Z., and Khan, M. K. Gtxchain: A secure iot smart blockchain architecture based graph neural network. IEEE Internet of Things Journal, 2023.
Goodfellow, J., Shlens, J., and Szegedy, C. Explain- ing and harnessing adversarial examples. arXiv preprint arXiv: 1412.5572, 2014.
Chen, J., Lin, X., Xiong, H., Wu, Y., Zheng, H., and Xuan, Q. Smoothing adversarial training for gnn. IEEE Trans- actions Computational Social Systems, 8(3):618-66) 2020a.
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explaining and harnessing adversarial adverssil examples, 2015. URL https: //arxiv. faazxiv..rrg/bs//411222 6572.
Grover, A. and Leskovec, J. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discov- ery and data mining, pp. 855-864, 2016.
Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y. Simple and deep graph convolutional networks, 2020b. URL https:://rrxx htgg/bbs/00/ 02133.

---

Adversarial Robust Generalization of Graph Neural Networks
Gu, J., Zhu, H., Han, Z., Li, X., and Zhao, Gsedroid: Gnn-based android malware detection framework using lightweight semantic embedding. Computers & Seccurity, 140:103807 2024.
Madry, A., Makelov, A., Schmidt, L.., Tsipras, D., and
Vladu, A. Towards deep learning models resistant to ad- versarial attacks, 2019. URL abs/ 1700606083.
Günnemann, S. Graph neural networks: Adversarial robust- ness. Graph neural networks: foundations, frontiers, and applications, pp. 149-176, 2022.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- tions of machine learning. MIT press, 2018.
Mustafa, W., Lei, Y., and Kloft, M. On the generalization analysis of adversarial learning. In International Con- ference on Machine Learning, pp. 16174-16196. PMLR, 2022.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Huang, R., Xu, B., Schuurmans, D., and Szepesvari, C. Learning with a strong adversary, 2016. URL https: //arxiv... org/ abs/ /1111. 03034.
Oono, K. and Suzuki, Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. Ad- vances Neural Information Processing Systems, 33: 18917-18930, 2020.
Jaeckle, F. and Kumar, M. P. Generating adversarial ex- amples with graph neural networks. Uncertainty in artificial intelligence, pp. 1556-1564. PMLR, 2021.
Seo, M., Kim, J., You, M., Shin, S., and Kim, J. gshock: A gnn-based fingerprinting system for permissioned blockchain networks over encrypted channels. IEEE Ac- cess, 2024.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint arXiv: 1609,02907, 2016.
Sun, J., Li, K., Chen, R., LI, J., Wu, C., Ding, Y., and Yan, J. InterpGNN: Understand and improve general- ization ability of transdutive GNNs through the lens of interplay between train and test nodes. The Twelfth International Conference on Learning Representations, 2024. URL https: /opnnreviww net fer/mmorm id id-pwW807PH WWW.W//0WJJG
Kong, K., Li, G., Ding, M., Wu, Z., Zhu, C., Ghanem, B., Taylor, G., and Goldstein, Robust optimization as data augmentation for large-scale graphs. Proceedings of the IEEE/CVF Conference on Computer Vision and Pullern Recognition, pp. 60-69, 2022.
Kurakin, A., Goodfellow, I., and Bengio, Adversarial examples in the physical world, 2017. URL https: //arxiv. org. abs/ 607. 02533.
Tang, H. and Liu, Y. Towards understanding generalization of graph neural networks. In International Conference on Machine Learning,
Li, J., Peng. J., Chen, L., Zheng, Z.. Liang. T., and Ling, Q. Spectral adversarial training for robust graph neural network. IEEE Transactions on Knowledge and Data Engineering, 35(9):9240-9253. 2022.
33677-33719, PMLR, 2023.
Tran, D.-H. and Park, M. Fn-gnn: A novel graph embedding approach for enhancing graph neural networks in network intrusion detection systems. Applied Sciences, 14(16): 6932, 2024.
Li, Q. Han, Z. and Wu, X.-M. Deeper insights into graph convolutional networks for supervisd leamn- ing, 2018. URL httpsttss//axxxi..ooo org/ abs/101 07606.
Tu, Z., Zhang, J., and Tao, D. Theoretical analysis of ad- versarial learning: minimax approach. Advances in Neural Information Processing Systems, 32, 2019.
Lin, X., Zhou, C.. Wu, J., Yang. H., Wang, H., Cao, Y., and Wang, B. Exploratory adversarial attacks on graph neural networks for sepe-sspe node classification. Pattern Recognition, 133: 109042, 2023.
Verma, S. and Zhang, Z.-L. Stability and generalization of graph convolutional neural networks. In Proceedings the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1539-1548, 2019.
Liu, T., Li. Z., Long, H., and Bilal, A. Nt-gnn: Network traffic graph for 5g mobile iot android malware detection. Electronics, 12(4))789, 2023.
Wang. Y., Zou, D., Yi, J., Bailey, J., Ma, X., and Gu, Q. Improving adversarial robustness requires revisit- ing misclassified examples. International Confer- ence on Learning Representations, 2020. URL https: / /ppenrevieww net forum?
Long, P. M. and Sedghi, H. Size-free generalization bounds for convolutional neural networks. CoRR, 12600, 2019. URL http:://axxi org//
10

---

Adversarial Robust Generalization of Graph Neural Networks
Xiao, Fan, Y., Sun, R., Wang, J., and Luo, Z.-Q. Stability analysis and generalization bounds of adversarial training. Advances in Neural Information Processing Systems, 35: 15446-15459, 2022.
Xing. Y., Song, Q. and Cheng, G. On the algorithmic stability of adversarial training. Advances neural infor- mation processing systems, 34:26523-26535, 2021.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? arXiv preprint arXiv: 1810. 00826, 2018.
Yan, B., Yang, C., Shi, C., Fang, Li, Q., Ye, Y., and
Du, J. Graph mining cybersecurity: A survey. ACM
Transactions on Knowledge Discovery from Data, 18(2):
1-52, November 2023. ISSN 1556-472X.
doi: 10.1145/
3610228. URL http: dx doi or1.10..110111555 3610228.
Yang. L., Zhang, L., and Yang, W. Graph adversarial self- supervised learning. Advances in Neural Information Processing Systems, (11488-11499) 2021.
Yin, D., Ramchandran, K., and Bartlett, Rademacher complexity for adversarially robust generalization, 2020. URL https: arxiv. wwg. aww//ssss1 11914.
Zhang. X. and Zitnik, M. Gnnguard: Defending graph
neural networks against adversarial attacks. Advances in neural information processing systems, 33:9263 9275, 2020.
Zhang, Z., Chen, D., Wang. J., Bai, L., and Hancock, E. R. Quantum-bart based subgraph convolutional neural networks. Pattern Recognition, 88:38 49, 2019.
Zhou, X. and Wang, H. The generalization error of graph convolutional networks may enlarge with more layers. Neurocomputing, 424:97-106, 2021. 2021.
Zhou, X., Liang, W., Li, W., Yan, K., Shimizu, S., Kevin, I., and Wang, K. Hierarchical adversarial attacks against traph--nurallneewwr--bee
iot network intrusion detec- tion system. IEEE Internet of Things Journal, 912)): 9310-9319, 2021.
Zügnnrr, D., Akbarnejad, A., and Günnemano, S. Adversarial attacks on neural networks for graph data. In Proceed- ings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2847-2856, 2018.

---

Adversarial Robust Generalization of Graph Neural Networks
A. Notations
The main notations this paper are summarized Table
Table 3. Summary of main notations involved in this paper
Notations
Descriptions
A
The adjacency matrix, where A E R
X
The node (input) feature matrix, where X E RRad The degree matrix with Di,; = Ej Ai, The graph filter of G, where g(A) E Raxx
D
((A)
W
The learning parameters of GNNs, where W = (We)e) The output function of GNNs The node feature and node label
((A,X,W)
(A, X, W))3))
The loss function
6.0
The perturbations and perturbation budget
B
The noise space {ō ||0||cc S {}}
As
Rx). The set of adversarial nodes {X 2............ = The adversarial loss function The training dataset and the extended training dataset with the perturbations The adversarial empirical (population) risk of the adversarial loss function The generalization error in the adversarial settings
+ 6, i [n]]
max XEAS
max
S
Rm( Rn(
Gen(J)
Cs
The cover of the noise set B
8, 8.
An arbitrary and fixed perturbations in the cover set Cs The model function class with the fixed perturbation ò The covering number of perturbed function class f at scale with an Ex metric The norm constraints of 2 and |
f
u(FFe, e, lloo,, S)
6.6
Cy, Ky, and Pr.
The Lipschitz constants of the loss function, output function, and activation function the norm constraint of the t-th layer's weight W.
wt
||0|| Ex, |zz1
The l norm of vector The foo norm of vector The infinity norm of matrix X
| 30 max Σ, |r,1
X oloc max E, Xayl
B. Proof of Main Results
B.I. Generalization for GNNs
As discussed in the main test, the main challenges in deriving the adversarial generalization bound for GNNs (Theorem 4.8) can be handled by Lemma 4.4 and Lemma 4.6. Followed by Mustafa, Lei, and Kloft (2022), we first present the proofs of Lemma 4.4, which controls the covering number of the adversarial loss class of GNNs through covered perturbation class.
Proof of Lemma 4.4. For each function f E F and a fixed d, E B, we construct a new function h 2 + (R as h(z,, 5.) (AfiAAX.... W). where X. [x] se,.................. ......... En 8e). The corresponding function class is
4= [z. E(L(A, W). v.) EF.
(1)
Recalling the adversarial loss class Ladv; let maxses (12,, 8) max maxxEAs ((f(A,, W), yi) for any B. In this
12

---

Adversarial Robust Generalization of Graph Neural Networks
part, we the cover elements of the constructed class L on dataset S build cover for the adversarial loss function class Ladv the same dataset S. Recall from the definition MaatWW(aadts 6, loo: S) is the cover for
Loduls := {{ mmxxh(z) 8).....
max h (zn 8))} c R..
8EB
First we construct an 2o cover for Laduls Is by utilizing an - for
Cls = ( (z), ((,,,..,,,,,,........... M(zn,60) d c (RK"),
which is VV 1loo, in definition. The cover of L of size Ne is denoted by
Cc = (c:6( (((.)) : jE [Nel] c (RR9)"
Then we can obtain the cover of Ludol s as
Clade = { := max (8).
max
maxe)((0) (6) :j :jE [Ncl] CR.
dEB
DEB
We have
max rE[n] BEB
max h(z,, 8) E (E[n]
max
max meaxh(z:) (zz max c,(()) BEB
max max (1(z,, 8) c,(08] Se. S
dEB
NE ml dEB
where the first equality is based on the construction of Creav. the first inequality follows from the inequality maxx f(xx) max [x))| & maxe (xx) - g(x)), and the last inequality is based on the covering number of C. LLasll, we have
W(Lade 1.1 l,,, S <C, e, S).
Now we control the complexity of the adversarial loss class. However, there is still a difficulty in deriving the upper bound of o (4, S), the functions in L take values in infiniteddimensional vector space. We approximate the space by finite discretization version solve this problem, where the function class of the discrete version is defined by
Lais := ((2,, 5) - E(f(A, W), v:): f F).
(2)
In this part, the target is control the covering number of the infinite-dimensiona class L with the finite-dimensional counterpart Lais. To approximate the functions h with discrete form, we construct an k/2C,Ky for set B
Cs = {8 j [Na]] C B,
where Ng is the size of the cover Cg. Let the function class and Lass be defined in Equation (1) and (2) respectively. Let the extended dataset be expressed by S = {xx,, 8, yi) i [n], 8 CB}. Our goal is construct an e-cover of by utilizing c/2-cover of Ldis. According to the set Cg, have
Laiss = { ( M ... ... Mizz, ((znz0)).... 81).... ..... C......,,(.,,, M22n, dNe))} c No
e, 1) is defined as an e/2-cover for Catelg of size Nea. which is denoted by
Caa. = ((0 ((,...... : [NVaaul] C 1R
Next, we construct a cover of Lls. The key idea is to construct functions (8) where j E [Neaul is a piece-wise constant around each ò E Cg. Let
Ce = { (c)()) = (arg min ||ō - (6)
(6) : 27 (arg min 115- 81)) : EEl (Ncc...) E (R05²² SECs
dECs
13

---

Adversarial Robust Generalization of Graph Neural Networks
be an e-cover of L. Therefore, we have
max max 11(2;; 8) (8)
8 8EB
max max [1 8) 11(22, 6*) )- - 11,2,, - 28)
6EB
(1( 6) -(zz,, 00) + (1 8¹) - cz -6(6)))
S max max dEB
< max max dEB
[1(z;, 6) 10 8*)) + max max (1 8) e (8))
dECB
< max max , 8" max max (z, 8) ()), BEB
SECs
<C;Kye/2CrK) + c/2
where 8" arg min ||ō - 51l. The first inequality follows from triangle inequality. The second inequality is followed by the construction of Cg, such that (6) = oj (5"). The third inequality is based on the Lipschitz properties of the loss function with respect to 8. The last inequality is based on the construction of 8* and Caa.. Then we can obtain
N(C,,, ||. 11,., S) S N e/2,1 1o., S),
which concludes that
WC 1.1 l). 5): (1x, s &N(aiis c/2, lo.
Now we finish the proofs of Lemma 4.4.
Lemma 4.4 utilizes the construction of covering number to control the complexity of Lade, thus removing the maximization on the adversarial loss, which is the first challenge of our work. The second challenge comes from the estimating of the covering number of Lais based the extended dataset S. Inspired by Bartlett et al. (2017), we break the task of covering whole function class F on S into cover term of the first layer and other cover terms for the layers' weights. We proceed with the proofs as follows.
proof of Lemma 4.6. Firstly, based on Assumption 4.2 and Lemma C.I, we have
max {(i(A, w) max ((F(A, W)), W),
CI
X
X
By the definition of covering number, we can obtain
N(Liiss c/2,1 1), F, 8) S N( c/202, || (),
where ă = max E.,, ((A(A, X, W;) and = ((2,, - f( X W) 8 E Cs}. To decompose the covering number of function class FF. under dataset S, we construct covers Es and En of the initial layer and the rest layers, respectively, where the cover of the first part depends on the cardinality of Cs, and covers of the rest parts depend on each choice [W1.... 3. To facilitate our analysis, we consider the rest as a whole there, which will be analyzed in the next section.
For any a, X' and å CB. choose an co-er Eg of {ar + 8. E CB), thus
Eul < ((xx, + 8 ô CB), Il (l,e, S) = [Ca(e/2CeK))l.
as the complexity of the adversarial examples X is controled by the cover set of the adversarial perturbations Cg.
For any n, X' and fixed 8 E Cg. choose cover Eg of F. Recalling that
f = (1x1, S.)) - (A X. 5. E Cs).
thus
E1 < N E1, || |].. = ,e(FFe/2CL. e/2Ct, || 1).
where the last equality is because the changes of the perturbation cover won't 't change the model function class.
14

---

Adversarial Robust Generalization of Graph Neural Networks
Lastly, as the complexity of class I depends the choices of the parts, the following inequalities hold
i(Ciss e/2, Il,o, (e(Fee//CC,1 loo,
s FollEil S (G -loc,
( (/2C,, ll 11.0.
where the last inequality is due to Lemma C.2.
Lemma 4.6 finally gets the covering number of the function class with fixed perturbations controlled by the constructed cover Cg on S. Next, we utilize transductive Rademacher complexity to derive the covering number- basber-based generalization bound over the adversarial loss.
Definition B.1 (Transductive Rademacher complexity). Let 9 be a set of vectors from R=++ and E (91..... 9m+m) E Rm+* and a = (01...., Omtu) be a vector of i.dd random variables such that
[0, 11- Let
1 withprobability
pi
-1
withprobability
p;
0
withprobabilityy
1 2p.
The transductive Rademacher complexity with parameter p is
Rm (9) = ( + { Eo
sup 9.Eg
o:g
Proof of Theorem 4.8. Combining Lemma C.3 with C.4 and considering the adversarial learning, we can obtain
4p Vn
12 n
20
Q1Q2
(Rm inf 4>0
Vlog (Caduv |. S)de) + &co0 1 /mmmmminmmmmmmmmmm/mmm u) + +2qV
8
Then, we apply Lemma 4.4 and Lemma 4.6, the following inequalities hold
(f) - (f)
4p
12
24ym+a
Q1Q2 1
< inf
+
N (Lado, C, 1o,, S)de + gcoQ1 miin/miimmmmmmmmmm 2)) 2)++2)+2000 +2g
In 8
n
4p
12
24ym+u
Q1Q2 In 2
inf
+
Nog e/2,1 1:0, S)de + geoQ1 / mmin(mm u) + 201
Vn
4u
12
24ymmuu
G0CcK2 "N(F WVFFFe/2CC,ll Side + qooQi V min(m, u) 2gg
Q1Q2 In
inf
log
nn
n
uvmm CE
inf
4p
+
24C²
V log
30K 30KK))
N E, 11 + qca min(m, u) + 2gg
Q1Q2 1 2
In
5
p>0
2ē7
where the last inequality replaces e/2C₂ with and remains the complexity estimate of f in the next section.
B.2. Proofs of Case Study.
Based Theorem 4.8, analyze the adversarial generalization of several classical GNNs via the lens of covering number.
Proof of Proposition 4.14. We first derive the Lipschitz constant Ky of GCN, Let the update rule of node x; with / E [L] is denoted by Zro (X, W W,,..., Wi) = oz
W 1,..., W;-1)W;) where Zea (-) means the i-th line of
15

---

Adversarial Robust Generalization of Graph Neural Networks
the output matrix. Thus we have h(zz, 6) = [(f. W). = (Z x WI... W..... w)) hold for any 8 B. The following inequalities hold
[M(z,; 5) h(z;, 8')1
<CellZa, (X, W i...... WL) Zx w...... W
<Cellor( [g(A))is (X, W1 1...., W WL -OL Σ ((()),)))))))))))))) Zz. (X, W....... ...... W Wi-l)W
j=1
j=1
<Cipl Σ [g(A)) 12, (X, WT. WL-1) 1 Zz+ W 1,
W Will)
<Cepello(A)]l max 1Z ( W WL-1) - (x, W
W W- W
<Cig"pi pi II
Wapt max X W Wilmx
<Cigh
PtPt max X j+ X X3+ jo 11000
t=1
<Cig"
Pt max T δ 33 10000
t=1
L
<Ceg" 7.
pi 81
t=1
Ko - 8'1100,
where the first inequality is due to Assumption 4.2, the third inequality is due to Assumption 4.10, the fourth inequality is according to the compatibility of the matrix norm constraint, and the fifth inequality is based on Assumption 4.11.
Now we analyze the covering number of model function class F. Denote by A = 11, e W W [n] and
Zio (X,,, cs W W'..... w...., Willow. where first observe that
[L]. Based on the Lipschitz property of activation function,
A = -Z, X e W1 Z,, Wi
< [g(A))ss X c.j. W1) 01 > To(A)) Xe,r 1o
SP1 Σ [g)A)) X a. (W 1i
Spig X |ejz 122l| (W; Wi
<pigbli W W'llbs
WW Willa loc
=bgp w1
Wi
where the third inequality is due to the fact that ||0]|oo < ||0||2 holds for any vector æ. For Xaje = (xz, 8o), we have
b= 1| c.ji ll2 & | 1| ll2 S b + vāllōlloo = bb+ vd9.
(3)
16

---

Adversarial Robust Generalization of Graph Neural Networks
Similarly, we have
2 Zio X W 1. W2) - (Xo: W W2
02 [o(A)) (X w)) 02
> ())( Zj- Wi) (x:: llo
5=1
Sp2 (o( 10 Zz. (x W W w22)+ + (Zj. (2..(X.) Wi) Zz. W'l
1 > [o(A)) x. (W) W2 + A1w2)
Spallg(A)] O0 (110) (
5=1
n
Spellg(A)]l (110)
Σ ( [[)a]]k Xe Wo) W2 - Willx + A1w2)
j=1
Sp2ll9( o0 (bgp)w) 11 W22- W loc + bgp uz W, &l
W Will
IW W 22ll>)
-bg² P1p2wi22 w2
W/2
where the second inequality follows by the triangle inequality and the last inequality is followed by the proofs of KGON- Then, for any > 0, using the induction step, we have
A1+1 = -l X, WI. W........ W+11) Zix (X, Wi..... W1+1)llo
<|10
W W....., Wi 01+1
(1) (X, Wi,... W4
j=1
j=1
Spt+19 (X W ...... 1+1 (X, W...W...,,........ ,., 1+
+ +11Zj- (X,, W W.....,,W W.),. (+1 (x. W W4
<bp1419
P W (+1 Wit P14194
H+1
W:
<bg 11
Pew
W//
Now we proceed to upper bound the covering number for F. For any fi(-) and f(()), applying the above inequality, the following hold
L.
L
W
W 10
=A s bg
II
powe
W
Then, based on the definition of the covering number, we have the following relation of the cover between the class f and W (W, W v al s w/}
bgght L
PeW.
Σ
cj wi
(4)
j=1
17

---

Adversarial Robust Generalization of Graph Neural Networks
Thus, according to Theorem 4.8, we focus on
sym++
30KGON
d (N(F e,
log
1loo, d)
20l
gymmr Ce
30K Iog.N loo, S)de
log
20g
30 KONG + V log Mog,((F,,,) 5.1 lo0. S)de
log
my Ce
38 30KoN
log
log II N(W, : sl I swyt.l lloo eg de j=1
201
symmtu
30KGNN
ddlo
de +
log(N(W, : W olloo S wj, |l e,),,, 1=1
(5)
M
P 20
20g
where the second inequality follows by (Va+b)) < (Vā+ + vb)?. and the third incquality is followed by (Bartlett et al., 2017: Tu et al., 2019). Next, we proceed to the proof of the first term as follows
30KGON de S Vd
Koex
30 e
1/3 I
log
log
de S 3v 33dd0KoNN
log de,
(6)
where the first inequality is based on the fact that ||6 - 8011 |o1| Since W E Rdxxd
regard it
vector in IR²", where v = max ..xxddo....dde ). Then the set (W; WW, WWllos Il I wj} forms a wyyball in R and the covering
number for this ball can be upper bounded by the following inequality for 0 S ej S wy (Long & Sedghi, 2019)
(30g v²
N(W; 3: (WWllos wy, 11x0, f2) s
and N(W, j : W 1 S wj, || (1oo, e3) for ej 2 wj. Then, by applying equation (7), focus the second term in equation (5) as follows.
log (WW, ||l S w,,ll Gj)d
3w'j de
log
C
3wi dej
bg L T
PaWe
log
Ej
W/
202
ebg
I PEW
3w0 de, Ej
log
Wi
vbg²
I PEW:
3w's deg
log
Wi
Ej
L
<3ubg*
II t=1
Wi
log
dep
Wy
Jo
1=1
1/3
<3vbg 1.
Pewe
log
dej.
(8)
18

---

Adversarial Robust Generalization of Graph Neural Networks
where the second inequality is based on equation (4) and the forth inequality is due to the condition that ej S w. Then combining equation (6) and (8); we can obtain
30 ) c.1 lo,, S)de
log
[,²,, +Vlog Vlog I -e + vōg² II Prwe f/3 log des)
L
<3
ddl Vd0Kan KOON
<3 v KoCN + obg II powe).
t=1
where the last inequality uses 22/3 v Vlgg = (2 + 22 (Vlog)) S (Tu et al., 2019). Finally, according
to Theorem 4.8, by setting l to 1 n. we can obtain the final generalization gap
(f) (f) + ( (Vm+u
Au + Vm+
72Cc
(vā0KoeN + udgt III pows) + q min(m, u) + 20V 2
Q1Q2
In
t=1
<Rm(S)+ + Ce
72C²
(VānKaex + obg²
II
L
prws) + gooQ1 V min(m, u) + 24V 2
Q102
In
Vm++ w
8
1=1
Now complete the proofs of Proposition 4.14.
Proof of Proposition 4.16. Denote by Z, X W L...., W = = X W W..... W for 1 E [L.]. Note that fe X W) = σz (E)= (A)); Zz- (Xe: W....., WL-1)), where Σソ= (A)l,, = Σ K-1 7(1 ((A))()()))))))))))))))))))))( +(1-
7)* ((A)* K Firstly, the Lipschitz constant KAPPNP is derived by
1h(z, 8) - -2),66)1
<Cellor
[b(A)) 23. [ W,,..., WL-1) - OLL Σ
((A)) Zj, (X W,,... WZ-1))
j=1
j=1
<Capråll (X, WI, 1, ..... W L 1--1) 7xja(X, W w,.... W Wi-1)ll
SCupLöllo--1(4 (X, W 1, 1..... WL-2) レ-1) -Z,- (X, W I..... W WL-2) WL L-1)llo
L-1
<CrOPl II 1=1
Pewill - -
2 KAPPNP 0'1100:
where I = [ S ~1(1+ + +kki (1 - 7)9) ) + - ()) K Now we proceed to the covering number of F. Let
A = 12 Xey c: W I,..., Wi) (X W 1...., W/)loo we have
A =1/ (Xe, W 1) (X., Wi)l
=1|0, X c W, 01 (X c,ia w
Sp X c.i. (W - 1illooo
<bp1 W: W'lloo.
Similar to the proofs of Proposition 4.14, using the induction step, we derive that
A41
Z
X c, WI...., W41) Zia (X. c. W W loc
S Sp4
Zio
X
W W...., Wi) 411 - Zio (X.; W Wi...., W)) W l41bo
|+1
H1
W, W llce
PEWE
8j
19

---

Adversarial Robust Generalization of Graph Neural Networks
Then we obtain the following inequalities
[Ji(A, X W) - ['(A, W)
" ② 5=1
=1/0r
(A) Zo (X W W..... Wi-1)) σ (A))); Zz (X. W Wi..... WL-1)) 100
/=1
(pr.ll((A)
11o A1
W Will
<bypl
II
PEtOE
8j
which implies the following relation between and Ej
L-1 Powh
< hăPl
9
(9)
8j
By applying Equation (9), we can derive the covering number of F below
ay
mmtu
C1
3PKPPPNP a "AF(F,E,
log
Vloo,
201
(log 30 APPNP
L.
3wl de
<vd
+ de
2 log Ej
202
j=1
202
<vd
KATUND
log
30K APPNP
de +
L-1
log
3wy dej Ej
óupr.
1==1 P
L-1
83
1=1
<3v 33Vd0KAPPM
1/33
1log de +
1
obğpr.
I
P
log
3wj
de:
8)
C
1/3 !.
L-1
1/3
1
<3 BoV/dKAAma
V log de + 3odgpl
PEWe
log de, Ej
0
<3 33(VA0KAPPM) wbgpr.
II pewe))
where the first inequality follows by the proofs of GCN. Finally, the adversarial generalization gap of APPNP is obtained by applying the covering number of F and setting μ to 1
Ra( (f) +
4p
+
72Cs
(VOOKAPPNP + vbgpt
L-1
II p.wx) + gcool v min(m, u) + +2// t=1
Q1Q₂ 2
In
1
/m +
Vm+ +
< Rm (f) +
4
72C'
(VdOKAPPNP + ebăpr
II 1=1
Pew)) + gcoQ1 Vmnn(m, u) + 2 2
1Q192
In
1
Vm++ + u
Now the proofs of Proposition 4.16 are finished.
Proof of Proposition 4.18. Denote by Zzja Xx,, Wo...., Wi = =ai((1
(X c. W Wo.... W,-1) +
aZj e, Wo) v)) )o))o((W)) (WW.). where Zio X 63 Wo) = xo W and (W,) 8) + 3W, We define
f( X., W) (Z.. X Wo.... W W--1) WL). Now we first derive the Lipschitz constant K in the fol-
20

---

Adversarial Robust Generalization of Graph Neural Networks
lowing
(1(2, 8) - 1122, 8')1
scill (2)) (x, W Wo...,, W2-n) WW.,,, WL--)
sCapr.0ss| 0r.-1 [(11 a) Eb(A))22 Wo..., WT.-2) + +abj- (X, Wn) W (W
1=1
-ol-1((1-00 (1-a) Σ
(0( (A)), (X, W Wo.... W + (X, Wo) W
5=1
SC₂ II prtof (1 - a)o (x, ( Wo.... WL-2) - (x,(X, Wo...., W WL-2)
1=|-1
a Zajo Wo) - Zzo X W Wo0l
where the second inequality is based on Assumption 4.10 and 4.12, and the third inequality can be further expanded as
(x,
(X, Wo, W..... WL-2) Zj Wo.... W WL-2)
12
L (11-a) a) Σ (A)) (x, Wo.... W L-3)) + ax Wol) v (W 2-2)
j=1
n
- 11-1((11 a) > ( (x, Wo..... W Wa-3)= + aZj. (X, Wo) ( 1-))
j=1
5PL-200122 (1 a)g 2x, W W 3-3)) - Zz0 (X W Wo.... W Wo-sil
+a|l3]- Wo) 2 1o)
Substituting the inequality back can obtain the final results as
[1(2, 8) - -112, 8')l
<Ce II
pi - aa) Zz. (X, Wo
(o. ..... WL WL-3) - Zx Wo. W WL-3)
1m/-2
1.
II 1=L-2
p: - aaga (x, Wo) 2x.(X Wo) + II
pe Zz- (x, Wo) Zj- 2x- (X W Woll
(=L-1
L-1
<C,
II
pere (1 - (1)
1)'-1 ا-و
II priig |Z (X, Wo) - (Wo)lll
1=1
1=1
t=t.jj
L-1
<C
II 1=0
perur (1 a)--1g" apo
(1 a)²² 9
II peaul] 11ó - -
t T--
<Cepndo
E (1-a)---8- g II priel 6 - -
8'11mo where the third inequality is due to that
<KGeNT118
1 (X, Wo) (X., Wo)lloo S sooiollX - X'1l S Po 8'lloc
and W is denoted by
(W:(W (I1-)),,+ SW,
- lb S1 -1-3+
-3+ Bwr.
21

---

Adversarial Robust Generalization of Graph Neural Networks
Notably, we set B 1 in wy and w.. Then we turn the covering number of F. Let A 1| (es Wo...., Wi) - Z (X oi Wo...., Willoo. For brevity, let Ap = (X, Wo... W lloc. and B Zz (Xe, W Wo...., W w..... p) Zio (Xc, W Wo...,, W gr..., W oollo where q S p. We make some preparation first
to facilitate the further derivations
Ap = 33. (Xo: Wo...., lloo
2 -1|08(( - a) Σ
[A(A)) W..... W, p-1) + (X,
(X., Wo) W
f=1
- - (Xe:
c, Wo. W....., W 1>-1) + Pp a 2x Woll
10p0ipp-11pp-100 ")²g² Z), X Wo...., W 22 + 11
Woll
+ Pp 12 Xx: c: W lo0
P II
<((1 ((1--ag) a)g)' /
II pe Zz.. (x,, Woll E(1 (11 a)g)'
pet. (X Wo)ll
1= t=p-j
<hpowo (11-a))
II p,wer
j=0
(=p-j
where the last inequality is according to [| (X., Wo)l S powoo /I X S bporos. Then, we repeat the proof procedure. which starts with
A -1, Wo, W) - (X
e1 W 1l
Z1 (X.: c: Wo. w1 - (X,
c, Wo W ) + (X. ei Wo. W') Zj. (X.. c, Wo Wo
=B} + By
Sm (| - a) Σ 2x, (XZ Wo)
(WW - (wi)l + +w (1((1-a)
Σls(A (A))))i (X 0. Wo) + tZZ, Wo)) - aa1-a) Σ 19( (A)) X o, W)) + aZj. wo)) ]]
1=1
5=1
SpI[((1 A0 + a (1) - (W')l + uz - (11 + [B
Sp1 [ -
+ +obb) B1| W, -W'll + + (11 + {.)]
where the last inequality is due ([, i) (W))) $ |3 W, W Wlooo- Next, we derive that
2
4 =2=1Z Wo. W.,W W W2) - Zz. X W Wi, W/)) = Σ
B₁
1=0
Spa a) Σ lo) (X Wo.Wii w aZ W (1W2)) ll
a
+ +
(1 x))
[o(A))is W.) - (1 a1) Σ
[o))))) (X. Wo, Wi)
1=1
J=1
+ 22
(1 a)
Σ (o(())ls Wo. Wi) - (1 - a) >
W.
1=1
+allZ,, (X,, (X,, Wo) (x,, W
Sp3 (11 - a)gAi + a (W,) ((W 10x + w2 - aa)((A)) - B + u ((1 a)g aB
SP2 (11 a)g4, + + B W2 Wolloo + بي ( + +BB.]
22

---

Adversarial Robust Generalization of Graph Neural Networks
For the inductive step, the following inequalities hold with the fact that Ag Bg
1+1
A
Σ
B
1=0
Sp++1
(11 + aA)) ( W W/+11lx + Wr+t ((1-a)944) + +Bb))
a W W 1+1 W 1 + (
- Willo
+ +t+1priit+ uir 01g - a) (1-a)gA BB) P14101+110B
( - a)gAt + aAo) 8 W 1-1 W 111100
11+1
W Willoo
+ P141 Wi [)g 03-1)AA-11111 + +aA)
+ 1141 wi( /²
A 1 + (p:+1 wi
a)g
Pt+ بن aBB
111
1+1
IW, W
H+1 1+
(1 a)g) (11 + aAA)
II
p
+ ((1 a)g)*+
Pri
ijj
H41
H+
+
((1 (a)))))) 41-
II j=j
B
j=1
141
H+1 II
W
W
1100
1+1 p
Σ
(11 a)g)
41 (1- + arA))
3
((1 - a)g)
II
ūj
1=
l=j
f=1
1+1
IW;
W'
2bb
(11
(1-a)g +
II
p
ij
)=
Finally, we can obtain
IIf(A, - fiA W
-110r(21. (X W W...., W - WY WL-1)W''llo
SpI(wi AL-1 - W 1- - W2
1-1
L-1
B| ; Willla) + AL-IPLLL
W Willo
SpliL (2b) Σ (11 [11))) b-1 ((1 a)gAA-1 a
II [=]
j=0
3 W j W 1|,00
26
(11 (1- aaA) II Pe:0
Similarly, by defining that
T,
Σ ((1 a)g) 4-( (1 1
1=
we have the relation between and as
1. Σ
c < 286 Σ g b- ()1-)) aAa)
II
p.ú
Ej
263
T
(10)
W;
0=0
[=]
j=1
t=j
23

---

Adversarial Robust Generalization of Graph Neural Networks
Then, the following inequalities hold
38K d "N[ e1 1loo: S)
log
30 KoNNn
38,
<vd
(log
de +
22 log
de
e
201
i=1
20
L.
38,
<3v d
22 log
de
Ci
i=1
20
I.
38, de;
83 Σ j=1 Tj II 1=
Pr
KO +
log
Ei
20
vbB
Σ j=
1
Tj 1
Pr
Iv m-m++ C2
38:
<3Vd0KGcNI
log
de:
Wj
E2
201
L
''"
1/3
I flogg
<3 KOCNNI v53
T
II
p:We
V
- de;
Ei
j=1
[=)
33(Vd0 + vd3
T II ()
where the third inequality is due to Equation (10). Finally, the generalization gap holds with μ
1 n
(f) (fm(f) +
4p
+
72C₁
(Vd0KGGNI + vd8
Σ T,
II [ + gcol1 min(m, u) [0)+20 222
Q1Q2
In 8
Vm+u Fu
vm+
+u
j=1
L
L
<fm(f)+
4
72C
(Vd0KocNu + vd,8
T
II petut + geoQ1 / //iimmimmmmmmmmm//mmmmm u) + 205
Q1Q2 1 2
In
+ u
Vm
8
j=1
Now we complete the proofs of Proposition 4.18.
C. Additional Lemmas
Lemma C.1. (Xiao et al., 2022) Let g(w, x) be the loss function and h(w, z) = max =|| ((w, be the adversarial loss. Assume that w > g(w, z) is || ||-Lipschitz with constant L,, we have
[[h[w, x) -(w', x)]1 S L|l w'll.
Lemma C.2. (Mohri et al., 2018) Ler ||- be an arbitrary norm and B be ball of radius n in Rdd Let be a smallest possible E-cover of B. Then,
3m
IC| S (E)
Lemma C.3. (El-Yaniv & Pechyony, 2009) Let G be set of real-valued vectors in [-q,q]m== Let Q1 + 1
m
ut Q2 (m+u-1/2m)) 1/2 m/2(ma)(m, and co / 32t we have
5.05. Then with probability of at least 1 - 5, for all g E G.
(g) & Rmlgg) + Ru (m + u)2 + gooQi / /min(m, u) + 24g
yeu
Q1Q2
In
2
8
Lemma C.4. (Bartlett et al., 2017) Let G be real-valued function class taking values in [-q, gl. where g > 0 is a constant, and assume that O E G. Then the transductive Rademacher complexity of G can be bounded as
4tr
12
24//
Rm+a(g) S inf
+
To,,N(G,6,11 11,,,,
#S0
Vn
n
24

---

Adversarial Robust Generalization of Graph Neural Networks
Table Summary of adversarial generalization analysis (m-numher of training samples; u-number of test samples; NNs-Neural Networks; expectation bound; 4-optimization bound).
Reference
Model
Learning mode
Analysis tool
Convergence rate
Xing al. (2021)
Multi-layer NNs
Inductive Inductive
Uniform argument stability
(1(m/m)
Xiao (2022)
Multi-layer NNs
Uniform stability
+1(1/m)
Yin et al. (2020)
One-layer NN
Inductive
Rademacher complexity
O(1/ m
Awasthi et al. (2020)
Multi-layer NNs
Inductive
Rademacher complexity
0 m
Tu.Zhang. and Tao (2019)
Multi-layer NNs
Inductive
Covering number
O(1/vm
Mustafa, Loi, and Kloft (2022)
Multi-layer NNs
Inductive
Covering number
10 1/)
Ours
Multi-layer GNNs
Transductive
Covering number
[max{
D. Additional Related Work.
Adversarial generalization analysis. As a powerful tool to explain generalization in adversarial training, classical learning- theoretic measures can provide encouraging inspiration in adversarial generalization analysis for GNNs. Xing et al. (2021) and Xiao al. (2022) utilize algorithm stability to derive adversarial stability bounds for NN models, which are based on certain algorithms such as SGD stochastic gradient descent). Awasthi et al. (2020) and Yin et al. (2020) provide an adversarial generalization bound via the lens of Rademacher complexity with restricted NN model structure. By using covering number, Tu, Zhang and Tao (2019) transform the adversarial expected risk over a distribution to the standard expected risk over a new distribution; Mustafa, Lei and Kloft (2022) approximate the complexity of the adversarial loss class by a finite discrete space. Table 4 summarizes the related works in adversarial learning using various techniques.
E. Limitations
Though this paper does not involve topology attacks, given the similar adversarial generation settings for topology attacks and node attacks, our analytical framework could be expanded upon the topology attacks.
To be more specific, let the adversarial graph be generated from (A || S 7). where À = A A' denotes the perturbation matrix added to the original adjacency matrix. The adversarial loss w.r.t. adversarial graph is defined by ma (A, X. ys). Analyzing analogously to the node attacks, we could measure the complexity of the adversarial loss function class by utilizing the covering number techniques, which is the main methodology developed in this paper (Lemma 4.6). This requires an additional assumption that the adversarial loss is La-Lipschitz continuous regarding the adjacency matrix A, where the constant LA can be derived if given specific GNN models. Finally we can solve the measurement difficulty caused by the graph topology perturbations and apply it to main results (Theorem 4.8). The remaining analysis will be left to future work.
F. Additional Experiments.
This section provides the detailed experimental configuration and results for adversarial training on GNNs. Unless otherwise indicated, we adopt two-layer GNN with the ELU activation in each layer and log-softmax activation for output, where the number of hidden units is fixed to 64. 7 and K in APPNP are set 0.5 and 10, respectively. a in GCNII is set as 0.1 and 3- log(E/// L + 1), where L is the number of layers and is fixed to 1. Notably, the learning rate of CoraFull is set as 0.2 with a weight decay of le-4. The implement is GeForce RTX 3080 GPU.
Next, we provide the numerical discussion for the experimental results of the remained datasets from the main text, other influencing factors assessment (comparison of different GNNs and different feature dimensions), and other classical attack methods (FGSM (Goodfellow et al., 2015) and BIM (Kurakin et al., 2017)).
Graph filter. Based on the default settings, when the unnormalized filter ((A) A+ I is adopted, the learning rate 1j is set by 0.01, where 1/ = 0.001 for CS and T = 400 for CoraFull, and the aggregation hop K of APPNP is set as 1. Figure 7-8 show the experimental results of the remaining datasets from the main text, Figure 9-11 present the results of adversarial training attacked by BIM, which exhibit similar trend with PGD.
Model architecture. For a clearer comparison, we adopt the unnormalized filter, and the experimental setup is similar to the experiments of the graph filter. Figure 12 shows the results of hyper-parameete Ty in APPNP and a in GCNII of the remained
25

---

Adversarial Robust Generalization of Graph Neural Networks
Geraralizaain Gap
coazralizaion Cap
Gonvaaizztionn
0.33
0.30
0.5
0400
01400
(a) Experiments of adversarial training Citeseer
GCN
APPNP
GONI
0140)
A4f
(D:17 (A
0.40
@D- (our)
Generalization Cap
0.32
(DID 1igh-p
(DrD (A1
Add
Ceneraliration
Gerardiraaion
0.20
0.30
0.2
0.31
0600
0401
04000
DMBS
0400
01000
0406
9
(b) Experiments of adversarial training Pubmed
GCN
APPNP
GCNT
A-d
(D-0- (t-0--t-
(249"(44)
Gap
Gauralbattinn Cap
(1:0
OnD Vu40
0.40
Gazralizatoon
0.36
0.32
0.35-
0.00
6106
0/125
0.000
0000
0036
0100
0.086
00016
01D4
(c) Experiments of adversarial training DBLP
Figure 7. The generalization gap for different graph filters g(A) with inereased perturbations 0 (attacked by PGD).
datasets from the main text. Moreover, Figure 13-14 show the results of adversarial training attacked by FGSM, which exhibit similar trend with PGD.
Model selection. We compare the adversarial generalization gaps of three different GNN models. Figure 3 reveals that GCN has the largest generalization gap in its deep version, GCNII and APPNP can improve their performance by their well-crafted architectures, especially by their optimizable parameters. Figure 16 and 17 present the results of adversarial training attacked by BIM and FGSM, respectively, indicating that our analysis has a wide range of applications to attack methods.
Number of layers. Based on the default settings, when the number of layers L is bigger than 5, the iteration T' is set 400 for CoraFull. Figure 18-19 display the experimental results of the remaining datasets from the main text, Figure 20-22 show the results of adversarial training attacked by BIM.
Regularization parameter. Figure 23-24 present the experimental results of the remaining datasets from the main text, Figure 25-27 show the results of adversarial training attacked by FGSM, which exhibit a similar trend with PGD.
Feature dimension. Based on the default settings, the number of hidden units is set as 128. Figure 28-29 present the experimental results of the remaining datasets from the main text, Figure 30-32 show the results of adversarial training attacked by BIM.
26

---

Adversarial Robust Generalization of Graph Neural Networks
Alt
Genvalizatian Gaap
0.4
"
Genzaliraaiinn Glap
0.34
Ceneriliaation
0.00
0.13
0.80
(a) Experiments of adversarial training on Pubmed
GCN
APPAP
GONI
Ganerlization
A44
(0+1 (A
040001-00000
Gineralizaaion Gop
0.50
A-4
(D-4) (4-40
Generalzation Cap
0.0
Aal
(M4
0.35
0.00
0.30
0.30
046
0.43
0.000
0008
0006
0431
0.000
0.008
0.28
0.00
0.00
0006
063
(b) Experiments of adversarial training CoraFull
Figure 8. The generaiizattio gap for different graph filters g(A) with increased perturbations 0 (attacked by PGD).
CONI
01100
Geseediizainn Gap
0.5
Cenzrolzzation Gap
Grnzrlizatton
0.33
0.90
0.8
0000
(U00))
(a) Experiments of adversarial training on Citeseer
GCN
APPNP
GCNI
A4t
A:l
Ald
(V (B0--y"
Geveralizaiion
0.35
(1~41 (p--))
Gesraltzation Cap
(DI "AA "0
Gavvallzation
0.5
0.25
6000
0003
41266
0461
0.000
(1000)
6400
01000
(606
010
(b) Experiments of adversarial training Cora
Figure The generalization gap for different graph filters ((A) with increased perturhations (attacked by BIM).
27

---

Adversarial Robust Generalization of Graph Neural Networks
GONI
0.33
(H:0"
(040)
Gennelizadin Gopp
Ceneraliration Cap
Cenerattationn
0.30
0.23
0.20
(a) Experiments of adversarial training on Pubmed
GCN
APPAP
GONI
A48
0.45
A-4
A4
(0-d) "Iu-DdiHD))
(D-41
Genrrliizalan Gop
(0-11%1-0
Gavealization Cap
0.35
(D41) (4-4)
0.40
Geveraization
0.30
0.00
0.35
0.00
0.000
0408
0006
0431
0.000
(1008)
0028
0.00
0.000
0006
0131
(b) Experiments of adversarial training DBLP
Figure 10. The generalization gap for different graph filters g(A) with increased perturbations 0 (attacked by BIM).
CONI
-1-000000000
Gezendizzaiin GaR
Gaserlization Cap
0.00
Gonerilizttonn
0.32
0.21
0.55
0.12
0.16-
0.30
0:0
0100
60016
0100
(a) Experiments of adversarial training CS
GCN
APPNP
GCNI
A4d
A.ll
All
Ganvallzatoon Cap
0,00
(D
Gianralizalimm Gapp
0.51
12 (0-0y""ouu0000 "
(1~4i (pu-))
Ganraltzatin Cap
(bet) (b4))(440)
0.33
0.90
0.5
0.42
6000
0003
41266
0401
0.000
(1000)
6400
01000
(106
(b) Experiments of adversarial training CoraFull
Figure 11. The generalization gap for different graph filters g(A) with increased perturhations 0 (attacked by BIM).
28

---

Adversarial Robust Generalization of Graph Neural Networks
Cora
DBLPP
gm01 9-05
grdd
Gienralizaaio Gog
Gensaalzztion Cap
9-03
Canrallzation
g-055
g-0.5
021
0600
0403
0006
0401
04000
(1000
04000
01000
0406
Experiments of adversarial training for APPNP
Cora
DELL
CS
0.35
ditaadiiraliinnnna Gap
=0033
Cavealization Gap
Canxailzation
-0.5
=05
-0.5
0.4
0.22
0.12
0.00
6U066
0424
0.000
010081
0000
01008
0006
(b) Experiments of adversarial training GCNII
Figure 12. The generalization gap for different hyper-paramene parameter yy in APPNP and a in GCNII with increased perturbations & (attacked by PGD).
Citeserr
Pubmd
0.904
g=0.1
9-a.2
g=03
9-0.3
Generalization Cap
9-033
0-01
9-0.
Geveraization
g-05
Generalzation
0.95-
0.30
0.43
0.30
0.29
0.000
0006
0d01
0.00
0000
0006
0000
0.000
0.06
DFL P
CS
CoraPull
g=0.1
9-01
0-01
Coveraitation
gm003
g-0.5
Greealizaiin
001
g-0.5
0-03
Ceneralizaiion Gap
0.00
0-03
0-505
0.23
0.50
0000
0408
0006
0121
0.000
0.008
0405
0/228
0.00
0.008
0616
Figure 13. The generalization gap for different hyper-paramette in APPNP with increased perturbations 0 (attacked by FGSM).
29

---

Adversarial Robust Generalization of Graph Neural Networks
Citeseer
Cora
Puhmed
0100
-0.1
-001
+0.3
Gennralleddion Gap
0.36
Ganerllzztion Cap
Genovaliaation
0.33
0.94
0.30
0.22
0032
0.30
0.2
6400
CoraFull
-0.1
-0.3
Cap
0.30
-03
Generalzrtton Cap
-0.3
0.30
Genxalization
0.45
0.30
0.6G
0.83
0140)
0.000
0006
04D1
0.000
0.00
0.06
0.000
0.008
0.06
0/D1
Figure 14. The generalization gap for different hyper-parameter in GCNII with increased perturbations 0 (attacked by FGSM).
Cora
DBLP
CS
0.83
OCN GUNI
Geseralzatten Cap
Gezeralization Cap
Geveraizalion Cap
0.28
GENI
GCNI
0:42
0L26-
0u00
0.30
0.000
0408
B.06
0.044
0.008
0006
0.244
0.000
0086
9
Figure 15. The generalization gap for different GNN models with increased perturbations (attacked by PGD).
Citeseer
Pubmed
GCN
GCN APPNP GUNI
GCN
Generaliation Gap
APENE
Generdizzaioo Cup
Geveraization Cap
APINE
GUNII
0.27
0.8-
0L24
0.03
0.21
0.088
0.06
0424
0.000
0.008
0.86
0.000
0.008
0016
0424
DBLP
CS
CoraFull
Gevealiratinn Cap
APPNN
CCNT
Gap
0.00
APPIN
GCNI
Censralization Cap
0.43
AFPNE
GUNI
0.42
0.00
0.30
0.000
0.088
0015
0/24
0.000
ades
0O8S
0.06
adm
0:08
edis
Figure 16. The generalization gap for different GNN models with increased perturbations (attacked by BIM).
30

---

Adversarial Robust Generalization of Graph Neural Networks
Clisse
Cora
Pubmmd
GCN
Cavealization Gap
Grerraizalion Gop
Gevralization Cap
GCNI
GUNI
0L2s
0.63
0L28
0L24
0.000
0.000
0006
0/244
0.000
00008
01085
0.28
0.000
01003
0,06
0421
CoraFull
GCN
OCN
GCN
Generalization Gap
APENa
Genrrlirzdimm Gap
6000
APPN
Geveralization Cop
ArYNa
0.25-
0.22
0.30
0.30
04006
Figure 17. The generalization gap for different GNN models with increased perturbations @ (attacked by FGSM).
GCN
APPNP
GCNI
q=0
q
q=0
0.46
40004
0455
q-0.0
Caurralzation Gap
9-0.0
q-0.00
q-0.00
Q-0.05
Genealizzaionn
Genzaaization
6.2
0.42
2
3
5
(a) Experiments of adversarial training on Citeseer
GUNI
Q--0
0.28
Q-0.00
Gap
0.38
000.0
Centralbation Cap
0.28
-0.00
-00.00
q=0.0
Gezerlitation
0La6:
0.25-
0.28
024
0.22
L
(b) Experiments of adversarial training on Pubmed
GCN
APPNP
CCNI
0.36
qm
9-0.04
Geraralizalie Gegp
Gensallzatlon Cap
Gaerallzatinn
9-0.00
q=:00
q=000
0.3
0.30
(c) Experiments of adversarial training DBLP
Figure The generalization gap for different adversarial perturbations 9 (attacked by PGD) with increased number of layers L.
31

---

Adversarial Robust Generalization of Graph Neural Networks
0.14
q-0
4-0
(.100)
q-0
Generalizatann Gap
Geverlization Cap
Generalization Gap
2-0.8
Q-0.8
0.12
0.12
0485
0.30
0.85
(a) Experiments of adversarial training DBLP
GCN
APPNP
GONI
Coxvolization Cot
Gesvooliaalenn Gap
Caseraltattonn GaD
0.32
Q-000
032
00:000
(14)
q=:00
0.88
0.44-
0.98
0.83
2
3
5
(b) Experiments of adversarial training on CoraFull
Figure 19. The generalization gap for different adversarial perturbations 9 (attacked by PGD) with increased number of layers L.
q-0
q-0
q-0 q=000
q-0.4
Genesliiation Gop
q-000
Gensraltration Cap
Gensralitation
0.00
0.83
0.22
0.55
0.38
(a) Experiments of adversarial training Citeseer
GCN
APPNP
GONI
0.20
Ceneralization Cap
q-0.00
000000
-0000
q=0.00
Covealizatonn
0.31
0.20
0.26-
0.00
2
5
(b) Experiments of adversarial training Cora
Figure 20. The generalization gap for different adversarial perturhations 0 (attacked by BIM) with increased number of layers T..
32

---

Adversarial Robust Generalization of Graph Neural Networks
q-0
0.25
q-00
q=00
q-0.04
Gesnrllaatinn Gap
q-0.0
q=000t
Q-008
Gensvalrathu
Gevsollzation
0.23-
0.33
n.2
0.26
(a) Experiments of adversarial training Pubmed
GCN
APPNP
GONI
0.30
decaaiitaaionn Gap
Cancallzzaton GaD
Canralizatinn
0-000
q -0000
q=:00
0.30
0.42-
0.33
0.36
2
5
(b) Experiments of adversarial training DBLP
Figure 21. The generalization gap for different adversarial perturbations 9 (attacked by BIM) with increased number of layers L.
q-0
q-0
4-0
Generalization Gap
015
Genoralization Cap
Gesevalization Gap
Q-0.0
0.00
0/0
(a) Experiments of adversarial training CS
GCN
APPNP
GONI
0.96
051
Generalizatoon Gap
9=0000
q0000
q=000
Coverlizaden
0.33
0.44
6.5
0.22
6.2
2
5
(b) Experiments of adversarial training CoraFull
Figure 22, The generalization gap for different adversarial perturhations 0 (attacked by BIM) with increased number of layers T..
33

---

Adversarial Robust Generalization of Graph Neural Networks
GCN
APPAP
GONI
Generaliaaion Gap
Ceneraliztionn Gap
Conerairattonn
0.33
-0,
0.30
0.5
0.45
0.40
0.00
0.000
0008
0006
0424
0.000
0008
0086
0.28
0,000
0.008
0.06
(a) Experiments of adversarial training Citeseer
GCN
APPNP
GCNT
-0.1
Generdizaiin Gap
Censralization Gap
Cenerolization
+0.2
=02
-02
0.32-
0.0
0.25-
0.34
0.2
0.00
0108
0006
0421
0.00
0.00
0476
0.21
0.00
0.008
0006
(b) Experiments adversarial training on Pubmed
GCN
APPNP
GONIT
:00
0.90
=00
m0.2
Geveraiizatinn Gap
-03
Ceneralizaionn Cap
=001
+022
Geveralizaionn
0.30
0.30-
0.31
0.30
0.30
0.000
0006
0421
0.000
0.008
0.06
0.000
0.008
0.06
(c) Experiments of adversarial training on DBLP
Figure 23. The generalization gap for different regularization parameter À with increased perturbations (attacked by PGD).
GCN
APPNP
GCNI
-0
-0
-0
Gommalizattoon Cap
=022
-01
Geveraiization Cap
1:02
-0.
Gezerlization Cap
0003
=002
-01
0.25
nmp
0.030
0007
0000
0004
0.000
DMN
odis
(a) Experiments of adversarial training on DBLP
APPNP
CCNI
m0
-0
0.30
-0.1
Grsarriiaaainna Gap
Geseralzzatoon Cap
0.4
Gonsralzatinn
0.45
0.61
042
(b) Experiments of adversarial training CoraFull
Figure The generalization gap for different regularization parameter with increased perturbations (attacked hy PGD).
34

---

Adversarial Robust Generalization of Graph Neural Networks
0.31
=0.1
-0
Gewerlleaaiin Gap
0.45
-0
Geasrllzzaionn Cap
-0
Genvollzatonn
6089
0.42
(a) Experiments of adversarial training Citeseer
GCN
APPNP
GONI
0.27
:002
Gezvolizationn Gap
=02
Cosgralzzatoon CaD
0.28
=02
Conralization
0.26-
0.000
0008
0016
0424
0.000
0.008
0.086
0006
0.000
0.088
0006
01D4
9
(b) Experiments of adversarial training Cora
Figure 25. The generalization for different regularization parameter À with increased perturbations 0 (attacked by FGSM).
=0
-0
-0
=0.1
Gap
Gensraltation Gap
Gennralization
e.2
028.
0.20
0.0
0.5-
0.00
0006
0606
(a) Experiments of adversarial training Pubmed
GCN
APPNP
GONI
Gesundirzdion Gap
033
Generalizatinn Gap
Conerliiakken
=02
=02
0.2
0.00
0.01
0000
0008
0016
0424
0.000
0.088
0.08
0.23
0.000
0.008
0006
0424
(b) Experiments of adversarial training DBLP
Figure 26. The generalization gap for different regularization parameter À with increased perturbations 0 (attacked hy FGSM).
35

---

Adversarial Robust Generalization of Graph Neural Networks
GCN
APPNP
GONT
0.100
Geveralztionn Gap
Generaliation Gap
cetrraatttion Gap
Generaliatioon Gap
Gap
0.033
0/000
0005
0007
0.000
0.000
adus
0134
00000
0.008
000G
0424
0000
0.008
0.05
0424
(a) Experiments of adversarial training CS
GCN
APPNP
GCNT
=0.1
Gonroliratioon Gap
-01
Ceneraliration Gap
Cevvolitationn
0.48-
=02
-0.
:02
0.44-
042
0.90
0.80
0000
0108
0006
0421
0.000
0.00
0,21
0.00
0.008
0006
0101
(b) Experiments of adversarial training on CoraFull
Figure 27. The generalization gap for different regularization parameter À with increased perturbations 0 (attacked by FGSM).
GCN
APPNP
CCNI
42
Generalization Gap
0.80
4/2
44
d1d
Geveaalzation
Gromesaizzaion
0.42
0.30
0.36
0400
0.000
0.08
0006
0424
0.000
0:008
0086
0.038
0.000
0.008
0016
9
(a) Experiments adversarial training on Citeseer
APPNP
GONI
422
Ceneralizaionn Cap
Gonraltzationn
0.22
0.20
0000
0d0s
00000
0000
0m8
adns
nrias
(b) Experiments of adversarial training on Pubmed
APPNP
CCNI
Gisansiiaaiin Gap
Genaraltatlonn Cap
Genoailzation
0.36
0000
0.34.
0.2-
(c) Experiments of adversarial training DBLPP
Figure The generalization gap for different input feature dimension d with increased perturbations (attacked by PGD).
36

---

Adversarial Robust Generalization of Graph Neural Networks
0.100
Gewsallzation Gapp
Gessralizatinn Gap
Gensralzzaton Cap
0.10
01233
0.25
0000
0006
(a) Experiments of adversarial training CS
GCN
APPNP
GONI
Dezssolltaaion Gap
Ceneraltzation Cap
0.30
0.22
Covralization
0.45
0.30
0.1
0.22
0.30
0.000
0008
0006
0/24
0.000
0.088
0.06
0.36
0.000
0.008
0006
0/D4
9
(b) Experiments of adversarial training on CoraFull
Figure 29. The generalization for different input feature dimension d with increased perturbations A (attacked by PGD).
Gesurallzation Gap
0.35
Gensraltraton Cap
0.01
Cenoralizatoon
0.42
D.42-
0.43
0.39
0.40
042
0396
0.00
0.00
(a) Experiments of adversarial training Citeseer
GCN
APPNP
GONI
0.28
dVi
033
Generaiization Cap
0.21
Conraliratinn
0.23
0.2-
028
0000
0008
0016
0424
0.000
0.088
0.086
0.23
0.000
0.008
0006
0624
(b) Experiments of adversarial training Cora
Figure 30. The generalization gap for different input feature dimension d with increased perturbations 0 (attacked hy BIM).
37

---

Adversarial Robust Generalization of Graph Neural Networks
Gewssllaation Cap
0.33
Consillaatonn
0.2b
0.22
Generalzaton
022
0.30
0.20
(a) Experiments of adversarial training Pubmed
GCN
APPNP
GONI
Mezssellratienn Gap
0.30
Cenraltzation Cap
61
Cavvalization
0.34
0.29
0.30
0.000
0/08
0006
0/24
0.000
0.008
0.066
0036
0.00
0.088
0006
0/D4
(h) Experiments of adversarial training DBLP
Figure 31. The generalization for different input feature dimension d with increased perturbations A (attacked by BIM).
Genvallzation Gasp
CLION
Gasp
GenavaBBaadienn
Genernllradionn
DLons.
0.089
0.000
ad06
0000
0036
0du6
(a) Experiments of adversarial training CS
GCN
APPNP
GONI
Gap
Ceneralizatoon Cap
Conerliiakeen
0.00
0.47
0.30
0.8G
0.38
0.85
0000
0008
0016
0424
0.000
0008
0.86
0.24
0.00
0.008
0006
0424
(b) Experiments of adversarial training CoraFull
Figure 32, The generalization gap for different input feature dimension d with increased perturbations (attacked hy BIM).
38


Reviews:
[{"review_id": "29SYplu8cg", "reviewer": "Reviewer_jE3b", "summary": "The paper investigates the adversarial robust generalization of GNNs through a theoretical lens. It derives high-probability generalization bounds for general GNNs in adversarial settings using covering number analysis. The key insight is modeling the adversarial loss class’s complexity by constructing a perturbation cover and analyzing GNN architectures (e.g., GCN, APPNP, GCNII). Theoretical results reveal that adversarial generalization depends on factors like perturbation budget, model depth, weight norms, and graph filters. Experiments on benchmark datasets validate these findings, showing that normalized graph filters, shallower architectures, and regularization reduce generalization gaps.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable comments! Please refer to our response below.\n\n> 1. Lack of testing for randomized splits of datasets.\n\n**A1**:  Thanks for pointing out the lack of considering the impact of dataset splitting. Taking two-layer GCN and two datasets for example, we show the generalization gap under different random split rates of training data (including 0.1, 0.3, and 0.5) in the table below. \n\n|              |                 | Cora            |                 |                 | CoraFull        |                 |\n| ------------ | --------------- | --------------- | --------------- | --------------- | --------------- | --------------- |\n|              | 0.1             | 0.3             | 0.5             | 0.1             | 0.3             | 0.5             |\n| $\\theta=0$   | 0.478$\\pm$0.013 | 0.296$\\pm$0.012 | 0.255$\\pm$0.014 | 0.396$\\pm$0.003 | 0.284$\\pm$0.002 | 0.208$\\pm$0.003 |\n| $\\theta=0.1$ | 0.516$\\pm$0.014 | 0.306$\\pm$0.012 | 0.261$\\pm$0.012 | 0.418$\\pm$0.003 | 0.301$\\pm$0.002 | 0.223$\\pm$0.002 |\n| $\\theta=0.2$ | 0.551$\\pm$0.016 | 0.309$\\pm$0.014 | 0.269$\\pm$0.015 | 0.434$\\pm$0.002 | 0.311$\\pm$0.001 | 0.234$\\pm$0.002 |\n\nThe results show that they have **consistent trends** under increasing perturbation budgets. We will include a comprehensive version of the experiments in our future version.\n\n> 2.  Adaptation to other GNNs.\n\n**A2**:  Our results provide a general analytical framework for GNN, and give three classical examples of spectral GNN. Although specific results are not presented in the paper, **spectral GNN** like SGC, AGCN and GPR-GNN are feasible. \n\nMoreover, we are reasonably confident in extending our results to other types of GNN (spatial-based GNN).  Taking a single-head GAT for example, as for the model function  $f_i(X,W)=\\sigma_2(\\sum_j\\alpha_{ij}W_2X_{j*})$, and $\\alpha_{ij}=softmax(\\sigma_1(w[W_1X_{i*}\\Vert W_1X_{j*}]))$, we can get the relation between the covering number of the model function class and that of the weight matrix set (i.e. $\\mathcal{N}(\\hat{F},\\epsilon,\\Vert \\cdot\\Vert)$ and $\\mathcal{N}(\\{W_j,\\Vert W_j\\Vert\\leq w_j\\},\\epsilon_j,\\Vert\\cdot\\Vert)$),  which can be applied to our analytical framework. \n\n> 3. Large-scale datasets are missing.\n\n**A3**:  Thanks for your valuable suggestions. Large-scale datasets like Nell and ogbn-arxiv will be included in our future versions.\n\n> 4. Extension to attacks against structures.\n\n**A4**:  Given the similar adversarial settings for topology attacks and node attacks, **we suggest that the methodology (e.g., Lemma 4.4 and Theorem 4.8) developed in this paper could be expanded upon the topology attack.**\n\nTo be more specific, let the adversarial graph be generated from $\\{\\tilde{A}:\\Vert\\tilde{A}\\Vert\\leq \\gamma \\}$, where $\\tilde{A}=A - A' $ denotes the perturbation matrix added to the original adjacency matrix. The adversarial loss w.r.t. adversarial graph is defined by $\\max_{\\Vert\\tilde{A}\\Vert \\leq \\gamma} \\ell(f_i(\\tilde{A},X,W),y_i) $.\n\nAnalyzing analogously to the node attacks. For each function $f\\in\\mathcal{F}$ and a fixed $\\tilde{A} _ c\\in\\mathcal{A}$, we construct a new function $h:\\mathcal{Z}\\rightarrow(\\mathbb{R}^n)^{\\mathcal{A}}$ as $h(z_i,\\tilde{A} _ c)=\\ell(f_i(\\tilde{A} _ c,X,W),y_i)$. The adversarial loss is denoted by $\\max_{\\tilde{A}\\in\\mathcal{A}} h(z_i,\\tilde{A})=\\max_{\\Vert\\tilde{A}\\Vert \\leq \\gamma}\\ell(f_i(\\tilde{A},X,W),y_i) $ for any $\\tilde{A}\\in\\mathcal{A}$. \n\nFrom the definition of covering number, we construct the cover of the class $H$ of function $h(z_i,\\tilde{A} _ c)$ and obtain the cover of the class $H_{adv}$ of function $\\max_{\\tilde{A}\\in\\mathcal{A}} h(z_i,\\tilde{A})$. Thus, the following inequality holds\n\n$\\mathcal{N}(H_{adv},\\epsilon,|\\cdot| _ {\\infty})\\leq\\mathcal{N}(H,\\epsilon,\\Vert\\cdot\\Vert _ {\\infty}).$\n\nNext, we construct a cover to control the infinite class $\\mathcal{A}$ by $\\mathcal{C} _ {\\mathcal{A}}:=${$\\hat{A} _ j,j\\in[N_A]$}.  Similarly, we can obtain the relation between $\\mathcal{N}(H,\\epsilon,\\Vert\\cdot\\Vert_{\\infty})$ and $\\mathcal{N}(H_{dis},\\epsilon,\\Vert\\cdot\\Vert_{\\infty})$, which needs an assumption that\n\n$|\\max h(z,A)-\\max h(z,A')|\\leq L_A\\Vert A-A'\\Vert$,\n\n where the constant $L_A$ can be obtained if given specific GNN models. \n\nThis allows us to solve the measurement difficulty caused by the graph structure perturbations and apply it to our main results (Theorem 4.8). The remaining analysis will be left to future work.", "claims_and_evidence": "The claims are supported by theoretical proofs.", "methods_and_evaluation_criteria": "The methods and evaluation make sense.", "theoretical_claims": "The proofs are logically sound.", "experimental_designs_or_analyses": "Experiments vary layers, filters, and attack budget on standard datasets, but there are some weaknesses:\n\n1. The accuracy difference metric varies depending on the dataset split and does not appear to have been tested for a sufficient number of randomized splits.  \n2. The datasets used are small and large-scale datasets are missing.  \n3. Experimental validation was performed on only three GNNs.", "relation_to_broader_scientific_literature": "The work extends adversarial generalization theory to GNNs, addressing unique challenges like transductive learning.", "essential_references_not_discussed": "There are no essential related works that are not cited.", "other_strengths_and_weaknesses": "There are some weaknesses:\n- The work seems to discuss only the case of counter-attacks against node attributes. However, for graph learning, attacks against structures are more extensively studied.\n- Can the proposed theoretical framework be adapted to other commonly used GNNs such as GAT, GraphSAGE, GIN, etc.?\n- The experiments conducted were limited, as described earlier.", "other_comments_or_suggestions": "I don't have other comments or suggestions.", "questions_for_authors": "Please see above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ny8tnM7mCj", "reviewer": "Reviewer_1KKU", "summary": "This paper establishes an adversarial generalization bound of various GNNs, such as GCN, APPNP, GCNII, in the context of transductive learning. The authors provide some guidlines for adversarial generalization based on the theoretical results. The guidlines based on theoretical results are all validated in experimental results.\n\n## update after rebuttal\n\nI had no specific concerns about this paper during my initial review. Therefore, I am maintaining my original score after the rebuttal.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate your acknowledgment of the solid and comprehensive theoretical analysis and the thoughtfully designed empirical results presented in our paper. Thanks for pointing out the typo, and we will fix it in the future version.", "claims_and_evidence": "Yes, the logical flow of the paper is sound, and all claims may be well supported through both theoretical analysis and empirical evidence.", "methods_and_evaluation_criteria": "While the paper does not propose a specific method, it offers valuable hyperparameter guidelines for improving robustness across different GNN backbones. The evaluations are conducted on a variety of well-established datasets, yielding consistent and reasonable results. Additionally, the inclusion of diverse GNN backbones strengthens the validity and generalizability of the theoretical findings.", "theoretical_claims": "I am not confident in assessing the correctness of the theoretical claims or proofs. I did not verify the detailed steps of the proofs, so I cannot confirm their validity. Please take this into consideration.", "experimental_designs_or_analyses": "The theoretical analyses appear sound and comprehensive. Moreover, the empirical results are thoughtfully designed to support and validate the theoretical findings.", "relation_to_broader_scientific_literature": "Contributing to Learning Theory of GNN adversarial generalization.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "- Important topic and solid theoretical analyses.\n- Writing quality is very good.\n- All theoretical findings are supported by the empirical results.", "other_comments_or_suggestions": "- Fig 2(a) caption might be \"Experiments of adversarial training for APPNP.\"", "questions_for_authors": "No", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zLm17uYi8X", "reviewer": "Reviewer_fe5j", "summary": "This paper investigates the generalization ability of graph neural networks (GNNs) under adversarial training, which is an important and widely interested research direction. The paper first proposes a high probability generalization limit and analyzes the generalization ability of GNN under adversarial training through covering number analysis. This provides theoretical support for understanding the behavior of GNN under adversarial learning. The paper selected three representative GNN variants for experiments and proposed a new adversarial training algorithm, which proved its effectiveness in improving the stability of GNN training through experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply thank you for acknowledging the rigorous logic, clear structure, and extensive formula reasoning of our work.  Below are our detailed responses.\n\n> 1. Why does the experimental part of this paper seem to lack a comparative study with previous work?\n\n**A1**: Generally speaking, our focus **does not lie in proposing a competitive algorithm tailored for a specific application scenario**. Instead, this paper **aims at a broader theoretical exploration of robust overfitting in a general adversarial scenario**.\n\nTo be specific, this paper focuses on the robust overfitting phenomenon of GNNs and provides theoretical guidance for improving their robust generalization in a general adversarial scenario.  Our work not only develops a **novel analytical framework** for general GNNs (Theorem 4.8), but also provides **helpful insights** into model construction and algorithm designs (Proposition 4.14~4.18). Based on our theoretical results,  our empirical evaluation focuses on the influencing factors (some model architecture-related factors, like graph filter,  weight norm, number of layers, hyperparameters, etc.) and demonstrates their important roles in improving (or deteriorating) the adversarial generalization.\n\n> 2. The description of Algorithm 1 seems somewhat vague.\n\n**A2**: Thanks for your helpful suggestion. Let $\\mathcal{A}$ be a gradient-based attack algorithm (e.g., PGD, BIM, Mettack), the updated version is provided below.\n\n---\n\n**Input**: Graph $G=(A,X)$, dataset $S$, perturbed dataset $\\tilde{S}$, perturbation budget $\\theta$, regularization parameter $\\lambda$, initialization $W_0$, learning rate $\\eta$, number of iterations $T$.\n\n**while** $t<T$ **do**\n\n$\\tilde{S}\\leftarrow\\emptyset$.\n\n **for** $i = 1, 2, \\ldots, n$ **do**\n\nFor the input matrix $X_t=[x_{1,t},\\dots,x_{n,t}]$, perturb $\\tilde{X_t} \\leftarrow X_t+\\mathcal{A} (X_t,A, \\theta)$.\n​    \nFor each perturbed node in $\\tilde{X_t}=[\\tilde{x} _ {1,t},\\dots,\\tilde{x} _ {n,t}]$, append it to $\\tilde{S_t}$ and choose $m$ samples randomly to the training set $\\tilde{S} _ {m,t}$.\n​    \n**end for**\n​    \nDefine a new objective $L(W _ {i,t})=\\frac{1}{m}\\sum_{\\tilde{X} _ {i,t}\\in\\tilde{S} _ {m,t}} \\ell(f _ {i,t}(A,X, W), y _ {i,t}) + \\lambda \\Vert W _ {i,t}\\Vert _ {\\infty}$.\n​    \nFor all $i\\in [m]$, update $W_t$ using SGD: $W_{i,t+1}\\leftarrow W_{i,t}-\\eta\\nabla {L}(W_{i,t})$.\n\n**end while**\n\n---\n> 3. Can the derivation process of coverage analysis be simplified? It seems to be difficult to understand and apply.\n\n**A3**: Covering number is a commonly used tool in (adversarial) generalization analysis [1,2]. Please let me briefly introduce our analysis technology first. \n\n**1.  For the maximization over adversarial loss ( $\\max_{\\tilde{X}}\\ell(f_i(A,\\tilde{X},W),y_i)$)**(Lemma 4.4). We construct new function classes ( $L$ and $L_{dis}$) and use their covering number to control the covering number of the adversarial loss class $L_{adv}$.\n\n**2. For the interplay between perturbed nodes** (Lemma 4.6). We cover the perturbation set $\\mathcal{B}$ and transform the cover of the loss class $L_{disc}$ to that of the perturbed model function class $\\hat{F}$ .\n\n**3** (Theorem 4.8). Now we can obtain the relation between the adversarial generalization and the covering number of GNN model class!\n\n**4. Covering number derivation** (Proposition 4.14~4.18). We utilize the relation between the model function $\\hat{F}$ and its weight matrix $W$ to derive the covering number of the perturbed GNN class  $\\mathcal{N}(\\hat{F},\\epsilon,\\Vert\\cdot\\Vert)$ by that of the weight matrix set $\\mathcal{N}(${$W_j,\\Vert W_j\\Vert\\leq w_j$}$,\\epsilon_j,\\Vert\\cdot\\Vert)$.\n\nActually, the main step that requires complex calculations is step 4, which is due to the propagation rules of GNN.\n\nTherefore, given the Lipschitz continuity assumption about the adjacency matrix, our work can be applied to topology attack scenarios (by step 1-3). Since our covering number-based framework is applicable to general GNNs, given a specific GNN model with the relation between model function and weight matrix, it can be applied to other types of GNN models (by step 4).  \n\n----\n\n[1] Tang, H. and Liu, Y. Towards understanding generalization of graph neural networks. ICML, pp. 33674–33719. PMLR, 2023.\n\n[2] Tu, Z. et al. Theoretical Analysis of Adversarial Learning: A Minimax Approach. Neurips, 32, 2019.", "claims_and_evidence": "This paper has rigorous formula derivation, which can theoretically support the method proposed in this article. Clear logic in experimental procedures and methods.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria mainly focus on analyzing the adversarial generalization ability of GNNs, which can be applied to the robustness research of GNNs and improving their generalization ability.", "theoretical_claims": "This paper has rigorous and extensive formula reasoning, and in my reading, I did not see any obvious errors.", "experimental_designs_or_analyses": "In the main text and appendix of the paper, the author conducted extensive experiments on six benchmark datasets to support the claims of this article. However, the description of Algorithm 1 seems somewhat vague.", "relation_to_broader_scientific_literature": "I'm not clear enough.", "essential_references_not_discussed": "I'm not clear enough.", "other_strengths_and_weaknesses": "Advantages\n1.The paper has a clear structure, rigorous logic, and standardized use of symbols.\n2.This paper establishes the high probability generalization limit of GNNs in adversarial learning, providing theoretical guidance for the design and training of GNNs.\nWeekness\nThe derivation process of the coverage analysis method is relatively complex and may be difficult to understand and apply.", "other_comments_or_suggestions": "nothing", "questions_for_authors": "1.You established a high probability generalization limit for GNNs in adversarial learning in your paper. Can the derivation process of this boundary be further simplified?\n2.You have proposed an adversarial training algorithm to learn a robust GNNs, but it seems that there is no clear description of the algorithm.\n3. Why does the experimental part of this paper seem to lack a comparative study with previous work?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CPnugIJBts", "reviewer": "Reviewer_5KXc", "summary": "The paper investigates the adversarial robustness of Graph Neural Networks (GNNs) in node classification tasks. The authors propose a high-probability generalization bound for GNNs under adversarial attacks using covering number analysis. They derive bounds for several popular GNN models (GCN, GCNII, APPNP) and analyze the impact of architectural factors on adversarial generalization. The paper also provides experimental results on benchmark datasets to validate the theoretical findings, showing that factors like model architecture, graph filters, and regularization parameters influence the generalization gap under adversarial attacks.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thorough review and valuable suggestions. However, **we would like to clarify the first misunderstanding below**: \n\n> 1. Lack of new insights, comparison with existing methods, and application to real-world scenarios.\n\n**A1**: Generally speaking, our focus **does not lie in proposing a competitive algorithm tailored for a real-world application scenario** (including real-world datasets and attack scenarios). Instead, this paper **aims at a broader theoretical exploration of the robust overfitting in a general adversarial scenario**. Our work not only develops a **novel analytical framework** for general GNNs (Theorem 4.8), but also provides **helpful insights** into model construction and algorithm designs (Proposition 4.14~4.18). \n\nSo, it is imperative for us to further clarify that  **\" The lack of comparison with state-of-the-art methods and the limited scope of the experiments weaken the paper's contribution to the field\" is not valid.** \n\nTo be specific, this paper focuses on the robust overfitting phenomenon of GNN and provides theoretical guidance for improving their robust generalization in a general adversarial scenario.  Based on our theoretical results, our empirical evaluation focuses on the influencing factors (some model architecture-related factors, like graph filter, weight norm, hyperparameters, etc.) and demonstrates their important roles in improving (or deteriorating) the adversarial generalization. \n\n> 2. Analytical challenges introduced by graph data.\n\n**A2**:  **Challenge 1**:  The information interaction of nodes leads to the correlation of perturbations between different nodes, making the adversarial perturbation set of graph data different from that of non-graph data. **Solvement 1**: In adversarial settings, we search for the worst perturbation vector $\\delta$ from all node features that consists of a perturbation matrix. Then, by incorporating the worst perturbation vector  $\\delta$  into coverage analysis, Lemma 4.6 reveals an additional term $(\\frac{6\\theta C_{\\ell}K_f}{\\epsilon})^d$ influencing generalization caused by the interaction between perturbed nodes.\n\n **Challenge 2**: Each node in GNN aggregates messages from its neighbor nodes through the message-passing mechanism, making the complexity measure of GNN model class different from NN. **Solvement 2**: In the decomposition of the propagation process (Proposition 4.14~4.18), we pay attention to the information interaction of graph data in the propagation process, which is reflected in the graph filter $\\sum_{j=1}^n[g(A)]_{ij}$.\n\n> 3. Lack of discussion of the assumptions made.\n\n**A3**: Our analytical framework doesn't require smoothness assumptions of the loss function. This paper only needs the Lipschitz continuity assumption of loss function (Assumption 4.2) and activation function (Assumption 4.10), which can be easily satisfied by some commonly used functions (eg, cross-entropy and hinge loss; Sigmoid and ELU).  Other assumptions about the norm constraint of input feature and weight matrix are also usually used in literature [1, 2]. \n\nIn particular, for **Assumption 4.1**, we give the specific Lipschitz constant of each GNN model. For example, for a two-layer GCN, and $X(\\delta)=[x_1+\\delta,\\dots,x_n+\\delta]$, we have\n\n$\\Vert f_i(A,X(\\delta),W)-f_i(A,X(\\delta'),W)\\Vert$ \n\n$\\leq\\rho_2\\Vert\\sum_{j=1}^n[g(A)] _ {ij}[\\sigma(g(A)X(\\delta)W_1] _ {j*}W_2-\\sum_{j=1}^n[g(A)] _ {ij}[\\sigma(g(A)X(\\delta')W_1] _ {j*}W_2\\Vert$\n\n$\\leq \\rho_2w_2 \\Vert g(A)\\Vert\\max_j\\Vert[\\sigma(g(A)X(\\delta)W_1] _ {j*}-[\\sigma(g(A)X(\\delta')W_1] _ {j*}\\Vert$\n\n$\\leq\\rho_1\\rho_2w_1w_2\\Vert g(A)\\Vert^2\\max_j\\Vert [X(\\delta)] _ {j*}-[X(\\delta')] _ {j*}\\Vert$\n\n$\\leq K_{GCN}\\Vert\\delta-\\delta'\\Vert$.\n\nGiven the GCN with ELU activation and normalized filter ($\\rho=1$, $\\Vert g(A)\\Vert=1$), conducting adversarial training with Algorithm 1 ($\\Vert W\\Vert$ is controlled) could lead to a controllable and small Lipschitz constant. \n\n> 4. Irrelevance and misses of some referred papers.\n\n**A4**: Thanks for pointing out the inaccuracy and misses. We will rectify the incorrect references (see [3,4]).  As this paper focuses more on the theoretical analysis for adversarial training of GNNs, we will add additional related works about GNN attacks and defenses in the appendix for reference.\n\n> 5. Applicable GNN types\n> 6. Extension to structure perturbations.\n\n**A5/A6**: Please refer to  **A2/A4** to the first reviewer (jE3b).\n\n------\n\n[1] Zhou, X. and Wang, H. The generalization error of graph convolutional networks may enlarge with more layers. Neurocomputing, 424:97–106, 2021.\n\n[2] Tang, H. and Liu, Y. Towards understanding generalization of graph neural networks. ICML, pp. 33674–33719. PMLR, 2023.\n\n[3] Ben, F., et al. Single-node attacks for fooling graph neural networks. Neurocomputing, 513:1–12, 2022.\n\n[4] Liu, T., et al. Nt-gnn: Network traffic graph for 5g mobile iot android malware detection. Electronics, 12(4):789, 2023.", "claims_and_evidence": "The paper makes several claims regarding the generalization bounds of GNNs under adversarial attacks. While the theoretical framework is well-structured, the evidence supporting these claims is not entirely convincing. \n\nThe experimental results, though consistent with the theoretical predictions, are limited in scope and do not fully validate the broad applicability of the proposed bounds. \n\nThe authors rely heavily on synthetic or controlled settings, and the generalization to real-world scenarios remains unclear. \n\nAdditionally, the paper lacks a thorough comparison with state-of-the-art adversarial training methods, which weakens the claim of providing a comprehensive understanding of adversarial robustness in GNNs.", "methods_and_evaluation_criteria": "The methods proposed in the paper, particularly the covering number analysis, are theoretically sound and appropriate for analyzing the adversarial robustness of GNNs. However, the evaluation criteria are somewhat limited. The experiments are conducted on standard benchmark datasets, but the adversarial attacks used (e.g., PGD) are relatively simple and do not cover the full spectrum of possible adversarial perturbations. The paper would benefit from evaluating the proposed bounds against more diverse and challenging attack scenarios, as well as comparing with other adversarial training techniques.", "theoretical_claims": "The theoretical claims are based on covering number analysis, which is a well-established tool in statistical learning theory. The proofs provided in the appendix appear to be correct, but the paper lacks a detailed discussion of the assumptions made (e.g., Lipschitz continuity of the loss function and model architecture). \n\nThese assumptions may not hold in practice, especially for more complex GNN architectures or non-smooth loss functions. For instance, though Assumption4.1 maybe satisfied in standard non-graph neural networks, it could be violated in graph neural networks due to the message passing on the interdependent graph data. \n\nThe paper would benefit from a more thorough exploration of the limitations of these assumptions and their impact on the generalization bounds.", "experimental_designs_or_analyses": "The experimental design is reasonable but lacks depth. The authors evaluate the generalization gap under adversarial attacks for different GNN models, but the experiments are limited to a few datasets and attack methods. The results, while consistent with the theoretical predictions, do not provide strong empirical evidence for the robustness of the proposed bounds. The paper would benefit from more extensive experiments, including comparisons with state-of-the-art adversarial training methods and evaluations on larger, more diverse datasets.", "relation_to_broader_scientific_literature": "The paper is well-situated within the broader literature on adversarial robustness and GNNs. It builds on prior work in adversarial training and generalization analysis, particularly in the context of graph-structured data. However, the paper does not sufficiently highlight how its contributions advance the state-of-the-art. \n\nWhile the theoretical bounds are novel, the practical implications and applications of these bounds are not clearly articulated. The paper would benefit from a more detailed discussion of how the proposed bounds compare to existing methods and what new insights they provide.", "essential_references_not_discussed": "The referred papers (Szegedyetal.,2013; Goodfellowetal.,2014) are irrelevant to GNN applications \n\nThe paper misses many relevant papers on GNN attacks and defenses", "other_strengths_and_weaknesses": "Strengths:\n* The paper addresses an important and timely problem in the field of adversarial robustness for GNNs.\n* The theoretical framework is well-structured and provides a solid foundation for analyzing the generalization properties of GNNs under adversarial attacks.\n\nWeaknesses:\n* The empirical evaluation is limited in scope and does not fully validate the broad applicability of the proposed bounds.\n* The paper lacks a thorough comparison with state-of-the-art adversarial training methods, which weakens its claim of providing a comprehensive understanding of adversarial robustness in GNNs.\n* The assumptions made in the theoretical analysis (e.g., Lipschitz continuity) are not thoroughly discussed, and their practical implications are not explored in depth.\n* The paper does not clearly articulate how its contributions advance the state-of-the-art or provide new insights beyond existing work.\n* The theoretical results is only for node feature perturbation, while graph structure perturbation is more common against GNNs. \n\n* The paper misses many relevant work on GNN attacks and defenses", "other_comments_or_suggestions": "Whats the key challenges/difficulties of the derived theoretical results, compared with the existing theoretical results on non-graph data? \n\nCan the proposed theoretical result be applied to graph structure perturbation? \n\nWhat type of GNN architecture is suited to the derived theoretical results?\n\nHow to calculate the generalization gap in the evaluations? The paper uses many assumptions which makes me doubtful on calculating the values of variables in the theoretical gap.", "questions_for_authors": "While the paper presents an interesting theoretical framework for analyzing the adversarial robustness of GNNs, the empirical evaluation is insufficient to support the broad claims made by the authors. The lack of comparison with state-of-the-art methods and the limited scope of the experiments weaken the paper's contribution to the field. Additionally, the assumptions made in the theoretical analysis are not thoroughly discussed, and their practical implications are not explored in depth. For these reasons, I recommend rejecting the paper in its current form.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper derive adversarial generalisation bounds for GNNs via covering number analysis. The topic is timely and important. Three out of four reviewers positively evaluated the paper with a "weak accept" and found the theoretical analyses to be solid. Issues regarding the comprehensiveness of the experimental validation were raised by several reviewers (small datasets, few models, limited scope). In my opinion this is not a major issues since the main contribution of the paper is theoretical. I disagree with Reviewer 5KXc that "thorough comparison with state-of-the-art adversarial training methods" is necessary, although it would of course strengthen the paper.

In general, I believe that the authors sufficiently addressed all the issues raised by Reviewer 5KXc in the rebuttal, even though the reviewer did not update their score. Specifically, the authors explained that their goal is to theoretically explain (adversarially) robust overfitting.  The authors also articulated how the paper's contributions advance the state-of-the-art, including how they address the analytical challenges introduced by graph data. The authors also clarified the assumptions on the loss functions, which are standard and reasonable.

Nonetheless, I suggest the authors to carefully revise their writing to avoid that impression of "broad claims made by the authors". I also encourage the authors to update the paper to reflect the discussion, e.g. the comments regarding an extension to topology attacks. I recommend the paper to be accepted.
Decision: Accept (poster)