From Walk-Derived Distance to Euclidean Graph Geometry

Shortest path distances are strong signals to capture graph geometry in a Euclidean embedding space. Random walks determine an upper bound on graph distance between visited node pairs and repeated walks only tightens the upper bound. In addition, random walks provide a computationally efficient method to select a subset of interacting node pairs for the graph embedding. We propose Fodiwalk, a two-stage framework to efficiently extract graph-related parameters such as shortest path distance estimates in the first stage and use them in the second stage to reflect graph geometry in the generated embedding. We employed a guaranteed-to-converge force model, which directly updates the embedding gradients using the Euclidean and the estimated graph distances. Experiments on different datasets show enhanced results on various prediction tasks and geometric metrics, while retaining robustness in different dimension sizes.