.png){kind=icon}
.png){kind=icon}
Return
A Sparse Power Method With Extrapolation for the Higher-Order Pagerank Problem
.png){kind=icon}
PRE
AI
DOI：10.1002/nla.70042.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Higher-order Markov chain plays an important role in high-dimensional data analysis and modeling multi-relational problems. As an application, higher-order PageRank is a generalization to Google's PageRank. For this problem, the challenge is how to solve higher-order PageRank both rapidly and accurately. Extrapolation methods are effectively accelerating techniques for large-scale scientific computations. As far as we know, there are no extrapolation accelerated methods for higher-order PageRank problem. One reason is that the stationary distribution of the higher-order PageRank problem is a large-scale and dense dataset, and existing extrapolation methods cannot apply to this problem directly. Sparse higher-order PageRank generated by the sparse power method is a good alternative to higher-order PageRank, in which the dense higher-order PageRank is approximated by using a combination of a sparse component and a rank-one component. In this work, we propose a sparse power method with extrapolation. The idea is to run the extrapolation method on the rank-one component and get the weighting coefficients first, and then apply the coefficients to both the sparse component and the rank-one component simultaneously. However, the difficulty is to show why this works theoretically. To settle this problem, we demonstrate the rationality of our strategy, and prove that the proposed method can converge faster than the original sparse power method. Extensive numerical experiments on both real-world and synthetic database illustrate the efficiency of the proposed method, and show the effectiveness of our theoretical results.
Keywords:
extrapolation
higher-order PageRank
multilinear PageRank
PageRank
sparse power method
Journal
N
IF:
2.1
Papers:
47
Citations:
2.1K
Organization
No organization information available