mlsanityData to 7 Oct 2026

Graph coarsening: From scientific computing to machine learning

arXiv 2106.11863 ↗First posted 22 Jun 2021cs.LG cs.DS cs.NAcited by 21

Not on the map. Why?

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.

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

Builds on

32 of 135 references.

References · 32

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  6. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  7. 2014DeepWalk: Online Learning of Social Representationscited by 1,543
  8. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  9. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
  10. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  11. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 786
  12. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
20 more
  1. 2015LINE: Large-scale Information Network Embeddingcited by 582
  2. 2019Graph U-Netscited by 489
  3. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
  4. 2017Representation Learning on Graphs: Methods and Applicationscited by 456
  5. 2019Self-Attention Graph Poolingcited by 421
  6. 2016Learning Convolutional Neural Networks for Graphscited by 314
  7. 2017Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphscited by 307
  8. 2015Deep Convolutional Networks on Graph-Structured Datacited by 246
  9. 2017Graph Embedding Techniques, Applications, and Performance: A Surveycited by 188
  10. 2019Understanding Attention and Generalization in Graph Neural Networkscited by 169
  11. 2018Towards Sparse Hierarchical Graph Classifierscited by 100
  12. 2017HARP: Hierarchical Representation Learning for Networkscited by 58
  13. 2019GraphZoom: A multi-level spectral approach for accurate and scalable graph embeddingcited by 58
  14. 2018Graph Coarsening with Preserved Spectral Propertiescited by 41
  15. 2019A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarseningcited by 31
  16. 2018MILE: A Multi-Level Framework for Scalable Graph Embeddingcited by 28
  17. 2013A Multiscale Pyramid Transform for Graph Signalscited by 15
  18. 2020Faster Graph Embeddings via Coarseningcited by 15
  19. 2019Unsupervised Learning of Graph Hierarchical Abstractions with Differentiable Coarsening and Optimal Transportcited by 12
  20. 2014Single Pass Spectral Sparsification in Dynamic Streamscited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 3; 2024: 7; 2025: 5; 2026: 2.

21 papers.

Sort:

  1. 2024A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensationcited by 57
  2. 2022SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networkscited by 36
  3. 2023Data-centric Graph Learning: A Surveycited by 22
  4. 2023A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarseningcited by 15
  5. 2022A Unified Framework for Optimization-Based Graph Coarseningcited by 9
  6. 2024A Survey on Graph Condensationcited by 9
  7. 2024Graph Coarsening via Supervised Granular-Ball for Scalable Graph Neural Network Trainingcited by 9
  8. 2025Hierarchical Implicit Neural Emulatorscited by 9
  9. 2024Two Trades is not Baffled: Condensing Graph via Crafting Rational Gradient Matchingcited by 8
  10. 2024Representing Molecules as Random Walks Over Interpretable Grammarscited by 7
  11. 2022HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clusteringcited by 6
  12. 2023A Comprehensive Survey on Graph Summarization with Graph Neural Networkscited by 3
9 more
  1. 2025Taxonomy of reduction matrices for Graph Coarseningcited by 3
  2. 2022Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral informationcited by 2
  3. 2024Efficient Large-Scale Urban Parking Prediction: Graph Coarsening Based on Real-Time Parking Service Capabilitycited by 2
  4. 2025Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarseningcited by 2
  5. 2025GBGC: Efficient and Adaptive Graph Coarsening via Granular-ball Computingcited by 2
  6. 2024PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithmscited by 0
  7. 2025Scalable Graph Attention-based Instance Selection via Mini-Batch Sampling and Hierarchical Hashingcited by 0
  8. 2026Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancementcited by 0
  9. 2026Train Small, Deploy Large: Zero-Shot GNN Transfer Through Geometric Renormalizationcited by 0