Towards Generalization Bounds of GCNs for Adversarially Robust Node Classification
Generalization Analysis; Adversarial Learning; Graph Convolution Networks;  Node Classification；Node Attacks
Yes
No ethics review needed.
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.
1. A comprehensive theoretical framework to analyze adversarial robustness in GCNs is provided.
2. The proposed method can be applied to a wide range of models and loss functions, including some deeper GNNs.
3. The experiment results demonstrate the effectiveness of the proposed method in reducing generalization error.
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.
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.
2. 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.

[1] Adversarial Attacks on Neural Networks for Graph Data.

[2] Adversarial attacks on node embeddings via graph poisoning.
Yes
No ethics review needed.
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. 

2/ 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]. 

3/  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. 

4/ 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]

5/ 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. 

6/ 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.

4/ 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]

[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.

[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.

[3] Han, Xiaotian, et al. "G-mixup: Graph data augmentation for graph classification." International Conference on Machine Learning. PMLR, 2022.

[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.
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.
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.
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.
Yes
No ethics review needed.
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?
1. 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.
1. First to study adversarial generalization bounds for GNNs
1. A plethora of interesting theoretical insights that are verified empirically
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.
1. This work solely studies feature perturbations and could elaborate on this earlier in the document
1. 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).

Minor:
- Equation 1 is hard to parse
Yes
No ethics review needed.
- Could you please provide insights on the possible extension to structural perturbations? 
- It would be great to clarify some of the hypothesis provided in the paper and their relation to the tightness of the provided bound.
- How generalisable is your study to other models such as GIN, GAT or spectral models? 
- On the experimental results, could you also results on other models such as to understand if empirically the results holds ?
- The paper’s aim and perspective is well motivated and overall well written and presented.
- The presented theoretical study is very interesting and clearly useful.
    - 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.
- The experimental setting seems to validate the theoretical insights.
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.
- 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).
- 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.
- Additionally, possible insights on generalization to the adversarial structure perturbations could be useful.


- 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 ?

- 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.
This paper presents a comprehensive generalization analysis of graph convolution networks for node classification tasks under adversarial attacks, by Transductive Rademacher Complexity.
@inproceedings{
anonymous2024towards,
title={Towards Generalization Bounds of {GCN}s for Adversarially Robust Node Classification},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=cp3aW7C5tD},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Generalization Analysis; Adversarial Learning; Graph Convolution Networks;  Node Classification；Node Attacks
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/b273fca830a6d9ab16f4c9e6ceff4c34a3c641d2.pdf
learning theory
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/3f511f964efde7938b1ca67910f32a0c39821c6c.zip
Towards Generalization Bounds of GCNs for Adversarially Robust Node Classification
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission