STGC-GNNs: A GNN-based traffic prediction framework with a spatial-temporal Granger causality graph

(1)Temporal dependence

Definition 1 (Temporal dependence). Temporal dependence is the effect that the traffic information at the current timestep has on the traffic information at future timesteps for the same node.

Definition 2 (Temporal lag). Temporal lag is the interval of time to transmit traffic information between two timesteps, which are temporally dependent.

(2)Spatial dependence

Definition 3 (Spatial dependence). Spatial dependence is the effect that the traffic information of one node has on the traffic information of another node at the current time step.

Definition 4 (Spatial lag). Spatial lag is the distance to transmit traffic information between two nodes, which are spatially dependent at one timestep.

Definition 5 (Target-node and Source-node). For a pair of nodes that are spatially dependent, we call the node that releases the traffic information the source-node and the node that receives the traffic information the target-node. As illustrated in Figure 3, node no. 4 is the source-node, and nodes no. 1, 2, 3, 5, and 7 are target-nodes.

(3)Spatial-temporal dependence

Definition 6 (Spatial-temporal dependence). Spatial-temporal dependence is the effect that the traffic information of one node at the current time step has on the traffic information of another node at the future time step.

Definition 7 (Spatial-temporal lag). Spatial-temporal lag is the temporal lag consumed by transmitting traffic information between different nodes, which is spatial-temporal dependent.

Similar to what was mentioned in Section I, existing methods ignore some important observations in real-world traffic systems. In this section, we will depict those observations that can help understand our methods.

(1)Observation 1: Power of spatial dependence

The nodes in the road network are not completely independent but interact with others with the movement of transport, which is manifested as the transmission of traffic information and will lead to spatial dependence between interacting nodes. In the GNN-based model, the predictions of target-nodes can be improved if the spatial dependence can be modeled correctly because the information of other nodes is correctly introduced.

We observe that for the GNN-based model, since the spatial dependence is modeled by the input graph, it is possible to determine whether the input graph contains a valid spatial dependence by comparing its prediction result with the result when only self-connected inputs are used. Figure 4 shows the prediction results of the model on the METR_LA dataset when the input graph is a spatial graph (which is formulated as a spatial weighting matrix) and a self-connected graph (which is formulated as an identity matrix).

Figure 4 shows that in the majority of cases, the prediction results of the spatial weighting matrix input outperform those of the identity matrix input, which indicates that it is necessary and effective to consider the spatial dependence. However, it can also be seen that on the horizon of 45 min, the prediction results of the STGCN with spatial graph input are instead worse than those with self-connected graph input, which indicates that when the captured spatial dependence is wrong or redundant, it may lead to worse performance compared to using the traffic information only from itself. We call the reason behind this phenomenon the power of spatial dependence.

Therefore, for the GNN-based traffic prediction model, the construction of input graphs modeling spatial dependence directly affects the prediction effect of the model even if all other settings of the model are kept consistent. This is exactly the power of spatial dependence, which must be taken into consideration when using GNN-based traffic prediction models.

(2)Observation 2: Spatial-temporal entanglement of traffic information transmission

In real-world transportation systems, the flow of traffic can be considered as a process of traffic information transmitting across space and time. This observation indicates that the spatial-temporal entanglement of traffic information transmission for the traveling distance and the corresponding time consumed are not independent. We depict this observation in Figure 5.

The observation of the spatial-temporal entanglement of traffic information transmission indicates that if we want to capture the spatial dependence of road networks from traffic information under global transmission, we must consider the spatial-temporal lag of traffic information transmission across space. We considered this in Algorithm 1.

(3)Observation 3: Capability boundary of spatial distance

The existing methods generally consider the spatial distribution of road network nodes as an important indicator to measure spatial dependence, so they often use traffic network topology graphs or spatial distance weighting graphs as spatial graphs to input into GNN structures, which essentially model a local and static spatial dependence, i.e., the spatial dependency obtained from a fixed distribution of nodes in a certain road network. However, when traffic information is long-term transmitted, it will exhibit the property of being global in space and dynamic in time. We refer to this kind of traffic information as global-dynamic traffic information (GDTi). The key to long-term prediction is to model the transmission of GDTi. Therefore, it cannot be described by a local and static spatial dependence.

The simulation process of traffic flow for the same road network on horizons of 15 min and 30 min is illustrated in Figure 6. Assume that the time required for traffic information to be transmitted between two adjacent intersections in this traffic system is 15 min. Then, when we predict the traffic characteristics (e.g., flow rate and flow speed) of the target-node after 15 minutes, we only need to trace the traffic characteristics of the 1st-order neighbors at the current moment because this part of the traffic information will consume 15 minutes to transmit to the target-node. Similarly, when predicting the short-term traffic characteristics after 30 minutes, we need to trace the traffic characteristics of the 2nd-order neighbors.

It can be inferred that the nodes to be tracked will be farther away from the target-node on the prediction horizon of 45 minutes and longer, and therefore the transmission of GDTi with a traveling time of 45 minutes needs to be captured. This is difficult to capture in the existing spatial graph.

To capture the long-term transmission of GDTi in the road network as accurately as possible, we propose the TCR hypothesis and further hypothesize the properties of TCR based on the above observations, which can derive our method. According to Observation 1 and Observation 3, we suggest that the spatial dependence for long-term prediction can be expressed by the transmission of GDTi, specifically as a kind of transmitting causal relationship (TCR), so we try to capture this TCR and model it directly as a graph input to the GNN structure. According to Observation 2, we consider the spatial-temporal entanglement of the transmission of GDTi and design the spatial-temporal alignment algorithm in the process of capturing the TCR.

TCR Hypothesis. The transmission of Global-Dynamic Traffic information (GDTi) appears as a stable causal relationship between nodes underlying transmitting traffic information, which is referred to as Transmitting Causal Relationship (TCR).

As illustrated in Figure 7, GNN-based traffic prediction models can always be formalized as a component that captures temporal dependence and a GNN that captures spatial dependence. However, existing spatial graphs describe a local and static spatial dependence that may fail to make long-term predictions. We propose a spatial-temporal Granger causality test method that captures global and dynamic spatial dependence and models it as a spatial-temporal Granger causality graph (STGC graph) input to the framework.

In this section, we further propose a spatial-temporal Granger causality test to approximate the causal relationship underlying traffic road networks based on the TCR hypothesis to capture global and dynamic spatial dependence. The spatial-temporal Granger causality test is further divided into two modules: the spatial-temporal alignment module and the Granger causality test module. The former aligns the release and receive time of TCR’s global transmission, so the cause-node and effect-node contain the same part of GDTi at the same timestep, making transmission easier to detect; the latter further tests which two nodes the global transmission occurs from the aligned time-series, thus capturing the stable TCR under dynamic traffic flow.

(1)Spatial-temporal alignment

According to the TCR hypothesis, the transmission of GDTi can be regarded as the flow of causal effect from the cause-node to the effect-node, i.e., the mechanism of TCR. According to Observation 1 and Observation 2, TCRs can be derived as having two significant properties.

• •

  Causal lag. The effect produced by the cause-node does not have an immediate impact on the effect-node. The occurrence of the cause and the effect has a time lag, which is expressed as a spatial-temporal lag between the cause-node and effect-node in the traffic road network.

• •

  Causal order. The effect always occurs or is observed after the cause, which is manifested as the effect-node’s receiving GDTi always occurring after the cause-node’s releasing GDTi.

Therefore, we designed a spatial-temporal alignment algorithm, which can be divided into two steps.

1. 1.

   According to the causal lag, the time consumed by the TCR to transfer from the cause-node to the effect-node is calculated, i.e., the spatial-temporal lag $s$ between them.

2. 2.

   According to the causal order, we shift the time series of the cause-node by $s$ timesteps along the time axis to align the time when the TCR is generated on the cause-node and the time it impacts on the effect-node, thus ensuring that the causal mechanism can be inferred directly from the observed time series, which is the outcome of this causal mechanism.

According to the definitions in Section III, for TCR, the source-node is the cause-node, and the target-node is the effect-node. The spatial lag between nodes is the spatial distance between them, and the spatial-temporal lag is the time it takes for GDTi to travel from the cause-node to the effect-node, i.e., the time required for TCR transmission. Since the spatial-temporal lag between nodes is related not only to the spatial distance between nodes but also to the flow velocity of traffic information, which cannot be measured precisely, we use the average velocity of the cause-node as an approximation of the traffic information flow velocity. The algorithm is shown schematically in Figure 8.

Algorithm 1 Spatial-temporal alignment. Spatial-temporal alignment is the operation that slides the time series of the source-node along the time axis, and the sliding stride is the spatial-temporal lag $s$ between the source-node and target-node. The $s$ is the ratio of the spatial lag between the source-node and target-node to the average traffic velocity of the source-node.

As illustrated in Figure 8, B is the source-node, and A is the target-node.

(2)Granger causality test

After the spatial-temporal alignment of cause-node and effect-node, we can assume that cause-node and effect-node contain the same part of GDTi at the same moment, and we can infer whether there is a transmission of GDTi between them directly from the observed time series. Therefore, we need to answer another important question: how can TCR be detected from long-term observed and dynamically changing time series?

Based on the observation of real-world systems, with the traveling of traffic flow, the traffic information of downstream nodes will contain the traffic information of their upstream nodes, and thus the traffic information of upstream nodes can significantly improve the prediction of downstream nodes. The Granger causality test considers the time-series variables that can significantly improve the prediction after joining as cause variables, while the improved one is the effect variable, which is consistent with our observation. Therefore, we believe that the TCR in the traffic system may be manifested as Granger causality, and using the Granger causality test algorithm, we are able to detect the transmission of traffic information between two nodes, which can express a global and dynamic spatial dependence.

Granger causality analysis determines whether there is a causal relationship between different time-series variables. The basic idea is that if the prediction result using the historical information of both X and Y is better than that of only using the historical information of Y, that is, X helps to explain the future trend of Y, then X is the Granger cause of Y. There are two important hypotheses behind this:

• •

  Adding information about the cause variable helps recover the information of the effect variable.

• •

  The time lags need to be modeled when using past data to predict future data.

The Granger causality test method established vector autoregressive models for each of the above two predictions as follows.

where $X_{t-j}$ and $Y_{t-j}$ represent the traffic values of the time series X and Y at time $t-j$ respectively,$\alpha_{j}$, $a_{j}$ and $b_{j}$ represent the regression parameters of the autoregressive model, $\varepsilon_{Y}$ and $\varepsilon_{Y\mid X}$ represent the residuals of the two autoregressive models respectively, $m$ is the time lag of autoregressive models. If $\operatorname{var}\left(\varepsilon_{Y\mid X}\right)<\operatorname{var}\left(\varepsilon_{Y}\right)$, then it can be determined that the X has a statistically significant Granger causality on Y, expressed as “$X$ Granger-causes $Y$”.

As shown in Figure 9, to perform a Granger causality test on the time series of node A and B, we need to input both time series $X_{A}=\left\{x_{A_{1}},x_{A_{2}},\ldots,x_{A_{T}}\right\}$ and $X_{B}=\left\{x_{B_{1}},x_{B_{2}},\ldots,x_{B_{T}}\right\}$ to be tested. If the returned p-value is below the significance level, the null hypothesis, “$X_{B}$ does not Granger-cause $X_{A}$”, is rejected, i.e., the conclusion obtained is that the node B is a Granger cause of the node A.

(3)STGC graph

We input the aligned time series of the two nodes into the Granger causality test module, i.e., we use the spatial-temporal Granger causality test method to test the TCR between the two nodes, as shown in Figure 10.

The spatial-temporal Granger causality test is able to detect a Granger causality relationship between two traffic nodes, which can imply global and dynamic spatial dependence. To model this spatial dependence into a graph to input to the GNN for prediction, the following settings are made based on our observations:

• •

  The reservation of long-range spatial dependence. To prevent filtering out the long-range spatial dependence, instead of obtaining the input graph by a distance filter or topological adjacency, we model the distance between nodes as a spatial-temporal lag and use the spatial-temporal Granger causality test to detect the spatial dependence under global transmission. It is important to note that we will not use the “cost” offered in the dataset (which implies the spatial distance between different nodes) directly; we calculate the shortest path in the road network between two nodes and obtain the minimum “cost” instead. The reason behind this operation is to reserve as much potential spatial dependence as possible to be detected because the raw dataset does not provide all “cost” between any two nodes, even nodes that are very close. This is also the way to obtain the spatial-temporal lag for long-range spatial dependence because the raw dataset does not provide the “cost” for two nodes that are far away from with a high probability.

• •

  The direction of cause-and-effect.Spatial-temporal Granger causality, as a manifestation of spatial dependency between nodes, describes a causal relationship underlying traffic information transmission, which can be understood as the tracking of traffic information in the real world. Among them, cause-node corresponds to the source-node of traffic flow, while effect-node corresponds to the target-node of traffic flow. therefore, unlike the spatial graph where the dependence is mostly undirected, the relationships of nodes in the STGC graph are directed, and the direction is from the cause-node to the effect-node. this is not only consistent with the real-world situation that traffic information always flows from source-node to target-node but also consistent with the message passing mechanism of GNN, that is, the message of cause-node can pass to effect-node and update effect-node thus helping effect-node to make better prediction.

Eventually, we input the STGC graph into the GNN-based traffic prediction model, which can capture both the temporal dependence and spatial dependence of the traffic road network. The GNN-based traffic prediction model generally combines two modules, one for modeling temporal dependence such as RNN and its variants, and the other for modeling spatial dependence using GNN. Among them, the GNN structure can propagate and aggregate the traffic information between nodes that are spatially dependent, which is a good way to depict the transmission of GDTi. We can evaluate the ability to predict traffic directly by the output result of the GNN-based traffic prediction model.

We conducted experiments on the real-world dataset METR_LA, which is a Los Angeles highway dataset in the United States and one of the benchmark datasets for traffic prediction. For this dataset, the spatial graph is modeled in the form of a spatial weighting graph, which is later referred to as the spatial distance graph (SD graph), i.e., the spatial distance between nodes is converted into weights using Gaussian filtering.

(1)Selection of dataset

Based on Observation 1, we compared the prediction performance of the STGCN on two U.S. highway datasets using self-connected graph (identity matrix as adjacency matrix) and SD graph (spatial weighting matrix as adjacency matrix) as input, the former representing the case of prediction using only the temporal dependence and the latter representing the case of introducing spatial dependence, as shown in Table I.

It can be found that on the PEMS_BAY dataset, the prediction performance of the GNN-based model using a self-connected graph as input is very close to that using the SD graph, while the difference between them on METR_LA is very significant. Additionally, the overall prediction error value of PEMS_BAY is smaller. This indicates that the METR_LA dataset has higher complexity and prediction difficulty and can more significantly compare the effectiveness of different input graphs, so this dataset is chosen for experiments and analysis in this work.

(2)Basic information of dataset

The basic information of the METR_LA dataset is listed in Table II.The study area and distribution of traffic sensors in the METR_LA dataset are shown in Figure 11.

To more directly compare the effectiveness of the input graph itself for capturing spatial dependence, we selected three GNN-based models that use the input graph directly instead of performing transformation operations such as the attention mechanism. These models can use the GNN mechanism to aggregate and update messages based on the dependence expressed in the input graph and can directly reflect the prediction improved by neighboring nodes.

1. 1.

   T-GCN[19]: A temporal graph convolution for traffic prediction that combines a graph convolutional network (GCN) and gated recurrent unit (GRU) to capture spatial dependence and temporal dependence.

2. 2.

   STGCN[21]:Spatiotemporal graph convolutional networks for traffic forecasting, which builds a model with complete convolutional structures for temporal and spatial prediction.

3. 3.

   Graph Wavenet[20]:A deep spatial-temporal graph model for traffic prediction by developing a novel adaptive dependency matrix to work with a spatial distance matrix. To compare our Granger spatial-temporal causal graph with the spatial distance graph, we remove the adaptive dependency matrix as the backbone.

We use these three models as backbone models, i.e., GNN-based traffic prediction models in Figure 7. Apart from this operation, the partitioning of the dataset, the structure of the model and the training settings are kept the same as those of the original model to make a fair and effective evaluation of the effects produced by the method proposed in this paper.

To evaluate the effectiveness of this method for traffic prediction tasks, the following metrics are used as a measure of the difference between real traffic data $Y_{t}$ and predicted data $\hat{Y}_{t}$.

• •

  Mean Absolute Error (MAE)

  $$MAE=\frac{1}{n}\sum_{i=1}^{n}\left|Y_{t}-\hat{Y}_{t}\right|$$

  (3)

• •

  Mean Absolute Percentage Error (MAPE)

  $$MAPE=\frac{1}{n}\sum_{i=1}^{n}\left|\frac{Y_{t}-\hat{Y}_{t}}{Y_{t}}\right|$$

  (4)

• •

  Root Mean Squared Error (RMSE)

  $$RMSE=\sqrt{\frac{1}{n}\sum_{i=1}^{n}\left(Y_{t}-\widehat{Y}_{t}\right)^{2}}$$

  (5)

We evaluated the performance on prediction horizons of 15 min, 30 min, 45 min, and 60 min. The results are listed in Table III, where the backbone using SD graph as input graph uses the original name, while “STGC-” indicates a model using STGC graph as input.

It can be seen that for the same backbone model, the SD graph has better prediction results in all metrics for short-term prediction of 15 min and 30 min, while for the long-term prediction of 45 min and 60 min, the STGC graph has better results. This suggests that spatial dependence constructed from local and static connectivity can capture most of the nodes that interact with the target-node within a short time but seems to fail in long-term prediction. Long-range spatial dependence is needed more for long-term prediction, which is supposed to be detected in the global transmission of traffic information.

The comparison experiments between the STGC graph and the SD graph under the control variable settings have been able to show that the STGC graph is more effective in long-term prediction than the SD graph. To further illustrate that this effectiveness of the STGC graph is self-induced and not just due to the invalidation of the SD graph, we add the results where the input graph is a self-connected graph only (the adjacency matrix is the identity matrix) in comparison. The results are shown in Table IV, where (-) represents that the input graph is a self-connected graph.

In addition, to argue that the validity of such long-term predictions is not due to randomness, we add random groups for comparison. For each prediction horizon, we generated 10 random graphs with the following settings: 1) the sparsity of the random graph is consistent with the STGC graph; 2) for each node, the number of neighboring nodes is consistent with that in the STGC graph; and 3) the IDs of neighboring nodes are randomly generated. The final accuracy is averaged by the evaluation results of 10 random graphs, labeled as STGCN (random) in Figure 12.

Taking the MAE metric as an example, it shows that the predictive power of both STGC-STGCN and STGCN (random) remains relatively steady as the prediction horizon increases, where STGC-STGCN achieves the best results in long-term prediction and STGCN (random) keeps performing poorly, which is not surprising because it randomly introduces information from other nodes. The MAE metric also indicates that the STGC graph’s capability of long-term prediction is not due to random factors such as sparsity but due to the correct capture of spatial dependence. It is noteworthy that the random matrix achieves better results than the identity matrix at a prediction horizon of 30 min and is comparable to the identity matrix at a prediction horizon of 60 min. This illustrates, on the one hand, the limitations of ignoring spatial dependence and, on the other hand, the possibility of achieving better results by chance than by information from itself, even if such luck is not always reliable.

As illustrated in Figure 12, the original model (STGCN) using the SD graph showed a significant decrease in predictive capability between 30 min and 45 min, while the predictive capability using the STGC graph was much more stable, which also supports our Observation 2.

Although our method outperforms the original model only on the 45-min and 60-min long-term predictions, for the 207 nodes in the METR_LA dataset, there are nodes that are densely distributed with simple upstream and downstream and thus low prediction difficulty, while there are also nodes located at intersections with higher prediction difficulty. Therefore, the prediction accuracy of individual nodes was calculated and visualized on OpenStreetMap separately. We take the STGCN as an example for analysis in this section.

(1) Visualization of the prediction results for the STGC-STGCN

For the long-term predictions of 45 min and 60 min, our method can achieve better results than the SD graph for most of the nodes (e.g., Figure 13a). For some nodes, our method can achieve better results than the SD graph on all prediction horizons (see Figure 13b), which are mostly located at the boundary and intersection of the road network. We also have better prediction for remote nodes (circle in Figure 13b), which indicates that our method has better results for nodes that are more difficult to predict on all horizons.

(2) Visualization of STGC-STGCN interpretability

To interpret the spatial-temporal Granger causality, we detect and compare it with the spatial connectivity inscribed by the SD graph. We visualize the road network and its spatial dependence: the nodes to be predicted are marked with a gray marker, and other nodes are marked with a light gray marker. To visualize the spatial dependence, we used makers with car icons. The cause-node with red marker (with car icon), the effect-node with blue marker (with car icon), and the neighboring nodes in the SD graph with green marker (with car icon).

Direction of STGC. The STGC graph describes a kind of spatial dependence caused by global traffic information transmission, which corresponds to the upstream and downstream relationship of traffic flow in the real world. The STGC graph describes a kind of spatial dependence caused by global traffic information transmission, which corresponds to the upstream and downstream of traffic flow in the real world. By examining the detected causal relationship with the directions marked on the highway by OpenStreetMap, the effect-node should be in the downstream direction of the cause-node. As shown in Figure 14, it can be found that the cause (upstream) and effect (downstream) of our detection are consistent with the direction of the highway marked on the map.

The local connectivity constructed in the SD graph is a static relationship generated from the invariant spatial structure of the road network (node location distribution, road network topology, etc.), which mostly has no direction and is unable to portray the interaction caused by dynamic traffic flow. However, driving on a highway is constrained by traffic rules, and it is difficult to have direct interactions between nodes on roads in different driving directions even if they are close to each other. Spatial dependence is likely to be wrong when determined only by spatial distance but without considering the possibility of actual interaction.

As shown in Figure 15, two nodes that are spatially dependent in the SD graph do not actually reach each other, and traffic flow interactions cannot be generated between them. Considering the possibility of actual interactions, it is likely to introduce incorrect spatial dependence.

Spatial-temporal Granger causality in a sense can avoid the introduction of incorrect information by detecting the global transmission of traffic information between two nodes. As shown in Figure 16, the effect-node of the node to predict always appears downstream, while the spatially connected node may appear on the road in the opposite direction, which cannot be either upstream or downstream.

STGC captures long-range spatial dependence. The STGC graph can model long-range spatial dependence, while the SD graph can only model local connected nodes, which will not spend a longer time interacting with the node to be predicted. As shown in Figure 17, the spatial dependence between the gray marker (with an icon of a car) in the upper picture and the red marker (with an icon of a car) in the lower picture can be detected by the STGC graph.