On the Embeddability of Random Walk Distances

Xiaohan Zhao

Adelbert Chang

Atish Das Sarma

Haitao Zheng

Ben Y. Zhao

*
Proceedings of the VLDB Endowment, Volume 6, Number 14, Pgs. 1690-1701, September 2013.
To Be Presented at The 40th International Conference on Very Large Data Bases, Hangzhou China, 2014
*

Paper Abstract

Analysis of large graphs is critical to the ongoing growth of search
engines and social networks. One class of queries centers around node
affinity, often quantified by random-walk distances between node pairs,
including *hitting time*, *commute time*, and *personalized
PageRank* (PPR). Despite the potential of these "metrics," they are
rarely, if ever, used in practice, largely due to extremely high
computational costs.

In this paper, we investigate methods to scalably and efficiently compute random-walk distances, by "embedding" graphs and distances into points and distances in geometric coordinate spaces. We show that while existing graph coordinate systems (GCS) can accurately estimate shortest path distances, they produce significant errors when embedding random-walk distances. Based on our observations, we propose a new graph embedding system that explicitly accounts for per-node graph properties that affect random walk. Extensive experiments on a range of graphs show that our new approach can accurately estimate both symmetric and asymmetric random-walk distances. Once a graph is embedded, our system can answer queries between any two nodes in 8 microseconds, orders of magnitude faster than existing methods. Finally, we show that our system produces estimates that can replace ground truth in applications with minimal impact on application output.