Fast Inbound Top-K Query for Random Walk with Restart

Area of Science:

• Graph theory
• Network analysis
• Data mining

Background:

• Random Walk with Restart (RWR) is a key node proximity measure for graphs, capturing structure and noise robustness.
• Existing RWR computation methods struggle with efficiency and accuracy for large-scale graph queries.
• The inbound top-k (Ink) query, based on RWR, seeks k nodes with highest weighted RWR scores to a query node.

Purpose of the Study:

• To address the limitations of existing RWR techniques for the novel Ink query.
• To develop accurate and efficient algorithms for processing Ink queries on large graphs.
• To enable applications like traffic scheduling, disease treatment, and targeted advertising through effective Ink query processing.

Main Methods:

• Proposed two novel algorithms: Squeeze and Ripple, for accurate and incremental Ink query processing.
• Squeeze: Iteratively uses matrix-vector multiplication to estimate lower/upper bounds for all nodes.
• Ripple: Focuses on nodes within a 'vicinity' of the query node, propagating scores from the boundary.

Main Results:

• Ink queries successfully retrieve meaningful results from real-life graph datasets.
• The proposed Squeeze and Ripple algorithms demonstrate significant speedups, being orders of magnitude faster than state-of-the-art methods.
• Both algorithms provide accurate answers to the Ink query in a fast and incremental manner.

Conclusions:

• The novel Ink query, leveraging RWR, offers valuable insights for various applications.
• Squeeze and Ripple algorithms provide an efficient and accurate solution for Ink queries on large graphs.
• The developed methods significantly advance the state-of-the-art in graph query processing.