A Survey on Personalized PageRank Computation Algorithms <s> A. OPTIMIZED ITERATIVE EQUATION SOLVING <s> We present a novel algorithm for the fast computation of PageRank, a hyperlink-based estimate of the ''importance'' of Web pages. The original PageRank algorithm uses the Power Method to compute successive iterates that converge to the principal eigenvector of the Markov matrix representing the Web link graph. The algorithm presented here, called Quadratic Extrapolation, accelerates the convergence of the Power Method by periodically subtracting off estimates of the nonprincipal eigenvectors from the current iterate of the Power Method. In Quadratic Extrapolation, we take advantage of the fact that the first eigenvalue of a Markov matrix is known to be 1 to compute the nonprincipal eigenvectors using successive iterates of the Power Method. Empirically, we show that using Quadratic Extrapolation speeds up PageRank computation by 25-300% on a Web graph of 80 million nodes, with minimal overhead. Our contribution is useful to the PageRank community and the numerical linear algebra community in general, as it is a fast method for determining the dominant eigenvector of a matrix that is too large for standard fast methods to be practical. <s> BIB001 </s> A Survey on Personalized PageRank Computation Algorithms <s> A. OPTIMIZED ITERATIVE EQUATION SOLVING <s> We propose a new scalable algorithm that can compute Personalized PageRank (PPR) very quickly. The Power method is a state-of-the-art algorithm for computing exact PPR; however, it requires many iterations. Thus reducing the number of iterations is the main challenge. ::: ::: We achieve this by exploiting graph structures of web graphs and social networks. The convergence of our algorithm is very fast. In fact, it requires up to 7.5 times fewer iterations than the Power method and is up to five times faster in actual computation time. ::: ::: To the best of our knowledge, this is the first time to use graph structures explicitly to solve PPR quickly. Our contributions can be summarized as follows. ::: ::: 1. We provide an algorithm for computing a tree decomposition, which is more efficient and scalable than any previous algorithm. ::: ::: 2. Using the above algorithm, we can obtain a core-tree decomposition of any web graph and social network. This allows us to decompose a web graph and a social network into (1) the core, which behaves like an expander graph, and (2) a small tree-width graph, which behaves like a tree in an algorithmic sense. ::: ::: 3. We apply a direct method to the small tree-width graph to construct an LU decomposition. ::: ::: 4. Building on the LU decomposition and using it as pre-conditoner, we apply GMRES method (a state-of-the-art advanced iterative method) to compute PPR for whole web graphs and social networks. <s> BIB002
These studies can be viewed as advanced versions of the power iteration. Actually, the power iteration itself is identical to the Jacobi method, which is the most basic iterative method of solving general linear equations. Since equation (4) is a linear equation, any iterative method for linear equation solving can be applied, and as we stated in section 2.D, PPR equation converges to the unique solution with iterative methods due to its mathematical properties. Therefore, linear equation solving algorithms such as the Gauss-Seidel method, Successive Overrelaxation (SOR), GMRES, and Multigrid methods can be applied to the problem. Though these iterative methods cannot produce exact solutions to the problems, their errors can be controlled and the error bound can be strictly defined unlike other approximation algorithms such as samplingbased methods. On the top of applying those general equation solvers, diverse techniques are devised for the specific problem of computing PPR. One of the most recent studies in this category utilizes the GMRES BIB002 . They utilize the GMRES for solving the equation (4), and applied a preconditioning method to accelerate the convergence of iterative algorithm. General concept of preconditioning is solving MA The matrix M is called the preconditioner, and a well-chosen preconditioner reduces the number of iterations. It is known that the matrices that are close to A −1 can be good preconditioners. To construct a good preconditioner, they apply coretree decomposition. They use an inversion of the tree-like part of the original graph as a preconditioner. The following table shows the result of the performance evaluation. Overall, their method performs better than the power iteration and naïve GMRES. They report that their algorithm reduces the iteration count to achieve the same accuracy by 1/5 comparing to power iteration and 1/3 to naïve GMRES. However, their algorithm still requires several minutes to process each query on large graphs with millions of nodes. Additionally, there are several studies seeking to accelerate the iterative method by tuning the power iteration. The extrapolation method is an example of the approach BIB001 . They accelerate the power iteration by subtracting nonprincipal eigenvectors periodically. They report that the extrapolation method can reduce the number of iterations of the power iteration by 1/2. It is an effective methods to solve the problem, but it is developed mainly for PageRank problem and its scalability for PPR computation is not guaranteed.