IRWR: incremental random walk with restart

Weiren Yu, Xuemin Lin

Abstract

Random Walk with Restart (RWR) has become an appealing measure of node proximities in emerging applications \eg recommender systems and automatic image captioning. In practice, a real graph is typically large, and is frequently updated with small changes. It is often cost-inhibitive to recompute proximities from scratch via \emph{batch} algorithms when the graph is updated. This paper focuses on the incremental computations of RWR in a dynamic graph, whose edges often change over time. The prior attempt of RWR [1] deploys \kdash to find top-$k$ highest proximity nodes for a given query, which involves a strategy to incrementally \emph{estimate} upper proximity bounds. However, due to its aim to prune needless calculation, such an incremental strategy is \emph{approximate}: in $O(1)$ time for each node. The main contribution of this paper is to devise an \emph{exact} and fast incremental algorithm of RWR for edge updates. Our solution, \IRWR\!, can incrementally compute any node proximity in $O(1)$ time for each edge update without loss of exactness. The empirical evaluations show the high efficiency and exactness of \IRWR for computing proximities on dynamic networks against its batch counterparts.
BibTeX
@inproceedings{yu2013irwr,
  author = {Weiren Yu and Xuemin Lin},
  title = {{IRWR: incremental random walk with restart}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2013},
  doi = {10.1145/2484028.2484114},
}

Loading related content...

Figure