Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training
Open Access
- 13 May 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1502-1510
Abstract
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.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Condensing Graphs via One-Step Gradient Matching2022
- Soft-Label Dataset Distillation and Text Dataset Distillation2021
- DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs2020
- CayleyNets: Graph Convolutional Neural Networks With Complex Rational Spectral FiltersIEEE Transactions on Signal Processing, 2018
- Graph Summarization Methods and ApplicationsACM Computing Surveys, 2018
- Vertex Sparsifiers: New Results from Old TechniquesSIAM Journal on Computing, 2014
- Motif simplification2013
- Herding dynamical weights to learn2009
- Collective Classification in Network DataAI Magazine, 2008
- A Fast Multi-Scale Method for Drawing Large GraphsJournal of Graph Algorithms and Applications, 2002