Understanding Over-Squashing in Dynamic Graphs

Graph neural networks (GNNs) have demonstrated significant success in solving real-world problems using both static and dynamic graph data. While static graphs remain constant, dynamic graphs evolve over time, presenting unique challenges that necessitate integrating GNN computations with sequential models. Despite advancements, existing research has primarily focused on static graphs, with dynamic graphs receiving comparatively less attention. This study extends the investigation of over-squashing—a phenomenon where excessive information compression leads to the loss of distant node information—from static to dynamic graphs. Over-squashing is exacerbated in dynamic graphs due to the combined compression of spatial and temporal information into narrow time windows. To address this issue, we propose the spatial and temporal compensation model for dynamic graphs, which is theoretically validated and incorporates two key modules: the structural similarity-based spatial compensation (SSSC) module and the representation and trend similarity-based temporal compensation (RTSTC) module. The former module mitigates spatial information loss by leveraging structural similarities among nodes, while the latter module addresses temporal information loss by integrating historical data and trends. The extensive experiments on real-world dynamic graph datasets demonstrate that our approach achieves state-of-the-art performance. The datasets and source codes are released at:https://github.com/wuchaokai/STCDG/