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: <uri xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">https://github.com/wuchaokai/STCDG/</uri>