Predicting Traffic Congestion Evolution: A Deep Meta Learning Approach

1 Introduction

Accurate prediction of congestion evolution (such as how the congestion propagates or diminishes across road segments) benefits many traffic management applications, such as traffic prediction [Nguyen et al., 2016], route planning, and bottleneck identification. Existing works on congestion evolution prediction typically rely on data mining techniques [Nguyen et al., 2016]. In these works, pattern mining is applied on historical traffic data to obtain frequent patterns from causality tree/graph [An et al., 2016; An et al., 2018]. These patterns (subtrees, subgraphs) are then utilized for congestion evolution prediction [Nguyen et al., 2016;

∗ corresponding author

Xiong et al., 2018]. The quality of such predictions is limited to the inherent properties found in the available patterns. These evolution patterns usually cannot sufficiently capture many realistic characteristics of true congestion evolution such as the significant variation in spatiotemporal range and granularity, and the asymmetric transitivity of congestion propagations.

Factors that will impact congestion evolutions include road characteristics (e.g., road type), Points of Interests (POIs, e.g, school, shopping mall) [Zhang et al., 2017], and weather conditions. However, existing works often do not consider the extent of influence that these factors have on congestion evolution, such as the time-varying impact of static factors (e.g., POIs) [Liao et al., 2018]. For example, a stadium holding large social event (e.g. football game) is likely to cause unexpected congestions; schools tend to affect the traffic only during morning peak, lunch time, and evening peak hours. In this paper, we develop methods to incorporate the abovementioned factors with time-varying impact on congestions to predict the congestion evolution between any road pairs.

The contributions of our work are summarized as follows.

• We propose a representation learning framework to characterize and predict congestion propagation/decay between any pair of road segments. This departs from existing methods that mostly rely on causality trees/graphs and mining propagation patterns.
• We are the first to characterize traffic congestion evolution (propagation/decay) using dynamic attributed networks (DANs). Various factors with time-varying impacts are incorporated into DANs as node attributes. These include static attributes (e.g., POIs, road characteristics) and dynamic attributes (e.g., traffic speed).
• We propose a Deep Meta Learning Model (DMLM) for learning representations of road segments that support accurate prediction of congestion evolution. Meta learning is used to learn the evolving strengths of temporal correlations at multiple scales based on DAN attributes. DMLM also employs meta-Attention modules to merge heterogeneous features while learning the time-varying impacts of both dynamic and static features.
• The performance of our framework on two congestion evolution behaviors, congestion propagation and congestion decay, is evaluated using real-world dataset. Re-

sults show that our framework significantly outperforms all state-of-the-art methods.

2 RelatedWork

Traffic Congestion Evolution. Many efforts have been undertaken to model congestion evolutions at three levels of granularity, i.e., macroscopic, microscopic, and mesoscopic. Macroscopic level formulates congestion as a cluster of likewise congested roads [Anwar et al., 2016; An et al., 2016], while microscopic level studies congestion evolution among subsections within an individual road [Sun et al., 2018; Khajeh-Hosseini and Talebpour, 2019; Cui et al., 2019]. Our work focuses on mesoscopic level, which associates congestion with individual road segment and congestion evolution across adjacent road segments. [Nguyen et al., 2016; Di et al., 2019; Yue et al., 2018] formulate congestion propagations as directed edges from downstream to upstream roads. Causality trees and graphs are constructed based on the edges and data mining techniques are used to obtain frequent subtrees/subgraphs as evolution patterns (e.g., decay and propagation). Some works also considered congestion evolution prediction based on the obtained evolution patterns. Most works at mesoscopic level rely on tree or graph structure to mine patterns and make predictions. However, such representation limits the design space of predictors due to the dependency on structural patterns.

Link Prediction on Network. The core idea of congestion propagation prediction is similar to link prediction on complex networks (e.g., social networks), which predicts new relationships (links). Similarity based methods, which assumes that two nodes are similar if they in close proximity or are connected to similar nodes, are most widely used for link prediction [Mart´ınez et al., 2016b]. Local similarity is learned based on local neighborhood information [Mart´ınez et al., 2016a], while global similarity relies on the topological information of the entire network [Lichtenwalter et al., 2010]. In general, similarity-based methods only focus on static structural information and neglect the evolving changes in the networks. In practice, nodes are often affiliated with rich attributes that co-evolve with network structures. As such, there has been a lot of interest to incorporate structure information and node attributes for link prediction [Li et al., 2018; Zhang et al., 2018]. However, existing works typically ignore the temporal characteristics in dynamic networks, and fail to capture long and short term node interactions. Link prediction on DANs is still currently an emerging area of research. In this paper, we study evolution prediction that takes into account dynamic traffic congestion networks (evolving topological structures), and their temporal characteristics (timevarying impacts of various factors on congestion evolution).

3 Constructing Congestion Evolution Networks

This section presents our method to construct attributed networks for modeling congestion evolution (propagation and decay), as shown in Figure 1 (a). The attributed networks capture dynamic congestion evolution using various types of temporal links, while incorporating both static and dynamic node attributes.

Traffic Network. The traffic network is represented as a DAN GC = {GtC }, where GtC = {V,E,Ct }, t is time slice (1 ≤ t ≤ T, there are T time slices in total), V = {r1, ..., rN} is a set of N vertice (each vertex is a road segment), E = {(i, j)} is a set of undirected edges (an edge (i, j) ∈ E indicates that ri and rj are spatially connected). V and E capture static topology information that remains unchanged over time. Matrix Ct ∈ {0, 1}N represents traffic congestion of all N road segments at time t. cti is an element in Cwhere cti = 1 if road ri's traffic state is congested at time t, otherwise, cti = 0. To capture congestion propagation and decay behaviors on the traffic network, two DANs, GP and GD, are constructed based on GC, as shown in Figure 2.

Attributed Propagation Network. GtP = (V t P ,EtP ,ADtP ,AStP ), where set V t p ⊆ V is a subset of V which includes road segments involved in propagations; EtP = {(i, j)} is a set of directed links, (i, j) ∈ EtP represents a congestion propagation from ri to rj at time t; ADtP is a matrix of dynamic attributes associated with set V t P and each vertex has Fd dynamic attributes (e.g., traffic speed, time indicator, weather); AStP is a matrix of static attributes associated with set V t P , and each vertex has Fs static attributes (e.g., POIs, road characteristics). The DAN GP is constructed in the following way, as shown in Figure. 2 (a). The congestion states at time t and t + 1 are illustrated in the upper box, based on which a set of congestion propagation paths are detected. Specifically, road r5 is congested at time t, then road r3 and r1 become congested from time t to time t + 1. This indicates that the congestion on r5 propagates to r3 and r1 (similarly, r6 propagates its congestion to r7). Formally, a path pa = 〈ri1 , .., rik , ..., riK 〉 is a propagation path if (ij, ij+1) ∈ E (1 ≤ j ≤ K - 1); cti1 = 1, ctij = 0 and ct+1 ij = 1(2 ≤ j ≤ K). All nodes in the obtained propagation paths are included in set V t P , and any link appearing in the propagation paths is included in set EtP . The static attributes AStP contain two parts: road characteristics and surrounding POIs. Road characteristics contain road length, number of lanes, number of bus stops and traffic signals, and road type, where one-hot encoding is applied to distinguish between 19 road types (e.g., highway, primary road, etc.). The POIs are grouped into 14 categories (Section 5.1). The POI distribution around a road segment ri (located in a circle area centered at the middle point of ri) is formulated as a vector of the number of POIs in each category. Thus, each ri has a vector of dimension 14. The dynamic attributes AStP of ri at time t contain: historical speeds of previous W time slices; historical daily and weekly average speed at time t (long term periodicity); time indicator such as time-of-day and day-of-week; holiday indicator ('1' indicates a holiday while '0' otherwise); and weather conditions in hourly granularity (e.g., raining, sunny, rainstorm, etc.) represented using one-hot coding.

Attributed Decay Network. Similar to GtP , the DAN GtD = (V tD ,EtD ,ADtD ,AStD ) is defined to capture the decay behaviors based on GC at time slots t - 1, t, and t + 1, as shown in Figure 2 (b). Gt-1 c contains a congestion cluster C tm consisting of 4 congested road segments that are spatially connected. The congestion cluster contracts over time in the following way. Nodes 2 and 3 released their congestion states from time t - 1 to t, then their neighboring nodes 5 and 6 released their congestion states from time t to t + 1. In this process, there are two congestion decay paths, i.e., r2 → r5 → r6 and r3 → r5 → r6, where nodes 2 and 3 are sources of congestion decay. Formally, a path pa = 〈ri1 , .., rik , ..., riK 〉 is a decay path if (ij, ij+1) ∈ E (1 ≤ j ≤ K - 1); ct-1 ij = 1(1 ≤ j ≤ K); cti1 = 0, ctij = 1(2 ≤ j ≤ K), and ctij = 0(1 ≤ j ≤ K) (consequently released). With the obtained decay paths, GtD can be constructed by including all nodes of the decay paths into set V tD and all links of the decay paths into set EtD . ADtD and AStD are constructed in the same way as ADtP and AStP .

Congestion Evolution Prediction. The congestion evolution prediction problem is formulated as a link prediction problem on DAN: Given a DAN (e.g., GP , GD), predict the existence of directed links from a road segment ri to rj , based on dynamic topological structures and diverse node attributes.

4 DMLMModel for Evolution Prediction

Figure 1 (b) shows the framework of Deep Meta-Learning Model (DMLM) for predicting congestion evolutions, which consists of 5 main steps: 1) Generating asymmetric initial representation by incorporating multiple temporal correlations while preserving structure and asymmetric transitivity; 2) Learning multiple evolving temporal correlations using meta-LSTM modules based on static and dynamic node attributes; 3) Learning time-varying significance for fusing heterogeneous features using meta-attention modules; 4) Generating final source and target representations by fusing learned latent features as well as their time-varying significance. 5) Predicting the propagation/decay between road pairs based on the obtained representations. The DMLM models for propagation prediction and decay prediction are trained separately. In the rest of the paper, we discuss how to build the model for propagation prediction. The model for decay prediction is obtained in the same way.

4.1 Asymmetric Initial Representations

As the congestion propagation is inherently asymmetric, i.e., the possibility of propagation from ri to rj is different from that of rj to ri, we propose to learn asymmetric representations [Ou et al., 2016; Zhou et al., 2017] for the road segments. For an APN GP , we generate a source representation epsrc i,t and a target representation eptrg i,t for each node ri at time t. Then a function φ takes epsrc i,t and eptrg j,t as input variables to predict the likelihood of existence of propagation from ri and rj. Due to the asymmetric property, φ(epsrc i,t , eptrg j,t ) ̸= φ(epsrc j,t , eptrg i,t ) ∈ [0, 1].

Three auxiliary matrices are constructed to capture diverse temporal dependencies of evolutions, e.g., recent dependency, daily periodicity, and weekly repeatability [Sun et al., 2019; Lv et al., 2018]. Given APN GP , we build 3 matrices for each time slice t, i.e., recent, daily and weekly propagation trend matrices: M tP,re , M tP,da , and M tP,we . Specifically, the matrix M tP,re , M tP,da and M tP,we characterize recent traffic, daily periodic and weekly periodic patterns, respectively. They are constructed as f(lx, Tx) = 1 lx ∑lx l=1 M t-T x∗l P , where M tP ∈ {0, 1}N×N and M tP (i, j) = 1 when {i, j} ∈ EtP of GP , lx is the number of previous days/weeks considered, Tx is the number of intervals per day/week (Tx = 288 for one day when the time slot is 5 minutes ). For M tP,re , (lx, Tx) = (6, 1), for M tP,da , (lx, Tx) = (7, 288), and for M tP,we , (lx, Tx) = (6, 288 ∗ 7). The aforementioned parameters are based on the settings from [Guo et al., 2019].

M tP,re , M tP,da and M tP,we are fed into an Non-negative Matrix Factorization (NMF) module (as shown in Figure 3 (a)) [Lee and Seung, 2001] to generate initial representations (3 source representations and 3 target representations corresponding to M tP,re , M tP,da and M tP,we respectively). The representations episrc,t re,i and epitrg,t re,i for ri at time t is obtained based on M tP,re by solving an objective function: min‖M tP,re -Stre (Ttre )T ‖2 , s.t. Stre ,Ttre ≥ 0, where episrc,t re,i ∈ RK is the ith row of matrix S ∈ RN×K , and epitrg,t re,i is the ith row of the transposition of matrix T ∈ RK×N (i.e., (T)′ ). episrc,t da,i , epitrg,t da,i , episrc,t we,i , and epitrg,t we,i are calculated in the same way.

4.2 Meta-LSTM Component

The constructed APN GP and ADN GD have included diverse factors (attributes), which can be used to identify impressionable congestion evolutions. This section introduces a Meta-LSTM module to learn the evolving temporal correlations from multiple views. As shown in Figure 3 (b),

�����

Figure 3: The three main components of DMLM: (a) Generating asymmetric initial representation, (b) Learning evolving temporal correlations using meta-LSTM, (c) Learning time-varying significance for feature fusion using meta-attention.

the Meta-LSTM component processes the source representation part and the target representation part separately, using two separate modules of the same structure. Each part has three separate meta-lstm modules, which fuse multi-view temporal correlation information (recent, daily, and weekly patterns) using heterogeneous weights that are learned via meta-learning based on diverse node attributes of APN GP . Taking meta-lstm-ws for learning source representation based on GtP as an example, the inputs involve three parts: representation of weekly propagation trend episrc we , static attributes ASP , and dynamic attributes ADP . meta-lstm-rs produces epasrc we ∈ RK .

As shown in Figure 3 (b), meta-lstm-we consists of a 3-layers LSTM module lstm-l that captures long-term and short-term dependency of dynamic attributes, a 2-layers FCN fcn-l that captures latent impacts of static attributes, and four meta learners for learning parameters in meta-LSTM (i.e., lstm-e). At each time step, the lstm-l learns a latent vector DLinf ∈ RDlml o from node ri's dynamic attributes ADtP (i) ∈ RFd (the i-th row of ADtP ), which incorporates dynamic latent information. The fcn-l learns a SLinf ∈ RDf ml o fromASP (i) ∈ RFs to incorporate static latent information. The knowledge learned from both static and dynamic attributes are concatenated before being fed into the four meta-learners, i.e., hinf = DLinf ⊕ SLinf . The four meta-learners learn weight parameters for input gate, forget gate, cell, and output gate in lstm-e module, based on hinf . Based on the learned weights frommeta leaners, the lstm-e takes episrc we as input to generate epasrc we .

The four meta learners are of the same structure as shown in Figure 3 (b). For example, the meta learners for output gate (ml-lstm-o) relies on four separate 2-layers FCN modules to learn 4 parameters for the output gate. Specifically, the four FCN modules (i.e., fcn-wio, fcn-who, fcn-bio and fcn-bho) take hinf as input and produce 4 parameters Wio ∈ RK×K , Who ∈ RK×K , bio ∈ RK , and bho ∈ RK for the output gate of lstm-e. In the same way, the parameters of lstm-e's other three parts (input gate, forget gate, cell) are learned using 3 meta learners. Then, lstm-e takes episrc we as input and produces epasrc we based on following equations:

where ◦ is Hadamard product, and σ is sigmoid functuion.

4.3 Meta-Attention Component

APN GP has included various factors that impact the traffic situations. The dynamic as well as the static attributes have time-varying impact on the congestion evolutions (as highlighted earlier). To capture such dynamic significance, we designed a Meta-Attention component to merge multiple temporal correlations as well as static and dynamic attributes. As shown in Figure 3 (c), Meta-Attention component relies on two separate meta-attention modules to learn source and target representations (meta-atten-s and meta-atten-t). In meta-atten-s, a 3-layers LSTM layer (lstm-a) is used to learn a latent vector representation (DLimp ∈ RDf ma o ) for dynamic attributes and a 2-layers FCN layer (fcn-a) is used to learn a latent vector representation (SLimp ∈ RDf ma o ) for the static attributes. Then, himp = DLimp ⊕ SLimp is fed into a meta learner, meta-weight-s, to learn weight parameters for the attention module fcn-e. The meta learner uses two separate twolayers FCNs, fcn-Ws and fcn-bs, to learn weight matrix and bias terms for fcn-e. Then, fcn-e takes three initial representations (episrc re , episrc da ,episrc we ) together with three attributed representations (epasrc re ,epasrc da ,epasrc we ) as inputs, and produces corresponding six scores aepi re , aepi da , aepi we , aepa re , aepa da and aepa we based on the following equations:

With the Meta-Attention module, each node in GP obtains six attention scores for source representation learning: aepi re,src , aepi da,src , aepi we,src , aepa re,src , aepa da,src , aepa we,src ; and six attention scores for target representation learning: aepi re,trg , aepi da,trg , aepi we,trg , aepa re,trg , aepa da,trg , aepa we,trg .

4.4 Fusion and Prediction

For a road segment ri at time t in APNGP , a source representation epsrc ∈ RK and a target representation eptrg ∈ RK are obtained via the following fusion process.

The likelihood of a directed link from ri to rj is calculated as inner product of ri's source representation and rj's target representation, i.e., yp (i, j) = σ(epsrc i · eptrg j ), σ is sigmoid function. There exists a link if yp (i, j) ≥ 0.5 and no link otherwise.

Loss function . The loss function for training DMLM to predict propagation behavior is defined as follows.

where n is the number of samples, yp k is prediction, and ˆ yp k is ground truth.

5 Experiments

5.1 Dataset

Road Network. The road network for our experiments is obtained from OpenStreetMap 1 , which covers a rectangle area in Downtown of Singapore (Southwest: 1.2718, 103.8002; Northeast: 1.3323, 103.8653) consisting of 1858 road segments. The topological information and static attributes of roads are extracted (as discussed in Section 3).

POIs. The POIs are collected from government website 2 . We group all POIs into 14 categories: shopping services, religion building, business, hotel, residence, education, food, government, scenic spot, medical care, sports, entertainment, bus stop, MRT station.

Traffic Data. The historical traffic speeds are calculated based on bus trajectories derived from bus arrival data 3 . Speeds are aggregated every 5 minutes. Then, a road segment is detected as congested at a time interval if its traffic speed is slower than a threshold value. Similar to existing works[Nguyen et al., 2016], we tested several thresholds, i.e., for ri, threshold θp i include different percentiles, denoted as p. p = 90% indicates that 90% of the ri's speed values in si

1 https://www.openstreetmap.org/export

2 https://data.gov.sg/dataset?q=Places+of+Interest

3 https://www.mytransport.sg/content/mytransport/home/dataMall .html

̂

̂

are larger than θp i . Thus, 10% of ri's speeds will be identified as congested in ci. The traffic data is collected from Aug. 01 to Nov. 30, 2018, where the data of the first 90 days (75%) is used for training and the remaining data is used for testing.

5.2 EvaluationMetrics and Baseline Methods

Metrics. The performance of the proposedmethods is evaluated using metrics accuracy and F1-score.

Baselines. 1) STC [Nguyen et al., 2016] extracts frequently appearing congestion propagation relationship by mining frequent subtrees. Then, a dynamic Bayesian network is constructed using the obtained patterns to predict propagations. 2) Pro-Graph [Xiong et al., 2018] works on a graph structure and predicts where certain congestions will propagate to the near future. 3) MMDNE [Lu et al., 2019] proposes temporal embedding method to incorporate evolution of dynamic networks at micro- and macro-level, and predicts links between node pairs. 4) GCN-GAN [Lei et al., 2019] considers non-linear characteristics and link weights in dynamic network leveraging on graph convolutional network (GCN), LSTM and generative adversarial network (GAN) for link prediction. 5) ANRL [Zhang et al., 2018] employs a neighbor enhancement autoencoder to model node attributes and a skip-gram model to formulate structures for learning node representations. Link prediction is then performed based on cosine similarity function. 6) node2bits [Jin et al., 2019] uses a time- and attribute-aware framework to study interactions of users in heterogeneous networks and predict whether two users correspond to the same entity. The first two baselines are the most recent works that investigate congestion evolution prediction problems. Baselines 3) and 4) are link prediction methods considering temporal dimension properties. Baseline 5) incorporates node attributes but ignore properties over temporal dimension, while baseline 6) considers both node attributes and temporal attributes. We also include the ablation version of our method by removing major components. 7) Ours-woML (without meta-LSTM) employs the original LSTM instead of the meta-LSTM structure. 8) OurswoMA (without meta-Attention) employs a widely used attention mechanism instead of the proposed meta-Attention structure.

̂

̂

5.3 Experiment Setup and Hyper-parameters

We implemented the DMLM model using PyTorch framework on Intel(R) Xeon(R) CPU E5-1650 v2 @ 3.50GHz with 32G RAM. The source code is available at https://github.com/HelenaYD/DMLM. The critical hyperparameters are optimized via grid search as follows. Size of hidden layers of meta learners's FCNs in Meta-LSTM and Meta-Attention: ˆDml h = 64, ˆDma h = 8; Size of hidden and output layers in lstm-l and lstm-a: Dlml h = 16, Dlml o = 8, Dlma h = 8, Dlma o = 32; Size of hidden and output layers in fcn-l and fcn-a: Df ml h = 4, Df ml o = 16, Df ma h = 4, Df ma o = 8; and the dimension of final representations K = 4. For decay prediction, the above parameters are set to: 16, 16, 64, 8, 128, 8, 64, 16, 16, 8, respectively. In addition, the learning rate is 0.0001 and the batch size is 40.

5.4 Results and Analysis

Table 1 and Table 2 show the comparison with 6 baselines and 2 ablation versions of our method. In addition to testing the prediction performance on congestion propagation, we also predict the congestion decay by training another DMLM using ADN GD. The results show that our method outperforms all the baselines in both accuracy or f1-score for both propagation and decay prediction. STC and Pro-Graph are designed for congestion propagation, and cannot be easily extended to decay prediction. Thus we only tested their performance on propagation prediction. Pro-Graph obtains comparable accuracy with our DMLM when p = 90% as it relies on propagation patterns (e.g., repeatability) to make predictions. As such, it produces higher accuracy for heavy congestions that repeat frequently, and the accuracy decreases rapidly with decreasing p. Both MMDNE and GCN-GAN considered temporal dependency and structure information but failed to obtain satisfying results. This indicates that it is critical to incorporate diverse node attributes in addition to the temporal dependency and network structure information. On the other hand, ANRL considered node attributes but ignore temporal dimension, leading to poor performance. In general, the baselines produce low-quality solutions because they either did not sufficiently incorporate the spatiotemporal correlations or failed to capture the dynamic significances of both the dynamic and static node attributes. On the other hand, Ours-woML and Ours-woMA produce obvious performance degradation for both propagation and decay prediction. This demonstrates that the Meta-LSTM and Meta-Attention modules play important roles in the DMLM. In addition, combining NMF with diverse temporal dependencies captures the underlying evolution trends, which makes prediction more stable.

Figure 4 illustrates the impacts of several factors on the prediction performance, including ˆDml h , ˆDma h , Dlml h , Dlml o , Df ma h , Df ma o , and K. These factors affect the dimensions of intermediate feature vectors. As shown in Figure 4 (a), increasing ˆDml h and ˆDma h first leads to perform improvement, and then results in performance degradation. In general, feature vectors that are too short cannot sufficiently characterize the complex correlations, while vectors that are too long not only fail to improve representation capability, but also lead to higher computation overhead. The parameters, e.g., Dlml h and Dlml o in Figure 4 (c), Df ma h and Df ma o in (d), also produce similar trends (the other parameters are not shown due to the page limit). The figure also shows that even under similar trends, the best parameter setting for propagation prediction is different from decay prediction.

6 Conclusion

This paper proposed methods to model and predict the likelihood of congestion evolution between any pair of road segments (connected via single or multiple paths). Dynamic attributed networks were constructed to incorporate both dynamic and static impact factors while preserving dynamic topological structures. A DMLM model was proposed to learn representations of road segments, which enable accurate prediction of congestion evolution. DMLM relies on meta-LSTM and meta-Attention techniques to incorporate the heterogeneous and time-varying impacts of multiple correlations, and various dynamic and static node attributes. Experiments on real-world datasets showed that the proposed method achieves significantly better results than all state-ofthe-art methods.

Acknowledgements

This research project is supported in part by the National Research Foundation Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme with the Technical University of Munich at TUMCREATE.