Abstract
Multivariate time series forecasting is critical for complex systems like urban traffic and sensor networks. While Spatial-Temporal Graph Neural Networks (STGNNs) are effective, they face significant scalability challenges due to $O(N^2)$ complexity in memory and computation as the number of nodes $N$ increases. This paper introduces SAGDFN, a scalable architecture that utilizes "slim" $N \times M$ adjacency matrices ($M \ll N$). By employing Significant Neighbors Sampling (SNS) and Sparse Spatial Multi-Head Attention (SSMA) with $\alpha$-Entmax, SAGDFN filters noise and reduces computational overhead. Experimental results on large-scale datasets with up to 2,000 nodes demonstrate that SAGDFN achieves state-of-the-art accuracy while being significantly faster and more memory-efficient than existing models.
Introduction
Predicting the future of complex, interconnected systems—such as traffic flow across a city or the availability of thousands of parking spots—is a massive computational challenge. While Spatial-Temporal Graph Neural Networks (STGNNs) have become the gold standard for these tasks, they suffer from a "square-law" problem: as the number of sensors ($N$) grows, the memory and compute requirements explode at a rate of $O(N^2)$. This bottleneck often leads to Out-of-Memory (OOM) errors on standard hardware when dealing with thousands of nodes. Furthermore, dense adaptive matrices often introduce "noise"—trivial correlations between unrelated sensors that can degrade forecast accuracy.
Methods
SAGDFN addresses the scalability issue by replacing massive $N \times N$ adjacency matrices with "slim" $N \times M$ matrices. The architecture consists of three core components:
- Significant Neighbors Sampling (SNS): Instead of considering all $N$ neighbors for every node, SAGDFN identifies a subset $M$ of "globally influential" nodes ($M \ll N$). It uses Euclidean distance-based ranking in the embedding space to find which nodes are most representative of the system's dynamics.
- Sparse Spatial Multi-Head Attention (SSMA): Once the $M$ significant nodes are selected, the model uses a multi-head attention mechanism to build a slim adjacency matrix of size $N \times M$. Crucially, it employs the $\alpha$-Entmax function instead of standard Softmax. $\alpha$-Entmax can assign exact zeros to low-correlation pairs, effectively filtering out noise and enforcing sparsity.
- OneStepFastGConv: The researchers integrate this slim matrix into a fast graph convolution operation within an Encoder-Decoder GRU framework. This allows the model to diffuse information across the graph efficiently without ever constructing a full $N \times N$ matrix.
Complexity and Scalability
The theoretical advantage of SAGDFN is evident in its complexity analysis. Traditional adaptive-weight GNNs like AGCRN, GTS, or STEP scale quadratically with the number of nodes $N$. In contrast, SAGDFN scales linearly with $N$ and $M$, significantly reducing the resource footprint.
Experimental Results
The researchers evaluated SAGDFN on four real-world datasets: METR-LA (207 nodes), London2000, NewYork2000, and CARPARK1918 (1,918 nodes).
- Performance: On the 2,000-node datasets (London and New York), SAGDFN outperformed all baselines. On the smaller METR-LA dataset, it achieved performance comparable to top-tier state-of-the-art models.
- Efficiency: On the CARPARK1918 dataset, SAGDFN used only 142,377 parameters, compared to 19.7 million for GTS.
- Speed: SAGDFN’s training time was roughly 7x faster than GTS and 8x faster than D2STGNN on the same hardware. Its inference time was nearly 10x faster than DCRNN.
Conclusion
SAGDFN breaks the scalability barrier in multivariate time series forecasting. By focusing on globally influential nodes and leveraging sparse attention, it provides a robust, efficient solution for large-scale sensor networks. While the selection of the hyperparameter $M$ remains a manual task, the model's ability to handle thousands of nodes on standard hardware represents a significant step forward for practical STGNN applications. Future work may involve automating the selection of $M$ or exploring the "slim matrix" approach in other graph-based domains like recommendation systems.
Summary updated