On the Diffusion Geometry of Graph Laplacians and Applications
Preprint
Abstract
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\} \neq \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} + \varepsilon\right)}.$$ $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.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Localization of quantum states and landscape functionsProceedings of the American Mathematical Society, 2017
- Effective Confining Potential of Quantum States in Disordered MediaPhysical Review Letters, 2016
- Sharp L 1-Poincaré inequalities correspond to optimal hypersurface cutsArchiv der Mathematik, 2015
- Lower Bounds on Nodal Sets of Eigenfunctions via the Heat FlowCommunications in Partial Differential Equations, 2014
- Normalized Cuts Are Approximately Inverse Exit TimesSIAM Journal on Matrix Analysis and Applications, 2013
- Universal mechanism for Anderson and weak localizationProceedings of the National Academy of Sciences, 2012
- Metastability and Low Lying Spectra¶in Reversible Markov ChainsCommunications in Mathematical Physics, 2002
- Brownian motion and the fundamental frequency of a drumDuke Mathematical Journal, 1994
- Computing the volume of convex bodies: a case where randomness provably helps1991
- Probabilistic approach to the neumann problemCommunications on Pure and Applied Mathematics, 1985