BePI

Authors:

Abstract
How can we measure similarity between nodes quickly and accurately on large graphs? Random walk with restart (RWR) provides a good measure, and has been used in various data mining applications including ranking, recommendation, link prediction and community detection. However, existing methods for computing RWR do not scale to large graphs containing billions of edges; iterative methods are slow in query time, and preprocessing methods require too much memory. In this paper, we propose BePI, a fast, memory-efficient, and scalable method for computing RWR on billion-scale graphs. BePI exploits the best properties from both preprocessing methods and iterative methods. BePI uses a block elimination approach, which is a preprocessing method, to enable fast query time. Also, BePI uses a preconditioned iterative method to decrease memory requirement. The performance of BePI is further improved by decreasing non-zeros of the matrix for the iterative method. Through extensive experiments, we show that BePI processes 100 times larger graphs, and requires up to 130 times less memory space than other preprocessing methods. In the query phase, BePI computes RWR scores up to 9 times faster than existing methods.
Funding Information
  • NRF (2015R1C1A2A01055739 and 2015K1A3A1A14021055)

This publication has 48 references indexed in Scilit: