# CoRe-GNN: Multilevel Message passing on Coarsened graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 38 references that are in the map.
- First posted on arXiv 3 Aug 2026.

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

- [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)
- [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)
- [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)
- [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)
- [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)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Condensing Graphs via One-Step Gradient Matching](https://mlsanity.com/paper/2206.07746/) (2022)
- [Decoupling the Depth and Scope of Graph Neural Networks](https://mlsanity.com/paper/2201.07858/) (2022)
- [Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification](https://mlsanity.com/paper/2406.08993/) (2024)
- [VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization](https://mlsanity.com/paper/2110.14363/) (2021)
- [Hierarchical Message-Passing Graph Neural Networks](https://mlsanity.com/paper/2009.03717/) (2020)
- [Towards Quantifying Long-Range Interactions in Graph Machine Learning: a Large Graph Dataset and a Measurement](https://mlsanity.com/paper/2503.09008/) (2025)
- [Influence-Based Mini-Batching for Graph Neural Networks](https://mlsanity.com/paper/2212.09083/) (2022)
- [Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training](https://mlsanity.com/paper/2312.15520/) (2023)
- [Graph Coarsening with Message-Passing Guarantees](https://mlsanity.com/paper/2405.18127/) (2024)
- [Learning on Large Graphs using Intersecting Communities](https://mlsanity.com/paper/2405.20724/) (2024)
- [Next Level Message-Passing with Hierarchical Support Graphs](https://mlsanity.com/paper/2406.15852/) (2024)
- [Taxonomy of reduction matrices for Graph Coarsening](https://mlsanity.com/paper/2506.11743/) (2025)
- [Efficient Learning on Large Graphs using a Densifying Regularity Lemma](https://mlsanity.com/paper/2504.18273/) (2025)
- [Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening](https://mlsanity.com/paper/2505.14033/) (2025)
- [FIT-GNN: Faster Inference Time for GNNs that 'FIT' in Memory Using Coarsening](https://mlsanity.com/paper/2410.15001/) (2024)

## Abstract (arXiv)

Training Graph Neural Networks on large graphs is challenged by the memory cost of storing all node representations across layers. We show that several existing scalable approaches can be written as structured modifications of the GNN propagation matrix, providing a unified perspective that exposes their respective limitations. In particular, graph coarsening replaces it by a low-rank approximation that enables spectral guarantees but assigns uniform representations to clustered nodes, while Cluster-GCN restricts the propagation matrix to intra-cluster connections that allow efficient batching but sever long-range information. These are complementary failures of the same decomposition of the graph into groups of nodes. To obtain the best of both worlds, we propose CoRe-GNN, which performs both propagations in parallel at each layer: a coarsened inter-cluster term capturing long-range structure, and a local intra-cluster term preserving per-node discriminability. We prove that CoRe-GNN inherits analogous approximation guarantees to those of graph coarsening, and introduce a natural cluster-based batching scheme that scales to graphs with millions of nodes. On node classification benchmarks spanning homophilic, heterophilic, large-scale, and long-range graphs, CoRe-GNN outperforms both graph coarsening and Cluster-GCN baselines. Notably, CoRe-GNN reaches competitive accuracy on long-range tasks, while remaining memory-efficient through batching.