PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks

Pascal Mattia Esser, Leena Chennuru Vankadara, Debarghya Ghoshdastidar

arXiv:2112.03968v1cs.LGstat.ML

TL;DR

The paper addresses limited theoretical understanding of generalization for GNNs in transductive inference. It analyzes learning-theoretic bounds for node classification and finds that, under distributional assumptions, transductive Rademacher complexity can explain observed GNN behavior, though the bounds have practical scope limits.

  • Problem

    There is little theoretical understanding of neural-network generalization beyond supervised learning, including the role of unlabeled data in transductive inference.

    Source: §1 · p. 1

  • Method

    The paper analyzes graph-convolutional networks for node classification using transductive VC-dimension and Rademacher-complexity bounds, including planted graph-and-feature models.

    Source: §1 · p. 3

  • Results

    Under distributional assumptions, transductive Rademacher-complexity bounds explain GNN generalization trends, and residual connections have a smaller generalization gap than vanilla GNNs.

    Source: §1 · p. 3, §5 · p. 10

  • Takeaways & Limitations

    The analysis suggests that classical learning theory can provide insight into GNN behavior when the complexity measure and data assumptions are appropriately chosen.

    Source: §5 · p. 10

    Generalization bounds can exceed 1 because of absolute constants that cannot be precisely estimated, so their parameter dependence is of interest.

    Source: §3.2 · p. 8

Abstract

from arXiv · show

In recent years, several results in the supervised learning setting suggested that classical statistical learning-theoretic measures, such as VC dimension, do not adequately explain the performance of deep learning models which prompted a slew of work in the infinite-width and iteration regimes. However, there is little theoretical explanation for the success of neural networks beyond the supervised setting. In this paper we argue that, under some distributional assumptions, classical learning-theoretic measures can sufficiently explain generalization for graph neural networks in the transductive setting. In particular, we provide a rigorous analysis of the performance of neural networks in the context of transductive inference, specifically by analysing the generalisation properties of graph convolutional networks for the problem of node classification. While VC Dimension does result in trivial generalisation error bounds in this setting as well, we show that transductive Rademacher complexity can explain the generalisation properties of graph convolutional networks for stochastic block models. We further use the generalisation error bounds based on transductive Rademacher complexity to demonstrate the role of graph convolutions and network architectures in achieving smaller generalisation error and provide insights into when the graph structure can help in learning. The findings of this paper could re-new the interest in studying generalisation in neural networks in terms of learning-theoretic measures, albeit in specific problems.

1 Introduction

The introduction frames a gap in theory for transductive learning and graph neural networks, where graph structure and unlabeled nodes matter. It proposes that suitable learning-theoretic measures, under distributional assumptions, can explain GNN generalization and illuminate architectural effects.

Related work

  • Prior GNN analyses cover transductive stability, supervised learning-theoretic measures, and limiting regimes, but the paper emphasizes graph information in the complexity bound and finite-network implications.It contrasts its focus with Oono et al. (2020b), which uses a weak-learning/boosting framework, and notes that implications of limiting analyses for finite GNNs are difficult to infer.Source: §1 · p. 2

Contributions and paper structure

  • VC-dimension generalization bounds are typically loose for graph-based transductive inference, except in a few trivial cases.Source: §1 · p. 3
  • Transductive Rademacher-complexity bounds are more informative, underscoring the importance of choosing an appropriate complexity measure.Source: §1 · p. 3
  • Under a planted graph-and-feature model, test error follows the trends predicted by the refined generalization bounds, supporting learning-theoretic explanations under distributional assumptions.The introduction notes that such analysis under random graphs is rare in GNN literature.Source: §1 · p. 3
  • Residual connections have a smaller generalization gap than vanilla GNNs, while bounds explain the influence of network depth on performance only to a limited extent.Source: §1 · p. 3

2 Statistical Framework for Transductive Learning on GNN

The section formalizes graph-based transductive learning and derives generalization bounds using VC dimension and transductive Rademacher complexity. VC-based bounds are often limited, while TRC bounds provide more expressive terms for examining graph and feature effects under suitable assumptions.

2.1 Framework for Transductive Learning

  • The framework treats the graph as part of the hypothesis class and models transduction with all features available, a subset of known labels, and predictions on the remaining nodes.GNN layers apply an activation to a bias plus the diffused previous-layer representation multiplied by trainable weights.Source: §2.1 · pp. 3–4

2.2 Generalisation Error-bound using VC Dimension

  • For connected practical graphs with rank(S)=O(n), the VC-based bound can be trivial when dK−1>rank(S) and does not reflect degree normalization’s positive influence.The discussion also notes that graph information can reduce class complexity in simpler settings.Source: §2.2 · p. 5

2.3 Generalisation Error-bound using Transductive Rademacher Complexity

  • With self-loop diffusion, ∥Sloop∥∞=1+dmax, so for fixed ω the bound grows with maximum degree and network depth.For regular graphs, the degree-normalized operator has ∥Snor∥∞=1.Source: §2.3 · p. 6
  • TRC bounds expose the roles of diffusion and features through ∥S∥∞ and ∥SX∥2→∞, and choosing ω=O(1/∥S∥∞) avoids exponential growth with network depth.The bound depends on how graph diffusion acts on the feature matrix, linking graph and feature information.Source: §2.3 · p. 6
  • An alternative bound connects repeated diffusion to oversmoothing: its diffusion factor is ∥S∥2^k, and increasing depth can lose graph information.The paper relates this to settings where the number of layers grows toward infinity.Source: §2.3 · p. 6

3 Generalization using TRC under Planted Models

Under planted-model assumptions, the paper uses transductive Rademacher complexity to analyze how graph and feature structure affect GNN generalization. Experiments follow several predicted trends, though the bounds do not establish the absolute theory–experiment gap.

3.1 Model and Bounds on TRC

  • The analysis bounds expected TRC under two-class Gaussian-mixture features and a two-community SBM, with Γ=|y^T z| measuring feature–graph alignment.Source: §3 · p. 6, §3.1 · p. 7
  • Normalization removes the n term from the compared bound, and both normalized cases grow more slowly with n; the self-loop deterministic term has extra n dependence.Source: §3.1 · pp. 7–8
  • Comparing no graph information (S=I) with normalized diffusion lets the random-graph analysis characterize when graph information helps.Source: §3.1 · p. 8

3.2 Experimental Results

  • As latent feature–graph alignment increases, generalization error increases; adding feature noise on Cora produces similar behavior, though Cora’s true alignment is unavailable.Source: §3.2 · pp. 8–9
  • TRC-bound slack terms can exceed 1, so further work is needed to characterize the absolute gap between theory and experiments.Source: §3.2 · p. 8
  • Across SBM and Cora, generalization error stays mostly consistent as n varies, while increasing observed labels sharply lowers error initially before convergence.Source: Figure 1 · p. 8, §3.2 · p. 9

4 Influence of Depth and Residual Connections on the Generalisation Error

The paper extends transductive Rademacher-complexity analysis to residual GNNs and examines how depth and skip connections relate to generalisation. The bounds favor residual connections, while experiments show where depth trends match or depart from theoretical predictions.

4.1 Model and bounds on TRC for GNN with Residual connections

  • Residual layers interpolate between the layer update and the initial features, preserving more feature influence than connections only to the previous layer.The paper follows the residual setup of Chen et al. (2020).Source: §4.1 · p. 9
  • The residual-network bound increases as α decreases, implying a lower bound for skip-connected GNNs than for vanilla GNNs.The comparison assumes β = ∥X∥∞.Source: §4.1 · p. 9

4.2 Experiments on depth and Residual networks

  • Residual GNN generalisation error is empirically below vanilla GNN's on SBM and Cora, and the α ordering matches predictions; depth growth departs from exponential bounds.The depth-related deviation is attributed to the bounded absolute values of Lu and Lm; the authors say the depth component needs refinement.Source: Figure 2 · p. 10, §4.2 · p. 10

5 Conclusion

The conclusion argues that, with an appropriate complexity measure and distributional assumptions, statistical learning theory can offer insight into GNN generalisation. It also identifies limits in the depth analysis and fixed parameter-norm assumptions.

5 Conclusion

  • Under distributional assumptions and a carefully constructed complexity measure, classical learning theory provides insight into GNN behavior.The paper identifies the TRC bound's predicted exponential dependence on depth K as only partially visible empirically.Source: §5 · p. 10
  • The analysis fixes trainable-parameter norm bounds, and its predicted exponential dependence on depth K is only partially observed empirically.The authors suggest that loosening the norm assumption could support analysis during training and under different optimization approaches.Source: §5 · p. 10
  • The authors propose extending planted-model analysis to stability, model selection, and supervised graph classification.They also note that the theoretical analysis could extend to architectures such as dropout or batch normalization.Source: §5 · p. 10

B Proof Proposition 1 — Generalisation error bound for GNNs using VC-Dimension

This proof section develops VC-dimension bounds for GNN hypothesis classes and discusses their dependence on graph and network properties. It motivates a different complexity measure when graph-rank arguments provide little insight.

B Proof Proposition 1 — Generalisation error bound for GNNs using VC-Dimension

  • VC dimension is the largest cardinality of a set that a hypothesis class can shatter, with infinite dimension if it can shatter arbitrarily large sets.The section uses this definition to develop generalisation bounds for GNN classes.Source: B Proof Proposition 1 — Generalisation… · p. 16

B.1 Generalization using VC-Dimension under specific graph assumptions

  • For the nonlinear GNN class, the proof loses information about hidden-layer dimensions; the resulting bound retains graph-rank dependence but only the last hidden-layer dimension.The text notes that rank cannot generally be ordered before and after applying a nonlinearity, so the linear-network argument does not extend directly.Source: §B.1 · pp. 16–17

B.2 Additional notes on the remarks related to Proposition 1

  • Because graph adjacency matrices can have full rank in expectation under stochastic block models, the authors turn to a complexity measure less reliant on combinatorial arguments.The section also reports similar expected-rank behavior for more complex graph models.Source: §B.2 · p. 17

C Proof Theorem 1 — Generalization error bound for GNNs using TRC

The appendix proves the TRC bound by recursively bounding contributions from GNN layers and then handling the first layer. Its supporting calculations use standard TRC lemmas and bounds on the network parameters.

C Proof Theorem 1 — Generalization error bound for GNNs using TRC

  • The proof derives a restricted GNN hypothesis-class TRC bound under per-layer constraints on bias and weight norms.It begins by recursively bounding the TRC of a neuron applied across layers, then combines that recursion with a first-layer bound.Source: C Proof Theorem 1 — Generalization… · p. 18

C.1 TRC calculus

  • The TRC calculus section invokes a Massart-style proof idea and a contraction lemma, extending the argument to Lipschitz continuous functions.These lemmas supply intermediate tools for the later bounds.Source: §C.1 · pp. 19–20

C.2 Recursive bound on the TRC of single neurons

  • For a single neuron, the recursive TRC step scales the previous-layer complexity by the diffusion-operator norm and the weight bound.The displayed derivation gives a factor of 2∥S∥∞ω.Source: §C.2 · pp. 21–22

C.3 Bound on the TRC for the first layer

  • The first-layer proof separately bounds the linear and bias terms before combining them into its final TRC bound.The bias contribution is bounded using βQ(n)2p.Source: §C.3 · pp. 23–24

C.4 Additional notes on the remarks related to Theorem 1

The remarks compare graph-free and graph-informed complexity for empty, fully connected, and b-regular graphs. For empty and fully connected graphs, the stated complexity is lower with graph information.

C.4 Additional notes on the remarks related to Theorem 1

  • For the empty graph, the analysis substitutes A = K_G into the expression for the graph-information term.The passage pairs this case with the complete graph, A = I.Source: §C.4 · p. 24
  • For the fully connected graph, the complexity measure is lower than when graph information is not considered.The text also states that the graph-free complexity upper-bounds the complexity when graph information is considered.Source: §C.4 · p. 24
  • For a b-regular graph, the analysis sets X = I to consider graph information alone and uses the normalized operator S.A b-regular graph is defined as one where every vertex has degree b.Source: §C.4 · p. 24

D Proof Theorem 3 — TRC for Residual GNNs

The appendix extends the transductive Rademacher complexity analysis to residual GNNs, deriving a bound analogous to the vanilla-network bound. The accompanying setup models features and graph structure with separate latent labels, allowing their alignment to vary.

D Proof Theorem 3 — TRC for Residual GNNs

  • The residual propagation rule mixes the transformed, graph-propagated layer with the initial representation using α ∈ (0, 1).The rule applies the activation function φ to the mixture.Source: D Proof Theorem 3 — TRC for Residual… · p. 25
  • The residual-network analysis derives a transductive Rademacher complexity bound analogous to the vanilla-network bound.It applies layer-wise propagation bounds recursively and combines them with a bound on the first layer.Source: D Proof Theorem 3 — TRC for Residual… · p. 25

E.1 Setup (recap from the main paper)

  • The setup samples features from a two-component Gaussian mixture and generates the graph from a two-class stochastic block model.The feature labels z and graph labels y can differ, so the setup allows graph and feature information to be misaligned.Source: §E.1 · p. 26

E.2 Main Proof

The proof obtains expected transductive Rademacher complexity bounds by decomposing terms and bounding their expectations. It treats self-loop and degree-normalized operators separately and applies the setup to Gaussian-mixture features and a two-class stochastic block model.

E.2 Main Proof

  • The proof decomposes the expected complexity terms, treating ∥SX∥2→∞ as deterministic and using Cauchy–Schwarz for the remaining terms.Table 1 summarizes concentration bounds for self-loop and degree normalization.Source: §E.2 · p. 26, Table 1 · p. 27

E.3 Concentration Bounds

  • The concentration analysis separates self-loop and degree-normalized diffusion operators when bounding the terms involving the random graph.The section notes that the final version sets the self-loop weight γ = 1.Source: §E.3 · pp. 27–28

E.3.2 Bound E [∥(X −X) S∥2→∞]

  • For the feature-noise term, the proof considers self-loop and degree-normalized cases and concludes its bound.The supplied text does not state the bound's value.Source: §E.3.2 · pp. 32–34

E.3.3 Bound E

  • The proof separately treats self-loop and degree-normalized cases in bounding the next expectation term.The supplied passages indicate completion of the bound but do not provide its value.Source: §E.3.3 · pp. 34–35

E.3.4 Bound ∥SX∥2→∞.

  • The cited discussion distinguishes two cases, labeling one “Self loop” and the other “Degree normalized”; the supplied excerpts do not state a bound for either case.For the degree-normalized case, the expected degree is (1 + o(1))n(p+q)/2.Source: §E.3.4 · pp. 35–36

F.1 Data

  • The data setup uses Gaussian-mixture node features and a two-class stochastic block model, with separate latent labels allowing graph and feature information not to align.The passages also identify Cora as a real-world dataset, with 2,708 papers, seven classes, and 1,433 bag-of-words features.Source: §F.1 · p. 37

F.2.1 SBM

The SBM experiments vary latent-label alignment, graph size, and the number of observed points. The reported theoretical bound is plotted only for its trend, while the discussion notes limits in capturing optimization and the absolute theory–experiment gap.

F.2.1 SBM

  • The SBM experiments vary alignment Γ, graph size n, and the fraction of observed points m/n.The setup specifies Γ/n = 0.7, p = 0.2, and q = 0.15 for the observed-points variation.Source: §F.2.1 · p. 37
  • The theoretical bound is plotted for its trend because its absolute value falls outside (0, 1).The passage attributes this to slack terms in the underlying bound that can already exceed 1.Source: §F.2.1 · p. 37
  • The bounds do not explicitly account for optimization, motivating the experiment's consideration of different training epochs.The text identifies analysis of parameter-bound behavior during optimization as a possible future direction.Source: §F.2.1 · p. 37
  • The clarity of the observed trends depends on the setting, and some learning rates make changes less evident.The passage says the reported learning rate is one for which the change is clearer.Source: §F.2.1 · p. 37
  • Further work is needed to characterize the absolute gap between theory and experiments; the plotted bounds fix β and ω at approximately 0.1.The passage calls for further analysis of how changing these parameter bounds changes the generalization-error bound.Source: §F.2.1 · p. 38

F.2.2 Cora

The Cora experiments vary feature noise, graph size, and the fraction of observed points. The setup uses a multi-class loss and Adam optimization.

F.2.2 Cora

  • The Cora setup uses a multi-class negative log-likelihood loss and Adam with learning rate 0.01.Source: §F.2.2 · p. 38
  • Adding Gaussian noise to Cora feature vectors produces behavior similar to the stochastic block model experiments as feature-noise scale varies over 10 steps.The noise is added as X + ϵ, with ϵ_i· drawn independently from N(0, σ²_FeატI).Source: §F.2.2 · p. 38
  • The experiments sample 10 Cora subgraphs with sizes ranging from 1,354 to 2,708 nodes.Source: §F.2.2 · p. 38
  • The observed-point fraction m/n varies from 0.05 to 0.3 over 10 steps.Source: §F.2.2 · p. 38

F.3 Experiments Section 4.2 (Residual connections)

The residual-connection experiments vary network depth and residual weight on two datasets. The implementation builds on Kipf et al.'s official code.

F.3 Experiments Section 4.2 (Residual connections)

  • Residual connections target the first layer, with hidden dimensions d_i = 16 for all layers; this differs from the direct-to-features setup in (13).The passage says this choice follows Chen et al. (2020), since connecting directly to features would otherwise fix hidden-layer size to n.Source: §F.3 · p. 38
  • The experiments vary depth K over [4] and compare two residual connections with α in {0.2, 0.5} on both datasets.Source: §F.3 · p. 38

F.4 Implementation

Loading 2112.03968v1…