T-gcn a temporal graph convolutional network for traffic prediction

Graph convolutional network (GCN) is an absolute game-changer in the deep learning domain.

Intro.

In a series of posts, we will explore the usage of GCN for time series tasks. Hands-on examples accompany most posts to provide a quick “sense” of this powerful approach. Recommendation: This post assumes prior knowledge of GCN. If you need an intro to GCN, I highly recommend referring to Michael Bronstein’s post: Do we need deep GNN. Also, a hands-on intro post by Tobias Skovgaard Jepsen.

Background

Graph neural networks (GNN) and, in particular, Graph convolutional networks (GCN) [1] can model the entities and their relationships. A straightforward example from natural sciences is atoms and their chemical bonds. Another example of traffic control is the dependency of the traffic road speed between many segments (which will be introduced in this post).

The learning aspect of graphs is the capability to generalize a model in graph-structured data. This generalization is made using features learning, where the graph convolutional operation is applied. Wide research has been done on vision and text data. However, there aren’t many works in the time-series domain with GCN. What can we do if we have time-varying features? This is where a new cool domain has recently presented…

Graphs for Time Series

The breakthrough of the GCN brings to the table the question of time-series usage and even some explainability capabilities.

As you probably guess, dealing with time-series data is less intuitive. We can not do any visualization and tell what the meaning is in most cases, compared to images, for example. Also, keeping in mind the causality property is very important, so we need to promise a well-trained model where we are not predicting the past :)

The time-series data is fundamentally different than spatial data. A combined GCN with RNN/LSTM/GRU may allow the net to capture spatial and temporal features together. This approach is named Temporal GCN (TGCN) and we will start by exploring it with a Traffic Prediction example [2].

TGCN: Traffic Prediction

Consider a problem of traffic speed prediction given a history of the traffic speed for a collection of road segments. The solution assumes each road segment’s traffic speed as a separate time series. It predicts the future values of each time series using the past values of the same time series. This results in a traffic speed prediction for many road segments.

As you probably note, the GRU is more than enough for temporal feature extraction- the traffic speed. But, is there any information we can get from looking at the big picture? One may think of the dependency of the traffic road speed between many segments. GCN can represent this dependency.

The suggested approach to tackle it was presented in [2]. The traffic network was defined as a graph and traffic speed as a signal on this graph. This is a great example of graphs with a static structure (the roads) and time-varying features. Considering the road network as a graph means that the individual segments of a road are the nodes on a graph, and the connections between those segments are the edges. As you probably understand, this graph will not change over time (almost). But, the amount of traffic actually will change. Hence, there is a need to capture both the spatial and temporal features.

The architecture includes a graph convolution layer and a gated recurrent unit (GRU) layer in this described problem.

Let’s dive a bit into the dataset of the road segments. We calculate the correlations to learn if there is any dependency between the different segments. If so, there is a clear justification for the GCN use. For that, we chose 26 roads out of 228 in the dataset and plotted the correlation map

Clearly, segments 4–5–6–7 and 19–20–21 are highly correlated. Hence, there is a solid motivation to include spatial features as the GCN does. In their paper, Ling Zhao et al. suggested an architecture that allows forecasting over the graph consisting of a graph convolution layer for the spatial features and a GRU layer for the temporal features. We played with the code [3] and arranged it in a Colab for a fast “run and play” [4]. The forecasting was pretty good, and we invite you to tune differently, run for more epochs and compare to other models.

Summary

The graph convolutional network is a very unique and revolutionary concept. There are many applications for the time-series domain, requiring the adjustment of the concept to include some temporal components. We discussed the traffic speed prediction problem to demonstrate the power of the TGCN and presented the correlation map to highlight the motivation.

About the Author

Barak Or received the B.Sc. (2016), M.Sc. (2018) degrees in aerospace engineering, and also B.A. in economics and management (2016, Cum Laude) from the Technion, Israel Institute of Technology. He was with Qualcomm (2019–2020), where he mainly dealt with Machine Learning and Signal Processing algorithms. Barak is currently studying toward his Ph.D. at the University of Haifa. His research interest includes sensor fusion, navigation, deep learning, and estimation theory.

Further reading and comments

[1] GCNs were first introduced in “Spectral Networks and Deep Locally Connected Networks on Graphs” (Bruna et al, 2014).

[2] A paper named “T-GCN: A Temporal Graph Convolutional Network for Traffic Prediction” by Ling Zhao et al was published in IEEE, 2020.

[3] The accompanied code can be found on the tutorial page of Keras. on the website. Arash Khodadadi is the author of the Keras tutorial for this paper. Data in [6].

[4] Colab implementation: Timeseries_Traffic_Forecasting. The dataset is from [3].

[5] Do we need deep graph neural networks — by Michael Bronstein

[6] The data can be found at the Keras website at the following link: https://keras.io/examples/timeseries/timeseries_traffic_forecasting/

What is temporal graph convolutional network?

What is GCN graph convolutional network?