Bidirectional PageRank Estimation: From
Average-Case to Worst-Case
Peter Lofgren1 , Siddhartha Banerjee2 , and Ashish Goel1
1

Stanford University, Stanford CA 94305, USA
Cornell University, Ithaca NY 14850, USA

arXiv:1507.08705v3 [] 15 Dec 2015

2

Abstract. We present a new algorithm for estimating the Personalized PageRank (PPR) between a source and target node on undirected
graphs, with sublinear running-time guarantees over the worst-case choice
of source and target nodes. Our work builds on a recent line of work on
bidirectional estimators for PPR, which obtained sublinear running-time
guarantees but in an average-case sense, for a uniformly random choice of
target node. Crucially, we show how the reversibility of random walks on
undirected networks can be exploited to convert average-case to worstcase guarantees. While past bidirectional methods combine forward random walks with reverse local pushes, our algorithm combines forward
local pushes with reverse random walks. We also discuss how to modify
our methods to estimate random-walk probabilities for any length distribution, thereby obtaining fast algorithms for estimating general graph
diffusions, including the heat kernel, on undirected networks.

1

Introduction

Ever since their introduction in the seminal work of Page et al. [23], PageRank
and Personalized PageRank (PPR) have become some of the most important
and widely used network centrality metrics (a recent survey [13] lists several
examples). At a high level, for any graph G, given ‘teleport’ probability α and a
‘personalization distribution’ σ over the nodes of G, PPR models the importance
of every node from the point of view of σ in terms of the stationary probabilities
of ‘short’ random walks that periodically restart from σ with probability α. It
can be defined recursively as giving importance α to σ, and in addition giving
every node importance based on the importance of its in-neighbors.
Formally, given normalized adjacency matrix W = D−1 A, the Personalized
PageRank vector πσ with respect to source distribution σ is the solution to
πσ = ασ + (1 − α)πσ W.

(1)

An equivalent definition is in terms of the terminal node of a random-walk
starting from σ. Let {X0 , X1 , X2 , . . .} be a random-walk starting from X0 ∼ σ,
and L ∼ Geometric(α). Then the PPR of any node t is given by [4]:
πσ (t) = P[XL = t]

(2)

2

The equivalence of these definitions can be seen using a power series expansion.
In this work, we focus on developing PPR-estimators with worst-case sublinear guarantees for undirected graphs. Apart from their technical importance, our
results are are of practical relevance as several large-scale applications of PPR are
based on undirected networks. For example, Facebook (which is an undirected
social network) used Personalized PageRank for friend recommendation [5]. The
social network Twitter is directed, but Twitter’s friend recommendation algorithm (Who to Follow) [16] uses an algorithm called personalized SALSA [19,6],
which first converts the directed network into an expanded undirected graph 3 ,
and then computes PPR on this new graph. Random walks have also been used
for collaborative filtering by the YouTube team [7] (on the undirected user-item
bipartite graph), to predict future items a user will view. Applications like this
motivate fast algorithms for PPR estimation on undirected graphs.
Equations (1) and (2) suggest two natural estimation algorithms for PPR
– via linear-algebraic iterative techniques, and using Monte Carlo. The linear
algebraic characterization of PageRank in Eqn. (1) suggests the use of power
iteration (or other localized iterations; cf Section 1.2 for details), while Eqn. (2)
is the basis for a Monte-Carlo algorithm, wherein we estimate πσ [t] by sampling
independent L-step paths, each starting from a random state sampled from σ.
For studying PageRank estimation algorithms, smaller probabilities are more
difficult to estimate than large ones, so a natural parametrization is in terms
of the minimum PageRank we want to detect. Formally, given any source σ,
target node t ∈ V and a desired minimum probability threshold δ, we want
algorithms that give accurate estimates whenever πσ [t] ≥ δ. Improved algorithms
are motivated by the slow convergence of these algorithms: both Monte Carlo
and linear algebraic techniques have a running time of Ω(1/δ) for PageRank
estimation. Furthermore this is true not only for worst case choices of target state
t, but on average Monte-Carlo requires Ω(1/δ) time to estimate a probability of
size δ. Power iteration takes Θ(m) time, where m is the number of edges, and
the work [21] shows empirically that the local version of power-iteration scales
with 1/δ for δ > 1/m.
In a recent line of work, linear-algebraic and Monte-Carlo techniques were
combined to develop new bidirectional PageRank estimators FAST-PPR [22] and
Bidirectional-PPR [20], which gave the first significant improvement in the
running-time of PageRank estimation since the development of Monte-Carlo
techniques. Given an arbitrary source distribution σ and a uniform random
target node t, these estimators were shown 
to return
 an accurate PageRank
q
d/δ , where d = m/n is the
estimate with an average running-time of Õ
 q

average degree of the graph. Given Õ n d/δ precomputation and storage,
3

Specifically, for each node u in the original graph, SALSA creates two virtual nodes,
a “consumer-node” u0 and a “producer-node” u00 , which are linked by an undirected
edge. Any directed edge (u, v) is then converted into an undirected edge (u0 , v 00 ) from
u’s consumer node to v’s producer node.

3

the authors prove worst case guarantees for this bidirectional estimator but in
practice that is a large precomputation requirement. This raised the challenge
of designing an algorithm with similar running-time guarantees over a worstcase choice of target node t. Inspired by the bidirectional estimators in [22,20],
we propose a new PageRank estimator for undirected graphs with worst-case
running time guarantees.

1.1

Our Contribution

We present the first estimator for personalized PageRank with sublinear running time in the worst case on undirected graphs. We formally present our
Undirected-BiPPR algorithm in Section 2, and prove that it has the following
accuracy and running-time guarantees:
Result 1 (See Theorem 1 in Section 2) Given any undirected graph G, teleport probability α, source node s, target node t, threshold δ and relative error ,
the Undirected-BiPPR estimator (Algorithm 2) returns an unbiased estimate
π
bs [t] for πs [t], which, with probability greater than 1 − pf ail , satisfies:
|b
πs [t] − πs [t]| < max {πs [t], 2eδ} .
Result 2 (See Theorem 2 in Section 2) Let any undirected graph G, teleport probability α, threshold δ and desired relative error  be given. For any
source,
 the Undirected-BiPPR algorithm has a running-time
 √target pairq(s, t),
ln(1/pf ail )
dt
, where dt is the degree of the target node t.
of O

δ
In personalization applications, we are often only interested in personalized importance scores if they are greater than global importance scores, so it is natural
to set δ based on the global importance of t. Assuming G is connected, in the limit
α → 0, the PPR vector for any start node s converges to the stationary distribution of infinite-length random-walks on G – that is limα→0 πs [t] = dt /m. This
suggests that a natural PPR significance-test is to check whether πs (t) ≥ dt /m.
To this end, we have the following corollary:
Result 3 (See Corollary 1 in Section 2) For any graph G and any (s, t)
pair such that πs (t) ≥ dmt , then with high probability 4 , Undirected-BiPPR returns
√ an estimate πs (t) with relative error  with a worst-case running-time of
O ( m log n/).
Finally, in Section 3, using ideas from [8], we extend our technique to estimating more general random-walk transition-probabilities on undirected graphs,
including graph diffusions and the heat kernel [11,18].
4

Following convention, we use w.h.p. to mean with probability greater than 1 −

1
.
n

4

1.2

Existing Approaches for PageRank Estimation

We first summarize the existing methods for PageRank estimation:
Monte Carlo Methods: A standard method [4,9] for estimating πσ [t] is by
using the terminal node of independently generated random walks of length
L ∼ Geometric(α) starting from a random node sampled from σ. Simple cone
centration arguments show that we need Θ(1/δ)
samples to get an accurate
estimate of πσ [t], irrespective of the choice of t and graph G.
Linear-Algebraic Iterations: Since the PageRank vector is the stationary
distribution of a Markov chain, it can also be estimated via forward or reverse
power iterations. A direct power iteration is often infeasible for large graphs; in
such cases, it is preferable to use localized power iterations [2,1]. These localupdate methods can also be used for other transition probability estimation
problems such as heat kernel estimation [18]. Local update algorithms are often
fast in practice, as unlike full power iteration methods they exploit the local
structure of the chain. However even in sparse Markov chains and for a large
fraction of target states, their running time can be Ω(1/δ). For example, consider
a random walk on a random d-regular graph and let δ = o(1/n). Then for
` ∼ logd (1/δ), verifying πes [t] > δ is equivalent to uncovering the entire logd (1/δ)
neighborhood of s. However since a large random d-regular graph is (w.h.p.) an
expander, this neighborhood has Ω(1/δ) distinct nodes.
Bidirectional Techniques: Bidirectional methods are based on simultaneously
working forward from the source node s and backward from the target node
t in order to improve the running-time. One example of such a bidirectional
technique is the use of colliding random-walks to estimate length-2` randomwalk transition probabilities in regular undirected graphs [14,17] – the main idea
here is to exploit the reversibility by using two independent random walks of
length ` starting from s and t respectively, and detecting if they collide. This
results in reducing the number of walks required by a square-root factor, based
on an argument similar to the birthday-paradox.
The FAST-PPR algorithm of Lofgren et al. [22] was the first bidirectional
algorithm for estimating PPR in general graphs; this was subsequently refined
and improved by the Bidirectional-PPR algorithm [20], and also generalized
to other Markov chain estimation problems [8]. These algorithms are based on
using a reverse local-update iteration from the target t (adapted from Andersen
et al. [1]) to smear the mass over a larger target set, and then using randomwalks from the source s to detect this target set. From a theoretical perspective, a
significant breakthrough was in showing that for arbitrary choice of source
qnode

s these bidirectional algorithms achieved an average running-time of Õ( d/δ)
over uniform-random choice of target node t – in contrast, both local-update and
Monte Carlo has a running-time of Ω(1/δ) for uniform-random targets. More
recently, [10] showed that a similar bidirectional technique achieved a sublinear
query-complexity for global PageRank computation, under a modified query
model, in which all neighbors of a given node could be found in O(1) time.

5

2

PageRank Estimation in Undirected Graphs

We now present our new bidirectional algorithm for PageRank estimation in
undirected graphs.
2.1

Preliminaries

We consider an undirected graph G(V, E), with n nodes and m edges. For ease
of notation, we henceforth consider unweighted graphs, and focus on the simple
case where σ = es for some single node s. We note however that all our results
extend to weighted graphs and any source distribution σ in a straightforward
manner.
2.2

A Symmetry for PPR in Undirected Graphs

The Undirected-BiPPR Algorithm critically depends on an underlying reversibility property exhibited by PPR vectors in undirected graphs. This property, stated
before in several earlier works [3,15], is a direct consequence of the reversibility
of random walks on undirected graphs. To keep our presentation self-contained,
we present this property, along with a simple probabilistic proof, in the form of
the following lemma:
Lemma 1. Given any undirected graph G, for any teleport probability α ∈ (0, 1)
and for any node-pair (s, t) ∈ V 2 , we have:
πs [t] =

dt
πt [s].
ds

Proof. For path P = {s, v1 , v2 , . . . , vk , t} in G, we denote its length as `(P )
(here `(P ) = k + 1), and define its reverse path to be P = {t, vk , . . . , v2 , v1 , s} –
note that `(P ) = `(P ). Moreover, we know that a random-walk starting from s
traverses path P with probability P[P ] = d1s · d1v · . . . · dv1 , and thus, it is easy
1
k
to see that we have:
P[P ] · ds = P[P ] · dt
(3)
Now let Pst denote the set of paths in G starting at s and terminating at t. Then
we can re-write Eqn. (2) as:
πs [t] =

Y
P ∈Pst

2.3

α(1 − α)`(P ) P[P ] =

Y
P ∈Pts

α(1 − α)`(P ) P[P ] =

dt
πt [s] 
ds

The Undirected-BiPPR Algorithm

At a high level, the Undirected-BiPPR algorithm has two components:

6

– Forward-work: Starting from source s, we first use a forward local-update
algorithm, the ApproximatePageRank(G, α, s, rmax ) algorithm of Andersen et
al. [2] (shown here as Algorithm 1). This procedure begins by placing one
unit of “residual” probability-mass on s, then repeatedly selecting some node
u, converting an α-fraction of the residual mass at u into probability mass,
and pushing the remaining residual mass to u’s neighbors. For any node u, it
returns an estimate ps [u] of its PPR πs [u] from s as well as a residual rs [u]
which represents un-pushed mass at u.
– Reverse-work: We next sample random walks of length L ∼ Geometric(α)
starting from t, and use the residual at the terminal nodes of these walks
to compute our desired PPR estimate. Our use of random walks backwards
from t depends critically on the symmetry in undirected graphs presented in
Lemma 1.
Note that this is in contrast to FAST-PPR and Bidirectional-PPR, which performs the local-update step in reverse from the target t, and generates randomwalks forwards from the source s.
Algorithm 1 ApproximatePageRank(G, α, s, rmax ) [2]
Inputs: graph G, teleport probability α, start node s, maximum residual rmax
1: Initialize (sparse) estimate-vector ps = 0 and (sparse) residual-vector rs = es
(i.e. rs [v] = 1 if v = s; else 0)
2: while ∃u ∈ V s.t. rsd[u]
> rmax do
u
3:
for v ∈ N [u] do
4:
rs [v] += (1 − α)rs [u]/du
5:
end for
6:
ps [u] += αrs [u]
7:
rs [u] = 0
8: end while
9: return (ps , rs )

In more detail, our algorithm will choose a maximum residual parameter
rmax , and apply the local push operation in Algorithm 1 until for all v, rs [v]/dv <
rmax . Andersen et al. [2] prove that their local-push operation preserves the
following invariant for vectors (ps , rs ):
X
πs [t] = ps [t] +
rs [v]πv [t],
∀ t ∈ V.
(4)
v∈V

Since we ensure that ∀v, rs [v]/dv < rmax , it is natural at this point to use the
symmetry Lemma 1 and re-write this as:
X rs [v]
πs [t] = ps [t] + dt
πt [v].
dv
v∈V
P
Now using the fact that
t πv [t] = nπ[t] get that ∀ t ∈ V , |πs [t] − ps [t]| ≤
rmax dt nπ[t].

7

However, we can get a more accurate estimate by using the residuals. The
key idea of our algorithm is to re-interpret this as an expectation:


rs [v]
πs [t] = ps [t] + dt EV ∼πt
.
(5)
dV
We estimate the expectation using standard Monte-Carlo. Let Vi ∼ πt and
Xi = rs (Vi )dt /dVi , so we have πs [t] = ps [t] + E[X]. Moreover, each sample Xi is
bounded by dt rmax (this is the stopping condition for ApproximatePageRank),
which allows us to efficiently estimate its expectation. To this end, we generate
w random walks, where
c rmax
w= 2
.
 δ/dt
The choice of c is specified in Theorem 1. Finally, we return the estimate:
π
bs [t] = pt [s] +

w
1 X
Xi .
w i=1

The complete pseudocode is given in Algorithm 2.

Algorithm 2 Undirected-BiPPR(s, t, δ)
Inputs: graph G, teleport probability α, start node s, target node t, minimum probability δ, accuracy parameter c = 3 ln (2/pfail ) (cf. Theorem 1)
1: (ps , rs ) = ApproximatePageRank(s, rmax )
2: Set number of walks w = cdt rmax /(2 δ)
3: for index i ∈ [w] do
4:
Sample a random walk starting from t, stopping after each step with probability
α; let Vi be the endpoint
5:
Set Xi = rs (Vi )/dVi
6: end for
P
7: return π
bs [t] = ps [t] + (1/w) i∈[w] Xi

2.4

Analyzing the Performance of Undirected-BiPPR

Accuracy Analysis: We first prove that Undirected-BiPPR returns an unbiased estimate with the desired accuracy:
Theorem 1. In an undirected graph G, for any source node s, minimum threshold δ, maximum residual rmax , relative error , and failure probability pfail , Algorithm 2 outputs an estimate π
bs [t] such that with probability at least 1 − pfail
we have:
|πs [t] − π̂s [t]| ≤ max{πs [t], 2eδ}.
The proof follows a similar outline as the proof of Theorem 1 in [20]. For
completeness, we sketch the proof here:

8

Proof. As stated in Algorithm 2, we average over w = cdt rmax /2 δ walks, where
c is a parameter we choose later. Each walk is of length Geometric(α), and we
denote Vi as the last node visited by the ith walk; note that Vi ∼ πt . As defined
above, let Xi = rs (Vi )dt /dVi ; the estimate returned by Undirected-BiPPR is:
π
bs [t] = pt [s] +

w
1 X
Xi .
w i=1

First, from Eqn. (5), we have that E[b
πs [t]] = πs [t]. Also, ApproximatePageRank
guarantees that for all v, rs [v] < dv rmax , and so each Xi is bounded in [0, dt rmax ];
for convenience, we rescale Xi by defining Yi = dt r1max Xi .
We now show concentration of the estimates via the following Chernoff
bounds (see Theorem 1.1 in [12]):
2
1. P[|Y − E[Y ]| > E[Y ]] < 2 exp(− 3 E[Y ])
2. For any b > 2eE[Y ], P[Y > b] ≤ 2−b
We perform a case analysis based on whether E[Xi ] ≥ δ or E[Xi ] < δ. First, if
E[Xi ] ≥ δ, then we have E[Y ] = dt rwmax E[Xi ] = 2cδ E[Xi ] ≥ c2 , and thus:


P [|b
πs [t] − πs [t]| > πs [t]] ≤ P X̄ − E[Xi ] > E[Xi ] = P [|Y − E[Y ]| > E[Y ]]
 2

 c

≤ 2 exp − E[Y ] ≤ 2 exp −
≤ pfail ,
3
3
where the last line holds as long as we choose c ≥ 3 ln (2/pfail ).
Suppose alternatively that E[Xi ] < δ. Then:


w
P[|π̂s [t] − πs [t]| > 2eδ] = P[ X̄ − E[Xi ] > 2eδ] = P |Y − E[Y ]| >
2eδ
dt rmax


w
2eδ .
≤P Y >
dt rmax
At this point we set b = 2eδw/dt rmax = 2ec/2 and apply the second Chernoff
bound. Note that E[Y ] = cE[Xi ]/2 δ < c/2 , and hence we satisfy b > 2eE[Y ].
We conclude that:
P[|π̂s [t] − πs [t]| > 2eδ] ≤ 2−b ≤ pfail
2


1
as long as we choose c such that c ≥ 2e
log2 pfail
. The proof is completed by
combining both cases and choosing c = 3 ln (2/pfail ). 

Running Time Analysis: The more interesting analysis is that of the runningtime of Undirected-BiPPR – we now prove a worst-case running-time bound:
Theorem 2. In an undirected graph, for any source node (or distribution) s,
target t with degree dt , threshold δ, maximum residual rmax , relative error , and
failure probability pfail , Undirected-BiPPR has a worst-case running-time of:

q
1 r
log pfail
dt 
.
O

δ

9

Before proving this result, we first state and prove a crucial lemma from [2]:
Lemma 2 (Lemma 2 in [2]). Let T be the total number of push operations performed by ApproximatePageRank, and let dk be the degree of the vertex involved
in the k th push. Then:
T
X

dk ≤

k=1

1
αrmax

Proof. Let vk be the vertex pushed in the k th step – then by definition, we have
that rs (vk ) > rmax dk . Now after the local-push operation, the sum residual ||rs ||1
decreases by at least αrmax dk . However, we started with ||rs ||1 = 1, and thus we
PT
have k=1 αrmax dk ≤ 1.

Note also that the amount of work done while pushing from a node v is dv .
Proof (of Theorem 2). As proven in Lemma 2, the push forward step takes

 total
time O (1/αrmax ) in the worst-case. The random walks take O(w) = O
time. Thus our total time is
!
1
ln pfail
1
rmax
O
+
.
rmax
2 δ/dt
Balancing this by choosing rmax =

q 
ln p 1

1 rmax
2 δ/dt

p
δ/dt , we get total running-time:

fail

q
O

1
ln pfail



r


dt 
.
δ



We can get a cleaner worst-case running time bound if we make a natural assumption on πs [t]. In an undirected graph, if we let α = 0 and take infinitely long
walks, the stationary probability of being at any node t is dmt . Thus if πs [t] < dmt ,
then s actually has a lower PPR to t than the non-personalized stationary probability of t, so it is natural to say t is not significant for s. If we set a significance
threshold of δ = dmt , and apply the previous theorem, we immediately get the
following:
Corollary 1. If πs [t] ≥ dmt , we can estimate πs [t] within relative error  with
probability greater than 1 − n1 in worst-case time:


log n √
O
m .

In contrast, the running time for Monte-Carlo to achieve the same accuracy
fail )
guarantee is O 1δ log(1/p
, and the running time for ApproximatePageRank
α2
 
¯
d
is O δα
. The FAST-PPR algorithm of [22] has an average case running time of

10


O

1
α2

q q
d¯
δ

log(1/pfail ) log(1/δ)
log(1/(1−α))


for uniformly chosen targets, but has no clean

worst-case running time bound because its running time depends on the degree
of nodes pushed from in the linear-algebraic part of the algorithm.

3

Extension to Graph Diffusions

PageRank and Personalized PageRank are a special case of a more general set
of network-centrality metrics referred to as graph diffusions [11,18]. In a a graph
diffusion we assign a weight αi to walks of length i. The score is then is a
polynomial function of the random-walk transition probabilities of the form:
f (W, σ) :=

∞
X


αi σW i ,

i=0

P

where αi ≥ 0, i αi = 1. To see that PageRank has this form, we can expand
Eqn. (1) via a Taylor series to get:
πσ =

∞
X

α(1 − α)i σW i



i=1

Another important graph diffusion is the heat kernel hσ , which corresponds to
the scaled matrix exponent of (I − W )−1 :
−1

hσ,γ = e−γ(I−W )

=

∞
X
e−γ γ i
i=1

i!

σW i



In [8], Banerjee and Lofgren extended Bidirectional-PPR to get bidirectional
estimators for graph diffusions and other general Markov chain transition-probability
estimation problems. These algorithms inherited similar performance guarantees
to Bidirectional-PPR – in particular, they had good expected running-time
bounds for uniform-random choice of target node t. We now briefly discuss how
we can modify Undirected-BiPPR to get an estimator for graph diffusions in
undirected graphs with worst-case running-time bounds.
First, we observe that Lemma 1 extends to all graph diffusions, as follows:
Corollary 2. Let any undirected graph G with random-walk
matrix W , and
P
∞
any set of P
non-negative length
weights
(α
)
with
α
=
1
be
given. Define
i
i
i=0

∞
f (W, σ) = i=0 αi σW i . Then for any node-pair (s, t) ∈ V 2 , we have:
f (W, es ) =

dt
f (W, et ) .
ds

As before, the above result is stated for unweighted graphs, but it P
also extends
to random-walks on weighted undirected graphs, if we define di = j wij .
Next, observe that for any graph diffusion f (·), the truncated sum f `max =

P∞
P`max
T i
obeys: ||f − f `max ||∞ ≤ `max +1 αk Thus a guarantee on an
i=0 αi πσ P

11

estimate for the truncated sum directly translates to a guarantee on the estimate
for the diffusion.
The main idea in [8] is to generalize the bidirectional estimators for PageRank
to estimating multi-step transitions probabilities (for short, MSTP). Given a
source node s, a target node t, and length ` ≤ `max , we define:
p`s [t] = P[Random-walk of length ` starting from s terminates at t]
Note from Corollary 2, we have for any pair (s, t) and any `, p`s [t]ds = p`t [s]dt .
Now in order to develop a bidirectional estimator for p`s [t], we need to define
a local-update step similar to ApproximatePageRank. For this, we can modify
the REVERSE-PUSH algorithm from [8], as follows.
Similar to ApproximatePageRank, given a source node s and maximum length
`max , we associate with each length ` ≤ `max an estimate vector qs` and a residual
vector rs` . These are updated via the following ApproximateMSTP algorithm:
Algorithm 3 ApproximateMSTP(G, s, `max , rmax )
Inputs: Graph G, source s, maximum steps `max , maximum residual rmax
1: Initialize: Estimate-vectors qsk = 0 , ∀ k ∈ {0, 1, 2, . . . , `max },
Residual-vectors rs0 = es and rsk = 0 , ∀ k ∈ {1, 2, 3, . . . , `max }
2: for i ∈ {0, 1, . . . , `max } do
3:
while ∃ v ∈ S s.t. rti [v]/dv > rmax do
4:
for w ∈ N (v) do
5:
rsi+1 [w] += rsi [v]/dv
6:
end for
7:
qsi [v] += rsi [v]
8:
rsi [v] = 0
9:
end while
10: end for
max
11: return {qs` , rs` }``=0

The main observation now is that for any source s, target t, and length `,
max
satisfy
after executing the ApproximateMSTP algorithm, the vectors {qs` , rs` }``=0
the following invariant (via a similar argument as in [8], Lemma 1):
p`s [t] = qs` [t] +

` X
X
k=0 v∈V

rsk [v]pv`−k [t] = qs` [t] + dt

` X k
X
rs [v] `−k
p [v]
dv t

k=0 v∈V

As before, note now that the last term can be written as an expectation over
random-walks originating from t. The remaining algorithm, accuracy analysis,
and runtime analysis follow the same lines as those in Section 2.

4

Lower Bound

In [22], the authors prove an average case lower bound for PPR-Estimation. In
particular they prove that there exists a family of undirected 3-regular graphs

12

for which any algorithm that can distinguish between pairs (s, t) with πs [t] > δ
and pairs (s, t) with πs [t] < 2δ (distinguishing correctly with constant probability
√
8/9), must access Ω(1/ δ) edges
 graph. Since the algorithms in [22,20]
qof the
d/δ , where d is the average degree of the
solve this problem in time O
√
given graph, there remains a d gap between the lower bound and the best
algorithm for the average case. For the worst case (possibly parameterized by
some property of the graph or target node), the authors are unaware of any lower
bound stronger than this average case bound, and an interesting open question
is to prove a lower bound for the worst case.

5

Conclusion

We have developed Undirected-BiPPR, a new bidirectional PPR-estimator for
undirected graphs, which for any (s, t) pair such that πs [t] > d√
t /m, returns
an estimate with  relative-error in worst-case running time of O( m/). This
thus extends the average-case running-time improvements achieved in [22,20] to
worst-case bounds on undirected graphs, using the reversibility of random-walks
on undirected graphs. Whether such worst-case running-time results extend to
general graphs, or if PageRank computation is fundamentally easier on undirected graphs as opposed to directed graphs, remains an open question.

6

Acknowledgments

Research supported by the DARPA GRAPHS program via grant FA9550-121-0411, and by NSF grant 1447697. One author was supported by an NPSC
fellowship. Thanks to Aaron Sidford for a helpful discussion.

References
1. R. Andersen, C. Borgs, J. Chayes, J. Hopcraft, V. S. Mirrokni, and S.-H. Teng.
Local computation of pagerank contributions. In Algorithms and Models for the
Web-Graph. Springer, 2007.
2. R. Andersen, F. Chung, and K. Lang. Local graph partitioning using pagerank
vectors. In Foundations of Computer Science, 2006. FOCS’06. 47th Annual IEEE
Symposium on, 2006.
3. K. Avrachenkov, P. Gonçalves, and M. Sokol. On the choice of kernel and labelled
data in semi-supervised learning methods. In Algorithms and Models for the Web
Graph, pages 56–67. Springer, 2013.
4. K. Avrachenkov, N. Litvak, D. Nemirovsky, and N. Osipova. Monte carlo methods in pagerank computation: When one iteration is sufficient. SIAM Journal on
Numerical Analysis, 2007.
5. L. Backstrom and J. Leskovec. Supervised random walks: predicting and recommending links in social networks. In Proceedings of the fourth ACM international
conference on Web search and data mining. ACM, 2011.

13
6. B. Bahmani, A. Chowdhury, and A. Goel. Fast incremental and personalized
pagerank. Proceedings of the VLDB Endowment, 4(3):173–184, 2010.
7. S. Baluja, R. Seth, D. Sivakumar, Y. Jing, J. Yagnik, S. Kumar, D. Ravichandran,
and M. Aly. Video suggestion and discovery for youtube: taking random walks
through the view graph. In Proceedings of the 17th international conference on
World Wide Web. ACM, 2008.
8. S. Banerjee and P. Lofgren. Fast bidirectional probability estimation in markov
models. In NIPS, 2015.
9. C. Borgs, M. Brautbar, J. Chayes, and S.-H. Teng. A sublinear time algorithm
for pagerank computations. In Algorithms and Models for the Web Graph, pages
41–53. Springer, 2012.
10. M. Bressan, E. Peserico, and L. Pretto. Approximating pagerank locally with
sublinear query complexity. arXiv preprint arXiv:1404.1864, 2014.
11. F. Chung. The heat kernel as the pagerank of a graph. Proceedings of the National
Academy of Sciences, 2007.
12. D. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of
Randomized Algorithms. Cambridge University Press, 2009.
13. D. F. Gleich. PageRank beyond the web. arXiv, cs.SI:1407.5107, 2014. Accepted
for publication in SIAM Review.
14. O. Goldreich and D. Ron. On testing expansion in bounded-degree graphs. In
Studies in Complexity and Cryptography. Miscellanea on the Interplay between
Randomness and Computation. Springer, 2011.
15. V. Grolmusz. A note on the pagerank of undirected graphs. Information Processing
Letters, 2015.
16. P. Gupta, A. Goel, J. Lin, A. Sharma, D. Wang, and R. Zadeh. Wtf: The who
to follow service at twitter. In Proceedings of the 22nd international conference
on World Wide Web, pages 505–514. International World Wide Web Conferences
Steering Committee, 2013.
17. S. Kale, Y. Peres, and C. Seshadhri. Noise tolerance of expanders and sublinear
expander reconstruction. In IEEE FOCS’08. IEEE, 2008.
18. K. Kloster and D. F. Gleich. Heat kernel based community detection. In ACM
SIGKDD’14, 2014.
19. R. Lempel and S. Moran. The stochastic approach for link-structure analysis
(salsa) and the tkc effect. Computer Networks, 33(1):387–401, 2000.
20. P. Lofgren, S. Banerjee, and A. Goel. Personalized pagerank estimation and search:
A bidirectional approach. In WSDM, 2016.
21. P. Lofgren and A. Goel. Personalized pagerank to a target node. arXiv preprint
arXiv:1304.4658, 2013.
22. P. A. Lofgren, S. Banerjee, A. Goel, and C. Seshadhri. FAST-PPR: Scaling Personalized PageRank estimation for large graphs. In ACM SIGKDD’14. ACM, 2014.
23. L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking:
bringing order to the web. 1999.

