Spectral Self-supervised Feature Selection
Authors: Daniel Segal
Ofir Lindenbaum
Ariel Jaffe
Venue: Accepted by TMLR ()

Abstract: Choosing a meaningful subset of features from high-dimensional observations in unsupervised settings can greatly enhance the accuracy of downstream analysis tasks, such as clustering or dimensionality reduction, and provide valuable insights into the sources of heterogeneity in a given dataset. In this paper, we propose a self-supervised graph-based approach for unsupervised feature selection. Our method's core involves computing robust pseudo-labels by applying simple processing steps to the graph Laplacian's eigenvectors. The subset of eigenvectors used for computing pseudo-labels is chosen based on a model stability criterion. We then measure the importance of each feature by training a surrogate model to predict the pseudo-labels from the observations. Our approach is shown to be robust to challenging scenarios, such as the presence of outliers and complex substructures. We demonstrate the effectiveness of our method through experiments on real-world datasets from multiple domains, with a particular emphasis on biological datasets.

Published in Transactions on Machine Learning Research (12/2024)
Spectral Self-supervised Feature Selection
Daniel Segal
segaldanniel22@@mail..oo
Hebrew University
Ofir Lindenbaum Bar Ilan University
ofirlin&gmmail com
Ariel Jaffe Hebrew University
ariel.joffe @emeeaillemmaii....o www.laaaaaa..oooooo ac.il
Reviewed on OpenReview: https: // openreview. net/ forum? id= t0EJ10d9Lg
Abstract
Choosing meaningful subset of features from high-dimensional observations unsuper- vised settings can greatly enhance the accuracy of downstream analysis tasks, such as clustering or dimensionality reduction, and provide valuable insights into the sources of heterogeneity in given dataset. In this paper, propose self-supervised graph-based approach for unsupervised feature selection. Our method's core involves computing robust pseudo-labels by applying simple processing steps to the graph Laplacian's eigenvectors. The subset of eigenvectors used for computing pseudo-labels is chosen based on a model stability criterion. We then measure the importance of each feature by training surrogate model predict the pscudo-labels from the observations. Our approach is shown to be robust lo challenging scenarios, such as the presence of outliers and complex substructures. We demonstrate the effectiveness of our method through experiments real-world datasets from multiple domains, with particular emphasis on biological datascts.
1 Introduction
Improvements in sampling technology enable scientists across many disciplines to acquire numerous variables from biological or physical systems. One of the critical challenges in real-world scientific data is the presence of noisy, information-poor, or nuisance features. While such features could be mildly harmful to supervisod learning, they could dramatically affect the outcome of downstream analysis tasks (e.g., clustering or manifold learning) in unsupervised settings (Mahdavi et al. 2019). There is thus growing need for unsupervised feature selection schemes that enhance latent signals of interest by removing nuisance variables and thus advance reliable data-driven scientific discovery.
Unsupervised Feature Selection (UFS) methods are designed to identify set of informative features that can improve the outcome of downstream analysis tasks such as clustering and manifold learning, With the lack of labels, however, selecting features becomes highly challenging since the downstream task cannot be used to drive the selection of features. As an alternative, most UFS methods use a label-free criterion that correlates with the downstream task. For instance, many UFS schemes rely on reconstruction prior (Li et al. 2017) and seek subset of features that can be used to reconstruct the entire datasel. as accurately possible. Several works use Autoencoders (AE) to learn reduced representation of the data while applying sparsification penalty to force the AE to remove redundant features. This idea was implemented with several types of sparsity-induccin regularizers, including ε2 based (Channda and Sharma
2015 Han et al.
2018), relaxed to [Balin et al. 2019: Shaham et al. 2022 Svirsky and Lindenbaum) and more.
One of the most commonly used criteria for UFS is feature smoothness. A common hypothesis that the structure of interest, such as clusters or a manifold, can be captured using a graph representation(Ne al. 2001). The smoothness of features is measured using the Laplacian Score (T.S) (He et. al. 2005), which is

---

Published in Transactions on Machine Learning Research (12/2024)
V.
(a)
(b)
(c)
(d)
(e)
Sarples
Survaiia
a(fi)
eelaccinn
Eigen- vector
Eigen-
1D Clustering
Facture Selecton
vectors
Selection
s(fa)
Sempla
V1
s(4a)
Saroles
Serfts
Sampinn
Figure Illustration of SSFS. Panel (a) shows tSNE scatter plot of noisy MNIST digits (3, 6, 8). Panel (b) presents the six leading eigenvectors computed based the graph Laplacian of the data. Samples are ordered according to the identity of the digit. (c) We apply the k-medoids algorithm to compute pseudo- labels y:- These are presented as colors overlayed on the eigenvectors.
(d) We select the three eigenvectors whose pseudo-labels are the most "stable" with respect to several prediction models (see Section 3.2). (e)
For each data feature we estimate its importance score for each of the selected eigenvectors (sce Scction 3.3 (I) We aggregate the feature scores across eigenvectors.
equal to the Rayleigh quotient of normalized feature vector and the graph Laplacian. A feature that is smooth with respect to the graph is considered to be associated with the primary underlying data structures. There are many other UFS methods that use a graph to select informative features Li et al. (2018); Roffo et al.
(2017;; Zhu et al. 2017 2020); Xie et al. (2023). (Li et al. 2012) derived Nonnegative Discriminative Feature
Selection (NDFS). : which performs feature selection and spectral clustering simultaneously. Its extension Li
and Tang (0055 adds a loss term to prevent the joint selection of correlated fcatures.
Embedded unsupervised feature selection schemes aim to cluster the data while simultaneously removing irrelevant features. Examples include Wang et al. (2015), which performs the selection directly on the clustering matrix, and Zhu and Yangl (2018), which learns feature weights while maximizing the distance between clusters. In recent years, several works have derived self-supervised learning methods for feature selection. The key idea is to design a supervised type learning task with pseudo-labels that do not require human annotation. A seminal work based on this paradigm is Multi-Cluster Feature Selection (MCFS) (Cai ct al. 2010). MCFS uses the eigenvectors of the graph Laplacian as pscudo-labels and learns the informative Teatures by optimizing over an & regularized least squares problem. More recently, Lee et al. 2021 used self-supervision with correlated random gates to enhance the performance of feature selection.
In this work, we present spectral self-supervised scheme for feature selection. Our main innovation is to properly select subset of Laplacian eigenvectors by multi-stage approach. Firstly, we generate robust discrete pscudo-labels from the cigenvectors and filter them based on stability measure. Next, we fit flexible surrogale classification models on the selected eigenvectors and query the models for feature scores. Using these components, we can identify informative features that are effective for clustering on real-world datascts.
2 Preliminaries
2.1 Laplacian score and irvresentation-baaee feature selection
Generating a graph-basee representation for a group of high-dimensional observations has become a common practice for unsupervised learning tasks. In manifold learning, methods such as ISOMAPS (Tenenbaum al.) 2000), LLE (Roweis and Saul 2000). Laplacian eigenmaps (Belkin and Niyogi 2003). and diffusion maps (Coimaan and Lafon 2006) compute low-dimensional representation that is associated with the manifold's
2

---

Published in Transactions on Machine Learning Research (12/2024)
latent structure. In spectral clustering, set of points is partitioned by applying the k-means algorithm to the leading Laplacian eigenvectors (gg et al. 2001).
In graph methods, each node v; corresponds to one of the observations æ; E Rs. The weight Wij between two nodes Us is computed based on some kernel function K( xy). For example, the popular Gaussian kernel equal to,
||=; - x,11
((x;, 1z) exp
20²
Where the parameter a determines the bandwidth of the kernel function. Let D be diagonal matrix with the degree each node in the diagonal, such that D2 = EE Wiz. The unnormalized graph Laplacian matrix is equal to L = D W. For any vector v E R" we have the following equality (Von Luxburg, 2007),
va L
1 Σ (
(u)
(u 106-1))
W,.,
(1)
2
The quadratic form in equation ! gives rise a notion of graph smoothness. (Ricaud et al., 2013). A vector is smooth with respect to graph if it has similar values pairs of nodes connected with an edge with significant weight. This notion underlies the Laplacian score suggested a measure for unsupervised feature selection (He et al. 2005). Let fm E R" denote the values of the m-th feature for all observations. The Laplacian score 8m is equal to,
2019 Shuman
1 (fma Ww.) 2 1.
8m ff
(2)
A low score indicates that a feature is smooth with respect to the computed graph and thus strongly associated with the latent structure of the high-dimensional data 2ı,..., Z.. The notion of the Laplacian
score has been the basis of several other feature selection methods as well (Lindenbaum et al. 2021 Shaham
eet al. 2022 Zhu et al. 2012).
Let v., A denote the i-th smallest eigenvector and eigenvalue of the Laplacian L. A slightly different interpretation of equation 2 that the score for each feature is equal a weighted sum of its correlation with the eigenvectors, such that
8m Σ A(
A potential drawback of the Laplacian score is its dependence on all cigenvectors, which may reduce its stability in measuring a feature's importance to the data's main structures. To overcome this limitation, Zhao and Liu (2007) derived an alternative score based only on feature's correlation to the leading Laplacian cigenvectors. A related, more sophisticated approach is Multi-Clustor Feature Sclection (MCFS) (Cai et al., 2010), which computes the solutions to the generalized eigenvector problem Lu = ADv. The leading eigenvectors are then used as pseudo-labels for a regression task with I regularization. Specifically, MCFS applies Least Angle Regression (LARS) (Efron et al., 2004) to obtain, for each leading eigenvector v., a sparse vector of cocfficients 8 E IP. The feature score is set the maximum over the absolute values of the coefficients computed from the leading eigenvectors, 8y = max, 13%). The output of MCFS is the set of features with the highest score. In the next section, we derive Spectral Self-supervised Feature Selection (SSFS), which improves upon the MCFS algorithm in several critical aspects.
3 Spectral Self-supervised Feature Selection
3.1 Rationale
As title suggests, MCFS aims to uncover features that scparate clusters in the data. Let us consider an ideal case where the observations are partitioned into & well-separated clusters, denoted Ai....,Ap such that the weight matrix Wyy 0 if æ; my in separate clusters. Let et denote indicator vector for cluster
3

---

Published in Transactions on Machine Learning Research (12/2024)
Values
Values
Values
Values
Samples
Samples
Samples
Samples
V4
Values
Values
Values
Values
Samples
Samples
Samples
Samples
(a) Prostate-GE cigenvectors.
(b) TOX-171 eigenvectors.
Figure 2: The first four Laplacian eigenvectors of two real datasets. Samples are sorted according to the class label and colored by the outcome of one-dimensional k-medoids per eigenvector. The vertical bar indicates the separation between the classes. In Prostate-GE. V2 is the most informative to the class labels, and an outlier can be seen on the upper left in the third and fourth eigenvectors. In TOX-171, 03 is most informative to the class labels than 22
such that
jEA, of - otherwise,
1/ 1/VIA
where |A,| denotes the size of cluster A, In this seenario, the zero cigenvalue of the graph Laplacian has multiplicity k and the corresponding eigenvectors are equal, to a rotation malrix, to a matrix E Baxd whose columns are equal to e e'....,eet et In this ideal setting, the & leading eigenvectors are indeed suitable for use as pseudo-labels for the feature selection task. Thus, the MCFS algorithm should provide highly informative features in terms of cluster separation.
In most applications, however, cluster separation is far from perfect, and the of leading eigenvectors may be suboptimal. Here are some common scenarios: 1) High-dimensional datasets may contain substructures in top eigenvectors, while the main structure of interest appears deeper in the spectrum. For illustration, consider the MNIST dataset visualized via t-SNE in Figure [ The data contains images of 3, 6 and 8. Figure D shows the elements of the six leading cigenvectors of the graph Laplacian matrix, sorted by their correspouding digits. The leading eigenvector shows a clear gap between images of digit 6 and the rest. of the data. However, there no clear separation between digits and 8. Indeed, the next eigenvector is not associated with such separation. Applying feature selection with this cigenvector may produce spurious features irrelevant to separating the two digits. This scenario is prevalent in the real datasets used in the experimental section. For example, Figure 2a shows four eigenvectors of graph computed from observations containing the genetic expression data from prostate cancer patients and controls (Singh et al. 2002). The leading two eigenvectors, however, are not associated with the patient-control separation.
2) The leading cigenvectors may be affected by outliers. For example, an eigenvector may indicate a small group of outliers separated from the rest of the data. This phenomenon can also be seen in the third and fourth vectors of the Prostate-GE example in Figure 2a] While the fourth eigenvector separates the categories, it is corrupted by outliers and, hence, unsuitable for use pseudo-labels in a classical regression task, as it might highlight features associated with the outlicrs.
3) The relation between important features and the separation of clusters may be highly non-linear. In such cases, applying linear regression models to obtain feature scores may be too restrictive.
Motivated by the above scenarios, we derive Spectral Self-supervised Feature Selection (SSFS). We explain our approach in detail in the following sections.
4

---

Published in Transactions on Machine Learning Research (12/2024)
3.2 Eigenvector processing and selection
Generating binary labels. Given the Laplacian eigenvectors V (#1,..., va), goal is to generate pseudo-labels that are highly informative to the cluster separation in the data. To that end, for each cigenvector Us we compute a binary label vector y; (pscudo-labels) by applying one-dimensional k-medoids algorithm (Kaulman and Rousseeuw [990) to the elements of 0;- In contrast. to k-means, in k-medoids, the cluster centers are set to one of the input points, which makes the algorithm robust to outliers. In Figure 2 the eigenvectors are colored according to the output of the k-medoids. After binarization, the fourth eigenvector of the Prostate- dataset is highly indicative of the category. The feature selection is thus based a classification rather than regression task, which is more aligned with selecting features for clustering. In Section 5.2 we show the impact of the binarization step multiple real-world datasets.
Eigenvector selection. Selecting &o eigenvectors according to their eigenvalues may be unstable in cases where the eigenvalues exhibit a small spectral gap. We derive a robust criterion for selecting informative eigenvectors that is based on the stability of a model learned for each vector. Formally, we consider a surrogate model features. The feature scores are non-negative and their sum is normalized to one. For example, can be the logistic regression model h(x)) (B"xx) æ)). In that case, a natural score function is the absolute value of the coelficient vector B. For each eigenvector vi, we train model h; on B (non-mulually exclusive) subsets of the input data X and the pseudo-labels y, We then estimate the variance of the feature score function, for every feature m E p}:
+ I,, and feature score function s(h) E IR,, where p denotes the number of
B B Σ
Var(sm (h,))
sm (
8m (
This procedure is similar (though not identical) to the Delete-d Jackknife method for variance estimation (Shao and Wu 1989). We keep, as pseudo-labels, the k binarized eigenvectors with the lowest sum of variance, S, E Var(sm. (h+))- We denote the set of selected eigenvectors by J. A pseudo-code for the pseudo-labels generation and eigenvector selection appears in Algorithm [
3.3 Feature selection
For the feature selection step, we train & models, denoted {fr i 1}. to predict the selected binary pseudo- labels based on the original data. Similarly to the eigenvector selection step, each model is associated with a feature score function sff). The features are then scored according to the following maximum criterion,
score(m) max sm (fi).
Finally, the features are ranked by their scores, and the top-ranked features are selected for the subsequent analysis. The choice of model for this step can differ from that used in the eigenvector selection step, allowing for flexibility in the modeling approach (see Section 3.4 for details). Pscudo-code for SSFS appears in Algorithm
3.4 Choice of Surrogate Models
Our algorithu is compatible with any supervised model capable of providing feature importance scores. We combine the structural information from the graph Laplacian with the capabilities of various supervised models for unsupevvised feature selection. Empirical evidence supports the use of more complex models such as Gradient- -addient-Boosted Decision Trees for various complex, real-world datascts (McElfresh et al.) 2023: Chen and Guestrin 2016). These models are capable of capturing complex nonlinear relationships, which we leverage by training them on pseudo-labels derived from the Laplacian's eigenvectors. For example, for eigenvector sclection, one can use a simple logistic regression model for fast training on the resampling procedure and more complex gradient boosting model such as XGBoost (Chen and Guestrin 2016) for the feature selection step.
5

---

Published in Transactions on Machine Learning Research (12/2024)
Algorithm Pseudo-code for Eigenvector Selection and Pseudo-labels Generation
Input: Dataset X E RRxx (with n samples and p fealures), number of eigenvectors select k, number of eigenvectors to compute d, surrogate models H {h, i [d]] feature scoring function s F R number of resamples B
1: Initialize an empty list for the pseudo-labels y" and an empty list for the sums of features variance
2: Compute the significant d eigenvectors of the Laplacian of X: (uh,..,,0u)) vd)
3: for i= 1 to do
Binarize the cigenvector v; using k-modoids obtain vy and append y
for b= to B do
Subsample ((X):, )o: (v))) )6) from (X, y²)) Fit the model hiD to ((X),, )n, (wt)) 8: Compute the feature scores Sm (h4.6)
9: end for
10: for m = 1 to do
11:
Estimate the variance of the m-th feature score:
1
Var(sm (hi)) B
Sm (he,b) - 3m (h:))
bm
12:
end for
13:
= >
Var(sm (l:))
14: Su
15: end for
16: Select the indices of the l smallest elements S and store in 7
17: return y",
Algorithm 2 Pseudo-code for Spectral Self-supervised Feature Selection (SSFS)
Input:
Dataset X E Rnxp (with n samples and p features) number of eigenvectors to select k, number of eigenvectors to compute d, surrogate eigenvector selection models H (h, i [4], surrogate feature selection models F= {fr [d], feature scoring function s: F RP, number of resamples B, number of features select É.
1: Apply Algorithm [ to obtain the pseudo-labels and the selected eigenvectors:
y" I EigenvectorSelection/ k d, H, 8,
2: for in / do
3: Fit the model f, on (X, yf)
Calculate the feature scores s(fi)
Normalize the feature scores such that their sum is one end for
for = 1 to do
8: Compute the final score for the m-th feature:
score(m) = max (fi)
iEl
end for
10: return list of & features with the highest score.
4 The importance of proper selection of eigenvectors: analysis of the product manifold model
As described in Section 3.1 the principle of selecting the leading Laplacian eigenvectors pseudo-labels is motivated by the case of highly separable clusters, where observations in different clusters have very low

---

Published in Transactions on Machine Learning Research (12/2024)
connectivity between them. In many cases, the separation between meaningful states (ie., biological medical conditions) may not be that clear. To illustrate this point, consider the MNIST example in Figure While images with the digit 6 constitute a cluster, the separation between digits 8 and 3 are not clearly separated. Figure Ba shows a scatter plot of these digits, where each image is located according to its coordinates the third and fourth eigenvectors. Even when considering the most. relevant eigenvectors, there no clear separation between the digits. Instead, the transition between and 8 smooth and depends on the properties of the digits.
To provide insight into the importance of eigenvector selection, we analyze product of manifold model. Our analysis is based on results from two research topics: (i) the convergence, under the manifold assumption, of the Laplacian eigenvectors to the eigenfunctions of the Laplace Beltrami operator associated with the manifold, and (ii) the properties of manifold products. We next provide a brief background on these two topics.
4.1 Convergence of the Laplacian eigenvectors
In many applications, high dimensional observations are assumed to reside close to some manifold M with low intrinsic dimensionality, which we denote by d. Many papers recent docades have analyzod the relation between the Laplacian eigenvectors and the manifold structure Von Luxburg al. (2008): Singer and Wu
2017 García. Trillos et al.] (2020); WWrmell and Reich (2021 Dunson et al.] (2021); 1; Calder and Trillos 2022 More formally, let vs denote the k-th eigenvector of the graph Laplacian, and let 9k denote the k-th
eigenfunction of the Saplace-Beltramy (LB) operator. We usually assume that 9k is normalized such that
J.w Ig (x) u(x)dV(())) 1,
where j is the distribution function over M. Under several assumptions and proper normalization of gk, we have
9k (X).
where (x) is vector of size n containing samples of the function at the rows of the data matrix X.
Let us consider a simple example. Suppose we have n points sampled uniformly at random over the interval [0, 1]. The LB operator over this interval defined as the second derivative, whose eigenfunctions are the harmonic functions given by (z(z) cos cosTk))). Figure g shows the three Laplacian eigenvectors computed with n 10², 1 and 3 103 points. As n n 0e, the vector Up converges to gx(
Here, we use convergence result from Cheng and Wu (2022), derived under the following assumptions: (i) The n observations are generated according to uniform distribution over the manifold, such that u(x)) equals to a constant μ. (ii) Let A denote the eigenvalue associated with the eigenfunction To ensure the stability of the cigenvectors, we assume a spectral gap between the smallest K cigenvalues bounded away from such that,
K-1 min (A++1 X²) 0.
1.5--xp xz 13512//1////// /l2)/en), with a bandwidth On (iii) The graph weights are computed by Gaussian kernel exp(- 11|10-11--00
2000
that satisfies en d/2+2 > Ck log for a constant Ck. The following result from Cheng and Wu
(0022)
guarantees the convergence the Laplacian eigenvectors to samples the LB eigenfunction.
Theorem (Theorem 5.4 of Cheng and Wu (2022)) For n + oo and under assumptions (i)-(1i), with probability larger than 4k"K" (2K +6)+ " the k-th eigenvector vn of the unnormalized Laplacian salisfies
Uk agn (x)|| =((x)) 00))))((1))
logn d/2+1
k K,
(3)
nen
where || and |a| o(1).
We next address the eigenvector structure in case of product-manifold model.

---

Published in Transactions on Machine Learning Research (12/2024)
4.2 The product of manifold model
In a product of two manifolds, denoled M = Mi M2, every point E M is associated with pair of points 21, 22 where æ1 E M1 and #2 E M2. We denote by тi (2))) the canonical projections of a point in M to its corresponding points æ1, 22 in M2, respectively. For example, a 2D rectangle is a product of two 1D manifolds, where Ti (x) and (z(x) select, respectively, the first and second coordinates.
We denote by (1) (z)), (2) (xx) the i-th eigenfunction of the LB operator of , M2, respectively, evaluated at point v, and by 1("), x(2) the corresponding eigenvalues. In a manifold product M M2,,, the eigenfunctions are equal the pointwise product of the cigenfunctions of the LB operator of M1, and the corresponding eigenvalues are equal to the sum of eigenvalues, such that
(2) (T2(2)) (1) (T (x)) 9h (xx(x)) = 9i
(2) Ar 2(1) + A
For simplicity, we denote by UIA the (1, k) eigenvector of the Laplacian matrix, as ordered by A An example of a product of manifolds is illustrated in Figure [b] The figure shows the leading eight cigenvectors of the graph Laplacian. The eigenvectors are indexed by the vector b [t, k). The full details of this example is provided in the next section.
1.00
n = 100
1000
0.75
3000
cos(rx)
Fourth eigenvector
Leading eigenvector
0.00
-0.25
0.50
1.00
Third eigenvector
0.0
0.2
0.4
0.6
0.8
1.0
(a) Noisy MNIST: digits 3 and 8
(b) Convergence eigenvectors for graph on an in- terval
Figure 3: Panel 3a shows scatter plot of the noisy MNIST dataset, containing digits and 8, where each image is located according to its coordinates in the third and fourth eigenvectors. Panel shows the leading eigenvector of a graph computed over points on 1D interval and the leading eigenfunction cos(TTz).
4.3 Considerations for eigenvector selection in a product- product-manifold model
We analyze a setting where the p features can be partitioned into H sets according to their dependencies on a set of latent and independent random variables 0t....0f, with some bounded support. feature fm that depends on 9% consists of samples from smooth transformation 0n Fm, fm- We denote by X the submatrix that contains the foatures associated with 0,. The smoothness of the transformations implics that the rows of (h) constitute random samples from a manifold of intrinsic dimension 1.
Figure 4a shows a 3D scatter plot, where the axis are three such features with values generated by three polynomials of 0, The figure an illustration of a manifold with single intrinsic dimension embedded 3D space. The independence of the latent variables f, implies that the observations æ, RP are samples
from product of H manifolds, each of dimensionality Zhang et al. 2021 He et al. 2023 The canonical
8

---

Published in Transactions on Machine Learning Research (12/2024)
0= (1.00
[2.0]
b=
3.0
2.
10
85
-0.
2.0
0- (1.1)
[4.0]
[4.2)
0.5
0.0
-0.5
0.0
1.0
-1.0
15
1.5
0.5
2.5
0.
25
0
Simulated data
(b) Eigenvectors of the simulated data
Figure 4: Panel (a) illustrates three features of simulated dataset. Each feature is equal to different polynomial of the same random latent variable 0,. Each point in the 3D scatter plot is located according to the values of the three features and colored by the value of 02. Panel (b) shows the eigenvectors of the graph Laplacian matrix. Each point is located according to the value of (01, (0),02) and colored by the value of corresponding element the eight leading eigenvectors. The eigenvectors are indexed by the vector b, whose elements b; determine the eigenvector order in the submanifold M
projection n (*) (x) selects the features associated with the latent variable An According the eigenfunctions properties in equation | the eigenfunctions are equal to the product of eigenfunctions of the submanifolds M(h,, and can thus be indexed by vector of size H, which denote by b N
11
1
9b (x)))
II h=1
9bn
(b) (T
(h) (x))
AB
bb.
(h)
h=1
Let (lh) denote an index vector with elements 9u (h)
e = if = h and otherwise. The first eigenfunctions
are equal to a constant for all submanifolds (h) Thus, The eigenfunctions Jeth are equal to
Ie (x)= 91 (1:) ( II
90 1 (z) Cgi (xth j
(5)
where C is some constant. Importantly, the functions (M) and thus 9a(h), depend only the parameter g(h), We define by & the family of vectors in No that include the indicator vectors e(h) or their integer products (c.g. th) (h( (h( etc.). A similar derivation as in equation 5 shows that for every index vector b E E, the eigenfunction gb depends on only one of the latent variable in 0, 01,...,
On the relevance of features for choosing eigenvectors as pseudo-labels. Our goal is to select a set of features that contains at least one (or more) features from each of the partitions. Such a choice would ensure that the set contains information about all the latent variables. Clearly, this imposes a requirement on the set of pseudo-label vectors: we would like at least one vector of pseudo-labels that is correlated with each latent variable.
It is instructive to consider the asymptotic where properties of manifold products, the eigenvectors converge to gb( (x))). A proper choice of eigenvectors for pscudo-labels would be the set {wae 1 as each of these vectors converges to the samples g (X), and is thus associated with a different latent variable. However, there is no guarantee that these eigenvectors have the smallest. eigenvalues.
and hence according to Theorem 1 and the
9

---

Published in Transactions on Machine Learning Research (12/2024)
Consider for example the case for the data illustrated in Figure 4a Panel (b) shows the leading eight eigenvectors of the graph Laplacian. The leading two eigenvectors are functions of 0, and by choosing them we completely disregard 02 with an obvious impact on the feature selection accuracy. A better choice for pscudo-labels would be the first and third eigenvectors, indexed by e1 and e2. Therefore, we need an improved criterion for selecting eigenvectors lo serve as pseudolabels for the feature selection process. The following theorem, proven in Appendix A.I1 implies that the feature vectors fa are relevant for developing such a criterion.
Theorem We assume that the samples are generated according to our specified latent variable model and that assumptions (1)-(18) are satisfied. Let Si E IK" be normalized, zero mean feature vector associaled with parameter 0g. Then,
log n d/2+1 nen
f.
f - O(cn)
4b $ E.
The theorem is proved via the following two steps. The details of the proof are provided in the appendix.
Step 1: We show that the inner product f gb (X) can be written as the inner product of two random vectors with independent elements. Thus, f. (66())
order 011/11 by standard concentration
inequalities.
Step 2: Combine the convergence of us to (x( with the concentration result of step 1.
Theorem 2 implies that one can use the inner products to avoid selecting less informative eigenvectors that depend on more than one variable. Further guarantees, such as selection of a single vector from each variable, require additional assumptions on the feature values, which we do not make here.
In Algorithm D we compute the normalized measure of stability for the feature scores {sm {sm( (h:))) obtained by the model h, to predict the labels computed from the i-th eigenvector. When the model h, is linear (or generalized linear), the score is strongly related to the simple inner product of Theorem 2 In that case, Thcorem indicates that the inner product between uninformative eigenvectors and all features is close to zero. Thus, we expect the variance (after normalization) to be similar to the variance of random positive noise. The advantage of the stability measure over the simple linear product as an eigenvector selection criterion is that it allows for more flexibility in the choice of model.
2
4.4 Computational Complexity
The computational complexity of our proposed method consists of several key steps. First, constructing the graph representation of the dataset using a Gaussian kernel requires computing pairwise distances between all data points, resulting in a complexity of O(n²p), where n is the number of samples and is the number of features. Following this, the eigendecompositionn of the graph has a complexity of O(n²). This can be reduced by randomized methods to Onndd), since we only require the first. d eigenvectors. Once eigenvectors are computed, we apply the k-modoids algorithm to cluster the cigenvectors and generate pscudo-labels, adding a further complexity of O(dkn²), where k is the number of clusters.
After creating pseudo-labels, trees to evaluate the features. Logistic regression has complexity of O(nd), while gradient-boosted trees, being more complex, scale with O log n), where T is the number of trees. We also use a resampling pro- cedure to estimate the variance of feature importance scores. Each resampling involves training a surrogate model, resulting in an overall complexity of O log logn) for gradient-booste regression. As a result, the overall computational complexity of SSFS mainly influenced by the graph construction and training the surrogate mode, resulting in complexity of O(n2d Bnd).
surrogate models such as logistic regression or gradient- grassent-boosted
boosted decision
trees or O(Bnd) for logistic
10

---

Published in Transactions on Machine Learning Research (12/2024)
5 Experiments
5.1
Evaluation on real world datasets
Data and experiment description. We applied SSFS to eight real-world datascts from various domains. Table 5 Appendix F.2 gives the number of features, samples, and classes in each dataset. All datasets are available online
We compare the performance of our approach the following alternatives: (i) standard Laplacian score (LS)
(He et al. 2005 (ii) Multi-Cluster Feature Selection (MCFS) (Cai et al 2010), (iit) Nonnegative Discrimina-
tive Feature Selection (NDFS), (Li et al. 2012 (iv) Unsupervised Discriminative Feature Selection (UDFS)
Yang et al. 20111, (v) Laplacian Score-regularizer Concrete Autoencoder (LS-CAE) (Shaham et al., 2022)
(vi) Unsupervised Feature Selection Based on Iterative Similarity Graph Factorization and Clustering by
Modularity (KNMFS) OOliveira et al.) 2022) and (vii) a naive baseline, where random selection applied with a different soed for cach number of selected features.
For evaluation, we adopt criterion that is similar to, but not identical to, the one used in prior studies Li et al. 2012 Wang et al., 2015). We select the top 2, 5, 10, 20, 30, 40, 50, 100, 150, 200, 250, and 300 features scored by cach method. Then, we apply k-means 20 times on the selected features and report the average clustering accuracy (along with the standard deviation), computed by CCai el al. 2011
ACC 1 N Σ 8(T(c),44)
where & and are the assigned cluster and true label of the i-th data point, respectively, 5(x, y) the delta function which equals one if x = y and zero otherwise, and represents permutation of the cluster labels, optimized via the Kuhn-Munkres algorithm MMunkres] 1957
Unlike the evaluation approach taken by Wang et al. 2015 Li et al. (012), which entailed grid search over hyper-parameters to report the optimum results for each method, our analysis employed the default hyper- parameters as specified by the respective implementations, including SSFS. This approach aims for a fair comparison to avoid favoring methods that are more sensitive hyper-parameter adjustments. In addition, it acknowledges the practical constraints in unsupervised settings where rrper-parameter tuning is typically infeasible. Such differences in the approach to rrpee-parancter selection could account for discrepancies between the results reported in previous studies and those in our study, See Appendix F.1 for additional details.
Table 1: Average clustering accuracy benchmark datasets along with the standard deviation. The number of selected features yielding the best clustering performance is shown in parentheses, the best result for each dataset highlighted in bold.
Dataset
Random
L8
MCFS
NDFS
UDPS
KNMPS
LS-CAE
SSPS
DOIL20
(2.14)
21.9 ((300)
(7.48::1:33000
63 1.4.22662200
(1.93):35(330)
68.1122.0(300)
64 14.222.11 1300
07.1.1/2 8(300)
GISETTE
70.220.1(150)
70.0200000 20200)
70.72000(3)
58 (4-311.00 (01000
68.122 1(50)
54.820.0:400
70.8:0.0((00)
66.7200.0
Vale
47.855.5/250
43.9925522 20300)
(4.139.9:500)
43 (1-55225(050)
63.8222.55 5(50)
(7.2224.36300)
46.22 66100)
50.3:22.5(
TOX-171
(1255)
51.3e (.05))
54.5220.3(5)
47.520.1(1500
10.25:3.51 (122:3.5(25))
45:1333.:220)
50. 10.12555(200)
59.41:2.5(
ALLAME
73.21617(3300)
72.2:3:0002000
75.01.0
(6.61.0.7(2)
3(50)
59.91-99 2500)
15.41:3.2(100)
Prostate-CIE
63.010.7(300
8u.0 (02)
61. 11.00.1..00 003000))
58. 03.883000012 0123
63.6.30 3(500
7...0.00000000
633 (08.7.0.000 (00)
76.9100.5(10)
DRL
38.811.8000 82200)
7(300)
57.00/2 825000
59 1::22 5(300)
57.31222 4(300)
(55.2:1/2.001.500
G1 G1 (002000000000
01.00:: (2(200)
ISOLFT
59.521.882000
50.731 (22000)
683. (3.003)4(3000
88.02: 1.7(000)
(2.7222333300)
02..0:2.005000
50.9:21.4(10
rank
Table D shows, for each method, the highest average accuracy and the number of features for which it
was achievod similarly to (Li et al.) 20122] Wang al., 2015). Figure 5 presents a comparative analysis of clustering accuracy across various datasels and methods, considering the full spectrum of selected features. This comparison aims to account for the inherent variance in each method, addressing a limitation where the criterion of the maximum accuracy over the number of selected features might inadvertently favor methods exhibiting higher variance.
https:///jndoong-giiiae http:///wwonn...iitt....////iiia htw.ge/.t..//c..aaaaaaaaaaaaaaaa
11

---

Published in Transactions on Machine Learning Research (12/2024)
COl
G/SFTTF
TOX-171
50
60
Clustering Accuracy
60
Clustering Accurescy
Clusterinng Accuratyy
Clustering Accuracy
65
40
150
40
30
40
53
20
20
30
<
300
1 8
300
8 P
selected features ALLAML
selected features PROSTATE
# of selected features
* of selected features
ORL
ISOLET
Clutering recurecy
Clustering Accurecy
Clatering Accuracy
80
Accurecy
60
20
70
50
40
60
60
40-
30
-5
35
30
20
3.
300
selected features
selected features
of selected features
of selected features
RANDOM
MCFS
NDFS
KNMPS
LS-AA
SSPS
Figure 5: Clustering accuracy vs. the number of selected features on eight real-world datasets.
For SSFS, we use the following surrogate models: (i) The eigenvector selection model h; is set to Logistic Regression with l regularization. We use scikit-learn's (Pedregosa et al.] 2011) implementation with a default regularization value of C = 1.0. Feature scores are equal to the absolute value of the model's coefficients. (ii) The feature selection model f, is set to XGBoost classifier with Gain feature importance. We use the popular implementation by DMLCC (Chen and Guestrin 2016).
Note that we employ the default hyper-parameterr for all surrogate models provided in their widely used implementations. However, it's worth noting that one undoubtedly leverage domain knowledge to select surrogate models and hyperparameters better suited to the specific domain. For each dataset, SSFS selects k from d = 2k eigenvectors, where k is the number of distinct classes in the data.
Results. SSFS has been ranked as the best method three out of eight datasels. has shown a significant advantage over competing methods, especially in the Yale, TOX-171, and Prostate-GBl datasets. As discussed in Section 3.1 the Prostate-GE dataset has several outliers, and the fourth eigenvector plays vital role in providing information about the class labels compared to the earlier eigenvectors. SSFS can effectively deal with such challenging scenarios, and this might explain its superior performance. Although our method is not ranked first in the other five datasets, it has produced results comparable to the leading method.
5.2 Ablation study
We demonstrate the importance of three SSFS components: (i) eigenvector selection, (ii) self-supervision with nonlinear surrogate models, and (iii) binarization of the Laplacian eigenvectors along with classifiers instead of regressors as surrogate models. The ablation study is performed on a synthetic dataset described in Section 5.2.1 and the eight real datasets used for evaluation in Section 5.1
5.2.1 Synthetic data
We generate a synthetic dataset follows: the first five features generated from two isotropic Gaussian blobs; those blobs define the clusters of interest. Additional 45 nuisance fcatures are generated according to a multivariate Gaussian distribution, with zero mean and a block-structured covariance matrix Σ, such that each block contains 15 features. The covariance elements Σg are equal to 0.5 if i.j are in the same block and 0.01 otherwise. We generated total of 500 samples; see Appendix [. for further details. In Figure Ga] you can see scatter plot of the first five features, and Figure 6b you can see a visualization of the covariance matrix. Our goal is to identify the features that distinguish between the two groups.
12

---

Published in Transactions on Machine Learning Research (12/2024)
Vellues
Samp les
Samples
Volues
Volues
Feature
10
Samples
(a) First 5 features
(b) Covariance matrix
(c) Eigenvectors
Figure 6: Visnalizations of the synthetic data: Panel (a): scatter plot of the first five features corresponding to the Gaussian blobs, colored by the real label. Panel (b): the covariance matrix of the dataset. Panel (c): the top-4 eigenvectors, samples are sorted by the label and are partitioned by the vertical bar, colored according to the output of k-medoids.
Ablation study: average clustering accuracy on benchmark datasets, the number of selected features is shown in parenthesis for the best clustering accuracy over the feature range.
Table 2:
Dataset
no selection
no XGBoost
no selection, regression
regression
SSFS
COIL20
65.0 (150)
62.1 (150)
70.5 (100)
69.0 (300)
67.1 (300)
GISETTE
72.5 (10)
64.9 (300)
64.6 (5)
64.6 (5)
69.7 (150)
Yale
48.6 (50)
42.7 (250)
49.8 (200)
47.4 (250)
50.3 (100)
TOX-171
50.9 (2)
45.6 (20)
45.0 (5)
45.5 (50)
59.4 (100)
ALLAML
75.4 (100)
66.7 (50)
71.1 (300)
71.1 (300)
75.4 (100)
Prostate-GE
59.8 (30)
69.6 (30)
61.8 (150)
61.8 (150)
75.9 (10)
ORL
60.0 (300)
56.8 (300)
58.5 (300)
58.5 (200)
61.1 (200)
ISOLET
57.0 (150)
57.1 (300)
61.3 (300)
58.7 (300)
59.9 (100)
Mean rank
2.94
4.0
3.0
3.5
1.56
Median rank
2.5
4.5
3.5
3.5
1.25
As Figure 6a demonstrates, the two clusters lincarly separated by three distinct fcatures. Furthermore, examining Figure 6c reveals that while the fourth eigenvector distinctly separates the clusters, the higher- ranked eigenvectors do not exhibit this behavior. This pattern arises due to the correlated noise, significantly influencing the graph structure. The evaluation of this dataset is performed by calculating the true positive rate (TPR) with respect to the tep-selected features and the discriminative features sampled from the two Gaussian blobs. The performance on the real-world datasets measured similarly Section 5.1
Table 3: Synthotic data results: Top-3 selected features (sorted descending order by rank), along with their TPR (relative the first five features).
Method
Top-3 Features
TPR
SSFS
2, 9, 19
0.3
(no XGBoost)
4, 3, 2
1.0
(no selection)
43, 30, 49
0.0
(regression)
15, 17, 14
0.0
MCFS
47, 7, 43
0.0
5.2.2 Results
Eigenvector Selection. We compare to a variation of SSFS termed SSFS (no selection), where we don't filter the eigenvectors. We Irain the surrogate feature selector model on the leading k eigenvectors, with set to the number of distinct classes in the data. Figure shows that our eigenvector selection scheme provides an advantage seven out of eight datasets. Similarly to Sec. [5.]] filtering the eigenvectors is espe- cially advantageous on the Prostate-GE dataset, our method successfully selects the most discriminative eigenvectors (see Figure 2a On the synthetic dataset, the selection procedure provides large advantage,
13

---

Published in Transactions on Machine Learning Research (12/2024)
seen in Table Figure 6c illustrates that the fourth eigenvector is the informative one with respect to the Gaussian blobs. Indeed, the fourth eigenvector and the third eigenvector are selected by the selection procedure, This eigenvector yields better features than MCFS and SSFS (no selection), which rely on the top two cigenvectors.
Classification and regression. We compare the following regression variants of SSFS which use the original contimuous eigenvectors as pseudo-labels (without binarization): (i) SSFS (regression): uses ridge regression for cigenvector selection and XGBoost regression for the feature selection as surrogate models. (ii) SSFS (no selection, regression): uses the top eigenvectors without binarization and XGBoost regression. Figure 7a and Table show that SSFS performs best six of the eight real-world datasets. Interestingly, when using continuous regression surrogate model, the selection procedure does not seem to provide an advantage compared to no selection.
Clztering hccurssy
Clustring Accuracy
60
60
20
20
20
GGETTE
Vale
TOK-171
ALLAMI
PROSTATE
ORL
ISOLET
000
GISA TE
Yole
TOK-171
ALLAML PROSTATE
GRI
ISOLET
(regression)
regression)
xghoosti
SSPS
SSFS
(a) Classification and regression
(b) Selection, and no XGBoost (logistic regression)
Figure 7: Ablation study results on the real-world datasets. The best clustering accuracy over the number of selected features shown for each method.
Complex nonlinear models surrogate models. We compare SSFS to variant of method denoted SSFS (no XGBoost), which employs logistic regression instead of XGBoost as the surrogate feature selector model. Figure 7b shows that XGBoost provides an advantage compared to the linear model on real-world datasets. On the synthetic dataset, the linear variant provides better coverage for the top-3 features that separate the Gaussian blobs, compared to XGBoost (see Table 3 and Figure Bap. That is not surprising since, in this example, the cluster separation is linear in each informative feature. We note, however, that the top-ranked feature by SSFS with XGBoost is a discriminative feature for the clusters the data. (see Figure Gal; therefore, its selection can still be considered successful in the case of single feature selection.
6 Discussion and future work
We proposed a simple procedure for filtering eigenvectors of the graph Laplacian and demonstrated that its application could have a significant impact on the outcome of the feature selection process. The selection is based on the stability of classification model predicting binary pseudo-labels. However, additional criteria, such as the accuracy of specific model the overlap of the chosen features for different eigenvectors, may provide information the suitability of a specific vector for feature selection task. We also illustrated the utility of expressive models, typically used for supervised learning, in unsupervised feature selection. Another dircction for further rescarch is using self-supervised approaches for group feature selection (GFS) for single modality (Sristi et al. 2022) or multi-modal data (Yang el al. 2023 YofTe el al. 2024).. In contrast to standard feature selection where the output sparse, GFS aims to uncover groups of features with joint effects on the data. Learning models based on different cigenvectors may provide information about group effects with potential applications such as detecting brain networks in Neuroscience and gene pathways in geneties.
14

---

Published in Transactions on Machine Learning Research (12/2024)
Broader Impact Statement
This work involves methods applicable to high-dimensional data, including sensitive domains like hcalthcare. While our experiments used publicly available datasets, minimizing immediate privacy concerns, practitioners applying this method to sensitive data should ensure compliance with data protection regulations and adopt robust srivacy-preservingg measures.
There is also a risk of misapplication in critical areas such as medical diagnosis or criminal justice, where biased or incorrect feature selection could lead to harmful decisions. To mitigate this, we recommend inte- grating bias detection and mitigation techniques into the training pipeline to enhance fairness and reliability,
Careful consideration of these ethical and societal implications essential for the responsible use of this method.
References
Muhammed Fatih Balm, Abubakar Abid, and James Zou. Concrete autoencoders: Disferentiable feature selection and reconstruction. In International conference machine learning, pages 444-45 453. PMLR, 2019.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Newral computation, 15(6):1373-1333 1196,, 2003.
Deng Cai, Chiyuan Zhang, and Xiaofei He. Unsupervised feature selection for multi-cluster data. In Pro- ceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. pages 333-342 2010.
Deng Cai, Xiaofci He, and Jiawei Han. Locally consistent concept factorization for document clustering. IEEE Transactions on Knowledge and Dala Engineering, 23(6):902 913, 2011.
Jeff Calder and Nicolas Garcia Trillos. Improved spectral convergence rates for graph laplacians on E-graphs and k-nn graphs. Applied and Computational Harmonic. Analysis, 00:123-175,, 2022.
B Chandra and Rajesh K Sharma. Exploring autoencoders for unsupervised feature selection. In 2015 International Joint Conference Neural Networks (IJCNN), pages 1 6. IEEE, 2015.
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and dula mining, pages 785 094,,994444 2016.
Xiuyuan Cheng and Nan Wu. Figen-conveerennce of gaussian kernelized graph laplacian by manifold heat interpolation. Applied and Computational Harmonic Analysis, 61:132 190, 2022.
Ronald R Coifman and Stéphanc Lafon. Diffusion maps. Applied and computational harmordc analysis, 21 (1):5 30, 2006.
David B Dunson, Hau-Tieng Wu, and Nan Wu. Spectral convergence of graph Laplacian and heat kernel reconotruction po0 from random samples. Applied and Compulational Harmonic Analysis, 55:282-338 2021.
Bradley Efron, Trevor Hastie, lain Johnstone, and Robert Tibshirani. Least angle regression. The Annals of Statistics, 32(2):407 499, 2004.
Nicolás García Trillos, Moritz Gerlach, Matthias Hein, and Dejan Slepčev. Error estimates for spectral convergence of the graph laplacian on random geometric graphs toward the Laplace-Beltrami Foundations of Computational Mathematics, 82()))2778887 2020.
Beltrami operator.
Kai Han, Yunhe Wang. Chao Zhang, Chao Li, and Chao Xu. Autoencoder inspired unsupervisod feature selection. 2018 IEEE international conference on acoustics, speech and signal processing (ICASSP), pages 2941-2945. TEEE, 2018.
15

---

Published in Transactions on Machine Learning Research (12/2024)
Jesse He, Tristan Brugère, and Gal Mishne. Product manifold learning with independent coordinate selection. In Topologionl, Algebraic and Geometric Learning Workshops 2023, pages 267-277 277. PMT.R, 2023.
Xiaofei He, Deng Cai, and Partha Niyogi. Laplacian score for feature selection. In Proceedings of the 18th International Conference on Neural Information Processing Systems, NIPS'05, page 507-514, Cambridge, MA, USA, 2005. MIT Press.
Leonard Kaufman and Peter J. Rousseeuw. Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley, 1990. ISBN 978-0-47031680-1.
Changhee Lec, Fergus Imric, and Mihacla van der Schaar. Sclf-supervision enhanced feature selection with correlated gates. In International Conference on Learning Representations, 2021.
Jundong Li, Jiliang Tang, and Huan Liu. Reconstruction-oee based unsupervised feature selection: An embedded approach. In IJCAI, pages 2159-2165, 2017.
Xuelong Li, Han Zhang, Rui Zhang, Yun Liu, and Feiping Nie. Generalized uncorrelated regression with adaptive graph for unsupervised feature selection. IEEE transactions on neural networks and learning systems, 30(5):1587-1555, 2018.
Zechao Li and Jinhui Tang. Unsupervised feature selection via nonnegative spectral analysis and redundancy control. IEEE Transactions on Image Processing, 24(12):5343-56) 5355, 2015.
Zechao Li, Yi Yang, Jing Liu, Xiaolang Zhou, and Hanqing Lu.. Unsupervised feature selection using nonnegative spectral analysis. In Proceedings of the AAAI conference artificial intelligence, volume 26, pages 1026-1032, 2012.
Ofir Lindenbaum, Uri Shaham, Erez Peterfreund, Jonathan Svirsky, Nicolas Casey, and Yuval Kluger. Dif- ferentiable unsupervised feature selection based on a gated laplacian. Advances in Neural Information Processing Systems, 14:1530-1542, 2021.
Kaveh Mahdavi, Jesus Labarta, and Judit Gimenez. Unsupervised feature selection for noisy data. In Advanced Data Mining and Applications: 15th International Conference, ADMA 2019, Dalian, China, November 21-23, 2019, Proceedings 15, pages 79-94. Springer, 2019.
Duncan McElfresh, Sujay Khandagale, Jonathan Valverde, Ganesh Ramakrishnan, Micah Goldblum, Colin White, et al. When do neural nets outperform boosted trees on tabular data? arXiv preprint urXin:2305.02009 2023.
Marina Meilä. Comparing clusterings by the variation of information. In Learning Theory and Kernel Machines: 16th Annual Conference Learning Theory and 7th Kernel Workshop, COLT COLT/Keran /Kernel 2003, Woshinglon, DC, USA, August 24-27, 2003. Proceedings, pages 173-187. Springer, 2003.
James R. Munkres. Algorithms for the assignment and transportation problems. Journal of The Society for Industrial and Applied Mathematics, 10:196-210, 1957. URL https://apl. semanticscholar http:s//pps.eennttccchh..... org/ CorpusID:15996577
Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14, 2001.
Marcos de S Olivcira, Sergio R de M Quciroz, and Francisco de AT de Carvalho. Unsupervised feature selection method based on iterative similarity graph factorization and clustering by modularity. Expert Systems with Applications, 208:118092 2022.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scíkit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2830, 2011.
16

---

Published in Transactions on Machine Learning Research (12/2024)
Benjamin Ricaud, Pierre Borgnat, Nicolas Tremblay, Paulo Gongalves, and Pierre Vandergheynst. Fourier could be data scientist: From graph fourier transform to signal processing on graphs. Comples Rendus Physique, 20(5):474 488, 2019.
Giorgio Roffo, Simone Melzi, Umberto Castellani, and Alessandro Vinciarelli. Infinite latent feature selection: A probabilistic latent graph-based ranking approach. In Proceedings of the IEEE international conference on computer vision, pages 1398-1406, 2017.
Sam T Roweis and Lawrence K Saul. Nonlincar dimensionality reduction by locally lincar embedding. science, 290(5500):2323 2326, 2000.
Uri Shaham, Ofir Lindenbaum, Jonathan Svirsky, and Yuval Kluger. Deep unsupervised feature selection by discarding muisance and correlated features. Neural Networks, 152:34443 -3, 2022.
Jun Shao and CF Jeff Wu. A general theory for jackknife variance estimation. The annals of Statistics, pages 1176 1197, 1989.
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3):83 98, 2013.
Amit Singer and Hau-Tieng Wu. Spectral convergence of the connection laplacian from random samples. Information and Inference: A Journal of the IMA, 6(1):58 123, 2017.
Dinesh Singh, Phillip Febbo, Kenneth Ross, Donald Jackson, Judith Manola, Christine Ladd, Pablo Tamayo, Andrew Renshaw, Anthony D' D'mmico, Jerome Richie, Eric Lander, Massimo Loda, Philip Kantoff, Todd Golub, and William Sellers. Gene expression correlates of clinical prostate cancer behavior. Cancer cell, 1:203 9, 04 2002. doi:
Ram Dyuthi Sristi, Gal Mishne, and Ariel Jaffe. Disc: Differential spectral clustering of features. Advances in Neural Information Processing Systems, 35:26269 26282, 2022.
Jonathan Svirsky and Ofir Lindenbaum. Interpretable deep clustering for tabular data. In Forty-first International Conference on Machine Learning.
Joshua B Tenenbaum, Vin de Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319-23333 2323, 2000.
Roman Vershynin. High-dimensional probability. University of California, Troine, 2020.
Ulrike Von Luxburg. Lutorial on spectral clustering. Statislics and computing, 17:395 416, 2007.
Ulrike Von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering. The Annals of Slatistics, pages 555-586, 2008.
Suhang Wang, Jiliang Tang, and Huan Liu. Embedded unsupervised feature selection. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Caroline L Wormell and Sebastian Reich. Spectral convergence of diffusion maps: Improved error bounds and an alternative normalization. STAM Journal on Numerical Analysis, 59(3):1687-1734, 2021.
Xijiong Xie, Zhiwen Cao, and Feixiang Sun. Joint learning of graph and latent representation for unsupervised feature selection. Applied Intelligence, pages 1-14, 2023.
Junchen Yang. Ofir Tindenbaum, Yuval Kluger, and Ariel Jaffe. Multi-modal differentiable unsupervised feature selection. In Uncertainty in Artificial Intelligence, pages 2400 2410. PMLR, 2023.
Yi Yang, Heng Tao Shen, Zhigang Ma, Zi Huang, and Xiaofang Zhou. L2,1-norm regularized discriminative feature selection for unsupervised learning. In Proceedings of the Twenty-Second International Joint Con- ference on Artificial Intelligence Volume Volume Two, IJCAI'11, page ISBN 9781577355144.
AAAI Press, 2011.
17

---

Published in Transactions on Machine Learning Research (12/2024)
Shira. Yoffe, Amit Moscovich, and Ariel Jaffe. Spectral extraction of unique latent variables, arXiv preprint arXiv:2402. 18741, 2024.
Sharon Zhang, Amit Moscovich, and Amit Singer. Product manifold learning. In International Conference on Artificial Intelligence and Statistics, pages 3241-3249. PMTR, 2021.
Zheng Zhao and Huan Liu. Spectral feature selection for supervised and unsupervised learning. In Proceedings of the 24th international conference on Machine learning, pages 1151 1157, 2007.
Linling Zhu, Linsong Miao, and Daoqiang Zhang. Iterative laplacian score for feature selection. In Chinese Conference on Pattern Recognition, 2012.
Qi-Hai Zhu and Yu-Bin Yang. Discriminative embedded unsupervised feature selection. Pattern Recogrétton Letters, 112:219-2251 2018.
Xiaofeng Zhu, Shichao Zhang, Rongyao Hu, Yonghua Zhu, et al. Local and global structure preservation for robust unsupervised spectral feature selection. IEEE Trunsactions on Knowledge and Data Engineering, 30(3):517-55) 529,, 2017.
Xiaoleng Zhu, Shichao Zhang, Yonghua Zhu, Penglei Zhu, and Yue Gao. Unsupervised spectral feature selection with dynamic hyper-graph learning. IEEE Transactions on Knowledge and Data Engineering, 34(6):3016 3028, 2020.
18

---

Published in Transactions on Machine Learning Research (12/2024)
A Product of manifold perspective.
A.1 Proof of Theorem 1.
As mentioned in the main text, the theorem is proven with the following two main steps:
Prove that the inner product ff (x) is of order 011/Vn) for all eigen fogeeffuntionns (X) indexed by vector b & E.
Step 1:
Step Combine the result of step with the convergence guarantees in Theorem Lo bound the inner product v/ ub.
Step According to our model, feature equal smooth transformation of a single latent variables. Assume w.l.o.g that the single variable 0 such that f. F.(0)). By the product of manifold assumption, the eigenfunction gb is equal to
(b( II gb. (x))) Ib. (T (x))
II gb. (T (x)).
Let @ denote the Hadamard product. We can write the inner product f gb( () as,
gX) = (fi @ &b, gb, (x (x)) (90.
Bgb ( (H) (X)).
(6)
The vectors f. and gb, (X)) both depend on 0 only. The vectors (gb, (I (X) depend, respectively, on f2..... 0μ. We set
a(0)) Si 9b, (m (x
gbg (T (3) ())() (X)) Ggb (T (X)).
The elements of the random vectors a(1)) and d(02..... 0.:) are statistically independent. In addition, we have that || 1 and
9 (
x))] = + 4(h),
see for example (Cheng and Wu, 2022 Lemma 3.4). This implies that both a(1)) and d(02...., OH) are bounded by + o(1). The inner product between two independent random vectors with unit norm and iid elements is of order (()/Vn), (see for example (Vershynin] 2020 Remark 3.2.5)). Thus,
[x)) (a(0:)² d(o2....., 001/m).
Step By the triangle incquality,
sT vol = 1s. (vn - -g gx())) < 1f,((u gb + IS gb(
(7)
The first term on the right-hau hand side equation can be bounded by the Sauchy-Schwarte inequality and Theorem via:
+0
log
[T (x(X)) | go (x) = +(e))+
(8)
d/2+1
TEn
The second term is bounded by step Since the term in equation dominates concludes the proof.
O(1/vn) for any 6n, this
B Stability analysis
We perform stability analysis using the Variation of Information (VI) criterion introduced by Meilä (2003)
measure of the distance between two clustering assignments. This criterion be used to measure the
19

---

Published in Transactions on Machine Learning Research (12/2024)
4000
4000
Veriation of Informationn
Variation of information
(a) TOX 171 dataset
(b) Yale dataset
Figure 8: Histograms of VI value distributions for SSTSS-elecced features (orange) and features (blue) on (a) TOX 171 and (b) Yale datasets. Lower VI values indicate higher stability in clustering results.
stability of clustering results, which valuable for assessing feature selection quality. For noisy features, we expect unstable clustering outputs with high variability between runs, while informative features should yield more stable results with less variability.
Our analysis involves applying k-means clustering to the selected features 500 times with random initializa- tions, caleulating the VT between all pairs of clustering outputs, and analyzing the distribution of VT values. Lower average VI and tighter distribution indicate higher stability, suggesting more informative features. We compared the stability of clusters obtained using the original datasel versus those obtained using features selected by our Stable Spectral Feature Selection (SSFS) method.
Table presents results for the TOX171 and Yale datasots, demonstrating clear improvement in stability when using SSFS. For both datasets, SSTS-selected features yield lower mean VI values, indicating more consistent clustering outcomes. Figure S visualizes the distributions of VI values for both datasets, showing the shift towards lower VI values when using SSFS sccleccee features compared to using all features.
Table Stability Analysis Results: Mean Variation of Information (VT) Standard Deviation
Datasct TOX171
SSFS (top 100 fcatures)
All features
1.64 + 0.39
2.01 + 0.36
Yale
2.12 + 0.27
2.25 + 0.27
C Interpretability
Interpretability is a fundamental aspect of unsupervised feature selection, particularly in domains where understanding the meaning and relevance of selected features is crucial.
In the context of our proposed SSFS algorithm, interpretability can be enhanced in several ways. Feature ranking, by examining the weights or importance scores assigned features during the selection process, can provide insights into which features are most important across the dataset. Visualization tochniques, demonstrated in Figure g can reveal patterns and distributions that highlight the discriminative capability of selected features across different classes clusters. Domain-specife analysis is another effective approach. In biological datascts, for instance, selected features can be mapped back to specific genes or biomarkers, allowing domain experts to validate the biological relevance of the selected features and potentially uncover new insights about the underlying biological processes.
These intorpretability techniques enhance the utility of unsupervisod feature selection algorithms like SSFS by providing insights into underlying relationships and feature relevance, which are essential for real-world applications across various domains.
20

---

Published in Transactions on Machine Learning Research (12/2024)
Figure visualizes the top twenty features selected by SSFS on the COIL20 dataset. Each column corresponds to sample, and each row represents selected feature. The columns are ordered by the class label. The figure highlights the discriminative effect the selected features have over five classes in this dataset.
1.00
0.78
0.67
Selected Features
Feature Value
0.44
0.33
0.11
0.00
50 100
150
200
250
300
350
Samples
Figure 9: Visualization of the top 20 selected features by SSFS across five classes in the COIL20 dataset. Samples are grouped by class, separated by white vertical lines, with class labels shown at the top. The color intensity indicates the relative feature values. This visualization allows for the comparison of feature patterns and distributions across different classes, highlighting potential discriminative features and class- specific characteristics.
D Additional experiments on synthetic data
We conducted further experiments to test method's robustness to noise, using two synthetic datasets with 100 samples per trial over 10 trials. Both datasets contain five meaningful features from two isotropic Gaussian blobs but differ in their nuisance features. The first dataset's nuisance features are sampled from a multivariate Gaussian distribution, similar to Section 5.2.1 but with varying numbers of nuisance features. The second uses a copula of correlated nuisance features formed of marginals with a Laplace distribution. We measure performance using recall, comparing the top five ranked features the five known meaningful ones.
Results in Figure 10 show SSFS with logistic regression linear classifier (denoted by linear clf) outper- forming other methods across both experiments. For Gaussian nuisance fcatures (Figure 10a), SSFS with a linear classifier maintained consistently high performance up to 60 features, while other methods exhibited a more pronounced decline as the number of nuisance features grew. In the case of Laplace-distributed muisance features (Figure ( the advantage of SSFS with a linear classifier was even more evident, with its performance decreasing more slowly as the number of muisance features increased. Overall, these exporiments demonstrate that SSFS is robust method for identifying relevant features, performing well for various noise distributions and maintaining high recall with increasing noise levels.
E
Ablation study additional details
E.1 Synthetic data generation
For the synthetic data, we generated 500 samples, where we used the make make_blobs function from scikit-learn to generate the first five features, with arguments cluster_std-f centers=2.
21

---

Published in Transactions on Machine Learning Research (12/2024)
regrendin sgbooet
50"5 regression
55%5 eggooottt
in, velertion
0.7
selertion
SS'S Iieeerrf
SSPS, jineer
MOFS
0.6
MCFS
Average Recall
Average Recall
0.4
03
02-
01
20
25
50
100
125
150
175
nulsance features
of nuisance features
(a) Ganssian nuisance features
(b) Laplace nuisance features
Figure 10: Performance comparison of feature selection methods under increasing noise levels. The x-axis shows the number of nuisance features added to the give meaningful oncs, while the y-axis represents the average recall (proportion of the top five ranked features matching the five meaningful features). Each point is the average 10 trials with 100 samples each. SSFS with linear classifier (logistic regression) consistently outperforms MCFS and the other SSFS variants.
CON
GISFTTE
TOX-171
70
50
60
Clustering Accuracy
Clustering Accurasy
70
Clustering Accuracs
60
d5
65
40 .35
-50
.50
60
30
40
<9 18 pp 1000
300
P
salected feotures ALLAML
salected features PROSTATE
# of selected fectures
of salected features
ORL
ISOLET
Clustering Accuracy
75
Clustering Accuracy
Clusteringg Accurecy
60
60
20
70
50
50
&
40
60
90
130
555
20
50
300
300
300
selected features
selected festures
of selected features
of selected features
xgboost)
regressiont
(regression)
Figure 11: Ablation study: Clustering accuracy on real-world datasets
E.2 Detailed Experimental Results
In this section, we provide more detailed results of the ablation study. Figure contains comparative analysis in terms of the performance for the whole selected feature range,
F
Experiments on real world datasets additional details
F.1
Additional Experimental Details
F.2 Datasets
Table provides information about the real-world datascts used the experiments.
For all datasets, the features z-score normalized to have zero and unit variance.
22

---

Published in Transactions on Machine Learning Research (12/2024)
Table Real-world datasets description.
Dataset
Samples
Dim
Classes
Domain
COIL.00
1440
1024
20
Image
ORL
400
1024
Image
Yale
165
1024
15
Bio
ALLAML
72
7129
Bio
P Prostate-GE
102
5966
2
Bio
TOX 171
171
5748
Bio
Isolet
1560
617
26
Speech
GISETTE
7000
5000
Image
F.3 Hyperparameters
Hyperparameter selection in unsupervised feature selection presents unique challenges and may infeasible due to the absence of labeled data for validation. In our methods, we have two lypes of hyperparameters: (i) For computing the spectral representation (kernel bandwidth and the number of eigenvectors) and (ii) parameters relating to the surrogate model, which predicts the pscudo-labels (i.c., regularization parameter for Logistic Regression). Note that the second lype of parameters is used in prediction lask; they can be determined similarly to hyperparameters in supervised settings, for example, through cross-validation.
In our experiments, for the surrogate models, we leverage the default hyperparameters from establishod machine learning packages such as XGBoost and scikit-learn's logistic regression, as these are generally robust for wide range of supervised tasks. However, surrogate models and their hyperparameters can also be chosen by performing hyperparameter tuning with cross-validation based on pseudo-labels derived from the eigenvectors. The selection of surrogate models is flexible and can be additionally guided by domain knowledge. Practitioners can also compare results across various models and analyze their selected features.
The first type of lyperparameters is inherent to the method, for example, the number of considered eigenvec- tors, which should increase with the number of classes and noise level in the data. For instance, in scenarios with more classes or where noise dominates the spectrum, a larger range of eigenvectors should be considered. While we used 500 resamples in our experiments, this number can be adjustod for larger datascts to balance computational cost and performance. Although traditional hyperparameter tuning may not be feasible in most unsupervised scenarios, practitioners working with domain-specific data could potentially fine-tune paramcters using cross-validation on similar, labeled datasets from the same domain (such as images).
For SSFS, we use the same hyperparameters, as follows:
Number eigenvectors to select & is set to the distinct number of classes in the specific dataset, they are selected from total of 2k cigenvectors.
Size of each subsample is 95% of the original dataset.
500 resamples are performed in every dataset.
For the affinity matrix, we used Gaussian kernel with an adaptive scale ojo, such that o; is the distance to the l = neighbor of æ;.
The Laplacian we used was the symmetric normalized Laplacian.
In the ablation study, for regression, we use scikit-learn ridge regression (for eigenvector selection) and DMLC XGBoost regressor (for the final feature scoring) with their default hyperparameters.
For all of the bascline methods, we used the default hyperparameters. So, for all methods, including SSFS, the hyperparameters are fixed for all datasets (excluding parameters that correspond the number of features to select and the number of clusters).
23

---

Published in Transactions on Machine Learning Research (12/2024)
For LS, MCFS, UDFS, and NDFS, we used an implementation from the scikit-feature library D and inputted the same similarity matrices as SSFS for the methods which accepted such an argument. We fixed a bug in MCFS implementation to choose by the max of the absolute value of the coefficients instead of the max of the coefficients (this improved MCFS performance). For LS-CAE, we used an implementation from 3 For KNMFS, we used an implementation from]
24


Reviews:
[{"review_id": "3MDLKnXTOY", "reviewer": "Reviewer_8p1s", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. To calculate the pseudo labels for a given set of laplacian eigenvectors, the authors use a one-dimensional k-medoids algorithm. This process of binarization seems to be highly effective as the feature selection is based on a classification rather than a regression task, which is more aligned with selecting features for clustering. The impact of the binarization step is also demonstrated on multiple real world data sets.\n2. The proposed algorithm is versatile and can be integrated with any supervised model that provides feature importance scores. By leveraging the structural information from the graph Laplacian alongside the strengths of various supervised models, this method enhances unsupervised feature selection. This straightforward yet effective approach significantly boosts the algorithm’s generalizability.\n3. The authors provide a solid theoretical foundation for the convergence properties of the Laplacian eigenvectors in high-dimensional spaces, establishing the accuracy and stability of the proposed approach. This theoretical foundation adds credibility to the method and provides further justification for the experimental results.\n\nWeaknesses\n\n1. The proposed approach is built on the assumption that the structure of the dataset of interest can be effectively captured by the graph Laplacian. While this works well for certain types of datasets, it may not be suitable for data that does not conform to this assumption, such as cases where feature correlations are not well-represented by a graph structure or where the data manifold is not smooth.\n2. While the paper demonstrates the effectiveness of the proposed algorithm on various real and synthetic datasets, it does not provide a detailed analysis of its computational complexity or scalability. Feature selection techniques often need to be computationally efficient, especially when dealing with large-scale or high-dimensional data.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In the manuscript, the authors propose a self-supervised graph-based approach for unsupervised feature selection. The proposed method involves computing robust pseudo-labels by applying simple processing steps to the graph Laplacian’s eigenvectors. The subset of eigenvectors used for computing pseudo-labels is chosen based on a model stability criterion. To measure the importance of each feature, the authors train a surrogate model to predict the pseudo-labels from the observations. The method is shown to be robust to challenging scenarios and the effectiveness of the method is demonstrated through experiments on real-world datasets.\n\nOverall, the proposed algorithm represents a significant step forward in unsupervised feature selection by leveraging graph-based structures and self-supervision, making it a promising tool for handling complex, high-dimensional datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Requested changes\n1. In the experiments section, the authors primarily emphasize the clustering accuracy of their method compared to others. While reporting clustering accuracy is valuable, assessing the quality of a clustering algorithm is inherently complex, as true labels are often unavailable. Even when true labels exist, they are typically assigned by humans and may contain errors. Incorporating a more robust comparison metric, such as the Variation of Information by Meila (2003), could provide a more rigorous and comprehensive evaluation of the algorithm’s performance. In my view, this would strengthen the paper further.\n2. The paper could potentially benefit from a deeper discussion on the time complexity of the proposed algorithm as well as comparisons with other methods. In my view, this is a critical addition to improve the quality of the paper.\n3. Incorporating an analysis of the interpretability of the selected features could also benefit the paper. A small discussion on how the proposed algorithm can be modified to enhance interpretability or provide examples of how the selected features can be understood in the context of specific application domains (e.g., biological datasets or image datasets). In my view, this would strengthen the paper further.", "broader_impact_concerns": "No concerns on the ethical implications of the work that could require a broader impact statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4K2CiEBkjZ", "reviewer": "Reviewer_PkzX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths:\n\n1. The introduction of a spectral self-supervised feature selection (SSFS) method, as a combination of spectral methods of graph Laplacian with a self-supervised algorithm, is a novel contribution to the field of unsupervised learning, particularly for feature selection. The method’s robustness to various scenarios, such as the presence of noise and outliers, is a significant strength. This makes the algorithm practical for real-world applications.\n\n2. The flexibility to use various supervised methods as surrogate models (e.g., logistic regression for eigenvector selection and XGBoost for feature selection) makes the method adaptable to various data types and complexity levels. This opens a door to extend all theoretical analysis in supervised models to more general unsupervised and feature selection settings.\n\n## Weaknesses:\n\nIt would be better to have a discussion on the computational complexity of SSFS. The SSFS method may have a higher computational cost compared to simpler unsupervised feature selection methods due to the need to evaluate multiple models and resampling procedures and the eigendecomposition of graph Laplacian. Addressing the computational efficiency could make the method more scalable to very large datasets.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a novel approach to unsupervised feature selection by leveraging spectral methods and self-supervision. The core idea is to use the eigenvectors of the graph Laplacian to create pseudo-labels that guide the feature selection process. The technique involves selecting a subset of eigenvectors based on their stability, and then using these selected eigenvectors to generate binary pseudo-labels. A surrogate model is then trained to predict these pseudo-labels from the data, and the feature importance is derived from the model's predictions. The proposed method, Spectral Self-supervised Feature Selection (SSFS), is robust in various challenging scenarios, such as the presence of outliers and complex data substructures. The authors show that SSFS outperforms other existing methods in terms of clustering accuracy on several real-world datasets, particularly excelling in biological data analysis. The authors also provide a theoretical analysis to justify the necessity of careful eigenvector selection in their feature selection algorithm in a product manifold model.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. In the first paragraph of page 7, dataset $X$ should be boldface.\n\n2. In the assumptions (i-iii) from page 7, can you give some simple examples where these assumptions are satisfied? For instance, in assumption (iii), the bandwidth is approaching zero, but how do you choose bandwidth in the SSFS algorithm?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Rnsl4j74TC", "reviewer": "Reviewer_Ynej", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The use of k-medoids clustering for generating pseudo-labels ensures robustness to outliers\n- The stability-based criterion for selecting informative eigenvectors enhances the reliability\n- Experiments on multiple real-world datasets demonstrate its effectiveness\n\nWeakness\n- Although the paper claims that SSFS is robust to outliers and complex substructures, there is limited discussion and empirical evidence on its robustness to different types and levels of noise in the data. Noisy features can also affect the graph construction and the subsequent eigenvector computation, which is crucial for practical applications in noisy real-world datasets.\n- The method involves several hyperparameters, such as the number of eigenvectors to select, the number of resamples for variance estimation, and the choice of surrogate models. The performance of the method can be sensitive to these hyperparameters, and selecting the optimal values may require extensive experimentation and domain knowledge. \n- It involves multiple stages, including the computation of the graph Laplacian, generation of pseudo-labels, selection of stable eigenvectors, and training of surrogate models. Each of these steps can be computationally intensive, especially for large datasets. A detailed analysis of the computational cost or scalability of the method can be insightful for practical applications.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces Spectral Self-supervised Feature Selection (SSFS) for unsupervised feature selection. SSFS generates robust pseudo-labels from graph Laplacian eigenvectors using k-medoids clustering. It employs a stability-based criterion to select the most informative eigenvectors. Empirical validation on real-world datasets demonstrates its superior performance, particularly in noisy and complex environments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Include an analysis or discussion of the computational cost and scalability of the method, along with potential optimizations?\n\n- Offer guidelines or automated strategies for hyperparameter tuning to enhance the method's usability.\n\n- Provide empirical evidence and discussion on the method's robustness to different types and levels of noise in the data.", "broader_impact_concerns": "The use of high-dimensional data, especially in sensitive domains like healthcare, raises concerns about privacy and data security. Ensuring that the method complies with data protection regulations is essential. In addition, there is a risk that the method could be misapplied in critical areas such as medical diagnosis or criminal justice, leading to potentially harmful decisions based on biased or incorrect feature selection.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers identified questions around complexity and clustering stability/performance. These issues were taken seriously and addressed by the authors. The authors submitted a revision that clearly identified the changes in response to these concerns. After revision, the reviewers supported acceptance.
Decision: Accept (poster)