Fast query execution for retrieval models based on path-constrained random walks

Ni Lao, William W. Cohen

Introduction

Modern information retrieval systems increasingly rely on relational graphs where documents are nodes connected by various metadata, such as authors, citations, and publication years. Path-Constrained Random Walks (PCRW) have emerged as a state-of-the-art method for querying these complex graphs. Unlike standard random walks, PCRW follows specific "recipes" or paths of edge types to retrieve relevant nodes. For example, a query might follow the path: "Find papers written by the same author as the query paper, then identify the papers they cite."

Path-Constrained Random Walk (PCRW) schema following specific edge types.

Despite its effectiveness, PCRW is computationally expensive. As a walker traverses a well-connected graph, the number of nodes with non-zero probability increases exponentially. Calculating exact distributions for every possible path becomes a significant bottleneck for real-time search and recommendation systems. This paper addresses this challenge by introducing efficient approximation strategies that maintain sparsity without sacrificing accuracy.

Approximation Methods

The authors propose four primary strategies to keep the number of active nodes in a walk small:

  1. Fingerprinting (Monte Carlo): This method simulates $K$ independent random walks. The probability of a node is estimated by the frequency with which walkers terminate at that node.
  2. Weighted Particle Filtering: A hybrid approach that uses exact calculations for high-probability branches and switches to sampling (particles) when a branch's probability falls below a threshold $\epsilon_{min}$. This reduces variance compared to pure fingerprinting.
  3. Fixed Truncation: At each step, any node with a probability below a fixed threshold $\epsilon$ is zeroed out.
  4. Beam Truncation: An adaptive version of truncation that retains only the top $W$ highest-probability nodes at each step.

These approximations are applied during both the learning phase (identifying important paths) and the inference phase (executing queries).

Experimental Setup and Datasets

The methods were evaluated on two large-scale scientific publication corpora from the biological domain:

  • Yeast: Comprising 48,000 papers, 164,000 nodes, and 2.8 million edges.
  • Fly: Comprising 127,000 papers, 770,000 nodes, and 3.5 million edges.

These datasets include intricate relationships between authors, papers, journals, years, genes, and proteins. The evaluation focused on three tasks: Reference Recommendation, Expert Finding, and Gene Recommendation.

Key Insights

  • The Power Law Advantage: Random walks on real-world graphs typically result in highly skewed distributions. A small number of nodes capture most of the probability mass, justifying truncation strategies that ignore the "long tail" of low-probability nodes.
  • Sparsity as Regularization: Surprisingly, approximated models outperformed exact models in 4 out of 6 tasks. Truncation acts as a noise filter, forcing the model to focus on robust, meaningful relationships rather than weak, noisy connections.
  • Particle Filtering Efficiency: Particle filtering proved to be 2-4x faster than fingerprinting for comparable accuracy levels by combining exact math with targeted sampling.

Results and Performance

The proposed strategies achieved significant speedups: 10x to 100x for sampling-based methods (Fingerprinting and Particle Filtering) and 2x to 10x for truncation strategies. In most tasks, using 1,000 to 10,000 particles was sufficient to match or exceed the accuracy of exact PCRW.

Comparison of Distribution Density (a) and Path Weights (b) between Beam and Fixed Truncation strategies.

When comparing truncation methods, Fixed Truncation was found to be slightly superior to Beam Truncation. Fixed truncation naturally penalizes longer paths—which are more prone to noise accumulation—thereby providing a cleaner ranking signal.

Conclusion and Future Work

This work demonstrates that PCRW can be made highly efficient through sparsity-inducing approximations. While the current study uses large biological datasets, future work could explore even larger web-scale graphs and dynamic graph updates. The finding that approximation can serve as a form of regularization suggests that these techniques are not just about speed, but also about improving retrieval quality in noisy relational environments.

Summary updated

Abstract

Many recommendation and retrieval tasks can be represented as proximity queries on a labeled directed graph, with typed nodes representing documents, terms, and metadata, and labeled edges representing the relationships between them. Recent work has shown that the accuracy of the widely-used random-walk-based proximity measures can be improved by supervised learning - in particular, one especially effective learning technique is based on Path-Constrained Random Walks (PCRW), in which similarity is defined by a learned combination of constrained random walkers, each constrained to follow only a particular sequence of edge labels away from the query nodes. The PCRW based method significantly outperformed unsupervised random walk based queries, and models with learned edge weights. Unfortunately, PCRW query systems are expensive to evaluate. In this study we evaluate the use of approximations to the computation of the PCRW distributions, including fingerprinting, particle filtering, and truncation strategies. In experiments on several recommendation and retrieval problems using two large scientific publications corpora we show speedups of factors of 2 to 100 with little loss in accuracy.
BibTeX
@inproceedings{lao2010fast,
  author = {Ni Lao and William W. Cohen},
  title = {{Fast query execution for retrieval models based on path-constrained random walks}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2010},
  doi = {10.1145/1835804.1835916},
}
Figure