  Personalized PageRank (PPR) is an extensively studied and applied node
proximity measure in graphs. For a pair of nodes $s$ and $t$ on a graph
$G=(V,E)$, the PPR value $\pi(s,t)$ is defined as the probability that an
$\alpha$-discounted random walk from $s$ terminates at $t$, where the walk
terminates with probability $\alpha$ at each step. We study the classic
Single-Source PPR query, which asks for PPR approximations from a given source
node $s$ to all nodes in the graph. Specifically, we aim to provide
approximations with absolute error guarantees, ensuring that the resultant PPR
estimates $\hat{\pi}(s,t)$ satisfy $\max_{t\in
V}\big|\hat{\pi}(s,t)-\pi(s,t)\big|\le\varepsilon$ for a given error bound
$\varepsilon$. We propose an algorithm that achieves this with high
probability, with an expected running time of
  - $\widetilde{O}\big(\sqrt{m}/\varepsilon\big)$ for directed graphs, where
$m=|E|$;
  - $\widetilde{O}\big(\sqrt{d_{\mathrm{max}}}/\varepsilon\big)$ for undirected
graphs, where $d_{\mathrm{max}}$ is the maximum node degree in the graph;
  - $\widetilde{O}\left(n^{\gamma-1/2}/\varepsilon\right)$ for power-law
graphs, where $n=|V|$ and $\gamma\in\left(\frac{1}{2},1\right)$ is the extent
of the power law.
  These sublinear bounds improve upon existing results. We also study the case
when degree-normalized absolute error guarantees are desired, requiring
$\max_{t\in V}\big|\hat{\pi}(s,t)/d(t)-\pi(s,t)/d(t)\big|\le\varepsilon_d$ for
a given error bound $\varepsilon_d$, where the graph is undirected and $d(t)$
is the degree of node $t$. We give an algorithm that provides this error
guarantee with high probability, achieving an expected complexity of
$\widetilde{O}\left(\sqrt{\sum_{t\in
V}\pi(s,t)/d(t)}\big/\varepsilon_d\right)$. This improves over the previously
known $O(1/\varepsilon_d)$ complexity.
