  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.
