Spatio-Temporal Graph Neural Point Process for Traffic Congestion Event Prediction

In recent years, many deep learning algorithms based on spatio-temporal graph modeling have been widely introduced in traffic prediction. Most of them integrated various spatial graph convolution networks (GCNs) and temporal learning modules to extract the complex spatio-temporal dependencies from the structural data. STGCN (Yu, Yin, and Zhu 2018) is the first work to combine the GCN with 1D CNN for spatio-temporal learning. ASTGCN (Guo et al. 2019) involved the attention mechanism based on STGCN. Both DCRNN (Li et al. 2018) and T-GCN (Zhao et al. 2019) integrated the gated recurrent unit (GRU) and GCN for traffic prediction. To capture long-range temporal dependencies, both STGNN (Wang et al. 2020) and GMAN (Zheng et al. 2020) employed self-attention mechanism. Graph WaveNet (Wu et al. 2019), AGRNN (Bai et al. 2020) and DMSTGNN (Han et al. 2021) proposed adaptive graph convolution to enhance the spatial representation from the predefined graphs. To capture the continuous spatio-temporal dynamics, STGODE (Fang et al. 2021) first combined the neural ODE with the normal GCN. However, most previous works about traffic prediction can only predict the sequential data in regular time snapshots and fixed-length time window. This framework is hard to be directly adopted in traffic congestion prediction because congestion may be absent or sparsely distributed over a fixed-length time window.

Neural point process has been widely applied in event forecasting of different domains such as electronic medical records (Enguehard et al. 2020), social web (Okawa et al. 2019; Zhang, Lipani, and Yilmaz 2021) and mobility (Wu, Cheng, and Sun 2021; Zhu et al. 2021a). RMTPP (Du et al. 2016) first adopted RNN to encode the historical sequential events to obtain the intensity function. Mei et al. (Mei and Eisner 2017) proposed an exponential decay based continuous LSTM to model the event sequences. Zuo et al. (Zuo et al. 2020) introduced Transformer as the encoder for long-term sequential event learning. To address calculation of integral term for likelihood optimization, Omi et al. (Omi, Aihara et al. 2019) proposed to model the cumulative intensity function. However, these previous works only focus on the temporal point process. To consider the spatio-temporal dynamics, a few spatio-temporal neural point process models (Zhu et al. 2021b; Zhou et al. 2021; Chen, Amos, and Nickel 2020) have been proposed in recent years. However, these works can only handle the applications in the spatio-temporal continuous scenarios, which can not be introduced into the traffic congestion event prediction because the traffic networks are discrete in the spatial scale.

Given a road network with $N$ links $V(|V|=N)$, it can be defined as a graph $\mathcal{G}=(V,E,A)$. $E$ denotes the set of edges, whose connections between different links are characterized by the adjacency matrix $A$. The traffic states $\mathcal{X}_{n}$ (eg., link speed) on each link $V_{n}$ are dense features in the snapshots of certain time granularity. The sequential congestion events on each link $V_{n}$ can be defined as a finite set $\mathcal{S}_{n}=\{s_{n,i}\}(i=1,2,\dots,|\mathcal{S}_{n}|)$, where $|\mathcal{S}_{n}|$ denotes the length of the set. In this paper, each congestion event can be defined as a two-element tuple $s_{n,i}=\langle t_{n,i},d_{n,i}\rangle$, where $t_{n,i}$ and $d_{n,i}$ respectively denote the occurrence time and the duration of the $i_{th}$ congestion event on link $V_{n}$. Given a fixed-length historical time window $T$ for each sample, the traffic congestion event prediction task aims to predict the occurrence time and duration of the next congestion event based on the historical congestion events and traffic states.

The point process is one type of stochastic process to simulate the sequential events in a given observation time interval $[0,T]$. The process can be characterized by the conditional intensity function $\lambda(t|H_{t})$, which represents the intensity function of events at time point $t$ depended on the historical sequential events $H_{t}$ up to $t$. The computation of intensity function can be given as:

When the conditional intensity function and the time points $\{t_{1},t_{2},\ldots,t_{i}\}$ of the historical events are given, the probability density function can be obtained as follows:

where the exponential term in the above equation denotes the probability that no events occur in the time interval $[t_{i},t_{i+1})$. In addition, we can also obtain the probability density function to observe an event sequence $\{t_{i}\}_{i=1}^{n}$, which is defined as follows:

where $\tau$ is the inter-event time that illustrates the time interval between two different events. Many previous related works (Du et al. 2016; Omi, Aihara et al. 2019; Shchur, Biloš, and Günnemann 2019; Zhang et al. 2020) directly use the inter-event time as the basic feature of each event. Note that, the most crucial part of the point process is the intensity function, which is difficult to characterize in real-world applications. Hence, neural networks can be a fruitful tool to approximate it.

First, we adopt a fully connected layer to map the historical traffic states into high-dimensional representation $Z\in R^{N\times T\times D}$. $N$, $T$ and $D$ represent the number of links, the length of time window and hidden dimension respectively. The detail architecture of the spatio-temporal graph learning module is illustrated in Fig. 3.

From the spatio-temporal learning module, we can obtain the contextual link representation $H_{c}$ for sequential congestion events. Therefore, we define the congestion event representation as follows:

where $d_{e}\in R^{N\times L_{max}\times 1}$ denotes the historical duration of each congestion event after zero padding, $H_{e}\in R^{N\times L_{max}\times D}$ is the output representation.

As a multi-task learning framework, our model simultaneously optimizes the negative log-likelihood of the probability density function of the inter-event time and the absolute error of the duration prediction during the training phase:

where $f_{d}(\cdot)$ denotes the fully connected layer for duration prediction of the next traffic congestion, $\alpha$ denotes the trade-off ratio. We set $\alpha$ as 1 by default.

During the inference phase, the duration prediction of the next congestion can be obtained directly by the output of $f_{d}(\cdot)$. For the occurrence time of the next congestion event, our model can also efficiently generate the prediction in the following way. Given the historical congestion event occurred at time point $\{t_{1},t_{2},\ldots,t_{i}\}$, the predictive probability density function $p^{*}(t|t_{1},t_{2},\ldots,t_{i})$ of the time point $t_{i+1}$ of the next congestion event is calculated from eq. (2). In this case, we utilize the median time point $t_{i+1}^{*}$ of the probability density distribution $p^{*}$ to estimate $t_{i+1}$. Hence, bisection method is used here and a accurate prediction can be obtained through multiple rounds of iterations

We evaluate our model on Beijing dataset and Chengdu dataset which are collected from the mobile application Amap, as shown in Table 1. Each dataset is chronologically split with 60% for training, 20% for validation and 20% for testing. We utilize the traffic states, congestion event information and spatio-temporal indexes in the last six hours to predict the occurrence time and duration of the next congestion event. Note that, we only employ the link speed data with condition labels as traffic states data. The condition label is a binary variable that describes whether the road is congested or not for each time slot (5 minutes). And the congestion events are also collected based on the condition labels. Congestion event information includes inter-event times, duration and periodic features. Our model is implemented by Pytorch 1.5 with NVIDIA TESLA V100 GPU. We set the number of stacks of Transformer and GCN as 2, the number of self-attention heads as 4 in Transformer layer, the number of GCN layers as 2 and the number of flow layers in continuous GRU as 2 by default. The dimension of hidden representations in our model is set as 64 and the dimension of random matrix for adaptive graph is set as 10. We set the optimizer as Adam with learning rate 0.001 and the batch size as 16.

We compare our model with ten state-of-art baselines, which can be divided into three categories. Simple models: Historical Average (HA), Gradient Boosting Decision Tree (GBDT) (Ye et al. 2009) and GRU (Cho et al. 2014). Spatio-temporal graph-based models: DCRNN (Li et al. 2018), Graph WaveNet (Wu et al. 2019) and STGODE (Fang et al. 2021). Neural point process-based models: NHTPP (Mei and Eisner 2017), RMTPP (Du et al. 2016), THPP (Zuo et al. 2020) and FNN-TPP (Omi, Aihara et al. 2019). For the simple models, we only use the traffic congestion event information as the input features to directly predict the next congestion events. For the spatio-temporal graph-based models, similar to most traffic flow prediction tasks, we employ the core architectures of spatio-temporal graph networks for spatio-temporal representation learning and predict the link condition labels in the next six hours (the six-hour time window is long enough to guarantee coverage of next congestion events). And then we can obtain the occurrence time and duration of the next traffic congestion event for each link according to the predicted link condition labels in the future time window. For neural point process-based models, we use congestion event information for point process modeling to predict the next congestion events.

The evaluation metrics are mean absolute errors (MAE) and negative log-likelihood (NLL). Note that, we use NLL and MAE to evaluate the prediction of occurrence time. For the prediction of duration, we only use MAE. In subsequent experiments, MAE-t denotes the metrics for occurrence time while MAE-d denotes the metrics for duration. From the results in Table 2, we can observe that our model STGNPP consistently outperforms the sub-optimal baselines with around 10% improvements in terms of all metrics on the two datasets, which demonstrates the superiority of our proposed method. From the experimental results, both of spatio-temporal graph-based baselines and neural point process-based baselines are significantly stronger than simple baselines. This is because the simple baselines can neither model inter-event dependencies nor capture spatio-temporal hidden information. The spatio-temporal graph-based baselines can fully exploit spatio-temporal information but neglect to model the congestion events, while neural point process-based baselines are the opposite. By contrast, our proposed model can not only fully exploit traffic-related spatio-temporal dependencies, but also model the sequence of congestion events, thereby outperforming other methods with a large margin.

We conduct ablation study on both of the two datasets to evaluate the effectiveness of each crucial module in our model. As shown in Table 3, we compared STGNPP with following ablation variants: 1) GWNPP, which replaces the spatio-temporal graph learning module in our model with that in Graph WaveNet 2) w/o GCN, which removes all the GCN layers from our models 3) w/o Trans, which removes the Transformer layers from our model. 4) w/o GRU, which replaces the continuous GRU with the fully connected networks. 5) w/o continuous, which replaces the continuous GRU with the discrete GRU. 6) w/o Gated, which removes the periodic gated unit from the intensity function networks.

From Table 3, we can find that our complete model STGNPP outperforms all the ablation variants. Since Graph WaveNet is a recognized excellent model in traffic prediction, the superiority of our model to GWNPP suggests that Transformer can capture long-term dependencies better than temporal convolutions in traffic congestion prediction scenarios. Our model significantly outperforms w/o GCN and w/o Trans can demonstrate that capturing either spatial and temporal dependencies of traffic states in road networks can be beneficial for congestion event prediction. The variant w/o GRU can illustrate that the continuous GRU layer can capture the contextual correlations in historical congestion event sequences for more accurate prediction. To further investigate the effectiveness of continuous modeling of GRU flow architectures, we compare STGNPP with w/o continuous. The results indicate that either the instantaneous dynamics or the continuous dynamics of the contextual link representations have a non-negligible effect on the prediction of traffic congestion event. We also compare our model with the w/o gated to investigate the effectiveness of periodic gated unit in intensity function network. The comparison results reflect the importance of involving periodic information into intensity function.

Since some parameters could significantly affect the learning capability, we conduct parameter study to further investigate the effectiveness of our model. We select the number of GCN layers $l_{g}$ and the number of flow layers $l_{f}$ in continuous GRU, because $l_{g}$ is critical for the spatial dependencies learning and $l_{f}$ is critical for modeling the continuous sequential congestion events. The experimental results are shown in Fig. 5. We can find that the best setting for $l_{g}$ is 3 for the two datasets. When $l_{g}$ increases, the NLL of Beijing and duration MAE of the two datasets become worse. The reason may be that the over-smoothing problem of GCNs limits the improvement of performance. For $l_{f}$, the best value for the two datasets is also 3. With the increase of $l_{f}$, the NLL of Chengdu and duration MAE of the two datasets become worse. This is because too many layers for continuous GRU could cause the over-fitting problem.