FrogWild! - Fast Page Rank Approximations on Graph Engines

We propose FROGWILD, a novel algorithm for fast approximation of high Page Rank vertices, geared towards reducing network costs of running traditional Page Rank algorithms. Our algorithm can be seen as a quantized version of power iteration that performs multiple parallel random walks over a directed graph. One important innovation is that we introduce a modification to the Graph Lab framework that only partially synchronizes mirror vertices. This partial synchronization vastly reduces the network traffic generated by traditional Page Rank algorithms, thus greatly reducing the per-iteration cost of Page Rank. On the other hand, this partial synchronization also creates dependencies between the random walks used to estimate Page Rank. Our main theoretical innovation is the analysis of the correlations introduced by this partial synchronization process and a bound establishing that our approximation is close to the true Page Rank vector. We implement our algorithm in Graph Lab and compare it against the default Page Rank implementation. We show that our algorithm is very fast, performing each iteration in less than one second on the Twitter graph and can be up to 7x faster compared to the standard Graph Lab Page Rank implementation.