Logo image
Back
Spectral Gap-Driven Coarsening for Dynamic Graph Neural Networks
Conference proceeding   Open access

Spectral Gap-Driven Coarsening for Dynamic Graph Neural Networks

Hieu Vu, Rares-Mihail Neagu and Bijaya Adhikari
Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2, pp.4718-4729
ACM Conferences
KDD '26: The 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining
08/08/2026
DOI: 10.1145/3770855.3818105
Appears in  UI Libraries Support Open Access
url
https://doi.org/10.1145/3770855.3818105View
Published (Version of record) Open Access

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.
 dynamic graphs graph coarsening graph neural networks UIOWA OA Agreement

Details

Metrics

1 Record Views
Logo image