PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Incremental and Personalized PageRank

Bahman Bahmani, Abdur Chowdhury, Ashish Goel

arXiv:1006.2880v2cs.DScs.DBcs.IR

TL;DR

The paper addresses efficient incremental computation of PageRank and related random-walk scores on evolving social networks. It uses Monte Carlo methods with stored short random-walk segments under distributed random access, random edge arrivals, and power-law personalized scores. The resulting bounds support accurate global maintenance and efficient top-k personalized queries, with experiments on Twitter validating the assumptions and analyses.

  • Problem

    Efficiently updating global and personalized PageRank and related scores on dynamically evolving large-scale social networks remains an important computational problem.

  • Method

    The paper uses Monte Carlo random-walk methods that store short walk segments in distributed shared memory for incremental updates and personalized top-k estimation.

  • Results

    O(n ln m/ε^2) total work maintains accurate global PageRank estimates, while top-k personalized queries require expected database calls O(k/R^((1-α)/α)) under the stated power-law and caching conditions.

  • Takeaways & Limitations

    The algorithm is reported to be fast enough for real-time queries over a dynamic social network, and Twitter experiments support its assumptions, analyses, and database-call bounds.

  • Takeaways & Limitations

    The analysis relies on distributed random access, random-order edge arrivals for efficiency, and power-law personalized scores for the top-k bound.

Abstract

from arXiv · show

In this paper, we analyze the efficiency of Monte Carlo methods for incremental computation of PageRank, personalized PageRank, and similar random walk based methods (with focus on SALSA), on large-scale dynamically evolving social networks. We assume that the graph of friendships is stored in distributed shared memory, as is the case for large social networks such as Twitter. For global PageRank, we assume that the social network has $n$ nodes, and $m$ adversarially chosen edges arrive in a random order. We show that with a reset probability of $ε$, the total work needed to maintain an accurate estimate (using the Monte Carlo method) of the PageRank of every node at all times is $O(\frac{n\ln m}{ε^{2}})$. This is significantly better than all known bounds for incremental PageRank. For instance, if we naively recompute the PageRanks as each edge arrives, the simple power iteration method needs $Ω(\frac{m^2}{\ln(1/(1-ε))})$ total time and the Monte Carlo method needs $O(mn/ε)$ total time; both are prohibitively expensive. Furthermore, we also show that we can handle deletions equally efficiently. We then study the computation of the top $k$ personalized PageRanks starting from a seed node, assuming that personalized PageRanks follow a power-law with exponent $α< 1$. We show that if we store $R>q\ln n$ random walks starting from every node for large enough constant $q$ (using the approach outlined for global PageRank), then the expected number of calls made to the distributed social network database is $O(k/(R^{(1-α)/α}))$. We also present experimental results from the social networking site, Twitter, verifying our assumptions and analyses. The overall result is that this algorithm is fast enough for real-time queries over a dynamic social network.

1. INTRODUCTION

The paper develops Monte Carlo methods for maintaining approximate global and personalized PageRank and SALSA on dynamically evolving social networks. Under distributed random access and random edge arrivals, the resulting bounds support efficient incremental updates and top-k personalized queries.

  • 1. INTRODUCTION: The paper targets incremental PageRank, personalized PageRank, and SALSA computation for reputation and recommendation systems on dynamic social networks.The approach assumes the graph is stored in distributed shared memory, enabling random access to the social graph.
  • 1. INTRODUCTION: Simple structural and data-layout assumptions yield dramatic running-time improvements for Monte Carlo PageRank estimation.The paper emphasizes distributed shared memory for social networks and validates its assumptions experimentally.
  • 1.2 Our Results: O(n ln m/ε^2) total work maintains accurate global PageRank estimates for every node across m adversarially chosen edges arriving in random order.The same framework also supports authority scores and uses stored short random-walk segments for updates.
  • 1.2 Our Results: Stored random-walk segments support top-k personalized PageRank computation with expected database calls O(k/R^((1-α)/α)) when personalized scores follow a power law with 0 < α < 1 and R > q ln n.Without the power-law assumption, finding the top k generally requires evaluating all n node scores.
  • 1.2 Our Results: Experiments on Twitter support the random-order assumption, power-law behavior of global and personalized scores, and the theoretical database-call bounds.The data was accessed through FlockDB, a distributed shared-memory database.

2. INCREMENTAL COMPUTATION OF PAGERANK

The paper uses stored Monte Carlo walk segments to maintain accurate PageRank approximations as a social network changes. Under random-order edge arrivals, updates require only logarithmically more work than initialization, while deletions are also efficient.

  • 2.1 Approximating PageRank: Monte Carlo walk segments provide sharply concentrated PageRank estimates around the true values, with good approximations reported even for R = 1.The estimate is formed from visit counts across R reset-bounded walks starting at every node.
  • 2.2 Updating the Approximations: The update procedure modifies only stored walk segments affected by arriving edges, rather than recomputing all PageRank values.Each affected segment can be rerun from the updated node or its source, costing at most 1/ε work on average.
  • 2.2 Updating the Approximations: Under the random permutation model, the expected total update work over m edge arrivals is at most O(nR ln m/ε^2).The expected work at the tth arrival is bounded by nR/(tε^2), which sums through the harmonic number H_m.
  • 2.2 Updating the Approximations: Randomly chosen edge deletions can be handled with expected update work at most nR/(mε^2) when the network has m edges.The deletion result uses the same stored-walk update framework.
  • 2.2 Updating the Approximations: The logarithmic total cost is close to initialization cost and can support real-time updates for sufficiently late edge arrivals in social-network settings.The analysis relies on distributed shared memory with random access to the social graph; adversarial edge arrival order can invalidate the bound.

3. APPROXIMATING PERSONALIZED PAGERANK AND SALSA

The paper reuses stored random-walk segments to approximate personalized PageRank and identify top-k nodes efficiently. The analysis depends on power-law personalized scores and limits database work by exploiting frequently visited high-score nodes.

  • 3. APPROXIMATING PERSONALIZED PAGERANK AND SALSA: The personalized algorithm stitches stored walk segments opportunistically, using database fetches that return a node’s R segments and neighbors.The walk begins at the seed and extends by consuming stored segments, resetting, or fetching when necessary.
  • 3. APPROXIMATING PERSONALIZED PAGERANK AND SALSA: The analysis targets the k nodes with largest personalized scores because recommendation applications need only the highest-authority results.The paper states that the same results extend to personalized SALSA.
  • 3.1 Network Model: The model assumes ranked personalized PageRank values follow a power law with exponent 0 < α < 1, supported by Twitter experiments.The experiments report that personalized PageRank, global PageRank, and indegree distributions have roughly the same average exponent.
  • 3.2 Approximating the top k nodes: The required walk length is determined by sπ_k = c, ensuring that each top-k node is visited c times in expectation.Visit counts X_s,v are approximated using sπ_v when the expected count is sufficiently large.
  • 3.2 Approximating the top k nodes: With R > q ln n stored walk segments per node, the expected fetch count for a walk of length s is bounded by Theorem 8 and yields Corollary 9 for top-k search.The analysis charges fetches to extra visits after stored segments are exhausted and uses concentration bounds for R > q ln n.
  • 3.2 Approximating the top k nodes: The fetch definition can cause memory problems at nodes with very large outdegree, such as @BarackObama with more than 750,000 outgoing edges.The paper discusses an alternative fetch operation but retains the original definition.
  • 3.2 Approximating the top k nodes: For α = 0.75, c = 5, R = 10, k = 100, and n = 10^8, the bounds are 63200 steps versus 2000 fetches.The fetch bound is substantially smaller because the power-law assumption concentrates work on high-score nodes.

4. EXPERIMENTS

Experiments on Twitter test the network assumptions and the personalized PageRank approximation strategy. The results support power-law behavior, validate the arrival-order condition, and show that short walks can recover top personalized results while fetches remain near the theoretical bound.

  • 4.3 Network Model Verification: 0.81 was the average observed mX across 4.63 million edge arrivals, supporting the condition required by the running-time analysis.The proof assumes mX = 1; the observed value was reported to validate the obtained running time.
  • 4.3 Network Model Verification: 0.76 was the approximate exponent for both network indegrees and global PageRank in the Twitter experiment.The result is presented in Figure 2, whose axes are both logarithmic.
  • 4.3 Network Model Verification: Personalized PageRank vectors followed power-laws for six random users, with around 2% of nodes having α > 1.The analysis is stated to extend readily to α > 1, although details are omitted; direct friends create a distinct initial segment.
  • 4.3 Network Model Verification: 0.77 was the average personalized PageRank exponent, with standard deviation 0.08 across users.The mean was almost the same as the exponent for indegree and global PageRank, despite variation between users.
  • 4.4 A Few Random Steps Go a Long Way: 80% precision at recall 0.8 was obtained when 5,000-step walks retrieved the top 1,000 candidates against 50,000-step reference walks.Directly connected nodes were excluded from both experiments, and the evaluation used 11-point interpolated average precision.
  • 4.5 Fetches: Observed fetch counts for R ∈ {5, 10, 20} were compared with theoretical upper bounds over walk lengths from 100 to 50,000.The observed averages over 100 users are shown as thin lines and the theoretical bounds as thick lines in Figure 6.

A. EFFECTIVENESS OF RANDOM WALK BASED METHODS FOR LINK PREDICTION

The appendix evaluates personalized random-walk methods for link prediction on Twitter users. Personalized PageRank and SALSA outperform HITS and cosine similarity in this observational recommendation setting, although the measurements are not from users exposed to recommendations.

  • A. EFFECTIVENESS OF RANDOM WALK BASED METHODS FOR LINK PREDICTION: 100 Twitter users were selected for having 20–30 friends initially and increasing their existing friend set by 50%–100%.The selection targeted reasonably active users who were increasing their friend sets.
  • A. EFFECTIVENESS OF RANDOM WALK BASED METHODS FOR LINK PREDICTION: The experiment compared personalized PageRank, personalized SALSA, personalized HITS, and COSINE after 10 iterations per method.Predicted links were evaluated against friendships formed between two dates.
  • A. EFFECTIVENESS OF RANDOM WALK BASED METHODS FOR LINK PREDICTION: The measured counts were limited because users formed only 10–30 new friendships without seeing the recommendations.The authors state that recommendation exposure could produce substantially larger counts.
  • A. EFFECTIVENESS OF RANDOM WALK BASED METHODS FOR LINK PREDICTION: Personalized PageRank and SALSA significantly outperformed HITS and also exceeded cosine similarity in predicting new friendships.The comparison averaged results over 100 selected users and used the top 100 or top 1,000 predictions.

B. PROOF OF THEOREM 1

The proof establishes concentration for Monte Carlo PageRank estimates by analyzing independent stored-walk contributions. It shows that sufficiently large PageRank values concentrate with one segment, while average values require logarithmically many segments.

  • B. PROOF OF THEOREM 1: E[eπv] = πv, so the proof focuses on obtaining a sharp concentration bound for the estimator.For R = 1, the analysis defines independent visit-count variables Xu from stored walks and bounds them using their walk lengths.
  • B. PROOF OF THEOREM 1: The concentration argument models each stored walk’s length through a geometrically distributed variable with reset parameter ε.The proof introduces W = εY and an optimization-dependent constant δ′ in its tail analysis.
  • B. PROOF OF THEOREM 1: πv = Ω(ln n/n) yields sharp concentration with R = 1 for a node whose PageRank is slightly above the average 1/n.The lower-tail analysis is described as analogous and omitted.
  • B. PROOF OF THEOREM 1: R = O(ln n) stored walk segments provide sharp concentration for average PageRank values πv = Θ(1/n).The resulting estimator tails decay exponentially.

C. PROOF OF LEMMA 7

The lemma couples the algorithmic walk with a stationary-distribution walk after the first reset. This coupling relates visits in the constructed walk to stationary-walk visits.

  • C. PROOF OF LEMMA 7: The proof couples the walk with a stationary-distribution walk at the first reset time ts and thereafter.The coupling is used to compare the number of visits to node v in the two walks.
  • C. PROOF OF LEMMA 7: The visit-count relation at ts supplies the step needed to derive the lemma’s bound.The proof then concludes with the reset-probability factor ε.
Loading 1006.2880v2…