Fast Personalized PageRank Computation on Very Large Graphs
Information
Abstract
Computation of Personalized PageRank (PPR) in graphs is an important function that is widely utilized in myriad application domains such as search, recommendation, and knowledge discovery. Because the computation of PPR is an expensive process, a good number of innovative and efficient algorithms for computing PPR have been developed. However, efficient computation of PPR within very large graphs with over millions of nodes is still an open problem. Moreover, previously proposed algorithms cannot handle updates efficiently, thus, severely limiting their capability of handling dynamic graphs. In this paper, we present a fast converging algorithm that guarantees high and controlled precision. We improve the convergence rate of traditional Power Iteration method by adopting successive over-relaxation, and initial guess revision, a vector reuse strategy. The proposed method vastly improves on the traditional Power Iteration in terms of convergence rate and computation time, while retaining its simplicity and strictness. Since it can reuse the previously computed vectors for refreshing PPR vectors, its update performance is also greatly enhanced.
Abstract (Korean)
그래프 내에서 개인화된 페이지랭크 (Personalized PageRank, PPR)를 계산하는 것은 검색, 추천, 지식발견 등 여러 분야에서 광범위하게 활용되는 중요한 작업이다. 개인화된 페이지랭크를 계산하는 것은 고비용의 과정이 필요하므로, 개인화된 페이지랭크를 계산하는 효율적이고 혁신적인 방법들이 다수 개발되어왔다. 그러나 수백만 이상의 노드를 가진 대용량 그래프에 대한 효율적인 계산은 여전히 해결되지 않은 문제이다. 그에 더하여, 기존 제시된 알고리즘들은 그래프 갱신을 효율적으로 다루지 못하여 동적으로 변화하는 그래프를 다루는 데에 한계점이 크다. 본 연구에서는 높은 정밀도를 보장하고 정밀도를 통제 가능한, 빠르게 수렴하는 개인화된 페이지랭크 계산 알고리즘을 제시한다.