Graph Coarsening via Convolution Matching for Scalable Graph Neural
  Network Training
Charles Dickens Eddie Huang Aishwarya Reganti Jiong Zhu Karthik Subbian Danai Koutra
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.