Source-linked AI summary
Personalized PageRank Estimation and Search: A Bidirectional Approach
Peter Lofgren, Siddhartha Banerjee, Ashish Goel
TL;DR
Personalized PageRank search must rank different target nodes for each searching user without infeasible storage or query-time computation. The paper introduces a bidirectional estimator and sampling-based search algorithms, achieving 3x-8x speedups over FAST-PPR and efficient operation on large networks.
Problem
Personalized PageRank search must rank user-dependent target nodes without Θ(n^2) storage or Θ(m) query-time computation.
Method
The paper combines forward and reverse vectors in a bidirectional PageRank estimator and uses PPR-proportional sampling for search over target sets.
Results
3x-8x faster than FAST-PPR at a given accuracy across a diverse set of networks.
Takeaways & Limitations
PPR sampling and sequential estimation provide practical alternatives for searching target sets, with experiments demonstrating scalability to networks with billions of edges.
Takeaways & Limitations
Precomputation requires storage that remains smaller than O(n^2) for sparse graphs, while storage can increase substantially when targets contain many keywords.
Abstract
from arXiv · showhide
We present new algorithms for Personalized PageRank estimation and Personalized PageRank search. First, for the problem of estimating Personalized PageRank (PPR) from a source distribution to a target node, we present a new bidirectional estimator with simple yet strong guarantees on correctness and performance, and 3x to 8x speedup over existing estimators in experiments on a diverse set of networks. Moreover, it has a clean algebraic structure which enables it to be used as a primitive for the Personalized PageRank Search problem: Given a network like Facebook, a query like "people named John", and a searching user, return the top nodes in the network ranked by PPR from the perspective of the searching user. Previous solutions either score all nodes or score candidate nodes one at a time, which is prohibitively slow for large candidate sets. We develop a new algorithm based on our bidirectional PPR estimator which identifies the most relevant results by sampling candidates based on their PPR; this is the first solution to PPR search that can find the best results without iterating through the set of all candidate results. Finally, by combining PPR sampling with sequential PPR estimation and Monte Carlo, we develop practical algorithms for PPR search, and we show via experiments that our algorithms are efficient on networks with billions of edges.
1. INTRODUCTION
The paper develops bidirectional methods for estimating Personalized PageRank and searching large target sets without scoring every candidate. Its algorithms exploit dot-product structure and PPR-proportional sampling, achieving substantial speedups and practical scalability.
- Problem: Personalized PageRank search ranks keyword-matching targets from a searcher’s perspective, addressing user-specific rankings in social networks.The paper motivates name search, such as finding people named John on Facebook, where results depend on the searcher and friendships.
- Problem: Θ(n2) storage for all user rankings and Θ(m) query-time computation for power iteration make naive personalized search infeasible.The target is a data structure smaller than O(n2) that ranks |T| targets in less than O(|T|) time.
- Bidirectional estimation: Bidirectional-PPR estimates are simple dot-products between forward and reverse vectors, enabling PPR samplers and distributed computation.The reverse vectors can be sharded across servers, while the estimator’s linear structure supports parallelization.
- PPR search: BiPPR-Precomp-Sampling samples targets proportional to their PPR, using skewed PPR values as a proxy for finding top results without scanning all candidates.The paper also describes grouped precomputation to exploit reverse-vector sparsity and speed runtime estimation.
- Evaluation: Twitter-2010 simulations demonstrate scalability and a storage-runtime trade-off, motivating different methods for different target-set sizes.The paper combines precomputation, sampling, sequential estimation, and Monte Carlo in its practical search algorithms.
2. PRELIMINARIES
The paper formalizes Personalized PageRank on a directed, possibly weighted graph using transition weights and a restart source distribution. It presents both a linear-algebraic definition and a random-walk interpretation.
- Graph model: The graph is G = (V, E), with n nodes and m edges; nodes have out-neighbors and weighted or unweighted outgoing transitions.For weighted graphs, positive edge weights are normalized so each node’s outgoing weights sum to one.
- Personalized PageRank: Personalized PageRank from source distribution σ to target t is defined as the solution to a linear-algebraic PageRank equation.The paper also gives an equivalent random-walk definition.
- Personalized PageRank: The paper often uses σ = e_s, meaning random walks start at a single node s, while the results extend to arbitrary starting distributions.This single-source case is used for concreteness rather than as a restriction of the framework.
- Background: Personalized PageRank was introduced in the original PageRank paper and has subsequent motivational and survey literature.The preliminaries point readers to prior references for additional background.
3. PAGERANK ESTIMATION
Bidirectional-PPR estimates personalized PageRank by combining reverse residual computation from the target with forward random walks from the source. It provides high-probability accuracy guarantees, supports extensions and distributed computation, and is substantially faster than prior estimators in experiments.
- Bidirectional-PPR Algorithm: Bidirectional-PPR first computes reverse contribution and residual vectors from target t, then estimates the residual expectation using random walks from source s.The estimator combines Approx-Contributions with forward walks whose terminal-node distribution is πs.
- Accuracy Guarantees: With probability at least 1 − pfail, the estimator achieves relative error ϵ when πs(t) ≥ δ and additive error 2eδ when πs(t) ≤ δ.The theorem requires rmax > 2eδ/(αϵ) and ϵ ≤ 1.
- Accuracy Guarantees: The estimator can distinguish significant from insignificant PPR pairs using its accuracy guarantee and threshold δ.The resulting estimate separates pairs above the minimum PPR threshold from pairs below it.
- Bidirectional-PPR Algorithm: The returned estimate is unbiased because it adds the reverse estimate pt(s) to the sampled residual average.The residual samples are bounded by rmax, enabling Monte Carlo concentration bounds.
- Efficiency: For uniformly random targets, Bidirectional-PPR has an asymptotically better running-time bound than FAST-PPR and is 3 to 8 times faster in experiments.Across diverse graphs, the reported speedup reflects smaller constants for the same accuracy as well as the improved bound.
- Extensions: The method extends to source distributions by sampling an independent starting node for each walk and replacing pt(s) with its expected value.A dynamic choice of rmax can further balance reverse computation against forward-walk generation in practice.
4. PERSONALIZED PAGERANK SEARCH
Personalized PageRank search ranks query-matching targets from a source user without scoring every candidate individually. The paper combines bidirectional estimation, precomputation, grouping, and PPR-proportional sampling to support fast search across target-set sizes, with storage and query-availability trade-offs.
- Problem: Personalized PageRank search returns the top-k targets in a query-filtered set T, ranked by πs[ti].The challenge is supporting user-specific rankings without infeasible per-user storage or graph-wide query-time computation.
- Baseline and precomputation: BiPPR-Precomp represents each target with a precomputed reverse vector and scores targets using dot-products with a query-time forward vector.It is faster than Bidirectional-PPR and Monte Carlo for small target sets, but its |T|-dependent scoring becomes too slow for large sets.
- Sampling: BiPPR-Precomp-Sampling samples targets approximately in proportion to πs[ti], identifying top-k candidates without computing every target score.The sampler uses expanded target-sets and can be built in average time O(rmax/δk), followed by O(1) sampling per target.
- Grouped scoring: BiPPR-Precomp-Grouped exploits shared coordinates among sparse reverse vectors to accelerate scoring across a target set.Its improved runtime requires additional storage, especially when targets contain many keywords.
- Experiments: On Twitter-2010, both precomputed methods remain below 250 ms with w = 10,000 and below 25 ms with w = 100,000 across tested target-set sizes.On Pokec, the same methods remain below 250 milliseconds across the tested range, while Monte Carlo and Bidirectional-PPR each dominate different target-set regimes.
5. RELATED WORK
The paper’s Bidirectional-PPR estimator improves on prior PPR estimation methods through a simpler linear structure that supports personalized search. Unlike approaches that approximate the full PPR vector, it computes only query-relevant entries.
- Bidirectional-PPR uses a forward vector and reverse vector whose dot product estimates πs(t), enabling its use for personalized search.
- Bidirectional-PPR is 3x-8x faster than FAST-PPR at the same accuracy across diverse networks.
- Its simpler linear structure yields simpler correctness proofs and performance analysis than FAST-PPR.
- The bidirectional approach computes only query-relevant πs(ti) entries instead of constructing a complete approximation to πs.
A. MORE EXPERIMENT PLOTS
Figure 5 compares search algorithms using median Precision@3 on Twitter-2010 under the same parameters as the w = 100,000 experiments. The precomputed variants share estimates and are plotted together.
- BiPPR-Precomp and BiPPR-Precomp-Grouped compute the same estimates.
- The precomputed variants have accuracy similar to Bidirectional-PPR, so they appear as a single accuracy line.