STDEN: Towards Physics-Guided Neural Networks for Traffic Flow Prediction

Based on the basic concepts above, we formally define the problem of traffic flow prediction as follows.
$\bullet$ Input: The history flow-sequence from time $t-T+1$ to $t$, $F^{(t-T+1:t)}$, the future flow-sequence from time $t+1$ to $t+H$, $F^{(t+1:t+H)}$, and the corresponding road network $G$.
$\bullet$ Output: A model $m(\cdot )$ satisfying ${\hat{F}}^{(t+1:t+H)}=m\left(F^{(t-T+1:t)}\right)$.
$\bullet$ Objective: Minimizing prediction errors of training data.

Data-driven methods directly model the correlation between $F^{(t-T+1:t)}$ and $F^{(t+1:t+H)}$ to generate predictions. We innovatively propose a physics-guided traffic flow prediction framework (see Figure 2), consisting of two parts: an explicit deep learning model STDEN and an implicit physical dynamic process PGFM. In PGFM, i.e.,Physics-Guided traffic Flow Modeling, we use a physics-based continuity equation to model the transformation between the PEF and the traffic flow (denoted as PF-Trans in Figure 2). Details of the implicit PGFM will be given in this section.

Over the implicit physical dynamic process, we implement a deep neural network model,  Spatio-Temporal Differential Equation Network (STDEN), which contains three components: an RNN-based network to encode the traffic flow-sequence as the initial state of PEF, a DE network to predict the evolution of the PEF, and a decoder governed by Eq. (1) to generate traffic flow from the predicted PEF. Note the layers of DE-Net correspond to the dynamic of potential energy in PGFM. Details of STDEN are in the next section.

In our model, the physical dynamic process and the deep learning model are unified under the same framework, that is why we call our model a “physics-guided” neural network.

In this section, we use a continuity equation to model the relations between the flow-sequence and PEF-sequence. First, we provide a brief introduction to the continuity equation.

In physics, the continuity equation describes the transport of some physical quantity, such as mass, energy, momentum, electric charge Lienhard and Lienhard (2008). Here we take the transport of energy as an example. Using the continuity equation, the energy transport process over a set of locations could be described as

where $u$ is the energy density (energy per unit volume), $q$ is the Energy Flux (a measure of energy “transport”), and $\mathrm{div}$ is the divergence operator. The differential equation in Eq. (2) gives a relation between the volume of the energy and the “transport” of that energy, i.e., the change of energy density leads to energy transport in the space. For example, heat always transports from hot locations to cold locations.

The traffic flow driven by traffic potential energy fields in a road network is naturally a specific example of the continuity equation. In Table 2, we draw an analogy between the potential energy-driven traffic flow and the energy continuity equation, where traffic flow on a road network could be considered as energy transport within a Potential Energy Field. In this section, we propose a continuity equation for traffic PEF to describe the dynamic relations between flow-sequence and PEF-sequence of a road network.

Our method is based on the neural ordinary Differential Equation Network (DE-Net) Chen et al. (2018), which is a kind of model that generalizes standard layer-to-layer neural networks as a continuous form. Specifically, in standard residual networks He et al. (2016), the layer-to-layer state update process is in the form of

where $h_t$ is hidden state of (i.e., layer outputs) of the $t$-th layer²²2In our model, the layer of DE-Net just corresponds to time slices, so we use $t$ as the index of the network layers in Eq. (9).. $F(\cdot )$ is the repeated network structure of the residual networks and ${\theta }_t$ is the network parameters at layer $t$.

Eq. (9) could be rewritten as a generalized form as

where $l$ is the step size and its value is 1 in residual networks. When $l\to 0$, the update process of state $h$ becomes

which is a continuous version of the residual networks. In Eq. (11), the deep residual neural network becomes a dynamic system that is governed by an ordinary differential equation Ruthotto and Haber (2019); Lu et al. (2018). Moreover, the function $F(\cdot ,\theta )$ is a neural network, which provides powerful representation learning capacity for complex data.

From the spatial perspective, if we set $t$ as a discrete value, Eq. (13) is equivalent to a residual GCN, where inputs of each layer are $z^{\left(t\right)}$ for all nodes of the road network. From the temporal perspective, the time $t$ is continuous, meaning we can calculate $z^{\left(t\right)}$ for any $t\in R$. Therefore, we name the proposed model based on the differential equation network in Eq. (13) as Spatio-Temporal DE Network.

To achieve a differentiable “sampling” operation, we adopt a reparametrization trick Kingma and Welling (2014) to implement generation process $g(\cdot )$ of $z^{\left(t_0\right)}$ in Eq. (15). In specific, given a batch of training data, we calculate $z_i^{\left(t_0\right)}$ of each node $i$ as

where ${ϵ}_i$ is sampled from a standard normal distribution $N(0,1)$. In this way, $z_i^{\left(t_0\right)}$ for a given batch of training data are fixed, and therefore, Eq. (16) is differentiable in backpropagation algorithm for neural network training. In the prediction phase, the ${ϵ}_i$ is sampled for every input example.

With the pipeline introduced above, we build a physics-guided latent variable model entitled Spatio-Temporal Differential Equation Network (STDEN). Using the backpropagation algorithm, the entire framework can be trained in an end-to-end manner by minimizing the negative log-likelihood of the predicted traffic flow-sequence with the ground truth in training data. The only difference compared with the training of standard neural network is the forward propagation of the DE-Net part needs to calculate using the neural ODE solver in Eq. (14).

Remark: In our model, the physical generation process of traffic flow in a potential energy field is expressed as deep residual GCN based DE-Net, providing a good explanation for our model structure. In other words, our model is not a complete “black-box” as other deep learning models. It could be considered as a kind of physics-guided generative model and therefore be expected to have better performance. Moreover, the elaborate residual DE-Net structure and the measure of uncertainty in potential energy fields also have the potential to improve the prediction performance.

We evaluate the performance of our model over the real-world urban traffic dataset collected by the Beijing Municipal Commission of Transport, which contains trajectories of 40,000 taxies in Beijing from April 1st 2015 to July 31st 2015 (totally 4 months). These trajectories mapped to the road networks using the map matching algorithm. We statistic the traffic flow by counting the number of taxis on each road segment during every 5-minute time interval, resulting in 288 data points per day.

Due to Beijing road networks are too complex, we select three sub-networks to construct datasets of our experiments. Without loss of dataset diversity, the selected sub-networks have different urban functions. The first one is a well-known entertainment area, i.e., Gong Ti (Workers’ Stadium), which has 221 road segments, the second is the area around Beijing West Railway Station, which has 393 road segments, and the last area is around the biggest business park in Beijing, i.e., Zhongguancun (China Silicon Valley), which has 564 road segments. We denote the three datasets as GT-221, WRS-393, and ZGC-564 respectively. We split each dataset into the training, validation, and test sets with a ratio of 7:1:2. For multi-step prediction, we use one-hour historical traffic flow data (12 time steps) to predict the next hour’s.

Table 3 shows the comparison of different approaches for 15 minutes, 30 minutes, and 1 hour ahead forecasting on three datasets. These methods are evaluated by three commonly used metrics in traffic flow prediction, including mean absolute error (MAE), root mean square error (RMSE), and mean absolute percentage error (MAPE).

There are four observations from Table 3. (1) The graph neural network-based spatio-temporal methods generally outperform the time series models, which emphasizes the importance of modeling the spatial correlations of road networks for traffic prediction. (2) Our STDEN improves spatio-temporal methods with a significant margin (an average 10.29%/13.49%/6.03% improvement on MAE/RMSE/MAPE compared with the second best method) and achieves the best performance for all horizons on all the metrics, which shows the effectiveness of the potential energy field DE to model the continuous spatial and temporal dynamics. (3) The approaches based on purely neural differential equation network are not effective than the spatio-temporal ones. Because they ignore the spatial correlation which is important to traffic flow prediction. However, they outperform the traditional time series methods. (4) Traditional methods including HA and VAR are not good enough due to their incapability of handling complex and non-linear spatio-temporal data. Besides, the performance of HA is invariant since this method does not depend on short-term data.

To better illustrate the effectiveness of the Potential Energy Field DE in Eq. (7), we compare STDEN with the following variants: (1) UnkP, which means unknown physics and replaces the potential energy field DE with a fully connected neural network. (2) IncP, which denotes incomplete physics and ignores the energy volume factor $\varphi$ in the potential energy field DE, making it incomplete.

Figure 3 shows the comparison of the two variants with regard to all metrics for different datasets. From the results, we have the following observations: (1) STDEN surpasses NoP by a large margin, demonstrating the superiority of deploying potential energy fields to model traffic flow. (2) That IncP beats UnkP shows the effectiveness of the potential energy field DE. The guidance of physical process expressed by the potential energy field DE introduces the diffusion process of energy in space. This allows IncP to capture the changing trend of potential energy fields throughout the road network. (3) However, IncP performs slightly worse than STDEN because of the absence of the energy volume factor $\varphi$. Without $\varphi$, IncP has to infer the potential energy only through the energy density, which is as hard as to calculate the mass of an object from density without object volume.

During the solving process of the differential equation network, we utilize an ODE solver which allows our method to dynamically balance the trade-off between prediction accuracy and the computation cost. As shown in Figure 4(a), 4(b) and 4(c), required number of function evaluation (NFE) increases consistently with the epochs, there is no stable stage because we set early stopping for the training process. Note that NFE varies with the difficulty of tasks. For example, flow prediction of GT-221 is the most complicated among all three tasks because the traffic flow in GT-221 changes more drastically. Therefore, the NFE is around 80% more than that of ZGC-564. From Figure 4(d), 4(e) and 4(f), it can be observed that the more evaluation (NFE), the lower the prediction error our method can achieve. This allows us to trade accuracy for faster response for emergency events during inference phase, which is very valuable in practice.

In this part, we qualitatively analyze why our STDEN can yield good performance. To this end, we visualize the learned potential energy and the real traffic flow in Figure 5.

Figure 5(a) and (c) shows the potential energy learned by STDEN and UnkP by a heat map, with real traffic flows at the corresponding moment represented by arrows. To see more clearly how the potential energy drives traffic flow, we select loop areas with complex traffic for detailed analysis. In Figure 5(b), traffic always flows along the road network from a place with high potential energy to a place with low potential energy. Besides, the gradient of potential energy roughly reflects the relative magnitude of the traffic flow. This shows that potential energy governed by physical equation captures the mechanism of traffic flow and can be interpreted as a force that drives traffic flow. However, without the guidance of potential energy field DE, the energy learned by neural networks in UnkP (Figure 5(d)) has no physical meaning and can not indicate the traffic flow mechanism. For example, there are some traffic flows that transport from a low-value node to a high-value node in Figure 5(d), which violates the physical constraint of the energy transport process.

In a word, the results in this section verifies that STDEN can capture the physical mechanism of traffic flow (Figure 5) and generate accurate predictions (Table 3) under the guidance of the potential energy field DE. This is because we combine the advantages of physics-based and data-driven methods.