Learning by Transference: Training Graph Neural Networks on Growing Graphs
This addresses scalability limitations for researchers and practitioners using GNNs on large networks, but it is incremental as it builds on existing graphon theory and gradient descent methods.
The paper tackles the high computational cost of training graph neural networks (GNNs) on large-scale graphs by proposing a method to train GNNs on growing graphs, inspired by graphon neural networks (WNNs). It shows that this approach retains comparable performance to training on full large graphs at reduced computational cost, as benchmarked on a decentralized control problem.
Graph neural networks (GNNs) use graph convolutions to exploit network invariances and learn meaningful feature representations from network data. However, on large-scale graphs convolutions incur in high computational cost, leading to scalability limitations. Leveraging the graphon -- the limit object of a graph -- in this paper we consider the problem of learning a graphon neural network (WNN) -- the limit object of a GNN -- by training GNNs on graphs sampled from the graphon. Under smoothness conditions, we show that: (i) the expected distance between the learning steps on the GNN and on the WNN decreases asymptotically with the size of the graph, and (ii) when training on a sequence of growing graphs, gradient descent follows the learning direction of the WNN. Inspired by these results, we propose a novel algorithm to learn GNNs on large-scale graphs that, starting from a moderate number of nodes, successively increases the size of the graph during training. This algorithm is further benchmarked on a decentralized control problem, where it retains comparable performance to its large-scale counterpart at a reduced computational cost.