Graph Neural Network for Traffic Forecasting: A Survey

In plain words

Cities need to predict traffic: how many cars will pass a sensor, how fast they will move, how many people will want a taxi or a bike. Deep learning has become good at reading past measurements over time, but roads, subway lines and bike stations form a network, and a plain grid or a plain sequence model fits that shape poorly. Graph neural networks are built for data that lives on a network. Each sensor, road segment or station becomes a point, and the links between points carry information from one point to its neighbours.

This survey collects the research from 2018 to 2020 that applies such networks to traffic forecasting. It sorts the problems (flows, speeds, demand and a few others), the ways people draw the network as a graph, the kinds of graph neural network they use, the public datasets and code they rely on, and the results they report. It ends with open problems such as messy data, changing road networks and models that are hard to explain.

Read it as a map rather than a leaderboard. The numbers it copies come from different papers that used different data splits, so they do not rank the methods fairly.

TL;DR

• Surveys graph neural network (GNN) methods for traffic forecasting. The authors reviewed 212 papers from 2018 to 2020, including preprints §1.
• Groups the forecasting problems into flow, speed, demand and other problems, each at road, region or station level §3.
• Classifies traffic graphs and adjacency matrices (road-based, distance-based, similarity-based, dynamic) and the GNN families used §4.1 §4.2.
• Lists open datasets and code, and copies a benchmark table from the surveyed papers, which the authors say are not directly comparable §5.1 §5.2 §5.3 tab. 11.
• Runs no experiments of its own. Open challenges and future directions are in §6.

Problem

Traffic states (flow, speed, demand) depend on both space and time. Earlier linear models such as vector autoregression capture only linear relations between locations, and CNNs on a grid assume Euclidean structure, so they cannot represent a road or subway network directly §1 §3. The survey treats forecasting as data-driven: it predicts from historical traffic states on a graph, optionally with external factors such as weather and calendar effects §1 §4.1 (formal definitions in [def. 4.1] and [def. 4.2]).

The survey assumes the GNN is trained on a labelled training set and evaluated on a test set, with forecasting cast as node-level regression and scored with RMSE, MAE or MAPE §4.2 §5.3.

Method

This is a literature survey, so the "method" is its classification scheme and the formal definitions it uses. The steps below follow the survey's structure.

1. Forecasting problems §3 tab. 1. Problems are split by the traffic state predicted: flow (road, region, station levels), speed (road and region levels, plus travel time, congestion and time of arrival), demand (ride-hailing, taxi, shared vehicle, bike) and other problems (accidents, anomalies, parking availability, emissions, railway delay, lane occupancy). Each row of tab. 1 lists the surveyed papers for one problem.

2. Formal setting §4.1 [def. 4.1] [def. 4.2]. A traffic graph is G = (V, E, A), with node set V, edge set E and adjacency matrix A. For a time step t, the node feature matrix has one row per node and one column per traffic state variable. The forecasting function maps the last T steps of features on G to the future state, with or without external factors. The survey assumes traffic states sit on nodes and handles the edge case as "derived similarly" §4.1. Single-step and multi-step forecasting are both covered §4.1.

3. Traffic graph types §4.1.1 tab. 2 fig. 2 fig. 3 fig. 4. Three levels, each with several graph types:

   • Road level: sensor graphs (nodes are sensors, edges are road links), road segment graphs, road intersection graphs and road lane graphs.
   • Region level: irregular region graphs (for example road-based or zip-code partitions), regular grid graphs, and OD graphs whose nodes are origin-destination pairs.
   • Station level: subway, bus, bike, railway, car-sharing, parking lot and parking block graphs, usually linked by lines or road links.

   Sensor graphs and road segment graphs are the most common §4.1.1.

4. Adjacency matrix types §4.1.2 tab. 3. Four families:

   • Road-based: connection matrices (binary), transportation connectivity (reachable by motorway or subway, or by travel time), and direction matrices (angle between road links).
   • Distance-based: neighbour matrices (shared boundary, with 1/4 for grid neighbours in some cases) and distance matrices (driving distance, shortest path, or random-walk-with-restart proximity). The survey notes that these are usually static and ignore similarity between distant nodes §4.1.2.
   • Similarity-based: traffic-pattern similarity (correlation of historical states) and functional similarity (correlation of point-of-interest distributions) §4.1.2.
   • Dynamic: learned during training rather than fixed in advance §4.1.2.

5. GNN families §4.2 fig. 6 tab. 5. The survey covers recurrent GNNs, convolutional GNNs, graph autoencoders and spatiotemporal GNNs. Spectral convolutions (ChebNet, and GCN as its first-order approximation) and spatial convolutions (DGC, MPNN, GraphSAGE, GAT) are described with the equations below. Spatiotemporal GNNs are split into RNN-based and CNN-based models, and the survey adds attention-based and FNN-based types §4.2. GCN is the most used GNN component, with GAT rising §4.2 tab. 5.

6. Classic models §4.2. DCRNN uses diffusion convolution with an RNN and was first proposed for speed forecasting. STGCN stacks spatio-temporal blocks (two temporal convolutions around one graph convolution). ASTGCN adds spatial and temporal attention to STGCN. Graph WaveNet learns a self-adaptive adjacency matrix and uses causal convolutions for time. The survey says that the adaptive matrix is fixed after training §4.2.

7. Design pipeline §4.2. The survey proposes four steps for building a GNN forecaster: find the graph structure; specify its type and scale (directed or not, static or dynamic, homogeneous or not); choose the loss and metrics, with supervised training as the usual setting; and assemble the model from GNN components already used in the surveyed studies.

Equations

Graph convolution as written for GCN, with the first-order filter §4.2:

\mathbf{X}_{*G} = \mathbf{W} (\mathbf{I}_N + \mathbf{D}^{-\frac{1}{2}} \mathbf{A} \mathbf{D}^{-\frac{1}{2}}) \mathbf{X} eq. 1

Renormalised form, with self-loops à = A + I_N and degrees D̃ taken from à §4.2:

\mathbf{X}_{*G} = \mathbf{W} (\tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}}) \mathbf{X} eq. 2

Message aggregation (MPNN), where M^(t) is the aggregation function of iteration t and e_ij the edge feature §4.2:

\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}) eq. 3

Readout, where U^(t) is the readout function of iteration t §4.2:

\mathbf{X}_i^{(t)} = \mathcal{U}^{(t)} (\mathbf{X}_i^{(t-1)},\mathbf{m}_{v_i}^{(t)}) eq. 4

Multi-head graph attention (GAT), where ‖ is concatenation and σ the activation §4.2:

\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)}) eq. 5

Diffusion convolution in DCRNN, with K diffusion steps and out-degree and in-degree matrices D_O and D_I §4.2:

\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} eq. 6

The graph-level notation in the survey is the normalised Laplacian L̃ = I_N − D^{-1/2} A D^{-1/2}, defined in §4.2 and listed in tab. 4.

Spatiotemporal GNN

The survey's typical spatiotemporal model uses a 1D-CNN for time and a GCN for space, with an MLP that produces the output. Either component can be swapped for another structure §4.2 fig. 5. The sketch below restates that structure.

# Spatiotemporal GNN forecaster  [§4.2] [fig. 5]
# Input:  history of node features on graph G = (V, E, A)  # (T, N, d)
# Output: predicted traffic states for the nodes

def spatiotemporal_gnn(history, adjacency):
    # Model each node's time series with a 1D convolution  [§4.2]
    temporal = temporal_conv_1d(history)
    # Mix features across neighbouring nodes with a graph convolution
    # [§4.2] [eq. 2]
    spatial = graph_conv(temporal, adjacency)
    # Map the learned features to the forecast with an MLP  [§4.2]
    return mlp(spatial)

The text does not fix the order of the temporal and spatial blocks. The caption of fig. 5 names the example "1D-CNN+GCN", which the sketch follows.

Hyperparameters

Not applicable. The survey trains no model and states no model hyperparameters. The settings a reader needs when using the surveyed datasets are below. Dataset descriptions and download footnotes are in §5.1.

Other reported settings: the default prediction horizon in the results table is 60 minutes unless stated otherwise §5.3. The TaxiNYC and BikeNYC rows of the results table are 30-minute predictions tab. 11. The survey does not state training, validation or test split ratios, or the imputation method, for the copied results §5.3.

Results

Author-reported. The survey runs no experiments. The table below is copied from the papers it surveys. The survey says these values are not directly comparable because splits, preprocessing and evaluation settings differ, and that newer results may exist §5.3. Units for RMSE and MAE are not stated in the source. Bold marks the best value in each group in the source tab. 11.

Setup: the rows come from the surveyed papers. The survey gives the split and preprocessing per row only in general terms, and states the 30-minute horizon for the TaxiNYC and BikeNYC rows §5.3 tab. 11.

Other headline numbers in the survey: 212 papers reviewed, 2018 to 2020 §1. The survey lists open-source projects for flow, speed, demand and other problems tab. 7 tab. 8 tab. 9 tab. 10, with TensorFlow and PyTorch the most used frameworks §5.2.

Paper vs code

No official code.

The paper is a survey and describes no implementation of its own. It links a GitHub repository for its resource list, github.com/jwwthu/GNN4Traffic, which the authors say will be updated with papers, datasets and code §1 §5.2. It is a list of resources, not code for a method, so no code field is set. The third-party code projects in tab. 7 to tab. 10 are not the authors' and are not used here. I checked the paper text, its footnotes and its abstract for an official repository and did not run a separate GitHub search, because a survey has no method to implement.

Pitfalls

• Not a benchmark. tab. 11 combines results from papers with different splits, preprocessing and metrics. The survey says the numbers are not directly comparable §5.3. Do not rank methods on this table without rerunning them.
• Horizon mismatch. The stated default is 60 minutes, but the TaxiNYC and BikeNYC rows are 30-minute results §5.3 tab. 11.
• Missing units and splits. The source states no units for RMSE and MAE and no split ratios for the copied results tab. 11 §5.3.
• MAPE at zero. MAPE divides by the true value. The survey gives no rule for zero or near-zero values, and TaxiSZ, TaxiNYC and BikeNYC report MAPE as N/A §5.3 tab. 11.
• Equation 1 and the Laplacian disagree in sign. Eq. 1 uses I + D^{-1/2} A D^{-1/2}, but the survey defines the normalised Laplacian as I − D^{-1/2} A D^{-1/2} eq. 1 §4.2. The survey does not say which form it means to use.
• GAT is under-specified. Eq. 5 uses an attention term α^k that is never defined, and it does not show the softmax normalisation or the attention scoring function. The survey does not state them eq. 5 §4.2.
• Diffusion convolution is hard to read as printed. The parentheses in eq. 6 do not balance. The exact grouping is not determinable from this card.
• Order of blocks. The text does not say whether a spatiotemporal GNN applies the temporal or the spatial block first §4.2 fig. 5.
• Version. The LaTeX source fetched for this card has an abstract that says "open data and source codes". The arXiv metadata for v4 says "open data and source resources". The source may not match v4 exactly. Check the arXiv version before quoting the survey's wording.
• Figures are not ours to reuse. fig. 1, fig. 2 and fig. 5 are adapted from other papers. fig. 2, fig. 3 and fig. 4 also carry third-party sources (a PeMS screenshot, a Manhattan zip-code map, a Beijing subway map). Under our licensing rules none of them may be added to this page, even when figure support lands.
• Claimed advantage is narrow. The survey says GNNs reach state-of-the-art results, but it also says that added modelling power gives only narrow margins over simpler statistical and machine-learning models §1 §6.1.

Lineage

• Compared against: the surveys it lists in §2. The survey names ye2020build, a graph-based deep learning review for traffic, as the only other GNN-focused survey, and notes that its own scope is traffic forecasting only §1 §2.
• Builds on: the GCN, ChebNet, MPNN, GraphSAGE and GAT papers and the DCRNN, STGCN and Graph WaveNet models, all cited in §4.2.
• Superseded by: not stated in this wiki.