# Graph Coarsening with Message-Passing Guarantees

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

## 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 (most cited first, 30 of 33)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [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)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [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)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba](https://mlsanity.com/paper/1803.02349/) (2018)
- [Condensing Graphs via One-Step Gradient Matching](https://mlsanity.com/paper/2206.07746/) (2022)
- [Scaling Up Graph Neural Networks Via Graph Coarsening](https://mlsanity.com/paper/2106.05150/) (2021)
- [Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data](https://mlsanity.com/paper/2306.02664/) (2023)
- [Understanding Pooling in Graph Neural Networks](https://mlsanity.com/paper/2110.05292/) (2021)
- [Spectrally approximating large graphs with smaller graphs](https://mlsanity.com/paper/1802.07510/) (2018)
- [Graph Coarsening with Neural Networks](https://mlsanity.com/paper/2102.01350/) (2021)
- [Graph Coarsening with Preserved Spectral Properties](https://mlsanity.com/paper/1802.04447/) (2018)
- [The expressive power of pooling in Graph Neural Networks](https://mlsanity.com/paper/2304.01575/) (2023)
- [A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening](https://mlsanity.com/paper/1902.09702/) (2019)
- [Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time](https://mlsanity.com/paper/1508.03261/) (2015)
- [A Survey and Taxonomy of Graph Sampling](https://mlsanity.com/paper/1308.5865/) (2013)
- [Influence-Based Mini-Batching for Graph Neural Networks](https://mlsanity.com/paper/2212.09083/) (2022)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates](https://mlsanity.com/paper/1506.04838/) (2015)

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

- [Taxonomy of reduction matrices for Graph Coarsening](https://mlsanity.com/paper/2506.11743/) (2025)
- [FIT-GNN: Faster Inference Time for GNNs that 'FIT' in Memory Using Coarsening](https://mlsanity.com/paper/2410.15001/) (2024)
- [Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle](https://mlsanity.com/paper/2605.13021/) (2026)
- [Adaptive Graph Coarsening for Efficient GNN Training](https://mlsanity.com/paper/2509.25706/) (2025)
- [Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms](https://mlsanity.com/paper/2601.22943/) (2026)
- [Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement](https://mlsanity.com/paper/2607.21885/) (2026)
- [Does Graph Compression Preserve Signal Propagation?](https://mlsanity.com/paper/2607.23338/) (2026)
- [Train Small, Deploy Large: Zero-Shot GNN Transfer Through Geometric Renormalization](https://mlsanity.com/paper/2607.27767/) (2026)
- [CoRe-GNN: Multilevel Message passing on Coarsened graphs](https://mlsanity.com/paper/2608.02128/) (2026)

## 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.