Dynamic Graph Learning Based on Hierarchical Memory for Origin-Destination Demand Prediction

1 Introduction

In the past decade, with the rapid growth of traffic infrastructure, an extensive amount of high-quality traffic data is collected for the industry and the research community. This opportunity promotes multiple promising applications of Intelligent Transportation System (ITS) including traffic time estimation [Han et al., 2021], traffic trajectory prediction [Ma et al., 2019], and traffic demand prediction [Yao et al., 2018].

Almost all the traffic applications require a meaningful and successful representation for traffic nodes (e.g., road segments, metro stations), which involves spatial dependency among nodes and temporal dependency across time. Among these applications, traffic demand prediction, which has a significant influence on transportation planning, is a vital and attractive domain in ITS. Especially, the node-to-node OD demand prediction attracts more and more researchers in recent years since it can not only provide the number of passengers, but it can also show which target places passengers tend to choose, which implies a potential to better model human mobility and further benefit the whole system.

∗Contact Author

To solve the problems, researchers have proposed a variety of models based on cutting-edge deep learning methods, such as CNNs [Noursalehi et al., 2021], RNNs [Zhang et al., 2021] and Transformers [Sankar et al., 2020]. GNNs, as their potential to learn high-quality representation on graph, are utilized in OD demand prediction to mine the complex spatial dependencies, which has achieved considerable success [Wang et al., 2019]; [Shi et al., 2020]; [Wang et al., 2021].

Despite all the efforts, two important issues are rarely discussed: First, previous methods tend to divide the dynamic trips into multiple regular-spaced time slices, using OD matrix at each time slice to represent the demand during the corresponding time(e.g. [Zhang et al., 2021]). This process makes it easy to fit existing recurrent deep learning methods, but this data compression replaces raw time information with discrete-time slices and misses useful information. Second, previous methods consider node relations directly and simply. For example, some researchers view two nodes are closely related if there are a great number of passengers from one to another in the last period like [Shi et al., 2020]. However, they fail to distinguish between origins and destinations, which neglects relations between origin nodes that have similar demands.

This paper aims to address the above two issues and proposes a dynamic node representation framework for OD demand prediction. However, it is a nontrivial endeavor to design such a framework due to the following challenges: First, the time granularity about how to organize the historical OD demand matrix is hard to choose. Choosing too coarse time granularity will result in an inability to sense useful information such as the trend while choosing too fine time granularity will lead to substantial noise. How to handle the complex temporal dynamics of trips is fundamental to node representations. Second, relations between nodes are time-evolving.

Demand from two nodes to other nodes could be similar on weekdays and completely different on weekends. How to dynamically capture these relations is crucial to node representations. Third, the model is required to predict demand values on every pair of nodes. Due to demand imbalance, many OD pairs have no demand at a certain time. How to properly handle these pairs is also challenging to stable training.

In this paper, we propose a Hierarchical Memory dynamic graph representation learning framework for OD Prediction (HMOD). First, a hierarchical memory updater is designed to integrate the continuous-time information and multi-level discrete-time information. This updater avoids limits of time information loss in previous discrete-time methods. Meanwhile, it constantly updates memory for dynamic node representation by message passing scheme and a message fusion mechanism is provided to integrate hierarchical memories. Second, a spatiotemporal propagation module is designed to aggregate neighbor node representations. This module is based on real-time demand and treats origins and destinations as two different semantic entities. It can effectively exploit similar relations between origins instead of a mix of origins and destinations. Third, an output layer and a specially designed objective function are deployed to predict the OD matrix. The objective function relaxes the error of nodemand pairs to alleviate the influence of data imbalance.

The contributions of this work are summarized as follows:

• We design hierarchical memories to integrate discretetime information and continuous-time information of OD demand. To the best of our knowledge, it is the first time that traffic node representation learning is extended to the continuous-time dynamic graph view.
• We propose an origin-destination embedding module to aggregate neighbor information along conditioned random walks. The module views origins and destinations as different semantic entities and can thus distinguish them to avoid mixing two types of information up.
• Extensive experiments are conducted on two real-world traffic datasets to evaluate the performance of the proposed framework and key components. The results demonstrate that our framework significantly outperforms other state-of-the-art methods.

2 RelatedWork

2.1 ODDemand Prediction

With extensive trip data are recorded by traffic cards and APPs , researchers are attracted to solve a more fine-grained traffic demand prediction, OD demand prediction. A simple solution is directly taking OD matrix as a two-dimensional image and applying convolution-based or spectral-based methods on it, such as [Noursalehi et al., 2021]. This kind of method fails to capture the spatiotemporal dependencies because they are limited to consider further relationship and topology, which is complex but common in traffic. Along with the development of graph neural networks, some researchers view stations or zones as nodes in the graph and design a variety of frameworks to address the problem of learning spatiotemporal dependencies. GEML [Wang et al.,

2019] uses GNN and LSTM to perform grid representation and capture temporal patterns. DNEAT [Zhang et al., 2021] design a spatiotemporal attention network and exploit different time granularity to mine complex temporal patterns. Although amazing results have been achieved by these methods, they still face the problem of missing fine-grained patterns since they are all based on discrete-time snapshots to update the representation.

2.2 Dynamic Graph Representation Learning

Dynamic graph representation learning is a technique to maintain evolving node states with time going on, while traditional graph representation learning frameworks generate static representations ignoring the dynamic changing content. For example, GraphSAGE [Hamilton et al., 2017] and GAT [Veliˇckovi´c et al., 2017] train an unchanged embedding without considering inserted or removed edges.

Recently, Dynamic Graph Representation Learning methods are proposed to address the above issues. Generally, the methods can be divided into two categories. The first category is called Discrete-Time Dynamic Graph (DTDG). The DTDG methods firstly define a length τ and then will update the embeddings every τ unit time. DynamicTraid [Zhou et al., 2018] and tNodeEmbed [Singer et al., 2019] are the representative ones. Although previously mentioned OD prediction methods are all able to model evolving patterns of node representations, it faces severe problems to sense finegrained information. On the contrary, the second category, named Continuous-Time Dynamic Graph (CTDG), updates node representations when an event happens. It is a more natural way to update the embeddings since raw events come in sequence instead of coming as snapshots. The typical ones are TGN [Rossi et al., 2020], DyRep [Trivedi et al., 2019], JODIE [Kumar et al., 2019]. However, these methods could only capture temporal dependencies of limited time steps.

3 Preliminaries

The trip dynamic graph is formulated as G = (V, E), where V = {v1, v2, · · · , vN} is the set of N nodes and E = {e1, e2, . . . , eM} is the edge set of M edges. These nodes represent stations or regions in the real world. Each edge em = (um, vm, tm, fm) represents a passenger departed at tm from um to vm with associated feature vector fm ∈ RdF . The feature vector contains travel distance, weather, payment, and tips. At a specific time point t, the dynamic graph can be represent as Gt = (V, {em|tm < t}), which contains trips happened before t. The OD demand matrix during time interval from t to t + τ is denoted is Yt:t+τ ∈ RN∗N whose (i,j)-entry represents the volume from vi to vj during this time interval. The purpose of OD demand prediction is to predict future OD matrix Yt,t+τ given historical trip data as a dynamic graph Gt.

Problem 1. Given the dynamic graph Gt at timestamp t, it is expected to learn a function Ψ to predict the OD Matrix ˆYt,t+τ =Ψ(Gt), i.e.,

where ODLoss will be given in the next section.

4 Methodology

In this section, we will elaborate details of HMOD. The overall architecture is shown in Figure 1. First, we will introduce the hierarchical memory updater which maintains the node representations and dynamically update them based on message passing, which can preserve hierarchical time semantic information for nodes. Next, to generate high-quality messages for memory update, an Origin-Destination Node Embedding method is designed to aggregate neighbor information by spatiotemporal random walks. In the last part, the output layer and specially designed objective function are introduced for the final prediction and training.

4.1 Hierarchical Memory Updater

Historical trips, which are original edges with continuous timestamps, reflect OD demand and are fundamental to node representation. Previous methods like GEML generally count edges in a fixed time window and make its time discrete, which discards practical time information. The more coarse time granularity is to generate time windows, the more information is lost. Unlike previous methods, we propose to maintain hierarchical-time memories for nodes by a hierarchical memory updater to address this problem. On the one hand, a part of it views time as continuous features and is updated when an edge comes. On the other hand, another part maintains multiple discrete-time memories to reveal a macro node state. Further, a memory fusion mechanism is designed to mix each level's memory while keeping mainly receiving the corresponding level message. Formally, D + 1 memories H ∈ R(D+1)×dH = {H0 ,H1 ,H2 , · · · ,HD} are maintained on each node, where H0 represents continuous-time memory and Hd (d ≥ 1) represents macro discrete-time memory covering ∆Td time unit. Their updating methods are as follows.

Message Function

The above hierarchical memory aims to always maintain updated node states. When a memory updating process is triggered, that is to say for continuous-time memories there is a new edge coming and for discrete-time memories, ∆Td time unit passed by, we need to calculate a message to update node memories according to information triggered this update. For

b) Hierarchical Memory Updater

Figure 1: The Overall Framework of HMOD.

continuous-time memories, the message contains the last updated node states, encoding of the time gap from the last update, and aggregated neighbor information which will be discussed in 4.2. For discrete-time memories, the message contains the last updated node states, OD matrix during ∆Td, and aggregated neighbor information. For the specefic node i, the above message generation process can be formulated as:

where M0d ∈ RdM represents the message described above, ⊙ represents element-wise product, t-i represents last update time of node i, Yit-2d-1∆T,t means the i-th row of the OD matrix. W∗ and b∗ are learnable parameters. Θ(Hd , G) represents the time encoding, which is utilized to sensing different time span's different effect. Ωd(Hd ,G) represents the node embedding method. σ represents the ReLU function.

Message Fusion

The message directly computed by the previously mentioned message function only contains information on a specific track, i.e. continuous information or discrete information of a specific granularity. However, the continuous message may lack certain global spatiotemporal information while the finegrained spatiotemporal information may be absent in discrete messages. However, how to integrate other time granularity information while preserving own message is a challenging problem. To this end, a message fusion mechanism is proposed to integrate the specific track message with others to integrate multiple types of spatiotemporal information.

Formally, the latest message M ∈ R(L+1)×dM = {M0 ,M1 , · · · ,ML} is stored with corresponding memory, whereM0 is the output of message function andMl (l ≥ 0) is computed as follows. When computing Ml , other messages from other time level is first aggregated then concatenated withMl-1 . It is intended to mix information from other time granularity while maintain the corresponding time granularity information. The concatenation is then passed to a fully connected layer to calculate the result. Intuitively, if treating the updating process of a node's memories as a graph where each memory at a certain timestamp is a node, M0 represents node's feature andMl aggregate Ml-1 with its l-hop neighbor. This mechanism can be formulated as:

c) OD Matrix Calculation

where Mld refers to message of dth memory at lth layer, σ is ReLU function, Wpool , Wmess , bpool and bmess are learnable parameters. Besides, a visual explanation of the implication graph is present in Figure1 b).

Memory Updater

When the model has computed the message for each memory, another problem arises: how to effectively update memories while preventing the model from forgetting past information. Thus, due to the capability to memorize information with reduced parameters, GRU [Cho et al., 2014] is employed to update memories here. On account of a deeper message having more information, MLd is directly used as GRU's input, which can be formulated as:

Note that there exist extremely dense edges in OD prediction, for example, millions of edges may occur in a day. It would take too much time for the model to train with one edge each iteration. Thus, a message aggregator is designed to aggregate continuous-time messages of an edge batch and reduce the training time. To be specific, instead of simply average messages of multiple edges, we extend the last update memory with another item which both considers node states and influence of time in a batch as exponential decay. Then we replace the first H in M′ with the average of the concatenation memories in a batch. Formally, when d = 0, for the specific node i, equation (2) can be rewritten as:

where b represents edges departed at i in a batch. Note that the choice of the batch can be variant. The message of continuous memories can be aggregated every ρ edges while being aggregated every τ time unit is also acceptable. The latter is chosen in our implementation for convenience.

4.2 Origin-Destination Node Embedding

When embedding traffic nodes to feature space, it is crucial to consider spatial topology relations between nodes. Most previous works for OD demand prediction capture nodes' spatial relations in a direct and simple way; they mostly leverage simple GNNs on either predefined geographic graph or last transition graph. In summary, they treat origin nodes and destination nodes as the same semantic entities. However, it may not fit this problem to neglect different semantic meanings between the origin nodes and destination nodes. Besides, since the OD graph is a fully connected graph, simply aggregating all neighbors of a node may result in high computation complexity. Therefore, a random walk based Origin-Destination Node Embedding is proposed for an effective and efficient node embedding.

Random Walk Sampling

Random walk-based methods have achieved amazing success in graph embedding due to their ability to sense graph structure, e.g. DeepWalk [Perozzi et al., 2014], node2vec [Grover and Leskovec, 2016]. However, directly utilizing previous random walk methods will mix up semantic relations of origin nodes and destination nodes, which should be carefully considered in OD demand prediction. For the example in Figure 1 a), there exists a dense OD demand from v3 to v4 and from v3 to u at morning peak, where u and v4 are two working area and v3 is a living area. It appears that though there is little demand between u and v4, they are more likely to share a similar demand pattern to other nodes. Motivated by this, the following random walk procedure is designed to distinguish the semantic entities while aggregating neighbor information.

This procedure can be explained as a) keeping sampling forward edges and reverse edges alternately and recursively, b) keeping sampling reverse edges and forward edges alternately and recursively. For example, when calculating embedding for node u in Figure 1 a), a random sampling process first starts from OD forward edges with origin node u and get destination node v1. Then, OD reverse edges with destination v1 are random sampled to get origin node v2. Finally, a node-set with ω nodes is sampled, which is denoted as P 0 . For another random walk, a random sampling process starts from OD reverse edges with destination node u and gets origin node v3. Then, edges with origin node v3 are random sampled to get node v4. Finally, a node-set with ω nodes is sampled, which is denoted as P 1 . Repeatedly using the above two random walk strategies, 2ε walks are obtained. For each step, the random sample probability is formulated as:

where ϕ represents row-wise normalization to make the sum of probability equal to 1, d = 0 represents generating random walks according to continuous-time edges and d ̸= 0 represents generating random walks according to dth discretetime memories. When calculating messages for continuoustime memories, ˆ t is firstly initialized as the calculating time t. When sampled an edge (u, v, t′ ), ˆ t is changed to t'.

Intra-Walk Aggregation

Based on sampled walks from the dynamic graph, we propose an intra-path aggregation module to obtain walk representations. As described above, the walks contain nodes with different semantic meanings. Therefore, a special transformation layer is designed to project nodes' into the same embedding space, which passes the node sampled as the origin to a fully connected layer W O and passes the node sampled as the destination to a fully connected layer W D . After node content transformation, mean aggregator is applied to compute representation of a walk, which can be formulated as:

where HdP i j represents the dth memory of node P i j , which may be different from our previous definition. j = 2k means even position of a walk since even position and odd position has different semantic meaning, P 2t′ means even number of the walk since even number of walks start sampling from forwarding edges while an odd number of walks start sampling from reverse edges.

Inter-Walk Aggregation

After intra-walk aggregation for each walk embedding, an attention aggregation is designed to aggregate information from different walks, which can be formulated as:

whereWa , a are learnable parameters.

4.3 ODMatrix Prediction

Fusion and Prediction

If requiring predicting ODMatrix at timestamp t, the hierarchical memories at t are fused to make the prediction. Since each memory contain specific granularity information, the memories are concatenated to keep the hierarchical information. Then a MLP is adopted to make the prediction. The ith row of prediction result can be formulated as:

where Wo1 , Wo2 , bo1 , bo2 are learnable parameters.

OD Loss

One last problem is there exists a large number of zeros in OD matrix while predicting them as negative numbers are also acceptable in the real-world scene. Besides, since a heavy negative number and a slice negative number may contain different meanings, directly training them to be zero could lead to poor performance. Therefore, an OD Loss is designed based on MSE, which can be formulated as:

5 Experiments

5.1 Dataset

To verify the performance of our framework, extensive experiments are conducted on two real-world datasets.

Beijing Metro Beijing Metro dataset contains railway trip data in Beijing from June to July in 2018. The first 6 weeks are selected as the training set, the next 1 week as the validation set, and another next 1 week as the test set. This dataset covers 268 stations of Beijing Metro and has over 200 million timestamped edges in total.

New York Taxi New York Taxi dataset contains taxi trip data in New York from January to June in 2019. The first 139 days are selected as the training set, the next 21 days as the validation set, and the next 21 days as the test set. This dataset covers 63 regions of New York and has over 38 million timestamped edges in total.

5.2 Experimental Settings

The task is to predict OD demand matrix in the next τ = 30 minutes with historical trip data. Adam [Kingma and Ba, 2014] is used as the optimizer with learning rate 1e-4 for Beijing Metro and 1e-5 for New York Taxi, and the learning rate is chosen from [1e-2, 1e-3, 1e-4, 1e-5, 1e-6]. Memory dimension dH and message dimension dM are set to 128, which is chosen from [64, 128, 256, 512]. Each experiment contains 500 epochs and an early stop strategy with 20-epoch patience is used to avoid overfitting. The model is implemented using the PyTorch framework on a machine with Intel(R) Xeon(R) Gold 6130 CPU @ 2.10GHz and 4 Tesla T4

GPUs. PCC (Pearson Correlation Coefficient) and RMSE (Root Mean Squared Error) are adopted as metrics to evaluate the performance of our model.

5.3 Baseline Methods

• HA (Historical Average) computes the historical average of OD demand matrix as the prediction.
• LR (Linear Regression) is a regression model which exploits linear correlations between input and output. The input of LR contains the historical OD demand of one OD pair from the last 4 consecutive snapshots.
• XGBoost [Chen and Guestrin, 2016] adopts gradient boosting tree to learn from the previous pattern. The input of XGBoost is organized as the same as LR.
• GEML [Wang et al., 2019] is an OD demand prediction model based on snapshots and pre-defined neighborhoods. It adopts graph convolution along with a skipRNN to extract spatial and temporal patterns.
• DNEAT [Zhang et al., 2021] is another OD demand prediction model based on snapshots and node-edge attention. It adopts graph attention along with a dilated convolution to capture spatiotemporal dependencies among discrete-time snapshots of a dynamic graph.
• TGN [Rossi et al., 2020] is a continuous-time dynamic graph representation learning framework. This framework is deployed to OD prediction task by this paper.

5.4 Experimental Results

Table 1 shows the comparison results, where ≥ p means the accuracy in the case where truth-value ≥ p. The evaluation with different p indicates whether the methods perform well in different situations. The results show that our model outperforms all the baselines on both RMSE and PCC, both datasets, and all the situations. In BJMetro, TGN performs poorer than other OD prediction methods. This is because BJMetro has a larger amount nodes and edges, which may make it harder to find important neighbors for TGN. However, in New York Taxi, it performs better than other baselines, which demonstrates the effectiveness of continuoustime information in this scenario. Owing to hierarchicaltime node representations, the proposed method could capture fine-grained and macro information simultaneously and always perform well.

5.5 Ablation Study

Ablation on Hierarchical Memories

The effect of hierarchical memories on Beijing Metro is shown in figure 2. The HMOD-x refers to our model with x discrete-time memories, while HMOD - 4 is the setting in our model. For the convenience in our implements, the first discrete memory leverages δT = 30 mins input, and the k-th discrete memory leverages 2k δT mins input. The results show that only one continuous memory can achieve a significant result, which demonstrates the effectiveness of the continuous-time method. Besides, the more discrete-time information added, the better performance will HMOD achieve, which also reflects the importance of the discrete-time information.

Ablation on Main Modules

The impact of main modules on Beijing Metro is shown in figure 3. The w/o c refers to removing the continuous-time memory part and containing four discrete-time memories to predict ODMatrix. The w/o emb refers to removing the OD node embedding part. The w/o ODLoss refers to replacing our designed OD Loss with MSE loss. The w/o c outperforms other baselines demonstrating the effectiveness of our message passing framework, while it performs worse than HMOD reflects the need for continuous-time memories. Perhaps due to the fact that ODLoss makes the negative predicted demand acceptable, which makes sense in the real world, it improves the result significantly. Besides, the results on the w/o emb demonstrate that our OD node embedding plays an important role in predicting OD demand, which could learn an meaningful node embedding.

6 Conclusion

This paper aimed to solve the pairwise OD demand prediction problem and proposed a novel dynamic node representation learning framework, HMOD. A hierarchical memory updater powered by a memory fusion mechanism was proposed to integrate both continuous-time fine-grained spatiotemporal dependencies and discrete-time general spatiotemporal dependencies. This is the first time traffic node representation learning is extended by continuous-time dynamic graph view. Meanwhile, an OD node embedding method based on temporal conditioned random walks was also proposed to aggregate semantic information from previous neighbors. Experiments on real-world datasets showed high prediction accuracy and robustness of the proposed model.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (71901011 and U1811463)