Diffusion map

Diffusion maps is a dimensionality reduction or feature extraction algorithm introduced by Coifman and Lafon[1][2][3][4] which computes a family of embeddings of a data set into Euclidean space (often low-dimensional) whose coordinates can be computed from the eigenvectors and eigenvalues of a diffusion operator on the data. The Euclidean distance between points in the embedded space is equal to the "diffusion distance" between probability distributions centered at those points. Different from linear dimensionality reduction methods such as principal component analysis (PCA), diffusion maps is part of the family of nonlinear dimensionality reduction methods which focus on discovering the underlying manifold that the data has been sampled from. By integrating local similarities at different scales, diffusion maps give a global description of the data-set. Compared with other methods, the diffusion map algorithm is robust to noise perturbation and computationally inexpensive.

Given non-uniformly sampled data points on a toroidal helix (top), the first two Diffusion Map coordinates with Laplace–Beltrami normalization are plotted (bottom). The Diffusion Map unravels the toroidal helix recovering the underlying intrinsic circular geometry of the data.

Definition of diffusion maps

Following [3] and,[5] diffusion maps can be defined in four steps.

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 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 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 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 right and left 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.

Parameter ${\displaystyle \alpha }$ and the Diffusion Operator

The reason to introduce the normalization step involving ${\displaystyle \alpha }$ is to tune the influence of the data point density on the infinitesimal transition of the diffusion. In some applications, the sampling of the data is generally not related to the geometry of the manifold we are interested in describing. In this case, we can set ${\displaystyle \alpha =1}$ and the diffusion operator approximates the Laplace–Beltrami operator. We then recover the Riemannian geometry of the data set regardless of the distribution of the points. To describe the long-term behavior of the point distribution of a system of stochastic differential equations, we can use ${\displaystyle \alpha =0.5}$ and the resulting Markov chain approximates the Fokker–Planck diffusion. With ${\displaystyle \alpha =0}$, it reduces to the classical graph Laplacian normalization.

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}=||\Psi _{t}(x_{i})-\Psi _{t}(x_{j})||^{2}\,}$

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

Algorithm

The basic algorithm framework of diffusion map is as:

Step 1. Given the similarity matrix L.

Step 2. Normalize the matrix according to parameter ${\displaystyle \alpha }$: ${\displaystyle L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }}$.

Step 3. Form the normalized matrix ${\displaystyle M=({D}^{(\alpha )})^{-1}L^{(\alpha )}}$.

Step 4. Compute the k largest eigenvalues of ${\displaystyle M^{t}}$ and the corresponding eigenvectors.

Step 5. Use diffusion map to get the embedding ${\displaystyle \Psi _{t}}$.

Application

In the paper,[6] Nadler et. al. showed how to design a kernel that reproduces the diffusion induced by a Fokker–Planck equation. Also, they explained that, when the data approximate a manifold, one can recover the geometry of this manifold by computing an approximation of the Laplace–Beltrami operator. This computation is completely insensitive to the distribution of the points and therefore provides a separation of the statistics and the geometry of the data. Since diffusion maps gives a global description of the data-set, it can measure the distances between pair of sample points in the manifold in which the data is embedded. Applications based on diffusion maps include face recognition,[7] spectral clustering, low dimensional representation of images, image segmentation,[8] 3D model segmentation,[9] speaker verification[10] and identification,[11] sampling on manifolds, anomaly detection,[12][13] image inpainting,[14] revealing brain resting state networks organization [15] and so on.

See also

• Nonlinear dimensionality reduction
• Spectral clustering

References

1. Coifman, R.R.; Lafon, S; Lee, A B; Maggioni, M; Nadler, B; Warner, F; Zucker, S W (2005). "Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps". PNAS. 102 (21): 7426–7431. Bibcode:2005PNAS..102.7426C. doi:10.1073/pnas.0500334102. PMC 1140422. PMID 15899970.
2. Coifman, R.R.; Lafon, S; Lee, A B; Maggioni, M; Nadler, B; Warner, F; Zucker, S W (2005). "Geometric diffusions as a tool for harmonic analysis and structure definition of data: Multiscale methods". PNAS. 102 (21): 7432–7437. Bibcode:2005PNAS..102.7432C. doi:10.1073/pnas.0500896102. PMC 1140426. PMID 15899969.
3. Coifman, R.R.; S. Lafon. (2006). "Diffusion maps". Applied and Computational Harmonic Analysis. 21: 5–30. doi:10.1016/j.acha.2006.04.006.
4. Lafon, S.S. (2004). Diffusion Maps and Geometric Harmonics (PDF) (PhD). Yale University.
5. De la Porte, J.; Herbst, B M; Hereman, W; Van der Walt, S J (2008). "An Introduction to Diffusion Maps". Proceedings of the Nineteenth Annual Symposium of the Pattern Recognition Association of South Africa (PRASA). CiteSeerX 10.1.1.309.674.
6. Nadler, Boaz; Stéphane Lafon; Ronald R. Coifman; Ioannis G. Kevrekidis (2005). "Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker–Planck Operators" (PDF). Advances in Neural Information Processing Systems. 18. arXiv:math/0506090. Bibcode:2005math......6090N.
7. Barkan, Oren; Weill, Jonathan; Wolf, Lior; Aronowitz, Hagai. "Fast high dimensional vector multiplication face recognition" (PDF). Proceedings of the IEEE International Conference on Computer Vision 2013: 1960–1967.
8. Zeev, Farbman; Fattal Raanan; Lischinski Dani (2010). "Diffusion maps for edge-aware image editing". ACM Trans. Graph. 29 (6): 145:1–145:10. doi:10.1145/1882261.1866171.
9. Oana, Sidi; van Kaick, Oliver; Kleiman, Yanir; Zhang, Hao; Cohen-Or, Daniel (2011). Unsupervised Co-Segmentation of a Set of Shapes via Descriptor-Space Spectral Clustering (PDF). ACM Transactions on Graphics.
10. Barkan, Oren; Aronowitz, Hagai (2013). "Diffusion maps for PLDA-based speaker verification" (PDF). Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP): 7639–7643.
11. Michalevsky, Yan; Talmon, Ronen; Cohen, Israel (2011). "Speaker Identification Using Diffusion Maps" (PDF). Cite journal requires |journal= (help)
12. Mishne, Gal; Cohen, Israel (2013). "Multiscale Anomaly Detection Using Diffusion Maps". IEEE Selected Topics in Signal Processing. 7 (1): 111–123. Bibcode:2013ISTSP...7..111M. doi:10.1109/jstsp.2012.2232279. S2CID 1954466.
13. Shabat, Gil; Segev, David; Averbuch, Amir (2018-01-07). "Uncovering Unknown Unknowns in Financial Services Big Data by Unsupervised Methodologies: Present and Future trends". KDD 2017 Workshop on Anomaly Detection in Finance. 71: 8–19.
14. Gepshtein, Shai; Keller, Yosi (2013). "Image Completion by Diffusion Maps and Spectral Relaxation". IEEE Transactions on Image Processing. 22 (8): 2983–2994. Bibcode:2013ITIP...22.2983G. doi:10.1109/tip.2013.2237916. PMID 23322762. S2CID 14375333.
15. https://www.pnas.org/content/113/44/12574.short