Joint Feature and Differentiable $ k $-NN Graph Learning using Dirichlet Energy
Authors: Lei Xu
Lei Chen
Rong Wang
Feiping Nie
Xuelong Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Feature Selection
Differential k-NN Graph
Dirichlet Energy
TL;DR: We propose a deep feature selector that simultaneously learns useful features and differential k-NN graphs based on the Dirichlet energy.

Abstract: Feature selection (FS) plays an important role in machine learning, which extracts important features and accelerates the learning process. In this paper, we propose a deep FS method that simultaneously conducts feature selection and differentiable $ k $-NN graph learning  based on the Dirichlet Energy. The Dirichlet Energy identifies important features by measuring their smoothness on the graph structure, and facilitates the learning of a new graph that reflects the inherent structure in new feature subspace. We employ Optimal Transport theory to address the non-differentiability issue of learning $ k $-NN graphs in neural networks, which theoretically makes our method applicable to other graph neural networks for dynamic graph learning. Furthermore, the proposed framework is interpretable, since all modules are designed algorithmically. We validate the effectiveness of our model with extensive experiments on both synthetic and real-world datasets.

Joint Feature and Differentiable K:-N Graph Learning using Dirichlet Energy
Lei Xu
Lei Chen
School of Computer Science & School of Artificial Intelligence, OPtics and ElectroNics (iOPEN)
School of Computer Science
Nanjing University of Posts and Telecommunications
Nanjing 210003, P.R. China chenlei @nj.t...nnjppeeeeeeee edu.ccn
Northwestern Polytechnical University
Xi' an 710072, P.R. China solerx119980gmil.ccom
Rong Wang School of Artificial Intelligence, OPtics and ElectroNics (iOPEN) Northwestern Polytechnical University Xi'an an 710072, P.R. China rangrongg7@tssighhan org.cn cn
Feiping Nie
School of Artificial Intelligence,
OPtics and ElectroNics (iOPEN) &
School of Computer Science
Northwestern Polytechnical University
Xi' an 710072. P.R. China feipingmies wwwpingnni@@mmmi.commm com
Xuelong Li
School of Artificial Intelligence, OPtics and ElectroNics (iOPEN) Northwestern Polytechnical University Xi' an 710072, P.R. China 1 @nwpu. edu. cn
Abstract
Feature selection (FS) plays an important role in machine learning, which extracts important features and accelerates the learning process. In this paper, we propose deep FS method that simultaneously conducts feature selection and differentiable k-NN graph learning based on the Dirichlet Energy. The Dirichlet Energy identifies important features by measuring their smoothness on the graph structure, and facil- itates the learning of new graph that reflects the inherent structure in feature subspace. We employ Optimal Transport theory to address the non-differentiability issue of learning k-NN graphs in neural networks, which theoretically makes our method applicable to other graph neural networks for dynamic graph learning. Furthermore, the proposed framework is interpretable, since all modules de- signed algorithmically. We validate the effectiveness of our model with extensive experiments both synthetic and real-world datasets.
Introduction
Feature selection (FS) critical technique in machine learning that identifies informative features within the original high-ding gigh-dimensional data. By removing irrelevant features, FS speeds up the learning process and enhances computational efficiency. In many real-world applications such as
"Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

image processing, bioinformatics, and text mining [1 FS techniques are widely used to identify important features, thereby providing some explanations about the results and boosting the learning
performance 4
While numerous FS methods have been proposed in both supervised and unsupervised settings, as several studies highlighted [8] [2] the nature of FS is more unsupervised due to the unavailabilityy of task-specific labels advance. The selected features should be versatile to arbitrary downstream tasks, which motivates us to focus on the unsupervised FS in this study. Related works have recently resorted to neural networks to exploit the nonlinear information within feature space. For example, AEFS [9] uses the group Lasso to regularize the parameters in the first layer of the autoencoder, so as to reconstruct original features based on the restricted use of original features. Another well-known method is CAE [8) which selects features by learning a concrete distribution over the input features. However, most unsupervised deep methods rely on the reconstruction performance to select useful features. On the one hand, if there exists noise in the dataset, the reconstruction performance will be terrible even if useful features are selected, since the noise cannot be reconstructed with these informative features (see our reconstruction experiments Madelon in Section 4.3). On the other hand, it is difficult to explain why selected features reconstruct the original data well. These issues prompt us to seek a new target for unsupervised deep FS.
As the saying goes, "birds of a feather flock together", the homophily principle [0] suggests that similar samples tend to be connected in a natural graph structure within real-world data. This graph structure is useful for describing the intrinsic structure of the feature space, and is commonly used in machine learning studies [2]. Building upon this graph structure, He et al. [13 introduce the Dirichlet Energy, which they call "locality preserving power", as a powerful tool for unsupervised FS that is able to identify informative features reflecting the intrinsic structure of the feature space.
In many practical applications. the graph structure is not naturally defined and needs to be constructed manually based on the input features using some similarity measurements. The quality of features affects the quality of the constructed graph. As highlighted in [4], the useless features increase the amount of unstructured information. which hinders the exploration of inherent manifold structure within data points and deteriorates the quality of constructed graph. Therefore, the reference [14] proposes the UDFS method to discard such nuisance features and constructs a sennarest--eighhee (NN) graph on the selected features using the heat kernel. Despite the good performance of UDFS, constructing graphs using the heat kernel may not reflect the intrinsic structure of the feature space. Besides, the sorting algorithms in learning the K-NN graph in UDFS is non-differentiable in neural networks, which restricts its application in downstream networks.
In this paper: (1) We propose deep unsupervised FS network that performs simultaneous feature selection and graph learning by minimizing the Dirichlet Energy, thereby revealing and harnessing the intrinsic structure in the dataset. (2) Within the network, a Unique Feature Selector (UFS) is devised to approximate discrete and distinct feature selection using the Gumbel Softmax technique combined with decomposition algorithms. (3) Moreover, a Differentiable Graph Learner (DGL) is devised based on the Optimal Transport theory, which is capable of obtaining differentiable k-NN graph that more accurately reflects the intrinsic structure of the data than traditional graph constructing methods. Due to the differentiability, DGL is also theoretically capable of serving as a learnable graph module for other graph- based networks. (4) The entire framework is developed algorithmically. Unlike most deep learning networks with complex components that are tough to decipher, each core module in our framework has an algorithmic and physically interpretable design, which greatly facilitates observing and understanding the network's 's internal operations during the learning process. (5) Experimental results on both synthetic datasets and real-world datasets demonstrate the effectiveness of our method.
Notations. For an arbitrary matrix M E Raxb m m. and m4.j denote the i-th row, the i-th column, and the (i,j)-th entry of M, respectively. Given a vector m E R¹, its fy-norm is defined as |||]|2=
When a -i=1 ma.i. Given two matrices M, N E Raxb we define their inner product as (M, N) = Ei =j=1" mi. 1, denotes a b-dimensional column vector with all entries being 1, and I, denotes a b-order identity matrix. (col(cond) is a boolean operator that equals 1 if cond is true, otherwise it equals 0. Moreover, given a vector m E R², we define its sorting permutation in ascending order as a E R², namely, ma, S Maz S ... E may.
V E mi². Based on this, the Frobenius norm of M is defined as || |= V a b, the trace of M is defined as tr(M) Di
2

---

((0) = 0.14
((() = 5.94
((() = 54.2
(a)
(b)
Illustration of the Dirichlet Energy on various graph structures and graph signals. Blue points, black edges, and red bars represent nodes, connections, and signal values on nodes, respec- tively. Upside bars represent positive values, and downside bars represent negative values.
Figure I:
2 Dirichlet Energy
Let X Ruxd be the data matrix with the n samples and d-dimensional features. In this paper, assume that the features have zero means and normalized variances namely, 1, x; 0 and x; x, 1 for i E {1...., .d.. According to the homophily assumption [10), assume that data X forms an inherent graph structure & with nodes standing for samples and edges standing for their correlations. In G. similar samples Graph G can be represented with a similarity matrix S E R4x", where St,j denotes the similarity between x and x². If $i,, = O, it means that there is no connection between x' and x in G, which is common in k-NN graphs since we only consider the local structure of the data space. Given adjacency matrix s we define the Laplacian matrix [15] as Ls = D S, where D is a diagonal matrix whose diagonal entries represent the degrees of data points, namely, di, Σド= 8i.j-
more likely to connect to each other than dissimilar ones.
Based on the Laplacian matrix Ls. we introduce the Dirichlet Energy [16] as powerful tool to identify important features. Specifically, given the Laplacian matrix Lş, the Dirichlet Energy of graph signal v is defined as
n Σ
n
Lair (v)
81. (ve - 0z)² v Lgv.
In graph theory, each dimensional feature æ; E RR can be seen as a graph signal on G. The Dirichlet Energy in Eq. (T) provides measure of the local smoothness [11] of each feature graph G, which is small when the nodes that are close to each other on G have similar feature values. Hence, the Dirichlet Energy can be used to identify informative features by evaluating the consistency of the distribution of feature values with the inherent data structure. To demonstrate this, we provide an example in Fig. [] where we generate a 2-NN graph & including two bubbles, and compose the data X using the two- -wo-dimensional coordinates of the graph nodes. Then we set the graph signal v as the first coordinate æ and visualize it on in Fig. vector. While in Fig. [[c] we change the graph structure to random 2-NN graph. We compute the Laplacian matrix Ls of each figure and present the corresponding Dirichlet Energy in the figures.
[[a] In Fig. [[b] we change v to a random noise
We can see that Fig. T(a] achieves the best smoothness, whereas both Fig. [(b) and Fig. [(c) have poor smoothness due to mismatch between the graph signal and the graph structure.
Based on the Dirichlet Energy, a well-known FS method called Laplacian Score (LS) is proposed in 13 However, the Laplacian matrix in LS is precomputed and fixed. If X contains too many irrelevant features, the quality of the graph G will be poor and not reflect the underlying structure. As illustrated in Fig. [[(c)] poor-quality graph will lead the poor smoothness even if the right feature is selected, this insight motivates us to learn graph and features jointly during the learning process.
3 Proposed Method
In this paper, we devise collaborative neural network driven by the Dirichlet Energy for joint feature and graph learning, as illustrated in Fig. Generally, the proposed framework consists of two
Note that constant features (if any) will be removed during the feature preprocessing stage.
e Note that the similarity matrix S of a k-NN graph is not symmetric. When calculating the objective in Eq.
3
we obtain the Laplacian matrix Ls using the symmetrized similarity matrix š (S + S/2
'LS considers both the smoothness and the variance of each feature. However, as assume that each feature
has unit variance according to 1, Φ; 0 and x. æ; 1, minimizing LS is equivalent to minimizing Eq. 1..
3

---

Feature Selection
DGL
A2
Dirichlet Energy
Distance
Measuring
Ls
Xd
Differentiable K-NN Selector
Selering
Gunbel
UFS
Gunbel
To Tazaal la
①
Matrix Transposition Multipiration
Saketire
Chucioky Dececppoiiim Elgendessmppstiee
Dirichlet
Energy
Adiitiun
Overview of the proposed framework, where smiley faces denote the value 1 representing that the feature selected, while sad faces denote the value 0 representing that the feature is unused. (2) Bottom Left Panel: Illustration of the Unique Feature Selector (UFS), where green bars denote the value distributions of different vectors. (3) Bottom Right Panel: Illustration of the Differentiable N--N Graph Learner (DGL), where the "Differentiable k-NN Selector" in deep blue shows how to learn nearest neighbors with the Optimal Transport theory.
Figure 2: (1) Top Panel:
modules: the Unique Feature Selector (UFS) and the Differentiable k-NN Graph Learner (DGL). At the beginning, the imput features X are selected with the learnable feature mask F generated by UFS. which is carefully designed avoid the duplicate feature selection. Based the selected data X, we measure the distances between different samples, and feed the resulting distance vectors of each sample into DGL learn their nearest neighbors. The adaptive graph structure and informative features are learned jointly under the Dirichlet Energy, so as to identify the optimal feature subset that effectively captures the underlying data structure.
3.1 Unique Feature Selector
Based on the original data X, the goal of FS is to identify a feature subset X Rexm from the original features by minimizing a prespecified target Lobj (X):
min Lobj (X) s.t. X XF, (0, dxm
Ims
F
where m S d denotes the number of selected features, and F E Rdxm denotes the selection matrix selecting features from X. Different from existing methods that use the reconstruction enror as Coss (X). , in this paper, we utilize the Dirichlet Energy in Eq. ( for FS as follows:
m
Lobs (X) Σ (o.) = tr(x Ls
Given the selection number m, Lotj updates the network parameters by minimizing the Dirichlet Energy, thereby selecting features that best reflect the intrinsic structure.
The constraints in problem 2 indicate that an ideal result F should exact and unique. Exact means the result should exactly be the original features, instead of their linear combinations. Unique means each feature should be selected only once under a given number m. These two properties require F to be binary and column-full-rani full-rank matrix including orthogonal one-hot column vectors.

---

3.1.1 Approximating Discrete Feature Selection
It is difficult to learn discrete F in neural networks due to its non-differentiable property. Inspired
by [ we propose learn the discrete distribution using the Gumbel Softmax [17 technique:
f. = softmax((log w, + gt)/TT with gt.j -log(--lop ur.)). (.i)...))) ".,j Uniform 1),
(4)
where W = W1 W2...., Wm. denotes a learnable parameter. The random vector 9, consists of Gumbel-distributee variables gi,j. which is generated with ui, sampled from Uniform distribution. Based on w, and gi. we obtain the approximated F$ vector fq that represents the i-th selected feature. The distribution of f; is controlled by a non-negative temperature parameter T. A smaller value of parameter T will generate better approximation of the one-hot vector, but will be more likely to be stuck in a poor local minimum. As suggested in [8], we employ the annealing schedule on T by initializing it with a high value and then gradually decreasing it during the learning process.
3.1.2 Selecting Unique Features
Algorithm UFS
Despite having obtained the approximated FS vectors in neural networks. Eq. (4) does not consider the uniqueness requirement of FS. This is because Eq. (4) learns each selected feature separately, and does not consider the orthogonal constraint between columns in F, which is prone to result in the repeated selection of the same features. To address this issue, we develop a unique feature selector (UFS) in Algorithm | where Ô E R(d-m)Xm denotes the zero matrix. First, we add a small
1: procedure UFS(E, c)
2:
PAP
F
F elm
LL
F F el
1 A
p
4:
F=
(L
(T-1)T
5: return F
end procedure
enough perturbation ( > 0) F F. Next, we perform the eigendecomposition (line 2) and the Cholesky decomposition (line 3) on the perturhed result respectively, and correspondingly obtain the diagonal matrix A Rmxm the orthogonal matrix P E R= and the lower triangle matrix L E Rmxm Based on A, P, and L, we obtain the selection matrix F in line 4 and have the following conclusion:
Proposition 3.1. Given any real matrix F E Rdxm, one can always generate a columm-orthoonal matrix F through Algorithm 7
The proof of Proposition 3.1 is provided in Appendix ST On the one hand, the small perturbation cmm m guarantees the column-full-rant property of F, thereby avoiding the duplicate selection results. On the other hand, the orthogonality property in Proposition 3.1 facilitates the approximation of discrete FS based on the matrix f We verify the efficacy of UFS in Section 4.2
3.2 Differentiable k-NN Graph Learner
The existence of noise and irrelevant features may negatively affect the quality of the constructed graph. As depicted in Fig. [ a low-quality graph structure can significantly perturb the smoothness of features and undermine the performance of feature selection. Hence, we propose to learn an adaptive graph during the learning process using the selected features.
3.2.1 Learning an Adaptive k-NN Graph Using Dirichlet Energy
Considering the objective function in Eq. (3), a natural way is to learn the similarity matrix S based on the Dirichlet Energy in Cody. However, this may yicld a trivial solution where, for sample æf, only the nearest data point can serve as its neighbour with probability 1, while all the other data points will not be its neighbours. To avoid this trivial solution, we propose learn an adaptive graph by incorporating the Tikhonov regularization [99 of S into the Dirichlet Energy:
min mintr ( LsX)= + a S s.t. S1, = 1,, 8i.j 2 0, 8i,5 =0 2
(5)
where denotes the trade-off parameter between the Dirichlet Energy and the Tikhonov regularization. Note that each row s² in S can be solved separately, instead of tuning a manually, we model a as
'I practice, we calculate F with F = F without eigendecomposition to achieve discrete FS vectors. We provide discussion in Appendix S2 to explain this treatment.
5

---

sample-specific parameter ag and determine it algorithmically, which plays an important role in learning nearest neighbors for each sample. Based on problem ( we define the distance matrix E
with its entries being j.j = l1(@' 5. )13. then we solve each row s' in problem (5) separately as
et 112 s.t. s1, = 1, 1,8.. 2 0, 81,3 = 0.
min ||
(6)
20;
Problem 6 can be solved easily by constructing the Lagrangian function and then using the Karush- (uhn-Tucker(KKT) conditions 200 By doing so, we obtain the solution of s1.j as
1 1e 8.J = (
+
E eW1)
)+ with
$ Bool(eis S &e,,ou);
4:
h 20:
20%
where [o1..... Tn] denotes the sorting permutation over e', i.c. 6i,01 S... Ci,o, and 6( denotes the selection vector identifying the k minimal values in e².
Recall that we aim to learn k nearest neighbors for each sample, which implies that there are only k nonzero elements in sf corresponding to the nearest neighbors. To this end, we determine the trade-off parameters Or such that S5,0r > 0 and 8t,0x11 S 0. Then we have:
(ke's E.T) - -' <a S (he't (he - with
(k) Si. -Boolees = Ci,o,)
(8)
where edx)) denotes an indicator vector identifying the k-th minimal value in e². Setting oş as the maximum and substituting into Eq. 7 we obtain the final solution as:
e Ci,o,
81,0,
ke'g. (++1) keig e²o
Bool(1 S S ks).
The detailed derivation of solution 99) can be found in Appendix S3 We note that the formulation in problem (6) bears similarity to CLR proposed in [1]. In Appendix S4 we discuss the connection between method and CLR, and highlight the differences between the two w.r.t. the feature utilization and the sorting operation. Remarkably, the k-NN can be obtained easily in CLR using off- the-shelf sorting algorithms, which not the case for neural networks due to the non-differentiabiiity of sorting algorithms. To address this issue, we propose to transform the k-NN selection into a differentiable operator utilizing the Optimal Transport (OT) (2 technique as follows.
3.2.2 Differentiable k-NN Selector
Let μa-
[M1 (41,/42... Mayl' IT and v = [1] V2 M22) be two discrete probability distributions defined on the supports A {a and B = { 5=1 respectively. The goal of OT is to find an
optimal transport plan r E Ru x between A and B by minimizing the following transport cost:
(C, F
s.t. rl,, = 14, r 1, = Ti5 2 O,
(10)
where C' R21x02 denotes the cost matrix with C.j h(a b,) 0 being the transport cost from a; to by. It widely known that the solution of the OT problem between two discrete univariate measures boils down to the sorting permutation 253 As stated in (25). if h is convex, the optimal assignment can be achieved by assigning the smallest element in A to b), the second smallest to b2, and so forth, which eventually yields the sorting permutation of A.
Given distance vector e, to learn selection vectors (A) and (A++1), we set A e, and B [0, 11....AA. k + 1). and define μl, v, and Cij as
1 Mi n' Vjj 1//n,
1 15jskt1
Gj = (a: b;)² (c: j+ 1)2. (11)
1)/n, j j=k+2
The optimal transport plan of problem 10) assigns the i-th smallest value ea, to if < < A +1 and assigns the remaining
1 values in e to bk-22. Namely,
=(0,m
1/m,
(1 i k + and j or (k + < i and = k
To.. = 00 i k and j +) or (k + 1 < i i n and j # +2)
(12)

---

Table 1: Details of data.
Type
Dataset
#Samples
#eatures
#Classes
Type
Dataset
#Samples
#Features
#Classes
Text
PCMAC 28
1943
3289
2
Artifiial
Madelon
29
2600
500
2
GLIOMA 30
50
4434
COIL-20
1440
1024
20
LUNG 33
203
3312
Yale
R3
165
1024
15
Biological
PROSTATE
34
102
5966
2
Image
Jaffc
35
213
676
10
SRBCT 36
PIX10
14
SMK 37
187
19993
2
warpPEF10P
X8
210
2420
10
Given a sample p. once we obtain the optimal transport assignment based on e", we calculate the g(k++) as follows:
variables 0(2) and 6p
& = T2 Ir
((k) p
5
e({++)
k+11
(13)
where H; and Ts. denote the i-th and the (k + 1)-th column of T, respectively. However, problem (10) still non-differentabble To address this issue, we consider the following entropy regularized OT problem:
min (C, + Σ Tay log Pay s.t. F1 = 1. w. I. 0,
(14)
where y a hyperparameter. The differentiability of problem (4) has been proven using the implicit
function theorem (see [26) Theorem 1]). Note that smaller yields better approximation to the
original solution problem (T)). but may compromise the differentiability of problem (14) (25
Problem (14) can be solved efficienlly using the iterative Bregman projections algorithm 27 the
details of which are provided in Appendix S5
4 Experiments
Our experiments fall into three parts: (1) Toy Experiments: First, we verify the FS ability and the graph learning ability of the proposed method synthetic datasets. (2) Quantitative Analysis: Next, we compare the performance selected features in various downstream tasks on real-world datasets and compare
method with other unsupervised ES methods. (3) Ablation Study: Finally, verify the effect of UFS and DGL by testing the performance of the corresponding ablated variants. We also provide the sensitivity analysis in Appendix (S6.6) The implementation details of all experiments can be found in Appendix 1
4.1 Datasets
For the toy experiments, we generate three 20-dimensional datasets named Blobs, Moons, and Circles (see Appendix 1S..1.I generation details). On top of that, we evaluate the proposed method on twelve real-world datasets that include text, biological, image, and artificial data. Table [ exxhibits the details of these datasets, which include many high nigh-dimensiooal datasets test the performance of our method. We standardize all features to zero means and normalize them with the standard deviation.
4.2 Toy Experiments
In this section, we consider three synthetic binary datasets with increasing difficulty in separating different classes. The first two dimensions in each dataset contain useful features that indicate the underlying structure, while the remaining 18 dimensions The presence of noise obscures the inherent structure of the data, which makes the graph learning process highly challenging. To see this, we generate 3-D plots of each dataset using the useful features and one noise feature, along with their 2-D projections on each plane, which are shown in Fig. a)). We can see that the noise blurs the boundary of different classes, especially in Moons and Circles. In addition, we used heat kernel (abbreviated as Heat) with 1 to learn the 5-NN graph on 20-dimensional features, as shown Fig. b). We can see that the heavy noise obscures the underlying structure of data points, resulting in chaotic graph outcome.
random noise sampled from from.)(0) (0, 1).
7

---

Blbs
Moons
Circles
(a) 3D Plot
(b) K-NN by Heat (c) K-NN by Ours (d) by Ours
(e) K-NN w/o UFS (1) w/o UFS
Figure 3: Toy results on synthetic datasets, where higher similarities are presented with thicker connections in k-NN graphs, and only present the connections to 5-NN for each sample. Blue bars and orange bars represent the distribution of fi and f2 in the FS matrix F, respectively.
Results. We our method on toy datasets for selecting m 2 target features. The results presented in Fig. [) and Fig. d), which demonstrate the success of our method in learning target features and intrinsic structures simultaneously. Moreover, it can be seen from Fig. d)d) that the proposed network obtains the approximately discrete FS vectors.
Learning Without Unique Feature Selector. In addition, conduct ablation study by removing the UFS module from the network and updating using Eq. { only. The results are shown in Fig. () and Fig. f(f,, where
that, without UFS, the ablated model repeatedly selects the same feature on all datasets. is also noteworthy that the nodes in the graph are mostly connected either horizontally vertically, indicating the effectiveness of DGL in learning the local structure solely based on the single selected feature.
4.3 Quantitive Analysis
Experimental Settings. In this section, we evaluate our method on real-world data. We partition each dataset into training data and testing data using an 8:2 ratio and identify useful features using training data. We then evaluate the performance of selected features on three downstream tasks: (1)
Classification Accuracy: We train a random forest (RF) [39 classifier with 1000 trees using selected features and evaluate the prediction accuracy the testing data. (2) Clustering Accuracy: We cluster testing set with selected features using k-means 40). where the cluster number set to #Classes. Then align the results with true labels and calculate the accuracy. (3) Reconstruction RMSE: We build 1 chidden-layer network with ReLU activation to reconstruct the original data using selected features. The hidden dimension is set to 3m/2 except for AllFea, where the hidden size is set to d. The network is learned on the training set with selected features, and evaluated on the testing set using root mean square eтror (RMSE) normalized by d.
Competing methods. We compare our methods with four deep methods (CAE 8. DUFS [4]. WAST [4]], AEFS (9) and three classical methods (LS 13, RSR (42). UDFS 43 ). Besides, we use all features (AllFea) as the baseline. To evaluate performance
each method on
downstream tasks, average the results over 10 random runs with the feature number m varied in {25, 50, 75, 100, 150, 200, 300} except for Madelon, where m is varied in (5, 10, 15, 20] since Madelon consists of only 20 useful features (29). Appendix [6.1] provides details of the overall evaluation workflow, including the implementation and the parameter selection of each method.
Results. Similar to 14], we present the best result w.r.t. m in Table 2 the standard deviations is
provided in Appendix S6.2 We also present some reconstruction results on PIXI0 by our method in Appendix S6.3) From Table 2 we find that: (1) Our method generally achieves the best performance in three tasks, indicating that our method selects more useful features. (2) In particular, we beat DUFS in all Classification and Clustering tasks, well most cases of the Reconstruction tasks. Recall that DUES also selects features based on the Dirichlet Energy. this result shows that the model (5) in method explores superior graph structure compared to the traditional Heat method. (3)

---

Table 2: Results in downstream tasks over 10 runs on optimal m that is shown in the bracket. "Cla.", "Clu." and "Rec." are short for classification, clustering, and reconstruction, respectively.
Task
Dataset
CAE
DUFS
WAST
AEFS
1.5
RSR
UDFS
Our
AllFaa
Madelon
0.65 (15)
0.52 (20)
0.87 (15)
0.87 (10)
0.51 (20)
0183 (10)
0,74(211)
0.90 (20)
0.77
PCMAC
(50)
0.77
(300)
(300)
0.91
0.87 (300)
(300)
COIL-20
1.00 (300)
1.00 (300)
1,00 (200)
1.00 (300)
0.98 (300)
1,00 (200)
1,00 (300)
1.00 (200)
1.00
Yale
0.72 (300)
0.72 (300)
0.70 (200)
0.70(150)
0.67 (200)
(272)200)
0.71 (200)
0.81 (300)
0.75
Juffe
0.97 (50)
0.97 (50)
0.97 (25)
0.97 (100)
0.97 (300)
0.98 (300)
0.98 (75)
1,00
0.98
PIXTO
0.99 (25)
0.98 (50)
0.59 (150)
0.9% (100)
0.97 (100)
0.97 (50)
0.97 (100)
1.00 (25)
0.97
WaIpPHELPP
0.96 (100)
0.96 (200)
0.95 (500)
0.98 (75)
0.96 (500)
0.98 (300)
0.97 (210))
0.99 (300)
0.98
Cla.
GLIOMA
0.68 (200)
0.66 (500)
0.72 (100)
0.63 (300)
0.67 (200)
0.67 (300)
0.68 (75)
0.81 (300)
0.72
(ACC 19
LUNG
(100)
0.57 (150)
(300)
(300)
(200)
0.93 (300)
0.91 (300)
PROSTATE
0.88 (300)
0.81 (150)
0.81 (300)
0.81 (150)
0.88 (300)
0,90 (150)
0.90 (300)
0.89 (300)
0.89
SRBCT
0.99 (300)
0.94 (150)
0.98 (300)
0.95 (200)
0.98 (300)
1.00 (200)
1.00 (150)
0.98 (150)
0.99
SMK
0.67
0.66 (50)
(50)
(300)
0,72 (75)
0.73 (100)
0.75 (200)
Average manking
4.7
5.9
4.9
5,5
6.3
2.8
1.8
3/2
# Top-1
1
3
9
2
Madelon
0,60 (15)
0:52 (15)
(.52(115)
(5)
0.52 (20)
0.61 (15)
0.57 (21)
0.60 (20)
0.58
PCMAC
0.52 (150)
0.51 (25)
0.51 (25)
0.51 (100)
0.52 (75)
0.51 (25)
0.51 (150)
0.53 (200)
0.51
COIL-20
0.69 (100)
0.59 (150)
0.65 (200)
0.60 (300)
0.53 (300)
0.59 (300)
(300)
0.66 (200)
0.63
Yale
0.55 (100)
0.55 (150)
(100)
0.54 (300)
0.58 (300)
(300)
0.58 (200)
0.62 (300)
0.61
Jaffe
0.85 (300)
0.50
0.83 (300)
(300)
(200)
0.83 (150)
0.83 (200)
(200)
PIXTO
0.86 (200))
0.79 (150)
0.85 (150)
0.79 (300)
0.85 (75)
0.72 (300))
0.81 (210)
0.87 (300)
0.78
WarPPIFTOP
0.55 (75)
0.42 (500)
0.44 (50)
0.53 (25)
0.55 (200)
0.57 (75)
0.49 (25)
0.51 (25)
0.45
Clu.
GLIOMA
(50)
0.65 (50)
(25)
(300)
(300)
0.65
0.68 (75)
(ACC
LUNG
0.64 (150)
0.64 (100)
0.62 (75)
0.66 (150)
0.65 (200)
0.69 (300)
0.61 (300)
0.72 (150)
0.69
PROSTATE
0.64 (25)
0.59 (150)
0.58 (300)
0.59 (25)
0.71 (25)
0.63 (25)
0.69 (25)
0.68 (50)
0.64
SRBCT
0.76 (150)
0.54 (75)
0.56 (200)
0.57 (200)
0.56 (200)
0.60
0.59 (150)
0.63 (50)
0.52
SMK
0.60 (300)
0.58 (25)
0.58 (25)
0.58 (50)
0.59 (50)
0.59 (50)
0.61 (200)
(25)
Average ranking
2.8
6.6
5.7
6
5
4.3
1.8
5.1
# Top-1
0
0
7
Madelon
0.99 (20)
0.99 (20)
0.98 (20)
0.98 (20)
0.99 (20)
0.98 (20)
0.98 (20)
0.98 (10)
0.28
PCMAC
1.34 (25)
1.03 (25)
1.05 (25)
1.05 (25)
1.04 (25)
(.1)
1.07 (25)
1.30 (25)
0.78
COIL-20
0.48 (300)
0.41 (500)
0.43 (300)
0.41 (300)
0.48 (300)
0.45 (300)
0.41 (300)
0.38 (300)
0.27
0.63 (300)
0.56 (500)
0.56 (300)
(300)
0.78 (200)
0,57 (300)
(200)
(300)
Jaffe
0.31 (300)
0.25 (300)
0.26 (300)
0.25 (300)
0.33 (200)
(300)
0.25 (300)
0.22 (300)
0.23
PIXIO
0.49 (300))
0.43 (500)
0.46 (300)
0.43 (300)
0.63 (50)
0.46 (300)
0.47 (300)
0.39 (300)
1.20
WasPPEELOP
0.26 (300)
0.27 (300)
(300)
0.45 (300)
0.27 (300)
(300)
Rec.
GLIOMA
0.74 (300)
0.71 (300)
0.71 (300)
0.73 (300)
0.71 (300)
(300
0.72 (300)
0.69 (300)
1.86
(RMSE
ULUNG
0.94 (300)
0.77 (300)
0,77 (300)
0.78 (300)
0.82 (300)
0.81 (300)
0.79 (300)
0.80 (300)
0.82
PROSTATE
1.00 (300)
0.78 (300)
0.77 (300)
(300)
0.72
0.74 (200)
0.71 (300)
0.73 (300)
1.48
SRBCT
0.84 (300)
0.77 (300)
0.77 (300)
(300)
0.80 (200)
0.79 (200)
0.78 (300)
(300)
SMK
0.98 (25)
0.68 (300)
0.68 (300)
0.68 (300)
0.78 (300)
0.78 (300)
0.73 (300)
0.69 (300)
4.32
Averago ranking
7.9
3.5
3.2
6.4
5,5
4.1
2.7
4.8
Top-1
Table 3: Results in ablation studies, where "w/o" is short for "without".
Task
Method
Madelon
PCMAC
Jaffe
PIXIO
GLIOMA
PROSTATE
Heat
0.5411001
0.5110.000
0.60=0.13
0.41:10.06
0.55 0.48=0.05
Effect of FS
DGL only
0.50++0.00
0.50++000
0.57-0.05
0.76++0.09
0.55-0.04
0.56++0.07
(Clu. with SC)
Our
0.5811.001
0,51
0.80 0.07
0.77.10.04
0.04
0.65.10.02
Effect of DGL.
w/o DGL.
0.51++0.02
0.72+0.02
0.97-0.01
0.98+-0.03
0.
0.81+00.44
(Cla, with RF)
Our
0.90:10.01
0.79
1.00 0.01
1.00
0.81 0.09
1.095
In classification and clustering, the best performance is mostly achieved by FS methods with fewer features, which verifies the necessity of FS. (4) AllFea achieves five optimums in Reconstruction, which is not surprising since, theoretically, AllFea can be projected to original features with an identity matrix. However, in biological data, the best reconstruction results are achieved by FS methods, probably because the high-dimensional data leads to overfitting in networks. (5) It is noteworthy that the reconstruction of Madelon poses significant challenge for FS methods, indicating the difficulty of reconstructing noise even using useful features. This observation supports our claim regarding the lack of reasonability in selecting features based on the reconstruction performance in Section I
4.4 Ablation Study
In this experiment, demonstrate the efficacy of the UFS and the DGL modules through ablation studies on six datasets: Madelon, PCMAC, Jaffe, PIX10, GLIOMA, and PROSTATE.
Effect of FS. Recall that we have demonstrated the efficacy of UFS in Fig. To further verify the efficacy of FS in graph learning, we remove the entire FS module from the framework and learn the graph using all features based on DGL. We also compare the graph learning result using Heat. We
9

---

cluster the obtained graphs with the spectral clustering (SC) method to verify their qualities. We tune the parameter a of Heat in (1.2..... 5), and fix = 5 for our method and the variant. The results are shown in Table which shows that FS has positive effect on graph learning compared with "DGL only". Besides, in Appendix [56.4] we visualize the learned graph on COIL-20 and Jaffe using I-SNE, which shows that using fewer features, we achieve separable graphs that contain fewer inter-class connections than other methods.
Effect of DGL. To verify the efficacy of DGL, we remove it from the model and learn the ablated variant with a fixed graph learned by Heat. Similar to Section 4.3 we first learn selected features using competing method, then evaluate the features in downstream tasks. We present the classification result in Table 3] and leave the other results in Appendix [S6.3] due to limited space. We can see that our method significant outperforms the ablated variant, especially in Madelon. This is probably because the noise undermine the graph structure and disrupt the learning of informative features.
5 Discussion
Conclusion. This paper proposes a deep unsupervised FS method that learns informative features and k-NN graph jointly using the Dirichlet Energy. The network is fully differentiable and all modules are developed algorithmically to present versatility and interpretability. We demonstrate the performance of our method with extensive experiments on both synthetic and real-world datasets.
Broader Impact. This paper presents not only an effective deep FS method, but also a differentiable k-NN graph learning strategy in the context of deep learning. This technique is particularly useful for end-to-end learning scenarios that require graph learning during the training process. And we do notice this practical need in existing literature, see [44] for example. We believe our study will inspire researchers who work on the dimensionality reduction and graph-related researches.
The major limitation of the proposed method is the lack of scalability, for which we do not evaluate method large datasets. This is because problem (14) requires iterative solution, requiring storage of all intermediate results for back-propagation. While literature [26] proposes memory-saving approach by deriving the expression of the derivative of I mathematically (see 26 Section 3J), it still requires at least (nk) space to update all intermediate variables to learn k nearest neighbors for singe sample, which results in O(n²k) space complexity learn for all samples. This is a huge memory cost on large datasets. Although learning in batch seems to be the most straightforward solution, in our method, the neighbours of each sample are determined based on the global information of L which has an n X n size. This requires to load the entire batch's s information during each iteration, for which we cannot employ subgraph sampling as other graph learning methods did to mitigate memory overhead. Another limitation of the proposed method is the low computational speed, as reported that the OT-based sorting can be slow (45
Limitations.
The future developments of the proposed method are twofold. First, we will try more differentiable sorting algorithms enhance computational speed. For example, reference [45) proposes to construct differentiable sorting operatooss as projections onto the permutahedron, which achieves a O(n log n) forward complexity and (n)) backward complexity. Second, due to the large cost of the global relationship in Ls, we are considering adopting a bipartite graph [16] [46] to make batch learning feasible. This graph introduces small number of anchor points, which are representative of the entire feature space. By doing this, smoothness can be measured based on the distance between samples to anchors, for which sample-to- cample-to-sample to-mpel relationships are no longer needed and the batch learning is enabled. It is worth noting that this idea is still in its conceptual stage, and we will explore its feasibility in upcoming research.
Acknowledgments
This work was supported in part by the National Natural Science Foundation of China under Grant 62276212 and Grant 61872190, in part by the National Key Research and Development Program of China under Grant 4022YFB3303800, and part by the Key Research and Development Program of Jiangsu Province under Grant B02021093.
10

---

References
[1] Y. Li, C. Luo, and S. M. Chung, "Text clustering with feature selection by using statistical data," IEEE Trans. Knowl. Data Eng., vol. 20, no. 5, pp. 641 2008.
[2] C. He, K. Li, Y. Zhang, Y. Zhang, Z. Guo, X. Li, M. Danelljan, and F. Yu, "Strategic preys make acute predators: Enhancing camouflaged object detectors by generating camouflaged objects," arXiv preprint arXiv:2308. 03166, 2023.
[3] H.-J Yu and D.-S. Huang. "Normalized feature vectors: novel alignment-free sequence comparison method based on the numbers of adjacent amino acids," IEEE/ACM Trans. Comput. Biol. Bioinformatics, vol. 10, no. pp. 457-467, 2013.
[4] C. He, K. Li, Zhang, L. Tang, Y. Zhang, Z. Guo, and X. Li, "Camouflaged object detection with feature decomposition and edge reconstruction," in Proc. CVPR, 2023, pp. 22 046-22222000 055.
[5] Z. Sun, G. Bebis, and R. Miller, "Object detection using feature subset selection," Puttern Recognit., vol. 37, no. 11, pp. 2165-2161111111 2176, 2004.
[6] L. Xu, R. Wang, F. Nie, and X. Li, "Efficient top-k feature selection using coordinate descent method," in Proc. AAAI, vol. 37, no. 9, 2023, pp. 10 594-10601.
[7] C. He, K. Li, Y. Zhang, G. Xu, I.. Tang. Y. Zhang, Z. Guo, and X. Li, "Weakly-supervised concealed object segmentation with sam-based pseudo labeling and multi-scale feature grouping." arXiv preprint ar3iv:2305. 1003, 2023.
[8] M. F. Bali, A. Abid, and J. Zou, "Concrete autoencoders: Differentiable feature selection and reconstruction," " in Proc. ICML, vol. 97, 2019, pp. 444-453.
[9] K. Han, Y. Wang, C. Zhang, C. Li, and C. Xu, "Autoencoder inspired unsupervised feature selection," in Proc. ICASSP, 2018, pp. 2941-2945.
[10] M. McPherson, L. Smith-Lovin, and J. M. Cook, "Birds of a feather: Homophily in social networks," Annu. Rev. Sociol., vol. 27, no. 1, pp. 415-444, 2001.
[11] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, "The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains," IEEE Signal Process. Mag., vol. 30, no. 3, pp. 83-98, 2013.
[12] R. Wang, P. Wang, D. Wu, Z. Sun, F. Nie, and X. Li, "Multi-view and multi-order structured graph learning," " IEEE Trans. Neural Netw. Learn. Syst., pp. 1-12, 2023.
[13] X. He, D. Cai, and Niyogi, "Laplacian score for feature selection," in Proc. NIPS, 2005, pp. 507-514.
[14] O. Lindenbaum, U. Shaham, Peterfreund, J. Svirsky, N. Casey, and Y. Kluger, "Differentiable unsupervised feature selection based on gated laplacian," in Proc. NIPS, vol. 34, 2021, pp. 1530-1542.
[15] U. Von Luxburg, "A tutorial on spectral clustering," Stat. Comput., vol. 17, pp. 395 416, 2007.
[16] R. Chung, Spectral graph theory. American Mathematical Soc., 1997, vol. 92.
[17] E. Jang, S. Gu, and B. Poole, "Categorical reparameterization with gumbel-softmase arXiv preprint arXiv: 161 1.01 1.01 2017.
[18] C. J. Maddison, Mnih and Y. W. Teh, "The concrete distribution: continuous relaxation of discrete random variables." in Proc. ICLR, 2017.
[19] A. Tikhonov and V. Arsenin, Solutions of Ill-posed Problems. Winston, 1977.
[20] S. P. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2014.
[21] Nie, X. Wang, M. Jordan, and H. Huang, "The constrained laplacian rank algorithm for graph-based clustering," in Proc. AAAI, vol. 30, no. 1, 2016.

---

[22] L. V. Kantorovich, "Mathematical methods of organizing and planning production," Manage. Sci., vol. no. pp. 366 366-4666622 422, 1960.
[23]
Santambrogio, Optimal Transport for Applied Mathematicians. Birkhäuser, 2015.
[24] G. Peyré and M. Cuturi, "Computational optimal transport," arXiv preprint 2020.
[25] M. Cuturi, O. Teboul, and J.-P. Vert, "Differentiable ranking and sorting using optimal transport." in Proc. NIPS, vol. 32, 2019.
[26] Y. Xie, H. Dai, M. Chen, Dai, T. Zhao, H. Zha, W. Wei, and T. Pfister, "Differentiable top-k with optimal transport," in Proc. NIPS, vol. 33, 2020, pp. 20 530-20531.
[27] J.-D. Benamou, G. Carlier, M. Cuturi, L. Nenna, and G. Peyré, "Iterative bregman projections for regularized transportation problems," SIAM J. Sci. Comput., vol. 37, no. 2, pp. Al111-A1138, 2015.
[28] K. Lang, "Newsweeder: Learning to filter netnews," in Machine Learning Proceedings 1995. Morgan Kaufmann, 1995, pp. 331-339.
[29] Guyon, J. Li, T. Mader, A. Pletscher, G. Schneider, and M. Uhr, "Competitive baseline methods set new standards for the nips 2003 feature selection benchmark," Pattern Recognit. Lett., vol. 28, no. 12, pp. 1438-1444 1444, 2007.
[30] C. L. Nutt, D. Mani, R. A. Betensky, P. Tamayo, G. Cairneross, C. Ladd, U. Pohl, C. Hartmann, M. E. McLaughlin, T. T. Batchelor, P. M. Black, A. von Deimling, S. L. Pomeroy, R. Golub, and Louis, "Gene Expression- Classification of Malignant Gliomas Correlates Better with Survival than Histological Classificationl," Cancer Res., vol. 63, no. 7, pp.
1602-1607, 2003.
[31] S. Nene, S. K. Nayar, H. Murase al., "Columbia object image library (coil-100))" Tech. Rep. CUCS-005-96, 1996.
[32] H. Peng, F. Long, and C. H. Q. Ding, "Feature selection based on mutual information: Criteria of max-dependency, max-relevance, and min-redundancy." IEEE Trans. Pattern Anal. Mach. Intell., vol. 27, no. 8, pp. 1226-1238, 2005.
[33] D. Cai, C. Zhang, and X. He, "Unsupervised feature selection for multi-cluster data," in Proc. SIGKDD, 2010, pp. 333-342.
[34] I. Petricoin, Emanuel F., D. K. Ornstein, C. P. Paweletz, Ardekani, Hackett, B. Hitt, A. Velassco, C. Trucco, L. Wiegand, K. Wood, C. B. Simone, P. Levine, W. M. Linehan, M. R. Emmert-Buck, S. M. Steinberg, E. C. Kohn, and L. A. Liotta, "Serum Proteomic Patterns for Detection of Prostate Cancer," J. Natl. Cancer Inst., vol. 94, no. 20, pp. 1576-1578, 2002.
[35] M. Lyons, J. Budynek, and S. Akamatsu, "Automatic classification of single facial images." IEEE Trans. Pattern Anal. Mach. Intell., vol. 21, no. 12, pp. 1357-1362, 1999.
[36] Khan, J. S. Wei, M. Ringner, H. Saal, M. Ladanyi, F. Westermann, F. Berthold, M. Schwab, C. R. Antonescu, C. Peterson et al., "Classification and diagnostic prediction of cancers using gene expression profiling and artificial neural networks," Nat. Med., vol. 7, no. 6, pp. 673-679, 2001.
[37] A. Spira, J. F. Beane, V. Shah, K. Steiling, G. Liu, F. Schembri, S. Gilman, Y.M. Dumas, Calner, P. Sebastiani et al., "Airway epithelial gene expression in the diagnostic evaluation of smokers with suspect lung cancer," Nat. Med., vol. 13, no. 3, pp. 361-366, 2007.
[38] T. Sim, S. Baker, and M. Bsat, "The cmu pose, illumination, and expression database," IEEE Trans. Pattern Anal. Mach. Intell., vol. 25, no. 12, pp. 1615-1618, 2003.
[39] L. Breiman, "Random forests," Mach. Learn., vol. 45, pp. 5-32, 2001.
[40] MacQueen, "Classification and analysis of multivariate observations," in 5th Berkeley Symp.
Math. Statist. Probability, 1967, pp. 281-297.
12

---

[41] G. Sokar. Z. Atashgahi, M. Pechenizkiy, and D. C. Mocanu, "Where to pay attention in sparse training for feature selection?" in Proc. NIPS, 2022.
[42] Zhu, W. Zuo, L. Zhang, Q. Hu, and C. Shiu, "Unsupervised feature selection by regularized self-representation:; Pattern Recognit, vol. 48, no. 2, pp. 438 2015.
[43] Y. Yang, H. T. Shen, Z. Ma, Z. Huang. and X. Zhou, "I.2,I-omm regularized discriminative feature selection for unsupervised learning," in Proc. IJCAI, 2011, pp. 1589-15994
[44] S. Miao, Y. Luo, M. Liu, and P. Li, "Interpretable geometric deep learning via learnable randomness injection," in Proc. ICLR, 2023.
[45] M. Blondel, O. Teboul, Q. Berthet, and Djolonga, "Fast differentiable sorting and ranking," in Proc. ICML, vol. 119, 2020, pp. 950-959.
[46] W. Liu, J. He. and S.-F. Chang, "Large graph construction for scalable semi-supervised learning," Proc. ICML, 2010, pp. 679-686.
[47] 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, "Scikit-learn; Machine learning in Python," J. Mach. Learn. Res., vol. 12, pp. 2825-2830, 2011.
[48] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga et al., "Pytorch: An imperative style, nigh-perrformace deep learning library," Proc. NIPS, vol. 32, 2019.
13

---

S1 Proof of Proposition 3.1
Proposition 3.1. Given any real matrix F R one always generate a column-orthogonal matrix F through Algorithm 1
Proof. We begin our proof by showing the feasibility Algorithm for any real matrix F, as the eigendecomposition, Cholesky decomposition, and inverse mentioned in the algorithm are subject to
specific conditions. For simplicity, we represent A = F F + el with e O. Note that for any nonzero real column vector R", we have
T A= =f F = (Pa t ==
12
0.
(S1)
Hence, the matrix A is positive-definite and can be eigendecomposed A PAP-1 where P E RRm is the square matrix whose i-th column is the eigenvector of A and A E R is the diagonal matrix whose diagonal entries are the corresponding eigenvalues. Moreover, it is easy show that A is symmetric, for which we have p =P- Therefore, we prove that A can be decomposed A PAP (line Algorithm
Since A is symmetric and pesitive-definite we will be able to perform Cholesky decomposition on A as LL" T = A (line 3 in Algorithm []. which yields lower triangular matrix L E Rm*m whose diagonal entries are all real and positive. This means that the determinant of L is larger than zero and L is invertible, which provides the feasibility of L- (line 4 in Algorithm 1 Consequently, the feasibility of Algorithm for any real matrix F is proved.
A 1/2
Next, we show that F is a column-orthogonal matrix. We denote Q =
and have:
0
q= [
1/2
A 12 = PAP A LL 6']
(S2)
Ó
Then we prove the orthogonality of the matrix F follows:
Q(I
-I-1
(S3)
(1')-
=Im
The proof is completed.
$2
Discussion on Algorithm
Although Algorithm [heoreticaly guarantees the orthogonality of the selection matrix F, utilizing this algorithm directly would bring us back to the problem of how to choose features and how to obtain discrete results. On one hand, the -onuuueqsss of cigendecomposition in line 2 prevents us from ensuring the discrete properties of matrix F. On the other hand, it is important to note that
A 1/2
in line 4 of Algorithm I we aim to construct column full-rank matrix Q
whereas
the construction of Q is also not unique since we can insert d - m zero rows at any position within the original matrix A 1/2pTT to achieve the column full-rankness. The placement of these zero rows directly affects the result feature selection.
Guided by Algorithm I devise more empirical approach by caleulating F with F F(L which effectively tackles the above two concerns. By doing so, we avoid the non-uniqueness of cigendecomposition, thereby obtaining solution that is discrete as F. Additionally, this approach ensures that the information of feature selection in F is retained within the column full-rank matrix.
14

---

Actually, F is an e-approximation of column-orthogen matrix, since we have:
= F(F
L - (A- )T
AL 1 - (L
(S4)
= -
m - cL
The experimental results in Section 4.2 verify the effectiveness of this approach in successfully
avoiding duplicate feature selection.
$3
Derivation of the Solution to Problem 5
Recall that we aim to solve the following problem to learn an adaptive k:-NN graph:
min
tr X Ls x)
2 S s.t. S1, = In 8i,j 2 0, 81,5 = 0,
S
(S5)
minl 81
l1
2t )|2sا + anolj
81 = 1,81 2 0, 81, = 0. s.t. Σ
j=l
Based on X, we define the quantity ei, = 11(0² +')l then we solve each row in problem (S5 separately as:
min %1
C St, + +a,s
s.t. Σ
Sij
2 0, S1,5 = 0, St.
2
j=1
j=1
min-
($i.)
+
Cii )²
8.t. Σ
8i.j = 1,, 2 81, = 0,
(S6)
#1.
2
200
j=1
1=1
e¹
min
|
11
s'1,
2 0, 8;,i 0.
20;
We first omit the constraint 8,, = 0 and consider it later, and solve problem (56) with the first two constraints, the Lagrangian function of which is as follows:
e'
n
C(s', >o, 3*) 2 8
1| Ar(8'1, 1) Σ
8i
Bi.j
(S7)
201
j=1
where \; and Bay are Lagrange multipliers. The derivative of L(s', >i. 3¹) w.r.t. 8i,5 is:
ac
Ci,j >; - Big
8i.
(S8)
Dss.j
20;
Then we have the Karush-Kuhn-Tiee
(uahnnTTcce((KKTT) conditions
20 of problem S7 as follows:
8i.j + Ei
Xe - Bi,j =
20
Si.j
j=1
(S9)
St
Big 2 0
BL,Siis 0.
Then we have:
eid )
81.j = (Ai
(S10)
20
15

---

Recall that there are only k nonzero elements in s' corresponding to the nearest neighbors of sample according to the constraint プラ=1 $1.j
k nonzero entries in s', we have:
1e
(A: Σ
Li = -1 200
1 A h
with
& = Bool(eis S ei,o),,
(S11)
20,
==1
where ( denotes the selection vector identifying the h minimal values in e', and σ [o....., nn) denotes the sorting permutation over e', i.e. ci,0r S ... S Ei,o,, Without loss of generality, we assume e' has no duplicates, namely Ci,rr <... < Ci,o.- Considering the constraint 81,i = 0, since 6i, = being the minimal value e holds for all samples, we replace ε, with a sufficiently large value to skip over this trivial solution.
Substituting (S11) into $10 we have:
EiJ
(S12)
h
h: 20;
20
Recall that there only nonzero entries in s², have
1 1e' (k)
1 ee'd
+
cLoo O,
1
eioo-
S O.
(S13)
1. 20;
20.
To
20;
20;
Note that we assume 0₁ > then we have
2 (keer! e'd!()) <a a; / (k+()))))))))))))) (
el((!)) with
(k) <
Booo(eis ,,,,), (S14)
where 5/²) is an indicator vector identifying the k-th minimal value in ef. According to S14 we set ag as maximal value as follows:
a, 5 (kele((t11) e'o!!)).
(S15)
Substituting S15 into Eq. S12
we have:
1 e 0(h)) (k)
Cij
81.
k
1: 20;
20
20:
e² 60(1))
keij )+
2k0;
ke'g
Ei
(k+1)
e (k)
+ e'0 61h)
keid
(S16)
kike c (k+l)
(()(
e'g! (k+1) -iij
(k+1) e 8 )+
ke
Eq. (116 is used for implementation in our code. Note that since ci .... Blio < Ci Ci we have
k
ke ke'g! (k+1) e2 -ke
Cioo
(Ci - -Gioo)) > 0.
(S17)
p=1
p=1
Then we obtain the solution of Ss.j as
e eig! (k+1)
Ci,g, (++1)
1 15isk
81.0y
keig!
-eio!
(818)
0,
otherwise
which is exactly the solution of Eq. (9) in our main paper:
e'c. Ci,a;
8i,05
k (++1)
e'o(
Bool(1 Sj S k).
(S19)
16

---

S4 Connection to CLR
We note that similar formulation problem 6 has been proposed in [1 (coined CLR), which expects closer samples to have higher similarity. It aligns with the notion of "smoothness" as we mentioned in Section 2 However, our method differs from CLR in at least two crucial aspects: Firstly, CLR measures the distance quantity Ei across all original features, making it more sensitive to the noise and irrelevant features in the original data. In contrast, our approach learns the graph structure using only informative features, resulting in enhanced robustness against noisy features. Secondly, it important to note that CLR is proposed in the context of traditional machine learnin..
where optimization is straightforward, as )(a) and <: ((++1)) can be updated using off-the-shelf sorting algorithms. Different from CLR, problem [6] is introduced in the realm of deep learning, where conventional sorting algorithms are non-differentiable and not applicable. This poses a huge challenge in learning an adaptive k-NN graph in neural networks. To overcome this challenge, we proposed to transform the top-k selection into a differentiable operator using the Optimal Transport technique.
S5 Iterative Bregman Projections
In this paper, we employ the iterative Bregman projections 27 algorithm solve the following problem:
Cin)
+ Σ Tis log Pigh s.t. Fla42 = n, r 1n = 1, 2 O.
(S20)
F
We first initialize two variables R and K (=x(k+2) u, 1/(k+2) and k., Sush, respectively. Then based on the following formulations, we repeatedly updating u and v for iterations:
(S21)
Ku' where the division in Eq. (S21 is feement-wise. In this paper, we set ( 200. After updating iteration, we obtain the optimal transport plan r as
KT
r = diag(v) K K diag(u).
(S22)
S6
Supplementary Experimental Details
S6.1
Implementation Details
All experiments are conducted on a server equipped with an RTX 3090 GPU and an Intel Xeon Gold 6240 (18C36T) @ 2.6GHz 2 (36 cores in total) CPU.
S6.1.1 Synthetic Datasets
We generate three datasets for toy experiments: (1) Blobs, (2) Moons, and (3) Circles. For each dataset, we generate the first two features using the scikit-lear library 47 by adding noise sampled from (00, 0.1). Additionally, we generate 18-dimensional noise features sampled from N/ 1).
1..1.2 Competing Methods
The implementation details of different methods, as well as their corresponding parameter selections
are provided below:
Our method is implemented using the Py PoTch framework (48). We train our method using the Adam optimizer for 1000 epochs on all datasets, with the learning rate searched from {10-1, 1,00 1 2000-000011_0 1, 100 10 We search the parameter Y in {10-3, 3, 10 - 10-1) and the parameter h. in 21 5). Note that the implementation of differentiable top-k selector is based on the code provided by (26) in htttps:/ppapers.ningg mips. Aatts--bbttttttttteaaeae html, which provides more memory-saving backward implementation compared to directly using the autograd method in Py Torch.
Our Method:
17

---

Where to Pay Attention in Sparse Training (WAST) 4I]: We use the official code released in litps://github. com/ whwa/aaaaaaaaaaaaaa /WST The parameter settings were adopted in accordance with Appendix A. of the original paper. Specifically, we train each dataset for epochs using stochastic gradient descent with a learning rate of 0.1 for all datasets except for SMK, where the learning rate is set to 0.01. For the parameter X, we set À = 0.9 on Madelon and PCMAC, À 0.4 on all image datasets, À 0.1 on all biological datasets except SMK, and X = 0.01 on SMK. The remaining parameters are kept as they were in the original paper.
Differentiable Unsupervised Feature Selection (DUSS) [4] released in htttttp:://ggttii of DUFS. For all datasets, we set 2, and train the method with SGD with a learning rate of 1 for 10000 epochs according to Appendix S7 in the original paper. We set the parameter C 5 on all datasets except for SRBCT, COIL, and PIXIO, where C is set to 2.
We use the official code com/ SarrrinnDUUFF DUFS and use the parameter-free loss version
Concrete AutoEncoder (CAE) 8 We use the official code released in httpts:/// hete:://githie gitb ccommffaainn/Caaccccco www.neennnnneeeeneeeeeeeeeeeeee Autoencoders, Since we could not find too much description about the parameter settings on different datasets in the original paper, we run CAE with default settings the code.
AutoEncoder Feature Selector (AEFS) [9] The original code provided by the au- thors is implemented in MATLAB, and requires a prohibitively long time to run this method MATLAB. Therefore, following the treatment in 411, use the code provided by the authors of CAB in https:///ithii: periments/geneeatee tatrt//ggeeeateecopariiinnn figures.py in their repository). We search the param- eter a in {10-9, 10-6, 10-3 10", 103, 10 10%), and the size of the hidden layer in {128, 256, 512, 1024].
com Offirlin/iii
(see ex-
Laplacian Score (LS) [3: : We use the official code released in/ttpp://ww cad. ..j...e.d. edu cn/home/ aanoom//deggai/Dataaa Bataa//DDDaa/Reoouuueeeeee
use the heat ker- nel for graph construction, and fix the size of neighbors & as 5 for all datasets.
Regularized Self Seff-Representation (RSR) 42
We use the official code released in We search the parameter in
httb::://githbb. com AWI.AESSKKEEEEEEEEE TJU/ RSR PR2015
{10 1, 10 1000 10", 10",10",,001 1.
We use the code provided in / jie weseegggttt github. 10/ code. html We use the heat kernel for graph con- struction, and fix the size of neighbors à as 5 for all datasets. We search the parameter y in (10-9,10 1, 10 10 100, 10%, 10
Unsupervised Discriminative Feature Selection (UDFS)
4
S6.1.3 Evaluation Workflow
The overall evaluation workflow in Section 4.3 is shown in Algorithm S2 which includes two steps:
1. Given the dataset X and prespecified feature number m, we first randomly split the dataset using an 8 2 ratio and select features based on the training set Xtr by FS method & using different parameters θ as shown in Algorithm SS]] This allows us obtain FS results under different parameter candidates 0; along with the corresponding reduced training data X and testing data X Based on the reduced data, we perform classification tasks on these datasets with the random forest, thereby obtaining the classification performance for each parameter combination. We select the parameter combination with the best classification performance the optimal parameter () for 3.
2. Based on the optimal parameter 6*, we construct the FS model Sa. and evaluate its perfor- mance in different downstream tasks. To avoid randomness, 10 times. With each random split, we use the training set Xsr to select features, and obtain reduced training set X fr and testing X te. We use these sets for downstream tasks in- cluding classification, clustering, and reconstruction, and obtain corresponding performance metrics. For each downstream task, calculate the average metric over 10 runs as the performance of 3 for the given number m.
randomly split the dataset
For each dataset, we vary the value of m and follow the aforementioned procedure to obtain the cor- responding performance. For each downstream task, we report the best metric and the corresponding feature number as the performance of the FS method in this downstream task.
18

---

Algorithm S1 Param_ _aaa__nning
Input: Training data (X tr Ver), testing data (X tex Yte), selected number m, FS method 3, and parameter set + = {0:}-
Output: Optimal parameter 8"
1: for 0, in ② do
2:
{ = 80, m);
Determining selected features by 3 under the parameter 0,. X fr = (ir X xte(;, (); & Generating reduced datasets using selected features.
3:
4:
ACC RF(X fy Dirr Xee ter VleD Evaluating selected features with random forest classifier.
5:
if ACC > ACC then
6:
ACC ACC;
7:
l" = 8
8: end if
9:
end for
Algorithm S2 Overall evaluation workflow
Input: Original dataset (Xx,, y), selected feature number m, FS method 8, parameter set θ = {0:}.
and downstream tasks = {Ti}.
Output: Performance M = (M.) in downstream tasks.
1: Partitioning the dataset into training data (Xir ir Ptr) and testing data (X te: Wre).
2: Determining 8" by Param titt__ttnnnnXXtt tr: Yor), (Xte, Mte). m, 3. θ) in Algorithm S1
3: for = 10 do
4: Partitioning the dataset into training data (X tri yoy) and testing data (X tes Ura).
5: m- So (Xtr, tr. m);
6: X tr = (tr(: ".,,s"),"" X,, = {=)::E");
7:
for T, in T do
8:
m T(( tr: Ytrr X'ce Diedi D Evaluating the performance in downstream tasks.
9: end for
10:
end for
for T, in I do
12: M, = Average(m((f:)))
end for
S6.1.4 Evaluation Metrics
We employ two metrics in our experiments: the accuracy (ACC) and the root mean square error (RMSE) normalized by d.
The formulation ACC is
ACC Ū) Σ 1 Bool 5)))
(S23)
where y E RD denotes the groundtruth labels and RD denotes the prediction label.
The formulation of RMSE normalized by is
Σ 12 x a a01
RMSE(X. X X, x)
(S24)
X d
where X
[2:; ...; [..] and X [ d2; : Sa denote the original feature matrix and the reconstructed feature matrix, respectively.
$6.1.5 Formulation of Heat Kernel Method
Here we describe the heat kernel (Heat) method compared in this paper. To implement Heat, we first compute the similarity matrix Š as follows:
$1.
exp(
(S25)
20
19

---

Based on S, we keep the k-nearest neighbors for each sample. Namely, for each sample i, we obtain its similarity vector s' as
Bi.j 0,
x E R(x')
$i.j
(S26)
otherwise
where R(x') denotes the i nearest neighbors of æ'. When we need to calculate the Laplacian matrix using S (for example, when we analyze the effect of DGL in Section 4.4), we use the symmetrized version of S:
$ S' +
(S27)
2
S6.2 Standard Deviations of Quantitative Analysis
Table ST Table S2 and Table S3
exhibit the mean and the standard deviations of the results in Table
2 in Section 4.3
Table S1: Classification results with standard deviations.
Dataset
CAE
DUPS
WAST
AEFS
LS
RSR
UDFS
Our
AllFeaa
Madelon
0.65-0.04
0.52-0.04
0.87++002
0.87++0.01
0.51++0.01
0.83++0.02
0.74+00.6
0.90++0.01
0.73+00.02
PCMAC
0.79=0.06
0.77=0.02
0.83:10.11
0.711:0.33
0.68:10.03
0.91+0.02
0.87:10022
0.79:1001
0,93:1.01
COIL-20
1.00=0.01
1.0000000
1.0000.00
1.0000.00
0.9810.01
1.00=:0.00
1.00=0.00
1.00=0.00
1.00=0.00
Yale
0.72=0005
0.72=0005
0.70110055
0.70:10.06
0.67::0.07
0.72:10.08
0.71:00066
0.81
0.75
Jaffe
0.97=0.02
0.97=0001
0.97+0001
0.974:0011
0,971:0.33
0.98:10.22
0.98:10.02
1.00=0.01
0.98=0.02
PIX10
0.99-0.02
0.98-1.03
0.99+0002
0.98-+0.11
0.97+00.06
0.97++0.04
0.97+00.4
1.00+0.00
0.97
WarPPIE10P
0.96=20.44
0.96=0.03
0.95++0.03
0.98-10.04
0.96:10.05
0,98:10.03
0.97=10.05
0.99=0002
0.98:10.04
GLIOMA
0.68=0.10
0.66=0.12
0.72
0.63+-0.12
0.67:+0.13
0.67++011
0.68=00.10
0.81-+0.99
0.72+00.14
LUNG
0.86=0.05
0.87=0.05
0.87+:0.44
0.871:0.05
0.92:10.04
0.93:10.05
0,91
0.94:0.03
0.90=0.055
PROSTATE
0.88=0005
081=0007
0.81+0006
0.81+0007
0. 0.88:10.07
0.90=10.07
0.90=
0.89=0.05
0.89=0.06
SRBCT
0.99=0.02
0.94=0.05
0.9810.03
0.951:0.55
0.98110.44
1.00110.00
1.00
0.98-10.3
0.99=0.02
SMK
0.67=0.06
0.66=0.07
0.65+00.7
0.66:-0.08
0.72+10.10
0.72#0.11
0,73=00.09
0.75=0.06
0.68=0.110
Table S2: Clustering results with standard deviations.
Dataset
CAE
DUFS
WAST
AEFS
LS
RSR
UDFS
Our
AllFeaa
Madelon
0.60=0.01
0.52=0.01
0.52+00.1
0.55:10.0
0.5211001
0.61:10.02
0.57:10.05
0.60:0.01
0.58:10.04
PCMAC
0.52-0.01
0.51=0.01
0.51++0.01
0.51++0.01
0.52+00.11
0.51+0.01
0.51+00.1
0.53+0..2
0.51+0.01
COIL-20
0.69-0.03
0.59=0.04
0.65++0.03
0.60+-0.04
0.53++0.04
0.59-10.03
0.60-10.04
0.66-10.33
0.63-+0.05
Yale
0.55=0.06
0.55=0.07
0.56::0.06
0.541:0.06
0.58:10.06
0.60:10.08
0.58::0.05
0.62:40.44
0.61
Jaffe
0.85=0.07
0.80=0.06
0.83100.55
0.80:10.07
0.76110.99
0.8310.08
0.83::0.09
0.87=0.06
0.82+0.06
PIX1O
0.86=0.05
0.79=0.04
0.85::0.06
0.79:10.04
0.85:10.10
0.72:10.08
0.81::0.09
0.87=10.07
0.78
WarpPIE
0.55=0.05
0.42=0.03
0.441:0.4
0,5340006
0.551:0.55
0.57-10.6
0.49:10.08
0.51
0.45
GLIOMA
0.69=0.07
0.65=0.11
0.65+0.100
0.62++0.10
0.63--0.13
0.65:10.16
0.68:10.11
0.75:10.88
0.62=#0.08
LUNG
0.64=0.07
0.64=0.11
0.62+0.100
0.661-00066
0.65++0.11
0.69
0.61++0.05
0.72++0.12
0.69
PROSTATE
0.64=0.11
0.59-0.05
0.58+0.05
0.594-0.05
0.71+10.13
0.63+10.10
0.69-10.11
0.68-00.9
0.64+0.10
SRBCT
0.76=0.09
0.54=0005
0.56++0.88
0.57-10008
0.56:10.00
0.60:10.11
0.59:10.11
0.63=10.10
0.52=0.06
SMK
0.60=0.06
0.58=0.05
0.58100006
0.58:10.05
0.59:10.05
0.59+10.05
0.61-10.07
0.64
0.60=0.07
Table S3: Reconstruction results with standard deviations.
Dataset
CAE
DUFS
WAST
AEFS
LS
RSR
UDFS
Our
AllFea
Madelon
0.99=0.01
0.99=0.00
0.98:10.00
0.981:0.00
0.99:10.00
0.98:10.00
0.98:10.00
0.98+0.00
0.28:10.00
PCMAC
1.14=0.17
1.03=0.06
1.05::0.06
1.05+10.07
1.04:10.06
1.17=0.119
1.07:0.12
1.30:0.22
0.78=10.03
COIL-20
0.48-0.03
0.41=0.02
0.4310001
0.4110001
0.48:10.02
0.45:10.02
0.41:0.02
0.38+0.02
0,2740.01
Yale
0.63=00.33
0.56=0.02
0.56+10.02
0.56++0.02
0.78-10.04
0.57-10.03
0.60-10.33
0.54-0.02
0.50=10.01
Jaffe
0.31=0005
0.25=0.05
0.26++0.05
0.25:10.00
0.33-+0.08
0.26::0.05
0.25:10.05
0.22:0.01
0.23
PIX1O
0.49=0.03
0.3-0004
0.46+00.05
0.434-0.02
0.63-10.05
0.46-10.04
0.47-+0.05
0.39-4.03
1.20-+0.23
WarpPIE1OP
0.30=0.03
0.26=0.02
0.27:10.02
0.26:t:.02
0.45:10.06
0.27+10.33
0.26:10.02
0.25:1001
0.25
GLIOMA
0.74=0.05
0.71=0.04
0.71+:0.04
0.72-10.05
0.71110.4
0.72+10.04
0.72-10.04
0.69:0.04
1.8620.59
LUNG
0.94=0.06
0.77=0002
0.77+:0.02
0.78:10.02
0.82-10.04
0.81:10.02
0.79=:0.02
0.80=1003
0.82:0.28
PROSTATE
1.00=0.14
0.78=0.08
0.7710008
0.77110.09
0.72100.10
0.74:10.10
0.71
0.73-0.13
1.4810.26
SRBCT
0.84=0.03
0.77-0002
0.77+-0.02
0.78-H-002
0 0.80--0:02
0.79-10.02
0,78=00.22
0.75++0.02
0.83-40.03
SMK
0.98=0.07
0.68=0.02
0.68++0.03
0.68.10.02
0.78:10.04
0.78-10.04
0.73++0.03
0.69-10.03
4.32-40.55
20

---

S6.3
Reconstruction Results on PIX10
Fig. Si presents the reconstruction results on PIXIO achieved by our method. We can see that our method is able to reconstruct the original images of 10000 dimensions reasonably well with only 300 features. Notably, the reconstructions capture important appearance details, including reflections. hair tips, and facial features, demonstrating the effectiveness of our method.
Groundtruth Images
Reconstructed Images
Figure S1: Reconstruction results on PIXI0 with 300 features, where the training data are indicated in blue and testing data are indicated in light orange.
S6.4 Graph Visualization
We visualize COIL-20 and Jaffe with t-SNE, and plot the graph structures obtained by different methods. The results are shown in Fig. S2 where red lines represent the intra-class connections and blue lines represent inter-class connections. Unlike "Heat" and "DGL only" that use the original features for visualization, we visualize data points using only selected features. Remarkably, our method successfully achieves separable structures using t-SNE, demonstrating its ability to capture features that reflect the intrinsic data structure.
(a) Heat
(b) DGL only
(c) Our
Figure S2: Visualization with t-SNE, where the first row and the second row correspond to COIL-20 and Jaffe, respectively. Different classes are indicated with different colors. Intra-class connections are indicated in red and inter-class connections are indicated blue. For each sample, we only present the connections to the 5 nearest neighbors.
S6.5 Extended Results for Ablation Study
Table S4 and Table S5 present the clustering result and the reconstruction result of the ablation study
on DGL in Section 44
Table $4: Clustering results without DGL.
Method
Madelon
PCMAC
Juffe
GLIOMA
PROSTATE
w/o DGL
0.5210.01 0.60-10.01
0.5110001 0.53-10.02
0.81110.06
0.78-10.06
0.65+10.8
0.57=0.05
Our
0,87-10.06
0.87-10.07
0.75-10.08
0.68-0.09
Table S5: Reconstruction results without DGL.
Method
Madelon
PCMAC
Jaffe
PIXI0
GLIOMA
PROSTATE
w/o DGL.
0.99:10.00
1.07-10.10
0.26:10.05
0.45:10.02
0.74:10.03
0.79-0.08
0.98:10.00
1.30::.22
0.22-10.01
0.39-10.03
0.69:10.04
0.73=0.13
21

---

S6.6 Additional Experiment: Parameter Sensitivity Analysis
In this section, we analyze the effect of the parameters of our method, including the learning rate, the number of nearest neighbors k. the hyperparameter in the entropy regularized OT problem 14 and the selected feature number m. We use four real-world datasets, including a text dataset PCMAC, an artificial dataset Madelon, an image dataset Jaffe, and a biological dataset PROSTATE.
The analysis is based on the optimal parameter obtained in Section 4.3 For each dataset, fix the values of the remaining parameters and vary the value of one parameter at a time. We retrain our method using the updated parameter combination and evaluate the corresponding FS result with the random forest. This allows us to observe the impact of different parameters on the performance of our method. For example, analyze the effect of the learning rate on Madelon, we keep k. 7, and m at their optimal values, then we vary the learning rate in { {10-* 1003 10 2, 100 ,,001,00" 1000, 10 } (the range as we described in Appendix S6.11.) and evaluate their corresponding performance in the classification task with the random forest. The overall results are shown in Fig. S3 where the stars represent the results using optimal parameters.
One the one hand, we observe that the variations in the learning rate, k; y have little impact on the performance of our method across different datasets. This suggests that proper range for these parameters, without the need to determine their values on different datasets. On the other hand, the most sensitive parameter is m, where a higher number of features contributes to better results, aligning with intuition and observations from existing literature. However, it is important to emphasize that more features are not always better. As demonstrated in Section 4.3 the FS methods consistently outperform AllFea in most classification and clustering tasks. Fewer features not only result in lower computational costs but also contribute to faster learning speeds. This suggests the need to adjust the value of m, for example, starting with a relatively small value and gradually increasing it until the model performance begins to decline.
set value within
100
100
102
80
60
10.2
10
122
10
10
16
Raining 100
(a) Madelon
100
100
100
100
MCC 84
MDC (4)
MCC
60
10
1012
10
187
101
10-1
16-1
100
150
200
360
(b) PCMAC
100
100
1006
160
ACC180)
ACC/198
80
60
80
90
10-
(c) Jaffe
100
100
MCC 168
AGC T5
00
40
ACS
(d) PROSTATE
Figure S3: Parameter sensitivity analysis using the random forest, where the starred point denotes the performance on the optimal parameter combination.
22


Reviews:
[{"review_id": "ntUQ2Who06", "reviewer": "Reviewer_EQBi", "summary": "In this paper, the authors propose an unsupervised feature selection method using Dirichlet energy. The proposed method learns the KNN graph and the feature selection jointly to reduce the influence on the feature selection quality by the noisy and irrelevant features. \n\nThe feature selection component minimizes the Dirichlet energy with Gumbel Softmax smoothed one-hot feature selection matrix. To ensure each resulting feature dimension is unique, the column orthogonality is enforced by linear decompositions.\n\nThe graph learning component also minimizes the Dirichlet energy. To avoid a trivial solution (graph with only self-connecting edges), Tikhonov regularization is applied to ensure the probabilistic behavior of similarity metrics and no self-loops.\n\nEmpirical results on both synthetic datasets and real-world applications show that the proposed method can effectively select useful features and has better performance than other baseline methods.", "questions": "* How can the method be generalized to handle noncontinuous categorical features?\n\n* Is a constant feature a trivial minimizer for the Dirichlet energy? How does the proposed method handle this?", "limitations": "See the weaknesses above.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* The paper is clearly motivated and well-structured. The derivations are clear and in detail. Overall the paper presentation is good.\n\n* The proposed method is interesting and novel, and the effectiveness of the proposed method is supported by both synthetic and real-world datasets.\n\n* The authors also discussed the limitations of the method and lies out the future directions to improve.", "weaknesses": "* As the authors mentioned in the discussion section, the method does not scale to large-scale problems.\n\n* The method is under the assumption that the features are continuous and of low dimension, whereas many real-world problems may face noncontinuous (e.x. categorical) or high dimensional (e.x. sparse BOW) features.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the positive comments.  We provide our response below.\n\n### Response to points in Questions\n\n**Q1: \"How can the method be generalized to handle noncontinuous categorical features?\"**\n\n**A1:** Thanks. Recall that Dirichlet Energy is inherently reliant on the manifold distribution of continuous features. Contrastingly, discrete data does not manifest a discernible distribution characteristic. The most straightforward example is within categorical features, where the distance between type 1 and type 3 is not inherently larger than that between type 1 and type 2. Therefore, we cannot directly apply continuous measurements for categorical features. \n\nIn order to incorporate discrete data into Dirichlet Energy calculations, we can first map the discrete data onto a continuous vector space, and then measure the distances between different vectors within this space. Specifically, suppose we have a feature set $\\\\mathbb{x}=\\\\mathbb{x}\\_{con}\\\\cup\\\\mathbb{x}\\_{cate}$ composed of continuous features $\\\\mathbb{x}\\_{con}$ and categorical features $\\\\mathbb{x}\\_{cate}$. For the categorical feature $\\\\hat{\\\\boldsymbol x}\\_p$, the Dirichlet Energy in Eq. (1) can be extended into the following form:\n$$\n\\\\mathcal{L}\\_{dir}(\\\\hat{\\\\boldsymbol x}\\_p) = \\\\frac{1}{2}\\\\sum\\_{i=1}^n\\\\sum\\_{j=1}^ns\\_{i,j}\\\\|\\\\mathfrak{f}(\\\\hat{x}\\_{i,p})-\\\\mathfrak{f}(\\\\hat{x}\\_{j,p})\\\\|\\_2^2\n$$\nwhere $\\\\mathfrak{f}$ is a nonlinear map function. For example, we can first convert the categorical feature $\\\\hat{x}\\_{i,p}$ into a one-hot vector, and then further map the one-hot vector into a continuous $h$-dim vector $\\\\boldsymbol z\\_{(i,p)}$ with a MLP, namely, $\\\\boldsymbol z\\_{(i,p)} = \\\\mathfrak{f}(\\\\hat{x}\\_{i,p})$. Consequently, the distance between $\\\\hat{x}\\_{i,p}$ and $\\\\hat{x}\\_{i,q}$ can be measured by the $\\\\ell\\_{2}$-norm distance between $\\\\boldsymbol z\\_{(i,p)}$ and $\\\\boldsymbol z\\_{(j,p)}$. Accordingly, the calculation of the distance matrix in line 163 in our paper is changed into \n$$\ne\\_{i,j}=\\\\sum\\_{\\\\hat{\\\\boldsymbol x}\\_p\\\\in \\\\mathbb{x}\\_{cate}}\\\\|\\\\mathfrak{f}(\\\\hat{x}\\_{i,p})-\\\\mathfrak{f}(\\\\hat{x}\\_{j,p})\\\\|\\_2^2+\\\\sum\\_{\\\\hat{\\\\boldsymbol x}\\_q\\\\in \\\\mathbb{x}\\_{con}}(\\\\hat{x}\\_{i,q}-\\\\hat{x}\\_{j,q})^2.\n$$\n\n**Q2: \"Is a constant feature a trivial minimizer for the Dirichlet energy? How does the proposed method handle this?\"**\n\n**A2:** Yes, according to Eq. (1) in our paper, the constant feature is a trivial solution to the Dirichlet Energy. However, as stated in the first paragraph in Section 2 (line 69), we assume that all features have zero means and normalized variances, namely, $\\\\boldsymbol 1\\_n^\\\\top\\\\boldsymbol x\\_p=0$ and $\\\\boldsymbol x\\_p^\\\\top\\\\boldsymbol x\\_p=1$. This practice is not unusual and is frequently employed during feature preprocessing in various Feature Selection studies, e.g., see [1], [2], and [3].  Under this assumption, constant features, which cannot satisfy this condition, will be dismissed at the preprocessing stage. We will clarify this in the revised version.\n\n**Ref:**\n\n[1] Lindenbaum, O., et al. (2021). Differentiable unsupervised feature selection based on a gated laplacian. in Proc. NIPS, 34, 1530-1542.\n\n[2] Sokar, G., et al. (2022). Where to pay attention in sparse training for feature selection?. in Proc. NIPS, 35, 1627-1642.\n\n[3] Nie, F., et al. (2010). Efficient and robust feature selection via joint ℓ2, 1-norms minimization. in Proc. NIPS, 23.\n\n"}, {"review_id": "iOIVY5gXBk", "reviewer": "Reviewer_f5Nx", "summary": "This article proposes an unsupervised feature selection method by minimizing the Dirichlet energy, and the energy function is on the other hand based on the k-NN graph computed from the selected features. In this sense, the features and the k-NN graph are jointly learned. To avoid discrete operations, the author(s) use Gumbel softmax to approximate the selection operation, and use OT-based sorting to construct k-NN graph. The proposed method is validated using a series of numerical experiments.", "questions": "1. I think both the title of Section 3.1.1 and the statement \"having selected *exact* original features\" in Section 3.1.2 need to be modified, as the Gumbel softmax technique is an approximation to the discrete optimization problem, not necessarily an exact one.\n2. The author(s) may consider a direct convex relaxation of the constraints in (2), which at least jointly handles the two different constraints.\n3. Some comments on the points in the weaknesses section would be helpful.", "limitations": "The author(s) have remarked that the proposed method may be difficult to scale up.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Overall the proposed method is an interesting joint feature selection and graph learning method, and the whole procedure is differentiable, thus useful for downstream analyses.", "weaknesses": "1. One major weakness of the proposed algorithm is its large computational cost, which the author(s) have mentioned in the article. The bottleneck seems to be in the sorting part. In fact, there are different variants of differentiable sorting, and it has been shown in some reports that OT-based sorting can be slow [1]. The author(s) may try other differentiable sorting algorithms such as [1], which has $O(n\\log n)$ forward complexity and $O(n)$ backward complexity.\n2. There exist several inconsistencies between the proposed method and the actual implementation, such as the symmetrized k-NN graph (page 2) and the actual computation of the $F$ matrix in page 5. Although the author(s) have explained their motivation, it downgrades the rigor of the method. Also Proposition 3.1 looks irrelevant if the actual $F$ is not computed in this way.\n3. Following point 2, I think a deeper reason for such inconsistencies is that the optimization problem (2) is difficult by nature, and Section 3.1.1 and Section 3.1.2 are tackling the constraints in (2) separately, not jointly. For example, Section 3.1.1 attempts to make $F$ approximately discrete, and Section 3.1.2 is concerned with $F^{T}F=I$. It is very likely that they are not met simultaneously using the current algorithm.\n\n[1] Blondel, M., Teboul, O., Berthet, Q., & Djolonga, J. (2020). Fast differentiable sorting and ranking. In International Conference on Machine Learning (pp. 950-959). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and positive comments. Below we provide our response:\n\n### Response to the points in Weaknesses\n\n**P1: Suggestion about a more computationally efficient  method for differentiable sorting in Weakness 1**\n\n**A1:** Thank you for this constructive comment. Reference [1] proposed to construct differentiable sorting operators as projections onto the permutahedron, and the $\\\\mathcal{O}(n \\\\log n)$ time and $\\\\mathcal{O}(n)$ space complexity was achieved with isotonic optimization. We will try this method in our future work. However, recall that there are $n$ sorting tasks in our network since we have $n$ samples, a space complexity of at least $\\\\mathcal{O}(n^2)$ would be required to store intermediate variables. While graph neural networks mitigate memory overhead by subgraph sampling [2], the neighbours of each sample in our method are determined on global information, which requires full information being loaded at each iteration. Hence, we have mentioned batch learning as a future research direction in our Discussion section for its potential to enhance scalability.\n\n**Ref:**\n\n[1] Blondel, M., et al. (2020). Fast differentiable sorting and ranking. in Proc. ICML (pp. 950-959).\n\n[2] Hamilton, W., et al. (2017). Inductive representation learning on large graphs. in Proc. NIPS, 30.\n\n**P2: Concern about the symmetrized k-NN graph in Weakness 2**\n\n**A2:** Thank you. The use of $\\\\hat{S} = (S+S^\\\\top)/2$ is indeed a common practice in Spectral graph methods, kindly see [1, Sec. 2.2] and [2, Sec. 2.1] for example. The underlying rationale is that the $k$-NN graph we learned is a directed graph, whereas the computation of the Laplacian matrix is based on the undirected graph. To make the graph undirected, a common approach is to ignore the directions of the edges. That is, we connect $x^i$ and $x^j$ if $x^i$ is among the $k$-NN of $x^j$ or $x^j$ is among the $k$-NN of $x^i$. After symmetrization, the Dirichlet Energy will select features based on the symmetrized undirected graph $\\\\hat{S}$, instead of the original graph $S$. We will clarify this in the revised version.\n\n**Ref:**\n\n[1] Von Luxburg, U. (2007). A tutorial on spectral clustering. Stat. Comput., 17, 395-416.\n\n[2] He, X., et al. (2005). Laplacian score for feature selection. in Proc. NIPS, 18.\n\n**P3: Concern about the actual computation of F and the Proposition 3.1  in Weakness 2**\n\n**A3:** Thank you, we agree that the actual computation of $F$ downgrades the rigor of the method, but we respectfully disagree that Proposition 3.1 is irrelevant to the actual computation. The significance of Proposition 3.1 is twofold.\n\nFirstly, since Cholesky decomposition is conditional, Eq. (S1) in Proposition 3.1 confirms that we are able to obtain a lower triangle matrix $L$ for any real matrix $\\\\hat{F}$, as $\\\\epsilon>0$ guarantees the positive-definiteness of $F^\\\\top F+\\\\epsilon{I}_m$. \n\nSecondly, Proposition 3.1 validates the efficacy of both Algorithm 1 and the actual computation in solving the orthogonal constraint. Actually, $F = \\\\hat{F}(L^{-1})^\\\\top$ is an approximation of Algorithm 1 since we have \n\n$${F}^\\\\top{F} =L^{-1}\\\\hat{F}^\\\\top\\\\hat{F}(L^{-1})^\\\\top=L^{-1}(A-\\\\epsilon{I}_m)(L^{-1})^\\\\top=L^{-1}A(L^{-1})^\\\\top-\\\\epsilon L^{-1}(L^{-1})^\\\\top=L^{-1}LL^\\\\top(L^{-1})^\\\\top-\\\\epsilon L^{-1}(L^{-1})^\\\\top=I_m-\\\\epsilon L^{-1}(L^{-1})^\\\\top,$$\n\nwhich can be viewed as an $\\\\epsilon$-approximation to orthogonality. While it cannot strictly attain orthogonality, the toy experiment nonetheless indicates that this design is effective for unique feature selection.\n\n### Response to the points in Questions\n\n**Q1: \"... both the title of Section 3.1.1 and the statement \"having selected *exact* original features\" in Section 3.1.2 need to be modified,...\"**\n\n**A1:** Thank you for the comment. We will modify the title and the statement in the revised version.\n\n**Q2: \"The author(s) may consider a direct convex relaxation of the constraints in (2), ...\"**\n\n**A2:** Thank you for this valuable comment. Inspired by reference [1], below we provide a relaxed version of the constraint in problem (2) in our paper. Instead of learning the selection matrix $F$, we learn a discrete vector $\\mathbf v$ containing only $k$ non-zero components: \n$$\n\\\\min_{{\\mathbf v}} \\\\mathrm{tr}(\\\\hat{{X}}^\\\\top{L}\\\\hat{{X}})\\\\quad\\\\mathrm{s.t.}\\\\  \\\\hat{{X}} = {X}\\\\mathrm diag({\\mathbf v}), {1}_d^\\\\top{\\mathbf v}=k,{\\mathbf v}\\\\in\\\\{0,1\\\\}^d\n$$\nBased on this, we can relax the discrete constraint to be the intersection of a solid cube and a shifted $\\\\ell_2$-sphere:\n$$\n{\\mathbf v}\\\\in\\\\{0,1\\\\}^d\\\\Leftrightarrow\\\\{{\\mathbf v}|{\\mathbf v}\\\\in[0,1]^d\\\\}\\\\cap\\\\{{\\mathbf v}|\\\\|{\\mathbf v}-({1}_d/2)\\\\|^2_2=d/4\\\\},\n$$\nas illustrated in Fig. 1 of the attached pdf file. While [1] suggests the relaxed problem is readily solved using the ADMM method, it's crucial to highlight their optimization is for traditional ML models. To implement the alternating optimization process into a neural network, we can design modules similar to ADMM-net [2], where each module represents an optimization step and is iteratively repeated, kindly see [2] [3] for example.\n\n**Ref:**\n\n[1] Zhang, X., et al. (2020). Top-k feature selection framework using robust 0–1 integer programming. IEEE Trans. Neural Netw. Learn. Syst., 32(7), 3005-3019.\n\n[2] Sun, J., et al. (2016). Deep ADMM-Net for compressive sensing MRI. in Proc. NIPS, 29.\n\n[3] Lin, Z., wt al. (2011). Linearized alternating direction method with adaptive penalty for low-rank representation. in Proc. NIPS, 24.\n\n### Extra words\nWe are grateful for these insightful comments. Despite limited space leading to a dense presentation, as noted by reviewer MNAm, we have endeavored to clearly detail our approach. We believe that this transparency can spur the evolution of improved solutions, just like P1 and Q2. Such insights are invaluable,  as they significantly contribute to the continuous refinement of our work."}, {"review_id": "SO7esSLcLn", "reviewer": "Reviewer_JXCq", "summary": "This paper proposes a deep FS method that simultaneously conducts feature selection and differentiable k-NN graph learning based on the Dirichlet Energy. The Dirichlet Energy identifies important features by measuring their smoothness on the graph structure, and facilitates the learning of a new graph that reflects the inherent structure in the new feature subspace during the training process using selected features. The authors employ the Gumbel Softmax technique and the Optimal Transport theory to address the non-differentiability issues of learning discrete FS results and learning k-NN graphs in neural networks, which theoretically makes our model applicable to other graph neural networks. Furthermore, the proposed framework is interpretable, since all modules are designed algorithmically. \n\n\n\n\n\n", "questions": "1. The biggest problem of this paper is the limited novelty in formulation of the proposed method, which is mainly obtained by combination of the existing works, i.e., dirichlet energy or the differentiable learner. The authors should better highlight their novelty in Section 3 of this paper, which make it significantly different from the existing works.\n\n2. The compared methods in the experiment are not enough for comparison and the authors can add one or more methods for comparison to validate the effectiveness of the proposed method.\n\n3. The adopted datasets in the experiment are almost with small scales. The largest number of the adopted datasets is 2600, i.e., madelon. The authors can add one or more datasets with large scales for comparison in the experiment.\n\n4. The experimental improvements of the proposed method compared with the existing methods are not obvious, i.e, the proposed method on SRBCT is 0.98 while UDFS is 1.00.\n\n5. The authors can further explain the interpretability of the proposed method in the corresponding section , which is also an advantage of the given network.", "limitations": "1. The biggest problem of this paper is the limited novelty in formulation of the proposed method, which is mainly obtained by combination of the existing works, i.e., dirichlet energy or the differentiable learner. The authors should better highlight their novelty in Section 3 of this paper, which make it significantly different from the existing works.\n\n2. The compared methods in the experiment are not enough for comparison and the authors can add one or more methods for comparison to validate the effectiveness of the proposed method.\n\n3. The adopted datasets in the experiment are almost with small scales. The largest number of the adopted datasets is 2600, i.e., madelon. The authors can add one or more datasets with large scales for comparison in the experiment.\n\n4. The experimental improvements of the proposed method compared with the existing methods are not obvious, i.e, the proposed method on SRBCT is 0.98 while UDFS is 1.00.\n\n5. The authors can further explain the interpretability of the proposed method in the corresponding section , which is also an advantage of the given network.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The originality of this paper is satisfying, which proposes a deep FS method that simultaneously conducts feature selection and differentiable k-NN graph learning based on the Dirichlet Energy and the significance is mainly built on this.\n\nThe quality and clarity of this paper is good based on the clear presentation of the proposed method shown in Figure 2.", "weaknesses": "1. The biggest problem of this paper is the limited novelty in formulation of the proposed method, which is mainly obtained by combination of the existing works, i.e., dirichlet energy or the differentiable learner. The authors should better highlight their novelty in Section 3 of this paper, which make it significantly different from the existing works.\n\n2. The compared methods in the experiment are not enough for comparison and the authors can add one or more methods for comparison to validate the effectiveness of the proposed method.\n\n3. The adopted datasets in the experiment are almost with small scales. The largest number of the adopted datasets is 2600, i.e., madelon. The authors can add one or more datasets with large scales for comparison in the experiment.\n\n4. The experimental improvements of the proposed method compared with the existing methods are not obvious, i.e, the proposed method on SRBCT is 0.98 while UDFS is 1.00.\n\n5. The authors can further explain the interpretability of the proposed method in the corresponding section , which is also an advantage of the given network.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for the feedback and suggestions.  Below we answer all questions and provide some additional experimental results.\n\n\n\n**Q1: Concern about the limited novelty of the proposed method**\n\n**A1:**  \n\nThank you for the suggestion about highlighting the novelty in Section 3. However, we respectfully disagree that our method has limited novelty. Our novelty lies in at least three aspects.\n  - Firstly, the proposed method is a model-driven framework, the design of which are motivated naturally by the issue of noisy and irrelevant data. It is noteworthy that each module in our framework is related to a specific algorithm design, kindly refer to our response to Q5.\n  - Secondly, the proposed UFS module is novel. Note that Equation (4) forms the core idea of CAE [1], a notable baseline advocating the use of Gumbel-softmax for feature selection (FS). However, CAE was criticized for duplicate selection [2, Sec. 2.2], as far as we know, few studies have addressed this issue. While UFS can proposes an improvement to CAE, with its efficacy demonstrated in our toy experiment.\n  - Thirdly, the proposed differentiable $k$-NN graph learning is novel. While OT techniques have been used for sorting before, to our knowledge, they have not been used for $k$-NN graph learning. In fact, there are few studies on the differentiable $k$-NN graph, and this point is supported by literature [3]. In order to obtain a differentiable graph, the authors in [3] simply relax the hard connection $w_{u,v}\\\\in\\\\{0,1\\\\}$ between node $u$ and node $v$ into a soft connection $w_{u,v}\\\\in(0,1)$, which potentially create a dense graph. In contrast, our method can generate a sparser graph structure, which provides a new paradigm for differentiable graph learning.\n\nWe're gratified by reviewers EQBi and MNAm acknowledging the novelty of our approach, while also recognizing MNAm's critique regarding the density of our writing. This may have obscured full comprehension of our contributions. We will add more explainations to make our method more accessible in the revised version.\n\n**Ref:**\n\n[1] Balın, M. F., et al. (2019, May). Concrete autoencoders: Differentiable feature selection and reconstruction. in Proc. ICML (pp. 444-453).\n\n[2] Atashgahi, Z., et al. (2022). Quick and robust feature selection: the strength of energy-efficient sparse training for autoencoders. Machine Learning, 1-38.\n\n[3] Miao, S., et al. (2022). Interpretable geometric deep learning via learnable randomness injection. in Proc. ICLR, 2023.\n\n\n\n**Q2: Concern about the compared methods**\n\n**A2:** Thank you for the comment. We have added the results of two popular FS methods (FIRDL [1] and STG [2]) on twelve datasets. The complete result is provided in Table 1 of the attached PDF file, below we provide some statistical results to show the superior performance of our method:\n\n| Task           | Methods      | STG  | FIRDL | Our     |\n| -------------- | ------------ | ---- | ----- | ------- |\n| Classification | Average rank | 2.1  | 2.3   | **1.1** |\n|                | Top-1 counts | 2    | 1     | **11**  |\n| Clustering     | Average rank | 2.3  | 2.3   | **1.1** |\n|                | Top-1 counts | 2    | 1     | **11**  |\n| Reconstruction | Average rank | 1.7  | 1.8   | **1.8** |\n|                | Top-1 counts | 5    | 5     | **7**   |\n\n**Ref:**\n\n[1] Wojtas, M., et al. (2020). Feature importance ranking for deep learning. in Proc. NIPS, 33, 5105-5114.\n\n[2] Yamada, Y., et al. (2020, November). Feature selection using stochastic gates. in Proc. ICML (pp. 10648-10659).\n\n**Q3: Concern about the datasets**\n\n**A3:** Thanks. As we mentioned in Discussion in our paper, the major limitation of our method is the lack of scalability, for which we did not adopt large datasets. We will work on this issue in our future study.\n\n**Q4: Concern about the experimental improvements of the proposed method**\n\n**A4:** Thank you. Given that Feature Selection (FS) outputs are typically used for various downstream tasks, and the specific task is often unknown in practical applications, the goal of FS is usually to select features that perform well across multiple tasks, which is named the 'unsupervised nature' of FS by existing literature [1].  Given this, we believe that evaluating the overall performance across various tasks and datasets provides a more comprehensive demonstration of a method's efficacy. Hence, our approach exhibits superior performance relative to existing methods (evident from the Average Ranking and # Top 1 in Table 2). \n\n**Ref:**\n\n[1] Balın, M. F., et al. (2019, May). Concrete autoencoders: Differentiable feature selection and reconstruction. in Proc. ICML (pp. 444-453).\n\n**Q5: Concern about the interpretability of the proposed method**\n\n**A5:** Thank you. Our work is rooted in model-driven neural networks, related work can be seen in [1] [2]. Interpretability here signifies comprehending the function of each module during learning.  Unlike most deep learning networks with complex components that are that are tough to decipher, each core module in our framework has an algorithmic, physically meaningful design, which greatly facilitates observing and understanding the network's internal operations during the learning process.\n\nSpecifically, UFS, designed from Algorithm 1 and Proposition 3.1, produces an output resembling an orthogonal and discrete matrix (as detailed in our response to Reviewer f5Nx in P3). Moreover, the design of DGL, based on problem (5), assures that the learned graph reflects the intrinsic structure of the selected features. We will add more explanations about interpretability in the revised version.\n\n**Ref:**\n\n[1] Xie, Q., et al. (2020). MHF-Net: An interpretable deep network for multispectral and hyperspectral image fusion. IEEE Trans. Pattern Anal. Mach. Intell., 44(3), 1457-1473.\n\n[2] Wang, H., et al. (2020). A model-driven deep neural network for single image rain removal. in Proc. CVPR (pp. 3103-3112)."}, {"review_id": "IbHzx4ao9u", "reviewer": "Reviewer_MNAm", "summary": "The authors present a method to jointly learn important features as well as a $k$-nearest neighbour graph for data. They extensively motivate and evaluate their method.", "questions": "- In equation 5, if we require $s_{i, i} = 0$, then why is $\\mathbf{S} = I$ a solution?", "limitations": "The authors do a great job describing the limitations of their method.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "- Great method, very novel and sensible.\n\n- Excellent and thorough evaluation.\n\n- Method is well-justified by theoretical explanations.\n\n- Good ablation studies allow disentangling of the different components of the method.\n\n- It is very admirable that the authors include the reconstruction metric in their main results, where their method does not perform as well. I agree with the authors that this is not a good metric for noisy data, but it is great that the authors do not try to hide their performance nonetheless.", "weaknesses": "- Very densely written, the paper should be more accessible than this. If the authors are able to improve the clarity of the writing, the impact of this work will greatly increase.\n\n- To the point above, I would recommend a few sentences about the intuition behind the method.\n\n**Overall**: Excellent work, some intuitive explanations about the method would greatly improve the reader's understanding of how the method works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer's positive comments on our work. We provide our response below:\n\n### Response to the point in Weaknesses\n\n**P1: \"I would recommend a few sentences about the intuition behind the method.\"**\n\n**A1:** Thank you. The main focus of our work is to select features in neural networks using the Dirichlet Energy. The motivation behind our method is that noisy and irrelevant data will deteriorate the quality of the graph structure, therefore degrading the performance of feature selection. To address this issue, we propose a deep FS method that uses the Dirichlet energy to learn features and update the $k$-NN graph structure jointly, which is the first contribution of our work illustrated in the top panel of Fig. 2 in our paper. As we depicted in the constraints in problem (2), the result of feature selection should be discrete and unique, although traditional gumbel-softmax method is capable of approximating the discrete result, the issue of uniqueness is still not addressed. To this end, we propose the second contribution of our paper, namely, the algorithmically designed UFS module, as illustrated in the bottom left panel of Fig. 2. Moreover, we propose to learn the $k$-NN graph by minimizing the Dirichlet Energy. Note that the traditional $k$-NN learning methods cannot be employed in neural networks due to the nondifferentiability nature of sorting operation. To address this issue, we employ the OT technique to learn $k$-NN differently, which is the third contribution of the proposed method illustrated in the bottom right panel of Fig. 2. We have also listed the novelty of the proposed method in our response to Reviewer JXCq in Q1, kindly refer to this response for extra information. The proposed framework is not only a novel FS method, but also provides a new paradigm for differentiable graph learning, which is demanded by existing literature. \n\n### Response to point in Questions\n\n**Q1: \"In equation 5, if we require $s_{i,i}=0$, then why is $S=I$ a solution?\"**\n\n**A1:** Thanks.  The trivial solution $S=I$ applies to $\\\\min_S tr(F^\\\\top LF)$. When the problem changed into\n$$\n\\\\min_S tr(F^\\\\top LF)\\\\ s.t. S1_n=1_n,s_{i,j}\\\\ge0,s_{i,i}=0,\n$$\nthis problem is equivalent to solving each row independently as \n$$\n\\\\min_{s_{i,j}} \\\\frac{1}{2} \\\\sum_{j=1}^ne_{i,j}s_{i,j}\\\\ s.t. \\\\sum_{j=1}^ns_{i,j}=1,s_{i,j}\\\\ge0,s_{i,i}=0,\n$$\nwhich can be derived from Eq. (S4) and Eq. (S5) in Appendix S3. It is easy to obtain that only the nearest data point can serve as the neighbour of $\\\\boldsymbol x^i$ with probability $1$, while all the other data points will not be the neighbours of $\\\\boldsymbol x^i$, which is also not desirable in $k$-NN graph learning.\n"}]

Author rebuttal:
We thank all the reviewers for the positive reviews and constructive comments that help us to emphasize the contributions of our approach. We are encouraged to hear that the reviewers found the approach  **interesting** (Reviewers EQBi, f5Nx), **novel** (Reviewers EQBi, MNAm), and **well-motivated** (Reviewers EQBi, MNAm). We appreciate that the reviewers acknowledge that the paper is **well-presented** (Reviewers EQBi, JXCq). In response to the thoughtful comments, we have addressed them one by one in the individual responses. 

In particular, we have highlighted our contribution in our response to Reviewer JXCq in Q1 and also described the intuition of the proposed method in the response to Reviewer MNAm in P1, please see these responses for detailed information. 

**Below we have uploaded a pdf file that includes the illustration of the relaxed constraint in our response to Reviewer f5Nx in Q2, as well as the detailed experimental results in our response to Reviewer JXCq in Q2.**

Thanks again for all of your valuable suggestions, we appreciate the reviewers' time to check our response.

Meta-review: There was some disagreement between reviewers on this submission, which led me to review it in depth myself, and while I agree that it has some limitations, I still think that it should be accepted **on the condition** that it addresses more clearly its limitations, mainly

- Issues with scale, and why a batch approach is not considered, and how it could be

- More in-depth literature review of differentiable discrete operators, as mentioned by the reviewers, including

[1] Blondel, M., Teboul, O., Berthet, Q., & Djolonga, J. (2020). Fast differentiable sorting and ranking.

[2] Q Berthet, M Blondel, O Teboul, M Cuturi, JP Vert, F Bach (2020) Learning with differentiable perturbed optimizers

[3] M Vlastelica, A Paulus, V Musil, G Martius, M Rolinek (2020) Differentiation of blackbox combinatorial solvers  

[4] M Paulus, D Choi, D Tarlow, A Krause, CJ Maddison (2020) Gradient estimation with stochastic softmax tricks
Decision: Accept (poster)