A Geometric Oracle for Distance Approximation in Large Real-World Graphs

Processing and analyzing massive real-world graphs rapidly has emerged as a key challenge in data analysis in recent years. Many important graph processing algorithms, such as p-center clustering, require estimation of shortest-path distances between node pairs. Computing good estimates for distances can be significantly accelerated by using approximate distance oracles. While there is a rich body of theoretical literature on distance oracles with worst-case bounds, there are only a handful of (mostly recent) approaches that are known to provide strong approximation in practice on real-world graphs. In this paper, we present empirical evidence of high fidelity geometric distance approximation oracles that use hyperbolic embeddings and directly leverage the intrinsic hyperbolicity existing in many real-world graphs. We show that for carefully-designed geometric oracles, the average additive distortion of distance can be significantly smaller than the theoretical worst-case upper bound of 2 delta log{N} where delta is the large-scale curvature of the N-node input graph. We substantiate this observation through numerical computations on a collection of real large-scale networks from multiple domains.