Graph convolutional network (GCN) is an absolute game-changer in the deep learning domain.
Introduction
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.
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.
----
[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.