# Dimension Reduction Using Samples’ Inner Structure Based Graph for Face Recognition

Authors: Bin Li; Wei Pang; Yuhao Liu; Xiangchun Yu; Anan Du; Yecheng Zhang; Zhezhou Yu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Graph construction plays a vital role in improving the performance of graph-based dimension reduction (DR) algorithms. In this paper, we propose a novel graph construction method, and we name the graph constructed from such method as samples’ inner structure based graph (SISG). Instead of determining thek-nearest neighbors of each sample by calculating the Euclidean distance between vectorized sample pairs, our new method employs the newly defined sample similarities to calculate the neighbors of each sample, and the newly defined sample similarities are based on the samples’ inner structure information. The SISG not only reveals the inner structure information of the original sample matrix, but also avoids predefining the parameter k as used in the k-nearest neighbor method. In order to demonstrate the effectiveness of SISG, we apply it to an unsupervised DR algorithm, locality preserving projection (LPP). Experimental results on several benchmark face databases verify the feasibility and effectiveness of SISG.


---

## Body

## 1. Introduction

Dimensionality reduction (DR) [1–4] has been intensively used as an effective approach to analyze high-dimensional data, especially face images. In particular, graph-based DR receives more and more attention recently in the fields of pattern recognition and machine learning. It is stated that most existing DR methods [5–11] actually fall into the graph embedding framework [12]. In graph embedding algorithms graph construction plays a vital role, because graph is an effective tool to reveal the structure information hidden in the original data. So it is worthwhile to study graph construction [13–17] and develop novel construction approaches to construct more reasonable graphs for graph-based DR methods. Jebara et al. [14] presented the so-called b-matching graph, which is an alternative approach to the traditional k-nearest neighbor graph. The authors in [15, 17] focused on developing a way of combining different graphs so that a better graph will be given a heavier weight. However, we point out that the traditional graph construction method suffers from the following two issues.(1)
Thek-nearest neighbors of each sample are based on the Euclidean distance between every two vectorized samples. However, samples’ inner structure information is not taken into consideration by the traditional graph construction method, and such information can be utilized to construct better graphs for dimension reduction algorithms.(2)
The same neighbor parameterk (or ɛ) [18, 19] has to be predefined for all samples before constructing graphs. This may cause the difficulty of parameter selection and it is not reasonable to set the same parameter value for all samples.To mitigate the shortcomings of the traditional graph construction method, in this paper we present a samples’ inner structure based graph construction method, and we name the graph constructed from such method as samples’ inner structure based graph (SISG). In this new method we first use the column similarity to determine the nearest neighbors of each column for sample matrices. Then we use the sample similarity measured by the number of nearest neighbor columns between sample pairs to determine the nearest neighbors of each sample. This strategy not only avoids the stiff criterion (predefining the same parameterk for all samples) as used in the traditional graphs but also utilizes every sample’s inner structure information. We summarize the favorable and attractive characteristics of SISG as follows.(1)
SISG preserves samples’ intrinsic features by using the inner structure information of sample matrices to construct graph.(2)
SISG uses the newly defined sample similarities to calculate the neighbors of each sample. This strategy avoids predefining the neighbor parameterk (or ɛ) in traditional graph construction methods.(3)
The edge weights of SISG are determined by the sample similarities between sample pairs. If the sample similarity between two samples is high, the edge weights between these two samples will be big. This means the greater the sample similarity between two samples is, the more important the corresponding edge is in the graph.(4)
Both the weighted adjacency matrix and the adjacency matrix of SISG are generally asymmetric. This characteristic may be more reasonable for capturing the relationship among samples.(5)
The construction method of SISG is very general. It can be applied to many graph-based DR algorithms.The rest of this paper is organized as follows. Section2 briefly reviews traditional graph construction and locality preserving projection (LPP). Section 3 firstly presents SISG’s construction method and then applies SISG to LPP. In Section 4 we perform a series of the experiments to evaluate the feasibility and effectiveness of SISG. This is followed by the conclusions made in Section 5.


## 2. Related Work

### 2.1. Traditional Graph Construction

LetA={A1,…,AN} be a set of N sample matrices, which are taken from an (n×m) dimensional image space. Then, the original samples were transformed into their vectorial forms, and we denote these vectors by X={x1,…,xN}, xi∈RD. The weighted graph can be denoted by G={V,E,W}, where V corresponds to the vectors in the set X, E is the set of edges, each of which is between one sample pair, and the matrix W contains weight values of the edges among sample pairs. The construction process of the graph G normally consists of two steps.The first step is the construction of edges, which includes the two categories ofɛ-neighborhood and k-nearest neighbor [12, 19].ɛ-Neighborhood: xi and xj are connected if ∥xi-xj∥<ɛ, where ∥·∥ is the Euclidean distance in RD and ɛ is a local threshold parameter.k-Nearest neighbor: xi and xj are connected if xi is one of the k-nearest neighbors of xj or xj is one of the k-nearest neighbors of Xi.The second step is the calculation of the weight value for each edge. The weight value ofWij can be calculated by the following two ways [12]:(1)
heat kernel(1)Wij={exp⁡(-∥xi-xj∥2t),ifxiandxjareneighbors,0,otherwise,wheret is the width parameter in the heat kernel;(2)
simple minded(2)Wij={1,ifxiandxjareneighbors,0,otherwise.


### 2.2. Locality Preserving Projection

The aim of locality preserving projection (LPP) [20] is to map the sample set in high-dimensional space into the low-dimensional one, in which the local manifold structures of high-dimensional space are preserved. This means if the original points xi and xj in the high-dimensional space are neighbors, the corresponding points yi and yj in the projected low-dimensional space are also neighbors. Suppose the projection from the high-dimensional space to the low-dimensional one is yi=αTxi, where α is the projection vector; the objective function of LPP is given in [20]
(3)∑ij‍∥yi-yj∥2wij=∑ij‍∥αTxi-αTxj∥2=2αTXLXTα.In (3) the weighted adjacency matrix W can be computed by either (1) or (2). The matrix D is a diagonal one Dii=∑j‍wij, and L=D-W. The constraint αTXDXTα=1 was added so that the arbitrary scaling in the embedding can be removed. The minimization problem in (3) thus becomes
(4)α*=argmin⁡αTXDXTα=1αTXLXTα.LPP can be solved by the generalized eigenvector approach [20]:
(5)XLXTα=λXDXTα.


## 2.1. Traditional Graph Construction

LetA={A1,…,AN} be a set of N sample matrices, which are taken from an (n×m) dimensional image space. Then, the original samples were transformed into their vectorial forms, and we denote these vectors by X={x1,…,xN}, xi∈RD. The weighted graph can be denoted by G={V,E,W}, where V corresponds to the vectors in the set X, E is the set of edges, each of which is between one sample pair, and the matrix W contains weight values of the edges among sample pairs. The construction process of the graph G normally consists of two steps.The first step is the construction of edges, which includes the two categories ofɛ-neighborhood and k-nearest neighbor [12, 19].ɛ-Neighborhood: xi and xj are connected if ∥xi-xj∥<ɛ, where ∥·∥ is the Euclidean distance in RD and ɛ is a local threshold parameter.k-Nearest neighbor: xi and xj are connected if xi is one of the k-nearest neighbors of xj or xj is one of the k-nearest neighbors of Xi.The second step is the calculation of the weight value for each edge. The weight value ofWij can be calculated by the following two ways [12]:(1)
heat kernel(1)Wij={exp⁡(-∥xi-xj∥2t),ifxiandxjareneighbors,0,otherwise,wheret is the width parameter in the heat kernel;(2)
simple minded(2)Wij={1,ifxiandxjareneighbors,0,otherwise.


## 2.2. Locality Preserving Projection

The aim of locality preserving projection (LPP) [20] is to map the sample set in high-dimensional space into the low-dimensional one, in which the local manifold structures of high-dimensional space are preserved. This means if the original points xi and xj in the high-dimensional space are neighbors, the corresponding points yi and yj in the projected low-dimensional space are also neighbors. Suppose the projection from the high-dimensional space to the low-dimensional one is yi=αTxi, where α is the projection vector; the objective function of LPP is given in [20]
(3)∑ij‍∥yi-yj∥2wij=∑ij‍∥αTxi-αTxj∥2=2αTXLXTα.In (3) the weighted adjacency matrix W can be computed by either (1) or (2). The matrix D is a diagonal one Dii=∑j‍wij, and L=D-W. The constraint αTXDXTα=1 was added so that the arbitrary scaling in the embedding can be removed. The minimization problem in (3) thus becomes
(4)α*=argmin⁡αTXDXTα=1αTXLXTα.LPP can be solved by the generalized eigenvector approach [20]:
(5)XLXTα=λXDXTα.


## 3. Samples’ Inner Structure Based Graph (SISG)

As discussed in Section1, the traditional graph construction method suffers from two main issues: the stiff criterion problem and the loss of inner structure information of samples. To overcome these limitations to some extent, in this section we first present a new approach to graph construction, and graphs constructed by this new approach are called samples’ inner structure based graph (SISG); then we incorporate SISG into LPP, which forms a new algorithm called SISG-LPP.


### 3.1. The Construction of SISG

Given a set ofN sample matrices A={A1,…,AN}, which is taken from an (n×m)dimensional image space, we let X={x1,…,xN}, xi∈RD, denote the vector pattern of image set A, and let l (l=1,2,…,m, and m is the maximum column number of the sample matrix) be the column number of each sample (Algorithm 1). Ail denotes the lth column of sample matrix Ai. SISG can be denoted by SISG={V,E,S,WSISG}, where V corresponds to the vectors in the set X,E is the adjacency matrix of SISG which denotes the edge set between the sample pairs, S is the sample similarity matrix of SISG which denotes sample similarities between sample pairs, and WSISG is the weighted adjacency matrix which denotes the weight values of the edges between sample pairs. There are two steps to build a SISG, as detailed below.Algorithm 1:Construction of SISG.
INPUT: Sample set A={A1,…,Ai,…,AN}, where Ai is a sample matrix.
OUTPUT: The weighted adjacency matrix WSISG of SISG
Algorithm:
fori=1 to N (N is the number of the training samples)
forj=1 to N
forl=1 to m (m is the column number of sample matrix)
ifexp⁡{-C(Ail,Ajl)/t}>(1/n)∑k=1Nexp⁡{-C(Ail,Akl)/t}
Gijl=1;
else
Gijl=0;
end if
end for
end for
forj=1 to N
Sij=∑l=1mGijl;
ifSij>∥Si·∥1/∥Si·∥0
WijSISG=Sij·[-exp⁡(∥xi-xj∥2t)];
(Xi is the vectorization representation of Ai)
else
WijSISG=0;
end if
end for
end forStep 1.
For thelth columns of all the samples, we calculate the nearest neighbors of each column.Definition 1 (column similarity).
Column similarity is calculated by the column similarity function:exp⁡{-C(Ail,Ajl)/t}, where C(Ail,Ajl)=∥Ail-Ajl∥/∑k=1N‍∥Ail-Akl∥ and t is the width parameter in the heat kernel. Let Gl denote the adjacency matrix of all samples’ lth columns:
(6)Gijl={1,ifexp⁡{-C(Ail,Ajl)t}>1n∑k=1N‍exp⁡{-C(Ail,Akl)t},0,otherwise.The meaning of (6) is as follows: for the lth column of the sample matrix i (Ail), if the column similarity between this column and Ajl is greater than the mean of column similarities between Ail and all other samples’ lth column, Ajl will become a neighbor of Ail, and we place an edge between Ail and Ajl; that is, Gijl=1.Figure1 shows the 3 nearest column neighbors of Ail, and the black rectangular boxes in the sample matrices represent the lth column of each sample.Figure 1
The 3 nearest neighbors of SampleAi’s lth column.Step 2.
Determine every sample’s neighbors by the sample similarity between sample pairs, and calculate the weight value for each neighbor pair.
In this step, the original samples are transformed into their forms representation, and we denote these vectors byX={x1,…,xN},xi∈RD.Definition 2 (sample similarity).
Sample similarity is determined by the number of column neighbors between sample pairs.
We letSij denote the number of column neighbors of sample xi for xj. So, Sij=∑l=1m‍Gijl (m is the maximum column number of a sample matrix) means the number of column neighbors of sample matrix Ai for sample matrix Aj. It is noted that Sij is normally not equal to Sji, and this characteristic is simply shown in Section 3.2. Consequently, the sample similarity of sample xi for xj is described by Sij.
When deciding which samples can be the nearest neighbors of samplexi, we only consider those samples whose sample similarity with sample xi is nonzero. This is because if there are no nearest neighbor columns between two sample matrices, these two sample matrices will not be similar at all, and thus they cannot become neighbors. The weighted adjacency matrix WSISG of the SISG is constructed according to the following equation:(7)WijSISG={Sij·[-exp⁡(∥xi-xj∥2t)],ifSij>∥Si·∥1∥Si·∥0,0otherwise,
where Si· is a vector and Si·=[Sij], j=1,…,N-1. Si· denotes the sample similarity of sample xi for all other samples. ∥·∥0 represents the L0-norm, which is the number of nonzero entries in a vector. So ∥Si·∥0 denotes the number of nonzero elements in vector Si·. ∥·∥1 represents the L1-norm, which is a linear combination of the absolute values of all entries in a vector. So ∥Si·∥1 is the sum of all entries in vector Si·.The meaning of (7) is as follows: if the sample similarity between samples xi and xj is greater than the mean of sample similarities between xi and all samples, then xj becomes a neighbor of xi, and we put an edge between them; that is, Eij=1.The weight value of the edge betweenxi and xj is the heat kernel multiplied by the sample similarity between samples xi and xj. By doing this, the greater the sample similarity between samples xi and xj, the more important the corresponding edge in WSISG. The meaning of WijSISG is as follows: the weight value between xi and xj is proportional to their sample similarity and inversely proportional to their Euclidean distance.


### 3.2. Characteristic of SISG

Both the weighted adjacency matrixWSISG and adjacency matrix E are asymmetric in most situations, and the symmetric ones are only special cases. This characteristic is more reasonable for effectively capturing and fitting the relationship among samples.ForAil, the mean of column similarities between this column and all other samples’ lth column is calculated as follows:
(8)Mil=1n∑k=1N‍exp⁡{-C(Ail,Akl)t}.ForAjl, the mean of column similarities between this column and all other samples’ lth column is calculated as follows:
(9)Mjl=1n∑k=1N‍exp⁡{-C(Ajl,Akl)t}.(1)
The following situations may arise when calculating the column similarity.
(1.1)
if(10)exp⁡{-C(Ail,Ajl)t}>Mil,exp⁡{-C(Ajl,Ail)t}>Mjl,Ail and Ajl become column neighbors of each other.(1.2)
if(11)exp⁡{-C(Ail,Ajl)t}≤Mil,exp⁡{-C(Ajl,Ail)t}≤Mjl,Ail is not a column neighbor of Ajl, and vice versa.(1.3)
if(12)exp⁡{-C(Ail,Ajl)t}>Mil,whileexp⁡{-C(Ajl,Ail)t}≤Mjl,Ajl is a column neighbor of Ail while Ail is not a column neighbor of Ajl.(2)
The following situations may arise when calculating the column similarity.
(2.1)
if(13)Sij>∥Si·∥1∥Si·∥0,Sji>∥Sj·∥1∥Sj·∥0,sampleAi and sample Aj become neighbors of each other.(2.2)
if(14)Sij≤∥Si·∥1∥Si·∥0,Sji≤∥Sj·∥1∥Sj·∥0,sampleAi is not a neighbor of sample Aj, and vice versa.(2.3)
if(15)Sij>∥Si·∥1∥Si·∥0,Sji≤∥Sj·∥1∥Sj·∥0,sampleAj is a neighbor of sample Ai while sample Ai is not a neighbor of sample Aj.If all the columns ofAi(Ail,l=1,2…,m) and all the columns of Aj(Ajl,l=1,2…,m) meet (1.1) or (1.2), Sij will equal Sji. Furthermore, if (2.1) or (2.2) can always be met for arbitrary Ai and Aj(i,j=1,…,n), WijSISG=WjiSISG. This is because the edge weights of SISG depend on the sample similarity of each sample. In this case, both the weighted adjacency matrix WSISG and the adjacency matrix E are symmetric.If the condition in (1.3) is met,Sij will not be equal to Sji. Furthermore, if (2.1) or (2.2) can always be met for arbitrary Ai and Aj(i,j=1,…,n), the adjacency matrix E will be symmetric, but WijSISG will not be equal to WjiSISG and the weighted adjacency matrix WSISG will be asymmetric.Apart from the two cases discussed in the above two paragraphs, both the weighted adjacency matrixWSISG and adjacency matrix E are normally asymmetric.We should notice that for all the columns ofAi(Ail,l=1,2…,m) and all the columns of Aj they must meet (1.1) or (1.2) at the same time, but (1.1) can never be met alone. Because Mil is the mean of column similarities, it is impossible that all the column similarities between any two columns Ail and Ajl are both greater than Mil. For similar reasons, (1.2), (2.1), and (2.2) can never be met alone either.From what has been discussed above, we can see that both the weighted adjacency matrixWSISG and adjacency matrix E are generally asymmetric, and symmetric ones are just their special cases, which are very rare situations.


### 3.3. SISG-LPP

The construction method of SISG is very general. So SISG can be used in many graph-based dimensionality reduction algorithms. In this subsection, we use SISG in state-of-the-art unsupervised DR algorithm, locality preserving projection (LPP), to develop a new DR algorithm called SISG-LPP.Similar to LPP, the goal of SISG-LPP is preserving the local manifold structures in high-dimensional space. Given a set ofN samples X={x1,…,xN}, xi∈RD, in high-dimensional space, we try to find a transformation matrix which can map these N points to a set of points y1,…,yN in low-dimensional space. Assuming that the projection is y=αTx, where α is the projection vector, the objective function of SISG-LPP is given in(16)∑ij‍∥yi-yj∥2WSISG=∑ij‍(yi2+yj2-2yiyi)WSISG=∑ij‍yi2WijSISG+∑ij‍yj2WijSISG-∑ij‍yiyjWijSISG-∑ij‍yjyiWijSISG=∑ij‍yi2Dii+∑ij‍yi2Djj′-∑ij‍yiyjWijSISG-∑ij‍yjyiWijSISG=αTX((Dii+Djj′)-(WijSISG+(WijSISG)T))XTα=αTX(D¯-W¯)XTα=αTXL¯XTα.In the above,WSISG is an asymmetric matrix, but W¯=WijSISG+(WijSISG)T is a symmetric matrix. Let Dii and Djj′ denote the diagonal matrices; the entries of Dii are column sums of WSISG, and the entries of Djj′ are column sums of (WijSISG)T. D¯=Dii+Djj′ is the diagonal matrix whose entries are column sums of W¯. So, L¯=D¯-W¯ is the Laplacian matrix. Because D¯ provides a measure on the “importance” of the data points, we impose the following constraint:
(17)αTX(Dii+Djj′)XTα=αTXD¯XTα=1.Thus, the optimization objective of SISG-LPP is(18)α*=argmin⁡αTXD¯XTα=1αTXL¯XTα.The solutions of (18) can be obtained by solving the generalized eigenvalue decomposition problem [21]. That is to say, the projection vectors of (18) are actually the eigenvectors which correspond to the first l smallest eigenvalues of XL¯XTα=λXD¯XTα [22].


## 3.1. The Construction of SISG

Given a set ofN sample matrices A={A1,…,AN}, which is taken from an (n×m)dimensional image space, we let X={x1,…,xN}, xi∈RD, denote the vector pattern of image set A, and let l (l=1,2,…,m, and m is the maximum column number of the sample matrix) be the column number of each sample (Algorithm 1). Ail denotes the lth column of sample matrix Ai. SISG can be denoted by SISG={V,E,S,WSISG}, where V corresponds to the vectors in the set X,E is the adjacency matrix of SISG which denotes the edge set between the sample pairs, S is the sample similarity matrix of SISG which denotes sample similarities between sample pairs, and WSISG is the weighted adjacency matrix which denotes the weight values of the edges between sample pairs. There are two steps to build a SISG, as detailed below.Algorithm 1:Construction of SISG.
INPUT: Sample set A={A1,…,Ai,…,AN}, where Ai is a sample matrix.
OUTPUT: The weighted adjacency matrix WSISG of SISG
Algorithm:
fori=1 to N (N is the number of the training samples)
forj=1 to N
forl=1 to m (m is the column number of sample matrix)
ifexp⁡{-C(Ail,Ajl)/t}>(1/n)∑k=1Nexp⁡{-C(Ail,Akl)/t}
Gijl=1;
else
Gijl=0;
end if
end for
end for
forj=1 to N
Sij=∑l=1mGijl;
ifSij>∥Si·∥1/∥Si·∥0
WijSISG=Sij·[-exp⁡(∥xi-xj∥2t)];
(Xi is the vectorization representation of Ai)
else
WijSISG=0;
end if
end for
end forStep 1.
For thelth columns of all the samples, we calculate the nearest neighbors of each column.Definition 1 (column similarity).
Column similarity is calculated by the column similarity function:exp⁡{-C(Ail,Ajl)/t}, where C(Ail,Ajl)=∥Ail-Ajl∥/∑k=1N‍∥Ail-Akl∥ and t is the width parameter in the heat kernel. Let Gl denote the adjacency matrix of all samples’ lth columns:
(6)Gijl={1,ifexp⁡{-C(Ail,Ajl)t}>1n∑k=1N‍exp⁡{-C(Ail,Akl)t},0,otherwise.The meaning of (6) is as follows: for the lth column of the sample matrix i (Ail), if the column similarity between this column and Ajl is greater than the mean of column similarities between Ail and all other samples’ lth column, Ajl will become a neighbor of Ail, and we place an edge between Ail and Ajl; that is, Gijl=1.Figure1 shows the 3 nearest column neighbors of Ail, and the black rectangular boxes in the sample matrices represent the lth column of each sample.Figure 1
The 3 nearest neighbors of SampleAi’s lth column.Step 2.
Determine every sample’s neighbors by the sample similarity between sample pairs, and calculate the weight value for each neighbor pair.
In this step, the original samples are transformed into their forms representation, and we denote these vectors byX={x1,…,xN},xi∈RD.Definition 2 (sample similarity).
Sample similarity is determined by the number of column neighbors between sample pairs.
We letSij denote the number of column neighbors of sample xi for xj. So, Sij=∑l=1m‍Gijl (m is the maximum column number of a sample matrix) means the number of column neighbors of sample matrix Ai for sample matrix Aj. It is noted that Sij is normally not equal to Sji, and this characteristic is simply shown in Section 3.2. Consequently, the sample similarity of sample xi for xj is described by Sij.
When deciding which samples can be the nearest neighbors of samplexi, we only consider those samples whose sample similarity with sample xi is nonzero. This is because if there are no nearest neighbor columns between two sample matrices, these two sample matrices will not be similar at all, and thus they cannot become neighbors. The weighted adjacency matrix WSISG of the SISG is constructed according to the following equation:(7)WijSISG={Sij·[-exp⁡(∥xi-xj∥2t)],ifSij>∥Si·∥1∥Si·∥0,0otherwise,
where Si· is a vector and Si·=[Sij], j=1,…,N-1. Si· denotes the sample similarity of sample xi for all other samples. ∥·∥0 represents the L0-norm, which is the number of nonzero entries in a vector. So ∥Si·∥0 denotes the number of nonzero elements in vector Si·. ∥·∥1 represents the L1-norm, which is a linear combination of the absolute values of all entries in a vector. So ∥Si·∥1 is the sum of all entries in vector Si·.The meaning of (7) is as follows: if the sample similarity between samples xi and xj is greater than the mean of sample similarities between xi and all samples, then xj becomes a neighbor of xi, and we put an edge between them; that is, Eij=1.The weight value of the edge betweenxi and xj is the heat kernel multiplied by the sample similarity between samples xi and xj. By doing this, the greater the sample similarity between samples xi and xj, the more important the corresponding edge in WSISG. The meaning of WijSISG is as follows: the weight value between xi and xj is proportional to their sample similarity and inversely proportional to their Euclidean distance.


## 3.2. Characteristic of SISG

Both the weighted adjacency matrixWSISG and adjacency matrix E are asymmetric in most situations, and the symmetric ones are only special cases. This characteristic is more reasonable for effectively capturing and fitting the relationship among samples.ForAil, the mean of column similarities between this column and all other samples’ lth column is calculated as follows:
(8)Mil=1n∑k=1N‍exp⁡{-C(Ail,Akl)t}.ForAjl, the mean of column similarities between this column and all other samples’ lth column is calculated as follows:
(9)Mjl=1n∑k=1N‍exp⁡{-C(Ajl,Akl)t}.(1)
The following situations may arise when calculating the column similarity.
(1.1)
if(10)exp⁡{-C(Ail,Ajl)t}>Mil,exp⁡{-C(Ajl,Ail)t}>Mjl,Ail and Ajl become column neighbors of each other.(1.2)
if(11)exp⁡{-C(Ail,Ajl)t}≤Mil,exp⁡{-C(Ajl,Ail)t}≤Mjl,Ail is not a column neighbor of Ajl, and vice versa.(1.3)
if(12)exp⁡{-C(Ail,Ajl)t}>Mil,whileexp⁡{-C(Ajl,Ail)t}≤Mjl,Ajl is a column neighbor of Ail while Ail is not a column neighbor of Ajl.(2)
The following situations may arise when calculating the column similarity.
(2.1)
if(13)Sij>∥Si·∥1∥Si·∥0,Sji>∥Sj·∥1∥Sj·∥0,sampleAi and sample Aj become neighbors of each other.(2.2)
if(14)Sij≤∥Si·∥1∥Si·∥0,Sji≤∥Sj·∥1∥Sj·∥0,sampleAi is not a neighbor of sample Aj, and vice versa.(2.3)
if(15)Sij>∥Si·∥1∥Si·∥0,Sji≤∥Sj·∥1∥Sj·∥0,sampleAj is a neighbor of sample Ai while sample Ai is not a neighbor of sample Aj.If all the columns ofAi(Ail,l=1,2…,m) and all the columns of Aj(Ajl,l=1,2…,m) meet (1.1) or (1.2), Sij will equal Sji. Furthermore, if (2.1) or (2.2) can always be met for arbitrary Ai and Aj(i,j=1,…,n), WijSISG=WjiSISG. This is because the edge weights of SISG depend on the sample similarity of each sample. In this case, both the weighted adjacency matrix WSISG and the adjacency matrix E are symmetric.If the condition in (1.3) is met,Sij will not be equal to Sji. Furthermore, if (2.1) or (2.2) can always be met for arbitrary Ai and Aj(i,j=1,…,n), the adjacency matrix E will be symmetric, but WijSISG will not be equal to WjiSISG and the weighted adjacency matrix WSISG will be asymmetric.Apart from the two cases discussed in the above two paragraphs, both the weighted adjacency matrixWSISG and adjacency matrix E are normally asymmetric.We should notice that for all the columns ofAi(Ail,l=1,2…,m) and all the columns of Aj they must meet (1.1) or (1.2) at the same time, but (1.1) can never be met alone. Because Mil is the mean of column similarities, it is impossible that all the column similarities between any two columns Ail and Ajl are both greater than Mil. For similar reasons, (1.2), (2.1), and (2.2) can never be met alone either.From what has been discussed above, we can see that both the weighted adjacency matrixWSISG and adjacency matrix E are generally asymmetric, and symmetric ones are just their special cases, which are very rare situations.


## 3.3. SISG-LPP

The construction method of SISG is very general. So SISG can be used in many graph-based dimensionality reduction algorithms. In this subsection, we use SISG in state-of-the-art unsupervised DR algorithm, locality preserving projection (LPP), to develop a new DR algorithm called SISG-LPP.Similar to LPP, the goal of SISG-LPP is preserving the local manifold structures in high-dimensional space. Given a set ofN samples X={x1,…,xN}, xi∈RD, in high-dimensional space, we try to find a transformation matrix which can map these N points to a set of points y1,…,yN in low-dimensional space. Assuming that the projection is y=αTx, where α is the projection vector, the objective function of SISG-LPP is given in(16)∑ij‍∥yi-yj∥2WSISG=∑ij‍(yi2+yj2-2yiyi)WSISG=∑ij‍yi2WijSISG+∑ij‍yj2WijSISG-∑ij‍yiyjWijSISG-∑ij‍yjyiWijSISG=∑ij‍yi2Dii+∑ij‍yi2Djj′-∑ij‍yiyjWijSISG-∑ij‍yjyiWijSISG=αTX((Dii+Djj′)-(WijSISG+(WijSISG)T))XTα=αTX(D¯-W¯)XTα=αTXL¯XTα.In the above,WSISG is an asymmetric matrix, but W¯=WijSISG+(WijSISG)T is a symmetric matrix. Let Dii and Djj′ denote the diagonal matrices; the entries of Dii are column sums of WSISG, and the entries of Djj′ are column sums of (WijSISG)T. D¯=Dii+Djj′ is the diagonal matrix whose entries are column sums of W¯. So, L¯=D¯-W¯ is the Laplacian matrix. Because D¯ provides a measure on the “importance” of the data points, we impose the following constraint:
(17)αTX(Dii+Djj′)XTα=αTXD¯XTα=1.Thus, the optimization objective of SISG-LPP is(18)α*=argmin⁡αTXD¯XTα=1αTXL¯XTα.The solutions of (18) can be obtained by solving the generalized eigenvalue decomposition problem [21]. That is to say, the projection vectors of (18) are actually the eigenvectors which correspond to the first l smallest eigenvalues of XL¯XTα=λXD¯XTα [22].


## 4. Experiments

In order to intuitively illustrate the construction process and the properties of SISG, we created an experiment to elucidate structure changes of SISG during the construction process. In addition, the experiment was also designed to show the differences between SISG and thek-nearest neighbor graph.In order to show the visualization effect of SISG, we compared the visualization effect of SISG-LPP, LPP [20], PCA [5], and NPE [11] on the ORL database [23].To investigate the influence of parameters on the classification performance of learning algorithms, we designed an experiment to show the sensitivity of LPP to the neighbor parameterk.In order to test and evaluate the effectiveness of SISG and SISG-LPP, we conducted a series of face recognition experiments on three well-known databases.


### 4.1. Experiment for the Structure of SISG

In this experiment, we hope to demonstrate the structure changes of SISG during the construction process. By comparing the structure ofk-nearest neighbor graph and that of SISG, we will be able to illustrate differences between them. This experiment was conducted on the well-known ORL database [23]. The ORL database contains 400 images from 40 different persons (ten for each person). All images are gray scale and the size of each image is 112×92 pixels. Figure 6(a) shows 10 sample face images for one person in ORL.First, we design a dataset containing ten images selected from the ORL database. Among all these images, six of them belong to the same person (in our dataset, images 2, 3, 4, 6, 7, and 9 belong to the same person) and the rest were selected at random. Then, we visualize the sample similarity matrix (Sij) of SISG, the adjacency matrix (E) of SISG, and the traditional k-nearest neighbor graph for the dataset, as shown in Figures 2, 3(a), and 3(b). Finally, we compare the adjacency matrix of SISG and the k-nearest neighbor graph.Figure 2
The sample similarity matrix of SISG.Visualization of the adjacency matrix of SISG (a) and thek-nearest neighbor (k=5) graph (b).
(a)
(b)In Figure2, those numbers without parentheses display the sample similarity between sample pairs. Sample similarity is described by the number of column neighbors between sample pairs. The value of Row 2 and Column 6 of Figure 2 is 16, and the value of Row 6 and Column 2 is 19, which, respectively, means that 16 columns of Image A6 become column neighbors of Image A2 and 19 columns of Image A2 become column neighbors of Image A6. After calculating the sample similarities, we determine each nearest neighbor according to sample similarity. When determining the nearest neighbors of each sample, we do not consider such sample pairs which are not similar to each other at all. For example, the value of Row 1 and Column 3 of Figure 2 is zero, which means Image A3 is impossible to become a neighbor of Image A1.Black squares in Figures3(a) and 3(b) indicate the two samples which are connected by them are neighbors. From Figures 3(a) and 3(b) we can see the following.(1)
Thek-nearest neighbor graph is symmetric while the SISG is asymmetric. For example, we can observe from (a) that Image A9 is a neighbor of Image A5 but Image A5 is not a neighbor of Image A9.(2)
SISG can more accurately reflect the relationship between samples. From (a) we can see that images which became neighbors generally belong to the same person. For example, from the second row of (a) we can see that ImagesA3,A4,A6,A7, and A9 are neighbors of Image A2, and from the third row of (a) we also can see that Images A2,A4, and A7 are neighbors of A3. We know that, in our dataset, Images A2,A3,A4,A6,A7, and A9 belong to the same person, so this example shows that the SISG makes similar samples become neighbors.(3)
Thek-nearest neighbor graph does not very successfully reflect the relationship between samples. We also take Image A2 as an example; from the second row of (b) we can observe that Images A3,A6,A7,A8, and A9 are neighbors of Image A2, but in fact, Images A8 and A2 do not belong to the same person. From the third row of (b) we can also see that Images A1,A2,A6,A9, and A10 are neighbors of Image A3, but in fact, Images A1,A3, and A10 do not belong to the same person.


### 4.2. Face Manifold Visualization

In this experiment, we compare the visualization effect of SISG-LPP, LPP, PCA, and NPE. We randomly selected 4 people from the ORL database and 10 samples from each person. Then we mapped all these samples to the 2-dimensional subspace using these algorithms. From Figure4(a) we can see that SISG-LPP more effectively separates the 4-class samples in its 2-dimensional reduction subspace. In contrast, in the subspaces of LPP (Figure 4(b)) and NPE (Figure 4(c)), the samples are not very well separated, and more than half of the samples overlapped. From Figure 4(d) we can see that in the subspace of PCA, the samples are basically entangled together.The 2-dimensional visualization of the four algorithms on the ORL database. (a) SISG-LPP, (b) LPP, (c) NPE, and (d) PCA.
(a)
(b)
(c)
(d)


### 4.3. Parameter Sensitivity of LPP

Since SISG does not have the neighbor parameterk, in this experiment, we only investigate the sensitivity of LPP to the neighbor parameter k. During this experiment, the set of images selected from face databases were partitioned into different sample collections. We use Gm/Pn to indicate that for each person in the face database m images were selected at random for training and the remaining n images were employed for testing. We conducted this experiment on G6/P4 in the ORL database. From Figure 5 we can see that LPP is very sensitive to the neighbor parameter k. In contrast, SISG-LPP does not have neighbor parameter k, so it is much less sensitive to the parameter than LPP.Figure 5
Influence of the parameterk on the classification performance of LPP.Sample face images from one person. (a) ORL, (b) YALE, and (c) the Illumination subset of PIE.
(a)
(b)
(c)


### 4.4. Face Recognition

To evaluate the proposed SISG and SISG-LPP algorithm, we compare the performance of SISG-LPP with LPP on three face databases. Here, we adopt the benchmark face databases ORL [23], YALE [24], and the subset of CMU PIE [25] to conduct experiments on face recognition. There are faces of 15 people in the YALE database, and each person has 11 face images with size 100×100. The CMU PIE database contains 41,368 images from 68 people, and the word PIE means Pose, Illumination, and Expression. The size of images in the PIE database is 217×178. In this research, we use the Illumination subset of the CMU PIE database to conduct our experiment; we select 16 different images per person from the Illumination subset. Figures 6(a), 6(b), and 6(c) show part of the face images in ORL, YALE, and the Illumination subset of PIE, respectively.As described above, we useGm/Pn to indicate that m images from each person are randomly selected as the training data and the remaining n images are used for testing. For each division with Gm/Pn, 50 random splits are generated and the final performance of the algorithm being tested is obtained by averaging the results of 50 classification accuracy values. The neighbor parameter k for LPP is set to m-1.Firstly, for each person we selectm (m = 5, 6) images from the ORL database and YALE database, respectively. Four divisions are considered: G5/P5,G6/P4 on the ORL database as well as G5/P6, G6/P5 on the YALE database; 50 random splits are generated and the final results of the four divisions are obtained by taking the mean of the 50 classification accuracy values. The accuracy values versus the numbers of reduced dimensions are shown by Figure 7.The recognition accuracy values of SISG-LPP and LPP versus the dimensions. (a)G5/P5 of the ORL database, (b) G6/P4 of the ORL database, (c) G5/P6 of the YALE database, and (d) G6/P5 of the YALE database.
(a)
(b)
(c)
(d)From Figures7(a) and 7(b) we can see that SISG-LPP outperforms LPP for all divisions, and from Figure 7(b) we can observe that SISG-LPP significantly outperforms LPP when the number of the reduced dimensions is relatively low. From Figures 7(c) and 7(d) we can find that SISG-LPP outperforms LPP for most of the situations.The mean accuracy values of LPP and SISG-LPP on ORL, YALE, and the Illumination subset of PIE database are listed in Tables1~3, respectively.Table 1
Mean accuracy values of LPP and SISG-LPP on the ORL database. The numbers in parentheses are the corresponding feature dimensions with the best results after dimensionality reduction.
G
2/P8
G
3/P7
G
4/P6
G
5/P5
G
6/P4
G
7/P3
G
8/P2
LPP
55.53 (55)
59.41 (95)
76.42 (46)
82.70 (32)
85.63 (59)
88.13 (45)
90.40 (37)
SISG-LPP
65.88 (61)
75.10 (55)
79.88 (48)
83.87 (52)
85.99 (67)
89.70 (63)
91.73 (57)From the results shown in Tables1~3, one can find the following.(1)
The overall accuracy values of all algorithms are improved at various degrees when the number of training samples is increased.(2)
From the results shown in Tables1 and 2, one can see that the recognition accuracy values of SISG-LPP are much higher than that of LPP when the number of training samples is relatively small. For instance, the accuracy of SISG-LPP on the division G3/P7 of the ORL database is 15.69% higher than that of LPP, while the accuracy of SISG-LPP on the division G8/P2 is only 1.33% higher than that of LPP.(3)
SISG-LPP outperforms LPP in all divisions withGm/Pn on the ORL and YALE databases. SISG-LPP outperforms LPP for most of the divisions with Gm/Pn on the Illumination subset of PIE database.Table 2
Mean accuracy values of LPP and SISG-LPP on the YALE database. The numbers in parentheses are the corresponding feature dimensions with the best results after dimensionality reduction.
G
2/P9
G
3/P8
G
4/P7
G
5/P6
G
6/P5
G
7/P4
G
8/P3
LPP
61.36 (25)
67.42 (32)
74.67 (37)
77.20 (34)
78.51 (17)
79.37 (46)
81.33 (69)
SISG-LPP
66.93 (25)
71.63 (35)
75.43 (45)
78.36 (26)
79.33 (47)
80.20 (55)
82.40 (61)Table 3
Mean accuracy values of LPP and SISG-LPP on the Illumination subset of PIE database. The numbers in parentheses are the corresponding feature dimensions with the best results after dimensionality reduction.
G
2/P14
G
3/P13
G
4/P12
G
5/P11
G
6/P10
G
7/P9
G
8/P8
LPP
81.88 (88)
91.91 (110)
95.88 (134)
98.31 (155)
99.17 (169)
99.58 (184)
99.90 (195)
SISG-LPP
80.75 (90)
92.98 (122)
96.32 (145)
98.55 (154)
99.33 (168)
99.62 (182)
99.94 (199)


## 4.1. Experiment for the Structure of SISG

In this experiment, we hope to demonstrate the structure changes of SISG during the construction process. By comparing the structure ofk-nearest neighbor graph and that of SISG, we will be able to illustrate differences between them. This experiment was conducted on the well-known ORL database [23]. The ORL database contains 400 images from 40 different persons (ten for each person). All images are gray scale and the size of each image is 112×92 pixels. Figure 6(a) shows 10 sample face images for one person in ORL.First, we design a dataset containing ten images selected from the ORL database. Among all these images, six of them belong to the same person (in our dataset, images 2, 3, 4, 6, 7, and 9 belong to the same person) and the rest were selected at random. Then, we visualize the sample similarity matrix (Sij) of SISG, the adjacency matrix (E) of SISG, and the traditional k-nearest neighbor graph for the dataset, as shown in Figures 2, 3(a), and 3(b). Finally, we compare the adjacency matrix of SISG and the k-nearest neighbor graph.Figure 2
The sample similarity matrix of SISG.Visualization of the adjacency matrix of SISG (a) and thek-nearest neighbor (k=5) graph (b).
(a)
(b)In Figure2, those numbers without parentheses display the sample similarity between sample pairs. Sample similarity is described by the number of column neighbors between sample pairs. The value of Row 2 and Column 6 of Figure 2 is 16, and the value of Row 6 and Column 2 is 19, which, respectively, means that 16 columns of Image A6 become column neighbors of Image A2 and 19 columns of Image A2 become column neighbors of Image A6. After calculating the sample similarities, we determine each nearest neighbor according to sample similarity. When determining the nearest neighbors of each sample, we do not consider such sample pairs which are not similar to each other at all. For example, the value of Row 1 and Column 3 of Figure 2 is zero, which means Image A3 is impossible to become a neighbor of Image A1.Black squares in Figures3(a) and 3(b) indicate the two samples which are connected by them are neighbors. From Figures 3(a) and 3(b) we can see the following.(1)
Thek-nearest neighbor graph is symmetric while the SISG is asymmetric. For example, we can observe from (a) that Image A9 is a neighbor of Image A5 but Image A5 is not a neighbor of Image A9.(2)
SISG can more accurately reflect the relationship between samples. From (a) we can see that images which became neighbors generally belong to the same person. For example, from the second row of (a) we can see that ImagesA3,A4,A6,A7, and A9 are neighbors of Image A2, and from the third row of (a) we also can see that Images A2,A4, and A7 are neighbors of A3. We know that, in our dataset, Images A2,A3,A4,A6,A7, and A9 belong to the same person, so this example shows that the SISG makes similar samples become neighbors.(3)
Thek-nearest neighbor graph does not very successfully reflect the relationship between samples. We also take Image A2 as an example; from the second row of (b) we can observe that Images A3,A6,A7,A8, and A9 are neighbors of Image A2, but in fact, Images A8 and A2 do not belong to the same person. From the third row of (b) we can also see that Images A1,A2,A6,A9, and A10 are neighbors of Image A3, but in fact, Images A1,A3, and A10 do not belong to the same person.


## 4.2. Face Manifold Visualization

In this experiment, we compare the visualization effect of SISG-LPP, LPP, PCA, and NPE. We randomly selected 4 people from the ORL database and 10 samples from each person. Then we mapped all these samples to the 2-dimensional subspace using these algorithms. From Figure4(a) we can see that SISG-LPP more effectively separates the 4-class samples in its 2-dimensional reduction subspace. In contrast, in the subspaces of LPP (Figure 4(b)) and NPE (Figure 4(c)), the samples are not very well separated, and more than half of the samples overlapped. From Figure 4(d) we can see that in the subspace of PCA, the samples are basically entangled together.The 2-dimensional visualization of the four algorithms on the ORL database. (a) SISG-LPP, (b) LPP, (c) NPE, and (d) PCA.
(a)
(b)
(c)
(d)


## 4.3. Parameter Sensitivity of LPP

Since SISG does not have the neighbor parameterk, in this experiment, we only investigate the sensitivity of LPP to the neighbor parameter k. During this experiment, the set of images selected from face databases were partitioned into different sample collections. We use Gm/Pn to indicate that for each person in the face database m images were selected at random for training and the remaining n images were employed for testing. We conducted this experiment on G6/P4 in the ORL database. From Figure 5 we can see that LPP is very sensitive to the neighbor parameter k. In contrast, SISG-LPP does not have neighbor parameter k, so it is much less sensitive to the parameter than LPP.Figure 5
Influence of the parameterk on the classification performance of LPP.Sample face images from one person. (a) ORL, (b) YALE, and (c) the Illumination subset of PIE.
(a)
(b)
(c)


## 4.4. Face Recognition

To evaluate the proposed SISG and SISG-LPP algorithm, we compare the performance of SISG-LPP with LPP on three face databases. Here, we adopt the benchmark face databases ORL [23], YALE [24], and the subset of CMU PIE [25] to conduct experiments on face recognition. There are faces of 15 people in the YALE database, and each person has 11 face images with size 100×100. The CMU PIE database contains 41,368 images from 68 people, and the word PIE means Pose, Illumination, and Expression. The size of images in the PIE database is 217×178. In this research, we use the Illumination subset of the CMU PIE database to conduct our experiment; we select 16 different images per person from the Illumination subset. Figures 6(a), 6(b), and 6(c) show part of the face images in ORL, YALE, and the Illumination subset of PIE, respectively.As described above, we useGm/Pn to indicate that m images from each person are randomly selected as the training data and the remaining n images are used for testing. For each division with Gm/Pn, 50 random splits are generated and the final performance of the algorithm being tested is obtained by averaging the results of 50 classification accuracy values. The neighbor parameter k for LPP is set to m-1.Firstly, for each person we selectm (m = 5, 6) images from the ORL database and YALE database, respectively. Four divisions are considered: G5/P5,G6/P4 on the ORL database as well as G5/P6, G6/P5 on the YALE database; 50 random splits are generated and the final results of the four divisions are obtained by taking the mean of the 50 classification accuracy values. The accuracy values versus the numbers of reduced dimensions are shown by Figure 7.The recognition accuracy values of SISG-LPP and LPP versus the dimensions. (a)G5/P5 of the ORL database, (b) G6/P4 of the ORL database, (c) G5/P6 of the YALE database, and (d) G6/P5 of the YALE database.
(a)
(b)
(c)
(d)From Figures7(a) and 7(b) we can see that SISG-LPP outperforms LPP for all divisions, and from Figure 7(b) we can observe that SISG-LPP significantly outperforms LPP when the number of the reduced dimensions is relatively low. From Figures 7(c) and 7(d) we can find that SISG-LPP outperforms LPP for most of the situations.The mean accuracy values of LPP and SISG-LPP on ORL, YALE, and the Illumination subset of PIE database are listed in Tables1~3, respectively.Table 1
Mean accuracy values of LPP and SISG-LPP on the ORL database. The numbers in parentheses are the corresponding feature dimensions with the best results after dimensionality reduction.
G
2/P8
G
3/P7
G
4/P6
G
5/P5
G
6/P4
G
7/P3
G
8/P2
LPP
55.53 (55)
59.41 (95)
76.42 (46)
82.70 (32)
85.63 (59)
88.13 (45)
90.40 (37)
SISG-LPP
65.88 (61)
75.10 (55)
79.88 (48)
83.87 (52)
85.99 (67)
89.70 (63)
91.73 (57)From the results shown in Tables1~3, one can find the following.(1)
The overall accuracy values of all algorithms are improved at various degrees when the number of training samples is increased.(2)
From the results shown in Tables1 and 2, one can see that the recognition accuracy values of SISG-LPP are much higher than that of LPP when the number of training samples is relatively small. For instance, the accuracy of SISG-LPP on the division G3/P7 of the ORL database is 15.69% higher than that of LPP, while the accuracy of SISG-LPP on the division G8/P2 is only 1.33% higher than that of LPP.(3)
SISG-LPP outperforms LPP in all divisions withGm/Pn on the ORL and YALE databases. SISG-LPP outperforms LPP for most of the divisions with Gm/Pn on the Illumination subset of PIE database.Table 2
Mean accuracy values of LPP and SISG-LPP on the YALE database. The numbers in parentheses are the corresponding feature dimensions with the best results after dimensionality reduction.
G
2/P9
G
3/P8
G
4/P7
G
5/P6
G
6/P5
G
7/P4
G
8/P3
LPP
61.36 (25)
67.42 (32)
74.67 (37)
77.20 (34)
78.51 (17)
79.37 (46)
81.33 (69)
SISG-LPP
66.93 (25)
71.63 (35)
75.43 (45)
78.36 (26)
79.33 (47)
80.20 (55)
82.40 (61)Table 3
Mean accuracy values of LPP and SISG-LPP on the Illumination subset of PIE database. The numbers in parentheses are the corresponding feature dimensions with the best results after dimensionality reduction.
G
2/P14
G
3/P13
G
4/P12
G
5/P11
G
6/P10
G
7/P9
G
8/P8
LPP
81.88 (88)
91.91 (110)
95.88 (134)
98.31 (155)
99.17 (169)
99.58 (184)
99.90 (195)
SISG-LPP
80.75 (90)
92.98 (122)
96.32 (145)
98.55 (154)
99.33 (168)
99.62 (182)
99.94 (199)


## 5. Conclusions

In this paper, we present a new graph construction method, and we name the graph constructed by this method as samples’ inner structure based graph (SISG). Unlike the traditional graph construction method, SISG avoids predefining neighbor parameterk (or ɛ). Moreover, SISG can also well preserve intrinsic features of samples by using samples’ inner structure information to construct graph. Both the weighted adjacency matrix and the adjacency matrix of SISG are generally asymmetric, which may be more reasonable for capturing the relationships among samples. For the sake of proving that the construction method of SISG is very general, we incorporated it into a state-of-the-art DR algorithm, locality preserving projection (LPP), and thus developed a novel DR algorithm SISG-LPP. Finally, several experiments are conducted on three well-known face databases. Experimental results verified the effectiveness and feasibility of the SISG and SISG-LPP algorithms.



---

*Source: 603025-2014-07-03.xml*