Shouldn't heat kernel on a weighted graph be inverse proportional to the shortest path length?

82 Views Asked by At

The heat kernel $k: \mathbb{R_{\geq 0}} \times \Omega \times \Omega \to \Bbb{R}_{\geq 0}$ on some domain $\Omega$ calculates the amount of energy (or information) transferred in time $t$ from $x \in \Omega$ to $y \in \Omega$. Intuitively, the value of $k(t, x, y)$ should be smaller for remote $x$ and $y$, which is reflected in e.g. the formula of heat kernel on $\Bbb{R}^n$: $$k(t, \mathbf{x}, \mathbf{y}) = \frac{1}{(4\pi t)^{n/2}}e^{-||\mathbf{x}-\mathbf{y}||^2/4t},\quad \mathbf{x}, \mathbf{y} \in \Bbb{R}^n.$$ However, when $\Omega$ is (the vertex set of) a complete weighted graph, the off-diagonal entries of heat kernel matrix $K_t = e^{-tL}$ (where $L$ is the Laplacian) are proportional to the weights of the corresponding edges. When the edge weights satisfy the triangle inequality and are positive, they are the shortest path distances between the vertices. Does it mean that the weights are not interpreted as distances by the heat kernel? Is there a way to construct (or approximate) the heat kernel regarding the graph as a finite metric space?