Succinct Graph Representations as Distance Oracles: An Experimental Evaluation

Download PDF

Abstract

Distance oracles answer shortest-path queries between any pair of nodes in a graph. They are often built using succinct graph repre- sentations such as spanners, sketches, and compressors to minimize oracle size and query answering latency. Node embeddings, in par- ticular, offer graph representations that place similar nodes nearby in a low-rank space. However, their use in distance oracles has not been sufficiently studied and compared to other respresentations. In this paper, we compare experimentally different distance ora- cles that are based on a variety of node embeddings and other graph representations. The evaluation focuses on exact distance oracles and is made in terms of relevant measures of efficiency, i.e., con- struction time, memory requirements, and query-processing time. It is conducted over fourteen real-world graph datasets and four syn- thetic graph families. Our findings suggest that distances between node embeddings are excellent estimators of graph distances when graphs are well-structured, for instance, when they are regular, or have high clustering coefficient and density. Moreover, depending on the embedding algorithm, their construction is up to 19 times faster than multi-dimensional scaling, they require up to 2 times less memory than approximate distance-preserving data structures, up to 23 times less processing time than compressed indexes, and are exact up to 1.7 times more than spanners. Finally, while the exactness of distance oracles is infeasible to maintain for huge graphs even under large amounts of resources, we find experimentally that GOSH, a parallelized implementation of spectral embedding, scales to graphs of 100M nodes with little loss on accuracy.