  In this paper we present the Markov variation, a smoothness measure which
offers a probabilistic interpretation of graph signal smoothness. This measure
is then used to develop an optimization framework for graph signal
interpolation. Our approach is based on diffusion embedding vectors and the
connection between diffusion maps and signal processing on graphs. As diffusion
embedding vectors may be expensive to compute for large graphs, we present a
computationally efficient method, based on the Nystr\"{o}m extension, for
interpolation of signals over a graph. We demonstrate our approach on the MNIST
dataset and a dataset of daily average temperatures around the US. We show that
our method outperforms state of the art graph signal interpolation techniques
on both datasets, and that our computationally efficient reconstruction
achieves slightly reduced accuracy with a large computational speedup.
