Graph Batch Coarsening framework for scalable graph neural networks

Due to the neighborhood explosion phenomenon, scaling up graph neural networks to large graphs remains a huge challenge. Various sampling-based mini-batch approaches, such as node-wise, layer-wise, and subgraph sampling, have been proposed to alleviate this issue. However, intensive random sampling incurs additional overhead during training and often fails to deliver good performance consistently. To surmount these limitations, we propose Graph Batch Coarsening (GBC), a simple and general graph batching framework designed to facilitate scalable training of arbitrary GNN models. GBC preprocesses the input graph and generates a set of much smaller subgraphs to be used as mini-batches; then any GNN model can be trained only on those small graphs. This framework avoids random sampling completely and makes no extra change on the backbone GNN models including hyperparameters. To implement the framework, we present a graph decomposition method based on label propagation and a novel graph coarsening algorithm designed for training GNN. Empirically, GBC demonstrates superior performance in accuracy, training time and memory usage on various small to large-scale graphs.