PaperlayerView exact revision on arXiv

Source-linked AI summary

Multilinear PageRank

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

arXiv:1409.1465v1math.NAcs.NA

TL;DR

Higher-order PageRank has attractive theoretical properties but can be computationally intractable because its stationary distribution requires large product-space storage. The paper studies the multilinear PageRank approximation and its spacey random surfer interpretation, along with the existence, uniqueness, and convergence behavior of solution methods. The authors find that uniqueness holds below a parameter threshold and that inner-outer and Newton methods are most reliable on challenging tested cases.

  • Problem

    Higher-order PageRank retains attractive properties but can require O(n2) memory for a second-order chain, making the full stationary distribution difficult to scale.

    Source: §4 · p. 8

  • Method

    The paper combines a rank-1 approximation of higher-order stationary distributions with a spacey random surfer model and analyzes iterative solution methods.

    Source: §1 · p. 2, §3 · p. 5, §4.1 · p. 10

  • Results

    On challenging cases where fixed-point and shifted fixed-point methods fail, inner-outer and Newton iterations perform best; multilinear PageRank solutions are unique when α < 1/(m −1).

    Source: §1 · p. 2, §7 · p. 27

  • Takeaways & Limitations

    The findings suggest trying the shifted method first, then using Newton or inner-outer iteration if it does not appear to converge.

    Source: §7 · p. 27

    The empirical findings are limited to the third-order case, and the authors have not found algorithms with guaranteed convergence when α > 1/(m −1).

    Source: §7 · pp. 27–28

Abstract

from arXiv · show

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.

1. Introduction.

The paper extends PageRank to higher-order Markov chains, then develops a tractable approximation motivated by a history-dependent random surfer. It studies when the resulting multilinear PageRank solutions and algorithms are reliable, contrasting that behavior with ordinary PageRank’s uniqueness and fast convergence.

1. Introduction.

  • PageRank’s uniqueness, fast convergence, and teleportation-based regularization help explain its success across graph applications.The paper argues these properties support reliable evaluation of important nodes despite modeling or sampling errors.Source: §1 · p. 1
  • Higher-order PageRank preserves the uniqueness and fast-convergence properties of ordinary PageRank, but computing its stationary distribution can require prohibitive memory.Higher-order chains depend on more history than the previous state; a second-order chain depends on the last two states.Source: §1 · pp. 1–2
  • The multilinear PageRank problem combines the higher-order PageRank modification with Li and Ng’s rank-1 approximation of the stationary distribution.For a second-order chain, its transition probabilities are represented by an n × n × n table and the approximation leads to polynomial equations.Source: §1 · p. 2
  • The spacey random surfer forgets its immediate history but uses aggregate history together with its current state to choose the next state.The paper connects this process to vertex-reinforced random walks.Source: §1 · p. 2
  • Unlike tensor decomposition approaches, the paper seeks a stationary distribution with a natural interpretation for a stochastic process represented by a probability table.The authors motivate this approach by the breadth of tensor applications and the desire for a meaningful, quickly computable distribution.Source: §1 · p. 2
  • Multilinear PageRank solutions are unique only when α < 1/(m −1); outside that regime, the authors’ methods can fail to converge, with inner-outer and Newton iterations most reliable on challenging cases.The authors assembled non-convergent cases through exhaustive enumeration and random sampling.Source: §1 · p. 2

2. Background.

The background establishes the notation and ordinary PageRank framework, then recasts higher-order chains on a product state space. It also introduces Li and Ng’s rank-1 approximation as a tractable alternative to storing the full higher-order stationary distribution.

2.1. Notation.

  • The paper distinguishes matrices, vectors, and tensors typographically, uses ⊗ for the Kronecker product, and calls nonnegative matrices with unit column sums column-stochastic.It cautions that its use of “tensor” refers more precisely to a coordinate representation, or hypermatrix.Source: §2.1 · p. 3

2.2. PageRank.

  • Ordinary PageRank uses a unique stationary vector for a random surfer that follows the Markov chain with probability α and teleports according to v otherwise.For common practical values of α between 0.5 and 0.99, the simple Richardson iteration converges quickly.Source: §2.2 · p. 3

2.3. Higher-order Markov chains.

  • An mth-order Markov chain depends on its m most recent states and can be represented as a first-order chain on a Cartesian-product state space.For a second-order chain, the stationary distribution is an n^2 × n^2 eigenvector problem; a 100,000-state example requires 10 billion entries.Source: §2.3 · p. 4

2.4. Li and Ng’s approximation.

  • Li and Ng’s approximation replaces each joint stationary probability X_ij with the product x_i x_j, yielding a tensor eigenvalue problem for x.This rank-1 substitution is presented as a computationally tractable alternative to working with the full product-space distribution.Source: §2.4 · p. 4

3. Higher-order PageRank.

The paper defines higher-order PageRank as the stationary distribution of a PageRank-modified higher-order chain, then relates that distribution to an ordinary PageRank problem on the reduced product space. The construction retains uniqueness and convergence guarantees, but the full stationary distribution has substantial memory costs.

3. Higher-order PageRank.

  • The higher-order PageRank tensor is the stationary distribution of the reduced chain, with entries indexed by the corresponding sequence of states.The transition rule combines the higher-order transition probability with teleportation mass (1 −α)vi.Source: §3 · pp. 4–5
  • The reduced higher-order PageRank chain need not have a complete set of transitions, unlike the PageRank modification of a first-order chain.The figure caption gives the missing transition ⟨2, 3⟩ to ⟨1, 3⟩ as an example.Source: Figure 1 · p. 6
  • Higher-order PageRank on the reduced product space is equivalent to an ordinary PageRank problem after m −1 steps, with teleportation parameter 1 −(1 −α)m−1.The equivalent PageRank problem uses a product distribution formed from m −1 copies of v.Source: §3 · pp. 6–7
  • The higher-order PageRank stationary distribution always exists and is unique, and the standard PageRank iteration converges with a stated 1-norm error bound.The bound is 2[1 −(1 −α)m−1]^k after (m −1)k iterations.Source: §3 · p. 8
  • The full second-order stationary distribution requires O(n2) memory, which quickly becomes infeasible as the number of states grows.The paper motivates the Li and Ng approximation as a way to address this scalability limit.Source: §4 · p. 8

4. Multilinear PageRank.

Multilinear PageRank uses a rank-1 approximation of a higher-order stationary distribution to form a polynomial system, and is motivated by a history-dependent spacey random surfer. The section establishes existence, parameter-conditional uniqueness, equivalence to ordinary PageRank in a special case, and a sparse-data operator construction.

4. Multilinear PageRank.

  • The Li–Ng rank-1 approximation yields a polynomial system for the multilinear PageRank vector, x = αP x^(m−1) + (1−α)v.The tensor represents an (m−1)th-order Markov chain; R is its stochastic flattening along the first index.Source: §4 · p. 9
  • A multilinear PageRank vector always exists, but it may not be unique: in one example, both [0, 1, 0]^T and [0.1890, 0.3663, 0.4447]^T solve the problem.Source: §4 · pp. 9–10

4.1. A stochastic process: the spacey random surfer.

  • The spacey random surfer forgets the prior state, guesses from visit frequencies, and forms a vertex-reinforced random walk whose stationary distributions solve the multilinear PageRank problem.The paper presents the connection between the process and the equation as a heuristic justification.Source: §4.1 · pp. 10–11

4.2. Sufficient conditions for uniqueness.

  • For order-m tensors, uniqueness is guaranteed when α < 1/(m−1); for third-order tensors, the sufficient condition is α < 1/2.The paper establishes this as a sufficient condition, not as a characterization of all cases with unique solutions.Source: §4.2 · pp. 11–12

4.3. Uniqueness via Li and Ng’s results.

  • The Li–Ng β > 1 uniqueness condition is stronger than the paper’s α < 1/2 condition for third-order problems.The paper defers the derivation of this comparison to its appendix.Source: §4.3 · p. 13

4.4. PageRank and higher-order PageRank.

  • When the flattened tensor is R = e^T ⊗ Q, the multilinear PageRank vector and higher-order PageRank marginal equal the ordinary PageRank vector for Q.This equivalence holds for all 0 < α < 1 and stochastic vectors v.Source: §4.4 · p. 13

4.5. Fast operators from sparse data.

  • For sparse Q with entries at most 1, a dangling-case correction yields a stochastic model whose operator evaluation takes work proportional to Q’s nonzeros.The construction generalizes the PageRank dangling indicator correction.Source: §4.5 · pp. 13–14

5. Algorithms for Multilinear PageRank.

The section examines algorithms for multilinear PageRank, covering convergence guarantees in specified parameter regimes and how methods behave outside them. It also describes a projected Newton iteration that keeps iterates stochastic.

5.1. The fixed-point iteration.

  • For α < 1/(m−1), the fixed-point iteration converges to the unique multilinear PageRank solution, but examples outside this regime can fail to converge.The authors show R1 converges with α = 0.95 but not with α = 0.96.Source: §5.1 · p. 15

5.2. The shifted fixed-point iteration.

  • When α > 1/(m−1), shifting with γ ≥ (m−2)/2 is recommended for general convergence; smaller shifts may fail, although γ = 1/2 rescues R1 at α = 0.96.For α < 1/(m−1), the shifted iteration converges to the unique solution; the general-convergence shift threshold follows from a necessary stability condition.Source: §5.2 · pp. 16–17

5.3. An inner-outer iteration.

  • The inner-outer method converges to the unique solution for α < 1/(m−1), but each iteration is more expensive and the method can fail at α = 0.99.Each step solves a unique multilinear PageRank subproblem; the method may be the only option when P is available only through a fast operator.Source: §5.3 · p. 18

5.4. An inverse iteration.

  • The inverse iteration converges to the unique solution for α < 1/(m−1), but requires detailed access to P to form S(xk) or compute S(xk)z.The authors report convergence behavior like the inner-outer method on the illustrated problems.Source: §5.4 · p. 20

5.5. Newton’s method.

  • For third-order stochastic tensors and α < 1/2, Newton’s method produces a unique well-defined sequence of iterates that converges quadratically to the unique solution.The proof establishes that the Jacobian remains nonsingular along the iteration.Source: §5.5 · pp. 20–21
  • When α < 1/2, the Newton iteration from Theorem 5.6 gradually grows the solution until it becomes stochastic and attains optimality.For α > 1/2, it often instead converges to a non-stochastic fixed point.Source: §5.5 · p. 22
  • For α > 1/2, the basic Newton iteration often converges to a non-stochastic fixed point, so the authors project each step onto the probability simplex.The projection sets negative elements to zero and normalizes the remaining elements to sum to one; in the R2, α = 0.99 example, the projected iteration converges while the unprojected one does not.Source: §5.5 · p. 23, Figure 6 · p. 23
  • The Jacobian system used by Newton’s method may be singular, although the authors did not encounter this in their experiments or study.The projected iteration was found superior to other tested choices, including a proximal point projection that also produces stochastic iterates.Source: §5.5 · p. 23
  • Newton’s method solves R2 with α = 0.99 in a few iterations, although neither inner-outer nor inverse iteration converges on that problem.Compared with both methods, Newton requires even more direct access to P to solve for steps with the Jacobian.Source: §5.5 · p. 23

6. Experimental Results.

The experiments probe difficult multilinear PageRank instances and compare convergence across iterative solvers. On these cases, inner-outer and Newton iterations are most reliable, while shifted-method reliability depends on the shift and α.

6. Experimental Results.

  • The experiments define success as a residual below 10−8 within the iteration limit, with trials running up to 10,000–100,000 iterations.The methods were evaluated as α varied, using v = e/n.Source: §6 · pp. 23–24
  • Newton’s iterates converged on R2 at α = 0.97 and 0.99, unlike the inner-outer and inverse iterations on the latter case.Newton requires more direct access to P to compute Jacobian steps.Source: Figure 7 · p. 24

6.1. Problems.

  • The test set combines exhaustively enumerated small binary tensors, randomly sampled 4 × 4 × 4 cases, and adversarially generated 6 × 6 × 6 cases.The 6 × 6 × 6 problems were designed to have strong directionality; symbolic computation often found multiple solutions for them, while the smaller tested problems had single solutions.Source: §6.1 · p. 24

6.2. Shifted iteration.

  • For R4,11 at α = 0.99, the shifted method began converging only above a shift between γ = 0.554 and γ = 0.5545, and γ = 1 converged rapidly.Across the 29 test problems, γ = 1 or 2 was most reliable; the authors recommend γ = 1 for third-order problems or γ = m − 2 for order-m tensors, while noting the test set was selected partly for failures at γ = 0 and 1/2.Source: §6.2 · p. 25, Figure 8 · p. 25, Table 1 · p. 26

6.3. Solver reliability.

  • Inner-outer and Newton methods were most reliable on the difficult test problems, and Newton solved all but R6,3 at α = 0.99.Under the default settings, none of the methods found R6,3’s true solution; Newton did find it from random starting points.Source: §6.3 · p. 26, Table 2 · p. 27
  • Higher-order PageRank guarantees uniqueness and fast convergence, whereas multilinear PageRank guarantees these properties only in a narrower regime.Outside that regime, a solution is guaranteed to exist, but uniqueness is not.Source: §7 · p. 27

7. Discussion.

Outside the uniqueness regime, multilinear PageRank solver convergence depends strongly on the data. The authors propose trying the shifted method first, then Newton or inner-outer iteration if it does not converge, while noting limits in scope and guarantees.

7. Discussion.

  • On difficult cases selected where fixed-point and shifted methods fail, inner-outer and Newton iterations perform best, motivating a shifted-first strategy with either as fallback.The empirical findings are limited to third-order problems.Source: §7 · p. 27
  • For R6,3 at α = 0.99, all default iterations were attracted to a small-residual point with an indefinite Jacobian, although random-start Newton sometimes found the sole solution.The authors identify this case as useful for future algorithmic studies.Source: Figure 9 · p. 28
  • When O(n^2) memory is available, the authors favor higher-order PageRank unless multilinear PageRank has a modeling rationale; guaranteed convergence above α < 1/(m − 1) remains unresolved.They report unsuccessful attempts so far and plan to explore sum-of-squares programming.Source: §7 · p. 28

Appendix A. Applying Li and Ng’s results to multilinear PageRank.

The appendix applies Li and Ng’s β criterion to multilinear PageRank. It shows how the criterion relates to the α < 1/2 uniqueness condition and decomposes under the paper’s construction of the modified tensor.

Appendix A. Applying Li and Ng’s results to multilinear PageRank.

  • The authors apply Li and Ng’s uniqueness quantity β [2013] to multilinear PageRank, using β rather than γ to avoid confusion with the shift parameter.β depends on P, and the displayed definition separates it into β1 and β2, each depending on a subset S.Source: Appendix A · p. 30
  • For third-order tensors, β > 1 guarantees uniqueness, and this condition is stronger than α < 1/2.α < 1/2 implies β > 1, but β > 1 can also hold when α > 1/2.Source: Appendix A · p. 30
  • For the construction P̄ = αP + Q, with Qijk = (1 − α)vi, the paper establishes β(P̄) = β(P) + β(Q).Both β1(Q) and β2(Q) equal 1 − α independently of S.Source: Appendix A · p. 30
Loading 1409.1465v1…