# Scaling Up Graph Neural Networks Via Graph Coarsening

arXiv: https://arxiv.org/abs/2106.05150 · HTML: https://mlsanity.com/paper/2106.05150/

## Key facts

- Cited by 80 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 50 references that are in the map.
- First posted on arXiv 9 Jun 2021.

## Builds on (most cited first, 30 of 35)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Learning Mesh-Based Simulation with Graph Networks](https://mlsanity.com/paper/2010.03409/) (2020)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Towards Deeper Graph Neural Networks](https://mlsanity.com/paper/2007.09296/) (2020)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1911.07323/) (2019)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Interpreting and Unifying Graph Neural Networks with An Optimization Framework](https://mlsanity.com/paper/2101.11859/) (2021)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [Inductive Matrix Completion Based on Graph Neural Networks](https://mlsanity.com/paper/1904.12058/) (2019)
- [GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding](https://mlsanity.com/paper/1910.02370/) (2019)
- [Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks](https://mlsanity.com/paper/2006.13866/) (2020)
- [LambdaNet: Probabilistic Type Inference using Graph Neural Networks](https://mlsanity.com/paper/2005.02161/) (2020)

## Built on by (most cited first, 30 of 80)

- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [Hierarchical Graph Transformer with Adaptive Node Sampling](https://mlsanity.com/paper/2210.03930/) (2022)
- [Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data](https://mlsanity.com/paper/2306.02664/) (2023)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Graph Condensation via Receptive Field Distribution Matching](https://mlsanity.com/paper/2206.13697/) (2022)
- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Does Graph Distillation See Like Vision Dataset Counterpart?](https://mlsanity.com/paper/2310.09192/) (2023)
- [Hyperbolic Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/2202.13852/) (2022)
- [SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks](https://mlsanity.com/paper/2207.07888/) (2022)
- [EIGNN: Efficient Infinite-Depth Graph Neural Networks](https://mlsanity.com/paper/2202.10720/) (2022)
- [Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition](https://mlsanity.com/paper/2405.13707/) (2024)
- [Data-centric Graph Learning: A Survey](https://mlsanity.com/paper/2310.04987/) (2023)
- [SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization](https://mlsanity.com/paper/2207.09179/) (2022)
- [Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks](https://mlsanity.com/paper/2207.08629/) (2022)
- [A Survey on Graph Neural Network Acceleration: Algorithms, Systems, and Customized Hardware](https://mlsanity.com/paper/2306.14052/) (2023)
- [Graph Data Condensation via Self-expressive Graph Structure Reconstruction](https://mlsanity.com/paper/2403.07294/) (2024)
- [Rethinking Node-wise Propagation for Large-scale Graph Learning](https://mlsanity.com/paper/2402.06128/) (2024)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [Towards Data-centric Graph Machine Learning: Review and Outlook](https://mlsanity.com/paper/2309.10979/) (2023)
- [Probabilistic Graph Rewiring via Virtual Nodes](https://mlsanity.com/paper/2405.17311/) (2024)
- [Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity](https://mlsanity.com/paper/2406.15575/) (2024)
- [Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training](https://mlsanity.com/paper/2312.15520/) (2023)
- [A Topology-aware Graph Coarsening Framework for Continual Graph Learning](https://mlsanity.com/paper/2401.03077/) (2024)
- [A Survey on Graph Condensation](https://mlsanity.com/paper/2402.02000/) (2024)
- [Graph Coarsening with Message-Passing Guarantees](https://mlsanity.com/paper/2405.18127/) (2024)
- [Can Modifying Data Address Graph Domain Adaptation?](https://mlsanity.com/paper/2407.19311/) (2024)
- [Graph Coarsening via Supervised Granular-Ball for Scalable Graph Neural Network Training](https://mlsanity.com/paper/2412.13842/) (2024)
- [Two Trades is not Baffled: Condensing Graph via Crafting Rational Gradient Matching](https://mlsanity.com/paper/2402.04924/) (2024)
- [Learning on Large Graphs using Intersecting Communities](https://mlsanity.com/paper/2405.20724/) (2024)

## Abstract (arXiv)

Scalability of graph neural networks remains one of the major challenges in graph machine learning. Since the representation of a node is computed by recursively aggregating and transforming representation vectors of its neighboring nodes from previous layers, the receptive fields grow exponentially, which makes standard stochastic optimization techniques ineffective. Various approaches have been proposed to alleviate this issue, e.g., sampling-based methods and techniques based on pre-computation of graph filters. In this paper, we take a different approach and propose to use graph coarsening for scalable training of GNNs, which is generic, extremely simple and has sublinear memory and time costs during training. We present extensive theoretical analysis on the effect of using coarsening operations and provides useful guidance on the choice of coarsening methods. Interestingly, our theoretical analysis shows that coarsening can also be considered as a type of regularization and may improve the generalization. Finally, empirical results on real world datasets show that, simply applying off-the-shelf coarsening methods, we can reduce the number of nodes by up to a factor of ten without causing a noticeable downgrade in classification accuracy.