STR-GODEs: Spatial–Temporal-Ridership Graph ODEs for Metro Ridership Prediction

Previous work did not support predictions over continuous or unequal density time intervals. To facilitate performance comparison between models, we follow the traditional prediction framework. Assuming N is the number of Metro stations, the time period T data can be expressed as $X_{t}=(X_{t}^{1},X_{t}^{2},...,X_{t}^{N})$, where $X_{t}^{i}\in\mathbb{R}^{2}$ represents the the passenger counts of inflow/outflow of the station i at time interval t. our target is to predict the future ridership sequence based on the observed historical values:

Suppose $Z(t)$ is the latent state including the ridership feature at time interval t, and $f(t,Z(t),\theta)$ is the function of ridership changing with spatial,temporal and ridership information. By Euler method, there is $Z(t+\Delta t)=Z(t)+\Delta t*f(t,Z(t),\theta)$.

The primal problem can be abstracted as we learn the ridership trend function $f(t,Z(t),\theta)$ according to the training data and pre-defined graph (Physical-Virtual Graph[22]), obtain the initial state $Z_{0}$ through the observation sequence, and predict the subsequent sequence.

Chen et al.[5] present a continuous-time, generative approach to modeling time series. Each trajectory is determined from a local initial state, $Z_{t_{0}}$ , and a global set of latent dynamics shared across all time series:

We follow the framework of Chen et al.[5] for both training and prediction. We modify the original ODE Block to make it suitable for graph network data, called GODE Block. As shown in figure 1, inspired by Rubanova et al.[29], we use the GODE-RNN structure to obtain the local initial state $Z_{t_{0}}$ by learning the spatial,temporal and ridership feature of $X_{t},X_{t+1},...,X_{t+n}$. In particular, due to the need to gather information from adjacent metro stations in GODE Block, we use GODE-RNN to learn the approximate posterior of local initial state $Z_{t_{0}}$ directly instead of learning the mean and standard deviation.

Furthermore, by combining the ridership information and its hidden state, we further improve the performance of the prediction model so that it can reduce the cumulative error over a long time series.

In this section, we follows the pre-defined graph proposed by PVCGN[22] to learn spatial information. In our work, the physical graph, similarity graph and correlation graph are denoted as $\mathcal{G}_{p}=(\mathcal{V},\mathcal{E}_{p},W_{p})$, $\mathcal{G}_{s}=(\mathcal{V},\mathcal{E}_{s},W_{s})$ and $\mathcal{G}_{c}=(\mathcal{V},\mathcal{E}_{c},W_{c})$, where $\mathcal{V}$ is a set of nodes represent real-world metro stations($|\mathcal{V}|=N$), $\mathcal{E}$ is a set of edges and $W\in\mathcal{R}^{N\times N}$ denotes the weights of all edges.

Physical Graph:$\mathcal{G}_{p}$is directly built based on the physical topology of the studied metro system. We first construct a physical connection matrix $P\in\mathbb{R}^{N\times N}$, where $P(i,j)=1$ if there exists an edge between node i and j, or else $P(i,j)=0$. Note that each diagonal value P(i, i) is directly set to 0.Finally, the edge weight $W_{p}$ is obtained by performing a linear normalization on each row:

Similarity Graph:The similarities of metro stations are used to guide the construction of $\mathcal{G}_{s}$. We construct a similarity score matrix $S\in\mathbb{R}^{N\times N}$, where the score S(i, j) between station i and j is computed with Dynamic Time Warping[3]: $S(i,j)=exp(-DWT(X^{i},X^{j}))$. Based on the matrix S, we select some station pairs to build edges $\mathcal{E}_{s}$ with a predefined similarity threshold 0.1 for HZMetro and by choosing the top ten stations with high similarity scores for SHMetro. Finally, we calculate the edge weights $W_{s}$ by conducting row normalization on S:

where $L(\mathcal{E}_{s},i,k)=1$ if $\mathcal{E}_{s}$ contains an edge connecting node i and k, or else $L(\mathcal{E}_{s},i,k)=0$.

Correlation Graph: We utilize the origin-destination distribution of ridership to build the virtual graph $\mathcal{G}_{c}$. First, we construct a correlation ratio matrix $C\in\mathbb{R}^{N\times N}$: $C(i,j)=\frac{D(i,j)}{\sum_{k=1}^{N}D(i,k)}$ where D(i, j) is the total number of passengers that traveled from station j to station i in the whole training set. Based on the matrix C, we select some station pairs to build edges $\mathcal{E}_{c}$ with a predefined similarity threshold 0.02 for HZMetro and by choosing the top ten stations with high similarity scores for SHMetro. Then, the edge weights $W_{c}$ is calculated by:

In general, the graph convolutional networks is a method to aggregate the information of neighbor nodes around the target node and can be expressed as[8, 19, 14, 32]:

where $x_{i}^{k}$ refers to the hidden state of node i in the k-th layer, $e_{i,j}$ refers to the eigenvector of the edge from node i to node j, $\square$ is the aggregation method of neighbor information, $\phi$ is the transformation method of neighbor information and $\gamma$ is a transformation that fuses one’s own feature with its aggregated neighbors’information.

These and related methods can be understood as special cases of a simple differentiable message-passing framework (Gilmer et al. 2017[13]):

where $h_{i}^{l+1}\in\mathcal{R}^{d}$ is hidden state of node $v_{i}$ in the l-th layer of the neural network. Incoming messages of the form $g_{m}(\cdot,\cdot)$ are accumulated and passed through an element-wise activation function$\sigma(\cdot)$. $\mathcal{M}_{i}$denotes the set of incoming messages for node $v_{i}$ and is often chosen to be identical to the set of incoming edges. It can also be expressed in the following form:

According to Neural ODEs[5], the hidden state h(t) can be defined as the solution to an ODE initial-value problem:

Inspired by R-GCN[30], we define our GODE-function by using learnable weights $\mathbf{\Theta}_{0}$ to learn the changes of stations latent states over time, and learnable weights $\mathbf{\Theta}_{r}$ to learn the association relationship between stations. For every station,there are:

For any time $t_{i}$, we can calculate the latent representation $Z_{t_{i}}$ by:

Rubanova et al. proposed using an ODE-RNN as the encoder for a latent ODEs model to learn the mean $\mu_{z_{0}}$ and standard deviation $\sigma_{z_{0}}$ of the approximate posterior $q(z_{t_{0}}|\{x_{i},t_{i}\}^{N}_{i=0})$ and the local initial state $Z_{t_{0}}=\mathcal{N}(\mu_{z_{0}},\sigma_{z_{0}})$.

As shown in algorithm 1, we made some modifications on ODE-RNN. We replaced ODESolve with GODESolve, which can be applied to graph data. We use GODE-RNN to learn the approximate posterior of local initial state $Z_{t_{0}}$ directly instead of learning the mean and standard deviation. The hidden state of ridership information is learned and stored in hidden, which is combined with $Z_{i}$ in RNNCell. In our work, we use the classical GRU[6] structure as the RNNCell. Specifically, the reset gate $r_{t}=\{r_{t}^{1},r_{t}^{2},\ldots,r_{t}^{N}\}$, update gate $z_{t}=\{z_{t}^{1},z_{t}^{2},\ldots,z_{t}^{N}\}$, new information $N_{t}=\{N_{t}^{1},N_{t}^{2},\ldots,N_{t}^{N}\}$ are computed by:

Before prediction, we convert the latent state $h_{0},hidden$ obtained from GODE-RNN to get $Z_{0},hidden$ with a transform block which is composed of a fully-connected layer, a tanh activation function, and a fully-connected layer.

Previous work uses Neural ODEs as decoder for prediction and when the sequence is long, the error will accumulate gradually. Similar to the GODE-RNN, We introduce ridership information and its hidden state into GODESolver through RNNCell structure, as shown in algorithm 2. The experimental results show that it can reduce the cumulative error over a long time series. Specifically, we use the classical GRU[6] structure described in session 3.5 as the RNNCell.

To evaluate the performance of our work, we conduct experiments on two real-world traffic: SHMetro and HZMetro²²2https://tianchi.aliyun.com/competition/entrance/231708/information.

SHMetro: The SHMetro dataset refers to the ridership data on the metro system of Shanghai, China. There are 288 metro stations connected by 958 physical edges. A total of 811.8 million transaction records were collected from Jul. 1st 2016 to Sept. 30th 2016, with 8.82 million ridership per day. Following the setting of PVCGN[22], for each station, we measured its inflow and outflow every 15 minutes by counting the number of passengers entering or exiting the station. The ridership data of the first two months and that of the last three weeks are used for training and testing, while the ridership data of the remaining days are used for validation.

HZMetro: The HZMetro dataset refers to the ridership data on the metro system of Hangzhou, China. There are 80 metro stations connected by 248 physical edges with 2.35 million ridership per day. The time interval of this dataset is also set to 15 minutes. Similar to SHMetro, this dataset is divided into three parts, including a training set (Jan. 1st - Jan. 18th), a validation set (Jan. 19th - Jan. 20th), and a testing set (Jan. 21th - Jan. 25th).

We have trained the official code of PVCGN[22], which has a small gap with the results of corresponding papers. To reduce the effect difference caused by different parameters and facilitate the model performance comparison, we keep the parameters in STR-GODEs the same as those in the official code of PVCGN.

We implement our STR-GODEs in Python with Pytorch 1.6.0 and executed on a server with one NVIDIA Titan X GPU card. The lengths of input and output sequences are set to 4 simultaneously. The input data and the ground-truth of output are normalized with Z-score Normalization³³3https://en.wikipedia.org/wiki/Standard_score before being fed into the network. The batch size is set to 8 and the feature dimensionality d is set to 256. The initial learning rate is 0.001 and its decay ratio is 0.1. We optimize the models by Adam[18] optimizer for a maximum of 200 epochs by minimizing the mean absolute error between the predicted results and the corresponding ground-truths. The best parameters for all deep learning models are chosen through a carefully parameter-tuning process on the validation set.

To evaluate the overall performance of our work, we compare STR-GODEs with widely used baselines and state-of-the-art models:

DCRNN: Huang et al.[16] proposed a deep learning framework specially designed for traffic prediction, which uses bidirectional random walks on graphs to capture spatial dependencies and an encoder-decoder architecture to learn temporal correlation. We implement this method with its official code.

Graph-WaveNet: Wu et al.[36] developed an adaptive dependency matrix to capture the hidden spatial dependencies, and used a stacked dilated 1D convolution component to handle very long sequences. We implement this method with its official code.

ST—ODEs: Zhou et al. applied the NODE to the prediction of urban flow grid maps. They concats the data over different time intervals, feeds it into CNN layer to get the initial state $Z_{0}$, and then uses the neural ODEs network for prediction.In this experiment, we reproduced the code and extended the ODE network to GODE network which can be used for graph data.

latent ODEs: Rubanova et al. refine the Latent ODE model of Chen et al. [5] by using the ODE-RNN as a recognition network, where ODE-RNN is generalized from RNNs with continuous-time hidden dynamics defined by ordinary differential. In the experiment, we modify its official code and extended the ODE network to GODE network which can be used for graph data.

PVCGN: Liu et al.[22] developed a Seq2Seq model with GC-GRU and FC-GRU to forecast the future metro ridership sequentially where Graph Convolution Gated Recurrent Unit (GC-GRU) is applied to learn the spatial-temporal representation and Fully-Connected Gated Recurrent Unit (FC-GRU) is applied to capture the global evolution tendency. We implement this method with its official code.

We measure the performance of predictive models with three widely used metrics - Mean Absolute Error (MAE), Root Mean Square Error (RMSE), and Mean Absolute Percentage Error (MAPE).

Conventional prediction experiment: Table 1 and Table 2 present the prediction performances in conventional prediction experiments of our STR-GODEs and representative comparison methods in HZMetro and SHMetro datasets. Compared with latent ODE, We can observe that the GODE network combined with ridership data and hidden states can indeed reduce the cumulative error. Compared with all other methods, STR-GODEs has achieved some improvement in most metrics.

Further more, we extract the prediction of ridership in peak periods(7:30-9:30 and 17:30-19:30) in conventional experiments, as shown in table 6 and table 7. We can observe that our STR-GODEs outperforms all comparative methods consistently on most metrics on both datasets. On HZMetro, we achieve a relative improvement of 4.13% in MAE metric compared with other optimal algorithms on average, 3.59% in RMSE and 4.28% MAPE. On SHMetro, we achieve a relative improvement of 4.32% in MAE metric compared with other optimal algorithms on average, 4.57% in RMSE and 1.84% MAPE.

Irregular prediction experiment: In order to compare the performance of different methods in continuous time or unequal interval time, we use a compromise experiment that the traditional method can also work.

In this experiment, assuming that $X_{t_{1}},X_{t_{2}},\ldots,X_{t_{N}}$ are the observed ridership sequence, where $t_{1},t_{2},\ldots,t_{N}$ is the random subsequence of $t-n+1,t-n+2,\ldots,t+1,\ldots,t+m$, our goal is to predict a the ridership sequence:

Table 3 and Table 4 present the prediction performances in irregular prediction experiments of our STR-GODEs and representative comparison methods in HZMetro and SHMetro datasets. Through the experimental results, we can see that Neural GODEs network is superior to the traditional method in irregular prediction and compared with other work, the superiority in effectiveness of the proposed STR-GODEs is verified.