DiSC: Differential Spectral Clustering of Features
Authors: Ram Dyuthi Sristi
Gal Mishne
Ariel Jaffe
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential features
spectral clustering
feature selection
manifold learning
graph theory

Abstract: Selecting subsets of features that differentiate between two conditions is a key task in a broad range of scientific domains. In many applications, the features of interest form clusters with similar effects on the data at hand. To recover such clusters we develop DiSC, 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. We then apply a spectral approach to compute subsets of nodes whose connectivity pattern differs significantly between the condition-specific feature graphs. On the theoretical front, we analyze our approach with a toy example based on the stochastic block model. We evaluate DiSC on a variety of datasets, including MNIST, hyperspectral imaging, simulated scRNA-seq and task fMRI, and demonstrate that DiSC uncovers features that better differentiate between conditions compared to competing methods.

DiSC: Differential Spectral Clustering of Features
Ram Dyuthi Sristi, Gal Mishne
Ariel Jaffe Hebrew University Jerusalem, Israel ariel, mai..huji.ac.il
UC San Diego La Jolla, CA, USA (rsristi, gmishne @ @ucsd.edu
Abstract
Selecting subsets of features that differentiate between conditions is key task a broad range of scientific domains. many applications, the features interest form clusters with similar effects the data at hand. To recover such clusters we develop DiSC, a data-driven approach for detecting groups of features that differentiate between conditions. For each condition, we construct graph whose nodes correspond to the features and whose weights are functions of the similarity between them for that condition. We then apply a spectral approach compute subsets of nodes whose connectivity pattern differs significantly between the condition- -specific feature graphs. On the theoretical front, we analyze our approach with toy example based on the stochastic block model. We evaluate DiSC on variety of datasets, including MNIST, hyperspectral imaging, simulated scRNA-seq and task fMRI, and demonstrate that DiSC uncovers features that better differentiate between conditions compared to competing methods.
Introduction
Detecting variables or features that separate between two conditions is critical task in many scientific domains. Often, the separation between conditions is caused by large number of strongly dependent features that form one more differentiating clusters. Recovering those clusters can provide insights into the data and its underlying mechanisms.
Strongly dependent differentiating features are common, for example, in transcriptome analysis, where the data consists of the gene expression of multiple cells. Often, the cells correspond to two or more biological conditions, such various cell types, the existence of particular disease, response to medical treatment, or two-time points in an evolutionary process [48].
Uncovering groups of differentiating genes (also known pathways) may significantly contribute to our understanding of biological processes happening in one condition and not the other. Differential feature grouping has various other interesting applications in neuroscience 43 computer vision and machine learning (6). all applications, detecting groups that are significant for differentiating between conditions adds interpretability to the otherwise black box models.
Due to its importance various domains, the feature selection task has been the focus of intensive research. Often, methods for feature selection are designed to yield sparse output, for example, by selecting only small number of features out of large correlated group. One example is the best subset selection approach, where features are iteratively added or removed until a predetermined criterion is met. Another popular approach to linear (or general linear) model that predicts function over the data points, e.g., class label. For example, classical LASSO relaxes the lo norm of the coefficient vector with its convex surrogate 7, [13 Alternatively, recent approach aims to approximate the lo regularizer via stochastic gates [44)
achieve sparse output by adding regularization terms
37
To address the case of correlated features, various extensions of LASSO were developed. Clustered LASSO 33 promotes sparsity among the coefficients and equal significance to non-zero coefficients
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

in the same group. Ordered Weighted LI regularization (OWL) 4 penalizes the coefficients in the order of their magnitude. i.e., the higher the absolute value of the coefficient, the higher the penalty that will be imposed. This induces equal coefficients to the correlated features [14]. Elastic Net [4 uses a combination of 1 and // regularizers which creates a feature grouping effect. Cluster Elastic Net [42] assumes that each feature belongs to one of k-distinct clusters and uses a clustering penalty, along with LASSO, which minimizes the sum of pairwise distances between the associations of features with the prediction within each cluster. A method that combines feature selection and grouping was also developed in [ A few methods explicitly use the correlation between the features in the regularization terms. 25 estimates the covariance between features from which they form graph. The graph Laplacian matrix is then used as a quadratic regularizer function.
This line of work typically addresses a linear regression model. However, in many settings the dependency on the important features is highly non-linear. This is typically the case, for example, in most discrete settings such as classification and clustering. Furthermore, most of these methods do not separate different groups of correlated features that are significant a classification or regression problem. In many settings, such separation is important gain insight into different sources of the variability in the data.
A different approach related to this work is feature selection via discriminant subspace analysis methods such as linear discriminant analysis [3 32 and the Fukunaga- Koontz transform [7 31
Here, the primary goal is to identify the subspace that best discriminates the classes according to a given criterion. For example, the classic Fischer criterion [[6] maximizes the ratio between inter-class variance and intra-class variance. Recent works applied similar methods in the context of non-negative
and Boolean matrix factorization (2 21
Some metric learning approaches (28) which take into account triplet relationships between points, learn a linear transform on the features so that the distance in the projected space better separates the classes. 7 introduces a Riemannian geometry based composite kernel for differential feature extraction. However, these approaches do not explicitly perform feature selection to identify different groups of correlated features that separate the classes.
In this paper we develop a data-driven method to detect and group relevant features that does not rely on a specific model. We consider the classification setting, where our aim is to identify class-specific information in the feature space that distinguishes between different conditions. To that end, we develop DiSC, a data-driven method to reveal groups of differential features. Our approach consists of two main steps: first, for each class, we compute a class-specifit graph, whose nodes correspond to the features of that class separately. Next, we apply spectral approach to obtain an embedding of the features that identifies groups of features whose connectivity differs between the graphs. Our contributions in this paper are:
1. We develop data-driven spectral approach on the feature space to identify groups of correlated features that distinguish between datasets
2. Our solution is non-symmetric such that we identify class-specific differential features
3. We provide theoretical analysis in the setting of a stochastic block model underlying the features
Our spectral approach is related to recent papers that address the challenges of multiview and data fusion. Here, data samples are observed by multiple sets of sensors, and the goal is identify latent
representations of the samples that are shared for all sets. The shared information can be recovered via the shared latent space between multiple sources. Alternating Diffusion Maps (ADM) (24) is a
nonlinear manifold learning approach to reveal shared latent variables. Shnitzer et al. [35 extend this identifying both common structures and the differences between the manifolds underlying the different modalities. In an alternative solution, [26] proposes kernel and distance metric for
diffusion maps on multiview datasets. There are numerous other data fusion techniques 277, [10] and applications (22]. Most of these techniques require one-to-one correspondence between data samples from different views, e.g., simultaneous recordings from different sources, and they mainly focus extracting a shared subspace or shared hidden variable of the samples. In contrast, in our setting the correspondence is between features two datasets, and not between samples. Our goal is to uncover connectivity patterns that are condition specific.

---

2 Problem formulation
We begin with formal description of our problem, followed by relevant notation. We consider two datasets X 4 E AA and X E a XP where the rows in each matrix are high-dimensional samples and the columns are the features, see illustration in Fig. Th. Both datasets have the same p features, such that the feature column in A, denoted X E R corresponds to the feature column in B, denoted X E R Our goal in this work is to detect one or more subsets of features that together differentiate between the two states A and B. These subsets can be, for example, groups of genes that form a biological pathways, or subset of brain parcels in fMRI data with similar blood oxygen level dependent (BOLD) activity.
In our approach, we compute two graphs, denoted GA. GB with nodes that correspond to the features of the given data (Fig. [p). We denote by Wa, WB the weight matrices of the two graphs, whose elements are functions of the similarity between features, as computed by two kernel functions,
(A x.)) RA x R + R
and
KB x R
R + R. (I)
These for example can be the RBF kernel (xxxx') = exp(-1Iz x' 2 Our underlying assumption that differences between the two states A, are expressed as differences in connectivity patterns between the two graphs GA and GB. For example, a pair of features i. may be insignificant state and highly signifieant and dependent in B. This will imply,
KA =0 and Kg x.) 0.
If there is subset of features , it that are strongly dependent in B but not in A, the resultant nodes in GB will form an independent component with dense connections among the nodes. However, this independent component will not exist in GA. see illustration in Figure 1 Thus, the task of obtaining sets of significant features boils down identifying the independent components that appear in one graph but not the other.
3 DiSC
3.1
A graph cut perspective
Given graph G with nodes and its associated weight matrix W E g=X", the minimum-cut of G is the minimum, over all possible partitions a and B. of the sum of the edge weights Eienjes W (i,,j). This task is strongly related to the spectral clustering algorithm. For completeness, we begin with brief description of this relation. For a more thorough review see [41]
variation of the minimum-cut, designed avoid highly imbalanced partitions, is the ratio-cut
Reut(a,
Σ
WE
+ B
(2)
iEO.EE
where [a], | denote the subset size. This can be formulated as
i
Reut(a, 3) = L where f.
(3)
E
and T., is the unnormalized graph Laplacian matrix given by D W. where D is diagonal the degrees of each node in its diagonal. Note that ff is a non-binary indicator vector where each elemnt of f. represented by only takes one of the two different values given in Eq. 3 If a, 3 are non-empty, then f orthogonal to the constant vector with Il = n. Minimizing Eq. (3) over all partitions is discrete optimization problem. To avoid it, one relax the discrete requirement over the elements of if in Eq. B while still maintaining the constraints f = 0 and || = n. This relaxation yields simple spectral solution, where the nodes partitioned according to the sign of the graph Laplacian eigenvector corresponding to the second smallest eigenvalue (a.k.a Fiedler vector).
The minimum-cut criterion is designed to attain densely connected components that have low connectivity with the rest of the graph. our work, however, densely connected components that appear in both graphs are of no interest, as they do not differentiate between the two states. Rather,
3

---

Deteset
Catasat
WA
Wo
U
Up Vea
b) Gx
Figure 1: DiSC overview. a) Datasets A and share the same features. b) Constructing graphs G and G the feature space for each dataset, aim to find which nodes have different connectivity pattern between the two datasets. c) The weight matrices each follow a stochastic block model, where in B subset of of the nodes form separate block. d) Subspaces spanned by the eigenvectors of PA and Pn, and the differential feature between B and A.
we would like to detect partition (a, 3), say on GB, that has two properties: 1) Reut(a, 3), on GB minimized, which indicates that and are independent connected components in GB; 2) To avoid detection of components that exist both in GA and GB. Rcut(a: 5) on G is lower bounded by some constant. This double objective can be formulated by
min S Lnf /
s.t.
L TA.
|||| 11
(4)
The constraint |l = is added for uniqueness, since LA. LB are rank deficient. Relaxing the discrete requirement in Eq. (3), the solution Eq. (4) is given by the generalized eigenvalue problem LBf = pL Since A is not invertible, one numerical trick is to strengthen the diagonal of L to make it full rank matrix. Relaxing the discrete requirement in 3), the solution is given by the eigenvalue problem,
(LA + LBf uf.
(5)
Motivated by the above derivation, in the next section present spectral approach for group feature discovery. In the appendix we present similar derivation that based on the normalized cut, whose relaxation relates the eigenvectors of the random walk graph Laplacian.
3.2 Spectral approach for group differential feature extraction
Our proposed approach for detecting differences between graphs is motivated by the solution of the double objective criterion given in Eq. (5) However, due to the instability and computational complexity the matrix inversion of the graph Laplacians LA, L.g, we make the following two changes. First, replace the unnormalized graph Laplacian matrices LA and Lg with the normalized random walk Laplacians
PA = DD= D WA
Pв = PB=DE'W: D WB.
where DA, DB are the degree matrices of G., GB, respectively. The random- walk Laplacian the basis of diffusion maps, which have been shown to be connected spectral clustering in [29] 30). Let UB E Ruxdy be a matrix containing the dg leading right cigenvectors of Pg. These vectors, scaled by their corresponding eigenvalues, are the diffusion vectors of the graph G (9] A vector containing the i-th element of the columns of UA is defined as the diffusion map representation the i-th node.
The second change we make is to replace the inverse operation with following projection operator,
Qa = -
-
The matrices Qa, QB are projection operators the subspace complementary to the diffusion vectors in UA, Up.

---

We compute the differential vectors of GA, denoted (Va), and their significance level (αA); by solving the following optimization problem
(aA); dim
min
max EES(E)
PAAQBol22
where a subspace RP, ((F) denotes unit Fuclidean sphere in E, (a is the optimal value of (7) and (Va), is the vector which optimal value of ( is attained. Note that the operator PaQB whose singular vectors are used to attain differential features is not symmetric in A and B. The differential vectors in VA highlight components that significant in A but not in B. Similarly, the differential vectors VB that are equal to the singular vectors of QBQA highlight components that are significant in B but not in A.
The relation between the diffusion vectors UA and the differentiating vectors VA is similar in nature to the relation between the outcome of the min-cut criterion in Eq. (3) and the double objective in Eq. 4 The diffusion vectors in UB capture significant processes that underlie state B. However, are only interested in processes that differentiate between state A and B. These are highlighted in the differential vectors VB. In the experimental results in Sec. 4 we compare the diffusion maps representation the differential vectors to illustrate this difference.
Differential vectors for downstream analysis The differential vectors VA, VB and their scores A,, o оB can be used in several ways. Here, and in the experimental section, use the vectors in one of two applications: (i) Detecting of differential subsets features. This can be done by performing of the matrices VA. VB; (ii) Computing differential meta- pettureesssess via VI XA and V XB. In section and supplementary material we provide several examples for using both options in downstream analysis (e.g., clustering, classification). In the next section derive a theoretical justification for application (i) that is motivated by the stochastic block model. Algorithm summarizes the steps of the DiSC algorithm. Further details about the computation of the graph and discussion on choice of hyperparameters is given in App. A
k-means clustering over the
Algorithm 1 DiSC
Input: Datasets X and X
Two kernel functions K Ka(--)) and KB(;,))
Output: Subsets of differentiating features VA, VB
1: Compute graphs GA and GB the columns of X and X with weights given by
1
2: Compute the random walk matrix, PA = D Wa, Pg = D3 We.
3: Calculate UA UB. the leading right eigenvectors
Ps.
4: Compute the projection matrices QA. QB via Eq. (6).
5: Compute differential vectors VA and VB via Eq.
6: Compute significance levels a and dg via Eq.
7: optional: Perform k-means over rows Va. and V8.
Computational Complexity Naively computing a graph based on a kernel function is of order O(y²). For some cases, this can be prohibitively large. However, there are simple ways reduce the complexity to be close to linear. For example, common approach is to compute the kernel function only for the closest k-nearest neighbors, and not for all the O(p2) pairs of features. Computing k-nearest neighbors for all features can be done effectively with structures such as KD-trees, with computing such
an average complexity (for each feature) graph is (kkplog(p)). More efficient graph construction is possible with approximate nearest neighbors. A second advantage of this approach is that the Laplacian matrix is sparse, with only kn non zero elements. Thus, the computation of the eigenvectors can be done efficiently as well with complexity Okk)).
log(p). Thus the total complexity
3.3
Two stochastic block models
The stochastic block model (SBM) has received lot of attention due to its significant role in obtaining theoretical guarantees for community detection. this setting, the individual community members modeled as nodes in random graph G. The edge weights Wy are sampled according
5

---

Bernuuli distribution, with
p
i,j belong to the same community
([WWy=1)-
(8)
l otherwise.
Usually, one assumes p > y such that the connectivity within a block is stronger than the connectivity
between blocks, See 1 for further details.
In our setting, we model the features in both states by two random graphs GA and Gg. We consider a toy problem in which the features that differentiate two states A and B have different graph connectivity in GA and GB. In graph GA the nodes are partitioned into two communities of sizes I and 1+ 8, with $ < I. In contrast, the graph GB has three communities, denoted a, 8 and Community is equal to the first community in GA. while B, y are partition of the second into two groups of size I and s.
Our goal is detect the elements in y via spectral approach whose steps are similar Algorithm For simplicity of exposition, instead of using the graph Laplacian matrix as in step 2 of the algorithm, we use the symmetric weight matrices WA WB. B- Our goal in this analysis is to provide insight into our ability to recover differentiating groups such as y via Algorithm [ Our main parameters of interest are the size of the differentiating group 7, and the ratio between the size of 7y and the size of the original block. Elements that depend on other parameters of the model (e.g. and q) are referred to as constants. Our derivation consists of three main steps. The proofs of our results are given in Appendix [ In addition, appendix presents numerical results that validate the bound in lemma 2 and test optimality. We note that all matrix norms (i.e. || in the following section and relevant appendices are the spectral norm.
Step 1: Here address the non-random matrix W[Wa]] where [E[]] is the expectation operator. Let for v3, vyy be the leading three eigenvectors of (E and by ey a binary indicator vector with elements (ey): 1ff E 7.
Lemma 1. The distance between By and 1 By is bounded by
Juy 1
1 --
The eigenvalue corresponding to u. is larger than (p - g)
Lemma shows that the ratio s/l is small enough, one can recover the elements in y by applying a threshold to uy.. However, in practice we only have access to Wy and WA. In the next step we bound the difference between By and the eigenvector we compute by our spectral approach.
Step 2: Let ua, ug be the two leading eigenvectors of the random weight matrix WA. and let Qw I - ua - -uguy. In this step we address the leading eigenvector of Qw, WBQw,. Lemma 2. Let Üy denote the leading eigenvector of Qwa W WBQWA. Then.
1| - - S C2(p.)) VI + Colp. 15.
w.p
1- (-exp(-I).
Step 3: Observing the two lemmas, we see that there is tradeoff concerning the size of the differentiating group y: On the one hand, Lemma D shows that having a small value for s makes the element more distinguishable in v. and thus easier to detect. On the other hand, if < vi then the computed vector ü, might be too noisy to actually detect the relevant features.
Combining the two lemmas, we conclude with the following theorem.
Theorem 1. We assume that s, I are large s.I. s, > max;(C.). and s = la with 0.5 < a < 1. We apply a threshold to J, determine the elements of 7 The relative number of errors N is bounded by
[C(lp 1)1 0.5 < a
CC(p, 2/3<
w.p
1 - exx((-l).
Proof of Theorem D Let Ca(p, q) = Ci(p.)) + Ca(p, q). combining Lemmas I inequality, and assuming s 1a yields the inequality
2 with the triangle
c $ 2) (1-200) + Ca(p, 9) 2((-1) + Cz(o, (p..

---

For 0.5 < a < 2/3, the dominant term is C2(p. -)²11= We recover the elements in y by setting threshold of 2/3 to By. Each misclassified element contributes at least 14(4)) to the squared l distance between e and öy. Thus, for 0.5 a S 2/3 the relative number of errors N is bounded with high probability by
N
1
||
b
c
(4s)/8
V8
A similar derivation can be done for 2/3 a1
4 Experiments
4.1 Toy problems
We demonstrate the usefulness of our methodology in three toy datasets which present different scenar- ios of feature correlation patterns: 1) a subset of features that is uncorrelated in one dataset becomes correlated in the second 2) a subset of features that are correlated in one dataset are divided into two correlated groups in the second. 3) The third problem demonstrates generalizing DiSC to more than two datasets. In all experiments the kernels AA, Kg are the RBF kernel with an adaptive bandwidth. The choice of the all the hyperparameters (bandwidth, d and d are discussed in Appendix A
4)
082
b)
0.00
307
0.5
200
-0.2
-0.00
100
200
0.20
(0gh
d)
0.2
Mah
Mah
(Og))
0.08
-0.2
0.00
20
100
200
200
200
3.00
20.0
3.00
200
1000
200
Figure 2: a) Random samples from X and X b) Feature correlation matrices of X (left) and _ (right). <) Significance of the differential vectors of X (blue) and X (orange). d) Top two differential vectors. e) Top four diffusion maps of the features of X (blue) and X 8 (orange).
Identifying newly connected features We generated two datasets X and XB with p = 250 features and A = n = 10. 000 samples from Gaussian mixture model (Fig. aa)). whose feature correlation shown in Fig. (b.. the two datasets, the first 100 features are i.i.d samples from a normal distribution and the next 50 features are sampled from two Gaussian distributions with low rank covariance matrices. Features 151-200 X are sampled from two other Gaussian distributions with low rank covariance matrices, whereas in = they are independent noise. Features 201-250 in X are independent noise, whereas X they are sampled from two other Gaussian distributions with low rank covariance matrices.
Our goal is to identify the features 151-200 as the features that distinguish X from XB and vice versa for features 201-250. We apply DiSC with d d = 20. The first two significance values of the differential features are high and then significance drop drastically (Fig. ())) indicating that the first two differential vectors are important in each dataset. These top two differential features for X and XB are shown Figure 2 Clearly, (VA)1 and (VA)2 highlight the features between 151-200 and more precisely, the two Gaussian mixtures Similarly. (VB)1 and (VB)² )2 highlight the features between 201-250 and these represent the other two Gaussian mixtures. On the other hand, the diffusion maps eigenvectors, UA and Ug. captures all the connected components and not just the differential features as unique groups, as shown in Fig. e(c).
separately represented in each of these vectors.
Identifying subsets of connected features We generated two datasets X and X with 200 features and n = ng = 10, 000 with correlation between the features as shown in Fig. 3 a). In both
Code to reproduce the results for Sections 4.1 and 4.2 is available in httth::t///eet https:///ttttan http://gtttttttt// www/Miihneeeaaaaeeeoeennnnn
DisC
7

---

a)
b) 0.2
d)
10sh
02
(UAls
KUahs
(UAlz
MW WO
KUa)z
-0.2
100 0
100
0.0
0.0
100
2000
100
200
(UAls
100
200
200
200
Figure 3: a) Correlation matrices. b) Significance levels. c) Differential features. d) Diffusion maps.
the datasets, the first 100 features are correlated. In XA, all the remaining features form second correlated group, yielding two connected components in the feature space. In X the remaining features are composed of two groups of correlated features, namely, feature indices 101-125 and 126-200.
Here the goal is to identify these smaller subsets of correlated features in X as this signifies an increase in the dimensionality of correlation structure compared to XA, This also means that X has richer feature information than X therefore we have to identify that there are differential features in XA.
We use the significance level associated with the differential vectors to determine if the differential vectors are meaningful. We apply DiSC with d, = dg 20. Fig. ( shows the differential vectors of X and X and the corresponding significance levels are shown in Fig. 3)). The significance level associated with the differential vectors of XA negligible compared to that of X indicating that feature information in X is contained in X In addition, the difference between the significance of the first two differential vectors of X B is large. Therefore, the first differential vector of X captures the major difference, and it groups feature indices 101-125 and 126-200 with positive and negative values respectively (Fig. ())). In contrast, diffusion maps captures the two connected components in X A and three connected components in X", and not just the differential components d)))
4.2 MNIST
The MNIST dataset 23 consists of images of hand written digits from O to 9, each of dimension 28 28 pixels. has 60k training samples and 10k testing samples. We used Algorithm DiSC on multiple datasets, on the MNIST dataset to extract differential features for each of the digits: features present single digit but are not present each of the other digits. To have a quantitative metric to measure the significance of these differential features, we develop a classifier for 10-class classification problem. For this, we use K-means clustering on the differential features for each digit (K=10) thus deriving clusters of pixels that together differentiate between digits. We then compute meta-feature by averaging pixel values for each cluster. Logistic regression is performed on these meta features to distinguish between the 10 classes.
We compare our approach with Diffusion maps. Elastic Net (EN) and Elastic Net logistic. For diffusion maps, we replaced the differential features with diffusion maps and followed the same procedure. For EN and EN-logistic, we obtained the feature importance vectors by training a classifier to distinguish between the 10-classes. K-means clustering is performed on these feature importance vectors. This cluster information further used to compute meta-featur and finally for classification. Additionally, the entire data (784 features) is used to obtain the clusters using K-means clustering which are further used to compute classification accuracy following the procedure mentioned above. We consider this as baseline. The results are tabulated below in Table I
We can see that our proposed method has the best performance, as it can capture the important differential information needed for classification. Since diffusion maps capture both shared and differential features, and entire data has all the information, their performance poor compared to DISC. Elastic Net has the least accuracy because it is designed for regression setup but this is classification problem. Elastic Net-logistic has better performance over Elastic Net as we use cross entropy loss function the one used for classification setup. Further, DiSC has better performance than Entire Data as it is designed to capture the differential features. However, DiSC outperformed EN-logistic as it is designed to extract groups of differential features unlike EN-logistic which just extracts all the differential features as single group, especially when those features have similar effect on the classification problem. Note in App. E we include an additional experiment pairwise
8

---

August
September
October
November
b)
August
Sestember
October
Noverbee
Dic
October change
DM coecchanging
8075
Figure 4: Hyperspectral imaging averaged across channels (a). Three clusters features (white, red and blue) formed from DiSC (b) and Diffusion Maps for changing data (c).
classification of MNIST digits which also includes more details about the choice of hyper-parameee for each of these methods.
Entire Data
Diffusion Maps
EN
EN-logistic
DiSC (Ours)
Test Accuracy(%))
76.23
87.42
69.96
82.42
89.75
Table I: Classification performance on MNIST using DiSC and other competitive approaches.
4.3
Hyperspectral imagery
We apply DiSC to a hyperspectral imagery change detection dataset [12], consisting of hyperspectral images of a particular scene that were captured during different weather conditions, lighting con- ditions, and across four different months of the year (August, September, October and November). Each hyperspectral image is captured at resolution of 100 100 pixels and 124 different bands. denote these by Xa Xxe,, X and X Bov These images consist of a metal frame, grass and trees in the background, 'Oetober-change" and denoted Xoctee was captured in October, in which an added object, a tarp, was added object, albeit various other
shown in Fig.
An additional hyperspectral image, referred to as
included in the scene, Fig. 44] The goal is to detect the tarp aforementioned different conditions during which the image is captured.
We consider X E {X""", X X X"__X_ _X"M) and X X and compute the differential vectors for these four pairs of datasets. Note that this similar to the toy problem presented Sec. and the theoretical analysis in Sec. 3.3 where group of correlated features in XA (the pixels belonging to the grass) are divided into two groups of correlated features in X (grass and tarp). With the addition of the tarp, the pixels belonging to the tarp remain correlated but their connectivity with the other pixels the grass is lost. The differential features X identify the tarp, see App. Fig.
We pick the top four significant differential vectors of X and perform k-means clustering these with k=3. Figure (b) shows these three feature clusters for the four pairs of datasets. The tarp is revealed as a dominant cluster in all months. We compare our results with Diffusion maps for changing data (DM-changing data) [8] spectral approach designed capture differences between two conditions, which introduces distance metric that measures the distance between diffusion maps calculated on a dataset that changes over time. We compute this pixel-wise distance between x and X and cluster the pixels into 3 groups based on this distance. These clusters are illustrated Figure This approach is much more affected by the acquisition conditions, For example: weather and lighting, than our approach, it groups additional objects that have not changed along with the tarp. Finally, DiSC performs better than DM-changing data the presence of added noise (see Appendix[E)
4.4 IMRI
We assess the performance of DiSC in identifying groups of brain parcels with correlated BOLD activity working memory task from Human Connectome Project [39] where subjects executed interleaved blocks of O--acck and 2-back working memory tasks. In these tasks, subjects are instructed to monitor a sequence of visual items and to respond whenever a presented item the same as the one previously presented 2 items ago (2-back) predetermined item (0-back). This fMRI

---

dataset consists of 515 subjects (subjects with high motion or incomplete data were removed), and a mhole-brain, functional atlas [4] was used to extract time-courses from p 268 brain parcels. Dataset X is composed of all blocks from the O-bacck task and X B is composed of all blocks from the 2-back task.
For each subject we calculated the top 2 dif- fusion maps eigenvectors as well as the top
(Ad))
kMb
differential features for each dataset, and aver- age these across all subjects. Fig. []] displays the correlation of each of the averaged vectors with indicator vectors for 10 canonical brain net- works [15]. Results show that diffusion maps is mainly correlated with visual networks, while the differential vector for the ()-acck task being most correlated with the visual II network. On the other hand, the differential vector for the 2-back task is most correlated with the frontal- parietal network, which has been shown to be
2011
6:11
1012
2814
EDW
2013
0003
6:00
9409
7377
CCM
60L1
LAN
Mob
6001
meriial Frental
fronbel pantees
ectkort Moide
mosbor
vissal ansecaaion
ofter dericca
audicettenl
creebsluum
predictive of working memory performance [2]. Thus, opposed to diffusion maps, DiSC re- veals that the 2-back task incorporates more high-level cognitive regions (e.g., prefrontal) compared to the O-back task which has lower cognitive load [18 19].
Figure 5: Canonical correlations of subject- averaged diffusion maps and differential features with 10 canonical brain networks for fMRI data of O-back (task A) and 2-back (task B) working memory tasks.
5 Discussion and future work
In this paper we introduced DiSC, a spectral approach for finding differential features between two or more datasets. We demonstrate the results of our model on various synthetic and real-world datasets and show that DiSC extracts better differential features as compared to the competing techniques. We also show the experimental results on more than two datasets. One limitation of our method is that it addresses only differences in "connectivity". values themselves. Another limitation is the choice of the hyperparameters, d and d.. High values would result in extracting noise or nuisance features as the differential features, and low values might not detect the essential differential features. Finally, the problem of "redundant" eigenvectors [I]] arising in spectral clustering and manifold learning may further complicate choosing the correct dimensionality. This can be mitigated by using redundatt eigenvectors 3 which we will explore in future work.
correlation, between features, not the feature
6 Acknowledgements
This research was partially supported by a Simons Foundation Pilot Award (876513SPI) and NSF award 2217058. 1MRI data were provided by the Human Connectome Project, WU-MinnConsortiun (Principal Investigators: David Van Essen and Kamil Ugurbil; 1111M0549 1657) funded by the 16 NIH Institutes and Centers that support the NIH Blueprint for Neuroscience Research. The authors thank Siyuan Gao for preprocessing of the fMRI dataset and for valuable discussions.
References
[1] Emmanuel Abbe, Afonso S Bandeira, and Georgina Hall. Exact recovery in the stochastic block model. IEEE Transactions on information theory, 62(1):471-45) 487, 2015.
[2] Emily W Avery, Kwangsun Yoo, Monica D Rosenberg, Abigail S Greene, Siyuan Gao, Duk L Na, Dustin Scheinost, Todd R Constable, and Marvin M Chun. Distributed patterns of functional connectivity predict working memory performance in novel healthy and memory-impaire individuals. Journal of cognitive neuroscience, 32(2):241-255, 2020.
[3] Yochai Blau and Tomer Michaeli. Non-redundant spectral dimensionality reduction. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 256-271. 2. Springer, 2017.
10

---

[4] Malgorzata Bogdan, Ewout van den Berg, Weijie Su, and Emmanuel Candes. Statistical estimation and testing via the sorted norm. arXiv preprint arXiv:1310.1 2013.
[5] Howard D Bondell and Brian J Reich. Simultaneous regression shrinkage, variable selection, and supervised clustering of predictors with OSCAR. Biometrics, 64(1):115-123, 2008.
[6] R. Caye Daudt, B. Le Saux, A. Boulch, and Y. Gousseau. Urban change detection for multispec- tral earth observation using convolutional neural networks. In IEEE International Geoscience and Remote Sensing Symposium (IGARSS), July 2018
[7] David Cohen, Tal Shnitzer, Yuval Kluger, and Ronen Talmon. Manifest: Manifold-basee feature selection for small data sets, 2022. URL htttss//aaxiv wtt.aaawww....aaaaa/eae
08574
[8] Ronald R Coifiaan and Matthew J Hirn. Diffusion maps for changing data. Applied and computational harmonic analysis, 36(1):79-107, 2014.
[9] Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, +1(1):5-30, 2006.
[10] Jiang Dong, Dafang Zhuang, Yaohuan Huang, and Jingying Fu. Advances in multi-sensor data fusion: Algorithms and applications. Sensors, 9(10) 2009.
[11] Carmeline J Dsilva, Ronen Talmon, Ronald Coifman, and Ioannis G Kevrekidis. Parsimonious representation of nonlinear dynamical systems through manifold learning: A chemotaxis case study. Applied and Computational Harmonic Analysis, 44(3):759- 773, 2018.
[12] Michael T Eismann, Joseph Meola, and Russell C Hardie. Hyperspectral change detection in the presence of diurnal and seasonal variations. JEEE Transactions Geoscience and Remote Sensing, 46(1):237-249, 2007.
[13] Michael Elad. Sparse and redundant representations: from theory applications in signal and image processing, volume 2, chapter Prologue, pages 3-15. Springer, 2010.
[14] Mario Figueiredo and Robert Nowak. Ordered weighted I regularized regression with strongly correlated covariates: Theoretical aspects. Artificial Intelligence and Statistics, pages 930- 938. PMLR, 2016.
[15] Emily S Finn, Xilin Shen, Dustin Scheinost, Monica Rosenberg, Jessica Huang. Marvin M Chun, Xenophon Papademetris, and R Todd Constable. Functional connectome fingerprinting: identifying individuals using patterns of brain connectivity. Nature neuroscience, 18(11): 1664-1671, 2015.
[16] Ronald A Fisher. The of multiple measurements in taxonomic problems. Annals of eugenics, 1728:179-188, 1936.
[17] Keinosuke Fukunaga and Warren LG Koontz. Application of the Karhunen-LLoee expansion to feature selection and ordering. IEEE Transactions on computers, 100(4):311-318, 1970.
[18] Siyuan Gao, Gal Mishne, and Dustin Scheinost. A hierarchical manifold learning framework for high-dimensional neuroimaging data. In International Conference on Information Processing in Medical Imaging, pages 631-643. Springer, 2019.
[19] Siyuan Gao, Gal Mishne, and Dustin Scheinost. Nonlinear manifold learning in functional magnetic resonance imaging uncovers a low-dimensional space of brain dynamics. Human brain mapping, 42(14):4511) (1:44))550-5524 2021.
[20] Sunil Kumar Gupta, Dinh Phung, Brett Adams, and Svetha Venkatesh. A matrix factorization framework for jointly analyzing multiple nonnegative data sources. In Data mining for service, pages 151-170. Springer, 2014.
[21] Sibylle Hess and Katharina Morik. C-salt: Mining class-specific alterations in boolean matrix factorization. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 547-563. Springer, 2017.
11

---

[22] Che-Wee Huang and Shrikanth Narayanan. Comparison of feature-level and kernl-level data fusion methods in sentirsensory fall detection. In 2016 IEEE 18th International Workshop on Multimedia Signal Processing (MMSP), pages 1-6. IEEE, 2016.
[23] Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010.
URL http:
//yann. 1ecun. com/ wwt.eoommmmmmceeeeeeo exxp/mnis/////////m
[24] Roy R Lederman and Ronen Talmon. Learning the geometry of common latent variables using alternating-diffun diffusion. Applied and Computational Harmonic Analysis, 44(3):509 536, 2018.
[25] Yuan Li, Benjamin Mark, Garvesh Raskutti, and Rebecca Willett. Graph- regularization for regression problems with highly-correlated designs. In 2018 IEEE Globul Conference on Signal and Information Processing (GlobalSIP), pages 740-742. IEEE, 2018.
[26] Ofir Lindenbaum, Arie Yeredor, Moshe Salhov, and Amir Averbuch. Multi-view diffusion maps. Information Fusion, 55:127-149, 2020.
[27] Tong Meng, Xuyang Jing, Zheng Yan, and Witold Pedrycz. A survey on machine learning for data fusion. Information Fusion, 17:115-1299 2020.
[28] Panagiotis Moutafis, Mengjun Leng, and Ioannis A. Kakadiaris. An overview and empirical comparison of distance metric learning methods. IEEE Transactions on Cybereticss 47(3): 612-625, 2017. doi: 111900YB..201..2250
[29] Boaz Nadler, Stephane Lafon, Ioannis Kevrekidis, and Ronald Coifman. Diffusion maps, spec- tral clustering and eigenfunctions of fokker-planck operators. Advances in neural information processing systems, 18, 2005.
[30] Boaz Nadler, Stéphane Lafon, Ronald R Coifman, and Ioannis G Kevrekidis. Diffusion maps, spectral clustering and reaction coordinates of dynamical systems. Applied and Computational Harmonic Analysis, 21(1): 13-127, 2006.
[31] S Ochilov, MS Alam, and A Bal. Fukunaga-koomi koontz transform based dimensionality reduction for hyperspectral imagery. In Algorithmms and Technologies for Multispectral, Hyperspectral, and Uttrappectrll Imagery XII, volume 6233, pages 829-836 SPIE, 2006.
[32] Alok Sharma, Kuldip K Paliwal, Seiya Imoto, and Satoru Miyano. A feature selection method using improved regularized linear discriminant analysis. Machine vision and applications, 25 (3):775-786, 2014.
[33] Yiyuan She. Sparse regression with exact clustering. Stanford University, 2008.
[34] Xilin Shen, Fuyuze Tokoglu, Xenios Papademetris, and R Todd Constable. Groupwise whole- brain parcellation from resting-state fMRI data for network node identification. Neuroimage, 82:403-415, 2013.
[35] Tal Shnitzer, Mirela Ben-Chen, Leonidas Guibas, Ronen Talmon, and Hau- Hau-Ticng Wu, Recover- ing hidden components in multimodal data with composite diffusion operators. SIAM Journal on Mathematics of Data Science, 1(3):588-8) (1688-666,1110 2019.
[36] Fengxi Song, Dayong Mei, and Hongfeng Li. Feature selection based on linear discrimi- nant analysis. In 2010 international conference on intelligent system design and engineering application, volume 1, pages 746-749. IEEE, 2010.
[37] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):667-888, 1996.
[38] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of machine learning research, 9(11), 2008
[39] David C Van Essen, Stephen M Smith, Deanna M Barch, Timothy EJ Behrens, Essa Yacoub, Kamil Ugurbil, Wu-Minn HCP Consortium, et al. The WU-Minn human connectome project: an overview, Neuroimage, 80:62-79, 2013.
12

---

[40] Roman Vershynin. High-dimensionadl probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[41] Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395-416. 2007.
[42] Daniela M Witten, Ali Shojaie, and Fan Zhang. The cluster elastic net for high-dimensional regression with unknown variable grouping. Technometrics, 56(1):112-122, 2014.
[43] Li Xiao, Julia M Stephen, Tony W Wilson, Vince D Calhoun, and Yu-Ping Wang. Alternating diffusion map based fusion of multimodal brain connectivity networks for IQ prediction. IEEE Transactions on Biomedical Engineering, 66(8))2140-2151, 2018.
[44] Yutaro Yamada, Ofir Lindenbaum, Sahand Negahban, and Yuval Kluger. Feature selection using stochastic gates. International Conference on Machine Learning, pages 10648-10659. PMLR, 2020.
[45] Yi Yu, Tengyao Wang. and Richard J Samworth. A useful variant of the for statisticians. Biometrika, 102(():315-23) 2015.
theorem
[46] Luke Zappia, Belinda Phipson, and Alicia Oshlack. Splatter: simulation of single-cell ma sequencing data. Genome biology, 18(1):1-15, 2017.
[47] Lihi Zelnik-Manor and Pietro Perona. Self-tuning spectral clustering. Advances neural information processing systems, 17, 2004.
[48] Jun Zhao, Ariel Jaffe, Henry Li, Ofrr Lindenbaum, Esen Sefik, Ruaidhrí Jackson, Xiuyuan Cheng, Richard Flavell, and Yuval Kluger. Detection of differentially abundant cell sub- populations in scrna-seq data. Proceedings of the National Academy of Sciences, 118(22), 2021.
[49] Hui Zou and Trevor Hastie. Regularization and variable selection via the clastic net. Journal of the royal statistical society: series B (statistical methodology), 67(2)301-330,, 2005.
13

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A] You strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data proprietary.
Did you include the license the code and datasets? [N/A]
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
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 We assume that difference between the two datasets are represented in the differences in their connectivity.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work does not have any direct potential negative societal impacts. (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]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We will include
the code in the supplemental material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No] Our algorithm is not computation expensive.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [No] We used open source data
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [No] We using publicly available and vastly used datasets.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe 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 participant compensation? [N/A]
14


Reviews:
[{"review_id": "uIsU8WPM8U", "reviewer": "Reviewer_FFG2", "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.", "questions": "See weaknesses above.", "limitations": "none", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The experimental results are good;\nWeaknesses:\n1. The proposed work makes me confused after I read the paper. It is not clear what the proposed method aims for, feature selection?\n2. If the proposed work aims for feature selection, why uses two datasets A and B?\n3. 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?", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "iXbQ0RbbVBG", "reviewer": "Reviewer_SwNk", "summary": "This paper proposes a closed-form spectral solution to the problem of selecting feature selection that maximize the difference between two datasets.\n\nThis 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.\n", "questions": "Can you clarify the selection of the baselines in the paper?\n", "limitations": "N\\A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strengths]\n\nThe 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.\n\nTheoretical 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.\n\n[Weaknesses]\n\nThe 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.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "V2eRCf5PxoF", "reviewer": "Reviewer_T7Zb", "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).\n\nThe 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.\n\nThe paper concludes with some interesting applications, showing potential for practical relevance of the method.\n\n#### Update following author rebuttal and in light of other reviewers' comments\nI 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.", "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?\n- 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?\n- 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?\n- What exactly does \"with high probability\" mean? I am sure it is not difficult to bring in this probability explicitly.\n- 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?\n\n\n\nI will also include in this section a few editorial comments/corrections\n- LASSO is an acronym, and so is usually written capitalised, and not as Lasso.\n- Notation of l-p norms should be consistent. Sometimes these are in math font, while other times not.\n- line 64: \"... identify groupS...\"\n- The term \"independent components\" carries a specific meaning in feature extraction, and I would suggest choosing a different phrase.\n- Line 125: peviously \"mincut\" was \"minimum-cut\" \n- 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\"\n- 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.\n- The two data sets are sometimes denoted X_A and X_B and sometimes X^A and X^B\n- \"algorithm 1\" should be \"Algorithm 1\"\n- the bracket in line 227 does not close.\n", "limitations": "I do not see any potential for foreseeable negative societal impact arising from the work.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- 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).\n- The presentation is fairly clear, and the paper well written for the most part.\n\nWeaknesses:\n- 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?\n\n- I will point out other minor issues in the following section, via queries.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GqOPJtIfak", "reviewer": "Reviewer_5Abs", "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.\n", "questions": "As explained in Sec. \"Weaknesses\", we summarize the expected\nimprovements here:\n\n1. More understanding of (7) in mathematics. \n\n2. More toy examples or benchmark that clear our concerns.\n", "limitations": "We appreciate the authors' work that could potentially make a contribution. And we do not foresee any potential negative societal impact.\n", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. 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.\n\n2. 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.\n\nWeaknesses:\n\n1. 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)).\n\n2. 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.\n\nStrengths(?) or Weaknesses(?):\nSec. 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.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept