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.

研究了消息传递神经网络（MPNNs）的泛化能力，并给出了具体适用于具有规范化求和和平均聚合的MPNNs的泛化边界。在更现实和具有挑战性的情境下，通过分析简单的随机图、扰动的图标和稀疏图，得出结论表明，只要图形足够大，比训练集的大小复杂，MPNNs仍然可以有效地泛化。

混合图上的消息传递网络的泛化界限