Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting

Paper Author

'Saptio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting' 논문에 대해 정리 및 알게 된 내용을 정리해 보고자 한다. 

 

1. Introduction

Traffic Forecast Task

• 교통 예측은 현재 상황을 모니터링하는 task이며, speed(속도), volume(차량의 양), density(밀도) 등을 지표로 활용한다. (sensor를 통해 정보를 수집한다.)
• 교통예측 task: 주요 교통 지점에서의 traffic flow / speed와 같은 정량적 지표를 예측하는 것이다.
• 교통 예측은 일반적으로 단기 예측과 장기 예측으로 나누어진다.
  • short term : 5 minutes ~ 30 minutes
  • medium and long term: over 30 minutes
  • 보통, 중장기적 예측이 더 중요하다.
• Mid - and - long term traffic prediction은 두 가지 범주로 나누어진다 -> dynamic modeling & data-driven methos.
  • Dynamic Modleing(물리적 동적모델링) -> 시뮬레이션을 통한 예측은 교통모델을 공식화하여 계산하나 비용적 측면과 정교하지 못한 문제를 야기한다.
  • Data-driven methos(데이터 기반 접근 - ex) linear regression, ARIMA, SVM) -> 단기 예측은 잘 수행하는 반면, traffic flow의 uncertainty와 complexity 때문에 중장기 예츠근 잘 수행하지 못한다.
• Traffic Network는 일반적으로 graph structure이다.

Traffic Flow

• 특징1: 도로 교통망이 수집되는 지점은 각 지점마다 공간적 특성을 기반으로 상호 관련성이 존재한다.
  • ex) 도로에서의 교통량증가/정체는 특정 도로지점에 더 영향력을 많이 줄 수 있음
• 특징2: 해당 task 자체가 미래를 예측하는 시간적 정보를 기반으로 진행한다.
  • ex) 30분의 정보를 바탕으로 미래의 10분 교통량 예측
• 따라서, 시공간적 특징을 동시에 반영하는 모델구조가 필요하다.
  • 시간적 특징만 반영하는 모델의 한계: LSTM에 각 수집자의 정보를 flatten하게 input으로 사용하는 경우, 공간적 상관성 무시한다.
  • 공간적 특징을 반영하는 모델의 한계: 2D-CNN을 이용하여 local 영역의 정보를 취합한 경우, 실제 연결여부의 특징을 반영하지 못한다.
• 논문에서는 공간정보를 완전하게 활용하기 위해, traffic network를 graph로 모델화 하였으며 시간 축을 recurrent neural network(RNN)이 아닌 a fully convolutional structure(CNN)을 사용하였다.
• 또한, 무엇보다도 traffic forecasting task에 spaito-temporal graph convolutional networks를 제안한 것이 이 논문의 가장 큰 핵심이다.

 

2. Preliminary

Predicting the most likely traffic measurement

Traffic Forecast는 전형적인 시게열 예측 문제이다. 관찰된 M개의 교통 정보를 통해서 다음 시점 H시점을 예측하는 것이다.

단, 한개의 도로를 수식으로 표현을 하면 다음과 같다.

• Vt = an observation vector of n road segments at time step t
• 즉, Vt는 n 번째 도로에서 t 번째 시간에서 관찰된 값이라고 생각하면 된다. 
• 시점 (t-M+1,....,t)에 관찰된 벡터를 통해서 (t+1,....t+H)시점을 예측하는데 가장 높은 확률을 가진 값으로 예측을 하는 것이다.

이제, 한개의 도로가 아닌 여러 개의 도로에 대해 생각해 보면 다음과 같다.

Graph Structured traffic data

• Each Vt indicates a frame of current traffic status at time step t, which is recorded in a graph-structured data matrix.
• 즉, 한 시점만 보면 다음과 같다. 각 road의 feature에 대한 정보와 road 간의 연결 정보가 담겨져 있다.

node_feature matrix

• 이번에는, (t-M+1,...,t+H) 시점까지 표현하면 다음과 같다.

Graph: G = (Vt, e, W)

• Vt = a finite set of verticles, corresponding to the observations from n monitor stations in a traffic network
• e = a set of edges, indicating the connectedness between stations
• W = the weighted adjacency matrix of G(graph)

 

3. Proposed Model

Network Architecture

Spatio-Temporal Graph Convolutional Networks(STGCN)

STGCN

• Input data -> ST-Conv Block -> ST-Conv Block -> Output Layer
• ST-Conv Block은 두 개의 gated sequential convolution layers와 한 개의 spatial graph convolution layer로 샌드위치처럼 구성되어 있다. 
  • The 'sandwhich' structure helps the network sufficiently apply bottleneck strategy to achieve scale compression and feature squeezing by downscaling and upscaling of channels C through the graph convolutional layer.
  • 또한, overfitting을 방지하기 위해 매 ST-Conv Block에서는 정규화(normalization)을 해줘야 한다.
• Output Layer은 Fully Connected Layer이다.

Gated CNNs for Extracting Temporal Features

• 비록 RNN 기반 모델들이 시계열 분석에서 널리 사용되지만, traffic prediction에서의 recurrent network는 time-consuming iterations, complex gate mechanims, slow response to dynamic changes의 문제점이 존재한다.
• 반면, CNN은 fast training, simple structures, no dependency constraints to previous steps라는 특징 및 장점이 존재한다.
• 따라서, 논문에서는 traffic flow의 temporal dynamic behavior을 포획하기 위해 time axis에 convolutional structure를 사용하였다.

The Temporal Gated Convolutional Define

• Temporal Gated Convolutional Layer은 비선형인 GLU gate인 kernel과 함께 1-D convolution을 포함한다.

• P, Q는 각각 gate GLU의 input data
• P, Q는 같은 사이즈의 채널을 반절로 나눈 것이다. 
• The sigmoid gate controls which input P of the current states are relevant for discovering compositional structure and dynamic variances in time series.

• For each node in graph, the temporal convolution explores kernel neighbors of input elements without padding, which leading to shorten the length of sequences by kernel-1 each time. 
  • Time = time - kernel + 1 (no padding)
  • Output feature: hyper - parameter
  • key point : 아직 센서 간의 정보 교류가 없음. time에 대한 정보만 추출.

 

Spatio Graph Convolution

• Spatial Graph Convolution을 통해 센서 간의 정보 교류를 할 수 있다. 
• 각 Time 시점별로는 동일한 GCN weight가 사용되며 Adjacency matrix와 함께 GCN Layer를 통해 각 센서들의 정보를 기반으로 hidden representation이 생성된다.

 

Output Layer

Fully Connected Layer에서는 마지막 시점의 representation만 사용한다. 

 

 

논문에서 두 가지 데이터로 예제를 들어 설명하였는데 다음 블로그에서 그 중 캘리포니아 교통 정보 데이터로 STGCN을 적용한 것을 정리하고자 한다.

 

 

참고논문: https://github.com/VeritasYin/STGCN_IJCAI-18