Laplacian-Based Dimensionality Reduction Including Spectral Clustering, Laplacian Eigenmap, Locality Preserving Projection, Graph Embedding, and Diffusion Map: Tutorial and Survey
arXiv:2106.02154
Abstract
This is a tutorial and survey paper for nonlinear dimensionality and feature extraction methods which are based on the Laplacian of graph of data. We first introduce adjacency matrix, definition of Laplacian matrix, and the interpretation of Laplacian. Then, we cover the cuts of graph and spectral clustering which applies clustering in a subspace of data. Different optimization variants of Laplacian eigenmap and its out-of-sample extension are explained. Thereafter, we introduce the locality preserving projection and its kernel variant as linear special cases of Laplacian eigenmap. Versions of graph embedding are then explained which are generalized versions of Laplacian eigenmap and locality preserving projection. Finally, diffusion map is introduced which is a method based on Laplacian of data and random walks on the data graph.
arXiv commentTo appear as a part of an upcoming textbook on dimensionality reduction and manifold learning. v2: applied readers' feedback
References in corpus (12)
- Graph Embedding Techniques, Applications, and Performance: A Survey
- Consistency of spectral clustering
- dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning
- Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker-Planck operators
- DynGEM: Deep Embedding Method for Dynamic Graphs
- Feature Selection and Feature Extraction in Pattern Analysis: A Literature Review
- Eigenvalue and Generalized Eigenvalue Problems: Tutorial
- Locally Linear Embedding and its Variants: Tutorial and Survey
- Multidimensional Scaling, Sammon Mapping, and Isomap: Tutorial and Survey
- Unsupervised and Supervised Principal Component Analysis: Tutorial
- Fisher and Kernel Fisher Discriminant Analysis: Tutorial
- Roweis Discriminant Analysis: A Generalized Subspace Learning Method