  We present a method to approximate pairwise distance on a graph, having an
amortized sub-linear complexity in its size. The proposed method follows the so
called heat method due to Crane et al. The only additional input are the values
of the eigenfunctions of the graph Laplacian at a subset of the vertices. Using
these values we estimate a random walk from the source points, and normalize
the result into a unit gradient function. The eigenfunctions are then used to
synthesize distance values abiding by these constraints at desired locations.
We show that this method works in practice on different types of inputs ranging
from triangular meshes to general graphs. We also demonstrate that the
resulting approximate distance is accurate enough to be used as the input to a
recent method for intrinsic shape correspondence computation.
