Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper introduces a data-driven approach for detecting groups of features that differentiate between conditions. For each condition, we construct a graph whose nodes correspond to the features and whose weights are functions of the similarity between them for that condition. Then a spectral approach is applied to compute subsets of nodes whose connectivity differs significantly between the condition specific feature graphs.
strengths_and_weaknesses: Strengths: 
1. The experimental results are good;
Weaknesses:
1. The proposed work makes me confused after I read the paper. It is not clear what the proposed method aims for, feature selection?
2. If the proposed work aims for feature selection, why uses two datasets A and B?
3. If the feature dimension p is very large, there will be a large number of nodes on the graph. How to handle the high computational cost?
questions: See weaknesses above.
limitations: none
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a closed-form spectral solution to the problem of selecting feature selection that maximize the difference between two datasets.

This paper was the hardest to review in my batch. While the approach is a rather straightforward application of spectral community detection on graphs, the theoretical results are interesting, and the problem rather practical. I put up my review a very low confidence with a hope to discuss the paper more with other reviewers/AC.

strengths_and_weaknesses: [Strengths]

The problem is very basic. Given two data sets, what makes them different? This seems like a rather fundamental tool in the data analysis toolbox to have, and I appreciate a closed-form solution.

Theoretical results on the stochastic block model are solid and interesting. They are informative to practical application of the method and provide interesting insights on distinguishability of differentiating features.

[Weaknesses]

The experimental study seems rather forced. The problem is rather basic, and I would love to see comparison to some straightforward baselines from the fields of nonparametric statistics, or even naive iterative selection strategies based on some notion of divergence in the data. The design of a MNIST experiment is very unclear to me – why do authors average pixel values for differentiating features? I find it hard to evaluate hyperspectral and fMRI experimental results as well.
questions: Can you clarify the selection of the baselines in the paper?

limitations: N\A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the selection of subsets of features that differentiate between conditions, which can be further used for classification or in-depth understanding of data or underlying mechanisms. It proposes a data-driven method DiSC to detect and group relevant features, which builds a graph with features as nodes and kernel functions as weights to quantify similarities between features. The principle is that the differences between class-specific graphs imply differences between conditions, and thus the task is to identify the independent components that appear in one graph but no the other. This paper further provides theoretical analysis for two stochastic block models and demonstrate the usefulness of DiSC in three toy datasets, MNIST, hyperspectral imagery, and fMRI datasets.

strengths_and_weaknesses: Strengths:

1. This paper uses kernel functions to define the weights for class-specific graphs of feature similarities, which is a sound idea considering the flexibility of kernel methods.

2. A graph cut perspective is a brilliant idea, on which this paper is based to propose "differential vectors" and "significance level". They make a contribution by the property of non-symmetry and the increase of stability.

Weaknesses:

1. We expect more in-depth theoretical understanding of strengths of your extensions, differential vectors & significance level, compared to diffusion map, double objective, etc. Indeed you have pointed out the advantages of the extension. We agree with your comments roughly in logic, however, a rigorous analysis would be more convincing. From 3.1 to 3.2 you have shown a logic chain to propose (7). As the main section of your method, we expect more mathematical comments (now we only have a vague understanding of strengths of (7)).

2. Admittedly your toy examples have shown the usefulness of your proposed approach, but for these toy examples. What we probably expect more is a kind of benchmark that could explore the boundary of your method. These boundaries might be conditions that guarantee the sound performance of your approach. In toy examples, the differences between conditions are "sharp": one correlated, one ideally independent. Indeed you have an underlying assumption (Line 101-104), while we like to see the performance when applying to non-ideal case (i.e. when the approximated 0 is not so ideally small, how the performance is compromised.). For example, would our approach work for such a scenario: one strongly correlated, one weakly correlated; and how such a metric that describes the comparative difference of correlations affect the performance? (The concern is similar to non-separable case in classification.) Analysis in theory is challenging; at least we like to see the performance in simulation.

Strengths(?) or Weaknesses(?):
Sec. 3.3 is indeed a good work in theory; however, we do not know how to evaluate its contributions considering the main story of this paper. One may refer more to other reviewers' comments on this section.

questions: As explained in Sec. "Weaknesses", we summarize the expected
improvements here:

1. More understanding of (7) in mathematics. 

2. More toy examples or benchmark that clear our concerns.

limitations: We appreciate the authors' work that could potentially make a contribution. And we do not foresee any potential negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper introduces a spectral approach for features which differentiate classes, in that these features are relevant to the structure in one class but not the other. The approach is based on producing a graph for each class which reflects the affinities between features in the associated class. The eigenvectors of the random walk (RW) Laplacian matrices of these graphs are generally seen as capturing the structure, and so in order to remove structure relevant to class B from the Laplacian from group A is projected into the null space of B's eigenvectors, and vice versa, and the spectral decomposition of these projected Laplacian matrices reveals structure relevant to the one class which is left after removing the relevant structure from the other. Post-processing of the singular vectors of the projected graph Laplacians provides groups of differentiating features (by clustering their rows) or meta-features (by projecting the original features from each class onto these singular vectors).

The paper provides a theoretical analysis in the context of a stochastic block model in which one group of features is shared by the two classes, while another is split in two by the one class but not the other.

The paper concludes with some interesting applications, showing potential for practical relevance of the method.

#### Update following author rebuttal and in light of other reviewers' comments
I am satisfied with the corrections which the authors have made which, I believe, remove my main concerns about the paper. The theoretical contributions are fairly modest and the proposed method not the most elegant, but I believe the novelty in how the authors have approached an interesting and potentially relevant problem is sufficient to justify acceptance. I think the work represents a good first investigation into this problem and I hope these authors, and potentially others, will improve on the formulation and solution of the problem in future.
strengths_and_weaknesses: Strengths:
- The problem studied in the paper is a very interesting one, and the approach taken appears to be fairly novel, both at a high level (looking specifically for discriminating features) and at a low level (the specific methodology proposed).
- The presentation is fairly clear, and the paper well written for the most part.

Weaknesses:
- The major weakness of the paper is in its technical clarity and, potentially, correctness. In particular, unless I am missing something, the proof of Theorem 1 is not correct. For the sake of font, let v be the vector \tilde v_\gamma from the paper and e the vector \frac{1}{\sqrt{s}}e_\gamma from the paper. The authors seem to assert that an index, say i, for which |v(i) - e(i)| >= 1/2\sqrt{s} contributes at least 1/2\sqrt{s} to the l_2 distance between the vectors. However, I don't see how this is the case. All I can see is that the proof shows us ||v - e|| < C => ||v - e||^2 < C^2 => C^2 >= \sum_{i=1}^n (v(i) - e(i))^2 >= \sum_{misclassification indices} (v(i) - e(i))^2 >= (number of misclassifications) (1/2\sqrt{s})^2 = (number of misclassifications)/4s => (number of misclassifications) < 4sC^2. Indeed, my suspicion was raised by the fact that ANY two vectors of unit length are bounded in distance by 2, and so their argument seems to give us that a randomly sampled vector on the unit sphere, thresholded as they propose, would give a misclassification rate of at most 2\sqrt{s}. If I am mistaken in my interpretation of the proof of theorem 1, perhaps the authors can address this issue?

- I will point out other minor issues in the following section, via queries.
questions: - Line 119: what is a "non-binary indicator vector"? and why is f one? Does this just mean the two distinct values are not 0 and 1?
- The formulation given in (4) and (5) seems more elegant than the one which is actually used. If this approach doesn't yield as good performance, then why discuss it in detail while omitting the detail for the approach which is actually employed?
- The constants in the lemmata are very important since, as mentioned above, all pairs of unit-length vectors are bounded in distance trivially. If the constants are large then the lemmata become irrelevant. Can you include them explicitly?
- What exactly does "with high probability" mean? I am sure it is not difficult to bring in this probability explicitly.
- I had to look at the appendix to learn what the quantities d_A and d_B in line 227 are. Do they actually appear in the paper somewhere?



I will also include in this section a few editorial comments/corrections
- LASSO is an acronym, and so is usually written capitalised, and not as Lasso.
- Notation of l-p norms should be consistent. Sometimes these are in math font, while other times not.
- line 64: "... identify groupS..."
- The term "independent components" carries a specific meaning in feature extraction, and I would suggest choosing a different phrase.
- Line 125: peviously "mincut" was "minimum-cut" 
- The notation used for l-p norms is again not consistent in that sometimes "||.||" is given without the value p, whereas in at least one instance we find "||.||_2"
- The expression in (7) seems incorrect, since the argmax is taken over E, meaning that the vector (V_A)_i to which it is assigned should be a subspace, and not the vector v as desired.
- The two data sets are sometimes denoted X_A and X_B and sometimes X^A and X^B
- "algorithm 1" should be "Algorithm 1"
- the bracket in line 227 does not close.

limitations: I do not see any potential for foreseeable negative societal impact arising from the work.
review_title: null

Meta-review: metareview: In the discussion, the area chair and the reviewers reached a consensus that the potential for practical relevance of the proposed method is very interesting and agreed to recommend the acceptance of the paper. The reviews provide valuable feedback to the authors to improve the final version of their paper that we are looking forward to see at the conference. 
confidence: Certain
Decision: Accept