Research map / Graph learning / GNN architectures
Over-squashing in Spatiotemporal Graph Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Formalizes spatiotemporal over-squashing in convolutional STGNNs, showing causal convolutions favor temporally distant inputs, that TTS and TAS designs are equally affected, and proposes dilated and row-normalized temporal rewiring.
Problem
Over-squashing, a known bottleneck in static GNNs, is unexplored for spatiotemporal GNNs, where information must propagate across both graph and time, compounding compression.
Approach
Extends Jacobian sensitivity analysis to STGNNs: bounds for temporal causal convolutions via powers of a Toeplitz temporal topology matrix show sensitivity to distant time steps grows relative to recent ones, and the space-time bound is multiplicative, so time-then-space (TTS) and time-and-space (TAS) architectures suffer equally. Proposes dilated and row-normalized temporal convolutions as rewiri
Key results
- On the synthetic CopyFirst/CopyLast tasks, standard causal convolutions fail on CopyLast when L_T > 5 due to the sink phenomenon, while row-normalized convolutions mitigate this.
- On ENGRAD, row-normalized temporal convolution (R_N) with L=1 reaches 40.38 MAE vs 44.47 for standard R, and the original GWNet gets 40.50.
- TTS MPTCNs perform comparably to TAS on average on LA, BAY and ENGRAD, with TTS winning most cases; combining FoSR spatial and temporal rewiring gives the best ENGRAD result (40.30 MAE with DCNN).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| row-normalize temporal convolution (ablation) | MPTCN · EngRad | MAE: 44.47{{ $\pm$0.42}} -> 40.38{{ $\pm$0.08}} | Helped |
| row-normalize temporal convolution (ablation) | MPTCN · LA | MAE: 3.14{{ $\pm$0.02}} -> 3.16{{ $\pm$0.01}}; 3.19{{ $\pm$0.02}} -> 3.17{{ $\pm$0.02}} | Mixed |
| row-normalize temporal convolution (ablation) | MPTCN · Bay | MAE: 1.63{{ $\pm$0.01}} -> 1.65{{ $\pm$0.01}}; 1.66{{ $\pm$0.00}} -> 1.65{{ $\pm$0.01}} | Mixed |
| use TTS processing instead of TAS processing (ablation) | MPTCN · LA, Bay, EngRad | MAE | No clear effect |
| add FoSR spatial rewiring (ablation) | TTS MPTCN with standard convolution and DCNN · EngRad | MAE: 44.47{ $\pm$0.42} -> 43.50{ $\pm$0.08} | Helped |
| add FoSR spatial rewiring (ablation) | TTS MPTCN with row-normalized convolution and DCNN · EngRad | MAE: 40.38{ $\pm$0.08} -> 40.30{ $\pm$0.16} | No clear effect |
| use row-normalized temporal convolution instead of standard convolution (ablation) | TTS MPTCN with original graph and DCNN · EngRad | MAE: 44.47{ $\pm$0.42} -> 40.38{ $\pm$0.08} | Helped |
| combine row-normalized temporal convolution and FoSR spatial rewiring (ablation) | TTS MPTCN with DCNN · EngRad | MAE: 44.47{ $\pm$0.42} -> 40.30{ $\pm$0.16} | Helped |
| add FoSR spatial rewiring and use RGCN (ablation) | TTS MPTCN with standard convolution · EngRad | MAE: 44.47{ $\pm$0.42} -> 43.78{ $\pm$0.29} | Helped |
| add FoSR spatial rewiring and use RGCN (ablation) | TTS MPTCN with row-normalized convolution · EngRad | MAE: 40.38{ $\pm$0.08} -> 41.10{ $\pm$0.11} | Hurt |
Surprising findings
- Causal convolutions amplify influence of temporally distant inputs, inverting the usual distance-decay pattern seen in MPNNs.
- Time-then-space architectures are not inherently limited in information propagation compared with time-and-space ones.
Limitations
- Analysis restricted to factorized convolutional STGNNs where space and time do not interact; recurrent and joint space-time filters are not covered.
- Sensitivity bounds are worst-case and potentially conservative.
- Row-normalization mainly benefits final-step forecasting and may be limited for imputation tasks requiring intermediate readouts.
Experimental setup
Datasets: CopyFirst CopyLast RocketMan TemporalNeighboursMatch METR-LA PEMS-BAY ENGRAD
Benchmarks: CopyFirst CopyLast RocketMan METR-LA PEMS-BAY ENGRAD
Metrics: success rate MSE MAE
Baselines: Graph WaveNet (TAS) FoSR rewiring standard causal convolution (R)
Builds on: over-squashing analysis in GNNs (Topping et al. / Di Giovanni et al.) FoSR rewiring Graph WaveNet DCNN diffusion convolution NeighboursMatch
Closest papers by meaning
- Spatio-Spectral Graph Neural Networks (NeurIPS 2024 · similarity 0.89)
- Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.88)
- Graph Neural Networks Do Not Always Oversmooth (NeurIPS 2024 · similarity 0.87)
- On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning (NeurIPS 2025 · similarity 0.87)
- Mitigating Over-squashing without Rewiring: A Sheaf Effective Resistance Perspective (NeurIPS 2026 · similarity 0.87)
- STRAP: Spatio-Temporal Pattern Retrieval for Out-of-Distribution Generalization (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.