Towards Generalization Bounds of GCNs for Adversarially Robust Node Classification
Authors: Wen Wen
Han Li
Tieliang Gong
Hong Chen
Venue: ICLR 2025 Poster (2025)
Keywords: Generalization Analysis; Adversarial Learning; Graph Convolution Networks;  Node Classification；Node Attacks
Primary area: learning theory
TL;DR: This paper presents a comprehensive generalization analysis of graph convolution networks for node classification tasks under adversarial attacks, by Transductive Rademacher Complexity.

Abstract: Adversarially robust generalization of Graph Convolutional Networks (GCNs) has garnered significant attention in various security-sensitive application areas, driven by intrinsic adversarial vulnerability. Albeit remarkable empirical advancement, theoretical understanding of the generalization behavior of GCNs subjected to adversarial attacks remains elusive. To make progress on the mystery, we establish unified high-probability generalization bounds for GCNs in the context of node classification, by leveraging adversarial Transductive Rademacher Complexity (TRC) and developing a novel contraction technique on graph convolution. Our bounds capture the interaction between generalization error and adversarial perturbations, revealing the importance of key quantities in mitigating the negative effects of perturbations, such as low-dimensional feature projection, perturbation-dependent norm regularization, normalized graph matrix, proper number of network layers, etc. Furthermore, we provide TRC-based bounds of popular GCNs with $\ell_r$-norm-additive perturbations for arbitrary $r\geq 1$. A comparison of theoretical results demonstrates that specific network architectures (e.g., residual connection) can help alleviate the cumulative effect of perturbations during the forward propagation of deep GCNs. Experimental results on benchmark datasets validate our theoretical findings.

Published as a conference paper at ICLR 2025
TOWARDS GENERALIZATION BOUNDS OF GCNs FOR ADVERSARIALLY ROBUST NODE CLASSIFICATION
Wen Wen', Han L Tieliang Gong", Hong Chen 1,2,3
College of Informatics, Huazhong Agricultural University 2 Engineering Research Center of Intelligent Technology for Agrieulture, Ministry of Education Shenzhen Institute of Nutrition and Health, Huazhong Agricultural University
"School of Computer Science and Technology, Xi' an Jiaotong University fwen199 90 9, adi dasgt @mmall 1 1 com, {lihan125, chenh) @mail. hzau. edu, cn
ABSTRACT
Adversarially robust generalization of Graph Convolutional Networks (GCNs) has garnered significant attention in various ceuurty-seenstive application areas, driven by intrinsic adversarial vulnerability. Albeit remarkable empirical advancement, theoretical understanding of the generalization behavior of GCNs subjected to adversarial attacks remains elusive. To make progress on the mystery, we establish unified high-probability generalization bounds for GCNs in the context of node clas- sification, by leveraging adversarial Transductive Rademacher Complexity (TRC) and developing novel contraction technique graph convolution. Our bounds capture the interaction between generalization error and adversarial perturbations, revealing the importance of key quantities mitigating the negative effects of perturbations, such as low-dimensional feature projection, perturbation-dependee norm regularization, normalized graph matrix, proper number of network layers, etc. Furthermore, we provide TRC-based bounds of popular GCNs with f--norm- additive perturbations for arbitrary r 2 1. A comparison of theoretical results demonstrates that specific network architectures (e.g., residual connection) can help alleviate the cumulative effect of perturbations during the forward propagation of deep GCNs. Experimental results on benchmark datasets validate our theoretical findings.
INTRODUCTION
Node classification, which aims at predicting a particular class for each unlabeled node in an attributed graph given the class labels of few nodes, has attracted tremendous attention due to its wide real- world applications (Zhou et al. 2019 Hang al. [021] Cao et al. (021). As one of the predominant models for processing graph-structured data, Graph Convolutional Networks (GCNs) (Wu et al.) 2020) have demonstrated superior prediction performance node classification tasks. However, GCNs have been recently shown to vulnerable to adversarial nodes, where the attacker injects imperceptible perturbations into node features, leading incorrect predictions (Dai et al. 2018 Ziigner et al., 2020) Ju et al., 2023). This has led to a proliferation of research aimed at enhancing the adversarial robustness of the trained models, built upon the min-max optimization principle of adversarial training (Madry et al. 2018 Wang et al. 2019; Kong et al. 2022 Tao et al. 2023 Li
al. 2022). Despite the empirical success, theoretical aspects of adversarially robust generalization of GCNs are not well understood yet. In this paper, we make progress on this goal by developing the generalization analysis of GCNs under node attacks.
Adversarial generalization problems have been widely investigated in recent years via the lens of statistical learning theory, ranging from uniform convergence analysis associated with hypothesis
space capacity (e.g., VC-dimension (Cullina et al.] 2018 Attias et al. (022). Rademacher complexity
(Awasthi et al., 2020 Yin al. 2019),, covering numbers (Tu et al. 2019 Mustafa et al. (2022) to
algorithmic stability analysis (Xiao al.) 2022 Xing al. 2021) l). However, all the aforementioned
work is primarily confined to supervised learning with individual samples as input, with extension
Corresponding author.

---

Published as a conference paper at ICLR 2025
to the graph learning remaining unexplored to the best of our knowledge. The significant challenge in analyzing the adversarial generalization of GCNs is that the feature information of each node is mechanism rather than being taken aggregated from its neighbors through the imessage-passingg
only from itself, leading to the interaction of perturbations between different nodes. The joint effect of different perturbations in a peessageppssinggg network invalidates the classic estimation methods in (Yin et al. 2019 Awasthi et al. 2020] Mustafa et al. (0022). resulting in the analytical intractability of the adversarial loss over graph-structured data. Furthermore, the learning approach for node classification no longer corresponds to the supervised learning setting, where the nodes to be predicted are unlabeled and available during training (Li et al. 2018 Oono Suzuki 2020 Song et al. 2022). This paradigm is typically formulated within a transductive learning framework.
To overcome these obstacles, we derive strict upper bounds on the original adversarial loss, and then analyze the generalization properties of the surrogate by leveraging the novel contraction technique on graph convolution, which can yield tighter generalization guarantees. The main contributions of this paper are summarized as follows.
We provide the sesh-probbbility generalization bounds of GCNs for adversarially robust binary and multi culli-classsi node classification tasks, through the lens of adversarial TRC. The derived bounds establish the connection between adversarial perturbations and generaliza- tion error, revealing the role of key factors (e.g., feature dimension, network architecture, graph matrix, etc.) in mitigating the negative impact of perturbations and improving the generalization ability. When the perturbation value is zero, we can recover the generalization bounds for the non-adversarial case, improving the dependence on the number of layers from exponential to the square root term compared to the existing TRC-based bounds.
Our analysis enjoys broad applicability across a wide range of models and loss functions, necessitating only the characterization of adversarial TRC. As application examples of theoretical analysis, we provide explicit generalization bounds for popular GCN models, encompassing SGC, Residual GCN, and GCNII, demonstrating the importance of specific network architectures for achieving adversarially robust generalization of deep GCN models.
Extensive experimental results on benchmark datasets demonstrate the effectiveness of our theoretical findings in reducing generalization error and achieving good generalization performance.
2 RELATED WORK
Adversarial attack and defense on GCNs Recent research has shown that node features with carefully crafted perturbations can induce GCNs towards making incorrect predictions with high confidence (Dai et al. 2018 Zügner et al. 2020 Ma et al.) (2020). To counter such attacks, various de- fense mechanisms have been developed to enhance the adversarial robustness, including regularizing the input gradient (Jia et al. [023] Zhang et al. 2024), designing robust network architectures (Cisse et al. 2017 Abbahaddoo et 2024), adversarial data augmentation (Suresh et al. [002]] Wu et al.
2022, Dong et al.) 2024)) and adversarial training (Feng et al. 2019 Li et al., 2022; Gosch et al.
2024). Among them, adversarial training has been validated to be the most effective defense strategy,
which trains the robust model jointly with clean data and their adversarial counterparts. The resulting robust GCN models have been successfully applied in various fields (Sun et al.] 2022). Despite the excellent performance, the generalization properties of GCNs under adversarial attacks are poorly understood.
Generalization analysis of GCNs Scarselli al. (0118) study the generalization ability of graph neural networks by leveraging the VC-dimension, which grows polynomially with the number of pa- rameters and the number of nodes. Garg al. (2020) establish the first data-dependent generalization bounds for message passing neural networks through the lens of the Rademacher complexity. |erma & Zhang (211)) develop stability-basel generalization bounds and reveal the relationship between the graph size and algorithmic stability. Different from the above work under supervised learning settings, Esser et al. (2021) consider the sumi-supere graph learning setting and provide the generalization bounds by using the transductive Rademacher complexity. Deng et al. (2022) establish generalization guarantees for GCN-based recommendation models under inductive and transductive
learning. Tang & Liu 2023) derive high probability bounds of generalization gap for popular graph
2

---

Published as a conference paper at ICLR 2025
models in the transductive setting. Although the aforementioned work cannot be directly extended to adversarial settings due to the outer maximization w.r.t. adversarial perturbations, provides valuable insights into the generalization analysis of GCNs under adversarial settings.
NOTATIONS AND PRELIMINARIES
Notations. Let [L] - ( We denote vectors as lowercase bold letters (e.g., w). The vector elements are denoted by lowercase letters (e.g., w (Wi,..., Wp) ). We denote matrices by boldface uppercase letters (e.g., W). For matrix W E Rmx* the (p, q)-mmmmmm is defined as | lp.. [[[ Wiillp...... (wnllp)]lg where W. the column of W. We use the shorthand notation | 1 =
Ipppp and write Hölder conjugates by star (e.g.,
(X X)) be attributed graph with nodes, where X [z),.... Ln. E Raxd denotes the node feature matrix, and E R=x denotes the adjacency matrix. this work, we focus node classification tasks in transductive manner, where the goal is to complete node labeling of the given graph with randomly sampled labels (Deng et al. 2022). Let S {x,, yb ) be the set of samples. Without loss of generality, are known, and aim at finding the best predictor f to predict the class labels ym+1,..., Yn by minimizing the training
Preliminaries. Let - (A,
assume that the selected labels 9ı...... Vnn E RR
ms Σ 5-1 ((f(A, ): Vs). where f()) E R represents the prediction of node i, and L R- - R denotes a given loss function. The test error is defined as (J) n-m -i 1 ((S(A, X) y:). In the transductive learning setting, the training and test
(f)
nodes typically determined by random partition (Ciano et al.
2021 Esser et al. 2021).
However, in the presence adversaries, imperceptible perturbations on node features can deceive the model to make wrong predictions (Dai et al. 2018 Bojchevski & Günnemann 2019). Following the previous empirical work (Sun et al. 2020 Jaeckle & Kumar (021). we assume that the set of
adversarial nodes is generated from the neighborhood (X) ) {X [ En.] ||ā; dz/1r- <
r 2 i E [n]]. where denotes the maximum perturbation bound. Given E > 0, an attributed graph (A, X), the label y; of node i, and the loss function é IR 14+, the adversary selects the effective adversarial nodes X.
[ia..... Fn.. by
X, arg max ((f(A,)): Xx)
and the adversarial loss of node i defined by
((( X):
max (X)
(()(A,X):
One of the popular defense methods against adversarial perturbations is adversarial training (Madry
al. 2018 Li et al. 2022), which aims to minimize the adversarial training error, i.e.,
m Z. :- m Σ (((A))))
which measures the worst-case performance of the predictor under adversarial perturbations. We are interested in the generalization behavior measured the adversarial test error, i.c.,
Σ E.(f)= = n1 i=
v.))).
(f), which could serve as an indicator We denote the generalization gap by Gen(f) =o,
of the generalization performance of F and often depends the capability of the function class F (Ooo & Suzuki 2020; Deng et al., 2022). This paper introduces the Transductive Rademacher Complexity (TRC) (El- Yaniv & Pechyony 2009) to quantity the complexity of hypothesis classes for deriving the generalization bounds.
Definition 3.1 (Transductive Rademacher Complexity). F R", E [0, 0.5), and m the number of labeled samples. Let (01,...,0a) Gn) be vector of i.i.d. random variables, where o; takes
3

---

Published as a conference paper at ICLR 2025
the value +1 or -1 with probability p. and 0 with probability 1 -2p. Transductive Rademacher Complexity of F is defined as
1 m
R Rm. (F)
E
oJ [EF
sup
n m
is noteworthy that the TRC degenerates to the standard Rademacher complexity (Bartlett & Mendelson 2002) if p = 1/2 and m n//2. For p 1/2, the TRC is beneficial obtain tighter
generalization bounds, where some Rademacher variables will reach zero value. This paper thus
considers the probability p of Rademacher variable a, +1 to be m(n=mm (El- El-iv & Pechyony 2009).
We introduce the following classic result by directly applying Corollary I in (EI- Yaniv & Pechyony 2009) to adversarial settings, which shows that the generalization gap can be controlled by adversarial TRC, i.c., Rm,, n. F).
Lemma 3.2. Suppose that the range of the loss function é [0, Let Q Then, with probability at least - 8 for all f E F,
( n-m)) and
Q2 10-1/2k1-1/2maxx(nn
Q1Q2
1
Gen(J) S Rm (t F) coQ V min(m, n m) +
In 8
where oo < 5.05 is absolute constant.
It is noteworthy that TRC-based bounds inherently exhibit monotonic decrease at a rate of Omax ( (n vn-m)) }) Yaniv Pechyony 2009: Esser et al., 2021 Deng et al. 2022), re- flecting the role of the number of labeled node m on the generalization. With Lemma 3.2 as a toolkit, establish the generalization bounds for adversarial learning algorithms in the context of transductive inference, and the explicit characterization of Rm,, Fl)F) for various models will be the
focus of this paper. However, deriving an upper bound on Rm. (Eo is often intractable, due to the maximization operator of the adversarial loss over the graph-structure data via the message-passing network. Our approach is to derive a surrogate upper bound on the original adversarial loss, and establish new risk bound terms of the TRC of the surrogate by developing the novel usage of contraction inequality on graph convolution.
Let the hypothesis class of GCNs be defined as follows (Garg et al. 2020 Deng et al. 2022):
F F H ((g(A)- o(g(A)XW()) ....)) W 12, (w() Ip w. [11].
(1)
and the propagation procedure can be written as
H = X, ( <(g( (-1)
I [L]
(2)
where w denotes the maximum bound over the || 112, || 1|p of W w E Rd 1x is layer- specific weight matrix, di is the width of 1-th layer, do d. Φ(-) is the ReLU function (Hahnloser et al. 2000), i.e., ((u) max u.. which is monotonically increasing 1-Lipschitz activation function. The graph filter ((A) Raxx Raxx function of the adjacency matrix A, such as
g(A) A In
the graph with self-loops (Xu et al. 2018
4(A) D-
the random-walk graph (Zhang et al.
2019
g(A) = D ADD 1/2
the symmetric normalized graph (Kipf & Welling
2017
where I, is the identity matrix, and D is the degree matrix defined by D -Ese(n) A
MAIN RESULTS
4.1 GENERAL ANALYSIS: BINARY CLASSIFICATION
Let the label takes values in {-1,+1}, and F. gaxdd + Ra be the function class of multi- layer GCNs defined in (1) We predict the label of node i with the sign of ʃ(A, X): for any
4

---

Published as a conference paper at ICLR 2025
f F. Assume that the loss function ((f x), (1) (A, x)) where é R R is monotonically nonincreasing and Le-iisschiz, the following equation holds:
()..Kk)) = max XEB:(X)
(), =(( min yi X):). (x)
Note that this assumption is a mild condition encompassing some common losses such as the hinge loss and logistic loss, which has been widely used in adversarial learning literature (Awasthi et al. 2020 Xiao et al.) 2022) to derive the non-trivial bounds. According the Talauran contraction inequality (Ledoux & Talagrand 2013), we have
Rm, (2 F) S Le
(3)
where
=: (A,X)
min v ( xE
(4)
The above inequality allows us to bound the TRC of the adversarial loss class Rm, (e F) by controlling the adversarial TRC of function class Rm,aa(F) which is presented in the following theorem. The proof provided in Appendix B.
Theorem 4.1. Let F Buxd + RR be the L-layer GCN function class defined in 1 and F be its adversarial counterpart with the form of (4) We have
Rm. (F) S Qm,n (( (2)g
())
( (Bp- || 12,00 + tes(r", p.d)),
where Bp = (2d, i = 1; Bpx = 2
if (1.2): Bpr 1, ifp E [2, +00),
Qm. mmnnmm) and s(r" rr", .p. fm
Remark 4.2. The adversarial TRC bound above has an unavoidable polynomial dimension depen- dency, i.e., s(r", p, d) as compared to its natural counterpart, which arises from the mismatch between the p-norm the weight (()) and the r-norm in the adversarial node set B (X). One could avoid such a dimension dependency by applying a wwwprraatiiondeeeeeee norm regularizer on the weight matrix. Namely, for arbitrary f,-norm perturbations and 1, the ep-norm regularizer that satisfies p [1) should be chosen such that s(r". p, 1, where
1. In contrast with related work on adversarial learning (Yin et al. 2019 Awasthi et af.) 2020 Mustafa et al.) 2022). our theory the first touch for the generalization analysis of graph-structured data with the -oom additive perturbations for 2 1.
Remark 4.3. For a L-layer GCN, the generalization gap might increase exponentially with the number of layers leading a vacuous bound, which explains why stacking too many layers tends to deteriorate the performance of GCN models (Kipf & Welling 2017 [Li et al. (018)). It is worth noting that if . = 1111ll9((/))) (A)]l or selecting an appropriate graph filter, one can significantly weaken depth dependency and tighten the bound. For the graph with self-loops, [l)(o)
Dmaxx while (l((A)] ox has maximum value / Dimax/DDuin for the symmetric normalized graph, and can be equal to 1 for the random-we walk graph, where Dinax and Dina denote the maximum and minimum degrees, respectively. This also demonstrates the benefit of normalized graph filters for reducing generalization error (Kipf & Welling 2017 Zhang et al. 2019).
Remark 4.4. Taking e = 0 and applying Lemma in the non-adversarial setting:
4.5 yield the upper bound of the generalization gap
o max
x (v (V 1))l Bp- 1 12.
Vn m
which has comparable convergence rate of Ommax ( }) to the existing TRC-based bound (Esser et al.] 2021 Tang & Liu 2023). Notably, bound improves the existing exponential dependency of the number of layers to logarithmic term O 12) facilitating the tighter bound than (Esser et al. 2021 Tang & Liu 2023). which benefit from the usage of the contraction technique.
5

---

Published as a conference paper at ICLR 2025
4.2 GENERAL ANALYSIS: MULTI-CLASS CLASSIHICATION
We turn to the multi-class classification with the standard margin bound framework. In K-category classification problems, define the label y [K] and consider the hypothesis class F Ruxd R For a given f E F, we carry out prediction for node i by arg max, max X)dy The quality of prediction measured by the ramp loss defined by
(v v) {
M(v. y) <0 0< M v. <>
M(O,
0
M 2 %
where M(n,y) = By maxjzy Vj denotes the margin operator. It is worth noting that & (v, is || -Lipschh with constant ? and is an upper bound on the zero-one loss (Mustafa et al. 2022). The corresponding adversarial loss is defined by
?( XA.
max (x)
().
Previous work (Yin et al., 2019) considers a surrogate margin loss based on a semidefinite program- ming (SDP) based relaxation (Raghunathan al. 2018) address the outer maximization problem of adversarial losses for multi-class classification. Since the SDP-based approach essentially derives an upper bound of the surrogate of adversarial loss rather than the upper bound on the original adver- sarial loss, the resulting surrogate often overestimates the adversarial loss, potentially leading to the meaningless bound. In addition, this surrogate only applicable to one-hidden-layer neural networks. Unlike the aforementioned work, we consider pairwise bongin-bound analysis w.r.t. adversarial perturbations, yielding a tighter upper bound on the original adversarial loss and enabling multi-layer network architectures.
Lemma 4.5. Let the robust surrogate loss be defined by
E(((A Wi) = (M) ((((AX)):))
where the worst-case error is
L-1 (w()) (1) |22 1l.
v(f(A,X)) = 2 max es(r", d) (A) W ck kE[K]
11
1=2
where s(r", ,p, d) = + Then, we have
max 1326 # arg max (A X 1 y y'E[K]
(X)
<É(S(A,)) (i) S 7( X), ).) S {(M(J(A, x). - V(S(A, X))) ST).
Remark 4.6. The proof is provided in Appendix C. The robust surrogate loss explicitly characterizes the standard error (f(AA (A, x). y:) regarded as an optimization objective the standard training and the worst-case error (J(A, )): incurred by adversarial perturbations that should be suppressed. The proposed robust loss can thus be used to adversarially train robust models to withstand adversarial perturbations. It is noteworthy that the magniuude of the perturbation applied during training should be controlled such that the worst-case error term is smaller than the standard error term.
With the Ledoux- Talagrand contraction inequality and Lemma 4.5 obtain the following structural result
Ledoux-Talagrand
Ri, o S Rm,, n (E F) (Rm,, (M F) + Rm, ( o F)).
In the following theorem, we present the TRC-based generalization bound of GCNs for multi-class node classification tasks by applying Lemma 3.2 The proof is provided in Appendix C.
Theorem 4.7. Let F. Raxd + B be the class of L-layer GCNs as defined in [.. Consider the robust surrogate loss defined in Lemma 4.5, For any fixed 7 > O, with probability at least 1 - Ó,
1
1E3 E (X s.t. Ys # arg max 3 y'E[K]
if, x)
m
HA S7+ max My + V(((A, + Rem,n (Zo + O mmn.
m

---

Published as a conference paper at ICLR 2025
where Om, (max vm vn-m!! 1).
4K
Rm ( S Qm, (Vlog(2)L + 1))lg(())ll (Bp-lI 122 + +es(r", pp
and Qm, Bg, s(r", .p.d) are as given in Theorem 4.1
Remark 4.8. Similarly, the upper bound above suffers from an additional perturbation-relevan term as compared to its non-adversarial counterpart, that is, O(es(r", (,,((",,,,))))) .,,)). As discussed in Remark 4.2 and 4.3 one could confine this complexity term and narrow the generalization gap by applying p-norm regularizer the weight to avoid polynomial dimension dependency in s(r", p. d), where p E [1,r"] and pr = 1, and choosing the factor w = O(1/llg( (()) [(<))))))))) or the appropriate graph filter mitigate depth dependency.
Remark 4.9. The convergence rate of (KK) in the number of classes K is comparable with the existing gencralization bounds for traditional multi-class classification tasks (Yin et al. 2019) Tu special case of Theorem 4.1] in which the loss function is fixed to the ramp loss. Letting e = O, we obtain the high-probability generalization bound of GCNs for multi-class classification, which fills theoretical gap in the multi-class node classification task to our knowledge.
et al. 2019). In particular, when K = 2, the above bound can be viewed
5 GENERALIZATION GAP FOR GCN VARIANTS
Recently, various variants of GCNs have achieved tremendous success in improving the generalization ability of deep GCNs, encompassing SGC. Residual GCN, and GCNIL In this section, we provide explicit generalization bounds for these popular variants through the extension of our theoretical analysis, elucidating the role of network architectures on the generalization performance of deep GCNs in adversarial settings. Here, we consider the case of the K Kccategory classification task.
SGC. et al. (2019) propose Simple Graph Convolution (SGC) by removing nonlinearities in Vanilla GCNs (Kipf & Welling 2017). The resulting linear model is
[(A, X) = Softmax(g(A (s())" (A) XW()... ...).,
where ( E Rdd-ixdd for / E [L], and di is the width of (-th layer (do = d and dr, = K).
Proposition 5.1. For any d E (0, 1), with probability
2K
Gen(f) S Omax Vm /n
+ Qm,m
(1 loc (Bp || 1|2 +Es(r", ,p p. p.))).
where Qm, By. and s(r", (((r",,,d p.d) are as given in Theorem
4.1
Remark 5.2. The proof is provided in Appendix D. worth noting that (A) I [1
thereby alleviating the negative impact of perturbation-relevan term and leading to tighter general- ization bound in Proposition 5. than in Theorem 4.7] This provides the theoretical understanding of why linear models can achieve comparable and even better generalization performance than nonlinear models. It is natural that if a linear GCN has small training error, it will also perform well on test samples based on the small generalization gap. Furthermore, for L-layer SGC, the aggregated information can contain the feature information of all L-hop-away neighbor nodes, thereby signifi- cantly improving the representation power of deep GCNs while avoiding over-smoothing (i.e., as depth increases, the representations of nodes are inclined to converge to certain value, resulting in performance degradation) (Chen al. 2020a).
Residual GCN. Kipf & Welling (201)) facilitate the training of deep GCNs by adding residual connections (He et al. 2016) between hidden layers that carry information from the previous layer. The forward propagation is defined by
H (1) = ((g(A))) (1(00) - (11),, H ((XW
where W( E Idd xd for E [L-1], 1I. ( E Rxdd' The final output of the model is expressed by f(A, X) Softmax H (L-1) (()), where (LL) Rd'
7

---

Published as a conference paper at ICLR 2025
Table 1: Dataset statistics.
Dataset
Classes
Nodes
Edges
Features
Training
Validation
Test
Citeseer
3,327
4,732
3,703
20 per class
500
1000
Cora
7
2,708
5,429
1,433
20 per class
500
1000
Pubmed
3
19,717
44,338
500
20 per class
500
1000
CS
15
18,333
81,894
6,805
20 per class
30 per class
Rest
Physics
5
34,493
247.962
8,415
20 per class
30 per class
Rest
ogbn-arxiv
40
169,343
1,166,243
128
20 per class
30 per class
Rest
Proposition 5.3. For any d E (0, 1), with probability
Gen(f) 50 max
Vm /n
4K
+ Q mm
(V (og(2) + 1) ()) + (Bp |X + d)).
where Qm.r. Byx, and s(r", p,d)
given in Theorem 4.1
Remark 5.4. The proof is provided in Appendix E. The generalization bound above has similar dependency on the number of network layers as Theorem 4.7] This implies that as the depth increases, the perturbation term will become the dominant factor and may lead to larger generalization errors. Our analysis thus provides the theoretical understanding that residual connections partially alleviate over-smoothing while degrading performance with increasing depth (Kipf & Welling) 2017).
GCNIL Chen et al. (020bb) effectively enhance the prediction performance of deep GCNs by building initial residual connection to the first layer, motivated by (He et al. 2016 Kipf & Welling 2017). The propagation process is
H = <{((1 - ())g(())HH))) aH (( B),, + (W))),
H o (
where a, e (0, W E Rd' for IL 1]. and W Raxd', The final output is defined
by fAA X) Softmax (oftmax(H! W(L)), w(()) where W(L) Rd'
Proposition 5.5. For any â E (0, 1), with probability 1 8,
Gen(f) {0ma 1
4K
vn }) + Qm,
( (Vlog(2)L + 1)(B, X 11,,, + "s(r", p.d))
a) (A) (1 B Bw) + a(1 - a
x w ((1-
1 (o(A))l 8 (w))).
1=0
where Qm By,, and s(r", pp.d) are as given in Theorem
comparison of Proposition 5.3 and Proposition 5.5 indicates that the product term of multiple norm bounds can be confined to the sum term via a tunable parameter a. This implies that as a increases, the perturbation term will significantly weaken the dependency on depth and be well suppressed, thereby reducing the generalization error. Additionally, is noteworthy that if 3 approaches zero and (l9(A))l < 1, the upper bound in Proposition 5.5 independent of the number of layers and can be considerably narrowed. The reason behind this behavior is that as a increases and / decreases, the network architecture close to the shallow model, which prevents the layer-by-layer propagation of adversarial perturbations. Hence, we posit that initial residual connection confers greater benefits to the generalization ability of deeper GCNs, being corroborated by certain empirical observations (Chen al. 2020b Liu al. 2021
Remark 5.6. The proof is provided in Appendix
EXPERIMENTS
In this section, evaluate the impact of some key quantities the generalization performance of GNC in adversarial settings, such as feature dimension, regularizer, graph filters, the number of layers, etc. Extensive experimental results validate theoretical findings in dections488
8

---

Published as a conference paper at ICLR 2025
Generalization Error
1.0
Citeseer
Generalization Error
0.7
Cora
funeralizaaioon Error
0.7
Pubmed
0.6
0.6
0.7
0.5
0.5
0.6
0.4
0.4
0.5
0.3
d/2
0.3
6:4
d/4
0.3
0.2
0.2
0.00 0.008 0.012
0.00 0.004 0.008
0.016
0.004
0.008
0.012
3
E
Generalization Emor
0.188
CS
Generalization Error
0.16
Physics
Generalization Frror
0.30
ogbn-arxiv
0.16
0.14
Td/2
0.25
0.14
0.12
a4
0.12
dd4
0.20
0.10
0.10
0.15
0.08
0.08
0.06
0.06
0.10
d44
0.04
0.00
0.004
0,008
0.016
0.04
0.00
0.044
0.008
0.012 0.016
0.05
0.00
0.004
0.008
0.012 0.016
3
Figure The empirical generalization error (mean value and standard deviation) with different feature dimensions. denotes the maximum allowable perturbation.
6.1 EXPERIMENTAL. SETUP
We adopt several widely-used benchmark datasets, including Citeseer, Cora, Pubmed, CS, Physics, and ogbn-arxiv (Sen al. 20088 Yang et al. 2016 Hu et al., 2020). Statistics of the datasets are summarized in Table
We adversarially train robust model by leveraging the following objective:
min max JEJ XEB:(X)
Σ () + A||W]|
(5)
where E(-) is cross-entropy loss, W denotes the weight parameter the first layer, 2 denotes the regularization coefficient, and denotes the maximum allowable perturbation. The training iterations is fixed to 600. During training and testing, the adversarial nodes are generated by the PPGD algorithm (aaryy al. 2018) with the step size =/128, where adversarial perturbations are added to test nodes after training to avoid a biased evaluation through memorization of the transductive
learning setting (Gosch al. 2024). Similar to previous work (Xiao al. 2022 Zou & Liu 2023
we consider an empirical proxy for the generalization gap:
Adversarial Training Accuracy Adversarial Test Accuracy
that is, the absolute value of the difference between the accuracy on adversarial training and test nodes. Each experiment is independently repeated 10 times and reported with the mean value and standard deviations. We default to present the experimental results of two-layer GCN proposed by (Kipf & Welling 2017). Please refer Appendix for more detailed experimental configurations and experimental results, including different attack methods, SGC, GCNII, and Residual GCN.
6.2 NUMERICAL DISCUSSION
Feature dimension. We compare the empirical generalization error with different dimensions, including the original dimension d, [d/2]. and [d/4]. ] For convenience, we use a single-layer neural network with ReLU activation learn a -imeenenni representation of the node features. As shown in Figure I the empirical generalization error decreases steadily with the dimension, which implies that low-dimensional feature projection can help reduce the generalization error.
apply fi-norm regular- izer on the weight matrix, since &xc -norm attack used to generate adversarial perturbations. We evaluate the effect of norm regularization the generalization ability by comparing the empirical
Regularization. Following the theoretical findings in Theorem 4.1

---

Published as a conference paper at ICLR 2025
Generalization Enror
1.0
Citeseer
deneralizationn Error
0.7
Cora
Generalization Emor
0.7
Pubmed
0.9
0.6
0.6
0.8
0.7
0.5
0.5
0.6
0.4
0.4
0.5
0.05
0.3
0000
0.3
0000
0.05
0.4
-.100
2-1.0
2- 0.10
0.3
0.15
2-015
0.2
0.00
0.004
0.008
0.012
0.016
0.00
0.004 0.088
0.012
0.016
0.00
0.004
0.008
0.012
0.016
3
CS
Physics
ogbn-arxiv
Generalization Error
0.18
Generalization Error
0..88
Generalizztion Error
0.30
0.16
-0000
1.16
2.
200000
0.05
0.25
2-0.05
0.14
0.10
0.14
A- 0.10
0.10
0.12
0.15
0.12
0.10
0.10
0.15
0.08
0.08
0.06
0.06
0.10
0.04
0.04
0.05
0.00
0.004
0.008
0.012
0.016
0.00
0.004
0.008
0.012 0.016
0.004 0.008 0.012 0.016
3
Figure 2: The empirical generalization error (mean value and standard deviation) of models trained with & regularization for different regularization parameters (i.e., A). & denotes the maximum allowable perturbation.
generalization error with different regularization coefficients X. As shown in Figure 2 the empirical generalization error of the regularized model is smaller than that without (i.e., X = 0), which is con- sistent with our theoretical analysis. Experimental results demonstrate the importance of appropriate regularizer achieve good generalization performance.
Graph filter. We present the empirical generalization error with different graph filters in Figure 3 where the number of layers is set to As shown in Figure 3 the graph with self-loops has larger empirical generalization errors than the normalized graphs. Hence, argue that normalizing the graph matrix can facilitate the adversarial generalization of GCNs.
Model depth. We compare the empirical generalization error with different depths in Figure The experimental results show that the generalization error increases the number of layers increases and tends to be stable or even decreases due the over-smoothing issue. This suggests that the appropriate number of layers should be determined balance the representation power and generalization capability.
Network architecture. We investigate the generalization ability of popular GCNs with adversarial perturbations, including Vanilla GCN, SGC, Residual GCN, and GCNII, where the number of layers set to Figure presents the empirical generalization error of different models with lxo PGD attacks. Emiprical observations show that GCNII with initial residual connection tends to have smaller generalization error, which demonstrates the effectiveness of the specific network structure in enhancing adversarial robustness. Furthermore, a on the generalization ability of GCNII. As shown Figure the larger a, the smaller empirical generalization error, which is consistent with our theoretical findings in Proposition 5.5
evaluate the role of the parameter
Labeled node size. We study the effect of the number of labeled nodes on the generalization ability of the learned model the node classification task. Specifically, we compare the empirical generalization error with different label rates m/n. where m/n denotes the number of labeled nodes used for training divided by the total number of nodes. As shown in Figure 7 when label rete m/n is too large too small, the generalization gap will be at large level, which aligned with the general consensus (EI- Yaniy & Pechyony 2009 Esser et al.) 2021). This implics that the amount of labeled data should be taken into consideration to achieve excellent prediction performance.
10

---

Published as a conference paper at ICLR 2025
7 CONCLUSION
In this paper, we provide a comprehensive generalization analysis for GCNs under perturbation attacks through the lens of the adversarial TRC. The derived bounds provide theoretical char- acterization of the interplay between the generalization етrоr, node perturbations, and adversarial robustness. Theoretical results reveal how graph-structure data and model parameters can help improve adversarially robust generalization of GCNs. Furthermore, we develop the generalization bounds for popular variants GCNs, which implies that specific network architecture (e.g., initial residual connection) is beneficial for enhancing adversarial robustness. Extensive experimental results on benchmark datasets validate our theoretical findings. Interesting directions for future work include analyzing the generalization properties for GCNs under topology attacks.
ACKNOWLEDGMENTS
This work was supported by the National Natural Science Foundation of China (Nos. 62376104, 12426512, and 11801201), and HZAU-AGIS Cooperation Fund (No. SZYJY2023010).
REFERENCES
Yassine Abbahaddou, Sofiane Ennadir, Johannes Lutzeyer, Michalis Vazirgiannis, and Henrik Boström. Bounding the expected robustness of graph neural networks subject to node feature attacks. In The Twelfth International Conference on Learning Representations, 2024.
Idan Attias, Arych Kontorovich, and Yishay Mansour. Improved generalization bounds for adversari- ally robust learning. The Journal of Machine Learning Research, 23(1):7877-7227, 2022.
Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. Adversarial learning guarantees for linear hypotheses and neural networks. In International Conference Machine Learning, pp. 431-441, 2020.
Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexitie: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):4663343)) 482, 2002.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. opectrally-normaliiee margin bounds for neural networks. Advances in Neural Information Processing Systems, 30, 2017.
Aleksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. International Conference on Machine Learning, pp. 695-704. PMLR, 2019.
Jiangxia Cao, Xixun Lin, Shu Guo, Luchen Liu, Tingwen Liu, and Bin Wang. Bipartite graph embedding via mutual information maximization. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp. 635-643, 2021.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Mcasuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp.
2020a.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020b.
Giorgio Ciano, Alberto Rossi, Monica Bianchini, and Franco Scarselli. On trancciveerransduuctvv learning with graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(2):758-769, 2021.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning, pp. 854-863. PMLR, 2017.
Daniel Cullina, Arjun Nitin Bhagoji, and Prateck Mittal. Pac-learning in the presence of adversaries. Advances in Neural Information Processing Systems, 31, 2018.
11

---

Published as a conference paper at ICLR 2025
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International Conference on Machine Learning, pp. 1115-1124. PMLR, 2018.
Leyan Deng, Defu Lian, Chenwang Wu, and Enhong Chen. Graph convolution network based recommender systems: Learning guarantee and item mixture powered strategy. Advances in Neural Information Processing Systems, 35:3900-3912 2022.
Yixiang Dong, Minnan Luo, Jundong Li, Ziqi Liu, and Qinghua Zheng. Semi-supervised graph contrastive learning with virtual adversarial augmentation. IEEE Transactions on Knowledge & Data Engineering, (01):1-12, 2024.
Ran El-Yaniv and Dmitry Pechyony. Transductive rademacher complexity and its applications. Journal of Artificial Intelligence Research, 35:193-234, 2009.
Pascal Esser, Leena Chennuru Vankadara, and Debarghya Ghoshdastidar. Learning theory can (sometimes) explain generalisation in graph neural networks. Advances Neural Information Processing Systems, 34:27043-27000 2021.
Fuli Feng, Xiangnan He, Jie Tang, and Tat-Seng Chua. Graph adversarial training: Dynamically regularizing based on graph structure. IEEE Transactions on Knowledge and Data Engineering, 2396)2449,- 2019.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference Machine Learning, pp. 3419-3430. PMLR, 2020.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Conference On Learning Theory, pp. 297-299. PMLR, 2018.
Lukas Gosch, Simon Geisler, Daniel Sturm, Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Adversarial training for graph neural networks: Pitfalls, solutions, and new directions. Advances in Neural Information Processing Systems, 36, 2024.
Uffe Haagerup. The best constants in the khintchine inequality. Studia Mathematica, 70(3):231-283, 1981.
Richard HR Hahnloser, Rahul Sarpeshkar, Misha A Mahowald, Rodney J Douglas, and H Sebastian Seung. Digital selection and analogue amplification coexist in cortex-inspired silicon eircuit. Nature, 405(6789):947-95,, 2000.
Mengyue Hang, Jennifer Neville, and Bruno Ribeiro. A collective learning framework to boost gnn expressiveness for node classification. In International Conference on Machine Learning, pp. 4040-4050. PMLR, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen I. Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. Advances in Neural Information Processing Systems, 33:22118 18-22133, 2020.
Florian Jaeckle and M Pawan Kumar. Generating adversarial examples with graph neural networks. In Uncertainty in Artificial Intelligence, pp. 1556-1564. PMLR, 2021.
Yaning Jia, Dongmian Zou, Hongfei Wang, and Hai Jin. Enhancing node-level adversarial defenses by lipschitz regularization of graph neural networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 951-963, 2023.
Mingxuan Ju, Yujie Fan, Chuxu Zhang, and Yanfang Ye. Let graph be the go board: Gradient-free node injection attack for graph neural networks via reinforcement learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pp. 4383 2023.
12

---

Published as a conference paper at ICLR 2025
Justin Khim and Po-Ling Loh. Adversarial risk bounds via function transformation. ArXiv Preprint ArXiv:1810.09519, 2018.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein. Robust optimization as data augmentation for large-scale graphs. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 60-69, 2022.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: Isoperimetry and Processes. Springer Science & Business Media, 2013.
Jintang Li, Jiaying Peng, Liang Chen, Zibin Zheng, Tingting Liang, and Qing Ling. Spectral adversarial training for robust graph neural network. IEEE Transactions on Knowledge and Data Engineering, 2022.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi supirsupereieed learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Xiaorui Liu, Jiayuan Ding, Wei Jin, Han Xu, Yao Ma, Zitao Liu, and Jiliang Tang. Graph neural networks with adaptive residual. Advances Neural Information Processing Systems, 34:9720- 9733, 2021.
Jiaqi Ma, Shuangrui Ding, and Qiaozhu Mei. Towards more practical adversarial attacks graph neural networks. Advances in Neural Information Processing Systems, 33:4756-4766, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT press, 2018.
Waleed Mustafa, Yunwen Lei, and Marius Kloft. On the generalization analysis of adversarial learning. In International Conference on Machine Learning, pp. 16174-16196, 2022.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In International Conference on Learning Representations, pp. 1-15, 2018.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The of graph and recursive neural networks. Neural Networks, 108:248-225 259, 2018
dimension
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al Magazine, 29(3):93-95 2008
Zixing Song, Xiangli Yang, Zenglin Xu, and Irwin King, Graph-based semi-supervised learning: A comprehensive review. IEEE Transactions on Neural Networks and Learning Systems, 2022.
Lichao Sun, Yingtong Dou, Carl Yang, Kai Zhang, Ji Wang, S Yu Philip, Lifang He, and Bo Li. Adversarial attack and defense on graph data: A survey. IEEE Transactions Knowledge and Data Engineering, 2022.
Yiwei Sun, Suhang Wang, Xianfeng Tang, Tsung- Yu Hsieh, and Vasant Honavar. Adversarial attacks on graph neural networks via node injections: A hierarchical reinforcement learning approach. In Proceedings of the Web Conference 2020, pp. 573-683, 2020.
13

---

Published as a conference paper at ICLR 2025
Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. Advances in Neural Information Processing Systems, 15933, 2021.
Huayi Tang and Yong Liu. Towards understanding generalization of graph neural networks. In International Conference Machine Learning, pp. 33674-33719, PMLR, 2023.
Shuchang Tao, Qi Cao, Huawei Shen, Yunfan Wu, Liang Hou, and Xueqi Cheng. Graph adversarial immunization for certifiable robustness. IEEE Transactions on Knowledge and Data Engineering. 2023.
Zhuozhuo Tu, Jingwei Zhang, and Dacheng Tao. Theoretical analysis of adversarial learning: A minimax approach. Advances in Neural Information Processing Systems, 32, 2019.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1539-1548, 2019.
Jingkang Wang. Tianyun Zhang, Sijia Liu, Pin-Yu Yu Chen, Jiacen Xu, Makan Fardad, and Bo Li. Towards unified min-max framework for adversarial exploration and robustness. Advances in Neural Information Processing Systems, 2019.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International Conference on Machine Learning, pp. 6861-6871. PMLR, 2019.
Tao Wu, Nan Yang, Long Chen, Xiaokui Xiao, Xingping Xian, Jun Liu, Shaojie Qiao, and Canyixing Cui. Ergen: Data enhancement basseed robust graph convolutional network against adversarial attacks. Information Sciences, 617:234-253, 2022.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24, 2020.
Jiancong Xiao, Yanbo Fan, Ruoyu Sun, Jue Wang, and Zhi-Quan Luo. Stability analysis and generalization bounds of adversarial training. In Advances in Neural Information Processing Systems, 2022.
Yue Xing, Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training. Advances in Neural Information Processing Systems, 34:26523-26535, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Machine Learning, 2018
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning, pp. 40-48. PMLR, 2016.
Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. In International Conference on Machine Learning, pp. 7085-7094, 2019.
Haimin Zhang, Min Xu, Guoqiang Zhang, and Kenta Niwa. Ssfg: Stochastically scaling features and gradients for regularizing graph convolutional networks. IEEE Transactions on Neural Nenworks and Learning Systems, 35(2):2223 -2344, 2024.
Zhihong Zhang, Dongdong Chen, Jianjia Wang, Bai, and Edwin Hancock. Quantum- subgraph convolutional neural networks. Pattern Recognition, 88:38-49, 2019.
Fan Zhou, Chengtai Cao, Kunpeng Zhang, Goce Trajcevski, Ting Zhong, and Ji Geng. Meta-gnn: On few-shot node classification in graph meta-learning. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 2357-2360, 2019.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. International Conference on Learning Representations, 2021.
14

---

Published as a conference paper at ICLR 2025
Xin Zou and Weiwei Liu. Generalization bounds for adversarial contrastive learning. Journal of Machine Learning Research, 24:1-54, 2023.
Daniel Zügner, Oliver Borchert, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on graph neural networks: Perturbations and their patterns. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(5):1-31, 2020.
15

---

Published as a conference paper at ICLR 2025
A NOTATION
For matrix W R the (p, q)-norm is defined as | p.g = where W.; the i-column of W. We use the shorthand notation the infinity norm of the matrix by > max1m[m] 2j=1 summarize the notations in T
[ W. W.. m p
p ppp. We denote W For ease of exposition, we
Table 2: Summary of notations involved in this paper.
Notations
Meaning
The feature of node i, 2; Rd.
2;
The label of node i.
X
The feature matrix nodes X [2F1, Fnl Raxd
y
The vector of labels, i.e. y (gh, M2, ......... Un) E R2. The graph filter, ie.. function of the adjacency matrix A. The adversarial perturbation.
((A)
(5(X)
The set of adversarial node {X = Ei,...., Rn): | 2all- S, r 2 1, [n]]
X)
The function of L-layer GCNs.
X),
The i-th element of the hypothesis f.
H
The feature representation of nodes L-th layer.
H
The feature representation of all adversarial nodes (-th layer.
w(
The weight matrix of I-th layer.
The norm bounds of the weight matrix.
Am... (F)
The TRC of the function class F.
The loss function.
Le
The Lipschitz constant of function
<(-)
The non-decrcasing I-Lipschitz activation function, c.g. ReLU activation.
p²
The Hölder conjugates by star, e.g. p" satisfying + = 1.
[r]]
The set of positive integers, i.c., [T]] = {1,....,L) L).
|| Ilp.ll -ll ||--
The ép- norm and the normm,, p. 2 1.
Before proceeding to prove main results, we introduce some necessary inequalities.
Lemma A.1. (Awathh et al. 2020) Let 1 S p, r S oo and be the dimension. Then,
||1||/- = s(r",p,d)) ,P,d), w1|rS1
sup
where s(r", p. d) +
Lemma A.2. Let 6 be 1-Lipschitz positive-homogennenn activation function. Then for any class of vector-valued functions F, and any convex and monotonically increasing function vb R. + [0, oc).
(1E
E
sup JEF JEF.
oe Σ KE(m)
(A))
(Io(A))loow)
Σ orl((A, x),1|
<2Eg JEFjela
sup
16

---

Published as a conference paper at ICLR 2025
Proof of Lemma A.2
Let W.1. W* #2..... Wan be the columns of the matrix W, we have
Σ 0
Σ
[(A))
max JEMN
kE|m]
R
max tE[n]
0
(max
Σ ((A))a)(((.
JE|M] kE/N)
< max j x
0.0 (19( A))
loc (AA
t=1
Σ 2: (19(4))] (I(A,))) | ))
Wa
W. ?
max je m
The supremum of this over all W.1: W W., en such that || 1 Σ W., S 2² must be obtained when |Ww,il = w for some I, and ||Waall for all + Therefore
(1Σ
Eg
sup fEF, Sw.JE
wb
Σ kE(N)
s(A) [(A))a](A,
<Eg
sup
Σ Wr
Σ
f(A,X)s
[
W..
JEF, SW,,kl
0, (19(A))l>x (f(,, Wai) )
-Eg
sup
fEF, wwllla=w.jElnl
<2B
sup JEF.IJW..ll=wwp
0e0 (Io(AA)l>> (F(A, X);, Woi)
(6)
where the last inequality follows from ((uu) S (u)) + (-=) and the symmetry in the distribution
of the random variables o; For incquality 6 having
T
2
sup FEF. W
+
Σ
(U(A,X); X)js W.:) oi [I9(A)]l (J(A,
<2E sup
V
alll((A)llo (((, W.i)
JEF. 1
x [lo(A))loo Woilla|
<22
sup
oof((A,))
JEF.IWWill=ww.eih
n
=2R, sup & (Io(A))loow) fEF-E[(]]
Σ Eoss(AXX))))
i=1
B PROOF OF THEOREM 4.1 [BINARY CLASSIFICATION]
Proof of Theorem 4.1
Let the function class of T-layer GCNs be defined by
F=
| || I ww [21] Raxd 4 R"
with the update rule:
H (()(())
(-1)
Rand H X,
17

---

Published as a conference paper at ICLR 2025
where the graph filter g(A): R=** H R"x", W R d; is the width of I-th layer, do d. dp = 1, and o(.) is ReLU activation. The corresponding adversarial counterpart defined by
F
inf ())(A,X); F.F. x)B((X)
Let the set of adversarial nodes of F be defined by X = Enl, where each C; is chosen by
T; arg (x):
inf
(A,
for i 1, .,... n and any E F. Denote Q m + n-m following inequality
With the definition above, we have the
QE
sup o, inf fEF 1=1
y. M.((A,)),
s
QBB
sup jEF t=1
o (f = Am (7)
xEB;(X)
where
8= - = 9(A)H W(l)
W (11 12, [ sw,
with update rule:
h ((o(()) -W()) H X,
where ((A) E Ruxn, W E xd for / [L - 1], and ((4) (4) E x1x1
We thus turn to bound R Rm,(() (F). By the definition of TRC.
H ()m (F)==E
Σ ai Σ
((4); Hf - w(())
sup
سa (| 1asw
JEImI
IQEE
sup
oie mmx (E(n)
9 (A))ss)
max
H wll))
[ lasw
sE(m
jE[n]
<QEa
sup
(A
Σ 0i
(1-11 w(ll
[ [aSwJE(x)
1 <Q log Eg
Al(o(A))lo
Σo;,
n
oi ( w(ll))
sup
cxp
A
1=1
1
<Q log Eg sup exp Allo(A)llocu jE(n)
(8)
A
1=1
We rewrite inequality 8 as
Q
x log E.
sup
exp
Alls(A)lloww
Σ 50.0 1=1
Σ 9(A)),
(L 2) w((h-))
SE
kE/ml
1 <Q x log
2IE, sup exp jEMN
Al :2
oi H Σ
a ( 1))
jz
where the last inequality follows from Lemma A.2 with (u))) steps, obtain
u.. By recursion
Σox o w( D)
Rm, (5) 10 log
E
exp (N1o(A))1<<w 1-11
Σ
sup ww
i=1
1 =Q
log
E sup exp (lls(A)] w sE(n]
Σ
(9)
)
i=1
18

---

Published as a conference paper at ICLR 2025
Let M ( and define random variable
Z = M sup jE(m)
Σ
o
i=1
where random as a function of the random variables 11.... n. Then,
1 log { Exp Xz)
L log(2)
1
+ デ
log X(Z - -E)] + EZ.
X
By Jensen's 's inequality and triangle inequality. EZ can be bounded by
EZ -M E. sup jE(n]
J
M E sup jE(n
o 2z 05)
p'
<M Eg sup jE[n]
0:00g
+
-=1
1=1
<M Eg sup
Σ
0
+ +s(r"
p. d)
Σ o - =z;](,)
jEIn]
i=1
1=1
n SM E. (1)
n
Σ
0,00
+ es((r" .p.
Σ oi
2m(n m)
V
(Bpr | + tes(r", Pp d))
n
where s(r", -.: d) PC Lit v=
/max $1 Bpn (2l if p 1 Mohri et al. 2018). Bp-
, if E (1,2), By = 1 if E [2, +oo) (Awathhi et al. 2020), the second inequality follows from Lemma A.1 and the last inequality is due the Rademacher variables (El-Yaniv & Pechyony 2009).
v2[
Note that Z is a deterministic function of the i.i.d. random variables dIy..,, on and satisfies
Z Z o ......,a - ( - o.) <2M sup ||ام|p
jE(n)
2M sup |aa + ã. 221lpp'
jE(n]
<2M sup jE(n]
| 11p2 + sup ||ã, - 2z11p-
jE(n)
<2M sup | ..pl. + Es(r' .p.
jE(n]
where the last inequality follows from Lemma A. This means that Z is sub-Gaussian satisfying a bounded-difference condition with variance factor
(2MR)² R2
where R= Su-puppeen |0yl|p- + Es(r" d), and satisfies
1 12
R=
log Exxp A(Z EZ)} < x
2
Letting À / 22L (2) (2)
and combining the above, the inequality (9) can be upper bounded as follows:
MR/n
0 1
A log { 2xxeep AZ
S <Q(EZ + 22og((2
< 2mm, (llgg || +Es(r", (o((r",,.)] d)) X X11,,p'
= (V2lo)))0= 1) +
ts(r", pp d))
19

---

Published as a conference paper at ICLR 2025
2n min-m] s(r" p, d) = dmaxio - 1, and Bpx = v 2log(22) if = 1, Bp
where Qm,
v2
- Vi
p (1. 2), Bpr pf E [2, +00). Combining inequalities 7 and (9), the proof
completed.
C PROOFS OF LEMMA 4.5 AND THEOREM 4.7 MULTIICLASS CLASSIFICATION]
Proof of Lemma 4.5 Let the function class F Raxd _2*k be defined in I.. Consider the activation function of the output layer as o(t) = Softmax(.). Let the pairwise class margin of [f(A,
node be defined as f""(AA X); prediction of the class u for node i. We would like to observe the relative change in error be- tween any two classes. Specifically, we consider the difference between the set of pairwise margin
[f(A, where [f, x),u denotes
(M (A, X); fu (A, x); Define (1)) and (1)) as the feature representation of X and X at I-th layer, respectively. Then,
fW (A. x): f (A,
((A),, H 1)
(W!l)
w(!!)
Σ I(A),,
H
(1-1) (W!ll) - w!!!)
jE|n]
JE(N]
<I1o(A) |ox]
max w!ll) wi!h)
Σ
g(A)
j.
(1-2) (1.-12) ( w((-11)
jE(n
kE(n]
<I19(A)
llee
W
w!l
max LE(n]
(max JEIn]
((4)ak)
(H (H!L-2) H(6-2) w(1-1))
kE(m)
<119(A) (lo(A))l 18
W (L)
w
(5)
11a
(L-1)
1|
max jE(n
H ((!-2)
HH/1" (1--2)
(A1 ( 11 w
11
(L-1)
112 (2
2a max jEfn
(X x,,) W
W (
(4-
12 | || W (1/1
max || xz 2211 jEIn]
<I19(A) W
w 11 II
W (1
(()) w |ps p, d)e.
(10)
According the definition of the ramp loss and the inequality above, we have
min 1(1: & arg max (A, X) bly))
((((K]
min XE
(I,(AAX)
2 26, min
min
If(A, )) IF( (f), ))bb))
vi (E
2e min [f, X kly, [f(A. X),b v(
max es(r" .p. ()pp))))((()))) p=((""p.dd)ll(())11 W!!! w! 11 II 0 ( 1,4%
(4((M(((. max Es(r" .p.):,.)))))())] KE[K]
|| ((1l))
2 (I(M(F(A)X))))) - max ss(r",,.))lo(A)) 11 KE[K]
w
|2 S 7)
20

---

Published as a conference paper at ICLR 2025
where s(r". .p.d) d) (0. the inequality (a) is due to the property of ramp loss, the inequality (b) is due to the definition of margin operator, the inequality (c) follows from inequality (TO), the inequality (d) comes from using triangle inequality, and the inequality (e) directly follows from property of ramp loss. This completes the proof of Lemma 4.5
Proof of Theurem 4.7
By the Ledoux- -allau--al contraction inequality, we know that Rm. (f F) - RRmm (M F) + Rm,n (V o F)).
(11)
For the right-hand side of the above inequality, Bm V F) can be bounded by
2es(r" P, d) (l9
W ww
(L) |
12
sup
max ke[k]
I| lI
1=2
x QE
$20 220mnes(r" (p
K| K| 112
|
w
sup I
22KQm es(r", p.
(12)
where 2m,
2n min j
We turn to prove the upper bound on Rm, (M o F).
Analyzing
analogously to the proof of Theorem
4.1 Rm. (M o F) has the following upper bound
QE
sup Sas
oi
Σ jE[n)
((A); K w!!!
(I
SQE,
sup
oo( sE(n)
max
g(A))s))
max jEIn)
(1-11) w.y!)
(1 1Sw
jEIm)
1 <Q log Ber
sup
exp
Al)g(A))loo
Σ ai (1(--1)
1) w!!!)) w!(h)) )
| (SS..jin)
1 log Bar sup exp
Allg(A)) koow Σ o, Ho 11
a
<Q x
sE/m]
-Q x
1 log Bo
Allg(A))looa)
Σo.0
E 9(A)s 2 ((((-)))
sup
exp
| ((SwJell)
kE(m)
<a 1
(lll(A)) w2 Σ H. 1))
x log
21 sup exp jE(n]
Repeating the process, having
2 log
2
exp {l(g(A)))
L-1
Σ o Jr, _oiXx..ooo))
sup I
1 = log
sup exp (Alo(A))) jE(m]
1 <0 log
2 exp
(Ala(())l
Σ
(13)
1=1
Denote M (lg(A))l and define the random function of the random variables d1, on as follows
Z = M.
Σ o
21

---

Published as a conference paper at ICLR 2025
Then,
I log { 2xxp exp X2)
L Log(2)
+
(Exp X(2 - R2)] + RZ
A
According well-known bounds the Rademacher complexity (Haagerup) 1981
Mohri al.
2018 Awasthi et al. 2020), having
2 log
(2d
X
2.p*
if =
Eg
Σ
og D'
I,-
2
X 12.p"
if
1 < 2
12.0*
if 2
where X (01, (#1,...;,,y Fn) Rexd
We thus have
n EZ M R Σ
0:00
S 1M8p-11X12.pp
(14)
1=1
where Bp. 2 log(d)) if p 1; Bp
/2
if E (1, Bp = 1f E [2, +
Mohri et al. 2018
Awasthi et al. 2020
Since deterministic function of .1..... nn and
satisfies
Zo σn) Z( 1......, 0z σn)
S2M
(15)
then Z satisfies a
property and Gaussian with the variance factor
x2 1p- = M
||= 10
1=1
and satisfies
1 Σ
2 1pp-
XM
Di=1
1
À (og(Eexp A(2 E2)) <
2
(2g and with the above, the inequality (13) can be upper bounded by M E. ||a.11..
Letting
2 1
x log f2" <Q (Z
RZ + (2
Σ a. 133
20m, M M (oggl 22 + Bp 112,pp
= mm ml ((A))l w (V (oglog()) + B) X 11
2n where Q = + 1 and Qm, min-
Combining the above, we obtain
Rm, F) < Qm (V/2oo(())) +1) 1)
X 1|,.p
(16)
Putting inequalities
12 and (66 backs into this completes the proof.
D PROOF OF PROPOSITION 5.1 [SGC]
Lemma D.1 (SGC), Let the robust surrogate loss be defined by
((((A Ui) = (M)( ((f(A,
where the worst-case error is
((((AX))) = max es(r", ps(r",p.d))lg(A)) - w (1 kE(K]
and s(r", ppr".p..) d) ( Then, we have
(A((AX)),,v) < (A x)
-WLC,,, $7).
22

---

Published as a conference paper at ICLR 2025
Proof of Lemma D.1 Analyzing analogously to the proof of Lemma 4.5 Consider the pairwise class
margin of node be defined as fr" (A, X); = [f(A, ))lu - [f(A )el. we then have
fuv (A,
f (),
( (. Xj. W (W!!) w:(')) Σ s(A) X,. w().. (W!') -w!l)
jE|n]
jEjn]
(Xj- - Xj+): w (W (L) w (
max vE|n]
max JEmn
jE(n)
(W!!) -w!l)) )1,
11e
max | xzy @z|lp=
5E(n)
<Ils(A))
(W!!) -w(l)) (lps(r" .P, d) max |, - 2z51r jEIn|
L-1
(A))(A) | wil 11a II
|| Ils((r p. d),
(17)
i=1
where the third inequality follows from Lemma A.2 According to the property of ramp loss, we have
E min M(JAAX)) x)))
(X)
Se, (min min [f(A, x) IF(A, x)
Va (xF:
<e, min (JA,, X )):lp= - [S(A, X) 1,
L-1 max es(e" p..r",,.,)llg(_ maxee(rr.p.)))l((4)1111. w w!l'l 8/PM
111
II 1=1
(e((M([(A,XX):)) - max Es(r", sp(r"",,d)llpppp (2.))l(())) kE[K]
W (2) ||I
(1)))))
(A max Es(r", .p. pp,))la(A) 1 (4) kE[K]
la
|| 11 S 2)
*
Theorem D.2 (restate Proposition 5.1 For any y 0, with probability at least - 8, we have for all f FF
1
1(3 E (X) s.l. Di * arg max k
[f4 }
i=
1 (X, S
max If (A,
max
Fyy + ((((AAX))))
2K
1mm.n ((((A) llow (Bp | |2 + Es(r". p. d)) + (maxf
/m /n }),
where s(r", p, d) = d (0. -b), Bps 222loog2220 ifp ifp= 1, By v2
r( 1ip
11 ifp (1,2).
v
Bp- = 1 E (2, +00), Qm,n mm(-m)
2n
Proof of Theorem D.2 Let the hypothesis class of SGC be defined by
F= f x)
xw w || |1. 1| S ww, [41}
(18)
where ( E x and dj is the width of I-th layer with d, = K and dg = d. According to Lemma D.I and the Ledoux-Talle Talagrand contraction inequality, have
1 Rm, ( F) S RRm, (M o F) + Rm,, ( ( o F)).
(19)
23

---

Published as a conference paper at ICLR 2025
Then, Rm, (M F) can be bounded by n
QEo
sup
max
{(A)(3
max se(mi
Jxs w w(y)
|| 1I Sw
(E(M)
JE(m)
<QIlg(A) blooo jEIn|
max Eo
Σ
p
1=1
n Σ
<Q]1g(A))1 1low Lo
o,00
i=1
5Q (Qmmll)(A)(1ll) Bp ||| 12,p'
(20)
where Qm,r V m(nn-mj Bpx
2n
v log( if 1; Bpr
-21-1-111
+
if
(1,2);
v/
Bpp = pf [2, t00).
For the second term on the right side of the inequality
19). Rm. C o F) is bounded by
L-1
n
max Es(r". p. ()d))lg(A)( ooo KE[K]
sup
(L)
11
||
QE
> 0
S.
<2Kes(r' -P, (l) flow Qm,a-
(21)
where Qm, V
m(nnmm) Combining Theorem 3.2 with inequality (9
2n
we complete the proof.
0
E PROOF OF PROPOSITION 5.3 |RESIDUAL GCN]
Lemma E.1 (Residual GCN). Let the robust surrogate loss be defined by (Af X);, s: 34) (, ((f(A,
where the worst-case error is
L-1
((((A,)))) = max Es(r", p, d) W 2 11 kE[K]
II W (1
+ 1) 1|
where s(r", ,p, d) = dm (0. 1 } Then, we have
((f(A,X);:) S XA, S 1 (M x):.))) (F(AAX)): 5
Proof of Lemma F. with the update rule
Recall the output of Residual GCNs: f(A X) Softmax H ((())
H (( ")) + H(- H = (
where (0) Rdxd' (L)) E Rdd xK ( e Rd xd' for = 1,...,L-1 --1.
Let O and O denote the feature representation of X and X at 1-th layer. We first ana- lyze the difference between set of pairwise margin (n,(A, X): f (A, X); for node i, where fuv (A, X); = [A, x) (A, (AAXX)) ))), having
(6( g( AA) L-2) 2) ((L- + H (L-2))
(w(") -w!!
jE(m]
(6( JEin]
g(A), i,j H (1-2) 2) w(1-1)) + H((122) (w!!) - (Wol)-W!! -w!!))
g(A) H (--2) H (L (L-2) ( + I.)) (with -w(!))
Σ ((A)..))
(H H (1 2) (L()-1) + In); w - w(())
max
max SE[n
(E(n)
jE[n]
W (T.)
wi(F) |1
( 1|2 + 1) max
[ (1-2)
H
30 (1-21
ru
JE(n]
24

---

Published as a conference paper at ICLR 2025
where I, denotes the Identity matrix and the second inequality is due to the Lipschitzness of the activation function Φ Applying recursive steps, we further obtain
L-1
W (L)
W (L)
(2l99(A)
+ 1)
max sefm
(X - xj.) |
1=1
L-1
[W!
(L)
(111g(()) (l)
112 1) || 11-("" pp d) max j. x,1b-
jE(N]
L-1
w (A)l L
CII
112 11
112 + 1)1l
|| Ips(r" p. p.E
where s(r", p, d) (maxx(0, (0...- } and the second inequality follows from Lemma A.2
By the property of ramp loss, the following inequality holds:
Eg( min (x
X).
<6 min
min [A, x)x ):l): (F(A, x)())
va (x)
Se, min (A, x) - [f(AA)):ls
max ss(r", .p, .p. d I1l II W 112 1)) ViZu
L-1
().M( - max KE[R]
dp.))) wh l|
II (1 (0 1|2 1)1l (k)
3I(M(F(A,X);))) - max (,)"',))))l9(A) w 1
I|2 + 1) 11) 11 S 7). (Il
KE[K]
Theorem F.2 (restate Proposition 5.3 for any 7 > O, with probability at least 1 - 8, we have for all F.
1E3 E (X) s.t. yo arg max D'E(K]
(A,,))
71
1=
1
1[f (A, Daly S max ff (A, byy
+ 0m,n
m
4K
+ Qm, y 116( (1) + 1) Tog(2)L + B) | 12p- + =s(r", ,p, d)).
where Om, = O(max 1
7m (--m))) }), s(1* -0 .p. d) = fmax((. + 1), Br = 2 log(2d) if = 1, + ip (1, Bp- if 12, +00), Qm,
By )
2n m[n-m] m)
VT
Proof of Theorem E.2 With Lemma E.T and the Ledoux- Ledoux-Talagrand contraction inequality, we have
Rm. ( F) s (Rm,, (M o F) + Rm,, oVo F)).
(22)
Let the hypothesis class of Residual GCNs be defined by
F= ==(AA,,) Softmax (L-1) (()) ( || sw,eE [b]}
(23)
25

---

Published as a conference paper at ICLR 2025
with the update rule
H = ((O(A)(H(H)))))))))))))) + H(-),,
H = XW
where W(L) E
W R
E Rdxd', w 'dd''d'
xd' for forl=1 = I. 1.
Applying the triangle inequality and Lemma A.2 we have the following upper bound on Rm, ( (MoF)
QE
sup |w
Σ 01
H
(1-1)
1)
w!ll)
< <QuB,
sup | 11llaSw
Σ
oi Φ Σ
9(A):,
fz
(1-22) (14-2) + H
im1
jE[n]
SQuEB
sup 1| 11ll55w
n
0 Σ a(A):
H/: 11 W(l-))) ( + sus
Σ
o,
H (L- (--2)
jE(n)
1 log 2E sup exp jE(n]
(wo A) lloow + 1)
Σ
1=1
=Q
1 log
E sup exp jE(n!
(wu(ll(A)) + +1)-11
Σ
2, 00 )
i=1
= x
1
log
2n sup exp ( + 1)6-1 jE(N]
Σ
n
,iX, pM)) )=²)
1 =Q
log
B exp
+ 1)d
Σ Eaaall
)
(24)
x
Let M = (ollo(A))loc) + 1)e and consider random variable
Z = M
Σ o
We then have
A log
1 Exp
{ 2 2 exp Xz
L log(2)
+ lE exp A(Z -EZ)] + EZ.
1
X
According to the inequalities Gaussian with the variance
14 and
15
we know that EZ < B, |X and Z is sub-
n
Σ 2M a
11- = M Σ
||:; 11
and satisfies
XM Σ
|| 112
log Eexp X(2 -EZ)] <
ii=!
2
Letting À= /20. (2)
the inequality 24 is bounded by
M, Ex ||..1
1 o log {2r 22 {2) <Q [B + 2 22gg(2))TM
|
{Qmaw(l((A))loo + 1)t (22 log (2)L+ B) || 11
where Q= -/2 + "² Qm. > m m. and Bp = logd)) if p = 1: Bp. = v21
2n
if E (1,2): Bp= = =iff o00) Thus,
Rm, (M e F) S (mm + 1) (V 2log(2)T + 1) |X 1,p--
26

---

Published as a conference paper at ICLR 2025
For the TRC of the worse-case, by || || w for E [L], we have
Rm, ( F) 52Kes(r' pp, p.d)wllg(A)ll (w + 1)4 x QE oj
2 PP d) A) A) (w + 1)
Putting the above estimation back into the inequality (2) and combining Theorem 3.2 this completes the proof.
where Qm,n
m mm
F PROOF OF PROPOSITION 5.5 |GCNII]
Lemma F.1 (GCNII), Let the robust surrogate loss be defined by (A, x); v:) = (M(((A, x) ((J(A, X):));
where (J )): is ma[
[W(()) (V)) |lpe((r* pp. d)A and A is defined by
+/
L-1
L-1 II (1 a) (2)l +
L-1
Σ
((L a) (lg
II
W 11)) +1).
[=1
W (1 (1, + (W and s(r" spr",p.d) = max (0. (0, -
Proof of Lemmal F.1 the update rule
The propagation of the GCNII is S(A, X) -Softmax (1.-1)) ((()) with
H
- ())(- + a a (H) ((1 3) 3) + (WW)), H = x
where I, is the identity matrix, ( E Rdxd' W(I) E Rd K w E Rd xd' for I E [L - 1].
Denote ( (1 I, + (W(). Let H and H denote the feature representation of
X and X at 1-th layer, respectively. Consider the difference between set of pairwise margin
fur (A, X): ));- fr (A, X); of node i, where (A, (A, = [S(A, - [f(A, X) having
H (L--1) 1) ((L - w - H (L-1)
(W(L) W!())
i
(L -w!!' |11 H (1-1)
(H((11))
H! (1--1)
1l:
ft
it
WWL w |11 ((1 - a)) Σ g(A) )i. H (H ((L)2)) + 0: (H! H W(1-1))
jE(m)
<W (L)
w 111 (((11)) 2|2 (11 (1 aa)
a) Σ ((A),, (1 (1(22))) 2))
jE(m]
a (H (
(W( -w!! 1| (((1))) (11 a)
max
mmxx
Σ g(A)sss (Hi!! (HL
H!! 21
tE(n
iE(n)
jE(n)
a ( x;llor)
( (L)
w || (1-1)) 11 (1 ())l JE(n
max
(
H ja
(1(1-111
j-
all (| |r("" p. d) ã,-- - xzil.r)
( - w ||| (1-111)) 2 (11 (1- (1)=))ll(AA11 max
H (2)-))
H 1111- (2]
je(m
a || p. d.)))..
27

---

Published as a conference paper at ICLR 2025
where s(r", P, p,d) d the inequality (a) follows from Lemma A.2 and the inequality (b) is due to | - æolr S.. E.
By recursive steps, further obtain
L-1
W w 111
a)
(2llo()))
max
H
(0)
H
||
je(m]
L-1
W lps((r .pdd)
(Ll-a)ll9(A)[1
II k=L-1-1
W 112) + +1)
a:) | 12 (A) (())
max jE(m
|| 2311p'
L-1
a
a|l Ips((r ..rr.pp.d p.d)E
((1 ()))
II
(1)) +1))
(L)
(
(1 - a:) (1
W Ips(r", Pp ,p,sr"",,d)e d)+
L-1
W
00) Ins((r pdd
Σ (1-aa) ((-a))lb(A11a
II (1 + +1))
W!l w hh /hes(""rrrr""" .p. d)A,
where A is defined by
L-1
(10) + +1). T-1
II - (1- IalllAA)))))) + a - a))a())))
II A-1-1-1
i=1
1=1
According to the property of ramp loss, we have
G min X):, X)
S6,( min *f x
min
[fAA, X) X)im: - [F(A,, x)l:;)
<6,
min [f(A, X )el - USA, X) of
max
WV(L)
(L)
-w!L || ((( Iees(r" | ppd))))))))))
<6, (M (A,X), x). - max
I
(L)
|||
W| Ippe(rr (pes(r".p,.))))
KE[K]
<I(M(f(A, 34) max KE[K]
W (.!.
| |pes(r",p.d))) < 7).
Theorem F.2 (restate Proposition 5.5 for any 7 > 0, with probability at least we have for all F.
1
113 (X s.t. D1 # arg max [f X ) yE(K]
m
(=++1
HIf(A x ) 5 max (A (A, X) ((J(A,))))) 3/
Vn- - }) + 4KQm,
+ O m
(vlog(2)L + 1)B | + +2Kes(r", Sp0((''',.0 d))
mm
x w² ( (1-a) (1-a)]l((A)]lt + Bw) + +al1 a)
lg le(A))l (1 - 3 Bw)))
28

---

Published as a conference paper at ICLR 2025
where s(r", p, d) = (1 Bp /2 log 2d) ifp= = L, By v2[ + ifp E (1.2).
p
Bp. = -ifpE +00), Qm.n V
2n m(n-m)
Proof of T'heorem F22
With Lemma F.1 and the Ledoux-Tallggrad contraction inequality, we have
Rm ( o F) (Rm. (M F) + Rm. (v o o F)).
(25)
Let the hypothesis class of GCNII be defined by
F= X) = (- : || S s1L [L]]
(26)
with layer-wise update rule:
H < - a)g( A) H (1 + +aH ((1 - 3) + BW"")), H = xW
where I, is the identity matrix, W E Raxd', W(L) E Rd and W E m
xd' for E [L- 1].
Denote (' (1 3) + (w for l [L 1]. We then have | 11 S (1 3) + Bw.
For the right-hand side of inequality 25
Rm (M F) is bounded by
QE,
sup [
Σ
oj
H (1-
w! 49
(1)
i=1
H, (1-1)
<QB sup
i=1
n
SQWE.
sup 1Ia
Σ 0,0 a11 iE|n]
max Σ s(A)sa) H (6-2) + aH! w(l--))|
1=1
jE(m)
0 ((1-a)]9((A)) 1!!-! + ~HH (((l--))
SQUEE
sup (1a
i=1
(0)
1 log 2r
(ww/)
Σ ((1 (11-a)lli a))lo( (A)l H + (
sup exp jEin]
1=1
log 2 <Q
sup |I
exp
(Awot( (11 ())l az
Σ
oi H H 2) 2)
+ a Σ
o,,,, (0))))
1=1
im1
(b) 1
n
=Q x
- log 2E sup exp (1-)((1)))l((AA) Σ jE(n]
o. H (1)
+ Bp. 1 |
jz
where W = (1- B) 3w. Bp- = 2 log( if = 1; Bp = /2
if E (1, 2];
Bp = 1 pf E +20). the inequality (a) follows from Lemma of (Golowich et al. 2018), and the
inequality (b) follows from the bounds on the Rademacher complexity given by Awasthi et al. (2020).
Applying recursive steps, Rm, (M F) can be further bounded by
n Σ o ,xX,, 1oxx1+ i=1
log log2"E.
E'
exp (1
sup | Su(jEn)
x
a(1 - -a)w= Bp- |
2.p- Σ llo((A)) (1
<Q \
log 1og2"Bn Ea exp (1 (1)1(1 A))l
Σ
0, +
p-
a(1 - a. | 112,0
Σ (lo(A))lo
1=0
29

---

Published as a conference paper at ICLR 2025
where W (1 -B) + Bw. Denote U a(1 ap
| 2,p- Σi=o l19(A))lbe and M
(1 w wwili1111 ())lg(A)) We define the following random variable
12 Σ 0
Z M
+..
Then we have
1 A
{ 2' E exp Xz)
L (2)
log
+ A
Exp A(Z -EZ) + EZ
A
With the inequality (14, it is clear that
EZ M Eg
Σ
a,
+ s MB || |2, + U
Note that a deterministic function of 01,..., nn and satisfies
Z(oI...., -((
Tn) S2M ||
(27)
which implies Z satisfies a bounded-difference property and is sub-Gaussian with the variance factor
Σ [2M| | M
2 lIp..
i=1
Therefore, the following inequality holds
2M 1
log E exp A(Z EZ)} <
2i=1
2
21. (2g
Letting
the following inequality holds
M, v Σ._ |...
1 log E2'Eex SQ EZ (2
Σ |
x
50m, (V20og())) 1) || 112,pp + +U)
2n where Qm, m(n-mj' and Bp- 2 if = 1; Bp. = v2 - Lig"
1
if E (1,2);
v
Bpt = 1ff 12, +20). Thus, we have the following upper bound on Rm, (M o).
Qm (o2l(V/l2))222 + 1)B,- 12.-~ (1- + a(1 - a)
Σ
19 (1)
1=0
where W =(1 + Bw. We proceed to derive an upper bound on Rm ( a F), that
QE.
sup [e
((A(((,))))
<2Kes(r* pp d)w ((1 (11 (1-)))l((A)]5 + a(1 a:)
Σ
llg [I
QE
Σ
1=0
22mm p. d)w (1- -
+a(1 - a) Σ (19(A))l(s
where Qm, V m(n-m) mj = (1 - B3 + Bw. and s(r",p,d) = +
2n
30

---

Published as a conference paper at ICLR 2025
G LIMITATIONS
We outline a few limitations of the current adversarial generalization analysis for GCNs. Since Rademacher complexity-basee analysis methods are used in this paper, our bounds suffer from the exponential depth dependence similar to (Bartlett et al., 2017 Golowich et al. 2018). Nonetheless, the derived high-probability generalization bounds for GCNs in adversarial settings are highly non- trivial, which provides theoretical guidance for improving the adversarial robustness. Moreover, this paper does not involve topology attacks, which leads to the limitation of theoretical results. However, our analysis can provide valuable theoretical insights into the generalization of topology attacks. Given the similar settings of topology attacks and node attacks, where adversarial perturbations measured within the norm space, the methodology (c.g., Lemma B.2) developed in this paper could be expanded upon the topology attack address the outer maximization of the adversarial loss and tighten the generalization bounds. It is worth noting that unlike node attacks, one can perturb the graph topology at the first layer, the last layer, the arbitrary intermediate layer, and all the layers of GCNs, thus posing additional analysis challenges. We will leave this interesting study as future work.
H ADDITIONAL RELATED WORK
Adversarial Generalization Theory. Adversarial robust generalization in Euclidean space has been studied extensively in recent years. Yin et al. (2019) investigate the adversarial generaliza- tion problem under fo -nom attacks via the lens of Rademacher complexity. They derive the high-probability generalization bounds for linear classifiers and one-hidden-layer neural networks, in- dicating the additional perturbation term that should be suppressed seriously affect the generalization performance. |Aassth al. (2020) establish the generalization bounds for one-hidden-layer additive neural networks under general perturbation attacks by extending the work of (Yin et al.) (019)) to the e,-norm attacks for arbitrary r 2 1. Several recent work (Khim & Loh 2018 Tu et al. 2019
Mustafa et al. 2022) has aimed to analyze the generalization properties of deep neural networks in adversarial settings. Khim & Loh (2018) provide the upper bounds of the adversarial risk by leveraging tree based decomposition. Their results depend on the assumption that each propagation path in the network can be optimized independently w.r.t. the perturbation, leading to vacuous bounds in (Khim & Loh| 2018). Tu et al.) (2019) introduce transport map between distributions and develop a new risk bound for multi-layer neural networks by means of covering numbers under the Lipschitz condition. MMstafa al. (022) establish the adversarial risk bounds for deep neural networks under both additive- perturratpnttt attacks and transform attacks via a novel usage of covering numbers. Xing al. (2021) and Xiao et al. (2022) investigate the adversarially robust generalization of learning algorithms from the perspective of algorithmic stability, showing that the maximization process w.r.t. adversarial perturbations causes the worse algorithmic stability than natural training. Although all the aforementioned work provides valuable insights into the adversarial generalization problem, it is difficult apply them to adversarial graph learning due discrepancies in learning paradigms and data characteristics. This work makes towards this by providing generalization guarantees of GCNs under node perturbation attacks, which is the first touch for adversarial graph learning to the best of our knowledge. Related work is summarized in Table 3
Table 3: Summary of generalization analysis for adversarial learning (NNs-Neural Networks; h- number of classes; mh number of unlabeled samples; n-the number of samples).
Reference
Model Structure
Artack Type
Analysis Tool
Convergence Rote
Learning Setting
Yin et al. (2019)
One-layer NNs
Ew norm
Radomacher complexity
O(k/vm)
Inductive
Awasthi (2020)
norm
Inductive
Klim and Lob (2018)
Ex
Rademadier complexity
Inductive
Tu (2019)
norm
Covering number
(0//m)
Inductive
Mustafa al. (2022)
Deep
norm
Covering number
(lag(R))
Inductive
Transfomation
Local Rademacher complexity
0(1/))
Inductive
Xing al. (2021)
Inductive
norm
Algorithmic stability
00/%)
Xiao et al. (2022)
Inductive
Ours
Deep GCNs
5, norm
Transductive Rademacher Complexity
OlA max
Transductive
31

---

Published as a conference paper at ICLR 2025
1 ADDITIONAL EXPERIMENTS FOR NUMERICAL DISCUSSION
Experiment details. Unless otherwise specified, we apply a two-layer network architecture for GCN, SGC, GCNII, and Residual GCN (Kipf & Welling 2017: Wu et al.) 2019 Chen al.) (2020)) where the number of hidden units for each layer is fixed to 16 or 64. For GCNII, the parameter or set by default to 0.5, 8 is set log(? @ + 1). where A 0.1 and I is the number of layers. We use ReLU function as activation function. The Adam optimizer (Kingma & Ba (013) with the learning rate 0.01 used the training process. The implement GeForce RTX 3080 GPU. The runtime of each experiment is about 200s~2hh.
Attack methods. We evaluate the generalization performance under different attacks including FGSM, BIM, and PGD. Figures 8 13 present the empirical generalization errors with dimensions of adopted datasets under attacks. As we can see, the experimental results for different attacks have the same overall trend (i.e., the smaller the dimension, the smaller the generalization error), which can not be affected by the choice of attack methods.
Feature dimension. We study the effect of feature dimension on the generalization performance of SGC, GCNII, and Residual GCN in adversarial settings. We compare the empirical generalization error with different dimensions, including the original dimension d, [d/2]. and [d/4]. For conve- nience, a single-layer neural network with ReLU activation is used to learn low-dimensional feature representation. As shown in Figures 14 16 the empirical generalization error decreases with node features, which suggests that cow-dimensional features help improve the adversarial generalization.
Regularization. We also evaluate the effect of regularization on the generalization ability for SGC, GCNII, and Residual GCN under adversarial attacks. Similarly, we consider & nn-oomm regularized model and observe the empirical generalization error with different regularization coefficients X. where A set as 0, 0.05, 0.10, and 0.15. Figure 17 19wshow that the empirical generalization error of the regularized model is smaller than that without, Hence, the regularization is beneficial to improve the generalization performance.
Model depth. We study the effect of the number of layers the adversarial generalization for SGC, GCNII, and Residual GČN. Figures 20 present the empirical generalization errors with different depths. As limited by its representation power. The generalization ability of GCNII and Residual GCN almost can not be affected by the number of layers. Hence, we suggest that the choice of model architecture is important for achieving the adversarial generalization.
see, the generalization performance of SGC deteriorates depth increases, which
Tightness. To evaluate the tightness between theory and experimental observations, we compare the generalization bounds in theory and empirical generalization errors w.r.t. feature dimensions in Figure 23 where the bounds are quantitatively computed based on the adopted dataset and the model parameters. The experimental results show that both theoretical and empirical generalization errors decrease as the feature dimension decreases, which is consistent with our theoretical findings. Hence, results provide meaningful practical guidance for improving the adversarial generalization of the learning models in a certain sense.
Generalize to other models. To evaluate the scalability of the theoretical findings, we further investigate the impact of the feature dimension on the generalization performance of S2GC (Zhu & Koniusz 202T) and GIN (Xu et al., 2018)) under PGD attacks. The empirical errors with different dimensions for the adopted datasets are plotted in Figure 24 demonstrating the low-dimensional feature mapping can enhace the adversarial robustness of the learning models. This observation aligns with our theoretical findings.
32

---

Published as a conference paper at ICLR 2025
Ceneralization Error Generalization Error
1.0
Citeseer
Generalization Error
0.7
Cora
Generalizatio Error
0.7
Pubmed
0.9
0.6
0.6
0.8
0.7
0.5
0.5
0.6
0.4
0.5
0.3
0.3
0.4
A
0.3
00 1o-1y
(--1
0.2
0.2
0.2
0.1
0.1
0.00
0.004
0.008 0012
0.16
0.00
0.004
0.008 0.012
0.016
0.00
0.004
0.008
0012
0.016
&
0.40
CS
Generalization Error
0.16
Physics
Generalization Error
ogbn-arxiv
0.35
0.14
0.30
- (D-A2" Ca- A
0.12
0.20
0.25
0.10
0.20
0.08
0.15
0.15
0.06
0.10
0.04
0.10
0.05
0.02
0.00
0.00
0.05
(P-7
0.00
0.004 0.008
0.012 0.016
0.00
0.004
0,008 0.122 0.016
0.004
0.008
0.012
0.016
&
Figure 3: The empirical generalization error (mean value and standard deviation) with graph filters, where depth is set to 6. denotes the maximum allowable perturbation.
Citeseer
Cora
Pubmed
Seneralization Error
1.0
Deneralization Eror
0.9
Generalization Error
0.8
0.8
0.9
0.004
0.8
0.004
0.7
0.004
0.7
0.7
0.002
0.6
0.6
0.6
0.000
0.5
0.000
0.5
0.5
0.4
0.4
0.4
0.3
0.3
0.3
0.2
0.1
0.2
0.0
0.1
0.1
2
7
8
9 10
12
2
4
6 7 8 9
101111
12
2
3
556 6 7 8 1011 12
Number of Layers
Number of Layers
Number of Layers
Generaline Generalization lizatiot Error
0.5
CS
Generalization Error
Physics
Generalization Error
0.4
ogbn-arxiv
0.4
8 0.002
0.004
0.4
c 0.002
0.3
0.002
0.004
0.3
0.000
0.3
- 0.000
0.2
0.2
0.2
0.1
0.1
0.1
0.0
0.0
0.0
10
12
5
9 1011
4
6
Number Layers
Number
Layers
Number Layers
Figure 4: The empirical generalization error (mean value and standard deviation) with different depths. denotes the maximum allowable perturbation.
33

---

Published as a conference paper at ICLR 2025
Citeseer
Cora
Pubmed
Generalization Error Generalization Error
1.0
Deneralization Errror
1.0
Generalizat leaaiiiiiionn Error
0.8
0.9
0.9
0.7
0.8
0.8
0.6
0.7
0.7
0.5
0.6
0.6
0.4
0.5
OCN
0.5
0.4
0.4
0.3
0.3
Residual GEN
0.3
Resibal
0.2
Rowddas OCN
OCNT
0.2
0.2
0.1
0.00
0.004
0.008
0.012 0.016
0.00
0.004 0.008 0.012 0.016
0.00
0.004
0.008
0.016
CS
Physics
ogbn-arxiv
0.30
Generalization Error
0.30
Generalization Error
0.30
GCN
0.25
SGON
0.25
SGON
0.25
0.20
Residual GCN
0.20
Residial GCN
0.20
GCNT
0.15
0.15
0.15
0.10
0.10
0.10
SGCN
0.05
0.05
0.05
Residual OCN
ACNI
0.00
0.00
0.00
0.00
0.004 0.00S 0.012 0.016
0.00
0.004 0.008 0.012 0.016
0.00
0.004
0.008
0.012 0.016 E
&
Figure 5: The empirical generalization error (mean value and standard deviation) for different model architectures, where depth is set to 6. E denotes the maximum allowable perturbation.
Citeseer
Cora
Pubmed
Generalization Error
1.0
Generalization Error
1.0
Generalization Error
0.7
0.9
0.9
0.6
0.8
0.8
0.7
0.7
0.5
0.6
0.6
0.4
0.5
0.5
0.4
0.1
0.4
0.3
0.3
0.3
0.3
0.2
0.5
0.2
0.2
0.7.
a-07
0.1
0.1
0.1
0.00
0.004
0.008
0.012 0.016
0.00
0.004 0.008
0.012 0.016
0.00
0.004 0.008
0.012
0.016
3
3
CS
Physics
ogbn-arxiv
Generalization Error
0.16
Generalization Error
0.20
Generalization Error
0.40
0.14
0.35
0.12
0.15
0.30
0.25
0.10
0.10
0.20
0.08
0.15
0.06
0.3
0.05
0.3
0.10
0.5
0.04
0.05
0.02
0.7
0.00
0.7
0.00
0.00
0.004
0.008 3
0.012 0.016
0.00
0.004 0,008 0.012 0,016
0.00
0.004 0.008
0.012 0.016
Figure 6: The empirical generalization error (mean value and standard deviation) of GCNII with the parameter where depth is set to 6, denotes the maximum allowable perturbation.
34

---

Published as a conference paper at ICLR 2025
Citeseer
Cora
Pubmed
Generali carrraaiztiiin Error
1.0
Generalization Error
0.6
General Feneralization Error Generalization Error
0.8
10.8
00.9
0.5
0.7
min- min-0.1
0.6
0.6
10.7
0.4
0.5
min
mir 0.3
0.5
0.3
0.4
0.3
0.4
0.2
0.3
0.1
0.2
min-
min- 0.5
0.1
mble
min- 0.3
0.5
0.2
0.1
0.0
0.0
0.0
0.00
0.014 0.008 0.012 0.016
0.00
0.014
0.008
0.012 0.016
0.00
0.004 0.008
0.112 0.016
CS
Physics
ogbn-arxiv
cenerraization Error
0.12
Generalization Error
0.12
0.40
mer 0.1
0.35
0.10
min 0.3
0.10
0.30
0.08
0.08
0.25
0.06
0.06
0.20
0.04
0.04
0.15
mir
0.10
mvo 0.3
0.02
0.02
0.05
0.00
0.00
0.00
0.00
0.004
0.008
0.012
0.016
0.00
0.004
0.008
0.012 0.016
0.00
0,004 0.008
0.012 0.016
3
Figure 7: The empirical generalization error (mean value and standard deviation) with the label rate m/n.& denotes the maximum allowable perturbation.
Seneralization Brro
1.0
Citeseer
fieneralization Error
1.0
Citeseer
fieneralization Error
1.0
Citeseer
0.9
0.9
0.9
0.8
0.8
0.8
0.7
0.7
0.7
0.6
0.6
0.6
0.5
0.5
0.5
d/2
d//2
d/2
0.4
d4
0.4
d/4
0.4
d/4
0.3
0.3
0.3
0.00
0.000
0.008
0.012 0.016
0.00
0.004
0.008
0.012 0.016
0.00
0.004 0.008
0.012 0.016
(a) FGSM
(b) BIM
(c) PGD
Figure 8: The empirical generalization error (mean value and standard deviation) for the Citeseer dataset under different attacks. denotes the maximum allowable perturbation.
Generaliz or
1.0
Cora
Generalization ErT
1.0
Cora
Generalization Error
0.7
Cora
0.9
0.9
0.6
0.8
0.8
0.7
0.7
0.5
0.6
0.6
0.5
0.5
0.4
0.4
Td/2
0.4
d/2
0.3
d/2
0.3
0.3
d/4
0.2
0.2
0.2
0.00
0.004
0.008 3
0.012
0.00
0.004
0.008
0.012 0.016
0.00
0.004 0.008 0.012
3
3
(a) FGSM
(b) BIM
(c)
PGD
Figure 9: The empirical generalization error (mean value and standard deviation) for the Cora dataset under different attacks. & denotes the maximum allowable perturbation.
35

---

Published as a conference paper at ICLR 2025
Pubmed
Pubmed
Pubmed
Generalizatio Error
1.0
Genera inerrlizatiinn Error
1.0
Generalization Error
0.7
0.9
0.9
0.6
0.8
0.8
0.7
0.7
0.5
0.6
0.6
0.5
0.5
0.4
0.4
0.4
0.3
0.3
d/4
0.3
d4
0.2
0.00
0.004
0,008
0.012
0.016
0.2
0.004
0.008 0.01200016
0.2
0.00
0.004 0.008
0.012 0.016
(a) FGSM
(b) BIM
(c) PGD
Figure 10:
The empirical generalization error (mean value and standard deviation) for the Pubmed dataset under different attacks. denotes the maximum allowable perturbation.
Generalization Eiror
0.55
CS
Generalization Error
0.55
0.5
CS
(eneralization Error
20.18
CS
0.16
0.4
0.4
d/2
0.14
[d/4]
0.3
0.3
0.12
0.2
0.2
0.10
0.08
0.1
dd/2
0.1
Td/2
d/4
d/4
0.06
0.0
0.0
0.04
0.004
0.012 0.016
0.00
0.004
0.008 0.012
0.004 0.008 0.012 0.016
(a)
FGSM
(b) BIM
(c) PGD
Figure 11: The empirical generalization error (mean value and standard deviation) for the CS dataset under different attacks. e denotes the maximum allowable perturbation.
Generalization Error 1
5 0.7
Physics
0.8
Physics
60.16
Physics
0.6
0.7
0.5
0.6
0.14
Td/2]
0.5
0.12
dd4
Ceneralization
0.4
0.4
0.10
0.3
0.2
d
Generali
0.3
0.2
d
0.08
0.1
d22
0.1
0.06
0.0
0.0
0.04
0.00
0.004
0.008
0.012 0.016
0.00
0.004 0.008
0.012 0.016
0.00
0.004 0.008 0.012 0.016
3
(a) FGSM
(b) BIM
(c) PGD
Figure 12: The empirical generalization error (mean value and standard deviation) for the Physics dataset under different attacks. e denotes the maximum allowable perturbation.
36

---

Published as a conference paper at ICLR 2025
ogbn-arxiv
ogbn-arxiv
ogbn-arxiv
0.8
Peneralization Error
0.8
Generalization Error
0.30
0.7
0.7
0.25
0.6
0.6
Generalization
0.5
0.5
0.20
0.4
0.4
0.15
0.3
0.3
d/2
d/2
0.2
d'4
0.2
d'4
0.10
d/2
0.1
0.1
d/4
0.05
0.00
0.004
0.008
0.012 0.016
0.00
0.004 0.008 0.016
0.00
0.004
0.008
0.012 0.016
3
(a) FGSM
(b) BIM
(c) PGD
Figure 13: The empirical generalization error (mean value and standard deviation) for the ogbn-arxiv dataset under different attacks. denotes the maximum allowable perturbation.
Citeseer
Cora
Pubmed
Teneralization Error
1.0
Generalization Error
0.8
Ceneralization Error
0.7
0.8
0.9
0.7
0.6
d/2
0.6
0.7
0.5
0.6
0.5
0.5
0.4
0.4
0.4
T/2
0.3
0.3
0.3
d/4
d/4
0.
0.00
0.008
0.016
0.2
0.00
0.004
0.008
0.012 0.016
0.2
0.00
0.004
0.008
0.012 0.016
CS
Physics
ogbn-arxiv
Generalization Error
0.30
Generalizate Generalization Error
0.30
Generalization Error
0.30
0.25
0.25
d/2
0.25
0.20
d/4
d/4
0.20
0.20
0.15
0.15
0.15
0.10
0.05
0.10
0.10
d/2
d4
0.00
0.05
0.05
0.00
0.004
0.008
0.012 0.016
0.00
0.004 0.008
0.012 0.016
0.00
0.004
0.008
0.012 0.016
3
3
Figure 14: The empirical generalization error (mean value and standard deviation) with different feature dimensions for SGC. e denotes the maximum allowable perturbation.
37

---

Published as a conference paper at ICLR 2025
Generalization Emor Gencralization Error
0.9
Citeseer
Gencralization Error
0.8
Gencralization Error
0.7
Pubmed
0.8
0.7
0.6
0.7
0.6
0.6
0.5
0.5
0.5
0.4
0.4
0.4
d
0.3
d/4
d/2
0.3
d/2
0.3
d/2
d/4
0.2
0.2
0.2
0.00
0.004
0.008
0.012 0.016
0.00
0.004
0.008
0.012 0.016
0.00
0.008
0.012
CS
Physics
ogbn-arxiv
0.30
Generalizer Generalization Error
0.30
Generalization Error
0.40
0.25
512
0.25
d 512
0.35
256
d 256
0.30
0.20
64
0.20
d= 64
0.25
0.15
0.15
0.20
0.10
0.10
0.15
d/2
0.05
0.05
0.10
d/4
0.00
0.00
0.05
0.00
0.004
0.008
0.012 0.016
0.00
0.004 0.008 0.012 0.016
0.00
0.004
0.008
0.012 0.016
3
Figure 15: The empirical generalization error (mean value and standard deviation) with different feature dimensions for GCNIL. denotes the maximum allowable perturbation.
Citeseer
Cora
Pubmed
Generalization Ineralization Error
1.0
Generalization Error
0.7
Teneralization Error
0.7
0.9
d
0.6
0.6
0.8
d/2
0.7
0.5
dd4
0.5
d/4
0.6
0.4
0.4
0.5
0.3
0.4
d/4
0.3
0.2
0.00
0.004
0.008
0.012
0.016
0.00
0.004 0.008
0.012 0.016
0.00
0.004
0.008
0.012 0.016
3
3
Generalization Error
0.14
CS
Generalization Error
0.16
Physies
Generalization Error
0.40
ogbn-arxiv
0.12
d/2
0.14
[a/2
0.35
[d/2
0.30
0.12
d/44
0.25
0.10
0.10
0.20
0.08
0.08
0.15
0.06
0.10
0.06
0.04
0.05
0.00
0.004
0.008 0.012 0.016
0.00
0.004 0.008 0.012 0.016
0.00
0.004 0.008 0.012 0.016
3
&
Figure 16: The empirical generalization error (mean value and standard deviation) with different feature dimensions for Residual GCN. denotes the maximum allowable perturbation.
38

---

Published as a conference paper at ICLR 2025
Citeseer
Cora
Pubmed
Generalization Error
1.0
Gennralization Error
0.8
Generalization Eirror
0.7
0.9
0.7
0.6
0.8
0.6
0.7
0.5
0.6
0.5
0.4
0.5
0.4
A
J. 0,00
0.4
0.05
0.3
0.055
0.3
0.10
2 0.1.0
0.3
0.15
0.2
0.2
2-0.15
0.2
1.00
0.004
0.008
0.012 0.016
0.00
0.004 0.008
0.012 0.016
0.00
0.004 0.008
0.012 0.016
3
3
CS
Physics
ogbn-arxiv
Generalizate miiizitiion Error
0.30
Feneralizzaton Error
0.30
Generalization Error
0.30
-000
A-000
0.25
2- 0.05
0.25
A- 0.05
0.25
0.10
0.10
0.20
0.15
0.20
0.15
0.20
0.15
0.15
0.15
--000
1-0.05
0.10
0.10
0.10
0.18
0.05
0.05
0.05
0.00
0:004 0,008 0.012 0.016
0.00
0.000
0:012 0.016
0.00
0.004 0.008
0.012 0.016
3
Figure 17: The empirical generalization error (mean value and standard deviation) of SGC trained with & regularization for different regularization parameters (i.e., A). denotes the maximum allowable perturbation.
Citeseer
1 0.8
Cora
Pubmed
Generalization lizatizziiinnnn Error Generalizatie lizatiioo 5
0.9
Generalization Error
0.7
0..8
0.7
0.6
0.7
0.6
General leraalliitionn
0.6
0.5
0.5
0.4
0.5
0.05
0.00
0.4
A- 0.05
0.4
2. -000
0.3
2 0.15
0.3
0.10
0.3
A 0.15
0.2
0.2
0.2
0.00
0.004
0.008
0.012
0.016
0.00
0.004 0.088
0.012 0.016
0.00
0.004
0.008
0.012
0.016
3
0.30
CS
fennralization Error
0.30
Physics
Seneralization Error
0.40
ogbn-arxiv
2 0.00
0.25
0-0.5
0.25
0.00
0.35
0.20
0010
-015
0.20
2
0.10
0.05
0.30
0.15
0.25
0.15
0.15
0.20
A -0000
0.10
0.10
0.15
0.055
0.05
0.05
0.10
2. 0.10
0.00
0.00
0.05
0.00
0.004 0.008 0.012
0.016
0.00
0.004
0.008
0.012 0.016
0.00
0.004 0.008 0.012 0.016
3
Figure 18: The empirical generalization error (mean value and standard deviation) of GCNII trained with & regularization for different regularization parameters (i.e., A). denotes the maximum allowable perturbation.
39

---

Published as a conference paper at ICLR 2025
Citeseer
Cora
Pubmed
1.0
Teneralization Error
0.7
0.7
0.9
1. -0000
0.6
0.0.55
20.6
0.8
Generalize lization
0.7
0.5
0.15
0.5
0.6
0.4
0.4
0.00
2..5
0.05
-
0.4
0.10
0.15
0.3
0.3
0.10
-015
0.3
0.2
0.2
0.00
0.004
0.008
0.012
0.016
0.00
0.004
0.008
0.012 0.016
0.00
0.004
0.008
0.012 0.016
CS
Physics
ogbn-arxiv
feneralization Error
0.16
Generalization Error
0.16
Generalization Brror
0.40
0.14
00000
1- 0.05
0.14
0.05
0.35
7. 0.00
0.12
0.10
0.12
0.10
0.30
2 0.10
2- 0.15
0.25
0.15
0.10
0.10
0.20
0.08
0.08
0.15
0.06
0.06
0.10
0.04
0.04
0.05
0.00
0.004
0,008
0.012 0.016
0.00
0.004
0,008
0.012 0.016
0.00
0.004 0.008 0.012 0.016
3
Figure 19: The empirical generalization error (mean value and standard deviation) of Residual GCN trained with regularization for different regularization parameters (i.e., A). & denotes the maximum allowable perturbation.
Citeseer
Cora
Pubmed
Dineralization Forror
Seneralization Error
0.9
Generalization Error
0.8
0.9
0.8
0.004
0.7
0.004
0.7
0.022
0.7
0.6
0.002
000000
0.6
0.000
0.5
0.5
0.5
0.4
0.4
0.4
0.2
0.3
0.3
0.3
0.1
0.2
0.2
0.0
0.1
0.1
5
6 7
101112
2 3
101112
2
5
6 7 101112
Number of Layers
Number of Layers
Number of Layers
CS
Physics
ogbn-arxiv
Generalivation Error
0.5
Generalization Error
0.5
Generalization Error
0.4
0.4
0.004
0.4
6 0.004
0.002
8 0.002
0.3
0.000
0.3
0.000
0.000
0.2
0.2
0.1
0.1
0.0
101111 0.0
0.0
9 Number Layers
4
5
6
7
8
2
101112
7 8 9 101112 Number Layers
4
Number Layers
Figure 20: The empirical generalization error (mean value and standard deviation) with different depths for SGC. denotes the maximum allowable perturbation.
40

---

Published as a conference paper at ICLR 2025
Citeseer
Cora
Pubmed
Generalization Enror
Generalization Error
Generalization Error
0.9
0.004
0.002
0.002
0.7
0.000
0,000
0.6
0.4
0.5-
0.4
0.4
0.3
0.3
0.2
0.2
0.2
2
3
4
5 6
9 10
101112
12
2 3
4 5 6 7 9
101112
2 3
7 8 9 101111 12
Number of Layers
Number of Layers
Number of Layers
(ieneralization Frror
0.30
CS
Generalization Error
0.18
Physics
Generalization Eiror
0.30
ogbn-arxiv
0.25
0.002
0.16
0.002
0.004
0.25
8 0.004
6 0.002
0.20
0.000
0.14
0.000
0.20
5 0.000
0.12
0.15
0.15
0.10
0.10
0.08
0.10
0.05
0.06
0.05
2 3
12
4 5
101112
5
101112
Number of Layers
Number of Layers
Number of Layers
Figure 21: The empirical generalization (mean value and standard deviation) with different depths for GCNII. denotes the maximum allowable perturbation.
Cileseer
Cora
Pubmed
Generalization Error
1.0
Generalization Error
0.7
Generalization Error
0.6
0.9
0.8
8 0,002
c
0.004
0.6
0.004
0,002
0.5
==0.004
0.002
o 000
0.5
11,000
0.000
0.7
0.4
0.6
0.4
0.3
0.5
0.3
0.2
0.2
0.3
4
101112
101112
2 3
101112
Number of Layers
Number of Layers
Number of Layers
Physics
ogbn-arxiv
Generalization Emor
0.30
deneralization Error
0.20
feneralization Error
0.40
0.25
0.20
0.002
0.000
0.004
0.16
0.18
0.14
c
0.000
0.30
0.35
0.25
c 0.004
0.002
0.15
0.12
0.20
0.10
0.10
0.15
0.08
0.10
0.05
4
6
101112
0.06
0.05
Number of Layers
4
12
2
101112
Number of Layers
Number of Layers
Figure 22: The empirical generalization error (mean value and standard deviation) with different depths for Residual GCN, denotes the maximum allowable perturbation.
41

---

Published as a conference paper at ICLR 2025
Generalization Bound
110
Citeseer
Generalization Bound
110
Cora
Generalization Bound
200
Pubmed
100
100
[d/2]
[d/2]
180
90
d/4
90
dd/4]
160
80
80
70
70
140
60
60
120
d/2
50
50
[14
100
0,00
0.004 0.008 0.012
0.00
0.004 0.008 0.012 0.016
0.00
0.004 0.008
0.012 0.016
3
3
3
Generalization Eлror
1.0
Citeseer
Generalization Error
0.7
Cora
Generalization Error
0.7
Pubmed
0.9
0.6
0.6
0.8
0.7
0.5
0.5
0.6
0.4
0.4
0.5
d22
0.3
d/2
0.3
0.4
d4
dM
0.3
0.00 0.004 0,008
0.01200016
0.2
0.00
0.004 0.008 0.01200016
0.2
0.004
0.008
0.016
3
3
Theoretical generalization bounds and empirical generalization errors of the adopted datasets w.r.t. feature dimensions. denotes the maximum allowable perturbation.
Figure 23:
Generalization tillizationn 1
1..
Citeseer
1.0
Cora
00.
Pubmed
0.9
0.9
0.7
0..
Genera ineerllization nattion
0.8
0.7
Generalizatio iatiitiiin
0.6
0.7
1.6
0.5
S2GC
0.6
0.5
dd/2
0.5
0.4
d
d/2
0.4
d/2
0.4
[d4
0.3
d:4
0.3
d/4
0.3
0.2
0.2
0.00
0.004 0.008
0.012 0.016
0.00
0.004 0.008 0.012 0.016
0.00
0.004 0.008
0.012 0.016
3
3
3
Generalization Error
1.0
Citeseer
Lieneraizzation Error
0.9
Cora
Generalization Error
0.7
Pubmed
0.9
0.8
0.6
0.8
0.7
GIN
0.7
0.6
0.5
0.6
0.5
0.4
d
0.5
0.4
d/2
d:4
0.4
0.3
[d2]
dd/4
0.3
d/2
d14
0.3
0.2
0.2
0.00
0.004
0.008
0.012 0.016
0.000.004
0.008
0.012 0.016
0.00
0.004 0.008
0.012 0,016
3
3
&
Figure 24: The empirical generalization error (mean value and standard deviation) with different dimensions for S2GC and GIN. denotes the maximum allowable perturbation.
42


Reviews:
[{"review_id": "XAWpivm46Q", "reviewer": "Reviewer_HnSA", "summary": "This paper presents1 a theoretical study on the generalization capabilities of Graph Convolutional Networks (GCNs) under adversarial conditions. The research aims to establish high-probability generalization bounds for GCNs in node classification tasks when exposed to adversarial perturbations. Using Transductive Rademacher Complexity (TRC) and a novel contraction technique, the authors examine the relationship between generalization error and adversarial robustness, accounting for key factors such as feature dimension, network depth, and graph normalization. Their theoretical contributions are validated with empirical experiments on benchmark datasets, highlighting the efficacy of different GCN architectures, including SGC, Residual GCN, and GCNII, under adversarial training.", "questions": "1. Comparisons to non-adversarial generalization bounds could benefit from further discussion on the trade-offs between robustness and model capacity in adversarial versus standard training settings. Can you add a specific subsection or paragraph that explicitly compares the derived bounds to non-adversarial bounds? It would clarify how model capacity and robustness trade off differently in these two contexts, strengthening the implications of the theoretical results.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. A comprehensive theoretical framework to analyze adversarial robustness in GCNs is provided.\n2. The proposed method can be applied to a wide range of models and loss functions, including some deeper GNNs.\n3. The experiment results demonstrate the effectiveness of the proposed method in reducing generalization error.", "weaknesses": "1. Only an $l_{\\infty}$-PGD attack is considered in the evaluation. Including additional state-of-the-art graph adversarial attacks would provide a more comprehensive evaluation of the proposed method’s robustness. For instance, it would be beneficial to evaluate against attacks such as [1, 2] to give clearer insights into performance under diverse adversarial scenarios.\n2. The proposed method is currently limited to feature perturbation attacks, while structural attacks are often more powerful and prevalent. Could the authors discuss the possibility and challenges of extending the method to structural perturbation attacks? Specifically, it would be helpful to address: 1) the key differences between feature and structural attacks that would need to be considered, 2) which parts of the current analysis might be adaptable to structural attacks, and 3) any new theoretical tools required for handling these types of attacks.\n\n[1] Adversarial Attacks on Neural Networks for Graph Data.\n\n[2] Adversarial attacks on node embeddings via graph poisoning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LHA8xRfTrr", "reviewer": "Reviewer_7Djx", "summary": "The paper introduce some theoritical bounds of the generalization of GCN and its variants. Through these bounds, the authors revealed the impact of mode parameters on the generalization behavior using the theory of Radamacher Complexity.", "questions": "1/ I cannot see how the generalization gap $Gen(f)$ in an indicator of the the generalization performance: 1-  $Gen(f)$ is the absolute difference of the adversarial error in the training set and the test set. 2- Since you re  considering the advesarial training, the adversarial training loss should converge to very low value compared to the adversarial test loss. 3- For me a good quantification of the generalization is $|\\mathcal{L}_u - \\tilde{\\mathcal{L}}_u |$ to consider in order to quantify the impact of the adversarial training. \n\n2/ In the Related Work section, you forgot to mention other type of Defence technique: GNNs thant enhace the robusntess by adapting the model architecture and seems to works well, For example, you can cite GCORN and Parseval networks [1,2]. \n\n3/  For me the empirical evaluation is too limited, ploting the generalization gap is not enough. You need to consider at least the test accuracy. And you can for example do an ablation study on different adversarial training strategies. \n\n4/ This is just a suggestion: I suggest generalizing the theoritical findings to the graph classification tasks, and compare the adversarial training to other generalization enhacement frameworks such data augmentation which is also linked to Rademacher Complexity. Ex of data aug techniques for graphs : G-Mixup [3]\n\n5/ The assumption you made about the loss function in Section 4.1 are not usually used in practice. For classification task, we usually use Cross entropy (which you also used in your experiments). Your assumption could work in node regression task perhaps. \n\n6/ This is just a suggestion:For the ablation study on the graph filter, you can try others such as Random-walk Normalised Laplacian, Unnormalised Laplacian matrix.\n\n4/ I recommend to evaluate the robustness against adversariat attacks using the Attack Success Rate (ASR), the percentage of attack attempts that produce successful adversarial examples, which implies that close input data should be predicted similarly [4]\n\n[1] ABBAHADDOU, Y., ENNADIR, S., Lutzeyer, J. F., Vazirgiannis, M., & Boström, H. Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks. In The Twelfth International Conference on Learning Representations.\n\n[2] Cisse, M., Bojanowski, P., Grave, E., Dauphin, Y., & Usunier, N. (2017, July). Parseval networks: Improving robustness to adversarial examples. In International conference on machine learning (pp. 854-863). PMLR.\n\n[3] Han, Xiaotian, et al. \"G-mixup: Graph data augmentation for graph classification.\" International Conference on Machine Learning. PMLR, 2022.\n\n[4] Jing Wu, Mingyi Zhou, Ce Zhu, Yipeng Liu, Mehrtash Harandi, and Li Li. Performance evaluation of adversarial attacks: Discrepancies and solutions. arXiv preprint arXiv:2104.11103, 2021.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The theoritical backgroud sounds interesting. The paper introduce some theoritical bounds of the generalization of GCN and its variants. Through these bounds, the authors revealed the impact of mode parameters on the generalization behavior using the theory of Radamacher Complexity.", "weaknesses": "I think you can still developp other aspects in the papers. For example, the empirical evaluation is very limited. See the points below in details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AxrkDLhGNU", "reviewer": "Reviewer_2X9z", "summary": "The authors study adversarial generalization bounds for feature perturbations for GNNs. For this, the authors employ the Transductive Radamacher Complexity (TRC) to quantify the expressivity of hypothesis classes of GNNs and thereafter use this to derive generalization bounds. The authors instantiate their results for various GCN variants and empirically verify their results.", "questions": "1. Why do the authors bound the l2 and lp norm of $W^{(l)}$ with the same constants? Aren't those norms in practice often of different magnitude?\n1. How tight/useful are the derived bounds? While I appreciate the analysis of the relationship between, e.g., dimensions and generalization, it would also be nice to understand how well the theoretical generalization errors relate to the practically observed ones.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. First to study adversarial generalization bounds for GNNs\n1. A plethora of interesting theoretical insights that are verified empirically", "weaknesses": "1. This work solely studies feature perturbations and could elaborate on this earlier in the document\n1. The authors could elaborate a bit on the specifics of how perturbations are introduced in a transductive setting. I.e., are perturbations of test data applied after training or before? A change after training is arguably inductive (e.g. see cited work of Gosch et al. 2024).\n\nMinor:\n- Equation 1 is hard to parse", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Bupp6mejc5", "reviewer": "Reviewer_6SrP", "summary": "The work tackles the problem of generalization of node classification when subject to adversarial attacks. Specifically, the study delves into the theoretical side, which is missing from the literature, by providing generalization bounds based on the Transductive Rademacher Complexity.", "questions": "- Could you please provide insights on the possible extension to structural perturbations? \n- It would be great to clarify some of the hypothesis provided in the paper and their relation to the tightness of the provided bound.\n- How generalisable is your study to other models such as GIN, GAT or spectral models? \n- On the experimental results, could you also results on other models such as to understand if empirically the results holds ?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper’s aim and perspective is well motivated and overall well written and presented.\n- The presented theoretical study is very interesting and clearly useful.\n    - Specifically, the connection between generalization and the dimension provided in Theorem 4.1 is very relevant. This can also serve as motivation to techniques that considered Weight regularisation as a defense approach while ensuring a good clean accuracy.\n- The experimental setting seems to validate the theoretical insights.", "weaknesses": "- The analysis seems to rather focus on the GCN. While this is great, it would also be interesting to generalization to other more recently used models (Attention based GAT for instance).\n- From my understanding of the problem setup, it seems that authors rather focus on adversarial perturbations targeting the node features. More clarification on this on the paper would be good.\n- Additionally, possible insights on generalization to the adversarial structure perturbations could be useful.\n\n\n- In the hypothesis class of GCNs (Eq. 1), the authors assume that the model’s weight norms are smaller or equal to $w$. Is there a specific motivation there? While I would agree that the existence of $w$ is clear (simply by taking the max over the norms), doesn’t that affect the tightness of the bound provided in Theorem 4.1 ?\n\n- While the proposed experimental results confirms some of the concepts that were derived from the theoretical insights. It would also also be great to delve in the tightness of the proposed bounds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)