Graph and graphon neural network stability
  Graph neural networks (GNNs) are learning architectures that rely on
knowledge of the graph structure to generate meaningful representations of
large-scale network data. GNN stability is thus important as in real-world
scenarios there are typically uncertainties associated with the graph. We
analyze GNN stability using kernel objects called graphons. Graphons are both
limits of convergent graph sequences and generating models for deterministic
and stochastic graphs. Building upon the theory of graphon signal processing,
we define graphon neural networks and analyze their stability to graphon
perturbations. We then extend this analysis by interpreting the graphon neural
network as a generating model for GNNs on deterministic and stochastic graphs
instantiated from the original and perturbed graphons. We observe that GNNs are
stable to graphon perturbations with a stability bound that decreases
asymptotically with the size of the graph. This asymptotic behavior is further
demonstrated in an experiment of movie recommendation.
