STG2Seq: Spatial-Temporal Graph to Sequence Model for Multi-step Passenger Demand Forecasting

1 Introduction

The widespread adoption of on-demand vehicle (cars and bikes) sharing services has revolutionized urban transportation. Passengers can now easily discover available vehicles in their surroundings using apps running on smartphones such as Uber, Didi, and Ola. However, these new ride-sharing platforms still suffer from the age-old problem of low accuracy in predicting passenger demand. On the one hand, drivers often have to drive a long way before they can find passengers due to low demand volumes in their proximity; on the other hand, passengers may experience long delays in obtaining rides due to high demands around their locations. This mismatch often leads to the excessive waiting time of passengers and a loss of income and waster energy resources for the drivers [Bai et al., 2019]. In particular, accurate prediction of passenger demand over multiple time steps (i.e., multi-step prediction) in different regions of the city is crucial for effective vehicle dispatching to overcome the aforementioned mismatch problem.

∗Contact Author

Predicting passenger demand is a challenging task due to the complex, nonlinear and dynamic spatial-temporal dependencies: the future passenger demand of a target region is influenced by not only the historical demand of this region but also the demand of other regions in the city [Zhang et al., 2017; Yao et al., 2018]. Previous work have proposed to use time series models [Moreira-Matias et al., 2013], cluster models [Li et al., 2015], or hybrid methods [Zhang et al., 2016b] to capture the correlations. Recent works focus on leveraging the representation capabilities of deep learning methods. These methods usually employ RNN and its variants such as Long-Short Term Memory (LSTM) [Yao et al., 2018] networks to capture temporal correlation and CNN [LeCun et al., 2015] to extract spatial relationships from the whole city [Zhang et al., 2016a; Zhang et al., 2017] or geographically nearest regions [Yao et al., 2018]. Similarly, hybrid models that combine CNN and RNN (e.g., Convolutional LSTM (ConvLSTM) [Xingjian et al., 2015; Ke et al., 2017; Zhou et al., 2018]) are proposed to extract both spatial and temporal correlations simultaneously.

However, these methods suffer from the following drawbacks:

• CNN-based methods (including ConvLSTM) assume that a city is partitioned into small grids (such as 1km × 1km area), which does not always hold [Chu et al., 2018]. Moreover, these methods can only model the Euclidean relationships between near regions and remote regions but not the non-Euclidean correlation among remote regions with similar characteristics. Consider the example in Figure 1(a). Region A shares points of in-

terests with region D (university and shopping areas) rather than co-located regions B and C (which contain parks). Thus, the passenger demand in region A shows a stronger correlation with D rather than B and C.

• Current methods strictly rely on RNN-based architecture (e.g., hybrid CNN-LSTM and ConvLSTM architectures) to capture temporal correlations. However, typical chain structured RNN architectures require execution of a number of iterative steps (equal to the window size of the input data) to process the demand data, and therefore lead to severe information oblivion in modeling the long-term temporal dependency. Moreover, utilizing RNN as a decoder for multi-step prediction is known to cause error accumulation in every step and may result in faster model deterioration [Yu et al., 2018].
• The current research efforts do not capture the dynamics that may exist in temporal correlation accurately. Most of them only reflect the collective influence of historical passenger demands. However, each previous step may have different and time-varying influence on the target step. Figure 1 (b) illustrates a passenger demand time series for a particular region where the influence of t1, t2 and t3 on t4 varies significantly. Moreover, the importance of t1, t2, t3 on t4 is different from the importance of t5, t6, t7 on t8.

In this paper, we propose a sequence-to-sequence model for multi-step passenger demand forecasting that is based on Graph Convolutional Networks (GCN) to solve the issues above. Specifically, we formulate the passenger demand on a graph with each region in the city acting as a node. Multiple GCN layers are utilized to form a Gated Graph Convolutional Module (GGCM) to capture the spatial and temporal relationships at the same time. Based on the GGCM, two encoder modules named long-term encoder and short-term encoder are designed to encode historical passenger demand and integrate new predictions, separately. Compared to the chain structured RNN, the hierarchical GCN structure shortens the path to capture the long-range temporal dependency [Gehring et al., 2017]. Besides, having two distinct encoders allows our model to utilize last step's prediction to generate the next step's prediction without requiring a RNN to act as a decoder, which reduces the associated issue of error accumulation. Finally, we also take into account the dynamic temporal correlations and design an attention-based output module, which can adaptively capture these dynamics. Overall, the contribution of this paper can be summarized as follows:

• We formulate the citywide passenger demand on a graph and present a GCN-based sequence-to-sequence model for citywide multi-step passenger demand forecasting. To the best of our knowledge, this is the first work that purely relies on graph convolution structure to extract spatial-temporal correlations for multi-step prediction.
• We propose an attention-based output module to capture the effect of the most influential historical time steps on the predicted demand and the dynamism that is inherent in these relationships.
• We conduct extensive experiments on three real-world

datasets and compare our method with three baselines and eight discriminative deep learning based state-ofthe-art methods. The experimental results show that our model can consistently outperform all the comparison methods by a significant margin.

2 Notations and Problem Statement

Suppose a city is partitioned into N small regions, irrespective of whether grid [Zhang et al., 2017] or road network [Chu et al., 2018] based partitioning is employed. We represent the region sets as {r1, r2, ..., ri, ...rN}. At each time step t, a 2-D matrix Dt ∈ RN×din represents the passenger demand of all regions in time step t. Another vector Et ∈ Rde represent the time features in time step t, which includes time of day, day of week, and information about holidays.

Given the citywide historical passenger demand sequence {D0,D1, ...,Dt} and time features {E0,E1, ...,Et+τ}, the target is to learn a prediction function Γ(·) that forecasts the citywide passenger demand sequence in the next τ time steps. Instead of using all the historical passenger demand, we only consider the most recent h time steps demand sequence {Dt-h+1,Dt-h+2, ...,Dt} as input, which is a common practice in time series data analysis. Our problem is thus formulated as:

3 Methodology

The architecture of STG2Seq (Figure 2) comprises three components: (i) the long-term encoder (ii) the short-term encoder and (iii) the attention-based output module. Both the long-term encoder and short-term encoder comprise several serial spatial-temporal Gated Graph Convolutional Modules (GGCM), which can extract the spatial-temporal correlations simultaneously through the use of GCN along the temporal axis. We will elaborate on each component as follows.

3.1 Passenger Demand on Graph

We first introduce how to formulate the citywide passenger demand on a graph. Previous works assume that the passenger demand in a region is influenced by the demand in nearby regions. However, we argue that spatial correlation does not exclusively rely on geographic locations. Remote regions may also share similar passenger demand patterns if they have similar attributes, such as point of interests (POIs). Therefore, we treat the city as a graph G = (ν, ξ, A), where ν is the set of regions ν = {ri|i = 1, 2, ...N}, ξ denotes the set of edges and A the adjacency matrix. We define the connectivity of the graph according to the similarity of the passenger demand patterns among the regions.

where ϵ is a threshold to which will determine the sparsity of matrix A. To quantify the similarity in passenger demand between different regions, we use the Pearson Correlation Coefficient. Let D0∼t(ri) represent the historical passenger demand sequence for region ri from time 0 to t (in the training data). Then the similarity of region ri and rj can be defined as:

3.2 Long-term and Short-termEncoders

Most prior works only consider next-step prediction, i.e., predicting passenger demand in the next time step. They optimize these models by reducing the error incurred in the prediction for the next time step in the training stage without considering the subsequent time steps. Hence, these methods are known to deteriorate rapidly for multi-step prediction. Only a few works have considered the problem of prediction for multiple time steps [Xingjian et al., 2015; Li et al., 2018]. These works adopt an encoder-decoder architecture based on RNN or its variants (i.e., ConvLSTM) as the encoder and decoder. These methods have two disadvantages: (1) The chain-structured RNNs employed in the encoder iterate over one input time step at a time. Thus, they require an equivalent number (i.e., h) of iterative RNN units when using the historical data over h time steps as the input. The long calculation distance between target demand and previous demands could cause severe information oblivion. (2) In the decoder part, to predict the demand for time step T, RNN takes as input the hidden state and the prediction of the previous time step T - 1. Thus, the errors from the previous time step are carried forward and directly influence the prediction, which results in error accumulation in each future step.

Different to all these previous works, we introduce an architecture that relies on the long-term and short-term encoder operating simultaneously to achieve multi-step prediction without the use of RNN. The long-term encoder takes the most recent h time steps citywide historical passenger demand sequence {Dt-h+1,Dt-h+2, ...,Dt} as input to learn the historical spatial-temporal patterns. These h steps citywide demand are combined and organized into a 3-D matrix, shape h ×N × din. The long term encoder comprises a number of GCCMs, wherein each GGCM captures spatial correlation among all N regions and temporal correlation among k (the patch size, a hyperparameter) time steps, which we will elaborate on in Section 3.3. Thus, only h-1 k-1 iterative steps are needed to capture the temporal correlation over the h historical steps. Compared to a RNN structure, our GGCMbased long-term encoder significantly decreases the iterative steps, which can further decrease the information loss. The output of the long-term encoder is another matrix Yh shaped h×N×dout, which is the encoded representation of the input The short-term encoder is used to integrate already predicted demand for multi-step prediction. It uses a sliding window sized q to capture the recent spatial-temporal correlations. When predicting the passenger demand at time step T (T ∈ [t + 1, t + τ]), it takes the citywide passenger demand of the most recent q time steps, i.e., {DT-q,DT-q+1, ...,DT-1} as input. Except for the length of time steps (h and q in long-term and short-term, respectively), the operation of the short-term encoder is the same as the long-term encoder. The short-term encoder generates a matrix Y T q shaped q×N×dout as the near trend representation. In contrast to a RNN-based decoder, the prediction of the last time step is fed back exclusively to the shortterm encoder. Thus, the prediction error will be attenuated by the long-term encoder, which eases the severe error accumulation problem that is inherent in the RNN-based decoder model [Yu et al., 2018].

3.3 Gated Graph Convolutional Module

The Gated Graph Convolutional Module is the core of both long-term encoder and short-term encoder. Each GGCM consists of several GCN layers, which are parallelized along the temporal axis. To capture the spatial-temporal correlations, each GCN layer operates on a limited historical window (k time steps) of the citywide demand data. It can extract the spatial correlation among all regions within these k time steps. By stacking multiple serial GGCMs, our model forms a hierarchical structure and can capture the spatial-temporal correlations from the entire input (h for long-term encoder and q for short-term encoder, h > q ≥ k). Figure 3 illustrates the exclusive use of GCN for extracting spatial-temporal correlations, where we omit the channel (dimension) axis for simplicity. In literature, there is one similar work [Yu et al., 2018] to our GGCM module. Their work first employs CNN to capture temporal correlation and then uses GCN to capture spatial correlation. Our approach is significantly simplified compared to theirs, as we can extract the spatial-temporal correlations simultaneously.

The detailed design of the GGCM module is shown in Figure 4. The input of the lth GGCM is a matrix shaped h × N × C l (or q × N × C l for short-term encoder, we only use h in the following for simplicity), where C l is the input dimension. In the first GGCM module, C l is din (as notated in Section 2). The output shape of lth GGCM is h × N × C l+1 . We first concatenate a zero padding matrix shaped (k - 1) × N × C l and form the new input (h + k - 1) × N × C l to ensure the transformation do not decrease the length of the sequence. Next, each GCN in the GGCM takes k time steps data shaped k ×N ×C l as input to extract spatial-temporal correlations, which is further reshaped as a 2-D matrix N × (k · C l ) for GCN calculation. According to [Kipf and Welling, 2017], the calculation of a GCN layer can be formulated as:

where ˜ A = A + In (A is the adjecency matrix of the graph defined in Section 3.1, In is the identity matrix), ˜ Pii = ∑j ˜ Aij, X ∈ RN×(k·Cl ) denotes the reshaped k time steps demand, W ∈ R(k·Cl )×Cl+1 ) represents the learned parameters, Xl+1 ∈ RN×Cl+1 is the output of GCN.

Furthermore, we adopt the gating mechanism [Dauphin et al., 2017] to model the complex non-linearity in passenger demand forecasting. And Eq. (4) is re-formulated as:

where ⊗ is the element-wise product operation, σ denotes the sigmoid function. Thus, the output is a linear transformation ( ˜ P - 12 ˜ A ˜ P - 12 )XlW1+Xl modulated by a non-linear gate σ(( ˜ P - 12 ˜ A ˜ P - 12 )XlW2). The non-linear gate controls which part of the linear transformation can pass through the gate and contribute to the prediction. Besides, residual connection [He et al., 2016] is utilized to avoid the network degradation as shown in Eq. (5).

Finally, the h outputs from the gating mechanism are combined along the temporal axis to generate the output of one GGCM module shaped h × N × C l+1 .

3.4 Attention-based Output Module

As notated in Section 3.2, the long-term spatial-temporal dependency and recent time spatial-temporal dependency are captured and represented as two matrices Yh and Y T q for the target time step T. We concatenate them together to form a joint representation Yh+q ∈ R(h+q)×N×dout , which will be decoded by the attention-based output module to obtain the prediction (we omit T here and in the following for simplicity). The three axes of Yh+q are time, space (i.e., region) and channel (i.e., dimension), respectively.

We first introduce the temporal attention mechanism for decoding Yh+q. The passenger demand is a typical time series data as previous historical demands have an influence on the future passenger demand. However, the importance of each previous step to target demand is different, and this influence changes with time. We design a temporal attention mechanism to add an importance score for each historical time step to measure the influence. The score is generated by aligning the joint representation Yh+q = [y1, y2, ..., yh+q](yi ∈ R(N×dout) ) with the target time step's time features ET , which can adaptively learn the dynamic temporal influence of each previous time step changing with time. We define the calculation of temporal attention as:

where W Y 3 ∈ R(h+q)×(N×dout)×1 , W E 4 ∈ Rde×(h+q) and b1 ∈ R(h+q) are transformation matrices to be learned, α ∈ R(h+q) is the temporal importance score which is normalized by the softmax function softmax(·). The joint representation Yh+q is then transformed by the importance score α:

Inspired by [Chen et al., 2017] which showed that the importance of each channel is also different, we further add a channel attention module after the temporal attention module to find the most important frames in Yα = [Y1, Y2, ..., Ydout ] with Yi ∈ RN . The calculation of channel attention is similar to temporal attention:

where W Y 5 ∈ Rdout×N×1 , W E 6 ∈ Rde×dout , b2 are transformation matrices; β ∈ Rdout is the importance score for each channel. In the case that target demand dimension is 1, Yβ is our predicted passenger demand D′T . When the target demand dimension is 2 (predict both start-demand and enddemand [Yao et al., 2019]), we can simply conduct channel attention for each dimension and concatenate them together to form the predicted passenger demand D′T .

3.5 Optimization

The outputs of all the τ time steps constitute the predicted passenger demand sequence (D′t+1 ,D′t+2 , ...,D′t+τ ). In the training process, our objective is to minimize the error between the predicted and actual passenger demand sequences. We define the loss function as sum of the mean squared error between the predicted and actual passenger demand for τ time steps, written as:

where Wθ represents all the learnable parameters in the network. These can be obtained via back-propagation and Adam optimizer. Further, we use the teacher forcing strategy in the training stage to achieve high efficiency. Specifically, we always use the true value for short-term encoder instead of the predicted value when training the model.

4 Experiments

4.1 Experimental Setup

We use three real-world datasets in our comparisons:

• DidiSY: This is a self-collected dataset that consists of 1) share car demand data from Didi, the biggest online ride-sharing company in China; 2) Time meta, including time of day, day of week, and holidays; This dataset was collected from Dec 5th, 2016 to Feb 4th, 2017 in Shenyang, a large city in China. Each time step is one hour. We use the data from the last six days for testing while the rest for training.
• BikeNYC [Zhang et al., 2017]: The public BikeNYC dataset consists of the bike demand and the time meta. The bike demand covers the shared bike hire and returns data of CityBike in New York from 1 Apr 2014 to 30th Sept 2014. Each time step is one hour. To be consistent with previous works that used this dataset [Zhang et al., 2016a][Zhang et al., 2017], the last ten days' data are used for testing.
• TaxiBJ [Zhang et al., 2017]: The public TaxiBJ dataset contains taxi demand in Beijing from 1 Mar 2015 to 30th Jun 2015. Similar to the DidiSY dataset, TaxiBJ contains passenger demand, time meta, and meteorological data. Each time step is 30 minutes. The data of the last ten days is used for testing to keep consistent with previous works.

We implemented our model in Python with TensorFlow 1.8. Historical passenger demand length h is set to 12, sliding window size q and patch size k are both set to 3. At each time step, we use three evaluation metrics to evaluate the model: Root Mean Square Error (RMSE), Mean Absolute Error (MAE) and Mean Absolute Percentage Error (MAPE).

4.2 Experimental Results

Next-step Prediction Comparison

We first compare our method with three representative traditional baselines: 1) Historical Average (HA); 2) Ordinary Linear Regression (OLR); 3) XGBoost [Chen and Guestrin,

2016]; and eight discriminative state-of-the-art methods: 4) DeepST [Zhang et al., 2016a]; 5) ResST-Net [Zhang et al., 2017]; 6) DMVST-Net [Yao et al., 2018]; 7) ConvLSTM [Xingjian et al., 2015]; 8) FCL-Net [Ke et al., 2017]; 9) FlowFlexDP [Chu et al., 2018]; 10)DCRNN [Li et al., 2018]; 11) STGCN [Yu et al., 2018].

Because most state-of-the-art methods can only achieve next-step prediction, we use the first time step result of STG2Seq in this comparison. Table 1 presents the comprehensive comparison results. We observe the following: (1) deep learning methods always outperform non-deep learning methods such as HA, OLSR, and XGBoost, which shows the superiority of deep learning methods in capturing nonlinear spatial-temporal correlations. (2) Our model consistently achieves the best performance and outperforms other methods with a significant margin in all three datasets. More specifically, STG2Seq gains 2.6%, 4.9% and 2.3% relative improvements in RMSE; 0.4%, 2.6% and 3.6% relative improvements in MAE; 3.8%, 4.5% and 2.1% relative improvements in MAPE over the best state-of-the-art methods for the three datasets, respectively. The results indicate that our model can capture more accurate spatial-temporal correlations than the state-of-the-art.

Multi-step Prediction Comparison

Next, we compare our STG2Seq model with HA, ConvLSTM, and DCRNN, which are also capable of conducting multi-step prediction. Each method predicts the passenger demand in the following 3 time steps. Figure 5 presents the experimental results about RMSE and MAE in three datasets. We can observe that the prediction error for HA is large but consistent for all 3 time steps. ConvLSTM and DCRNN can achieve good prediction in the first time step. However, they deteriorate fast with time, especially with the DidiSY dataset. STG2Seq can achieve good prediction result for all time steps and deteriorates slower than ConvLSTM and DCRNN, which demonstrates that our method is effective and eases the error accumulation problem that is inherent in RNN-based decoder for multi-step prediction.

nature of our network design.

Prediction for Irregular Regions

Previous results rely on the assumption that the target regions are partitioned as regular grids. In this experiment, we investigate the feasibility of our method when the city is partitioned into irregular regions. The DidiSY dataset contains the precise GPS location of each service request. This allows us to re-partition the city (Shenyang) into sub-regions based on the road network, which results in irregularly sized partitions. Under this setting, our method is flexible and can be applied to the re-organized dataset without modification. However, most state-of-the-arts introduced in the next-step prediction comparison part cannot be used as they are only suitable to extract Euclidean correlations when the city is partitioned to equally sized grids. To benchmark our method, we include three better suited comparative methods, namely: Auto-Regressive Integrated Moving Average model (ARIMA), Seasonal Auto-Regressive Integrated Moving model (SARIMA) and Multiple Layer Perceptron (MLP). The results in Table 3 show that STG2Seq significantly outperforms the baselines, thus demonstrating its generality.

5 Conclusion

In this paper, we propose a novel deep learning framework for multi-step citywide passenger demand forecasting. We formulate the citywide passenger demand on a graph and employ the hierarchical graph convolution architecture to extract spatial and temporal correlations simultaneously. The long-term encoder and short-term encoder are introduced to achieve multi-step prediction without relying on RNN. Moreover, our model considers the dynamic attribute in temporal correlation by using the attention mechanism. Experimental results on three real-world datasets show that our model outperforms other state-of-the-art methods by a large margin.

Component Analysis

To evaluate the effect of each component on our model, we compare five variants obtained by (1) removing the short-term encoder, (2) replacing the temporal attention module by a 2D CNN layer (for reducing the dimension), (3) replacing the channel attention module by a 2-D CNN layer, (4) replacing the gate mechanism in GGCM by Relu activation function, and (5) removing the teacher forcing strategy when training the model. The experimental results on Bike NYC dataset are shown in Table 2. We gain three observations from this table. First, without the short-term encoder, the model degenerates to a single-step prediction model. Second, the temporal and channel attention modules not only improve the prediction accuracy but also slow down the rate of deterioration in multistep prediction, which demonstrates the importance of both parts and the effectiveness of our design. Third, the gating mechanism is better at modeling non-linearities when compared with Relu. The results also exemplify the progressive