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

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.

To appear as a part of an upcoming textbook on dimensionality reduction and manifold learning. v2: applied readers' feedback

References in corpus (8)

• Consistency of spectral clustering
• Eigenvalue and Generalized Eigenvalue Problems: Tutorial
• Feature Selection and Feature Extraction in Pattern Analysis: A Literature Review
• 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

Cited by in corpus (2)

• Unified Framework for Spectral Dimensionality Reduction, Maximum Variance Unfolding, and Kernel Learning By Semidefinite Programming: Tutorial and Survey
• Sufficient Dimension Reduction for High-Dimensional Regression and Low-Dimensional Embedding: Tutorial and Survey