Laplacian-Based Dimensionality Reduction Including Spectral Clustering, Laplacian Eigenmap, Locality Preserving Projection, Graph Embedding, and Diffusion Map: Tutorial and Survey

This is a tutorial and survey paper for nonlinear dimensionality and feature\nextraction methods which are based on the Laplacian of graph of data. We first\nintroduce adjacency matrix, definition of Laplacian matrix, and the\ninterpretation of Laplacian. Then, we cover the cuts of graph and spectral\nclustering which applies clustering in a subspace of data. Different\noptimization variants of Laplacian eigenmap and its out-of-sample extension are\nexplained. Thereafter, we introduce the locality preserving projection and its\nkernel variant as linear special cases of Laplacian eigenmap. Versions of graph\nembedding are then explained which are generalized versions of Laplacian\neigenmap and locality preserving projection. Finally, diffusion map is\nintroduced which is a method based on Laplacian of data and random walks on the\ndata graph.\n