Generalization Bounds for Message Passing Networks on Mixture of
  Graphons
Sohir Maskey Gitta Kutyniok Ron Levie
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.