Aug 2026· Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2· 0 citations· 14 references
TL;DR
Experimental results demonstrate that the coarsening technique significantly accelerates dynamic GNN training and inference without compromising predictive performance, offering a practical path toward scalable dynamic graph learning.
Abstract
Dynamic Graph Neural Networks (DGNNs) suffer from a significant scalability bottleneck due to high computational demands resulting from their innate design to aggregate information both over graph topology and over time. While graph coarsening has successfully mitigated these costs for static graph neural networks, its potential remains largely untapped in the dynamic setting. Bridging this gap is particularly challenging because different DGNN architectures in literature aggregate information across structural topologies and temporal dimensions in different manners. %Hence, we require a coarsening method that can adapt to the complexity of a system evolving over time in different manners. In this work, we first group popular DGNNs into two general categories based on their topological and temporal message passing patterns. We then derive appropriate coarsening criteria for both classes of DGNNs with a goal to maximize the connectivity in the coarsened graph. Specifically, we aim to maximize the spectral gap of a generalized combinatorial Laplacian matrix in each case. In order to determine the quality of the candidate node-pairs to merge in an efficient manner, we derive an estimated change in eigenvalues from first principles using the Matrix Perturbation Theory. This leads to a naturally efficient algorithm Spectral-gap Aware Coarsening of Dynamic networks (SACoD). Experimental results demonstrate that our coarsening technique significantly accelerates dynamic GNN training and inference without compromising predictive performance, offering a practical path toward scalable dynamic graph learning.
This work introduces a novel method Schreier-Coset Graph Rewiring, a group-theoretic rewiring method that augments the input graph with a Schreier-Coset graph derived from a special linear group, creating a low-resistance bypass for long-range communication.
Aryan Mishra, Randy Martinez, Lizhen Lin· 0 citations
CoRe-GNN is proposed, 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.
Antonin Joly, Nicolas Keriven, Aline Roumy· 0 citations
Graph Neural Networks (GNNs) are popular deep learning models designed to process graph-structured data through recursive neighborhood aggregations in the message passing process. When applied to semi-supervised node classification, the message-passing enables GNNs to understand short-range spatial interactions, but also causes them to suffer from over-smoothing and over-squashing. These challenges hinder model expressiveness and prevent the use of deeper models to capture long-range node interactions (LRIs) within the graph. Popular solutions for LRIs detection are either too expensive to process large graphs due to high time complexity or fail to generalize across diverse graph structures. To address these limitations, we propose a mechanism called information flow control, which leverages a novel connectivity measure, called information flow score, to address over-smoothing and over-squashing with linear computational overhead, supported by theoretical evidence. Building on this mechanism, we introduce DeltaGNN, to the best of our knowledge among the first scalable (featuring linear computational and memory complexity overhead) and generalizable (capable of effectively handling graphs with diverse homophily, density, and topology) architectures for long-range and short-range interaction detection. We benchmark our model across 10 real-world datasets, including graphs with varying sizes, topologies, densities, and homophilic ratios, showing superior performance with limited computational complexity.
Kevin Mancini, Islem Rekik· IEEE Transactions on Pattern...· 2 citations
The proposed method, TRicci, extends classical Forman-Ricci curvature to directed weighted temporal graphs by capturing structural support, temporal recency, and local interaction competition and suggests that temporal curvature can serve as a principled basis for scalable temporal graph learning by preserving predictive temporal-structural information under substantial sparsification.
Poupak Azad, C. Akcora, Kiarash Shamsi· 0 citations
This work proposes $\partial$lift (DiffLift), a general framework for learning graph liftings to hypergraphs and cellular- and simplicial complexes in an end-to-end fashion and shows that $\partial$lift outperforms existing lifting methods on multiple benchmarks for graph and node classification across different TNN architectures.
J. L. Franco, Gabriel Duarte, Alexander Nikitin et al.· 2 citations
Graph neural networks (GNNs) have emerged as a powerful framework for learning from graph-structured data. However, their efficient training remains challenging, particularly in distributed computing environments. This challenge arises from the use of message passing, which couples all graph nodes, leading to expensive optimization steps, high memory requirements, and substantial communication overhead. To alleviate these limitations, we propose a novel domain-decomposition (DD) variant of AG2m, an AdaGrad method enhanced with second-order curvature information and momentum, denoted by DD-AG2m. The proposed DD-AG2m alternates between AG2m optimization on the original (global) graph and AG2m optimization on the partitioned graphs. To incorporate global information at reduced cost, we further introduce a two-level variant (2DD-AG2m) that performs global optimization steps on a coarse graph obtained by randomly subsampling nodes within each subdomain. Numerical experiments spanning graph classification, node-level regression, and spatiotemporal forecasting tasks demonstrate that the proposed DD methods reduce the computational cost required to achieve the same predictive performance by a factor of 4-8. Moreover, for the fixed computational cost, they improve the predictive performance of GNNs by up to 22% compared with the baseline AG2m.
Laurynas Varnas, Julien Herrmann, Alexander Heinlein et al.· 0 citations