Estimating pairwise distances in large graphs

Point-to-point distance estimation in large scale graphs is a fundamental and well studied problem with applications in many areas such as Social Search. Previous work has focused on selecting an appropriate subset of vertices as landmarks, aiming to derive distance upper or lower bounds that are as tight as possible. In order to compute a distance bound between two vertices, the proposed methods apply triangle inequalities on top of the precomputed distances between each of these vertices and the landmarks, and then use the tightest one. In this work we take a fresh look at this setting and approach it as a learning problem. As features, we use structural attributes of the vertices involved as well as the bounds described above, and we learn a function that predicts the distance between a source and a destination vertex. We conduct an extensive experimental evaluation on a variety of real-world graphs and show that the average relative prediction error of our proposed methods significantly outperforms state-of-the-art landmark-based estimates. Our method is particularily efficient when the available space is very limited.