Semi-Decentralized Inference in Heterogeneous Graph Neural Networks for Traffic Demand Forecasting: An Edge-Computing Approach

Mahmoud Nazzal, Abdallah Khreishah, Joyoung Lee, Shaahin Angizi, Ala I. Al-Fuqaha, Mohsen Guizani

This paper, published in 2023, tackles the dual challenges of scalability and latency in real-time traffic forecasting. By moving away from static city-grid models and embracing a dynamic, edge-computing-based approach, the authors provide a blueprint for more efficient Intelligent Transportation Systems (ITS).

TL;DR

The authors propose a semi-decentralized inference framework for taxi demand forecasting that uses heterogeneous Graph Neural Networks (hetGNNs) and LSTMs. By distributing computation across edge "cloudlets" and using an adaptive node-assignment strategy, they achieve an order-of-magnitude reduction in inference time compared to centralized or fully decentralized systems without sacrificing accuracy.

What Problem Does This Paper Address?

Predicting where passengers will be (demand) and where vacant taxis are (supply) is vital for reducing wait times and increasing driver profits. While Graph Neural Networks (GNNs) are excellent at capturing the spatial relationships of a city, they face two major hurdles in this context:

  1. Static vs. Dynamic Modeling: Most existing models treat city regions as fixed nodes. However, the real "nodes" of the system—the taxis—are constantly moving. Treating taxis as nodes makes the graph dynamic and much harder to compute.
  2. The Scalability-Latency Trap: A centralized server (cloud) cannot easily scale to handle city-wide graphs of thousands of taxis. Conversely, a fully decentralized (peer-to-peer) approach, where taxis talk to each other, creates massive communication overhead. The authors prove mathematically that in a decentralized GNN, message-passing delay grows quadratically with the number of communication hops.

Methods

The authors introduce a two-part solution: a new model architecture and a new deployment strategy.

  • hetGNN-LSTM Model: Instead of a simple graph, they model the system as a Heterogeneous Information Network (HIN). It uses three types of edges:
  • Connectivity: Are the taxis on the same road network?
  • Proximity: Are they physically close?
  • Destination Similarity: Are they heading toward the same area? The model combines these spatial features using hetGNN layers and processes temporal patterns using Long Short-Term Memory (LSTM) networks.

  • Semi-decentralized Inference: They propose using "cloudlets"—moderate computing devices integrated into cellular base stations. The city is divided into Cloudlet Networks (CLNs).

  • Adaptive Node-CLN Assignment: To minimize the "chatter" between cloudlets, the authors developed a distributed heuristic (based on k-means and minimum-cut partitioning) to assign taxis to the cloudlet that shares the most edges with them. This minimizes the need for expensive inter-cloudlet communication.

Datasets

The study uses the NYC Taxi Dataset, specifically 35 million trip records from April to June 2016. The data includes pickup/drop-off times, GPS coordinates, and trip distances. This real-world dataset allows the authors to test their model against dynamic, high-density traffic scenarios.

Key Insights and Ideas

  • The "Goldilocks" of Decentralization: The paper identifies that neither the "all-in-one" cloud approach nor the "every-taxi-for-itself" P2P approach works for real-time GNNs. Semi-decentralization at the edge provides the necessary balance.
  • Taxis as Nodes: By treating taxis as nodes rather than grid cells, the model provides granular, driver-level predictions. This allows a driver to know the supply/demand specifically in their immediate 3x3 vicinity.
  • The Quadratic Bottleneck: A key theoretical contribution (Theorem 1) is the derivation of bounds for decentralized GNN delay. This provides a mathematical justification for why fully decentralized GNNs fail as the number of layers (hops) increases.

Key Results

  • Speedup: The semi-decentralized approach reduced overall inference time by approximately 10 times compared to centralized and decentralized schemes.
  • Accuracy: The model outperformed state-of-the-art baselines like DCRNN, Graph WaveNet, and CCRNN. In "region-to-region" comparisons, the proposed model reduced error metrics (MSE, MAE, and MAPE) by over 45% compared to CCRNN.
  • Communication Efficiency: The adaptive assignment algorithm reduced inter-cloudlet communication by roughly 2x compared to a simple uniform assignment.
  • Federated Learning Compatibility: The authors demonstrated that the model could be trained using federated learning across cloudlets with only a marginal (7%) drop in accuracy, enhancing data privacy.

Limitations and Future Work

  • Infrastructure Dependence: The system assumes the presence of 5G small cells or similar edge-computing infrastructure (cloudlets) throughout the city.
  • Boundary Effects: While adaptive assignment minimizes inter-cloudlet communication, taxis at the very edge of a cloudlet's range still face slight performance degradation due to missing information from non-adjacent cloudlets.
  • Future Directions: The authors suggest incorporating more node types (like roads and passengers) and refining the time-dependency modeling to make the predictions even more robust. They also aim to explore more sophisticated ways to handle the "cold-start" problem for taxis entering the network.

Summary updated

Abstract

Prediction of taxi service demand and supply is essential for improving customer experience and provider's profit. Recently, graph neural networks (GNNs), modeling city areas as nodes in a transportation graph, have been shown efficient for this application as they utilize both local node features and the graph structure in the prediction. Still, further improvement can be achieved by either simultaneously exploiting different types of nodes/edges in the graphs or enlarging the scale of the transportation graph. However, both alternatives are challenged by the scalability of GNNs. An immediate remedy to the scalability challenge is to decentralize the GNN operation. In return, as shown by our theoretical analysis and experimentation, this creates prohibitively excessive node-to-node communication. In this paper, we first propose a heterogeneous GNN-LSTM algorithm for improved taxi-level demand and supply forecasting utilizing several edge types in the graph. Then, to enable the large-scale application of this approach, we propose a semi-decentralized GNN inference approach that achieves scalability at minimized communication and computation overheads. This is achieved by utilizing multiple cloudlets; data centers with moderate computation and communication capabilities that can fit at cellular base stations. Extensive experiments over real data show the advantage of the proposed GNN-LSTM algorithm in improving prediction accuracy, and the ability of the proposed semi-decentralized GNN approach in reducing the overall inference time by about an order of magnitude compared to centralized and decentralized inference schemes.
BibTeX
@article{nazzal2024semi,
  author = {Mahmoud Nazzal and Abdallah Khreishah and Joyoung Lee and Shaahin Angizi and Ala I. Al-Fuqaha and Mohsen Guizani},
  title = {{Semi-Decentralized Inference in Heterogeneous Graph Neural Networks for Traffic Demand Forecasting: An Edge-Computing Approach}},
  journal = {IEEE Trans. Veh. Technol. 2024},
  year = {2024},
  doi = {10.1109/tvt.2024.3355971},
}

Loading related content...

Figure