A Local Graph Limits Perspective on Sampling-Based GNNs
Yeganeh Alimohammadi Luana Ruiz Amin Saberi
We propose a theoretical framework for training Graph Neural Networks (GNNs)
on large input graphs via training on small, fixed-size sampled subgraphs. This
framework is applicable to a wide range of models, including popular
sampling-based GNNs, such as GraphSAGE and FastGCN. Leveraging the theory of
graph local limits, we prove that, under mild assumptions, parameters learned
from training sampling-based GNNs on small samples of a large input graph are
within an $\epsilon$-neighborhood of the outcome of training the same
architecture on the whole graph. We derive bounds on the number of samples, the
size of the graph, and the training steps required as a function of $\epsilon$.
Our results give a novel theoretical understanding for using sampling in
training GNNs. They also suggest that by training GNNs on small samples of the
input graph, practitioners can identify and select the best models,
hyperparameters, and sampling algorithms more efficiently. We empirically
illustrate our results on a node classification task on large citation graphs,
observing that sampling-based GNNs trained on local subgraphs 12$\times$
smaller than the original graph achieve comparable performance to those trained
on the input graph.