Ollivier-Ricci Curvature Based Spatio-Temporal Graph Neural Networks for Traffic Flow Forecasting

Xing Han, Guowei Zhu, Ling Zhao, Ronghua Du, Yuhan Wang, Zhe Chen, Yang Liu, Silu HeSymmetry 2023 · DOI

TL;DR

This paper introduces a novel approach to traffic flow forecasting by incorporating Ollivier-Ricci curvature into Spatio-Temporal Graph Neural Networks (STGNNs). By leveraging this geometric property to better model "bottleneck" connections between road network communities, the proposed method significantly improves prediction accuracy compared to traditional adjacency or distance-based graph structures.

What Problem Does This Paper Address?

Intelligent Transportation Systems (ITS) rely heavily on accurate traffic flow forecasting to optimize urban planning and management. The core challenge in this domain is capturing the complex interplay between spatial dependencies (how traffic at one location affects others) and temporal dependencies (how traffic evolves over time). Existing Spatio-Temporal Graph Neural Networks (STGNNs) use graph structures to model spatial relationships, but they often rely on simple node-to-node connections like adjacency or Euclidean distance. This overlooks crucial local topological features of road networks, such as how different communities of roads are connected by "bottleneck" edges, which can disproportionately influence traffic flow.

Methods

The paper proposes enhancing STGNNs by incorporating Ollivier-Ricci curvature into the graph convolution module. This geometric concept, originally from differential geometry, is adapted to discrete graphs to measure the "bottleneck" nature of edges.

  • Ollivier-Ricci Curvature: This metric quantifies how much a graph's local structure deviates from a tree-like structure. In road networks, edges with negative curvature often connect different communities (acting as bottlenecks), while positive curvature edges connect nodes within the same community.
  • Edge Bottleneck Coefficient ($r_{ij}$): The raw Ollivier-Ricci curvature values are normalized into a coefficient $r_{ij}$ between 0 and 1. A higher $r_{ij}$ indicates a stronger bottleneck, signifying a more critical connection between road network communities.
  • Curvature Graph Convolution Module: This module integrates the $r_{ij}$ coefficient into the message-passing mechanism of STGNNs. Instead of solely relying on node adjacency or distance, the model uses $r_{ij}$ to weigh the influence of neighboring nodes, effectively guiding message passing based on neighborhood-to-neighborhood connectivity and local topology.

Datasets

The proposed method was evaluated on two real-world traffic datasets:

  • PEMS-BAY: A traffic speed dataset collected from 325 sensors in California, spanning January to June 2017.
  • PEMSD7: A traffic flow dataset collected from 883 sensors in California, spanning July to August 2016.

These datasets are standard benchmarks for traffic forecasting research.

Key Insights and Ideas

  • Topology Matters: Simple adjacency or distance-based graph structures are insufficient for capturing the nuanced spatial dependencies in traffic flow. Local topological features, like those captured by Ollivier-Ricci curvature, play a significant role.
  • Bottlenecks Drive Flow: Edges with high negative Ollivier-Ricci curvature (bottleneck edges) are critical for inter-community traffic flow. Incorporating this information allows models to better understand how these critical connections influence traffic.
  • Neighborhood-to-Neighborhood is Key: The proposed method moves beyond simple node-to-node interactions to consider neighborhood-to-neighborhood relationships, which are more representative of how traffic flows across different parts of a road network.
  • Curvature Enhances Existing Models: The integration of Ollivier-Ricci curvature provides a tangible improvement to established STGNN architectures like STGCN and T-GCN, demonstrating its general applicability.

Key Results

The proposed STGNNs with the curvature graph convolution module (labeled as STGCN+ and TGCN+) consistently outperformed baseline models (STGCN, STGCN-, TGCN, TGCN-) across both datasets and various prediction horizons (15, 30, 45, and 60 minutes).

  • PEMS-BAY: STGCN+ achieved improvements of up to 3.51% in MAE compared to STGCN for shorter horizons. TGCN+ showed even more substantial improvements, up to 30.87% in MAE compared to TGCN.
  • PEMSD7: Similar improvements were observed, with STGCN+ outperforming STGCN and TGCN+ outperforming TGCN across all metrics and horizons.
  • Qualitative Analysis: Visualizations showed that STGCN+ better aligned with ground truth, especially during volatile periods and for longer prediction horizons, indicating a more robust capture of traffic dynamics.

Limitations and Future Work

  • Limitations: While the curvature-based approach shows promise, the paper notes that for longer prediction horizons (e.g., 60 minutes on PEMS-BAY), the performance gains were less pronounced, and in some cases, adjacency-based models performed comparably or better. This suggests that while curvature is important, it might not be the sole determinant of spatial dependence, and other factors might become more dominant over longer time scales.
  • Future Work: The authors suggest exploring the incorporation of multiple topological properties beyond Ollivier-Ricci curvature to further exploit the impact of road network structures on traffic flow. They also propose investigating how node-to-node and neighborhood-to-neighborhood relationships can be combined to handle complex traffic scenarios more effectively.

Summary updated

BibTeX
@article{han2023ollivier,
  author = {Xing Han and Guowei Zhu and Ling Zhao and Ronghua Du and Yuhan Wang and Zhe Chen and Yang Liu and Silu He},
  title = {{Ollivier-Ricci Curvature Based Spatio-Temporal Graph Neural Networks for Traffic Flow Forecasting}},
  journal = {Symmetry},
  year = {2023},
  doi = {10.3390/sym15050995},
}
Figure