mlsanityData to 7 Oct 2026

PAC-Bayesian Adversarially Robust Generalization Bounds for Graph Neural Network

arXiv 2402.04038 ↗First posted 6 Feb 2024stat.ML cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) have gained popularity for various graph-related tasks. However, similar to deep neural networks, GNNs are also vulnerable to adversarial attacks. Empirical studies have shown that adversarially robust generalization has a pivotal role in establishing effective defense algorithms against adversarial attacks. In this paper, we contribute by providing adversarially robust generalization bounds for two kinds of popular GNNs, graph convolutional network (GCN) and message passing graph neural network, using the PAC-Bayesian framework. Our result reveals that spectral norm of the diffusion matrix on the graph and spectral norm of the weights as well as the perturbation factor govern the robust generalization bounds of both models. Our bounds are nontrivial generalizations of the results developed in (Liao et al., 2020) from the standard setting to adversarial setting while avoiding exponential dependence of the maximum node degree. As corollaries, we derive better PAC-Bayesian robust generalization bounds for GCN in the standard setting, which improve the bounds in (Liao et al., 2020) by avoiding exponential dependence on the maximum node degree.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 28 of its 45 references that are in the map. First posted on arXiv 6 Feb 2024.

Builds on

28 of 45 references.

References · 28

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2013Intriguing properties of neural networkscited by 5,114
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  5. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 786
  6. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  7. 2018Junction Tree Variational Autoencoder for Molecular Graph Generationcited by 647
  8. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 395
  9. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  10. 2018Certified Defenses against Adversarial Examplescited by 305
  11. 2018Adversarial Attack on Graph Structured Datacited by 300
  12. 2015Norm-Based Capacity Control in Neural Networkscited by 299
16 more
  1. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  2. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  3. 2020GNNGuard: Defending Graph Neural Networks against Adversarial Attackscited by 195
  4. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  5. 2018Rademacher Complexity for Adversarially Robust Generalizationcited by 132
  6. 2016Discriminative Embeddings of Latent Variable Models for Structured Datacited by 130
  7. 2018Adversarial Attacks on Node Embeddings via Graph Poisoningcited by 109
  8. 2018Learning Multimodal Graph-to-Graph Translation for Molecular Optimizationcited by 87
  9. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
  10. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  11. 2018Generalizable Adversarial Training via Spectral Normalizationcited by 68
  12. 2019Transferring Robustness for Graph Neural Network Against Poisoning Attackscited by 58
  13. 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
  14. 2020Adversarial Learning Guarantees for Linear Hypotheses and Neural Networkscited by 47
  15. 2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 39
  16. 2022Adversarial Rademacher Complexity of Deep Neural Networkscited by 18

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 2.

4 papers.

  1. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  2. 2026Topology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networkscited by 1
  3. 2025Adversarial generalization of unfolding (model-based) networkscited by 0
  4. 2026PAC-Bayesian Adversarially Robust Generalization for Message Passing Graph Neural Networks: A Sensitivity Analysiscited by 0