  We present GNNAutoScale (GAS), a framework for scaling arbitrary
message-passing GNNs to large graphs. GAS prunes entire sub-trees of the
computation graph by utilizing historical embeddings from prior training
iterations, leading to constant GPU memory consumption in respect to input node
size without dropping any data. While existing solutions weaken the expressive
power of message passing due to sub-sampling of edges or non-trainable
propagations, our approach is provably able to maintain the expressive power of
the original GNN. We achieve this by providing approximation error bounds of
historical embeddings and show how to tighten them in practice. Empirically, we
show that the practical realization of our framework, PyGAS, an easy-to-use
extension for PyTorch Geometric, is both fast and memory-efficient, learns
expressive node representations, closely resembles the performance of their
non-scaling counterparts, and reaches state-of-the-art performance on
large-scale graphs.
