Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments

By Dániel Fogaras, Balázs Rácz, Károly Csalogány, Tamás Sarlós. 2005

340 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Information Systems, 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 Information Systems

In Statistical and Nonlinear Physics

Citations in the corpus

Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time (2017, background): “These types of Monte Carlo approaches measure the importance of one node relative to another, and recommendations can be made according to these scores [13].”
The query-flow graph: model and applications (2008, background): “In all our experiments, we chose a =0.85, as it is customary in the PageRank literature [4], and used the .1-norm of the di.erence of two successive iterates to decide when to stop.”
HeteSim: A General Framework for Relevance Measure in Heterogeneous Networks (2013, methodology): “It is extended to the scalable calculation for online queries [13], [14] an d the topk answers [15].”
On the Embeddability of Random Walk Distances (2013, methodology): “linear algebraic optimization [19, 29] and Monte Carlo approximation algorithms [13, 3].”
FAST-PPR: scaling personalized pagerank estimation for large graphs (2014, neutral): “This technique was first proposed by Jeh and Widom [2], and subsequently improved by other researchers [20, 9].”
Computing Personalized PageRank Quickly by Exploiting Graph Structures (2014, methodology): “Fogaras et al. [21] proposed a Monte Carlo based algorithm for PPR.”
PathSim (2011, background): “More discussions on how to scale the calculation for online queries are in [6, 18], etc.”
GraphJet: Real-Time Content Recommendations at Twitter (2016, methodology): “To introduce personalization, we include a reset step on the left-to-right edge traversals: with a ﬁxed probability α , we restart from the query vertex to ensure that the random walk doesn’t “stray” too far from the query vertex, which is the same intuition behind personalized PageRank [13, 4].”
Scalable Graph Embedding for Asymmetric Proximity (2017, methodology): “We follow the Monte-Carlo End-Point sampling method mentioned in (Fogaras et al. 2005), SampleEndPoint randomly samples a path p starting from v with a stopping probability of α, and returns the ending node u in p.”
WTF: the who to follow service at Twitter (2013, methodology): “It is wellknown that this Monte-Carlo approach will approximate the stationary distribution of random walk algorithms such as personalized PageRank [8] [2].”
Fast Incremental and Personalized PageRank (2010, methodology): “…use only the end points of these walks for our estimates) the approximate personalized PageRank vectors that we get would have at most R non-zero entries, which is signiﬁcantly fewer than what we need in all applications of interest; previous works [11,13] do not explore this tradeoﬀ in any detail.”