Adversarial Robust Generalization of Graph Neural Networks

While Graph Neural Networks (GNNs) have shown outstanding performance in node classification tasks, they are vulnerable to adversarial attacks, which are imperceptible changes to input samples. Adversarial training, as a widely used tool to enhance the adversarial robustness of GNNs, has presented remarkable effectiveness in node classification tasks. However, the generalization properties for explaining their behaviors remain not well understood from the theoretical viewpoint. To fill this gap, we develop a high probability generalization bound of general GNNs in adversarial learning through covering number analysis. We estimate the covering number of the GNN model class based on the entire perturbed feature matrix by constructing a cover for the perturbation set. Our results are generally applicable to a series of GNNs. We demonstrate their applicability by investigating the generalization performance of several popular GNN models under adversarial attacks, which reveal the architecturerelated factors influencing the generalization gap. Our experimental results on benchmark datasets provide evidence that supports the established theoretical findings. Adversarial Robust Generalization of Graph Neural Networks Table 1. Summary of generalization analysis of GNNs (m-number of training data, u-number of test data). Reference Under Attack Learning Mode Analysis Tool Convergence Rate Verma and Zhang (2019) No Inductive Uniform stability O(1/ √ m) Zhou and Wang (2021) No Inductive Uniform stability O(1/ √ m) Garg et al. (2020) No Inductive Rademacher complexity O(1/ √ m) Oono and Suzuki (2020) No Transductive Rademacher complexity O(max1/ √ m, 1/ √ u) Esser et al. (2021) No Transductive Rademacher complexity O(max1/ √ m, 1/ √ u) Tand and Liu (2023) No Transductive Rademacher complexity O((1/m + 1/u) √ m + u) Sun et al. (2024) No Transductive PAC-Bayes O(1/ √ m) Ours Yes Transductive Covering number O(max1/ √ m, 1/ √ u) covering number. Our analysis exhibits broad applicability across a wide range of GNNs and losses. Our findings provide theoretical support for the empirical success of adversarial training and offer valuable insights for training robust GNNs that generalize well. The key contributions are as follows.