Towards Generalization Bounds of GCNs for Adversarially Robust Node Classification

Authors: Wen Wen, Han Li, Tieliang Gong, Hong Chen
Primary area: learning theory
Keywords: Generalization Analysis; Adversarial Learning; Graph Convolution Networks;  Node Classification；Node Attacks

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.

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 8

Reviews and discussion:
<thread>
creation date:
1730637884774

thread_type:
official_review

<thread_object>
creator: reviewer_6srp

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

strengths:
- 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.

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

questions:
- 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 ?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730713529068

thread_type:
official_review

<thread_object>
creator: reviewer_2x9z

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

strengths:
1. First to study adversarial generalization bounds for GNNs
1. 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
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

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?
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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730897596740

thread_type:
official_review

<thread_object>
creator: reviewer_7djx

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

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.

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. 

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731239908382

thread_type:
official_review

<thread_object>
creator: reviewer_hnsa

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

strengths:
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.

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

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732187845301

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Would you mind confirming if you have further questions? Thanks!

comment:
Dear Reviewer HnSA, Reviewer 7Djx, Reviewer 2X9z, Reviewer 6SrP

We appreciate reviewers for their efforts and time in providing constructive comments. We have carefully considered the reviewers' concerns/advice and provided as much refinement and experiments as possible to address the issues regarding the submission. Would you mind checking our response and confirming whether we have addressed your concerns? If there are any further questions or suggestions, we will try our best to solve them to improve our work.

Sincerely,

The authors of Paper 5326
</content>
</thread_object>

</thread>
<thread>
creation date:
1732786866821

thread_type:
official_comment

<thread_object>
creator: area_chair_bm7b

<content>
comment:
I would like to encourage the reviewers to engage with the author's replies if they have not already done so. At the very least, please 
acknowledge that you have read the rebuttal.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper propose generalisation bounds for GCN under adversarial attacks based on the transductive rademacher complexity. They study the effect of feature dimension, network depth, and graph normalization. The work tackles only feature perturbations. Some reviewers mentioned that this fact should be better highlighted and the authors concur. While some reviewers found the experimental evaluation to be limited other reviewers stated that "The experiment results demonstrate the effectiveness of the proposed method in reducing generalization error.". Overall, given the theoretical focus of the work I deem the experiments to be sufficient. The insight can provide guidance for improving GNNs' adversarial generalization.