Over-squashing in Spatiotemporal Graph Neural Networks
Authors: Ivan Marisca
Jacob Bamberger
Cesare Alippi
Michael M. Bronstein
Venue: NeurIPS 2025 poster ()
Keywords: Graph Neural Networks
Spatiotemporal Graph Neural Networks
Over-squashing
Time Series Processing
Time Series Forecasting
Primary area: deep_learning
TL;DR: We formalize the over-squashing phenomenon in spatiotemporal graph neural networks and analyze how it affects information propagation across the spatial and temporal dimensions.

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.

Over-squashing in Spatiotemporal Graph Neural Networks
Ivan Marisca
Jacob Bamberger*
Cesare Alippi!.
Michael M. Bronstein
Università della Svizzera italiana, IDSIA, Lugano, Switzerland. 2 University of Oxford, Oxford, UK. Politecnico di Milano, Milan, Italy.
AITHYRA, Vienna, Austria.
Abstract
Graph Neural Networks (GNNs) have achieved remarkable success across vari- domains. However, recent theoretical advances have identified fundamental limitations in their information propagation capabilities, such as over-squashing, where distant nodes fail 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 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 informa- tion propagation from points temporally distant rather than close in time. Moreover, we prove that architectures that follow either aame-and-space or teme-thee-space processing paradigms are equally affected by this phenomenon, providing theoret- ical 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.
Introduction
Graph deep learning [1, 2] has become powerful paradigm for learning from relational data, par- ticularly through graph neural networks (GNNs) [3-5]. These models process attributed graphs, where nodes represent entities and edges encode their relationships, and have shown strong per- formance in applications such as drug discovery [6, 7]. material synthesis [8, 9], and social media analysis [10]. Beyond static graphs, GNNs have also been extended dynamic settings where graph data evolves over time [11-13]. When data can be represented as synchronous sequences associated with nodes of a graph, common approach is to pair GNNs with sequence models like recurrent neural networks (RNNs) [14, 15] or temporal convolutional networks (TCNs) [16, 17], leading to the class of spatiotemporal graph neural networks (STGNNs) [18-20]. These architectures have been successfully applied to real-world problems ranging from traffic forecasting [19, 21] to energy systems [22, 23] and epidemiology [24]. While the strong empirical performance of STGNNs has largely driven their development, much less attention has been devoted to understanding their theoret- ical capabilities and limitations. This contrasts with the literature on static GNNs, which includes extensive analyses on expressivity [25, 26] and training dynamics, including over-smoothing [27-29] and over-squashing [30-32], In particular, over-squashing where information from distant nodes is compressed through graph bottlenecks has emerged central limitation of message-passing
Work done while at University of Oxford. Correspondance to ivan. mari marisca@usi.cch
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Spatial graph
Spatiotemporal graph
Temporal graph
(v. t)
Figure I: Example of spatiotemporal topology governing information propagation in STGNNs. The increasing receptive fields of graph-based and sequence-processiin architectures compound, as shown in the Cartesian product of spatial and temporal graphs the right.
architectures. However, these insights do not directly extend to STGNNs, in which information is propagated not only across the graph but also along the time axis. Understanding how over-squashing occurs in this joint spatiotemporal setting remains an open question.
The temporal axis represents an additional challenge, typically handled by imposing a locality assumption: adjacent time steps are presumed to be more correlated than distant ones. Under this assumption, the sequence behaves like a second, directed graph whose edges encode temporal order. As we stack local filters- - or simply process longer sequences increasing volumes of information are stored into fixed-width embeddings, a limitation already noted for recurrent architectures [33, 34). When this temporal compression meets the constraints of spatial message passing, creates compound bottleneck we call spatiotemporal over-squashin: messages must cross rapidly expanding receptive fields in both space and time, exceeding the capacity of intermediate representations. Figure 1 visualizes this dual-graph structure, where information must propagate across both the spatial dimensions (blue edges) and temporal dimensions (red edges), with each path potentially contributing to the over-squashing phenomenon.
Two dominant architectural strategies have emerged to propagate information both through time and space. Time-then-space (TTS) models first compress each node's sequence into a vector representation and only afterward propagate these embeddings across the graph, whereas time-and- and-space (T&S) models interleave temporal and spatial processing so that information flows across both axes at every layer [35, 20J. While the choice between these paradigms has been driven mainly by empirical accuracy and computational costs, we argue that a principled analysis of these trade-offs is essential for guiding the design of future STGNNs.
In this work, we investigate how the interplay between temporal and spatial processing in STGNNs shapes learned representations, and how this process is limited by spatiotemporal over-squashing. We analyze information propagation patterns in existing STGNNs designs by tracing the sensitivity of each embedding to the input features contained neighboring nodes and time steps. Specifically, our study focuses on convolutional STGNNs, whose temporal component is implemented through a shift operator that exchanges messages between adjacent time steps the time-domain analogue of message- message-passing on graphs [36]. In summary, our contributions are the following:
1. We formally characterize spatiotemporal over-squashing and show its fundamental differences from the static case. The temporal dimension introduces an additional axis for information flow, potentially amplifying the compression effects observed in static graphs. (Sec.3)
2. We prove both thcoretically and empirically that architectures leveraging causal convolutions are, counterintuitively, more sensitive to information far apart in time, and outline architectural modifications that mitigate this imbalance when required by the task. (Sec.4)
We demonstrate that spatiotemporal over-squashing affects T&S and TTS paradigms to the same degree. Thus, the computational benefits of TTS models come at no extra cost in terms of information bottlenecks, providing theoretical support for scalable designs. (Sec.5)
All theoretical findings are supported by empirical results on both synthetic tasks specifically designed to highlight spatiotemporal bottlenecks. and real-world benchmarks, demonstrating that our insights translate to practical improvements. To our knowledge, no previous work addressed the over- squashing phenomenon in STGNNs, despite its potential impact on spatiotemporal modeling. Our work fills this gap by providing theoretical framework for understanding information propagation in STGNNs, with direct implications for model design and optimization.

---

2 Background
Problem setting We denote by V the set of N synchronous and regularly-sampled time series, with zy E IR being the dy-diimesional observation at time step t associated with time series v E V. The sequence T..T: E Ix'xd= indicates the node observations in the interval (t - T, tJ. X, E Nxd, the matrix of all observations in V at time t, so that (Xe), z; is the v-th entry of Xx. When referring to a generic node or time step, we omit the indices " and if not required. We express temporal dependencies across observations within Tt-T:t a directed path graph T E 10.1)"XT, named temporal graph, where (T)i i.e., the edge from time step ( - i to L- j. is 1 only i j- 1; T acts as the backward shift operator [37]. We assume the existence of relationships across time series, describing dependencies or correlations between the associated observations. We express them as edges in a spatial graph with (weighted) adjacency matrix A E R N where a = (A) uv is nonzero only if there exists edge connecting node operator, i.e., an N x N real matrix with a"" * 0 if and only if anv A 0 [38].
v. We use A to indicate graph shift
We focus on node-level tasks and, given window of T observations Xi-r: and target label Y,, we consider families of (parametric) models fa conditioned on the structural dependencies such that
y (fe (Xt-T:t, A,))), VVEV,
(1)
where 0 is the set of learnable parameters and De is the estimate for y. For classification tasks, y encodes the node label, while for prediction, the label is a sequence of k: future observations x x k- Parameters are optimized using task-dependent loss function, e.g., the mean squared error (MSE).
Spatiotemporal message passing STGNNs are architectures specifically designed to process graph-structured data whose node features evolve over discrete time steps [20, 13]. These models leverage GNNs to capture spatial dependencies while employing gruuence-processing operators to model temporal dynamics. Among the different GNN variants, the primary deep learning approach for relational data are message- paassagg-pssinggggg neural networks (MPNNs) [39], which operate by iteratively updating each node's 's representation through aggregation of information from neighboring nodes [4, 5, 2]. In an MPNN, node representations h" (1) E Rd at the I-th layer are computed through MP(') as
h (1) (MP()) (H-) a)),==9) (1-11, AGGR (EN(
(0(0) (n.(1-1), h (((1-)) aaw)) })
(2)
where 70) and (()) are differentiable update and message functions, respectively, A is permutation invariant aggregation function over the set of messages, and N N(v) is the set incoming the term temporal message- passing [40] for any function TMP!!) that computes each i-th representation ( from the sequence (t-1) by conditioning on the temporal dependencies defined by T, i.e. htTT
neighbors of v. Borrowing this terminology, in the following
(1) +- TMP!!)
(nE-T' T
Examples of this function class include RNNs and TCNs. While the MP and TMP operators described previously are constrained to processing along single dimension, the spatiotemporal pressage-passingg layer STMP extends this capability to operate simultaneously across both spatial and temporal dimensions [41]. This allows the model to condition its output on both the graph and backward shift-operators A and T, respectively:
v() h h (STMP()) (H.)))...T)) A.T)))
Over-squashing in GNNs mation throughout the layers of a GNN [30], which particularly hinders long-range interactions [42]. A common way to assess over-squashing is by means of sensitivity analysis through the Jacobian
This term describes the compression of exponentially increasing infor-
(L)
V P(L) = (h) E Rdxd
(5)
whose spectral norm [[)] acts as a proxy to measure how much initial information at node u can influence the representation computed at node after L GNN processing layers [31, 32]. For broad class of MPNNs, Di Giovanni et al. [43] obtained the following bound, which isolates the two contributions of architecture and graph structure over-squashing
3

---

Theorem C.1 (from Di Giovanni et al. [43]). Consider an MPNN with L layers. with cę being the Lipschitz constant of the update function after activation and 9m and 9, being the maximal norms over all weight matrices in the message and update functions, respectively. For e, u E V we have:
|4n - (gg0m)) (SL)
model
togology
where : - -1 diag (A c2 RNNN is the peesagg-passsigg matrix such that the
Pm Jacobian of the message function (1 w.r.t. the target (v) and neighbor (u) node features has bounded norms 01 and C2 respectively.
Information propagation and over-squashing in STGNNs
In line with previous works [41, 20J, we consider STGNNs obtained by stacking L STMP lay- ers (Bq.4), preceded and followed by differentiable encoding and decoding (readout) functions:
h
(0) ENCODER (a="))
(6)
U READOUT (n.(1))
Note that the encoder is applied independently to each node and time step, while the readout produces estimates for the label using only node representations associated with the last time step. Most existing STGNNs can represented following this framework and differ primarily in the processing carried out in STMP. In the following, we consider STMP operators resulting from the composition of message- pasggegg,.ing..... i.e., MP, and sequence praeicceproessingg..m i.e., TMP, operators.
3.1 Spatiotemporal message-passian passing designs
straightforward yet effective strategy to design an STMP layer is to factorize processing along the two dimensions with sequential application of MP and TMP. This enables using existing operators, making the resulting STGNN easy to implement. We can write the (-th STMP layer as:
= TMP()) (n ( T) Y (8) XLT
2 = (MP!Ls XLs A)) Aj (0,)
(9)
21-7:8 Rxxd is the sequence of intermediate representations resulting from node-level temporal encoding, and MP is applied independently (with shared parameters) across time steps. The subscript xLr xL.)) concisely denotes stack LT (Ls) functions of the same family with distinct parameters- each receiving as input representation the output from the preceding function in stack. Although processing is decoupled within a single STMP MP layer, the resulting representations effectively incorporate information from the history of neighboring nodes.
where r(f)
Unlike the graph domain, where MPNNs have established themselves as the standard framework for processing relational data, the temporal domain lacks a unified approach that encompasses all architectures. Due to their architectural similarity to GNNs, in this work, we focus on TCNs, which allows for more natural extension to spatiotemporal modeling and facilitates drawing analogies between temporal and graph-based representation learning.
We call message-passingg temporal convolutional networks (MPTCNs) those STGNNs obtained by combining TCNs and MPNNs following the framework defined in Eq. 8-9 [44, 21]. Specifically, the TMP operator is implemented as a causal convolution of a nonlinear filter with P elements the temporal dimension [45, 36, 16). Causal convolutions can be expressed through Toeplitz matrix formulation, which enables the analysis of their propagation dynamics. To formalize this, introduce the lower-triangular, Toeplitz matrix R (0, 1] 1J'xx where (R); = 1 the input at time step - influences the output at time step t - j. This matrix encodes temporal dependencies analog to how the graph shift operator À encodes spatial relationships in MPNNs. We define the (-th layer of a TCN TC())
MPTCNs
h TiT = () (N R = 'n' diag, (R) h 1 (!
(1)
(10)
where each W (1) E Rdxd d is matrix learnable weights, a an element-wise activation function (c.g., ReLU), and diag,(R) (R) is the matrix obtained by zeroing all entries of R except those its

---

p-th lower diagonal. In standard convolutional implementations, we employ R = Ep=o T", with iR) 1 only if 0 S i j-j < P. such that diag, (R) T². This formulation reveals the structural parallels between temporal and spatial message passing, both conditioned on specialized operators (R and A, respectively) that encode the underlying topology.
Time-and-
time-then-space By adjusting the number of outer layers L and inner layers LT and Ls, we can control the degree of temporal-spatial integration while maintaining fixed total processing depth, LLT and LLs, which refer the temporal and spatial budget respectively. Fixing both budgets enables a fair experimental comparison between TTS and T&S variants. When - processing becomes fully decoupled, yielding the computationally efficient TTS approach that has gained recent prominence [35, 46, 47]. This efficiency arises because encoder-decoder architectures only require representations time / and layer I. for readout (see Eq. 7), allowing message passing on single (static) graph with features H!L) Thus, with equivalent parameter counts and layer depths, the TTS approach offers substantially reduced computational complexity for spatial processing, scaling with O(Z) detailed discussion of the computational complexities provided in Appendix C. This advantage is particularly valuable in practical applications, where temporal processing can occur asynchronously across nodes before being enriched with spatial context, enabling efficient distributed implementations [48]. However, T&S architectures may be more suitable and straightforward to adopt when the graph topology varies over time, with time steps associated with potentially different adjacency matrices.
3.2 Spatiotemporal over-squashing
While sensitivity analysis has become a standard approach to studying over-squashing in static GNNs [31, 32, 43, 491, it has been limited graphs with static node features. We extend this analysis to STGNNs by examining the sensitivity of node representations after both temporal and spatial processing. In particular, we are interested in studying how information propagation across space and time affects the sensitivity of learned representations to initial node features at previous time steps. Considering that ah, ( /dx = 0 and θÿÿ /ōh, uiL) 0 for each j O, # v, we analyze the Jacobian between node features after a stack of L, STMP layers, i.e.,
((L) = ah,
(h)()) o(L)
E Rdddd
(11)
0h u(0)
This quantity differs conceptually from the simpler static-graph setting (Eq.5), 5), as the temporal dimension represents an additional propagation axis. Notably, in decoupled STMP functions (Eq.8- 9), information flows strictly along separate dimensions: TMP operates exclusively within the temporal domain, while MP processes only spatial relationships, preventing cross-dimensional interactions. Hence, given an STGNN of L layers, for each layer E [1, LJ. nodes u, v E V and
i [0, I) we have
Oh v(l)
v(t)
m(l)
(12)
ah
m([-1)
azy-g
oh ((11)
space
This factorization allows to independently study the effects of temporal and spatial processing within each layer on the output representations. Moreover, in the TTS case where L 1, this result provides a factorized tool to investigate Vin, ((L) and measure how initial representations affect the final output. While the spatial component has been extensively studied in the literature on GNNs (as discussed in Sec. 6), the temporal dimension, especially the phenomenon of temporal over-squashing, remains less explored. In the following section, we investigate how temporal processing affects representation learning in TCNs, and consequently, MPTCNs. Following an incremental approach, we first discuss its effects on propagation dynamics in TCNs in the next section, and then extend the analysis to the spatiotemporal setting in Sec.5.
4 Over-squashing in TCNs
To isolate the temporal dynamics, we focus exclusively on the temporal processing component by analyzing encoder-decoder networks constructed from LT successive TC layers positioned between
5

---

encoding and readout operations. In these architectures, each additional layer expands the network's s temporal receptive field, enabling the model capture progressively longer-range dependencies in the input sequence. This hierarchical processing creates an information flow pattern that can be precisely characterized through the powers of the temporal topology matrix R. Specifically, R represents the temporal receptive field at the 1-th layer, where entry (R') )ig quantifies the number of distinct paths through which information can propagate from the input at time step - to the representation at time step f j after / layers of processing.
Understanding how information flows through these paths is crucial for analyzing the model's capacity to effectively leverage temporal context. To formalize this analysis, we investigate how the output representations are influenced by perturbations in the input at preceding time steps. The following theorem establishes a bound on this sensitivity, revealing how the temporal topology governs information flow across layers and drawing important parallels to the graph domain.
Theorem 4.1. Consider TCN with LT successive TC layers in Eq. 10, all with kernel size P. and assume that ||W;)) I w for all p < and S LT, and that |a"| S ca. For each i,j E [0, T),
we have:
(IT)
(cow)* AT (R
Ōh (0)
model
temporal topology
Proof provided in Appendix A. Similar to the spatial case in Theorem C. I, this bound comprises two components: one dependent model parameters and another on the temporal topology encoded in R. Unlike spatial topologies. however, the temporal structure follows a specific, well-defined pattern that enables deeper theoretical analysis. The lower-triangule triangular Toeplitz structure of R ensures that its powers maintain this structure [50]. This property leads to a distinctive pattern of influence distribution, formalized in the following proposition:
Proposition 4.2. Ler R E R be real. lower-triangulat Toeplitz band matrix with lower bandwidth P L, i.e., with (R); -r-s for 0 i- P. and P 2 r1 # O. and ro & O. Then
for any > j we have
(R')
as xo. In fact
= ((-((-))) Informally, this (R)
R 1a
[R])
means that the final token receives considerably more influence from tokens positioned earlier.
Proof provided in Appendix A.2. Proposition 4.2 reveals a critical insight: causal convolutions progressively diminish sensitivity to recent information while amplifying the influence of temporally distant inputs. This creates a form of temporal over-squashing that inverts the pattern observed in MPNNs, where distant nodes suffer from reduced influence [30]. We show this graphically in Fig.20 2a, which also displays the powers of the temporal topology matrix ( 1-.2.,,); a yellow color in matrix entry (i.j) indicates strong influence exerted from time step f- i to t t-j. 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 fixed-length context vector. Indeed, causal convolutions propagate information along powers of 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. Crucially, because causal convolutions are forward-only, each time step can preserve its information in the associated context vector through self-loops only, with major impact on the last time step in the sequence.
When model's receptive field exceeds the sequence length. i.e., (P- L) > T, the earliest time step exerts disproportionate influence on the final output compared to any intermediate time step. mirroring the recently investigated attention sink effect in Transformers [51, 52]. This behavior directly undermines the locality bias that causal convolutions are designed to enforce, partieularly in time series applications, where recent observations typically carry greater relevance. To achieve more balanced receptive field that preserves local information while incorporating broader context, we can act by modifying R, effectively implementing temporal graph rewiring analogous to techniques used to address over-squashin in MPNNs [31, 32).
Temporal graph rewiring Proposition 4.2 outlines that the influence from recent time steps pro- gressively vanishes when the temporal topology (1) remains fixed across layers and (2) maintains a lower-trianullar Toeplitz structure. We propose two rewiring approaches targeting these assumptions

---

Model depth
(a) Standard causal convolution
(b) Dilated convolution
(c) Normalized convolution
(a.1) R
(a.2) R
(b.1) R
(b.2) RØ
(c.1) R
(c:2) R
0t a. p. 1
Distinee froes
255
00
10
2 8 10 14 Distance from
0246 12
0.1. 4.4
10 Distunce from
12
1 12
Distanee from
Discance From
Distance from
Distanoe
Figure 2: Top row: paths for information flow from the most recent and an earlier time step to the last-layer representation at time Bottom row: evolution of the temporal receptive field after 4 and 20 layers, seen through the powers of the temporal topology matrix. For standard (R) and dilated (RD) convolution, the highest-influnce region shifts towards the initial time step, while for row-normalized (Rx) convolution, observe progressive shift to uniform distribution across all time steps (first column). Entries are scaled matrix-wise in the range [0, 1] for comparison purposes.
separately. Our first approach addresses the fixed topology assumption by employing different matrices R() at each layer (each maintaining lower- triar-triangllrr Toeplitz structure). This modifies the Jacobian bound Theorem 4.1 depend on I R()) rather than RLT, Dilated convolutions naturally implement this approach, applying filters with progressively increasing gaps d(l) (dilation rates) between elements [16] (Fig. 2b). These convolutions produce matrices R with nonzero entries (R));; ri-; only when - j = ()) for Is E P). When d(1) pp-1, the receptive field expands exponentially while ensuring (II, = for each p S Pl, hence distributing influence equally across all time steps in the receptive field (Fig. 2b. Thus, besides efficiency, dilated convolutions have the advantage of preserving local information better than standard convo- lutions. However, this strategy results in the trivial identity R IT for > logp T, with deeper architectures required reset the dilation rate every m layers, i.e., d() P(I-1) mod While effective practice, these resets reintroduce over-squashing patterns, as shown in Fig. 2b.2.
Our second approach targets the Toeplitz assumption by row-normalizing R to create Ry (Hag(R1)-1Pe R. where each entry (Rx)ij normalized by the number of edges from time step - (Fig.2c), 2c). This normalization maintains stronger influence from recent time steps while expanding the receptive field, with (R'y), converging to for all i E j0, 7') as + oo (illustrated in Fig. 2c. 1-c.2 and proven Proposition A.2 in the appendix). Despite violating the Toeplitz structure, this approach remains computationally efficient by simply dividing the input at time step t i by min(i + P). Nonetheless, this normalization primarily benefits the final time step prediction, making it particularly suitable for forecasting tasks where only the last output is used. For tasks requiring readout at intermediate time steps (e.g., imputation), the benefits of such mitigation may be limited.
Empirical validation We empirically validate the effects of our proposed temporal convolution modifications through two synthetic sequence memory tasks: COPYFiRS, and COPYLAST, where the goal to output, respectively, the first or last observed value in a sequence of = random values sampled uniformly in [0. 1]. Since always predicting 0.5 yields an MSE of z 0.083, we consider task solved when the test MSE is lower than 0.001 and report the success rate across multiple runs. We compare three TCNs architectures obtained by stacking LT TC layers with different temporal convolution topologies: (I) R, the standard causal convolution; (2) Ry, where is now-normalized: (3) R. implementing dilated convolutions with dilation rates (()) p(l-1) mod m and with M We set P = in R and R,,, and P 2 in R.p and vary LT from 1 to 20: Fig. 3 shows the simulation results. For small IT, the COPYFIRST task remains unsolved as the initial time step falls outside the receptive field, while standard convolutions fail COPYLAST when LT > 5 due to
7

---

COPYFIRST
COPYLAST
Success rate (%)
100
R
R
R
50
0
12345
8
10
12
16
20
12345
8 10
12
16 20
12345
8
10
12
16
20
Number of layers LT
Figure 3: Success rate (%) on the tasks of copying the first or last observed value across different temporal topologies and number of layers LT.
the sink phenomenon. As network depth increases, performance degrades across all approaches, despite COPYFIRST remaining more tractable given the sink-induced bias toward earlier time steps, suggesting fundamental connection vanishing gradients [33].
5
Over-squashing in MPTCNs
Having analyzed over-squashing in temporal and spatial domains separately, we now integrate these insights to investigate information flow in MPTCNs, in which temporal and spatial processing are interleaved across layers. For our analysis, we consider the same class of message- passage-passing functions employed by Di Giovanni et al. [43] in Theorem C. 1, which generalizes many popular MPNNs [25, 53-55J. Following the space-time factorization established in Eq. 12, we observe that within a single layer, the sensitivity is simply the product of the spatial bound from Theorem C. and the temporal bound from Theorem 4.1. For TTS architectures with L. 1, this yields:
V [())
(ce0m) Ls (S uy
(cow) Lr (R'T). 40
(13)
space
time
This bound directly measures how input features influence the final representations used by the readout layer. However, this result only addresses the case where L = 1 (the TTS approach). The question remains: how does information propagate when temporal and spatial processing alternate multiple times (L > 1, the T&S approach)? To answer this question, derive the following theorem that characterizes sensitivity across MPTCNs with any number of alternating processing blocks.
Theorem 5.1. Consider an MPTCN with STMP layers, each consisting of Ly temporal (TMP) and Ls spatial ( (MP) layers as defined in Eq. Eq.8-9. Assume that each TMP layer satisfies the conditions of Theorem 1, and each MP layer satisfies the assumptions in Theorem Then, for any U. E and i.j E [0,T), the following holds:
(())
I (c)0m) Lis (cow)LLr LLT (SLLs) un (R (R.LT))
m())
model
spatiotemporal topology
The proof is provided in Appendix A.2. This result bounds the influence of input features h on output representation k:(() revealing clean separation between model parameters and topological factors, as well as between spatial and temporal components. Two key implications emerge from this factorization. First, the bound's multiplicative structure across space and time dimensions persists regardless of how many STMP layers are used. This means that redistributing the computational budget among outer layers L and inner layers LT and Ls does not alter the bound's characteristics. Therefore. from the perspective of information propagation, TTS architectures (L = 1) are not inherently limited compared to T&S architectures (L 1). While this does not guarantee equivalence in expressivity or optimization dynamics, it provides a principled justification for adopting more computationally efficient TTS designs without compromising how information flows. Second, the theorem reveals that spatiotemporal over-squashing in MPTCNs arises from the combined effects of spatial and temporal over-squashing. This evident in spatiotemporal topology component, where both the spatial distance between nodes and and the temporal distance between time steps / i and - contribute equally to potential bottlenecks. This insight carries significant practical implications: addressing over-squashing effectively requires targeting both dimensions
8

---

(a)
RING (P
(b) RING (P =
(c) LOLLIPOP (P
(d) LOLLIPOP (P=1)
Spatial distance
s
Success (1)
12
0
Temporal distance
Temporal distance
Temporal distance
Temporal distance (
Figure 4: Success rate (%) TTS MPTCNs on the ROCKETMAN dataset, where the goal is to copy the average value associated with k-hop neighbors at time step / i. The tasks vary for the type of graph used (RING or LOLLIPOP) and size of P (2 or 3).
simultaneously. Improving only one component through either spatial temporal graph rewiring alone - wwlll prove insufficient if bottlenecks persist in the other dimension.
5.1 Empirical validation
To validate our theoretical results, we conducted experiments on both synthetic and real-world tasks that highlight the effects of spatiotemporal over-squashing. The reference MPTCN architecture used in the experiments features the Diffusion Convolution (DCNN) operator [54] as the MP layer.
Synthetic environments We design synthetic memory task named ROCKETMAN where, given a graph and a time window of random values, the model must retrieve the average value at time step -- for nodes exactly I hops away from a target node. We keep the input size constant across tasks and employ TTS architecture with precisely enough layers in each dimension to span the entire input space, reporting success rates across multiple runs. The results, shown Fig. 4, reveal two key patterns consistent with our theory. First, the task is significantly more challenging graph compared to the RING graph, confirming the known spatial over- squashig characteristics of these topologies [43]. Second, the convolutional filter size P increases, observe that the task becomes more challenging for lower temporal distances, aligning perfectly with our analysis of TCNs. Complete experimental details, including comparative results for a T&S architecture, provided in Appendix B, while Appendix D we show results on TEMPOR A NEIGHROURS adaptation of the synthetic environment NEIGHBOURSMATCH [30] to the spatiotemporal setting.
the LOLLIPOP
Real-world benchmarks To verify that our theoretical insights extend to practical applica- tions, evaluated various MPTCNs of fixed spatial and temporal budgets LLs and LLT re- spectively, three spatiotemporal forecasting benchmarks: METR-LA [19], PEMS- BAY [19],
Table 1: Forecasting error (MAE) of MPTCNs with fixed budget in real-world benchmarks.
MODELS
L
METR-LA PEMS-BAY
EngRAD
6
3.19
1.644am
44.43=0.41
R
3.19
1.65
43.8310.
and EngRAD [40]. Tab. presents the prediction errors in terms of mean absolute eтror (MAE).
МPTCN
3. 14
1.6320a1
44.47.2042
The results offer several insights that support our theoretical analysis. First, T&S and TTS ap- proaches perform comparably average, with the more efficient TTS models outperforming in the majority of cases. This empirical finding supports our theoretical conclusion that the TTS design is not inherently limited from an infor- mation propagation perspective, although additional factors beyond may also influence comparative performance. Second, the EngRAD dataset, which requires larger filter sizes to cover the input se- quence, the nww.maaaizzaiinnn approach consistently improves performance. This hints that temporal over-squashing affects standard convolutional models in practical scenarios where longer temporal contexts are needed, our theory suggests. Finally, we compare Graph WaveNet (GWNet) [21] widely-used and more complex T&S architecture against its TTS counterpart. Results show that findings remain valid even when sophisticated architectural components involved.
6
3.17=002
1.65+am
41.82=0.38
R
3
3.17
1.65
41.78:100>
3.100
1.6510.0
40.38
GWNet (urig.)
3.02=maz
1.55
40.50+4.27
GWNet TTS
3.00
1.57
40.64.0.29

---

Combining spatial and temporal rewiring In this experiment, we assess the combined ef- fect of spatial and temporal graph rewiring in alleviating spatiotemporal over-squashing. We adopt FOSR [56] as the graph rewiring method and evaluate the forecasting error with and with- out nownormalizedd convolutions. We test the models on EngRAD for its symmetric topology, which makes rewiring more meaningful com- pared to traffic forecasting tasks, where spatial structure is rigidly defined by the underlying road network. Besides our original MPTCN imple- mentation relying on DCNN as MP layer, we further consider RGCN [57], to weight differently the contribution of rewired edges. We report results in the TTS setting in Tab. 2. We can observe that combining both spatial and temporal rewiring yields the best performance in the original implementa- tion using DCNN. In particular, rewiring in each dimension individually improves accuracy, with the temporal one contributing the largest marginal gain. This is consistent with our theoretical analysis, reinforcing that temporal bottlenecks are significant limiting factor in STGNNs.
Table 2: Forecasting error (MAE) of TTS MPTCNs with and without spatial and temporal graph rewiring in EngRAD.
Original graph
FOSR rewiring
w/ RGCN
w/ DCNN
44.47:20.2
43.7820.29
43.50
R
40.38
41.10=a.11
40.30
6 Related work
The issue of over-squashing in GNNs was first highlighted by Alon and Yahav [30], who showed that GNNs struggle to capture long-range dependencies in graphs with structural bottlenecks. Building on this, Topping et al. [31] introduced a sensitivity-baat -bsed framework to identify over squusquus,,n which was later extended by Di Giovanni et al. [32, 43]. Two main strategies have emerged to alleviate this problem: graph re- wiring to enhance connectivity [58, 31, 56, 59]. and architectural modifications to stabilize gradients 160-62, 49]. Notably, these efforts largely overlook the role of time-evolving node features. Similar challenges
modeling long-range dependencies have been studied temporal architectures like RNNs, where vanishing and exploding gradients hinder effective learning [33, 34). Solutions include enforcing orthogonality [63] or antisymmetry [64] in weight matrices, as well as designing specialized stable architectures [65]. Recently, the attention sink effect [51] has revealed bias in Transformers towards early tokens [66]. with Barbero et al. [52] linking this phenomenon to over-squashing in language models. In the spatiotemporal domain, Gao and Ribeiro [35] analyzed the expressive power of STGNNs, showing their capabilities and limits in distinguishing non-isomorphic graphs in both T&S and TTS settings, while Gravina et al. [67] propose framework tailored to long-range tasks in continuous-time dynamic graphs. Yet, to our knowledge, no prior work has directly tackled the problem of spatiotemporal over-squashing in STGNNs, where the interaction between spatial and temporal dimensions introduces unique challenges for information propagation.
7 Conclusions
In this work, we have formally characterized spatiotemporal over-squashing in STGNNs, demon- strating its distinctions from the static case. Our analysis reveals that convolutional STGNNs counterintuitively favor information propagation from temporally distant points, offering key in- sights into their behavior. Despite their structural differences, we proved that both T&S and TTS paradigms equally suffer from this phenomenon, providing theoretical justification for computa- tionally efficient implementations. Experiments on synthetic and real-world datasets confirm our theoretical framework's 's practical relevance. The insights from this study directly impact the design of effective spatiotemporal architectures. By bridging theory and practice, we contribute to deeper understanding of STGNNs and provide principled guidance for their implementation.
Limitations and future work We focus on factorized convolutional STGNNs, aligning with established GNN research while extending existing theoretical results to the spatiotemporal domain. This choice allows for clean theoretical bounds and controlled setting applicable to both TTS and T&S variants. However, it also limits the generality of our results to models where cross- dimensional interactions are blocked. Extending our framework to models with joint space- paace-time filters or recurrent STGNNs, which follow fundamentally different propagation dynamies, represents a valuable direction for future work. Finally, our sensitivity bounds are derived in the worst case and are therefore potentially conservative; deriving tighter, data-dependent estimates and conducting a systematic analysis of mitigation strategies remain promising directions for future research.
10

---

Acknowledgments and Disclosure of Funding
The authors wish thank Francesco Di Giovanni for the valuable feedback and collaboration during the initial phase of this research. M.B. and J.B. are partially supported by the EPSRC Turing AI World- Leading Research Fellowship No. EP/X040062/1 and EPSRC AI Hub No. EP/Y028872/1. C.A. is partly supported by the Swiss National Science Foundation under grant no. 204061 HORD GNN: Higher--rder Relations and Dynamics Graph Neural Networks and the International Partnership Program of the Chinese Academy of Sciences under Grant 104GJHZ2022013GC..
References
[1] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXivv1806.01261, 2018.
[2] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13478, 2021.
[3] M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, volume 2. pages 729-734, 2005.
[4] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions neural networks, 20(1):61-88) 2008.
[5] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[6] Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Noom-Ackermmnn, et al. deep learning approach antibiotic discovery. Cell, 180(4))688-700) 2020.
[7] Gary Liu, Denise B Catacutan, Khushi Rathod, Kyle Swanson, Wengong Jin, Jody C Mo- hammed, Anush Chiappino-Pa Pepe, Saad A Syed, Meghan Fragis, Kenneth Rachwalski, et al. Deep learning- soannidg-guiedd discovery of an antibiotic targeting acinetobacter baumannii. Nature Chemical Biology, 19(11)1332--350, 2023.
[8] Amil Merchant, Simon Batzner, Samuel S Schoenholz, Muratahan Aykol, Gowoon Cheon, and Ekin Dogus Cubuk. Scaling deep learning for materials discovery. Nature, 624(7990):80-8) 2023.
[9] Nathan J Szymanski, Bernardus Rendy, Yuxing Fei, Rishi E Kumar, Tanjin He, David Milsted, Matthew McDermott, Max Gallant, Ekin Dogus Cubuk, Amil Merchant, et al. An autonomous laboratory for the accelerated synthesis of novel materials. Nature, 624(7990):86-9)) 2023.
[10] Federico Monti, Fabrizio Frasca, Davide Eynard, Damon Mannion, and Michael M Bron- stein. Fake news detection on social media using geometric deep learning. arXiv preprint arXiv:1902.00663: 2019.
[11] Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey, Journal of Machine Learning Research, 21(70)) 2020.
[12] Antonio Longa, Veronica Lachi, Gabriele Santin, Monica Bianchini, Bruno Lepri, Pietro Lio, Franco Scarselli, and Andrea Passerini. Graph neural networks for temporal graphs: State of the art, open challenges, and opportunities. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
[13] Ming Jin, Huan Yee Koh, Qingsong Wen, Daniele Zambon, Cesare Alippi, Geoffrey I Webb, Irwin King, and Shirui Pan. A survey on graph neural networks for time series: Forecasting, classification, imputation, and anomaly detection. IEEE Transactions on Pottern Analysis and Machine Intelligence, 2024.

---

[14] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 98): 1735-1780, 1997.
[15] Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder- decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1724-1734, 2014.
[16] Aaron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. Wavenet: A generative model for raw audio. arXiv preprint (XXi::6609003999 2016.
[17] Anastasia Borovykh, Sander Bohte, and Cornelis W Oosterlee. Conditional time series forecast- ing with convolutional neural networks. arXiv preprint (Xiv:1703.04691, 2017.
[18] Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. In International Conference on Neural Information Processing, pages 362-373. Springer, 2018.
[19] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural net- work: Data-driven traffic forecasting. In International Conference on Learning Representations, 2018.
[20] Andrea Cini, Ivan Marisca, Daniele Zambon, and Cesare Alippi. Graph deep learning for time series forecasting. ACM Computing Surveys, June 2025. ISSN 0360-0300. doi: 10. 10.1145/ 3742784. Just Accepted.
[21] Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang. Graph wavenet for deep spatial-temporal graph modeling. In Proceedings of the Twenty-Eighte International Joint Conference on Artificial Intelligence, pages 1907-1913. Association for the Advancement of Artificial Intelligence (AAAT), 2019. doi: 10.24963/jjca..20199 20119/444.
[22] Mahdi Khodayar and Jianhui Wang. Spatio-temporal graph deep neural network for short-term wind speed forecasting. IEEE Transactions Sustainable Energy, 10(2):670-681, 2018.
[23] Simone Eandi, Andrea Cini, Slobodan Lukovic, and Cesare Alippi. Spatio-temporal graph neural networks for aggregate load forecasting. In 2022 International Joint Conference on Neural Networks (IJCNN), pages 1-8. IEEE, 2022.
[24] Amol Kapoor, Xue Ben, Luyang Liu, Bryan Perozzi, Matt Barnes, Martin Blais, and Shawn O' Banion. Examining covid-19 forecasting using spatio-temporal gnns. In Proceedings of the 16th International Workshop on Mining and Learning with Graphs (MLG), 2020.
[25] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[26] Filippo Maria Bianchi and Veronica Lachi. The expressive power of pooling in graph neural networks. In A. Oh, Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 7 71603-71618, Curran Associates, Inc., 2023.
[27] Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006.13:: 2020.
[28] Francesco Di Giovanni, James Rowbottom, Benjamin Paul Chamberlain, Thomas Markovich, and Michael M. Bronstein. Understanding convolution on graphs via energies. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
[29] T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303. /0993, 2023.
[30] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
12

---

[31] Jake Topping, Francesco Di Giovanni. Benjamin Paul Chamberlain. Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022.
[32] Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Leurning, pages 7865-7885. PMLR, 2023.
[33] Yoshua Bengio, Patrice Simard, and Paolo Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE transactions neural networks, 5(2):157-166, 1994.
[34] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 1310-1318, Atlanta, Georgia, USA, Jun 2013, PMLR.
[35] Jianfei Gao and Bruno Ribeiro. On the equivalence between temporal and static equivariant graph representations. In International Conference on Machine Learning, pages 7052-7076. PMLR, 2022.
[36] Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. An empirical evaluation of generic convolu- tional and recurrent networks for sequence modeling. /r03v 2018
[37] George EP Box, Gwilym M Jenkins, Gregory C Reinsel, and Greta M Ljung. Time series analysis: forecasting and control. John Wiley & Sons, 2015.
[38] Aliaksei Sandryhaila and José MF Moura. Discrete signal processing on graphs. IEEE transactions on signal processing, 61(7):1644-1656, 2013.
[39] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272 PMLR, 2017.
[40] Ivan Marisca, Cesare Alippi, and Filippo Maria Bianchi. Graph- forecasting with missing data through spatiotemporal downsampling, In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 34846- 34865. PMLR, 2024.
[41] Andrea Cini, Ivan Marisca, Daniele Zambon, and Cesare Alippi. Taming local effects in graph-based spatiotemporal forecasting. In Advances in Neural Information Processing Systems, 2023.
[42] Jacob Bamberger, Benjamin Gutteridge, Scott Le Roux, Michael M. Bronstein, and Xiaowen Dong, On measuring long-range interactions in graph neural networks. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 2770-2789. PMLR, 13-19 Jul 2025.
[43] Francesco Di Giovanni, T. Konstantin Rusch, Michael Bronstein, Andreca Deac, Mare Lackenby, Siddhartha Mishra, and Petar Veličković. How does wer-ssuashing affect the power of gnns? Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
[44] Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: deep learning framework for traffic forecasting. In Proceedings of the 27th International Joint Conference on Artificial Intellgence, pages 3634-3640, 2018.
[45] Yann LeCun, Yoshua Bengio, et al. Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks, 3361(10):1995, 1995.
[46] Victor Garcia Satorras, Syama Sundar Rangapuram, and Tim Januschowski. Multivariate time series forecasting with latent graph inference. arXiv preprint arXiv:2203.0m 03423, 2022.
[47] Andrea Cini, Daniele Zambon, and Cesare Alippi. Sparse graph learning from spatiotemporal time series. Journal of Machine Learning Research, 24(242):1-36, 2023.
13

---

[48] Andrea Cini, Ivan Marisca, Filippo Maria Bianchi, and Cesare Alippi. Scalable spatiotemporal graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence. 37(6): 7218-7226, June 2023. doi: 10.1
[49] Alessio Gravina, Moshe Eliasof, Claudio Gallicchio, Davide Bacciu, and Carola-Bibiane Schönlieb. On oversquashing in graph neural networks through the lens of dynamical systems. Proceedings of the AAAI Conference on Artificial Intelligence, 39(16):16966-166 Apr 2025.
doi: 10.1609/aaii. (at00//aaa.v333i16.. v39116.3388..
[50] Ismaiel Krim, Mohamed Tahar Mezeddek, and Abderrahmane Smail. On powers and roots of triangular toeplitz matrices. Applied Mathematics E-Notes, 22:322-330, 2022.
[51] Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. In International Conference on Learning Representations, 2024.
[52] Federico Barbero, Andrea Banino, Steven Kapturowski, Dharshan Kumaran, João Madeira Araújo, Oleksandr Vitvitskyi, Razvan Pascanu, and Petar Veličković. Transformers need glasses! information over-squashing in language tasks. Advances in Neural Information Processing Systems, 37:981 11-99122, 2024.
[53] Thomas N. Kipf and Max Welling. ceni-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[54] James Atwood and Don Towsley. Diffusiin--onnoluttonaa neural networks. In Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[55] Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint 17X.5:171,.05533, 2017.
[56] Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montufar. Fosr: First-order spectral rewiring for addressing oversquashing in gnns. In The Eleventh International Conference on Learning Representations, 2023.
[57] Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In Aldo Gangemi, Roberto Navigli, Maria-Esther Vidal, Pascal Hitzler, Raphaël Troncy, Laura Hollink, Anna Tordai, and Mchwish Alam, editors, The Semantic Web, pages 593-607, Cham, 2018. Springer International Publishing. ISBN 118-3-319-93417-2
[58] Johannes Gasteiger, Stefan Weiß enberger, and Stephan Günnemann. Diffusion improves graph learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[59] Federico Barbero, Ameya Velingker, Amin Saberi, Michael M. Bronstein, and Francesco Di Giovanni. Locality-aware graph rewiring in GNNs. In The Twelfth International Conference on Learning Representatiinss 2024.
[60] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothig problem for graph neural networks from the topologiaal view. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04) 3445, Apr 2020. doi: 10.1609/ vat...444445444
[61] Domenico Tortorella and Alessio Micheli. Leave graphs alone: Addressing over-squashing without rewiring. In The First Learning on Graphs Conference, 2022.
[62] Alessio Gravina, Davide Bacciu, and Claudio Gallicchio. Anti-symmetric dgn: a stable architecture for deep graph networks. In The Eleventh International Conference on Learning Representations, 2023.
[63] Eugene Vorontsov, Chiheb Trabelsi, Samuel Kadoury, and Chris Pal. On orthogonality and learning recurrent networks with long term dependencies. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3570-3578, PMLR, 06-11 Aug 2017.
14

---

Grinstead and Snell's introduction to [64] Bo Chang, Minmin Chen, Eldad Haber, and Ed H Chi. Antisymmetricmn: A dynamical system view on recurrent neural networks. In International Conference on Learning Representations. 2021.
[65] T. Konstantin Rusch and Siddhartha Mishra. Unicornn: A recurrent model for learning very long time dependencies. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th In- ternational Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 9168-9178 PMLR, 18-2 24 Jul 2021.
[66] Xinyi Wu, Yifei Wang, Stefanie Jegelka, and Ali Jadbabaie. On the emergence of position bias in transformers. arXiv preprini urXiv:2502.0195/ 2025.
[67] Alessio Gravina, Giulio Lovisotto, Claudio Gallicchio, Davide Bacciu, and Claas Grohnfeldt. Long range propagation on continuous-ting dynamic graphs. In Proceedings of the 41st Inter- national Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 16206-16225. PMLR, 21-27 Jul 2024.
[68] Charles Miller Grinstead and James Laurie Snell. probability. Chance Project, 2006.
[69]
Guido Van Rossum and Fred L. Drake. Python 3 Reference Manual. CreateSpace, Scotts Valley, CA, 2009. ISBN 1441412697.
[70] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjic Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024 8035. Curran Associates, Inc., 2019.
[71] Matthias Fey and Jan Lenssen. Fast graph representation learning with pytorch geometric. In ICLR Workshop Representation Learning on Graphs and Manifolds, 2019.
[72] Andrea Cini and Ivan Marisca. Torch spatiotemporal, March 2022. URL httpt:///gthhbbb
timm/ToorchSattioempporo emporal/tsl.
[73] William Falcon and The PyTorch Lightning team. Pytorch lightning, March 2019. URL
https://gi tht.. com/
[74] Omry Yadan. Hydra framework for elegantly configuring complex applications. Github,
2019. URL https: / thub. chtp://accbbookrserrccc//// chyba
[75] Charles R Harris, K Jarrod Millman, Stéfan J Van Der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel Smith, et al. Array programming with numpy. Nature, 585(7825) 2020.
[76] Lukas Biewald. Experiment tracking with weights and biases, 2020. URL https://wwk wandb. comd Software available from wandh.com.
[77] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1120001412.6980, 2014.
[78] Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus). arXiv preprint 0:X1::16006.08415,201 2016.
15

---

Appendix
A
Proofs
This appendix gathers the complete proofs of all theoretical results showcased in the main text. For clarity and ease of reference, we restate each proposition or theorem before providing its corresponding proof. We begin with the results pertaining to TCNs, followed by those related to the sensitivity analysis in MPTCNs.
A.1 Sensitivity bound of TCNs
Theorem 4.1 establishes the sensitivity bound for TCN composed by LT stacked causal convolutional layers TC. The resulting inequality factorises into a model-dependent term (c,w) and a term R dependent instead on the temporal topology. The proof proceeds by induction on the number of layers, bootstrapping from the single-layer Jacobian estimate we provide in Lemma A.I.
Lemma A.I (Single TC layer). Consider a TC layer as in Eq. 10 with kernel size P, and assume that W Il S w for all < P, and that ool S Ca. For each i. E [0, T), the following holds:
0h
S co (R)
oh (0)
Proof. Let h2 be the pre-activation output of the TC layer, such that h." = = (). Since R is lower-triangular and Toeplitz and has lower bandwidth P - 1, i.e. (R) ri-j for S i < P. for indices i,j E T), we have
oh - Oh (0)
ri-j W 0 P
0.
otherwise.
Applying the chain rule through the pointwise non-linearity gives
Oh -
oh
diag (o'
[
0h (0)
Applying the sub-multiplicative property of the spectral norm together with the bounds |o'| S co and (W,, S. w yields
(1)
( ah
(1) s Idiaag (o' (o((
!h!!!
S co cow/lr
= cow (R) 1s
which proves the theorem.
We now use the result in Lemma A.I to prove the bound of Theorem 4.1 for TCN obtained by stacking LT TC layers.
Theorem 4.1. Consider TCN with La successive TC layers in Eq. 10, all with kernel size P. and assume that || [W S w for all p < and S LT, and that |o'| S Cg. For each i, E [0, T), have:
(Lr)
S (c LT
R
Oh
(0)
model
temporal topology
Proof. We fix the number of stacked TC layers to be / = LT and prove the bound by induction on L.
For the base case / 1, Lemma A. gives
(1)
S Co)(R)) = (cow)
(4.1.1)
Th (0)
16

---

so the claim holds for one layer. We assume the bound is true for - 1:
ah (1-1) 1-k
I (c
Vi,k.
(4.1.2)
0h (-}
(0)
For layers, the chain rule gives
ah !) ah
oh,
(1-1)
T-1
0h
ahis ah
(1-1)
k-k
0h
t-k
k=
where the first factor is the base case of a single layer (4.1.1,, and the second one is the induction hypothesis (4.1.2). Substituting these bounds gives
oh i
T-1 ((ow) (R) (R'
Σ
S
ah
k=
T-1
(cow)'
Σ (R--1) )ak R))s
k=0
=coo))(RR))::
which proves the induction.
A.2 Asymptotic of R and sensitivity in MPTCNs
In the following, we provide detailed analysis of the asymptotic behavior of the temporal topology matrix, which characterizes information propagation across time steps in both TCNs and MPTCNs. Afterwards, we provide the sensitivity bound and related proof for the latter.
A.2.1 Asymptotic behavior of R and RN
Proposition 4.2. Let R E RTXT be real, lower-triangular Toeplitz band matrix with lower bandwidth P 1, iee. with (R) = ri-j for S - P, and P 2 2, r1 # O, and To # 0. Then
R
R i0 (R))
for any we have
0(1-(-13) Informally, this means that the final token receives considerably more influence from tokens positioned earlier.
10 R'
0 as
In fact
Proof. Write R roI N. where R is strictly lower-triangular. Because I and N commute, the binomial expansion for commuting matrices gives
R'
r +
LEN,
the sum truncating at T' since N 0. For a fixed row index 2 1, the strictly lower-triangular structure implies (N*) ): O whenever & > i, thus
Σ (1) 1 ro
(R'),0
*
With ls fixed, (1) /k/ll since lim
+ so with some abuse of notation
jk
1- k!
30
rd
k!nk )..
(Nr
1 co.
k=1
Note that it the product of rá and degree i polynomial in therefore in order the behaviour as + co it suffices to study the leading term Trg
&' (N') and the factor of r/. Additionally, due to
17

---

+1==
+-==
+1=
+==
+-=11
L= 30
Influence towards t
10a1
Influence towards
1.0
10
10
0.5
10a
0.0
12
12
Distance from last time step
Distance from last time step
a) Standard convolution (R)
b) Normalized convolution (Ryv
Figure 5: Sensitivity of last-layer representations associated with last time step t to earlier ones in TCNs with L layers and kernel size P 3. The values correspond entries (R") ) for the standard convolution (a) and (R for the normalized convolution (b), with i 2 being the backward distance from t. As depth increases, the standard convolution favors information from earlier steps, while the normalized version asymptotically approaches uniform sensitivity across all steps.
the strictly lower triangular structure of N, we have (N') ri. This follows from the fact that, in directed acyclic graph as the one described by N, there exists unique directed path of length from the i-th node to the sink node O. Each edge along this path contributes multiplicative factor of rı, resulting in total weight of ri for the path. Applying the same reasoning with replaced by j < i, we can study the ratio
(R 3
1
1 [i-j]
O
0,
1 TTO
jレ
I
which proves the proposition.
The proposition that follows shows that the powers R converge to the rank-one matrix 1eg- In probabilistic terms, the normalization turns the temporal topology into absorbing Markov chain whose unique absorbing state is the last time step. Consequently, the influence of any time step t concentrates on t as the depth grows, eventually reaching uniform sensitivity of the last time step over the entire sequence. Fig.5 shows a comparison between the sensitivity curves as function of the (backward) temporal distance from the last time step for increasingly deeper TCNs in the case of standard (a) and normalized (b) convolutions.
Proposition A.2. Let R TR 10 be a positive, real, lower-triangular Toeplitz band matrix with lower bandwidth P 1, i.e., with (R); = Ti-j for S j < P, and let P 2 2, Tı F 0, and + O. We define Ry == diag(R1) -RR-RRRRR R to be the now-normalized matrix R. (1 is the all-ones vector). Then
lim R 1eg
i.e. every row of R converges to ej =
Proof. Since R, is stochastic matrix (every row sum to 1 by construction), we can interpret R the transition matrix of Markov chain on the finite state space {0, 1, ..... T 1}. Because R is tower-triangular we have that state 0 is absorbing, i.e. (Rw Juo ro/ro = 1, hence once the chain reaches 0 never leaves. Moreover, since rı * 0, for every > 0 and j = 1 there is positive probability of moving one step closer to 0, i.e.,
RRN) Dmin(P (P- Tp
0,
Ep=
hence all states 1.2..... 1 are transient. For finite absorbing Markov chain with single absorbing state (0). every state eventually reaches the absorbing state () with probability (Theorem 11.3 from [68]). Thus,
lim R = 1e k
where the i-th row of the limit contains the absorption probabilities starting from state and are all equal to for state 0 and to 0 for the others.
18

---

A.2.2 Sensitivity bounds of MPTCNs
In this subsection, we aim to prove the sensitivity bounds of a MPTCN obtained by stacking L STMP layers defined as Eq. 8-9, where the temporal processing TMP takes the form of a temporal causal convolution, denoted by TC, defined in Eq. 10.
In line with previous work by Di Giovanni et al. [43], for spatial processing, we consider MP the following family of MPNNs:
h = (of + E a"M (no(t-1), 12al--1))
(14)
where @ WW &Rdxd are matrices of learnable weights, (00) is C function, and is pointwise nonlinear activation function. This class includes common MPNNs, such as GCN [53], DCNN [54], GIN [25], and GatedGCN [55]. For this class of function, we make the following assumptions:
Assumption A.3. Given MPNN with L layers, each as in Eq. 14, assume for each layer that
15'1 ce. |
I ou. and
- 6m. We further assume the Jacobian of the message function
((0) w.r.t. the target (v) and neighbor (u) node features to be bounded as ||00(0/ (Oh || S and [as(0) (Do()/Ohm(e ((h
S C2.
Given an MPNN as defined in Eq. 14 and for which Assumption A.3 holds, Di Giovanni et al. [43] established the following sensitivity bound.
Theorem C.1 (from Di Giovanni et al. [43]). Consider an MPNN with L layers, with ce being the Lipschitz constant of the update function after activation and Om and O, being the maximal norms over all weight matrices in the message and update functions, respectively. For 0, u E V we have:
| S (ce0m)) (SL) 1007
model
topology
+ c2 A E RNNN is the message-passing matrix such that the Jucobian of the message function ()))) w.r.t. the target (v) and neighbor (u) node features has bounded norms C1 and C22 respectively.
where = 8u I -1 diag 1A Fm
As done in the previous section prove the bound for TCNs, proceed by induction the number of layers L, and start the analysis by establishing the bound for a single-layer MPTCN in Lemma A.4. The proof takes advantage of the result for TCNs we demonstrated in the previous section (Theorem 4.1) and Theorem C. by Di Giovanni et al. [43] for MPNNs.
Lemma A.4 (Sensitivity bound TTS MPTCN). Consider TTS MPTCN (L = 1) with LT temporal (TMP) layers and Ls spatial (MP) as defined in Eq. 8-9. Assume that each TMP layer satisfies the conditions of Theorem 4,1, I, and each MP layer satisfiex the assumptions in Theorem C. 1. Then, for any v, u E V and j.j E [0, T), the following holds:
ah
0h ((1)
S (ce0m) is (sLL) uy (cow) ET (R
0h 2-1
u(U)
space
time
Proof. Fix u, U E V and i,j E [0, One STMP layer first applics the LT TMP layers node- and then the Lg MP layers time-wise. Thus, for the chain rule, have
0h #()
((I) ah
Σ
Oz
(A.4.1)
u(O] 0h [-i
0z k
LLL ah
WEV
K=
Every MP layer processes each time step separately, hence oh!
"(1) ((ITT) unless
/0
Similarly, every TMP layer processes each node separately, hence 0z,, D2,((())) w = u. Both sums E..A.. therefore collapse, giving
(((TT) u(0)
jah
0 unless
ah
an:y) 021-1
u(LT)
t-j
0h. [0)
dz(((T)
u(L)
19

---

Using uub-mutiplicaaiiityy of the spectral norm, and considering the bounds from Theorem C. for MP layers and Theorem 4.1 for TC layers, we have
ah #()
:-j u(O) Ozulle)
t-1
(ceOm) is (S's) un (cow)(r (R(T)
Building on this result for a single-layer MPTCN, we extend the sensitivity bound for a MPTCN of layers in the following theorem.
Theorem 5.1. Consider an MPTCN with STMP layers, each consisting of LT temporal (TMP) and L5 spatial (MP) layers as defined in E-.8-9. Assume that each TMP layer satisfies the conditions of Theorem I, and each MP layer satisfies the assumptions in Theorem Then, for any U, u E and j.j E [0, T), the following holds:
S (ce0m) (cow) (SLLs) ue
(R!LT)
( u(0)
model
spatiotemporal topology
Proof. We fix the number of STMP layers to be l L and prove the bound by induction on The base case where = 1 follows directly from Lemma A.4, i.c.,
Ōh ((1)
Öh,-
- (c)0m)) (SLs) (cow)+T (R!
(5.1.))
@h
(0)
We assume the bound holds for 1 stacked STMP blocks, for all u, E V and i, E [0;
mll11) ah
S (ce0m) (1-)LS (I-) (S(L-1)(s)
R (1-))T))
(5.1.2)
0h m(0)
For the /-th layer, we apply the chain rule, the triangle inequality, and sub-mulippicaatiitty:
oh v(t)
0h
0h e())
Öh ((-1) k
ah.-.
1 Dh t-k
ah k(0)
WEV k=0
The first term is the base of single outer layer (5.1.1), and the right term is our induction hypothesis (5.1.2), which combined with the triangular incquality proves the induction:
(ce0m) (c.w) (sLs) wv (R!*)
0h a(0]
WEV V k=U
(ce0m) (1-1)bs (1-0m) (cow) (S(1-1)Ls) uw
(R (R(1))LT)
st)
T-1
= (ce0m) Uss (Co
Σ
(S (S(-1))Ts)
(R!T) (R(-)) sk
wEV km@ (SIL-I)ss
(ce0m) (cow)
R
(R-1))RRRR R(T)
= ((((m) U/s (C. (S")s)
(R"TT)
Induction on / establishes the inequality for every S Tı particular for L,, which is exactly the claimed bound.
20

---

(a) RING
(b) LOLLIPOP
Figure 6: RING and LOLLIPOP graphs used in the synthetic experiments. We highlight in green the target node O and show example of a source node O when the spatial distance k is equal to the graph diameter.
B Experiments
All numerical simulations performed regression tasks. For experiments real-world data, the goal is H- H-steps-ahead forecasting. Given a window of T past observations, the forecasting task consists predicting the H future observations at each node, i.c., y x i We consider families of (parametric) models fo such that
bett = (Jo (X,-T;, A,T)), VVEV,
(15)
where 0 is the set of learnable parameters and fi++ the forecasted values node for the interval [1, H). The parameters are optimized using an element-wise cost function, e.g., the MSE:
H #-1
θ = arg min
Σ DEV 1
Σ
x/+il2 1.
(16)
NH
Software & Hardware All the code used for the experiments has been developed with Python [69] and relies on the following open-soure, libraries: Py ToTch [70]; PyTorch Geometric [71]: Torch Spatiotemporal [72]; PyTorch Lightning [73]; Hydra [74]; Numpy [75]. We relied on Weights & Biases [76] tracking and logging experiments. The code to reproduce the experiments available
at gi github.... www.coo//aaaaaa.. wommmarshkaa/////aooaoaaa.aaaaaa ht////paaittpppoooo caamppral-overruuuue -vvrssuushing.
All experiments were conducted on a workstation running Ubuntu 22.04.5 LTS, equipped with two AMD EPYC 7513 CPUs and four NVIDIA RTX A5000 GPUs, each with 24 GB of memory. To accelerate the experimental process, multiple runs were executed parallel, with shared access to both CPU and GPU resources. This setup introduces variability in execution times, even under identical experimental configurations. On average, experiments involving real- dorld datasets required approximately to 2 hours per run, while synthetic experiments when not terminated early due to early-stopping criterion completed within minutes.
Datasets We begin by introducing a of synthetic datasets and tasks specifically designed to highlight the effects of over- in both space and time.
COPYFIRST Each sequence Ii-Ta consists of T = 16 time steps, with values sampled uniformly from the [0. 1] interval. The task is to predict the first element in the sequence, i.e., 24-T+1. We generate 20,000 sequences for training, 320 for validation, and 500 for testing.
COPYLAST This task is analogous to COPYFIRST, but the model is required to predict the last value in the sequence, i.e., Zy. Together with COPYFIRST, these are the datasets used in the experiments in 4.c.4.
Table 3: Statistics of the datasets and considered sliding-window parameters.
Datasets
Type
Nodes
Edges
Time steps
Sampling Rate
Window
Horizon
METR-LA
Directed
207
1,515
34,272
5 minutes
12
12
PEMS FEMS-BAY
Directed
325
2,369
52,128
5 minutes
12
12
EngRAD
Undirected
487
2,297
26,304
hour
24
6
21

---

ROCKETMAN This is the dataset used in the synthetic experiments in Sec.5. We generate graph with a given structure and N 16 nodes. At each node, we generate sequence of T 9 time steps, again sampling values uniformly from the [0, 1] interval. The task is to predict, for target node v, the average value at time step & - i of nodes located exactly & hops away from v. That is, given a spatial distance & E [0, Pj. where D is the graph's diameter, we define the source set Nix (v) as the nodes at shortest-path distance & from v, with No(v) = {v). The label for node is then y = -mENN [W while predictions for all other nodes are masked out. We use the same
split as in the other synthetic tasks. We use as graphs the RING and LOLLIPOP graphs illustrated in Fig. 6. We further show in Fig. 7 the performance of an MPTCN in this dataset with both TTS (7a) and T&S (7b) approaches.
We now present the real-world datasets used in the experiments of Tab. 1. We split datasets into windows of T time steps, and train the models predict the next H observations. We closely follow the setup of previous works [40, 41]. In the following, we report detailed information for experiments on each dataset for completeness.
METR-LA & PEMS-BAY Both are widely popular benchmarks for graph-based spatiotemporal
forecasting. PEMS-BAY contains 6 months of data from 325 traffic sensors in the San Francisco Bay Area, while METR-LA contains 4 months of analogous readings acquired from 207 detectors in the Los Angeles County Highway [19]. We use the same setup as previous works [41, 21, 19] for all the preprocessing steps. As such, we normalize the target variable to have zero mean and unit variance on the training set and obtain the adjacency matrix as a thresholded Gaussian kernel on the road distances [19]. We sequentially split the windows into 70% 70%/10%/ 1////10%//// /20% partitions for training, validation, and testing. respectively. We use encodings of the time of day and day of the week additional input to the model. For METR-LA, we impute the missing values with the last observed value and include a binary mask as an additional exogenous input. Window and horizon lengths are set as T 12 and H 12.
EngRAD The EngRAD dataset contains hourly measurements of 5 different weather variables collected at 487 grid points in England from 2018 to 2020. We use solar radiation as the target variable, while all other weather variables are used as additional inputs, along with encodings of the time of the day and the year. Window and horizon lengths are set as T = 24 and H = 6. We scale satellite radiation in the [0, range and normalize temperature values to have zero mean and unit variance. We do not compute loss and metrics on time steps with zero radiance and follow the protocol of previous work [40] to obtain the graph and training/validatoonlessngg folds.
Training setting We trained all models using the Adam [77] optimizer with an initial learning rate of 0.001, scheduled by a cosine annealing strategy that decays the learning rate to 10-6 over the full training run. Gradients are clipped to maximum norm of 5 to improve stability. For synthetic experiments, we trained for maximum of 150 epochs with early stopping if the validation loss did not improve for 30 consecutive epochs, using we limit each epoch to the first 400 randomly sampled batches in the experiments for Fig. 4. For experiments on real-world datasets, we used the MAE as the loss function, trained for up to 200 epochs with a patience of 50 epochs, and in each epoch randomly sampled without replacement 300 mini-batche of size 64 from the training set.
of size 32. To reduce computational time,
Baselines In the following, we report the hyperparameters used in the experiment for the considered architectures. Whenever possible, we relied on code provided by the authors or available within open-source libraries to implement the baselines.
MPTCN We use d = 64 hidden units and the GELU activation function [78] throughout all layers. As MP, we use the Diffusion Convolution operator from [54]. For the real-world datasets, we compute messages with different weights from both incoming and outgoing neighbors up to 2 hops, done by Li et al. [19]. As the ENCODER, (non-trained) sethoorthogonal d₂ x d matrix, such that the norm of the input is preserved. As the READOUT, use different linear projections for each time step in the forecasting horizon.
upscale the input features through random
GWNet We used the same parameters reported in the original paper [21], except for those con- trolling the receptive field. Being GWNet a convolutional architecture, this was done to ensure that the receptive field covers the whole input sequence. In particular, we used 6 layers with
22

---

(a) RING (P =
(b) RING (P = 3)
(c) LOLLIPOP (P 2)
(d) LOLLIFOP (P 3)
x
-2
Spatial distance
Sancoo rile (%)
5.
50
Temporal distance
Temporal distance
Temporal distance
Temporal distance i
(a) TTS MPTCN
(a) RING (P 2)
(h) RINO (P = 3)
(c) LOLLIPOP (P 2)
(d) LOLLIPO (P
E. SA t -
Spatial distance
Aaccea rite (%)
50
12
25
Temporal distance
Temporal distance
Temporal distance
Temporal distance i
(b) T&S MPTCN
Figure 7: Success rate (%) of MPTCNs on the ROCKETMAN dataset. The tasks vary for the type of graph used (RING LOLLIPOP) and size of P (2 or 3). The plot axes show the source neighbors distance and the temporal distance i.
temporal kernel size and dilation of 3 for EngRAD since the input window has length 24, For the TTS implementation, we compute all message-passing operations stacked at the end of temporal processing, without interleaving any dropout or normalization (as done in the temporal part). The final representation is added through non-trainable skip-connection to the output temporal processing, to mimic the original T&S implementation. The two approaches share the same number of trainable parameters.
C Computational complexity
In this appendix, analyze the computational complexity of MPTCNs with spatiotemporal message passing as defined in 8-10 A summary computational complexities is provided in Tab.4, where omit constant factors and the dependency feature dimension d for clarity.
Naive approach. We begin by analyzing the temporal component Eq.8, where TMP operator implemented stack of causal convolutional layers, each with kernel size P specified in Eq. 10. Each temporal layer performs P matrix-vector multiplications and thus incurs a time complexity of O(Pd)). With LT such layers, the total cost of temporal processing becomes OLL) per node. Since this is applied independently to all N nodes across L outer layers, the cumulative temporal cost is N Pd)). Next, consider the spatial processing in Eq.9, 9, where the MP operator is composed Ls message- mnessage-passing layers, each defined as in Eq. 14. Assuming the message function (!)) involves a matrix multiplication, with complexity ( (d) where [E] is the number of graph edges. Additionally, each layer applies
matrix-vector multiplications per node, one for e() and one for ( Hence, the cost of single message- passsegg layer O(EE)d + 2Nd?). Repeating this over Ls spatial layers, T time steps, and L outer layers results in total spatial cost of O ( Eld + 2Nd))). Combining both components, the overall computational complexity of an MPTCN with number of layers L,, IrT, and Ls, kernel size P, and hidden dimension d is:
O (L LsT([E)d 2Ndd)))
Encoder-decoded architectures, as the STGNNs under study, typically require only the final representation (,(4) to produce the output g². As result, the last STMP layer only
Optimized approach.
23

---

Table 4: Comparison of computational complexity between TTS and T&S under fixed spatial and temporal budgets (Bg- = LLs, By = LLT), and fixed kemnel size P, assuming that each layer's s receptive field satisfies PLT 2 T. The TTS approach achieves a --lold reduction in computation.
TTS (1.=1)
T&S (I,>1)
Naive Optimized
O NBP + B)T O (BTNP Bs(El)
O NB + BBT(E) O ( + E (Bs (s)
requires performing message passing exclusively at the last time step f, using the embeddings H.!)) This reduces the spatial computation at the final layer to O (Ls(EE]d (1 + 2Nd2)) which is a factor of T more efficient than in the naive approach. Assuming that PLT T. i.e., each STMP layer has a temporal receptive field that spans the entire sequence, all preceding STMP layers still require access to all T' time steps and therefore cannot be similarly optimized. Under this assumption, the total complexity becomes:
O (LL + ((L -LL-11444 1)LTT + Ls) (1E)d + +2Nd)).
and simplifies in the case of TTS architecture with - 1 to O (LTNNd + Ls((E)de + 2N If we relax the assumption PLT > T, the T&S method still yields a computational gain over the naive implementation for the layers required cover the full sequence length T. The remaining layers, however, incur the same cost as in the naive case. This results in a moderate speedup, albeit still significantly less efficient than the TTS approach.
D TEMPORALNEIGHHOURSM...T
an adaptation of NEIGHBOURSMATCH [30] to the spatiotemporal setting. In NEIGHBOURSMATCH information is propagated from sender nodes to a root node, and the goal is to classify the root node with the label of the sender node with matching features. We extend this to a spatiotemporal 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 an additional hyperparameter, akin depth in TREENEEGHHBURRS The goal in the FEMPORALNFIGHBOURE. ATCH problem remains to route the correct sender's s label - identified by matching features - to the root node at later step. This task complements our existing synthetic benchmarks, as it emphasizes information compression, i.e., the need to retain and route specific input signals through bottlenecks.
We propose SEMPOORANNIGHHBORRS.......
where the graph topology is tree.
For our experiment, we use which the topology a tree and fixed, while the nonzero leaf features are placed either the initial or the final time step. In Tab. 5, we report test accuracy in the range [0, 1] for varying tree depths and Regarding spatial over-squashing. we observe the same pattern
controlled environment, in
a fixed number of time steps T as in the original experiments of Alon and Yahav [30]. Indeed, accuracy begins to drop at depth 4 and shows substantial degradation at depth 5. Notably, performance is higher at depth when the relevant information appears at the start of the sequence rather than at the end, consistent with our theoretical and empirical findings. However, the large drop in accuracy at depth in both scenarios suggests that the main bottleneck is spatial rather than temporal. This indicates that the task, when combined with a tree-like topology, is limited its ability to capture the nuances of the spatiotemporal bottleneck problem.
Table 5: Test accuracy on TEXMPORALTRRENNEIIIIOORSS...... with varying tree depth and feature position.
TREE DEPTH
FEATURES POSITION
3
First step
1.00 10.00
1.00 +0.00
0.09 10.01
Last step
1.00 +0.01
0.73 +0.46
0.11 +0.08
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Contributions are listed bullet points in the introduction, each clearly pointing to the section where that contribution is made.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: A limitations section has been added to the conclusion to discuss the limitations of the work as well as future directions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
25

---

Answer: [Yes]
Justification: Each Proposition and Theorem clearly state their assumptions. All proofs are found in the appendix, and the best of the authors knowledge, correct.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Experimental results are presented in the main body of the paper, with addi- tional details necessary for reproduction provided in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
26

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
The code reproduce the experiments is available gi github. www/marsska//pppaeeaaocaa pttpspptttttppraaaa www.oooooooooooroosssseeeeee -oversquashing All datasets used can either be generated by the codebase or downloaded from public sources.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm co/
mublic/guide wttpe//ooSSuuumisiioioo ollicy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. wwtppccppccc/ppcpt.ccccccccctcct guwic// CodeSubmisss wwwssssssilloooooeooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The paper follows standard practices established in prior work regarding training and evaluation. All relevant details - such as data splits, hyperparameters, optimizer settings, and selection criteria provided in Appendix B to ensure reproducibility.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Error bars are suitably and correctly defined wherever they are needed (e.g.. tables). For the synthetic experiment, the success rate over multiple experiments was reported as a measure of uncertainty.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
27

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: All details about computer resources and compute time are provided in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https :tttpps://eeeee /ttpe//eess///e//ee//ee
Answer: [Yes]
Justification: The research conducted in the paper conform with the guidelines provided in NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: The paper proposes theoretical analysis of spatiotemporal graph neural architectures, and proposes architectural solutions certain problems that may arise. consequence, the paper does not have direct positive negative societal impact.
28

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not concern data or models that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All code, data, and models used in the paper are properly cited and do not require explicit mention of license and terms of use.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
29

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
All new code is sufficiently documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
30

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "WZh5Yci7eO", "reviewer": "Reviewer_7S5V", "summary": "This paper investigates over-squashing in Spatiotemporal Graph Neural Networks (STGNNs), where information from distant nodes is overly compressed. It formalizes the issue in the spatiotemporal setting and shows that causal convolutions can unintentionally increase sensitivity to distant inputs. Both time-and-space (T&S) and time-then-space (TTS) architectures are equally affected, indicating TTS’s efficiency doesn’t worsen bottlenecks. Results on synthetic and real-world tasks offer insights for alleviating information loss in STGNNs.", "questions": "See Weakness part.", "limitations": "See Weakness part.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n1. The paper tackles an underexplored yet important problem in STGNNs: over-squashing in joint spatiotemporal networks, which has received little rigorous analysis in prior work.\n2. The mathematical formalization of spatiotemporal over-squashing is well-structured, offering a strong theoretical foundation (Sections 4 and 5).\n3. The synthetic experiments effectively validate the theory and enhance interpretability. For instance, Figure 4 clearly illustrates how spatial and temporal bottlenecks affect performance, depending on graph structure and filter size.\n4. The paper provides practical insights, such as the effectiveness of temporal row normalization and dilated convolutions in reducing temporal over-squashing supported by both theoretical and empirical evidence.\n\n### Weakness\n1. Some figures (such as Figure 2) present heatmaps with specialized axes (e.g., “distance from $t$”), but the paper could better guide the reader through their interpretation. More detailed explanations of how the displayed values relate to over-squashing severity would improve accessibility for a broader audience.\n2. While the theoretical equivalence of TTS and T&S architectures in terms of over-squashing is well established, the paper could benefit from a deeper discussion of practical trade-offs, such as optimization stability or data modality that might still make one paradigm preferable in real-world applications.\n3. The analysis focuses entirely on factorized convolutional architectures. Extending or comparing the findings to other popular spatiotemporal models, such as recurrent or Transformer-based architectures [1,2,3,4], would make the study more comprehensive. This is not strictly necessary, but would meaningfully strengthen the paper’s overall contribution.\n\n[1] Liu, Kay, et al. \"Tgtod: A global temporal graph transformer for outlier detection at scale.\" Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, Singapore, 2025.\n\n[2] Wu, Liming, et al. \"Equivariant spatio-temporal attentive graph networks to simulate physical dynamics.\" Advances in Neural Information Processing Systems 36 (2023): 45360-45380.\n\n[3] Xu, Mingxing, et al. \"Spatial-temporal transformer networks for traffic flow forecasting.\" arXiv preprint arXiv:2001.02908 (2020).\n\n[4] Zhang, Tong, et al. \"Spatial–temporal recurrent neural network for emotion recognition.\" IEEE transactions on cybernetics 49.3 (2018): 839-847.", "was_revised": true, "final_justification": "I maintain my positive score.", "rebuttal": "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:\n\n* **W1. Interpretation of heatmaps (Figure 2)**  \n  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.  \n\n* **W2. Practical trade-offs between TTS and T\\&S architectures**  \n  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.  \n\n* **W3. Scope limited to factorized convolutional architectures**  \n  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."}, {"review_id": "CXrI2cV8Zo", "reviewer": "Reviewer_c2D6", "summary": "This paper introduces a formal characterization of over-squashing in Spatiotemporal Graph Neural Networks (STGNNs). It highlights how the temporal dimension amplifies information compression, distinguishing it from static graph over-squashing. The authors demonstrate that convolutional STGNNs counterintuitively favor information propagation from temporally distant points. They prove that both time-and-space (T&S) and time-then-space (TTS) processing paradigms are equally affected by this phenomenon, providing theoretical justification for computationally efficient TTS implementations. The paper validates these findings on synthetic and real-world datasets, offering insights for more effective STGNN designs.", "questions": "1.  Can you further explain why your causal convolution setup reduces sensitivity to recent information? This seems contrary to typical causal convolution properties. How might this impact tasks highly dependent on very recent history?\n\n2.  For dilated convolutions, how can we best choose parameters like $P$ and $M$ to avoid reintroducing over-squashing? Can you elaborate on the specific limitations of row-normalization for STGNN tasks beyond forecasting?\n\n3.  Your claims on TTS vs. T&S equivalence apply to MPTCNs. Do you expect this equivalence to hold for recurrent STGNNs or models with joint space-time filters? I am interested if you you think these results will be generalizable across architectures as I dont seem to find any part of the theorems which are architecture specific\n\nI understand this is mainly a theoretical paper but I felt the experimental section of the paper to be insufficient to empirically prove the claims the authors made in the theoretical sections. \n\nI would be very interested if you could conduct a synthetic sensitivity analysis for the parameters of the proposed mitigation strategies. For dilated convolutions ($R_D$), systematically vary $P$  and $M$ to quantify how they influence the reintroduction of over-squashing patterns (as seen in Figure 2 (b.2) ). For row-normalization ($R_N$), explore its effects on tasks where non-final time steps are crucial, to quantify its specific limitations beyond forecasting.\n\nI think this will add a lot of value to the paper", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1. The paper introduces the concept of over-squashing specifically for Spatiotemporal Graph Neural Networks (STGNNs), a previously unexplored area despite its importance in static GNNs. This is a critical gap addressed. The formal characterization of spatiotemporal over-squashing is a novel and significant theoretical contribution\n2. The theoretical framework is robust. It formally characterizes spatiotemporal over-squashing and provides clear bounds on information propagation for TCNs and MPTCNs. The paper effectively disentangles the spatial and temporal components of over-squashing, which is crucial for understanding STGNNs. The finding that Time-then-Space (TTS) and Time-and-Space (T&S) paradigms are equally affected by over-squashing, despite TTS models offering computational benefits, is a key theoretical insight for practical design.\n3. The theoretical claims are strongly backed by comprehensive empirical evaluations on both synthetic and real-world datasets (METR-LA, PEMS-BAY, EngRAD). The synthetic memory tasks are well-designed to isolate and demonstrate spatiotemporal bottlenecks. The consistent performance of TTS and T&S models in experiments reinforces the theoretical arguments about information bottlenecks.\n4. The paper's counterintuitive discovery that convolutional STGNNs favor information propagation from temporally distant points is a significant finding. This \"temporal over-squashing,\" likened to the attention sink effect in Transformers, offers crucial insights into TCN behavior.\n\n### Weaknesses\n\n 1. The primary focus is on \"factorized convolutional approaches\" (MPTCNs). While relevant, the analysis explicitly excludes recurrent architectures and models with joint space-time filters. This limits the generalizability of the theoretical equivalence between TTS and T&S to the broader STGNN landscape.\n\n2. The statement that causal convolutions \"progressively diminish sensitivity to recent information\" and \"undermine the locality bias\"  needs more detailed explanation. This appears counterintuitive to the common understanding of causal convolutions' role in preserving temporal locality. A deeper dive into the specific mechanism leading to this \"inverted pattern\" within their formulation would enhance clarity.\n\n3. While dilated convolutions and row-normalization are proposed, the discussion on their limitations could be expanded. For instance, the reintroduction of over-squashing with dilated convolution resets (Fig. 2 b.2) warrants a more thorough analysis of optimal parameter selection to mitigate this issue. Similarly, the benefits of row-normalization primarily for forecasting tasks suggest potential limitations for other STGNN applications that are not fully explored.\n\n Minor Visual Clarity in Figure 2: While the text clearly describes the behavior of $R_N$, the visual representation in Figure 2 (c.1 & c.2) for row-normalized convolutions could be slightly clearer in depicting the convergence to a uniform distribution on the first column, as stated in the text and Proposition A.2.", "was_revised": true, "final_justification": "I will maintain my positive score for this paper. The authors provided a thorough and thoughtful rebuttal that successfully addressed my concerns. One key thing is that have committed to making key changes in the final version, including clearer explanations, improved visualizations, and a deeper discussion of the nuances and limitations of their mitigation strategies.\n\nThe paper's core contributions—a novel theoretical framework for over-squashing in STGNNs and the practical insights derived from it—remain strong and compelling.", "rebuttal": "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.\n\n1. **W1 & Q3. Extension to recurrent architectures and models with joint space-time filters**  \n   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.  \n   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.  \n   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.  \n2. **W2 & Q1. Reduced sensitivity towards earlier time steps**  \n   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.  \n3. **W3 & Q2. Limitations of mitigation strategies**  \n   Thank you for highlighting the limitations of the proposed mitigation techniques.  \n    - **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.\n\n    - **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.\n\nWe 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."}, {"review_id": "1YMsbBlv4u", "reviewer": "Reviewer_QFNp", "summary": "This paper investigates the phenomenon of over-squashing in Spatiotemporal Graph Neural Networks (ST-GNNs), where long-range spatial and temporal dependencies are inadequately propagated due to the bottlenecking of information in message passing. The authors theoretically characterize how spatiotemporal over-squashing arises from the interaction between graph topology and temporal resolution, extending prior over-squashing definitions from static GNNs.  Experiments on tailored synthetic memory tasks (Fig. 2–4) and on three traffic-style forecasting benchmarks (METR-LA, PEMS-BAY, EngRAD) confirm the theory and show that row-normalised filters and TTS variants either match or slightly outperform their vanilla or T&S counterparts while being more scalable", "questions": "1. It is clear that the sensitivity is presented by upper-bound, this upper-bound does not offer much in understanding over-squashing issues.  Ideally we shall have a lower-bound.    I understand that this result from [42].  My question here is how this upper-bound can benefit analysis.\n\n2. Author(s) may consider comparing row-normalised MPTCN (TTS) with at least one transformer-style STGNN (e.g., StemGNN or CrossFormer) and with a graph-rewiring baseline such as FoSR or Locality-Aware Rewiring on METR-LA. Report MAE and inference latency.\n\n3. Can the Jacobian factorisation be extended to a joint 2-D convolution (shared kernels over space & time)? A short appendix note or experiment would strengthen the theoretical scope.", "limitations": "The paper lacks a direct discussion of its limitations.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1.\tFirst systematic theory of over-squashing in spatiotemporal GNNs; the factorised Jacobian bound (Theorem 5.1) extends static-graph analyses to a two-axis setting and immediately explains several empirical quirks (sink bias, depth brittleness).\n\n2.\tThe paper extends the definition of over-squashing by formulating a “temporal effective resistance” metric that captures how temporal bottlenecks compound spatial ones. \n\n3.  The paper is clearly written.   The paper is modular (Sec. 4  temporal, Sec. 5 full STGNN), proofs are deferred yet sketched, and a separate limitations paragraph is included. \n\nWeaknesses:\n\n1.\tWhile the definition of temporal effective resistance is interesting, the results can be implied from the existing given by Di Giovanni et al. [42], in fact MPTCN is a combination of two GNN operations.\n\n2. Real-data experiments compare only within the MPTCN family (vanilla vs RN vs Dilation) and Graph WaveNet; no transformer-based STGNNs, diffusion-imputation models or recent graph-rewiring baselines are included, limiting claims of generality.", "was_revised": true, "final_justification": "Thank you the author(s) for your clarification on my previous misunderstanding, taking my suggestion into account and completing several extra experiments which can be revised into the new version of the paper. I have no more questions, and at this stage I support the acceptance of the paper.", "rebuttal": "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.\n\n1. **W1. Relation to results on GNNs**  \n   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.  \n2. **W2. Comparison with non-convolutional models**  \n   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.  \n3. **Q1. Significance of upper-bound analysis**  \n   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.  \n4. **Q2. Comparison with graph-rewiring baselines**  \n   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:  \n     \n   | MP operation   | $R$            | $R_N$          |  \n   |----------------|----------------|----------------|  \n   | DCNN           | 43.50 ± 0.08   | 40.30 ± 0.16   |  \n   | RGCN           | 43.78 ± 0.29   | 41.10 ± 0.11   |  \n   | Original       | 44.47 ± 0.42   | 40.38 ± 0.08   |\n\n   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.  \n   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.  \n5. **Q3. Extension to joint space-time convolution**  \n   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.  \n6. **Discussion of limitations**  \n   > \"The paper lacks a direct discussion of its limitations.\"  \n\n    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.\n\nWe 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.\n\n---\n[1] Karhadkar et al. \"FoSR: First-order spectral rewiring for addressing oversquashing in GNNs.\" arXiv preprint arXiv:2210.11790 (2022).\n[2] Schlichtkrull et al. \"Modeling relational data with graph convolutional networks.\" European semantic web conference. Cham: Springer International Publishing, 2018."}, {"review_id": "opC1cruG1D", "reviewer": "Reviewer_sWQM", "summary": "This paper investigates the over-squashing issue in Spatiotemporal Graph Neural Networks (STGNNs), where information from distant nodes and time steps fails to propagate effectively due to bottlenecks.\n\nThe authors formalize this spatiotemporal over-squashing problem, demonstrating its distinct characteristics from the static case, including a counterintuitive finding that convolutional STGNNs can favor temporally distant information. \n\nTheir theoretical and empirical results show that different architectural paradigms (time-and-space vs. time-then-space) are equally affected, providing justification for computationally efficient designs and offering principled guidance for more effective STGNN architectures.", "questions": "1. The synthetic tasks (COPYFIRST/LAST, k-hop average) are illustrative but do not fully capture the essence of spatiotemporal bottleneck challenges in the same fundamental way as NeighboursMatch in prior work [3]. Could the authors discuss the challenges in designing an analogous 'Spatiotemporal NeighboursMatch' or a similar fundamental task? What would be the key characteristics of such a task (e.g., requiring precise information from specific spatiotemporal locations across bottlenecks)? Even if not fully implemented, a conceptual discussion could be valuable. \n2. This work primarily focuses on temporal rewiring (RD, RN) to address temporal over-squashing. Theorem 5.1 suggests that spatiotemporal over-squashing arises from the combined effects. What would the interplay be between the proposed temporal rewiring strategies and existing spatial graph rewiring techniques? Would applying both be additive, or are there more complex interactions? \n3. Theorem 5.1 provides a compelling theoretical argument for the similar impact of over-squashing on TTS and T&S architectures under the lens of the derived Jacobian bound. However, practical performance can also be influenced by optimization landscapes, expressivity differences not captured by this specific bound, or sensitivity to hyperparameter choices. Could the authors elaborate on the extent to which the empirical results (Table 1, and perhaps unreported ablations) support this equivalence more broadly?", "limitations": "Adequately addressed.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\n1. The paper provides a theoretical foundation for its claims. It formalizes spatiotemporal over-squashing using Jacobian-based sensitivity analysis (Eq. 11, 12) and derives explicit bounds (Theorem 4.1, Theorem 5.1) that clearly separate model parameter contributions from topological contributions (both spatial S and temporal R).\n2. The paper is overall well written, with a clear structure that outlines the problem, contributions, and methodology in a logical flow. It uses consistent notation, helpful visualisations, and intuitive explanations to convey over-squashing, making the technical content accessible.\n\n$~$\n\n## Weaknesses\n\n1. The paper primarily focuses on STGNNs where the temporal component is a Temporal Convolutional Network (TCN). While TCNs are a valid and increasingly popular choice, many STGNNs also employ Recurrent Neural Networks (RNNs) for temporal modeling [1, 2]. The analysis might not directly translate to RNN-based STGNNs, a point acknowledged in the Limitations and future work section but important for contextualizing the paper's scope.\n2.  The issue of over-squashing was clearly demonstrated in static GNNs through the fundamental NeighboursMatch task introduced in prior work [3]. Multiple GNNs were shown to suffer from the issue. However, this paper does not provide any compelling fundamental benchmarks to assess over-squashing in STGNNs.\n3. The core ideas of over-squashing, sensitivity analysis via Jacobians, and graph rewiring are established concepts in the GNN literature, restricting the originality of the work.\n\n$~$\n\nReferences:\n1. Spatio-Temporal Graph Neural Networks: A Survey, In arXiv 2301.10569.\n2. Graph Neural Networks for Temporal Graphs: State of the Art, Open Challenges, and Opportunities, In TMLR 2024.\n3. On the Bottleneck of Graph Neural Networks and its Practical Implications, In ICLR 2021.", "was_revised": true, "final_justification": "After considering the paper, the rebuttal, and discussions, I maintain a borderline recommendation, leaning slightly positive due to the paper's clear theoretical framing and timely focus.\n\nSuggestion: Please include a strong empirical benchmark similar to NeighboursMatch in the final version to better validate the theoretical claims. A preliminary evaluation of recurrent architectures on this task, along with a more in-depth analysis of convolutional models, would significantly enhance the practical impact of the work.", "rebuttal": "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.\n\n1. **W1. Extension to RNN-based STGNNs**  \n   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.  \n2. **W2 & Q1. Designing a Spatiotemporal NeighboursMatch to Complement Propagation Benchmarks**  \n   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.  \n     \n   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.\n\n   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.\n\n   \n\n   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.\n\n   \n\n3. **W3. Originality of the work compared to GNN literature**  \n   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.  \n4. **Q2. Interplay of temporal and spatial rewiring**  \n   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**.  \n5. **Q3. Empirical support for the equivalence of TTS and T\\&S models**  \n   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.\n\nWe 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.\n\n---\n\n[1] Alon, U., & Yahav, E. “On the bottleneck of graph neural networks and its practical implications.” International conference on Learning Representations, 2021  \n[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\\.  \n[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\\."}]

Author rebuttal:

Meta-review: Summary:
This paper investigates the over-squashing issue in spatiotemporal graph neural networks, a problem where distant nodes fail to effectively exchange information. The authors highlight that the temporal dimension in spatiotemporal graphs amplifies this challenge by increasing the amount of information that needs to be propagated. In this work, the authors formally define the spatiotemporal over-squashing problem and demonstrate its unique characteristics compared to the static case. They validate their findings on both synthetic and real-world datasets, providing insights into their operational dynamics and principled guidance for more effective STGNN designs.

Strengths:
1. Over-squashing in spatiotemporal networks is a critical and underexplored problem.
2. The theoretical framework is robust, and its claims are strongly supported by comprehensive empirical evaluations on both synthetic and real-world datasets.
3. The paper is well-written and easy to follow.


Weaknesses:
1. Some parts of the paper, such as Figure 2, require a more detailed illustration.
2. The analysis primarily focuses on "factorized convolutional approaches" (MPTCNs). By explicitly excluding recurrent architectures and models with joint space-time filters, the work limits the generalizability of its theoretical findings to the broader STGNN landscape.
3. The core ideas of over-squashing, sensitivity analysis via Jacobians, and graph rewiring are established concepts in the GNN literature, which somewhat restricts the originality of the work.


This paper addresses the important and underexplored problem of over-squashing in spatiotemporal graph neural networks. While the task is significant, some of its core ideas are established concepts in the existing GNN literature. I recommend that the authors address the issues suggested by the reviewers in their revised version.
Decision: Accept (poster)