Diffusion map

Connectivity

Diffusion maps exploit the relationship between heat diffusion and random walk Markov chain. The basic observation is that if we take a random walk on the data, walking to a nearby data-point is more likely than walking to another that is far away. Let ${\displaystyle (X,{\mathcal {A}},\mu )}$ be a measure space, where ${\displaystyle X}$ is the data set and ${\displaystyle \mu }$ represents the distribution of the points on ${\displaystyle X}$.

Based on this, the connectivity ${\displaystyle k}$ between two data points, ${\displaystyle x}$ and ${\displaystyle y}$, can be defined as the probability of walking from ${\displaystyle x}$ to ${\displaystyle y}$ in one step of the random walk. Usually, this probability is specified in terms of a kernel function of the two points: ${\displaystyle k:X\times X\rightarrow \mathbb {R} }$. For example, the popular Gaussian kernel:

${\displaystyle k(x,y)=\exp \left(-{\frac {||x-y||^{2}}{\epsilon }}\right)}$

More generally, the kernel function has the following properties

${\displaystyle k(x,y)=k(y,x)}$

(${\displaystyle k}$ is symmetric)

${\displaystyle k(x,y)\geq 0\,\,\forall x,y}$

(${\displaystyle k}$ is positivity preserving).

The kernel constitutes the prior definition of the local geometry of the data-set. Since a given kernel will capture a specific feature of the data set, its choice should be guided by the application that one has in mind. This is a major difference with methods such as principal component analysis, where correlations between all data points are taken into account at once.

Given ${\displaystyle (X,k)}$, we can then construct a reversible discrete-time Markov chain on ${\displaystyle X}$ (a process known as the normalized graph Laplacian construction):

${\displaystyle d(x)=\int _{X}k(x,y)d\mu (y)}$

and define:

${\displaystyle p(x,y)={\frac {k(x,y)}{d(x)}}}$

Although the new normalized kernel does not inherit the symmetric property, it does inherit the positivity-preserving property and gains a conservation property:

${\displaystyle \int _{X}p(x,y)d\mu (y)=1}$

Diffusion process

From ${\displaystyle p(x,y)}$ we can construct a transition matrix of a Markov chain (${\displaystyle M}$) on ${\displaystyle X}$. In other words, ${\displaystyle p(x,y)}$ represents the one-step transition probability from ${\displaystyle x}$ to ${\displaystyle y}$, and ${\displaystyle M^{t}}$ gives the t-step transition matrix.

We define the diffusion matrix ${\displaystyle L}$ (it is also a version of graph Laplacian matrix)

${\displaystyle L_{i,j}=k(x_{i},x_{j})\,}$

We then define the new kernel

${\displaystyle L_{i,j}^{(\alpha )}=k^{(\alpha )}(x_{i},x_{j})={\frac {L_{i,j}}{(d(x_{i})d(x_{j}))^{\alpha }}}\,}$

or equivalently,

${\displaystyle L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }\,}$

where D is a diagonal matrix and ${\displaystyle D_{i,i}=\sum _{j}L_{i,j}.}$

We apply the graph Laplacian normalization to this new kernel:

${\displaystyle M=({D}^{(\alpha )})^{-1}L^{(\alpha )},\,}$

where ${\displaystyle D^{(\alpha )}}$ is a diagonal matrix and ${\displaystyle {D}_{i,i}^{(\alpha )}=\sum _{j}L_{i,j}^{(\alpha )}.}$

${\displaystyle p(x_{j},t|x_{i})=M_{i,j}^{t}\,}$

One of the main ideas of the diffusion framework is that running the chain forward in time (taking larger and larger powers of ${\displaystyle M}$) reveals the geometric structure of ${\displaystyle X}$ at larger and larger scales (the diffusion process). Specifically, the notion of a cluster in the data set is quantified as a region in which the probability of escaping this region is low (within a certain time t). Therefore, t not only serves as a time parameter, but it also has the dual role of scale parameter.

The eigendecomposition of the matrix ${\displaystyle M^{t}}$ yields

${\displaystyle M_{i,j}^{t}=\sum _{l}\lambda _{l}^{t}\psi _{l}(x_{i})\phi _{l}(x_{j})\,}$

where ${\displaystyle \{\lambda _{l}\}}$ is the sequence of eigenvalues of ${\displaystyle M}$ and ${\displaystyle \{\psi _{l}\}}$ and ${\displaystyle \{\phi _{l}\}}$ are the biorthogonal left and right eigenvectors respectively. Due to the spectrum decay of the eigenvalues, only a few terms are necessary to achieve a given relative accuracy in this sum.

Diffusion distance

The diffusion distance at time ${\displaystyle t}$ between two points can be measured as the similarity of two points in the observation space with the connectivity between them. It is given by

${\displaystyle D_{t}(x_{i},x_{j})^{2}=\sum _{y}{\frac {(p(y,t|x_{i})-p(y,t|x_{j}))^{2}}{\phi _{0}(y)}}}$

where ${\displaystyle \phi _{0}(y)}$ is the stationary distribution of the Markov chain, given by the first left eigenvector of ${\displaystyle M}$. Explicitly:

${\displaystyle \phi _{0}(y)={\frac {d(y)}{\sum _{z\in X}d(z)}}}$

Intuitively, ${\displaystyle D_{t}(x_{i},x_{j})}$ is small if there is a large number of short paths connecting ${\displaystyle x_{i}}$ and ${\displaystyle x_{j}}$. There are several interesting features associated with the diffusion distance, based on our previous discussion that ${\displaystyle t}$ also serves as a scale parameter:

1. Points are closer at a given scale (as specified by ${\displaystyle D_{t}(x_{i},x_{j})}$) if they are highly connected in the graph, therefore emphasizing the concept of a cluster.
2. This distance is robust to noise, since the distance between two points depends on all possible paths of length ${\displaystyle t}$ between the points.
3. From a machine learning point of view, the distance takes into account all evidences linking ${\displaystyle x_{i}}$ to ${\displaystyle x_{j}}$, allowing us to conclude that this distance is appropriate for the design of inference algorithms based on the majority of preponderance.^[3]

Diffusion process and low-dimensional embedding

The diffusion distance can be calculated using the eigenvectors by

${\displaystyle D_{t}(x_{i},x_{j})^{2}=\sum _{l}\lambda _{l}^{2t}(\psi _{l}(x_{i})-\psi _{l}(x_{j}))^{2}\,}$

So the eigenvectors can be used as a new set of coordinates for the data. The diffusion map is defined as:

${\displaystyle \Psi _{t}(x)=(\lambda _{1}^{t}\psi _{1}(x),\lambda _{2}^{t}\psi _{2}(x),\ldots ,\lambda _{k}^{t}\psi _{k}(x))}$

Because of the spectrum decay, it is sufficient to use only the first k eigenvectors and eigenvalues. Thus we get the diffusion map from the original data to a k-dimensional space which is embedded in the original space.

In ^[6] it is proved that

${\displaystyle D_{t}(x_{i},x_{j})^{2}\approx ||\Psi _{t}(x_{i})-\Psi _{t}(x_{j})||^{2}\,}$

so the Euclidean distance in the diffusion coordinates approximates the diffusion distance.