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

Abstract

Prediction of taxi service demand and supply is essential for improving customer's experience and provider's profit. Recently, graph neural networks (GNNs) have been shown promising for this application. This approach models city regions as nodes in a transportation graph and their relations as edges. GNNs utilize local node features and the graph structure in the prediction. However, more efficient forecasting can still be achieved by following two main routes; enlarging the scale of the transportation graph, and simultaneously exploiting different types of nodes and edges in the graphs. However, both approaches are challenged by the scalability of GNNs. An immediate remedy to the scalability challenge is to decentralize the GNN operation. However, this creates excessive node-to-node communication. In this paper, we first characterize the excessive communication needs for the decentralized GNN approach. Then, we propose a semi-decentralized approach utilizing multiple cloudlets, moderately sized storage and computation devices, that can be integrated with the cellular base stations. This approach minimizes inter-cloudlet communication thereby alleviating the communication overhead of the decentralized approach while promoting scalability due to cloudlet-level decentralization. Also, we propose a heterogeneous GNN-LSTM algorithm for improved taxi-level demand and supply forecasting for handling dynamic taxi graphs where nodes are taxis. Extensive experiments over real data show the advantage of the semi-decentralized approach as tested over our heterogeneous GNN-LSTM algorithm. Also, the proposed semi-decentralized GNN approach is shown to reduce the overall inference time by about an order of magnitude compared to centralized and decentralized inference schemes.

Introduction

Real-time traffic forecasting is a cornerstone of modern Intelligent Transportation Systems (ITS). Predicting taxi demand and supply accurately allows for reduced passenger wait times and increased driver profitability. While Graph Neural Networks (GNNs) have emerged as a powerful tool for capturing spatial dependencies in urban environments, they traditionally rely on static grid-based models. This paper moves beyond these limitations by treating individual taxis as dynamic nodes in a heterogeneous graph, addressing the twin challenges of scalability and latency through a novel edge-computing framework.

The Scalability-Latency Trap

Centralized cloud-based systems often struggle to scale with city-wide graphs containing thousands of moving nodes, leading to high latency. Conversely, a fully decentralized peer-to-peer (P2P) approach, where taxis communicate directly, suffers from massive communication overhead. The authors demonstrate that in decentralized GNNs, message-passing delay grows quadratically with the number of communication hops, creating a significant bottleneck for real-time applications.

The hetGNN-LSTM Architecture

To capture the complex relationships between taxis, the authors propose a Heterogeneous Information Network (HIN) model. Unlike simple graphs, this model utilizes three distinct edge types to define relationships:

  1. Connectivity: Based on the shared road network.
  2. Proximity: Based on physical distance.
  3. Destination Similarity: Based on shared target regions.
The hetGNN-LSTM architecture models spatial relationships through three edge types (connectivity, proximity, and destination similarity) and temporal patterns via LSTM layers.

This spatial information is processed through heterogeneous GNN (hetGNN) layers, while temporal patterns are captured using Long Short-Term Memory (LSTM) networks. This combination allows for granular, driver-level predictions, enabling a driver to understand supply and demand dynamics within their immediate vicinity.

Semi-decentralized Inference at the Edge

The core contribution of this work is a semi-decentralized inference framework that utilizes "cloudlets"—computing devices integrated into cellular base stations. The city is partitioned into Cloudlet Networks (CLNs), and an adaptive node-assignment strategy is employed to minimize inter-cloudlet "chatter."

Comparison of inference schemes: (a) centralized cloud-based, (b) fully decentralized peer-to-peer, and (c) the proposed semi-decentralized cloudlet-based approach.

By using a distributed heuristic based on k-means and minimum-cut partitioning, taxis are assigned to the cloudlet with which they share the most edges. This "Goldilocks" approach balances the efficiency of centralization with the scalability of decentralization.

Experimental Evaluation

The framework was evaluated using the NYC Taxi Dataset, comprising 35 million trip records. Key results include:

  • Inference Speedup: The semi-decentralized approach achieved an order-of-magnitude reduction (approximately 10x) in inference time compared to both centralized and fully decentralized schemes.
  • Forecasting Accuracy: The model outperformed state-of-the-art baselines (DCRNN, Graph WaveNet, CCRNN), reducing error metrics like MSE and MAPE by over 45% in region-to-region comparisons.
  • Communication Efficiency: The adaptive assignment algorithm reduced inter-cloudlet communication by roughly 2x compared to uniform assignment.
  • Privacy and Federated Learning: The model proved compatible with federated learning, maintaining high accuracy (only a 7% drop) while enhancing data privacy.

Conclusion

By shifting from static grids to dynamic, taxi-centric graphs and implementing a semi-decentralized edge-computing architecture, this research provides a scalable solution for real-time urban forecasting. Future work will look to incorporate additional node types, such as road segments and passengers, and address the "cold-start" problem for taxis newly entering the network.

Summary updated

Abstract

Prediction of taxi service demand and supply is essential for improving customer's experience and provider's profit. Recently, graph neural networks (GNNs) have been shown promising for this application. This approach models city regions as nodes in a transportation graph and their relations as edges. GNNs utilize local node features and the graph structure in the prediction. However, more efficient forecasting can still be achieved by following two main routes; enlarging the scale of the transportation graph, and simultaneously exploiting different types of nodes and edges in the graphs. However, both approaches are challenged by the scalability of GNNs. An immediate remedy to the scalability challenge is to decentralize the GNN operation. However, this creates excessive node-to-node communication. In this paper, we first characterize the excessive communication needs for the decentralized GNN approach. Then, we propose a semi-decentralized approach utilizing multiple cloudlets, moderately sized storage and computation devices, that can be integrated with the cellular base stations. This approach minimizes inter-cloudlet communication thereby alleviating the communication overhead of the decentralized approach while promoting scalability due to cloudlet-level decentralization. Also, we propose a heterogeneous GNN-LSTM algorithm for improved taxi-level demand and supply forecasting for handling dynamic taxi graphs where nodes are taxis. Extensive experiments over real data show the advantage of the semi-decentralized approach as tested over our heterogeneous GNN-LSTM algorithm. Also, the proposed semi-decentralized GNN approach is shown to reduce 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},
}
Figure