Hypergraph-Enhanced Multi-Granularity Stochastic Weight Completion in Sparse Road Networks

Abstract

Road network applications, such as navigation, incident detection, and Point-of-Interest (POI) recommendation, make extensive use of network edge weights (e.g., traveling times). Some of these weights can be missing, especially in a road network where traffic data may not be available for every road. In this article, we study the stochastic weight completion (SWC) problem, which computes the weight distributions of missing road edges. This is difficult, due to the intricate temporal and spatial correlations among neighboring edges. Besides, the road network can be sparse, i.e., there is a lack of traveling information in a large portion of the network. To tackle these challenges, we propose a multi-granularity framework for Region-Wise Graph Completion (RegGC). To learn coarse spatial correlations among distantly located roads, we construct a region-wise hypergraph neural architecture based on semantic region dependencies. For finer spatial correlations, we incorporate contextual road network properties (e.g., speed limits, lane counts, and road types). Moreover, it incorporates recent and periodic dimensions of road traffic. We evaluate RegGC against 10 existing methods on 3 real road network datasets. They show that RegGC is more effective and efficient than state-of-the-art solutions.