Space Meets Time: Local Spacetime Neural Network For Traffic Flow Forecasting

With the increasing volume of traffic data and the growing impacts of data-driven technologies in modern transportation systems, the traffic flow forecasting problem is drawing increasing attention [1]. Reliable and timely predictions of the traffic dynamics can assist transportation management, help alleviate traffic congestion, and enhance traffic efficiency.

A traffic system is characterised by the changing flows at locations in a road network, i.e., nodes (sensors) interlinked by road segments, from which one may observe salient patterns: sudden bursts, drastic fluctuations, and periodic shifts. One can develop an understanding of these patterns from two perspectives. On the outside, traffic is the accumulation of various extrinsic factors, from road layout, to geographic features of the environment, to traffic laws, and erratic behaviours of drivers, all playing a role in shaping traffic conditions. On the inside, intrinsic principles are governing the flow of traffic, as vehicles – particles in the road system – maintain stable directional, speed and concentration features as they travel through space and time, giving rise to some universal patterns of the traffic flow. These universal patterns are what is behind well-established traffic flow models, such as Wardrop’s equilibria, and Kerner’s three-phase traffic theory, that describe traffic flow from a mathematical point of view [2].

We argue that accurate predictions of traffic flow – based on macro-level traffic data – rest upon a model’s ability to grasp not only extrinsic features from the given data set, but also intrinsic principles that are universal to any traffic systems. At its core, traffic can be seen as a physical system [3] where localised changes cascade like waves along roads, to some other locations, some time later [4]. Therefore the key to capturing the intrinsic principles of traffic flow lies in extracting the latent correlations between locations’ present states and surrounding locations’ past.

Recent breakthroughs in neural-based techniques, in particular those based on graph neural networks (GNNs) [5, 6, 7, 8], represent a significant step towards representing non-linear traffic features by leveraging topological constraints while achieving better prediction results as compared to earlier statistical methods such as autoregressive models [9]. However, existing GNN-based traffic forecasting models have three common limitations: (1) These models heavily rely on the graph structure which varies across different road networks. As such, they are restricted to a particular road network, rather than revealing intrinsic properties of traffic system; (2) They apply computationally expensive feature aggregation operations (e.g., graph convolutions takes) on the entire network, and thus are not scalable to large road networks that contain hundreds of thousands of sensors. For instance, graph convolution network (GCN) scales quadratically w.r.t. the number of nodes in the network. (3) These models all consist of separate components to extract features from the spatial and the temporal dimensions, respectively, before integrating them into the same feature map to derive a prediction. The extracted feature map represents “aggregated” correlations between locations of the network across time. This setup implicitly assumes that the correlations between locations stay uniform over time. However, two locations may have different correlations at different times: As indicated in Figure 1, against the current ($t_{3}$) target node, node $a$ has a stronger correlation at an earlier time (i.e., $t_{1}$) than a later time (i.e., $t_{2}$), while $b$ has a weaker correlation at $t_{1}$ than at $t_{2}$.

To break the above limitations in existing GNN-based models, we propose a new spatio-temporal correlation learning paradigm, called Spacetime Interval Learning, which fuses the spatial dimensions and the temporal dimension into a single manifold, i.e., a spacetime, as coined in special relativity theory. The correlations that we aim to capture reflects a form of “distance” between two traffic events in spacetime, where the distance is referred to as interval in spacetime terminologies [10]. Specifically, the proposed spacetime interval learning paradigm extracts the traffic data of nearby sensors within a fixed time window, regarded as the local-spacetime context of each target location. The local-spacetime context is analogous to the “receptive field” of sensors to ignore the sensors that do not contribute much to the final prediction. Then, the spacetime interval learning paradigm learns to correlate a node $x$ at a given time $t$ with another node $y$ at a different time $t^{\prime}\geq t$ in the local-spacetime context.

The proposed learning paradigm addresses the limitations of the GNN-based models as follows. Firstly, it models the spatio-temporal correlations within the local-spacetime context of each target location. In this way, the model we build is independent of the graph structure, and thus is universal for traffic flows at large, as opposed to for any specific network. Secondly, our method focuses on the local-spacetime, such that it changes the traffic prediction from network-level to node-level. That is, our model can be predict the traffic for multiple locations of interest in parallel on different machines. Thirdly, unlike existing methods, we fuse the spatial and the temporal dimensions into a single manifold to capture the varying spatial correlations between locations across time.

Under the spacetime interval learning paradigm, we propose an implementation called Spacetime Neural Network (STNN), which combines novel spacetime attention blocks and spacetime convolutional blocks. The former highlights the interval between events, while the latter aggregates the learned features from spatial, temporal, and spatio-temporal aspects. The main advantage of the model are as follows. The code is available on https://github.com/songyangco/STNN.

1. 1.

   Accuracy: The learned spacetime intervals explicitly capture the correlations between locations across different time instances, making the learned features highly informative in traffic prediction. As validated through experiments on two real-world datasets, METR-LA and PeMS-Bay, when trained on data from a single network, our model outperforms existing methods, with, e.g., 4% improvement over current state-of-the-art complicated models for 15-min predictions. See Section VI-B.

2. 2.

   Transferrability amounts to a main advantage of our universal model. For this, we train a single STNN model on one dataset and use it without fine-tuning on unseen traffic datasets. In all cases, the results achieve competitive, if not better, performance compared to state-of-the-art approaches, validating the applicability of our universal model. See Section VI-B.

3. 3.

   Ability to handle dynamic networks is another natural consequence of converting raw input to a local-spacetime for every target node. This refers to, e.g., the network undergoes structural changes such as the blocking or addition of roads. We perform an experiment on a synthetic dynamic network. Our model is much better than baselines. See Section VI-C.

4. 4.

   Scalability: Previous GNN-based models all assume a small fixed network whose size is limited by computational capability. By performing prediction on node-level, we break the limit on the network size. The complexity of our model is independent from the network size, making our model applicable to networks of arbitrary size. See Section VI-F.

Studies on traffic forecasting through spatio-temporal data analysis can roughly be divided into four types.

Statistical methods. Early studies in the 2000s use various statistical methods, such as historical average (HA), autoregressive integrated moving average (ARIMA) [9], and vector autoregression (VAR) [11] for the traffic forecasting problem. However, these approaches assume the input time series to be stationary and univariate. This assumption may not hold in a complex traffic system. Thus, statistical methods often generate inaccurate predictions.

Machine learning methods. To account for more complex traffic data, various classical machine learning methods, such as kNN [12], SVM [13], SVR [14], are employed in the early 2010s. One shortcoming of these methods is that they fail to capture the highly non-linear spatial and temporal patterns present in the data.

Deep learning methods. After 2015, capitalising on the success of deep learning [15], several deep learning models are proposed to capture the underlying patterns of traffic data. Recurrent neural networks (RNNs) are adopted to analyse time series patterns [16, 17], while convolutional neural networks (CNNs) are used to capture spatial dependencies by treating a traffic network as a grid [18, 19]. However, these methods omit the road network, which is an essential spatial constraint on how traffic moves in the spatial dimension. This limitation inhibits traditional deep learning methods from accurate traffic forecasting.

Graph neural networks. More recently, graph-based deep learning models are increasingly used for spatio-temporal data analysis. Yu et al. [5] propose a spatio-temporal graph convolutional network based on spectral graph theory to extract features from the road network and the historical time series data. In particular, the spatial patterns are captured by graph convolutional layers while the temporal patterns are extracted by gated convolutional layers. Li et al. [20] model the traffic flow as a diffusion process and capture the spatial dependencies by random walks on a graph followed by an RNN to extract temporal patterns. Yao et al. [6] use graph embeddings to capture the road network information and integrate Long-Short Term Memory (LSTM) and CNN with the graph embeddings for traffic prediction. Attention mechanism has also been adopted to learn spatial and temporal patterns with improved performance [21, 22]. However, all of these methods fall into the same paradigm that separate layers are applied to extract spatial patterns and temporal patterns respectively. We summarize current methods under this paradigm in Table I. Particularly, CNN, Graph Convolutional Network (GCN), or spatial attention are often used to learn spatial patterns. Gated Recurrent Unit (GRU), LSTM, gated temporal convolution (gated TCN), or temporal attention are used to learn temporal patterns.

Unlike current methods, this work proposes a novel learning paradigm. Instead of using separate components or layers to learn spatial and temporal patterns, we design a novel spacetime module to learn the local spatio-temporal correlations, and capture both spatial and temporal patterns at the same time. Our model does not fall into any existing categories. Specially, instead of exploiting GNN to learn spatial patterns, we fuse spatial features with temporal features together and learned by a unified layer.

We summarise the list of important notations in Table II.

Traffic condition like vehicle speed is often recorded by the road-side sensor station $v$ along with other auxiliary information including time, sensor location, etc. Aggregating $N$ sensors together forms a sensor set $V\in\mathbb{R}^{N}$ which monitor the traffic flow of a certain area.

At each time step $t$, the $i$-th sensor station $v_{i}$ records local traffic measures such as vehicle average speed in a fixed time duration and supplementary data. These measurements form a feature vector $\mathbf{x}^{(t)}_{i}\in\mathbb{R}^{F}$. In particular, we have two features in our input data: average speed, timestamp. Collecting the feature vectors of all sensor stations together, we obtain the overall observation of the traffic network at time step $t$ as $\mathbf{X}^{(t)}=\left(\mathbf{x}^{(t)}_{1},\mathbf{x}^{(t)}_{2},\ldots,\mathbf{x}^{(t)}_{i}\right)\in\mathbb{R}^{N\times F}$. A traffic flow dataset contains the measures of a sequence of $T_{h}$ time steps, where $T_{h}>0$, and is thus presented as a sensor feature tensor $\mathcal{X}\coloneqq\left(\mathbf{X}^{(1)},\mathbf{X}^{(2)},\ldots,\mathbf{X}^{(T_{\mathrm{h}})}\right)\in\mathbb{R}^{N\times F\times T_{\mathrm{h}}}$.

Based on the location of sensor stations, we can get the travel distance on road network between any two sensors. Consequently, we built a matrix $\mathbf{Q}$ to reflect the distances of all sensor pairs. One can think $\mathbf{Q}$ as the weighted adjacent matrix of a directed complete graph. The edge weight is affected by the actual distance and complete graph is because we can always calculate the distance between two sensors. Furthermore, we do not require $\mathbf{Q}$ remain unchanged all the time. On the contrary, the travel distance between two sensors might be variable because of events like traffic accidents or road constructions which alter the underlying topology of road network, leading to a further travel distance. Thus, to better incorporate the network dynamics in our model, we use $\mathbf{Q}^{(t)}$ to just indicate the spatial context at the particular time step $t$. $\mathcal{Q}\coloneqq\left(\mathbf{Q}^{(1)},\mathbf{Q}^{(2)},\dots,\mathbf{Q}^{(T_{\mathrm{h}})}\right)\in\mathbb{R}^{N\times N\times T_{\mathrm{h}}}$ reflects the underlying road network structure dynamics over $T_{\mathrm{h}}$ time steps, where $T_{\mathrm{h}}>0$. For a static network, $\mathcal{Q}$ reduces to Q.

Traffic flow forecasting: Given a sensor feature tensor $\mathcal{X}$ and a spatial context tensor $\mathcal{Q}$ over past $T_{\mathrm{h}}$ time steps, as well as a set of nominated target nodes $V_{\mathrm{tar}}=\{v_{1},v_{2},\ldots,v_{M}\}\subseteq V$. The traffic flow forecasting problem aims to predict the traffic flow of the next $T_{\mathrm{r}}$ time steps for every target node in $V_{\mathrm{tar}}$. The desired output is thus $\mathcal{Y}=(\mathbf{y}_{1},\mathbf{y}_{2},\dots,\mathbf{y}_{M})\in\mathbb{R}^{M\times T_{\mathrm{r}}}$ where $\mathbf{y}_{p}=(y_{p}^{T_{\mathrm{h}}+1},y_{p}^{T_{\mathrm{h}}+2},\dots,y_{p}^{T_{\mathrm{h}}+T_{\mathrm{r}}})\in\mathbb{R}^{T_{\mathrm{r}}}$ denotes the traffic conditions of the next $T_{\mathrm{r}}$ time steps at node $v_{p}\in V_{\mathrm{tar}}$.

Spacetime interval learning aims to discover the influence between traffic events in a single spacetime manifold instead of modeling the spatial and temporal dimensions separately. We define traffic events and spacetime as follows:

A traffic event, defined analogously to the notion of events in physics [27], embodies both spatial and temporal information of a traffic measurement by a sensor station.

A spacetime manifold can be organzied as a 3D structure where first dimension corresponding to the time, the second dimension corresponding to the space, and the third is the observed traffic measurement. The time dimension is easy to understand but the space data needs more work. In order to squeeze the spatial information into a single dimension, we transfer the sensor coordinates to the travel distance with the anchor/target sensor. As a result, we construct a local-spacetime around a target sensor and use that to predict the future traffic flow of that particular sensor.

The spacetime interval between two traffic events denotes the extent to which one event influences the other; a smaller interval means a closer association between two traffic events. In a local-spacetime, we only care about the intervals between traffic events of the target sensor with other sensors.

A crucial step in the proposed learning paradigm is to build the local-spacetime of a target node $v_{p}$, which is then used for spacetime interval learning. In this way, the trained model not only captures the spacetime interval explicitly, but also be able to generalize learned patterns to other local-spacetimes in the same road network or event different city. We now give details of how to construct a local-spacetime for an arbitrary node $v_{p}\in V_{\mathrm{tar}}$ where $V_{\mathrm{tar}}$ is a set of nodes we want to predict. The pseudocode is outlined in Algorithm 1.

Given a time step $t$, we define a connectivity matrix $\mathbf{A}^{(t)}\in{V^{(t)}}^{2}\to[0,1]$ by applying the Gaussian kernel on the distance matrix $\mathbf{Q}^{(t)}$ to convert travel distance to a weight reflect the connectivity of two sensors. Longer distance corresponds to smaller weight, namely,

where $i$, $j$ are any two nodes in $V^{(t)}$ and $\theta$ is a hyper-parameter. Empirically, we set $\theta$ as the standard deviation among all $\mathbf{Q}^{(t)}(i,j)$. Intuitively, $\mathbf{A}^{(t)}(i,j)$ is a normalized value that expresses how easy to travel from $v_{i}$ to $v_{j}$ in the network at time step $t$. Note that Equation (1) guarantees $\mathbf{A}^{(t)}(i,i)=1$. The superscript $t$ used to depict the variational travel distance caused by the underlying networks structure change.

Using $\mathbf{A}^{(t)}$, we extract a set of nodes, denoted as $V_{p}$, that could benefit the future traffic flow prediction for the target node $v_{p}$ as

where $\epsilon$ is a pre-determined threshold parameter that indicates how close a node should be from (or to) $v_{p}$ to be considered relevant to the traffic flow at $v_{p}$. Note that $\mathbf{A}^{(t)}(i,p)$ can be different from $\mathbf{A}^{(t)}(p,i)$ because $\mathbf{Q}^{(t)}$ is not symmetric. $\epsilon$ control the trade-off between computational cost and prediction accuracy. Moreover, to have the fixed shape input data for training, we require the size of $V_{p}$ to be $\alpha$, namely, $|V_{p}|=\alpha$. This is done by keeping the nearest $\alpha$ neighbors only if $|V_{p}|>\alpha$ or add dummy nodes if $|V_{p}|<\alpha$. Dummy nodes have no connections with other nodes, and their features are all zero. As a results, nodes in $V_{p}$ are sorted based on the travel distance to $v_{p}$ in ascending order.

We now construct a local-spacetime $\mathcal{D}_{p}$ of $v_{p}$. For $t\in\{1,\ldots,T_{\mathrm{h}}\}$, each row of the matrix $\mathbf{D}_{p}^{(t)}\in\mathbb{R}^{|V_{p}|\times(F+1)}$ is defined as:

where $\mathbf{x}^{(t)}_{i}$ is the traffic measurement recorded at node $v_{i}$ and time step $t$, and $[\cdot;\cdot]$ denotes concatenation. The matrix $\mathbf{D}_{p}^{(t)}$ can be regarded as a snapshot of local-spacetime $\mathcal{D}_{p}$. It encodes spatial relationship between $v_{p}$ and those nodes in $V_{p}$, as well as traffic measurements of all these nodes at time step $t$. Finally, define the local-spacetime $\mathcal{D}_{p}$ by

Since $\mathcal{D}_{p}$ contains all the information we need to train a predictive model of the future traffic flow at $v_{p}$, the learning process is independent on the size of the entire network, thus resolving the scalability issue. Moreover, the incorporation of the network information at all time steps $t\in\{1,\ldots,T_{\mathrm{h}}\}$ makes the model capable of handling dynamic network topology.

In summary, the spacetime interval learning framework reduces the traffic flow forecasting problem to learning a universal function $g(\cdot)$ that maps $\mathcal{D}_{p}$ to the future traffic flow of $v_{p}$ and $p\in\{1,\dots,n\}$:

In next section, we propose a novel model as a realization of the mapping function $g(\cdot)$, namely, the spacetime neural network.

The core task of spacetime interval learning is to adaptively learn the influence between traffic events and use them to predict the future traffic flow. To this end, we propose SpaceTime Neural Network (STNN), which is an end-to-end deep learning model that realizes the function $g(\cdot)$ in Equation 5.

Design Principles. To quantify the influence of traffic events in the local-spacetime to the prediction of future traffic flow on the target sensor, a natural idea is to learn how each single traffic event influences the prediction. However, we observe that traffic events in local-spacetime are not independent and they may interfere each other. For example, congestion in an arterial road may increase the traffic in a surrounding region and then diffuse to further road segments. As such, we design our model with two main principles: (1) the model should be able to capture the pair-wise influence, and (2) it needs to be aware of the conditions of nearby regions, capturing the many-to-one influence.

Model Architecture. Following the above two principles, we propose a novel spacetime module, on top of which we build the proposed STNN model. A spacetime module comprises a Spacetime Attention Block (Section V-A) to capture the pair-wise influence, and a Spacetime Convolution Block (Section V-B) to capture the many-to-one influence.

The overall architecture of STNN is shown in Figure 2. The input is a local-spacetime of the target (central) node represented by the blue cylinder. STNN employs several spacetime modules to predict the future traffic of the target node.

More formally, convert the raw data to the local-spacetime $\mathcal{D}_{p}$ and permute $\mathcal{D}_{p}$ to the channel-first format, i.e., $\mathcal{D}_{p}\in\mathbb{R}^{(F+1)\times N\times T_{\mathrm{h}}}$. Then the input $\mathcal{D}_{p}$ is transformed using $1\times 1$ convolution to map traffic events to a high-dimensional feature space. Next, we stack $k$ spacetime modules where $k$ controls the trade-off between model complexity and performance. A smaller $k$ leads to a model with fewer parameters and unlikely to overfits the data. A larger $k$ gives better performance but may jeopardize the generalization ability. Residual connections are also applied for each module. Last, we use a fully connected layer with linear activation to present the prediction results $\left(\hat{y}_{p}^{T_{\mathrm{h}}+1},\dots,\hat{y}_{p}^{T_{\mathrm{h}}+T_{\mathrm{r}}}\right)$.

To evaluate the performance of the proposed model, we compare STNN with the state-of-the-art traffic prediction models on two public traffic datasets in Section VI-B. In addition, a simulated dynamic traffic network is used to demonstrate our model’s capability of handling dynamic graphs in Section VI-C. We further investigate the learned spacetime interval via a case study (Section VI-D) and the impacts of different components of STNN (Section VI-E).

In this paper, we propose a novel spacetime interval learning framework and spacetime neural network (STNN) for accurate traffic prediction. Our approach captures the intrinsic principles of traffic flow by learning the spacetime intervals between traffic events. The model works on the local-spacetime extracted for target nodes and thus can handle dynamic network topology. Experiments on two real-world datasets and a simulated dynamic network show that the proposed framework significantly outperforms state-of-the-art methods. This confirms the effectiveness of capturing spatio-temporal correlations directly. In the future, we will further explore the possibility of capturing the graph dynamics from the input data when the underlying graph structure is unknown. Another promising direction is to embed the local-spacetime construction into an end-to-end deep learning framework, making the parameters used in local-spacetime construction learnable. Last, we would like to investigate the spacetime interval learning paradigm in other spatio-temporal data modeling scenarios.