# On the Diffusion Geometry of Graph Laplacians and Applications

arXiv: https://arxiv.org/abs/1611.03033 · HTML: https://mlsanity.com/paper/1611.03033/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2016.

## Built on by (most cited first, 2 of 2)

- [Hyperbolic Diffusion Embedding and Distance for Hierarchical Representation Learning](https://mlsanity.com/paper/2305.18962/) (2023)
- [Neural FIM for learning Fisher Information Metrics from point cloud data](https://mlsanity.com/paper/2306.06062/) (2023)

## Abstract (arXiv)

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.