A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Generalization BoundsMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
PAC-Bayesian Adversarially Robust Generalization Bounds for Graph Neural Network
Graph neural networks (GNNs) have gained popularity for various graph-related tasks. However, similar to deep neural networks, GNNs are also vulnerable to adversarial attacks. Empirical studies have shown that adversaria…
Generalization BoundsGraph Neural NetworkTopology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networks
Graph neural networks have demonstrated excellent applicability to a wide range of domains, including social networks, biological systems, recommendation systems, and wireless communications. Yet a principled theoretical…
Stochastic OptimizationRecommendation SystemsGraph ClassificationPAC-Bayesian Generalization Bounds for Knowledge Graph Representation Learning
While a number of knowledge graph representation learning (KGRL) methods have been proposed over the past decade, very few theoretical analyses have been conducted on them. In this paper, we present the first PAC-Bayesia…
DecoderGeneralization BoundsGraph Neural NetworkGraph Representation Learning+5PAC-Bayesian Generalization Bounds for MultiLayer Perceptrons
We study PAC-Bayesian generalization bounds for Multilayer Perceptrons (MLPs) with the cross entropy loss. Above all, we introduce probabilistic explanations for MLPs in two aspects: (i) MLPs formulate a family of Gibbs …
Generalization BoundsVariational InferenceGeneralization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion
Graph neural networks are widely used tools for graph prediction tasks. Motivated by their empirical performance, prior works have developed generalization bounds for graph neural networks, which scale with graph structu…
Generalization Bounds