Zhifeng Bao

Due to various reasons such as noisy measurement and privacy preservation, a network/graph is often uncertain such that each edge in the network has a probability of existence. In this paper, we study finding the most probable shortest path which has the highest probability of being the shortest path between a given pair of nodes in an uncertain network. Despite significant progress being made, this problem still suffers from the efficiency and scalability issue. To solve this problem, the state-of-the-art adopts a two-phase approach where Phase 1 generates some candidate paths and Phase 2 estimates their probabilities of being the shortest path and returns the one with the highest probability as the solution. Notably, Phase 2 requires a large number of simulations over all edges in the network and can easily dominate the cost of the whole process. In this paper, we aim to resolve the efficiency and scalability issue by optimizing Phase 2. Specifically, we first propose a non-learning based fast approximation technique which significantly reduces the number of samples for the probability estimation in each simulation. Afterwards, we further propose a learning-based method which can directly estimate the probability of each candidate path without costly simulations. Extensive experiments show that (1) compared to the state-of-the-art, our fast approximation technique and learning-based method can achieve up to 5x and 210x speedups in Phase 2 respectively while maintaining highly competitive or even equivalent results, (2) the training process is highly scalable and (3) the prediction function can work effectively under the problem settings different from the one it was trained.