  We present new, more efficient algorithms for estimating random walk scores
such as Personalized PageRank from a given source node to one or several target
nodes. These scores are useful for personalized search and recommendations on
networks including social networks, user-item networks, and the web. Past work
has proposed using Monte Carlo or using linear algebra to estimate scores from
a single source to every target, making them inefficient for a single pair. Our
contribution is a new bidirectional algorithm which combines linear algebra and
Monte Carlo to achieve significant speed improvements. On a diverse set of six
graphs, our algorithm is 70x faster than past state-of-the-art algorithms. We
also present theoretical analysis: while past algorithms require $\Omega(n)$
time to estimate a random walk score of typical size $\frac{1}{n}$ on an
$n$-node graph to a given constant accuracy, our algorithm requires only
$O(\sqrt{m})$ expected time for an average target, where $m$ is the number of
edges, and is provably accurate.
  In addition to our core bidirectional estimator for personalized PageRank, we
present an alternative algorithm for undirected graphs, a generalization to
arbitrary walk lengths and Markov Chains, an algorithm for personalized search
ranking, and an algorithm for sampling random paths from a given source to a
given set of targets. We expect our bidirectional methods can be extended in
other ways and will be useful subroutines in other graph analysis problems.
