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

Haotian Ju, Dongyue Li, Aneesh Sharma, Hongyang R. Zhang
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:6314-6341, 2023.

Abstract

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 structures in terms of the maximum degree. In this paper, we present generalization bounds that instead scale with the largest singular value of the graph neural network’s feature diffusion matrix. These bounds are numerically much smaller than prior bounds for real-world graphs. We also construct a lower bound of the generalization gap that matches our upper bound asymptotically. To achieve these results, we analyze a unified model that includes prior works’ settings (i.e., convolutional and message-passing networks) and new settings (i.e., graph isomorphism networks). Our key idea is to measure the stability of graph neural networks against noise perturbations using Hessians. Empirically, we find that Hessian-based measurements correlate with observed generalization gaps of graph neural networks accurately; Optimizing noise stability properties for fine-tuning pretrained graph neural networks also improves the test performance on several graph-level classification tasks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-ju23a, title = {Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion}, author = {Ju, Haotian and Li, Dongyue and Sharma, Aneesh and Zhang, Hongyang R.}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {6314--6341}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/ju23a/ju23a.pdf}, url = {https://proceedings.mlr.press/v206/ju23a.html}, abstract = {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 structures in terms of the maximum degree. In this paper, we present generalization bounds that instead scale with the largest singular value of the graph neural network’s feature diffusion matrix. These bounds are numerically much smaller than prior bounds for real-world graphs. We also construct a lower bound of the generalization gap that matches our upper bound asymptotically. To achieve these results, we analyze a unified model that includes prior works’ settings (i.e., convolutional and message-passing networks) and new settings (i.e., graph isomorphism networks). Our key idea is to measure the stability of graph neural networks against noise perturbations using Hessians. Empirically, we find that Hessian-based measurements correlate with observed generalization gaps of graph neural networks accurately; Optimizing noise stability properties for fine-tuning pretrained graph neural networks also improves the test performance on several graph-level classification tasks.} }
Endnote
%0 Conference Paper %T Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion %A Haotian Ju %A Dongyue Li %A Aneesh Sharma %A Hongyang R. Zhang %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-ju23a %I PMLR %P 6314--6341 %U https://proceedings.mlr.press/v206/ju23a.html %V 206 %X 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 structures in terms of the maximum degree. In this paper, we present generalization bounds that instead scale with the largest singular value of the graph neural network’s feature diffusion matrix. These bounds are numerically much smaller than prior bounds for real-world graphs. We also construct a lower bound of the generalization gap that matches our upper bound asymptotically. To achieve these results, we analyze a unified model that includes prior works’ settings (i.e., convolutional and message-passing networks) and new settings (i.e., graph isomorphism networks). Our key idea is to measure the stability of graph neural networks against noise perturbations using Hessians. Empirically, we find that Hessian-based measurements correlate with observed generalization gaps of graph neural networks accurately; Optimizing noise stability properties for fine-tuning pretrained graph neural networks also improves the test performance on several graph-level classification tasks.
APA
Ju, H., Li, D., Sharma, A. & Zhang, H.R.. (2023). Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:6314-6341 Available from https://proceedings.mlr.press/v206/ju23a.html.

Related Material