{'fraction_non_alphanumeric': 0.037307217323874896, 'fraction_numerical': 0.014187656164737644, 'mean_word_length': 4.802366272287952, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Graph Autoencoder-Based Unsupervised Feature Selection with Broad and Local Data Structure Preservation

Feature selection is a dimensionality reduction technique that selects a subset of representative features from high-dimensional data by eliminating irrelevant and redundant features. Recently, feature selection combined with sparse learning has attracted significant attention due to its outstanding performance compared with traditional feature selection methods that ignores correlation between features. These works first map data onto a low-dimensional subspace and then select features by posing a sparsity constraint on the transformation matrix. However, they are restricted by design to linear data transformation, a potential drawback given that the underlying correlation structures of data are often non-linear. To leverage a more sophisticated embedding, we propose an autoencoder-based unsupervised feature selection approach that leverages a single-layer autoencoder for a joint framework of feature selection and manifold learning. More specifically, we enforce column sparsity on the weight matrix connecting the input layer and the hidden layer, as in previous work. Additionally, we include spectral graph analysis on the projected data into the learning process to achieve local data geometry preservation from the original data space to the low-dimensional feature space. Extensive experiments are conducted on image, audio, text, and biological data. The promising experimental results validate the superiority of the proposed method.

tend to include significant redundancy in adjacent features, or even noise, which leads to large amounts of useless or even harmful information being processed, stored, and transmitted [2,3]. All these issues present challenges to many conventional data analysis problems. Moreover, several papers in the literature have shown that the intrinsic dimensionality of high-dimensional data is actually small [4][5][6]. Thus, dimensionality reduction is a popular preprocessing step for high-dimensional data analysis, which decreases time for data processing and also improves generalization of learned models.
Feature selection [7][8][9][10][11][12] is a set of frequently used dimensionality reduction approaches that aim at selecting a subset of features. Feature selection has the advantage of preserving the same feature space as that of raw data.
Feature selection methods can be categorized into groups based on different criteria summarized below; refer to [13] for a detailed survey on feature selection.
• Search Strategy. In terms of selection strategies, feature selection methods can be categorized into filter, wrapper, and embedded methods. Wrapper methods [33,34] are seldom used in practice since they rely on a repetition of feature subset searching and selected feature subset evaluation until some stopping criteria or some desired performance are reached, which requires an exponential search space and thus is computationally prohibitive when feature dimensionality is high. Filter feature selection methods, e.g. Laplacian score (LapScore) [14] and SPEC [15], assign a score (measuring task relevance, redundancy, etc.) to each feature and select those with the best scores. Though convenient to computation, these methods are often tailored specifically for a given task and may not provide an appropriate match to the specific application of interest.
Embedded methods combine feature selection and model learning and provide a compromise between the two earlier extremes, as they are more efficient than wrapper methods and more task-specific than filter methods. In this paper, we focus on embedded feature selection methods.
In recent years, feature selection algorithms aiming at selecting features that preserve intrinsic data structure (such as subspace or manifold structure) [16][17][18][19][20][21][22][23][24][25][26][27][28][29][30] have attracted significant attention due to their good performance and interpretability [13]. In these methods, data are linearly projected onto new spaces through a transformation matrix, with fitting errors being minimized along with some sparse regularization terms. Feature importance is usually scored using the norms of corresponding rows/columns in the transformation matrix. In some methods [20][21][22][23][24][25][28][29][30], the local data geometric structure, which is usually characterized by nearest neighbor graphs, is also preserved in the low-dimensional projection space. A more detailed discussion on this type of methods is in Section 2.1. One basic assumption of these methods is that the data to be processed lie in or near a completely linear low-dimensional manifold, which is then modeled as a linear subspace. 1 However, this is not always true in practice, in particular with more sophisticated data.
In the case when data lies on or close to more generalized or non-linear manifolds, many approaches for dimensionality reduction have been proposed that leverage the data local geometry using neighborhood graphs, such as ISOMAP [35], Laplacian eigenmaps [36], locally linear embedding [37], etc., but few developments have been reported in feature selection. In this paper, we propose a novel algorithm for graph and autoencoder-based feature selection (GAFS). The reason we choose an autoencoder for the underlying manifold learning is because of its broader goal of data reconstruction, which is a good match in spirit for an unsupervised feature selection framework: we expect to be able to infer the entire data vector from just a few of its dimensions. In this method, we integrate three objective functions into a single optimization framework: (i) we use a single-layer autoencoder to reconstruct the input data; (ii) we use an 2,1 -norm penalty on the columns of the weight matrix connecting the autoencoder's input layer and hidden layer to provide feature selection; (iii) we preserve the local geometric structure of the data through to the corresponding hidden layer activations. To the best of our knowledge, we are the first to combine unsupervised feature selection with an autoencoder design and the preservation of local data geometric structure. Extensive experiments are conducted on image data, audio data, text data, and biological data. Many experimental results are provided to demonstrate the outstanding performance achieved by the proposed method compared with other state-of-the-art unsupervised feature selection algorithms.
The key contributions of this paper are highlighted as follows.
• We propose a novel unsupervised feature selection framework which is based on an autoencoder and graph data regularization. By using this framework, the information of the underlying data subspace can be leveraged, which loosens the assumption of linear manifold in many relevant techniques.
• We present an efficient solver for the optimization problem underlying the proposed unsupervised feature selection scheme. Our approach relies on an iterative scheme based on the gradient descent of the proposed objective function.
• We provide multiple numerical experiments that showcase the advantages of the flexible models used in our feature selection approach with respect to the state-of-the-art approaches from the literature.
The rest of this paper is organized as follows. Section 2 overviews related work. The proposed framework and the corresponding optimization scheme are presented in Section 3. Experimental results and the corresponding analysis are provided in Section 4. Section 5 includes conclusion and future work.

Related Work
In this section, we provide a review of literature related to our proposed method and introduce the paper's notation standard. Datasets are denoted by X = [X (1) , X (2) , · · · , X (n) ] ∈ R d×n , where X (i) ∈ R d is the ith sample in X for i = 1, 2, · · · , n, and where d and n denote data dimensionality and number of data points in X, respectively. For a matrix X, X (q) denotes the q th column of the matrix, while X (p,q) denotes the entry of the matrix at the p th row and q th column.
The r,p -norm for a matrix W ∈ R a×b is denoted as Two common norm choices in optimization are the 2,1 -norm and the squared Frobenius norm (e.g., r = p = 2). Note that unlike most of the literature, our outer sum is performed over the r -norms of the matrix columns instead of its rows; this is done for notation convenience of our subsequent mathematical expressions.

Sparse Learning-Based Unsupervised Feature Selection
Many unsupervised feature selection methods based on subspace structure preservation have been proposed in the past decades. For cases missing class labels, unsupervised feature selection methods select features that are representative of the underlying subspace structure of the data [16]. The basic idea is to use a transformation matrix to project data to a new space and guide feature selection based on the sparsity of the transformation matrix [17]. To be more specific, the generic framework of these methods is based on the optimization where Y = [Y (1) , Y (2) , · · · , Y (n) ] ∈ R m×n (m < d) is an embedding matrix in which Y (i) ∈ R m for i = 1, 2, · · · , n denotes the representation of data point X (i) in the obtained low-dimensional subspace. L(·) denotes a loss function, and R(·) denotes a regularization function on the transformation matrix W ∈ R m×d . The methods differ in their choice of embedding Y and loss and regularizoation functions; some examples are presented below.
Multi-cluster feature selection (MCFS) [18] and minimum redundancy spectral feature selection (MRSF) [19] are two long-standing and well-known subspace learning-based unsupervised feature selection methods. In MCFS, the embedding Y ∈ R m×n of each data X is first learned based on spectral clustering. After that, all data points are regressed to the learned embedding through a transformation matrix W ∈ R m×d = [W (1) ; W (2) ; · · · ; W (m) ]. The loss function is set to the Frobenius norm of the linear transformation error and the regularization function is set to the 1,1 norm of the transformation matrix, which promotes sparsity. Thus, MCFS can be formulated mathematically as the set of separate optimization problems where W (q) ∈ R d and Y (q) ∈ R n are the qth rows of W and Y, respectively, for q = 1, 2, · · · , m. A score for each feature is measured by the maximum absolute value of the corresponding row of the transformation matrix: This score is then used in a filter-based feature selection scheme. MRSF is an extension of MCFS that changes the regularization function to an 2,1 -norm that enforce column sparsity on the transformation matrix. Ideally, the selected features should be representative enough to keep the loss value close to that obtained when using all features. In order to achieve feature selection, we expect that W holds a sparsity property with its columns, which means only a subset of the columns are nonzeros. We use the 2 -norm of a W column to measure the importance of the corresponding feature, leading to an 2,1 -norm regularization function. Furthermore, MRSF ranks the importance of each feature according to the 2 -norm of the corresponding column of the transformation matrix.
Both MCFS and MRSF are able to select features that best preserve the subspace structure of the data due to the application of spectral clustering to detect cluster structure. However, the performance of these two methods is often degraded by the separate nature of subspace learning and feature selection [29]. In order to address this problem, many approaches on joint subspace learning and feature selection have been proposed. For example, Gu et. al. [20] proposed a joint framework that combines subspace learning and feature selection. In this framework, data are linearly projected to a low-dimensional subspace with a transformation matrix, and the local data geometric structure captured by a nearest neighbor graph is preserved in data embeddings on low-dimensional subspace. In the meanwhile, an 2,1 −norm is performed on transformation matrix to guide feature selection simultaneously. That is, subspace learning and feature selection are not two separate steps but combined into a single framework. Studies like [21][22][23][24][25] made further modifications to [20]: besides combining subspace learning and feature selection into a single framework, these methods also exploit the discriminative information of the data for unsupervised feature selection. For example, in unsupervised discriminative feature selection (UDFS) [21], data instances are assumed to come from c classes. UDFS uses local data geometric structure, which is based on the k-nearest neighbor set of each data point, to incorporate local data discriminative information into a feature selection framework. Like MCFS and MRFS, UDFS also assumes the existence of a transformation matrix W ∈ R m×c that maps data to a low-dimensional space. The objective function of UDFS is where M is an elaborate matrix that contains local data discriminative information; see [21] for details. One drawback of these discriminative exploitation feature selection methods is that the feature selection performance relies on an accurate estimation of number of classes.
Instead of projecting data onto a low-dimensional subspace, some approaches consider combining unsupervised feature selection methods with self-representation. In these methods, each feature is assumed to be representable as a linear combination of all (other) features, i.e., X = WX + E, where W ∈ R d×d is a representation matrix and E ∈ R d×n denotes a reconstruction error. That is, the data are linearly projected into the same data space so that the relationships between features can be gleaned from the transformation matrix. This type of method can be regarded as a special case of subspace learning-based feature selection methods where the embedding subspace is equal to the original space. Zhu et. al. [26] proposed a regularized self-representation (RSR) model for unsupervised feature selection that sets both the loss function and the regularization function to 2,1 -norms on the representation error E (for robustness to outlier samples) and transformation matrix W (for feature selection), respectively. RSR can therefore be written as RSR has been extended to non-convex RSR [27], where the regularization function is instead set to an 2,p -norm for 0 < p < 1. Unsupervised graph self-representation sparse feature selection (GSR SFS) [28] further extends [27] by changing the loss function to a Frobenius norm, as well as by considering local data geometric structure preservation on embedding WX through spectral graph analysis. GSR SFS can be written in the following formulation where L is the graph Laplacian matrix, which will be elaborated in Section 3.1. Self-representation based dual-graph regularized feature selection clustering (DFSC) [29] considers the error of self-representation for both the columns and the rows of X (i.e., both for features and data samples). Moreover, spectral graph analysis on both domains is considered. Subspace clustering guided unsupervised feature selection (SCUFS) [30] combines both self-representation and subspace clustering with unsupervised feature selection. In addition, SCUFS also exploits discriminative information for feature selection.

Single-Layer Autoencoder
A single-layer autoencoder is an artificial neural network that aims to learn a function h(x; Θ) ≈ x with a single hidden layer, where x ∈ R d is the input data, h(·) is a nonlinear function, and Θ is a set of parameters. To be more specific, the workflow of an autoencoder contains two steps: • Encoding: mapping the input data x to a compressed data representation y ∈ R m : where W 1 ∈ R m×d is a weight matrix, b 1 ∈ R m is a bias vector, and σ(·) is an elementary nonlinear activation function. Commonly used activation functions include the sigmoid function, the hyperbolic tangent function, the rectified linear unit, etc.
• Decoding: mapping the compressed data representation y to a vector in the original data spaceX ∈ R d : where W 2 ∈ R d×m and b 2 ∈ R d are the corresponding weight matrix and bias vector, respectively.
The optimization problem brought by the autoencoder is to minimize the difference between the input data and the reconstructed/output data. To be more specific, given a set of data X = [X (1) , X (2) , · · · , X (n) ], the parameters W 1 , W 2 , b 1 , and b 2 are adapted to minimize the reconstruction error n i=1 X (i) −X (i) 2 2 , whereX (i) is the output of autoencoder to the input X (i) . The general approach to minimize the reconstruction error is by selecting the parameter values via the backpropagation algorithm. 2 The data reconstruction capability of the autoencoder makes it suitable to capture the essential information of the data while discarding information that is not useful or redundant. Therefore, it is natural to assume that the compressed representation in the hidden layer of a single-layer autoencoder can capture the manifold structure of the 2 For more details on the backpropagation algorithm, refer to the survey paper [38].
input data when such manifold structure exists and is approximated well by the underlying weighting and nonlinearity operations. There are many variations of autoencoders, e.g., sparse autoencoder, denoising autoencoder, variational autoencoder, contractive autoencoder, etc. In this paper we only consider the baseline (standard) autoencoder model, which will be elaborated in Section 3. We will explore the combination of unsupervised feature selection and other specific variations of autoencoder in future work.

Proposed Method
In this section, we introduce our proposed graph autoencoder-based unsupervised feature selection (GAFS). Our proposed framework performs broad data structure preservation through a single-layer autoencoder and also preserves local data geometric structure through spectral graph analysis. In contrast to existing methods that exploit discriminative information for unsupervised feature selection by imposing orthogonal constraints on the transformation matrix [21] or low-dimensional data representation [22,23], GAFS does not include such constraints. More specifically, we do not add orthogonal constraints on the transformation matrix because feature weight vectors are not necessarily orthogonal with each other in real-world applications [39], allowing GAFS to be applicable to a larger set of applications [17]. Furthermore, methods posing orthogonal constraints on low-dimensional data representations makes a good estimation of number of classes necessary to obtain reliable label indicators for those algorithms; such estimation is difficult to achieve in an unsupervised framework.

Objective Function
The objective function of GAFS includes three parts: a term based on a single-layer autoencoder promoting broad data structure preservation; a term based on spectral graph analysis promoting local data geometric structure preservation; and a regularization term promoting feature selection. As mentioned in Section 2.2, a single-layer autoencoder aims at minimizing the reconstruction error between output and input data by optimizing a reconstruction error-driven loss function: ; we use the sigmoid function as the activation function: σ(z) = 1/(1 + exp(−z)).
Since W 1 is a weight matrix applied directly on the input data, each column of W 1 can be used to measure the importance of the corresponding data feature. Therefore, R(Θ) = W 1 2,1 can be used as a regularization function to promote feature selection as detailed in Section 2.1. The objective function for the single-layer autoencoder based unsupervised feature selection can be obtained by combining this regularization function with the loss function of (10), providing us with the optimization where λ is a balance parameter.
Local geometric structures of the data often contain discriminative information of neighboring data point pairs [18].
They assume that nearby data points should have similar representations. It is often more efficient to combine both broad and local data information during low-dimensional subspace learning [40]. In order to characterize the local data geometric structure, we construct a k-nearest neighbor (kNN) graph G on the data space. The edge weight between two connected data points is determined by the similarity between those two points. In this paper, we choose cosine distance as similarity measurement for its simplicity. Therefore the adjacency matrix A for the graph G is defined as where N k (X (i) ) denotes the k-nearest neighborhood set for X (i) , and X (i) T refers to the transpose of X (i) . The Laplacian matrix L of the graph G is defined as L = D − A, where D is a diagonal matrix whose i th element on the diagonal is defined as D (i,i) = n j=1 A (i, j) .
In order to preserve the local data geometric structure in the learned subspace (i.e., if two data points X (i) and X ( j) are close in original data space then the corresponding low-dimensional representations Y (i) and Y ( j) are also close in the low-dimensional embedding space), we set up the following minimization objective: where Tr(·) denotes the trace operator, Y (i) (Θ) = σ(W 1 x (i) + b 1 ) for i = 1, 2, · · · , n (and we often drop the dependence on Θ for readability), and Y(Θ) = [Y (1) Therefore, by combining the single-layer autoencoder based feature selection objective (11) and the local data geometric structure preservation into consideration, the resulting objective function of GAFS can be written in terms of the following minimization with respect to the parameters Θ = [W 1 , = arg min where λ and γ are two balance parameters. Filter-based feature selection is then performed using the score function GAFS (q) = W (q) 1 2 based on the weight matrix W 1 fromΘ.

Optimization
The objective function of GAFS shown in (17) does not have a closed-form solution. In this work, we implement the L-BFGS algorithm [41] using the minFunc toolbox [42] to solve the GAFS optimization problem. The solver requires the gradients of the objective function in (17) with respect to its parameters Θ.
The gradients for the loss term L(Θ) can be obtained through a back-propagation algorithm. We defer the details for the derivation of the gradients of the error term, which are standard in the formulation of backpropagation for an autoencoder. The resulting gradients are as follows: Each column ∆ (i) 2 and ∆ (i) 3 of ∆ 2 ∈ R m×n and ∆ 3 ∈ R d×n , respectively, contains the error term of the corresponding data point for the hidden layer and the output layer, respectively, having entries as follows: for p = 1, 2, · · · , d, q = 1, 2, · · · , m, and i = 1, 2, · · · , n, and whereX denotes the reconstructed data output of the autoencoder. Equation (20) can also be rewritten in matrix form as where • denotes the element-wise product operator. In the sequel, we use 1 and 0 to denote an all-ones and all-zeros matrix or vector with of the appropriate size, respectively.
The regularization term R(Θ) = W 1 2,1 , whose derivative does not exist for its ith column W (i) 1 when W (i) 1 = 0 for i = 1, 2, · · · , d. In this case, where U ∈ R d×d is a diagonal matrix whose ith element on the diagonal is where is a small constant added to avoid overflow [29]. Since W 1 2,1 is not differentiable at 0, we calculate the subgradient for each element in W 1 in that case. That is, for each element in W 1 , the subgradient at 0 can be an arbitrary value in the interval [−1, 1], and so we set the gradient to 0 for computational convenience. In summary, the gradients for the regularization term is: The gradients of the graph term G(Θ) = γTr(YLY T ) can be obtained in a straightforward fashion as follows: Type  MNIST  784  60000  10  Image  COIL20  1024  1440  20  Image  Yale  1024  165  15  Image  PCMAC  3289  1943  2  Text  BASEHOCK 4862  1993  2  Text  RELATHE  4322  1427  2  Text  Prostate GE  5966  102  2  Biology  Isolet  617  1560 26 Audio Table 1: Details of datasets used in this paper.

Dataset Features Instances Classes
To conclude, the gradients of the GAFS objective function with respect to Θ = [W 1 , W 2 , b 1 , b 2 ] can be written as

Experiments
In this section, we evaluate the feature selection performance of GAFS in terms of both supervised and unsupervised tasks, e.g. clustering and classification, on several benchmark datasets. We also compare GAFS with other state-of-the-art unsupervised feature selection algorithms. To be more specific, we first select p representative features and then perform both clustering and classification on those selected features. The performance of clustering and classification is used as the metric to evaluate feature selection algorithms. We perform experiments on eight benchmark datasets, 3 including three image datasets (MNIST, COIL20, Yale), three text datasets (PCMAC, BASEHOCK, RELATHE), one audio dataset (Isolet), and one biological dataset (Prostate GE). Detailed properties of those datasets are summarized in Table 1.

Evaluation Metric
We perform both supervised (i.e., classification) and unsupervised (i.e., clustering) tasks on datasets formulated by the selected features in order to evaluate the effectiveness of feature selection algorithms. For classification, we employ softmax classifier for its simplicity and compute the classification accuracy as the evaluation metric for feature selection effectiveness. For clustering, we use k-means clustering on the selected features and use two different evaluation metrics to evaluate the clustering performance of all methods. The first is clustering accuracy (ACC), defined as where n is the total number of data samples, δ(·) is defined by δ(a, b) = 1 when a = b and 0 when a b, map(·) is the optimal mapping function between cluster labels and class labels obtained using the Hungarian algorithm [43], and c i and g i are the clustering and ground truth labels of a given data sample x i , respectively. The second is normalized mutual information (NMI), which is defined as where C and G are clustering labels and ground truth labels, respectively, MI(C, G) is the mutual information between C and G, and H(C) and H(G) denote the entropy of C and G, respectively. More details about NMI are available in [44]. For both ACC and NMI, 20 clustering processes are repeated with random initialization for each case following the setup of [18] and [21], and we report the corresponding mean values of ACC and NMI.

Experimental Setup
In our last experiment, we compare GAFS with LapScore 4 [14], SPEC 5 [15], MRSF 6 [19], UDFS 7 [21], and RSR 8 [26]. Among these methods, LapScore and SPEC are filter feature selection methods which are based on data similarity. LapScore uses spectral graph analysis to set a score for each feature. SPEC is an extension to LapScore and can be applied to both supervised and unsupervised scenarios in which schemes of constructing graphs used for data similarity measurement are different. Details on MRSF, UDFS, and RSR can be found in Section 2.1. Besides the five methods, we also compare GAFS with the performance of using all features as the baseline.
For each specific value of p on a certain dataset, we tune the parameters for each algorithm in order to achieve the best results among all possible combinations. For classification, we report the highest classification accuracy. For clustering, we report the highest average values for both ACC and NMI from 20 repetitions.

Parameter Sensitivity
We study the performance variation of GAFS with respect to the hidden layer size m and the two balance parameters λ and γ. We show the results on all the 8 datasets in terms of ACC.
We first study the parameter sensitivity of GAFS with respect to subspace dimensionality m. Besides the aforementioned manifold dimensionality range m ∈ {10, 20, 30, 40}, which are common for both proposed and comparing algorithms, we also conducted experiments with hidden layer size values of m ∈ {100, 200, 300, 400} to investigate the performance change for a larger range of reduced dimensionality values. The results in Fig. 1 show that the performance of GAFS is not too sensitive to hidden layer size on the given datasets, with the exception of Yale, where the performance with hidden layer size of m ∈ {10, 20, 30, 40} is apparently better than that with reduced dimensionality m ∈ {100, 200, 300, 400}, while the performance variations are small in the latter set. One possible reason behind this behavior is that for a human face image dataset like Yale, the differences between data instances can be subtle since they may only lie in a small area of relevance such as eyes, mouth, nose, etc. Therefore, in this case a small subspace dimensionality can be enough for information preservation, while a large subspace dimensionality may introduce redundant information that may harm feature selection performance.
We also study the performance of GAFS on balance parameters λ and γ, with fixed percentage of selected features and hidden layer size. We set p = 20%, as Fig. 1 shows that the performance stabilizes starting at that value of p.
For subspace dimensionality, we choose m = 10 since Fig. 1 shows that the performance of GAFS is not sensitive to the value of m. The performance results are shown in Fig. 2, where we find that different datasets present different trends on the ACC values with respect to λ and γ. However, we also find that the performance differences on PCMCA, BASEHOCK, and RELATHE are not greater than 0.8%, 0.8%, and 0.4%, respectively. Therefore we cannot make any conclusion on the influence from two balance parameters on ACC based on these 3 datasets. For the parameter λ, which controls the column sparsity of W 1 , we can find that for Yale the performance monotonically improves as the value of λ increases for each fixed value of γ, even though the number of selected features m is fixed. We believe this is further evidence that a small number of selected features receiving large score (corresponding to large λ) is sufficient to obtain good learning performance, while having a large number of highly scoring features (corresponding to small λ) may introduce irrelevant features to the selection. We also find a similar behavior for Prostate GE and Isolet. For both MNIST and COIL20, we can find that the overall performance is best when λ = 10 −2 and both smaller and larger values of λ degrade the performance. This is because the diversity among instances of these two datasets is large enough: a large value of λ may remove informative features, while a small value of λ prevents the exclusion of small, irrelevant, or redundant features. For the parameter γ, which controls local data geometric structure preservation, we can find that both large values and small values of γ degrade performance. On one hand, we can conclude that local data geometric structure preservation does help improve feature selection performance to a certain degree. On the other hand, large weights on local data geometric structure preservation may also harm feature selection performance.

Feature Selection Illustration
We randomly select five samples from the Yale dataset to illustrate the choices made by different feature selection algorithms. For each sample, p ∈ {10%, 20%, 30%, 40%, 50%, 60%, 70%, 80%, 100%} features are selected. Figure   3 shows images corresponding to the selected features (i.e., pixels) for each sample and value of p, with unselected pixels shown in white. The figure shows that GAFS is able to capture the most discriminative parts on human face such as eyes, nose, and mouse.

Clustering Illustration
We show a toy example of clustering from the low-dimensional data representation (i.e., the hidden layer features) when the hidden layer size is set to m = 2 in Fig. 4, with circles of different colors representing data embeddings corresponding to different digits for MNIST and different classes for COIL20; we focus on these two datasets due to space constraints. In this experiment, we empirically set the parameters {λ = 10 −2 , γ = 10 −3 } for MNIST and {λ = 10 −3 , γ = 5 × 10 −3 } for COIL20 for autoencoder training. In order to present a clear illustration, we show the clustering results of digits from 0 to 4 for MNIST instead of 0 to 9 and 5 randomly selected classes for COIL20 instead of all 20 classes, respectively. From Fig. 4 we can find that for COIL20 the 5 classes are well separated, while for MNIST the digits 0 and 1 are will separated from other digits.

Performance Comparison
We present the classification accuracy, ACC, and NMI results of GAFS and the comparison feature selection algorithms on all datasets in Fig. 5, Fig. 6, and Fig. 7, respectively. From these figures, we can find that GAFS performs better than other compared algorithms in most cases. Comparing the performance of GAFS with that of using all features, which is represented by a black dashed line in each figure, we can find that GAFS can always achieve better performance with far less features. In the meanwhile, with fewer features, the computational load in corresponding classification and clustering tasks can be decreased. These results demonstrate the effectiveness of GAFS in terms of removing irrelevant and redundant features in classification and clustering tasks.

Conclusion
In this paper, we proposed a graph and autoencoder-based unsupervised feature selection (GAFS) method. Unlike current relevant techniques that combines sparse learning and feature selection, the proposed method projects the data to a lower-dimensional space using a single-layer autoencoder, in contrast to the linear transformation used by most existing methods. With our proposed framework, we bypass the limitation of existing methods that the dimensionality reduction subspace must be a linear projection of the data space, which may lead to performance degradation for data sets with richer structure, which is predominant in modern datasets. Experimental results demonstrate the advantages of GAFS versus methods in the literature for both classification and clustering tasks.
The work we present here is our first attempt to leverage autoencoders for unsupervised feature selection purposes.
Therefore, we use the most standard setting for the construction of the autoencoder, e.g., there is no desired or particular structure to the activations or the reconstruction error. In the future, we plan to explore the effectiveness of more elaborate versions of an autoencoder for feature selection purposes. Furthermore, we will also extend our framework to more sophisticated machine learning problems such as transfer learning.