cs.LGAug 3, 2026

CoRe-GNN: Multilevel Message passing on Coarsened graphs

Authors: Antonin Joly, Nicolas Keriven, Aline Roumy

Organizations: CNRS, IRISA, Rennes, FRANCE · INRIA, Rennes, FRANCE

Abstract

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 \emph{same} decomposition of the graph into groups of nodes. To obtain the best of both worlds, we propose \textbf{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 \emph{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 \emph{long-range} tasks, while remaining memory-efficient through batching.

Explore similar work

CardsList
May 13, 2026cs.LG

Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle

Graph coarsening is a graph dimensionality reduction technique that aims to construct a smaller and more tractable graph while preserving the essential structural and semantic properties of the original graph. However, most existing methods rely on pair-wise similarity matching, where each node independently searches for its best partner based on global information. This selfishness matching paradigm incurs substantial computational and memory overhead. To address this problem, we shift to a non-selfishness principle that prioritizes the collective interference of neighborhood in coarsening, and propose an efficient method named NOPE, which achieves linear memory consumption and near-linear computational complexity in the number of nodes. Furthermore, we derive a faster variant NOPE*, which reduces O(δ\dot d) interference evaluation to O(d) based on the local isotropy assumption, and consequently alleviates the computational bottleneck for high-degree nodes. Experimental results show that NOPE* achieves 1.8-10\times speedup over NOPE and surpass almost all baselines with 1-3 orders of magnitude acceleration. Meanwhile, learning on coarsened graphs yields comparable performance to original graphs, and can even show superior performance over LLM-based graph reasoning owing to compact graph information. The code can be available at https://github.com/dazonglian/NOPE-main.
Xu Bai, Bin Lu, Kun Zhang +4
Graph LearningCoarse-To-FineSemantic Similarity MetricsPrinciplesComputable
AskPDF
Jul 24, 2026cs.LG

Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement

Coarsening-based training for graph neural networks (GNNs), i.e.\ training on coarsened graphs rather than the original large ones, has become a promising direction for scaling GNNs to massive graphs. However, prior work has been evaluated almost exclusively on \textit{homophilic} graphs, leaving the more challenging \textit{heterophilic} settings underexplored. We show, both empirically and theoretically, that existing coarsening-based training methods suffer significant performance degradation on heterophilic graphs due to inevitable loss of graph information during coarsening. To address this, we propose {\bf A}daptive {\bf C}omplementary {\bf E}nhancement, a plug-and-play, model-agnostic strategy that reintegrates the information discarded in coarsening: ACE learns a projector for re-constructing original node features and applies \textit{anisotropic structural regularization} to embed local heterophily. We further adopt \textit{homoscedastic uncertainty weighting} to adaptively balance the combined training objective of primary coarsened-graph training loss and full-graph auxiliary loss with augmented node features re-constructed by the heterophily-aware projector. Extensive experiments show that ACE drives consistent gains on heterophilic benchmarks while preserving competitive results on homophilic graphs with minimal computational overhead. Code is available at the GitHub repository: https://github.com/vasile-paskardlgm/ACE.
Guoming Li, Jian Yang, Xukun Wang +3
Graph Neural NetworksHeterogeneityCoarse-To-FineLoss FunctionAdaptive Histogram EqualizationRemediation
AskPDF
May 29, 2026cs.LG

On Efficient Scaling of GNNs via IO-Aware Layers Implementations

Graph Neural Networks (GNNs) are bottlenecked by sparse, irregular memory access. Popular frameworks such as DGL and PyTorch Geometric support general message passing, but complex layers often materialize edge-wise intermediates, increasing memory traffic and limiting scalability on large graphs. We take an I/O- and arithmetic-intensity--centric view and show that widely used layers fall into three kernel families: SpMM-based convolutions, reduction-based aggregations, and attention-based layers (GATv2/Graph Transformer). For each family, we develop GPU kernels that reduce data movement, improve locality, and remain robust across realistic graphs. We also study graph reordering and find that its impact depends on the kernel mapping: it benefits neighbor-parallel (gather-dominated) kernels more consistently than feature-parallel designs. Empirically, our fused attention kernels reach up to 3.9×\textbf{3.9}\times speedup for Graph Transformer (median 1.6×\textbf{1.6}\times), with Tensor Core (block-sparse) variants up to 7.3×\textbf{7.3}\times on locally dense graphs; for GATv2 we reach up to 8.5×\textbf{8.5}\times speedup (median 2.0×\textbf{2.0}\times) while reducing peak memory by up to 76×\textbf{76}\times (median 6×\textbf{6}\times). Our degree-aware reduction kernels achieve up to 10×\textbf{10}\times speedup (median 2.6×\textbf{2.6}\times). For SpMM-based layers, properly cached cuSPARSE achieves up to 8×\textbf{8}\times speedup over DGL and outperforms evaluated custom baselines in the majority of evaluations. We release our implementations as drop-in replacements to support reproducible, hardware-aware GNN acceleration.
Daria Fomina, Daniil Krasylnikov, Alexey Boykov +3
Graph Neural NetworksGraphics Processing Unit KernelsTensor ProgramsDynamic Sparse AttentionBatch Normalization
AskPDF