We study directed, weighted graphs $G=(V,E)$ and consider the (not necessarily symmetric) averaging operator $$ (mathcal{L}u)(i) = -sum_{j sim_{} i}{p_{ij} (u(j) - u(i))},$$ where $p_{ij}$ are normalized edge weights. Given a vertex $i in V$, we define the diffusion distance to a set $B subset V$ as the smallest number of steps $d_{B}(i) in mathbb{N}$ required for half of all random walks started in $i$ and moving randomly with respect to the weights $p_{ij}$ to visit $B$ within $d_{B}(i)$ steps. Our main result is that the eigenfunctions interact nicely with this notion of distance. In particular, if $u$ satisfies $mathcal{L}u = lambda u$ on $V$ and $$ B = left{ i in V: - varepsilon leq u(i) leq varepsilon right} eq emptyset,$$ then, for all $i in V$, $$ d_{B}(i) log{left( frac{1}{|1-lambda|} right) } geq log{left( frac{ |u(i)| }{|u|_{L^{infty}}} right)} - log{left(frac{1}{2} + varepsilonright)}.$$ $d_B(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.
Download