pipette
ESEspañol

Instance-Optimality of Single-Pair Personalized PageRank

Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup, Hanzhi Wang, Shuyi Yan

Preprint

In the authors' words

We consider discounted random walks in a directed simple graph . Such a walk terminates at each step with a constant probability and otherwise continues to a uniform random out-neighbor. Given a pair , we denote by the probability of such a discounted random walk starting at terminates at . This probability is referred to as the Personalized PageRank (PPR) of with respect to . The problem of estimating within a constant multiplicative factor with constant success probability for a given vertex pair is called the single-pair PPR estimation problem. We investigate the instance-optimality of single-pair PPR estimation in directed graphs. We present a new algorithm that aims at instance-optimal running time up to polylogarithmic factors. In other words, no correct algorithm can run faster than our algorithm on any valid graph by more than a polylogarithmic factor. We show that our algorithm is instance-optimal in the standard adjacency-list query model if is not known (as is often the case for most of the large networks to which PPR is applied). When is known, our algorithm is still instance-optimal for sparse graphs. For denser graphs, when is known, we show that no algorithm can achieve general instance-optimality. For the multiplicative approximation of PPR, we also improve the worst-case complexity from to the near-optimal . This is not only for the single-pair discussed above, but also for the single-source and single-target variants of the PPR estimation problem.

Main resultLimitation the authors admit

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.