  Personalized PageRank (PPR) is a widely used node proximity measure in graph
mining and network analysis. Given a source node $s$ and a target node $t$, the
PPR value $\pi(s,t)$ represents the probability that a random walk from $s$
terminates at $t$, and thus indicates the bidirectional importance between $s$
and $t$. The majority of the existing work focuses on the single-source
queries, which asks for the PPR value of a given source node $s$ and every node
$t \in V$. However, the single-source query only reflects the importance of
each node $t$ with respect to $s$. In this paper, we consider the {\em
single-target PPR query}, which measures the opposite direction of importance
for PPR. Given a target node $t$, the single-target PPR query asks for the PPR
value of every node $s\in V$ to a given target node $t$. We propose RBS, a
novel algorithm that answers approximate single-target queries with optimal
computational complexity. We show that RBS improves three concrete
applications: heavy hitters PPR query, single-source SimRank computation, and
scalable graph neural networks. We conduct experiments to demonstrate that RBS
outperforms the state-of-the-art algorithms in terms of both efficiency and
precision on real-world benchmark datasets.
