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

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.