Index-free Approach with Theoretical Guarantee for Efficient Random Walk with Researt Query

CategoryPublications 204

Authors: Dandan Lin, Raymond Chi-Wing Wong, Min Xie, Victor Junqiu Wei

Name of Conference: IEEE International Conference on Data Engineering(ICDE 2020), April 20-24, 2020, Dallas, Texas, USA

Date of Publication: April 20, 2020


Due to the prevalence of graph data, graph analysis is very important nowadays. One popular analysis on graph data is Random Walk with Restart (RWR) since it provides a good metric for measuring the proximity of two nodes in a graph. Although RWR is important, it is challenging to design an algorithm for RWR. To the best of our knowledge, there are no existing RWR algorithms which, at the same time, (1) are index-free, (2) return answers with a theoretical guarantee and (3) are efficient. Motivated by this, in this paper, we propose an index-free algorithm called Residue-Accumulated approach (ResAcc) which returns answers with a theoretical guarantee efficiently. Our experimental evaluations on large-scale real graphs show that ResAcc is up to 4 times faster than the best-known previous algorithm, guaranteeing the same accuracy. Under typical settings, the best-known algorithm ran around 1000 seconds on a large dataset containing 41.7 million nodes, which is too time-consuming, while ResAcc finished in 275 seconds with the same accuracy. Moreover, ResAcc is up to 6 orders of magnitude more accurate than the best-known algorithm in practice with the same execution time, which is considered as a substantial improvement.

View Full Text

Keywords2020Approximation theory and practiceICDEMin Xie Previous: Next: