Towards Generalization Bounds of GCNs for Adversarially Robust Node Classification

We thank Reviewer 6SrP for the valuable comments and positive feedback! We will answer your questions as follows: (the modifications in the revised manuscript are marked in blue for easy reading)

A1 Extension to topology attacks. Given the similar adversarial generation settings and adversarial loss definitions for topological attacks and node attacks, we suggest that the methodology (e.g., Lemma B.2) developed in this paper could be expanded upon the topology attack to address the outer maximization of the adversarial loss and tighten the generalization bounds.

To be more specific, let the adversarial graph be generated from $\{\tilde{A}: \Vert A - \tilde{A}\Vert_\infty \leq \epsilon \}$, where $A$ and $\tilde{A}$ denote the original graph matrix and its adversarial counterpart. The adversarial loss w.r.t. adversarial graph is defined by $\max_{\Vert A - \tilde{A}\Vert_\infty \leq \epsilon} \ell(f(\tilde{A},X)_i,y_i) = \hat{\ell} (\min _ {\Vert A - \tilde{A}\Vert _ \infty \leq \epsilon} y_if(\tilde{A},X)_i)$,

where $\hat{\ell}:\mathbb{R}\rightarrow\mathbb{R} _ +$ is monotonically increasing. Analyzing analogously to the node attacks and applying the contraction technique in Lemma B.2, we obtain

$Q \mathbb{E} _ {\sigma}\Big[\sup _ {f\in\mathcal{F}}\sum _ {i=1}^n\sigma _ i \inf _ {\Vert A - \tilde{A}\Vert_\infty \leq \epsilon} y_i f(\tilde{A},X) _ i \Big] \leq Q \mathbb{E} _ {\sigma} \Big[\sup_{f\in \mathcal{F}} \sum _ {i=1}^n \sigma _ i f(\hat{A},X) _ i \Big],$

where $\hat{A} = \arg\inf _ {\tilde{A}:\Vert A - \tilde{A}\Vert _ \infty \leq \epsilon} y_i f(\tilde{A},X)_i$. If perturbing the graph topology at the last layer, then

$Q \mathbb{E} _ {\sigma} \Big[\sup_{f\in \mathcal{F}} \sum_{i=1}^n \sigma_i f(\hat{A},X)_i \Big]$

$= Q \mathbb{E} _ {\sigma}\sup _ {\Vert W^{(L)}\Vert _ 2\leq \omega} \bigg[\sum _ {i=1}^n \sigma_i \Big(\sum _ {j\in[n]} g(\hat{A}) _ {i,j} f^{(L-1)}(A,X) _ {j*} W^{(L)}\Big)\bigg]$

$\leq Q\frac{1}{\lambda} \log \Bigg( 2 \Vert g(\hat{A})\Vert_\infty \omega \mathbb{E} _ {\sigma}\sup _ { j\in[n]} \exp \lambda \bigg\Vert\sum _ {i=1}^n \sigma _ i f^{(L-1)}(A,X) _ {j*} \bigg\Vert \Bigg)$

$\cdots$

$\leq Q\frac{1}{\lambda} \log \Bigg(2^L \Vert g(\hat{A})\Vert_\infty \Vert g(A)\Vert^{L-1}_\infty \omega^L \mathbb{E} _ {\sigma} \sup _ {j\in[n]} \exp \bigg(\lambda \Big\Vert\sum _ {i=1}^n \sigma _ i x _ {j}\Big\Vert _ {p*} \bigg)\Bigg)$

Subsequent proof is similar to Eq (9) in Page 17. Notably, the upper bound of $\Vert g(\hat{A})\Vert^L_\infty$ for specific adversarial graph filters needs to be proved. Moreover, it remains to analyze the effect of perturbing the graph topology at the first layer, any intermediate layers, and all layers on generalization. We will leave this interesting study as future work. To refine this paper, we have added the discussion about topology attacks in Appendix G. Please refer to Page 30 in the revised paper.

A2. Connection between empirical results and theoretical bounds. To further illustrate the tightness of the derived bounds to empirical observations, we quantitatively compute the theoretical generalization errors of the GCN model on the adopted dataset. As shown in Figure 23 (Page 41 of the revised paper), theoretical generalization errors decrease as the feature dimension decreases, which has the same overall trend as empirical observations. Hence, we suggest that these theoretical findings can provide effective guidance for improving the adversarial generalization of GCN models.

A3. Weight norm. We clarify that for simplicity of notation, denote by $\omega$ the max bound over the norms, where $\omega=\max\{\omega_2,\omega_p \}$, $\Vert W^{(l)}\Vert_2 \leq \omega_2$, and $\Vert W^{(l)}\Vert_p \leq \omega_p$. It is noteworthy that as discussed in Remark 4.2 (Page 5 of the revised paper), this weight norm constraint can help weaken the negative impact of adversarial perturbations, yielding tighter generalization bounds. Furthermore, the weight norm constraint is typically required to be a small constant, thereby rarely affecting the tightness of the bound. Inspired by the theoretical results, we adversarially train a robust model by leveraging the regularized adversarial training objective. Our experimental results further demonstrate the importance of an appropriate weight regularizer for achieving good generalization performance (Page 9 of the revised paper), and show that the norm of the weights could be less than or equal to 1. For clear reading, we have added the definition of $\omega$ below Eq. (2) in the revised paper.

We thank Reviewer 2X9z for the insightful comments and positive feedback! We will answer your questions as follows: (the modifications in the revised manuscript are marked in blue for easy reading)

A1. Mention feature perturbations earlier. Following the reviewer's suggestion, we have introduced the concept of the node perturbation attack at the beginning of the Introduction and elucidated the focus of this paper. Please refer to Page 1 of the revised paper.

A2. Experimental setup of perturbations. We clarify that adversarial perturbations are added to test nodes after training, which avoids a biased evaluation due to memorization, as mentioned in [1]. We have added this description in Experimental Setup (Page 9 of the revised paper).

A3. Same norm constant. We clarify that for simplicity of notation, denote by $\omega$ the max bound over the $\Vert \cdot\Vert_2, \Vert \cdot\Vert_p$-norms, where $\omega=\max\{\omega_2,\omega_p \}$, $\Vert W^{(l)}\Vert_2 \leq \omega_2$, and $\Vert W^{(l)}\Vert_p \leq \omega_p$. For clear reading, we have added the definition of $\omega$ below Eq. (2) in the revised paper.

A4. Correlation between theoretical and observed generalization errors. To address your concerns, we compare both the theoretical and empirical generalization errors w.r.t. the feature dimension for the adopted datasets in Figure 23 (Page 41 of the revised paper), where the theoretical generalization error is computed based on the adopted dataset and the derived bounds. In Figure 23, the top three sub-figures present the theoretical generalization error, while the bottom three sub-figures present the experimental generalization error. Our experimental results show that both theoretical and empirical generalization errors decrease as the feature dimension decreases, with the same overall trend, which is consistent with our theoretical results. Therefore, we believe that our results can provide effective theoretical guidance for enhancing the adversarially robust generalization of GCNs.

Reference:

1. Gosch et al. Adversarial training for graph neural networks: Pitfalls, solutions, and new directions. NIPS. 2024.

I thank the authors for clarifying most of my points and adjusting the paper accordingly!

Regarding the theoretical bounds. While I do understand that it might be challenging, if not impossible, to derive simple bounds that are tight, is it correct that the theoretical bounds are about 2 orders of magnitude looser than the empirically observed ones?

Nevertheless, I want to emphasize that if think that the paper is interesting regardless of how tight the bounds are.

We thank Reviewer 7Djx for the insightful feedback! We will answer your questions as follows: (the modifications in the revised manuscript are marked in blue for easy reading）

A1. Evaluation criteria about generalization gap. The difference between the population risk $\tilde{\mathcal{L}}_u(f)$ and the empirical risk $\tilde{\mathcal{L}}_m(f)$ is known as the generalization gap of $f$, denoted by $\mathrm{Gen}(f) = \tilde{\mathcal{L}}_u(f) - \tilde{\mathcal{L}}_m(f)$. A small generalization gap $\mathrm{Gen}(f)$ indicates that on average or high probability, the empirical performance of $f$ on the training dataset can be taken as a reliable measure of generalization to unknown samples. A large amount of work [1-6] aims at establishing the generalization error bound from the lens of statistical learning theory to guarantee the generalization of learning models.

Notably, the generalization gap in theory usually cannot be calculated due to the unknown data distribution. Extensive work [1-4] thus considers an empirical proxy of the generalization gap: $\vert \textrm{Adversarial Training Accuracy} - \textrm{Adversarial Test Accuracy}\vert,$ and then validate the theoretical findings by evaluating the empirical generalization errors with relevant factors. Accordingly, we utilize the empirical generalization error rather than ASR or other metrics to evaluate the adversarially robust generalization of the models, which is reasonable and realistic for verifying our theoretical findings.

A2. Related work. Thanks for the recommended literature. We have cited the work of GCORN and Parseval networks in Page 2 of the revised paper.

A3. Assumption. We clarify that the cross-entropy loss, defined by $L_{CE} = -\sum_{i=1}^n y_i\log(\hat{y}_i)$, where $y_i$ is the true label and $\hat{y}_i\in[0,1]$ is the probability of the predicted label, is indeed monotonically non-increasing loss function, which satisfies the monotonicity assumption considered in this paper (Page 4). It is noteworthy that this assumption is mild and realistic, encompassing commonly used losses such as the hinge loss, logistic loss, and exponential loss [1, 4], and has been widely used in adversarial learning literature [1, 4-6] to derive the non-trivial bounds. For clear reading, we have added a more detailed discussion about the assumption in Page 4 of the revised paper.

A4. Experiments about graph filters. In Figure 3 (Page 32), we indeed compare the empirical generalization error with different graph filters, including the unnormalized Laplacian graph, symmetric normalized graph, and the random-walk graph. The experimental results show that the unnormalized graph has larger empirical generalization errors than the normalized graphs. Hence, we argue that normalizing the graph matrix can facilitate the adversarial generalization of GCNs. This also validates our theoretical findings.

A5. Experiments about adversarial training strategies. In Appendix I (Page 31 of the revised paper), we also have compared the empirical generalization errors with feature dimensions for different adversarial training strategies, where the adversarial examples are generated by FGSM and BIM attack algorithms. The experimental results in Figures 8-13 (Pages 34-36) show that the low-dimensional feature mapping helps enhance the generalization performance of adversarial training models. This further verifies the effectiveness of our theoretical findings.

Reference:

1. Yin, Ramchandran, Bartlett. Rademacher complexity for adversarially robust generalization. ICML. 2019.

2. Verma and Zhang. Stability and generalization of graph convolutional neural networks. KDD. 2019.

3. Deng et al. Graph convolution network based recommender systems: Learning guarantee and item mixture powered strategy. NIPS. 2022.

4. Xiao et al. Stability analysis and generalization bounds of adversarial training. NIPS. 2022.

5. Khim and Loh. Adversarial risk bounds via function transformation. 2018.

6. Awasthi et al. Adversarial learning guarantees for linear hypotheses and neural networks. ICML. 2020.

We thank Reviewer HnSA for the valuable comments and positive feedback! We will answer your questions as follows: (the modifications in the revised manuscript are marked in blue for easy reading)

A1. Diverse attacks. We have conducted additional experiments to evaluate the generalization performance under FGSM and BIM node attack methods. The empirical generalization errors with dimensions of adopted datasets under attacks are plotted in Figures 8-13 (Pages 34-36 of the revised paper). The experimental results show that the low-dimensional feature mapping can help improve the generalization ability of the learning models against adversarial attacks, which is consistent with our theoretical findings.

A2. Discussion about topology attacks. In the revised paper, we have added more discussion about topology attacks in Appendix G (Page 30 of the revised paper). We emphasize that given the similar adversarial generation settings and adversarial loss definitions for topological attacks and node attacks, the methodology (e.g., Lemma B.2) developed in this paper could be expanded upon the topology attack to address the outer maximization of the adversarial loss and tighten the generalization bounds. However, further investigation is needed regarding the norm bounds of adversarial graph filters and the impact of perturbing the graph topology at different network layers (including the first, last, intermediate, and all layers).

To be more specific, let the adversarial graph be generated from $\{\tilde{A}: \Vert A - \tilde{A}\Vert_\infty \leq \epsilon \}$, where $A$ and $\tilde{A}$ denote the original graph matrix and its adversarial counterpart. The adversarial loss w.r.t. adversarial graph is defined by

$\max_{\Vert A - \tilde{A}\Vert_\infty \leq \epsilon} \ell(f(\tilde{A},X)_i,y_i) = \hat{\ell} (\min _ {\Vert A - \tilde{A}\Vert _ \infty \leq \epsilon} y_if(\tilde{A},X)_i)$,

where $\hat{\ell}:\mathbb{R}\rightarrow\mathbb{R} _ +$ is monotonically non-increasing. Analyzing analogously to the node attacks and applying the contraction technique in Lemma B.2, we obtain

$Q \mathbb{E} _ {\sigma}\Big[\sup _ {f\in\mathcal{F}}\sum _ {i=1}^n\sigma _ i \inf _ {\Vert A - \tilde{A}\Vert_\infty \leq \epsilon} y_i f(\tilde{A},X) _ i \Big] \leq Q \mathbb{E} _ {\sigma} \Big[\sup_{f\in \mathcal{F}} \sum _ {i=1}^n \sigma _ i f(\hat{A},X) _ i \Big],$

where $\hat{A} = \arg\inf _ {\tilde{A}:\Vert A - \tilde{A}\Vert _ \infty \leq \epsilon} y_i f(\tilde{A},X)_i$. If perturbing the graph topology at the last layer, then

$Q \mathbb{E} _ {\sigma} \Big[\sup_{f\in \mathcal{F}} \sum_{i=1}^n \sigma_i f(\hat{A},X)_i \Big]$

$= Q \mathbb{E} _ {\sigma}\sup _ {\Vert W^{(L)}\Vert _ 2\leq \omega} \bigg[\sum _ {i=1}^n \sigma_i \Big(\sum _ {j\in[n]} g(\hat{A}) _ {i,j} f^{(L-1)}(A,X) _ {j*} W^{(L)}\Big)\bigg]$

$\leq Q\frac{1}{\lambda} \log \Bigg( 2 \Vert g(\hat{A})\Vert_\infty \omega \mathbb{E} _ {\sigma}\sup _ { j\in[n]} \exp \lambda \bigg\Vert\sum _ {i=1}^n \sigma _ i f^{(L-1)}(A,X) _ {j*} \bigg\Vert \Bigg)$

$\cdots$

$\leq Q\frac{1}{\lambda} \log \Bigg(2^L \Vert g(\hat{A})\Vert_\infty \Vert g(A)\Vert^{L-1}_\infty \omega^L \mathbb{E} _ {\sigma} \sup _ {j\in[n]} \exp \bigg(\lambda \Big\Vert\sum _ {i=1}^n \sigma _ i x _ {j}\Big\Vert _ {p*} \bigg)\Bigg)$

Subsequent proof is similar to Eq (9) in Page 17. Notably, the upper bound of $\Vert g(\hat{A})\Vert^L_\infty$ for specific adversarial graph filters needs to be proved. In addition, it remains to analyze the effect of perturbing the graph topology at the first layer, any intermediate layers, and all layers on generalization.

A3. Comparison with non-adversarial bounds. Following the reviewer's suggestion, we have provided a detailed comparison in Remark 4.4 (Page 5 of the revised paper). "Taking $\varepsilon=0$ and applying Lemma 4.5 yield the upper bound of the generalization gap in the non-adversarial setting:

$\mathcal{O}\Big(\max \big( \frac{1}{\sqrt{m}},\frac{1}{\sqrt{n-m}} \big) \times \big(\sqrt{2\log(2)L}+1 \big) \Vert g(A)\Vert^L_\infty \omega^L B_{p^*}\Vert X\Vert_{2,p^*} \Big),$

which has a comparable convergence rate of $\mathcal{O}(\max(\frac{1}{\sqrt{m}},\frac{1}{\sqrt{n-m}}))$ to the existing TRC-based bound [1-3]. Notably, our bound improves the existing exponential dependency of the number of layers to a logarithmic term $\mathcal{O}(\sqrt{2\log(2)L})$, facilitating the tighter bound than [1, 2], which benefit from the usage of the contraction technique. "

Reference:

1. Esser et al. Learning theory can (sometimes) explain generalisation in graph neural networks. NIPS. 2021.

2. Tang and Liu. Towards understanding generalization of graph neural networks. ICML. 2023.

3. Deng et al. Graph convolution network based recommender systems: Learning guarantee and item mixture powered strategy. NIPS. 2022.