8th International Conference on
Computational Harmonic Analysis

September 12-16, 2022

Ingolstadt, Germany

"Stability and Generalization Capabilities of Message Passing Graph Neural Networks"

Maskey, Sohir

Message Passing Neural Networks (MPNNs) are considered state-of-the-art tools for solving a large variety of graph-focused problems. We study the generalization capabilities of MPNNs in graph classification. We assume that graphs of different classes are sampled from different random graph models. Based on this data distribution, we derive a non-asymptotic bound on the generalization gap, that decreases to zero as the graphs become larger. This is proven by showing that a MPNN, applied on a graph, approximates the MPNN applied on the geometric model that the graph discretizes.

« back