Over-squashing in Spatiotemporal Graph Neural Networks

• URL: http://arxiv.org/abs/2506.15507v1
• Date: Wed, 18 Jun 2025 14:45:06 GMT
• Title: Over-squashing in Spatiotemporal Graph Neural Networks
• Authors: Ivan Marisca, Jacob Bamberger, Cesare Alippi, Michael M. Bronstein,
• Abstract summary: Graph Neural Networks (GNNs) have achieved remarkable success across various domains.<n>Recent theoretical advances have identified fundamental limitations in their information propagation, such as over-squashing, where distant nodes fail to effectively exchange information.<n>We show that temporaltemporal GNNs favor information propagation from points temporally distant rather than close in time.<n>We prove that architectures that follow either time-and-space or time-then-space processing paradigms are equally affected by this phenomenon.
• Score: 36.45742156049148
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) have achieved remarkable success across various domains. However, recent theoretical advances have identified fundamental limitations in their information propagation capabilities, such as over-squashing, where distant nodes fail to effectively exchange information. While extensively studied in static contexts, this issue remains unexplored in Spatiotemporal GNNs (STGNNs), which process sequences associated with graph nodes. Nonetheless, the temporal dimension amplifies this challenge by increasing the information that must be propagated. In this work, we formalize the spatiotemporal over-squashing problem and demonstrate its distinct characteristics compared to the static case. Our analysis reveals that counterintuitively, convolutional STGNNs favor information propagation from points temporally distant rather than close in time. Moreover, we prove that architectures that follow either time-and-space or time-then-space processing paradigms are equally affected by this phenomenon, providing theoretical justification for computationally efficient implementations. We validate our findings on synthetic and real-world datasets, providing deeper insights into their operational dynamics and principled guidance for more effective designs.

Related papers

• Mind the truncation gap: challenges of learning on dynamic graphs with recurrent architectures [10.434476078553786]
  Continuous-time dynamic graphs (CTDGs) pose challenges for machine learning (ML) approaches.<n>We show that a short truncation of backpropagation-through-time (BPTT) can limit the learning of dependencies beyond a single hop.<n>We argue that understanding and addressing this gap is essential as the importance of CTDGs grows.
  arXiv  Detail & Related papers  (2024-12-30T16:07:41Z)
• Conservation-informed Graph Learning for Spatiotemporal Dynamics Prediction [84.26340606752763]
  In this paper, we introduce the conservation-informed GNN (CiGNN), an end-to-end explainable learning framework.<n>The network is designed to conform to the general symmetry conservation law via symmetry where conservative and non-conservative information passes over a multiscale space by a latent temporal marching strategy.<n>Results demonstrate that CiGNN exhibits remarkable baseline accuracy and generalizability, and is readily applicable to learning for prediction of varioustemporal dynamics.
  arXiv  Detail & Related papers  (2024-12-30T13:55:59Z)
• DyExplainer: Explainable Dynamic Graph Neural Networks [37.16783248212211]
  We present DyExplainer, a novel approach to explaining dynamic Graph Neural Networks (GNNs) on the fly. DyExplainer trains a dynamic GNN backbone to extract representations of the graph at each snapshot. We also augment our approach with contrastive learning techniques to provide priori-guided regularization.
  arXiv  Detail & Related papers  (2023-10-25T05:26:33Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  Temporal graphs exhibit dynamic interactions between nodes over continuous time. We propose a novel method of temporal graph convolution with the whole neighborhood. Our proposed TAP-GNN outperforms existing temporal graph methods by a large margin in terms of both predictive performance and online inference latency.
  arXiv  Detail & Related papers  (2023-04-15T08:17:18Z)
• Uncovering the Missing Pattern: Unified Framework Towards Trajectory Imputation and Prediction [60.60223171143206]
  Trajectory prediction is a crucial undertaking in understanding entity movement or human behavior from observed sequences. Current methods often assume that the observed sequences are complete while ignoring the potential for missing values. This paper presents a unified framework, the Graph-based Conditional Variational Recurrent Neural Network (GC-VRNN), which can perform trajectory imputation and prediction simultaneously.
  arXiv  Detail & Related papers  (2023-03-28T14:27:27Z)
• Space-Time Graph Neural Networks with Stochastic Graph Perturbations [100.31591011966603]
  Space-time graph neural networks (ST-GNNs) learn efficient graph representations of time-varying data. In this paper we revisit the properties of ST-GNNs and prove that they are stable to graph stabilitys. Our analysis suggests that ST-GNNs are suitable for transfer learning on time-varying graphs.
  arXiv  Detail & Related papers  (2022-10-28T16:59:51Z)
• STGIN: A Spatial Temporal Graph-Informer Network for Long Sequence Traffic Speed Forecasting [8.596556653895028]
  This study proposes a new spatial-temporal neural network architecture to handle the long-term traffic parameters forecasting issue. The attention mechanism potentially guarantees long-term prediction performance without significant information loss from distant inputs.
  arXiv  Detail & Related papers  (2022-10-01T05:58:22Z)
• Backpropagation with Biologically Plausible Spatio-Temporal Adjustment For Training Deep Spiking Neural Networks [5.484391472233163]
  The success of deep learning is inseparable from backpropagation. We propose a biological plausible spatial adjustment, which rethinks the relationship between membrane potential and spikes. Secondly, we propose a biologically plausible temporal adjustment making the error propagate across the spikes in the temporal dimension.
  arXiv  Detail & Related papers  (2021-10-17T15:55:51Z)
• Space-Time Graph Neural Networks [104.55175325870195]
  We introduce space-time graph neural network (ST-GNN) to jointly process the underlying space-time topology of time-varying network data. Our analysis shows that small variations in the network topology and time evolution of a system does not significantly affect the performance of ST-GNNs.
  arXiv  Detail & Related papers  (2021-10-06T16:08:44Z)
• Constructing Geographic and Long-term Temporal Graph for Traffic Forecasting [88.5550074808201]
  We propose Geographic and Long term Temporal Graph Convolutional Recurrent Neural Network (GLT-GCRNN) for traffic forecasting. In this work, we propose a novel framework for traffic forecasting that learns the rich interactions between roads sharing similar geographic or longterm temporal patterns.
  arXiv  Detail & Related papers  (2020-04-23T03:50:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.