Over-squashing in Spatiotemporal Graph Neural Networks

Ivan Marisca, Jacob Bamberger, Cesare Alippi, Michael M. Bronstein

Abstract

This paper formalizes the phenomenon of "spatiotemporal over-squashing" in Spatiotemporal Graph Neural Networks (STGNNs). By extending Jacobian sensitivity analysis to the spatiotemporal domain, the authors reveal that the addition of a temporal dimension creates compounding information bottlenecks. They identify a counterintuitive "temporal sink" effect where standard models favor distant past information over recent events. The study proves that efficient "Time-then-Space" (TTS) architectures are theoretically as robust as computationally intensive "Time-and-Space" (T&S) models and proposes temporal graph rewiring to mitigate these bottlenecks.

Introduction

In standard Graph Neural Networks (GNNs), over-squashing is a known issue where information from an expanding neighborhood is compressed into fixed-size vectors, leading to significant data loss. While well-studied in static graphs, real-world data often evolves over time (e.g., traffic networks, weather grids). STGNNs address this by processing sequences of graphs, requiring information to propagate across both spatial and temporal axes.

Construction of a spatiotemporal graph as a product of spatial and temporal graphs.

Prior to this work, it was unknown how over-squashing manifests in this joint setting. The authors investigate whether the temporal dimension amplifies the spatial bottleneck and how different architectural designs—specifically Time-and-Space (T&S) versus Time-then-Space (TTS)—handle information flow.

Methods: Jacobian Sensitivity Analysis

The authors utilize Jacobian sensitivity analysis to measure how changes in an input (a specific node at a past time step) impact the final output representation. They focus on Message-Passing Temporal Convolutional Networks (MPTCNs) and analyze two dominant paradigms:

  1. Time-and-Space (T&S): Interleaves temporal and spatial processing at every layer.
  2. Time-then-Space (TTS): Processes the entire temporal sequence for each node before applying spatial message passing at the final step.

Key Insights: The Temporal Sink and Multiplicative Bottlenecks

A primary discovery is the "Temporal Sink" effect. Counterintuitively, causal convolutions in STGNNs suffer from temporal over-squashing that inverts typical spatial patterns. Because causal convolutions move forward in time, earlier time steps accumulate influence through an increasing number of propagation paths, causing the model to lose track of recent information in favor of the distant past.

Comparison of information flow in standard, dilated, and normalized causal convolutions. Heatmaps show sensitivity relative to distance from time t.

Furthermore, the authors prove that spatiotemporal over-squashing is the multiplicative product of spatial and temporal bottlenecks. This implies that addressing only one dimension (e.g., spatial rewiring) is insufficient. Crucially, they demonstrate that TTS and T&S models are affected by these bottlenecks to the exact same degree, providing a strong theoretical justification for using the more computationally efficient TTS designs.

Proposed Solutions: Temporal Graph Rewiring

To mitigate these bottlenecks, the authors propose temporal graph rewiring techniques:

  • Dilated Convolutions: Alter the temporal graph structure to capture longer-range dependencies.
  • Row-Normalized Convolutions: Adjust weights to ensure recent data is not overshadowed by the temporal sink.

Results

The authors validated their findings across synthetic and real-world benchmarks:

  • Synthetic Tasks: On the COPYLAST task, standard temporal convolutions failed as depth increased, while row-normalized convolutions maintained a 100% success rate.
  • Real-World Performance: On traffic (METR-LA, PEMS-BAY) and weather (EngRAD) datasets, TTS models performed comparably to or better than T&S models. On EngRAD, combining spatial rewiring (FOSR) with temporal normalization reduced Mean Absolute Error (MAE) from 44.47 to 40.30, confirming that addressing both bottlenecks yields the best results.

Conclusion and Future Work

This research provides a theoretical foundation for understanding information flow in STGNNs. By identifying the temporal sink and the equivalence of TTS and T&S architectures, it offers clear pathways for designing more robust spatiotemporal models. Future work will extend this framework to recurrent STGNNs and derive tighter, data-dependent sensitivity bounds.

Summary updated

BibTeX
@inproceedings{marisca2025over,
  author = {Ivan Marisca and Jacob Bamberger and Cesare Alippi and Michael M. Bronstein},
  title = {{Over-squashing in Spatiotemporal Graph Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=CVp0WCw4a1},
}
Figure