TrafficStream: A Streaming Traffic Flow Forecasting Framework Based on Graph Neural Networks and Continual Learning

1 Introduction

In recent years, the development of the economy and society has prompted the construction of transportation facilities like roads, toll stations, subway stations, etc. To monitor the real-time traffic status of these facilities, the number of traffic sensors deployed also gains rapid growth. As a result, more high-quality traffic flow data is recorded, revealing the expansion of traffic networks and the evolution of traffic flows.

∗Corresponding Author

Traffic flow forecasting is one of the most crucial tasks of Intelligent Transportation System (ITS), which significantly affect our daily routines. Nevertheless, the intricate spatialtemporal correlation of traffic flow raises the difficulty of accurate forecasting. To tackle this problem, researchers introduce various cutting-edge methods into this field, such as CNNs [Zhang et al., 2017], LSTMs [Li et al., 2017] and Transformers [Wang et al., 2020c]. Impressed by the promising performance of GNNs on graph structure data, researchers are devoted to integrating GNNs into traffic flow forecasting model for mining dependency on spatial-temporal aspect, which becomes a great success [Yu et al., 2017; Song et al., 2020; Chen et al., 2020]. However, along with the improvement of model performance, there comes a considerable increase in the number of parameters. Besides, they still face the challenges of long-term streaming traffic networks.

The long-term streaming networks, referring to traffic networks with changing flows of nodes and expanding structures in a long-term period, i.e., several years, have been less studied, whereas the real-world scene is like this. The simplest way is to retrain a model every year. However, the massive amount of parameters of a new model are severe challenges to computing resources and the amount of data, especially when datacenters store data in a queue-like manner. Besides, it will be difficult to generate accurate predictions via less data from new added stations. Considering that previous models have been well trained and for resource conservation, it is natural to transfer their knowledge to the model in the current year.

Directly using previous models still needs to address two critical problems. Firstly, previous models should accommodate the new data. Unlike short-term data whose trends are more stable and regular, traffic flow patterns gradually evolve in the long-term streaming networks. The inconsistency between patterns of new data and historical data will reduce the accuracy of forecasting. Besides, due to network expansion, the topological structures of traffic networks corresponding to the new data are also different from the previous ones. So the spatial dependency captured by previous models may not be suitable anymore. Secondly, knowledge extracted by previous models should be consolidated as there is rich information about previously learned patterns 1 . Therefore, how to efficiently capture patterns from new data while consolidating historical knowledge becomes our motivation.

1 Previously learned patterns include long-term stable patterns and temporarily disappearing patterns.

For efficiency and effectiveness, we propose a Streaming Traffic Flow Forecasting Framework based on GNNs and Continual Learning, TrafficStream. On the one hand, we design a traffic pattern fusion approach to integrate the unknown patterns of new nodes and changing patterns of existing nodes into the model. To discover these new patterns, we propose an algorithm based on JS-divergence to measure the changes of node features depending on the model. On the other hand, in order to consolidate historical traffic knowledge and transfer it to the current model for better prediction, we adopt strategies of historical information replay and parameter smoothing from data and model perspectives, respectively. Finally, a long-term streaming network flow dataset is constructed to verify the performance of TrafficStream.

Our main contributions are summarized as follows:

• We explore the problem of streaming traffic flow forecasting based on GNNs. To our best knowledge, it is the first time that GNNs are introduced in the scenario of changing flows of nodes and expanding network structures in long-term streaming traffic networks.
• We propose a novel unified framework for GNN-based models to address the difficulty of fusing historical knowledge and new flow data. We design different components for training models on expanding networks and nodes with new evolutionary patterns. Information replay and knowledge smoothing components are adopted to consolidate historical knowledge.
• To verify the effectiveness and efficiency of our framework, we construct a long-term streaming network dataset, PEMSD3-Stream, based on real-world traffic data. The performance indicates the superiority of our model in consuming time with comparative accuracy.

2 RelatedWork

2.1 Traffic Flow Forecasting

Recent years have witnessed the rapid development of ITS, attracting researchers to solve one of the key problems, traffic flow forecasting. Statistical models, such as VAR [Zivot and Wang, 2006] and SVR [Castro-Neto et al., 2009] simplify the forecasting into individual time-series prediction. These methods failed to capture the spatial-temporal correlation between different locations. In addition, training such a model for all locations results in poor performance, while each location with a model will increase cost in both consuming time and storage. Along with the development of deep learning, researchers apply various frameworks to overcome the difficulty of understanding the pattern of spatial-temporal data. DMVST-Net [Yao et al., 2018] integrates CNN and longshort term memory (LSTM) to extract spatial and temporal dependencies. STGCN [Yu et al., 2017] introduces graph convolution for mining spatial patterns and CNN with the gated mechanism for temporal features. Graph WaveNet [Wu et al., 2019] is proposed to adaptively learn the spatial adjacency matrix and expand the receptive field along the time axis. STSGCN [Song et al., 2020] simultaneously models the spatial-temporal correlation via a localized spatial-temporal graph. Although these methods achieve impressive results on traffic flow forecasting task, they are not designed for long term streaming network scene.

2.2 Continual Learning on Graphs

Continual learning, also called as life-long learning and incremental learning, is a technique to train the model sequentially when data from different tasks arrives in a streaming manner. Generally, existing methods can be divided into three categories: regularization-based methods [Kirkpatrick et al., 2017], replay-based methods [Rolnick et al., 2019] and parameter isolation methods [Rusu et al., 2016], and all of them aim to learn knowledge from new tasks without forgetting knowledge from previously trained tasks. Traditional continual learning methods mainly focus on image processing, assuming that samples are independent to each other.

Recently, continual learning has been applied in the field of graph learning, which can deal with the efficient update of graph models, especially on large-scale dynamic graphs. ContinualGNN [Wang et al., 2020b] proposes an incremental GNN model on streaming graphs by detecting new coming patterns efficiently and consolidating existing patterns via continual learning. Besides, ER-GNN [Zhou et al., 2020] and Feature Graph [Wang et al., 2020a] presents different experience replay strategies for continual graph representation learning. However, these methods only consider the incremental learning of GNN models when the graph structures change, and thus can only be applied to scenarios such as social networks and knowledge graphs. They fail to handle the effective update of the spatial-temporal model in traffic networks when the temporal patterns of stations and the topological structures of networks evolve simultaneously.

3 Preliminaries

The long term streaming traffic network is represented as G = (G1,G2, . . . ,GT )2 , where Gτ = Gτ-1 + ∆Gτ for all time intervals τ, meaning the network keeps expanding over time. Traffic network of the τ-th year can be denoted as a graph Gτ = (Vτ , Eτ , Aτ ), where Vτ is a finite node set with |Vτ | = Nτ nodes. Nodes on the graph can represent sensors or stations. Eτ represents the edge set with edges connecting nodes from Vτ and Aτ ∈ RNτ×Nτ is the adjacency matrix. Devices deployed at nodes will periodically measure and record traffic status features, including flows, speed and occupancy. Flow data of all nodes on graph Gτ observed at time-step t can be denote as Xt τ ∈ RNτ×F , where F is the number of traffic status features.

The purpose of traffic flow forecasting is to provide accurate predictions of future traffic flow when historical data is given, which can be formulated as:

Problem 1. Given the long-term streaming traffic network G = (G1,G2, . . . ,GT ) with Gτ = (Vτ ,Eτ ,Aτ) and the corresponding historical data Xτ = (X1 τ , . . . ,X T τ ), we are expected to learn a series of function Ψ = (Ψ1, Ψ2, . . . , ΨT ) for prediction of traffic flow series ˆ Yτ = Ψτ(Xτ) = ( ˆ Y T+1 τ , . . . , ˆ Y T+K τ ) for all Nτ nodes in the next K timesteps after time-step T, i.e.,:

2 In this paper, we use τ ∈ {1, 2, . . . , T } to represent a long time interval that the traffic network structure remains unchanged within τ . t ∈ {1, 2, . . . , T} denotes the time-steps traffic data is observed.

where Y T τ ∈ RNτ denotes the ground-truth of the traffic flow at time-step T and Yτ = (Y T+1 τ , . . . , Y T+K τ ) represents the time series to be forecast.

4 TrafficStream

In this section, we elaborate on the proposed framework of streaming traffic flow forecasting based on GNNs and Continual Learning, TrafficStream. We firstly introduce a simple GNN model as a surrogate model of those complex traffic flow forecasting methods. Our framework balances between learning new traffic patterns from new data and maintaining the historical knowledge learnt from previous data. New nodes with its 2-hops neighbors are used to construct a sub-graph for mining the influence of network expansion. Existing nodes whose traffic patterns change significantly are detected through an algorithm based on JS-divergence. To consolidate the previous knowledge, historical nodes of traffic networks are replayed and weighted smoothing constraints are imposed on the current training model. The details of TrafficStream are described in the following.

4.1 Surrogate Traffic Flow ForecastingModel

The great success of graph neural networks (GNNs) have attracted the attention of researchers and they are introduced to capture spatial and temporal features of traffic flow data. Consequently, current studies on traffic flow forecasting are mainly based on GNNs: they are leveraged to extract spatial dependency between nodes together with sequence models like CNNs and RNNs mining temporal trends of traffic flow [Yu et al., 2017; Wu et al., 2019; Guo et al., 2019]. Recent studies simultaneously capture spatial-temporal correlation through applying GNNs on spatial-temporal fusion graphs constructed by data [Song et al., 2020; Mengzhang and Zhanxing, 2020].

To intuitively describe our framework, we follow their common design and propose a simple surrogate traffic flow forecasting model (SurModel) to represent those complex ones deployed in ITS. SurModel is composed of two GNN layers with a CNN layer sandwiched in between. Denote the input of l-th GNN layer in τ-th year as Hlτ ∈ RNτ×Clτ (H0 i = Xτ ), spatial information obtained by the GNN layer can be formulated as:

where W l τ 1 , W l τ2 ∈ RClτ ×Cl+1 τ are learnable parameters. I ∈ RNτ×Nτ is identity matrix and σ is the activation function. 1D CNN is adopted to capture temporal patterns on the output of the first GNN layer and generate features for the second GNN layer. We apply skip connection to concatenate input Xτ with output of the second GNN layer H2 τ . The result will be fed into a fully connected layer to generate traffic flow in the next K time-steps. SurModel is set to minimize the L2loss between predicted value ˆ Yτ and ground-true value Yτ :

4.2 New Traffic Pattern Fusion

Traffic flow patterns are believed to be stable without accidents on the roads. Researchers tend to categorize them into daily pattern, weekly pattern, monthly pattern and so on. Based on this assumption, they are devoted to decomposing traffic flow into different patterns for deeper comprehension of traffic systems and better prediction of traffic status. However, this assumption becomes invalid if we observe the flow in a long term: trends may evolves sluggishly over time and it is also possible that the network structures change due to deployment of new sensors or stations. The extracted patterns are not more accurate enough to describe traffic laws of the current network. To efficiently update these patterns under such situations, we propose two components for training on expanding networks and better extracting evolving patterns.

Expanding Network Training

Current GNN based traffic flow forecasting models have a huge amount of parameters, and the time complexities are O(N 2 τ-1 ) which can be attributed to matrix multiplication of GNN layers in Eq. (2). When network scale changes, retraining the model definitely raises the complexity to O(N 2 τ ) = O((Nτ-1 + ∆Nτ)2 ). Here ∆Nτ is the node set that only contains newly added nodes. In real-world traffic network, it is often the case that previous networks are sufficiently large while the newly deployed nodes only account for a small part. Thus, retraining seems more time consuming as ∆Nτ ≪ Nτ . Motivated by the scale between ∆Nτ and Nτ as well as online learning methods, we firstly use ∆Nτ to update the trained SurModel Ψτ-1 as Ψτ . Note that GNN layers aim to capture the dependency between nodes and its neighborhoods, we generate a sub-graph by selecting neighbor nodes of newly added nodes on Gτ within 2-hops. The complexity is reduced to O((∆Nτ d2 )2 ) where d is the average degree of nodes. Remember that on a traffic network nodes are connected to 2 nodes on a straight road and 4 at a crossroads, so that d is around 2∼4 and O((∆Nτ d2 )2 ) is much smaller than O(N 2 τ ).

Evolution Pattern Detection

In addition to the effect of network expansion, traffic patterns would not remain constant: people may change residences and workplaces or there may be some changes at the point of interest (POI), and thus travelling plans vary over time. It is necessary to detect nodes where current patterns sharply conflict with previous ones. We design a node detection algorithm to discover these nodes: given the last graph Gτ-1 and current graph Gτ , for all the nodes on Gτ-1, we select flow data of the last week at τ - 1 and τ. Denote these data as Xτ-1 and Xτ , and previous SurModel Ψτ-1 without the last fully connected layer is ψτ-1. Patterns captured from data can be represented as the output feature U of ψτ-1:

To tackle the problem that features are different between weekdays and weekends, in the time dimension, we normalize Uτ and Uτ-1 and utilize histogram of the normalize features as its distribution. Let Pτ and Pτ-1 represent these two distribution of feature value. We aim to discover the similarity between these two distribution as it reveals the change of current and previous patterns. Thus, Jensen-Shannon divergence (JSD or JS divergence) is introduced as the measurement of similarity:

where D(P ||Q) = ∑x∈X P (x) log(P (x)/Q(x)) is the Kullback-Leibler divergence and ¯ P = (Pτ + Pτ-1)/2.

If JSD of a node is pretty high, its pattern can be considered as evolving substantially. Finally, we choose the top 5% of nodes with the highest JSD score as candidate nodes for learning the new patterns. Similar to those newly added nodes, we also construct a sub-graph for GNN layers.

4.3 Historical Traffic Knowledge Consolidation

When models capture the new patterns through components mentioned above, another problem arises: the model may forget previous knowledge it has learnt because it focus on those new patterns only. The catastrophic forgetting phenomenon arouses us to consolidate historical traffic knowledge. One way to preserve existing patterns is to track back to the source where these knowledge from, i.e., historical flow data. The other is to force current training model Ψτ to remember useful knowledge from Ψτ-1. Motivated by these two ideas, we design two components to consolidate knowledge from data and model perspectives. Details are presented as follows.

Information Replay

In order to maintain existing knowledge, we can train the model Ψτ with sampled historical information and make a replay. A simple strategy is to randomly sample flow data of some nodes, whereas it has large errors for these samples may be less representative. Rethinking the node detection algorithm based on JS divergence, nodes whose JSD scores are lower reveal that their flow is more stable, so that it is reasonable to choose these nodes. In the end, whose nodes with the lowest JSD scores are selected and construct a sub-graph to train Ψτ as a replay.

Parameter Smoothing

For better preserving previous knowledge, we utilize the last model Ψτ-1 to impose smoothing constraints on parameters of the current one Ψτ , so as to avoid large deviation of the model and the occurrence of the forgetting problem. Adopting l2 constraints is a crude approach, where excessive restrictions on the model may make it lack the ability to learn new patterns. If we know which parameters are essential to the existing patterns of traffic flows and only restrict these parameters, we can get a more expressive model for forecasting.

Therefore, we introduce elastic weight consolidation (EWC) [Kirkpatrick et al., 2017], adding a more flexible and exquisite smoothing term to the loss function:

where λ is the weight of the smoothing term and Fi is the importance of the i-th parameter in the model Ψτ-1, which is estimated using Fisher Information as

where g is the is first order derivatives of the loss.

Through the weighted smoothing term, the weight of the less essential parameters for historical data is smaller, and these parameters can better adapt to the new patterns. On the contrary, the more important parameters for historical data are more weighted, and thus their changes are restricted, ensuring the preservation of historical knowledge.

5 Experiments

5.1 Dataset

To verify the effectiveness and efficiency of our framework, we conduct some experiments on a real-world dataset, PEMS3-Stream. PEMS3-Stream is collected by California Transportation Agencies (CalTrans) Performance Measurement System (PeMS) [Chen et al., 2001] in real-time by every 30 seconds. The data is aggregated into every 5-minutes interval from 30-seconds data instances. PEMS3-Stream contains traffic flow data in North Central Area from 2011 to 2017. We select data from July 10th to August 9th every year. The details are shown in Table 1.

5.2 Preprocessing

To construct a high-quality dataset, we select sensors by the following rules: (1) the location shifting of a sensor in corresponding metadata should be less than 100 meters; (2) the missing ratio of data of a sensor should be less than 15%; (3) the traffic network of PEMS3-Stream keeps expanding, meaning sensor i at the τ -th year must appear at the (τ +∆τ )- th year, ∆τ ∈ {1, 2, . . . , 7 - τ}.

The adjacency matrix Aτ at the τ-th year can be extracted from metadata of sensors:

where dij denotes the distance between sensor i and j. σd is set to 10 and ϵ is set to 1.0 to control the sparsity of Aτ .

5.3 Experimental Settings

Data of each year is split into training, validation and testing sets with ratio 6:2:2 in the time dimension. Our task is to forecast traffic flows in the next hour with data from the last hour as T = K = 12. AdamW [Loshchilov and Hutter, 2017] is used as the optimizer with learning rate 0.005. Batch size is 128 and we train 100 epochs for each year with early stopping to accelerate training process. We apply random search strategy to find the best hyper-parameters for TrafficStream.

To evaluate the performance of our framework, we adopt Mean Absolute Errors (MAE), Root Mean Squared Errors (RMSE) and Mean Absolute Percentage Errors (MAPE) as the metric for effectiveness. Total training time and training time per epoch are used to reveal model efficiency.

5.4 Baseline Methods

• SVR [Castro-Neto et al., 2009]: Support Vector Regression adapts support vector machine for regression task.
• GRU [Cho et al., 2014]: Gated Recurrent Unit is an RNNmodel that leverages gated mechanism.
• STGCN [Yu et al., 2017]: Spatial-Temporal Graph Convolutional Network adopts graph convolution and gated CNN to extract spatial and temporal patterns. We train a STGCN using data from all nodes every year.
• STSGCN [Song et al., 2020]: Spatial-Temporal Synchronous Graph Convolutional Network synchronously captures the localized spatial-temporal correlations. We train a STSGCN using data from all nodes every year.
• Retrained-STModel: We train a surrogate model introduced in Sec 4.1 using data from all nodes every year. We use models at the last year as initialization.
• Static-STModel: We utilize data at the first year (i.e., 2011) to train a surrogate model, and forecast traffic flow after 2011 using the surrogate model directly.
• Expansible-STModel: We train a surrogate model in an online manner, that is, at every year, we only train the data from the newly added nodes with the models trained at the last year as initialization.
• TrafficStream: Our proposed framework. We train a surrogate model in an online manner with new pattern fusion and historical knowledge consolidation.

5.5 Experimental Results

In this section, we compare TrafficStream with other baselines on the traffic flow forecasting task and discuss the results from effectiveness and efficiency.

Effectiveness

Table. 2 shows the overall performance of traffic forecasting at different time granularity (i.e., 15-, 30-, 60-minutes in the future). We compute the averaged MAE, RMSE and MAPE in 7 years of each model. Our model, TrafficStream achieves lower prediction error compared with the traditional online training methods (i.e., Static-STModel and Expansible-STModel). And it reaches almost the same effect as the upper bound (i.e., Retrained-STModel, STGCN and STSGCN). Besides, STModel adopts GCN and CNN to capture spatial-temporal correlation. It is significantly better than simple methods like SVR and LSTM, and has comparable performance with the advanced model like STGCN.

Figure 1(a), 1(b), 1(d) and 1(e) show the effect of models on consecutive years. Every year, as Static-STModel does not update the model incrementally, it cannot capture new patterns on the traffic network, resulting in a rapid increase in prediction errors. Expansible-STModel only trains incrementally on new nodes every year and does not maintain the patterns of other nodes, leading to the problem of catastrophic forgetting. The expressive ability of the model will become unsatisfactory and unstable. Especially when the patterns of new nodes are inconsistent with other nodes (e.g., 2015), Expansible-STModel will get very poor prediction results. TrafficStream can maintain good and stable forecasting, indicating that it can continuously learn new traffic patterns while maintaining existing knowledge.

Efficiency

Table 2, Figure 1(c) and Figure 1(f) show the running time of each model, including total training time and training time per epoch, and we compute the averaged time in 7 years. The training time of Retrained-STModel and STGCN is much higher than online methods (i.e., Expansible-STModel and TrafficStream), which is about 3 times longer. It proves that TrafficStream can maintain high efficiency while achieving accurate prediction, providing the opportunity for realworld applications. Note that Static-STModel uses the model trained in the first year to predict the annual traffic flows after that, so its training time is 0 after 2011.

5.6 Ablation Study

Impact of New Pattern Fusion

We first analyze the impact of the fusion of new patterns on the forecasting performance, as shown in Figure 2. NonExpand refers to not integrating the patterns of new nodes and only integrating the new patterns of existing nodes. On the contrary, Non-Detect represents only integrating the patterns of new nodes. TrafficStream integrates all possible new patterns. It shows that it is not enough only to learn any parts of new patterns. Our model fuse all potential new patterns well so as to obtain the latest and best parameters to forecast the traffic flows in the future.

Impact of Knowledge Consolidation

We then analyze the influence of historical knowledge on the forecasting performance, as shown in Figure 3. NonConso. represents that it does not consolidate any knowledge learned by the previous model at all. Non-Replay and Non-Smooth respectively refer to training without data replay and without model smoothing. TrafficStream utilizes both approaches simultaneously.The results of not consolidating historical knowledge are the worst, indicating that the forgetting of historical knowledge occurs, so that the prediction of some nodes becomes worse. The two consolidation approaches can avoid the forgetting problem to a certain extent, and the approach of data replay is better. Besides, the combination of the two further improves the predictive ability of the model.

6 Conclusion

In this paper, we propose a GNN framework for streaming traffic flow forecasting. Continual learning is introduced to achieve efficient update and effective prediction in streaming traffic data. The model is evaluated and proved to be very effective on PEMS3-Dynamic dataset. Compared with the traditional retraining approach, TrafficStream achieves high prediction accuracy while reducing training complexity greatly.