Do We Really Need Graph Neural Networks for Traffic Forecasting?
Spatio-temporal graph neural networks (STGNN) have become the most popular
solution to traffic forecasting. While successful, they rely on the message
passing scheme of GNNs to establish spatial dependencies between nodes, and
thus inevitably inherit GNNs' notorious inefficiency. Given these facts, in
this paper, we propose an embarrassingly simple yet remarkably effective
spatio-temporal learning approach, entitled SimST. Specifically, SimST
approximates the efficacies of GNNs by two spatial learning techniques, which
respectively model local and global spatial correlations. Moreover, SimST can
be used alongside various temporal models and involves a tailored training
strategy. We conduct experiments on five traffic benchmarks to assess the
capability of SimST in terms of efficiency and effectiveness. Empirical results
show that SimST improves the prediction throughput by up to 39 times compared
to more sophisticated STGNNs while attaining comparable performance, which
indicates that GNNs are not the only option for spatial modeling in traffic
forecasting.
Xu Liu, Yuxuan Liang, Chao Huang, Hengchang Hu, Yushi Cao, Bryan Hooi, Roger Zimmermann
# Do We Really Need Graph Neural Networks for Traffic Forecasting?

###### Abstract

Spatio-temporal graph neural networks (STGNN) have become the most popular solution to traffic forecasting. While successful, they rely on the message passing scheme of GNNs to establish spatial dependencies between nodes, and thus inevitably inherit GNNs' notorious inefficiency. Given these facts, in this paper, we propose an embarrassingly simple yet remarkably effective spatio-temporal learning approach, entitled SimST. Specifically, SimST approximates the efficacies of GNNs by two spatial learning techniques, which respectively model local and global spatial correlations. Moreover, SimST can be used alongside various temporal models and involves a tailored training strategy. We conduct experiments on five traffic benchmarks to assess the capability of SimST in terms of efficiency and effectiveness. Empirical results show that SimST improves the prediction throughput by up to 39 times compared to more sophisticated STGNNs while attaining comparable performance, which indicates that _GNNs are not the only option for spatial modeling in traffic forecasting_.

Machine Learning, ICML

## 1 Introduction

In recent years, urban traffic forecasting has emerged as one of the most important components of Intelligent Transportation Systems. Given historical traffic observations (e.g., traffic speed, flow) collected from sensors on road networks, the task focuses on predicting future traffic trends for each sensor, which provides insights for improving urban planning and traffic management (Zheng et al., 2014). Spatio-Temporal Graph Neural Networks (STGNNs) have become the de facto most popular tool for traffic forecasting, in which sequential models such as Temporal Convolution Networks (TCNs) or Recurrent Neural Networks (RNNs) are applied for modeling temporal dependencies (Yu et al., 2018; Pan et al., 2019; Wu et al., 2020; Lan et al., 2022), and Graph Neural Networks (GNNs) (Kipf and Welling, 2017; Defferrard et al., 2016) are utilized to capture spatial correlations among different locations.

After revisiting the STGNNs proposed in recent years, we find that they mostly focus on enhancing the spatial learning modules (i.e., GNNs) with either complex aggregation rules or sophisticated layers to improve predictive performance. While successful, we note that they rely heavily on GNNs for performing the message passing step and thus inevitably inherit GNNs' notorious inefficiencies, especially when the graphs are large or with dense connections (Chen et al., 2021; Zhang et al., 2022). As a concrete example, the commonly used adaptive adjacency matrix is built by matrix multiplication of two node embedding tables, producing a fully-connected graph (Wu et al., 2019; Bai et al., 2020; Han et al., 2021). During feature aggregation, such a fully-connected structure leads to _quadratic_ computational complexity w.r.t. the number of sensors. Consequently, the scalability challenges of GNNs hinder the deployment of STGNNs in large-scale and real-time traffic forecasting systems that are latency-bound and require fast inference.

Although there are plenty of efforts in the graph domain to improve the efficiency of GNNs, such as via graph simplification (Hamilton et al., 2017; Chen et al., 2018; Chiang et al., 2019; Zeng et al., 2020; Zheng et al., 2020), the related studies in STGNNs are still scarce to the best of our knowledge, as such simplification usually leads to information loss and performance degradation (Wu et al., 2020). Given these facts and inspired by recent progress in eliminating GNNs for node classification (Zhang et al., 2022; Tian et al., 2022), we may ask: _can we remove GNNs to trim down the explosive complexity while still remaining competitive in traffic forecasting accuracy?_

Present WorkTo answer this question, we first demonstrate the functionalities of GNNs as follows. The superior performance of GNNs stems from its structure-aware exploitation of graphs: (1) for each node in the graph, a single GNN layer is used to first aggregate features from nodes' neighbors and then transform the aggregated representations via a feed-forward network, and (2) by stacking multiple layers, the hidden representations of nodes receive messages from long-distance neighbors.
In this work, we propose two spatial learning modules to _approximate_ the above efficacies of GNNs without requiring message passing, reducing the time complexity to _linear_. (1) _Local Proximity Modeling_. We take a local view and fragment the traffic network to build an _ego-graph_ for each node, which is constructed by incorporating historical observations of the node's neighbors. Then an MLP is applied to transform the observations to the hidden states at each time step. (2) _Global Correlation Learning_. Inspired by recommender systems that learn user embeddings to reflect user behavioral similarities (He et al., 2017; Zhang et al., 2019), we propose to use sensor embeddings to represent sensors' inherent properties and collaboratively capture spatial relationships between _arbitrary sensor pairs_ in a data-driven manner. Compared with stacking a number of GNN layers to enlarge the receptive field and build long-range spatial dependencies, our module sets up direct connections between nodes and thereby learns the global correlations.

In practice, GNNs can be used alongside various temporal models, such as GRU (Chung et al., 2014), WaveNet (Oord et al., 2016), and Transformer (Vaswani et al., 2017), for spatio-temporal learning. Analogously, we empirically find that our proposed spatial modules are agnostic to the temporal encoders and work in a plug-and-play manner. Moreover, we devise a new training strategy for SimST to further boost performance, which increases sample diversity during batch formation and enhances generalization.

Integrating the above components, we propose a Simple yet effective Spatio-Temporal learning approach termed **SimST**, which _trims the quadratic cost and performs on par with STGNNs in empirical studies_. Our contributions are summarized as follows.

* We for the first time demonstrate that GNNs are not the only choice for spatial modeling in traffic forecasting, by presenting a simple yet admirable method called SimST.
* Despite its simplicity, SimST achieves remarkable empirical results in terms of throughput and accuracy against sophisticated state-of-the-art STGNNs: SimST is significantly more efficient than baselines, with up to \(\mathbf{39}\times\) higher inference throughput, while performing on par with them.
* We conduct ablation and case studies to promote a better understanding of our method and motivate future research to rethink the importance of GNNs in traffic forecasting.

## 2 Related Work

Traffic forecasting is a crucial application in smart city efforts. In recent years, STGNNs have become the most widely used tools for predicting traffic (Cao et al., 2020; Liu et al., 2022; Chen et al., 2021, 2022). Generally, they integrate GNNs with either RNNs or TCNs to capture the spatial and temporal dependencies in traffic data. For example, DCRNN (Li et al., 2018) considered traffic flow as a diffusion process and combined a novel diffusion convolution with GRU. Other efforts (Pan et al., 2019; Fang et al., 2021; Liu et al., 2022) were also based on RNNs. To improve training speed and enjoy parallel computation, plenty of works (Wu et al., 2019, 2020; Li & Zhu, 2021) replaced RNNs with dilated causal convolution.

A fundamental problem for using GNNs in traffic modeling is how to establish a graph structure. The mainstream approach to define such structures is using either a predefined and sparse matrix constructed from the road network distances between sensors (Yu et al., 2018; Li et al., 2018; Song et al., 2020), or an adaptive and dense matrix that records the pairwise relationships between nodes (Wu et al., 2019; Bai et al., 2020; Han et al., 2021; Choi et al., 2022). However, researchers have noted that the predefined matrix is heuristic and does not reflect the genuine dependencies between nodes, which degrades model performance (Wu et al., 2019; Bai et al., 2020). Models applying the adaptive matrix generally achieve superior performance. Though successful, the adaptive matrix discards the sparsity of the graph and incurs a quadratic computational cost, making it hard to deploy for latency-constrained or large-scale traffic applications. Other methods that use attention mechanisms for spatial learning (Zheng et al., 2020) also suffer from quadratic time complexity. In this study, we propose SimST to alleviate the inefficiency issue by eliminating the inefficient GNN component in the model.

## 3 Preliminary

Traffic ForecastingLet \(G=(\mathcal{V},\mathcal{E})\) represent a directed sensor graph with \(|\mathcal{V}|\) nodes and \(|\mathcal{E}|\) edges, and \(\mathbf{X}^{T}\in\mathbb{R}^{|\mathcal{V}|\times\mathcal{V}}\) denote the features of all nodes from time step 1 to \(T\), where \(F\) is the feature dimension. The features usually consist of a target attribute (e.g., traffic speed) and other auxiliary information, such as time of day (Wu et al., 2019). Following common settings (Li et al., 2018; Wu et al., 2019), a weighted adjacency matrix \(\mathbf{A}\in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|}\) is applied to describe the graph topology, where \(\mathbf{A}_{ij}=\exp(-\frac{\mathrm{dist}(v_{i},v_{j})^{2}}{s^{2}})\) if \(\mathrm{dist}(v_{i},v_{j})\leqslant r\) else \(\mathbf{A}_{ij}=0\), \(\mathrm{dist}(v_{i},v_{j})\) denotes the road network distance between sensors \(v_{i}\) and \(v_{j}\), \(s\) is the standard deviation of distances, and \(r\) is a threshold for sparsity (Shuman et al., 2013). The non-zero entries in \(\mathbf{A}\) form the set of edges in \(\mathcal{E}\).

In traffic forecasting, we aim to learn a neural network \(\mathbf{\Theta}\) to predict the target attribute in future \(T_{f}\) steps based on \(T_{h}\) historical observations over the sensor graph:

\[G,\mathbf{X}^{T_{h}}\xrightarrow{\mathbf{\Theta}}\hat{\mathbf{Y}}^{T_{f}} \tag{1}\]

where \(\mathbf{X}^{T_{h}}\in\mathbb{R}^{|\mathcal{V}|\times T_{h}\times F}\) indicates the observations and \(\hat{\mathbf{Y}}^{T_{f}}\in\mathbb{R}^{|\mathcal{V}|\times T_{f}\times 1}\) is the predictions. A prediction loss, e.g.,
mean absolute error, is utilized to train the neural network:

\[\mathcal{L}(\mathbf{\Theta})=\frac{1}{|\mathcal{V}|}\sum_{v_{i}\in\mathcal{V}}|\hat{ \mathbf{Y}}_{v_{i}}^{T_{f}}-\mathbf{Y}_{v_{i}}^{T_{f}}| \tag{2}\]

Graph Neural NetworksAlthough various forms of GNNs exist, our work refers to the conventional message passing scheme (Kipf and Welling, 2017) that is widely adopted in traffic forecasting. Specifically, message passing functions in two ways: aggregating one-hop neighbors to model local correlations, and stacking layers to build long-range relationships. Formally, the node representations \(\mathbf{H}^{l}\) at the \(l\)-th layer of GNNs are learned by first aggregating messages from node neighbors \(\mathcal{N}(v)\), and then transforming the representations via feed-forward propagation:

\[\mathbf{H}^{l}=\sigma(\tilde{\mathbf{A}}\mathbf{H}^{l-1}\mathbf{W}^{l}) \tag{3}\]

where \(\tilde{\mathbf{A}}\) denotes the normalized adjacency matrix, \(\mathbf{W}^{l}\) denotes the learnable weights at the \(l\)-th layer, and \(\sigma\) is the activation function (e.g., ReLU).

## 4 Methodology

As a typical spatio-temporal data mining task, traffic forecasting requires modeling both spatial and temporal aspects. In this section, we start by describing how spatial correlations are set up by the proposed spatial learning modules in Section 4.1. We then introduce three temporal encoders to capture the temporal dependencies and a predictor for generating the future in Section 4.2. Finally, we present a node-based batch sampling method for training SimST in Section 4.3. Figure 1 depicts the architecture of SimST.

### Spatial Learning Modules

The inefficiency of GNNs has been extensively discussed within the graph domain (Chiang et al., 2019; Chen et al., 2021; Zhang et al., 2022). Relying on GNNs to set up spatial correlations via message passing, STGNNs also suffer from flagrant inefficiencies. In this work, we propose two simple yet effective alternatives to approximate the functionalities of GNNs and thus allow each node to exploit spatial information without message passing.

Local Proximity ModelingA single GNN layer is capable of aggregating neighborhood features in a non-Euclidean structure. To consider such a locality characteristic without using a GNN layer, we propose to first perform graph fragmentation to generate an _ego-graph_ for each node. The features of each ego-graph are the \(T_{h}\) steps historical time series of the center node and its one-hop neighbors. Multi-hop neighbors can also be incorporated if needed, but we found that incorporating more neighbors may suffer from overfitting in experiments (see Section 5.4.3). We then transform the raw features at each time step to their hidden representations via a multi-layer perceptron (MLP).

Specifically, for each node \(v\), we consider its top-\(k\) one-hop neighbors based on the weights in the normalized matrix \(\tilde{\mathbf{A}}\), where \(\tilde{\mathbf{A}}=\tilde{\mathbf{D}}^{-\frac{1}{2}}(\mathbf{A}+\mathbf{I})\tilde{\mathbf{D}}^{- \frac{1}{2}}\) and \(\tilde{\mathbf{D}}\) is the degree matrix of \(\mathbf{A}+\mathbf{I}\). We also consider the neighbors in the reversed direction, i.e., the entries in \(\mathbf{A}^{T}\), so that the model can perceive the impact from forward and backward neighbors. Let \(\mathcal{N}_{f}^{1}(v)\) and \(\mathcal{N}_{b}^{1}(v)\) denote the selected one-hop neighbors in two directions. We construct the feature matrix \(\mathbf{X}_{G_{v}}^{T_{h}}\in\mathbb{R}^{T_{h}\times(2k+3)}\) of an ego-graph \(G_{v}\) during period \(T_{h}\):

\[\mathbf{X}_{G_{v}}^{T_{h}}=\text{COMBINE}(\mathbf{X}_{v}^{T_{h}},\{\mathbf{X} _{v_{f}}^{T_{h}}:v_{f}\in\mathcal{N}_{f}^{1}(v)\},\\ \{\mathbf{X}_{v_{b}}^{T_{h}}:v_{b}\in\mathcal{N}_{b}^{1}(v)\},\mathbf{X}_{ avgf}^{T_{h}},\mathbf{X}_{avgg}^{T_{h}}) \tag{4}\]

where the last two terms are the average histories of all one-hop neighbors in two directions, allowing the center node to learn more about its local context. Note that the execution of building ego-graphs can be completed in data preprocessing, so it has no influence on model training and inference. Then, we apply an MLP to transform the raw features in \(\mathbf{X}_{G_{v}}^{T_{h}}\) and generate the representations \(\mathbf{H}_{G_{v}}^{T_{h}}\in\mathbb{R}^{T_{h}\times D_{m}}\), where \(D_{m}\) is the model hidden dimension. Compared with a GNN layer, our module replaces message aggregation (i.e., weighted sum) operation with ego-graph construction that can be finished in the data preprocessing stage.

Figure 1: An overview of SimST from the perspective of a node \(v\) with \(T_{h}\)-step history. Our approach is essentially a single-node architecture (each node is handled individually by the model), which differs from existing STGNNs that require the entire graph as input.
Global Correlation LearningRepresenting users with unique embeddings and learning with these embeddings to capture similarities in behavior among users, is a fundamental technique in recommender systems (He et al., 2017; Zhang et al., 2019). Along a similar line, we argue that the traffic situation of a sensor is largely influenced by its specific position on a road, e.g., on the mainline or on a ramp. This is an intrinsic, time-invariant property of the sensor: hence, we propose to represent it using static sensor location embeddings. During end-to-end training, the embedding table collaboratively learns spatial relationships between _arbitrary node pairs_ in a data-driven manner. Apart from capturing global correlations, this module can serve as a complement to the local proximity modeling function, which is particularly useful when the connections in \(\mathbf{A}\) are noisy (Wu et al., 2019; Bai et al., 2020). A detailed case study is conducted in Section 5.5, where we show that the learned sensor embeddings contain significant information for sensor relevance reasoning.

Compared with stacking multiple GNN layers to enlarge the receptive field and establish long-range correlations, our proposed module uses embedding similarity to reflect the relationships between arbitrary sensor pairs, and thus further considers global knowledge. Moreover, the connections between sensors are built in a direct way, which keeps our module from over-squashing (Alon and Yahav, 2021). As for implementation, we randomly initialize a low-dimensional embedding for each sensor, leading to an embedding table \(\mathbf{E}\in\mathbb{R}^{|\mathcal{V}|\times D_{n}}\), where \(D_{n}\) is the node embedding size. To fuse the embeddings with model hidden representations, we apply an MLP to map \(\mathbf{E}\) to \(\mathbf{H}\in\mathbb{R}^{|\mathcal{V}|\times D_{m}}\).

Complexity ComparisonWe provide a complexity comparison between the spatial learning modules here. As GCN (Kipf and Welling, 2017) is the widely adopted form of GNNs in spatio-temporal models, we take it as a baseline. Suppose a \(L\)-layer GCN with fixed hidden features \(D_{m}\) is applied. For STGNNs applying the predefined adjacency matrix, the time complexity is \(O(L|\mathcal{E}|D_{m}+L|\mathcal{V}|D_{m}^{2})\). When applying the adaptive adjacency matrix that boosts performance, the complexity becomes \(O(L|\mathcal{V}|^{2}D_{m}+L|\mathcal{V}|D_{m}^{2})\). In SimST, the complexity of proximity modeling is \(O(|\mathcal{V}|R)\), where \(R\) is the average degree of nodes. The complexity of correlation learning is \(O(|\mathcal{V}|D_{n}D_{m})\). It is obvious that SimST has lower complexity and is capable of supporting forecasting applications on large-scale sensor networks.

### Temporal Encoder & Predictor

There are several viable options for building the temporal dependencies of a node's history. To demonstrate that SimST can be generalized to various temporal models, we incorporate three basic and popular backbones in this study: GRU (Chung et al., 2014) (RNN-based), WaveNet (Oord et al., 2016) (TCN-based), and Transformer (Vaswani et al., 2017). The representations \(\mathbf{H}_{G_{v}}^{T_{h}}\in\mathbb{R}^{T_{h}\times D_{m}}\) are the input of the temporal encoder. For GRU and WaveNet, they compress the temporal dimension to 1, generating the output \(\mathbf{h}_{G_{v}}\in\mathbb{R}^{D_{m}}\), while for Transformer, the resulting representation still has the same shape as \(\mathbf{H}_{G_{v}}^{T_{h}}\). We only take the last time step as the final output.

Moreover, since the standard Transformer is aware of all input time steps during self-attention and the traffic status at the current step is in fact not conditioned on its future, we follow WaveNet to introduce causality into the attention mechanism, leading to the design of the Causal Transformer. This ensures that the model cannot violate the temporal order of inputs and such causality can be easily implemented by masking the specific entries in the attention map. Finally, we concatenate the spatio-temporal summary \(\mathbf{h}_{G_{v}}\in\mathbb{R}^{D_{m}}\) of node \(v\) with its location embedding \(\mathbf{H}_{v}\in\mathbb{R}^{D_{m}}\), which is then fed into the predictor (implemented as an MLP) for generating the forecasting results of node \(v\): \(\mathbf{\dot{Y}}_{v}^{T_{f}}=\text{MLP}(\mathbf{h}_{G_{v}}||\mathbf{H}_{v})\).

### Node-based Batch Sampling for Training SimST

When training an STGNN, the input data are usually a four-dimensional tensor \(\mathbf{X}^{T_{h}}\in\mathbb{R}^{B\times|\mathcal{V}|\times T_{h}\times F}\), where \(B\) denotes the set batch size. That said, nodes are strictly bound together and the batch sampling unit is the entire graph. However, directly applying this graph-based sampling to SimST leads to two issues. First, since SimST is a single-node architecture, the actual batch size \(B^{*}\) for SimST is \(B\times|\mathcal{V}|\). For example, there are 883 nodes in the PeMSD7 dataset (Song et al., 2020) and usually \(B\) is set to 64, then \(B^{*}=~{}\)56,512. Such a large number reduces the noise in the gradient estimation and leads to a degenerated generalization (Keskar et al., 2017). Also, when \(|\mathcal{V}|\) is large, it can easily cause GPU out-of-memory problems. Second, we argue that the graph-based sampling method significantly diminishes sample diversity when forming mini-batches. For example, the traffic flow of all nodes from 8 to 9 a.m. on January 26 will always appear in the same batch.

To tackle these issues, we propose to remove the restriction on nodes and change the batch sampling unit from a graph to a single node. Note that the same node at different time periods is viewed as different instances. Consequently, the input to SimST becomes \(\mathbf{X}^{T_{h}}\in\mathbb{R}^{B^{*}\times T_{h}\times F}\), where \(B^{*}\ll B\times|\mathcal{V}|\). The benefits are two-fold. First, our solution provides flexibility to choose \(B^{*}\), which can be disproportionate to \(|\mathcal{V}|\) and thus allows for smaller values like 256. This property enhances generalization (Keskar et al., 2017), and allows SimST to have low GPU memory costs and to easily scale to large graphs. Second, our approach provides more sample diversity when forming mini-batches, which yields a generalization improvement (Ash et al., 2020).
## 5 Experiments

### Experimental Setup

DatasetsWe conduct experiments on commonly used traffic benchmarks. The details are presented in Table 2. All traffic readings are aggregated into 5-minute windows, resulting in 288 data points per day. Note that the values in traffic flow datasets are generally much larger than those in speed-related datasets. Following (Li et al., 2018; Song et al., 2020; Choi et al., 2022), we use the 12-step historical data to predict the next 12 steps. Z-score normalization is applied to the input data for fast training. We build the adjacency matrix of each dataset by using road network distances with a thresholded Gaussian kernel (Shuman et al., 2013). The threshold \(r\) is set to 0 for PeMSD4, PeMSD7, PeMSD8, and 0.1 for LA and BAY. More information is provided in Appendix A.

BaselinesWe compare SimST with the following baselines. Historical Average (HA) (Pan et al., 2012) and Vector Autoregression (VAR) (Toda, 1991) are traditional methods. DCRNN (Li et al., 2018), STGCN (Yu et al., 2018), ASTGCN (Guo et al., 2019), GWNET (Wu et al., 2019), STSGCN (Song et al., 2020), and AGCRN (Bai et al., 2020) are well-known STGNNs. We also incorporate methods that are published recently: STGODE (Fang et al., 2021), STGCNDE (Choi et al., 2022), GMSDR (Liu et al., 2022).

Implementation DetailsSimST is implemented with PyTorch 1.12. There are three variants of SimST based on the applied temporal encoders. We describe the specific configurations for different variants in Appendix B. The following settings are the same for all variants. We train our method via the Adam optimizer with an initial learning rate of 0.001 and a weight decay of 0.0001. We set the maximum epochs to 150 and use an early stop strategy with a patience of 20. The batch size is 1,024. The embedding size \(D_{n}\) is 20. The top-\(k\) nearest neighbors are set to 3 for LA and BAY, and 0 for PeMSD4, PeMSD7, and PeMSD8 (due to limited available edges). For baselines, we run their codes based on the recommended configurations if their accuracy is not known for a dataset. If known, we use their officially reported accuracy. Experiments are repeated five times with different seeds on an NVIDIA RTX A6000 GPU.

Evaluation MetricsWe adopt three common metrics in forecasting tasks to evaluate the model performance, including mean absolute error (MAE), root mean squared error (RMSE), and mean absolute percentage error (MAPE). For efficiency measurement, the commonly used floating point operations per second (FLOPS) cannot reflect the "real" running speed of methods because it ignores the effects of parallelization. Hence, we apply the metric of throughput per second (TPS) in this study, which indicates the average number of samples the network can process in one second. We provide a wall-clock time comparison in Appendix D.

### Performance Comparison

In this section, we conduct a model comparison between SimST variants and state-of-the-art STGNNs on five real-world traffic benchmarks. The three variants of SimST are SimST-GRU, SimST-WaveNet (WN), and SimST-Causal Transformer (CT). According to the empirical results in

\begin{table}
\begin{tabular}{l|c c c|c c c|c c c|c c c|c c c} \hline \multirow{2}{*}{Method} & \multicolumn{3}{c|}{PeMSD4} & \multicolumn{3}{c|}{PeMSD7} & \multicolumn{3}{c|}{PeMSD8} & \multicolumn{3}{c|}{LA} & \multicolumn{3}{c}{BAY} \\ \cline{2-13}  & MAE & RMSE & MAPE & MAE & RMSE & MAPE & MAE & RMSE & MAPE & MAE & RMSE & MAPE & MAE & RMSE & MAPE \\ \hline \hline HA & 38.03 & 59.24 & 27.88\% & 45.12 & 65.64 & 24.51\% & 34.86 & 59.24 & 27.88\% & 4.16 & 7.80 & 13.00\% & 2.88 & 5.59 & 6.80\% \\ VAR & 24.54 & 38.61 & 17.24\% & 50.22 & 75.63 & 32.22\% & 19.19 & 29.81 & 13.10\% & 5.28 & 9.06 & 12.50\% & 2.24 & 3.96 & 4.83\% \\ \hline DCRNN & 22.39 & 34.93 & 15.19\% & 23.41 & 36.66 & 9.98\% & 16.62 & 25.95 & 10.60\% & 3.14 & 6.28 & 8.65\% & 1.63 & 3.65 & 3.70\% \\ STGCN & 21.59 & 33.83 & 15.49\% & 26.12 & 41.43 & 11.92\% & 17.41 & 26.72 & 11.78\% & 3.39 & 6.79 & 9.34\% & 1.88 & 4.30 & 4.28\% \\ ASTGCN & 21.58 & 33.76 & 14.71\% & 25.77 & 39.41 & 11.67\% & 17.91 & 27.34 & 11.36\% & 3.57 & 7.19 & 10.32\% & 1.86 & 4.07 & 4.27\% \\ GWNET & 19.33 & **30.73** & 13.18\% & 20.65 & 33.47 & 8.84\% & **14.98** & **23.75** & 9.75 & **30.6** & **6.10** & **8.38\%** & 1.58 & 3.54 & 3.59\% \\ STSGCN & 21.19 & 33.65 & 15.90\% & 24.26 & 39.03 & 10.21\% & 17.13 & 26.80 & 10.96\% & 3.32 & 6.66 & 9.06\% & 1.79 & 3.91 & 4.06\% \\ AGCRN & 19.83 & 32.26 & 12.97\% & 20.69 & 34.19 & 8.86\% & 15.95 & 25.22 & 10.09\% & 3.19 & 6.41 & 8.84\% & 1.62 & 3.61 & 3.66\% \\ STGODE & 20.84 & 32.82 & 13.77\% & 22.99 & 37.54 & 10.14\% & 16.81 & 25.97 & 10.62\% & 4.73 & 7.60 & 11.71\% & 1.77 & **3.33** & 4.02\% \\ STGCNDE & 19.21 & 31.09 & **12.76\%** & 20.53 & 33.84 & 8.80\% & 15.45 & 24.81 & 9.92\% & 3.58 & 6.84 & 9.91\% & 1.68 & 3.66 & 3.80\% \\ GMSDR & 20.49 & 32.13 & 14.15\% & 22.27 & 34.94 & 9.86\% & 16.36 & 25.58 & 10.28\% & 3.21 & 6.41 & 8.76\% & 1.69 & 3.80 & 3.74\% \\ \hline SimST-WN & 19.56 & 31.24 & 13.38\% & 20.81 & 33.94 & 8.87\% & 15.55 & 24.70 & 10.17\% & 3.19 & 6.35 & 8.97\% & 1.60 & 3.55 & 3.66\% \\ SimST-CT & 19.32 & 30.98 & 13.35\% & 20.63 & 33.71 & 8.70\% & 15.13 & 24.18 & 2.73\% & 3.11 & 6.19 & 8.73\% & 1.59 & 3.50 & 3.61\% \\ SimST-GRU & **19.19** & 30.92 & 13.13\% & **20.14\({}^{*}\)** & **33.34** & **8.46\%** & 14.99 & 24.26 & **9.66\%** & 3.16 & 6.29 & 8.82\% & **1.57** & 3.47 & **3.58\%** \\ \hline \end{tabular}
\end{table}
Table 1: Test MAE, RMSE, and MAPE results averaged over all predicted time steps on five datasets. We bold the best results and underline the second best results. \({}^{*}\) denotes the improvement of SimST over the best baseline is statistically significant at level 0.05.

\begin{table}
\begin{tabular}{l|c c c c} \hline Dataset & \#Node & \#Edge & \#Instance & Attribute \\ \hline \hline PeMSD4 (Song et al., 2020) & 307 & 338 & 16,992 & Flow \\ PeMSD7 (Song et al., 2020) & 883 & 865 & 28,224 & Flow \\ PeMSD8 (Song et al., 2020) & 170 & 276 & 17,856 & Flow \\ LA (Li et al., 2018) & 207 & 1,515 & 34,272 & Speed \\ BAY (Li et al., 2018) & 325 & 2,369 & 52,116 & Speed \\ \hline \hline \end{tabular}
\end{table}
Table 2: Dataset statistics.
Table 1, all variants of SimST achieve competitive performance on the three evaluation metrics of all datasets, which validates the effectiveness of SimST and indicates SimST can generalize to various architectures of temporal models. For comparison among SimST variants: note that for fairness we ensure that the variants have a similar number of parameters (around 150k). SimST-GRU generally achieves comparable performance to state-of-the-art baselines, i.e., GWNET and STGNCDE. SimST-CT also attains competitive accuracy, with little difference from SimST-GRU and GWNET. We notice that while Transformers are generally considered a more powerful model, our results show that a simple GRU works well for traffic prediction. In summary, our results provide strong support for our claim that GNNs are not the only option for spatial modeling in traffic forecasting. Moreover, considering the very different design of SimST compared to other state-of-the-art methods, we hope that this will inspire follow-on studies in graph-less designs.

Additionally, we find that: (1) STGNNs approaches surpass HA and VAR by a large margin due to their greater learning capacity. (2) The capability of methods that apply the adaptive matrix, such as GWNET and AGCRN, has been overlooked. They have achieved similar performance to the recently proposed approaches.

### Efficiency Comparison

In this part, we select the top-performing approaches and compare their efficiency with SimST variants. It can be seen from Table 3 that all SimST variants are significantly more efficient than baselines, thanks to their simple model architecture and linear time complexity w.r.t. \(|\mathcal{V}|\). Specifically, comparing TCN-based models, SimST-WN has around 45% fewer parameters than GWNET but achieves \(3.3\times-5.6\times\) higher TPS. For RNN-based methods, SimST-GRU is \(3.7\times\) - \(6.1\times\) and \(19\times-26\times\) faster than AGCRN and GMSDR, respectively. STGODE and STGNCDE are the recently published methods that are based on neural ordinary differential equations. Though achieving competitive performance, they suffer from significant inefficiency problems. For example, SimST-WN has comparable performance to them but is \(11\times\) - \(17\times\) and \(30\times\) - \(39\times\) faster. Among the variants, SimST-WN achieves the highest TPS due to WaveNet's superior parallelism capability. SimST-GRU also achieves good TPS results, which we attribute to an optimized implementation in the PyTorch library. See Appendix D for more results on efficiency comparison.

### Ablation Study

We have demonstrated the effectiveness and efficiency of SimST. Next, we select SimST-GRU and SimST-CT as the representatives (due to their preferable performance) and conduct a series of ablation and case studies on one flow-based dataset PeMSD4, and one speed-related dataset LA.

#### 5.4.1 Effects of spatial learning modules

To study the effects of two spatial modules, we consider the following three settings for comparisons: (1) **w/o Correlation Learning (CL)**: we turn off the spatial correlation learning module. (2) **w/o Proximity Modeling (PM)**: for each node, we only input the histories of itself. (3) **CT/GRU**: we do not perform spatial learning. The results

\begin{table}
\begin{tabular}{l|c c|c c|c c|c c c|c c|c c|c c} \hline \hline \multirow{2}{*}{Method} & \multicolumn{3}{c|}{PeMSD4} & \multicolumn{3}{c|}{PeMSD7} & \multicolumn{3}{c|}{PeMSD8} & \multicolumn{3}{c|}{LA} & \multicolumn{3}{c}{BAY} \\ \cline{2-13}  & Param & TPS & \(\Delta\) & Param & TPS & \(\Delta\) & Param & TPS & \(\Delta\) & Param & TPS & \(\Delta\) & Param & TPS & \(\Delta\) \\ \hline \hline GWNET & 303 & 1,876 & \(4.15\times\) & 314 & 522 & \(5.65\times\) & 300 & 3,258 & \(3.75\times\) & 301 & 2,825 & \(3.30\times\) & 303 & 1,738 & \(3.52\times\) \\ AGCRN & 749 & 1,559 & \(4.99\times\) & 755 & 445 & \(6.62\times\) & 747 & 1,733 & \(7.06\times\) & 748 & 1,604 & \(5.82\times\) & 749 & 1,466 & \(4.17\times\) \\ STGODE & 715 & 552 & \(14.09\times\) & 733 & 226 & \(13.04\times\) & 710 & 721 & \(16.97\times\) & 709 & 682 & \(13.69\times\) & 713 & 532 & \(11.49\times\) \\ STGNCDE & 377 & 217 & \(35.85\times\) & 388 & 76 & \(38.79\times\) & 374 & 362 & \(33.79\times\) & 375 & 251 & \(37.19\times\) & 377 & 204 & \(29.97\times\) \\ GMSDR & 880 & 267 & \(29.14\times\) & 2253 & 119 & \(27.77\times\) & 423 & 465 & \(26.31\times\) & 641 & 300 & \(31.12\times\) & 923 & 238 & \(25.68\times\) \\ \hline SimST-CT & 147 & 4,597 & \(1.69\times\) & 159 & 1,656 & 1.78\(\times\) & 144 & 7,887 & \(1.55\times\) & 145 & 5,969 & \(1.56\times\) & 148 & 4,041 & \(1.51\times\) \\ SimST-GRU & 130 & 6,167 & \(1.26\times\) & 142 & 2,268 & \(1.30\times\) & 127 & 10,494 & \(1.17\times\) & 128 & 7,766 & \(1.20\times\) & 131 & 5,440 & \(1.12\times\) \\ SimST-WN & 167 & **7,780** & - & 179 & **2,948** & - & 164 & **12,232** & - & 165 & **9,335** & - & 168 & **6,113** & - \\ \hline \hline \end{tabular}
\end{table}
Table 3: A efficiency comparison between five best-performing baselines and SimST variants. Param denotes the number of learnable parameters and the magnitude of parameters is Kilo (\(10^{3}\)). TPS is measured on the validation set during inference. We bold the highest TPS. The \(\Delta\) column means the TPS improvements of SimST-WN over all the other methods.

Figure 2: Effects of two spatial learning modules: correlation learning (CL) and proximity modeling (PM).
are shown in Figure 2. First, we find that removing CL leads to significant degradation of MAE for both SimST-GRU and SimST-CT on both datasets, revealing the great importance of building global correlations under the SimST framework. Second, the benefit of PM is marginal on PeMSD4. This is because the average degree of nodes in PeMSD4 is only 1.1, so the available neighbor information is very limited. In contrast, the average degree of nodes in the LA dataset is 7.3, where PM affects performance more. Third, we notice that removing the CL module has a greater impact on the PeMSD4 dataset than on the LA dataset. The reason is that when neighbor information is scarce, the CL module takes a greater responsibility to supplement neighbor knowledge. Conversely, when there are more neighbors, the influence of CL on performance is less significant.

#### 5.4.2 Effects of Node-based Batch Sampling

We examine the effects of the node-based sampling method from two aspects. First, we show the influence of the batch size number in the first row of Figure 3. Generally, both SimST-GRU and SimST-CT reach their best performance when setting \(B^{*}\) to 1,024 on the two datasets, revealing the necessity of applying a small \(B^{*}\). The negative influence of using a large batch size such as 19,648, is more significant on the PeMSD4 dataset. Besides, we find that SimST-CT only occupies around 2GB of memory on our GPU across all datasets. In contrast, the memory cost of STGNNs usually grows as \(|\mathcal{V}|\) increases. For example, on the dataset with the lowest \(|\mathcal{V}|=170\) and the highest \(|\mathcal{V}|=883\), GWNET requires around 3GB and 11GB of memory, respectively.

Second, we present the effects of different batch-forming approaches, i.e., graph-based sampling and node-based sampling by drawing the convergence curves in the second and third rows of Figure 3. Note that we ensure fair comparisons by setting the same \(B^{*}\) in experiments. In Figure 3, it can be seen that node-based batch sampling surpasses the counterpart. Concretely, node-based sampling is only slightly better than the graph-based method when a large \(B^{*}\) is applied (e.g., 19,648/13,248). This is because the sample diversity of graph-based sampling is rich enough at this time. As \(B^{*}\) decreases to small values (e.g., 1,228/828), which is necessary to improve performance, the impact of sample diversity becomes significant, i.e., generalization performance is greatly improved, especially on PeMSD4. Also, we find that the curves of node-based sampling are generally more stable than the graph-based method.

#### 5.4.3 Hyperparameter Study

In Figure 4, first row, we show the effects of the number of top-\(k\) one-hop neighbors. We replace PeMSD4 with the BAY dataset because the average degree of nodes is only 1.1 in PeMSD4. From the figure, we observe that the performance gradually improves when \(k\) increases from 0 to 3. But the performance worsens when we set \(k\) to 4, indicating a potential overfitting issue. Next, we assess the effects of the sensor embedding dimension size in the second row of Figure 4. We find that both SimST-GRU and SimST

Figure 4: Effects of the top-\(k\) neighbors on BAY and LA datasets, and sensor embedding dimension on PeMSD4 and LA datasets.

Figure 3: Effects of the node-based batch sampling strategy on PeMSD4 (left column) and LA (right column) datasets. For simplicity, here we denote SimST-GRU as GRU and SimST-CT as CT. In the first row, the largest values in the x-axis are computed by \(|\mathcal{V}|\times 64\) (the common batch size used in STGNNs (Wu et al., 2019; Bai et al., 2020; Choi et al., 2022)). In the second and third rows, the number in the legend denotes \(B^{*}\).
CT are not sensitive to the changes in the dimension on both datasets. The results also suggest that a small dimension such as 16, is sufficient to learn correlations between nodes.

### Case Study

In this section, we explore further to understand _what exactly the sensor embeddings have learned_ through a case study that makes connections between embedding similarities and real-world sensor locations. We apply SimST-CT on LA and BAY since only these two datasets provide sensors' coordinates. Concretely, we first compute pairwise cosine similarities between sensor embeddings, i.e., for \(v_{i},v_{j}\in\mathcal{V},\text{similarity}=\frac{E_{v_{i}}\cdot E_{v_{j}}}{ \left\|E_{v_{i}}\right\|_{2}\left\|E_{v_{j}}\right\|_{2}}\), and pairwise geodesic distances between sensors based on their coordinates. Then we calculate the average cosine similarities within the ranges of 0-1, 1-5, 5-10, 10-20, and 20-35 kilometers of all sensors, leading to a statistical overview shown in Figure 5 (left part). It can be seen that cosine similarity becomes smaller when the geodesic distance gets larger. This result obeys Tobler's First Law of Geography, i.e., near things are more related than distant things.

Next, we look at an example by selecting sensor 62 in LA as the anchor node, which is located at the intersection of two highways. We also visualize its top similar neighbors based on cosine similarity in Figure 5 (upper right). We find that (1) sensors 13 and 58 are the nearby neighbors, which are also included in the adjacency matrix. (2) sensors 201 and 178 are distant nodes. They are considered similar sensors because they are also located at intersections, and thus share similar traffic patterns to the anchor. The situation in the BAY dataset is similar to LA (shown in the lower right of Figure 5), so we do not elaborate further.

### Discussion & Future Work

We find that SimST-GRU and SimST-CT perform worse than the state-of-the-art STGNNs (i.e., STGNCDE and GWNET) when we turn off the node-based batch sampling strategy. This result indicates that the proposed two spatial learning modules can only approximate the efficacies of GNNs, and the training strategy of SimST is an indispensable component to obtain comparable performance to the state-of-the-art. In addition, we note that when the neighbor information is relatively rich, such as with LA, SimST-CT is slightly below the state-of-the-art. Therefore, we plan to address this performance gap by utilizing pretrained models and knowledge distillation (Zhang et al., 2022). Lastly, our findings in this work are currently limited to traffic forecasting, while we would like to expand SimST to other spatio-temporal applications such as air quality prediction.

## 6 Conclusion

In this paper, we propose SimST, a simple, effective, and efficient spatio-temporal learning method for traffic forecasting. It approximates GNNs with two proposed spatial learning modules, involves a node-based batch sampling strategy, and is temporal-model-agnostic. Our study suggests that message passing is not the only effective way of modeling spatial relations in traffic forecasting; hence, we hope to spur the development of new model designs with both high efficiency and effectiveness in the community.

Figure 5: A case study of learned sensor embeddings. The Count axis on the left part means the number of sensor pairs within the corresponding ranges, and the trend is indicated by red dotted line. The sum of the counts is \(|\mathcal{V}|^{2}\). On the right part, the star icons represent the anchor sensor, the circle icons denote the selected similar sensors, and the roads colored in red are the highways in California, USA.