Fast Personalized PageRank for Customized Analysis Range Using Static Index
Tsuyoshi Yamashita, Kunitake Kaneko · 2024
PPR is an essential computation for customized graph analysis, and its fast computation methods have been proposed. FORA +, one of the fastest methods, introduces an index to speed up PPR computation by referencing the end nodes of pre-generated random walks with a specific termination probability$\alpha_{index}$. Although for customized graph analysis, it is essential to query with different termination probabilities$\alpha$for controlling the analysis range, FORA + does not contribute to the speedup for such different$\alpha$other than the$\alpha_{index}$. This paper proposes a method to quickly determine the end nodes of random walks for arbitrary termination probabilities$\alpha (\leq\alpha_{index})$by focusing on the fact that the random walks become probabilistically longer as the termination probability decreases. In particular, we repeatedly reference the index based on the probability$p$defined by$\alpha_{index}$and$\alpha$to make the longer random walks. By defining$p$according to mathematical considerations, the results of our method are guaranteed. In addition, our method can be used in FORA + without modifying its index structure. We incorporate our method into FORA + and evaluate the processing time using six real-world graph datasets. As a result, our method achieves up to 19.8 times speedup over the existing index-free method.