PAC-Bayesian Adversarially Robust Generalization for Message Passing Graph Neural Networks: A Sensitivity Analysis

• URL: http://arxiv.org/abs/2606.06293v1
• Date: Thu, 04 Jun 2026 15:31:21 GMT
• Title: PAC-Bayesian Adversarially Robust Generalization for Message Passing Graph Neural Networks: A Sensitivity Analysis
• Abstract summary: We extend PAC-Bayesian framework from deep neural networks to message passing GNNs.<n>We derive a tighter robust generalization bound in the adversarial setting.
• Score: 80.64607823130437
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Whilst the vulnerability of graph neural networks (GNNs) to adversarial attacks poses a critical threat to graph representation learning, the understanding of the robust generalization behavior remains a fundamental challenge in the adversarial setting. Recently, PAC-Bayesian margin-based generalization analysis substantially advances this line of research by providing a flexible and data-dependent analytical framework. However, existing robust analyses often rely on isotropic Gaussian posteriors and control weight perturbations in the full parameter space, which limits the ability to capture heterogeneous parameter sensitivity yet hinges on hidden-width-dependent complexity terms, resulting in not-tight-enough generalization bounds. In this paper, we extend a recently proposed sensitivity-aware PAC-Bayesian framework from deep neural networks to message passing GNNs (MPGNNs) and derive a tighter robust generalization bound in the adversarial setting. Specifically, we first quantify how sensitive the perturbations across different parameter blocks are to the network outputs by deriving the output Jacobians with respect to the weight parameters. Exploiting the fact that these Jacobian matrices have rank at most $K$ in $K$-class graph classification, we then construct Jacobian-aligned sensitivity matrices and use anisotropic Gaussian posteriors with optimized covariances to upper bound the KL divergence in a tight way. Notably, by refining the spectral-norm dependence on the learned weights and reducing the leading dimension factor from hidden-width-dependent terms to the number of classes $K$, our analysis yields much tighter robust generalization guarantees for MPGNNs, thereby guiding their designs to enhance adversarial robustness.

Related papers

• Topology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networks [21.139538521229273]
  We propose a topology-aware PAC-Bayesian norm-based generalization framework for graph convolutional networks (GCNs)<n>By imposing different structures on sensitivity matrices from both spatial and spectral perspectives, we derive a family of generalization error bounds with graph structures embedded.<n> Notably, the proposed framework explicitly integrates graph structural properties into the generalization analysis, enabling a unified inspection of GNN generalization behavior.
  arXiv  Detail & Related papers  (2026-04-12T09:52:27Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Towards A Unified PAC-Bayesian Framework for Norm-based Generalization Bounds [63.47271262149291]
  We propose a unified framework for PAC-Bayesian norm-based generalization.<n>The key to our approach is a sensitivity matrix that quantifies the network outputs with respect to structured weight perturbations.<n>We derive a family of generalization bounds that recover several existing PAC-Bayesian results as special cases.
  arXiv  Detail & Related papers  (2026-01-13T00:42:22Z)
• Sheaf Graph Neural Networks via PAC-Bayes Spectral Optimization [13.021238902084647]
  Over-smoothing in Graph Neural Networks (GNNs) causes collapse in distinct node features.<n>We introduce SGPC (Sheaf GNNs with PAC-Bayes), a unified architecture that combines cellular-sheaf message passing with several mechanisms.<n> Experiments on nine homophilic and heterophilic benchmarks show that SGPC outperforms state-of-the-art spectral and sheaf-based GNNs.
  arXiv  Detail & Related papers  (2025-08-01T06:39:28Z)
• PAC-Bayesian Adversarially Robust Generalization Bounds for Graph Neural Network [5.340644246815989]
  Graph neural networks (GNNs) are vulnerable to adversarial attacks. In this paper, we provide adversarially robust generalization bounds for two kinds of popular GNNs.
  arXiv  Detail & Related papers  (2024-02-06T14:34:17Z)
• Neural Characteristic Activation Analysis and Geometric Parameterization for ReLU Networks [2.2713084727838115]
  We introduce a novel approach for analyzing the training dynamics of ReLU networks by examining the characteristic activation boundaries of individual neurons. Our proposed analysis reveals a critical instability in common neural network parameterizations and normalizations during convergence optimization, which impedes fast convergence and hurts performance.
  arXiv  Detail & Related papers  (2023-05-25T10:19:13Z)
• Out-of-distributional risk bounds for neural operators with applications to the Helmholtz equation [6.296104145657063]
  Existing neural operators (NOs) do not necessarily perform well for all physics problems. We propose a subfamily of NOs enabling an enhanced empirical approximation of the nonlinear operator mapping wave speed to solution. Our experiments reveal certain surprises in the generalization and the relevance of introducing depth. We conclude by proposing a hypernetwork version of the subfamily of NOs as a surrogate model for the mentioned forward operator.
  arXiv  Detail & Related papers  (2023-01-27T03:02:12Z)
• Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks [59.142826407441106]
  We study the generalization behavior of shallow neural networks (SNNs) by leveraging the concept of algorithmic stability. We consider gradient descent (GD) and gradient descent (SGD) to train SNNs, for both of which we develop consistent excess bounds.
  arXiv  Detail & Related papers  (2022-09-19T18:48:00Z)
• Generalization Error Bounds for Deep Neural Networks Trained by SGD [3.148524502470734]
  Generalization error bounds for deep trained by gradient descent (SGD) are derived. The bounds explicitly depend on the loss along the training trajectory. Results show that our bounds are non-vacuous and robust with the change of neural networks and network hypers.
  arXiv  Detail & Related papers  (2022-06-07T13:46:10Z)
• A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks [99.46182575751271]
  We derive generalization bounds for the two primary classes of graph neural networks (GNNs) Our result reveals that the maximum node degree and spectral norm of the weights govern the generalization bounds of both models.
  arXiv  Detail & Related papers  (2020-12-14T16:41:23Z)
• Understanding Generalization in Deep Learning via Tensor Methods [53.808840694241]
  We advance the understanding of the relations between the network's architecture and its generalizability from the compression perspective. We propose a series of intuitive, data-dependent and easily-measurable properties that tightly characterize the compressibility and generalizability of neural networks.
  arXiv  Detail & Related papers  (2020-01-14T22:26:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.