Extrapolation methods for fixed-point multilinear PageRank computations

Abstract

Nonnegative tensors arise very naturally in many applications that involve large and complex data flows. Due to the relatively small requirement in terms of memory storage and number of operations per step, the (shifted) higher-order power method is one of the most commonly used technique for the computation of positive Z-eigenvectors of this type of tensors. However, unlike the matrix case, the method may fail to converge even for irreducible tensors. Moreover, when it converges, its convergence rate can be very slow. These two drawbacks often make the computation of the eigenvectors demanding or unfeasible for large problems. In this work we consider a particular class of nonnegative tensors associated to the multilinear PageRank modification of higher-order Markov chains. Based on the simplified topological $\epsilon$-algorithm in its restarted form, we introduce an extrapolation-based acceleration of power method type algorithms, namely the shifted fixed-point method and the inner-outer method. The accelerated methods show remarkably better performance, with faster convergence rates and reduced overall computational time. Extensive numerical experiments on synthetic and real-world datasets demonstrate the advantages of the introduced extrapolation techniques.

Please cite this work as:

@article{cipolla2020extrapolation,
  title={Extrapolation methods for fixed-point multilinear PageRank computations},
  author={Cipolla, Stefano and Redivo-Zaglia, Michela and Tudisco, Francesco},
  journal={Numerical Linear Algebra with Applications},
  volume={27},
  number={2},
  pages={e2280},
  year={2020},
  publisher={Wiley Online Library}
}

Keywords: nonnegative tensors pagerank higher-order Markov chain extrapolation power method