Source-linked AI summary
DDP-GCN: Multi-Graph Convolutional Network for Spatiotemporal Traffic Forecasting
Kyungeun Lee, Wonjong Rhee
TL;DR
Traffic speed forecasting requires modeling spatial dependencies that distance-only approaches may not capture in complex, directional road networks. DDP-GCN adds direction and positional relationship to distance through multi-graph convolution and partition filters, improving forecasting especially over long horizons in highly complex urban networks. The study also identifies limits from omitted daily and weekly periodicity and from the uncertain general usefulness of positional relationships.
Problem
Previous traffic forecasting methods mainly modeled road-network spatial dependencies using distance, despite the network’s complex non-Euclidean and directional characteristics.
Method
DDP-GCN uses distance, direction, and positional relationship as multi-graph spatial elements, with partition filters dividing elements into similar components.
Results
DDP-GCN improved forecasting, especially for long-term prediction in highly complex urban networks, across two large-scale real-world datasets.
Takeaways & Limitations
Direction and positional relationship should be included alongside distance for more accurate forecasting of complex spatial traffic relationships.
Takeaways & Limitations
The study uses consecutive time sequences without daily or weekly periodicity, and the usefulness of positional relationship may depend on the network.
Abstract
from arXiv · showhide
Traffic speed forecasting is one of the core problems in transportation systems. For a more accurate prediction, recent studies started using not only the temporal speed patterns but also the spatial information on the road network through the graph convolutional networks. Even though the road network is highly complex due to its non-Euclidean and directional characteristics, previous approaches mainly focused on modeling the spatial dependencies using the distance only. In this paper, we identify two essential spatial dependencies in traffic forecasting in addition to distance, direction and positional relationship, for designing basic graph elements as the fundamental building blocks. Using the building blocks, we suggest DDP-GCN (Distance, Direction, and Positional relationship Graph Convolutional Network) to incorporate the three spatial relationships into deep neural networks. We evaluate the proposed model with two large-scale real-world datasets, and find positive improvements for long-term forecasting in highly complex urban networks. The improvement can be larger for commute hours, but it can be also limited for short-term forecasting.
1 Introduction
Traffic speed forecasting benefits from spatial road-network information, but distance-only models miss directional and positional relationships. DDP-GCN encodes distance, direction, and positional relationship with multi-graphs and improves forecasting, especially for long-term prediction in complex urban networks.
- Motivation: Accurate traffic speed forecasting supports congestion prevention, shorter travel times, and reduced carbon emissions.The task predicts future speeds for each road segment from historical speed data.
- Motivation: Distance-only spatial modeling can miss traffic relationships shaped by driving direction and on-path proximity.A nearby link may have a different speed pattern because it travels in another direction, while farther links can share direction or positional relationships.
- Contribution: DDP-GCN models distance, direction, and positional relationship through multiple graph elements for traffic speed forecasting.The model also uses partition filters to subdivide spatial graph elements into components with similar characteristics.
- Results: DDP-GCN outperformed state-of-the-art baselines on two large-scale real-world datasets representing highly complex urban networks.The reported benefit is especially associated with long-term forecasting.
2 Graph Convolutional Networks for Traffic Forecasting
Traffic data can be represented as vectors, grids, or graphs, but representation choices affect how well deep networks capture complex road relationships. Graph convolution addresses irregular neighborhoods by aggregating weighted information through graph-defined spatial filters.
- 2.1 Representing Traffic Data for DNN: Vector stacking is simple and flexible but lacks a principled procedure for ordering road-network data.Its effectiveness depends heavily on how the data is presented to the network.
- 2.1 Representing Traffic Data for DNN: Grid representations enable image-based CNNs but can be inefficient because many grid points lack road links and multiple links may share a cell.Higher spatial resolution can enlarge the matrix and worsen this inefficiency.
- 2.1 Representing Traffic Data for DNN: Graph representations encode pairwise road-link relationships in an N × N matrix, preserving spatial information that vector and grid representations handle less directly.The matrix entries can represent distance, connectivity, or other relationships between road links.
- 2.3 Brief History of Graph Convolutional Networks: Graph convolution performs weighted neighborhood aggregation, using an N × N spatial filter to accommodate irregular and variable-sized graph neighborhoods.Nonzero matrix entries represent neighboring nodes relative to each node, unlike a common fixed-shape image filter.
- 2.3 Brief History of Graph Convolutional Networks: Traffic GCNs commonly weight graph edges by adjacency, physical distance, or travel-related measures, while later work adds relationships such as reachability and inflow/outflow.Multi-graph convolution has also combined distinct graph elements for demand and flow prediction.
3 Definitions and Problem Formulation
The paper represents road links as directed graph nodes and defines link vectors and directions from their endpoints. Traffic forecasting is formulated as learning a function that maps historical graph signals to future graph signals.
- Definitions: A link vector is the difference between a road link’s endpoint and start point, and its direction is represented by the vector’s angle.The link vector is defined for a road segment without an internal merge or diverge section.
- Definitions: A traffic network is modeled as a weighted directed graph whose nodes are road links and whose weighted adjacency matrix represents spatial interdependencies.Connectedness is fully described by the weight matrix in the paper's formulation.
- Problem Formulation: The forecasting problem learns a function that maps T′ historical graph signals to T future graph signals.Each graph signal represents traffic speed observed across the road-link nodes at a time interval.
- Problem Formulation: Although the dataset uses only speed as the observed feature, the formulation also applies directly when each link has multiple observed features.The general graph-signal size is R^N×P, with P denoting the number of observed features per link.
4 Proposed Model
DDP-GCN represents road-network spatial relationships with distance, direction, and positional graph elements, then combines partition filtering with multi-graph convolution in spatio-temporal blocks.
- 4.1 Framework Overview: The framework uses two spatio-temporal convolutional blocks followed by a 1x1 convolution, with each block combining spatial and temporal processing.The temporal block uses a 1-D convolution, while the spatial block applies partitioned graph elements and two types of multi-graph convolution.
- 4.2 Definition of the Spatial Graph Elements: DDP-GCN represents distance, direction, and positional relationships as three spatial graph elements for directed road networks.The model constructs weighted adjacency matrices for these relationships before applying graph convolutions.
- 4.2 Definition of the Spatial Graph Elements: The distance graph weights link pairs using shortest inter-link distance and a thresholded Gaussian kernel.Distances for nonadjacent links are evaluated with Dijkstra’s algorithm, with σ and κ as hyperparameters.
- 4.2 Definition of the Spatial Graph Elements: The direction graph encodes relative link directions, while partition filters subdivide direction weights into components with similar characteristics.The proposed direction measure is normalized, and partition filters preserve the element-wise sum while grouping directional patterns.
- 4.2 Definition of the Spatial Graph Elements: The positional graph captures how extended link vectors meet, representing four possible positional relationships between links.Each intersection type indicates how two links could interact; exactly parallel links receive zero positional weights.
5 Experiment
Experiments on two complex Seoul urban traffic datasets show that DDP-GCN improves long-horizon forecasting over established baselines, with gains especially visible during commute hours. Ablations indicate that positional relationship, partition filters, and stacked spatial elements contribute substantially to performance.
- Experiment Setup: Experiments used Urban1 and Urban2, highly connected Seoul networks with bidirectional links, intersections, traffic signals, and direction-bearing road links.The datasets contained taxi-derived traffic data collected during April 2018, with normalized data split into training, validation, and test sets.
- Performance Comparison: DDP-GCN(Stacked) achieved the best performance in every evaluated case except Urban1’s 30-minute MAPE, improving 60-minute forecasting by 7.52% on average and up to 10.14% over prior state-of-the-art performance.Its performance remained sustained as the horizon increased from 30 to 60 minutes, unlike DCRNN and STGCN.
- Performance Comparison: Relative improvements were as large as 20–45% during morning commute hours, when traffic dynamics were more complicated.Figure 11 reports hourly RMSE curves and relative improvements over DCRNN and STGCN for Urban1 60-minute forecasting.
- Ablation Test: Removing or replacing graph elements showed that positional relationship caused the largest degradation, while distance alone was least important and insufficient for modeling complex spatial relationships.The ablation results support feeding direction and positional relationship into the network alongside distance.
- Ablation Test: DDP-GCN(Stacked) outperformed GCN models using larger K-hop distance convolutions, while increasing K did not improve its own performance, indicating that stacked spatial elements outperform simple K-hops.The comparison used K-polynomial ChebNet on the distance element.
6 Discussion and Conclusion
The proposed network uses distance, direction, and positional relationships through multi-graph convolution to improve traffic speed forecasting, particularly for long-term prediction in complex urban networks. The study also identifies limitations in temporal periodicity modeling and in explaining how each spatial dependency contributes to performance.
- 6 Discussion and Conclusion: The model improved forecasting especially for long-term prediction in highly complex urban networks.The evaluation compared the proposed models with popular baseline models.
- 6 Discussion and Conclusion: DDP-GCN represents distance, direction, and positional relationships as spatial graph elements within multi-graph convolution.Partition filters further subdivide each spatial graph element into components with similar characteristics.
- 6 Discussion and Conclusion: The networks used consecutive time sequences but did not exploit daily or weekly periodicity in their inputs.The authors identify constructing inputs that fully exploit periodicity as future work.
- 6 Discussion and Conclusion: Weekly periodicity gave Historical Average competitive forecasting performance on the highly complex urban networks.The authors note that weekly periodicity had significant forecasting power in these networks.
- 6 Discussion and Conclusion: The study cannot determine exactly how the three spatial dependencies individually contribute to the performance improvement.The authors propose evaluating many traffic datasets simultaneously to identify when direction and positional information helps.