Abstract
Message passing neural networks (MPNN) have seen a steep rise in popularitysince their introduction as generalizations of convolutional neural networks tograph-structured data, and are now considered state-of-the-art tools forsolving a large variety of graph-focused problems. We study the generalizationerror of MPNNs in graph classification and regression. We assume that graphs ofdifferent classes are sampled from different random graph models. We show that,when training a MPNN on a dataset sampled from such a distribution, thegeneralization gap increases in the complexity of the MPNN, and decreases, notonly with respect to the number of training samples, but also with the averagenumber of nodes in the graphs. This shows how a MPNN with high complexity cangeneralize from a small dataset of graphs, as long as the graphs are large. Thegeneralization bound is derived from a uniform convergence result, that showsthat any MPNN, applied on a graph, approximates the MPNN applied on thegeometric model that the graph discretizes.