Differentiable Unsupervised Feature Selection based on a Gated Laplacian
Authors: Ofir Lindenbaum
Uri Shaham
Erez Peterfreund
Jonathan Svirsky
Nicolas Aidan Casey
Yuval Kluger
Venue: NeurIPS 2021 Poster (2021)
Keywords: Feature Selection
Graph Laplacian
Laplacian Score

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 set in the high noise regime. Using several real-world examples, we demonstrate the efficacy and advantage of the proposed approach over leading baselines.

Differentiable Unsupervised Feature Selection based on a Gated Laplacian
Ofrr Lindenbaum Faculty of Engineering Bar-Ilan University
Uri Shaham
Center for Outcome Research and Evaluation
Yale University
Ramat Gan, Israel 5290002
New Haven, CT 16510, USA uri shaham@yalee.eeeeemamemeaaaaaaae edu
o ofir.. w.r..iindenaaau@bi...
il
Erez Peterfreund Hebrew University
Jonathan Svirsky Independent Researcher
Nicolas Casey University of Pennsylvania
Yuval Kluger
Program in Applied Math Department of Pathology
Yale University
New Haven, CT 065 10, USA yuval. www.lllwweeeeeyll.eee... edu
Abstract
Scientific observations may consist of large number of variables (features). Select- ing subset of meaningful features is often crucial for identifying patterns hidden in the ambient space. this paper, we present method for unsupervised feature selection, and we demonstrate its advantage in clustering, common unsupervised task. We propose a differentiable loss that combines a graph Laplacian-baser score that favors low- low-frequency features with a gating mechanism for removing nuisance features. Our method improves upon the naive graph Laplacian score by replacing it with 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 is erucial 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 the proposed approach over leading baselines.
Introduction
Unsupervised and self- 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 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 simultancous measurement of numerous features, making the analysis large, nigh-dimensional datascts a vital research need.
Indicates equal contribution
35th Conference on Neural Information Processing Systems (NcurIPS 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 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 use autoencoders to identify features that are sufficient for reconstructing the data. Other clustering-dedicate 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 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 (L.S) [33 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
manifold learning. Among studies that tackle the former task, [33 12
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 demonstrated in Section 3) This may happen in the presence of 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 higher ambient space, were studied in [7
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 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).
2 Preliminaries
Consider a data matrix, X E Raxd, with d dimensional observations Ii. Ix. We refer to the columns of X as features f..... fa. where f; E IR," and, assume that features are centered and normalized such that 12 = 0 and [| = 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-pont -poor. The structured part of the data is considered as either a path- gath-connected manifold, union of mub-manifolds, or a set of clusters. Our goal is identify the subset of relevant features S which preserve the data structure and discard the remaining ones.
2.1 Graph Laplacian
Given n data points, kernel matrix K is an n n matrix whose K,,, entry represents the similarity between æ; and æz. A popular choice for K is the Gaussian kernel
[ x;
Kij = exp
20
Inn section 3 we consider scenarios where low dimensional datasets that form manifold or cluster structures are augmented with information-pon -porr nuisance features that are independent of the original structure and are. themselves, of no particular underlying structure.
2

---

where is user-defined bandwidth (chosen, for example, based on the maximum value of the 1- nearest-neighhors of all points). The unnormalized graph Laplacian matrix is defined as Ln D K, where D is diagonal matrix, whose elements D.,; ブØ=ı Kijj correspond to the degrees of the points = 1,.., n. The diffusion graph Laplacian is defined as
Lai = D
(2)
and expresses the transition prohabilities of random walk to move between data points and induces 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
2.2 Laplacian Score
Following the success of the graph Laplacian 4 and 266. 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 fd Lunf. where Lun is the unnormalized graph Laplacian. Since
fT Lun
where Lun =E Xuur is the eigen-decompositton of Lun- the score is smaller when f has larger projection on the subspace the leading cigenvectors (corresponding to the smallest eigenval- ues) of Lun. Such features can be thought of as "informative", Eigenvalues the Laplacian can be interpreted as frequencies, and eigenvectors corresponding to larger eigenvalues of Lun (or smaller eigenvalues of Lan) oscillate faster. Based 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.
they respect the graph structure.
3 Demonstration of the Importance of Unsupervised Feature Selection in High Dimensional Data with Nuisance Features
By taking diffusion perspective, first demonstrate the importance of feature selection supervised 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 normal Gaussian distribution with the structured part of the data. A concrete example is detailed in the following subsection.
3.1 A Diffusion Perspective
Consider the structured 2-dimensional dataset, known as two-moons, shown in the top-left panel of Fig. [ We concatenate the structured data with "nuisance" dimensions, where each such dimension composed of i.i.d unif(0, 1) entries. This means that that the & Gaussian variables do not carry any information about the two mmoon-shaped" clusters in this dataset. As 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 recover the main structure of the data (say, using manifold learning or clustering) are likely to fail.
data consists of 2 + & variables. Note
From diffusion perspective, data is considered to be clusterable when the time it takes 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: Las D K, 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). Fach added nuisance dimension increases the distance between points which 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 characterized by the second largest eigenvalue, X2 of Lair (the largest eigenvalue è carries no information it corresponds to the constant eigenvector 1/ 1), which decreases as the number of nuisance dimensions grows, see the top right panel of Fig. [ 'The fact that X2 decreases implies that the diffusion distances [24] decrease as well which, turn, means that the clusters become more connected. 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 more nuisance dimensions added is also manifested by the eigenvector, 2/2, corresponding to the second largest eigenvalue of Lai (or the second smallest eigenvalue of Lun), which becomes less representative of the cluster structure (bottom left panel of Fig.
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, shown in the bottom right panel of Fig. | 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.
3.2 Analysis of Clustering with Nuisance Dimensions
In order to observe the effect of nuisance dimensions, this section considers a simple example with two clusters in 1-D space and set of nuisnace variables which do not carry any information about these clusters. Specifically, consider a dataset that includes 2n datapoints in I, where n of which are IR and the remaining ones are at Next, we concatenate d nuisance dimensions to first coordinate, so samples lie in RR+11 The value for each datapoint in each nuisance dimension is sampled independently from N(00, 0.5?).
(i.e., each cluster is concentrated at specific point).
2.4
1.5
14
1.0
0.8
x
-0.9
-1.0
0.4
1.5
-2.5
0.2
Number of nuisance dimensions
dimensions
nuisanca dimansions
nuisance dimansions
nuisance dimansions
PCi nuisance dimensions
dimonsioons
nulsance dimensions
dimensions
Figure 1: The Two-moons example. Top Left: the original 2-dimensional data. Top right: the second largest eigenvalue of the random walk matrix, Lant decreases the number, k of nuisance dimen- sions grows. This suggests that the graph becomes more connected- and, hence, less clusterable- as the number of nuisance dimensions grows. Bottom left: the eigenvector, 2b, (y-axis) (corresponding to the second largest eigenvalue), of Lai becomes less representative of the true cluster structure the number of nuisance variables (k) grows. The x-axis represents the sample index Bottom right: the leading two principal components of the + 2 dimensional data (x and axes) cannot help recover the true cluster structure when 0.

---

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 the correct cluster. Consider points x, y belonging to the same cluster. Then (æ - y) = (0, Mi,...., Uza) -where iid
04 ~ (0, 1), and, therefore, || yll² ~ xå- Similarly, if x; belong to different clusters, then || - v/ ~ + X2. where r is the distance between clusters in the first coordinate. Now, to find conditions for and d under which the neighbors of each point are highly likely to belong to the same cluster, we can utilize the x²
bounds [8]]
Lemma 3.1 (18) P.1325). Let X ~ Xa. Then
1. P(X - d 2 2/d7 + 27)= S exp(-7)
2. Pdd - 2 2 - exp(->)
Given sufficiently small 7 > 0 we can divide the segment [d, d + r²] to two disjoint segments of lengths 2 2y and 2/ (and solve for d in order to have the total length r²) This yields
2 27
vd
4/7
If all distances between points from the same cluster are at most d + 2/ 2y and all distances between points from different clusters will be at least d + r² 22/7, the nearest neighbors of each point will be from the same cluster. According lemma 3.1 this happens with probability of at least (1 - exp( exp(->))2= 2n we obtain
For a small 6 > 0, denoting this probability as e and solving for 7,
S - logg(1
(2m
(4)
Plugging
4 into 3
we obtain
p4
d = 0
(5)
log((1
(2n
For fixed number of samples (n) and a small value of c O, equation implies that the number of nuisance dimensions must be at most on the order of r to make cluster mixture unlikely. In addition, for a fixed r and e, 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 simultancously filters nuisance features and re-evaluates the smoothness of the remaining features.
Proposed Method
4.1 Rationale
Recall that the core component of the Laplacian score [33 is the quadratic term f Lf. which measures the inner product of the feature f with the eigenvectors of the Laplacian L. For L
Lun D D-- K, large Laplacian score implies that f has large component in the subspace of cigenvectors corresponding to the largest eigenvalues of L. Assuming that the structure of the data varies slowly, these leading eigenvectors (corresponding to large cigenvalues) manifest the main structures in the data; thus, a large score implies that 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 f" Lxgff, where Lxs is the random walk Laplacian computed based on a subset of features { Fes)) When the Laplacian is computed on only the informative features (i.e., when Lx. = Lxs- ), such a gated Laplacian score would produce a high value for the informative features, S*
5

---

450
1.0
Fw0
192
* of nuisance variables
Intersection of plws, y) 0.7
Polynomial fit up to degree
0.8
0.6
250
p(42
200
0.4
150
0.2
0.0
10:
10"
0.6
0.8
1.0
1.2
14 1.6 18
2.0
of nuisance variables
Distance between clusters
Figure 2: Two cluster datasets. We evaluate the influence of Gaussian nuisance variables the Laplacian. We generate two clusters using 50 samples each with distance apart in 1-D. We use d Gaussian nuisance variables and evaluate the leading non trivial eigenvector 12 of the Laplacian. Left: correlation between the second cigenvector 1 and the true cluster assignments for different values of r. As the number of nuisance variables grows, the eigenvector 1//2 becomes meaningless. As the distance between cluster grows more nuisance variables are required to "break" the cluster structure captured by 2/2. Right: by computing the intersection between the damped correlation curves and 0.7 (shown in the left plot) for different values of we evaluate the relation between and number of nuisance variables required for breaking the cluster structure. This empirical result supports
analysis presented in 3.2 in which show that d O log(1
For convenience
(2H
added polynomial fit up to degree 4 presented as the black line.
1325
3.20
-04
Feature index
Feature index
-1.0 100
200 400
epochs
Figure 3: Illustrating the information captured by the Laplacian Score (using Lrw) on the noisy two-moons dataset (see Fig. [T. The first two features are informative, while the rest are nuisance variables. Our goal is to train the differentiable stochastic gates for identifying the two informative features. Left: Laplacian score f Lf at initialization, based on all 10 dimensions. The score for the informative features is slightly higher. Middle: Laplacian score, based on the gated Laplacian f Lxs- the gates' convergence. The informative features attain a substantially higher score based on the gated Laplacian. Right: the parameter-free loss (black line) and the average number of active gates (red line) as a function of the number epochs.
Searching over all the different feature subsets is infeasible even for 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 expected to have higher scores than nuisance ones, penalize open gates to minimize the number of features and retain the most relevant (smooth) features. By applying gradient decent cost function based on Lxs- 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.
obtain desired dynamic, in which gates
4.2 Stochastic Gates
Recently, several authors have incorporated continuous approximations of discrete random variables into neural network training [22 [6). Such relaxations have been used for many applications, such as

---

Algorithm Differentiable Unsupervised Feature Selection (DUFS) Pseudo-code
Input:
data, {.1....:.8. Fn. I2 regularization parameter X, required number of features number of epochs T:
Initialize the gate parameters: 14 0.5 for i L....,d.
for t 1 to I" do
Sample a stochastic gate (STG) vector
.Z...... Zd) as described in (6)
Apply the STG to the data 2; to obtain the gated data i;; ( (;;
C Z).
Compute a kernel matrix K E "R (see T using the gated data {
Compute the graph Laplacian Laift E B as described in 2 Update yI...., by applying GD to the loss function or end for
Return s features with largest pi.
model compression 21,, discrete softmmx activations [15]. and feature selection [36]. Here, use
Gaussian- based relaxation Bernoulli variables, termed Stochastic Gates (STG) [3)., which relies on the repamaterization trick [23 [ to reduce the variance of the gradient estimates.
We denote the STG random vector as E [0, 174, parametrized by μ E Rd. Each vector entry is defined as
(6) where μt is a learnable parameter, 6, is drawn from ((,0, and ø is fixed throughout training. This approximation can be viewed as a clipped, mean-shifted, Gaussian random variable. In Fig. we illustrate the gating mechanism and show examples of the densities of Z; for different values of μ4- Note that, even though Z, is not differentiable at or 1, we can use the sub/sup gradient,, which is defined using the one-sided gradient of the function at 0 1.
Z: max (0, min(1, H4 + c:))
Multiplication of each feature by its corresponding gate enables us to derive a fully differentiable feature selection method. At initialization 14; = 0.5 for 1, ,..., d, so that all gates approximate
a "fair" Bernoulli variable. The parameters 14 can be learned via gradient decent by incorporating
the gates into diffrentiable loss term. To encourage feature selection in the supervised setting, (36 proposed the following differentiable regularization term:
(1
14 V2o )):
r(Z) Σ P(Z
Σ
crf
2
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 (4.).
4.3 Differentiable Unsupervised Feature Selection (DUFS)
Let X E Rmxd be a data mini-batch. Let E [0, 1j be a random variable representing the stochastic gates, parametrized by fa IRd, as defined in Section 2. For each mini-batch, we draw a vector, z.
= 0.5
f
Z
fz(m))
fzl4))
μ
E
N.(,0.5')
Figure 4: Left: The stochastic gate Z is defined via the repamaterization trick 223 1 Standard
Gaussian noise is injected and shifted by trainable parameter 14;; the sum thresholded to (0. 1 based on (6). Two examples of the density of the stochastic gate Z, Middle: at initialization, μ4; = 0.5.
and the gate approximates 'fair' Bernoulli variable. Right: the distribution at ia -1 approximates
a "closed' gate.
7

---

of realizations from Z and define matrix. E [0,1] consisting of m copies of z. We denote
X - X Z as the gated input, where @ is an element-wise multiplication, also known as the Hadamard product. Let _ be the random walk graph Laplacian computed on X.
We propose two loss function variants. Both variants contain feature scoring term,
1 Tr g X and a feature selection regularization term, Σ P(Z; 2 0), as in 7 In the first variant the two terms are balanced using a hyperparameter N
L(p; X) Tr
T
L
PZZ 20.
(8)
1=1
Tuning À allows for flexibility in the number of selected features. In Section S2 of the Appendix, we present an unsupervised scheme for tuning X. To obviate the need tune X, we introduce an alternative parameter-free loss function:
Tr
L x X
I Tepuram free (1L) E P Zi 2 08
where 5 is small constant added 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 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 ( ( This optimization algorithm will use the following calculation.
d du
{
2 T X Ex,(xX)) )ade dps
( E,
Kis
Z: E (0, 1)
Tr(X L L
K.,
Z: E {0,
d duu
P(Z: 2
erf
14i
djp
V20
where erf() is the Gauss error function and X., denotes the i-th column of X. After training, remove the stochasticity (c; in (6)) from the gates and retain features satisfying Z; > At each step compute kernel K, (see (1), based
of the training procedure,
mini-batch of size m. The complexity this calculation is (m)??) 77, using the top & nearest neighbors for each point. A pseudo code describing the steps of our method shown in Algorithm [
4.3.1 Raising L to the t'th Power
Replacing the Laplacian L in equations 8 and (9) by its t-th power, L', 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 / = 2, which was observed to improve the performance of our proposed approach (see Appendix for additional details).
Experiments
To demonstrate the capabilities of DUFS, we begin by presenting an artificial two-moons experi- ment. We then report results obtained on several standard datasets and compare them to existing unsupervised feature selection algorithms. When applying the method real data we perform feature
selection based on Eq. (8) using several values of X. In the Appendix (Section S22). we describe
procedure for choosing the optimal value of X. Next, following the analysis [84, 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(Z,) (see 77). The number clusters l 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).
8

---

Prectsion
Clstering
02
530 1000
2008 2530 2048 3000 3043 4230 340
1003
1520 2003
3006 3003 3300
4003
500
1000
2006 2000 2006 3030 3543 4030
Figure 5: Evaluating the precision and recall of feature selection, in addition clustering quality as a function of epoch number. We apply the parameter-free loss variant (see (9) on the noisy two-moons data with total of d features, out of which only the leading 2 capture the structure the two-moons. Left: feature selection precision. Here, precision is defined as the ratio between amount
of retrieved informative features and all retrieved features, that is: >> P(2,>0) Middle: feature 2 P(Z,>0)
selection recall. Here, recall is defined the ratio between amount of retrieved informative features and all informative features, that is: D2 P(Z,20) Note that, in all of these examples, the gates converge "deterministic" values. Namely, P(Z > 0) for informative features 1, and P(Z, 0) = 0 for the nuisance features i = 3, ..., d. Right: clustering accuracy obtained with the retrieved features (recorded every 10 epochs). Here, clustering performed using spectral clustering 26 with a Gaussian kernel.
2
5.1 Noisy Two-Moons
In the first experiment, features. The first two coordinates f f: f2 are generated by adding Gaussian noise, with zero mean and variance of of 0.1, from a multivariate Gaussian distribution with zero mean and identity covariance. The total number of samples
two-moons-shaped dataset (see Fig. 1 concatenated with nuisance
nested half circles. Nuisance features f,: 3,..., d, drawn
100. Note that the small sample size makes the task of identifying nuisance features more challenging.
We evaluate the convergence of the parameter-free free loss using gradient decent. We 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.
5.2 Noisy Image Data
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 random value drawn uniformly from [0, 1] (see also (29)). Here, we focus only on the digits '3' and '8'. The second dataset noisy variant of PIXRAWIOP (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 both datasets, identifying low frequency features. In the top panels of Fig. 6, we present the leading 50 features retained on the noisy MÑIST 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 DUES to achieve 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 SS4 for additional information on this experiment and for extended results on COIL.20 and COIL [25].
5.3 Clustering of Real World Data
Here, we evaluate the capabilities of the proposed approach (DUFS) real-world high dimensional datasets whose properties are summarized Table 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-Subspaac Randomization and
All datasets publicly available, see description in Appendix section S7

---

Acc=0.857
Acc=0.811
# 300 #Feat=50
# #Feat=50
Acc=0.778
Acc=0,639
Figure 6: Noisy image experiments. Top: examples of noisy MNIST digits highlighted with the leading 50 features selected by DUFS (left) and LS (right). Bottom: examples from the noisy PIXI0 datasets overlaid with the leading 300 features selected by DUFS (left) and LS (right). This figure is best viewed color. The grayscale of MNIST images is inverted to improve visibility.
(CAE) [] We compare the accuracy of clustering based on the feature selected by DUFS those selected by the baselines, and all features (All), As can be seen in table | DUFS outperforms all baselines on 9 datasets and ranks second on the remaining 3. Overall, In the Appendix, we present complementary table with the standard deviations of the clustering accuracies obtained this example. Our results demonstrate that our method 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 the bottom 4 datasets were sequenced using scRNA-seq technology; these datasets, DUFS improves the cluster assignments by 23.0% (on average) compared with assignments obtained based on all features.
Collaboration (SRCFS)
and Concrete
median and mean rankings of DUFS are and 1.31, respectively.
20
37
DimnSumplee
GISETTE
75.8 (50)
56.5 (50)
(250)
72.5 (50)
68.5 (50)
77.3 (250)
99.5 (50)
74.4
4955 / 6000 2/ Image
PIXTO
76.6 (150)
75.9 (200)
(206)
69.1 (300)
75.9 (100)
94.1 (250)
88.4 (50)
74.3
10000 / 100 10 Image
Almage
Yale
42.7 (300)
(300)
(3050)00)
42.6 (300)
46.3 (250)
(250)
47.9 (200)
38.3
1024 165 / /hmage
RCVI
54,9 (300)
50.1 (1.50)
55.1 (150)
55.0
$3.7 (300)
54.9 (300)
62.2 (300)
50.0
24408 / 22/222/ 2/ Test
TOX-171
47.5 (200)
(2.5(110)
(100)
16.7 (250)
45.8 (150)
47.7(100)
49.1
41.5
5748 / 17L /4
(100)
PROSTATE
56.8 (300)
(300)
58.3 (100)
57.8 (50)
60.6
(250)
64.7 (150)
58.1
5966 102 102/22 /Bio
SRBCT
A1.11300)
43.7(250)
11.0500
15.6
33.19((50)
62.6 (290)
51.7 (50)
39.5
2308 / 83 / Bio
BIASE
83.8 (200)
95.5 (300)
(100)
(300)
50.8 (50)
85.1 (250)
100 (50)
41.8
25683 / 56: / Bio
(100)
FAN
(5.5(150) (2.9(110))
18.8 (100)
(500
29.0 (100)
35.2 (300)
49.0 (50)
37.5
25683 56
POLLEN
46.9 (150)
66.5 (300)
48.9 (50)
(100)
(300)
$8.0 (250)
60.2 (50)
$4.9
21810 / 301 744 Bio
Table 1: Left sub-table: Average clustering accuracy several benchmark datasets. Clustering is performed by applying k-means to the features selected by the different methods. The number of selected features is shown in parenthesis. Right sub-table: Properties of the real world data used for empirical evaluation.
6 Conclusions
In this paper, we propose DUFS, novel unsupervised feature selection method that introduces learn- able Bernoulli gates into Laplacian score. DUFS has advantage over the standard Laplacian score, as it re-evaluates the graph Laplacian based on the subset of selected features. We demonstrate that 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 several real-world datasets.
Acknowledgements
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, UMIPA05141, 950CA121974, and UOIDA053628.
10

---

References
[1] A. Abid, M. F. Balin, and Zou. Concrete autoencoders for diffcrentiable feature selection and reconstruction. arXiv preprint wrXiv:1901.09320 2019.
[2] O. Alter, P. O. Brown, and D. Botstein. Singular value decomposition for genome -wide expression data processing and modeling. Proceedings of the National Academy of Sciences, 97(18):00101-10006 2000.
[3] M. Banerjee and N. R. Pal. Feature selection with svd entropy: Some modification and extension. Information Sciences, 264: 184:118-111 134,,,, 2014.
[4] M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in neural information processing systems, pages 585-591, 2002.
[5] Benaych- and R. R. Nadakuditi. The singular values and vectors of low rank perturbations of large rectangular random matrices. Journal of Multivariate Analysis, 111:120- 135, 2012.
[6] D. Cai, C. Zhang, and X. He. Unsupervised feature selection for multi-cluster data. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 333-342, 2010.
[7] J. Chen, H.-r Fang, and Y. Saad. Fast approximate knn graph construction for high dimensional data via recursive lanezos bisection. Journal of Machine Learning Research, 10(9). 2009.
[8] R. R. Coifman and S. Lafon. Diffusion maps. Applied and computational harmonic analysis,
21 21(1):5-30, 2006.
[9] D. Devakumari and K. Thangavel. Unsupervised adaptive floating search feature selection based on contribution entropy. In 2010 international conference on communication and computational intelligence (INCOCCI), pages 223-627.22 IEEE, 2010.
[10] D. L. Donoho, M. Gavish, and I. M. Johnstone. Optimal shrinkage of eigenvalues in the spiked covariance model. Annals of statistics, 46(4): 2018.
[11] M. Figurnov, S. Mohamed, and A. Mnih. Implicit reparameterization gradients. In Advances in Neural Information Processing Systems, pages 441 1452, 2018.
[12] K. Han, Wang, C. Zhang, C. Li, and C. Xu. Autoencoder inspired unsupervised feature selection. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2941-29000 2941-2945. IEEE, 2018
[13] X. He, D. Cai, and Niyogi. Laplacian score for feature selection. Advances in neural information processing systems, pages 507-514, 2006.
[14] D. Huang, X. Cai, and C.-D. Wang. Unsupervised feature selection with multi-subspace randomization and collaboration. Knowledge-Based Systems, 182:104856, 2019.
[15) E. Jang, S. Gu, and B. Poole. Categorical reparameterizatioon with gumbel-softmax. arXiv preprint 161 1,41 2016.
[16] E. Jang, S. Gu, and B. Poole. Categorical reparameterization with gumbel-softmax. 2017.
[17] I. M. Johnstone. On the distribution of the largest eigenvalue in principal components analysis. Annals of statistics, pages 295-327, 2001.
[18] B. Laurent and P. Massart. Adaptive estimation of quadratic functional by model selection. Annals of Statistics, pages 1302-1338, 2000.
[19] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 2324, 1998.
[20] 7. Li, Y. Yang, Liu, X. Zhou, and H. Lu. Unsupervised feature selection using nonnegative spectral analysis. In Twenty-Sixth AAAI Conference Artificial Intelligence, 2012.

---

[21] C. Louizos, M. Welling, and D. P. Kingma. Learning sparse neural networks through 1_0 regularization. arXiv preprint urXiv:1712.013122 2017.
[22] C. J. Maddison, A. Mnih, and W. Teh. The concrete distribution: continuous relaxation of discrete random variables. arXiv preprini
2016.
[23] A. Miller, N. Foti, A. D' Amour, and R. P. Adams. Reducing reparameterization gradient variance. In Advances in Neural Information Processing Systems, pages
2017.
[24] B. Nadler, S. Lafon, R. Coifman, and G. Kevrekidis. Diffusion maps-a probabilistic inter- pretation for spectral embedding and clustering algorithms. In Principal manifolds for data visualization and dimension reduction, pages 238-260. Springer, 2008.
[25] S. A. Nene, S. K. Nayar, H. Murase, et al. Columbia object image library (coil-100). 1996.
[26] A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Advances neural information processing systems, pages 849-856, 2002.
[27] P. Padungweang, C. Lursinsap, and K. Sunat. Univariate filter technique for unsupervised feature selection using new laplacian score based local nearest neighbors. In 2009 Asia-Pacific Conference on Information Processing, volume 2, pages 196-200. IEEE, 2009.
[28] E. Peterfreund and M. Gavish. Multidimensional scaling of noisy high dimensional data. Applied and Computational Harmonic Analysis, 2020.
[29] Y. Qi, H. Wang, R. Liu, B. Wu, Y. Wang. and G. Pan. Activity-dependen neuron model for noise resistance. Neurocomputing, 357:240-247, 2019.
[30] V. M. Rao and V. Sastry. Unsupervised feature ranking based on representation entropy. In 2012 1sl International Conference on Recent Advances in Information Technology (RAIT), pages
421 425. IEEE, 2012.
[31] R. Varshavsky, A. Gottlieb, M. Linial, and D. Horn Novel unsupervised feature filtering of biological data. Bioinformatics, 22(14):557-<4513, 2006.
[32] U. Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4)3395-416, 2007.
[33] S. Wang, 7. Ding, and Y. Fu. Feature selection guided auto-encoder. Thirty-First AAAI Conference Artificial Intelligence, 2017.
[34] S. Wang, J. Tang, and H. Liu. Embedded unsupervised feature selection. In Twenty-ninth AAAI conference on artificial intelligence, 2015.
[35] X. Wei and S. Y. Philip. Unsupervised feature selection by preserving stochastic neighbors. In Artificial intelligence and statistics, pages 995-1003, 2016.
[36] Y. Yamada, O. Lindenbaum, S. Negahban, and Y. Kluger. Feature selection using stochastic gates. In International Conference on Machine Learning, pages 10648-10659, PMLR, 2020.
[37] H. Zeng and Y.-m. Cheung. Feature selection and kemel learning for local learning- based clustering. IEEE transactions on pattern analysis and machine intelligence, 33(8): 2010.
[38] Z. Zhao and H. Liu. Spectral feature selection for supervised and unsupervised learning. In Proceedings of the 24th international conference on Machine learning, pages 1151-1157, 2007.
[39] Z. A. Zhao and H. Liu. Spectral Feature Selection for Data Mining (Open Access). CRC Press, 2011.
12

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See section S8 in the Appendix.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 3.2
(b) Did you include complete proof's of all theoretical results? [Yes] We write the proof throughout Section 3.2
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main perimental results (either in the supplemental material or as a URL)? [Yes] Code is available in the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Description of all training procedure appears in Section S3 in the Appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] The std error values of our experiments, which were shown in Table T are presented in Table [T in the Appendix.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] Description of the computational resources are described in Section S3 the Appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "vaSUJUGu4kn", "reviewer": "Reviewer_Rzva", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am curious as to how the proposed method preserves the structure of the original data given that the original data graph and the full data are not referred to in the objective functions implemented here. In [36], the features selected are used to predict the same labels as the full data. Here, it appears to me that the features are judged as to how well-matched they are to the graph structure appearing from the *currently selected* features, not the entire set available originally.\n\nIs there a sense for how well the proposed method preserves the structure of the full data that are relevant in the unsupervised learning task? This is an interesting question in terms of how the clustering performance is preserved after the selection, as well as to  whether the proposed method can be expanded to other tasks beyond clustering.\n\nIt would be good to describe how the derivative in the equation after line 229 is computed.\n\nThe author questions state that a theoretical result is provided in Section 3.2, but no new lemma or theorem appears there. Perhaps (5) should be reformatted as such.\n\nSome of the answers to the author questions (Q4, regarding data) are missing.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations provided are common to feature selection methods: it is assume that nuisance variables exist in the original data, and here it is further assumed that they are of a high frequency nature. The notion of frequency, however, is not described in terms of the problem addressed in the manuscript; does this refer to the alignment of the features with the eigenvectors of the graph Laplacian having small eigenvalues?\n\nThere is an interesting question here of what the dimensions that are discarded might mean in real-world datasets that are successfully modeled by neighborhood graphs. For example, while in images discarding certain pixels may not have a negative impact, one wonders what may be discarded when working with demographic data, for example.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "vDbq7y2_gy", "reviewer": "Reviewer_2vfK", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper demonstrates very strong experimental results, especially on clustering real-world datasets (Table 1). This seems different enough from previous works, and has promise to be used by practictioners who work with clustering high-dimensional data (e.g. computational biologists). Also, the code and experimental details are provided in the supplementary material. \n\nHowever, the paper could be improved by addressing the following questions:\n- The existing methods that are compared in Section 5.3 are not the same as the prior work discussed in Section 1. How are these methods different from the proposed work/prior work and why were they chosen for comparison? How does the proposed work compare to other extensions of LS (mentioned in line 39 page 2)?\n- What is the run time/actual computation time of the proposed algorithm? How does it compare to the other methods?\n- In Section 5.3, is clustering done identically across the different feature selection methods, i.e. is the difference in performance solely due to the difference in feature selection? Is k-means clustering applied after DUFS?\n- It's not clear to me how much Section 3, especially 3.2, adds to the paper. Why does the result from this exercise suggest that \"Laplacian is sensitive to the number of nuisance dimensions in large datasets\"?\n\nThe paper is easy to follow most of the time, but a few comments on clarity:\n- In Algorithm 1, should $\\tilde{x}_i = x_i \\odot Z_i$? And is $L_{diff} = L_{\\tilde{X}}$, given that $L_{diff}$ does not appear in (8) or (9)?\n- There are some awkward margins, especially before and after figures. For example, Figure 3 cuts off the paragraph above.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "YdS6vlkRwLJ", "reviewer": "Reviewer_X1KW", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well organized and clearly written. \nThis paper provides enough information to reproduce its results.\nThe submission addresses a difficult task in a better way than previous work, but i think it is hard  to use the ideas or build on them.\nThe work is a combination of well-known techniques and related work is adequately cited, but i think it is not very clear how this work differs from previous contributions.\nThe proposed method is supported by sufficient experimental results without theoretical analysis.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitations and potential negative societal impact of their work. However, there are some concerns as follows:\n1.The main concern is the innovation of this paper. Firstly,  laplacian score is proposed by Ref.13 for feature selection as an unsupervised measure. Secondly, i think that the main contribution of this paper is stochastic gates, but in Ref.36, the technology of stochastic gates is already used in supervised feature selection. Finally, authors focus on the traditional unsupervised feature selection problem. Thus i think that the core contribution of this paper is that authors extend the supervised problem in Ref.36 to the unsupervised problem without theoretical guarantees. Even authors introduce the importance of unsupervised feature selection from a diffusion perspective, but i don't think this is the core contribution of this article. For this question, if the authors can persuade me , I will change my score.\n2.Authors introduce the importance of unsupervised feature selection from a diffusion perspective and i think this is a very novel thing for feature selection, but i can't understand what is the difference between similarity and exit times in nature. I hope the author can give me a more detailed explanation to understand the difference.\n3.Authors sample a stochastic gate (STG) vector in algorithm 1 and thus i think that the proposed method should have randomness. But in the main experiment of this paper, i don't see this randomness analyzed by authors. \n4.It would be better if the authors add some future work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "E_5m0bRgjbE", "reviewer": "Reviewer_LQQD", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n1. The proposed method applied differential stochastic gates to compute the Laplacian scores, which added a novel perspective to identify the informative features with some theoretical assumptions.\n\n2. Removing nuisance features is a fundamental task when dealing with high-dimension data, which is a useful method to discover main structure and improve the performance of clustering.\n\n\nCons/Questions:\n\n1. The presentation is somewhat difficult to follow. The writing could be improved by framing the storyline more, giving the readers more guideposts and simplifying the caption of figures.\n\n2. It would be interesting to see the performance on the manifold learning task.\n\n3. It would be better to try different noise patterns. For real data, entire dimensions may be more complicated including some structured but useless features. A multivariate Gaussian distribution can be considered as one of common noise patterns. More noise levels and patterns can be investigated.\n\n4. In the experiments of real-world data, what is the general relationship between the clustering accuracy and dimension of selected features? What will the results change if all the baselines choose the same dimensions of features? As a hyper-parameter, is there any quick selection mechanism or theoretical guarantee for the dimension/proportion of the selected features?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See Main Review.", "review_text": "", "extra_scores": {"ethical_concerns": "n.a.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "~5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers found that the proposed work proposes a sufficiently novel and interesting analysis and approach to solve an important problem, together with compelling experiments.

The rebuttal provides clear responses to the comments and questions of the reviewers.

The authors are strongly encouraged to take into account the comments of the reviewers and the elements they themselves contributed to this discussion when preparing the final version of the manuscript. 
Decision: Accept (Poster)