  Heat kernel pagerank is a variation of Personalized PageRank given in an
exponential formulation. In this work, we present a sublinear time algorithm
for approximating the heat kernel pagerank of a graph. The algorithm works by
simulating random walks of bounded length and runs in time
$O\big(\frac{\log(\epsilon^{-1})\log
n}{\epsilon^3\log\log(\epsilon^{-1})}\big)$, assuming performing a random walk
step and sampling from a distribution with bounded support take constant time.
  The quantitative ranking of vertices obtained with heat kernel pagerank can
be used for local clustering algorithms. We present an efficient local
clustering algorithm that finds cuts by performing a sweep over a heat kernel
pagerank vector, using the heat kernel pagerank approximation algorithm as a
subroutine. Specifically, we show that for a subset $S$ of Cheeger ratio
$\phi$, many vertices in $S$ may serve as seeds for a heat kernel pagerank
vector which will find a cut of conductance $O(\sqrt{\phi})$.
