# Robust Graph Structure Learning for Multimedia Data Analysis

Authors: Wei Zhou; Zhaoxuan Gong; Wei Guo; Nan Han; Shaojie Qiao
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

With the rapid development of computer network technology, we can acquire a large amount of multimedia data, and it becomes a very important task to analyze these data. Since graph construction or graph learning is a powerful tool for multimedia data analysis, many graph-based subspace learning and clustering approaches have been proposed. Among the existing graph learning algorithms, the sample reconstruction-based approaches have gone the mainstream. Nevertheless, these approaches not only ignore the local and global structure information but also are sensitive to noise. To address these limitations, this paper proposes a graph learning framework, termed Robust Graph Structure Learning (RGSL). Different from the existing graph learning approaches, our approach adopts the self-expressiveness of samples to capture the global structure, meanwhile utilizing data locality to depict the local structure. Specially, in order to improve the robustness of our approach against noise, we introducel2,1-norm regularization criterion and nonnegative constraint into the graph construction process. Furthermore, an iterative updating optimization algorithm is designed to solve the objective function. A large number of subspace learning and clustering experiments are carried out to verify the effectiveness of the proposed approach.


---

## Body

## 1. Introduction

With the rapid growth of information technology and computer network technology, a large number of multimedia data can be collected from many research fields such as computer vision, image processing, and natural language processing. However, most of the multimedia data are represented by the high dimension and complex structures [1, 2]. Therefore, how to accurately analyze these data becomes a vital problem. Inspired by the pattern recognition and machine learning techniques, many multimedia data analysis approaches based on subspace learning and clustering have been put forward recently [3–6]. However, learning or constructing a valuable graph to describe the pairwise similarity or relationship among the samples is a key issue to multimedia data analysis [7].Nowadays, a series of graph learning approaches have been proposed in which the heat-kernel function is the most widely used graph construction manner, such ask-nearest-neighborhood graph (k-NN graph) or ε-nearest-neighborhood graph (ε graph). The edges of vertexes are computed based on the Euclidean distance among samples and then the weights of the edge between two vertexes are estimated by the heat kernel [8]. However, there are two main limitations in these approaches [9]. First, the choice of parameters in these approaches, such as the neighbor number k or radius ε, is very challenging, which can impact the final performance of the task. Second, the processes of neighbor selection and weight calculation are independent, which are sensitive to noise and often cannot well reveal the real similarities of samples [10].To overcome these drawbacks, sparse representation (SR) based graph construction approach has been proposed, which is often calledl1-graph or sparse graph. In l1-graph [11], each sample is regarded as the query sample and the rest of samples are considered as the dictionary to represent the query sample. Therefore, the similarities between the query sample and the remainder samples can be measured. Since l1-graph employs l1-norm constraint on the regression model for selecting a few important samples, it has a better discriminability and more robustness to deal with noise. In the past decades, a series of excellent learning approaches based on l1-graph have been designed and successfully applied in different areas [12]. Although l1-graph can reveal the linear relationship between a single point and other points, there are still some limitations as follows. First, l1-graph strictly assumes the dictionary of regression should be overcompleted, which is unsatisfied in many real applications especially for the graph learning. Second, l1-graph pays too much attention on the sparsity while it neglects the correlations between the samples, so it cannot offer a smooth data representation. Therefore, SR is not a good choice for graph construction. To overcome the aforementioned problems suffered by SR, Zhang et al. [13] introduced a Collaborative Representation (CR) linear regression approach by employing the l2-norm rather than l1-norm sparsity regularization. Compared to SR, CR provides more relaxation for regression coefficients and obtains a smoother data representation.Considering that both SR and CR usually reveal the linear relationship between a single data point and other data points, the global structure of the data is ignored. To address this problem, Liu et al. [14] suggested Low-Rank Representation (LRR) for subspace clustering. The main purpose of LRR is to find a coefficient matrix Z by trying to reconstruct each data point as a linear combination of all the other data points, which is called self-representation. Different from the traditional similarity measurement approaches based on distance, i.e., k-nearest neighborhood or ε-nearest neighborhood, the representation-based approaches, such as SR, CR, or LRR, measure the similarity between data by solving an optimization problem. These approaches improve the image structure to achieve better classification and clustering performance overall. However, the objective function of LRR is not differentiable which has a high computation complexity on solving the rank minimization problem. To efficiently solve the limitation of LRR, Lu et al. [15] proposed Least Squares Regression (LSR) by grouping the highly correlated data together, which is robust to noise. Compared with LRR, LSR is simpler and more efficient.In recent years, researchers found that the relationships between data in real applications usually show high dimension nonlinear, so the aforementioned linear representation approaches can hardly achieve good performance. Many researchers paid more attention on revealing the nonlinear relationship between data points of interests [16–27]. For example, Wang et al. [28] explored the criterion of Locally Linear Embedding (LLE) and used it to construct the graph by computing the weights between the pairs of samples. Wei and Peng [29] adopted a similar criterion to that LLE to construct a neighborhood-preserving graph for semisupervised dimensionality reduction. Furthermore, Yu et al. [30] have found that the nonzero coefficients of the sparse coding always are assigned to the neighbor samples of the query sample. To encourage the coding to be locality, some local feature-based coding approaches have been proposed, which achieve excellent performance for the classification and clustering tasks [31]. With the usage of the merits of local constraints, Peng et al. [32] put forward Locality-Constrained Collaborative (LCC) representation, which achieves better classification performance than those nonlocal approaches. Chen and Yi [33] took the local constraint and LSR into consideration and designed Locality-Constrained LSR (LCLSR) for subspace clustering. LCLSR explores both the global structure of data points and the local linear relationship for data points, forcing the representation to prefer the selection of neighborhood points. Although LCLSR considers the locality structure of data, there are still some limitations on the graph structure. On the one hand, the objective function of LCLSR is based on l2-norm, which is very sensitive to noise; on the other hand, the process of sample reconstruction ignores the relationships between sample representations. For example, similar original samples should generate similar coding vectors, and this process weakens the effectiveness of graph learning approaches.To combat these issues, we design a novel graph learning approach, named Robust Graph Structure Learning (RGSL). Specifically, the self-expressiveness of samples and adaptive neighbor selection approach are introduced to preserve both the local and global structures of data. For enhancing the robustness of graph construction, we introduce thel2,1-norm constraint and nonnegative constraint on the adjacency graph weight matrix to reduce the influence of noise points in graph construction. Therefore, the proposed approach can estimate the graph from data alone by self-expressiveness of samples and data locality, which is independent of a priori affinity matrix. We assess the benefits of the proposed approach on the subspace learning and clustering tasks. Extensive experiments verify the effectiveness of the proposed approach over other state-of-the-art approaches. The framework of the proposed approach is shown in Figure 1.Figure 1
The framework of the proposed approach.The outline of this paper is as follows. Section2 reviews some related work briefly. Section 3 gives the proposed approach in details. Section 4 shows extensive experiments to prove the effectiveness of the proposed approach. Section 5 presents some conclusions.


## 2. Related Work

In this section, first, many classic and widely used graph construction approaches are introduced. Then, two kinds of multimedia data analysis techniques including subspace learning and spectral clustering are presented in detail accordingly.


### 2.1. Graph Construction Approaches

Recently, many graph construction approaches have been proposed for multimedia data analysis. In this subsection, we will review some graph construction approaches related to our work as below.Liu et al. [14] proposed a Low-Rank Representation (LRR) graph construction approach, in which each sample can be represented by a linear combination of all samples, and meanwhile, a low-rank constraint of coefficient matrix is imposed. Given a high dimensional database X=x1,x2,⋯,xN∈Rd×N in which d is the data dimensionality and N is the number of samples. The LRR graph can be obtained by optimizing the following problem:
(1)minWW∗s.t.X=XW,where ⋅∗ denotes the nuclear norm of a matrix, i.e., the sum of the singular values of the matrix. W denotes the coefficient matrix of data X with the lowest rank.Although LRR graph can obtain the global structure of data, it is very time-consuming to solve the problem of optimal nuclear norm. Hence, Lu et al. [15] utilized the l2-graph based on Frobenius norm in place of nuclear norm for fast computing the weight matrix. The LSR graph is defined as
(2)minWXFs.t.X=XW,diagW=0,where ⋅F is the Frobenius norm. diag⋅ denotes the diagonal operation of a matrix.In order to make full use of the advantage of locality constraints, Chen and Yi [33] combined LSR and the locality constraints into a unified framework and proposed the LCLSR approach for graph construction. The objective function of LCLSR is
(3)minW12X−XWF2+β12WF2+β22W⊙DF2,where β1 and β2 are two balance parameters and the symbol ⊙ represents the Hadamard product. D=dijN×N=edistxi,xjN×N denotes the distance matrix between samples where the function distxi,xj is a distance metric, such as the Euclidean distance.


### 2.2. Subspace Learning

Locality Preserving Projection (LPP) [34] is a well-known subspace learning approach which is used to discover the geometric property of high-dimensional feature space. Suppose that the adjacency graph weight matrix W is given, LPP as aims at ensuring that if the original high-dimensional samples xi and xj are “close,” then the low-dimensional representations yi and yj should be close as well. With the usage of weight matrix Wij as a penalty, LPP is to minimize the following objective function:
(4)12∑i,j=1Nyi−yj22Wij=trWTXLXTW,where L=D−W is the Laplacian matrix, in which D is a diagonal matrix with diagonal elements dii=∑j=1NWij. trS is the trace of matrix S. dii is used to measure the local density around xi and the bigger dii indicates that yi is more important. Hence, a nature constraint can be imposed as YTDY=I. Based on the equation Y=PTX, the LPP model can be rewritten as
(5)minPtrPTXLXTPs.t.PTXDXTP=I.The projection matrixP is constructed by the eigenvectors associated with d smallest nonzero eigenvalues, which can be solved by
(6)XLXTp=λXDXTp.For a new high-dimensional datax, with the usage of the obtained projection matrix P, we can obtain a low-dimensional data representation by y=PTx.


### 2.3. Spectral Clustering

Spectral clustering is a popular clustering approach that uses eigenvectors of a symmetric matrix derived from the distance between data points [35, 36]. Given a data set consisting of N data points X∈RN×D, spectral clustering approach is aimed at partitioning X into K disjoint clusters by exploiting the top K eigenvectors of the normalized graph Laplacian L. Suppose that the graph matrix W is obtained by graph construction approaches and the new representation Q∈RC×N can be acquired by optimizing the following objective function:
(7)minQQT=ITrQLWQT,where LW=D−W+WT/2 is the Laplacian matrix of W, in which D∈RN×N is the diagonal matrix with dii=∑jwij+wji/2. C is the number of selected clusters. Each column in Q represents the new discriminative representation of the corresponding original sample.Finally, data clustering can be accomplished by performingK-means on the new representation Q.


## 2.1. Graph Construction Approaches

Recently, many graph construction approaches have been proposed for multimedia data analysis. In this subsection, we will review some graph construction approaches related to our work as below.Liu et al. [14] proposed a Low-Rank Representation (LRR) graph construction approach, in which each sample can be represented by a linear combination of all samples, and meanwhile, a low-rank constraint of coefficient matrix is imposed. Given a high dimensional database X=x1,x2,⋯,xN∈Rd×N in which d is the data dimensionality and N is the number of samples. The LRR graph can be obtained by optimizing the following problem:
(1)minWW∗s.t.X=XW,where ⋅∗ denotes the nuclear norm of a matrix, i.e., the sum of the singular values of the matrix. W denotes the coefficient matrix of data X with the lowest rank.Although LRR graph can obtain the global structure of data, it is very time-consuming to solve the problem of optimal nuclear norm. Hence, Lu et al. [15] utilized the l2-graph based on Frobenius norm in place of nuclear norm for fast computing the weight matrix. The LSR graph is defined as
(2)minWXFs.t.X=XW,diagW=0,where ⋅F is the Frobenius norm. diag⋅ denotes the diagonal operation of a matrix.In order to make full use of the advantage of locality constraints, Chen and Yi [33] combined LSR and the locality constraints into a unified framework and proposed the LCLSR approach for graph construction. The objective function of LCLSR is
(3)minW12X−XWF2+β12WF2+β22W⊙DF2,where β1 and β2 are two balance parameters and the symbol ⊙ represents the Hadamard product. D=dijN×N=edistxi,xjN×N denotes the distance matrix between samples where the function distxi,xj is a distance metric, such as the Euclidean distance.


## 2.2. Subspace Learning

Locality Preserving Projection (LPP) [34] is a well-known subspace learning approach which is used to discover the geometric property of high-dimensional feature space. Suppose that the adjacency graph weight matrix W is given, LPP as aims at ensuring that if the original high-dimensional samples xi and xj are “close,” then the low-dimensional representations yi and yj should be close as well. With the usage of weight matrix Wij as a penalty, LPP is to minimize the following objective function:
(4)12∑i,j=1Nyi−yj22Wij=trWTXLXTW,where L=D−W is the Laplacian matrix, in which D is a diagonal matrix with diagonal elements dii=∑j=1NWij. trS is the trace of matrix S. dii is used to measure the local density around xi and the bigger dii indicates that yi is more important. Hence, a nature constraint can be imposed as YTDY=I. Based on the equation Y=PTX, the LPP model can be rewritten as
(5)minPtrPTXLXTPs.t.PTXDXTP=I.The projection matrixP is constructed by the eigenvectors associated with d smallest nonzero eigenvalues, which can be solved by
(6)XLXTp=λXDXTp.For a new high-dimensional datax, with the usage of the obtained projection matrix P, we can obtain a low-dimensional data representation by y=PTx.


## 2.3. Spectral Clustering

Spectral clustering is a popular clustering approach that uses eigenvectors of a symmetric matrix derived from the distance between data points [35, 36]. Given a data set consisting of N data points X∈RN×D, spectral clustering approach is aimed at partitioning X into K disjoint clusters by exploiting the top K eigenvectors of the normalized graph Laplacian L. Suppose that the graph matrix W is obtained by graph construction approaches and the new representation Q∈RC×N can be acquired by optimizing the following objective function:
(7)minQQT=ITrQLWQT,where LW=D−W+WT/2 is the Laplacian matrix of W, in which D∈RN×N is the diagonal matrix with dii=∑jwij+wji/2. C is the number of selected clusters. Each column in Q represents the new discriminative representation of the corresponding original sample.Finally, data clustering can be accomplished by performingK-means on the new representation Q.


## 3. Proposed Method

In this section, some notations are introduced first. Second, we give some detailed descriptions of the proposed RGSL approach. At last, an iterative update algorithm is designed to solve our RGSL approach.


### 3.1. Notations

LetX=x1,x2,⋯,xN∈RD×N be the given high-dimensional original data matrix, where D is the dimensionality of samples and N corresponds to the total number of samples. For a matrix B∈RD×N, the definitions of Frobenius norm and l2,1-norm are as follows: BF=∑i=1Dbi22=∑j=1Nbj22 and B2,1=∑i=1D∑j=1Nbij2, in which bi and bj are the i-th row and the j-th column of B, respectively.


### 3.2. Objective Function

First, in order to enhance the robustness of graph learning algorithm to noise and obtain the discriminative graph structure, thel2,1-norm measure criterion on the traditional LSR is introduced, which is defined as
(8)min∑i=1Nxi−Xwi2+αwi2=X−XW2,1+αW2,1=trX−XWTGX−XW+αtrWTQW,where ⋅2 and ⋅2,1 denote l2-norm and l2,1-norm, respectively. α is a balance parameter. G and Q are diagonal matrices whose diagonal elements are, respectively, defined as Gij=1/xi−Xwj2+ε and Qii=1/wi2+ε. ε is a small nonnegative constant for preventing the value of the denominator from being zero.Second, the relationship between representation coefficients is ignored in the sample reconstruction, i.e., similar original samples should generate similar coding vectors, weakening the effectiveness of graph learning. To solve the abovementioned issue, a modified manifold constraint based on thel2,1-norm is designed, which is defined as
(9)minW∑i,j=1Nwi−wj2sij=∑i,j=1Ntrwi−wjTRwi−wj=trWTD−RW=trWTLW,where sij denotes the similarity weight value between sample xi and sample xj. The elements in matrix R are defined as Rij=sij/wi−wj2+ε, and D is a diagonal matrix whose diagonal elements are Dii=∑j=1Rij. L is the Laplacian of the graph matrix W.At last, the nonnegative constraint is also imposed on the representation coefficients, and the final objective function of the proposed approach is(10)minX−XW2,1+αW2,1+βtrWTLW=trX−XWTGX−XW+αtrWTQW+βtrWTLWs.t.W≥0,where α and β are two positive balance parameters.


### 3.3. Optimization

In this section, we give the optimization procedures for the objective function of the proposed approach in Equation (10). From Equation (10), we can observe that the objective function is related to l2,1-norm. Thus, the variable W in the objective function is nonconvex and a closed form solution to Equation (10) cannot be given. With regard to this limitation, an iterative update algorithm is designed to optimize the objective function.


#### 3.3.1. FixG, Q, and R, Update W

First, we fix matricesG, Q, and R. After removing the irrelevant terms, the optimization problem with respect to W in Equation (10) can be simplified to
(11)mintrXTGX−2WTXTGX+WTXTGXW+αtrWTQW+βtrWTLWs.t.W≥0.The Lagrangian function of Equation (11) is represented as
(12)ℓW=trXTGX−2WTXTGX+WTXTGXW+αtrWTQW+βtrWTLW+λtrΛWs.t.W≥0.By computing the derivative of Equation (12) with respect to W and setting it equals to zero
(13)∂ℓW∂W=−2XTGX+2XTGXW+2αQW+2βLW+λΛ=0.According to the KKT condition [37], we update the solution for W as below:
(14)Wij=WijXTGXijαQ+βL+XTGXij.


#### 3.3.2. FixW, Update G, Q, and R

WhenW is fixed and all the irrelevant terms are removed, the solution can be formulated as
(15)Gij=1xi−Xwj2+ε,(16)Qii=1wi2+ε,(17)Rij=sijwi−wj2+ε.


### 3.4. Algorithm

In conclusion, the proposed optimization algorithm for RGSL can be summarized as below.Algorithm 1: RGSL.
1:Input: the data matrix X=x1,x2,⋯,xN, two balance parameters α and β.2:Initialize: set Gt and Qt to be the identity matrices, random matrix W, and sample similarity matrix S, t=1.3:Repeat4:  Update the matrixRt+1=Rt+1,ijN×N=sij/wt,i−wt,j2+ε5:  Compute the matrixDt+1,ii=∑j=1NRt+1,ij and the Laplacian matrix Lt+1=Dt+1−Rt+16:  Update the matrixWij=WijXTGXij/αQ+βL+XTGXij7: Update the matrixGt+1=Gt+1,ijN×N=1/xi−Xwt+1,j2+ε8:  Update the matrixQt+1=Qt+1,iiN×N=1/wt+1,i2+ε9: t=t+110:Until convergence11:Output: the graph matrix WIn Algorithm1, the convergence condition is defined as the change of the value of objective function in Equation (10) which is less than a threshold or a predefined maximum iteration number is reached.


## 3.1. Notations

LetX=x1,x2,⋯,xN∈RD×N be the given high-dimensional original data matrix, where D is the dimensionality of samples and N corresponds to the total number of samples. For a matrix B∈RD×N, the definitions of Frobenius norm and l2,1-norm are as follows: BF=∑i=1Dbi22=∑j=1Nbj22 and B2,1=∑i=1D∑j=1Nbij2, in which bi and bj are the i-th row and the j-th column of B, respectively.


## 3.2. Objective Function

First, in order to enhance the robustness of graph learning algorithm to noise and obtain the discriminative graph structure, thel2,1-norm measure criterion on the traditional LSR is introduced, which is defined as
(8)min∑i=1Nxi−Xwi2+αwi2=X−XW2,1+αW2,1=trX−XWTGX−XW+αtrWTQW,where ⋅2 and ⋅2,1 denote l2-norm and l2,1-norm, respectively. α is a balance parameter. G and Q are diagonal matrices whose diagonal elements are, respectively, defined as Gij=1/xi−Xwj2+ε and Qii=1/wi2+ε. ε is a small nonnegative constant for preventing the value of the denominator from being zero.Second, the relationship between representation coefficients is ignored in the sample reconstruction, i.e., similar original samples should generate similar coding vectors, weakening the effectiveness of graph learning. To solve the abovementioned issue, a modified manifold constraint based on thel2,1-norm is designed, which is defined as
(9)minW∑i,j=1Nwi−wj2sij=∑i,j=1Ntrwi−wjTRwi−wj=trWTD−RW=trWTLW,where sij denotes the similarity weight value between sample xi and sample xj. The elements in matrix R are defined as Rij=sij/wi−wj2+ε, and D is a diagonal matrix whose diagonal elements are Dii=∑j=1Rij. L is the Laplacian of the graph matrix W.At last, the nonnegative constraint is also imposed on the representation coefficients, and the final objective function of the proposed approach is(10)minX−XW2,1+αW2,1+βtrWTLW=trX−XWTGX−XW+αtrWTQW+βtrWTLWs.t.W≥0,where α and β are two positive balance parameters.


## 3.3. Optimization

In this section, we give the optimization procedures for the objective function of the proposed approach in Equation (10). From Equation (10), we can observe that the objective function is related to l2,1-norm. Thus, the variable W in the objective function is nonconvex and a closed form solution to Equation (10) cannot be given. With regard to this limitation, an iterative update algorithm is designed to optimize the objective function.


### 3.3.1. FixG, Q, and R, Update W

First, we fix matricesG, Q, and R. After removing the irrelevant terms, the optimization problem with respect to W in Equation (10) can be simplified to
(11)mintrXTGX−2WTXTGX+WTXTGXW+αtrWTQW+βtrWTLWs.t.W≥0.The Lagrangian function of Equation (11) is represented as
(12)ℓW=trXTGX−2WTXTGX+WTXTGXW+αtrWTQW+βtrWTLW+λtrΛWs.t.W≥0.By computing the derivative of Equation (12) with respect to W and setting it equals to zero
(13)∂ℓW∂W=−2XTGX+2XTGXW+2αQW+2βLW+λΛ=0.According to the KKT condition [37], we update the solution for W as below:
(14)Wij=WijXTGXijαQ+βL+XTGXij.


### 3.3.2. FixW, Update G, Q, and R

WhenW is fixed and all the irrelevant terms are removed, the solution can be formulated as
(15)Gij=1xi−Xwj2+ε,(16)Qii=1wi2+ε,(17)Rij=sijwi−wj2+ε.


## 3.3.1. FixG, Q, and R, Update W

First, we fix matricesG, Q, and R. After removing the irrelevant terms, the optimization problem with respect to W in Equation (10) can be simplified to
(11)mintrXTGX−2WTXTGX+WTXTGXW+αtrWTQW+βtrWTLWs.t.W≥0.The Lagrangian function of Equation (11) is represented as
(12)ℓW=trXTGX−2WTXTGX+WTXTGXW+αtrWTQW+βtrWTLW+λtrΛWs.t.W≥0.By computing the derivative of Equation (12) with respect to W and setting it equals to zero
(13)∂ℓW∂W=−2XTGX+2XTGXW+2αQW+2βLW+λΛ=0.According to the KKT condition [37], we update the solution for W as below:
(14)Wij=WijXTGXijαQ+βL+XTGXij.


## 3.3.2. FixW, Update G, Q, and R

WhenW is fixed and all the irrelevant terms are removed, the solution can be formulated as
(15)Gij=1xi−Xwj2+ε,(16)Qii=1wi2+ε,(17)Rij=sijwi−wj2+ε.


## 3.4. Algorithm

In conclusion, the proposed optimization algorithm for RGSL can be summarized as below.Algorithm 1: RGSL.
1:Input: the data matrix X=x1,x2,⋯,xN, two balance parameters α and β.2:Initialize: set Gt and Qt to be the identity matrices, random matrix W, and sample similarity matrix S, t=1.3:Repeat4:  Update the matrixRt+1=Rt+1,ijN×N=sij/wt,i−wt,j2+ε5:  Compute the matrixDt+1,ii=∑j=1NRt+1,ij and the Laplacian matrix Lt+1=Dt+1−Rt+16:  Update the matrixWij=WijXTGXij/αQ+βL+XTGXij7: Update the matrixGt+1=Gt+1,ijN×N=1/xi−Xwt+1,j2+ε8:  Update the matrixQt+1=Qt+1,iiN×N=1/wt+1,i2+ε9: t=t+110:Until convergence11:Output: the graph matrix WIn Algorithm1, the convergence condition is defined as the change of the value of objective function in Equation (10) which is less than a threshold or a predefined maximum iteration number is reached.


## 4. Experiment and Results

In this section, first, we will introduce the used databases in our experiment. Next, some graph learning comparison approaches are given. At last, subspace learning and clustering tasks are employed for verifying the effectiveness of the proposed approach.


### 4.1. Databases

Four commonly used multimedia databases from the Internet including Yale [38], AR [39], CMU PIE [40], and Extended YaleB [41] are used for verifying the effectiveness of the proposed approach. The detailed statistical information about the four different databases is depicted in Table 1.Table 1
Description of databases.
DatabasesImage sizeInstancesClassesInstances of per classYale32×321651511AR32×32140010014CMU PIE32×3216326824Extended YaleB32×3224323864Yale database: it contains 165 face images captured from 15 different subjects. Each subject has 11 different images with the varied facial expressions, under different illumination conditions, and wearing glasses or not. Some example images of the Yale database are depicted in Figure 2(a).Figure 2
Some of the images from the different databases employed in our experiments.
(a)
Yale(b)
AR(c)
CMU PIE(d)
Extended YaleBAR database: it consists of over 4000 facial images obtained from 70 male and 56 female faces. Images of each person were captured with 26 frontal face images with anger, smiling, and screaming, under varied illumination conditions, and with sunglass and scarf occlusions. Some examples of the AR database are shown in Figure 2(b).CMU PIE database: there are 41,368 face images of 68 different subjects. Images of each person are captured under 43 different illumination conditions with 13 different poses and 4 different expressions. Here, we employ a subset of CMU PIE which consists of 24 images per subject. A part of example images is illustrated in Figure 2(c).Extended YaleB database: there are 38 individuals and each individual has 64 images. For each individual, the face images are taken from different illumination conditions with small changes in head pose and facial expression. Example images from this database are shown in Figure 2(d).Although we can obtain the graph structure from the proposed approach, it is intractable to assess the graph learning approaches using the estimated graph alone. Hence, we will assess the quality of the learned graph by two kinds of multimedia data analysis tasks including subspace learning and spectral clustering. In our experiments, we first vary the graph construction approaches by fixing the graph learning task and then observe the obtained performance associated with subspace learning and spectral clustering tasks.


### 4.2. Comparison among Several Graph Learning Approaches

To investigate the performance of our approach on subspace learning and clustering, several state-of-the-art graph learning approaches are chosen to compare in our work, which are shown as below:(i)
KNN graph [8]: the graph edges connected by two vertexes can be generated by the Euclidean distance-based K-nearest neighbor and the heat kernel function is used to measure the weight of an edge(ii)
LLE graph [28]: each sample is linearly reconstructed by its neighbors within a local area to preserve the local manifold structure(iii)
L1 graph [11]: the locality structure of data by using L1 sparse representation optimization(iv)
LRR graph [14]: based on self-expressive property, a low-rank graph is obtained(v)
LSR graph [15]: self-expressive property and Frobenius norm are used for fast computing the weight matrix(vi)
LCLSR graph [33]: it combines the locality constraint and LSR together to explore both the global structure of data points and the locality linear relationship of data points(vii)
SGLS graph [42]: it integrates manifold constraints on the unknown sparse codes as a graph regularizer(viii)
Our proposed RGSL graph: our approach takes the global and local structure information into consideration and also introduces thel2,1-norm regularization criterion and nonnegative constraint into graph construction process to enhance its robustness


### 4.3. Subspace Learning Experiment and Analysis

In this section, we employ an unsupervised subspace learning approach represented by Locality Preserving Projections (LPP) to verify the effectiveness of the proposed approach. In our experiments, different graphs are employed asW in LPP approach for subspace learning and then the classification accuracy is used for performance comparison. For each database, we randomly select l images from each class as the training samples. The remaining images are treated as the test samples. The values of l for Yale, AR, CMU PIE, and Extended YaleB databases are set as 4,5,6, 4,5,6, 6,8,10, and 10,15,20, respectively. In order to more effectively and fairly test the performance of the proposed approach, the random sample selection is repeated 20 times and the average classification accuracy and standard deviation are regarded as the final results for comparison. In this work, we employ the nearest neighbor classifier with Euclidean distance for classification due to its simplicity. To compare the performances of different approaches, the classification accuracy rate is chosen as the evaluation criterion, which is defined as
(18)Class_accuracy=Nt_correctNtotal×100%,where Nt_correct is the number of test samples which are correctly classified using the nearest neighbor classifier. Ntotal is the total number of the test samples.All the experiments are conducted using MATLAB 2016b on a 3.60 Hz with 8 G RAM. In order to acquire the optimal parameters of different approaches, we employ the grid-search manner in our experiments. Tables2–5 depict the average classification accuracy rates and standard deviations of the proposed approach on the Yale, AR, CMU PIE, and Extended YaleB databases, respectively. Note that the brackets in Tables 2–5 mean the data dimensionality when achieving the best classification accuracy rates.Table 2
The average classification accuracy rates (%) and standard deviations (%) of different approaches on the Yale database.
Methodl=4l=5l=6KNN+LPP74.86±2.70 (56)77.56±2.39 (72)79.07±3.27 (80)LLE+LPP77.71±4.22 (56)79.78±1.55 (56)80.13±3.23 (80)L1+LPP81.52±2.30 (44)84.79±2.19 (64)85.07±3.31 (80)LRR+LPP79.43±2.70 (56)82.33±2.59 (72)82.93±4.06 (76)LSR+LPP84.29±4.07 (56)86.00±2.58 (72)86.40±5.02 (80)LCLSR+LPP82.57±3.84 (52)85.56±2.92 (72)85.73±4.71 (80)SGLS+LPP83.33±4.15 (56)85.33±3.18 (72)85.20±3.74 (76)RGSL+LPP84.95±4.12 (56)86.89±1.72 (64)86.53±4.14 (64)Table 3
The average classification accuracy rates (%) and standard deviations (%) of different approaches on the AR database.
Methodl=4l=5l=6KNN+LPP60.76±1.92 (320)61.40±1.99 (400)60.11±1.41 (400)LLE+LPP66.79±2.28 (320)67.56±2.15 (380)66.39±3.17 (400)L1+LPP74.12±1.90 (280)74.96±1.47 (360)72.46±2.64 (400)LRR+LPP77.66±1.16 (380)78.93±0.95 (400)82.56±1.53 (400)LSR+LPP79.39±1.80 (320)80.14±0.83 (400)83.66±1.43 (400)LCLSR+LPP80.23±1.54 (380)81.76±1.01 (400)85.36±1.06 (400)SGLS+LPP79.43±2.06 (380)84.18±0.97 (400)85.35±1.01 (400)RGSL+LPP83.28±1.25 (380)85.20±1.06 (400)90.54±1.23 (380)Table 4
The average classification accuracy rates (%) and standard deviations (%) of different approaches on the CMU PIE database.
Methodl=6l=8l=10KNN+LPP85.37±0.81 (400)86.56±0.70 (400)86.63±0.99 (400)LLE+LPP87.55±0.92 (400)88.05±0.91 (400)87.95±0.80 (400)L1+LPP88.95±0.86 (380)88.97±0.73 (400)88.09±1.13 (380)LRR+LPP90.08±0.37 (380)90.18±0.87 (400)90.11±0.99 (400)LSR+LPP89.90±0.55 (400)90.26±0.81 (400)90.21±0.89 (320)LCLSR+LPP90.32±0.44 (400)90.68±0.73 (400)90.68±0.83 (400)SGLS+LPP89.72±0.68 (400)90.08±0.57 (280)90.09±0.93 (380)RGSL+LPP90.46±0.81 (340)92.72±0.63 (380)93.60±0.48 (400)Table 5
The average classification accuracy rates (%) and standard deviations (%) of different approaches on the Extended YaleB database.
Methodl=10l=15l=20KNN+LPP65.38±2.33 (360)69.62±1.12 (400)64.49±1.54 (400)LLE+LPP73.93±1.71 (360)75.00±1.18 (400)72.05±1.17 (400)L1+LPP75.77±4.10 (280)75.97±1.84 (340)67.70±1.69 (380)LRR+LPP82.67±1.02 (360)85.97±0.71 (400)84.53±1.19 (380)LSR+LPP84.20±0.66 (360)86.19±0.84 (360)85.14±0.71 (400)LCLSR+LPP85.59±0.75 (360)88.06±0.75 (400)87.62±0.62 (380)SGLS+LPP84.83±0.73 (360)86.64±0.73 (380)87.09±0.94 (340)RGSL+LPP86.14±0.65 (360)90.99±0.48 (400)92.68±0.54 (400)From the results depicted in Tables2–5, we can clearly observe that most of the graph learning approaches perform better than the KNN graph and LLE graph. It indicates that graph learning based on Euclidean distance is very sensitive to noise points, weakening the classification performance. Besides, compared to L1 graph learning approach, LRR graph, LSR graph, SGLS graph, and LCLSR graph take the locality structure of data into consideration during the process of graph construction to get more excellent performance. At last, the proposed RGSL approach performs best among all of the compared approaches. The main reasons are as follows: first, both the global structure and local structure are essential to the graph learning. Second, l2,1-norm regularization criterion and nonnegative constraint are introduced into graph construction process to improve the robustness of our approach against noise. Therefore, our approach can improve the classification performance further.There are two parameters, i.e.,α and β in the objective function of our proposed approach. Hence, how to appropriately set their values is very important for our approach. In this study, we tune the values of parameters α and β by searching the grid 0.001,0.01,0.1,1,10,100 in an alternate manner. The best results of different parameter values on the four databases are shown in Figure 3.Figure 3
The classification accuracy rates of the proposed RGSL approach with different values of parametersα and β on the four different databases.
(a)
Yale(b)
AR(c)
CMU PIE(d)
Extended YaleBAs we can see from Figure3, when the values of parameters α and β are relatively small, the performance of the proposed approach is relatively small. With the increase of parameters α and β, the performance of the proposed approach will be improved. However, after it achieves its best classification result, the performance of the proposed approach dramatically decreases with the increase of the two parameters. Therefore, the proposed approach can obtain its best classification results when the values of parameters α and β are set as neither too large nor too small. At last, the convergence curves of our RGSL on the four databases are shown in Figure 4. In this figure, the x-axis and the y-axis are, respectively, denoted as the iteration number and the value of the objective function. As seen from Figure 4, the value of the objective function declines at each iteration and converges very fast on all of the databases.Figure 4
The convergence curves of RGSL on the four databases: (a) Yale, (b) AR, (c) CMU PIE, and (d) Extended YaleB.
(a)
Yale(b)
AR(c)
CMU PIE(d)
Extended YaleB


### 4.4. Clustering Experiment and Analysis

In spectral clustering, the initialization has a major impact on the performance of theK-means clustering algorithm. Therefore, we carry out the process of clustering 50 times with different random initializations. Then, the average clustering results with standard deviations are used as the final results. In the experiments, three widely employed clustering evaluation indicators including Accuracy (ACC), Normalized Mutual Information (NMI), and Purity are used to evaluate the performance of the proposed approach.For a given samplexi, supposing that the obtained clustering result is pi and true label is ti, the clustering accuracy is calculated as
(19)ACC=∑i=1Nδti,mpiN,where δx,y=1 if x=y, δx,y=0 otherwise. The function m· maps the clustering result to the corresponding ground truth label. N is the number of samples. The Kuhn-Munkres algorithm [37] is employed to find the best mapping result.Assuming thatP and T are, respectively, the clustering result and the true label set obtained by different approaches, the Mutual Information (MI) is defined as
(20)MIP,T=∑pi∈Q,ti∈TQpi,ti⋅log2Qpi,tiQpi⋅Qti,where Qpi and Qti represent the probabilities that a sample is randomly selected from the dataset belonging to pi and ti, respectively. Qpi,ti represents the joint probability of a sample randomly being selected from the dataset belonging to pi and ti.LetHP and HT be the entropies of P and T, respectively. The Normalized Mutual Information (NMI) is calculated as
(21)NMI=MIP,TmaxHP,HT.Purity is defined as follows:(22)Purity=1k∑i=1kCidCi,where k represents the number of clusters, Cid is the number of elements in the most numerous category in cluster Ci, and Ci is the number of elements in cluster Ci.Tables6–9 show the best values of ACC, NMI, and Purity of eight approaches, respectively, on the Yale, AR, CMU PIE, and Extended YaleB databases. According to the results as shown in Tables 6–9, the following conclusions can be obtained. First, since KNN graph and LLE graph are based on Euclidean distance, they are very sensitive to the noise points, outliers, and parameter values. So the clustering performance based on KNN graph and LLE graph is lower than that based on other compared approaches. Second, the performance of LRR graph, LSR graph, SGLS graph, and LCLSR graph is superior to that of L1 graph because of taking the locality structure of data into consideration during the process of graph construction. However, these objective functions are all based on l2-norm, so it is very sensitive to the noise data. Besides, the relationship between the representation coefficients is ignored in the sample reconstruction, i.e., similar original samples should generate similar coding vectors, weakening the effectiveness of graph learning. To overcome these disadvantages, our RGSL approach combines l2,1-norm with manifold constraints on the coding coefficients to learn a locality and smoothness representation. Therefore, the performance of the proposed approach is superior to that of all of the comparison approaches.Table 6
The clustering results obtained by different approaches on the Yale database.
MethodACCNMIPurityKNN0.6887±0.01730.7098±0.00690.6753±0.0155LLE0.7028±0.00320.7147±0.00480.7085±0.0028L10.6998±0.01910.7396±0.01450.7145±0.0160LRR0.7320±0.01190.7580±0.01020.7358±0.0111LSR0.7509±0.01230.7790±0.00920.7520±0.0122LCLSR0.7782±0.02200.7848±0.01830.7865±0.0202SGLS0.7353±0.02840.7811±0.02010.7550±0.0219RGSL0.8532±0.02430.8665±0.03210.8563±0.0304Table 7
The clustering results obtained by different approaches on the AR database.
MethodACCNMIPurityKNN0.3907±0.00600.6556±0.00320.4023±0.0062LLE0.3908±0.00720.6645±0.00430.4090±0.0064L10.6451±0.01230.8057±0.00680.6816±0.0096LRR0.6763±0.01210.8182±0.00820.7130±0.0096LSR0.7236±0.01650.8703±0.00780.7547±0.0144LCLSR0.8108±0.01470.9050±0.00520.8326±0.0103SGLS0.8130±0.01510.9186±0.00560.8361±0.0121RGSL0.8301±0.01240.9243±0.00360.8485±0.0132Table 8
The clustering results obtained by different approaches on the CMU PIE database.
MethodACCNMIPurityKNN0.4825±0.01180.7186±0.00590.5244±0.0082LLE0.5884±0.01240.7520±0.00490.6108±0.0090L10.6284±0.01680.7484±0.00910.6644±0.0130LRR0.7805±0.01930.8694±0.00650.7992±0.0151LSR0.8077±0.01460.8774±0.00490.8165±0.0096LCLSR0.8159±0.01140.8733±0.00590.8262±0.0084SGLS0.8276±0.01470.8717±0.00690.8380±0.0109RGSL0.8399±0.00950.8886±0.00700.8490±0.0081Table 9
The clustering results obtained by different approaches on the Extended YaleB database.
MethodACCNMIPurityKNN0.4195±0.00740.5191±0.00690.4311±0.0061LLE0.4611±0.00900.5460±0.00700.4757±0.0070L10.4793±0.01680.5981±0.00870.5082±0.0123LRR0.7146±0.01470.7603±0.00850.7181±0.0139LSR0.7043±0.01810.7496±0.01020.7086±0.0174LCLSR0.7157±0.02260.7656±0.01400.7186±0.0219SGLS0.7220±0.02350.7768±0.01220.7256±0.0226RGSL0.7402±0.02760.7897±0.01630.7487±0.0194Similar to the subspace learning experiment, we also tune the values of parametersα and β by searing the grid 0.001,0.01,0.1,1,10,100 in an alternate manner. From the objective function, we can learn that there are three terms. When the values of parameters α and β are set as small, the effectiveness of the second and third terms in the objective function will be weakened, and the role of the first term will be overemphasized. On the contrary, the second and third terms in the objective function will play a major role, reducing the effect of the first term. Therefore, the proposed RGSL approach can achieve the best performance when parameters α and β are set as moderate values, which is similar to the discussions of subspace learning.


## 4.1. Databases

Four commonly used multimedia databases from the Internet including Yale [38], AR [39], CMU PIE [40], and Extended YaleB [41] are used for verifying the effectiveness of the proposed approach. The detailed statistical information about the four different databases is depicted in Table 1.Table 1
Description of databases.
DatabasesImage sizeInstancesClassesInstances of per classYale32×321651511AR32×32140010014CMU PIE32×3216326824Extended YaleB32×3224323864Yale database: it contains 165 face images captured from 15 different subjects. Each subject has 11 different images with the varied facial expressions, under different illumination conditions, and wearing glasses or not. Some example images of the Yale database are depicted in Figure 2(a).Figure 2
Some of the images from the different databases employed in our experiments.
(a)
Yale(b)
AR(c)
CMU PIE(d)
Extended YaleBAR database: it consists of over 4000 facial images obtained from 70 male and 56 female faces. Images of each person were captured with 26 frontal face images with anger, smiling, and screaming, under varied illumination conditions, and with sunglass and scarf occlusions. Some examples of the AR database are shown in Figure 2(b).CMU PIE database: there are 41,368 face images of 68 different subjects. Images of each person are captured under 43 different illumination conditions with 13 different poses and 4 different expressions. Here, we employ a subset of CMU PIE which consists of 24 images per subject. A part of example images is illustrated in Figure 2(c).Extended YaleB database: there are 38 individuals and each individual has 64 images. For each individual, the face images are taken from different illumination conditions with small changes in head pose and facial expression. Example images from this database are shown in Figure 2(d).Although we can obtain the graph structure from the proposed approach, it is intractable to assess the graph learning approaches using the estimated graph alone. Hence, we will assess the quality of the learned graph by two kinds of multimedia data analysis tasks including subspace learning and spectral clustering. In our experiments, we first vary the graph construction approaches by fixing the graph learning task and then observe the obtained performance associated with subspace learning and spectral clustering tasks.


## 4.2. Comparison among Several Graph Learning Approaches

To investigate the performance of our approach on subspace learning and clustering, several state-of-the-art graph learning approaches are chosen to compare in our work, which are shown as below:(i)
KNN graph [8]: the graph edges connected by two vertexes can be generated by the Euclidean distance-based K-nearest neighbor and the heat kernel function is used to measure the weight of an edge(ii)
LLE graph [28]: each sample is linearly reconstructed by its neighbors within a local area to preserve the local manifold structure(iii)
L1 graph [11]: the locality structure of data by using L1 sparse representation optimization(iv)
LRR graph [14]: based on self-expressive property, a low-rank graph is obtained(v)
LSR graph [15]: self-expressive property and Frobenius norm are used for fast computing the weight matrix(vi)
LCLSR graph [33]: it combines the locality constraint and LSR together to explore both the global structure of data points and the locality linear relationship of data points(vii)
SGLS graph [42]: it integrates manifold constraints on the unknown sparse codes as a graph regularizer(viii)
Our proposed RGSL graph: our approach takes the global and local structure information into consideration and also introduces thel2,1-norm regularization criterion and nonnegative constraint into graph construction process to enhance its robustness


## 4.3. Subspace Learning Experiment and Analysis

In this section, we employ an unsupervised subspace learning approach represented by Locality Preserving Projections (LPP) to verify the effectiveness of the proposed approach. In our experiments, different graphs are employed asW in LPP approach for subspace learning and then the classification accuracy is used for performance comparison. For each database, we randomly select l images from each class as the training samples. The remaining images are treated as the test samples. The values of l for Yale, AR, CMU PIE, and Extended YaleB databases are set as 4,5,6, 4,5,6, 6,8,10, and 10,15,20, respectively. In order to more effectively and fairly test the performance of the proposed approach, the random sample selection is repeated 20 times and the average classification accuracy and standard deviation are regarded as the final results for comparison. In this work, we employ the nearest neighbor classifier with Euclidean distance for classification due to its simplicity. To compare the performances of different approaches, the classification accuracy rate is chosen as the evaluation criterion, which is defined as
(18)Class_accuracy=Nt_correctNtotal×100%,where Nt_correct is the number of test samples which are correctly classified using the nearest neighbor classifier. Ntotal is the total number of the test samples.All the experiments are conducted using MATLAB 2016b on a 3.60 Hz with 8 G RAM. In order to acquire the optimal parameters of different approaches, we employ the grid-search manner in our experiments. Tables2–5 depict the average classification accuracy rates and standard deviations of the proposed approach on the Yale, AR, CMU PIE, and Extended YaleB databases, respectively. Note that the brackets in Tables 2–5 mean the data dimensionality when achieving the best classification accuracy rates.Table 2
The average classification accuracy rates (%) and standard deviations (%) of different approaches on the Yale database.
Methodl=4l=5l=6KNN+LPP74.86±2.70 (56)77.56±2.39 (72)79.07±3.27 (80)LLE+LPP77.71±4.22 (56)79.78±1.55 (56)80.13±3.23 (80)L1+LPP81.52±2.30 (44)84.79±2.19 (64)85.07±3.31 (80)LRR+LPP79.43±2.70 (56)82.33±2.59 (72)82.93±4.06 (76)LSR+LPP84.29±4.07 (56)86.00±2.58 (72)86.40±5.02 (80)LCLSR+LPP82.57±3.84 (52)85.56±2.92 (72)85.73±4.71 (80)SGLS+LPP83.33±4.15 (56)85.33±3.18 (72)85.20±3.74 (76)RGSL+LPP84.95±4.12 (56)86.89±1.72 (64)86.53±4.14 (64)Table 3
The average classification accuracy rates (%) and standard deviations (%) of different approaches on the AR database.
Methodl=4l=5l=6KNN+LPP60.76±1.92 (320)61.40±1.99 (400)60.11±1.41 (400)LLE+LPP66.79±2.28 (320)67.56±2.15 (380)66.39±3.17 (400)L1+LPP74.12±1.90 (280)74.96±1.47 (360)72.46±2.64 (400)LRR+LPP77.66±1.16 (380)78.93±0.95 (400)82.56±1.53 (400)LSR+LPP79.39±1.80 (320)80.14±0.83 (400)83.66±1.43 (400)LCLSR+LPP80.23±1.54 (380)81.76±1.01 (400)85.36±1.06 (400)SGLS+LPP79.43±2.06 (380)84.18±0.97 (400)85.35±1.01 (400)RGSL+LPP83.28±1.25 (380)85.20±1.06 (400)90.54±1.23 (380)Table 4
The average classification accuracy rates (%) and standard deviations (%) of different approaches on the CMU PIE database.
Methodl=6l=8l=10KNN+LPP85.37±0.81 (400)86.56±0.70 (400)86.63±0.99 (400)LLE+LPP87.55±0.92 (400)88.05±0.91 (400)87.95±0.80 (400)L1+LPP88.95±0.86 (380)88.97±0.73 (400)88.09±1.13 (380)LRR+LPP90.08±0.37 (380)90.18±0.87 (400)90.11±0.99 (400)LSR+LPP89.90±0.55 (400)90.26±0.81 (400)90.21±0.89 (320)LCLSR+LPP90.32±0.44 (400)90.68±0.73 (400)90.68±0.83 (400)SGLS+LPP89.72±0.68 (400)90.08±0.57 (280)90.09±0.93 (380)RGSL+LPP90.46±0.81 (340)92.72±0.63 (380)93.60±0.48 (400)Table 5
The average classification accuracy rates (%) and standard deviations (%) of different approaches on the Extended YaleB database.
Methodl=10l=15l=20KNN+LPP65.38±2.33 (360)69.62±1.12 (400)64.49±1.54 (400)LLE+LPP73.93±1.71 (360)75.00±1.18 (400)72.05±1.17 (400)L1+LPP75.77±4.10 (280)75.97±1.84 (340)67.70±1.69 (380)LRR+LPP82.67±1.02 (360)85.97±0.71 (400)84.53±1.19 (380)LSR+LPP84.20±0.66 (360)86.19±0.84 (360)85.14±0.71 (400)LCLSR+LPP85.59±0.75 (360)88.06±0.75 (400)87.62±0.62 (380)SGLS+LPP84.83±0.73 (360)86.64±0.73 (380)87.09±0.94 (340)RGSL+LPP86.14±0.65 (360)90.99±0.48 (400)92.68±0.54 (400)From the results depicted in Tables2–5, we can clearly observe that most of the graph learning approaches perform better than the KNN graph and LLE graph. It indicates that graph learning based on Euclidean distance is very sensitive to noise points, weakening the classification performance. Besides, compared to L1 graph learning approach, LRR graph, LSR graph, SGLS graph, and LCLSR graph take the locality structure of data into consideration during the process of graph construction to get more excellent performance. At last, the proposed RGSL approach performs best among all of the compared approaches. The main reasons are as follows: first, both the global structure and local structure are essential to the graph learning. Second, l2,1-norm regularization criterion and nonnegative constraint are introduced into graph construction process to improve the robustness of our approach against noise. Therefore, our approach can improve the classification performance further.There are two parameters, i.e.,α and β in the objective function of our proposed approach. Hence, how to appropriately set their values is very important for our approach. In this study, we tune the values of parameters α and β by searching the grid 0.001,0.01,0.1,1,10,100 in an alternate manner. The best results of different parameter values on the four databases are shown in Figure 3.Figure 3
The classification accuracy rates of the proposed RGSL approach with different values of parametersα and β on the four different databases.
(a)
Yale(b)
AR(c)
CMU PIE(d)
Extended YaleBAs we can see from Figure3, when the values of parameters α and β are relatively small, the performance of the proposed approach is relatively small. With the increase of parameters α and β, the performance of the proposed approach will be improved. However, after it achieves its best classification result, the performance of the proposed approach dramatically decreases with the increase of the two parameters. Therefore, the proposed approach can obtain its best classification results when the values of parameters α and β are set as neither too large nor too small. At last, the convergence curves of our RGSL on the four databases are shown in Figure 4. In this figure, the x-axis and the y-axis are, respectively, denoted as the iteration number and the value of the objective function. As seen from Figure 4, the value of the objective function declines at each iteration and converges very fast on all of the databases.Figure 4
The convergence curves of RGSL on the four databases: (a) Yale, (b) AR, (c) CMU PIE, and (d) Extended YaleB.
(a)
Yale(b)
AR(c)
CMU PIE(d)
Extended YaleB


## 4.4. Clustering Experiment and Analysis

In spectral clustering, the initialization has a major impact on the performance of theK-means clustering algorithm. Therefore, we carry out the process of clustering 50 times with different random initializations. Then, the average clustering results with standard deviations are used as the final results. In the experiments, three widely employed clustering evaluation indicators including Accuracy (ACC), Normalized Mutual Information (NMI), and Purity are used to evaluate the performance of the proposed approach.For a given samplexi, supposing that the obtained clustering result is pi and true label is ti, the clustering accuracy is calculated as
(19)ACC=∑i=1Nδti,mpiN,where δx,y=1 if x=y, δx,y=0 otherwise. The function m· maps the clustering result to the corresponding ground truth label. N is the number of samples. The Kuhn-Munkres algorithm [37] is employed to find the best mapping result.Assuming thatP and T are, respectively, the clustering result and the true label set obtained by different approaches, the Mutual Information (MI) is defined as
(20)MIP,T=∑pi∈Q,ti∈TQpi,ti⋅log2Qpi,tiQpi⋅Qti,where Qpi and Qti represent the probabilities that a sample is randomly selected from the dataset belonging to pi and ti, respectively. Qpi,ti represents the joint probability of a sample randomly being selected from the dataset belonging to pi and ti.LetHP and HT be the entropies of P and T, respectively. The Normalized Mutual Information (NMI) is calculated as
(21)NMI=MIP,TmaxHP,HT.Purity is defined as follows:(22)Purity=1k∑i=1kCidCi,where k represents the number of clusters, Cid is the number of elements in the most numerous category in cluster Ci, and Ci is the number of elements in cluster Ci.Tables6–9 show the best values of ACC, NMI, and Purity of eight approaches, respectively, on the Yale, AR, CMU PIE, and Extended YaleB databases. According to the results as shown in Tables 6–9, the following conclusions can be obtained. First, since KNN graph and LLE graph are based on Euclidean distance, they are very sensitive to the noise points, outliers, and parameter values. So the clustering performance based on KNN graph and LLE graph is lower than that based on other compared approaches. Second, the performance of LRR graph, LSR graph, SGLS graph, and LCLSR graph is superior to that of L1 graph because of taking the locality structure of data into consideration during the process of graph construction. However, these objective functions are all based on l2-norm, so it is very sensitive to the noise data. Besides, the relationship between the representation coefficients is ignored in the sample reconstruction, i.e., similar original samples should generate similar coding vectors, weakening the effectiveness of graph learning. To overcome these disadvantages, our RGSL approach combines l2,1-norm with manifold constraints on the coding coefficients to learn a locality and smoothness representation. Therefore, the performance of the proposed approach is superior to that of all of the comparison approaches.Table 6
The clustering results obtained by different approaches on the Yale database.
MethodACCNMIPurityKNN0.6887±0.01730.7098±0.00690.6753±0.0155LLE0.7028±0.00320.7147±0.00480.7085±0.0028L10.6998±0.01910.7396±0.01450.7145±0.0160LRR0.7320±0.01190.7580±0.01020.7358±0.0111LSR0.7509±0.01230.7790±0.00920.7520±0.0122LCLSR0.7782±0.02200.7848±0.01830.7865±0.0202SGLS0.7353±0.02840.7811±0.02010.7550±0.0219RGSL0.8532±0.02430.8665±0.03210.8563±0.0304Table 7
The clustering results obtained by different approaches on the AR database.
MethodACCNMIPurityKNN0.3907±0.00600.6556±0.00320.4023±0.0062LLE0.3908±0.00720.6645±0.00430.4090±0.0064L10.6451±0.01230.8057±0.00680.6816±0.0096LRR0.6763±0.01210.8182±0.00820.7130±0.0096LSR0.7236±0.01650.8703±0.00780.7547±0.0144LCLSR0.8108±0.01470.9050±0.00520.8326±0.0103SGLS0.8130±0.01510.9186±0.00560.8361±0.0121RGSL0.8301±0.01240.9243±0.00360.8485±0.0132Table 8
The clustering results obtained by different approaches on the CMU PIE database.
MethodACCNMIPurityKNN0.4825±0.01180.7186±0.00590.5244±0.0082LLE0.5884±0.01240.7520±0.00490.6108±0.0090L10.6284±0.01680.7484±0.00910.6644±0.0130LRR0.7805±0.01930.8694±0.00650.7992±0.0151LSR0.8077±0.01460.8774±0.00490.8165±0.0096LCLSR0.8159±0.01140.8733±0.00590.8262±0.0084SGLS0.8276±0.01470.8717±0.00690.8380±0.0109RGSL0.8399±0.00950.8886±0.00700.8490±0.0081Table 9
The clustering results obtained by different approaches on the Extended YaleB database.
MethodACCNMIPurityKNN0.4195±0.00740.5191±0.00690.4311±0.0061LLE0.4611±0.00900.5460±0.00700.4757±0.0070L10.4793±0.01680.5981±0.00870.5082±0.0123LRR0.7146±0.01470.7603±0.00850.7181±0.0139LSR0.7043±0.01810.7496±0.01020.7086±0.0174LCLSR0.7157±0.02260.7656±0.01400.7186±0.0219SGLS0.7220±0.02350.7768±0.01220.7256±0.0226RGSL0.7402±0.02760.7897±0.01630.7487±0.0194Similar to the subspace learning experiment, we also tune the values of parametersα and β by searing the grid 0.001,0.01,0.1,1,10,100 in an alternate manner. From the objective function, we can learn that there are three terms. When the values of parameters α and β are set as small, the effectiveness of the second and third terms in the objective function will be weakened, and the role of the first term will be overemphasized. On the contrary, the second and third terms in the objective function will play a major role, reducing the effect of the first term. Therefore, the proposed RGSL approach can achieve the best performance when parameters α and β are set as moderate values, which is similar to the discussions of subspace learning.


## 5. Conclusions

This paper proposes a novel graph learning framework, named Robust Graph Structure Learning (RGSL) for effective multimedia data analysis. In order to preserve both local and global structures of data, we employ the data self-representativeness to capture the global structure and adaptive neighbor approach to describe the local structure. Furthermore, we also introduce thel2,1-norm regularization criterion and nonnegative constraint into graph learning to improve the robustness of the model against noise. Extensive experimental results associated with subspace learning and clustering tasks show that the proposed approach performs better performance than the state-of-the-art graph learning approaches. Since our proposed approach will be affected by the graph construction when the dimensionality of data is high, in the future, we will take the dimensionality reduction, subspace learning, and graph learning into a united framework to address this issue.



---

*Source: 9458188-2021-06-25.xml*