A Graphop Analysis of Graph Neural Networks on Sparse Graphs: Generalization and Universal Approximation

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 equicontinuous. 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 equicontinuous. 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.

Graphs are mathematical objects that represent various networks, ranging from social networks, to molecules. Graph neural networks (GNNs) are a powerful class of machine learning models, designed to learn from such data. While most of the existing literature is focused on the study of dense graphs (graphs in which each node is connected to most of the other nodes in the graph), or sparse graphs with bounded size, real world data is often represented by huge networks that are sparse. For example, in social networks, most users follow only a small fraction of other users in the network. In this work, we present a unified framework for all graphs, both sparse and dense, of all sizes - and study various properties of GNNs from a theoretical perspective. We prove a generalization bound, guaranteeing that a GNN performing well on training data will also perform well on unseen data. We also establish universal approximation capabilities, showing that GNNs can represent a broad class of functions on graphs. Together, these results provide a stronger and more complete theoretical foundation for GNNs operating on all kinds of large, sparse networks encountered in practice.