Graph Embedding and Extensions: A General Framework for Dimensionality Reduction

Shuicheng Yan, Member, IEEE, Dong Xu, Benyu Zhang, Hong-Jiang Zhang, Fellow, IEEE, Qiang Yang, Senior Member, IEEE, and Stephen Lin

This paper proposes a general formulation known as graph embedding to unify them within a common framework.

Introduction & Motivation

• Techniques for dimensionality reduction in supervised or unsupervised learning tasks have attracted much attention in computer vision and pattern recognition.
• PCA, LDA, LPP, ISOMAP, LLE, Laplacian Eigenmap, and the recently proposed tensor based algorithms, can all be reformulated within this common framework.

Contribution

1. This paper propses a general framework called graph embedding, along with its linearization, kernelization, and tensorization, that offers a unified view for understanding and explaining many of the popular dimensionality reduction algorithms
2. Show that the graph embedding framework can be used as a general platform for developing new dimensionality reduction algorithms.

Method

Graph Embedding

1. Linearization

Assuming that the low-dimensional vector representations of the vertices can be obtained from a linear projection the objective function becomes

2. Kernelization

A technique to extend methods for linear projections to nonlinear cases is to directly take advantage of the kernel trick. The intuition of the kernel trick is to map the data from the original input space to another higher dimensional Hilbert space and then perform the linear algorithm in this new feature space.

3. Tensorization

A natural further extension of the above linearization and kernelization of graph embedding is to conduct dimensionality reduction with vertices encoded as general tensors of an arbitrary order.

General Framework for Dimensionality Reduction

Marginal Fisher Analysis

Design an intrinsic graph that characterizes the intraclass compactness and another penalty graph which characterizes the interclass separability.

conclusion & limitations

• This paper aims to provide insights into the relationship among the state-of-the-art dimensionality reduction algorithms, as well as to facilitate the design of new algorithms.
• There are also certain limitations in the graph embedding framework. For example, this framework only considers the L2 distance as a similarity measure, which means that it can only take into account the second-order statistics of the data set