A Graphop Analysis of Graph Neural Networks on Sparse Graphs: Generalization and Universal Approximation
This addresses a theoretical gap in graph neural network analysis for researchers, providing a unified framework that improves upon existing bounds, though it appears incremental as it extends prior graph limit theory.
The paper tackles the problem of analyzing generalization and approximation capabilities of message passing graph neural networks (MPNNs) on graphs of all sizes, both sparse and dense, by defining a compact metric space under which MPNNs are Hölder continuous, leading to more powerful universal approximation theorems and generalization bounds than previous works.
Generalization and approximation capabilities of message passing graph neural networks (MPNNs) are often studied by defining a compact metric on a space of input graphs under which MPNNs are Hölder continuous. Such analyses are of two varieties: 1) when the metric space includes graphs of unbounded sizes, the theory is only appropriate for dense graphs, and, 2) when studying sparse graphs, the metric space only includes graphs of uniformly bounded size. In this work, we present a unified approach, defining a compact metric on the space of graphs of all sizes, both sparse and dense, under which MPNNs are Hölder continuous. This leads to more powerful universal approximation theorems and generalization bounds than previous works. The theory is based on, and extends, a recent approach to graph limit theory called graphop analysis.