Personalized PageRank Estimation and Search: A Bidirectional Approach

Abstract

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.

WSDM 2016

References in corpus (5)

• Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)
• Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)
• FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs
• Efficient Algorithms for Personalized PageRank
• Fast Bidirectional Probability Estimation in Markov Models

Cited by in corpus (18)

• Scaling Graph Neural Networks with Approximate PageRank
• Personalized PageRank to a Target Node, Revisited
• Efficient Algorithms for Personalized PageRank Computation: A Survey
• PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs
• Inequality and Inequity in Network-based Ranking and Recommendation Algorithms
• Efficient Estimation of Heat Kernel PageRank for Local Clustering
• Distributed Algorithms for Fully Personalized PageRank on Large Graphs
• Efficient Algorithms for Personalized PageRank
• Efficient and Effective Similarity Search over Bipartite Graphs
• Efficient Estimation of Pairwise Effective Resistance
• Edge-based Local Push for Personalized PageRank
• Effective and Efficient PageRank-based Positioning for Graph Visualization
• The Impact of Global Structural Information in Graph Neural Networks Applications
• Towards Deeper Understanding of PPR-based Embedding Approaches: A Topological Perspective
• Deep Node Ranking for Neuro-symbolic Structural Node Embedding and Classification
• Revisiting Local Computation of PageRank: Simple and Optimal
• On the role of clustering in Personalized PageRank estimation
• Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal