A Survey on Personalized PageRank Computation Algorithms <s> B. OPTIMIZED DIRECT EQUATION SOLVING <s> M. S. BARTLETT (1951), An inverse matrix adjustment arising in discriminant analysis, Ann. Math. Statist., 22,pp. 107-111. E. BODEWIG (1959), Matrix Calculus, Second edition, North-Holland, Amsterdam, New York. A. S. HOUSEHOLDER (1964), Theory of Matrices in Numerical Analysis, Blaisdell, New York. W. W. PIEGORSCH AND G. CASELLA (1989), The early use of matrix diagonal increments in statistical problems, SIAM Rev., 31, pp. 428-434. J. SHERMAN AND W. J. MORRISON (1949), Adjustment of an inverse matrix corresponding to changes in the elements of a given column or given row of the original matrix, Ann. Math. Statist., 20, p. 621. M. A. WOODBURY (1950), Inverting modifed matrices, Tech. Report 42, Statistical Research Group, Princeton University, Princeton, NJ. <s> BIB001 </s> A Survey on Personalized PageRank Computation Algorithms <s> B. OPTIMIZED DIRECT EQUATION SOLVING <s> How closely related are two nodes in a graph? How to compute this score quickly, on huge, disk-resident, real graphs? Random walk with restart (RWR) provides a good relevance score between two nodes in a weighted graph, and it has been successfully used in numerous settings, like automatic captioning of images, generalizations to the "connection subgraphs", personalized PageRank, and many more. However, the straightforward implementations of RWR do not scale for large graphs, requiring either quadratic space and cubic pre-computation time, or slow response time on queries. We propose fast solutions to this problem. The heart of our approach is to exploit two important properties shared by many real graphs: (a) linear correlations and (b) block- wise, community-like structure. We exploit the linearity by using low-rank matrix approximation, and the community structure by graph partitioning, followed by the Sherman- Morrison lemma for matrix inversion. Experimental results on the Corel image and the DBLP dabasets demonstrate that our proposed methods achieve significant savings over the straightforward implementations: they can save several orders of magnitude in pre-computation and storage cost, and they achieve up to 150x speed up with 90%+ quality preservation. <s> BIB002 </s> A Survey on Personalized PageRank Computation Algorithms <s> B. OPTIMIZED DIRECT EQUATION SOLVING <s> Convex optimization problems arise frequently in many different fields. A comprehensive introduction to the subject, this book shows in detail how such problems can be solved numerically with great efficiency. The focus is on recognizing convex optimization problems and then finding the most appropriate technique for solving them. The text contains many worked examples and homework exercises and will appeal to students, researchers and practitioners in fields such as engineering, computer science, mathematics, statistics, finance, and economics. <s> BIB003 </s> A Survey on Personalized PageRank Computation Algorithms <s> B. OPTIMIZED DIRECT EQUATION SOLVING <s> Graphs are fundamental data structures and have been employed for centuries to model real-world systems and phenomena. Random walk with restart (RWR) provides a good proximity score between two nodes in a graph, and it has been successfully used in many applications such as automatic image captioning, recommender systems, and link prediction. The goal of this work is to find nodes that have top-k highest proximities for a given node. Previous approaches to this problem find nodes efficiently at the expense of exactness. The main motivation of this paper is to answer, in the affirmative, the question, 'Is it possible to improve the search time without sacrificing the exactness?'. Our solution, K-dash, is based on two ideas: (1) It computes the proximity of a selected node efficiently by sparse matrices, and (2) It skips unnecessary proximity computations when searching for the top-k nodes. Theoretical analyses show that K-dash guarantees result exactness. We perform comprehensive experiments to verify the efficiency of K-dash. The results show that K-dash can find top-k nodes significantly faster than the previous approaches while it guarantees exactness. <s> BIB004 </s> A Survey on Personalized PageRank Computation Algorithms <s> B. OPTIMIZED DIRECT EQUATION SOLVING <s> Given a large graph, how can we calculate the relevance between nodes fast and accurately? Random walk with restart (RWR) provides a good measure for this purpose and has been applied to diverse data mining applications including ranking, community detection, link prediction, and anomaly detection. Since calculating RWR from scratch takes long, various preprocessing methods, most of which are related to inverting adjacency matrices, have been proposed to speed up the calculation. However, these methods do not scale to large graphs because they usually produce large and dense matrices which do not fit into memory. In this paper, we propose BEAR, a fast, scalable, and accurate method for computing RWR on large graphs. BEAR comprises the preprocessing step and the query step. In the preprocessing step, BEAR reorders the adjacency matrix of a given graph so that it contains a large and easy-to-invert submatrix, and precomputes several matrices including the Schur complement of the submatrix. In the query step, BEAR computes the RWR scores for a given query node quickly using a block elimination approach with the matrices computed in the preprocessing step. Through extensive experiments, we show that BEAR significantly outperforms other state-of-the-art methods in terms of preprocessing and query speed, space efficiency, and accuracy. <s> BIB005
The direct equation solving method that solves linear equations by computing the inversions is not generally recommended due to its high complexity. However, when approximated answers are acceptable, revised versions of the method that produce approximated solutions can be an alternative method to solve PPR problems. One of pioneering studies in this category introduces the low rank approximation to reduce the inversion complexity BIB002 . They use singular value decomposition (SVD) for the low rank approximation. By using the Low rank approximation and Sherman-Morrison lemma BIB001 , it computes PPR using a smaller inversion matrix. It can be achieved as follows. WhenP = USV and˜ = (S −1 − cVU ) −1 , then (I − cP) −1 ∼ = (I − cU˜ V ) holds according to the Sherman-Morrison lemma. Since the dimension of S is far smaller than P, (I − cU˜ V ) can be computed more efficiently than (I − cP) −1 . This method provides a good approximation for PPR problem; however, its error bound is hard to control. They reported that their algorithm performs better than direct inversion and the power iteration. However, they use a relatively small graph (with 315K nodes) in the experiment. There is also a study that optimizes direct equation solving without introducing the approximation BIB004 . They reorder the dimensions of the overall equations before the inversion to preserve the sparsity of the original matrix. Generally, matrix inversion can be computed via LU decomposition, and the result is computed as U −1 L −1 . With the proper reordering, the sparsity of the original matrix is also preserved with respect to U −1 and L −1 , and the sparse matrices can be stored and processed more efficiently than dense matrices. Though it can efficiently process queries (one matrixvector multiplication per each query), it requires massive precomputation time since it performs LU decomposition that requires over O(N 2 ) time. Considering that the size of the datasets used in their experiments are relatively small (under 300K nodes), it is hard to say whether it can work with very large graphs with over 10M nodes. BEAR (Block Elimination Approach for Random Walk with Restart on Large Graphs) is one of important recent advancement BIB005 . It basically follows the studies of the optimized direct equation solving category according to our taxonomy. BEAR reduced the dimension of the matrix that is to be inverted by the block elimination using the Schur complement method BIB003 . When using the Schur complement method, we need to invert only some submatrices and the Schur complement matrix, which is smaller than the whole matrix. For an effective application of the Schur complement method, the adjacency matrix should have a large and easyto-invert submatrix such as a block diagonal matrix. The BEAR utilizes reordering and clustering to easily invert a system matrix, similar to in Fujiwara et al. BIB004 . BEAR decomposed the graph into hubs and spokes. Within each connected component containing spokes, BEAR reorders the nodes in ascending order of the degrees within the component. As a result, BEAR can get an adjacency matrix whose upperleft area is a large and sparse block diagonal matrix that is easily inverted, while the lower-right area is a small but dense matrix. In the rest of the preprocessing step, BEAR precomputes several matrices including the Schur complement. To solve the equation using the block elimination method, it requires inverting the Schur complement matrix and block diagonal submatrix. BEAR inverts these matrices using LU decomposition. In the query phase, the BEAR quickly computes PPR scores for a given query node using the matrices that are computed in the preprocessing step. The BEAR takes less time and memory space than other preprocessing methods. Their experiments show that their algorithm runs 300 times faster than the simple iterative method.