EMAGN: Efficient Multi-Attention Graph Network via Learned Clustering for Scalable Traffic Forecasting

# EMAGN: Efficient Multi-Attention Graph Network via Learned Clustering for Scalable Traffic Forecasting
Source: [https://arxiv.org/html/2607.13241](https://arxiv.org/html/2607.13241)
Mingxing Xu1\*,Rakesh Chowdary Machineni2\*,Ke Liu3\*,Xi Cheng4, † Chengqi Lu5,Xin Hu2,Lyuhao Chen6,Xiangyu Li7,Junwei You8,Oliver Gao4 1Shanghai Jiao Tong University2University of Michigan, Ann Arbor3University of California, Berkeley 4Cornell University5Technische Universität Dresden 6Carnegie Mellon University7The University of Texas at Austin8University of Wisconsin–Madison

###### Abstract

Traffic forecasting is highly challenging due to complex and nonlinear spatial and temporal dependencies\. Self\-attention mechanisms have been widely adopted to model dynamic and long\-range dependencies, achieving state\-of\-the\-art performance, but suffer from limited scalability due to quadratic computational and memory complexity\. To address this, we propose an Efficient Multi\-Attention Graph Network \(EMAGN\) that linearises the spatial attention mechanism itself, inspired by the theory of fast high\-dimensional Gaussian filtering\. Two learned clustering matricesCkC\_\{k\}andCvC\_\{v\}adaptively group key and value vectors intoMMsuper\-clusters, reducing complexity from𝒪​\(N2​d\)\\mathcal\{O\}\(N^\{2\}d\)to𝒪​\(N​M​d\)\\mathcal\{O\}\(NMd\)without sacrificing the flexibility of attention for dynamic dependency modelling\. Experimental results on PEMS\-BAY and METR\-LA show that EMAGN achieves accuracy within 2\.7–3\.2% MAE of full\-attention GMAN while reducing training time by 32%, inference time by 38%, and GPU memory by 58%\. Critically, atK=16K\{=\}16attention heads, full\-attention GMAN runs out of memory on a standard 11 GB GPU entirely while EMAGN continues to operate, demonstrating a categorical expansion of feasible model configurations\. EMAGN also surpasses Linformer and Performer in both accuracy and efficiency within the same backbone, owing to its traffic\-network\-aware adaptive clustering\.

††footnotetext:\*Equal Contributions††footnotetext:†Corresponding author:xc557@cornell\.edu*Keywords*Traffic forecasting⋅\\cdotSelf\-attention⋅\\cdotGraph neural networks⋅\\cdotLinear complexity⋅\\cdotSpatial\-temporal modeling\.

## 1Introduction

With the deployment of affordable traffic sensor technologies, traffic data are growing rapidly, bringing us to the era of transportation big data\. Intelligent Transportation Systems \(ITS\)Moriet al\.\([2015](https://arxiv.org/html/2607.13241#bib.bib4)\)leverage this data for efficient urban traffic control and planning\. Traffic forecasting, namely predicting future traffic conditions \(e\.g\., speeds, volumes, and density\) from historical observations plays a critical role in ITS\. Classical statistical methodsLiuet al\.\([2011](https://arxiv.org/html/2607.13241#bib.bib29)\); Lippiet al\.\([2013](https://arxiv.org/html/2607.13241#bib.bib55)\)rely on stationarity assumptions that are violated by the nonlinear, non\-stationary nature of traffic flow\. Deep learning approaches, from CNNsMaet al\.\([2017](https://arxiv.org/html/2607.13241#bib.bib82)\)and RNNsWu and Tan \([2016](https://arxiv.org/html/2607.13241#bib.bib25)\)to graph neural networksYuet al\.\([2018](https://arxiv.org/html/2607.13241#bib.bib27)\); Liet al\.\([2018](https://arxiv.org/html/2607.13241#bib.bib5)\); Wuet al\.\([2019](https://arxiv.org/html/2607.13241#bib.bib38)\), have progressively improved forecasting accuracy by incorporating spatial structure\. Self\-attention mechanismsVaswaniet al\.\([2017](https://arxiv.org/html/2607.13241#bib.bib85)\)have been widely adopted to model dynamic and long\-range spatial\-temporal dependenciesZhenget al\.\([2020](https://arxiv.org/html/2607.13241#bib.bib36)\); Parket al\.\([2020](https://arxiv.org/html/2607.13241#bib.bib37)\), achieving state\-of\-the\-art performance\. However, these self\-attention\-based models suffer from limited scalability due to the quadratic computational and memory complexity of the self\-attention mechanism\. As illustrated in Fig\.[1](https://arxiv.org/html/2607.13241#S1.F1), pairwise interactions across all elements must be computed, resulting in𝒪​\(N2\)\\mathcal\{O\}\(N^\{2\}\)complexity\. The challenge grows with the addition of multi\-head attention and deeper architectures, though both are essential for high performance on large\-scale networks\. While recent methods such as STAEformerLiuet al\.\([2023](https://arxiv.org/html/2607.13241#bib.bib84)\)and MLCAFormerHeet al\.\([2025](https://arxiv.org/html/2607.13241#bib.bib77)\)continue to advance accuracy through architectural redesign, adaptive embeddings, hierarchical attention, propagation\-delay modelling, the memory bottleneck of quadratic spatial attention itself remains unaddressed\. Despite this well\-known limitation, existing traffic forecasting benchmarks do not report GPU memory consumption in their experimental evaluations, making it impossible to assess the practical deployability of these models on resource\-constrained hardware\.

![Refer to caption](https://arxiv.org/html/2607.13241v1/figure1.png)Figure 1:Illustration of the attention mechanisms\. \(a\) Standard self\-attention with𝒪​\(N2​d\)\\mathcal\{O\}\(N^\{2\}d\)complexity\. \(b\) Fast Gaussian filtering aggregates nearby positions into cluster centers\. \(c\) Our linear\-complexity self\-attention uses learned clustering matricesCkC\_\{k\}andCvC\_\{v\}to compress keys and values, achieving𝒪​\(N​M​d\)\\mathcal\{O\}\(NMd\)complexity whereM≪NM\\ll N\.To alleviate this bottleneck, we propose an Efficient Multi\-Attention Graph Network \(EMAGN\), achieving comparable forecasting performance while being much more efficient and scalable\. A linear\-complexity self\-attention mechanism is developed to model spatial dependencies across elements\. Specifically, we adaptively group and aggregateNNkey vectors intoMMsuper\-key vectors \(super\-value vectors are generated accordingly\), and then dependencies between query and super\-key vectors are calculated, reducing the computational complexity from𝒪​\(N2\)\\mathcal\{O\}\(N^\{2\}\)to𝒪​\(N​M\)\\mathcal\{O\}\(NM\), whereMMis a predefined hyperparameter\. As a result, complexity scales linearly with the size of the traffic network\. Our idea is derived from the fast high\-dimensional Gaussian filtering technique in classical signal processingAdamset al\.\([2010](https://arxiv.org/html/2607.13241#bib.bib59)\)\. The key insight is that value vectors associated with nearby positions can be combined into a single super\-value vector, significantly reducing computational cost while achieving near\-exact filtering performance\. EMAGN builds upon GMANZhenget al\.\([2020](https://arxiv.org/html/2607.13241#bib.bib36)\)as its base architecture, since GMAN explicitly computes fullN×NN\\times Nspatial attention across all sensor pairs, making the quadratic bottleneck most pronounced and the efficiency gain most measurable\. To address the scalability problem, GMAN proposed a group\-spatial attention mechanism that randomly partitions vertices into groups and computes only intra\-group and inter\-group attentions\. However, random grouping does not guarantee performance, and more groups are needed to achieve desirable accuracy\. In contrast, we learn the grouping adaptively during training to exploit the inherent spatial clustering within traffic networks\. Empirically, we find that a small number of learned groups suffices for competitive performance\. The main contributions of this paper are as follows:

- •We propose a linear\-complexity self\-attention mechanism derived from fast high\-dimensional Gaussian filtering, reducing spatial attention complexity from𝒪​\(N2​d\)\\mathcal\{O\}\(N^\{2\}d\)to𝒪​\(N​M​d\)\\mathcal\{O\}\(NMd\)through learned adaptive clustering matricesCkC\_\{k\}andCvC\_\{v\}that are trained end\-to\-end with the forecasting objective\.
- •We develop EMAGN, an efficient multi\-attention graph network for traffic forecasting that achieves accuracy within 2\.7–3\.2% MAE of full\-attention GMAN while reducing training time by 32%, inference time by 38%, and GPU memory by 58% on METR\-LA\.
- •We show that EMAGN expands the feasible configuration space of attention\-based traffic forecasting: atK=16K\{=\}16attention heads, full\-attention GMAN exceeds the memory of a standard 11 GB GPU, while EMAGN continues to operate at 8,568 MB\.
- •We provide the first direct empirical comparison of general linear attention mechanisms, LinformerWanget al\.\([2020a](https://arxiv.org/html/2607.13241#bib.bib51)\)and PerformerChoromanskiet al\.\([2022](https://arxiv.org/html/2607.13241#bib.bib52)\), against full attention on standard traffic benchmarks, demonstrating that EMAGN simultaneously achieves better accuracy and better efficiency than both alternatives\.

## 2Related Work

### 2\.1Traffic flow forecasting

Early deep learning approaches to traffic forecasting employ CNNs to extract spatial features from grid\-converted traffic networksMaet al\.\([2017](https://arxiv.org/html/2607.13241#bib.bib82)\); Zhanget al\.\([2019](https://arxiv.org/html/2607.13241#bib.bib81)\), but this conversion discards the irregular topology inherent to road graphs\. Graph neural networks \(GNNs\) overcome this limitation by operating directly on the network structureScarselliet al\.\([2008](https://arxiv.org/html/2607.13241#bib.bib83)\); Kipf and Welling \([2017](https://arxiv.org/html/2607.13241#bib.bib19)\)\. STGCNYuet al\.\([2018](https://arxiv.org/html/2607.13241#bib.bib27)\)applies spectral graph convolutions, while DCRNN and GraphWaveNetLiet al\.\([2018](https://arxiv.org/html/2607.13241#bib.bib5)\); Wuet al\.\([2019](https://arxiv.org/html/2607.13241#bib.bib38)\)adopt diffusion convolutions on directed graphs to capture directional flow\. These models, however, rely on fixed adjacency matrices and cannot adapt to time\-varying spatial dependencies\. Adaptive\-graph methods such as AGCRNBaiet al\.\([2020](https://arxiv.org/html/2607.13241#bib.bib46)\)and MTGNNWuet al\.\([2020](https://arxiv.org/html/2607.13241#bib.bib47)\)address this by learning the graph structure from data, yet they still depend on local message\-passing and may struggle to capture long\-range spatial interactions\.

Self\-attention mechanisms offer a natural solution to these problems with graph structure data, as they model pairwise dependencies across all nodes regardless of graph distancePanet al\.\([2019](https://arxiv.org/html/2607.13241#bib.bib73)\); Zhenget al\.\([2020](https://arxiv.org/html/2607.13241#bib.bib36)\); Parket al\.\([2020](https://arxiv.org/html/2607.13241#bib.bib37)\); Wanget al\.\([2020b](https://arxiv.org/html/2607.13241#bib.bib39)\)\. GMANZhenget al\.\([2020](https://arxiv.org/html/2607.13241#bib.bib36)\)introduces a graph multi\-attention mechanism with group\-based spatial attention; PDFormerJianget al\.\([2023](https://arxiv.org/html/2607.13241#bib.bib48)\)incorporates propagation delay\-aware attention; STAEformerLiuet al\.\([2023](https://arxiv.org/html/2607.13241#bib.bib84)\)shows that a vanilla Transformer with well\-designed adaptive embeddings can achieve strong results; and MLCAFormerHeet al\.\([2025](https://arxiv.org/html/2607.13241#bib.bib77)\)captures hierarchical spatio\-temporal dependencies via multi\-level causal attention\. Despite their effectiveness, all these models inherit the𝒪​\(N2\)\\mathcal\{O\}\(N^\{2\}\)cost of standard self\-attention, which limits their scalability to large networks\. Recent work has begun to tackle this bottleneck\. BigSTHanet al\.\([2024](https://arxiv.org/html/2607.13241#bib.bib49)\)achieves linear complexity through linearised graph convolutions, and STGformerWanget al\.\([2024](https://arxiv.org/html/2607.13241#bib.bib50)\)reduces cost via a single\-layer high\-order attention design\. However, BigST sacrifices the flexibility of attention by relying on graph convolutions, while STGformer still depends on pre\-computed graph structures\. In this paper, we take a different approach: we derive a linear\-complexity self\-attention mechanism from fast high\-dimensional Gaussian filtering that preserves the full modelling flexibility of attention while scaling linearly with network size\.

### 2\.2Efficient attention mechanisms

The quadratic complexity of standard self\-attentionVaswaniet al\.\([2017](https://arxiv.org/html/2607.13241#bib.bib85)\)has motivated extensive research on efficient alternatives, which can be broadly grouped into three families\.Sparse attentionmethods restrict the attention pattern to a subset of element pairs\. InformerZhouet al\.\([2021](https://arxiv.org/html/2607.13241#bib.bib76)\), for example, selects dominant queries via a KL\-divergence measure to achieve𝒪​\(L​log⁡L\)\\mathcal\{O\}\(L\\log L\)complexity, but its sparse patterns are data\-agnostic and require task\-specific heuristics\.Low\-rank and kernel approximationmethods exploit the low\-rank structure of the attention matrix\. LinformerWanget al\.\([2020a](https://arxiv.org/html/2607.13241#bib.bib51)\)projects keys and values into a lower\-dimensional space, PerformerChoromanskiet al\.\([2022](https://arxiv.org/html/2607.13241#bib.bib52)\)approximates the softmax kernel with positive orthogonal random features, and FMMformerNguyenet al\.\([2021](https://arxiv.org/html/2607.13241#bib.bib56)\)decomposes attention into near\-field and far\-field components inspired by the fast multipole method\. While these methods achieve theoretical linear complexity, they apply fixed or random projection strategies that treat all sequence positions uniformly, without regard to the underlying data structure\. In the traffic forecasting setting, where sensors exhibit strong geographic clustering and spatially structured dependencies, this position\-agnostic treatment leads to suboptimal approximations of the full attention matrix\.Clustering and inducing\-pointmethods are conceptually closest to our work\. Set TransformerLeeet al\.\([2019](https://arxiv.org/html/2607.13241#bib.bib86)\)introduces learnable inducing points to reduce pairwise computations, while NyströmformerXionget al\.\([2021](https://arxiv.org/html/2607.13241#bib.bib54)\)reconstructs the attention matrix from a subset of landmark points via the Nyström approximation\. However, these methods rely on generic clustering or random sampling strategies that are agnostic to the underlying data structure\.

Despite the advances of efficient attention mechanisms, their direct application to spatio\-temporal graph data for traffic forecasting remains limited\. Traffic data also shows unique characteristics \(e\.g\., irregular graph topology, jointly and dynamically evolving spatial and temporal dimensions\) that general\-purpose methods do not explicitly address\. We bridge this gap by deriving a linear\-complexity self\-attention mechanism from the theory of fast high\-dimensional Gaussian filtering, where the clustering matrices are learned end\-to\-end to adapt to the spatial structure of traffic networks\.

## 3Proposed Model

We first derive a linear\-complexity self\-attention mechanism from the theory of fast high\-dimensional Gaussian filtering, then develop the full EMAGN architecture for traffic forecasting\.

### 3\.1Linear\-Complexity Self\-Attention

Standard self\-attention computesX^=Softmax​\(α​Q​KT\)​V\\hat\{X\}=\\text\{Softmax\}\(\\alpha QK^\{T\}\)Vwith𝒪​\(N2​d\)\\mathcal\{O\}\(N^\{2\}d\)complexityVaswaniet al\.\([2017](https://arxiv.org/html/2607.13241#bib.bib85)\), whereQ,K,VQ,K,Vare linearly projected from the input\. This quadratic cost is structurally analogous to naive high\-dimensional Gaussian filtering:

v^i=∑je‖pi−pj‖22​vj,\\hat\{v\}\_\{i\}=\\sum\_\{j\}e^\{\\frac\{\\\|p\_\{i\}\-p\_\{j\}\\\|^\{2\}\}\{2\}\}v\_\{j\},\(1\)wherepip\_\{i\}andviv\_\{i\}are high\-dimensional positions and value vectors, which also requires all\-pairs evaluation\. Fast filtering algorithmsAdamset al\.\([2010](https://arxiv.org/html/2607.13241#bib.bib59)\)reduce this to linear cost by grouping nearby positions intoMMclusters and pre\-aggregating their value contributions, as displayed in Fig\.[1](https://arxiv.org/html/2607.13241#S1.F1)\. Specifically, given cluster centrepcp\_\{c\}, the contribution of all elements in a cluster to a querypip\_\{i\}is approximated via a truncated Taylor expansion as

∑je‖pi−pj‖2/2​vj≈e‖pi−pc‖2/2​Pr​\(‖pi−pc‖2\),\\textstyle\\sum\_\{j\}e^\{\{\\\|p\_\{i\}\-p\_\{j\}\\\|^\{2\}\}/\{2\}\}\{v\_\{j\}\}\\;\\approx\\;e^\{\{\\\|p\_\{i\}\-p\_\{c\}\\\|^\{2\}\}/\{2\}\}\\,P\_\{r\}\(\\\|p\_\{i\}\-p\_\{c\}\\\|^\{2\}\),\(2\)wherePrP\_\{r\}aggregates therr\-th order Taylor terms and can be precomputed per cluster, so that each query attends only toM≪NM\\ll Ncluster summaries rather than allNNelements\.

Self\-attention can be viewed as a generalisation of Gaussian filtering with directed dependencies and a scaled\-product kernel rather than a Gaussian kernel\. Following this analogy, we replace the hand\-crafted clustering of classical filtering with two learnable clustering matricesCk,Cv∈ℝM×NC\_\{k\},C\_\{v\}\\in\\mathbb\{R\}^\{M\\times N\}that are optimised end\-to\-end, allowing the grouping to adapt to the spatial structure of traffic networks\. The resulting linear\-complexity self\-attention is

X^=Softmax​\(α​Q​\(Ck​K\)T\)​Cv​V\.\\hat\{X\}=\\mathrm\{Softmax\}\(\\alpha Q\(C\_\{k\}K\)^\{T\}\)C\_\{v\}V\.\(3\)The attention matrix becomesA=α​Q​\(Ck​K\)T∈ℝN×MA=\\alpha Q\(C\_\{k\}K\)^\{T\}\\in\\mathbb\{R\}^\{N\\times M\}, reducing complexity from𝒪​\(N2​d\)\\mathcal\{O\}\(N^\{2\}d\)to𝒪​\(N​M​d\)\\mathcal\{O\}\(NMd\)\(see Fig\.[1](https://arxiv.org/html/2607.13241#S1.F1)\)\. SinceMMis predefined and independent ofNN, computation scales linearly with network size\. This mechanism can be replicated across multiple heads for richer representational capacity\.

### 3\.2EMAGN for Traffic Forecasting

##### Problem formulation\.

We denote𝒢​\(𝒱,ℰ,W\)\\mathcal\{G\}\(\\mathcal\{V\},\\mathcal\{E\},W\)as the input graph representing a traffic network, where𝒱\\mathcal\{V\}represents the nodes set withNNsensors,ℰ\\mathcal\{E\}is the set of edges reflecting physical connectivity between sensors andW∈ℝN×NW\\in\\mathbb\{R\}^\{N\\times N\}is the adjacency matrix which is usually constructed with the Euclidean distances between sensors via Gaussian kernel\. Formally, givenPPhistorical traffic speeds\[vτ−P\+1,⋯,vτ\]∈ℝP×N×1\[v^\{\\tau\-P\+1\},\\cdots,v^\{\\tau\}\]\\in\\mathbb\{R\}^\{P\\times N\\times 1\}observed by theNNsensors in the traffic network𝒢\\mathcal\{G\}, a traffic forecasting modelℱ\\mathcal\{F\}is learned to predict the nextTTtime step traffic speeds\[v^τ\+1,⋯,v^τ\+T\]\[\\hat\{v\}^\{\\tau\+1\},\\cdots,\\hat\{v\}^\{\\tau\+T\}\]as

v^τ\+1,⋯,v^τ\+T=ℱ​\(vτ−P\+1,⋯,vτ;𝒢\)\.\\hat\{v\}^\{\\tau\+1\},\\cdots,\\hat\{v\}^\{\\tau\+T\}=\\mathcal\{F\}\(v^\{\\tau\-P\+1\},\\cdots,v^\{\\tau\};\\mathcal\{G\}\)\.\(4\)
![Refer to caption](https://arxiv.org/html/2607.13241v1/figure2.png)Figure 2:The architecture of the proposed EMAGN\. Left: overall encoder\-decoder architecture with stacked STBlocks and an alignment module\. Top right: the alignment module computes attention matrixAAfrom past and future embeddings, then transforms encoder outputXs​tX^\{st\}for the decoder\. Bottom right: parallel fusion STBlock where spatial and temporal attention are computed independently and merged via a gated mechanism\.
##### Overall architecture\.

The architecture of the proposed model is illustrated in Fig\.[2](https://arxiv.org/html/2607.13241#S3.F2), consisting of an encoder and decoder\. An alignment module that models the dynamical dependencies between historical and future time steps is also adopted\. The STBlock consists of two modules: one for modeling spatial dependencies and another for modeling temporal dependencies\. Spatial and temporal features are extracted independently within each STBlock and then fused using a gate\. STBlocks are stacked to capture deep spatial and temporal features\. To achieve spatial embedding, the node2vec algorithmGrover and Leskovec \([2016](https://arxiv.org/html/2607.13241#bib.bib78)\)is used to learn the embeddingsDsD\_\{s\}\. For temporal embedding, we encode the day of the week and the time step in a day using one\-hot encoding\. These are then concatenated into a single vector, denoted asDtD\_\{t\}\. The spatial and temporal embeddings are both projected into a fixed\-dimensional vectorD∈ℝdeD\\in\\mathbb\{R\}^\{d\_\{e\}\}using two\-layer fully connected networks\. The learned spatial and temporal embeddings are concatenated with each input feature vector as positional embeddings\.

##### Spatial dependencies modeling\.

We propose adopting a linear\-complexity self\-attention mechanism to model spatial dependencies\. For simplicity, we will use the example of time steptit\_\{i\}for notation\. Especially, for graph representationsXti∈ℝN×\(ds\+de\)X\_\{t\_\{i\}\}\\in\\mathbb\{R\}^\{N\\times\(d\_\{s\}\+d\_\{e\}\)\}that is either traffic speeds information or learned representation from the previous layer augmented with spatial\-temporal embedding\. Three linear projectionsWqs∈ℝ\(ds\+de\)×dqW\_\{q\}^\{s\}\\in\\mathbb\{R\}^\{\(d\_\{s\}\+d\_\{e\}\)\\times d\_\{q\}\},Wks∈ℝ\(ds\+de\)×dkW\_\{k\}^\{s\}\\in\\mathbb\{R\}^\{\(d\_\{s\}\+d\_\{e\}\)\\times d\_\{k\}\}andWvs∈ℝ\(ds\+de\)×dvW\_\{v\}^\{s\}\\in\\mathbb\{R\}^\{\(d\_\{s\}\+d\_\{e\}\)\\times d\_\{v\}\}and two clustering matricesCk∈ℝM×NC\_\{k\}\\in\\mathbb\{R\}^\{M\\times N\}andCv∈ℝM×NC\_\{v\}\\in\\mathbb\{R\}^\{M\\times N\}are learned\. Formally, the updated graph features could be written as

X^ti=Softmax​\(1dk​Xti​Wqs​\(Ck​Xti​Wks\)T\)​Cv​Xti​Wvs\.\\hat\{X\}\_\{t\_\{i\}\}=\\mathrm\{Softmax\}\\\!\\left\(\\frac\{1\}\{\\sqrt\{d\_\{k\}\}\}X\_\{t\_\{i\}\}W\_\{q\}^\{s\}\(C\_\{k\}X\_\{t\_\{i\}\}W\_\{k\}^\{s\}\)^\{T\}\\right\)C\_\{v\}X\_\{t\_\{i\}\}W\_\{v\}^\{s\}\.\(5\)In Eq\. \([5](https://arxiv.org/html/2607.13241#S3.E5)\),Q=Xti​WqsQ=X\_\{t\_\{i\}\}W\_\{q\}^\{s\},K=Ck​Xti​WksK=C\_\{k\}X\_\{t\_\{i\}\}W\_\{k\}^\{s\}andV=Cv​Xti​WvsV=C\_\{v\}X\_\{t\_\{i\}\}W\_\{v\}^\{s\}are the learned query, super\-key and super\-value vectors, respectively\. The key and value vectors are firstly adaptively grouped intoMMclusters before modeling spatial dependencies\. Compared to random grouping, we can achieve better performance with smaller groups\. Multi\-head attention can be further employed for various spatial patterns and the representations are further concatenated and fused with a two\-layer fully connected network\.

##### Temporal dependencies modeling\.

In this study, we also employ a self\-attention mechanism for modeling dynamic and long\-range temporal dependencies\. Specifically, we consider time sequence featuresHvi∈ℝP×\(de\+dt\)H\_\{v\_\{i\}\}\\in\\mathbb\{R\}^\{P\\times\(d\_\{e\}\+d\_\{t\}\)\}of nodeviv\_\{i\}\. The updated time features can be formally written as

H^vi=Softmax​\(1dk​Hvi​Wqt​\(Hvi​Wkt\)T\)​Hvi​Wvt\\hat\{H\}\_\{v\_\{i\}\}=\\mathrm\{Softmax\}\\\!\\left\(\\frac\{1\}\{\\sqrt\{d\_\{k\}\}\}H\_\{v\_\{i\}\}W\_\{q\}^\{t\}\(H\_\{v\_\{i\}\}W\_\{k\}^\{t\}\)^\{T\}\\right\)H\_\{v\_\{i\}\}W\_\{v\}^\{t\}\(6\)whereWqt∈ℝ\(de\+dt\)×dqW\_\{q\}^\{t\}\\in\\mathbb\{R\}^\{\(d\_\{e\}\+d\_\{t\}\)\\times d\_\{q\}\},Wkt∈ℝ\(de\+dt\)×dkW\_\{k\}^\{t\}\\in\\mathbb\{R\}^\{\(d\_\{e\}\+d\_\{t\}\)\\times d\_\{k\}\}andWvt∈ℝ\(de\+dt\)×dvW\_\{v\}^\{t\}\\in\\mathbb\{R\}^\{\(d\_\{e\}\+d\_\{t\}\)\\times d\_\{v\}\}are three linear projection matrices\. As temporal sequences are fixed atT=P=12T=P=12in our setting, the quadratic cost of temporal attention is negligible—𝒪​\(T2​d\)\\mathcal\{O\}\(T^\{2\}d\)withT≪NT\\ll N, and the dominant complexity of EMAGN remains𝒪​\(N​M​d\)\\mathcal\{O\}\(NMd\)in the spatial dimension\. When the sequence grows much larger, linear complexity can be further considered\. Similar to spatial dependencies modeling, multi\-head attention can also be adopted and fused with fully connected networks\.

##### Multi\-step predictions\.

To model the dynamic temporal dependencies between past and future time steps, we employ an additional attention mechanism\. By utilizing spatial and temporal embeddings for input and output time steps as features, we can effectively capture the dynamic temporal dependencies for different nodes\. Formally, letDvip∈ℝT×deD\_\{v\_\{i\}\}^\{p\}\\in\\mathbb\{R\}^\{T\\times d\_\{e\}\}andDvif∈ℝT×deD\_\{v\_\{i\}\}^\{f\}\\in\\mathbb\{R\}^\{T\\times d\_\{e\}\}denote the past and future embeddings of nodeviv\_\{i\}, respectively, then the alignment matrix can be calculated with attention mechanism as

A=Softmax​\(f​\(Dvip\)​\(f​\(Dvif\)\)T\),A=\\mathrm\{Softmax\}\\bigl\(f\(D\_\{v\_\{i\}\}^\{p\}\)\(f\(D\_\{v\_\{i\}\}^\{f\}\)\)^\{T\}\\bigr\),\(7\)whereAAis the alignment matrix andffare learnable linear projections\. In our settingP=TP=T, so both past and future embeddings share the same dimensionality\. The output of encoderXvis​tX\_\{v\_\{i\}\}^\{st\}is then transformed withAAasA​Xvis​tAX\_\{v\_\{i\}\}^\{st\}before fed into decoder\.

## 4Experiments

We evaluate the proposed model on two real\-world benchmark datasets: PEMS\-BAY and METR\-LA\. As METR\-LA is the more challenging benchmark, with higher speed variance \(std 19\.50 vs\. 9\.44 km/h\) and stronger sensitivity to spatial structure, all ablation and scalability analyses are conducted on METR\-LA unless otherwise stated\.

### 4\.1Datasets and Data Preprocessing

PEMS\-BAY consists of 6 months of speed data from 325 sensors in the Bay Area of California, starting from January 1st, 2017 through May 31st, 2017\. METR\-LA consists of traffic data from 207 sensor stations in the California state highway system during weekdays from May through June in 2012\. The data statistics are presented in Table[1](https://arxiv.org/html/2607.13241#S4.T1)\.

Table 1:Dataset statistics\. \# denotes the number of; std denotes the standard deviation of speeds\.Following the common data processing pipeline, traffic speeds are aggregated every five minutes and normalised with Z\-score\. Data are split into 70% training, 10% validation, and 20% testing\. The road topology is encoded as a graph adjacency matrix using pairwise road distances via Gaussian kernel:

Wi​j=\{exp⁡\(−di​j2σ2\),exp⁡\(−di​j2σ2\)\>ϵ0,otherwise,W\_\{ij\}=\\begin\{cases\}\\exp\\\!\\left\(\\tfrac\{\-d\_\{ij\}^\{2\}\}\{\\sigma^\{2\}\}\\right\),&\\exp\\\!\\left\(\\tfrac\{\-d\_\{ij\}^\{2\}\}\{\\sigma^\{2\}\}\\right\)\>\\epsilon\\\\ 0,&\\text\{otherwise,\}\\end\{cases\}\(8\)wheredi​jd\_\{ij\}is the distance between sensorsviv\_\{i\}andvjv\_\{j\},σ\\sigmais the standard deviation andϵ\\epsiloncontrols the sparsity of the adjacency matrix\.

### 4\.2Evaluation Metrics and Baselines

We report mean absolute error \(MAE\), root mean squared error \(RMSE\), and mean absolute percentage error \(MAPE\), respectively, at 15, 30, and 60 minute prediction horizons\. Baselines include graph\-based deep models: STGCNYuet al\.\([2018](https://arxiv.org/html/2607.13241#bib.bib27)\), DCRNNLiet al\.\([2018](https://arxiv.org/html/2607.13241#bib.bib5)\), GraphWaveNetWuet al\.\([2019](https://arxiv.org/html/2607.13241#bib.bib38)\), MTGNNWuet al\.\([2020](https://arxiv.org/html/2607.13241#bib.bib47)\), and STIDShaoet al\.\([2022](https://arxiv.org/html/2607.13241#bib.bib80)\)\. Among Transformer based methods \(†\\dagger\), we compare against PDFormerJianget al\.\([2023](https://arxiv.org/html/2607.13241#bib.bib48)\), STAEformerLiuet al\.\([2023](https://arxiv.org/html/2607.13241#bib.bib84)\), MLCAFormerHeet al\.\([2025](https://arxiv.org/html/2607.13241#bib.bib77)\), and GMANZhenget al\.\([2020](https://arxiv.org/html/2607.13241#bib.bib36)\), the full\-attention model that EMAGN directly improves upon\. For GMAN we adopt the published code with default settings; all remaining baseline results are reported from their original papers\.

### 4\.3Experimental Settings and Model Configurations

All experiments are conducted on an NVIDIA RTX 2080Ti GPU\. Models are trained using the Adam optimiser with an initial learning rate of10−310^\{\-3\}, decaying by a factor of 0\.7 every 5 epochs, and weight decay10−310^\{\-3\}\. Early stopping is applied after 10 consecutive epochs without validation improvement\. We use 12 historical steps to predict the next 15\-, 30\-, and 60\-minutes\. Model depth is set proportional to dataset complexity, with PEMS\-BAY usingL=1L=1STBlock and METR\-LA usingL=5L=5STBlocks, both withK=8K=8attention heads and 8 channels per head\. Unless stated otherwise, EMAGN usesM=4M=4clusters for METR\-LA, determined by the ablation in Section[4\.5](https://arxiv.org/html/2607.13241#S4.SS5)\.

Table 2:MAE, RMSE, and MAPE \(%\) on PEMS\-BAY and METR\-LA\. Top\-2 results per column inbold\.†\\daggerdenotes Transformer\-based methods\.Table 3:Comparison of linear attention mechanisms on METR\-LA at the 60\-minute prediction horizon \(L=5L=5,K=8K=8,M=4M=4\)\.
### 4\.4Experimental Results

Table[2](https://arxiv.org/html/2607.13241#S4.T2)reports MAE, RMSE, and MAPE at the 15\-, 30\-, and 60\-minute horizons on PEMS\-BAY and METR\-LA, respectively\. We design the numerical experiments around three questions: \(i\) how does EMAGN compare in absolute accuracy ? \(ii\) what accuracy–efficiency trade\-off does it achieve? and \(iii\) does its learned\-clustering mechanism outperform other linear attention designs?

#### Accuracy comparison\.

Quadratic\-attention Transformers \(i\.e\., MLCAFormer and STAEformer\) achieve the highest overall accuracy on both benchmarks, benefiting from full𝒪​\(N2\)\\mathcal\{O\}\(N^\{2\}\)pairwise interactions, followed by graph\-based models \(GraphWaveNet, MTGNN\) and the full\-attention GMAN\. EMAGN, operating at𝒪​\(N​M\)\\mathcal\{O\}\(NM\)complexity, incurs a moderate accuracy gap relative to these𝒪​\(N2\)\\mathcal\{O\}\(N^\{2\}\)methods yet remains firmly within the range of established baselines\. On METR\-LA at the 60\-minute horizon, EMAGN achieves an MAE of 3\.54%, placing it within 3\.2% of its full\-attention parent GMAN \(3\.43%\) and on par with GraphWaveNet \(3\.53%\) and DCRNN \(3\.60%\)\. On PEMS\-BAY at 60 min, the gap narrows to 2\.7% MAE \(1\.92% vs\. GMAN’s 1\.87%\), while EMAGN substantially outperforms DCRNN \(2\.07%\) and STGCN \(2\.49%\)\. A noteworthy trend emerges across prediction horizons: the accuracy gap between EMAGN and GMAN consistently shrinks as the forecasting horizon increases—from 5\.1% relative MAE at 15 min to 3\.2% at 60 min on METR\-LA, and from 3\.0% to 2\.7% on PEMS\-BAY\. This suggests that EMAGN’s learned clustering captures the dominant spatial dependencies most critical for long\-range prediction, where modelling global structure matters more than fine\-grained pairwise interactions\.

#### Accuracy–efficiency trade\-off\.

Relative to GMAN, the full\-attention architecture from which EMAGN is derived, our model reduces training time by 32% \(721\.5→489\.4721\.5\\to 489\.4s/epoch\), inference time by 38% \(36\.9→22\.736\.9\\to 22\.7s\), and peak GPU memory by 58% \(10,666→4,47210\{,\}666\\to 4\{,\}472MB\) on METR\-LA \(Table[4](https://arxiv.org/html/2607.13241#S4.T4), rowM=4M\{=\}4vs\. Full\)\. As Section[4\.6](https://arxiv.org/html/2607.13241#S4.SS6)demonstrates, these savings enable model configurations, such asK=16K\{=\}16attention heads, that cause full\-attention GMAN to exceed the memory of a standard 11 GB GPU, whereas EMAGN continues to operate at 8,568 MB\. Quadratic\-attention baselines that achieve higher accuracy \(STAEformer, MLCAFormer\) inherit the same𝒪​\(N2\)\\mathcal\{O\}\(N^\{2\}\)bottleneck and therefore face identical scalability limits\. EMAGN thus occupies a distinct position on the accuracy–efficiency Pareto front: it is the only method that simultaneously achieves accuracy within the range of established graph\-based baselines and guarantees linear\-complexity attention\.

#### Comparison with linear attention alternatives\.

The efficiency gains above could, in principle, be obtained by any linear attention mechanism\. To isolate the contribution of EMAGN’s learned clustering design, we replace its attention module with LinformerWanget al\.\([2020a](https://arxiv.org/html/2607.13241#bib.bib51)\)and PerformerChoromanskiet al\.\([2022](https://arxiv.org/html/2607.13241#bib.bib52)\), two widely adopted linear\-attention methods, within the identical GMAN backbone\. All three linear variants use the same network depth \(L=5L\{=\}5\), head count \(K=8K\{=\}8\), and projection dimension \(m=4m\{=\}4\), ensuring a controlled comparison\. Table[3](https://arxiv.org/html/2607.13241#S4.T3)reports accuracy at 60 min and efficiency on METR\-LA\. EMAGN outperforms both alternatives across all reported metrics\. In accuracy, it surpasses Linformer by 0\.10 MAE \(2\.7% relative\) and Performer by 0\.08 MAE \(2\.2%\); the gap is especially pronounced in MAPE, where EMAGN \(10\.27%\) improves over Performer \(10\.78%\) by 4\.7% relative\. In efficiency, EMAGN consumes 2% less memory \(4,472 vs\. 4,562 MB\) and runs 8% faster at inference \(22\.7 vs\. 24\.7 s\)\. The advantage stems from the fact that Linformer and Performer apply fixed or random projections that treat all positions uniformly, whereas EMAGN learns separate clustering matricesCkC\_\{k\}andCvC\_\{v\}end\-to\-end that can adapt to the spatial structure of the traffic network\.

### 4\.5Ablation Study

#### Influence of the number of clusters\.

A key hyperparameter in EMAGN is the cluster countMM, which controls the trade\-off between approximation quality and computational efficiency\. Table[4](https://arxiv.org/html/2607.13241#S4.T4)lists accuracy and resource consumption asMMvaries from 2 to 128, benchmarked against full𝒪​\(N2\)\\mathcal\{O\}\(N^\{2\}\)attention\.

Table 4:Effect of cluster sizeMMon METR\-LA\. “Full” is standard quadratic self\-attention \(L=5L\{=\}5,K=8K\{=\}8, batch 16\)\.Boldis the default\.Three findings are noteworthy\. First,M=4M=4achieves accuracy essentially on par withM=8M=8\(MAE 2\.91 vs\. 2\.90 at 15 min; 3\.54 vs\. 3\.58 at 60 min\) while using 4,472 MB versus 5,286 MB, and both are far below full attention’s 10,666 MB\. Second, larger cluster sizes \(M=64M=64,M=128M=128\) do not consistently improve over smaller ones and in several cases perform worse\. This behaviour is consistent with the Gaussian filtering analogy: once the learned clusters capture the dominant spatial groupings in the traffic network, additional clusters provide diminishing approximation benefit while increasing compute\. Third, and most significantly, the fact thatM=4M=4matches or exceedsM=128M=128on accuracy confirms that traffic sensor graphs have inherent low\-rank spatial structure\. A small number of learned clusters suffices because sensors naturally group into coherent geographic corridors, a structure that EMAGN discovers end\-to\-end, and that generic low\-rank projections \(Linformer, Performer\) cannot exploit\. We setM=4M=4as the default for METR\-LA\.

### 4\.6Scalability Analysis

Beyond the efficiency gains at existing configurations, EMAGN’s linear complexity enables model configurations that are infeasible under full attention\. We demonstrate this through three controlled scaling experiments on METR\-LA\.

#### Scalability with the Number of STBlocksLL

Table[5](https://arxiv.org/html/2607.13241#S4.T5)shows resource consumption as more STBlocks are stacked\. Both models scale roughly linearly inLL, as expected\. However, EMAGN’s costs are consistently and substantially lower at every depth\. Notably, even atL=1L=1, EMAGN already consumes 58% less memory \(895 MB vs\. 2,133 MB\) and trains 23% faster than GMAN, confirming the efficiency advantage is not a deep\-model artefact but is present at every configuration\. AtL=5L=5, EMAGN requires 489\.4s training time and 4,472 MB memory versus GMAN’s 721\.5s and 10,666 MB, reductions of 32% and 58% respectively\. Within a fixed memory budget, EMAGN can therefore deploy significantly deeper models than GMAN, enabling richer spatial\-temporal feature extraction that is entirely inaccessible under full attention\.

Table 5:Scalability with STBlocksLLon METR\-LA \(K=8K=8,M=4M=4for EMAGN\)\.
#### Scalability with the Number of Attention HeadsKK

Figure[3](https://arxiv.org/html/2607.13241#S4.F3)reports the effect of varying the number of attention headsKK\. AtK=16K\{=\}16, GMAN exceeds the 11 GB GPU memory \(OOM\), whereas EMAGN continues to operate at 954 s training time and 8,568 MB\. At the shared configurationK=8K\{=\}8, EMAGN consumes 58% less memory and runs1\.6×1\.6\{\\times\}faster at inference, confirming that the efficiency advantage grows with the number of attention heads\.

![Refer to caption](https://arxiv.org/html/2607.13241v1/x1.png)Figure 3:Scalability with number of attention headsKKon METR\-LA \(L=5L=5,M=4M=4for EMAGN\)\.OOM: out of memory on a single 11 GB GPU\.
#### Scalability with Traffic Network SizeNN

Figure[4](https://arxiv.org/html/2607.13241#S4.F4)evaluates how costs scale with network sizeNNby sub\-sampling the METR\-LA graph\. At smallNN\(N=10N=10\), both models exhibit similar resource requirements since the quadratic termN2N^\{2\}is negligible\. AsNNgrows, the gap widens significantly and follows the predicted pattern: GMAN’s costs grow steeply while EMAGN’s costs follow a near\-linear trajectory, directly validating the theoretical𝒪​\(N​M\)\\mathcal\{O\}\(NM\)complexity\. AtN=207N=207, EMAGN requires 32% less training time and 58% less memory\. For deployment on larger real\-world networks, city\-scale systems with thousands of sensors, this gap would grow substantially further, making full\-attention models practically infeasible while EMAGN remains deployable\.

![Refer to caption](https://arxiv.org/html/2607.13241v1/x2.png)Figure 4:Scalability with traffic network sizeNNon METR\-LA \(L=5L=5,K=8K=8,M=4M=4for EMAGN\)\.Together, the three scalability analyses consistently confirm that EMAGN achieves its theoretical𝒪​\(N​M\)\\mathcal\{O\}\(NM\)advantage in practice across all three axes of scale\. The efficiency gains are not merely cost reductions at existing configurations, they translate directly into new capabilities: deeper networks, richer multi\-head configurations, and larger\-scale deployments that full\-attention models cannot support within standard hardware budgets\.

## 5Conclusion

In this paper, we proposed EMAGN, an efficient multi\-attention graph network for traffic speed forecasting\. Inspired by the high\-dimensional Gaussian filtering, we developed a linear\-complexity attention mechanism that replaces the𝒪​\(N2\)\\mathcal\{O\}\(N^\{2\}\)pairwise interactions of standard self\-attention with𝒪​\(N​M\)\\mathcal\{O\}\(NM\)operations through learned adaptive clustering\. The EMAGN architecture stacks spatial\-temporal blocks with parallel fusion of spatial and temporal attention, combined with a transform\-attention alignment module for multi\-step prediction\.

Extensive experiments on PEMS\-BAY and METR\-LA demonstrate that EMAGN achieves accuracy closely competitive with the state\-of\-the\-art full\-attention model GMAN, with only a 2\.7–3\.2% MAE gap at the 60\-minute horizon, while reducing training time by 32%, inference time by 38%, and memory consumption by 58%\. Scalability experiments further show that EMAGN supports configurations \(e\.g\., 16 attention heads\) that exceed the memory capacity of full\-attention models\. Ablation studies confirm that as few as 4–8 learned clusters suffice to approximate full pairwise attention, validating the design principle derived from fast Gaussian filtering\. A controlled comparison with Linformer and Performer further shows that learned clustering achieves better accuracy and efficiency than generic linear attention alternatives within the same backbone\.

Future work includes extending the linear attention mechanism to temporal dependencies when dealing with longer historical sequences, exploring adaptive selection of cluster sizeMMduring inference, and evaluating EMAGN on larger city\-scale traffic networks\.

## References

- Fast high\-dimensional filtering using the permutohedral lattice\.Computer Graphics Forum \(Eurographics\)29\(2\),pp\. 753–762\.Cited by:[§1](https://arxiv.org/html/2607.13241#S1.p2.6),[§3\.1](https://arxiv.org/html/2607.13241#S3.SS1.p1.8)\.
- L\. Bai, L\. Yao, C\. Li, X\. Wang, and C\. Wang \(2020\)Adaptive graph convolutional recurrent network for traffic forecasting\.InAdvances in Neural Information Processing Systems,Vol\.33,pp\. 17804–17815\.Cited by:[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p1.1)\.
- K\. Choromanski, V\. Likhosherstov, D\. Dohan, X\. Song, A\. Gane, T\. Sarlos, P\. Hawkins, J\. Davis, A\. Mohiuddin, L\. Kaiser, D\. Belanger, L\. Colwell, and A\. Weller \(2022\)Rethinking attention with performers\.External Links:2009\.14794,[Link](https://arxiv.org/abs/2009.14794)Cited by:[4th item](https://arxiv.org/html/2607.13241#S1.I1.i4.p1.1),[§2\.2](https://arxiv.org/html/2607.13241#S2.SS2.p1.1),[§4\.4](https://arxiv.org/html/2607.13241#S4.SS4.SSSx3.p1.5)\.
- A\. Grover and J\. Leskovec \(2016\)Node2vec: scalable feature learning for networks\.InProceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining,pp\. 855–864\.Cited by:[§3\.2](https://arxiv.org/html/2607.13241#S3.SS2.SSS0.Px2.p1.3)\.
- J\. Han, W\. Zhang, H\. Liu, T\. Tao, N\. Tan, and H\. Xiong \(2024\)Bigst: linear complexity spatio\-temporal graph neural network for traffic forecasting on large\-scale road networks\.Proceedings of the VLDB Endowment17\(5\),pp\. 1081–1090\.Cited by:[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p2.1)\.
- H\. He, Z\. Long, Y\. Zhang, and X\. Jiang \(2025\)Spatio\-temporal transformer traffic prediction network based on multi\-level causal attention\.Plos one20\(9\),pp\. e0331139\.Cited by:[§1](https://arxiv.org/html/2607.13241#S1.p1.1),[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p2.1),[§4\.2](https://arxiv.org/html/2607.13241#S4.SS2.p1.1)\.
- J\. Jiang, C\. Han, W\. X\. Zhao, and J\. Wang \(2023\)PDFormer: propagation delay\-aware dynamic long\-range transformer for traffic flow prediction\.InProceedings of the 37th AAAI Conference on Artificial Intelligence,pp\. 4365–4373\.Cited by:[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p2.1),[§4\.2](https://arxiv.org/html/2607.13241#S4.SS2.p1.1)\.
- T\. N\. Kipf and M\. Welling \(2017\)Semi\-supervised classification with graph convolutional networks\.In5th Int\. Conf\. Learn\. Rep\. \(ICLR\),Toulon, France\.Cited by:[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p1.1)\.
- J\. Lee, Y\. Lee, J\. Kim, A\. Kosiorek, S\. Choi, and Y\. W\. Teh \(2019\)Set transformer: a framework for attention\-based permutation\-invariant neural networks\.InInternational conference on machine learning,pp\. 3744–3753\.Cited by:[§2\.2](https://arxiv.org/html/2607.13241#S2.SS2.p1.1)\.
- Y\. Li, R\. Yu, C\. Shahabi, and Y\. Liu \(2018\)Diffusion convolutional recurrent neural network: data\-driven traffic forecasting\.In6th Int\. Conf\. Learn\. Rep\. \(ICLR\),Vancouver, BC, Canada\.Cited by:[§1](https://arxiv.org/html/2607.13241#S1.p1.1),[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p1.1),[§4\.2](https://arxiv.org/html/2607.13241#S4.SS2.p1.1)\.
- M\. Lippi, M\. Bertini, and P\. Frasconi \(2013\)Short\-term traffic flow forecasting: an experimental comparison of time\-series analysis and supervised learning\.IEEE Transactions on Intelligent Transportation Systems14\(2\),pp\. 871–882\.Cited by:[§1](https://arxiv.org/html/2607.13241#S1.p1.1)\.
- H\. Liu, Z\. Dong, R\. Jiang, J\. Deng, J\. Deng, Q\. Chen, and X\. Song \(2023\)Spatio\-temporal adaptive embedding makes vanilla transformer sota for traffic forecasting\.InProceedings of the 32nd ACM international conference on information and knowledge management,pp\. 4125–4129\.Cited by:[§1](https://arxiv.org/html/2607.13241#S1.p1.1),[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p2.1),[§4\.2](https://arxiv.org/html/2607.13241#S4.SS2.p1.1)\.
- W\. Liu, Y\. Zheng, S\. Chawla, J\. Yuan, and X\. Xing \(2011\)Discovering spatio\-temporal causal interactions in traffic data streams\.InProc\. 17th ACM SIGKDD Int\. Conf\. Knowl\. Disc\. Data Min\.,San Diego, CA, USA,pp\. 1010–1018\.Cited by:[§1](https://arxiv.org/html/2607.13241#S1.p1.1)\.
- X\. Ma, Z\. Dai, Z\. He, J\. Ma, Y\. Wang, and Y\. Wang \(2017\)Learning traffic as images: a deep convolutional neural network for large\-scale transportation network speed prediction\.sensors17\(4\),pp\. 818\.Cited by:[§1](https://arxiv.org/html/2607.13241#S1.p1.1),[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p1.1)\.
- U\. Mori, A\. Mendiburu, M\. Álvarez, and J\. A\. Lozano \(2015\)A review of travel time estimation and forecasting for advanced traveller information systems\.Transportmetrica A: Transport Science11\(2\),pp\. 119–157\.Cited by:[§1](https://arxiv.org/html/2607.13241#S1.p1.1)\.
- T\. Nguyen, V\. Suliafu, S\. Osher, L\. Chen, and B\. Wang \(2021\)Fmmformer: efficient and flexible transformer via decomposed near\-field and far\-field attention\.Advances in neural information processing systems34,pp\. 29449–29463\.Cited by:[§2\.2](https://arxiv.org/html/2607.13241#S2.SS2.p1.1)\.
- Z\. Pan, Y\. Liang, W\. Wang, Y\. Yu, Y\. Zheng, and J\. Zhang \(2019\)Urban traffic prediction from spatio\-temporal data using deep meta learning\.InProceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining,pp\. 1720–1730\.Cited by:[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p2.1)\.
- C\. Park, C\. Lee, H\. Bahng, Y\. Tae, S\. Jin, K\. Kim, S\. Ko, and J\. Choo \(2020\)ST\-grat: a novel spatio\-temporal graph attention networks for accurately forecasting dynamically changing road speed\.InProceedings of the 29th ACM international conference on information & knowledge management,pp\. 1215–1224\.Cited by:[§1](https://arxiv.org/html/2607.13241#S1.p1.1),[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p2.1)\.
- F\. Scarselli, M\. Gori, A\. C\. Tsoi, M\. Hagenbuchner, and G\. Monfardini \(2008\)The graph neural network model\.IEEE transactions on neural networks20\(1\),pp\. 61–80\.Cited by:[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p1.1)\.
- Z\. Shao, Z\. Zhang, F\. Wang, W\. Wei, and Y\. Xu \(2022\)Spatial\-temporal identity: a simple yet effective baseline for multivariate time series forecasting\.InProceedings of the 31st ACM international conference on information & knowledge management,pp\. 4454–4458\.Cited by:[§4\.2](https://arxiv.org/html/2607.13241#S4.SS2.p1.1)\.
- A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, Ł\. Kaiser, and I\. Polosukhin \(2017\)Attention is all you need\.Advances in neural information processing systems30\.Cited by:[§1](https://arxiv.org/html/2607.13241#S1.p1.1),[§2\.2](https://arxiv.org/html/2607.13241#S2.SS2.p1.1),[§3\.1](https://arxiv.org/html/2607.13241#S3.SS1.p1.3)\.
- H\. Wang, J\. Chen, T\. Pan, Z\. Dong, L\. Zhang, R\. Jiang, and X\. Song \(2024\)Stgformer: efficient spatiotemporal graph transformer for traffic forecasting\.arXiv preprint arXiv:2410\.00385\.Cited by:[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p2.1)\.
- S\. Wang, B\. Z\. Li, M\. Khabsa, H\. Fang, and H\. Ma \(2020a\)Linformer: self\-attention with linear complexity\.arXiv preprint arXiv:2006\.04768\.Cited by:[4th item](https://arxiv.org/html/2607.13241#S1.I1.i4.p1.1),[§2\.2](https://arxiv.org/html/2607.13241#S2.SS2.p1.1),[§4\.4](https://arxiv.org/html/2607.13241#S4.SS4.SSSx3.p1.5)\.
- X\. Wang, Y\. Ma, Y\. Wang, W\. Jin, X\. Wang, J\. Tang, C\. Jia, and J\. Yu \(2020b\)Traffic flow prediction via spatial temporal graph neural network\.InProceedings of The Web Conference 2020,pp\. 1082–1092\.Cited by:[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p2.1)\.
- Y\. Wu and H\. Tan \(2016\)Short\-term traffic flow forecasting with spatial\-temporal correlation in a hybrid deep learning framework\.arXiv preprint arXiv:1612\.01022\.Cited by:[§1](https://arxiv.org/html/2607.13241#S1.p1.1)\.
- Z\. Wu, S\. Pan, G\. Long, J\. Jiang, X\. Chang, and C\. Zhang \(2020\)Connecting the dots: multivariate time series forecasting with graph neural networks\.InProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pp\. 753–763\.Cited by:[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p1.1),[§4\.2](https://arxiv.org/html/2607.13241#S4.SS2.p1.1)\.
- Z\. Wu, S\. Pan, G\. Long, J\. Jiang, and C\. Zhang \(2019\)Graph wavenet for deep spatial\-temporal graph modeling\.InProceedings of the Twenty\-Eighth International Joint Conference on Artificial Intelligence,pp\. 1907–1913\.Cited by:[§1](https://arxiv.org/html/2607.13241#S1.p1.1),[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p1.1),[§4\.2](https://arxiv.org/html/2607.13241#S4.SS2.p1.1)\.
- Y\. Xiong, Z\. Zeng, R\. Chakraborty, M\. Tan, G\. Fung, Y\. Li, and V\. Singh \(2021\)Nyströmformer: a Nyström\-based algorithm for approximating self\-attention\.InProceedings of the 35th AAAI Conference on Artificial Intelligence,pp\. 14138–14148\.Cited by:[§2\.2](https://arxiv.org/html/2607.13241#S2.SS2.p1.1)\.
- B\. Yu, H\. Yin, and Z\. Zhu \(2018\)Spatio\-temporal graph convolutional networks: a deep learning framework for traffic forecasting\.InProceedings of the 27th International Joint Conference on Artificial Intelligence,pp\. 3634–3640\.Cited by:[§1](https://arxiv.org/html/2607.13241#S1.p1.1),[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p1.1),[§4\.2](https://arxiv.org/html/2607.13241#S4.SS2.p1.1)\.
- J\. Zhang, Y\. Zheng, J\. Sun, and D\. Qi \(2019\)Flow prediction in spatio\-temporal networks based on multitask deep learning\.IEEE Transactions on Knowledge and Data Engineering32\(3\),pp\. 468–478\.Cited by:[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p1.1)\.
- C\. Zheng, X\. Fan, C\. Wang, and J\. Qi \(2020\)GMAN: a graph multi\-attention network for traffic prediction\.InAAAI,pp\. 1234–1241\.Cited by:[§1](https://arxiv.org/html/2607.13241#S1.p1.1),[§1](https://arxiv.org/html/2607.13241#S1.p2.6),[§2\.1](https://arxiv.org/html/2607.13241#S2.SS1.p2.1),[§4\.2](https://arxiv.org/html/2607.13241#S4.SS2.p1.1)\.
- H\. Zhou, S\. Zhang, J\. Peng, S\. Zhang, J\. Li, H\. Xiong, and W\. Zhang \(2021\)Informer: beyond efficient transformer for long sequence time\-series forecasting\.InProceedings of the AAAI conference on artificial intelligence,Vol\.35,pp\. 11106–11115\.Cited by:[§2\.2](https://arxiv.org/html/2607.13241#S2.SS2.p1.1)\.