Differentiable Unsupervised Feature Selection based on a Gated Laplacian
Year: 2022

Abstract:
Scientific observations may consist of a large number of variables (features). Selecting a subset of meaningful features is often crucial for identifying patterns hidden in the ambient space. In this paper, we present a method for unsupervised feature selection, and we demonstrate its advantage in clustering, a common unsupervised task. We propose a differentiable loss that combines a graph Laplacian-based score that favors low-frequency features with a gating mechanism for removing nuisance features. Our method improves upon the naive graph Laplacian score by replacing it with a gated variant computed on a subset of low-frequency features. We identify this subset by learning the parameters of continuously relaxed Bernoulli variables, which gate the entire feature space. We mathematically motivate the proposed approach and demonstrate that it is crucial to compute the graph Laplacian on the gated inputs rather than on the full feature space in the high noise regime. Using several real-world examples, we demonstrate the efficacy and advantage of the proposed approach over leading baselines.

heading: 1 Introduction
text: Unsupervised and self-supervised learning studies have been significantly growing interest in the neural network research community. This was prompted by the impressive empirical results that unsupervised learning methods produce in analyzing large amounts of unlabeled data, such as in natural language processing. Many scientific domains, such as biology and physics, have seen the growth of computational and storage resources, alongside advancements in the simultaneous measurement of numerous features, making the analysis of large, high-dimensional datasets a vital research need.
∗Indicates equal contribution
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In such datasets, discarding irrelevant (e.g., noisy, high frequency, or information-poor) features may reveal clear underlying natural structures that are otherwise hidden in the high dimensional space. We refer to features which do not correspond to the “main” data structure as “nuisance features”2. While nuisance features are mildly harmful in the supervised regime, discarding such features is critical in the unsupervised regime and may determine the success of downstream analysis tasks (e.g., clustering or manifold learning). Some of the pitfalls caused by nuisance features could be mitigated using an appropriate unsupervised feature selection method.
Unsupervised feature selection methods mostly focus on one of two main tasks: either clustering or manifold learning. Among studies that tackle the former task, [33, 12, 1] use autoencoders to identify features that are sufficient for reconstructing the data. Other clustering-dedicated unsupervised feature selection methods assess the relevance of each feature based on different statistical or geometric measures. For example entropy, variance, divergence, and mutual information are used in [2, 31, 9, 3, 30, 35] to identify features that are informative for clustering the data. A popular tool for evaluating features is the graph Laplacian [26, 4]. The Laplacian Score (LS) [13] evaluates the importance of each feature by its ability to preserve the local structure. The features that most preserve the manifold structure (captured by the Laplacian) are retained. Several studies, such as [38, 27, 39], extend the LS based on different spectral properties of the Laplacian.
While these methods are widely used in the feature selection community, they rely on the success of the Laplacian in capturing the “main” structure of the data. We argue that the Laplacian often fails to identify the informative features when computed on the entire dataset (as is demonstrated in Section 3). This may happen in the presence of a large number of nuisance features: when the variability of the nuisance features masks the variability associated with the structured features. Scenarios resembling this are prevalent in bioinformatics for example, where a large number of biomarkers are measured to characterize developmental and chronological biology processes such as cell differentiation or cell cycle. These processes may depend merely on a few biomarkers. In such situations, it is desirable to have an unsupervised method that can filter nuisance features before the computation of the Laplacian. Related problems, in which data spanning low dimensional subspace is dressed by perturbations in a higher ambient space, were studied in [17, 5, 10, 28].
In this study, we propose a differentiable objective for unsupervised feature selection. Our proposed method utilizes stochastic input gates, trained to select features with high correlation with the leading eigenvectors of a graph Laplacian computed based on these features. This gating mechanism allows us to re-evaluate the Laplacian for different subsets of features and, thus, unmask the “main” data structure buried by the nuisance features. We demonstrate that the proposed approach can significantly improve cluster assignments compared with leading baselines using high-dimensional datasets from multiple domains (image, text, and biological observations).

heading: 2 Preliminaries
text: Consider a data matrix, X ∈ Rn×d, with d dimensional observations x1, ...,xn. We refer to the columns of X as features f1, ...,fd, where f i ∈ Rn, and, assume that features are centered and normalized such that 1Tf i = 0 and ‖f i‖22 = 1. We assume that the data has an inherent structure, determined by a subset of the variables S∗ and that other variables are nuisance features (i.e., noisy or information-poor). The structured part of the data is considered as either a path-connected manifold, a union of sub-manifolds, or a set of clusters. Our goal is to identify the subset of relevant features S∗ , which preserve the data structure and discard the remaining ones.

heading: 2.1 Graph Laplacian
text: Given n data points, a kernel matrixK is an n× n matrix whoseKi,j entry represents the similarity between xi and xj . A popular choice forK is the Gaussian kernel
Ki,j = exp
( −‖xi − xj‖ 2
2σ2b
) , (1)
2In section 3, we consider scenarios where low dimensional datasets that form manifold or cluster structures are augmented with information-poor nuisance features that are independent of the original structure and are, themselves, of no particular underlying structure.
where σb is a user-defined bandwidth (chosen, for example, based on the maximum value of the 1- nearest-neighbors of all points). The unnormalized graph Laplacian matrix is defined asLun =D−K, whereD is a diagonal matrix, whose elementsDi,i = ∑n j=1Ki,j correspond to the degrees of the points i = 1, ..., n. The diffusion graph Laplacian is defined as
Ldiff =D −1K, (2)
and expresses the transition probabilities of a random walk to move between data points and induces a diffusion distance [8]. Graph Laplacian matrices are extremely useful in many unsupervised machine learning tasks. In particular, it is known that the eigenvectors corresponding to the small eigenvalues of the unnormalized Laplacian (or the large eigenvalues of the random walk Laplacian) are useful for embedding the data in lower dimensions (see, for example, [32]).

heading: 2.2 Laplacian Score
text: Following the success of the graph Laplacian [4], and [26], the authors in [13] have presented an unsupervised measure for feature selection, termed Laplacian Score (LS). The LS evaluates each feature based on its correlation with the leading eigenvectors of the graph Laplacian.
At the core of the LS method, the score of feature f is determined by the quadratic form fTLunf , where Lun is the unnormalized graph Laplacian. Since
fTLunf = n∑ i=1 λi〈ui,f〉2,
where Lun = ∑n i=1 λiuiu T i is the eigen-decomposition of Lun, the score is smaller when f has a larger projection on the subspace of the leading eigenvectors (corresponding to the smallest eigenvalues) of Lun. Such features can be thought of as “informative”, as they respect the graph structure. Eigenvalues of the Laplacian can be interpreted as frequencies, and eigenvectors corresponding to larger eigenvalues of Lun (or smaller eigenvalues of Ldiff) oscillate faster. Based on the assumption that the interesting underlying structure of the data (e.g. clusters) depends on the slowly varying features in the data, [13] proposed to select the features with the smallest scores.

heading: 3 Demonstration of the Importance of Unsupervised Feature Selection in High Dimensional Data with Nuisance Features
text: By taking a diffusion perspective, we first demonstrate the importance of feature selection to unsupervised learning when the data contains nuisance features. Then, a simple two cluster structure hidden in the ambient space is used to analyze how Gaussian nuisance dimensions affect clustering capabilities. Here, we model the effect of nuisance variables by concatenating variables drawn from a normal Gaussian distribution with the structured part of the data. A concrete example is detailed in the following subsection.

heading: 3.1 A Diffusion Perspective
text: Consider the structured 2-dimensional dataset, known as two-moons, shown in the top-left panel of Fig. 1. We concatenate the structured data with k “nuisance” dimensions, where each such dimension is composed of i.i.d unif(0, 1) entries. This means that our new data consists of 2 + k variables. Note that the k Gaussian variables do not carry any information about the two “moon-shaped” clusters in this dataset. As one may expect, when the number of nuisance dimensions is large, the amount of unstructured information (manifested by the nuisance dimensions) dominates the amount of structured information (manifested by the two leading dimensions). Consequently, attempts to recover the main structure of the data (say, using manifold learning or clustering) are likely to fail.
From a diffusion perspective, data is considered to be clusterable when the time it takes a random walk starting in one cluster to transition to a point outside the cluster is long. These exit times from different clusters are manifested by the leading eigenvalues of the Laplacian matrix: Ldiff = D−1K, for which the large eigenvalues (and their corresponding eigenvectors) are the ones that capture different aspects of the data’s structure (see, for example, [24]). Each added nuisance dimension increases the distance between points which are nearest neighbors in the two dimensional structured subspace. In
addition, the noise creates spurious similarities between points, regardless of the cluster they belong to. Overall, this shortens the cluster exit times. This phenomenon is characterized by the second largest eigenvalue, λ2 of Ldiff (the largest eigenvalue λ1 = 1 carries no information as it corresponds to the constant eigenvector ψ1), which decreases as the number of nuisance dimensions grows, see the top right panel of Fig. 1. The fact that λ2 decreases implies that the diffusion distances [24] decrease as well which, in turn, means that the clusters become more connected. A similar view may be obtained by observing that the second smallest eigenvalue of the un-normalized graph Laplacian Lun =D −K, also known as Fiedler number or algebraic connectivity, grows with the number of nuisance features. The fact that the graph becomes less clusterable as more nuisance dimensions are added is also manifested by the eigenvector, ψ2, corresponding to the second largest eigenvalue of Ldiff (or the second smallest eigenvalue of Lun), which becomes less representative of the cluster structure (bottom left panel of Fig. 1).
Altogether, this means that, in order for the data to be clusterable, the nuisance features ought to be removed. One may argue that principal component analysis can be used to retain the structure of the two-moons while attenuating the effect of the k nuisance variables. However, as shown in the bottom right panel of Fig. 1, projecting the data onto the first two principal directions does not yield the desired result, since the directions of maximal variance do not capture the two-moons structure, unfortunately. In the next sections, we will describe our differentiable unsupervised feature selection approach, demonstrating that it does succeed to recognize the cluster patterns of the data in this case.

heading: 3.2 Analysis of Clustering with Nuisance Dimensions
text: In order to observe the effect of nuisance dimensions, this section considers a simple example with two clusters in 1-D space and a set of nuisnace variables which do not carry any information about these clusters. Specifically, consider a dataset that includes 2n datapoints in R, where n of which are at 0 ∈ R and the remaining ones are at r > 0 (i.e., each cluster is concentrated at a specific point). Next, we concatenate d nuisance dimensions to first coordinate, so samples lie in Rd+1. The value for each datapoint in each nuisance dimension is sampled independently from N(0, 0.52).
Suppose we construct the graph Laplacian by connecting each point to its nearest neighbors. We would now investigate the conditions under which the neighbors of each point belong to the correct cluster. Consider points x, y belonging to the same cluster. Then (x− y) = (0, u1, . . . , ud) -where ui
iid∼ N(0, 1), and, therefore, ‖x − y‖2 ∼ χ2d. Similarly, if x, y belong to different clusters, then ‖x− y‖2 ∼ r2 + χ2d, where r is the distance between clusters in the first coordinate. Now, to find conditions for n and d under which the neighbors of each point are highly likely to belong to the same cluster, we can utilize the χ2 measure-concentration bounds [18].
Lemma 3.1 ([18] P.1325). Let X ∼ χ2d. Then
1. P(X − d ≥ 2 √ dγ + 2γ) ≤ exp(−γ). 2. P(d−X ≥ 2 √ dγ) ≤ exp(−γ).
Given sufficiently small γ > 0 we can divide the segment [d, d + r2] to two disjoint segments of lengths 2 √ dγ + 2γ and 2 √ dγ (and solve for d in order to have the total length r2). This yields
√ d = r2 − 2γ 4 √ γ . (3)
If all distances between points from the same cluster are at most d+ 2 √ dγ + 2γ and all distances between points from different clusters will be at least d+ r2 − 2 √ dγ, the nearest neighbors of each point will be from the same cluster. According to lemma 3.1, this happens with a probability of at least (1− exp(−γ))2n2−n. For a small > 0, denoting this probability as 1− and solving for γ, we obtain
γ ≤ − log(1− (2n2−n) √ 1− ). (4)
Plugging (4) into (3), we obtain
d = O
( r4
− log(1− (2n2−n) √ 1− )
) . (5)
For fixed number of samples (n) and a small value of > 0, equation (5) implies that the number of nuisance dimensions must be at most on the order of r4 to make cluster mixture unlikely. In addition, for a fixed r and , increasing the number of data points brings the argument inside the log term arbitrarily close to zero, which implies that the Laplacian is sensitive to the number of nuisance dimensions in large datasets. We support these findings via experiments, as shown in Figure 2. This sensitivity to nuisance dimensions suggests that capturing the “main” structure of the data, requires filtering nuisance features prior to the construction of the Laplacian. In Section 4, we present our proposed approach, which simultaneously filters nuisance features and re-evaluates the smoothness of the remaining features.

heading: 4 Proposed Method

heading: 4.1 Rationale
text: Recall that the core component of the Laplacian score [13] is the quadratic term fTLf , which measures the inner product of the feature f with the eigenvectors of the Laplacian L. For L = Ldiff = D
−1K, a large Laplacian score implies that f has a large component in the subspace of eigenvectors corresponding to the largest eigenvalues of L. Assuming that the structure of the data varies slowly, these leading eigenvectors (corresponding to large eigenvalues) manifest the main structures in the data; thus, a large score implies that a feature contributes to the structure of the data. However, as we demonstrated in the previous section, these leading eigenvectors become less representative of the true structure in the presence of nuisance features. In this regime, one could benefit from evaluations of the Laplacian score when it is computed using different subsets, S, of features (i.e., of the form fTLXSf , where LXS is the random walk Laplacian computed based on a subset of features {f `}`∈S ). When the Laplacian is computed on only the informative features (i.e., when LXS = LXS∗ ), such a gated Laplacian score would produce a high value for the informative features, S∗.
analysis presented in 3.2 in which we show that d = O
(
r4
− log(1− (2n 2−1)√1− )
)
. For convenience we
added a polynomial fit up to degree 4 presented as the black line.
Searching over all the different feature subsets is infeasible even for a moderate number of features. Fortunately, we can use continuous stochastic “gating” functions to explore the space of feature subsets. Specifically, we propose to apply differential stochastic gates to the input features, computing the Laplacian score after multiplying the input features with the gates. Taking advantage of the fact that informative features are expected to have higher scores than nuisance ones, we penalize open gates to minimize the number of features and retain the most relevant (smooth) features. By applying gradient decent to a cost function based on LXS , we obtain a desired dynamic, in which gates corresponding to features that contain high levels of noise gradually close, and gates corresponding to features that are consistent with the true structures in the data gradually become fully open. This is demonstrated in Fig. 3.

heading: 4.2 Stochastic Gates
text: Recently, several authors have incorporated continuous approximations of discrete random variables into neural network training [22, 16]. Such relaxations have been used for many applications, such as
Algorithm 1 Differentiable Unsupervised Feature Selection (DUFS) Pseudo-code
Input: data, {x1, . . . ,xn} ⊂ Rd, regularization parameter λ, required number of features s, number of epochs T . Initialize the gate parameters: µi = 0.5 for i = 1, . . . , d. for t = 1 to T do
Sample a stochastic gate (STG) vector Z = (Z1, . . . , Zd) as described in (6). Apply the STG to the data xi to obtain the gated data x̃i ( x̃i = xi Z). Compute a kernel matrixK ∈ Rn×n (see (1)) using the gated data {x̃i}. Compute the graph Laplacian Ldiff ∈ Rn×n as described in (2). Update µ1, . . . , µd by applying GD to the loss function ((8) or (9)).
end for Return s features with largest µi.
model compression [21], discrete softmax activations [15], and feature selection [36]. Here, we use a Gaussian-based relaxation of Bernoulli variables, termed Stochastic Gates (STG) [36], which relies on the repamaterization trick [23, 11], to reduce the variance of the gradient estimates.
We denote the STG random vector as Z ∈ [0, 1]d, parametrized by µ ∈ Rd. Each vector entry is defined as Zi = max(0,min(1, µi + i)), (6) where µi is a learnable parameter, i is drawn fromN (0, σ2), and σ is fixed throughout training. This approximation can be viewed as a clipped, mean-shifted, Gaussian random variable. In Fig. 4, we illustrate the gating mechanism and show examples of the densities of Zi for different values of µi. Note that, even though Zi is not differentiable at 0 or 1, we can use the sub/sup-gradient, which is defined using the one-sided gradient of the function at 0 or 1.
Multiplication of each feature by its corresponding gate enables us to derive a fully differentiable feature selection method. At initialization µi = 0.5 for i = 1, ..., d, so that all gates approximate a ”fair” Bernoulli variable. The parameters µi can be learned via gradient decent by incorporating the gates into a diffrentiable loss term. To encourage feature selection in the supervised setting, [36] proposed the following differentiable regularization term:
r(Z) = d∑ i=1 P(Zi > 0) = d∑ i=1 ( 1 2 − 1 2 erf ( − µi√ 2σ )) , (7)
where erf() is the Gauss error function. The term (7) penalizes open gates, encouraging those corresponding to features that are not useful for prediction to transition into a closed state (which is the case for small µi).

heading: 4.3 Differentiable Unsupervised Feature Selection (DUFS)
text: LetX ∈ Rm×d be a data mini-batch. LetZ ∈ [0, 1]d be a random variable representing the stochastic gates, parametrized by µ ∈ Rd, as defined in Section 2. For each mini-batch, we draw a vector, z,
of realizations from Z and define a matrix, Z̃ ∈ [0, 1]m×d, consisting of m copies of z. We denote X̃ 4 = X Z̃ as the gated input, where is an element-wise multiplication, also known as the
Hadamard product. Let LX̃ be the random walk graph Laplacian computed on X̃ .
We propose two loss function variants. Both variants contain a feature scoring term, − 1mTr[X̃ T LX̃X̃], and a feature selection regularization term, ∑d i=1 P(Zi ≥ 0), as in (7). In the first variant (8), the two terms are balanced using a hyperparameter λ ≥ 0.
L(µ; λ) := − Tr [ X̃ T LX̃X̃ ] m + λ d∑ i=1 P(Zi ≥ 0). (8)
Tuning λ allows for flexibility in the number of selected features. In Section S2 of the Appendix, we present an unsupervised scheme for tuning λ. To obviate the need to tune λ, we introduce an alternative parameter-free loss function:
Lparam-free(µ) := − Tr [ X̃ T LX̃X̃ ] m ∑d i=1 P(Zi ≥ 0) + δ , (9)
where δ is a small constant added to circumvent division by 0. The parameter-free variant (9) seeks to minimize the average score per selected feature, where the average is calculated as the total score (in the numerator) divided by a proxy for the number of selected features (the denominator). Minimizing both objectives (8) and (9) will encourage the gates to remain open for features that yield high Laplacian scores and closed for the remaining features.
Our algorithm involves applying a standard optimization scheme (such as stochastic gradient decent) to objective (8) or (9). This optimization algorithm will use the following calculation.
d
dµi Tr[X̃
T LX̃X̃] =
{ 2Zi(X̃ :,i) TLX̃X̃ :,i + ∑ s,t(X̃X̃ T )s,t d dµi ( Kt,s∑ lKt,l ) Zi ∈ (0, 1)
0 Zi ∈ {0, 1}
d
dµi d∑ i=1 P(Zi ≥ 0) = d dµi erf ( µi√ 2σ ) ,
where erf() is the Gauss error function and X̃ :,i denotes the i−th column of X̃ . After training, we remove the stochasticity ( i in (6)) from the gates and retain features satisfying Zi > 0. At each step of the training procedure, we compute a kernelK, (see (1)), based on a mini-batch of size m. The complexity of this calculation is O(mk2) [7], using the top k nearest neighbors for each point. A pseudo code describing the steps of our method is shown in Algorithm 1.

heading: 4.3.1 Raising L to the t’th Power
text: Replacing the Laplacian L in equations (8) and (9) by its t-th power, Lt, with t > 1 corresponds to taking t random walk steps [24]. This suppresses the smallest eigenvalues of the Laplacian, while preserving its eigenvectors. We used t = 2, which was observed to improve the performance of our proposed approach (see Appendix for additional details).

heading: 5 Experiments
text: To demonstrate the capabilities of DUFS, we begin by presenting an artificial two-moons experiment. We then report results obtained on several standard datasets and compare them to existing unsupervised feature selection algorithms. When applying the method to real data we perform feature selection based on Eq. (8) using several values of λ. In the Appendix (Section S2), we describe a procedure for choosing the optimal value of λ. Next, following the analysis in [34], we perform k-means clustering using the leading 50, 100, 150, 200, 250, or 300 selected features and average the results over 20 runs. Leading features are identified by sorting the gates based on P(Zi) (see (7)). The number clusters k is set as the number of classes, and the sample labels are utilized to evaluate clustering accuracy. The best average clustering accuracy is recorded along with the number of selected features |S|.
of retrieved informative features and all retrieved features, that is:
∑2
i=1 P (Zi>0)∑d i=1 P (Zi>0)
. Middle: feature selection recall. Here, recall is defined as the ratio between amount of retrieved informative features and all informative features, that is: ∑2 i=1 P (Zi>0)
2 . Note that, in all of these examples, the gates converge to “deterministic” values. Namely, P (Zi > 0) ' 1 for informative features i = 1, 2, and P (Zi > 0) ' 0 for the nuisance features i = 3, ..., d. Right: clustering accuracy obtained with the retrieved features (recorded every 10 epochs). Here, clustering is performed using spectral clustering [26] with a Gaussian kernel.

heading: 5.1 Noisy Two-Moons
text: In the first experiment, we use a two-moons-shaped dataset (see Fig. 1) concatenated with nuisance features. The first two coordinates f1,f2 are generated by adding a Gaussian noise, with zero mean and variance of σ2r = 0.1, to two nested half circles. Nuisance features f i, i = 3, ..., d, are drawn from a multivariate Gaussian distribution with zero mean and identity covariance. The total number of samples is n = 100. Note that the small sample size makes the task of identifying nuisance features more challenging.
We evaluate the convergence of the parameter-free loss (9) using gradient decent. We use a different number of features d and plot the precision and recall of feature selection throughout training (see Fig. 5). In all of the presented examples, perfect precision and recall are achieved at convergence.

heading: 5.2 Noisy Image Data
text: In the following experiment, we evaluate our method on two noisy image datasets. The first is a noisy variant of MNIST [19], in which each background pixel is replaced by a random value drawn uniformly from [0, 1] (see also [29]). Here, we focus only on the digits ‘3‘ and ‘8‘. The second dataset is a noisy variant of PIXRAW10P (abbreviated PIX10), created by adding noise drawn uniformly from [0, 0.3] to all pixels. In both datasets, the images were scaled into [0, 1] prior to the addition of noise. We applied DUFS and LS to both datasets, identifying low frequency features. In the top panels of Fig. 6, we present the leading 50 features retained on the noisy MNIST along with the average clustering accuracy over 20 runs of k-means. In this case, DUFS’ open gates concentrate at the left side of the handwriting area, which is the side that distinguishes ‘3‘ from ‘8‘. This allows DUFS to achieve a higher clustering accuracy comparing to LS. The bottom panels of Fig. 6 show the leading 300 features retained on noisy PIX10 along with the average clustering accuracy. Here, DUFS selects features which are more informative for clustering the face images. We refer the reader to Appendix S4 for additional information on this experiment and for extended results on COIL20 and COIL100 [25].

heading: 5.3 Clustering of Real World Data
text: Here, we evaluate the capabilities of the proposed approach (DUFS) on real-world high dimensional datasets whose properties are summarized in Table 1 3. We compare DUFS to Laplacian Score (LS) [4], Multi-Cluster Feature Selection (MCFS) [6], Local Learning based Clustering (LLCFS) [37], Nonnegative Discriminative Feature Selection (NDFS) [20], Multi-Subspace Randomization and
3All datasets are publicly available, see description in Appendix section S7
Collaboration (SRCFS) [14], and Concrete Auto-encoders (CAE) [1]. We compare the accuracy of clustering based on the feature selected by DUFS to those selected by the 6 baselines, and all features (All). As can be seen in table 1, DUFS outperforms all baselines on 9 datasets and ranks second on the remaining 3. Overall, the median and mean rankings of DUFS are 1 and 1.31, respectively. In the Appendix, we present a complementary table with the standard deviations of the clustering accuracies obtained in this example. Our results demonstrate that our method is extremely useful in bioinformatics; for example, when scientists study single-cell RNA sequencing (scRNA-seq), accurate cluster assignments are vital for downstream analysis. In table 1, the bottom 4 datasets were sequenced using scRNA-seq technology; on these datasets, DUFS improves the cluster assignments by 23.0% (on average) compared with assignments obtained based on all features.

heading: 6 Conclusions
text: In this paper, we propose DUFS, a novel unsupervised feature selection method that introduces learnable Bernoulli gates into a Laplacian score. DUFS has an advantage over the standard Laplacian score, as it re-evaluates the graph Laplacian based on the subset of selected features. We demonstrate that our proposed approach captures structures in the data that are not detected by the standard Laplacian score. Finally, we experimentally demonstrate that our method outperforms current unsupervised feature selection baselines on several real-world datasets.

heading: Acknowledgements
text: The authors thank Stefan Steinerberger, Boaz Nadler and Ronen Basri for helpful discussions. The work of OL and YK was supported by the National Institutes of Health R01GM131642, UM1PA05141, P50CA121974, and U01DA053628.

Review summaries:
This paper studies the problem of unsupervised feature selection for clustering. It proposes adding stochastic gates to the features such that those that minimize the Laplacian score are learned, and the algorithm iteratively updates the stochastic gate parameters and the random walk graph Laplacian matrix (that is computed only using the features selected by the gates). Experimental results on both simulated and real-world data (e.g. image data, single cell RNA-sequence data) suggest improvement over the naive Laplacian score and other unsupervised feature selection methods.

The paper proposes a feature selection mechanism that aims to preserve the structure of the neighborhood graph of the data. The mechanism is based on the use of stochastic gates that is trained via a regularizer, which balances (i) the goodness of fit of the selected features to the neighborhood graph Laplacian with (ii) the expected value of the number of features preserved. The numerical results show improvements in performance vs. the literature of varying levels and in most tested datasets.

This paper proposes a novel unsupervised feature selection method to efficiently remove nuisance features. The model combines a graph Laplacian score with stochastic gates, which adds a re-evaluation of the graph Laplacian to improve the performance in downstream applications. Experiment results are provided to validate the theoretical claims.

This paper proposes an unsupervised feature selection method that introduces learnable Bernoulli gates into a Laplacian score. Specifically, The proposed method utilizes stochastic input gates, trained to select features with high correlation with the leading eigenvectors of a graph Laplacian computed based on these features. Finally, compared with baselines, the proposed method can improve cluster assignments using some real datasets.