Improving Spatio-Temporal Residual Error Propagation by Mitigating Over-Squashing

Technical Summary: Teger – Improving Spatio-Temporal Residual Error Propagation by Mitigating Over-Squashing

Problem Statement
Recurrent models for multivariate time-series forecasting, particularly in Intelligent Transportation Systems (ITS), suffer from residual error propagation. Small prediction inaccuracies compound over time, degrading long-horizon performance. While recent deep learning models effectively parametrize time-varying contemporaneous correlations, they often assume temporal independence of errors and neglect spatial correlations across the observed network. Existing methods, such as TCVAR, model temporal covariance but fail to capture spatial interactions. Furthermore, these models struggle to explicitly capture volatility, leading to miscalibrated uncertainty estimates.

A core theoretical limitation identified is the over-squashing (OQ) phenomenon in Graph Neural Networks (GNNs). OQ occurs when long-range dependencies are excessively compressed into bounded representations, distorting information propagation. In the context of traffic forecasting, this manifests as bottleneck edges (identified by negative discrete curvature) that severely attenuate information flow between distant nodes. Consequently, existing models underestimate cross-region correlations and concentrate dependence along thin chains, failing to model the true spatio-temporal covariance structure of forecast residuals.

Methodology: Teger
The authors propose Teger, a backbone-agnostic probabilistic framework designed to model spatio-temporal residuals on dynamic graphs. Teger integrates a curvature-aware spatial covariance mechanism into a low-rank-plus-diagonal (LRD) noise head, preserving tractable inference via the Woodbury identity.

1. Probabilistic Formulation:
   The model decomposes the time series variable $x_t$ into a predictive mean $\mu_t$ and a stochastic error component $\eta_t \sim \mathcal{N}(0, \Sigma_t)$. To handle large $N$ (number of nodes), the covariance matrix $\Sigma_t$ is parameterized as a low-rank-plus-diagonal form: $\Sigma_t = L_t L_t^\top + \text{diag}(d_t)$.

2. Temporal Correlation:
   Temporal dependencies over a finite horizon $D$ are captured by stacking residuals into a batch vector $\eta^{bat}_t$. The temporal correlation matrix $C_t$ is modeled as a dynamic kernel mixture (similar to TCVAR), where weights are learned via a softmax network.

3. Spatial Correlation and Curvature-Aware Rewiring:
   The core innovation is a curvature-aware spatial precision matrix rewiring mechanism.

   • Bottleneck Identification: The method utilizes Balanced Forman curvature to identify edges acting as information bottlenecks (edges with curvature $\kappa(i, j) \leq -2 + \delta$).
   • Reweighting Strategy: Unlike structural rewiring methods (e.g., LASER) that add or remove edges to create new paths, Teger keeps the input topology fixed. It reweights existing edges based on their curvature. Edges identified as bottlenecks are strengthened using a learnable function: $W'_{ij,t} = W_{ij,t}(1 + \lambda b_{ij,t})$, where $b_{ij,t}$ is a bottleneck score derived from the curvature.
   • Covariance Construction: The reweighted graph Laplacian $L'_t$ is projected into a low-dimensional factor space ($R \ll N$) to construct a spatial precision matrix $Q_t = \alpha I_R + \beta L^{(R)}_t + \sigma_{min} I_R$. The spatial factor covariance is then $G_t = Q_t^{-1}$. This approach admits a closed-form low-rank projection, integrating cleanly into the Woodbury-style covariance update.

4. Inference-Time Refinement:
   To address the underestimation of volatility and propagation of early-step errors, Teger employs a refinement step. It draws next-step residual samples from a Gaussian conditional induced by the model covariance. Crucially, it introduces node-wise volatility scaling, separating the conditional covariance into a dimensionless correlation matrix and an empirical node-wise volatility estimate (via exponential moving average of squared residuals). This prevents double-counting marginal variance while adapting to local volatility.

Key Contributions

1. Dynamic LRD Covariance Model: A probabilistic framework for spatio-temporal residuals that captures spatial dependence via graph-aware latent factors and temporal dependence via an autoregressive structure.
2. Curvature-Based Spatial Mechanism: A novel approach to modeling error diffusion on dynamic graphs using state-aware dynamics and volatility adaptation, specifically targeting the alleviation of over-squashing.
3. Efficient Reweighting Algorithm: An edge-reweighting step embedded in the covariance head that maps the rewired Laplacian into an $R$-dimensional factor space with $O(R^3)$ complexity (vs. $O(N^3)$), representing the first integration of curvature-based rewiring into a probabilistic spatio-temporal forecaster.
4. Unified Framework: Integration of these components into a unified autoregressive framework that maintains computational tractability while expanding the expressiveness of uncertainty modeling.

Experimental Results
The authors evaluated Teger on four real-world spatio-temporal datasets (PeMS03, PeMS04, PeMS07, and Brussels) using four different backbones: LSTM, Transformer, xLSTM, and MTGNN.

• Performance: Teger consistently outperformed baselines, including naive approaches, TCVAR (temporal correlation only), and LASER (structural rewiring), across most forecasting horizons. The primary metric used was the Continuous Ranked Probability Score (CRPS).
• Quantitative Gains: On the Brussels dataset, Teger improved CRPS by 25.3% over LASER. In general, modeling spatial error propagation reduced MAE error magnitude by nearly 30% compared to TCVAR.
• Theoretical Validation: The paper reports improvements in spectral connectivity (spectral gap), reduced effective resistance (Kirchhoff index), and alleviated local bottlenecks (cut conductance) following the rewiring process.
• Interpretability: Qualitative analysis on the Brussels dataset showed that Teger's reweighting preserves the correspondence between graph topology and physical road structure, whereas LASER's added edges sometimes introduced physically unrealistic pathways.

Significance and Claims
The paper claims that Teger addresses a critical gap in probabilistic forecasting: the inability to capture spatio-temporal covariance patterns in residuals, which are intrinsically linked to the over-squashing phenomenon.

• Scope of Claim: The authors are explicit that edge reweighting is a "strictly weaker tool" than structural rewiring (like LASER or SDRF) because it cannot create new long-range pathways where none exist. However, they argue this is well-matched to road-network forecasting where the physical graph is fixed, but edge importances vary over time.
• Theoretical Link: The work provides theoretical evidence connecting curvature-aware rewiring to (i) over-squashing alleviation, (ii) improved spectral connectivity, (iii) reduced effective resistance, and (iv) improved covariance calibration bounds.
• Backbone Agnosticism: Teger requires only the latent state produced by any autoregressive encoder, making it applicable to a wide range of existing models (LSTM, Transformer, xLSTM).

The authors conclude that by mitigating residual error propagation through curvature-aware spatial modeling, Teger achieves more reliable uncertainty quantification and improved long-horizon forecasting performance in complex spatio-temporal systems.