PaperlayerView exact revision on arXiv

Source-linked AI summary

A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks

Renjie Liao, Raquel Urtasun, Richard Zemel

arXiv:2012.07690v1cs.LG

TL;DR

Few existing analyses explain GNN generalization across model variants or account tightly for graph statistics. This paper uses PAC-Bayesian analysis to bound generalization for GCNs and MPGNNs. The bounds generalize MLP/CNN results for GCNs and improve on the Rademacher-complexity bound for MPGNNs, though the reported bound values remain vacuous.

  • Problem

    Few works explain why GNNs generalize to unseen graphs, and existing analyses are limited to specific variants or have loose dependencies on graph statistics.

    Source: §1 · p. 1

  • Method

    The paper derives PAC-Bayesian generalization bounds for GCNs and MPGNNs using GNN-specific perturbation analysis and an approach that handles non-homogeneous networks.

    Source: §1 · p. 2

  • Results

    The GCN bound generalizes MLP/CNN bounds, while the MPGNN bound improves on the Rademacher-complexity bound in its dependencies on maximum node degree and maximum hidden dimension.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The analysis can extend to node classification and link prediction, and to other loss functions when they are bounded.

    Source: §5 · p. 9

    The bound values remain vacuous in the experiments, and the worst-case perturbation analysis may be loose.

    Source: §5 · p. 9

Abstract

from arXiv · show

In this paper, we derive generalization bounds for the two primary classes of graph neural networks (GNNs), namely graph convolutional networks (GCNs) and message passing GNNs (MPGNNs), via a PAC-Bayesian approach. Our result reveals that the maximum node degree and spectral norm of the weights govern the generalization bounds of both models. We also show that our bound for GCNs is a natural generalization of the results developed in arXiv:1707.09564v2 [cs.LG] for fully-connected and convolutional neural networks. For message passing GNNs, our PAC-Bayes bound improves over the Rademacher complexity based bound in arXiv:2002.06157v1 [cs.LG], showing a tighter dependency on the maximum node degree and the maximum hidden dimension. The key ingredients of our proofs are a perturbation analysis of GNNs and the generalization of PAC-Bayes analysis to non-homogeneous GNNs. We perform an empirical study on several real-world graph datasets and verify that our PAC-Bayes bound is tighter than others.

1 Introduction

Although GNNs have achieved empirical success, few works explain their generalization, and existing analyses are limited to specific variants or have loose dependencies on graph statistics. This paper derives PAC-Bayesian generalization bounds for GCNs and MPGNNs, relating graph structure and learned weights to generalization.

1 Introduction

  • GNNs learn representations by propagating information through shared local computations, with GCNs generalizing convolution and MPGNNs parameterizing message passing with neural networks.The paper asks how graph structure affects generalization bounds in relation to existing MLP/CNN results.Source: §1 · pp. 1–2
  • The GCN bound extends ReLU MLP/CNN bounds by adding a maximum-degree factor, and coincides with them on graphs without edges.Both bounds share a product of layerwise weight spectral norms multiplied by a factor additive across layers.Source: §1 · p. 2
  • The bounds for MPGNNs improve the dependency on maximum node degree and maximum hidden dimension over the Rademacher-complexity bound, and are tighter on four real-world graph datasets.The governing terms include a geometric series of learned weights and a multiplicative factor involving maximum node degree.Source: §1 · p. 2
  • The analysis adapts PAC-Bayes proofs to GNNs using vector-norm perturbation analysis and a constructed weight quantity that accommodates non-homogeneous networks.The construction supports the perturbation constraints and a finite covering needed for the PAC-Bayes bound.Source: §1 · p. 2

2 Background

The background establishes the graph-classification setting and assumptions, introduces GCNs and MPGNNs as the models under study, and reviews the PAC-Bayes framework used in the analysis.

2 Background

  • The paper reviews the analysis setup, representative GNN models, and PAC-Bayes analysis needed for its bounds.The setup assumes graph samples are drawn i.i.d. from an unknown distribution.Source: §2 · p. 2, §2.1 · p. 3

2.1 Analysis Setup

  • The setup considers K-class graph classification with i.i.d. graph samples, bounded node-feature norms, a maximum hidden dimension, and simple graphs with a maximum node degree.The graph sample is a triplet of adjacency matrix, node features, and output label.Source: §2.1 · pp. 2–3

2.2 Graph Neural Networks (GNNs)

  • The model section reviews GCNs and MPGNNs for graph classification and uses a multiclass margin loss.GCNs use graph convolution and mean readout; the selected MPGNN family follows a shared message-passing framework.Source: §2.2 · pp. 3–4

2.3 Background of PAC-Bayes Analysis

  • PAC-Bayes bounds use a prior and a learned posterior over models; perturbing learned weights can yield a tractable bound when the output change remains small with high probability.The framework permits constructing priors and posteriors to obtain an analytical KL divergence.Source: §2.3 · pp. 4–5

3 Generalization Bounds

The section develops PAC-Bayesian generalization bounds for GCNs and MPGNNs using perturbation analysis, then compares the bounds with prior GNN results and relates the GCN bound to neural-network bounds.

3.1 PAC-Bayes Bounds of GCNs

  • GCN perturbation analysis bounds output changes using weight spectral norms and graph statistics, with maximum node degree identified as the key stability statistic.The resulting generalization bound is presented in Theorem 3.2.Source: §3.1 · pp. 5–6

3.2 PAC-Bayes Bounds of MPGNNs

  • For MPGNNs, shared weights across message-passing steps yield a geometric-series term, and a specialized weight quantity supports PAC-Bayes analysis of non-homogeneous models.The section gives a perturbation bound and then Theorem 3.4 for generalization.Source: §3.2 · p. 6

3.3 Comparison with Other Bounds

  • The comparison covers GNN generalization bounds, while the spectral-norm dependencies cannot be compared without learned-weight values.The paper uses an empirical study for the spectral-norm comparison.Source: §3.3 · p. 7, Table 1 · p. 7, §3.3.1 · p. 7

3.3.1 Comparison with Existing GNN Generalization Bounds

  • For maximum node degree, the MPGNN bound scales as O(d^(l−1)) and is described as better than the Rademacher bound for large-degree graphs; its O(√h log h) hidden-dimension dependence is tighter than the Rademacher and VC-dimension bounds, whose VC term is O(h^4).The paper notes that large hubs are common in social networks.Source: §3.3.1 · p. 7

3.3.2 Connections with Existing Bounds of MLPs/CNNs

  • The GCN bound adds a graph-degree factor to the MLP/CNN bound and coincides with it on single-node graphs, so it generalizes the result of (Neyshabur et al., 2017).The paper treats MLPs/CNNs with ReLU activations as GCNs on single-node graphs.Source: §3.3.2 · p. 8

4 Experiments

Experiments compare the PAC-Bayes and Rademacher complexity bounds on synthetic and real-world graph-classification datasets. The PAC-Bayes bound is mostly tighter across both groups, although both bounds remain vacuous.

Experimental setup

  • Experiments cover six synthetic random-graph datasets and four real-world graph-classification datasets, with three random initializations per experiment.The real-world datasets are COLLAB, IMDB-BINARY, IMDB-MULTI, and PROTEINS.Source: §4 · p. 8

Results

  • The PAC-Bayes bound is mostly tighter than the Rademacher complexity bound across varying message-passing steps on synthetic and real-world datasets.The authors report that the improvement generally grows with maximum node degree and, in most cases, with the number of steps.Source: §4 · p. 8, Figure 2 · p. 9

Experimental setup

  • Figure 2 evaluates the bounds on ER and SBM synthetic datasets whose maximum node degrees range from 25 to 87 for ER and from 25 to 36 for SBM.The figure caption identifies the settings and their left-to-right order.Source: Figure 2 · p. 9

Results

  • Both bounds exceed 1 on all reported evaluations, indicating that they remain vacuous; both also grow with more message-passing steps.The experiments use at most 10 steps, and the authors report dC > 1 and a geometric series much greater than 1 across datasets.Source: §4 · p. 9

5 Discussion

The paper summarizes its bounds for GCNs and MPGNNs, identifies possible extensions, and notes that the current analysis does not yet explain practical GNN behavior.

Discussion

  • The analysis may extend to node classification and link prediction, and to other loss functions such as regression losses when they are bounded.The stated extension is supported by perturbation bounds on the maximum change of any node representation.Source: §5 · pp. 9–10

Limitations

  • The experiments yield vacuous bounds, and worst-case perturbation analysis may be loose; the Gaussian posterior may not match the posterior induced by learning, and optimization is not explicitly modeled.The authors state that optimization affects the learned weights.Source: §5 · p. 9

Future work

  • Open questions include whether graph statistics beyond maximum node degree affect generalization, whether the analysis extends to attention or learnable spectral-filter architectures, and how optimization algorithms affect generalization.The paper also raises whether neural-network compression and data-dependent priors could improve the bounds.Source: §5 · p. 10

A Appendix

The appendix summarizes important notation and says that the following sections provide proofs of the main-text results and additional details.

A Appendix

  • The following sections provide proofs of all main-text results and additional details.Source: A Appendix · p. 13
  • Table 2 summarizes important notations used throughout the paper.The appendix introduces the table as a reference for notation used in the following sections.Source: Table 2 · p. 13, A Appendix · p. 13
  • The appendix includes the notation table as part of its supporting material.Source: Table 2 · p. 13

A.1 PAC Bayes Results

This section supplies proofs of standard PAC-Bayes results, including a two-sided bound and a perturbation-based lemma for models with parameter distributions independent of training data.

A.1 PAC Bayes Results

  • Theorem 2.1 gives a two-sided PAC-Bayes result that holds with probability 1 − δ for every posterior distribution and any γ > 0.Source: §A.1 · p. 15
  • The proof of the two-sided result combines Hoeffding’s inequality with a two-sided tail lemma for a random variable bounded by exponential tails.Source: §A.1 · pp. 14–15
  • Lemma 2.2 constructs a posterior by perturbing model parameters, assuming the prior is independent of training data and the perturbation keeps outputs within γ/4 with probability above 1/2.Source: §A.1 · p. 15
  • The perturbation-lemma proof bounds a restricted posterior’s contribution using the Bernoulli entropy and nonnegativity of KL divergence.Source: §A.1 · pp. 16–17

A.2 Graph Results

This section proves norm bounds for the self-loop-adjusted graph Laplacian used in GCN perturbation analysis.

A.2 Graph Results

  • For the Laplacian formed from the adjacency matrix with self-loops, the spectral norm is at most 1 and the Frobenius norm is at most √r, where r is its rank.Source: §A.2 · p. 18
  • The same lemma bounds the Laplacian’s 1-norm and infinity norm by a quantity dependent on the graph’s maximum node degree.Source: §A.2 · p. 18
  • The proof uses symmetry and nonnegativity of the self-loop-adjusted adjacency matrix, together with spectral properties of the Laplacian.Source: §A.2 · p. 18

A.3 GCN Results

This section proves the GCN generalization bound through perturbation analysis of node representations and the graph-level readout.

A.3 GCN Results

  • The proof recursively analyzes perturbations in node representations before bounding their effect on the final readout layer.Source: §A.3 · pp. 19, 21
  • The perturbation is added to each layer’s weights, and the proof uses the input-feature bound and the graph-Laplacian lemma in bounding node representations.Source: §A.3 · p. 19
  • For layers before readout, the analysis bounds both the maximum node-representation norm and the maximum change under weight perturbation.Source: §A.3 · pp. 19–20
  • Theorem 3.2 states a generalization bound for an l-layer GCN under the stated B, δ, and γ conditions.Source: §A.3 · p. 21

A.4 MPGNNs Results

The MPGNN analysis uses weight perturbations to bound output changes and derive a generalization bound, with separate treatment for dC = 1 and dC ≠ 1.

A.4 MPGNNs Results

  • The proof recursively bounds perturbation effects on node representations before bounding the output change at the final readout.The perturbation lemma covers an l-step MPGNN; the proof handles the readout after the other steps.Source: §A.4 · pp. 24, 28
  • For simple graphs, the incoming-incidence norm is at most d−1; the analysis relaxes this to d to also cover graphs with added self-loops.Source: §A.4 · p. 24
  • The generalization bound defines λ from the first and readout-layer spectral norms and ξ from Cφ and dC, with ζ the minimum of three weight spectral norms.The theorem applies to l-step MPGNNs and holds with probability at least 1−δ over an i.i.d. training set.Source: §A.4 · p. 29
  • The dC = 1 case is included for completeness, and the authors say it occurs rarely in practice.Source: §A.4 · p. 31
  • The proof applies to both homogeneous and non-homogeneous GNNs.Source: §A.4 · p. 33

A.5 Bound Comparison

This section explains the comparison between GNN generalization bounds based on Rademacher complexity and the paper’s bounds.

A.5 Bound Comparison

  • The section provides details of a comparison involving Rademacher-complexity-based GNN generalization bounds.Source: §A.5 · p. 33
  • The comparison concerns generalization bounds for GNNs.Source: §A.5 · p. 33
  • Rademacher complexity is the stated basis for the bounds examined in this section.Source: §A.5 · p. 33

A.5.1 Rademacher Complexity based Bound

This subsection restates the Rademacher-complexity-based GNN bound and clarifies its notation and layer counting.

A.5.1 Rademacher Complexity based Bound

  • The subsection restates the Rademacher-complexity-based generalization bound from Garg et al. (2020).Source: §A.5.1 · p. 33
  • B1, B2, and Bl denote the spectral norms of W1, W2, and Wl, respectively.Source: §A.5.1 · p. 33
  • The exponent l−1 in the numerator of M counts the readout function among the l layers or steps.This counting corresponds to l−1 message-passing steps.Source: §A.5.1 · p. 33

A.5.2 Comparison in Our Context

The section compares PAC-Bayes and Rademacher-complexity bounds across practical regimes, relates the GCN bound to ReLU-network results, and reports empirical comparisons on real-world and synthetic datasets.

A.5.2 Comparison in Our Context

  • A uniform upper bound on the update function φ is considered impractical for common choices such as ReLU, and would make the bound more cumbersome.Source: §A.5.2 · p. 34
  • In practice, the Rademacher comparison typically falls in case C (dC > 1, ξ ≫ 1), while the PAC-Bayes comparison more often falls in case B (dC > 1, ξ ≫ 1, ζ ≤ 1).Source: §A.5.2 · p. 35
  • The VC-dimension bound scales as O(h^4N^2), yielding a generalization bound of O(h^4N/√m), and N may greatly exceed the maximum degree d.Source: §A.5.2 · p. 35

A.6 Connections with Existing Bounds of MLPs/CNNs

  • The GCN bound adds a graph-degree factor to the ReLU-network bound and coincides with it for single-node graphs where d = 1.Source: §A.6 · p. 36

A.7 Experimental Details

  • Experiments use six synthetic Erdős–Rényi and stochastic-block-model datasets with 200 graphs each, testing depths 2, 4, 6, and 8; real-world runs test depths 2 and 4.Source: §A.7 · pp. 36–37
  • PAC-Bayes bounds are tighter in all evaluated settings except one synthetic setting with small maximum degree and large step count.The comparison includes both real-world and synthetic datasets; reported bound values are in the log domain.Source: §A.7 · p. 37, Table 6 · p. 37, Table 7 · p. 37
Loading 2012.07690v1…