BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart

Overview

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 scalable, accurate, and fast 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× larger graphs, and requires up to 130× less memory space than other preprocessing methods. In the query phase, BePI computes RWR scores up to 9× faster than existing methods.

Paper

BePI is described in the following paper:

• BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart
  Jinhong Jung, Namyong Park, Lee Sael, and U Kang.
  ACM International Conference on Management of Data (SIGMOD) 2017, Chicago, Illinois, USA
  [PDF][BIBTEX]

Code

The code of the methods used in the paper is available here.

• BePI_matlab_v1.1: [Download]

Datasets