To model real-world systems like city-wide traffic networks, power grids, or large-scale social interactions, we must capture two dimensions simultaneously: space (how entities connect) and time (how these connections and states evolve). Spatiotemporal Graph Neural Networks (STGNNs) have become the standard tool for this task. However, as networks grow to encompass thousands of sensors or millions of users, these models hit a severe scalability wall.
The Spatiotemporal Complexity Explosion
The root of the problem is a "square-law" complexity bottleneck. In a traditional STGNN, if a network has $N$ nodes and we track them over $T$ time steps, the computational and memory requirements often scale at $O(N^2)$ or worse—sometimes even reaching cubic complexity, as noted by Yang.
Why does this happen? Traditional architectures tightly interleave spatial message passing with temporal sequencing (such as recurrent loops or attention mechanisms). If a model attempts to compute a unique, dynamic adjacency matrix at every single time step to capture evolving correlations, the parameter count and training time explode (Ma et al.). For a large metropolitan area, calculating these dense, time-varying spatial relationships becomes computationally prohibitive on standard hardware (Jiang et al.).
To build scalable models, researchers have developed three primary strategies: decoupling, structural sparsification, and one-shot propagation.
Strategy 1: Breaking the Quadratic Barrier via Decoupling
If a model can separate long-term historical trends from immediate, real-time spatial interactions, it can bypass the $O(N^2)$ bottleneck entirely.
A prime example of this strategy is the BigST framework designed by Han et al.. BigST achieves linear complexity $O(N)$ by completely decoupling long-term historical data processing from real-time prediction. Instead of running expensive graph convolutions across every historical step, it employs a linearized spatial convolution that scales gracefully with the number of nodes.
Similarly, Shao et al. introduced D2STGNN, which decouples traffic signals into two distinct components: spatial diffusion (vehicles moving between sensors) and inherent local traffic. By separating these signals, specialized, more efficient modules can process them independently, avoiding the need to compute massive, fully connected dynamic adjacency matrices for the entire network.
Traditional STGNN:
[Spatial Message Passing] ──> [Temporal RNN/Attention] ──> [Spatial Message Passing] ==> O(N²) per time step
Decoupled STGNN (e.g., BigST, D2STGNN):
[Long-Term History] ───────> [Linearized Spatial Conv] ──> [Real-Time Prediction] ==> O(N) linear scaling
Another elegant approach to decoupling is the Scalable Graph Predictor (SGP) developed by Cini et al.. Instead of training heavy recurrent layers over complex graph structures—which typically incurs quadratic complexity relative to both time series length and edge count—SGP combines training-free randomized recurrent networks (reservoir computing) with efficient graph-signal propagation. This allows the architecture to be highly parallelized, making it orders of magnitude faster and more memory-efficient while maintaining high forecasting accuracy.
Strategy 2: Structural Pruning and Temporal Sparsification
Another intuitive way to scale temporal graphs is to reduce the amount of data the network has to process in the first place. Real-world dynamic graphs are often dense and continuously growing, creating massive computational overhead (TRicci). However, not every edge or time step contains unique information.
The TRicci framework (TRicci) leverages a geometric concept called temporal Forman-Ricci curvature to prune dynamic graphs. By identifying and retaining only the most "informative" edges—those providing strong structural support rather than redundant local competition—TRicci can eliminate up to 80% of the edges. This structural sparsification slashes downstream training and inference times by over 55% while preserving nearly all of the original predictive performance.
Rather than treating every time step as an isolated snapshot, which scales poorly as time intervals increase, Cong et al. proposed DyFormer. The authors construct a "temporal-union" graph structure combined with intelligent node sampling. This allows a Transformer-based architecture to scale efficiently over long temporal horizons without succumbing to the standard scalability walls of snapshot-based dynamic graph processing.
Strategy 3: One-Shot Generation and Propagation
Scalability bottlenecks also plague generative models and random-walk algorithms on dynamic networks. Traditionally, generating dynamic graphs or computing node similarities required simulating thousands of temporal random walks, a process that is slow and computationally expensive (Li et al.; Han et al.).
To bypass this, Li et al. designed VRDAG (Variational Recurrent Dynamic Attributed Graph Generator). Instead of relying on iterative, step-by-step random-walk sampling, VRDAG uses a "one-shot" variational recurrent architecture. By generating the evolving graph structure and attributes in a single unified pass, it accelerates synthetic data generation by up to four orders of magnitude without sacrificing graph quality.
Key Foundational Work
Kernel-based reconstruction of space-time functions via extended graphs (2016) — contributed 1 concept elements to this direction.
Reachability Analysis and Modeling of Dynamic Event Networks (2012) — contributed 1 concept elements to this direction.