Abstract
This paper introduces three novel optimization algorithms—NL1, S-FW, and GK—designed to solve the PageRank problem on massive, sparse graphs with sub-linear time complexity. By reframing PageRank as a convex minimization problem over a unit simplex and leveraging sparse update techniques, the authors demonstrate that stationary distributions can be approximated without processing every edge in each iteration. Experimental results on real-world and synthetic datasets show that the Sparse Frank-Wolfe (S-FW) algorithm is particularly effective, offering significant performance gains over traditional methods.
Introduction
The PageRank algorithm is a cornerstone of information retrieval, used to determine node importance in networks. Mathematically, this requires finding the stationary distribution of a Markov Chain, which translates to solving a massive system of linear equations $Px = x$. Traditional methods like power iteration or direct matrix inversion struggle with the scale of modern web graphs. Furthermore, stochastic methods often rely on a "spectral gap" that is frequently unknown or extremely small in real-world sparse graphs. This work addresses the challenge of solving PageRank for billion-node graphs efficiently when the graph is sparse but the spectral gap is problematic.
Methods
The authors treat PageRank as a convex optimization problem constrained to a unit simplex. They propose three primary algorithms, each exploiting sparsity through specialized data structures:
- NL1 ($\ell_1$-Proximal Gradient Descent): This method utilizes a proximal step in the $\ell_1$ norm. A key theoretical contribution (Lemma 2.1) proves that the optimal update vector at each step is extremely sparse, containing only two non-zero coordinates. By employing a doubly-linked list of binary heaps to track gradient components, the algorithm achieves logarithmic iteration complexity relative to the graph's dimension.
- S-FW (Sparse Frank-Wolfe): An extension of the Frank-Wolfe algorithm, S-FW is "projection-free." It identifies the optimal movement direction by finding the minimum coordinate of the gradient, a process highly efficient for sparse matrices.
- GK (Grigoriadis-Khachiyan variant): Targeting the $\ell_\infty$ norm of the error, this randomized mirror descent approach uses a binary tree structure for managing and sampling from probability distributions, allowing updates independent of the total number of edges.
The paper also introduces a Matrix Sparsification technique to handle nodes with massive in-degrees or out-degrees by decomposing dense rows/columns into multiple sparse equations, ensuring the $d$-sparse assumption holds.
Results
The algorithms were evaluated on synthetic $d$-diagonal matrices (up to $n=10^8$) and real-world web graphs from the Stanford University collection, including Stanford, NotreDame, BerkStan, and Google.
Key findings include:
- Practical Performance: S-FW emerged as the most practical algorithm, consistently outperforming NL1 in real-world tests. For instance, on the Stanford dataset, S-FW achieved the target accuracy ($10^{-4}$) in 0.008 seconds, compared to 0.145 seconds for NL1.
- Scalability: On synthetic matrices, S-FW's runtime remained nearly constant as the dimension $n$ increased from $10^2$ to $10^8$, validating the near dimension-independent nature of the sparse updates.
- Sparsity Advantage: Sparse variants were orders of magnitude faster than their full-update counterparts (e.g., S-FW vs. S-FW(NS)).
Discussion and Conclusion
The primary insight of this work is that knowing the sparsity pattern of the transition matrix allows for "sub-linear" time complexity—finding approximate solutions in less time than it takes to read all non-zero elements. By shifting from linear algebra to first-order optimization tools like Frank-Wolfe and Mirror Descent, the authors effectively handle constraints on the unit simplex.
However, limitations remain. The GK algorithm, despite strong theoretical bounds, exhibited numerical instability in practice due to vanishingly small probability values. Additionally, performance still depends on the maximum degree $d$ of the graph. Future work will focus on improving convergence rates relative to accuracy ($\epsilon$) while maintaining linear dependence on dimension.
Summary updated