# Graph coarsening: From scientific computing to machine learning

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 135 references that are in the map.
- First posted on arXiv 22 Jun 2021.

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

- [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)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Learning Convolutional Neural Networks for Graphs](https://mlsanity.com/paper/1605.05273/) (2016)
- [Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs](https://mlsanity.com/paper/1704.02901/) (2017)
- [Deep Convolutional Networks on Graph-Structured Data](https://mlsanity.com/paper/1506.05163/) (2015)
- [Graph Embedding Techniques, Applications, and Performance: A Survey](https://mlsanity.com/paper/1705.02801/) (2017)
- [Understanding Attention and Generalization in Graph Neural Networks](https://mlsanity.com/paper/1905.02850/) (2019)
- [Towards Sparse Hierarchical Graph Classifiers](https://mlsanity.com/paper/1811.01287/) (2018)
- [HARP: Hierarchical Representation Learning for Networks](https://mlsanity.com/paper/1706.07845/) (2017)
- [GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding](https://mlsanity.com/paper/1910.02370/) (2019)
- [Graph Coarsening with Preserved Spectral Properties](https://mlsanity.com/paper/1802.04447/) (2018)
- [A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening](https://mlsanity.com/paper/1902.09702/) (2019)
- [MILE: A Multi-Level Framework for Scalable Graph Embedding](https://mlsanity.com/paper/1802.09612/) (2018)
- [A Multiscale Pyramid Transform for Graph Signals](https://mlsanity.com/paper/1308.4942/) (2013)
- [Faster Graph Embeddings via Coarsening](https://mlsanity.com/paper/2007.02817/) (2020)

## Built on by (most cited first, 21 of 21)

- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks](https://mlsanity.com/paper/2207.07888/) (2022)
- [Data-centric Graph Learning: A Survey](https://mlsanity.com/paper/2310.04987/) (2023)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [Hierarchical Implicit Neural Emulators](https://mlsanity.com/paper/2506.04528/) (2025)
- [A Unified Framework for Optimization-Based Graph Coarsening](https://mlsanity.com/paper/2210.00437/) (2022)
- [A Survey on Graph Condensation](https://mlsanity.com/paper/2402.02000/) (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)
- [Representing Molecules as Random Walks Over Interpretable Grammars](https://mlsanity.com/paper/2403.08147/) (2024)
- [HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering](https://mlsanity.com/paper/2210.14813/) (2022)
- [A Comprehensive Survey on Graph Summarization with Graph Neural Networks](https://mlsanity.com/paper/2302.06114/) (2023)
- [Taxonomy of reduction matrices for Graph Coarsening](https://mlsanity.com/paper/2506.11743/) (2025)
- [Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral information](https://mlsanity.com/paper/2201.05923/) (2022)
- [Efficient Large-Scale Urban Parking Prediction: Graph Coarsening Based on Real-Time Parking Service Capability](https://mlsanity.com/paper/2410.04022/) (2024)
- [Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening](https://mlsanity.com/paper/2505.14033/) (2025)
- [GBGC: Efficient and Adaptive Graph Coarsening via Granular-ball Computing](https://mlsanity.com/paper/2506.19224/) (2025)
- [PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms](https://mlsanity.com/paper/2412.13592/) (2024)
- [Scalable Graph Attention-based Instance Selection via Mini-Batch Sampling and Hierarchical Hashing](https://mlsanity.com/paper/2502.20293/) (2025)
- [Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement](https://mlsanity.com/paper/2607.21885/) (2026)
- [Train Small, Deploy Large: Zero-Shot GNN Transfer Through Geometric Renormalization](https://mlsanity.com/paper/2607.27767/) (2026)

## Abstract (arXiv)

The general method of graph coarsening or graph reduction has been a remarkably useful and ubiquitous tool in scientific computing and it is now just starting to have a similar impact in machine learning. The goal of this paper is to take a broad look into coarsening techniques that have been successfully deployed in scientific computing and see how similar principles are finding their way in more recent applications related to machine learning. In scientific computing, coarsening plays a central role in algebraic multigrid methods as well as the related class of multilevel incomplete LU factorizations. In machine learning, graph coarsening goes under various names, e.g., graph downsampling or graph reduction. Its goal in most cases is to replace some original graph by one which has fewer nodes, but whose structure and characteristics are similar to those of the original graph. As will be seen, a common strategy in these methods is to rely on spectral properties to define the coarse graph.