  PageRank is a famous measure of graph centrality that has numerous
applications in practice. The problem of computing a single node's PageRank has
been the subject of extensive research over a decade. However, existing methods
still incur large time complexities despite years of efforts. Even on
undirected graphs where several valuable properties held by PageRank scores,
the problem of locally approximating the PageRank score of a target node
remains a challenging task. Two commonly adopted techniques, Monte-Carlo based
random walks and backward push, both cost $O(n)$ time in the worst-case
scenario, which hinders existing methods from achieving a sublinear time
complexity like $O(\sqrt{m})$ on an undirected graph with $n$ nodes and $m$
edges.
  In this paper, we focus on the problem of single-node PageRank computation on
undirected graphs. We propose a novel algorithm, SetPush, for estimating
single-node PageRank specifically on undirected graphs. With non-trival
analysis, we prove that our SetPush achieves the
$\tilde{O}\left(\min\left\{d_t, \sqrt{m}\right\}\right)$ time complexity for
estimating the target node $t$'s PageRank with constant relative error and
constant failure probability on undirected graphs. We conduct comprehensive
experiments to demonstrate the effectiveness of SetPush.
