Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training
This addresses scalability issues for GNN training in large graphs, offering a complementary preprocessing technique that is incremental in improving efficiency.
The paper tackles the problem of scalable graph neural network (GNN) training by proposing the CONVMATCH algorithm for graph coarsening, which preserves graph convolution output and reduces graph size to 1% while achieving up to 95% of the prediction performance on node classification and up to 2x improvement on link prediction tasks.
Graph summarization as a preprocessing step is an effective and complementary technique for scalable graph neural network (GNN) training. In this work, we propose the Coarsening Via Convolution Matching (CONVMATCH) algorithm and a highly scalable variant, A-CONVMATCH, for creating summarized graphs that preserve the output of graph convolution. We evaluate CONVMATCH on six real-world link prediction and node classification graph datasets, and show it is efficient and preserves prediction performance while significantly reducing the graph size. Notably, CONVMATCH achieves up to 95% of the prediction performance of GNNs on node classification while trained on graphs summarized down to 1% the size of the original graph. Furthermore, on link prediction tasks, CONVMATCH consistently outperforms all baselines, achieving up to a 2x improvement.