pith. sign in

arxiv: 2606.06293 · v1 · pith:LH6KYWA6new · submitted 2026-06-04 · 💻 cs.LG · stat.ML

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

Ziling Liang , Xinping Yi , Qingsong Wen , Shi Jin This is my paper

Pith reviewed 2026-06-28 02:55 UTC · model grok-4.3

classification 💻 cs.LG stat.ML
keywords PAC-Bayesian boundsadversarial robustnessmessage passing graph neural networksgeneralization analysissensitivity analysisanisotropic posteriorsJacobian rank
0
0 comments X

The pith

A sensitivity-aware PAC-Bayesian analysis yields tighter robust generalization bounds for message passing graph neural networks by aligning posteriors to low-rank Jacobians.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends a sensitivity-aware PAC-Bayesian framework to message passing GNNs in the adversarial setting. It quantifies parameter-block sensitivities through output Jacobians with respect to weights, then exploits the fact that these Jacobians have rank at most K for K-class tasks. This construction permits Jacobian-aligned sensitivity matrices and anisotropic Gaussian posteriors whose covariances are optimized to tighten the KL term. The resulting bound replaces hidden-width factors with the number of classes K and refines the spectral-norm dependence on learned weights.

Core claim

By deriving output Jacobians with respect to weight parameters and constructing Jacobian-aligned sensitivity matrices from the fact that these Jacobians have rank at most K, the analysis obtains anisotropic Gaussian posteriors that upper-bound the KL divergence tightly; the resulting robust generalization bound for MPGNNs therefore carries a leading dimension factor of K rather than hidden width and a refined spectral-norm dependence on the learned weights.

What carries the argument

Jacobian-aligned sensitivity matrices built from the rank-at-most-K output Jacobians of network outputs with respect to weight parameters, used to define optimized anisotropic Gaussian posteriors.

If this is right

  • The bound guides architectural choices that reduce the spectral norms of learned weights or that concentrate sensitivity in fewer parameter blocks.
  • Anisotropic posteriors allow the analysis to penalize perturbations more heavily in sensitive parameter blocks while relaxing them in less sensitive ones.
  • The reduction of the dimension factor from hidden width to K makes the bound scale better with network depth and width in practice.
  • The same Jacobian construction can be reused to derive bounds for other message-passing variants that preserve the low-rank output structure.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the low-rank Jacobian property holds for regression or multi-label tasks with output dimension d, the same construction would replace K by d in the bound.
  • Training procedures that explicitly minimize the spectral norms appearing in the bound could be derived as a direct corollary and tested against standard adversarial training.
  • The framework suggests that graph-level pooling operators that further reduce effective output rank could produce still tighter guarantees.

Load-bearing premise

The Jacobian matrices of network outputs with respect to weight parameters have rank at most K in K-class graph classification tasks.

What would settle it

A direct computation on a trained MPGNN for a K-class graph dataset showing that the Jacobian of outputs with respect to any weight block has rank strictly larger than K.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper extends a sensitivity-aware PAC-Bayesian framework from DNNs to message-passing GNNs (MPGNNs) in the adversarial setting. It computes output Jacobians w.r.t. weight blocks, exploits their rank-at-most-K property for K-class graph classification to construct Jacobian-aligned sensitivity matrices, and employs anisotropic Gaussian posteriors with optimized covariances to obtain a tighter KL upper bound. The resulting robust generalization bound refines the spectral-norm dependence on learned weights and replaces hidden-width-dependent leading factors with a factor of K.

Significance. If the derivation holds, the work supplies meaningfully tighter data-dependent robust generalization guarantees for MPGNNs than prior isotropic analyses. The explicit Jacobian construction, rank reduction, and anisotropic posterior optimization constitute a clean, non-circular extension of the underlying framework and supply concrete design guidance for improving adversarial robustness of graph models.

minor comments (3)
  1. §3.2: the precise definition of the Jacobian-aligned sensitivity matrix S_l should be stated explicitly (including how the rank-K projection is applied to each weight block) rather than left as a reference to the DNN case.
  2. Eq. (12): the optimized covariance construction for the anisotropic posterior is described at a high level; an explicit closed-form expression or optimization procedure for the per-block variances would improve reproducibility.
  3. Table 1 and §5: the numerical comparison of the new bound against the isotropic baseline should report the exact values of the leading dimension factor (K vs. hidden width) used in each bound to make the claimed tightening transparent.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation of minor revision. The report contains no specific major comments requiring point-by-point rebuttal.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation extends a prior sensitivity-aware PAC-Bayesian framework to MPGNNs via explicit Jacobian derivations with respect to weight blocks, then applies the standard fact that output dimension K implies Jacobian rank at most K to build aligned sensitivity matrices and anisotropic posteriors. This rank reduction is a direct dimensional consequence of K-class outputs rather than a fitted or self-defined quantity. Spectral-norm refinements and replacement of hidden-width factors by K are presented as analytical consequences of the MPGNN structure and the Jacobian construction, without reduction of the final bound to any internally fitted constant or self-citation chain. The central tighter-bound claim therefore rests on independent structural handling of message-passing layers and remains self-contained.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The analysis rests on the rank property of Jacobians and the extension of an existing PAC-Bayesian framework; the optimized covariances constitute a free parameter whose selection is not independently justified in the abstract.

free parameters (1)
  • optimized covariances of the anisotropic Gaussian posteriors
    Chosen to tightly upper-bound the KL divergence term after constructing Jacobian-aligned sensitivity matrices.
axioms (1)
  • domain assumption Output Jacobian matrices have rank at most K for K-class graph classification
    Invoked explicitly to enable construction of Jacobian-aligned sensitivity matrices from the derived output Jacobians.

pith-pipeline@v0.9.1-grok · 5810 in / 1336 out tokens · 40544 ms · 2026-06-28T02:55:49.391437+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

42 extracted references · 5 canonical work pages · 2 internal anchors

  1. [1]

    The graph neural network model,

    F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The graph neural network model,”IEEE Transactions on Neural Networks, vol. 20, no. 1, pp. 61–80, 2009

    2009

  2. [2]

    Relational inductive biases, deep learning, and graph networks

    P. W. Battaglia, J. B. Hamrick, V . Bapst, A. Sanchez-Gonzalez, V . Zam- baldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner et al., “Relational inductive biases, deep learning, and graph networks,” arXiv preprint arXiv:1806.01261, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  3. [3]

    Semi-supervised classification with graph convolutional networks,

    T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” inInternational Conference on Learning Representations, 2017

    2017

  4. [4]

    Inductive representation learning on large graphs,

    W. L. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” inAdvances in Neural Information Processing Systems, vol. 30, 2017, pp. 1024–1034

    2017

  5. [5]

    Modeling polypharmacy side effects with graph convolutional networks,

    M. Zitnik, M. Agrawal, and J. Leskovec, “Modeling polypharmacy side effects with graph convolutional networks,”Bioinformatics, vol. 34, no. 13, pp. i457–i466, 2018

    2018

  6. [6]

    Graph convolutional neural networks for web-scale recommender systems,

    R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec, “Graph convolutional neural networks for web-scale recommender systems,” inProceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2018, pp. 974–983

    2018

  7. [7]

    Graph neural networks for scalable radio resource management: Architecture design and theoretical analysis,

    Y . Shen, Y . Shi, J. Zhang, and K. B. Letaief, “Graph neural networks for scalable radio resource management: Architecture design and theoretical analysis,”IEEE Journal on Selected Areas in Communications, vol. 39, no. 1, pp. 101–115, 2021

    2021

  8. [8]

    Intriguing properties of neural networks,

    C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. J. Goodfellow, and R. Fergus, “Intriguing properties of neural networks,” inInternational Conference on Learning Representations, 2014

    2014

  9. [9]

    Explaining and harnessing adversarial examples,

    I. J. Goodfellow, J. Shlens, and C. Szegedy, “Explaining and harnessing adversarial examples,” inInternational Conference on Learning Repre- sentations, 2015

    2015

  10. [10]

    Adversarial attacks on neural networks for graph data,

    D. Z ¨ugner, A. Akbarnejad, and S. G ¨unnemann, “Adversarial attacks on neural networks for graph data,” inProceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2018, pp. 2847–2856

    2018

  11. [11]

    Adversarial attacks on graph neural networks via meta learning,

    D. Z ¨ugner and S. G ¨unnemann, “Adversarial attacks on graph neural networks via meta learning,” inInternational Conference on Learning Representations, 2019

    2019

  12. [12]

    Adversarial examples on graph data: Deep insights into attack and defense,

    H. Wu, C. Wang, Y . Tyshetskiy, A. Docherty, K. Lu, and L. Zhu, “Adversarial examples on graph data: Deep insights into attack and defense,” inProceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019, pp. 4816–4823

    2019

  13. [13]

    Adversarial attacks on graph classification via Bayesian optimisation,

    X. Wan, H. Kenlay, B. Ru, A. Blaas, M. A. Osborne, and X. Dong, “Adversarial attacks on graph classification via Bayesian optimisation,” inAdvances in Neural Information Processing Systems, vol. 34, 2021, pp. 6983–6996

    2021

  14. [14]

    Revisiting adversarial attacks on graph neural networks for graph classification,

    X. Wang, H. Chang, B. Xie, T. Bian, S. Zhou, D. Wang, Z. Zhang, and W. Zhu, “Revisiting adversarial attacks on graph neural networks for graph classification,”IEEE Transactions on Knowledge and Data Engineering, vol. 36, no. 5, pp. 2166–2178, 2024

    2024

  15. [15]

    GNNGuard: Defending graph neural net- works against adversarial attacks,

    X. Zhang and M. Zitnik, “GNNGuard: Defending graph neural net- works against adversarial attacks,” inAdvances in Neural Information Processing Systems, 2020

    2020

  16. [16]

    All you need is low (rank): Defending against adversarial attacks on graphs,

    N. Entezari, S. A. Al-Sayouri, A. Darvishzadeh, and E. E. Papalexakis, “All you need is low (rank): Defending against adversarial attacks on graphs,” inProceedings of the Thirteenth ACM International Conference on Web Search and Data Mining, 2020, pp. 169–177

    2020

  17. [17]

    A causality-aligned structure rationalization scheme against adversarial biased perturbations for graph neural networks,

    J. Jia, S. Ma, Y . Liu, L. Wang, and R. H. Deng, “A causality-aligned structure rationalization scheme against adversarial biased perturbations for graph neural networks,”IEEE Transactions on Information Forensics and Security, vol. 19, pp. 59–73, 2024

    2024

  18. [18]

    Adversarial training for graph neural networks via graph subspace energy optimization,

    G. Liu, Z. Liang, X. Huang, X. Yi, and S. Jin, “Adversarial training for graph neural networks via graph subspace energy optimization,”IEEE Transactions on Information Forensics and Security, vol. 21, pp. 2284– 2299, 2026

    2026

  19. [19]

    The Vapnik-Chervonenkis dimension of graph and recursive neural networks,

    F. Scarselli, A. C. Tsoi, and M. Hagenbuchner, “The Vapnik-Chervonenkis dimension of graph and recursive neural networks,”Neural Networks, vol. 108, pp. 248–259, 2018

    2018

  20. [20]

    Learning theory can (sometimes) explain generalisation in graph neural networks,

    P. Esser, L. Chennuru Vankadara, and D. Ghoshdastidar, “Learning theory can (sometimes) explain generalisation in graph neural networks,” in Advances in Neural Information Processing Systems, vol. 34, 2021, pp. 27 043–27 056

    2021

  21. [21]

    Generalization and represen- tational limits of graph neural networks,

    V . K. Garg, S. Jegelka, and T. Jaakkola, “Generalization and represen- tational limits of graph neural networks,” inProceedings of the 37th International Conference on Machine Learning, 2020, pp. 3419–3430. 13

    2020

  22. [22]

    Generalization bounds for graph convolutional neural networks via rademacher complexity,

    S. Lv, “Generalization bounds for graph convolutional neural networks via rademacher complexity,”arXiv preprint arXiv:2102.10234, 2021

    work page arXiv 2021

  23. [23]

    Stability and generalization of graph convolutional neural networks,

    S. Verma and Z.-L. Zhang, “Stability and generalization of graph convolutional neural networks,” inProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019, pp. 1539–1548

    2019

  24. [24]

    The generalization error of graph convolutional networks may enlarge with more layers,

    X. Zhou and H. Wang, “The generalization error of graph convolutional networks may enlarge with more layers,”Neurocomputing, vol. 424, pp. 97–106, 2021

    2021

  25. [25]

    Graph neural tangent kernel: Fusing graph neural networks with graph kernels,

    S. S. Du, K. Hou, R. Salakhutdinov, B. P ´oczos, R. Wang, and K. Xu, “Graph neural tangent kernel: Fusing graph neural networks with graph kernels,” inAdvances in Neural Information Processing Systems, 2019

    2019

  26. [26]

    Simplified PAC-Bayesian margin bounds,

    D. A. McAllester, “Simplified PAC-Bayesian margin bounds,” inLearning Theory and Kernel Machines. Springer, 2003, pp. 203–215

    2003

  27. [27]

    PAC-Bayes & margins,

    J. Langford and J. Shawe-Taylor, “PAC-Bayes & margins,” inAdvances in Neural Information Processing Systems, 2003, pp. 439–446

    2003

  28. [28]

    Catoni,PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning

    O. Catoni,PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning. Institute of Mathematical Statistics, 2007

    2007

  29. [29]

    PAC-Bayes bounds with data dependent priors,

    E. Parrado-Hern ´andez, A. Ambroladze, J. Shawe-Taylor, and S. Sun, “PAC-Bayes bounds with data dependent priors,”Journal of Machine Learning Research, vol. 13, no. 1, pp. 3507–3531, 2012

    2012

  30. [30]

    Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data,

    G. K. Dziugaite and D. M. Roy, “Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data,” inProceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, 2017

    2017

  31. [31]

    Spectrally-normalized margin bounds for neural networks,

    P. L. Bartlett, D. J. Foster, and M. J. Telgarsky, “Spectrally-normalized margin bounds for neural networks,” inAdvances in Neural Information Processing Systems, 2017

    2017

  32. [32]

    A PAC-Bayesian approach to spectrally-normalized margin bounds for neural networks,

    B. Neyshabur, S. Bhojanapalli, and N. Srebro, “A PAC-Bayesian approach to spectrally-normalized margin bounds for neural networks,” inInternational Conference on Learning Representations, 2018

    2018

  33. [33]

    A PAC-Bayesian approach to generalization bounds for graph neural networks,

    R. Liao, R. Urtasun, and R. S. Zemel, “A PAC-Bayesian approach to generalization bounds for graph neural networks,” inInternational Conference on Learning Representations, 2021

    2021

  34. [34]

    Generalization in graph neural networks: Improved PAC-Bayesian bounds on graph diffusion,

    H. Ju, D. Li, A. Sharma, and H. R. Zhang, “Generalization in graph neural networks: Improved PAC-Bayesian bounds on graph diffusion,” in International Conference on Artificial Intelligence and Statistics, 2023, pp. 6314–6341

    2023

  35. [35]

    Topology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networks

    X. Yi, “Topology-aware PAC-Bayesian generalization analysis for graph neural networks,”arXiv preprint arXiv:2604.10553, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  36. [36]

    A PAC-Bayes analysis of adversarial robustness,

    P. Viallard, E. G. Vidot, A. Habrard, and E. Morvant, “A PAC-Bayes analysis of adversarial robustness,” inAdvances in Neural Information Processing Systems, 2021

    2021

  37. [37]

    PAC-Bayesian spectrally-normalized bounds for adversarially robust generalization,

    J. Xiao, R. Sun, and Z.-Q. Luo, “PAC-Bayesian spectrally-normalized bounds for adversarially robust generalization,” inAdvances in Neural Information Processing Systems, 2023

    2023

  38. [38]

    PAC-Bayesian adversarially robust generalization bounds for graph neural network,

    T. Sun and J. Lin, “PAC-Bayesian adversarially robust generalization bounds for graph neural network,”arXiv preprint arXiv:2402.04038, 2024

    work page arXiv 2024

  39. [39]

    Towards a unified PAC-Bayesian framework for norm-based generalization bounds,

    X. Yi, G. Jin, X. Huang, and S. Jin, “Towards a unified PAC-Bayesian framework for norm-based generalization bounds,”arXiv preprint arXiv:2601.08100, 2026

    work page arXiv 2026

  40. [40]

    Discriminative embeddings of latent variable models for structured data,

    H. Dai, B. Dai, and L. Song, “Discriminative embeddings of latent variable models for structured data,” inInternational Conference on Machine Learning, 2016, pp. 2702–2711

    2016

  41. [41]

    Pardo,Statistical Inference Based on Divergence Measures

    L. Pardo,Statistical Inference Based on Divergence Measures. Chapman and Hall/CRC, 2018

    2018

  42. [42]

    Hanson-Wright inequality and sub- gaussian concentration,

    M. Rudelson and R. Vershynin, “Hanson-Wright inequality and sub- gaussian concentration,”Electronic Communications in Probability, vol. 18, pp. 1–9, 2013

    2013