Limits, approximation and size transferability for GNNs on sparse graphs
  via graphops
Thien Le Stefanie Jegelka
Can graph neural networks generalize to graphs that are different from the
graphs they were trained on, e.g., in size? In this work, we study this
question from a theoretical perspective. While recent work established such
transferability and approximation results via graph limits, e.g., via graphons,
these only apply non-trivially to dense graphs. To include frequently
encountered sparse graphs such as bounded-degree or power law graphs, we take a
perspective of taking limits of operators derived from graphs, such as the
aggregation operation that makes up GNNs. This leads to the recently introduced
limit notion of graphops (Backhausz and Szegedy, 2022). We demonstrate how the
operator perspective allows us to develop quantitative bounds on the distance
between a finite GNN and its limit on an infinite graph, as well as the
distance between the GNN on graphs of different sizes that share structural
properties, under a regularity assumption verified for various graph sequences.
Our results hold for dense and sparse graphs, and various notions of graph
limits.