Transferability of Graph Neural Networks using Graphon and Sampling
  Theories
A. Martina Neuman Jason J. Bramburger
Graph neural networks (GNNs) have become powerful tools for processing
graph-based information in various domains. A desirable property of GNNs is
transferability, where a trained network can swap in information from a
different graph without retraining and retain its accuracy. A recent method of
capturing transferability of GNNs is through the use of graphons, which are
symmetric, measurable functions representing the limit of large dense graphs.
In this work, we contribute to the application of graphons to GNNs by
presenting an explicit two-layer graphon neural network (WNN) architecture. We
prove its ability to approximate bandlimited signals within a specified error
tolerance using a minimal number of network weights. We then leverage this
result, to establish the transferability of an explicit two-layer GNN over all
sufficiently large graphs in a sequence converging to a graphon. Our work
addresses transferability between both deterministic weighted graphs and simple
random graphs and overcomes issues related to the curse of dimensionality that
arise in other GNN results. The proposed WNN and GNN architectures offer
practical solutions for handling graph data of varying sizes while maintaining
performance guarantees without extensive retraining.