Efficient processing node proximity via random walk with restart

Abstract

Graph is a useful tool to model complicated data structures. One important task in graph analysis is assessing node proximity based on graph topology. Recently, Random Walk with Restart (RWR) tends to pop up as a promising measure of node proximity, due to its proliferative applications in e.g. recommender systems, and image segmentation. However, the best-known algorithm for computing RWR resorts to a large LU matrix factorization on an entire graph, which is cost-inhibitive. In this paper, we propose hybrid techniques to efficiently compute RWR. First, a novel divide-and-conquer paradigm is designed, aiming to convert the large LU decomposition into small triangular matrix operations recursively on several partitioned subgraphs. Then, on every subgraph, a “sparse accelerator” is devised to further reduce the time of RWR without any sacrifice in accuracy. Our experimental results on real and synthetic datasets show that our approach outperforms the baseline algorithms by at least one constant factor without loss of exactness.

Publication DOI: https://doi.org/10.1007/978-3-319-11116-2_50
Divisions: College of Engineering & Physical Sciences
Event Title: 16th Asia-Pacific Web Conference
Event Type: Other
Event Dates: 2014-09-05 - 2014-09-07
ISBN: 978-3-319-11115-5, 978-3-319-11116-2
Last Modified: 21 Nov 2024 08:26
Date Deposited: 24 Jan 2017 14:55
Full Text Link:
Related URLs: https://link.sp ... -319-11116-2_50 (Publisher URL)
PURE Output Type: Conference contribution
Published Date: 2014
Authors: Lv, Bingqing
Yu, Weiren (ORCID Profile 0000-0002-1082-9475)
Wang, Liping
McCann, Julie A.

Download

[img]

Version: Accepted Version


Export / Share Citation


Statistics

Additional statistics for this record