An Accelerated Newton-GMRES Method for Multilinear PageRank
This work addresses a bottleneck in modeling multiway relationships for applications like web ranking and social networks, offering an incremental improvement in computational methods.
The paper tackles the computational challenge of solving the multilinear PageRank problem for large-scale networks by proposing an accelerated Newton-GMRES method that uses Krylov subspace techniques and vector extrapolation to approximate Newton steps without forming large Jacobian matrices, resulting in significant improvements in efficiency, robustness, and scalability over classical solvers as demonstrated in experiments.
Modeling complex multiway relationships in large-scale networks is becoming more and more challenging in data science. The multilinear PageRank problem, arising naturally in the study of higher-order Markov chains, is a powerful framework for capturing such interactions, with applications in web ranking, recommendation systems, and social network analysis. It extends the classical Google PageRank model to a tensor-based formulation, leading to a nonlinear system that captures multi-way dependencies between states. Newton-based methods can achieve local quadratic convergence for this problem, but they require solving a large linear system at each iteration, which becomes too costly for large-scale applications. To address this challenge, we present an accelerated Newton-GMRES method that leverages Krylov subspace techniques to approximate the Newton step without explicitly forming the large Jacobian matrix. We further employ vector extrapolation methods, including Minimal Polynomial Extrapolation (MPE), Reduced Rank Extrapolation (RRE), and Anderson Acceleration (AA), to improve the convergence rate and enhance numerical stability. Extensive experiments on synthetic and real-world data demonstrate that the proposed approach significantly outperforms classical Newton-based solvers in terms of efficiency, robustness, and scalability.