A Unified View of Diffusion Maps and Signal Processing on Graphs

In this paper we explore the connection between diffusion maps and signal processing on graphs. We aim to create a common ground for both approaches through the definition of the graph shift operator as the transition matrix of a Markov chain defined on the graph. We then demonstrate several advantages of this definition, as well as the resulting diffusion map interpretation of operations defined in signal processing on graphs. For example, one advantage is the ability to process a graph signal over a Euclidean domain. Another advantage is the ability to use the Nystr\{o}m extension for computationally efficient interpolation of signals over a graph. In addition, we present a definition of signals over a graph and show the relation between the diffusion embedding vectors and the spectrum of these signals.