1
PAC-Bayesian Adversarially Robust Generalization for Message Passing Graph Neural Networks: A Sensitivity Analysis
arXiv:2606.06293v1 [cs.LG] 4 Jun 2026
Ziling Liang, Xinping Yi, Member, IEEE, Qingsong Wen, Senior Member, IEEE, and Shi Jin, Fellow, IEEE
mislead the well-trained models to make wrong classification in the inference phase, the graph learning tasks using GNNs can also suffer significantly from adversarial perturbations on node features or graph structures [10]–[14]. The consequence of adversarial perturbations is even more severe for GNNs, as local perturbations can be propagated and amplified through message passing, thereby affecting graph-level predictions. It, therefore, provides a stringent test of whether learned representations are stable to both attribute-level and topology-level variations. As such, there is a growing line of work in the literature to investigate adversarial attacks and defenses (e.g., adversarial training) for GNNs [15]–[18] to probe and defend against the potential adversarial vulnerability. However, these algorithmic and/or empirical studies do not convincingly explain whether the adversarial robustness observed on training graphs can generalize to unseen graph samples. Such a gap makes it essential to analyze adversarially robust generalization for understanding the reliability of GNNs. From a statistical learning perspective, the weight sharing and topology-dependent message passing pose fundamental challenges for classical generalization analyses. To address these challenges, several theoretical frameworks have been explored for GNNs. The VC-dimension analyses provide capacity measures for GNNs, but the resulting bounds often scale unfavorably with model and graph size [19], [20]. More refined data-dependent analyses use Rademacher complexity to study I. I NTRODUCTION Graph neural networks (GNNs) have achieved remarkable message passing GNNs (MPGNNs) and graph convolutional performance in a wide range of graph-related tasks, emerging networks (GCNs), relating the bounds to local computation as a powerful learning paradigm for relational and structured trees, aggregation neighborhoods, and graph-dependent quandata [1]–[3]. They have been successfully applied to social tities [20]–[22]. The algorithmic stability analyses provide networks [4], biological modeling [5], recommendation sys- another perspective by connecting generalization to the stability tems [6], and wireless networks [7], to name just a few. The of the training algorithm and the spectral behavior of graph key mechanism of GNNs is to propagate information over filters [23], [24]. The neural tangent kernel (NTK) methods the graph through local computations shared across nodes and further characterize the infinite-width regime of GNNs trained edges, which enables the learned representations to capture by gradient descent through graph NTKs [25]. These studies indicate that generalization performance for GNNs is shaped both feature information and graph-structural dependencies. Despite their empirical success, the reliability of GNNs under by graph statistics, aggregation dynamics, feature propagation, adversarial perturbations remains a critical concern. Similar and the norm complexity of the learned weights. Nevertheless, to the vulnerability of convolutional neural networks (CNNs) most existing bounds are developed for standard non-adversarial to adversarial examples in image classification tasks [8], [9], settings and analyze these factors separately. Among existing approaches, PAC-Bayesian provides a flexiwhere certain imperceptible perturbations of input images can ble and data-dependent framework for deriving high-probability Z. Liang, X. Yi, and S. Jin are with the School of Information Science and generalization bounds [26]–[30]. In deep learning, norm-based Engineering, Southeast University, Nanjing 210096, China. E-mail: {zlliang, and margin-based analyses connect generalization to the stabilxyi, jinshi}@seu.edu.cn. Q. Wen is with Squirrel Ai Learning, Bellevue, WA, 98004 USA. Email: ity of predictions under random weight perturbations, leading [email protected]. to bounds governed by norm-based complexity measures of the 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-widthdependent 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.
2
learned weights [31], [32]. The norm-based viewpoint has also the output dimension, which allows us to design low-rank been extended to graph-structured models. In particular, PACsensitivity matrices. Together with anisotropic Gaussian Bayesian bounds for GCNs and MPGNNs show that graphposteriors, these matrices focus the perturbation analysis dependent quantities and spectral norms of the learned weights on the parameter directions that affect the output margin. play a central role in controlling GNN generalization [33]. • Refined spectral and dimensional dependencies. We For GCNs, these bounds can be viewed as graph extensions tighten the robust PAC-Bayesian bound for MPGNNs of spectrally normalized margin bounds for feedforward and in both spectral and dimensional dependence, i.e., the convolutional networks, while for MPGNNs they require a spectral scale of the learned weights is tightened, and the separate treatment because the input-injection and messageleading dimension factor is reduced from a hidden-widthpassing terms make the architecture non-homogeneous in the dependent term to the number of classes, and show that layer weights. Subsequent PAC-Bayesian analyses further refine the obtained bound also recovers GCNs as special cases. this line of work by measuring graph dependence through the The rest of this paper is organized as follows. Section II spectral norm of the graph diffusion operator, rather than solely introduces the problem setting and necessary preliminaries. through node degrees [34], [35]. In adversarial settings, PAC- Section III develops the main robust PAC-Bayesian analysis Bayesian analysis has been extended from standard margin for MPGNNs and its GCN specialization. Section IV concludes losses to robust margin losses [36], [37]. This viewpoint is the paper. Detailed proofs are provided in the Appendix. particularly useful because the worst-case adversarial example depend on the model weights, making direct output comparison II. P RELIMINARIES under weight perturbations difficult. For GNNs, robust PACNotation. We collect the notation used throughout the paper. Bayesian bounds evaluate margins over adversarially perturbed For a positive integer k, let [k] ≜ {1, . . . , k}. Scalars, vectors, graph samples and show that the resulting robust bounds matrices, and sets are denoted by a, a, A, and A, respectively. are governed by the norms of the learned weights and the The i-th entry of a, the i-th row of A, and the (i, j)-th adversarial perturbation budget [38]. entry of A are denoted by ai , Ai,: , and Aij , respectively. Despite the growing body of PAC-Bayesian generalization We use 1n , 0, and In for the all-one vector, zero vector or bounds for GNNs, existing analyses still exhibit several strucmatrix, and identity matrix, with dimensions clear from the tural limitations. First, most prior framework adopt isotropic context. The vectorization operator is denoted by vec(·), diag(·) Gaussian posteriors for analytical tractability, implicitly asdenotes a diagonal matrix, and 1{·} denotes the indicator suming homogeneous uncertainty across all parameters; and function. For a vector a, ∥a∥2 and ∥a∥∞ denote the Euclidean the perturbation bound is governed by matrix concentration and maximum norms. For a matrix A, ∥A∥2 , ∥A∥F , and inequalities which are loose for deep or wide architectures. ∥A∥2,∞ ≜ maxi ∥Ai,: ∥2 denote the spectral norm, Frobenius Second, existing generalization analyses bound perturbations norm, and maximum row Euclidean norm, respectively. We in the full parameter space, without exploiting the low-rank write Tr(A), det(A), and log det(A) for the trace, determistructure of the output sensitivity in graph classification tasks, nant, and log-determinant of a square matrix. For symmetric leading the complexity term depend on the maximum hidden matrices, A ⪰ 0 means that A is positive semidefinite, and dimension rather than the effective output dimension. Third, A ⪰ B means A − B ⪰ 0. The Kronecker product is existing PAC-Bayesian bounds usually analyze GCNs and denoted by ⊗, and we use vec(AXB) = (B T ⊗ A)vec(X) MPGNNs through separate perturbation arguments. Although and ∥A ⊗ B∥2 = ∥A∥2 ∥B∥2 . Finally, N (µ, Σ) denotes a GCN-type models can be viewed as special cases of the Gaussian distribution with mean vector µ and covariance MPGNN formulation, the connection is not fully used to matrix Σ ⪰ 0, blkdiag(·) denotes a block-diagonal matrix, and obtain a unified bound. Moreover, due to the non-homogeneous DKL (Q∥P ) denotes the Kullback–Leibler divergence between structure of MPGNNs, existing analyses still use relatively the distributions Q and P . coarse spectral factors for the learned weights, leaving room to tighten both the spectral dependence and the dimensional A. Graph Neural Networks (GNNs) dependence of the bound. Motivated by the above limitations, we develop a novel We consider the K-class graph classification task for simple sensitivity-aware PAC-Bayesian analytical framework for ad- and undirected graphs. The input space Z consists of graph versarially robust generalization of MPGNNs, with the main samples z = (G, y) ∈ Z, where G = (X, AG ), X ∈ Rn×h0 contributions summarized as follows. denotes the node feature matrix over n nodes and satisfies n×n • Unified robust PAC-Bayesian framework for MPGNNs. ∥X∥2,∞ = maxi ∥Xi,: ∥2 ≤ B, AG ∈ {0, 1} is the We extend the recently proposed sensitivity-aware adjacency matrix, and y ∈ {1, . . . , K} denotes the output anisotropic PAC-Bayesian framework in [39] from deep label. We denote y = arg maxy fw (G)[y], where fw ∈ H : neural networks in the standard setting to graph-structured X × G → RK is a function specified by a parameterized models in the adversarial setting, and develop a unified learning model with model parameters w. The spaces Z, robust margin-based generalization analysis for MPGNNs X , G, and H denote the input sample space, node feature under adversarial perturbations. space, graph space, and hypothesis class space, respectively. A • Low-rank Jacobian-based perturbation analysis. We dataset S = {z1 , . . . , zm } with m training samples is drawn derive the blockwise output Jacobians of MPGNNs and independently and identically from an unknown distribution D show that they have a low-rank structure determined by is given to learn the model parameters w.
3
MPGNNs. Message passing GNNs cover a wide range of graph learning architectures based on iterative neighborhood aggregation and node-wise transformations [21], [40]. We study the following MPGNN formulation for graph classification, with each layer containing an input-injection block and a message-passing block, i.e., Hj = ϕj XUj + ρj PG ψj (Hj−1 )Wj , j ∈ [l − 1], Hl = fw (G) =
1 ⊤ 1 Hl−1 Wl , n n
H0 = 0,
(1)
B. Background of PAC-Bayes Analysis Margin loss. In K-class graph classification, margin-based losses quantify the confidence gap between the true class and its competitors and serve as the risk functions in the PACBayesian analysis. We first define the margin with respect to the true label y ∈ [K] as M (fw (G), y) = fw (G)y − max fw (G)b . b̸=y
(3)
For the adversarial perturbation analysis, it is also useful to compare the scores of two classes directly. Thus, for any a, b ∈ [K], we define the pairwise margin as
where X ∈ Rn×d denotes the node feature matrix, and Hj ∈ Rn×hj , j ∈ [l − 1], denotes the node representation at the j-th M (fw (G), a, b) = fw (G)a − fw (G)b . (4) hidden layer, the final readout is Hl = fw (G) ∈ R1×K . For d×hj each j ∈ [l − 1], Uj ∈ R is the input-injection weight The condition M (fw (G), y) > 0 indicates correct classification. matrix and Wj ∈ Rhj−1 ×hj is the message-passing weight For any margin level γ > 0, we define the population margin matrix, while Wl ∈ Rhl−1 ×K is the readout weight matrix. We loss and its empirical counterpart as also write h = maxj∈[l−1] hj for the maximum hidden width. n o LD,γ (fw ) = P(G,y)∼D M (fw (G), y) ≤ γ , The propagation operator in (1) is taken as the normalized o adjacency matrix with self-loops, (5) 1 X n L̂S,γ (fw ) = 1 M (fw (G), y) ≤ γ . 1 1 m − − (G,y)∈S PG = DG 2 (I + AG )DG 2 , (2) where DG = diag(1 + D1 , . . . , 1 + Dn ), and Di is the degree The standard generalization gap is LD,0 (fw ) − L̂S,γ (fw ). We now incorporate adversarial perturbations by replacing of node i in G. This normalization gives ∥PG ∥2 ≤ 1. For later each graph with its worst admissible perturbation. Let δw (G) use, we decompose the j-th hidden-layer update into the predenote the attack set associated with G and fw . Under ϵ-attack, activation term Ej = XUj + ρj (Fj ) and the message-passing ′ every G = (X ′ , A′G ) ∈ δw (G) satisfies ∥X ′ − X∥2,∞ ≤ ϵ, term Fj = PG ψj (Hj−1 )Wj , for j ∈ [l − 1]. ′ The trainable parameters are collected from the matrices while AG may be any adjacency matrix. As such, the robust margins are defined as l {Uj }l−1 j=1 and {Wj }j=1 . More precisely, let RM (fw (G), y) = ′ inf M (fw (G′ ), y) , T T T T T G ∈δw (G) w = wU1 , . . . , wUl−1 , wW1 , . . . , wWl , (6) RM (fw (G), a, b) = ′ inf M (fw (G′ ), a, b) . G ∈δw (G) where wUj = vec(Uj ) and wWj = vec(Wj ). The weight perturbation is written in the same form as Let G∗w ∈ arg minG′ ∈δw (G) M (fw (G′ ), y) denote an adversarial graph that attains the worst-case margin. Replacing the T u = uTU1 , . . . , uTUl−1 , uTW1 , . . . , uTWl , standard margin by the robust margin in (5) gives n o where uUj = vec(∆Uj ) and uWj = vec(∆Wj ). As such, the RD,γ (fw ) = P(G,y)∼D RM (fw (G), y) ≤ γ , perturbed model can therefore be parameterized by w + u. o (7) 1 X n R̂S,γ (fw ) = 1 RM (fw (G), y) ≤ γ . Throughout the analysis, we assume that the node features m are bounded as ∥X∥2,∞ ≤ B. For the layer weights, define (G,y)∈S M1 = max ∥Uj ∥2 , j∈[l−1]
M2 = max ∥Wj ∥2 . j∈[l]
Thus ∥Uj ∥2 ≤ M1 for j ∈ [l − 1] and ∥Wj ∥2 ≤ M2 for j ∈ [l]. We take M1 , M2 ≥ 1, which is consistent with the spectral scale of trained model parameters and will simplify the subsequent upper-bound comparisons. The mappings ϕj , ρj , and ψj are applied element-wise and are assumed to be L-Lipschitz, satisfying ϕj (0) = ρj (0) = ψj (0) = 0. The graph convolutional network (GCN) is obtained from (1) by setting Uj = 0 for all j, taking ρj and ψj as identity mappings, choosing ϕj as ReLU, and using H0 = X. Thus the l-layer GCN can be rewritten as Hj = ϕj (PG Hj−1 Wj ) , j ∈ [l − 1], 1 T Hl = fw (G) = 1n Hl−1 Wl . n
The robust generalization gap is RD,0 (fw ) − R̂S,γ (fw ). PAC-Bayesian generalization bound [32]. Let fw : X → RK be a deterministic classifier with parameters w, and let P be a prior distribution over the parameters independent of the training data. For any fixed w, let Q denote the distribution of the perturbed parameters w + u, where u is a random weight perturbation. If the perturbation condition is satisfied, i.e., γ 1 Pu max fw+u (x) − fw (x) ∞ < ≥ , (8) x∈X 4 2 then, for any γ, δ > 0, with probability at least 1 − δ over an i.i.d. training set S of size m drawn from D, we have the generalization bound for any w, i.e., s 2DKL (Q∥P ) + log 8m δ LD,0 (fw ) ≤ L̂S,γ (fw ) + . (9) 2(m − 1)
4
Robust PAC-Bayesian bound for GCN [38]. Under the same sampling and confidence setting as in (9), the robust bound for an l-layer GCN under ϵ-attack gives RD,0 (fw ) ≤ R̂S,γ (fw ) s (10) (B + ϵ)2 l2 h log(lh)Φ(fw ) + log ml δ + O 2 γ m
and (12c) connects output stability to the quadratic sensitivity term. Notably, Aj is to encode the blockwise sensitivity of the model output, while Rj determines how posterior variance is allocated across different perturbation directions. Variance choice. The probabilistic constraint in (12b) is handled by concentration √ of Gaussian quadratic forms [42]. With κ = 1 + 2 ln 2 + 4 ln 2, it is sufficient to ensure, with probability at least 1/2, that
Pd ∥W ∥2 Qd l l with spectral complexity Φ(w) = l=1 ∥Wl ∥22 l=1 ∥Wll ∥F2 . X X γ2 2 . (13) ∥Aj uj ∥22 ≤ σ 2 κ Tr(Aj Rj ATj ) ≤ The key step behind the robust bound is to control the 16 j=1 j=1 change of the robust margin under the weight perturbation. Specifically, for any perturbation ∆w = vec({∆Wk }lk=1 ) 2 satisfying ∥∆Wk ∥2 ≤ ∥Wk ∥2 /l for all k ∈ [l], and for any Thus, σ is chosen as the largest value allowed by (13), so as to satisfy the perturbation condition while minimizing the KL a, b ∈ [K], the robust margin perturbation is bounded as term in (12a). |RM (fw+∆w (G), a, b) − RM (fw (G), a, b)| Optimized posterior covariance. For fixed sensitivity ! l l matrices, minimizing the KL term in (12a) with respect to Y X ∥∆Wk ∥2 (11) ≤ 2e(B + ϵ) ∥Wk ∥2 . the covariance blocks gives ∥Wk ∥2 k=1 k=1 −1 16κ∥w∥22 T ∗ R = I + A A . (14) j j j C. The Unified Framework γ2 Anisotropic perturbations and sensitivity matrices. The T unified PAC-Bayesian framework in [39] establishes a flex- Thus, directions with larger sensitivity, as measured by Aj Aj , ible analytical framework for generalization by introducing receive smaller posterior variance, while less sensitive direcanisotropic Gaussian posteriors for weight perturbations and tions can retain larger variance. In doing so, the unified framework reduces the derivation of sensitivity matrices that measure how different perturbation PAC-Bayesian bounds to three steps: 1) Construct sensitivity directions affect the model output. The weight perturbation T T T matrices that dominate the perturbation effect; 2) Choose σ 2 is partitioned into l parameter blocks, u = (u1 , . . . , ul ) . 3) Evaluate the The framework considers u ∼ N (0, σ 2 R), where R = so that the perturbation condition holds, and ∗ KL term using the optimized covariance R . j blkdiag(R1 , . . . , Rl ). Each covariance block Rj specifies the posterior variance within the j-th parameter block, so that the distribution of weight perturbations can adapt to directionIII. ROBUST G ENERALIZATION B OUNDS dependent sensitivities rather than assigning a common variance In this section, we extend the unified framework from deep to all directions. To quantify the effect of these perturbations, neural networks to graph-structured models and from the a block-diagonal sensitivity matrix A = blkdiag(A1 , . . . , Al ) standard setting to the adversarial setting. Specifically, we is introduced, where Aj controls the sensitivity w.r.t. uj . present a tighter adversarially robust generalization bound Optimization Formula. For the Gaussian prior P = 2 2 for MPGNNs, which also covers classical graph learning N (0, σ I) and the anisotropic posterior Q = N (w, σ R), architectures such as GCNs as special cases. the KL term takes the form [41] In what follows, we start with some useful lemmas, followed l i 1 X h ∥Wj ∥2F by a modified version of the optimization problem in (12) DKL = + Tr(Rj ) − log det Rj − dim(Rj ) . σ2 2 j=1 dedicated to the adversarial settings. The framework in [39] seeks sensitivity matrices and posterior covariance blocks that satisfy the perturbation condition while minimizing KL, yielding the following optimization min
DKL (σ 2 , {Rj }), (12a) l X γ2 1 s.t. Pu∼N (0,σ2 R) ∥Aj uj ∥22 < ≥ , 16 2 j=1
σ 2 ,{Rj },{Aj }
Lemma 1 (Jacobian matrices with respect to Uj and Wj ). ∂fw (G) ∂fw (G) By defining JUj = ∂vec(U and JWj = ∂vec(W as the j) j) Jacobian matrices of the network output with respect to the input-injection weight matrix Uj and the message-passing weight matrix Wj , we have JUj = Mj Bjϕ Ihj ⊗ X , j ∈ [l − 1], (15) ϕ ρ JWj = Mj Bj Bj Ihj ⊗ PG ψj (Hj−1 ) , j ∈ [l] (16)
(12b) ∥fw+u (x) − fw (x)∥2∞ ≤
l X
∥Aj uj ∥22 .
j=1
(12c) Here (12a) minimizes the KL complexity of the anisotropic posterior, (12b) enforces the probabilistic perturbation condition,
∂fw (G) where Mj ≜ ∂vec(H is the Jacobian matrix of the network j) output with respect to the graph embeddings at the j-th layer ! Y j+1 ψ 1 ϕ ρ T T T Mj = Wl ⊗ 1n Bk Bk Wk ⊗ PG Bk , n k=l−1 (17)
5
with the diagonal matrices diag vec(ϕ′k (Ek )) , ϑ = ϕ, ϑ ′ Bk ≜ diag vec(ρk (Fk )) , ϑ = ρ, diag vec(ψk′ (Hk−1 )) , ϑ = ψ,
The output control in (23) verifies the output-stability condition in (12c), since ∥ · ∥∞ ≤ ∥ · ∥2 , and can also be translated into pairwise margin control, for any a, b ∈ [K], (18)
|M (fw+u (G), a, b) − M (fw (G), a, b)|
≤ 4∥fw+u (G) − fw (G)∥22 l−1 l X X ≤ 4 ∥AUj uUj ∥22 + ∥AWj uWj ∥22 .
where ϑ′k denotes the derivative of the activation function ϑ, with ϑ ∈ {ϕ, ρ, ψ}.
j=1
Proof. See Appendix A. Lemma 2 (Low-rank sensitivity matrices for MPGNN). For l > 1, B, L > 0, M1 , M2 ≥ 1, define τ = L3 M2 , and let 1/l l−1 −1 LM M τ , τ ̸= 1, 1 2 (19) β= τ −1 √ LM1 M2 , τ = 1. The spectral norm bound for all Jacobian matrices is given by max ∥JUj ∥2 , ∥JWj ∥2 ≤ Bs, (20) j∈[l]
l
where s = β if τ ̸= 1, s = (l − 1)β 2 if τ = 1, and we set JUl = 0 for notational convenience. Since fw (G) ∈ RK , the Jacobian matrices of the network output with respect to weight matrix satisfy rank(JUj ) ≤ K and rank(JWj ) ≤ K, we write JUj = QUj SUj VUTj ,
j=1
This margin form will be used to pass from standard perturbation control to robust-margin perturbation control. The scale s gives a common spectral envelope for the blockwise Jacobians: it captures the geometric accumulation of message passing when τ ̸= 1, and the linear accumulation in the critical case τ = 1. In the adversarial setting, the same rankK directions are retained, while the active scale is enlarged from B to B + ϵ, and the final bounds preserve the graphspectral dependence through τ and β, while replacing ambient dimension dependence by the K-dependent low-rank term. Lemma 3 (MPGNN robust margin perturbation with optimized variance). Let fw be an l-layer MPGNN with l > 1, and let AϵUj and AϵWj be the adversarial sensitivity matrices defined below in (26). Consider the prior P = N (0, σ 2 I) and the perturbation distribution u ∼ N (0, σ 2 Rϵ ), where Rϵ is block diagonal with
JWj = QWj SWj VWTj ,
ϵ RU = (I + η 2 (AϵUj )T AϵUj )−1 , j
SUj = diag(sUj ,1 , . . . , sUj ,K , 0, . . . , 0),
ϵ RW = (I + η 2 (AϵWj )T AϵWj )−1 , j
SWj = diag(sWj ,1 , . . . , sWj ,K , 0, . . . , 0).
√ where η 2 = 16κ∥w∥22 /γ 2 , with κ = 1 + 2 ln 2 + 4 ln 2. Since the prior variance cannot depend on the learned value of β, fix a cover point β̂ such that 1 β, τ ̸= 1, l+1 |β − β̂| ≤ 1 β, τ = 1, 3
where sUj ,1 ≥ · · · ≥ sUj ,K ≥ 0 and sWj ,1 ≥ · · · ≥ sWj ,K ≥ 0 denote the singular values in the at most K output directions. Accordingly, define the rank-K sensitivity matrices √ AUj = 2l − 1 VUj diag Bs, . . . , Bs, 0, . . . , 0 VUTj , (21) | {z } K
AWj =
2
√
2l − 1 VWj diag Bs, . . . , Bs, 0, . . . , 0 VWTj . (22) | {z } K
Then for any perturbation u, we have ∥fw+u (G) − fw (G)∥22 =
l−1 X
JUj uUj +
j=1
≤
l−1 X
∥AUj uUj ∥22 +
j=1
ŝ = l X
2
JWj uWj
j=1 l X
and define
∥AWj uWj ∥22 .
( l β̂ ,
τ ̸= 1,
(l − 1)β̂ 2 ,
τ = 1.
Consequently, with probability at least 1/2 over u, 2
(23)
|M (fw+u (G), a, b) − M (fw (G), a, b)|
2
(24)
≤ 4e2 σ 2 κ(2l − 1)2 KB 2 ŝ 2 .
j=1
Proof. See Appendix B. Remark 1. Lemma 2 constructs the sensitivity matrices in the standard setting. The key observation is that each blockwise output Jacobian maps parameter perturbations to the Kdimensional graph-level output, and therefore has rank at most K, regardless of the ambient dimension of the corresponding weight block. Hence it is sufficient to control the Jacobian action on these K active singular directions, rather than uniformly over all parameter directions. □
Furthermore, under the ϵ-attack with ϵ > 0, with probability at least 1/2 over u, the robust margin perturbation satisfies |RM (fw+u (G), a, b) − RM (fw (G), a, b)| ≤ 4e2 σ 2 κ(2l − 1)2 K(B + ϵ)2 ŝ 2 .
2
(25)
Comparing (24) with (25), the sensitivity scale is enlarged from B to B + ϵ. Thus, under the ϵ-attack, define Σϵ = diag (B + ϵ)s, . . . , (B + ϵ)s, 0, . . . , 0 , | {z } K
6
If τ = 1, then
and set the adversarial sensitivity matrices as √ AϵUj = 2l − 1 VUj Σϵ VUTj , √ AϵWj = 2l − 1 VWj Σϵ VWTj .
(26)
By setting 16e2 κ(2l − 1)2 K(B + ϵ)2 ŝ 2 1 = , σ2 γ2
(27)
with probability at least 1/2 over u, we have 2
|RM (fw+u (G), a, b) − RM (fw (G), a, b)| ≤
γ2 . 4
RD,0 (fw ) ≤ R̂S,γ (fw ) s m 2 4 2 4 l K(B + ϵ) β ∥w∥2 + ln δ , + O γ2m where ∥w∥22 = in (19).
Pl−1
2 j=1 ∥Uj ∥F +
(31)
Pl
2 j=1 ∥Wj ∥F , and β is defined
Proof. See Appendix D. (28)
Proof. See Appendix C. Lemma 3 provides the concrete probabilistic perturbation construction used in the robust PAC-Bayesian analysis. Compared with the optimization formulation in the preliminaries, the standard output-stability constraint is replaced by a robustmargin stability constraint. Accordingly, the sensitivity and covariance blocks Aj and Rj are replaced by their adversarial counterparts Aϵj and Rjϵ . This yields the modified optimization formulation in the adversarial setting, i.e.,
Remark 2. Theorem 1 gives the final robust PAC-Bayesian bound obtained from the Jacobian-based anisotropic perturbation analysis. The adversarial perturbation enters the bound through attacked feature matrix with maximum row Euclidean norm at most B +ϵ, when the attacked adjacency matrix can be arbitrary, the corresponding normalized propagation operator remains bounded by the worst-case with ∥PG′ ∥2 = 1. □
Remark 3. Compared with the existing isotropic robust PACBayesian framework, the proposed analysis improves both the dimensional and spectral dependence of the bound. Existing bounds control random perturbations in the full parameter min DKL (σ 2 , {Rjϵ }), (29a) space and therefore contain a hidden-width factor h log(lh), σ 2 ,{Rjϵ },{Aϵj } where l is the number of layers and h is the maximum l 2 X γ 1 hidden width [33], [38]. In contrast, our bound exploits the ϵ 2 s.t. Pu∼N (0,σ2 Rϵ ) ∥Aj uj ∥2 < ≥ , 16 2 rank structure of the blockwise output Jacobians, so the j=1 (29b) leading dimensional factor becomes K, the number of classes. Since typically K ≪ h log(lh) in graph classification tasks, 2 RM (fw+u (G), a, b) − RM (fw (G), a, b) this yields a tighter dimensional dependence. The spectral l X dependence is also refined for the non-homogeneous MPGNN ≤4 ∥Aϵj uj ∥22 . (29c) architecture. Taking τ ̸= 1 as an example, the previous −1 1/l j=1 robust MPGNN bound sets β = max{ζ , ξ }, where l−1 l ζ = min {∥U ∥ } , {∥W ∥ } denotes the smallest The adversarial sensitivity matrices in (26) are designed to j 2 j=1 j 2 j=1 spectral norm among the 2l − 1 weight blocks [38]. In contrast, satisfy the robust-margin domination requirement in (29c). 1/l our bound only uses the scale ξ . Hence the two scales Compared with the standard sensitivity matrices, they preserve −1 1/l coincide when ζ ≤ ξ , while our bound is strictly tighter the same Jacobian-aligned rank-K directions and only enlarge the active singular-value scale from Bs to (B + ϵ)s, which when ζ −1 dominates. In particular, if the smallest layer spectral matches the transition from (24) to (25). The variance choice norm is only slightly positive, then ζ −1 can be very large, in (27) is then used to meet the probabilistic perturbation making the previous β much larger than ξ 1/l . Thus, the requirement in (29b). Finally, the cover point β̂ ensures that the proposed bound preserves the graph-propagation dependence □ prior variance is chosen independently of the learned spectral while removing this reciprocal small-layer factor. scale, while ŝ records the corresponding Jacobian envelope in Remark 4. The generalization bounds obtained in [21], [33] the two regimes τ ̸= 1 and τ = 1. for parameter-sharing MPGNNs are special cases of Theorem 1. Given the above key lemmas, we are ready to derive the Note that such parameter-sharing MPGNNs are obtained by adversarially robust generalization bounds for MPGNNs. tying the layerwise weights in the present MPGNN formulation, Theorem 1 (Robust generalization bound for MPGNN). For where Uj = W1sh and Wj = W2sh for j ∈ [l−1], and the readcorresponding shared-parameter any B > 0 and l > 1, let fw ∈ H : X × G → RK be an out matrix is kept separate. PThe Pl−1 l−1 sh sh = l-layer MPGNN. Consider the ϵ-attack with ϵ > 0. Then, for Jacobians are JW j=1 JUj and JW2 = j=1 JWj . 1 any δ, γ > 0, with probability at least 1 − δ over the choice Since the layerwise Jacobians are dominated by the common sh ∥ ≤ (l − 1)Bs, and the of an i.i.d. size-m training set S according to D, for any w, sensitivity scale Bs, then ∥JW 2 2 sh 3 same bound holds for JW1 and JWl . Thus, parameter sharing we have, given τ = L M2 , that introduces at most an O(l) factor in the shared Jacobian norm, If τ ̸= 1, then but reduces the number of independent perturbation blocks RD,0 (fw ) ≤ R̂S,γ (fw ) from O(l) to O(1). Hence the margin-based perturbation bound s 2 2 2 m(l+1) 2 2 2 2l (30) remains of order O(l K(B +ϵ) s ), leading to the same robust l K(B + ϵ) β ∥w∥2 + ln δ +O ; generalization bound as in Theorem 1. □ γ2m
7
Corollary 1 (Robust generalization bound for GCNs). Under the same mild assumptions, consider the ϵ-attack with ϵ > 0. Let fw be an l-layer GCN with ReLU activations and normalized propagation operator ∥PG ∥2 ≤ 1. Then, for any δ, γ > 0, with probability at least 1 − δ over the choice of an i.i.d. size-m training set S ∼ Dm , for any w, we have RD,0 (fw ) ≤ R̂S,γ (fw ) s l2 K(B + ϵ)2 β 2l−2 ∥w∥22 + ln ml δ + O γ2m
(32)
Q 1/l Pl l where β = ∥W ∥ , and ∥w∥22 = j=1 ∥Wj ∥2F j 2 j=1 after the homogeneous normalization ∥Wj ∥2 = β. Proof. See Appendix E. Remark 5. Corollary 1 shows that the proposed MPGNN analysis naturally recovers the GCN case [33], [38]. The key difference is that GCNs are homogeneous in the layer weights, so the weights can be spectrally normalized without changing 1/l Ql the represented function. With β = and j=1 ∥Wj ∥2 W̃j = ∥Wβj ∥2 Wj , we have fw = fw̃ , and the spectral term becomes β
2l−2
∥w̃∥22 =
l Y j=1
∥Wj ∥22
A finer analysis of the impact of topology change PG′ − PG may yield robust bounds that more explicitly capture the role of topology attacks. Another direction is to refine the sensitivity matrix design as in [35] to account for graph structures. The present Jacobian-aligned low-rank construction exploits the K-dimensional output structure, but does not fully leverage the data-dependent graph geometry or architecture-specific constraints. Incorporating graph spectra, learned representations, or a message-passing structure, may further tighten the complexity term and improve the interpretability of robust generalization bounds for graph neural networks. A PPENDIX A. Proof of Lemma 1 Proof. For the readout layer, we have 1 vec(fw (G)) = WlT ⊗ 1Tn vec(Hl−1 ), n which yields 1 ∂fw (G) = WlT ⊗ 1Tn . ∂vec(Hl−1 ) n
(34)
For k = j + 1, . . . , l − 1, by the chain rule, we have ∂vec(Hk ) ∂vec(Ek ) = Bkϕ ∂vec(Hk−1 ) ∂vec(Hk−1 ) ∂vec(Fk ) = Bkϕ Bkρ ∂vec(Hk−1 ) = Bkϕ Bkρ WkT ⊗ PG Bkψ .
l X ∥Wj ∥2
F 2. ∥W ∥ j 2 j=1
Thus, the bound recovers the classical product-norm spectral complexity for homogeneous ReLU architectures. Unlike general MPGNNs, whose non-homogeneous input-injection and message-passing terms require a common spectral envelope, GCNs admit an exact layerwise spectral normalization. At the same time, the low-rank Jacobian construction replaces the hidden-width factor h log(lh) in isotropic PAC-Bayesian bounds by the class-dependent factor K, preserving the improved dimension dependence. □
(33)
(35)
Therefore, Mj =
j+1 Y ∂vec(Hk ) ∂fw (G) ∂vec(Hl−1 ) ∂vec(Hk−1 )
1 = n
k=l−1 Y j+1 WlT ⊗ 1Tn Bkϕ Bkρ k=l−1
! WkT ⊗ PG
Bkψ
,
(36) which proves (17). Next, for the input-injection weight matrix Uj , the perturbaThis paper derived a tighter PAC-Bayesian generalization tion enters the j-th layer through XUj , bound for MPGNNs in the adversarial setting using a Jacobian based sensitivity analytical approach. The analysis shows that, ∂vec(Hj ) ∂vec(XUj ) = Bjϕ = Bjϕ Ihj ⊗ X . (37) for graph classification, the output sensitivity of MPGNNs ∂vec(Uj ) ∂vec(Uj ) admits a low-rank structure induced by the K-dimensional Using the chain rule gives graph-level output. By exploiting this structure together with ∂fw (G) ∂vec(Hj ) optimized anisotropic Gaussian posteriors, we obtain robust JUj = = Mj Bjϕ Ihj ⊗ X , (38) ∂vec(Hj ) ∂vec(Uj ) generalization bounds with sharper spectral dependence and improved dimensional dependence compared with existing state- which proves (15). of-the-art methods. In particular, the spectral scale associated Similarly, for the message-passing weight matrix Wj , the with the learned weights is tightened, and the leading dimension perturbation enters the j-th layer through PG ψj (Hj−1 )Wj , factor is reduced from a hidden-width-dependent term to the such that number of classes. The framework also recovers GCN-type ∂vec(Hj ) ∂vec(PG ψj (Hj−1 )Wj ) = Bjϕ Bjρ models as special cases, yielding a unified robust generalization ∂vec(Wj ) ∂vec(Wj ) (39) analysis for representative GNN architectures. ϕ ρ = Bj Bj Ihj ⊗ PG ψj (Hj−1 ) , Several directions remain for future work. Although the present analysis allows arbitrary topology perturbations, their (40) JWj = Mj Bjϕ Bjρ Ihj ⊗ PG ψj (Hj−1 ) , effect is constrained by the worst-case bound ∥PG′ ∥2 ≤ 1, which does not distinguish different edge perturbation patterns which proves (16). In particular, for j = 1, since ψ1 (H0 ) = 0, or describe how graph changes affect the propagation operator. we obtain JW1 = 0. IV. C ONCLUSION
8
Define τ = L3 M2 ∥PG ∥2 , with the bound ∥PG ∥2 ≤ 1, and 1/l l−1 −1 LM M τ , τ ̸= 1, 1 2 β= τ −1 √ LM1 M2 , τ = 1.
B. Proof of Lemma 2 Proof. From Lemma 1, we first bound ∥Mj ∥2 as l−1 ∥Wl ∥2 Y √ ∥Mj ∥2 ≤ n
Bkϕ Bkρ (WkT ⊗ PG )Bkψ
2
k=j+1
≤
l−1 ∥Wl ∥2 Y 3 √ L ∥Wk ∥2 ∥PG ∥2 n
(41)
k=j+1
M2 ≤ √ τ l−1−j . n
Since fw (G) ∈ RK , the Jacobian matrices of the network output with respect to weight matrix satisfy rank(JUj ) ≤ K and rank(JWj ) ≤ K, hence we have
For the input-injection weight matrix Uj , we have ∥JUj ∥2 ≤ ∥Mj ∥2 ∥Bjϕ ∥2 Ihj ⊗ X 2 LM2 ∥X∥2 l−1−j √ ≤ τ n ≤ BLM2 τ l−1−j ,
By (42) and (49), with JUl = 0, M1 , M2 , L, τ > 0, then ( l Bβ , τ ̸= 1, max ∥JUj ∥2 , ∥JWj ∥2 ≤ (50) j∈[l] B(l − 1)β 2 , τ = 1.
JUj = QUj SUj VUTj ,
(42)
SUj = diag(sUj ,1 , . . . , sUj ,K , 0, . . . , 0), SWj = diag(sWj ,1 , . . . , sWj ,K , 0, . . . , 0),
where the last inequality uses √ √ ∥X∥2 ≤ ∥X∥F ≤ n ∥X∥2,∞ ≤ n B.
(43)
For the message-passing weight matrix Wj , we have ∥JWj ∥2 ≤ ∥Mj ∥2 ∥Bjϕ ∥2 ∥Bjρ ∥2 ∥PG ψj (Hj−1 )∥2
where sUj ,1 ≥ · · · ≥ sUj ,K ≥ 0 and sWj ,1 ≥ · · · ≥ sWj ,K ≥ 0 denote the singular values in the at most K output directions. Accordingly, define the rank-K sensitivity matrices √ AUj = 2l − 1 VUj diag Bs, . . . , Bs, 0, . . . , 0 VUTj , (51) | {z } K
≤ L2 ∥Mj ∥2 ∥PG ∥2 ∥ψj (Hj−1 )∥2 (44)
≤ L3 ∥Mj ∥2 ∥PG ∥2 ∥Hj−1 ∥F 1 ≤ √ τ l−j ∥Hj−1 ∥F , n
A Wj =
√
2l − 1 VWj diag Bs, . . . , Bs, 0, . . . , 0 VWTj , (52) | {z } K
where
where ψj is L-Lipschitz and ψj (0) = 0, such that
s=
∥ψj (Hj−1 )∥2 ≤ ∥ψj (Hj−1 )∥F ≤ L∥Hj−1 ∥F .
(45)
( l β,
JUTj JUj ⪯
∥Hj ∥F = ∥ϕj (Ej )∥F ≤ L∥XUj + ρj (Fj )∥F
(l − 1)β 2 ,
1 AT AUj , 2l − 1 Uj
2
≤ LM1 ∥X∥F + L ∥Fj ∥F
∥fw+u (G) − fw (G)∥22 =
2
≤ LM1 ∥X∥F + L ∥PG ∥2 ∥ψj (Hj−1 )∥F ∥Wj ∥2 ≤ LM1 ∥X∥F + L3 M2 ∥PG ∥2 ∥Hj−1 ∥F = LM1 ∥X∥F + τ ∥Hj−1 ∥F .
T JW JWj ⪯ j
1 AT AWj . 2l − 1 Wj
∥Hj ∥F ≤ LM1 ∥X∥F
j=1
≤ τ k,
(47)
k=0
τk ≤
√
n BLM1
k=0
j−2 X
τ k . (48)
Combining (44) and (48), we obtain j−2 X k=0
2
JWj uWj
j=1
l−1 X j=1
∥AUj uUj ∥22 +
j=1 l X
∥AWj uWj ∥22 .
(53)
j=1
Since ∥ · ∥∞ ≤ ∥ · ∥2 , (53) directly implies the output-stability condition in (12c). It also yields a corresponding pairwise margin control, for any a, b ∈ [K], by the definition of M , |M (fw+u (G), a, b) − M (fw (G), a, b)| = fw+u (G)a − fw+u (G)b − fw (G)a − fw (G)b
k=0
l−j
JUj uUj +
l X
2 l−1 l X X ≤ (2l − 1) ∥JUj uUj ∥22 + ∥JWj uWj ∥22
(46) j−1 X
l−1 X j=1
Since H0 = 0, iterating (46) gives
∥JWj ∥2 ≤ BLM1 τ
τ = 1.
Therefore, for any perturbation u, we have
≤ L∥XUj ∥F + L∥ρj (Fj )∥F
j−2 X
τ ̸= 1,
It is clear that
It remains to bound ∥Hj−1 ∥F , which is given by
∥Hj−1 ∥F ≤ LM1 ∥X∥F
JWj = QWj SWj VWTj ,
≤ |fw+u (G)a − fw (G)a | + |fw+u (G)b − fw (G)b | k
τ .
(49)
≤ 2∥fw+u (G) − fw (G)∥2 . (54)
9
Consequently,
Combining (59) with (53), we obtain
|M (fw+u (G), a, b) − M (fw (G), a, b)|
2
∥fw+u (G) − fw (G)∥22 ≤ e2 σ 2 κ(2l − 1)2 KB 2 ŝ 2 .
≤ 4∥fw+u (G) − fw (G)∥22 l−1 l X X ≤ 4 ∥AUj uUj ∥22 + ∥AWj uWj ∥22 . j=1
By (54), for any a, b ∈ [K], we have (55)
j=1
Thus, the same low-rank quadratic control can also be used for the pairwise margin perturbation condition. This completes the proof. C. Proof of Lemma 3 Proof. Consider the prior P = N (0, σ 2 I) and the random perturbation u ∼ N (0, σ 2 R). Note that the σ of the prior and the perturbation distributions are the same and will be set according to β. More precisely, we set σ based on cover point β̂ of β since the prior P cannot depend on any learned weights directly. We fix any β̂ and consider β which satisfies 1 β, τ ̸= 1, l+1 |β − β̂| ≤ 1 β, τ = 1. 3 If τ ̸= 1, then 1e β l ≤ β̂ l ≤ eβ l ; If τ = 1, then 49 β 2 ≤ β̂ 2 ≤ 16 2 1 2 2 2 9 β , which also implies e β ≤ β̂ ≤ eβ . We introduce the approximations of AUj and AWj , i.e., ÂUj = ÂWj =
√
√
2l − 1 VUj diag Bŝ, . . . , Bŝ, 0, . . . , 0 VUTj , | {z }
(56)
K
2l − 1 VWj diag Bŝ, . . . , Bŝ, 0, . . . , 0 VWTj , (57) | {z } K
where ŝ =
( l β̂ ,
τ ̸= 1, 2
(l − 1)β̂ ,
τ = 1,
with s ≤ eŝ, we have AUj ATUj ⪯ e2 ÂUj ÂTUj ,
AWj ATWj ⪯ e2 ÂWj ÂTWj . (58)
Then optimize the posterior covariance to minimize the KL divergence as in (14), such that RUj = (I + η 2 ATUj AUj )−1 ,
RWj = (I + η 2 ATWj AWj )−1 √ where η 2 = 16κ∥w∥22 /γ 2 , with κ = 1 + 2 ln 2 + 4 ln 2, since RUj ⪯ I and RWj ⪯ I. By the Gaussian concentration bound, with probability at least 1/2 over u, we have l−1 X
∥AUj uUj ∥22 +
j=1
l X
l−1 l X X ≤ σ2 κ Tr(AUj RUj ATU ) + Tr(AWj RWj ATW ) j
j
j=1
l−1 l X X Tr(ÂUj ÂTU ) + Tr(ÂWj ÂTW ) ≤ e2 σ 2 κ j
j
= e2 σ 2 κ(2l − 1)2 KB 2 ŝ 2 .
|M (fw+u (G), a, b) − M (fw (G), a, b)| ≤ Cσ B.
(60)
(61)
Consider the ϵ-attack with ϵ > 0. We choose the adversarial ∗ sample G∗w = arg inf G′ ∈δw (G) M (fw (G′ ), a, b) with Xw being the corresponding attacked node feature matrix, which minimizes the pairwise margin operator. Then we have |RM (fw+u (G), a, b) − RM (fw (G), a, b)| = M (fw+u (G∗w+u ), a, b) − M (fw (G∗w ), a, b) n ≤ max M (fw+u (G∗w+u ), a, b) − M (fw (G∗w+u ), a, b) , o |M (fw+u (G∗w ), a, b) − M (fw (G∗w ), a, b)| ∗ ∗ ≤ Cσ max ∥Xw+u ∥2,∞ , ∥Xw ∥2,∞ ≤ Cσ (B + ϵ). (62) Therefore, we have |RM (fw+u (G), a, b) − RM (fw (G), a, b)|
2
≤ 4e2 σ 2 κ(2l − 1)2 K(B + ϵ)2 ŝ 2 .
(63)
We now verify the two perturbation constraints in (29b) and (29c). Comparing (60) with (63), the robust margin perturbation has the same low-rank sensitivity structure as the standard margin perturbation, while the active scale is enlarged from B to B +ϵ. Therefore, to dominate the robust margin perturbation, it is sufficient to keep the Jacobian-aligned rank-K directions in (51) and (52), and replace the nonzero singular values Bs by (B + ϵ)s. Define Σϵ = diag (B + ϵ)s, . . . , (B + ϵ)s, 0, . . . , 0 . {z } | K
Then the adversarial sensitivity matrices are √ AϵUj = 2l − 1 VUj Σϵ VUTj , √ AϵWj = 2l − 1 VWj Σϵ VWTj . With these choices, the blockwise form of (29c) becomes 2
|RM (fw+u (G), a, b) − RM (fw (G), a, b)| l−1 l X X ≤ 4 ∥AϵUj uUj ∥22 + ∥AϵWj uWj ∥22
(64)
j=1
≤ 4e2 σ 2 κ(2l − 1)2 K(B + ϵ)2 ŝ 2 ,
j=1
j=1
2
≤ 4e2 σ 2 κ(2l − 1)2 KB 2 ŝ 2 . √ Equivalently, letting Cσ = 2eσ κK (2l − 1)ŝ, we have
j=1
∥AWj uWj ∥22
j=1
|M (fw+u (G), a, b) − M (fw (G), a, b)|
j=1
(59)
where the last inequality follows from (59). Next, for fixed adversarial sensitivity matrices, the covariance blocks are chosen by minimizing the KL term with respect to R. Applying (14) with Aj replaced by Aϵj , we obtain −1 ϵ,∗ 2 ϵ T ϵ RU = I + η (A ) A , Uj Uj j −1 ϵ,∗ RW = I + η 2 (AϵWj )T AϵWj . j
10
By (64), it is sufficient to choose σ 2 so that 2
4e2 σ 2 κ(2l − 1)2 K(B + ϵ)2 ŝ 2 ≤
γ . 4
Thus, setting 1 16e2 κ(2l − 1)2 K(B + ϵ)2 ŝ 2 = , σ2 γ2
(65)
gives, with probability at least 1/2 over u, that γ2 . 4 This verifies the perturbation requirement in (29b) together with (29c) and completes the proof. 2
|RM (fw+u (G), a, b) − RM (fw (G), a, b)| ≤
D. Proof of Theorem 1 Proof. In the adversarial setting, the posterior covariance is chosen according to the adversarial sensitivity matrices with the optimized adversarial covariance blocks, i.e., −1 ϵ,∗ RU = I + η 2 (2l − 1)VUj Σ2ϵ VUTj j −1 T = VUj I + η 2 (2l − 1)Σ2ϵ VUj , (66) −1 T ϵ,∗ = VWj I + η 2 (2l − 1)Σ2ϵ VWj , (67) RW j where η 2 = 16κ∥w∥22 /γ 2 . The optimized covariance has the same form as in the standard sensitivity framework, but its shrinkage is determined by the adversarial sensitivity scale (B + ϵ)s. Plugging the choice of 1/σ 2 in Lemma 3 into the KL objective (12a), we have " l−1 1 ∥w∥22 X ϵ,∗ ϵ,∗ 2 + Tr(R ) − log det(R ) − h DKL ≤ Uj Uj 2 σ2 j=1 # l X ϵ,∗ ϵ,∗ + Tr(RW ) − log det(RW ) − h2 j j j=1
8e2 κ∥w∥22 (2l − 1)2 K(B + ϵ)2 ŝ 2 ≤ γ2 2l−1 K 1 XX √ δ η 2l − 1 (B + ϵ)s + 2 j=1 k=1 8e κ∥w∥22 ≤ (2l − 1)2 K(B + ϵ)2 s2 γ2 4
η2 (2l − 1)2 K(B + ϵ)2 s2 2 8(e4 + 1)κ∥w∥22 = (2l − 1)2 K(B + ϵ)2 s2 γ2 2 l K(B + ϵ)2 s2 ∥w∥22 ≲O , γ2 √ where η 2 = 16κ∥w∥22 /γ 2 , κ = 1 + 2 ln 2 + 4 ln 2, +
δ(x) ≜
1 + log(1 + x2 ) − 1 ≤ x2 . 1 + x2
Recall that s(β) =
( l β,
τ ̸= 1, 2
(l − 1)β ,
τ = 1.
(68)
Thus, the fixed-β KL bound can be written as 2 l K(B + ϵ)2 β 2l ∥w∥22 , O γ2 DKL (Q∥P ) ≲ 4 l K(B + ϵ)2 β 4 ∥w∥22 O , γ2
τ ̸= 1, τ = 1.
Hence, for any fixed cover point β̂, with probability at least 1 1 − δ, for any w such that |β − β̂| ≤ l+1 β when τ ̸= 1, and 1 |β − β̂| ≤ 3 β when τ = 1, we have the following bounds, i.e., If τ ̸= 1, then RD,0 (fw ) ≤ R̂S,γ (fw ) s (69) l2 K(B + ϵ)2 β 2l ∥w∥22 + ln m δ + O ; 2 γ m If τ = 1, then RD,0 (fw ) ≤ R̂S,γ (fw ) s (70) l4 K(B + ϵ)2 β 4 ∥w∥22 + ln m δ . + O γ2m Finally, following the same arguments in [33], [38], we take a union bound over multiple choices of β̂ so that the bound holds for any β. In what follows, we treat the two cases separately. 1) If τ ̸= 1, then the nontrivial values of β satisfy 1/l √ 1/l γ m γ ≤β≤ . (71) 2(B + ϵ) 2(B + ϵ) On one hand, if β l < γ/(2(B + ϵ)), then for any attacked graph G′ and any i, j ∈ [K], using the Frobenius-norm bound on the hidden representation in (48), we have |RM (fw (G), i, j)| = |M (fw (G′ ), i, j)| ≤ 2∥fw (G′ )∥2 1 T ′ 1 H Wl =2 n n l−1 2 1 T ′ ≤2 1 ∥Hl−1 Wl ∥F n n 2 (72) 2 ′ ∥F ∥Wl ∥2 ≤ √ ∥Hl−1 n τ l−1 − 1 ≤ 2(B + ϵ)LM1 M2 τ −1 = 2(B + ϵ)β l < γ. Therefore, based on the definition in Eq. (7), we always have R̂S,γ (fw ) = 1 when β l < γ/(2(B √ + ϵ)). On the other hand, if β l > γ m/(2(B + ϵ)), it follows that s r l2 K(B + ϵ)2 β 2l ∥w∥22 + ln m l2 K∥w∥22 δ ≥ ≥ 1, (73) 2 γ m 4 with l ≥ 2, K ≥ 1, and ∥w∥22 ≥ 1. β To make |β − β̂| ≤ l+1 satisfied, we require |β − β̂| ≤ 1/l γ 1 . If a covering of the interval in Eq. (71) with l+1 2(B+ϵ) 1/l γ 1 radius l+1 can make the fixed-β̂ bound validated 2(B+ϵ)
11
with β̂ taking all possible values from the covering, then we could end up with a bound that holds for all β. It follows that 1 such a covering exists with size at most (l + 1)m 2l . Taking a union bound over all choices of β̂ with the cover yields the final generalization bound with probability 1 − δ for any β,
Moreover, for k = 1, . . . , j − 1, we have ∥Hk ∥F ≤ L∥PG ∥2 ∥Hk−1 ∥F ∥Wk ∥2 . Iterating (82) with H0 = X gives
RD,0 (fw ) ≤ R̂S,γ (fw ) s (74) l2 K(B + ϵ)2 β 2l ∥w∥22 + ln m(l+1) δ . + O 2 γ m 2) If τ = 1, the nontrivial values of β satisfy 12 12 √ γ γ m . ≤β≤ 2(B + ϵ)(l − 1) 2(B + ϵ)(l − 1)
∥Hj−1 ∥F ≤ ∥X∥F ≤
nB
L∥PG ∥2 ∥Wk ∥2
k=1 j−1 Y
(83)
L∥PG ∥2 ∥Wk ∥2 .
Combining (80), (81), and (83), we obtain (75)
and there exists a covering of the interval in Eq. (75) with size 1 at most 3m 4 . Taking a union bound over all choices of β̂ with the cover yields the final generalization bound with probability 1 − δ for any β, i.e.,
∥JWj ∥2 ≤ B (L∥PG ∥2 )
l−1
l Y
∥Wk ∥2 .
(84)
k=1 k̸=j
Since ϕj is the ReLU activation function, we have L = 1, and we use the normalized adjacency matrix ∥PG ∥2 ≤ 1, such that Y ∥JWj ∥2 ≤ B ∥Wk ∥2 . (85) k̸=j
Let β=
l Y
!1/l ∥Wk ∥2
.
k=1
(77)
By the homogeneity of GCNs, we normalize the weights as W̃k =
Summarizing two cases completes the proof.
β Wk , ∥Wk ∥2
so that we have fw = fw̃ . For the normalized weights, ∥W̃k ∥2 = β, then (85) gives
E. Proof of Corollary 1 Proof. For the readout layer,
∥JWj ∥2 ≤ Bβ l−1 .
1 ∂fw (G) = WlT ⊗ 1Tn . ∂vec(Hl−1 ) n
JWj = QWj SWj VWTj , SWj = diag(sWj ,1 , . . . , sWj ,K , 0, . . . , 0),
Therefore, j+1 Y
! Bkϕ
WkT ⊗ PG
.
(78)
k=l−1
For the message-passing weight matrix Wj , we have ∂vec(Hj ) = Bjϕ Ihj ⊗ PG Hj−1 , ∂vec(Wj ) JWj = Mj Bjϕ Ihj ⊗ PG Hj−1 , j ∈ [l].
≤ L∥Mj ∥2 ∥PG ∥2 ∥Hj−1 ∥F ,
(88)
It is clear that (79)
T JW JWj ⪯ j
1 T A A Wj , l Wj
j ∈ [l].
(80) ∥fw+u (G) − fw (G)∥22 =
l X j=1
k=j+1
(89)
Therefore, for any perturbation u, we have
where l−1 ∥Wl ∥2 Y ∥Mj ∥2 ≤ √ L∥PG ∥2 ∥Wk ∥2 . n
(87)
where sWj ,1 ≥ · · · ≥ sWj ,K ≥ 0, and we have sWj ,r ≤ Bβ l−1 for r ∈ [K]. Accordingly, define √ AWj = l VWj diag(Bβ l−1 , . . . , Bβ l−1 , 0, . . . , 0)VWTj . | {z } K
We next bound the spectral norm of JWj as ∥JWj ∥2 ≤ ∥Mj ∥2 ∥Bjϕ ∥2 ∥PG Hj−1 ∥2
(86)
Since fw (G) ∈ RK , the Jacobian matrices of GCN output have rank at most K. Hence, for j ∈ [l], we have
For k = j + 1, . . . , l − 1, by the chain rule, we have ∂vec(Hk ) = Bkϕ WkT ⊗ PG . ∂vec(Hk−1 )
1 WlT ⊗ 1Tn Mj = n
√
j−1 Y
k=1
If√β 2 < γ/(2(B + ϵ)(l − 1)), then R̂S,γ (fw ) = 1; if β 2 > γ m/(2(B + ϵ)(l − 1)), then s s l4 K(B + ϵ)2 β 4 ∥w∥22 + ln m l4 K∥w∥22 δ ≥ ≥ 1, (76) γ2m 4(l − 1)2
RD,0 (fw ) ≤ R̂S,γ (fw ) s l4 K(B + ϵ)2 β 4 ∥w∥22 + ln m δ + O . γ2m
(82)
(81)
≤
l X j=1
2
JWj uWj 2
∥AWj uWj ∥22 .
(90)
12
Since the prior cannot depend on the learned value of β, we fix a cover point β̂ such that |β − β̂| ≤ βl . Then β l−1 ≤ eβ̂ l−1 . Let us introduce the approximations of the sensitivity matrices √ ÂWj = l VWj diag(B β̂ l−1 , . . . , B β̂ l−1 , 0, . . . , 0)VWTj , {z } | K
(91) and optimize the posterior covariance to minimize the KL with −1 16κ∥w∥22 . RWj = I + η 2 ÂTWj ÂWj , η2 = γ2 Since RWj ⪯ I, by the Gaussian concentration bound, with probability at least 1/2 over u, we have l X
∥AWj uWj ∥22 ≤ σ 2 κ
j=1
l X
Tr AWj RWj ATWj
j=1
≤ e2 σ 2 κ
l X
(92)
Tr ÂWj ÂTWj
j=1
= e2 σ 2 κl2 KB 2 β̂ 2l−2 . Combining (92) with (90), we obtain ∥fw+u (G) − fw (G)∥22 ≤ e2 σ 2 κl2 KB 2 β̂ 2l−2 .
(93)
Consider the ϵ-attack with ϵ > 0, we have |RM (fw+u (G), i, j) − RM (fw (G), i, j)|
2
(94)
≤ 4e2 σ 2 κl2 K(B + ϵ)2 β̂ 2l−2 . By setting 1 16e2 κl2 K(B + ϵ)2 β̂ 2l−2 = , σ2 γ2
(95)
the robust perturbation condition 2
|RM (fw+u (G), i, j) − RM (fw (G), i, j)| ≤
γ2 4
is satisfied with probability at least 1/2 over u. It remains to derive the KL term and remove the dependence of the prior on the learned value β. Plugging the choice of 1/σ 2 in (95) into the KL objective gives 2 l K(B + ϵ)2 β 2l−2 ∥w∥22 . (96) DKL (Q∥P ) ≲ O γ2 Therefore, for any fixed cover point β̂, we have RD,0 (fw ) ≤ R̂S,γ (fw ) s (97) l2 K(B + ϵ)2 β 2l−2 ∥w∥22 + ln m δ + O . γ2m With the same arguments as in the MPGNN, we end up with the final robust generalization bound RD,0 (fw ) ≤ R̂S,γ (fw ) s (98) l2 K(B + ϵ)2 β 2l−2 ∥w∥22 + ln ml δ + O . γ2m This completes the proof.
R EFERENCES [1] 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. [2] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zambaldi, 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. [3] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in International Conference on Learning Representations, 2017. [4] W. L. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in Advances in Neural Information Processing Systems, vol. 30, 2017, pp. 1024–1034. [5] M. Zitnik, M. Agrawal, and J. Leskovec, “Modeling polypharmacy side effects with graph convolutional networks,” Bioinformatics, vol. 34, no. 13, pp. i457–i466, 2018. [6] R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec, “Graph convolutional neural networks for web-scale recommender systems,” in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2018, pp. 974–983. [7] 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. [8] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. J. Goodfellow, and R. Fergus, “Intriguing properties of neural networks,” in International Conference on Learning Representations, 2014. [9] I. J. Goodfellow, J. Shlens, and C. Szegedy, “Explaining and harnessing adversarial examples,” in International Conference on Learning Representations, 2015. [10] D. Zügner, A. Akbarnejad, and S. Günnemann, “Adversarial attacks on neural networks for graph data,” in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2018, pp. 2847–2856. [11] D. Zügner and S. Günnemann, “Adversarial attacks on graph neural networks via meta learning,” in International Conference on Learning Representations, 2019. [12] H. Wu, C. Wang, Y. Tyshetskiy, A. Docherty, K. Lu, and L. Zhu, “Adversarial examples on graph data: Deep insights into attack and defense,” in Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019, pp. 4816–4823. [13] X. Wan, H. Kenlay, B. Ru, A. Blaas, M. A. Osborne, and X. Dong, “Adversarial attacks on graph classification via Bayesian optimisation,” in Advances in Neural Information Processing Systems, vol. 34, 2021, pp. 6983–6996. [14] 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. [15] X. Zhang and M. Zitnik, “GNNGuard: Defending graph neural networks against adversarial attacks,” in Advances in Neural Information Processing Systems, 2020. [16] N. Entezari, S. A. Al-Sayouri, A. Darvishzadeh, and E. E. Papalexakis, “All you need is low (rank): Defending against adversarial attacks on graphs,” in Proceedings of the Thirteenth ACM International Conference on Web Search and Data Mining, 2020, pp. 169–177. [17] 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. [18] 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. [19] 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. [20] 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. [21] V. K. Garg, S. Jegelka, and T. Jaakkola, “Generalization and representational limits of graph neural networks,” in Proceedings of the 37th International Conference on Machine Learning, 2020, pp. 3419–3430.
13
[22] S. Lv, “Generalization bounds for graph convolutional neural networks via rademacher complexity,” arXiv preprint arXiv:2102.10234, 2021. [23] S. Verma and Z.-L. Zhang, “Stability and generalization of graph convolutional neural networks,” in Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019, pp. 1539–1548. [24] X. Zhou and H. Wang, “The generalization error of graph convolutional networks may enlarge with more layers,” Neurocomputing, vol. 424, pp. 97–106, 2021. [25] S. S. Du, K. Hou, R. Salakhutdinov, B. Póczos, R. Wang, and K. Xu, “Graph neural tangent kernel: Fusing graph neural networks with graph kernels,” in Advances in Neural Information Processing Systems, 2019. [26] D. A. McAllester, “Simplified PAC-Bayesian margin bounds,” in Learning Theory and Kernel Machines. Springer, 2003, pp. 203–215. [27] J. Langford and J. Shawe-Taylor, “PAC-Bayes & margins,” in Advances in Neural Information Processing Systems, 2003, pp. 439–446. [28] O. Catoni, PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning. Institute of Mathematical Statistics, 2007. [29] E. Parrado-Hernández, 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. [30] G. K. Dziugaite and D. M. Roy, “Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data,” in Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, 2017. [31] P. L. Bartlett, D. J. Foster, and M. J. Telgarsky, “Spectrally-normalized margin bounds for neural networks,” in Advances in Neural Information Processing Systems, 2017. [32] B. Neyshabur, S. Bhojanapalli, and N. Srebro, “A PAC-Bayesian approach to spectrally-normalized margin bounds for neural networks,” in International Conference on Learning Representations, 2018. [33] R. Liao, R. Urtasun, and R. S. Zemel, “A PAC-Bayesian approach to generalization bounds for graph neural networks,” in International Conference on Learning Representations, 2021. [34] 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. [35] X. Yi, “Topology-aware PAC-Bayesian generalization analysis for graph neural networks,” arXiv preprint arXiv:2604.10553, 2026. [36] P. Viallard, E. G. Vidot, A. Habrard, and E. Morvant, “A PAC-Bayes analysis of adversarial robustness,” in Advances in Neural Information Processing Systems, 2021. [37] J. Xiao, R. Sun, and Z.-Q. Luo, “PAC-Bayesian spectrally-normalized bounds for adversarially robust generalization,” in Advances in Neural Information Processing Systems, 2023. [38] T. Sun and J. Lin, “PAC-Bayesian adversarially robust generalization bounds for graph neural network,” arXiv preprint arXiv:2402.04038, 2024. [39] 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. [40] H. Dai, B. Dai, and L. Song, “Discriminative embeddings of latent variable models for structured data,” in International Conference on Machine Learning, 2016, pp. 2702–2711. [41] L. Pardo, Statistical Inference Based on Divergence Measures. Chapman and Hall/CRC, 2018. [42] M. Rudelson and R. Vershynin, “Hanson-Wright inequality and subgaussian concentration,” Electronic Communications in Probability, vol. 18, pp. 1–9, 2013.