Random Walk with Restart on Large Graphs Using Block Elimination

Cited 12 time in webofscience Cited 0 time in scopus
  • Hit : 44
  • Download : 0
Given a large graph, how can we calculate the relevance between nodes fast and accurately? Random walk with restart (RWR) provides a good measure for this purpose and has been applied to diverse data mining applications including ranking, community detection, link prediction, and anomaly detection. Since calculating RWR from scratch takes a long time, various preprocessing methods, most of which are related to inverting adjacency matrices, have been proposed to speed up the calculation. However, these methods do not scale to large graphs because they usually produce large dense matrices that do not fit into memory. In addition, the existing methods are inappropriate when graphs dynamically change because the expensive preprocessing task needs to be computed repeatedly. In this article, we propose BEAR, a fast, scalable, and accurate method for computing RWR on large graphs. BEAR has two versions: a preprocessing method BEARS for static graphs and an incremental update method BEARD for dynamic graphs. BEARS consists of the preprocessing step and the query step. In the preprocessing step, BEARS reorders the adjacency matrix of a given graph so that it contains a large and easy-to-invert submatrix, and precomputes several matrices including the Schur complement of the submatrix. In the query step, BEARS quickly computes the RWR scores for a given query node using a block elimination approach with the matrices computed in the preprocessing step. For dynamic graphs, BEARD efficiently updates the changed parts in the preprocessed matrices of BEARS based on the observation that only small parts of the preprocessed matrices change when few edges are inserted or deleted. Through extensive experiments, we show that BEARS significantly outperforms other state-of-the-art methods in terms of preprocessing and query speed, space efficiency, and accuracy. We also show that BEARD quickly updates the preprocessed matrices and immediately computes queries when the graph changes.
Publisher
ASSOC COMPUTING MACHINERY
Issue Date
2016-06
Language
English
Article Type
Article
Citation

ACM TRANSACTIONS ON DATABASE SYSTEMS, v.41, no.2

ISSN
0362-5915
DOI
10.1145/2901736
URI
http://hdl.handle.net/10203/250522
Appears in Collection
EE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 12 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0