PaperlayerView exact revision on arXiv

Source-linked AI summary

FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs

Peter Lofgren, Siddhartha Banerjee, Ashish Goel, C. Seshadhri

arXiv:1404.3181v2cs.DScs.SI

TL;DR

Personalized PageRank supports ego-centric measures and social search, where candidate results need PPR estimates. FAST-PPR uses a bidirectional search technique and is reported to be at least 20 times faster than the state of the art across graphs, without sacrificing accuracy.

  • Problem

    Social-network applications need ego-centric measures, and personalized-search protocols estimate PPR for each candidate result.

    Source: §1 · p. 1

  • Method

    FAST-PPR estimates Personalized PageRank using a new bidirectional search technique.

    Source: §1.1 · p. 2

  • Results

    At least 20 times faster than the state of the art across graphs, FAST-PPR does not sacrifice accuracy.

    Source: §1.1 · p. 2, §1 · p. 2

  • Takeaways & Limitations

    The reported speedups are relevant to social-search protocols that estimate PPR for candidate results.

    Source: §1 · p. 1, §1.1 · p. 2

    The correctness proof assumes perfect FRONTIER outputs, which are not achieved; a more complex variant is proven theoretically.

    Source: §3 · p. 5

Abstract

from arXiv · show

We propose a new algorithm, FAST-PPR, for estimating personalized PageRank: given start node $s$ and target node $t$ in a directed graph, and given a threshold $\delta$, FAST-PPR estimates the Personalized PageRank $\pi_s(t)$ from $s$ to $t$, guaranteeing a small relative error as long $\pi_s(t)>\delta$. Existing algorithms for this problem have a running-time of $\Omega(1/\delta)$; in comparison, FAST-PPR has a provable average running-time guarantee of ${O}(\sqrt{d/\delta})$ (where $d$ is the average in-degree of the graph). This is a significant improvement, since $\delta$ is often $O(1/n)$ (where $n$ is the number of nodes) for applications. We also complement the algorithm with an $\Omega(1/\sqrt{\delta})$ lower bound for PageRank estimation, showing that the dependence on $\delta$ cannot be improved. We perform a detailed empirical study on numerous massive graphs, showing that FAST-PPR dramatically outperforms existing algorithms. For example, on the 2010 Twitter graph with 1.5 billion edges, for target nodes sampled by popularity, FAST-PPR has a $20$ factor speedup over the state of the art. Furthermore, an enhanced version of FAST-PPR has a $160$ factor speedup on the Twitter graph, and is at least $20$ times faster on all our candidate graphs.

1. INTRODUCTION

Personalized PageRank provides an ego-centric measure used in social search, but estimating it for source–target pairs is difficult at the small thresholds common in large networks. FAST-PPR combines a bidirectional search with practical balancing and storage variants, and the paper reports faster estimates and theoretical results on its running-time dependence.

1. INTRODUCTION

  • Personalized PageRank measures visits to nodes via short random walks from a source and supports ego-centric social search.Applications include personalized web search, collaborative tagging, social-network name search, and social Q&A.Source: §1 · p. 1
  • Existing PPR-estimation techniques take Ω(1/δ) time, making them infeasible for large networks when δ is O(1/n) or O((log n)/n).Source: §1 · p. 1

1.1 Our Contributions

  • At least 20 times faster than the state of the art across all graphs, FAST-PPR preserves accuracy; Balanced FAST-PPR takes under 3 seconds on Twitter-2010 random pairs.Figure 1 compares Balanced FAST-PPR, Monte-Carlo, and Local-Update across networks.Source: Figure 1 · p. 2, §1.1 · p. 2
  • FAST-PPR estimates source-to-target Personalized PageRank using a new bidirectional search technique.The paper also proposes Balanced FAST-PPR, a heuristic that achieves significant speedups in practice.Source: §1.1 · p. 2
  • FAST-PPR can obtain worst-case running-time bounds by pre-computing and storing additional information.Source: §1.1 · p. 2
  • The paper establishes an Ω(1/√δ) lower bound for PPR estimation, indicating that FAST-PPR’s dependence on δ cannot be improved.The stated running-time analysis assumes constant desired relative error and teleport probability.Source: §1.1 · p. 2
  • The authors state that FAST-PPR’s performance gains also apply to PageRank with arbitrary preference vectors, though the paper focuses on Personalized PageRank.Source: §1.1 · p. 2

2. PRELIMINARIES

The section defines Personalized PageRank and motivates estimating source-to-target PPR at thresholds near 1/n, where existing methods can be too costly. FAST-PPR instead uses a target-specific frontier and source-side random walks to estimate the value bidirectionally.

2. PRELIMINARIES

  • For directed graphs, d = m/n is the average in-degree, and PPR describes the distribution of a random walk that returns to its start with probability α.The inverse-PPR values for a target sum to n times its global PageRank.Source: §2 · p. 2

2.1 Existing Approaches for PPR Estimation

  • Existing local-update and Monte Carlo approaches can require Ω(1/δ) work to estimate PPR values near threshold δ.The section notes that such thresholds can be O(1/n) or O((log n)/n).Source: §2.1 · pp. 2–3

2.2 Intuition for our approach

  • FAST-PPR works backward from t to build a target-specific set, then runs walks forward from s to test whether they hit its frontier.The frontier is used because the target and source-side sets need not intersect even when π_s(t) > δ.Source: §2.2 · p. 3, Figure 2 · p. 4

2.3 Additional Definitions

  • A blanket set intercepts every path from s to t, allowing π_s(t) to be decomposed into first-hit probabilities times the PPR values from the hit nodes to t.The target set contains nodes whose inverse-PPR exceeds ε_r; the frontier contains their in-neighbors outside the target set.Source: §2.3 · p. 3

2.4 A Bidirectional Estimator

  • The bidirectional estimator balances O(d/ε_r) frontier construction against O(ε_r/δ) source walks, yielding O(√(d/δ)) work when ε_r is optimized.The section also gives an Ω(1/√δ) lower bound and distinguishes FAST-PPR from fixed-skeleton schemes by constructing target sets at query time.Source: §2.4 · p. 4

3. THE FAST-PPR ALGORITHM

FAST-PPR estimates PPR by combining an approximate target-specific frontier with random walks from the source. Its average running time balances frontier construction and forward sampling, while the stated vanilla correctness analysis assumes a perfect FRONTIER procedure.

3. THE FAST-PPR ALGORITHM

  • FAST-PPR calls FRONTIER to obtain target and frontier sets with inverse-PPR estimates, then averages frontier values over source walks that first hit the frontier.The algorithm uses c and β to control the number of walks and the quality of inverse-PPR estimates.Source: §3 · pp. 4–5

3.1 Running-time of FAST-PPR

  • The FRONTIER procedure has average running time O(d/(αε_r)), and FAST-PPR's average running time is O(α^-1(d/ε_r + ε_r/δ)).Choosing ε_r to optimize this bound gives average per-query work O(α^-1√(d/δ)).Source: §3 · p. 5, §3.1 · p. 5
  • The reverse-time bound is averaged over targets and can be much larger for high-global-PageRank targets, whereas forward time is similar across sources and predictable.That difference motivates the workload-balancing version described in the section.Source: §3.1 · p. 5

3.2 FAST-PPR with Perfect FRONTIER

  • With exact inverse-PPR estimates from FRONTIER, Theorem 3 gives an estimate with probability greater than 0.99 for queries above threshold δ.Its proof uses k = cε_r/δ independent walks and bounded scaled contributions to apply Chernoff bounds.Source: §3.2 · p. 5

3. THE FAST-PPR ALGORITHM

  • The perfect-FRONTIER assumption is unrealistic; the paper presents a more complex variant with provable guarantees, while implementing vanilla FAST-PPR in practice.The proof's constant c is chosen for exposition and is not optimized.Source: §3.2 · p. 5

4. LOWER BOUND FOR PPR ESTIMATION

The section establishes an edge-access lower bound for thresholded PPR estimation. Its reduction from Detect-High(δ) shows that the δ dependence cannot be improved beyond the stated order.

4. LOWER BOUND FOR PPR ESTIMATION

  • The lower bound gives FAST-PPR's algorithms the stated optimal dependence on δ.The theorem's numerical constants are not optimized.Source: §4 · p. 5
  • Any algorithm for Detect-High(δ) must access Ω(1/δ) graph edges.Detect-High(δ) must accept when π_s(t) > δ and reject when π_s(t) < δ^2, each with probability above 9/10.Source: §4 · p. 5
  • The authors reduce Detect-High(δ) to expansion testing, so fewer than 1/δ queries would yield a distinguisher contradicting the cited lower bound.The proof outline uses distributions of undirected 3-regular graphs.Source: §4 · p. 6

5. FURTHER VARIANTS OF FAST-PPR

This section addresses the gap between FAST-PPR’s practical frontier estimates and the perfect estimates assumed by its correctness proof. It presents a provable variant, a workload-balancing heuristic, and stored-oracle options.

5. FURTHER VARIANTS OF FAST-PPR

  • The section presents a truly provable FAST-PPR variant without assumptions, but identifies vanilla FAST-PPR as the better practical candidate and the implemented version.It also introduces precomputation and dynamic workload balancing as further variants.Source: §5 · p. 6

5.1 Using Approximate Frontier-Estimates

  • Approximate inverse-PPR estimates have additive error and may be zero for small values, so a target-avoiding-walk procedure bootstraps good estimates with an additional log(1/δ) running-time factor.The resulting algorithm provides the desired accuracy guarantee.Source: §5.1 · p. 6

5.2 Balanced FAST-PPR

  • BALANCED-FAST-PPR dynamically lowers ϵr until estimated remaining forward work matches reverse work already spent, using largest-residual pushes to balance the two.The authors report that this balancing significantly reduces average running time.Source: §5.2 · p. 6

5.3 FAST-PPR using Stored Oracles

  • Precomputing frontiers for all nodes and storing them can convert average-case bounds to worst-case bounds, while precomputed walks support query-time joins on distributed systems.The stored-walk variant illustrates FAST-PPR’s modular trade-offs among implementation resources.Source: §5.3 · p. 6

6. EXPERIMENTS

The experiments compare FAST-PPR with Monte Carlo and Local-Update across varied graphs, query settings, and accuracy tests. They examine running time, PPR-value distributions, and the effects of frontier use and balancing forward and reverse work.

6.1 Experimental Setup

  • The experiments span directed social networks, undirected social and collaboration graphs, and a UK web graph with 3.7 billion edges; benchmarks include Monte Carlo and Local-Update.Twitter-2010 has 41 million users and 1.5 billion edges, with one node having more than 700,000 in-neighbors.Source: §6.1 · p. 7

6.2 Distribution of PPR values

  • The complementary cumulative distribution of PPR values for 10,000 uniformly sampled Twitter pairs was roughly linear on a log-log plot, suggesting a power law.The study used FAST-PPR to compute the sampled PPR values.Source: §6.2 · p. 7, Figure 3 · p. 7

6.3 Running Time Comparisons

  • FAST-PPR was much faster than previous methods for targets with high global PageRank, and BALANCED-FAST-PPR improved average running time, especially for lower-PageRank targets.Targets were selected by global-PageRank percentile, with running times averaged over random source nodes.Source: §6.3 · pp. 7–8
  • On Twitter-2010, Balanced FAST-PPR took less than 3 seconds for global-PageRank targets, versus more than 6 minutes for Monte Carlo and more than an hour for Local Update.Figure 4 compares average running times across networks and target-sampling schemes.Source: Figure 4 · p. 8, §6.3 · p. 8

6.4 Measuring the Accuracy of FAST-PPR

  • Across graphs, FAST-PPR was more accurate than Local-Update and Monte Carlo under the parameters used in the running-time experiments.The accuracy tests sampled source nodes whose PPR values were near the significance threshold δ.Source: §6.4 · p. 8

6.5 Some Other Empirical Observations

  • Using inverse-PPR estimates from the frontier produced better accuracy than using estimates from the target set, whose high inverse-PPR values increase estimator variance.The figure compares estimated with true PPR values; perfect estimates lie on y = x.Source: Figure 6 · p. 9, §6.5 · p. 9
  • Balanced FAST-PPR corrected FAST-PPR’s mismatch in forward and reverse work: the unbalanced algorithm did too much reverse work for high-PageRank targets and too much forward work for low-PageRank targets.The comparison varies target global PageRank on Twitter-2010.Source: Figure 7 · p. 9, §6.5 · p. 9

A. FAST-PPR WITH APPROXIMATE FRONTIER ESTIMATES

With approximate frontier estimates, FAST-PPR uses target-avoiding random walks to address additive-error problems at frontier nodes and high variance from walks entering the target set. Its runtime bounds distinguish reverse-time averages over node pairs from forward-time averages over algorithm randomness.

A. FAST-PPR WITH APPROXIMATE FRONTIER ESTIMATES

  • Approximate inverse-PPR errors can make frontier estimates unhelpful, while allowing walks to reach the target set can produce high variance.The stated difficulty includes frontier nodes whose inverse-PPR is below the additive-error bound and target-set nodes whose inverse-PPR may be Ω(1).Source: A. FAST-PPR WITH APPROXIMATE FRONTIER… · p. 11
  • The method uses target-avoiding random walks, stopping when the target-set entering probability falls below a threshold or the walk reaches its length limit.It estimates a target set, then accumulates weighted scores along walks generated by rejection-sampling neighbors outside that set.Source: A. FAST-PPR WITH APPROXIMATE FRONTIER… · pp. 11–12
  • Theorem 6 gives a correctness guarantee with probability at least 1−pfail when πs(t) > δ and the requested relative-error tolerance is c < 1.The supplied theorem passage does not include the estimate bound itself.Source: A. FAST-PPR WITH APPROXIMATE FRONTIER… · p. 12
  • The runtime analysis averages reverse time over random (s, t) pairs and forward time over the algorithm's randomness; the authors also describe balancing the two times.The six internal parameters set frontier-estimate accuracy, the number of walks, and controls on target-avoiding walks.Source: A. FAST-PPR WITH APPROXIMATE FRONTIER… · p. 12

B. DETAILS OF LOWER BOUND

The lower-bound argument reduces distinguishing two graph distributions to Detect-High(δ), using cases where a random node pair has PageRank above δ or zero. The constructed distinguisher is correct with probability at least 2/3.

B. DETAILS OF LOWER BOUND

  • With probability greater than 3/4, a graph drawn from G1 has πs(t) > δ for the considered node pair.The proof uses random matchings to form an expander with probability greater than 3/4.Source: B. DETAILS OF LOWER BOUND · p. 13
  • For any graph in G2, two uniformly random nodes have πs(t) = 0 with probability at least 3/4 because they may lie in different components.Each G2 graph has four connected components of equal size.Source: B. DETAILS OF LOWER BOUND · p. 13
  • The constructed distinguisher is correct with probability at least 2/3, contradicting the assumed Detect-High(δ) query bound if that bound is too small.It uses a single query to the detection algorithm, and the argument bounds its error using the two graph cases.Source: B. DETAILS OF LOWER BOUND · p. 13

C. BALANCED-FAST-PPR PSEUDOCODE

The paper supplies complete pseudocode for Balanced FAST-PPR and Balanced Frontier. Its frontier procedure uses random-walk runtime estimates to determine how much backward local-update work to perform.

C. BALANCED-FAST-PPR PSEUDOCODE

  • The paper introduces BALANCED-FAST-PPR in Section 5.2, gives only a brief description there, and provides its complete pseudocode in Algorithms 4 and 5.Source: C. BALANCED-FAST-PPR PSEUDOCODE · p. 13
  • The novelty in Balanced Frontier is using random-walk runtime estimates to determine the amount of backward local-update work.The inverse-PPR update rule itself is based on prior local-update algorithms [14, 20].Source: C. BALANCED-FAST-PPR PSEUDOCODE · p. 13

D. RUNTIME VS. LESS-ACCURATE MONTE-CARLO

Even with a minimal-walk, less-accurate Monte Carlo baseline, Balanced FAST-PPR is faster in the reported comparison. That Monte Carlo setting has significantly greater average relative error than FAST-PPR.

D. RUNTIME VS. LESS-ACCURATE MONTE-CARLO

Loading 1404.3181v2…