Fast Incremental and Personalized PageRank

By Bahman Bahmani, Abdur Chowdhury, Ashish Goel. 2010

405 citations recorded by the source corpus.

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 e, the expected total work needed to maintain an accurate estimate (using the Monte Carlo method) of the PageRank of every node at all times is [EQUATION]. 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 [EQUATION] total time and the Monte Carlo method needs O(mn/e) total time; both are prohibitively expensive. 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 α 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.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Predict then Propagate: Graph Neural Networks meet Personalized PageRank (2018, background): “Furthermore, faster or incremental approximations of personalized PageRank (Bahmani et al., 2010; 2011; Lofgren et al., 2014) and more sophisticated propagation schemes would also beneﬁt the method.”
Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time (2017, background): “Manyalgorithmsrandomwalks to harness the graph structure for recommendations [2, 3, 28].”
The Effect of Recommendations on Network Structure (2016, methodology): “The friend-of-friend algorithm and similar approaches, such as personalized PageRank, generate recommendations by exploring a user’s local network neighborhood [4, 15].”
Scalable Graph Embedding for Asymmetric Proximity (2017, methodology): “Due to the complexity of the iteration-style computation, Monte Carlo approach is usually adopted when calculating Rooted PageRank values (Gupta et al. 2013; Fogaras et al. 2005; Bahmani, Chowdhury, and Goel 2010; Avrachenkov et al. 2007).”
Fast personalized PageRank on MapReduce (2011, methodology): “[3] propose Monte Carlo algorithms for Personalized (and Global) PageRank approximation in the random access model.”
Computing Personalized PageRank Quickly by Exploiting Graph Structures (2014, methodology): “PPR and other personalized random walk based measures are very eﬀective in various applications such as link prediction [34] and friend recommendation [8] in social networks.”
Data Poisoning Attack against Unsupervised Node Embedding Methods (2018, methodology): “We comapare with several baselines: (1) random attack: this baseline is general and used for both integrity attack and availability attack. We randomly add or remove edges; (2) personalized PageRank (Bahmani et al., 2010): this baseline is only used for integrity attack. Given a target edge (A;B), w”
A benchmarking study of embedding-based entity alignment for knowledge graphs (2020, background): “GC NA lig n At trE IM US E SE A RS N4 EA Mu lt iK E RD GC N Pr op or tio n 0 1 [2,4] >= 5”
An Uncertainty-Aware Approach for Exploratory Microblog Retrieval (2015, methodology): “For the affected random walks, existing incremental graph ranking algorithms [3] perform re-sampling and update the ranking scores by aggregating the statistics of these new random walks into the original results.”
FAST-PPR: scaling personalized pagerank estimation for large graphs (2014, methodology): “are easy to update in dynamic settings [15].”
WTF: the who to follow service at Twitter (2013, methodology): “A useful “primitive” that underlies many of our user recommendation algorithms is what we call a user’s “circle of trust”, which is the result of an egocentric random walk (similar to personalized PageRank [8, 2]).”
PageRank beyond the Web (2014, background): “Localized PageRank is believed to be part of Twitter’s follower suggestion scheme too [Bahmani et al., 2010].”