Fast inbound top-k query for random walk with restart

Chao Zhang, Shan Jiang, Yucheng Chen, Yidan Sun, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Random walk with restart (RWR) is widely recognized as one of the most important node proximity measures for graphs, as it captures the holistic graph structure and is robust to noise in the graph. In this paper, we study a novel query based on the RWR measure, called the inbound top-k (Ink) query. Given a query node q and a number k, the Ink query aims at retrieving knodes in the graph that have the largest weighted RWR scores to q. Inkqueries can be highly useful for various applications such as traffic scheduling, disease treatment, and targeted advertising. Nevertheless, none of the existing RWR computation techniques can accurately and efficiently process the Inkquery in large graphs. We propose two algorithms, namely Squeeze and Ripple, both of which can accurately answer the Ink query in a fast and incremental manner. To identify the top-k nodes, Squeeze iteratively performs matrix-vector multiplication and estimates the lower and upper bounds for all the nodes in the graph. Ripple employs a more aggressive strategy by only estimating the RWR scores for the nodes falling in the vicinity of q, the nodes outside the vicinity do not need to be evaluated because their RWR scores are propagated from the boundary of the vicinity and thus upper bounded. Ripple incrementally expands the vicinity until the top-k result set can be obtained. Our extensive experiments on real-life graph data sets show that Ink queries can retrieve interesting results, and the proposed algorithms are orders of magnitude faster than state-of-the-art method.

Original languageEnglish (US)
Title of host publicationMachine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2015
EditorsVitor Santos Costa, Carlos Soares, Annalisa Appice, Annalisa Appice, Pedro Pereira Rodrigues, Vitor Santos Costa, Carlos Soares, João Gama, Alípio Jorge, Pedro Pereira Rodrigues, João Gama, Vitor Santos Costa, Alípio Jorge, Annalisa Appice, Pedro Pereira Rodrigues, João Gama, Annalisa Appice, Carlos Soares, Alípio Jorge, João Gama, Pedro Pereira Rodrigues, Vitor Santos Costa, Carlos Soares, Alípio Jorge
PublisherSpringer-Verlag
Pages608-624
Number of pages17
ISBN (Print)9783319235240, 9783319235240, 9783319235240, 9783319235240
DOIs
StatePublished - Jan 1 2015
EventEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2015 - Porto, Portugal
Duration: Sep 7 2015Sep 11 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9285
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2015
CountryPortugal
CityPorto
Period9/7/159/11/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Fast inbound top-k query for random walk with restart'. Together they form a unique fingerprint.

  • Cite this

    Zhang, C., Jiang, S., Chen, Y., Sun, Y., & Han, J. (2015). Fast inbound top-k query for random walk with restart. In V. S. Costa, C. Soares, A. Appice, A. Appice, P. P. Rodrigues, V. S. Costa, C. Soares, J. Gama, A. Jorge, P. P. Rodrigues, J. Gama, V. S. Costa, A. Jorge, A. Appice, P. P. Rodrigues, J. Gama, A. Appice, C. Soares, A. Jorge, J. Gama, P. P. Rodrigues, V. S. Costa, C. Soares, ... A. Jorge (Eds.), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2015 (pp. 608-624). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9285). Springer-Verlag. https://doi.org/10.1007/978-3-319-23525-7_37