TPA : Fast, Scalable, and Accurate Method for Approximate Random Walk with Restart on Billion Scale Graphs

Overview

Given a large graph, how can we determine similarity between nodes in a fast and accurate way? Random walk with restart (RWR) is a popular measure for this purpose and has been exploited in numerous data mining applications including ranking, anomaly detection, link prediction, and community detection. However, previous methods for computing exact RWR require prohibitive storage sizes and computational costs, and alternative methods which avoid such costs by computing approximate RWR have limited accuracy.

In this paper, we propose TPA, a fast, scalable, and highly accurate method for computing approximate RWR on large graphs. TPA exploits two important properties in RWR: 1) nodes close to a seed node are likely to be revisited in following steps due to block-wise structure of many real-world graphs, and 2) RWR scores of nodes which reside far from the seed node are proportional to their PageRank scores. Based on these two properties, TPA divides approximate RWR problem into two subproblems called neighbor approximation and stranger approximation. In the neighbor approximation, TPA estimates RWR scores of nodes close to the seed based on scores of few early steps from the seed. In the stranger approximation, TPA estimates RWR scores for nodes far from the seed using their PageRank. The stranger and neighbor approximations are conducted in the preprocessing phase and the online phase, respectively. Through extensive experiments, we show that TPA requires 3.5× less time with 40× less memory space than other state-of-the-art methods for the preprocessing phase. In the online phase, TPA computes approximate RWR up to 30× faster than existing methods while maintaining high accuracy.


Paper

TPA is described in the following paper:


Code

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


Datasets

Name#Nodes#EdgesDescriptionSourceDownload
Friendster68,349,4662,586,147,869 Friendster friendship network Internet Archive Link
Twitter41,652,2301,468,365,182 Twitter follower network Advanced Networking Lab at Kaist Link
WikiLink12,150,976378,142,420 Wiki-links of the English Wikipedia Wikimedia Link
LiveJournal4,847,57168,475,391 LiveJournal friendship network Stanford Large Network Dataset Collection Link
Pokec1,632,80330,622,564 Friendship network from the Slovak social network Pokec Pokec Link
Google875,7135,105,039 Hyperlink network between web pages of Google Google programming contest Link
Slashdot82,144549,202 Social network of users in the technology news site Slashdot DAI-Labor Link