Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

Is 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.

It would be good to describe how the derivative in the equation after line 229 is computed.

The 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.

Some of the answers to the author questions (Q4, regarding data) are missing.
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?

There 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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Pros:

1. 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.

2. 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.


Cons/Questions:

1. 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.

2. It would be interesting to see the performance on the manifold learning task.

3. 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.

4. 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?

limitations_and_societal_impact: See Main Review.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: This paper is well organized and clearly written. 
This paper provides enough information to reproduce its results.
The 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.
The 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.
The proposed method is supported by sufficient experimental results without theoretical analysis.
limitations_and_societal_impact: The authors addressed the limitations and potential negative societal impact of their work. However, there are some concerns as follows:
1.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.
2.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.
3.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. 
4.It would be better if the authors add some future work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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. 

However, the paper could be improved by addressing the following questions:
- 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)?
- What is the run time/actual computation time of the proposed algorithm? How does it compare to the other methods?
- 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?
- 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"?

The paper is easy to follow most of the time, but a few comments on clarity:
- 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)?
- There are some awkward margins, especially before and after figures. For example, Figure 3 cuts off the paragraph above.
limitations_and_societal_impact: Yes.
review_title: null

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)