On efficient randomized algorithms for finding the PageRank vector

A. V. Gasnikov ; D. Yu. Dmitriev

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 3, pp. 355-371

Résumé

Two randomized methods are considered for finding the PageRank vector; in other words, the solution of the system $\mathbf{p}^{\mathrm{T}}=\mathbf{p}^{\mathrm{T}}P$ with a stochastic $n\times n$ matrix $P$, where $n\sim 10^7$–$10^9$, is sought (in the class of probability distributions) with accuracy $\varepsilon:\varepsilon\gg n^{-1}$. Thus, the possibility of brute-force multiplication of $P$ by the column is ruled out in the case of dense objects. The first method is based on the idea of Markov chain Monte Carlo algorithms. This approach is efficient when the iterative process $\mathbf{p}_{t+1}^{\mathrm{T}}=\mathbf{p}_t^{\mathrm{T}}P$ quickly reaches a steady state. Additionally, it takes into account another specific feature of $P$, namely, the nonzero off-diagonal elements of $P$ are equal in rows (this property is used to organize a random walk over the graph with the matrix $P$). Based on modern concentration-of-measure inequalities, new bounds for the running time of this method are presented that take into account the specific features of $P$. In the second method, the search for a ranking vector is reduced to finding the equilibrium in the antagonistic matrix game $$ \min_{\mathbf{p}\in S_n(1)}\max_{\mathbf{u}\in S_n(1)}\langle \mathbf{u}, (P^{\mathrm{T}}-I)\mathbf{p}\rangle, $$ where $S_n(1)$ is a unit simplex in $\mathbb{R}^n$ and $I$ is the identity matrix. The arising problem is solved by applying a slightly modified Grigoriadis–Khachiyan algorithm (1995). This technique, like the Nazin–Polyak method (2009), is a randomized version of Nemirovski’s mirror descent method. The difference is that randomization in the Grigoriadis–Khachiyan algorithm is used when the gradient is projected onto the simplex rather than when the stochastic gradient is computed. For sparse matrices $P$, the method proposed yields noticeably better results.