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

Abstract

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.

References in corpus (14)

• Semi-Supervised Classification with Graph Convolutional Networks
• Spectral Networks and Locally Connected Networks on Graphs
• Gated Graph Sequence Neural Networks
• How Powerful are Graph Neural Networks?
• Graph networks as learnable physics engines for inference and control
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Spectrally-normalized margin bounds for neural networks
• Learning Multimodal Graph-to-Graph Translation for Molecular Optimization
• Stronger generalization bounds for deep nets via a compression approach
• Generalization and Representational Limits of Graph Neural Networks
• Spatially-Aware Graph Neural Networks for Relational Behavior Forecasting from Sensor Data
• On the equivalence between graph isomorphism testing and function approximation with GNNs
• Stability and Generalization of Graph Convolutional Neural Networks

Cited by in corpus (8)

• On Provable Benefits of Depth in Training Graph Convolutional Networks
• From Local Structures to Size Generalization in Graph Neural Networks
• Generalizing Graph Neural Networks on Out-Of-Distribution Graphs
• Generalization bounds for graph convolutional neural networks via Rademacher complexity
• Reconstruction for Powerful Graph Representations
• Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks
• On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction
• Multi-fidelity Stability for Graph Representation Learning