Graph Embedding with Constraints

1 Introduction

In many real world applications like face recognition and text categorization, the data is often of very high dimensionality. Procedures that are analytically or computationally manageable in low-dimensional spaces can become completely impractical in a space of several hundreds or thousands dimensions [Duda et al., 2000]. Thus, various techniques have been developed for reducing the dimensionality of the feature space, in the hope of obtaining a manageable problem. Two of the most popular techniques for this purpose are Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA) [Duda et al., 2000].

PCA is an unsupervised method. It aims to project the data along the direction of maximal variance. LDA is supervised. It searches for the project axes on which the data points of different classes are far from each other while requiring data points of the same class to be close to each other. Both of them are spectral methods, that is, methods based on eigenvalue decomposition of either the covariance matrix for PCA or the scatter matrices for LDA.

Recently, graph embedding has become a topic of significant interest for dimensionality reduction [Brand, 2003; Cai et al., 2007; Li et al., 2008; He et al., 2005b; Sugiyama, 2007]. It usually constructs a graph to encode the geometrical information in the data. For some applications like Web

Hujun Bao

State Key Lab of CAD&CG College of Computer Science Zhejiang University, China bao@cad.zju.edu.cn

search, the graph can be pre-defined by using hyperlinks. Using the notion of graph Laplacian [Chung, 1997], one can find a lower-dimensional representation which respects the graph structure. Many state-of-the-art dimensionality reduction algorithms such as Isomap [Tenenbaum et al., 2000], Laplacian Eigenmap [Belkin and Niyogi, 2001], Locally Linear Embedding [Roweis and Saul, 2000], Neighborhood Preserving Embedding (NPE, [He et al., 2005a]) and Locality Preserving Projections [He et al., 2005b], as well as canonical algorithms like PCA and LDA, can be interpreted in a general graph embedding framework with different choices of the graph structure.

In some situations, there may be label information (or within-class and between-class advice) available. The most natural way to make use of such prior information is to incorporate it into the graph structure by modifying the weight matrix. Specifically, if two points share the same label or there is within-class advice for them, then the edge weight is increased. If two points have different labels or there is between-class advice for them, then the edge weight is decreased. The typical supervised graph embedding algorithms include Local Discriminant Embedding (LDE, [Chen et al., 2005]). Note that, NPE and LPP can also be performed in supervised manner by incorporating the label information into the graph structure. The major disadvantage of these approaches is that there is no theoretical guarantee that data points from the same class are mapped into a lower dimensional space in which they are actually sufficiently close to each other.

In this paper, we propose a novel constrained dimensionality reduction algorithm, called Constrained Graph Embedding (CGE), that considers the label information or withinclass/between-class advice as additional constraints. We constrain the space of the solutions that we explore only to contain embedding results that are consistent with the labels (advice). This way, the data points belonging to the same class are merged together in the embedding space in which better classification or clustering performance can be obtained. A key problem in graph embedding is the out-of-sample extension. We further propose that an explicit mapping function can be learned which is defined everywhere.

The paper is structured as follows: in Section 2, we provide a review of graph based dimensionality reduction. Our Constrained Graph Embedding (CGE) algorithm is introduced in Section 3. In Section 4, we discuss how to perform out-ofsample extension. The experimental results are presented in Section 5. Finally, we provide some concluding remarks in Section 6.

2 AReview of Graph based Dimensionality Reduction

Suppose we have m data points {xi}mi=1 . In the past decades, many dimensionality reduction algorithms have been proposed to find a lower-dimensional representation of xi. Despite the different motivations of these algorithms, they can be nicely interpreted in a general graph embedding framework [Brand, 2003; He et al., 2005b].

Given a graph G with m vertices, each vertex represents a data point. Let W be a a symmetric m × m matrix with Wij having the weight of the edge joining vertices i and j. The G and W can be defined to characterize certain statistical or geometrical properties of the data set. The purpose of graph embedding is to represent each vertex of the graph as a low dimensional vector that preserves similarities between the vertex pairs, where similarity is measured by the edge weight.

Let y = (y1, · · · , ym)T be the map from the graph to the real line. The optimal y is given by minimizing [Belkin and Niyogi, 2001]:

where D is a diagonal matrix whose entries are column (or row, since W is symmetric) sums of W, Dii = ∑j Wij . The constraint yT Dy = 1 removes an arbitrary scaling factor in the embedding. This objective function incurs a heavy penalty if neighboring vertices i and j are mapped far apart. Therefore, minimizing it is an attempt to ensure that if vertex i and j are connected with high weight then yi and yj are close in the embedding space [Belkin and Niyogi, 2001; Guattery and Miller, 2000]. With some simple algebraic formulations, we have∑

where L = D -W is the graph Laplacian [Chung, 1997]. Finally, the minimization problem reduces to find

The optimal y's can be obtained by solving the minimum eigenvalue problem:

It would be interesting to note that graph embedding has a close connection to differential geometry. Suppose the data points are sampled from an underlying submanifoldMwhich is embedded in the ambient space. Let f : M → R be a smooth one-dimensional map. Belkin and Niyogi showed that the optiaml map preserving locality can be obtained by solving the following optimization problem on the manifold:

By Stokes' theorem, we have:

where L is the Laplace-Beltrami operator, i.e. Lf = -div∇(f). Therefore, the optimal f to the objective function (4) has to be an eigenfunction of L. Belkin and Niyogi have shown that the optimal solution y∗ gives a discrete approximation to the eigenfunction of L [Belkin and Niyogi, 2001].

3 Constrained Graph Embedding

There is no theoretical guarantee for previous graph embedding algorithms that two data points sharing the same label are mapped into a low dimensional space in which they are actually sufficiently close to each other. In this section, we introduce our Constrained Graph Embedding algorithm which makes use of the label information as additional constraints. We begin with a formal definition of the problem of constrained graph embedding.

3.1 The Problem

The generic graph embedding problem is the following. Given a graph G(V,W) where V = {x1, · · · , xm} is the set of nodes and W is the weight matrix, find a Euclidean embedding of the m nodes y1 , · · · , ym in Rd , such that yi "represents" xi. Our method considers the particular situation that there is label information, or within-class/between-class advice, available. Thus, it is necessary to constrain the space of the solutions that we explore only to contain embedding results that are consistent with this prior knowledge.

3.2 The Algorithm

Given m data points {x1, x2, · · · , xm} ⊂ Rn sampled from the underlying submanifold M, one can build a nearest neighbor graph G to model the local geometrical structure of M. For each data point xi, we find its k nearest neighbors and put an edge between xi and its neighbors. There are many choices of the weight matrix W. A simple definition is as follows:

(6)

Let y = (y1, · · · , ym) be a one-dimensional map of xi's. Without loss of generality, suppose there is label information available for the first p data points x1, · · · , xp. The rest m-p data points xp+1, · · · , xm are unlabeled. Suppose the labeled data points are from c classes.

As we have described earlier, the label information can be introduced into graph embedding as additional constraints.

Let ui be a m-dimensional indicator vector for the i-th class. That is, ui,j = 1 if and only if xj is labeled with the i-th class; ui,j = 0 otherwise. Let ei be a m-dimensional vector whose i-th element is 1 and all other elements are 0. We introduce the label constraint matrix U as follows:

As an example, consider that x1, x2, x3 are labeled with the first class, x4, x5 are labeled with the second class, and the rest m - 5 points are unlabeled. Thus, the constraint matrix U can be represented as follows:

where Im-5 is a (m5) × (m5) identity matrix. Using the label constraint matrix U, we can impose the label constraints explicitly by introducing an auxiliary vector z:

With the above constraint, it is clearly to see that if xi and xj share the same label, then yi = yj. Thus, we have:

and

Finally, the minimization problem reduces to finding:

The optimal vector z that minimizes the objective function is given by the minimum eigenvalue solution to the generalized eigenvalue problem:

It is easy to check that L is positive semi-definite and D is positive definite. Since the column vectors of U are linearly independent, for any non-zero z, Uz is not a zero vector. Therefore, U T LU is still positive semi-definite and U T DU is positive definite. This implies that λ ≥ 0. Let 1d be d-dimensional vector of all ones. Note that U is a m × (c + m - p) matrix and U1c+m-p = 1m. It is easy to check that L1m = 0, thus U T LU1c+m-p = 0. This implies that 1c+m-p is an eigenvector associated with the zero eigenvalue. This eigenvector should be removed since it leads to a constant embedding and all the maps collapse to a single point. Once z is solved, the embedding result y can be obtained by Eq. (8). When there is no label information available, U = Im. In this case, our algorithm reduces to the ordinary Laplacian Eigenmap.

4 Out-of-Sample Extension

The approach described so far yields a map which is defined only on the training points. For real applications such as face recognition, we need to have an explicit mapping function which is defined everywhere. In this section, we discuss how to perform out-of-sample extension.

Consider a linear map f (x) = aT x. Let X = (x1, · · · , xm) be a n ×m data matrix. Thus, the optimal a should satisfy:

However, in reality, such a may not exist. A possible way is to find a which can best fit the equation in the least squares sense:

The technique for solving the least square problem is already matured [Golub and Loan, 1996] and there exist many efficient iterative algorithms (e.g., LSQR [Paige and Saunders, 1982]) that can handle very large scale least square problems.

In the situation that the number of data points is smaller than the number of features, the minimization problem (11) is ill posed. There can be infinitely many solutions to the linear equations system X T a = y (the system is under-determined). The most popular way to solve this problem is to impose a Tikhonov regularizer:

The regularized least square is also called ridge regression [Hastie et al., 2001]. The γ ≥ 0 is a parameter to control the amounts of shrinkage [Hastie et al., 2001]. The regularized least squares in (12) can be rewritten in the matrix form as follows:

Requiring the derivative of the right hand side with respect to a vanish, we get:

5 Experimental Results

In this section, we investigate the use of CGE on face recognition. We compare our proposed algorithm with Eigenface (PCA, [Turk and Pentland, 1991]), Fisherface (LDA, [Belhumeur et al., 1997]), Laplacianface (LPP, [He et al., 2005b]), and Neighborhood Preserving Embedding (NPE, [He et al., 2005a]). We begin with a brief discussion about data preparation.

5.1 Data Preparation

Two face database were tested. The first one is the AT&T database 1 , and the second one is the CMU PIE database [Sim et al., 2003]. In all the experiments, preprocessing to locate the faces were applied. Original images were normalized (in scale and orientation) such that the two eyes were aligned at the same position. Then, the facial areas were cropped into the final image for matching. The size of each cropped image in all the experiments is 32 × 32 pixels, with 256 gray levels per pixel. Thus, each image can be represented by a 1024dimensional vector in image space. No further preprocessing is done. The nearest neighbor classifier is applied for its simplicity. In our algorithm, the parameter k (number of nearest neighbors) is empirically set to 3, and γ is set to 0.1.

1 http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html

5.2 Face Recognition on AT&T Database

The AT&T face database consists of a total of 400 face images, of a total of 40 subjects (10 samples per subject). The images were captured at different times and have different variations including expressions (open or closed eyes, smiling or non-smiling) and facial details (glasses or no glasses). The images were taken with a tolerance for some tilting and rotation of the face up to 20 degrees. Fig. 1 shows some of the faces with varying expressions and facial details in the AT&T database.

For each subject, l(= 2, 4, 6, 8) images are randomly selected as labeled set and the rest are considered as unlabeled set for testing. By applying CGE, LPP, PCA, LDA, and NPE, we can learn a face subspace in which the recognition is then performed. For each given l, we average the results over 20 random splits.

Fig. 2 shows the plots of error rate versus dimensionality reduction for different algorithms. For the baseline method, the recognition is simply performed in the original 1024dimensional image space without any dimensionality reduction. Note that, the upper bound of the dimensionality of Fisherface is c - 1 where c is the number of subjects [Duda et al., 2000]. As can be seen, the performance of these algorithms varies with the number of dimensions. We show the best results obtained by them in Table 1.

Our algorithm outperforms all other five methods. PCA performs the worst in all cases. It does not obtain any improvement over the baseline method. LPP and NPE significantly outperform LDA when there are only 2 labeled samples per subject. As the number of labeled samples increases, the performance difference between LDA, NPE, and LPP gets smaller.

5.3 Face Recognition on CMU PIE Database

The CMU PIE face database [Sim et al., 2003] contains 68 subjects with 41,368 face images as a whole. The face images were captured by 13 synchronized cameras and 21 flashes, under varying pose, illumination and expression. In this experiment, we choose the frontal pose (C27) with varying lighting and illumination which leaves us 49 images per subject. Fig. 3 shows the sample cropped face images from the chosen database. For each subject, l = (10, 20, 30) images are randomly selected as labeled samples and the rest are considered as unlabeled samples for testing.

The experimental design is the same as that in the last subsection. For each given l, we average the results over 20 random splits. Fig. 4 shows the plots of error rate versus dimensionality reduction for the PCA, LDA, NPE, LPP, CGE, and baseline methods. The best results obtained in the optimal subspace for each method are shown in Table 2.

As can be seen, our CGE algorithm consistently outperforms the other five algorithms in all the cases. The error rates obtained by LDA, NPE, and LPP are very close to each other.

5.4 Discussion

Several experiments on two standard face database have been systematically performed. We would like to highlight several

points:

1. It is clear that the use of dimensionality reduction is beneficial in face recognition. There is a significant increase in performance from using LDA, NPE, LPP, and CGE. However, PCA fails to gain improvement over the baseline. This is because that PCA does not encode the discriminative information.
2. Our CGE algorithmsignificantlyoutperforms the canonical subspace learning algorithms (e.g. PCA and LDA) and the state-of-the-art subspace learning algorithms (e.g. NPE and LPP). The reason lies in the fact that CGE constrains the space of the solutions that we explore only to contain embedding results that are consistent with the labels. This way, discriminative information can be encoded in the learned subspace more accurately.
3. The NPE and LPP algorithms are only slightly better than LDA. All of these three algorithms aim to discover the intrinsic manifold structure. They encode the label information in the graph model by assigning higher weights between data points sharing the same label. However, it remains unclear how to select the optimal

weight in a principled manner.

6 Conclusions

This paper introduces a novel dimensionality reduction algorithm called Constrained Graph Embedding to enable more effective discriminant analysis. CGE shares some similar properties to LPP, such as a locality preserving character. However, unlike previous manifold learning algorithms which simply incorporate prior knowledge into the graph structure, our proposed algorithmmakes full use of the prior knowledge to constrain the solution space. Thus, the obtained embedding results are consistent with the prior knowledge such that data points sharing the same label are merged together and simultaneously respect the geometrical structure. The experimental results on two standard databases have shown that our algorithm can significantly improve the face recognition accuracy.

The presented algorithm is linear. However, it can be easily extended to nonlinear embedding by using kernel tricks [Sch¨olkopf and Smola, 2002]. Moreover, in this work we use a nearest neighbor graph. It would be interesting to explore other ways to construct the graph for better describing the geometrical and discriminating structure in the data.

Acknowledgements

This work is supported by Program for Changjiang Scholars and Innovative Research Team in University (IRT0652,PCSIRT), National Science Foundation of China under Grant 60875044, and National Key Basic Research Foundation of China under Grant 2009CB320801.