ICDM'06.pdf

Random walk with restart (RWR) is a technique used to compute the relevance score between two nodes in a weighted graph. However, straightforward implementations of RWR do not scale for large graphs, requiring either quadratic space and cubic pre-computation time or slow response time on queries. The proposed solution, B LIN, exploits two properties of real graphs: linear correlations and block-wise, community-like structure. It uses low-rank matrix approximation and graph partitioning, followed by the Sherman-Morrison lemma for matrix inversion. Experimental results demonstrate significant savings over straightforward implementations, achieving up to 150x speedup with 90%+ quality preservation. The method is operational, with careful design and numerous optimizations, and has been applied to various settings, including automatic captioning of images and personalized PageRank.