One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor

Personalized PageRank (PPR) is a fundamental graph proximity measure with a wide range of applications. The single-source Personalized PageRank (SSPPR) query aims to compute the PPR values for all nodes from a given source node. Due to the high computational cost of exact SSPPR computation, most existing solutions focus on approximate queries with accuracy guarantees. The state-of-the-art approaches for approximate SSPPR queries are index-based and are typically designed for a single, fixed value of α. However, real-world applications often require handling multiple values of α, and current index-based methods struggle to adapt to varying values of α without rebuilding the index. To address this limitation, we propose a novel and efficient index approach for SSPPR queries that supports all values of α. A striking feature of our approach is that it stores only a single index for all possible values of α. This is achieved by leveraging the loop-erased α-random walk interpretation of PPR and constructing a stack-style meta-index with a sufficiently large damping factor ā, denoted as StackIndex. Then, we develop a novel technique to efficiently transform StackIndex into a new index for any specified damping factor α, without the need to rebuild the index. We show that our index construction algorithm requires around O (ω n ) time and O (ω n ) space to ensure approximation quality, where ω and n represent the sample size and the number of nodes in the graph, respectively. We also develop an index maintenance technique to update our StackIndex when handling dynamic graphs with edge insertions and deletions. Extensive experiments on 5 large real-world graphs demonstrate that StackIndex offers substantial speedups over previous index-based methods for PPR queries with different α while maintaining the same accuracy guarantee.