这是用户在 2024-6-3 10:26 为 https://ar5iv.labs.arxiv.org/html/2101.11174?_immersive_translate_auto_translate=1 保存的双语快照页面,由 沉浸式翻译 提供双语支持。了解如何保存?

Graph Neural Network for Traffic Forecasting: A Survey
用于交通预测的图神经网络:调查

Weiwei Jiang  蒋伟伟 Department of Electronic Engineering, Tsinghua University, Beijing, 100084, China
清华大学电子工程系, 北京, 100084
Jiayun Luo  罗佳云 School of Computer Science and Engineering, Nanyang Technological University, 639798, Singapore
南洋理工大学计算机科学与工程学院, 639798, 新加坡
Abstract 抽象的

Traffic forecasting is important for the success of intelligent transportation systems. Deep learning models, including convolution neural networks and recurrent neural networks, have been extensively applied in traffic forecasting problems to model spatial and temporal dependencies. In recent years, to model the graph structures in transportation systems as well as contextual information, graph neural networks have been introduced and have achieved state-of-the-art performance in a series of traffic forecasting problems. In this survey, we review the rapidly growing body of research using different graph neural networks, e.g. graph convolutional and graph attention networks, in various traffic forecasting problems, e.g. road traffic flow and speed forecasting, passenger flow forecasting in urban rail transit systems, and demand forecasting in ride-hailing platforms. We also present a comprehensive list of open data and source codes for each problem and identify future research directions. To the best of our knowledge, this paper is the first comprehensive survey that explores the application of graph neural networks for traffic forecasting problems. We have also created a public GitHub repository where the latest papers, open data, and source codes will be updated.
交通预测对于智能交通系统的成功非常重要。深度学习模型,包括卷积神经网络和循环神经网络,已广泛应用于交通预测问题中,以对空间和时间依赖性进行建模。近年来,为了对交通系统中的图结构以及上下文信息进行建模,引入了图神经网络,并在一系列交通预测问题中取得了最先进的性能。在这项调查中,我们回顾了使用不同图神经网络的快速增长的研究,例如图卷积和图注意力网络,用于各种流量预测问题,例如道路交通流量和速度预测、城市轨道交通系统客流预测、网约车平台需求预测。我们还提供了每个问题的开放数据和源代码的完整列表,并确定了未来的研究方向。据我们所知,本文是第一篇探索图神经网络在交通预测问题中的应用的综合调查。我们还创建了一个公共 GitHub 存储库,其中将更新最新论文、开放数据和源代码。

keywords:
Traffic Forecasting , Graph Neural Networks , Graph Convolution Network , Graph Attention Network , Deep Learning
关键词:流量预测、图神经网络、图卷积网络、图注意力网络、深度学习
journal: Journal of  Templates
期刊:LaTeX 模板期刊

1 Introduction 1简介

Transportation systems are among the most important infrastructure in modern cities, supporting the daily commuting and traveling of millions of people. With rapid urbanization and population growth, transportation systems have become more complex. Modern transportation systems encompass road vehicles, rail transport, and various shared travel modes that have emerged in recent years, including online ride-hailing, bike-sharing, and e-scooter sharing. Expanding cities face many transportation-related problems, including air pollution and traffic congestion. Early intervention based on traffic forecasting is seen as the key to improving the efficiency of a transportation system and to alleviate transportation-related problems. In the development and operation of smart cities and intelligent transportation systems (ITSs), traffic states are detected by sensors (e.g. loop detectors) installed on roads, subway and bus system transaction records, traffic surveillance videos, and even smartphone GPS (Global Positioning System) data collected in a crowd-sourced fashion. Traffic forecasting is typically based on consideration of historical traffic state data, together with the external factors which affect traffic states, e.g. weather and holidays.
交通系统是现代城市最重要的基础设施之一,支撑着数百万人的日常通勤和出行。随着快速城市化和人口增长,交通系统变得更加复杂。现代交通系统包括公路车辆、轨道交通以及近年来兴起的网约车、共享单车、共享电动车等多种共享出行方式。不断扩张的城市面临着许多与交通相关的问题,包括空气污染和交通拥堵。基于交通预测的早期干预被视为提高交通系统效率和缓解交通相关问题的关键。在智慧城市和智能交通系统(ITS)的开发和运营中,交通状态通过安装在道路上的传感器(例如环路探测器)、地铁和公交系统交易记录、交通监控视频,甚至智能手机GPS(全球定位系统)来检测。 )以众包方式收集的数据。交通预测通常基于历史交通状态数据以及影响交通状态的外部因素(例如,交通状况)的考虑。天气和假期。

Both short-term and long-term traffic forecasting problems for various transport modes are considered in the literature. This survey focuses on the data-driven approach, which involves forecasting based on historical data. The traffic forecasting problem is more challenging than other time series forecasting problems because it involves large data volumes with high dimensionality, as well as multiple dynamics including emergency situations, e.g. traffic accidents. The traffic state in a specific location has both spatial dependency, which may not be affected only by nearby areas, and temporal dependency, which may be seasonal. Traditional linear time series models, e.g. auto-regressive and integrated moving average (ARIMA) models, cannot handle such spatiotemporal forecasting problems. Machine learning (ML) and deep learning techniques have been introduced in this area to improve forecasting accuracy, for example, by modeling the whole city as a grid and applying a convolutional neural network (CNN) as demonstrated by Jiang & Zhang [2018]. However, the CNN-based approach is not optimal for traffic foresting problems that have a graph-based form, e.g. road networks.
文献中考虑了各种运输方式的短期和长期交通预测问题。这项调查的重点是数据驱动的方法,其中涉及基于历史数据的预测。交通预测问题比其他时间序列预测问题更具挑战性,因为它涉及高维的大数据量,以及包括紧急情况在内的多种动态,例如紧急情况。交通意外。特定位置的交通状态既有空间依赖性(可能不仅仅受附近区域的影响),也有时间依赖性(可能是季节性的)。传统的线性时间序列模型,例如自回归和综合移动平均(ARIMA)模型无法处理此类时空预测问题。该领域已引入机器学习(ML)和深度学习技术来提高预测准确性,例如,通过将整个城市建模为网格并应用卷积神经网络(CNN),如Jiang和Zhang [2018]所示。然而,基于 CNN 的方法对于具有基于图的形式的流量森林问题来说并不是最佳的,例如道路网络。

In recent years, graph neural networks (GNNs) have become the frontier of deep learning research, showing state-of-the-art performance in various applications [Wu et al., 2020b]. GNNs are ideally suited to traffic forecasting problems because of their ability to capture spatial dependency, which is represented using non-Euclidean graph structures. For example, a road network is naturally a graph, with road intersections as the nodes and road connections as the edges. With graphs as the input, several GNN-based models have demonstrated superior performance to previous approaches on tasks including road traffic flow and speed forecasting problems. These include, for example, the diffusion convolutional recurrent neural network (DCRNN) [Li et al., 2018b] and Graph WaveNet [Wu et al., 2019] models. The GNN-based approach has also been extended to other transportation modes, utilizing various graph formulations and models.
近年来,图神经网络(GNN)已成为深度学习研究的前沿,在各种应用中显示出最先进的性能 [Wu et al., 2020b]。 GNN 非常适合交通预测问题,因为它们能够捕获空间依赖性(使用非欧几里得图结构表示)。例如,道路网络本质上是一个图,以道路交叉口为节点,以道路连接为边。以图为输入,一些基于 GNN 的模型在道路交通流量和速度预测问题等任务上表现出了优于之前方法的性能。例如,其中包括扩散卷积递归神经网络 (DCRNN) [Li et al., 2018b] 和 Graph WaveNet [Wu et al., 2019] 模型。基于 GNN 的方法还利用各种图形公式和模型扩展到其他交通模式。

To the best of the authors’ knowledge, this paper presents the first comprehensive literature survey of GNN-related approaches to traffic forecasting problems. While several relevant traffic forecasting surveys exist [Shi & Yeung, 2018, Pavlyuk, 2019, Yin et al., 2021, Luca et al., 2020, Fan et al., 2020, Boukerche & Wang, 2020a, Manibardo et al., 2021, Ye et al., 2020a, Lee et al., 2021, Xie et al., 2020a, George & Santra, 2020, Haghighat et al., 2020, Boukerche et al., 2020, Tedjopurnomo et al., 2020, Varghese et al., 2020], most of them are not GNN-focused with only one exception [Ye et al., 2020a]. For this survey, we reviewed 212 papers published in the years 2018 to 2020. Additionally, because this is a very rapidly developing research field, we also included preprints that have not yet gone through the traditional peer review process (e.g., arXiv papers) to present the latest progress. Based on these studies, we identify the most frequently considered problems, graph formulations, and models. We also investigate and summarize publicly available useful resources, including datasets, software, and open-sourced code, for GNN-based traffic forecasting research and application. Lastly, we identify the challenges and future directions of applying GNNs to the traffic forecasting problem.

Instead of giving a whole picture of traffic forecasting, our aim is to provide a comprehensive summary of GNN-based solutions. This paper is useful for both the new researchers in this field who want to catch up with the progress of applying GNNs and the experienced researchers who are not familiar with these latest graph-based solutions. In addition to this paper, we have created an open GitHub repository on this topic 111https://github.com/jwwthu/GNN4Traffic, where relevant content will be updated continuously.

Our contributions are summarized as follows:

1) Comprehensive Review: We present the most comprehensive review of graph-based solutions for traffic forecasting problems in the past three years (2018-2020).

2) Resource Collection: We provide the latest comprehensive list of open datasets and code resources for replication and comparison of GNNs in future work.

3) Future Directions: We discuss several challenges and potential future directions for researchers in this field, when using GNNs for traffic forecasting problems.

The remainder of this paper is organized as follows. In Section 2, we compare our work with other relevant research surveys. In Section 3, we categorize the traffic forecasting problems that are involved with GNN-based models. In Section 4.1, we summarize the graphs and GNNs used in the reviewed studies. In Section 5, we outline the open resources. Finally, in Section 6, we point out challenges and future directions.

2 Related Research Surveys

In this section, we introduce the most recent relevant research surveys (most of which were published in 2020). The differences between our study and these existing surveys are pointed out when appropriate. We start with the surveys addressing wider ITS topics, followed by those focusing on traffic prediction problems and GNN application in particular.

Besides traffic forecasting, machine learning and deep learning methods have been widely used in ITSs as discussed in Haghighat et al. [2020], Fan et al. [2020], Luca et al. [2020]. In Haghighat et al. [2020], GNNs are only mentioned in the task of traffic characteristics prediction. Among the major milestones of deep-learning driven traffic prediction (summarized in Figure 2 of Fan et al. [2020]), the state-of-the-art models after 2019 are all based on GNNs, indicating that GNNs are indeed the frontier of deep learning-based traffic prediction research.

Roughly speaking, five different types of traffic prediction methods are identified and categorized in previous surveys [Xie et al., 2020a, George & Santra, 2020], namely, statistics-based methods, traditional machine learning methods, deep learning-based methods, reinforcement learning-based methods, and transfer learning-based methods. Some comparisons between different categories have been considered, e.g., statistics-based models have better model interpretability, whereas ML-based models are more flexible as discussed in Boukerche et al. [2020]. Machine learning models for traffic prediction are further categorized in Boukerche & Wang [2020a], which include the regression model, example-based models (e.g., k-nearest neighbors), kernel-based models (e.g. support vector machine and radial basis function), neural network models, and hybrid models. Deep learning models are further categorized into five different generations in Lee et al. [2021], in which GCNs are classified as the fourth generation and other advanced techniques that have been considered but are not yet widely applied are merged into the fifth generation. These include transfer learning, meta learning, reinforcement learning, and the attention mechanism. Before these advanced techniques become mature in traffic prediction tasks, GNNs remain the state-of-the-art technique.

Some of the relevant surveys only focus on the progress of deep learning-based methods [Tedjopurnomo et al., 2020], while the others prefer to compare them with the statistics-based and machine learning methods [Yin et al., 2021, Manibardo et al., 2021]. In Tedjopurnomo et al. [2020], 37 deep neural networks for traffic prediction are reviewed, categorized, and discussed. The authors conclude that encoder-decoder long short term-memory (LSTM) combined with graph-based methods is the state-of-the-art prediction technique. A detailed explanation of various data types and popular deep neural network architectures is also provided, along with challenges and future directions for traffic prediction. Conversely, it is found that deep learning is not always the best modeling technique in practical applications, where linear models and machine learning techniques with less computational complexity can sometimes be preferable [Manibardo et al., 2021].

Additional research surveys consider aspects other than model selection. In Pavlyuk [2019], spatiotemporal feature selection and extraction pre-processing methods, which may also be embedded as internal model processes, are reviewed. A meta-analysis of prediction accuracy when applying deep learning methods to transport studies is given in Varghese et al. [2020]. In this study, apart from the models themselves, additional factors including sample size and prediction time horizon are shown to have a significant influence on prediction accuracy.

To the authors’ best knowledge, there are no existing surveys focusing on the application of GNNs for traffic forecasting. Graph-based deep learning architectures are reviewed in Ye et al. [2020a], for a series of traffic applications, namely, traffic congestion, travel demand, transportation safety, traffic surveillance, and autonomous driving. Specific and practical guidance for constructing graphs in these applications is provided. The advantages and disadvantages of both GNNs and other deep learning models ,e.g. recurrent neural network (RNN), temporal convolutional network (TCN), Seq2Seq, and generative adversarial network (GAN), are examined. While the focus is not limited to traffic prediction problems, the graph construction process is universal in the traffic domain when GNNs are involved.

3 Problems

In this section, we discuss and categorize the different types of traffic forecasting problems considered in the literature. Problems are first categorized by the traffic state to be predicted. Traffic flow, speed, and demand problems are considered separately while the remaining types are grouped together under “other problems”. Then, the problem-types are further broken down into levels according to where the traffic states are defined. These include road-level, region-level, and station-level categories.

Different problem types have different modelling requirements for representing spatial dependency. For the road-level problems, the traffic data are usually collected from sensors, which are associated with specific road segments, or GPS trajectory data, which are also mapped into the road network with map matching techniques. In this case, the road network topology can be seen as the graph to use, which may contain hundreds or thousands of road segments potentially. The spatial dependency may be described by the road network connectivity or spatial proximity. For the station-level problems, the metro or bus station topology can be taken as the graph to use, which may contain tens or hundreds of stations potentially. The spatial dependency may be described by the metro lines or bus routes. For the region-level problem, the regular or irregular regions are used as the nodes in a graph. The spatial dependency between different regions can be extracted from the land use purposes, e.g., from the points-of-interest data.

A full list of the traffic forecasting problems considered in the surveyed studies is shown in Table LABEL:tab:problems. Instead of giving the whole picture of traffic forecasting research, only those problems with GNN-based solutions in the literature are listed in Table LABEL:tab:problems.

Table 1: Traffic forecasting problems in the surveyed studies.
Problem Relevant Studies
Road Traffic Flow  Zhang et al. [2018b], Wei et al. [2019], Xu et al. [2020a], Guo et al. [2020a], Zheng et al. [2020b], Pan et al. [2020, 2019], Lu et al. [2019a], Mallick et al. [2020], Zhang et al. [2020j, l], Bai et al. [2020], Fang et al. [2019], Huang et al. [2020a], Wang et al. [2018b], Zhang et al. [2020e], Song et al. [2020a], Xu et al. [2020b], Wang et al. [2020g], Chen et al. [2020e], Lv et al. [2020], Kong et al. [2020], Fukuda et al. [2020], Zhang & Guo [2020], Boukerche & Wang [2020b], Tang et al. [2020b], Kang et al. [2019], Guo et al. [2019c], Li et al. [2019b], Xu et al. [2019], Zhang et al. [2019d], Wu et al. [2018a], Sun et al. [2020], Wei & Sheng [2020], Li et al. [2020f], Cao et al. [2020], Yu et al. [2018, 2019b], Li et al. [2020b], Yin et al. [2020], Chen et al. [2020g], Zhang et al. [2020a], Wang et al. [2020a], Xin et al. [2020], Qu et al. [2020], Wang et al. [2020b], Xie et al. [2020d], Huang et al. [2020b], Guo et al. [2020b], Zhang et al. [2020h], Fang et al. [2020a], Li & Zhu [2021], Tian et al. [2020], Xu et al. [2020c], Chen et al. [2020c]
Road OD Flow  Xiong et al. [2020], Ramadan et al. [2020]
Intersection Traffic Throughput  Sánchez et al. [2020]
Regional Taxi Flow  Zhou et al. [2020d], Sun et al. [2020], Chen et al. [2020d], Wang et al. [2018a], Peng et al. [2020], Zhou et al. [2019], Wang et al. [2020e], Qiu et al. [2020]
Regional Bike Flow  Zhou et al. [2020d], Sun et al. [2020], Wang et al. [2018a, 2020e]
Regional Ride-hailing Flow  Zhou et al. [2019]
Regional Dockless E-Scooter Flow  He & Shin [2020a]
Regional OD Taxi Flow  Wang et al. [2020e], Yeghikyan et al. [2020]
Regional OD Bike Flow  Wang et al. [2020e]
Regional OD Ride-hailing Flow  Shi et al. [2020], Wang et al. [2020h, 2019]
Station-level Subway Passenger Flow  Fang et al. [2019, 2020a], Peng et al. [2020], Ren & Xie [2019], Li et al. [2018a], Zhao et al. [2020a], Han et al. [2019], Zhang et al. [2020b, c], Li et al. [2020e], Liu et al. [2020b], Ye et al. [2020b], Ou et al. [2020]
Station-level Bus Passenger Flow  Fang et al. [2019, 2020a], Peng et al. [2020]
Station-level Shared Vehicle Flow  Zhu et al. [2019]
Station-level Bike Flow  He & Shin [2020b], Chai et al. [2018]
Station-level Railway Passenger Flow  He et al. [2020]
Road Traffic Speed  Li et al. [2018b], Wu et al. [2019], Zhang et al. [2018b], Wei et al. [2019], Xu et al. [2020a], Guo et al. [2020a], Zheng et al. [2020b], Pan et al. [2020, 2019], Lu et al. [2019a], Mallick et al. [2020], Zhang et al. [2020j], Lv et al. [2020], Li et al. [2020f], Yin et al. [2020], Guo et al. [2020b], Li & Zhu [2021], Chen et al. [2020d], Zhao et al. [2020a], Bai et al. [2021], Tang et al. [2020a], James [2020], Shin & Yoon [2020], Liu et al. [2020a], Zhang et al. [2018a, 2019f], Yu & Gu [2019], Xie et al. [2019], Zhang et al. [2019a], Guo et al. [2019a], Diao et al. [2019], Cirstea et al. [2019], Lu et al. [2019b], Zhang et al. [2019c], James [2019], Ge et al. [2019a, b], Zhang et al. [2019b], Lee & Rhee [2022], Shleifer et al. [2019], Yu et al. [2020a], Ge et al. [2020], Lu et al. [2020b], Yang et al. [2020], Zhao et al. [2019], Cui et al. [2019], Chen et al. [2019], Zhang et al. [2019e], Yu et al. [2019a], Lee & Rhee [2019], Bogaerts et al. [2020], Wang et al. [2020f], Cui et al. [2020b, a], Guo et al. [2020c], Zhou et al. [2020a], Cai et al. [2020], Zhou et al. [2020b], Wu et al. [2020c], Chen et al. [2020f], Opolka et al. [2019], Mallick et al. [2021], Oreshkin et al. [2021], Jia et al. [2020], Sun et al. [2021], Guo & Yuan [2020], Xie et al. [2020b], Zhang et al. [2020i], Zhu et al. [2021], Feng et al. [2020], Zhu et al. [2020], Fu et al. [2020], Zhang et al. [2020d], Xie et al. [2020c], Park et al. [2020], Agafonov [2020], Chen et al. [2020a], Lu et al. [2020a], Jepsen et al. [2019, 2020], Bing et al. [2020], Lewenfus et al. [2020], Zhu et al. [2022], Liao et al. [2018], Maas & Bloem [2020], Li et al. [2020d], Song et al. [2020b], Zhao et al. [2020b], Guopeng et al. [2020], Kim et al. [2020]
Road Travel Time  Guo et al. [2020a], Hasanzadeh et al. [2019], Fang et al. [2020b], Shao et al. [2020], Shen et al. [2020]
Traffic Congestion  Dai et al. [2020], Mohanty & Pozdnukhov [2018], Mohanty et al. [2020], Qin et al. [2020a], Han et al. [2020]
Time of Arrival  Hong et al. [2020]
Regional OD Taxi Speed  Hu et al. [2018]
Ride-hailing Demand  Pian & Wu [2020], Jin et al. [2020b], Li & Axhausen [2020], Jin et al. [2020a], Geng et al. [2019b], Lee et al. [2019], Bai et al. [2019b], Geng et al. [2019a], Bai et al. [2019a], Ke et al. [2021a], Li et al. [2020c]
Taxi Demand  Lee et al. [2019], Bai et al. [2019b, a], Ke et al. [2021b], Hu et al. [2020], Zheng et al. [2020a], Xu & Li [2019], Davis et al. [2020], Chen et al. [2020h], Du et al. [2020], Li & Moura [2020], Wu et al. [2020a], Ye et al. [2021]
Shared Vehicle Demand  Luo et al. [2020]
Bike Demand  Lee et al. [2019], Bai et al. [2019b, a], Du et al. [2020], Ye et al. [2021], Chen et al. [2020b], Wang et al. [2020d], Qin et al. [2020b], Xiao et al. [2020], Yoshida et al. [2019], Guo et al. [2019b], Kim et al. [2019], Lin et al. [2018]
Traffic Accident  Zhou et al. [2020e], Yu et al. [2020b], Zhang et al. [2020k], Zhou et al. [2020f]
Traffic Anomaly  Liu et al. [2020c]
Parking Availability  Zhang et al. [2020g], Yang et al. [2019], Zhang et al. [2020f]
Transportation Resilience  Wang et al. [2020c]
Urban Vehicle Emission  Xu et al. [2020d]
Railway Delay  Heglund et al. [2020]
Lane Occupancy  Wright et al. [2019]

Generally speaking, traffic forecasting problems are challenging, not only for the complex temporal dependency, but only for the complex spatial dependency. While many solutions have been proposed for dealing with the time dependency, e.g., recurrent neural networks and temporal convolutional networks, the problem to capture and model the spatial dependency has not been fully solved. The spatial dependency, which refers to the complex and nonlinear relationship between the traffic state in one particular location with other locations. This location could be a road intersection, a subway station, or a city region. The spatial dependency may not be local, e.g., the traffic state may not only be affected by nearby areas, but also those which are far away in the spatial range but connected by a fast transportation tool. The graphs are necessary to capture such kind of spatial information as we would discuss in the next section.

Before the usage of graph theories and GNNs, the spatial information is usually extracted by multivariate time series models or CNNs. Within a multivariate time series model, e.g., vector autoregression, the traffic states collected in different locations or regions are combined together as multivariate time series. However, the multivariate time series models can only extract the linear relationship among different states, which is not enough for modeling the complex and nonlinear spatial dependency. CNNs take a step further by modeling the local spatial information, e.g., the whole spatial range is divided into regular grids as the two-dimensional image format and the convolution operation is performed in the neighbor grids. However, the CNN-based approach is bounded to the case of Euclidean structure data, which cannot model the topological structure of the subway network or the road network.

Graph neural networks bring new opportunities for solving traffic forecasting problems, because of their strong learning ability to capture the spatial information hidden in the non-Euclidean structure data, which are frequently seen in the traffic domain. Based on graph theories, both nodes and edges have their own attributes, which can be used further in the convolution or aggregation operations. These attributes describe different traffic states, e.g., volume, speed, lane numbers, road level, etc. For the dynamic spatial dependency, dynamic graphs can be learned from the data automatically. For the case of hierarchical traffic problems, the concepts of super-graphs and sub-graphs can be defined and further used.

3.1 Traffic Flow

Traffic flow is defined as the number of vehicles passing through a spatial unit, such as a road segment or traffic sensor point, in a given time period. An accurate traffic flow prediction is beneficial for a variety of applications, e.g., traffic congestion control, traffic light control, vehicular cloud, etc [Boukerche & Wang, 2020a]. For example, traffic light control can reduce vehicle staying time at the road intersections, optimizing the traffic flow, and reducing traffic congestion and vehicle emission.

We consider three levels of traffic flow problems in this survey, namely, road-level flow, region-level flow, and station-level flow.

Road-level flow problems are concerned with traffic volumes on a road and include road traffic flow, road origin-destination (OD) Flow, and intersection traffic throughput. In road traffic flow problems, the prediction target is the traffic volume that passes a road sensor or a specific location along the road within a certain time period (e.g. five minutes). In the road OD flow problem, the target is the volume between one location (the origin) and another (the destination) at a single point in time. The intersection traffic throughput problem considers the volume of traffic moving through an intersection.

Region-level flow problems consider traffic volume in a region. A city may be divided into regular regions (where the partitioning is grid-based) or irregular regions (e.g. road-based or zip-code-based partitions). These problems are classified by transport mode into regional taxi flow, regional bike flow, regional ride-hailing flow, regional dockless e-scooter flow, regional OD taxi flow, regional OD bike flow, and regional OD ride-hailing flow problems.

Station-level flow problems relate to the traffic volume measured at a physical station, for example, a subway or bus station. These problems are divided by station type into station-level subway passenger flow, station-level bus passenger flow, station-level shared vehicle flow, station-level bike flow, and station-level railway passenger flow problems.

Road-level traffic flow problems are further divided into cases of unidirectional and bidirectional traffic flow, whereas region-level and station-level traffic flow problems are further divided into the cases of inflow and outflow, based on different problem formulations.

While traffic sensors have been successfully used, data collection for traffic flow information is still a challenge when considering the high costs in deployment and maintenance of traffic sensors. Another potential approach is using the pervasive mobile and IoT devices, which have a lower cost generally, e.g., GPS sensors. However, challenges still exist when considering the data quality problems frequently seen in GPS data, e.g., missing data caused by unstable communication links.

The traffic light is another source of challenges for various traffic prediction tasks. Short-term traffic flow fluctuation and the spatial relation change between two road segments can be caused by the traffic light. The way of controlling the traffic light may be different in different time periods, causing an inconsistent traffic flow pattern.

3.2 Traffic Speed

Traffic speed is another important indicator of traffic state with potential applications in ITS systems, which is defined as the average speed of vehicles passing through a spatial unit in a given time period. The speed value on the urban road can reflect the crowdedness level of road traffic. For example, Google Maps visualizes this crowdedness level from crowd-sourcing data collected from individual mobile devices and in-vehicle sensors. A better traffic speed prediction is also useful for route navigation and estimation-of-arrival applications.

We consider two levels of traffic speed problems in this survey, namely, road-level and region-level problems. We also include travel time and congestion predictions in this category because they are closely correlated to traffic speed. Travel time prediction is useful for passengers to plan their commuting time and for drivers to select fast routes, respectively. Traffic congestion is one of the most important and urgent transportation problems in cities, which brings significant time loss, air pollution and energy waste. The congestion prediction results can be used to control the road conditions and optimize vehicle flow, e.g., with traffic signal control. In several studies, traffic congestion is judged by a threshold-based speed inference. The specific road-level speed problem categories considered are road traffic speed, road travel time, traffic congestion, and time of arrival problems; while the region-level speed problem considered is regional OD taxi speed.

Traffic speed is concerned in both urban roads and freeways. However, the challenges differ in these two different scenarios. Freeways have a few traffic signals or on/off-ramps, making the prediction easier than the urban case. And the challenge mainly comes from the complex temporal dependency. More complex traffic networks exist in urban roads with more complicated connection patterns and abrupt changes. For example, different road segments may have different speed limit values and the allowed vehicle types. Besides the complex temporal dependency, modeling the spatial dependency becomes a bigger challenge for urban traffic speed forecasting.

3.3 Traffic Demand

Traffic demand prediction is a key component for taxi and ride-hailing services to be successful, which benefits these service providers to allocate limited available transportation resources to those urban areas with a higher demand. For passengers, traffic demand prediction encourages the consideration of various transportation forms, e.g., taking the public transit service when taxi or ride-hailing services are in short supply.

Traffic demand refers to the potential demand for travel, which may or may not be fulfilled completely. For example, on an online ride-hailing platform, the ride requests sent by passengers represent the demand, whereas only a subset of these requests may be served depending on the supply of drivers and vehicles, especially during rush hours. Accurate prediction of travel demand is a key element of vehicle scheduling systems (e.g. online ride-hailing or taxi dispatch platforms). However, in some cases, it is difficult to collect the potential travel demand from passengers and a compromise method using transaction records as an indication of the traffic demand is used. In such cases the real demand may be underestimated. Based on transport mode, the traffic demand problems considered include ride-hailing demand, taxi demand, shared vehicle demand, and bike demand.

3.4 Other Problems

In addition to the above three categories of traffic forecasting problems, GNNs are also being applied to the following problems.

Traffic accident and Traffic anomaly: the target is to predict the traffic accident number reported to the police system. Traffic anomaly is the major cause of traffic delay and a timely detection and prediction would help the administrators to identify the situation and turn the traffic situation back to normal as quickly as possible. A traffic accident is usually an accident in road traffic involving different vehicles, which may cause significant loss of life and property. The traffic anomaly has a broader definition that deviates from the normal traffic state, e.g., the traffic jam caused by a traffic accident or a public procession.

Parking availability: the target is to predict the availability of vacant parking space for cars in the streets or in a car parking lot.

Urban vehicle emission: while not directly related to traffic states, the prediction of urban vehicle emission is considered in Xu et al. [2020d]. Urban vehicle emission refers to the emission produced by motor vehicles, e.g., those use internal combustion engines. Urban vehicle emission is a major source of air pollutants and its amount is affected by different traffic states, e.g., the excess emission would be created in traffic congestion situations.

Railway delay: the delay time of specific routes in the railway system is considered in  Heglund et al. [2020].

Lane occupancy: With simulated traffic data, lane occupancy has been measured and predicted [Wright et al., 2019].

4 Graphs and Graph Neural Networks

In this section, we summarize the types of graphs and GNNs used in the surveyed studies, focusing on GNNs that are frequently used for traffic forecasting problems. The contributions of this section include an organized approach for classifying the different traffic graphs based on the domain knowledge, and a summary of the common ways for constructing adjacency matrices, which may not be encountered in other neural networks before and would be very helpful for those who would like to use graph neural networks. The different GNN structures already used for traffic forecasting problems are briefly introduced in this section too. For a wider and deeper discussion of GNNs, refer to Wu et al. [2020b], Zhou et al. [2020c], Zhang et al. [2020m].

4.1 Traffic Graphs

4.1.1 Graph Construction

A graph is the basic structure used in GNNs. It is defined as G=(V,E,A)𝐺𝑉𝐸𝐴G=(V,E,A), where V𝑉V is the set of vertices or nodes, E𝐸E is the set of edges between the nodes, and A𝐴A is the adjacency matrix. Both nodes and edges can be associated with different attributes in different GNN problems. Element aijsubscript𝑎𝑖𝑗a_{ij} of A𝐴A represents the “edge weight” between nodes i𝑖i and j𝑗j. For a binary connection matrix A𝐴A, aij=1subscript𝑎𝑖𝑗1a_{ij}=1 if there is an edge between nodes i𝑖i and j𝑗j in E𝐸E, and aij=0subscript𝑎𝑖𝑗0a_{ij}=0 otherwise. If A𝐴A is symmetric, the corresponding graph G𝐺G is defined as undirected. Otherwise, G𝐺G is directed, when the edge only exists in one direction between a node pair.

For simplicity, we assume that the traffic state is associated with the nodes. The other case with edges can be derived similarly. In practice, the traffic state is collected or aggregated in discrete time steps, e.g. five minutes or one hour, depending on the specific scenario.

For a single time step t𝑡t, we denote the node feature matrix as χtRN×dsubscript𝜒𝑡superscript𝑅𝑁𝑑\chi_{t}\in{R}^{N\times d}, where N𝑁N is the number of nodes and d𝑑d is the dimension of the node features, i.e., the number of traffic state variables. Now we are ready to give a formal definition of traffic graph.

Definition 4.1 (Traffic Graph).

A traffic graph (with node features) is defined as a specific type of graph G=(V,E,A)𝐺𝑉𝐸𝐴G=(V,E,A), where V𝑉V is the node set, E𝐸E is the edge set, and A𝐴A is the adjacency matrix. For a single time step t𝑡t, the node feature matrix χtRN×dsubscript𝜒𝑡superscript𝑅𝑁𝑑\chi_{t}\in{R}^{N\times d} for G𝐺G contains specific traffic states, where N𝑁N is the number of nodes and d𝑑d is the number of traffic state variables.

Then we give a formal definition of graph-based traffic forecasting problem without leveraging external factors firstly.

Definition 4.2 (Graph-based Traffic Forecasting).

A graph-based traffic forecasting (without external factors) is defined as follows: find a function f𝑓f which generates y=f(χ;G)𝑦𝑓𝜒𝐺y=f(\mathbf{\chi};G), where y𝑦y is the traffic state to be predicted, χ={χ1,χ2,,χT}𝜒subscript𝜒1subscript𝜒2subscript𝜒𝑇\mathbf{\chi}=\{\chi_{1},\chi_{2},...,\chi_{T}\} is the historical traffic state defined on graph G𝐺G, and T𝑇T is the number of time steps in the historical window size.

In single step forecasting, the traffic state in the next time step only is predicted, whereas in multiple step forecasting the traffic state several time steps later is the prediction target. As mentioned in Section 1, traffic states can be highly affected by external factors, e.g. weather and holidays. The forecasting problem formulation, extended to incorporate these external factors, takes the form y=f(χ,ε;G)𝑦𝑓𝜒𝜀𝐺y=f(\mathbf{\chi},\varepsilon;G), where ε𝜀\varepsilon represents the external factors. Figure 1 demonstrates the graph-based traffic forecasting problem, where different color patches represent different traffic variables.

Refer to caption
Figure 1: The single-step graph-based traffic forecasting problem. Adapted from Ye et al. [2020a] with external factors added.

Various graph structures are used to model traffic forecasting problems depending on both the forecasting problem-type and the traffic datasets available. These graphs can be pre-defined static graphs, or dynamic graphs continuously learned from the data. The static graphs can be divided into two types, namely, natural graphs and similarity graphs. Natural graphs are based on a real-world transportation system, e.g. the road network or subway system; whereas similarity graphs are based solely on the similarity between different node attributes where nodes may be virtual stations or regions.

We categorize the existing traffic graphs into the same three levels used in Section 3, namely, road-level, region-level and station-level graphs.

Road-level graphs. These include sensor graphs, road segment graphs, road intersection graphs, and road lane graphs. Sensor graphs are based on traffic sensor data (e.g. the PeMS dataset) where each sensor is a node, and the edges are road connections. The other three graphs are based on road networks with the nodes formed by road segments, road intersections, and road lanes, respectively. The real-world case and example of road-level graphs are shown in Figure 2. In some cases, road-level graphs are the most suitable format, e.g., when vehicles can move only through pre-defined roads.

Refer to caption
Refer to caption
Figure 2: The real-world case and example of road-level graphs. 2 The road network in the Performance Measurement System (PeMS) where each sensor is a node. Source: http://pems.dot.ca.gov/. 2 The road-level graph examples. Adapted from Ye et al. [2020a].

Region-level graphs. These include irregular region graphs, regular region graphs, and OD graphs. In both irregular and regular region graphs the nodes are regions of the city. Regular region graphs, which have grid-based partitioning, are listed separately because of their natural connection to previous widely used grid-based forecasting using CNNs, in which the grids may be seen as image pixels. Irregular region graphs include all other partitioning approaches, e.g. road based, or zip code based Ke et al. [2021b]. In the OD graph, the nodes are origin region - destination region pairs. In these graphs, the edges are usually defined with a spatial neighborhood or other similarities, e.g., functional similarity derived from point-of-interests (PoI) data. The real-world case and example of region-level graphs are shown in Figure 3.

Refer to caption
Refer to caption
Figure 3: The real-world case and example of region-level graphs. 3 The zip codes of Manhattan where each zip code zone is a node. Source: https://maps-manhattan.com/manhattan-zip-code-map. 3 The region-level graph example.

Station-level graphs. These include subway station graphs, bus station graphs, bike station graphs, railway station graphs, car-sharing station graphs, parking lot graphs, and parking block graphs. Usually, there are natural links between stations that are used to define the edges, e.g. subway or railway lines, or the road network. The real-world case and example of station-level graphs are shown in Figure 4.

Refer to caption
Refer to caption
Figure 4: The real-world case and example of station-level graphs. 4 The Beijing subway system where each subway station is a node. Source: https://www.travelchinaguide.com/cityguides/beijing/transportation/subway.htm. 4 The station-level graph example.

A full list of the traffic graphs used in the surveyed studies is shown in Table 2. Sensor graphs and road segment graphs are most frequently used because they are compatible with the available public datasets as discussed in Section 5. It is noted that in some studies multiple graphs are used as simultaneous inputs and then fused to improve the forecasting performance [Lv et al., 2020, Zhu et al., 2019].

Table 2: Traffic graphs in the surveyed studies.
Graph Node Edge Relevant Studies
Sensor Graph Traffic Sensors Road Links Li et al. [2018b], Wu et al. [2019], Xu et al. [2020a], Zheng et al. [2020b], Pan et al. [2020, 2019], Lu et al. [2019a], Mallick et al. [2020], Zhang et al. [2020j], Bai et al. [2020], Huang et al. [2020a], Zhang et al. [2020e], Song et al. [2020a], Xu et al. [2020b], Wang et al. [2020g], Chen et al. [2020e], Lv et al. [2020], Kong et al. [2020], Fukuda et al. [2020], Zhang & Guo [2020], Boukerche & Wang [2020b], Tang et al. [2020b], Kang et al. [2019], Guo et al. [2019c], Li et al. [2019b], Sun et al. [2020], Wei & Sheng [2020], Li et al. [2020f], Cao et al. [2020], Yu et al. [2018, 2019b], Li et al. [2020b], Yin et al. [2020], Chen et al. [2020g], Zhang et al. [2020a], Wang et al. [2020a], Xin et al. [2020], Xie et al. [2020d], Huang et al. [2020b], Li & Zhu [2021], Tian et al. [2020], Xu et al. [2020c], Chen et al. [2020c], Xiong et al. [2020], Chen et al. [2020d], Tang et al. [2020a], Zhang et al. [2018a, 2019a], Cirstea et al. [2019], Ge et al. [2019a, b], Shleifer et al. [2019], Ge et al. [2020], Yang et al. [2020], Zhao et al. [2019], Cui et al. [2019], Chen et al. [2019], Yu et al. [2019a], Wang et al. [2020f], Cui et al. [2020b, a], Zhou et al. [2020a], Cai et al. [2020], Zhou et al. [2020b], Wu et al. [2020c], Chen et al. [2020f], Opolka et al. [2019], Mallick et al. [2021], Oreshkin et al. [2021], Jia et al. [2020], Sun et al. [2021], Guo & Yuan [2020], Zhang et al. [2020i], Feng et al. [2020], Xie et al. [2020c], Park et al. [2020], Chen et al. [2020a], Lewenfus et al. [2020], Maas & Bloem [2020], Li et al. [2020d], Song et al. [2020b], Zhao et al. [2020b], Wang et al. [2020c]
Road Segment Graph Road Segments Road Intersections Zhang et al. [2018b], Guo et al. [2020a], Pan et al. [2019], Zhang et al. [2020j, l], Wang et al. [2018b], Zhang et al. [2020e], Lv et al. [2020], Zhang et al. [2019d, 2020a], Qu et al. [2020], Guo et al. [2020b], Ramadan et al. [2020], Zhao et al. [2020a], Bai et al. [2021], Shin & Yoon [2020], Liu et al. [2020a], Yu & Gu [2019], Xie et al. [2019], Guo et al. [2019a], Diao et al. [2019], Lu et al. [2019b], Zhang et al. [2019c], James [2019], Zhang et al. [2019b], Lee & Rhee [2022], Yu et al. [2020a], Lu et al. [2020b], Zhao et al. [2019], Cui et al. [2019], Zhang et al. [2019e], Lee & Rhee [2019], Cui et al. [2020b, a], Guo et al. [2020c], Xie et al. [2020b], Zhu et al. [2021, 2020], Fu et al. [2020], Zhang et al. [2020d], Agafonov [2020], Lu et al. [2020a], Jepsen et al. [2019, 2020], Zhu et al. [2022], Liao et al. [2018], Guopeng et al. [2020], Kim et al. [2020], Hasanzadeh et al. [2019], Fang et al. [2020b], Dai et al. [2020], Han et al. [2020], Hong et al. [2020], Chen et al. [2020h], Yu et al. [2020b]
Road Intersection Graph Road Intersections Road Segments Zhang et al. [2018b], Wei et al. [2019], Fang et al. [2019], Zhang et al. [2020e], Xu et al. [2019], Wu et al. [2018a], Sánchez et al. [2020], James [2020], Zhang et al. [2019f], Lu et al. [2019b], Zhang et al. [2019c], Bogaerts et al. [2020], Shao et al. [2020], Qin et al. [2020a]
Road Lane Graph Road Lanes Road Line Adjacency Wright et al. [2019]
Irregular Region Graph Irregular Regions Regional Adjacency or Virtual Edges Zhou et al. [2020d], Sun et al. [2020], Chen et al. [2020d], Bing et al. [2020], Mohanty & Pozdnukhov [2018], Mohanty et al. [2020], Hu et al. [2018], Li & Axhausen [2020], Bai et al. [2019b, a], Ke et al. [2021a], Hu et al. [2020], Zheng et al. [2020a], Davis et al. [2020], Du et al. [2020], Li & Moura [2020], Ye et al. [2021], Zhang et al. [2020k], Liu et al. [2020c]
Regular Region Graph Regular Regions Regional Adjacency or Virtual Edges Pan et al. [2020], Wang et al. [2020b], Zhang et al. [2020h], Wang et al. [2018a], Zhou et al. [2019], Wang et al. [2020e], Qiu et al. [2020], He & Shin [2020a], Yeghikyan et al. [2020], Shi et al. [2020], Wang et al. [2019], Shen et al. [2020], Pian & Wu [2020], Jin et al. [2020b, a], Geng et al. [2019b], Lee et al. [2019], Geng et al. [2019a], Li et al. [2020c], Xu & Li [2019], Davis et al. [2020], Wu et al. [2020a], Zhou et al. [2020e, f], Xu et al. [2020d]
OD Graph OD Pair Virtual Edges Wang et al. [2020h], Ke et al. [2021b]
Subway Station Graph Subway Stations Subway Lines Fang et al. [2019, 2020a], Ren & Xie [2019], Li et al. [2018a], Zhao et al. [2020a], Han et al. [2019], Zhang et al. [2020b, c], Li et al. [2020e], Liu et al. [2020b], Ye et al. [2020b], Ou et al. [2020]
Bus Station Graph Bus Stations Bus Lines Fang et al. [2019, 2020a]
Bike Station Graph Bike Stations Road Links He & Shin [2020b], Chai et al. [2018], Du et al. [2020], Chen et al. [2020b], Wang et al. [2020d], Qin et al. [2020b], Xiao et al. [2020], Yoshida et al. [2019], Guo et al. [2019b], Kim et al. [2019], Lin et al. [2018]
Railway Station Graph Railway Stations Railway Lines He et al. [2020], Heglund et al. [2020]
Car-sharing Station Graph Car-sharing Stations Road Links Zhu et al. [2019], Luo et al. [2020]
Parking Lot Graph Parking Lots Road Links Zhang et al. [2020g, f]
Parking Block Graph Parking Blocks Road Links Yang et al. [2019]

4.1.2 Adjacency Matrix Construction

Adjacency matrices are seen as the key to capturing spatial dependency in traffic forecasting [Ye et al., 2020a]. While nodes may be fixed by physical constraints, the user typically has control over the design of the adjacency matrix, which can even be dynamically trained from continuously evolving data. We extend the categories of adjacency matrices used in previous studies [Ye et al., 2020a] and divide them into four types, namely, road-based, distance-based, similarity-based, and dynamic matrices.

Road-based Matrix. This type of adjacency matrix relates to the road network and includes connection matrices, transportation connectivity matrices, and direction matrices. A connection matrix is a common way of representing the connectivity between nodes. It has a binary format, with an element value of 1 if connected and 0 otherwise. The transportation connectivity matrix is used where two regions are geographically distant but conveniently reachable by motorway, highway, or subway [Ye et al., 2020a]. It also includes cases where the connection is measured by travel time between different nodes, e.g. if a vehicle can travel between two intersections in less than 5 minutes then there is an edge between the two intersections [Wu et al., 2018a]. The less commonly used direction matrix takes the angle between road links into consideration.

Distance-based Matrix. This widely used matrix-type represents the spatial closeness between nodes. It contains two sub-types, namely, neighbor and distance matrices. In neighbor matrices, the element values are determined by whether the two regions share a common boundary (if connected the value is set to 1, generally, or 1/4 for grids, and 0 otherwise). In distance-based matrices, the element values are a function of geometrical distance between nodes. This distance may be calculated in various ways, e.g. the driving distance between two sensors, the shortest path length along the road [Kang et al., 2019, Lee & Rhee, 2022], or the proximity between locations calculated by the random walk with restart (RWR) algorithm [Zhang et al., 2019e]. One flaw of distance-based matrices is that the fail to take into account the similarity of traffic states between long-distance nodes, and the constructed adjacency matrix is static in most cases.

Similarity-based Matrix. This type of matrix is divided into two sub-types, namely, traffic pattern and functional similarity matrices. Traffic pattern similarity matrices represent the correlations between traffic states, e.g. similarities of flow patterns, mutual dependencies between different locations, and traffic demand correlation in different regions. Functional similarity matrices represent, for example, the distribution of different types of PoIs in different regions.

Dynamic Matrix. This type of matrix is used when no pre-defined static matrices are used. Many studies have demonstrated the advantages of using dynamic matrices, instead of a pre-defined adjacency matrix, for various traffic forecasting problems.

A full list of the adjacency matrices applied in the surveyed studies is shown in Table 3. Dynamic matrices are listed at the bottom of the table, with no further subdivisions. The connection and distance matrices are the most frequently used types, because of their simple definition and representation of spatial dependency.

Table 3: Adjacency matrices in the surveyed studies.
Adjacency Matrix Formula Relevant Studies
Connection Matrix aij=1subscript𝑎𝑖𝑗1a_{ij}=1 when nodes i𝑖i and j𝑗j are connected and aij=0subscript𝑎𝑖𝑗0a_{ij}=0 otherwise Zhang et al. [2018b], Wei et al. [2019], Xu et al. [2020a], Guo et al. [2020a], Zhang et al. [2020l], Wang et al. [2018b], Song et al. [2020a], Zhang & Guo [2020], Xu et al. [2019], Cao et al. [2020], Yu et al. [2019b], Chen et al. [2020g], Zhang et al. [2020a], Qu et al. [2020], Wang et al. [2020b], Huang et al. [2020b], Xiong et al. [2020], Sánchez et al. [2020], Wang et al. [2020h], Zhang et al. [2020c], Li et al. [2020e], Liu et al. [2020b], Ou et al. [2020], He et al. [2020], Bai et al. [2021], Liu et al. [2020a], Zhang et al. [2019f], Yu & Gu [2019], Xie et al. [2019], Guo et al. [2019a], Lu et al. [2019b], Zhang et al. [2019c], James [2019], Zhang et al. [2019b], Zhao et al. [2019], Cui et al. [2019, 2020b, 2020a], Wu et al. [2020c], Opolka et al. [2019], Sun et al. [2021], Guo & Yuan [2020], Xie et al. [2020b], Zhu et al. [2021, 2020], Zhang et al. [2020d], Agafonov [2020], Chen et al. [2020a], Lu et al. [2020a], Bing et al. [2020], Zhu et al. [2022], Fang et al. [2020b], Shao et al. [2020], Shen et al. [2020], Qin et al. [2020a], Hong et al. [2020], Xu & Li [2019], Davis et al. [2020], Chen et al. [2020h], Wang et al. [2020d], Zhou et al. [2020e], Yu et al. [2020b], Liu et al. [2020c], Zhang et al. [2020g, f], Heglund et al. [2020], Yin et al. [2020], Zhang et al. [2020b]
Transportation Connectivity Matrix aij=1subscript𝑎𝑖𝑗1a_{ij}=1 when one can travel from node i𝑖i to node j𝑗j and aij=0subscript𝑎𝑖𝑗0a_{ij}=0 otherwise Pan et al. [2020, 2019], Lv et al. [2020], Wu et al. [2018a], Ye et al. [2020b], Geng et al. [2019b, a], Luo et al. [2020], Wright et al. [2019]
Direction Matrix aij=subscript𝑎𝑖𝑗absenta_{ij}= the angle between two road segments Shin & Yoon [2020], Lee & Rhee [2022, 2019]
Neighbor Matrix aij=1subscript𝑎𝑖𝑗1a_{ij}=1 when nodes i𝑖i and j𝑗j are neighbors and aij=0subscript𝑎𝑖𝑗0a_{ij}=0 otherwise Wang et al. [2018a], Yeghikyan et al. [2020], Shi et al. [2020], Wang et al. [2019], Hu et al. [2018], Geng et al. [2019b], Lee et al. [2019], Ke et al. [2021a, b], Hu et al. [2020], Zheng et al. [2020a], Yoshida et al. [2019]
Distance Matrix aij=dijsubscript𝑎𝑖𝑗subscript𝑑𝑖𝑗a_{ij}=d_{ij} and dijsubscript𝑑𝑖𝑗d_{ij} is some distance between nodes i𝑖i and j𝑗j Li et al. [2018b], Zheng et al. [2020b], Pan et al. [2020, 2019], Lu et al. [2019a], Mallick et al. [2020], Huang et al. [2020a], Xu et al. [2020b], Wang et al. [2020g], Boukerche & Wang [2020b], Kang et al. [2019], Sun et al. [2020], Wei & Sheng [2020], Yu et al. [2018], Li et al. [2020b], Chen et al. [2020g], Wang et al. [2020a], Xin et al. [2020], Xie et al. [2020d], Li & Zhu [2021], Tian et al. [2020], Xu et al. [2020c], Chen et al. [2020c], Zhou et al. [2020d], Chen et al. [2020d], He & Shin [2020a], Ren & Xie [2019], Zhu et al. [2019], He & Shin [2020b], Chai et al. [2018], Shin & Yoon [2020], Zhang et al. [2018a], Ge et al. [2019a, b], Lee & Rhee [2022], Shleifer et al. [2019], Ge et al. [2020], Yang et al. [2020], Chen et al. [2019], Zhang et al. [2019e], Lee & Rhee [2019], Bogaerts et al. [2020], Wang et al. [2020f], Guo et al. [2020c], Zhou et al. [2020a], Cai et al. [2020], Zhou et al. [2020b], Chen et al. [2020f], Mallick et al. [2021], Jia et al. [2020], Zhang et al. [2020i], Feng et al. [2020], Xie et al. [2020c], Li et al. [2020d], Song et al. [2020b], Zhao et al. [2020b], Kim et al. [2020], Mohanty & Pozdnukhov [2018], Mohanty et al. [2020], Jin et al. [2020b], Li & Axhausen [2020], Jin et al. [2020a], Geng et al. [2019a], Ke et al. [2021a], Li et al. [2020c], Ke et al. [2021b], Luo et al. [2020], Chen et al. [2020b], Xiao et al. [2020], Guo et al. [2019b], Kim et al. [2019], Lin et al. [2018], Yang et al. [2019], Wang et al. [2020c], Xu et al. [2020d]
Traffic Pattern Similarity Matrix aij=subscript𝑎𝑖𝑗absenta_{ij}= the correlation coefficient of historical traffic states of nodes i𝑖i and j𝑗j Lv et al. [2020], Li & Zhu [2021], Xu et al. [2020c], Zhou et al. [2020d], Sun et al. [2020], Wang et al. [2020e], He & Shin [2020a], Ren & Xie [2019], Han et al. [2019], Liu et al. [2020b], He & Shin [2020b], Chai et al. [2018], Lu et al. [2020a], Lewenfus et al. [2020], Dai et al. [2020], Han et al. [2020], Jin et al. [2020b], Li & Axhausen [2020], Jin et al. [2020a], Bai et al. [2019b, a], Li et al. [2020c], Ke et al. [2021b], Chen et al. [2020b], Wang et al. [2020d], Yoshida et al. [2019], Kim et al. [2019], Lin et al. [2018], Zhou et al. [2020f]
Functional Similarity Matrix aij=subscript𝑎𝑖𝑗absenta_{ij}= the correlation coefficient of POI distributions in regions i𝑖i and j𝑗j Lv et al. [2020], He & Shin [2020a], Shi et al. [2020], Zhu et al. [2019], Ge et al. [2019a, b, 2020], Jin et al. [2020b], Geng et al. [2019b, a], Ke et al. [2021b], Luo et al. [2020], Zhang et al. [2020k]
Dynamic Matrix N/A Wu et al. [2019], Bai et al. [2020], Fang et al. [2019], Zhang et al. [2020e], Chen et al. [2020e], Kong et al. [2020], Tang et al. [2020b], Guo et al. [2019c], Li et al. [2019b], Zhang et al. [2019d], Li et al. [2020f], Guo et al. [2020b], Zhang et al. [2020h], Peng et al. [2020], Zhou et al. [2019], Shi et al. [2020], Li et al. [2018a], Tang et al. [2020a], Zhang et al. [2019a], Diao et al. [2019], Yu et al. [2020a], Fu et al. [2020], Maas & Bloem [2020], Li & Axhausen [2020], Du et al. [2020], Li & Moura [2020], Wu et al. [2020a], Ye et al. [2021]

4.2 Graph Neural Networks

Previous neural networks, e.g. fully-connected neural networks (FNNs), CNNs, and RNNs, could only be applied to Euclidean data (i.e. images, text, and videos). As a type of neural network which directly operates on a graph structure, GNNs have the ability to capture complex relationships between objects and make inferences based on data described by graphs. GNNs have been proven effective in various node-level, edge-level, and graph-level prediction tasks [Jiang, 2022]. As mentioned in Section 2, GNNs are currently considered the state-of-the-art techniques for traffic forecasting problems. GNNs can be roughly divided into four types, namely, recurrent GNNs, convolutional GNNs, graph autoencoders, and spatiotemporal GNNs [Wu et al., 2020b]. Because traffic forecasting is a spatiotemporal problem, the GNNs used in this field can all be categorized as the spatiotemporal GNNs. However, certain components of the other types of GNNs have also been applied in the surveyed traffic forecasting studies.

To give the mathematical formulation of GCN, we further introduce some notations. Give a graph G=(V,E,A)𝐺𝑉𝐸𝐴G=(V,E,A), 𝒩(vi)𝒩subscript𝑣𝑖\mathcal{N}(v_{i}) is defined as the neighbor node set of a single node visubscript𝑣𝑖v_{i}. 𝐃𝐃\mathbf{D} is defined as the degree matrix, of which each element is 𝐃ii=𝒩(vi)subscript𝐃𝑖𝑖norm𝒩subscript𝑣𝑖\mathbf{D}_{ii}=\|\mathcal{N}(v_{i})\|. 𝐋=𝐃𝐀𝐋𝐃𝐀\mathbf{L}=\mathbf{D}-\mathbf{A} is defined as the Laplacian matrix of an undirected graph and 𝐋~=𝐈N𝐃12𝐀𝐃12~𝐋subscript𝐈𝑁superscript𝐃12superscript𝐀𝐃12\tilde{\mathbf{L}}=\mathbf{I}_{N}-\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}} is defined as the normalized Laplacian matrix, where 𝐈Nsubscript𝐈𝑁\mathbf{I}_{N} is the identity matrix with size N𝑁N. Without considering the time step index, the node feature matrix of a graph is simplified as 𝐗RN×d𝐗superscript𝑅𝑁𝑑\mathbf{X}\in{R}^{N\times d}, where N𝑁N is the node number and d𝑑d is the dimension of the node feature vector as before. The basic notations used in this survey is summarized in Table 4.

Table 4: Basic notations used in this study.
Symbol Description
G𝐺G Graph
V𝑉V Node set
E𝐸E Edge set
A𝐴A Adjacency matrix
χtsubscript𝜒𝑡\chi_{t} or 𝐗𝐗\mathbf{X} Node feature matrix w/o time step index t𝑡t
N𝑁N Node number
d𝑑d Node feature dimension
𝒩(vi)𝒩subscript𝑣𝑖\mathcal{N}(v_{i}) Neighbor node set of a single node visubscript𝑣𝑖v_{i}
𝐃𝐃\mathbf{D} Degree matrix
𝐋𝐋\mathbf{L} Laplacian matrix
𝐋~~𝐋\tilde{\mathbf{L}} Normalized Laplacian matrix
𝐈Nsubscript𝐈𝑁\mathbf{I}_{N} Identity matrix with size N𝑁N

When extending the convolution operation from Euclidean data to non-Euclidean data, the basic idea of GNNs is to learn a function mapping for a node to aggregate its own features and the features of its neighbors to generate a new representation. GCNs are spectral-based convolutional GNNs, in which the graph convolutions are defined by introducing filters from graph signal processing in the spectral domain, e.g., the Fourier domain. The graph Fourier transform is firstly used to transform the graph signal to the spectral domain and the inverse graph Fourier transform is further used to transform the result after the convolution operation back. Several spectral-based GCNs are introduced in the literature. Spectral convoluted neural networking [Bruna et al., 2014] assumes that the filter is a set of learnable parameters and considers graph signals with multiple channels. GNN [Henaff et al., 2015] introduces a parameterization with smooth coefficients and makes the spectral filters spatially localized. Chebyshev’s spectral CNN (ChebNet) [Defferrard et al., 2016] leverages a truncated expansion in terms of Chebyshev polynomials up to K𝐾Kth order to approximate the diagonal matrix.

GCN [Kipf & Welling, 2017] is a first-order approximation of ChebNet, which approximates the filter using the Chebyshev polynomials of the diagonal matrix of eigenvalues. To avoid overfitting, K=1𝐾1K=1 is used in GCN. Formally, the graph convolution operation Gabsent𝐺*G in GCN is defined as follows:

𝐗G=𝐖(𝐈N+𝐃12𝐀𝐃12)𝐗subscript𝐗absent𝐺𝐖subscript𝐈𝑁superscript𝐃12superscript𝐀𝐃12𝐗\mathbf{X}_{*G}=\mathbf{W}(\mathbf{I}_{N}+\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}})\mathbf{X} (1)

where 𝐖𝐖\mathbf{W} is a learnable weight matrix, i.e., the model parameters. While in practice, the graph convolution operation is further developed in order to alleviate the potential gradient explosion problem as follows:

𝐗G=𝐖(𝐃~12𝐀~𝐃~12)𝐗subscript𝐗absent𝐺𝐖superscript~𝐃12~𝐀superscript~𝐃12𝐗\mathbf{X}_{*G}=\mathbf{W}(\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}})\mathbf{X} (2)

where 𝐀~=𝐀+𝐈N~𝐀𝐀subscript𝐈𝑁\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}_{N} and 𝐃~ii=j𝐀~ijsubscript~𝐃𝑖𝑖subscript𝑗subscript~𝐀𝑖𝑗\tilde{\mathbf{D}}_{ii}=\sum_{j}{\tilde{\mathbf{A}}_{ij}}.

The alternative approach is spatial-based convolutional GNNs, in which the graph convolutions are defined by information propagation. Diffusion graph convolution (DGC) [Atwood & Towsley, 2016], message passing neural network (MPNN) [Gilmer et al., 2017], GraphSAGE [Hamilton et al., 2017], and graph attention network (GAT) [Veličković et al., 2018] all follow this approach. The graph convolution is modeled as a diffusion process with a transition probability from one node to a neighboring node in DGC. An equilibrium is expected to be obtained after several rounds of information transition. The general framework followed is a message passing network, which models the graph convolutions as an information-passing process from one node to another connected node directly. To alleviate the computation problems caused by a large number of neighbors, sampling is used to obtain a fixed number of neighbors in GraphSAGE. Lastly, without using a predetermined adjacency matrix, the attention mechanism is used to learn the relative weights between two connected nodes in GAT.

MPNN uses message passing functions to unify different spatial-based variants. MPNN operates in two stages, namely, a message passing phase and a readout phase. The message passing phase is defined as follows:

𝐦vi(t)=vj𝒩(vi)(t)(𝐗i(t1),𝐗j(t1),𝐞ij)superscriptsubscript𝐦subscript𝑣𝑖𝑡subscriptsubscript𝑣𝑗𝒩subscript𝑣𝑖superscript𝑡superscriptsubscript𝐗𝑖𝑡1superscriptsubscript𝐗𝑗𝑡1subscript𝐞𝑖𝑗\mathbf{m}_{v_{i}}^{(t)}=\sum_{v_{j}\in\mathcal{N}{(v_{i})}}\mathcal{M}^{(t)}(\mathbf{X}_{i}^{(t-1)},\mathbf{X}_{j}^{(t-1)},\mathbf{e}_{ij}) (3)

where 𝐦vi(t)superscriptsubscript𝐦subscript𝑣𝑖𝑡\mathbf{m}_{v_{i}}^{(t)} is the message aggregated from the neighbors of node visubscript𝑣𝑖v_{i}, (t)()superscript𝑡\mathcal{M}^{(t)}(\cdot) is the aggregation function in the t𝑡t-th iteration, 𝐗i(t)superscriptsubscript𝐗𝑖𝑡\mathbf{X}_{i}^{(t)} is the hidden state of node visubscript𝑣𝑖v_{i} in the t𝑡t-th iteration, and 𝐞ijsubscript𝐞𝑖𝑗\mathbf{e}_{ij} is the edge feature vector between node visubscript𝑣𝑖v_{i} and node vjsubscript𝑣𝑗v_{j}.

The readout phase is defined as follows:

𝐗i(t)=𝒰(t)(𝐗i(t1),𝐦vi(t))superscriptsubscript𝐗𝑖𝑡superscript𝒰𝑡superscriptsubscript𝐗𝑖𝑡1superscriptsubscript𝐦subscript𝑣𝑖𝑡\mathbf{X}_{i}^{(t)}=\mathcal{U}^{(t)}(\mathbf{X}_{i}^{(t-1)},\mathbf{m}_{v_{i}}^{(t)}) (4)

where 𝒰(t)()superscript𝒰𝑡\mathcal{U}^{(t)}(\cdot) is the readout function in the t𝑡t-th iteration.

In GAT [Veličković et al., 2018], the attention mechanism [Vaswani et al., 2017] is incorporated into the propagation step and the multi-head attention mechanism is further utilized with the aim of stabilizing the learning process. The specific operation is defined as follows:

𝐗i(t)=kσ(j𝒩(vi)αk(𝐗i(t1),𝐗j(t1))𝐖(t1)𝐗j(t1))\mathbf{X}_{i}^{(t)}=\|_{k}\sigma(\sum_{j\in\mathcal{N}{(v_{i})}}\alpha^{k}(\mathbf{X}_{i}^{(t-1)},\mathbf{X}_{j}^{(t-1)})\mathbf{W}^{(t-1)}\mathbf{X}_{j}^{(t-1)}) (5)

where \| is the concatenation operation, σ𝜎\sigma is the activation method, αk()superscript𝛼𝑘\alpha^{k}(\cdot) is the k𝑘k-th attention mechanism.

A general spatiotemporal GNN structure is shown in Figure 5, in which GCN is used to capture the spatial dependency and 1D-CNN is used to capture the temporal dependency. Both GCN and 1D-CNN components can be replaced with other structures for other spatiotemporal GNNs. A multilayer perceptron (MLP) component is used to generate the desired output. As for comparison, a two-layer GCN is also shown in Figure 5, in which only the spatial dependency is concerned.

Refer to caption
Refer to caption
Figure 5: A comparison between a two-layer GCN model and a typical spatiotemporal GNN structure (1D-CNN+GCN as an example). Adapted from Wang et al. [2021]. 5 a two-layer GCN model; 5 a typical spatiotemporal GNN structure.

Spatiotemporal GNNs can be further categorized based on the approach used to capture the temporal dependency in particular. Most of the relevant studies in the literature can be split into two types, namely, RNN-based and CNN-based spatiotemporal GNNs [Wu et al., 2020b]. The RNN-based approach is used in Li et al. [2018b], Guo et al. [2020a], Pan et al. [2020, 2019], Lu et al. [2019a], Mallick et al. [2020], Zhang et al. [2020j, l], Bai et al. [2020], Huang et al. [2020a], Wang et al. [2018b, 2020g], Lv et al. [2020], Fukuda et al. [2020], Zhang & Guo [2020], Boukerche & Wang [2020b], Kang et al. [2019], Li et al. [2019b], Xu et al. [2019], Wu et al. [2018a], Wei & Sheng [2020], Li et al. [2020f], Yu et al. [2019b], Yin et al. [2020], Xin et al. [2020], Qu et al. [2020], Huang et al. [2020b], Guo et al. [2020b], Fang et al. [2020a], Li & Zhu [2021], Chen et al. [2020c], Ramadan et al. [2020], Zhou et al. [2020d], Wang et al. [2018a], Peng et al. [2020], Zhou et al. [2019], Wang et al. [2020e], Qiu et al. [2020], Shi et al. [2020], Wang et al. [2020h, 2019], Zhang et al. [2020b], Liu et al. [2020b], Ye et al. [2020b], Zhu et al. [2019], Chai et al. [2018], He et al. [2020], Bai et al. [2021], Zhang et al. [2018a, 2019f], Xie et al. [2019], Zhang et al. [2019a], Guo et al. [2019a], Cirstea et al. [2019], Lu et al. [2019b], Zhang et al. [2019b], Lu et al. [2020b], Zhao et al. [2019], Cui et al. [2019], Chen et al. [2019], Zhang et al. [2019e], Bogaerts et al. [2020], Cui et al. [2020a], Zhou et al. [2020a], Mallick et al. [2021], Sun et al. [2021], Xie et al. [2020b], Zhu et al. [2021, 2020], Fu et al. [2020], Chen et al. [2020a], Lewenfus et al. [2020], Zhu et al. [2022], Liao et al. [2018], Zhao et al. [2020b], Guopeng et al. [2020], Shao et al. [2020], Shen et al. [2020], Mohanty & Pozdnukhov [2018], Mohanty et al. [2020], Hu et al. [2018], Pian & Wu [2020], Jin et al. [2020a], Geng et al. [2019a], Bai et al. [2019a], Li et al. [2020c], Ke et al. [2021b], Hu et al. [2020], Xu & Li [2019], Davis et al. [2020], Chen et al. [2020h], Du et al. [2020], Wu et al. [2020a], Ye et al. [2021], Luo et al. [2020], Chen et al. [2020b], Wang et al. [2020d], Xiao et al. [2020], Guo et al. [2019b], Lin et al. [2018], Zhou et al. [2020f], Liu et al. [2020c], Zhang et al. [2020g], Yang et al. [2019], Zhang et al. [2020f], Wang et al. [2020c], Wright et al. [2019]; while the CNN-based approach is used in Wu et al. [2019], Fang et al. [2019], Zhang et al. [2020e], Xu et al. [2020b], Chen et al. [2020e], Kong et al. [2020], Tang et al. [2020b], Guo et al. [2019c], Sun et al. [2020], Yu et al. [2018], Li et al. [2020b], Wang et al. [2020a], Tian et al. [2020], Chen et al. [2020d], Zhao et al. [2020a], Zhang et al. [2020c], Ou et al. [2020], Tang et al. [2020a], Diao et al. [2019], Lee & Rhee [2022, 2019], Wang et al. [2020f], Wu et al. [2020c], Guo & Yuan [2020], Zhang et al. [2020i], Feng et al. [2020], Zhang et al. [2020d], Xie et al. [2020c], Lu et al. [2020a], Maas & Bloem [2020], Li et al. [2020d], Song et al. [2020b], Dai et al. [2020], Hong et al. [2020], Zheng et al. [2020a], Zhou et al. [2020e], Yu et al. [2020b], Xu et al. [2020d], Heglund et al. [2020].

With the recent expansion of relevant studies, we add two sub-types of spatiotemporal GNNs in this survey, namely, attention-based and FNN-based. Attention mechanism is firstly proposed to memorize long source sentences in neural machine translation [Vaswani et al., 2017]. Then it is used for temporal forecasting problems. As a special case, Transformer is built entirely upon attention mechanisms, which makes it possible to access any part of a sequence regardless of its distance to the target [Xie et al., 2020d, Cai et al., 2020, Jin et al., 2020b, Li & Moura, 2020]. The attention-based approaches are used in Zheng et al. [2020b], Zhang et al. [2020a], Wang et al. [2020b], Xie et al. [2020d], Cai et al. [2020], Zhou et al. [2020b], Chen et al. [2020f], Park et al. [2020], Fang et al. [2020b], Jin et al. [2020b], Bai et al. [2019b], Li & Moura [2020], Zhang et al. [2020k], while the simpler FNN-based approach is used in Zhang et al. [2018b], Wei et al. [2019], Song et al. [2020a], Cao et al. [2020], Chen et al. [2020g], Zhang et al. [2020h], Sun et al. [2020], He & Shin [2020a], Yeghikyan et al. [2020], Ren & Xie [2019], Li et al. [2018a], Han et al. [2019], He & Shin [2020b], Zhang et al. [2019c], Ge et al. [2019a, b], Yu et al. [2020a], Ge et al. [2020], Yu et al. [2019a], Guo et al. [2020c], Agafonov [2020], Geng et al. [2019b], Qin et al. [2020b], Kim et al. [2019]. Apart from using neural networks to capture temporal dependency, other techniques that have also been combined with GNNs include autoregression [Lee et al., 2019], Markov processes [Cui et al., 2020b], and Kalman filters [Xiong et al., 2020].

Among different approaches for temporal modeling, RNNs suffer from time-consuming iterations and gradient vanishing or explosion problem with long sequences. CNNs demonstrate their superiority in terms of simple structure, parallel computing and stable gradients. As for the traffic problems, the spatial and temporal dependencies are closely intertwined in reality. For example, it is argued that the historical observations in different locations at different times have varying impacts on central region in the future [Guo et al., 2019c]. Some efforts are put to jointly modeling the potential interaction between spatial and temporal features and one promising direction is the incorporate of the graph convolution operations into RNNs to capture spatial-temporal correlations [Yu et al., 2019b, Zhou et al., 2019, Chen et al., 2019, Liu et al., 2020b, Chen et al., 2020f, Guo et al., 2020a]. For example, the localized spatio-temporal correlation information is extracted simultaneously with the adjacency matrix of localized spatio-temporal graph in Song et al. [2020a], in which a localized spatio-temporal graph that includes both temporal and spatial attributes is constructed first and a spatial-based GCN method is applied then.

Of the additional GNN components adopted in the surveyed studies, convolutional GNNs are the most popular, while recurrent GNN [Scarselli et al., 2008] and Graph Auto-Encoder (GAE) [Kipf & Welling, 2016] are used less frequently. We further categorize convolutional GNNs into the following five types: (1) GCN [Kipf & Welling, 2017], (2) DGC [Atwood & Towsley, 2016], (3) MPNN [Gilmer et al., 2017], (4) GraphSAGE [Hamilton et al., 2017], and (5) GAT [Veličković et al., 2018]. These relevant graph neural networks are listed chronologically in Figure 6. While different GNNs can be used for traffic forecasting, a general design pipeline is proposed in [Zhou et al., 2020c] and suggested for future studies as follows:

  1. 1.

    Find graph structure. As discussed in Section IV, different traffic graphs are available.

  2. 2.

    Specify graph type and scale. The graphs can be further classified into different types if needed, e.g., directed/undirected graphs, homogeneous/heterogeneous graphs, static/dynamic graphs. For most cases in traffic forecasting, the graphs of the same type are used in a single study. As for the graph scale, the graphs in the traffic domain are not as large as those for the social networks or academic networks with millions of nodes and edges.

  3. 3.

    Design loss function. The training setting usually follows the supervised approach, which means the GNN-based models are firstly trained on a training set with labels and then evaluated on a test set. The forecasting task is usually designed as the node-level regression problem. Based on these considerations, the proper loss function and evaluation metrics can be chosen, e.g., root mean square error (RMSE), mean absolute error (MAE) and mean absolute percentage error (MAPE).

  4. 4.

    Build model using computational modules. The GNNs discussed in this section are exactly those which have already been used as computational modules to build forecasting models in the surveyed studies.

Refer to caption
Figure 6: The relevant graph neural networks in this survey.

A full list of the GNN components used in the surveyed studies is shown in Table 5. Currently, the most widely used GNN is the GCN. However, we also notice a growing trend in the use of GAT in traffic forecasting.

Table 5: GNNs in the surveyed studies.
GNN Relevant Studies
Recurrent GNN Wang et al. [2018b, a], Lu et al. [2019b, 2020b]
GAE Xu et al. [2020a, 2019], Opolka et al. [2019], Shen et al. [2020]
GCN Wu et al. [2019], Zhang et al. [2018b], Guo et al. [2020a], Lu et al. [2019a], Zhang et al. [2020j, l], Bai et al. [2020], Fang et al. [2019], Zhang et al. [2020e], Song et al. [2020a], Xu et al. [2020b], Wang et al. [2020g], Lv et al. [2020], Boukerche & Wang [2020b], Tang et al. [2020b], Guo et al. [2019c], Li et al. [2019b], Zhang et al. [2019d], Sun et al. [2020], Li et al. [2020f], Cao et al. [2020], Yu et al. [2018, 2019b], Li et al. [2020b], Chen et al. [2020g], Zhang et al. [2020a], Wang et al. [2020a], Xin et al. [2020], Qu et al. [2020], Wang et al. [2020b], Huang et al. [2020b], Guo et al. [2020b], Fang et al. [2020a], Li & Zhu [2021], Xu et al. [2020c], Chen et al. [2020c], Xiong et al. [2020], Ramadan et al. [2020], Zhou et al. [2020d], Sun et al. [2020], Peng et al. [2020], Zhou et al. [2019], Wang et al. [2020e], Qiu et al. [2020], He & Shin [2020a], Yeghikyan et al. [2020], Shi et al. [2020], Wang et al. [2020h], Ren & Xie [2019], Li et al. [2018a], Zhao et al. [2020a], Han et al. [2019], Zhang et al. [2020b, c], Liu et al. [2020b], Ye et al. [2020b], Zhu et al. [2019], Chai et al. [2018], He et al. [2020], Bai et al. [2021], Tang et al. [2020a], James [2020], Zhang et al. [2018a, 2019f], Yu & Gu [2019], Guo et al. [2019a], Diao et al. [2019], Zhang et al. [2019c], James [2019], Ge et al. [2019a, b], Zhang et al. [2019b], Lee & Rhee [2022], Yu et al. [2020a], Ge et al. [2020], Zhao et al. [2019], Cui et al. [2019], Zhang et al. [2019e], Yu et al. [2019a], Lee & Rhee [2019], Bogaerts et al. [2020], Cui et al. [2020b, a], Guo et al. [2020c], Cai et al. [2020], Wu et al. [2020c], Chen et al. [2020f], Jia et al. [2020], Sun et al. [2021], Xie et al. [2020b], Zhu et al. [2021], Feng et al. [2020], Zhu et al. [2020], Fu et al. [2020], Agafonov [2020], Chen et al. [2020a], Lu et al. [2020a], Jepsen et al. [2019, 2020], Bing et al. [2020], Lewenfus et al. [2020], Zhu et al. [2022], Liao et al. [2018], Maas & Bloem [2020], Li et al. [2020d], Song et al. [2020b], Zhao et al. [2020b], Guopeng et al. [2020], Shao et al. [2020], Dai et al. [2020], Mohanty & Pozdnukhov [2018], Mohanty et al. [2020], Qin et al. [2020a], Han et al. [2020], Hong et al. [2020], Hu et al. [2018], Li & Axhausen [2020], Jin et al. [2020a], Geng et al. [2019b], Bai et al. [2019b], Geng et al. [2019a], Bai et al. [2019a], Ke et al. [2021a], Li et al. [2020c], Ke et al. [2021b], Hu et al. [2020], Zheng et al. [2020a], Davis et al. [2020], Chen et al. [2020h], Du et al. [2020], Li & Moura [2020], Ye et al. [2021], Luo et al. [2020], Chen et al. [2020b], Wang et al. [2020d], Qin et al. [2020b], Xiao et al. [2020], Yoshida et al. [2019], Guo et al. [2019b], Kim et al. [2019], Lin et al. [2018], Zhou et al. [2020e], Yu et al. [2020b], Zhang et al. [2020k], Zhou et al. [2020f], Liu et al. [2020c], Zhang et al. [2020g], Yang et al. [2019], Zhang et al. [2020f], Xu et al. [2020d], Heglund et al. [2020]
DGC Li et al. [2018b], Mallick et al. [2020], Chen et al. [2020e], Fukuda et al. [2020], Ou et al. [2020], Chen et al. [2019], Wang et al. [2020f], Zhou et al. [2020a, b], Mallick et al. [2021], Xie et al. [2020c], Kim et al. [2020], Wang et al. [2020c]
MPNN Wei et al. [2019], Xu et al. [2020b], Wang et al. [2019]
GraphSAGE Liu et al. [2020a]
GAT Zheng et al. [2020b], Pan et al. [2020, 2019], Huang et al. [2020a], Kong et al. [2020], Zhang & Guo [2020], Tang et al. [2020b], Kang et al. [2019], Wu et al. [2018a], Wei & Sheng [2020], Yin et al. [2020], Xie et al. [2020d], Zhang et al. [2020h], Tian et al. [2020], He & Shin [2020b], Tang et al. [2020a], Zhang et al. [2019a], Cirstea et al. [2019], Yang et al. [2020], Guo & Yuan [2020], Zhang et al. [2020i, d], Park et al. [2020], Song et al. [2020b], Fang et al. [2020b], Pian & Wu [2020], Jin et al. [2020b], Xu & Li [2019], Wu et al. [2020a], Wright et al. [2019]

During the process of customizing GNNs for traffic forecasting, some classical models stand out in the literature. The most famous one is diffusion convolutional recurrent neural network (DCRNN) [Li et al., 2018b], which uses diffusion graph convolutional networks and RNN to learn the representations of spatial dependencies and temporal relations. DCRNN was originally proposed for traffic speed forecasting and is now widely used as a baseline. To create the traffic graph, the adjacency matrix is defined as the thresholded pairwise road network distances. Compared with other graph convolutional models that can only operate on undirected graphs, e.g., ChebNet, DCRNN introduces the diffusion convolution (DC) operation for directed graph and is more suitable for transportation scenarios, which is defined as follows:

𝐗DC=k=0K1(θk,1(DO1A)k)+θk,2(DI1AT)k)𝐗\mathbf{X}_{*DC}=\sum_{k=0}^{K-1}(\theta_{k,1}(D_{O}^{-1}A)^{k})+\theta_{k,2}(D_{I}^{-1}A^{T})^{k})\mathbf{X} (6)

where 𝐗RN×d𝐗superscript𝑅𝑁𝑑\mathbf{X}\in{R}^{N\times d} is the node feature matrix, A𝐴A is the adjacency matrix, DOsubscript𝐷𝑂D_{O} and DIsubscript𝐷𝐼D_{I} are diagonal out-degree and in-degree matrices, θk,1subscript𝜃𝑘1\theta_{k,1} and θk,2subscript𝜃𝑘2\theta_{k,2} are model parameters, K𝐾K is the number of diffusion steps. By defining and using out-degree and in-degree matrices, DCRNN models the bidirectional diffusion process to capture the influence of both upstream and downstream traffic. While DCRNN is a strong baseline, it is not suitable or desirable for the undirected graph cases. Then DCRNN is extended with a stronger learning ability in graph GRU in Zhang et al. [2018a], in which a unified method for constructing an RNN based on an arbitrary graph convolution operator is proposed, instead of the single RNN model used in DCRNN.

Spatio-temporal graph convolutional network (STGCN) [Yu et al., 2018] stacks multiple spatio-temporal convolution blocks and each block concatenate two temporal convolution and one graph convolution layer. ChebNet is chosen as the graph convolution operator in STGCN, after a comparison with its first-order approximation. The usage of temporal convolution layers instead of RNNs for temporal modeling accelerates the training phase of STGCN. Attention based Spatio-temporal graph convolutional network (ASTGCN) [Guo et al., 2019c] further introduces two attention layers in STGCN to capture the dynamic correlations in spatial dimension and temporal dimension, respectively.

Graph WaveNet [Wu et al., 2019] constructs a self-adaptive matrix to uncover unseen graph structures automatically from the data and WaveNet, which is based on causal convolutions, is used to learn temporal relations. However, the self-adaptive matrix in Graph WaveNet is fixed after training, which is unable to be adjusted dynamically with the data characteristics.

5 Open Data and Source Codes

In this section, we summarize the open data and source code used in the surveyed papers. These open data are suitable for GNN-related studies with graph structures discussed in Section IV, which can be used to formulate different forecasting problems in Section III. We also list the GNN-related code resources for those who want to replicate the previous GNN-based solutions as baselines in the follow-up studies.

5.1 Open Data

We categorize the data used in the surveyed studies into three major types, namely, graph-related data, historical traffic data, and external data. Graph-related data refer to those data which exhibit a graph structure in the traffic domain, i.e., transportation network data. Historical traffic data refer to those data which record the historical traffic states, usually in different locations and time points. We further categorize the historical traffic data into sub-types as follows. External data refer to the factors that would affect the traffic states, i.e., weather data and calendar data. Some of these data can be used in the graph-based modeling directly, while the others may require some pre-processing steps before being Incorporated into GNN-based models.

Transportation Network Data. These data represent the underlying transportation infrastructure, e.g., road, subway, and bus networks. They can be obtained from government transportation departments or extracted from online map services, e.g., OpenStreetMap. Based on their topology structure, these data can be used to build the graphs directly, e.g., the road segments or the stations are nodes and the road intersections or subway links are the edges. While this modeling approach is straightforward, the disadvantage is that only static graphs can be built from transportation network data.

Traffic Sensor Data. Traffic sensors, e.g. loop detectors, are installed on roads to collect traffic information, e.g., traffic volume or speed. This type of data is widely used for traffic prediction, especially road traffic flow and speed prediction problems. For graph-based modeling, each sensor can be used as a node, with road connections as the edges. One advantage of using traffic sensor data for graph-based modeling is that the captured traffic information can be used directly as the node attributes, with little pre-processing overhead. One exception is that the sensors are prone to hardware faults, which causes the missing data or data noise problems and requires corresponding pre-processing techniques, e.g., data imputation and denoising methods. Another disadvantage of using traffic sensor data for graph-based modeling is that the traffic sensors can only be installed in a limited number of locations for a series of reasons, e.g., installation cost. With this constraint, only the part of the road networks with traffic sensors can be incorporated into a graph, while the uncovered areas are neglected.

GPS Trajectory Data. Different types of vehicles (e.g. taxis, buses, online ride-hailing vehicles, and shared bikes) can be equipped with GPS receivers, which record GPS coordinates in 2-60 second intervals. The trajectory data calculated from these GPS coordinate samples can be matched to road networks and further used to derive traffic flow or speed. The advantage of using GPS trajectory data for graph-based modeling is both the low expense to collect GPS data with smartphones and the wider coverage with the massive number of vehicles, compared with traffic sensor data. However, GPS trajectory data contain no direct traffic information, which can be derived with corresponding definitions though. The data quality problems also remain with GPS trajectory data and more pre-processing steps are required, e.g., map matching.

Location-based Service Data. GPS function is also embedded in smartphones, which can be used to collect various types of location-related data, e.g., check-in data, point-of-interest data, and route navigation application data. The pros and cons of using location-based service data are similar with GPS trajectory data. And the difference is that location-based service data are often collected in a crowd-sourced approach, with more data providers but potentially a lower data quality.

Trip Record Data. These include departure and arrival dates/times, departure and arrival locations, and other trip information. Traffic speed and demand can derived from trip record data from various sources, e.g., taxis, ride-hailing services, buses, bikes, or even dock-less e-scooters used in He & Shin [2020a]. These data can be collected in public transportation systems with mature methods, for example, by AFC (Automatic Fare Collection) in the subway and bus systems. Trip record data have the advantage of being capable of constructing multiple graph-based problems, e.g., station-level traffic flow and demand problems. They are also easier to collect in existing public transportation systems.

Traffic Report Data. This type of data is often used for abnormal cases, e.g., anomaly report data used in Liu et al. [2020c] and traffic accident report data used in Zhou et al. [2020e], Zhang et al. [2020k], Zhou et al. [2020f]. Traffic report data are less used in graph-based modeling because of their sparsity in both spatial and temporal dimensions, compared with trip record data.

Multimedia Data. This type of data can be used as an additional input to deep learning models or for verifying the traffic status indicated by other data sources. Multimedia data used in the surveyed studies include the Baidu street-view images used in Qin et al. [2020a] for traffic congestion, as well as satellite imagery data [Zhang et al., 2020k], and video surveillance data [Shao et al., 2020]. Multimedia data are also less seen in graph-based modeling because of their higher requirement for data collection, transmission and storage, compared with traffic sensor data with similar functionalities. It is also more difficult to extract precise traffic information, e.g., vehicle counts, from images or videos through image processing and object detection techniques.

Simulated Traffic Data. In addition to observed real-world datasets, microscopic traffic simulators are also used to build virtual training and testing datasets for deep learning models. Examples in the surveyed studies include the MATES Simulator used in Fukuda et al. [2020] and INTEGRATION software used in Ramadan et al. [2020]. With many real-world datasets available, simulated traffic data are rarely used in GNN-based and more broader ML-based traffic forecasting studies. Traffic simulations have the potential of modeling unseen graphs though, e.g., evaluating a planned road topology.

Weather Data. Traffic states are highly affected by the meteorological factors including temperature, humidity, precipitation, barometer pressure, and wind strength.

Calendar Data. This includes the information on weekends and holidays. Because traffic patterns vary significantly between weekdays and weekends/holidays, some studies consider these two cases separately. Both weather and calendar data have been proven useful for traffic forecasting in the literature and should not be neglected in graph-based modeling as external factors.

While present road network and weather data can be easily found on the Internet, it is much more difficult to source historical traffic data, both due to data privacy concerns and the transmission and storage requirements of large data volumes. In Table 6 we present a list of the open data resources used in the surveyed studies. Most of these open data are already cleaned or preprocessed and can be readily used for benchmarking and comparing the performance of different models in future work.

Table 6: Open data for traffic prediction problems.
Dataset Name Relevant Studies
METR-LA  Li et al. [2018b], Wu et al. [2019], Xu et al. [2020a], Pan et al. [2020, 2019], Lu et al. [2019a], Zhang et al. [2020e], Wang et al. [2020g], Zhang & Guo [2020], Boukerche & Wang [2020b], Cao et al. [2020], Yu et al. [2019b], Li & Zhu [2021], Tian et al. [2020], Chen et al. [2020d], Bai et al. [2021], Zhang et al. [2018a], Cirstea et al. [2019], Shleifer et al. [2019], Yang et al. [2020], Chen et al. [2019], Wang et al. [2020f], Cui et al. [2020b], Zhou et al. [2020a], Cai et al. [2020], Zhou et al. [2020b], Wu et al. [2020c], Chen et al. [2020f], Opolka et al. [2019], Oreshkin et al. [2021], Jia et al. [2020], Zhang et al. [2020i], Feng et al. [2020], Xie et al. [2020c], Park et al. [2020], Song et al. [2020b]
PeMS all  Mallick et al. [2020, 2021]
PeMS-BAY  Li et al. [2018b], Wu et al. [2019], Zheng et al. [2020b], Pan et al. [2020, 2019], Xu et al. [2020b], Wang et al. [2020g], Zhang & Guo [2020], Boukerche & Wang [2020b], Li et al. [2020f], Cao et al. [2020], Xie et al. [2020d], Li & Zhu [2021], Tian et al. [2020], Shleifer et al. [2019], Chen et al. [2019], Yu et al. [2019a], Wang et al. [2020f], Cui et al. [2020b], Zhou et al. [2020a], Cai et al. [2020], Zhou et al. [2020b], Wu et al. [2020c], Chen et al. [2020f], Oreshkin et al. [2021], Guo & Yuan [2020], Zhang et al. [2020i], Feng et al. [2020], Xie et al. [2020c], Park et al. [2020], Song et al. [2020b]
PeMSD3  Song et al. [2020a], Cao et al. [2020], Chen et al. [2020g], Wang et al. [2020a], Li & Zhu [2021]
PeMSD4  Bai et al. [2020], Huang et al. [2020a], Zhang et al. [2020e], Song et al. [2020a], Chen et al. [2020e], Tang et al. [2020b], Guo et al. [2019c], Li et al. [2019b], Wei & Sheng [2020], Cao et al. [2020], Li et al. [2020b], Yin et al. [2020], Zhang et al. [2020a], Wang et al. [2020a], Xin et al. [2020], Huang et al. [2020b], Guo et al. [2020b], Li & Zhu [2021], Xu et al. [2020c], Chen et al. [2020c], Ge et al. [2019a, b, 2020], Zhao et al. [2020b]
PeMSD7  Zhang et al. [2020j], Huang et al. [2020a], Song et al. [2020a], Xu et al. [2020b], Tang et al. [2020b], Sun et al. [2020], Cao et al. [2020], Yu et al. [2018, 2019b], Chen et al. [2020g], Wang et al. [2020a], Xin et al. [2020], Xie et al. [2020d], Li & Zhu [2021], Zhang et al. [2019a], Ge et al. [2019a, b, 2020], Yu et al. [2019a], Zhao et al. [2020b]
PeMSD8  Bai et al. [2020], Huang et al. [2020a], Song et al. [2020a], Chen et al. [2020e], Guo et al. [2019c], Wei & Sheng [2020], Cao et al. [2020], Li et al. [2020b], Yin et al. [2020], Zhang et al. [2020a], Wang et al. [2020a], Guo et al. [2020b], Li & Zhu [2021]
Seattle Loop  Cui et al. [2019, 2020a], Sun et al. [2021], Lewenfus et al. [2020]
T-Drive  Pan et al. [2020, 2019]
SHSpeed  Zhang et al. [2020j], Wang et al. [2018b], Guo et al. [2019a]
TaxiBJ  Zhang et al. [2020h], Wang et al. [2018a], Bai et al. [2019b]
TaxiSZ  Bai et al. [2021], Zhao et al. [2019]
TaxiCD  Hu et al. [2018, 2020]
TaxiNYC  Zhang et al. [2020h], Sun et al. [2020], Zhou et al. [2019], Hu et al. [2018], Jin et al. [2020b], Li & Axhausen [2020], Zheng et al. [2020a], Xu & Li [2019], Davis et al. [2020], Du et al. [2020], Li & Moura [2020], Ye et al. [2021], Zhou et al. [2020f]
UberNYC  Jin et al. [2020b], Ke et al. [2021a]
DiDiChengdu  Zhang et al. [2019d], Qu et al. [2020], Wang et al. [2020b], Zhou et al. [2019], Wang et al. [2020h], Bogaerts et al. [2020], Li et al. [2020c]
DiDiTTIChengdu  Lu et al. [2020a]
DiDiXi’an  Qu et al. [2020], Bogaerts et al. [2020]
DiDiHaikou  Pian & Wu [2020], Jin et al. [2020a]
BikeDC  Sun et al. [2020], Wang et al. [2020d]
BikeNYC  Zhang et al. [2020h], Sun et al. [2020], Wang et al. [2018a], He & Shin [2020b], Chai et al. [2018], Lee et al. [2019], Bai et al. [2019b], Du et al. [2020], Ye et al. [2021], Wang et al. [2020d], Guo et al. [2019b], Lin et al. [2018]
BikeChicago  Chai et al. [2018]
SHMetro  Liu et al. [2020b]
HZMetro  Liu et al. [2020b]

5.1.1 Traffic Sensor Data

The relevant open traffic sensor data are listed as follows.

METR-LA 222Download link: https://github.com/liyaguang/DCRNN: This dataset contains traffic speed and volume collected from the highway of the Los Angeles County road network, with 207 loop detectors. The samples are aggregated in 5-minute intervals. The most frequently referenced time period for this dataset is from March 1st to June 30th, 2012.

Performance Measurement System (PeMS) Data 333http://pems.dot.ca.gov/: This dataset contains raw detector data from over 18,000 vehicle detector stations on the freeway system spanning all major metropolitan areas of California from 2001 to 2019, collected with various sensors including inductive loops, side-fire radar, and magnetometers. The samples are captured every 30 seconds and aggregated in 5-minute intervals. Each data sample contains a timestamp, station ID, district, freeway ID, direction of travel, total flow, and average speed. Different subsets of PeMS data have been used in previous studies, for example:

  • 1.

    PeMS-BAY 444Download link: https://github.com/liyaguang/DCRNN: This subset contains data from 325 sensors in the Bay Area from January 1st to June 30th, 2017.

  • 2.

    PeMSD3: This subset uses 358 sensors in the North Central Area. The frequently referenced time period for this dataset is September 1st to November 30th, 2018.

  • 3.

    PeMSD4: This subset uses 307 sensors in the San Francisco Bay Area. The frequently referenced time period for this dataset is January 1st to February 28th, 2018.

  • 4.

    PeMSD7: This subset uses 883 sensors in the Los Angeles Area. The frequently referenced time period for this dataset is May to June, 2012.

  • 5.

    PeMSD8: This subset uses 170 sensors in the San Bernardino Area. The frequently referenced time period for this dataset is July to August, 2016.

Seattle Loop 555Download link: https://github.com/zhiyongc/Seattle-Loop-Data: This dataset was collected by inductive loop detectors deployed on four connected freeways (I-5, I-405, I-90, and SR-520) in the Seattle area, from January 1st to 31st, 2015. It contains the traffic speed data from 323 detectors. The samples are aggregated in 5-minute intervals.

5.1.2 Taxi Data

The open taxi datasets used in the surveyed studies are listed as follows.

T-drive [Yuan et al., 2010]: This dataset contains a large number of taxicab trajectories collected by 30,000 taxis in Beijing from February 1st to June 2nd, 2015.

SHSpeed (Shanghai Traffic Speed) [Wang et al., 2018b] 666Download link: https://github.com/xxArbiter/grnn: This dataset contains 10-minute traffic speed data, derived from raw taxi trajectory data, collected from 1 to 30 April 2015, for 156 urban road segments in the central area of Shanghai, China.

TaxiBJ [Zhang et al., 2017]: This dataset contains inflow and outflow data derived from GPS data in more than 34,000 taxicabs in Beijing from four time intervals: (1) July 1st to October 30th, 2013; (2) March 1st to June 30th, 2014; (3) March 1st to June 30th, 2015; and (4) November 1st, 2015 to April 10th, 2016. The Beijing city map is divided into 32×32323232\times 32 grids and the time interval of the flow data is 30 minutes.

TaxiSZ [Zhao et al., 2019] 777Download link: https://github.com/lehaifeng/T-GCN: This dataset is derived from taxi trajectories in Shenzhen from January 1st to 31st, 2015. It contains the traffic speed on 156 major roads of the Luohu District every 15 minutes.

TaxiCD 888 https://js.dclab.run/v2/cmptDetail.html?id=175: This dataset contains 1.4 billion GPS records from 14,864 taxis collected from August 3rd to 30th, 2014 in Chengdu, China. Each GPS record consists of a taxi ID, latitude, longitude, an indicator of whether the taxi is occupied, and a timestamp.

TaxiNYC999http://www.nyc.gov/html/tlc/html/about/trip_record_data.shtml: The taxi trip records in New York starting from 2009, in both yellow and green taxis. Each trip record contains pick-up and drop-off dates/times, pick-up and drop-off locations, trip distances, itemized fares, rate types, payment types, and driver-reported passenger counts.

5.1.3 Ride-hailing Data

The open ride-hailing data used in the surveyed studies are listed as follows.

UberNYC 101010https://github.com/fivethirtyeight/uber-tlc-foil-response: This dataset comes from Uber, which is one of the largest online ride-hailing companies in the USA, and is provided by the NYC Taxi & Limousine Commission (TLC). It contains data from over 4.5 million Uber pickups in New York City from April to September 2014, and 14.3 million more Uber pickups from January to June 2015.

Didi GAIA Open Data 111111https://outreach.didichuxing.com/research/opendata/: This open data plan is supported by Didi Chuxing, which is one of the largest online ride-hailing companies in China.

  • 1.

    DiDiChengdu: This dataset contains the trajectories of DiDi Express and DiDi Premier drivers within Chengdu, China. The data contains trips from October to November 2016.

  • 2.

    DiDiTTIChengdu: This dataset represents the DiDi Travel Time Index Data in Chengdu, China in the year of 2018, which contains the average speed of major roads every 10 minutes.

  • 3.

    DiDiXi’an: This dataset contains the trajectories of DiDi Express and DiDi Premier drivers within Xi’an, China. The data contains trips from October to November 2016.

  • 4.

    DiDiHaikou: The dataset contains DiDi Express and DiDi Premier orders from May 1st to October 31st, 2017 in the city of Haikou, China, including the coordinates of origins and destinations, pickup and drop-off timestamps, as well as other information.

5.1.4 Bike Data

The open bike data used in the surveyed studies are listed as follows.

BikeNYC 121212 https://www.citibikenyc.com/system-data: This dataset is from the NYC Bike System, which contains 416 stations. The frequently referenced time period for this dataset is from 1st July, 2013 to 31th December, 2016.

BikeDC 131313 https://www.capitalbikeshare.com/system-data: This dataset is from the Washington D.C. Bike System, which contains 472 stations. Each record contains trip duration, start and end station IDs, and start and end times.

BikeChicago 141414https://www.divvybikes.com/system-data: This dataset is from the Divvy System Data in Chicago, from 2015 to 2020.

5.1.5 Subway Data

The subway data referenced in the surveyed studies are listed as follows.

SHMetro [Liu et al., 2020b] 151515Download link: https://github.com/ivechan/PVCGN: This dataset is derived from 811.8 million transaction records of the Shanghai metro system collected from July 1st to September 30th, 2016. It contains 288 metro stations and 958 physical edges. The inflow and outflow of each station are provided in 15 minute intervals.

HZMetro [Liu et al., 2020b] 161616Download link: https://github.com/ivechan/PVCGN: This dataset is similar to SHMetro, from the metro system in Hangzhou, China, in January 2019. It contains 80 metro stations and 248 physical edges, and the aggregation time length is also 15 minutes.

5.2 Open Source Codes

Several open source frameworks for implementing general deep learning models, most of which are built with the Python programming language, can be accessed online, e.g. TensorFlow 171717https://www.tensorflow.org/, Keras 181818https://keras.io/, PyTorch 191919https://pytorch.org/, and MXNet 202020https://mxnet.apache.org/. Additional Python libraries designed for implementing GNNs are available. These include DGL 212121https://www.dgl.ai/, pytorch_geometric 222222https://pytorch-geometric.readthedocs.io/, and Graph Nets 232323https://github.com/deepmind/graph_nets.

Many authors have also released open-source implementations of their proposed models. The open source projects for traffic flow, traffic speed, traffic demand, and other problems are summarized in Tables 7,  8,  9, and 10, respectively. In these open source projects, TensorFlow and PyTorch are the two frameworks that are used most frequently.

Table 7: Open source projects for traffic flow related problems.
Article Year Framework Problem Link
Zheng et al. [2020b] 2020 TensorFlow Road Traffic Flow, Road Traffic Speed https://github.com/zhengchuanpan/GMAN
Bai et al. [2020] 2020 PyTorch Road Traffic Flow https://github.com/LeiBAI/AGCRN
Song et al. [2020a] 2020 MXNet Road Traffic Flow https://github.com/wanhuaiyu/STSGCN
Tang et al. [2020b] 2020 TensorFlow Road Traffic Flow https://github.com/sam101340/GAGCN-BC-20200720
Wang et al. [2020a] 2020 MXNet, PyTorch Road Traffic Flow https://github.com/zkx741481546/Auto-STGCN
Guo et al. [2020b] 2020 PyTorch Road Traffic Flow, Road Traffic Speed https://github.com/guokan987/DGCN
Li & Zhu [2021] 2020 MXNet Road Traffic Flow, Road Traffic Speed https://github.com/MengzhangLI/STFGNN
Tian et al. [2020] 2020 PyTorch, DGL Road Traffic Flow https://github.com/Kelang-Tian/ST-MGAT
Xiong et al. [2020] 2020 TensorFlow Road OD Flow https://github.com/alzmxx/OD_Prediction
Peng et al. [2020] 2020 Keras Road Station-level Subway Passenger Flow, Station-level Bus Passenger Flow, Regional Taxi Flow https://github.com/RingBDStack/GCNN-In-Traffic
Qiu et al. [2020] 2020 Pytorch Regional Taxi Flow https://github.com/Stanislas0/ToGCN-V2X
Yeghikyan et al. [2020] 2020 PyTorch Regional OD Taxi Flow https://github.com/FelixOpolka/Mobility-Flows-Neural-Networks
Zhang et al. [2020b] 2020 Keras Station-level Subway Passenger Flow https://github.com/JinleiZhangBJTU/ResNet-LSTM-GCN
Zhang et al. [2020c] 2020 Keras Station-level Subway Passenger Flow https://github.com/JinleiZhangBJTU/Conv-GCN
Liu et al. [2020b] 2020 PyTorch Station-level Subway Passenger Flow https://github.com/ivechan/PVCGN
Ye et al. [2020b] 2020 Keras Station-level Subway Passenger Flow https://github.com/start2020/Multi-STGCnet
Pan et al. [2019] 2019 MXNet, DGL Road Traffic Flow, Road Traffic Speed https://github.com/panzheyi/ST-MetaNet
Guo et al. [2019c] 2019 MXNet Road Traffic Flow https://github.com/wanhuaiyu/ASTGCN
Guo et al. [2019c] 2019 PyTorch Road Traffic Flow https://github.com/wanhuaiyu/ASTGCN-r-pytorch
Wang et al. [2018b] 2018 PyTorch Road Traffic Flow https://github.com/xxArbiter/grnn
Yu et al. [2018] 2018 TensorFlow Road Traffic Flow https://github.com/VeritasYin/STGCN_IJCAI-18
Li et al. [2018a] 2018 Keras Station-level Subway Passenger Flow https://github.com/RingBDStack/GCNN-In-Traffic
Chai et al. [2018] 2018 TensorFlow Bike Flow https://github.com/Di-Chai/GraphCNN-Bike
Table 8: Open source projects for traffic speed related problems.
Article Year Framework Problem Link
 Zhang et al. [2020h] 2020 Keras Road Traffic Speed https://github.com/jillbetty001/ST-CGA
 Bai et al. [2021] 2020 TensorFlow Road Traffic Speed https://github.com/lehaifeng/T-GCN/tree/master/A3T
 Yang et al. [2020] 2020 TensorFlow Road Traffic Speed https://github.com/fanyang01/relational-ssm
 Wu et al. [2020c] 2020 PyTorch Road Traffic Speed https://github.com/nnzhan/MTGNN
 Mallick et al. [2021] 2020 TensorFlow Road Traffic Speed https://github.com/tanwimallick/TL-DCRNN
 Chen et al. [2020a] 2020 PyTorch Road Traffic Speed https://github.com/Fanglanc/DKFN
 Lu et al. [2020a] 2020 PyTorch Road Traffic Speed https://github.com/RobinLu1209/STAG-GCN
 Guopeng et al. [2020] 2020 TensorFlow, Keras Road Traffic Speed https://github.com/RomainLITUD/DGCN_traffic_forecasting
 Shen et al. [2020] 2020 PyTorch Road Travel Time https://github.com/YibinShen/TTPNet
 Hong et al. [2020] 2020 TensorFlow Time of Arrival https://github.com/didi/heteta
 Wu et al. [2019] 2019 PyTorch Road Traffic Speed https://github.com/nnzhan/Graph-WaveNet
 Shleifer et al. [2019] 2019 PyTorch Road Traffic Speed https://github.com/sshleifer/Graph-WaveNet
 Zhao et al. [2019] 2019 TensorFlow Road Traffic Speed https://github.com/lehaifeng/T-GCN
 Cui et al. [2019] 2019 TensorFlow Road Traffic Speed https://github.com/zhiyongc/Graph_Convolutional_LSTM
 Jepsen et al. [2019, 2020] 2019 MXNet Road Traffic Speed https://github.com/TobiasSkovgaardJepsen/relational-fusion-networks
 Li et al. [2018b] 2018 TensorFlow Road Traffic Speed https://github.com/liyaguang/DCRNN
 Li et al. [2018b] 2018 PyTorch Road Traffic Speed https://github.com/chnsh/DCRNN_PyTorch
 Zhang et al. [2018a] 2018 MXNet Road Traffic Speed https://github.com/jennyzhang0215/GaAN
 Liao et al. [2018] 2018 TensorFlow Road Traffic Speed https://github.com/JingqingZ/BaiduTraffic
 Mohanty & Pozdnukhov [2018], Mohanty et al. [2020] 2018 TensorFlow Traffic Congestion https://github.com/sudatta0993/Dynamic-Congestion-Prediction
Table 9: Open source projects for traffic demand related problems.
Article Year Framework Problem Link
Hu et al. [2020] 2020 TensorFlow Taxi Demand https://github.com/hujilin1229/od-pred
Davis et al. [2020] 2020 TensorFlow, PyTorch Taxi Demand https://github.com/NDavisK/Grids-versus-Graphs
Ye et al. [2021] 2020 PyTorch Taxi Demand, Bike Demand https://github.com/Essaim/CGCDemandPrediction
Lee et al. [2019] 2019 TensorFlow, Keras Ride-hailing Demand, Bike Demand, Taxi Demand https://github.com/LeeDoYup/TGGNet-keras
Ke et al. [2021b] 2019 Keras Taxi Demand https://github.com/kejintao/ST-ED-RMGC
Table 10: Open source projects for other problems.
Article Year Framework Problem Link
Zhou et al. [2020e] 2020 TensorFlow Traffic Accident https://github.com/zzyy0929/AAAI2020-RiskOracle/
Yu et al. [2020b] 2020 PyTorch, DGL Traffic Accident https://github.com/yule-BUAA/DSTGCN
Zhang et al. [2020f] 2020 PyTorch, DGL Parking Availability https://github.com/Vvrep/SHARE-parking_availability_prediction-Pytorch
Wang et al. [2020c] 2020 TensorFlow Transportation Resilience https://github.com/Charles117/resilience_shenzhen
Wright et al. [2019] 2019 TensorFlow, Keras Lane Occupancy https://github.com/mawright/trafficgraphnn

5.3 State-of-the-art Performance

It is known that different works use different datasets and it is very hard to assess the relative performance of different state-of-the-art models [Tedjopurnomo et al., 2020]. Even for those studies using the same dataset, different subsets may be used. Different preprocessing techniques, e.g., the missing data imputation method, and different evaluation settings, e.g., the training/validation/test subset split ratio, also cause incomparable results. Considering these difficulties, we only summarize those comparable results for the most frequently used datasets from the surveyed studies in this part.

Some commonly used evaluation metrics, namely, RMSE, MAE and MAPE, are defined as follows:

  • 1.

    RMSE(𝐲,𝐲^)=1Mi=1M(yiy^i)2RMSE𝐲^𝐲1𝑀superscriptsubscript𝑖1𝑀superscriptsubscript𝑦𝑖subscript^𝑦𝑖2\text{RMSE}(\mathbf{y},\mathbf{\hat{y}})=\sqrt{\frac{1}{M}\sum_{i=1}^{M}{(y_{i}-\hat{y}_{i})^{2}}};

  • 2.

    MAE(𝐲,𝐲^)=1Mi=1M|yiy^i|MAE𝐲^𝐲1𝑀superscriptsubscript𝑖1𝑀subscript𝑦𝑖subscript^𝑦𝑖\text{MAE}(\mathbf{y},\mathbf{\hat{y}})=\frac{1}{M}\sum_{i=1}^{M}|y_{i}-\hat{y}_{i}|;

  • 3.

    MAPE(𝐲,𝐲^)=1Mi=1M|yiy^i|yiMAPE𝐲^𝐲1𝑀superscriptsubscript𝑖1𝑀subscript𝑦𝑖subscript^𝑦𝑖subscript𝑦𝑖\text{MAPE}(\mathbf{y},\mathbf{\hat{y}})=\frac{1}{M}\sum_{i=1}^{M}\frac{|y_{i}-\hat{y}_{i}|}{y_{i}};

where 𝐲𝐲\mathbf{y} denotes the true values, 𝐲^^𝐲\mathbf{\hat{y}} denotes the predicted values, and M𝑀M is the number of values to predict. A lower RMSE or MAE value indicates a better prediction performance. The summary for the state-of-the-art performance is shown in Table 11, with all or some of the above evaluation metrics and best values in bold. The default prediction time period is 60 minutes in Table 11 unless otherwise specified. Some classical baselines are also listed for comparison if available, e.g., DCRNN [Li et al., 2018b], STGCN [Yu et al., 2018] and Graph WaveNet [Wu et al., 2019]. Interested readers are recommended to check the experimental details in relevant studies.

Table 11: State-of-the-art performance for traffic prediction problems.
Dataset RMSE MAE MAPE Relevant Studies
METR-LA 7.59 3.60 10.5% DCRNN
7.40 3.55 10.0% ST-UNet [Yu et al., 2019b]
7.37 3.53 10.0% Graph WaveNet
7.20 3.30 9.7% SLCNN [Zhang et al., 2020e]
6.68 3.28 9.08% Traffic Transformer [Cai et al., 2020]
6.40 3.18 8.81% STFGNN [Li & Zhu, 2021]
PeMS-BAY 4.74 2.07 4.9% DCRNN
4.53 2.03 4.8% SLCNN [Zhang et al., 2020e]
4.52 1.95 4.63% Graph WaveNet
4.32 1.86 4.31% GMAN [Zheng et al., 2020b]
4.36 1.77 4.29% Traffic Transformer [Cai et al., 2020]
3.74 1.66 3.77% STFGNN [Li & Zhu, 2021]
PeMSD3 30.31 18.18 18.91% DCRNN
30.12 17.49 17.15% STGCN
32.94 17.48 16.78% Graph WaveNet
28.34 16.77 16.30% STFGNN [Li & Zhu, 2021]
PeMSD4 39.70 25.45 17.29% Graph WaveNet
34.89 21.16 13.83% STGCN
33.44 21.22 14.17% DCRNN
32.26 19.83 12.97% AGCRN [Bai et al., 2020]
31.88 19.83 13.02% STFGNN [Li & Zhu, 2021]
PeMSD7 42.78 26.85 12.12% Graph WaveNet
38.78 25.38 11.08% STGCN
38.58 25.30 11.66% DCRNN
35.80 22.07 9.21% STFGNN [Li & Zhu, 2021]
PeMSD8 31.05 19.13 12.68% Graph WaveNet
27.09 17.50 11.29% STGCN
26.36 16.82 10.92% DCRNN
26.22 16.64 10.60% STFGNN [Li & Zhu, 2021]
25.22 15.95 10.09% AGCRN [Bai et al., 2020]
Seattle Loop 8.22 4.64 11.18% DCRNN
3.59 2.45 5.90% GLT-GCRNN [Sun et al., 2021]
TaxiSZ 4.76 3.38 N/A Graph WaveNet
4.64 3.31 N/A DCRNN
4.13 2.79 N/A T-GCN [Zhao et al., 2019]
4.13 2.76 N/A STGCN
4.10 2.77 N/A AST-GCN [Zhu et al., 2021]
3.97 2.74 N/A A3T-GCN [Bai et al., 2021]
TaxiNYC (30 min) 22.65 18.46 N/A STGCN
14.79 8.43 N/A DCRNN
13.07 8.10 N/A Graph WaveNet
9.56 5.50 N/A CCRNN [Ye et al., 2021]
BikeNYC (30 min) 3.60 2.76 N/A STGCN
3.29 1.99 N/A Graph WaveNet
3.21 1.90 N/A DCRNN
2.84 1.74 N/A CCRNN [Ye et al., 2021]

Since the relevant studies of applying GNNs for traffic forecasting are growing everyday, the results listed in this part are not guaranteed to be the latest ones and the readers are recommended to follow our Github repository to track latest results.

6 Challenges and Future Directions

In this section, we discuss general challenges for traffic prediction problems as well as specific new challenges when GNNs are involved. While GNNs achieve a better forecasting performance, they are not the panacea. Some existing challenges from the border topic of traffic forecasting remain unsolved in current graph-based studies. Based on these challenges, we discuss possible future directions as well as early attempts in these directions. Some of these future directions are inspired from the border traffic forecasting research and remain insightful for the graph-based modeling approach. We would also highlight the special opportunities with GNNs.

6.1 Challenges

6.1.1 Heterogeneous Data

Traffic prediction problems involve both spatiotemporal data and external factors, e.g., weather and calendar information. Heterogeneous data fusion is a challenge that is not limited to the traffic domain. GNNs have enabled significant progress by taking the underlying graph structures into consideration. However, some challenges remain; for example, geographically close nodes may not be the most influential, both for CNN-based and GNN-based approaches. Another special challenge for GNNs is that the underlying graph information may not be correct or up to date. For example, the road topology data of OpenStreetMap, an online map services, are collected in a crowd-sourced approach, which may be inaccurate or lagged behind the real road network. The spatial dependency relationship extracted by GNNs with these inaccurate data may decrease the forecasting accuracy.

Data quality concerns present an additional challenge with problems such as missing data, sparse data and noise potentially compromising forecasting results. Most of the surveyed models are only evaluated with processed high-quality datasets. A few studies do, however, take data quality related problems into consideration, e.g., using the Kalman filter to deal with the sensor data bias and noise [Chen et al., 2020a], infilling missing data with moving average filters [Hasanzadeh et al., 2019] or linear interpolation [Agafonov, 2020, Chen et al., 2020a]. Missing data problem could be more common in GNNs, with the potential missing phenomena happening with historical traffic data or underlying graph information, e.g., GCNs are proposed to fill data gaps in missing OD flow problems [Yao et al., 2020].

Traffic anomalies (e.g., congestion) are an important external factor that may affect prediction accuracy and it has been proven that under congested traffic conditions a deep neural network may not perform as well as under normal traffic conditions [Mena-Oreja & Gozalvez, 2020]. However, it remains a challenge to collect enough anomaly data to train deep learning models (including GNNs) in both normal and anomalous situations. The same concern applies for social events, public holidays, etc.

Challenges also exist for data privacy in the transportation domain. As discussed in Section 5.1, many open data are collected from individual mobile devices in a crowd sourcing approach. The data administrator must guarantee the privacy of individuals who contribute their personal traffic data, as the basis for encouraging a further contribution. Different techniques may be used, e.g., privacy-preserving data publishing techniques and privacy-aware data structures without personal identities.

6.1.2 Multi-task Performance

For the public service operation of ITSs, a multi-task framework is necessary to incorporate all the traffic information and predict the demand of multiple transportation modes simultaneously. For example, knowledge adaption is proposed to adapt the relevant knowledge from an information-intensive source to information-sparse sources for demand prediction [Li et al., 2020a]. Related challenges lie in data format incompatibilities as well as the inherent differences in spatial or temporal patterns. While some of the surveyed models can be used for multiple tasks, e.g., traffic flow and traffic speed prediction on the same road segment, most can only be trained for a single task at one time.

Multi-task forecasting is a bigger challenge in graph-based modeling because different tasks may use different graph structures, e.g., road-level and station-level problems use different graphs and thus are difficult to be solved with a single GNN model. Some efforts that have been made in GNN-based models for multi-task prediction include taxi departure flow and arrival flow [Chen et al., 2020h], region-flow and transition-flow [Wang et al., 2020b], crowd flows, and OD of the flows [Wang et al., 2020e]. However, most of the existing attempts are based on the same graph with multiple outputs generated by feed forward layers. Nonetheless, GNN-based multi-task prediction for different types of traffic forecasting problems is a research direction requiring significant further development, especially those requiring multiple graph structures.

6.1.3 Practical Implementation

A number of challenges prevent the practical implementation of the models developed in the surveyed studies in city-scale ITSs.

First, there is significant bias introduced by the small amount of data considered in the existing GNN-based studies which, in most cases, spans less than one year. The proposed solutions are therefore not necessarily applicable to different time periods or different places. If longer traffic data are to be used in GNNs, the corresponding change of the underlying traffic infrastructures should be recorded and updated, which increases both the expense and difficulty of the associated data collection process in practice.

A second challenge is the computation scalability of GNNs. To avoid the huge computation requirements of the large-scale real-world traffic network graphs, only a subset of the nodes and edges are typically considered. For example, most studies only use a subset of the PeMS dataset when considering the road traffic flow or speed problems. Their results can therefore only be applied to the selected subsets. Graph partitioning and parallel computing infrastructures have been proposed for solving this problem. The traffic speed and flow of the entire PeMS dataset with 11,160 traffic sensor locations are predicted simultaneously in Mallick et al. [2020], using a graph-partitioning method that decomposes a large highway network into smaller networks and trains a single DCRNN model on a cluster with graphics processing units (GPUs). However, increased modeling power can only improve the state-of-the-art results with narrow performance margins, compared to statistical and machine learning models with less complex structures and computational requirements.

A third challenge is presented by changes in the transportation networks and infrastructure, which are essential to build the graphs in GNNs. The real-world network graphs change when road segments or bus lines are added or removed. Points-of-interest in a city also change when new facilities are built. Static graph formulations are not enough for handling these situations. Some efforts have been made to solve this problem with promising results. For example, a dynamic Laplacian matrix estimator is proposed to find the change of Laplacian matrix, according to changes in spatial dependencies hidden in the traffic data [Diao et al., 2019], and a Data Adaptive Graph Generation (DAGG) module is proposed to infer the inter-dependencies between different traffic series automatically, without using pre-defined graphs based on spatial connections [Bai et al., 2020].

6.1.4 Model Interpretation

The challenge of model interpretation is a point of criticism for all “black-box” machine learning or deep learning models, and traffic forecasting tasks are no exception [Wu et al., 2018b, Barredo-Arrieta et al., 2019]. While there have been remarkable progresses for visualizing and explaining other deep neural network structures, e.g., CNNs, the development of post-processing techniques to explain the predictions made by GNNs is still in an early phase [Baldassarre & Azizpour, 2019, Pope et al., 2019, Ying et al., 2019] and the application of these techniques to the traffic forecasting domain has not yet been addressed.

Compared with other similar forecasting problems in other domains, lack of model interpretation may be a more severe problem in the transportation domain, when complex data types and representations of heterogeneous traffic data make it more challenging to design an interpretable deep learning model, compared with other data formats, e.g., images and text. While some efforts have been made to incorporate the state space model to increase the model interpretation for traffic forecasting [Li et al., 2019a], this problem has not fully solved, especially for GNN-based models.

6.2 Future Directions

6.2.1 Centralized Data Repository

A centralized data repository for GNN-based traffic forecasting resources would facilitate objective comparison of the performance of different models and be an invaluable contribution to the field. This future direction is proposed for the challenge of heterogeneous data as well as the data quality problem. Another unique feature of this repository could be the inclusion of graph-related data, which have not be provided directly in previous traffic forecasting studies.

Some criteria for building such data repositories, e.g. a unified data format, tracking of dataset versions, public code and ranked results, and sufficient record lengths (longer than a year ideally), have been discussed in previous surveys [Manibardo et al., 2021]. Compiling a centralized and standardized data repository is particularly challenging for GNN-based models where natural graphs are collected and stored in a variety of data formats (e.g. Esri Shapefile and OSM XML used by Openstreetmap are used for digital maps in the GIS community) and various different similarity graphs can be constructed from the same traffic data in different models.

Some previous attempts in this direction have been made in the machine learning community, e.g. setting benchmarks for several traffic prediction tasks in Papers With Code 242424https://paperswithcode.com/task/traffic-prediction, and in data science competitions, e.g., the Traffic4cast competition series 252525https://www.iarai.ac.at/traffic4cast/. However, the realization of a centralized data repository remains an open challenge.

A centralized data repository is also the basis for benchmarking traffic prediction, which is previously discussed in Section 5.3. With more and more GNN-based models being proposed, it becomes even more difficult to compare different models and validate the effectiveness of new traffic forecasting methods without a considerable effort, when a standardized benchmark dataset and consistent experimental settings have not been established yet. The most close one is the PeMS dataset, but it covers the road-level case only and more efforts are still needed, especially for the remaining cases.

6.2.2 Traffic Graph Design

While various graphs have been constructed in the surveyed studies as discussed in Section 4.1 and have been proven successful to some extent, most of them are natural graphs based on a real-world transportation system, e.g. the road network or subway system, as the current development status. And most of the graphs used are static, instead of dynamic ones. One specific direction that is not fully considered before is the design of transportation knowledge graph. As an important tool for knowledge integration, knowledge graph is a complex relational network that consists of concepts, entities, entity relations and attributes [Yin et al., 2021]. The transportation knowledge graph helps to leverage the traffic semantic information to improve the forecasting performance. And the challenge is to extract the hidden transportation domain knowledge from multi-source and heterogeneous traffic data.

6.2.3 Combination with Other Techniques

GNNs may be combined with other advanced techniques to overcome some of their inherent challenges and achieve better performance.

Data Augmentation. Data augmentation has been proven effective for boosting the performance of deep learning models, e.g. in image classification tasks and time series prediction tasks. Data augmentation is proposed for the challenge of the possible forecasting bias introduced by the small amount of available data. However, due to the complex structure of graphs, it is more challenging to apply data augmentation techniques to GNNs. Recently, data augmentation for GNNs has proven helpful in semi-supervised node classification tasks [Zhao et al., 2021]. However, it remains a question whether data augmentation may be effective in traffic forecasting GNN applications.

Transfer Learning. Transfer learning utilizes knowledge or models trained for one task to solve related tasks, especially those with limited data. In the image classification field, pre-trained deep learning models from the ImageNet or MS COCO datasets are widely used in other problems. In traffic prediction problems, where a lack of historical data is a frequent problem, transfer learning is a possible solution. For GNNs, transfer learning can be used from a graph with more historical traffic data for the model training process to another graph with less available data. Transfer learning can also be used for the challenge caused by the changes in the transportation networks and infrastructure, when new stations or regions have not accumulated enough historical traffic data to train a GNN model. A novel transfer learning approach for DCRNN is proposed in Mallick et al. [2021], so that a model trained on data-rich regions of highway network can be used to predict traffic on unseen regions of the highway network. The authors demonstrated the efficacy of model transferability between the San Francisco and Los Angeles regions using different parts of the California road network from the PeMS.

Meta-learning. Meta-learning, or learning how to learn, has recently become a potential learning paradigm that can absorb information from a task and effectively generalize it to an unseen task. Meta-learning is proposed for the challenge of GNN-based multi-task prediction, especially those involving mutiple graphs. There are different types of meta learning methods and some of them are combined with graph structures for describing relationships between tasks or data samples [Satorras & Estrach, 2018, Liu et al., 2019]. Based on a deep meta learning method called network weight generation, ST-MetaNet+ is proposed in Pan et al. [2020], which leverages the meta knowledge extracted from geo-graph attributes and dynamic traffic context learned from traffic states to generate the parameter weights in graph attention networks and RNNs, so that the inherent relationships between diverse types of spatiotemporal correlations and geo-graph attributes can be captured.

Generative Adversarial Network (GAN) [Goodfellow et al., 2014]. GAN is a machine learning framework that has two components, namely, a generator, which learns to generate plausible data, and a discriminator, which learns to distinguish the generator’s fake data from real data. After training to a state of Nash equilibrium, the generator may generate undistinguished data, which helps to expand the training data size for many problems, including GNN-based traffic forecasting. GAN is proposed for the challenges caused by the small data amount used in previous studies or the changes in the transportation networks and infrastructure when not enough historical traffic data are available. In Xu et al. [2020a], the road network is used directly as the graph, in which the nodes are road state detectors and the edges are built based on their adjacent links. DeepWalk is used to embed the graph and the road traffic state sensor information is transferred into a low-dimensional space. Then, the Wasserstein GAN (WGAN) [Arjovsky et al., 2017] is used to train the traffic state data distribution and generate predicted results. Both public traffic flow (i.e., Caltrans PeMSD7) and traffic speed (i.e., METR-LA) datasets are used for evaluation, and the results demonstrate the effectiveness of the GAN-based solution when used in graph-based modeling.

Automated Machine Learning (AutoML). The application of machine learning requires considerable manual intervention in various aspects of the process, including feature extraction, model selection, and parameter adjustment. AutoML automatically learns the important steps related to features, models, optimization, and evaluation, so that machine learning models can be applied without manual intervention. AutoML would help to improve the implementation of machine learning models, including GNNs. AutoML is proposed for the challenge for computational requirements in graph-based modeling, in which case the hyper parameter tuning for GNNs can be more efficient with state-of-the-art AutoML techniques. An early attempt to combine AutoML with GNNs for traffic prediction problems is an Auto-STGCN algorithm, proposed in Wang et al. [2020a]. This algorithm searches the parameter space for STGCN models quickly based on reinforcement learning and generates optimal models automatically for specific scenarios.

Bayesian Network. Most of the existing studies aim for deterministic models that make mean predictions. However, some traffic applications rely on uncertainty estimates for the future situations. To tackle this gap, the Bayesian network, which is a type of probabilistic graphical model using Bayesian inference for probability computations, is a promising solution. The combination of GNNs with Bayesian networks is proposed for the challenge of GNN model interpretation. With probabilistic predictions, uncertainty estimates are generated for the future situations, especially the chance of extreme traffic states. A similar alternative is Quantile Regression, which estimates the quantile function of a distribution at chosen points, combined with Graph WaveNet for uncertainty estimates [Maas & Bloem, 2020].

6.2.4 Applications in Real-World ITS Systems

Last but not the least, most of the surveyed GNN-based studies are only based on the simulations with historical traffic data, without being validated or deployed in real-world ITS systems. However, there are a number of potential applications, especially for GNN-based models with the better forecasting performance. To name a few potential cases, the GNN-based forecasting model can be used for traffic light control in signalized intersections, when each intersection is modeled as a node in the graph and the corresponding traffic flow forecasting result can be used to design the traffic light control strategy. Another example is the application in map service and navigation applications, in which each road segment is modeled as a node in the graph and the corresponding traffic speed and travel time forecasting result can be used to calculate the estimated time of arrival. A third example is the application in online ride-hailing service providers, e.g., Uber and Lyft, in which each region is modeled as a node and the corresponding ride-hailing demand forecasting can be used to design a more profitable vehicle dispatching and scheduling system. Inspired by these potential application scenarios, there are a lot of potential research opportunities for researchers from both the academia and the industry.

7 Conclusion

In this paper, a comprehensive review of the application of GNNs for traffic forecasting is presented. Three levels of traffic problems and graphs are summarized, namely, road-level, region-level and station-level. The usages of recurrent GNNs, convolutional GNNs and graph autoencoders are discussed. We also give the latest collection of open dataset and code resource for this topic. Challenges and future directions are further pointed out for the follow-up research.

References

  • Agafonov [2020] Agafonov, A. (2020). Traffic flow prediction using graph convolution neural networks. In 2020 10th International Conference on Information Science and Technology (ICIST) (pp. 91–95). IEEE.
  • Arjovsky et al. [2017] Arjovsky, M., Chintala, S., & Bottou, L. (2017). Wasserstein gan. arXiv preprint arXiv:1701.07875, .
  • Atwood & Towsley [2016] Atwood, J., & Towsley, D. (2016). Diffusion-convolutional neural networks. In NIPS.
  • Bai et al. [2021] Bai, J., Zhu, J., Song, Y., Zhao, L., Hou, Z., Du, R., & Li, H. (2021). A3t-gcn: attention temporal graph convolutional network for traffic forecasting. ISPRS International Journal of Geo-Information, 10, 485.
  • Bai et al. [2019a] Bai, L., Yao, L., Kanhere, S. S., Wang, X., Liu, W., & Yang, Z. (2019a). Spatio-temporal graph convolutional and recurrent networks for citywide passenger demand prediction. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management (pp. 2293–2296).
  • Bai et al. [2019b] Bai, L., Yao, L., Kanhere, S. S., Wang, X., & Sheng, Q. Z. (2019b). Stg2seq: spatial-temporal graph to sequence model for multi-step passenger demand forecasting. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (pp. 1981–1987). AAAI Press.
  • Bai et al. [2020] Bai, L., Yao, L., Li, C., Wang, X., & Wang, C. (2020). Adaptive graph convolutional recurrent network for traffic forecasting. In Advances in Neural Information Processing Systems.
  • Baldassarre & Azizpour [2019] Baldassarre, F., & Azizpour, H. (2019). Explainability techniques for graph convolutional networks. In International Conference on Machine Learning (ICML) Workshops, 2019 Workshop on Learning and Reasoning with Graph-Structured Representations.
  • Barredo-Arrieta et al. [2019] Barredo-Arrieta, A., Laña, I., & Del Ser, J. (2019). What