Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion

1 Introduction

• The paper develops GNN generalization bounds that replace maximum-degree dependence with dependence on the graph diffusion matrix's spectral norm.The analysis uses stability against noise injections and Hessians.Source: §1 · p. 2
• The bounds cover message-passing, graph convolutional, and graph isomorphism networks, with a matching lower-bound instance scaling with the diffusion matrix's spectral norm.The unified analysis extends beyond the single-layer, node-prediction setting described for prior stability analysis [50].Source: §1 · pp. 2–3
• The paper uses the trace of the loss Hessian to measure GNN noise stability, with its formal analysis applying to twice-differentiable, Lipschitz-continuous activations such as tanh and sigmoid.The authors also identify uniform convergence of the Hessian matrix as a potentially independent technique.Source: §1 · p. 3
• The Hessian-based bounds are non-vacuous and match the scale of observed generalization gaps, while the graph-dependent bounds are numerically much smaller than prior results [16] [38].The comparison is illustrated on real-world graphs in Figure 1.Source: Figure 1 · p. 2, §1 · p. 3
• The proposed fine-tuning algorithm updates perturbed GNN weights; experiments on molecular graph classification tasks show its benefit in fine-tuning.The motivation is to address overfitting and poor test performance when fine-tuning large pretrained GNNs.Source: §1 · pp. 1–3

Generalization Bounds

• Prior multilayer-network bounds use norm or margin approaches based on Rademacher complexity or PAC-Bayesian analysis, and can apply to fine-tuning from initialization [4] [20] [39] [2] [43] [37] [34].The paper builds on Arora et al. (2018) and Ju et al. (2022), while noting that the latter's Hessian analysis lacks explicit data dependence.Source: §2 · p. 3

Graph Representation Learning

• Graph-learning research includes convolutional, attention, isomorphism-testing, message-passing, and pooling architectures; fine-tuning pretrained graph representations has received little generalization study [6] [36] [24] [49] [27].The paper's analysis explicitly depends on graph structure and applies to message-passing layers with additional nonlinear mappings.Source: §2 · pp. 3–4

Generalization in Graph Neural Networks

• GNN generalization research includes algorithm-task alignment, transductive Rademacher bounds, and size generalization, which concerns performance degradation on graphs of different sizes [14] [48] [58].The authors suggest their tools may also be useful for studying extrapolation.Source: §2 · p. 4

Expressivity of Graph Neural Networks

• GNN expressivity for graph classification is related to one-dimensional Weisfeiler-Lehman testing [42], with limitations on tasks such as cycle counting [45] [3].The paper treats expressivity as orthogonal to generalization, which concerns sample efficiency.Source: §2 · p. 4

3.1 Problem setup

• The setup models graph-level prediction from independently sampled graphs using node features, graph diffusion layers, and a final pooling layer.Source: §3.1 · pp. 4–5

3.2 Main results

• Bounds for l-layer MPNNs depend on ||P_G||_2^(l−1); the framework unifies untied-weight GCNs and MPNNs and also covers GIN and mean-aggregation GraphSAGE.Source: §3.2 · pp. 5–6, Table 1 · p. 6

3.3 Comparison with prior art

• Across three tasks, our bounds are consistently smaller than prior results; adjacency diffusion has norm below maximum degree, while normalized symmetric adjacency has norm at most one.Source: §3.3 · p. 7, Figure 2 · p. 7

3.4 A matching lower bound

• On a complete graph with self-loops, linear diffusion layers, zero U, and logistic loss, a constructed distribution yields a lower bound matching the upper bound's diffusion-norm scaling.Source: §3.4 · p. 8
• Although worst-case bounds become vacuous for large depth, a data-dependent Hessian-trace bound is non-vacuous and matches the scale of observed generalization errors.Source: §3.4 · p. 8

4 Proof Techniques and Extensions

• For a star graph, the (1, ∞) norm of the GCN diffusion matrix is √n, while its spectral norm is less than one.The cited comparison says the former norm can exceed the latter by a factor of √n.Source: §4 · pp. 8–9
• Taylor expansion links the perturbed loss to the Hessian trace: the first-order noise term averages to zero, while the second-order term contributes σ^2 times the trace.A PAC-Bayesian bound combines expected perturbation loss with a prior-posterior KL term; layerwise noise variances balance these components.Source: §4 · p. 9
• The analysis treats graph-level prediction; extending it to node-level prediction would require a random-graph population perspective and remains future work.The passage notes that directly applying the analysis to semi-supervised learning is problematic because graph size is finite.Source: §4 · p. 10
• Lipschitz conditions on activation derivatives enable uniform Hessian convergence and bounds on its trace using weight-matrix and graph spectral norms.The proof uses an epsilon-cover argument and induction on derivatives through the feedforward layers.Source: §4 · pp. 9–10

4.1 Extensions

• The graph-isomorphism-network extension bounds generalization using the spectral norm of averaged graph diffusion matrices.It averages classification losses across layers and incorporates the linear classification layer into the analysis.Source: §4.1 · pp. 10–11
• The bounds extend to fine-tuning pretrained GNNs by setting norm constraints to the distance between pretrained and fine-tuned models.Source: §4.1 · p. 11

5 An Algorithm for Fine-tuning Graph Neural Networks

• The algorithm minimizes expected perturbed loss, equivalent to minimizing empirical loss plus the Hessian trace, using paired positive and negated noise perturbations.The negated perturbation cancels the first-order Taylor term; the method is motivated by small-data fine-tuning overfit risk.Source: §5 · p. 11

5.1 Experimental setup

• Experiments fine-tune pretrained GINs on five MoleculeNet graph-classification datasets using a fixed five-layer architecture and scaffold splits.Baselines include early stopping, weight decay, dropout, weight averaging, and distance-based regularization.Source: §5.1 · pp. 11–12

5.2 Experimental results

• Our algorithm outperforms baseline methods by average rank on all five molecular property prediction datasets.Table 2 reports test ROC-AUC averaged over binary prediction tasks in each dataset and over five random seeds.Source: §5.2 · p. 12, Table 2 · p. 13
• The algorithm consistently reduces the BACE training-test loss gap, particularly with training set size N = 600; Figure 3 also reports decreasing Hessian trace and largest eigenvalue during training.The Hessian trace reduction is reported as more significant than with early stopping.Source: §5.2 · p. 12, Figure 3 · p. 13
• Using negated perturbations improves performance by 1% on average over five datasets compared with omitting them.Ten perturbations are reported as sufficient to obtain most of the gain.Source: §5.2 · pp. 12–13

• The unified analysis develops sharp generalization bounds depending on the graph diffusion matrix and uses Hessian-based bounds that match observed gaps on real-world graphs.Source: §6 · p. 13
• Noise-stability optimization provides an algorithmic demonstration of the practical implications of the theoretical findings.Source: §6 · p. 14
• Whether these tools extend to graph attention networks or Hessian-based measurement of out-of-distribution gaps remains open.The passage also notes a subsequent analysis of algorithm convergence rates under Lipschitz-continuous gradient conditions.Source: §6 · p. 14

A Proofs

• The appendix organizes the complete proofs for Section 3, including the MPNN bound, Theorem 3.1, the lower bound, and graph-isomorphism networks.It begins with notations and graph facts before the proof subsections.Source: A Proofs · p. 17
• For an undirected graph with maximum degree d_G, the adjacency-matrix spectral norm lies between √d_G and d_G.Source: A Proofs · p. 17
• The star graph has ∥PG∥ close to √d_G, whereas the complete graph has ∥PG∥ close to d_G.Source: A Proofs · p. 17

A.1 Proof of our PAC-Bayesian bound (Lemma 4.1)

• The proof assumes twice-differentiable activations and loss, with Lipschitz bounds on the functions and their first- and second-order derivatives.Source: §A.1 · p. 18

A.1.1 Proof of Proposition A.4

• Proposition A.4 bounds perturbation-induced changes in layer-output Hessians, while Claim A.6 bounds changes in the corresponding Jacobians.Source: §A.1 · p. 18, §A.1.1 · p. 21

A.1 Proof of our PAC-Bayesian bound (Lemma 4.1)

• The PAC-Bayesian argument bounds the noisy-versus-original loss difference using a Taylor expansion involving the Hessian trace.The proof then applies a PAC-Bayes bound under a bounded-loss condition.Source: §A.1 · pp. 19–20
• ξ is O(N^-3/4 + log(δ^-1)N^-1), which the proof bounds by O(log(δ^-1)/N^3/4).Source: §A.1 · p. 20

A.2 Proof for message passing graph neural networks

• The proof strategy first derives a trace bound for the Hessian, then establishes first- and second-order derivative bounds before completing the Theorem 3.1 proof.Source: §A.2 · pp. 24–25

A.2.1 Proof of Lemma 4.3

• Lemma 4.3 treats the Hessian trace as two parts associated with the layer weight matrices.Source: §A.2.1 · p. 25

A.2.2 Dealing with first-order derivatives

• Proposition A.7 gives bounds on first-order derivatives of layer outputs with respect to W(i) and U(i) for layers j ≥ i.Source: §A.2.2 · p. 26

A.2.3 Deal with second-order derivatives

• Proposition A.8 addresses second-order derivatives of the final layer output with respect to W(i) and U(i).Source: §A.2.3 · p. 28

A.2.4 Proof of Theorem 3.1

• The proof applies first- and second-order derivative bounds through Lemma 4.3 to obtain a bound on the Hessian trace with respect to W(i).Source: §A.2.4 · p. 32
• An induction over layers bounds the Frobenius norm of H(i−1), which is then used to bound the trace of H(l) with respect to W(i).Source: §A.2.4 · p. 32
• The proof also bounds the final-layer weight Hessian trace and states that the corresponding U(i) trace satisfies the same bound, completing the MPNN case.Source: §A.2.4 · p. 33

A.3 Proof of matching lower bound (Theorem 3.2)

• The lower-bound construction uses a complete graph and fixes arbitrary layer weights, forming Z as their product and selecting its largest singular value and corresponding singular vectors.The feature matrix is set from the leading left singular vector, while labels are uniform over +1 and −1.Source: §A.3 · p. 34
• The construction evaluates the network with logistic loss and expresses the example losses using α, the diffusion factor and largest singular value of Z.The passage gives α = n^(l−1)λmax(Z), with P having all entries equal to one and λmax(P) = n.Source: §A.3 · p. 34
• The product matrix’s spectral norm is bounded above by the product of the layer norm bounds, completing the proof of equation (6).The proof states that for sufficiently large N, the generalization gap is at least a lower threshold with probability at least 0.1, but the threshold is not included in the passage.Source: §A.3 · p. 34

A.4 Proof for graph isomorphism networks (Corollary 4.5)

• For graph isomorphism networks, the empirical and population losses are respectively the sample average and expectation of the loss averaged across classification layers.The section first specifies this averaged loss function.Source: §A.4 · p. 35
• The proof applies the trace guarantee and repeats earlier proposition steps across layer indices to derive the loss-Hessian trace bound.It also states a propagation-matrix bound as part of the derivation.Source: §A.4 · p. 35
• These steps complete the generalization-error analysis for graph isomorphism networks in equation (11).Source: §A.4 · p. 35

B Experiment Details

• The bound uses B = 5.4 as an upper bound on loss across all training and testing examples in five experimental datasets.Source: B Experiment Details · p. 36
• The bound comparison uses GCN and MPGNN architectures, with shared weights across the first l−1 layers and layer width 128 at depths 2, 4, and 6.GCNs use ReLU with U set to zero; MPGNNs use ReLU for ϕt and Tanh for ρt and ψt.Source: B Experiment Details · p. 36
• On the three collaboration-network datasets, models use one-hot node-degree features and are trained with Adam at learning rate 0.01 for 50 epochs with batch size 128.The bounds are computed following the setup in Liao et al. [38].Source: B Experiment Details · p. 36
• The comparison includes bounds from Liao et al. [38] and Garg et al. [16], with the latter passage identifying maximum degree, hidden width, and desired margin as bound parameters.Source: B Experiment Details · p. 36