Multilinear PageRank

David F. Gleich, Lek-Heng Lim, Yongyang Yu

Abstract: Standard PageRank algorithms operate on first-order Markov processes, where future states depend only on the current position. However, many real-world systems exhibit higher-order dependencies. While higher-order Markov chains can model these dependencies, they suffer from an exponential explosion in memory requirements. "Multilinear PageRank" introduces a framework to approximate these memory-dependent random walks using a system of polynomial equations. This paper explores the theoretical foundations, physical interpretations like the "spacey random surfer," and robust numerical solvers required to handle the non-linearities inherent in this higher-order approach.

Introduction

The PageRank algorithm revolutionized web search by modeling the importance of nodes based on a random surfer's behavior. Yet, the assumption that a surfer's next move is independent of their history is often a simplification. In biological networks or complex web navigation, history matters. Modeling this with higher-order Markov chains typically requires $O(n^m)$ memory for $m$ steps of history, making it impractical for large-scale graphs. Multilinear PageRank offers a solution by using a multilinear approximation that captures higher-order effects without the memory explosion.

The Challenge of Higher-Order Memory

Modeling a process where the next state depends on the previous $m-1$ states leads to a state-space explosion. For a graph with $n$ nodes, a second-order chain has $n^2$ states.

The transition matrix structure for a higher-order Markov chain illustrates the complexity and sparsity patterns involved in modeling memory-dependent transitions.

As shown in the transition matrix structure above, the complexity grows rapidly, necessitating more efficient representations. The authors tackle this by resulting in a system of non-linear equations rather than a simple linear system, allowing for the capture of higher-order effects without the exponential memory overhead.

The Multilinear PageRank Framework

The core of the paper is the Multilinear PageRank equation: $$x = \alpha \mathbf{P}x^{(m-1)} + (1-\alpha)v$$ Where $x$ is the importance vector, $\mathbf{P}$ is a transition tensor, and $v$ is the teleportation vector.

To provide a physical intuition, the authors introduce the "Spacey Random Surfer." In this model, a surfer occasionally "spaces out" and forgets their immediate history, instead choosing their next destination based on the aggregate frequency of all their past visits—a concept known as a vertex-reinforced random walk.

Comparison between a standard higher-order Markov chain (a) and the proposed higher-order PageRank chain (b), showing the addition of teleportation edges (red) that regularize the system.

Theory and Algorithms

Unlike the linear PageRank system, Multilinear PageRank does not always have a unique solution. The authors prove uniqueness is guaranteed only when the teleportation probability $\alpha$ is small ($\alpha < 1/(m-1)$). As $\alpha$ approaches 1, the system can exhibit multiple solutions or oscillatory behavior.

To solve these systems, the paper evaluates several algorithms:

  1. Fixed-point iteration: The standard "power method" approach.
  2. Shifted fixed-point: Adds a damping term ($\gamma$) to prevent oscillations.
  3. Newton’s Method: A second-order solver with a custom projection step to ensure the solution stays as a valid probability distribution (the "probability simplex").

Key Results

The study highlights a fundamental phase transition in solver reliability. For difficult cases with high $\alpha$ (e.g., 0.99), standard fixed-point methods often fail. In a test of 29 difficult problems:

  • The standard Fixed-point method solved only 5.
  • The Shifted method solved 9.
  • Newton’s method solved 28.

The authors also proved that Newton's method converges quadratically when inside the unique regime, making it highly efficient for the problems it can handle.

Conclusion

Multilinear PageRank provides a mathematically rigorous yet computationally feasible way to incorporate history into graph-based ranking. While Newton's method offers superior robustness, its scalability for massive, web-scale graphs remains a challenge due to the need for Jacobian approximations. Future work aims to apply these methods to large-scale bioinformatics and social network datasets to determine if the multilinear approach provides better insights than standard PageRank.

Summary updated

Abstract

In this paper, we first extend the celebrated PageRank modification to a higher-order Markov chain. Although this system has attractive theoretical properties, it is computationally intractable for many interesting problems. We next study a computationally tractable approximation to the higher-order PageRank vector that involves a system of polynomial equations called multilinear PageRank, which is a type of tensor PageRank vector. It is motivated by a novel "spacey random surfer" model, where the surfer remembers bits and pieces of history and is influenced by this information. The underlying stochastic process is an instance of a vertex-reinforced random walk. We develop convergence theory for a simple fixed-point method, a shifted fixed-point method, and a Newton iteration in a particular parameter regime. In marked contrast to the case of the PageRank vector of a Markov chain where the solution is always unique and easy to compute, there are parameter regimes of multilinear PageRank where solutions are not unique and simple algorithms do not converge. We provide a repository of these non-convergent cases that we encountered through exhaustive enumeration and randomly sampling that we believe is useful for future study of the problem.
BibTeX
@article{gleich2015multilinear,
  author = {David F. Gleich and Lek-Heng Lim and Yongyang Yu},
  title = {{Multilinear PageRank}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2015},
  doi = {10.1137/140985160},
}
Figure