Learned Approximate Distance Labels for Graphs

Distance computation is a fundamental problem in algorithmic graph theory with broad applications across various fields. Distance labeling is the method of assigning a label \(\ell \) to each node in a given graph G such that the distance between any pair of nodes u, v can be efficiently computed (or approximated) using only their labels \(\ell (u)\) and \(\ell (v)\) . Minimizing the size of these labels is of crucial importance for performance. In this paper, we address this challenge by introducing a novel learning-based approach to distance labeling inspired by collaborative filtering. This approach achieves superior performance compared to the theoretical baseline on label size with a trade-off in distance approximation error on special graph classes such as cycles and trees. We also report promising experimental results on general graphs that obtain lower error than cycles and trees.