Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphs
This work addresses a foundational theoretical gap for researchers in graph machine learning by extending convergence guarantees to widely used MPGNN architectures, though it is incremental as it builds on prior results for specific cases.
The paper tackles the problem of proving convergence of message passing graph neural networks (MPGNNs) with generic aggregation functions to their continuous counterparts on large random graphs, extending previous results limited to normalized means. It provides non-asymptotic bounds with high probability for a broad class of aggregation functions, including attention-based and max convolutional methods, with separate treatment for coordinate-wise maximum aggregation yielding a different convergence rate.
We study the convergence of message passing graph neural networks on random graph models to their continuous counterpart as the number of nodes tends to infinity. Until now, this convergence was only known for architectures with aggregation functions in the form of normalized means, or, equivalently, of an application of classical operators like the adjacency matrix or the graph Laplacian. We extend such results to a large class of aggregation functions, that encompasses all classically used message passing graph neural networks, such as attention-based message passing, max convolutional message passing, (degree-normalized) convolutional message passing, or moment-based aggregation message passing. Under mild assumptions, we give non-asymptotic bounds with high probability to quantify this convergence. Our main result is based on the McDiarmid inequality. Interestingly, this result does not apply to the case where the aggregation is a coordinate-wise maximum. We treat this case separately and obtain a different convergence rate.