Generalization Bounds for Message Passing Networks on Mixture of Graphons
This work addresses generalization issues for graph neural networks in practical scenarios, but it is incremental as it extends prior results to more realistic conditions.
The paper tackles the problem of generalization in Message Passing Neural Networks (MPNNs) by deriving bounds for normalized sum and mean aggregation in a realistic setting with perturbed graphons and sparse graphs, showing that generalization improves as graph size increases.
We study the generalization capabilities of Message Passing Neural Networks (MPNNs), a prevalent class of Graph Neural Networks (GNN). We derive generalization bounds specifically for MPNNs with normalized sum aggregation and mean aggregation. Our analysis is based on a data generation model incorporating a finite set of template graphons. Each graph within this framework is generated by sampling from one of the graphons with a certain degree of perturbation. In particular, we extend previous MPNN generalization results to a more realistic setting, which includes the following modifications: 1) we analyze simple random graphs with Bernoulli-distributed edges instead of weighted graphs; 2) we sample both graphs and graph signals from perturbed graphons instead of clean graphons; and 3) we analyze sparse graphs instead of dense graphs. In this more realistic and challenging scenario, we provide a generalization bound that decreases as the average number of nodes in the graphs increases. Our results imply that MPNNs with higher complexity than the size of the training set can still generalize effectively, as long as the graphs are sufficiently large.