Integrating Local & Global Features for Estimating Shortest-path Distance in Large-scale Graphs

We propose an effective hybrid approach jointly leveraging local and global features for shortest-path (SP) distance estimation in domain-agnostic large-scale graphs. Previous works struggle to make estimations either from node-wise local embeddings or by compressing a global SP distance matrix, causing insufficient learning at some distance and loss of accuracy. Unlike them, we find a way to better preserve local distance on node embeddings, and then integrate them with a global process for accurate estimation at every distance. First, we propose a distance-consistent embedding method that better preserves the distance between each node and its local neighbors due to resampling node occurrence on random walks. Second, we train a feed-forward network with boosting techniques (FFN-BT) to estimate SP distance from these embeddings plus existing global features. Experimental results show that our approach averagely yields 10% improved accuracy and 20% reduced time when compared to existing methods on a broad class of graphs.