Fast Random Walk with Restart and Its Applications Export

@inproceedings{citeulike:1256221, abstract = {How closely related are two nodes in a graph? How to compute this score quickly, on huge, disk-resident, real graphs? Random walk with restart (RWR) provides a good relevance score between two nodes in a weighted graph, and it has been successfully used in numerous settings, like automatic captioning of images, generalizations to the "connection subgraphs", personalized PageRank, and many more. However, the 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. We propose fast solutions to this problem. The heart of our approach is to exploit two important properties shared by many real graphs: (a) linear correlations and (b) block- wise, community-like structure. We exploit the linearity by using low-rank matrix approximation, and the community structure by graph partitioning, followed by the Sherman- Morrison lemma for matrix inversion. Experimental results on the Corel image and the DBLP dabasets demonstrate that our proposed methods achieve significant savings over the straightforward implementations: they can save several orders of magnitude in pre-computation and storage cost, and they achieve up to 150x speed up with 90\%+ quality preservation.}, address = {Washington, DC, USA}, author = {Tong, Hanghang and Faloutsos, C. and Pan, J. Y.}, booktitle = {Data Mining, 2006. ICDM '06. Sixth International Conference on}, citeulike-article-id = {1256221}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1193207.1193363}, citeulike-linkout-1 = {http://doi.ieeecomputersociety.org/10.1109/ICDM.2006.70}, citeulike-linkout-2 = {http://dx.doi.org/10.1109/ICDM.2006.70}, citeulike-linkout-3 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4053087}, day = {08}, doi = {10.1109/ICDM.2006.70}, journal = {Data Mining, 2006. ICDM '06. Sixth International Conference on}, keywords = {hitting-time, random-walk, rwr}, month = {January}, pages = {613--622}, posted-at = {2008-09-04 17:17:51}, priority = {2}, publisher = {IEEE Computer Society}, title = {Fast Random Walk with Restart and Its Applications}, url = {http://dx.doi.org/10.1109/ICDM.2006.70}, year = {2007} }

TY - CONF ID - citeulike:1256221 L3 - citeulike-article-id:1256221 N2 - How closely related are two nodes in a graph? How to compute this score quickly, on huge, disk-resident, real graphs? Random walk with restart (RWR) provides a good relevance score between two nodes in a weighted graph, and it has been successfully used in numerous settings, like automatic captioning of images, generalizations to the "connection subgraphs", personalized PageRank, and many more. However, the 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. We propose fast solutions to this problem. The heart of our approach is to exploit two important properties shared by many real graphs: (a) linear correlations and (b) block- wise, community-like structure. We exploit the linearity by using low-rank matrix approximation, and the community structure by graph partitioning, followed by the Sherman- Morrison lemma for matrix inversion. Experimental results on the Corel image and the DBLP dabasets demonstrate that our proposed methods achieve significant savings over the straightforward implementations: they can save several orders of magnitude in pre-computation and storage cost, and they achieve up to 150x speed up with 90%+ quality preservation. JF - Data Mining, 2006. ICDM '06. Sixth International Conference on AD - Washington, DC, USA EP - 622 TI - Fast Random Walk with Restart and Its Applications PB - IEEE Computer Society T2 - Data Mining, 2006. ICDM '06. Sixth International Conference on SP - 613 KW - hitting-time KW - random-walk KW - rwr AU - Tong, Hanghang AU - Faloutsos, C AU - Pan, JY PY - 2007/01/08/ UR - http://dx.doi.org/10.1109/ICDM.2006.70 ER -