Generalization Bounds for Message Passing Networks on Mixture of Graphons

arXiv:2404.03473v1 Announce Type: new
Abstract: 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 …

abstract aggregation analysis arxiv capabilities class cs.lg data gnn graph graph neural networks mean networks neural networks study type