Efficient Algorithms for Personalized PageRank Computation: A Survey

Abstract

Personalized PageRank (PPR) is a traditional measure for node proximity on large graphs. For a pair of nodes $s$ and $t$, the PPR value ${\pi }_s(t)$ equals the probability that an $\alpha$-discounted random walk from $s$ terminates at $t$ and reflects the importance between $s$ and $t$ in a bidirectional way. As a generalization of Google's celebrated PageRank centrality, PPR has been extensively studied and has found multifaceted applications in many fields, such as network analysis, graph mining, and graph machine learning. Despite numerous studies devoted to PPR over the decades, efficient computation of PPR remains a challenging problem, and there is a dearth of systematic summaries and comparisons of existing algorithms. In this paper, we recap several frequently used techniques for PPR computation and conduct a comprehensive survey of various recent PPR algorithms from an algorithmic perspective. We classify these approaches based on the types of queries they address and review their methodologies and contributions. We also discuss some representative algorithms for computing PPR on dynamic graphs and in parallel or distributed environments.

20 pages, "accepted version" of an article accepted by IEEE Transactions on Knowledge and Data Engineering (TKDE) for publication

References in corpus (14)

• Scaling Graph Neural Networks with Approximate PageRank
• VERSE: Versatile Graph Embeddings from Similarity Measures
• Personalized PageRank Estimation and Search: A Bidirectional Approach
• Fast Distributed PageRank Computation
• Personalized PageRank to a Target Node, Revisited
• Approximate Graph Propagation
• PowerWalk: Scalable Personalized PageRank via Random Walks with Vertex-Centric Decomposition
• Efficient Estimation of Heat Kernel PageRank for Local Clustering
• FREDE: Anytime Graph Embeddings
• Distributed Algorithms for Fully Personalized PageRank on Large Graphs
• Efficient and Effective Similarity Search over Bipartite Graphs
• Edge-based Local Push for Personalized PageRank
• Effective and Efficient PageRank-based Positioning for Graph Visualization
• Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond

Cited by in corpus (4)

• A Hybrid Similarity-Aware Graph Neural Network with Transformer for Node Classification
• Beyond Over-smoothing: Uncovering the Trainability Challenges in Deep Graph Neural Networks
• ALPHA-PIM: Analysis of Linear Algebraic Processing for High-Performance Graph Applications on a Real Processing-In-Memory System
• Matching Game Preferences Through Dialogical Large Language Models: A Perspective