Generalization Error of Graph Neural Networks in the Mean-field Regime
This work addresses a theoretical bottleneck for researchers in graph machine learning, offering incremental improvements in understanding generalization in over-parameterized regimes.
The paper tackles the problem of uninformative generalization error bounds for over-parameterized graph neural networks by deriving upper bounds with a convergence rate of O(1/n) in the mean-field regime, providing theoretical assurance for performance on unseen data.
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 over-parametrized 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 over-parameterized regime and overall contribute to our understanding of their performance.