mlsanityData to 14 Oct 2026

Graph Coarsening with Message-Passing Guarantees

arXiv 2405.18127 ↗First posted 28 May 2024cs.LG stat.MLcited by 9

Not on the map. Why?

Abstract (arXiv)

Graph coarsening aims to reduce the size of a large graph while preserving some of its key properties, which has been used in many applications to reduce computational load and memory footprint. For instance, in graph machine learning, training Graph Neural Networks (GNNs) on coarsened graphs leads to drastic savings in time and memory. However, GNNs rely on the Message-Passing (MP) paradigm, and classical spectral preservation guarantees for graph coarsening do not directly lead to theoretical guarantees when performing naive message-passing on the coarsened graph. In this work, we propose a new message-passing operation specific to coarsened graphs, which exhibit theoretical guarantees on the preservation of the propagated signal. Interestingly, and in a sharp departure from previous proposals, this operation on coarsened graphs is oriented, even when the original graph is undirected. We conduct node classification tasks on synthetic and real data and observe improved results compared to performing naive message-passing on the coarsened graph.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 33 of its 48 references that are in the map. First posted on arXiv 28 May 2024.

Builds on

33 of 48 references.

References · 33

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Inductive Representation Learning on Large Graphscited by 6,320
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  4. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  5. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  6. 2019Simplifying Graph Convolutional Networkscited by 1,477
  7. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,167
  8. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 993
  9. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 976
  10. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 787
  11. 2019Self-Attention Graph Poolingcited by 421
  12. 2020Graph Neural Networks with Heterophilycited by 202
21 more
  1. 2020Graph Clustering with Graph Neural Networkscited by 163
  2. 2021Graph Condensation for Graph Neural Networkscited by 150
  3. 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
  4. 2018Billion-scale Commodity Embedding for E-commerce Recommendation in Alibabacited by 105
  5. 2022Condensing Graphs via One-Step Gradient Matchingcited by 100
  6. 2021Scaling Up Graph Neural Networks Via Graph Coarseningcited by 80
  7. 2023Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Datacited by 71
  8. 2021Understanding Pooling in Graph Neural Networkscited by 69
  9. 2018Spectrally approximating large graphs with smaller graphscited by 56
  10. 2021Graph Coarsening with Neural Networkscited by 55
  11. 2018Graph Coarsening with Preserved Spectral Propertiescited by 41
  12. 2023The expressive power of pooling in Graph Neural Networkscited by 35
  13. 2019A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarseningcited by 31
  14. 2015Constructing Linear-Sized Spectral Sparsification in Almost-Linear Timecited by 17
  15. 2013A Survey and Taxonomy of Graph Samplingcited by 15
  16. 2022Influence-Based Mini-Batching for Graph Neural Networkscited by 15
  17. 2023A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarseningcited by 15
  18. 2015Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updatescited by 14
  19. 2019Unsupervised Learning of Graph Hierarchical Abstractions with Differentiable Coarsening and Optimal Transportcited by 12
  20. 2023Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Trainingcited by 12
  21. 2019Latent Distance Estimation for Random Geometric Graphscited by 11

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 6.

9 papers.

  1. 2025Taxonomy of reduction matrices for Graph Coarseningcited by 3
  2. 2024FIT-GNN: Faster Inference Time for GNNs that 'FIT' in Memory Using Coarseningcited by 1
  3. 2026Rethinking Efficient Graph Coarsening via a Non-Selfishness Principlecited by 1
  4. 2025Adaptive Graph Coarsening for Efficient GNN Trainingcited by 0
  5. 2026Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithmscited by 0
  6. 2026Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancementcited by 0
  7. 2026Does Graph Compression Preserve Signal Propagation?cited by 0
  8. 2026Train Small, Deploy Large: Zero-Shot GNN Transfer Through Geometric Renormalizationcited by 0
  9. 2026CoRe-GNN: Multilevel Message passing on Coarsened graphscited by 0