Partially‐Updating Extrapolation Methods for Multilinear PageRank

ABSTRACT Multilinear PageRank is an extension of the famous PageRank to higher order Markov chain. The minimal polynomial extrapolation method is an efficient way to speed up the fixed‐point iteration for multilinear PageRank computation. However, the storage requirements of the minimal polynomial extrapolation method bring us an enormous burden when the size of the problem is very large. Thus, it is interesting to seek new technologies that can reduce memory consumption while achieving acceleration simultaneously. On the other hand, it is only necessary to rank some of the most important elements of multilinear PageRank, in practice, rather than all of them. In this work, we first propose a partially updating extrapolation method for speeding up multilinear PageRank. Second, to further enhance the accuracy of some less important elements in the computed solution, we present a partially updating fixed‐point iteration for multilinear PageRank, and propose an improved partially updating extrapolation method. The idea is to use some important elements (i.e., we are interested in) to refine the accuracy of the less important ones. Third, theoretical analysis is given to justify the validity of the partially updating fixed‐point iteration, and the convergence behavior of the improved partially updating extrapolation method is investigated. Comprehensive numerical experiments on some real‐world data sets show that the proposed methods can reduce memory usage and accelerate computations. In particular, they are competitive candidates for large‐scale and difficult multilinear PageRank problems.