# Linear Attention is Enough in Spatial-Temporal Forecasting

arXiv: https://arxiv.org/abs/2408.09158 · HTML: https://mlsanity.com/paper/2408.09158/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 37 of its 66 references that are in the map.
- First posted on arXiv 17 Aug 2024.

## Builds on (most cited first, 30 of 37)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting](https://mlsanity.com/paper/2012.07436/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [Graph WaveNet for Deep Spatial-Temporal Graph Modeling](https://mlsanity.com/paper/1906.00121/) (2019)
- [Enhancing the Locality and Breaking the Memory Bottleneck of Transformer on Time Series Forecasting](https://mlsanity.com/paper/1907.00235/) (2019)
- [Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks](https://mlsanity.com/paper/2005.11650/) (2020)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [GMAN: A Graph Multi-Attention Network for Traffic Prediction](https://mlsanity.com/paper/1911.08415/) (2019)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [Universal Approximation with Deep Narrow Networks](https://mlsanity.com/paper/1905.08539/) (2019)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Spatial-Temporal Transformer Networks for Traffic Flow Forecasting](https://mlsanity.com/paper/2001.02908/) (2020)
- [Discrete Graph Structure Learning for Forecasting Multiple Time Series](https://mlsanity.com/paper/2101.06861/) (2021)
- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [SOFT: Softmax-free Transformer with Linear Complexity](https://mlsanity.com/paper/2110.11945/) (2021)

## Abstract (arXiv)

As the most representative scenario of spatial-temporal forecasting tasks, the traffic forecasting task attracted numerous attention from machine learning community due to its intricate correlation both in space and time dimension. Existing methods often treat road networks over time as spatial-temporal graphs, addressing spatial and temporal representations independently. However, these approaches struggle to capture the dynamic topology of road networks, encounter issues with message passing mechanisms and over-smoothing, and face challenges in learning spatial and temporal relationships separately. To address these limitations, we propose treating nodes in road networks at different time steps as independent spatial-temporal tokens and feeding them into a vanilla Transformer to learn complex spatial-temporal patterns, design STformer achieving SOTA. Given its quadratic complexity, we introduce a variant NSTformer based on Nystrddotom method to approximate self-attention with linear complexity but even slightly better than former in a few cases astonishingly. Extensive experimental results on traffic datasets demonstrate that the proposed method achieves state-of-the-art performance at an affordable computational cost. Our code is available at hrefhttps://github.com/XinyuNing/STformer-and-NSTformerhttps://github.com/XinyuNing/STformer-and-NSTformer.