Over-squashing in Spatiotemporal Graph Neural Networks
This addresses a fundamental limitation in STGNNs for researchers and practitioners, providing theoretical insights and guidance for more effective designs, but it is incremental as it extends known static issues to spatiotemporal contexts.
The paper formalizes the over-squashing problem in Spatiotemporal Graph Neural Networks (STGNNs), showing it has distinct characteristics from static graphs, such as favoring information from temporally distant points, and proves that common processing paradigms are equally affected, with validation on synthetic and real-world datasets.
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.