I am reading about diffusion maps. It is stated that here: "the diffusion map preserves the local geometry of the graph." We know that this embedding is based on the Markov matrix. Now, I am curious to know:
- How much does precise this statement? And what can we say about the global geometry rather than local geometry?
- Are there other approaches that can preserves the geometry of a graph?
I am new in this area and your detailed answers will be appreciated.
It can be made fairly precise I think. If the data are sampled from a manifold $(M,g)$, then as the number of samples goes to infinity, the graph Laplacian $L$ converges to the true Laplace-Beltrami operator $\Delta_g$ of the underlying Riemannian manifold.
The heat (diffusion) equation of this manifold is: $$ \partial_t u= \Delta_g u $$ with fundamental solution (heat kernel): $$ K_t(x,y) = \sum_i \exp(-\lambda_i t)\phi_i(x)\phi_i(y) $$ where $ \lambda_i\phi_i(x)=-\Delta_g\phi_i(x) $, so that the "diffusion distance" is written $$ d_t(x,y) = \sum_k \exp(-2t\lambda_k)[\phi_k(x) - \phi_k(y)]^2 $$ Note we can rescale time to get rid of the $2$ or $2/\lambda_k$ as well.
Discretizing the heat kernel gives a matrix: $$ K(t) = \Phi \exp(-\Lambda t) \Phi^T $$ This operator has eigenvalues $\xi_j^t=\exp(-\lambda_jt)$.
Back to the discrete diffusion maps. Here they define: $$ \Psi_t(x) = (\xi_1^t \psi_1(x),\ldots,\xi_n^t \psi_n(x) )$$ where $\xi_i$ are the eigenvalues of the Markov transition matrix $P$, which converges to the heat/diffusion operator in the limit. (i.e. $P$ approximates the heat kernel). In the limit, $p_t(x,y)=K_t(x,y)$.
Coifman shows (written sloppily without measures here by me): $$ d_t(x,y)^2 = \int_M [p_t(x,u) - p_t(y,u)]^2 / \pi(u) du = || \Psi_t(x) - \Psi_t(y) ||^2 $$ where $\pi$ is the stationary distribution.
The heat operator $P$ describes the transition density of a random walk on the graph. In the limit, this converges to Brownian motion on $M$, described by an Ito diffusion with infinitesimal generator $\Delta_g$ or the Langevin equation (e.g. here, here, and here). (In other words, if the graph is constructed from an underlying manifold, then this approach faithfully preserves the geometry of that manifold, as best it can given the discretization.)
What the equations above show is that (1) the diffusion distance is basically the normalized total distance that all possible paths between two points take, weighted by likelihood and (2) this interpretation is "precise" in the sense that the random graph walk converges to Brownian motion on the manifold (i.e. this interpretation is as good as it can be in the discretized case).
For global geometry, it's clear that this interpretation makes sense for arbitrarily far points. In fact, part of the motivation for it is its robustness to topological changes over larger scales (which geodesic distances do not have), yet being quite similar to geodesic distances over short distances.
Another sense in which the global geometry is preserved is that the transformation using the heat eigenfunctions depends only on the Laplace-Beltrami operator, rendering it invariant to isometric transformations. Note that the embedding of every point relies on eigenfunctions of $\Delta_g$, which are fundamentally non-local entities.
There are plenty of other approaches: biharmonic distances and commute-time distances, for example (see refs). Laplacian eigenmaps are fairly similar as well. And there is a nice recent work on Laplace-Beltrami estimation here.
References
Nadler et al, Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker-Planck Operators, 2005
Coifman and Lafon, Diffusion maps, 2006
Lipman et al, Biharmonic Distance, 2010
Zeng et al, Discrete Heat Kernel Determines Discrete Riemannian Metric, 2010