PaperlayerView exact revision on arXiv

Source-linked AI summary

FrogWild! -- Fast PageRank Approximations on Graph Engines

Ioannis Mitliagkas, Michael Borokhovich, Alexandros G. Dimakis, Constantine Caramanis

arXiv:1502.04281v1cs.DCcs.ITcs.SI

TL;DR

FrogWild targets fast approximation of high PageRank vertices while reducing the communication costs of graph-engine PageRank. It uses parallel random walks with partial synchronization, analyzes the resulting dependencies, and achieves substantial speed and network-traffic improvements over GraphLab PageRank.

  • Problem

    Fast computation of high PageRank vertices is needed because PageRank creates substantial memory, computation, and communication challenges in large-scale graph processing.

  • Method

    FrogWild uses a sublinear number of random walkers and modifies GraphLab PowerGraph to partially synchronize mirror vertices, while replacing teleportations with random starting positions and geometrically distributed walk lengths.

  • Results

    FrogWild takes less than 1 sec per iteration on the Twitter graph, achieving more than a 7x speedup over GraphLab PageRank and a 1000x network improvement over exact GraphLab PageRank.

  • Takeaways & Limitations

    FrogWild provides a fast, communication-efficient approach for identifying high PageRank vertices in distributed graph engines.

  • Takeaways & Limitations

    Reducing synchronization probability lowers network traffic but creates dependent random walks, so the standard Power Method analysis no longer applies and requires a separate correlation analysis.

Abstract

from arXiv · show

We propose FrogWild, a novel algorithm for fast approximation of high PageRank vertices, geared towards reducing network costs of running traditional PageRank 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 GraphLab framework that only partially synchronizes mirror vertices. This partial synchronization vastly reduces the network traffic generated by traditional PageRank algorithms, thus greatly reducing the per-iteration cost of PageRank. On the other hand, this partial synchronization also creates dependencies between the random walks used to estimate PageRank. 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 PageRank vector. We implement our algorithm in GraphLab and compare it against the default PageRank 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 GraphLab PageRank implementation.

1. INTRODUCTION

FrogWild targets fast top-k PageRank estimation by replacing dense PageRank updates with parallel random walks and partial mirror synchronization. The method reduces graph-engine costs, while its analysis addresses the dependencies introduced by synchronization and its experiments report substantial speed and traffic improvements.

  • 1. INTRODUCTION: FrogWild targets fast computation of only the highest-PageRank vertices, avoiding the full vector when distinguishing top-ranked nodes matters most.The paper focuses on k approximately 10–1000 and motivates this target through applications where key users or keywords are a small fraction of the graph.
  • 1. INTRODUCTION: FrogWild uses a small number of discrete random walkers as a quantized form of power iteration, sampling from normalized PageRank after sufficient mixing.The walkers perform random walks with teleportation behavior implemented through random starting positions and geometrically distributed lifetimes.
  • 1. INTRODUCTION: Partial mirror synchronization reduces communication by exposing a per-vertex probability ps and activating each mirror independently with that probability.The modification is applied within GraphLab PowerGraph’s vertex-cut architecture, where masters synchronize cached mirror copies.
  • 1. INTRODUCTION: Partial synchronization creates correlated walker trajectories, so standard Power Method analysis no longer applies; the paper proves the resulting estimate remains close to PageRank with high probability.The analysis combines coupling, pairwise random-walk intersection probabilities, and a contrast bound for non-reversible chains.

2. PROBLEM AND MAIN RESULTS

FrogWild targets fast estimation of the top-k PageRank vertices rather than the full vector, using parallel random walks and partial mirror synchronization in GraphLab. The method reduces communication and computation while preserving an approximation of PageRank through randomized walker behavior.

  • Problem and objective: FrogWild estimates the top k PageRank vertices, focusing on high-mass nodes rather than recovering the full PageRank vector.The paper motivates this target because distinguishing the highest-ranked nodes matters more than accurately ranking the long tail.
  • Problem and objective: The algorithm uses multiple random walks and evaluates outputs with captured PageRank mass and exact top-k identification probability.The captured-mass metric gives partial credit for high-PageRank vertices outside the exact top-k list, whereas exact identification does not.
  • FrogWild mechanism: Uniformly initializing frogs and terminating each walk geometrically reproduces the teleportation behavior without global random jumps.This design avoids the dense messaging pattern that teleportations would create in a partitioned graph engine.
  • Analysis and evaluation: The paper analyzes partial synchronization and compares FrogWild with reduced-iteration PageRank within the same GraphLab PowerGraph framework.The stated comparison covers running time, network communication, and scalability.
  • Graph-engine design: FrogWild modifies PowerGraph so each mirror synchronizes independently with probability ps, leaving unsynchronized replicas idle during that super-step.This randomized synchronization avoids communication and CPU work for inactive replicas.

FrogWild! vertex program

The vertex program propagates surviving frogs through synchronized mirrors, counts their positions, and uses those counts to estimate the invariant PageRank distribution. The analysis addresses the correlations caused by partial synchronization and provides high-probability accuracy guarantees.

  • FrogWild! vertex program: Frogs die independently with probability pT, while surviving frogs are distributed through synchronized mirrors using binomial randomization.The implementation preserves the expected number of surviving frogs while limiting scatter work to synchronized replicas.
  • Correlation analysis: Partial synchronization leaves each individual walk’s distribution unchanged but correlates simultaneously running walks when they intersect.The analysis controls this correlation using ps and the pairwise probability that two walks meet.
  • Estimator: The estimator uses vertex frog tallies c(i) to approximate the invariant distribution after the walks stop.The paper defines the estimator from the positions of N random walks and identifies c(i) as the vertex-program tally.
  • Main result: Theorem 1 gives a high-probability guarantee that the estimator captures mass close to the optimum for uniformly initialized frogs stopped geometrically or after at most t steps.The required number of iterations and frogs scale with the maximum capturable mass µk(π).
  • Main result: Theorem 2 bounds walk-intersection probability using the maximum PageRank value, and the paper argues this probability vanishes for common graph-size regimes.For constant or logarithmic t, increasing graph size can make the meeting probability small, after which frog count controls the remaining error term.
  • Scope and relation to prior work: The work positions FrogWild as a graph-engine-specific top-PageRank approximation that uses far fewer than O(n) walkers to reduce distributed network traffic.This contrasts with approaches that start one walker per node and target global approximation.

3. EXPERIMENTS

Experiments compare FrogWild with GraphLab PR on execution cost, top-k accuracy, sparsification, and scaling across Twitter and LiveJournal. FrogWild substantially reduces runtime and communication while retaining competitive approximation quality.

  • Experimental setup: The evaluation compares FrogWild with GraphLab v2.2 PageRank using execution-stage runtime, network usage, and accuracy, excluding graph-loading ingress costs.Experiments use VirtualBox and AWS clusters on LiveJournal and Twitter graphs, including Twitter with 41.6M nodes and 1.4B edges.
  • Twitter performance: More than 7x speedup per iteration and 1000x lower network usage than exact GraphLab PR are reported on Twitter, with lower CPU usage as well.With 12 nodes, GraphLab PR takes about 7.5 seconds per iteration, whereas FrogWild takes less than 1 second; network usage is also more than 10x lower than one- or two-iteration GraphLab PR.
  • Approximation accuracy: FrogWild with ps = 1 or ps = 0.7 always outperforms one-iteration GraphLab PR on both mass captured and exact identification.ps = 0.4 remains relatively good on both metrics, while ps = 0.1 is reasonable for mass captured.
  • Accuracy-cost tradeoff: At accuracy comparable to GraphLab PR, FrogWild uses much less total running time and network traffic across tested iteration counts and synchronization probabilities.Figure 3 evaluates the tradeoff between accuracy, running time, and network usage for different FrogWild configurations.
  • Comparison with sparsification: FrogWild outperforms graph sparsification in running time while achieving comparable accuracy.The comparison deletes each edge with probability r before executing GraphLab PR.
  • LiveJournal and scaling: On LiveJournal, 800K initial random walks and 4 iterations achieve good accuracy and running time, while FrogWild remains faster and uses much less network.The same parameters are reasonable for Twitter and LiveJournal despite their order-of-magnitude size difference, suggesting slow growth in the required number of frogs.

A. EDGE ERASURE MODEL

The edge erasure model temporarily disables graph edges independently of the random walks and constrains how erasures are generated. The theory covers independent erasures and an at-least-one-out-edge variant used in the implementation.

  • Model definition: An edge erasure model temporarily erases a subset of edges at time t, independently of the random walks up to that time.Erased edges are reconsidered in the next step rather than permanently removed.
  • Required properties: The model requires independence across vertices, preservation probability at least ps for every outgoing edge, limited negative correlation, and symmetry among same-sized erased subsets.These properties constrain the allowable dependence and distribution of edge erasures.
  • Concrete models: The theory covers independent erasures and the at-least-one-out-edge-per-node model, while experiments use the latter.Independent erasures preserve every edge independently with probability ps; the alternative enables one outgoing edge when all are erased.

B.1 Proof of Theorem 1

The proof decomposes FrogWild into fixed-step and truncated-geometric sampling, then analyzes edge erasures and the dependence they introduce between walkers. It establishes equivalence before first interference and combines mixing and sampling arguments to bound the captured PageRank mass.

  • Model caveat: Independent edge erasures can temporarily create zero-out-degree nodes, so this erasure model may lose walkers.This limitation motivates distinguishing the independent-erasures model from alternatives that ensure at least one outgoing edge remains enabled.
  • Sampling construction: The proof first relates fixed-step teleporting walks to truncated-geometric walks on the original graph, which removes explicit teleportations while preserving the sample distribution.Process 15 starts walkers uniformly, uses geometrically distributed lifetimes, and truncates them after t steps; Lemma 16 states that its samples have the same distribution as Process 11.
  • Accuracy bound: The sampling guarantee combines a mixing-loss bound for the truncated process with a sampling-loss bound for the FrogWild estimator.Lemma 17 bounds mass missed because of distributional mismatch, while Lemma 18 gives a high-probability lower bound for the estimator using N samples despite randomized synchronization.
  • Dependence analysis: Under edge erasures, walkers are generally dependent when they meet, because they may face the same erased edges and make the same subsequent decision.The analysis therefore tracks interference rather than assuming independent trajectories.
  • Dependence analysis: Two blocking walks are identical to independent walks until their first meeting at which at least one walker is blocked.This process equivalence follows because, before interference, walkers effectively choose uniformly from the full outgoing edge set.

B.2 Proof of Theorem 2

This proof analyzes the walk distribution from a uniform start using the PageRank transition matrix and its invariant distribution. It bounds the resulting contrast through spectral properties and nonnegative transition probabilities.

  • B.2 Proof of Theorem 2: The two walks start from the same uniform distribution and follow the same transition law, so they have identical marginal distributions at every time.The proof writes the common marginal as p_t = Q^t u and uses PageRank invariance under Q.
  • B.2 Proof of Theorem 2: The proof bounds the walk distribution using the invariant PageRank vector and the nonnegative entries of the transition matrices.These properties provide an upper bound on the maximal element of the distribution after t steps.
  • B.2 Proof of Theorem 2: Uniform initialization supplies the base-case norm relation used to control later distribution norms.The argument explicitly uses p_0 = u and the fact that probability vectors are nonnegative and sum to one.

B.3 Proof of Proposition 7

The proposition bounds the expected maximum value among independent samples from a power-law distribution. The result follows by applying Markov’s inequality to the expectation bound.

  • B.3 Proof of Proposition 7: Emax = O(n^(-1/(θ−1))) bounds the expected maximum of n independent draws from a power-law distribution with parameter θ.The expectation bound is attributed to prior work and is then used in the proposition’s argument.
  • B.3 Proof of Proposition 7: Markov’s inequality converts the expected-maximum bound into the proposition’s stated probabilistic guarantee.The proof describes this final step as a direct application of Markov’s inequality.
Loading 1502.04281v1…