Over-squashing in Spatiotemporal Graph Neural Networks

We thank the reviewer for the constructive feedback and for recognizing the clarity of our theoretical framework and the quality of the visualizations. Below, we address the concerns raised regarding scope, evaluation methodology, and originality.

1. W1. Extension to RNN-based STGNNs
   We agree that extending the analysis to RNN-based STGNNs is an important and valuable direction. In this work, we focus on convolutional STGNNs (specifically MPTCNs) due to their widespread use and because their architectural structure lends itself to tractable theoretical analysis. In particular, the analogy between temporal and spatial convolutions enables a unified sensitivity framework. RNNs, by contrast, involve sequential dynamics with nonlinear hidden-state recursion, which introduce fundamentally different analytical challenges. A unified treatment would require distinct tools and significantly broaden the scope beyond what is feasible in a single paper. We view our work as a foundation for such future extensions and have clarified this in the conclusion.

2. W2 & Q1. Designing a Spatiotemporal NeighboursMatch to Complement Propagation Benchmarks
   We thank the reviewer for this excellent suggestion. We agree that a spatiotemporal NeighboursMatch would be a valuable addition to our evaluation suite, as it would evaluate complementary aspects to over-squashing.

   We propose TemporalNeighboursMatch, an adaptation of NeighboursMatch $1$ to the spatiotemporal setting. In NeighboursMatch, information is propagated from sender nodes to a root node, with the correct sender identified by matching node degrees to the root node. We extend this to a temporal setting with fixed graph topology in time and a single active time step, where only sender nodes receive non-zero features. This time step is a hyperparameter, akin to depth in TreeNeighboursMatch. The goal remains to route the correct sender’s feature—identified by matching degree—to the root at a later step.

   We are currently implementing this synthetic benchmark and plan to run experiments during the rebuttal period. While results are not yet available, we believe it will meaningfully strengthen our evaluation, and we will report updates as they become available.

   This proposed task complements our existing benchmarks. COPYFIRST and COPYLAST test temporal memory and long-range propagation, while RocketMan (k-hop average) targets spatiotemporal information propagation bottlenecks, extending prior synthetic tasks such as **GraphTransfer $2$ ** and **RingTransfer $3$ **. In particular, it requires retrieving information from a specific spatiotemporal location, with temporal and spatial distances, as well as graph topology, jointly configurable. In contrast, NeighboursMatch-style tasks emphasize information compression—the need to retain and route specific input signals through bottlenecks. Together, these benchmarks help capture multiple aspects of over-squashing in spatiotemporal models.

3. W3. Originality of the work compared to GNN literature
   Our main contribution is to extend over-squashing analysis, traditionally studied in static GNNs, to the spatiotemporal setting, where temporal structure interacts with graph topology in nontrivial ways. Prior work has not addressed how over-squashing manifests when information must propagate both across nodes and over time. While tools like Jacobian sensitivity and rewiring are established in the static case, applying them to STGNNs introduces new challenges. For example, temporal message passing reshapes receptive fields, and static formulations do not capture how temporal and spatial dependencies interact. Our theoretical results (Theorems 4.1 and 5.1) explicitly disentangle these effects, and our empirical findings uncover behaviors unique to the temporal dimension, such as non-monotonic sensitivity with respect to time. Although STGNNs build on GNN components, their information flow is structurally different. We believe that adapting core techniques to this setting, and revealing new failure modes, adds both novelty and value.

4. Q2. Interplay of temporal and spatial rewiring
   This is an insightful question. As Theorem 5.1 shows, temporal and spatial topologies jointly influence the sensitivity through a multiplicative relationship. Improving only one component (e.g., temporal connectivity) may not mitigate over-squashing if the other remains bottlenecked. We conducted additional experiments combining temporal and spatial rewiring, through row-normalized convolutions and FoSR, to assess their combined effect. Please see answer n.4 in the rebuttal for reviewer QFNp.

5. Q3. Empirical support for the equivalence of TTS and T&S models
   We agree with the reviewer that, beyond Jacobian-based sensitivity bounds, forecasting accuracy can also be influenced by optimization dynamics, model expressivity, and hyperparameter sensitivity. While Theorem 5.1 shows that TTS and T&S architectures face similar over-squashing risks in theory, this does not imply identical empirical performance. In our experimental setup, TTS and T&S models are deliberately designed to be highly comparable, differing only in the order in which spatial and temporal processing is applied while keeping the same temporal and spatial budgets. When trained under identical hyperparameter settings, we observe that TTS models tend to perform slightly better across both synthetic and real-world datasets. However, we acknowledge that T&S architectures may benefit from different optimization choices (e.g., learning rate, initialization, or depth), which we have not extensively tuned. The observed performance gap is modest, but we agree that a more thorough empirical analysis—particularly examining optimization dynamics—would further complement the theoretical findings. We consider this a valuable direction for future work.

We appreciate the reviewer’s thoughtful feedback and hope our clarifications help contextualize the scope and novelty of our contributions. We would be grateful if these responses support a more favorable evaluation.

[1] Alon, U., & Yahav, E. “On the bottleneck of graph neural networks and its practical implications.” International conference on Learning Representations, 2021
[2] Di Giovanni et al. "On over-squashing in message passing neural networks: The impact of width, depth, and topology." International conference on machine learning. PMLR, 2023.
[3] Gravina et al. "On oversquashing in graph neural networks through the lens of dynamical systems." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 39. No. 16. 2025.

We thank the reviewer for their thoughtful feedback and for highlighting the strengths of our work, particularly the theoretical characterization of spatiotemporal over-squashing and the clarity of our exposition. Below, we respond to the main concerns and questions raised.

1. W1. Relation to results on GNNs
   We agree that temporal and spatial convolutions share structural similarities, and this motivated our decision to focus on convolutional STGNNs. However, as we highlight in Theorem 4.1, the temporal convolutional setting exhibits specific behaviors not directly implied by the more general spatial (GNN) case. In particular, the causal and sequential structure of temporal topology introduces new forms of bottlenecking not directly applicable to arbitrary graphs. This distinction allows us to derive sharper theoretical insights that are specific to the spatiotemporal setting and not straightforward extensions of existing GNN results. We believe this makes the formalization meaningful, novel, and distinct.

2. W2. Comparison with non-convolutional models
   Our experimental objective was not to comprehensively benchmark all STGNN architectures, but to validate our theoretical results for MPTCNs on not only synthetic tasks but also real-world settings, an aspect often overlooked in theoretical studies. We included Graph WaveNet, a still-competitive and widely used STGNN, to demonstrate that the observed similarities between TTS and T&S architectures concerning over-squashing in factorized convolutional STGNNs also hold in more complex settings that incorporate additional components such as dropout, batch normalization, and residual connections. We explicitly avoid making claims of generality beyond this class of models. Our assumptions and scope are stated clearly throughout the paper. Nonetheless, we appreciate the suggestion and plan to extend our comparisons in future work to include other common STGNN designs.

3. Q1. Significance of upper-bound analysis
   We appreciate this important question. While upper bounds may not fully capture the tightest sensitivity behavior, they serve a critical role in identifying potential bottlenecks. Specifically, the upper bound in Theorem 4.1 reveals how variations in the temporal topology matrix $R$ can limit the propagation of information between time steps. For instance, a small $(R)\_{ij}$ results in reduced sensitivity from $t-i$ to $t-j$. We corroborate this behaviour empirically in our synthetic experiments, demonstrating that the bound, though conservative, provides practical guidance in identifying over-squashing. We fully agree that developing a lower bound would yield a valuable yet complementary perspective; however, it remains an open problem, and we regard this as a promising direction for future work. We will add a note on the limitation of the upper bound in the limitations section.

4. Q2. Comparison with graph-rewiring baselines
   While the primary goal of our experimental section was to validate our theoretical results within the MPTCN family, we recognize the value of broader comparisons, particularly incorporating graph rewiring components alongside our proposed temporal mitigations. As suggested by the reviewer, we adopted FoSR $1$ as the graph rewiring method and evaluated its performance with and without row-normalized convolutions on the EngRAD dataset. We selected EngRAD due to its symmetric topology, which makes rewiring more meaningful compared to traffic forecasting tasks, where spatial structure is rigidly defined by the underlying road network. Besides our original MPTCN implementation relying on Diffusion Convolution (DCNN) as message-passing operation, we further consider RGCN $2$ , to weight differently the contribution of rewired edges. We report results in terms of MAE in the TTS setting below:

   MP operation	$R$	$R_N$
   DCNN	43.50 ± 0.08	40.30 ± 0.16
   RGCN	43.78 ± 0.29	41.10 ± 0.11
   Original	44.47 ± 0.42	40.38 ± 0.08

   These results indicate that combining both spatial and temporal rewiring yields the best average performance when using DCNN. In particular, each technique individually improves performance, with temporal rewiring contributing the largest marginal gain. This is consistent with our theoretical analysis, reinforcing that temporal bottlenecks are a significant limiting factor in STGNNs.
   We also measured inference latency in terms of batches processed per second at test time. We found that spatial rewiring introduces a substantial overhead (~70% throughput compared to models without rewiring), whereas row normalization has only a minor effect (~92%). These findings will be included in the revised version of the paper to address this concern more thoroughly.

5. Q3. Extension to joint space-time convolution
   Thank you for this insightful suggestion. Our current results are derived under a factorized architecture, which constrains the Jacobian structure in a way that allows clean theoretical bounds and comparable experimental frameworks, applicable to both TTS and T&S variants. Joint space-time convolution (e.g., 2D kernels over space-time) represents a broader class, which enables interactions among different nodes and time steps spanning both dimensions simultaneously. In this case, the factorization is not possible unless we assume these cross-dimensional interactions to be blocked, resorting to our factorized case. Generalizing the sensitivity analysis to arbitrary joint convolutions is non-trivial due to the coupling of spatial and temporal dependencies, but we agree that this is a promising direction. We have added a note on this in the discussion section and plan to explore this extension in future work.

6. Discussion of limitations

   "The paper lacks a direct discussion of its limitations."

   We do include a limitations paragraph in Section 7, where we state that our theoretical framework applies primarily to convolutional architectures, and does not cover recurrent or general joint spatiotemporal models. We will revise this section to more explicitly highlight the limits of our analysis and assumptions to ensure clarity.

We appreciate the reviewer’s constructive feedback and hope that our responses and additions help clarify the paper’s scope and contributions. We would be grateful if these points might support a more favorable reassessment.

[1] Karhadkar et al. "FoSR: First-order spectral rewiring for addressing oversquashing in GNNs." arXiv preprint arXiv:2210.11790 (2022). [2] Schlichtkrull et al. "Modeling relational data with graph convolutional networks." European semantic web conference. Cham: Springer International Publishing, 2018.

We sincerely thank the reviewer for the thoughtful and encouraging feedback. We are glad that the reviewer recognizes the novelty, significance, and robustness of our theoretical framework and its practical relevance. Below, we address each of the raised points.

1. W1 & Q3. Extension to recurrent architectures and models with joint space-time filters
   We fully agree that extending the analysis to recurrent architectures or models with joint space-time filters is a valuable direction for future work. In this paper, we focused on delivering a rigorous and targeted analysis of spatiotemporal over-squashing within a widely-used class of factorized convolutional STGNNs.
   Recurrent STGNNs following a T&S paradigm exhibit fundamentally different information propagation dynamics. In these models, the spatial receptive field typically expands with the sequence length, differently from the TTS counterpart, where the entire temporal sequence is encoded into a latent state later used for message passing. A thorough theoretical analysis of recurrent STGNNs would require substantially broader analysis, which we view as out of scope for a conference-length submission.
   Conversely, joint space-time filters are more closely aligned with our setting. The factorized convolutional models we study can be viewed as a special case of joint space-time architectures with a constrained parameterization. Therefore, our theoretical results apply directly to a subset of joint models where cross-dimensional edges are not considered. However, generalizing our sensitivity bounds to arbitrary joint space-time filters – which by design follow a T&S scheme only – would require analyzing a larger architectural space. We consider this a promising future direction and have added a note on this in the discussion.
2. W2 & Q1. Reduced sensitivity towards earlier time steps
   We agree that the finding appears counterintuitive at first glance. Our analysis shows that this effect emerges at depth, rather than in shallow causal convolutional networks. Specifically, Proposition 4.2 shows that as more convolutional layers are stacked, the influence of temporally recent inputs diminishes relative to more distant ones. This behavior stems from the structure of causal convolutions, which incrementally incorporate more information into a fixed-length context vector. When viewed through the matrix-multiplication perspective (i.e., using the Toeplitz matrix representation), it becomes evident that causal convolutions propagate information along powers of a directed path graph. Over multiple layers, earlier time steps accumulate influence through an increasing number of propagation paths, while more recent inputs have fewer paths for propagating their initial information. Importantly, because causal convolutions are forward-only, each time step can preserve its information in the associated context vector through self-loops only, with a major impact on the last time step in the sequence. When a task requires preserving local or recent information, this primacy bias can negatively impact performance even in trained neural networks, as demonstrated in the CopyLast experiment (Fig. 3). We have expanded the relevant discussion to clarify this mechanism and its practical implications for tasks that rely heavily on recent inputs.
3. W3 & Q2. Limitations of mitigation strategies
   Thank you for highlighting the limitations of the proposed mitigation techniques.

   • Dilated convolutions ($R\_D$): The parameters $P$ (dilation base) and $m$ (reset modulo) are primarily chosen to control the temporal receptive field at each layer. To avoid the sink effect (seen in Fig. 2(b.2)), we require $m \> L$, i.e., no resets within the model depth. However, when the dilation rate grows beyond the window size at layer $l \> \\log\_P T$, the convolution degenerates into a fully-connected layer shared across time. In these cases, resets become necessary for temporal propagation, but reintroduce the risk of over-squashing. Smaller $P$ allows more flexibility in setting $m$ before hitting this tradeoff.

   • Row-normalization ($R\_N$): While effective in retaining local information for the last time step – useful for encoder-decoder architectures – the behavior for earlier steps is still similar to the vanilla model. As shown in Fig. 2 (c.2), however, paths toward the final time step dominate compared to any other paths in the temporal graph. Thus, for tasks requiring readout at intermediate time steps (e.g., imputation), the benefits of $R\_N$ may be limited. We have added a clarifying note in the discussion of mitigation strategies.

We appreciate the suggestion to conduct a systematic sensitivity analysis of the mitigation strategies. While we agree that this could yield interesting insights, we believe it would fall outside the intended scope and focus of this work. As the reviewer kindly acknowledged, our paper is primarily theoretical, and our experiments were designed to validate core theoretical claims rather than to fully optimize or benchmark each mitigation strategy. We have added a brief mention of this limitation and encourage future work to build upon these mitigation techniques with a more exhaustive empirical lens.

We thank the reviewer for their thoughtful and constructive feedback. We are pleased that the reviewer finds our theoretical analysis rigorous and our empirical results insightful. We respond to the weaknesses raised point-by-point below:

• W1. Interpretation of heatmaps (Figure 2)
  We appreciate this suggestion. Figure 2 displays heatmaps of the normalized entries of the temporal topology matrices. These values correspond to the right-hand side of the upper bound in Theorem 4.1. A lower value for the $(i,j)$ entry indicates a higher risk of temporal over-squashing from time step $t-i$ to $t-j$, as it implies a weaker effective connectivity between the two time steps at the corresponding layer. We have revised the caption of Figure 2 to explicitly clarify this interpretation and added a brief explanatory sentence in the main text to guide readers through the heatmap axes and color scale.

• W2. Practical trade-offs between TTS and T&S architectures
  Thank you for this insightful suggestion. In the manuscript (Lines 163–174), we briefly highlight the efficiency advantages of TTS, particularly for distributed implementations where temporal processing can be conducted individually across the time series before spatial processing. We agree that a more detailed discussion of practical trade-offs adds value. Accordingly, we have expanded the text to highlight that T&S architectures may be more suitable when the graph topology varies over time, with each time step potentially associated with a different adjacency matrix. In such cases, TTS models require additional mechanisms to aggregate or align spatial topologies across time steps. This addition complements the analysis of computational complexity for both approaches, as detailed in Appendix C.

• W3. Scope limited to factorized convolutional architectures
  We fully agree that analyzing over-squashing in other STGNN paradigms – such as recurrent or Transformer-based models – is a valuable direction. We acknowledge this limitation in the paper and emphasize that our goal was to provide a formalization of spatiotemporal over-squashing and a deeper analysis in a specific and popular class of STGNNs. Different paradigms (e.g., attention-based or recurrent models) rely on fundamentally different information propagation mechanisms, making it challenging to analyze them under a unified framework. Doing so with comparable theoretical depth would substantially increase the scope and length of the paper and require a level of detail beyond what is feasible within the limits of a conference-length submission. We view our work as laying the theoretical foundation for future explorations into over-squashing in other architectures, and have clarified this in the conclusion section.