Generalization error of graph neural networks in the mean-field regime

Conference item

This work provides a theoretical framework for assessing the generalization error of graph neural networks in the over-parameterized regime, where the number of parameters surpasses the quantity of data points. We explore two widely utilized types of graph neural networks: graph convolutional neural networks and message passing graph neural networks. Prior to this study, existing bounds on the generalization error in the overparametrized regime were uninformative, limiting our understanding of over-parameterized network performance. Our novel approach involves deriving upper bounds within the mean-field regime for evaluating the generalization error of these graph neural networks. We establish upper bounds with a convergence rate of O(1/n), where n is the number of graph samples. These upper bounds offer a theoretical assurance of the networks’ performance on unseen data in the challenging overparameterized regime and overall contribute to our understanding of their performance.

Authors: Aminian, G; He, Y; Reinert, G; Szpruch, L; Cohen, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Proceedings of Machine Learning Research
• Host title: Proceedings of the 41st International Conference on Machine Learning (ICML 2024)
• Volume: 235
• Pages: 1359-1391
• Publication date: 2024-07-29
• Acceptance date: 2024-05-02
• Event title: 41st International Conference on Machine Learning (ICML 2024)
• Event location: Vienna, Austria
• Event website: https://icml.cc/
• Event start date: 2024-07-21
• Event end date: 2024-07-27
• Language: English