A Sparse Power Method With Extrapolation for the Higher-Order Pagerank Problem

doi:10.1002/nla.70042

2025-10-01

PRE

Shengwei Zhou

Gang Wu *

DOI：10.1002/nla.70042

原文链接

原文求助

摘要

En 中文

高阶马尔可夫链在分析高维数据和建模多关系问题中扮演着重要角色。作为应用，高阶PageRank是Google PageRank的一种推广。对于该问题，挑战在于如何既快速又准确地求解高阶PageRank。外推法是大规模科学计算的有效加速技术。据我们所知，目前尚无用于高阶PageRank问题的外推加速方法。其中一个原因是高阶PageRank问题的稳态分布是大规模且密集的数据集，现有外推方法无法直接应用于此问题。由稀疏幂方法生成的高阶PageRank是高阶PageRank的一个良好替代方案，其中密集的高阶PageRank通过稀疏分量和秩一分量的组合进行近似。在本工作中，我们提出了一种带外推的稀疏幂方法。其思路是先在秩一分量上运行外推方法并获取权重系数，然后将这些系数同时应用于稀疏分量和秩一分量。然而，难点在于从理论上证明这种方法为何有效。为解决这一问题，我们论证了我们所提策略的合理性，并证明了该方法比原始稀疏幂方法具有更快的收敛速度。在真实世界和合成数据库上的大量数值实验验证了所提方法的有效性，并展示了我们理论结果的有效性。

Keyword:

extrapolation

higher-order PageRank

multilinear PageRank

PageRank

sparse power method