On the Diffusion Geometry of Graph Laplacians and Applications

We study directed, weighted graphs G=(V,E) and consider the (not necessarily symmetric) averaging operator (Lu)(i) = -sum_j ~ ipij (u(j) - u(i)), where pij are normalized edge weights. Given a vertex i ∈ V, we define the diffusion distance to a set B subset V as the smallest number of steps dB(i) ∈ mathbbN required for half of all random walks started in i and moving randomly with respect to the weights pij to visit B within dB(i) steps. Our main result is that the eigenfunctions interact nicely with this notion of distance. In particular, if u satisfies Lu = λ u on V and B = left i ∈ V: - varepsilon ≤ u(i) ≤ varepsilon right neq emptyset, then, for all i ∈ V, dB(i) logleft( frac1|1-λ| right) ≥ logleft( frac |u(i)| |u|_L∞ right) - logleft(frac12 + varepsilonright). dB(i) is a remarkably good approximation of |u| in the sense of having very high correlation. The result implies that the classical one-dimensional spectral embedding preserves particular aspects of geometry in the presence of clustered data. We also give a continuous variant of the result which has a connection to the hot spots conjecture.