Efficient Multi-view Unsupervised Feature Selection with Adaptive Structure Learning and Inference

1 Introduction

As information technology develops rapidly, data collected from heterogeneous sources often contains multiple representations [Hu et al., 2019; Zhong and Pun, 2020; Liang et al., 2022b; Liang et al., 2022a; Zhao et al., 2023; Peng et al., 2023]. To process this kind of data, multi-view learning has been proposed in recent years [Hu et al., 2021; Liu et al., 2022; Yang et al., 2024; Xu et al., 2024; Liang et al., 2024]. As a special case, multi-view feature selection that aims to select representative features from the original feature space has become a fundamental task. Depending on the availability of data class labels, current methods can be realized in supervised, semi-supervised, and unsupervised ways [Bai et al., 2021; Jiang et al., 2022; Zhang et al., 2023b; Li et al., 2024b; Zhao et al., 2024]. Considering the expensive cost of manually labeling data, several researchers have devoted to the multi-view unsupervised feature selection, which utilizes the intrinsic data structure to select informative features without the guidance of label information.

To select a feature subset from multi-view data, existing methods can be mainly categorized into two manners. The first kind of method directly concatenates the features from different views and then invokes single-view models on the concatenated features. Typical methods include feature selection with graph learning [Nie et al., 2016; Chen et al., 2023; Tang et al., 2023] and spectral feature selection [Zhao and Liu, 2007; Li and Tang, 2015; Zhou et al., 2023]. Considering that different views have specific properties and contribute variously to final models, this kind of method treats different views equally and neglects the difference between them, causing performance deterioration in practical domains [Tang et al., 2019; Zhong and Pun, 2021]. Instead of simply concatenating different views, another kind of method exploits the underlying correlations among views and introduces weights to balance the contributions of different views. Representative methods include feature selection with adap- Membership matrices tive similarity and view weight (ASVW) [Hou et al., 2017], multilevel projections with adaptive neighbor graph for multiview feature selection (MAMFS) [Zhang et al., 2021], and robust feature selection via multi-group adaptive graph representation (MGAGR) [You et al., 2023]. Commonly, these methods follow two separate steps, i.e., constructing a graph on each view to explore view-specific structures and performing feature selection based on the weighted combination of multiple graphs. To avoid the trivial solution of view weights, an extra weight-related parameter that needs to be manually determined is introduced, weakening their applicability [Li et al., 2022]. Moreover, they suffer from a higher computation due to constructing graphs on all samples. Recently, [Chen et al., 2023] proposed to learn a bipartite graph between samples and anchors to reduce computational costs. However, they focus on learning graphs to characterize similarity structures, yet are incapable of capturing the inherent cluster structure of data that can positively guide feature selection.

To explore the cluster structure information, [Feng et al., 2013] proposed to learn the feature projections and the pseudo cluster labels of data (i.e., the cluster indicator matrix) by a linear regression model. Inheriting from [Feng et al., 2013], many variants have been developed in recent years. For example, [Dong et al., 2018] incorporated graph learning into the framework of [Feng et al., 2013], such that the similarity graph can be updated in the feature selection process. Instead of the orthogonal constraint, [Shi et al., 2023] imposed a binary hash constraint on the cluster indicator matrix to improve the discrimination. Despite achieving some progress, these methods still face the following limitations: i) the similarity graph directly derived from the original features is susceptible to poor-quality features since the original data usually contains irrelative features, impairing the graph reliability and finally affecting the effectiveness of selected features; ii) their focus lies in learning the cluster indicator matrix of all samples, such that the optimization procedure involves the decomposition or inverse operations of high-order matrices, leading to expensive computational complexity.

Motivated by the aforementioned issues, we propose an efficient multi-view unsupervised feature selection with adaptive structure learning and inference (EMUFS). Fig. 1 illustrates the basic framework of EMUFS. The main contributions of this paper are summarized as follows:

• We propose an efficient multi-view unsupervised feature selection method that simultaneously leverages membership matrices and bipartite graphs to capture the cluster information of anchors and the similarity structure between samples and anchors, facilitating the ultimate feature selection and reducing computational costs.
• We design a collaborative fusion manner for membership matrices and graphs to learn the compatible structures, so that the cluster information of samples can be inferred via the similarity between samples and anchors, balancing different views without extra parameters.
• We utilize the neighbor relations of data in the selected feature subspace to adaptive learn a unified bipartite graph, reducing the impact of poor-quality features.

2 Our ProposedMethodology

2.1 Notations

Throughout the paper, vectors are written in bold lowercase letters, and matrices are written in bold uppercase letters. Besides, mi represents the i-th row of a given matrix M, Tr(M)

denotes the trace of M and ‖M‖F = √Tr(MT M) denotes the Frobenius norm. ‖M‖2,1 = ∑i ‖mi‖2 and ‖M‖2,0 = ∑i ‖mi‖02 denote the l2,1-norm and l2,0-norm of M, respectively. Table 1 lists the frequently used notations.

2.2 Similarity Structure Learning and Fusion

Most methods construct n-order graphs to mine the similarity relations among samples, leading to high computational costs [Hu et al., 2022; Li et al., 2024a]. To this end, our proposed EMUFS learns bipartite graphs between samples and anchors to improve the efficiency of graph construction. Specifically, the alternate sampling strategy proposed by [Li et al., 2022] is used to generate a consistent anchor set on different views. Then, the view-specific similarity structures between samples and generated anchors can be captured by solving:

where Sv ∈ Rn×m is the bipartite graph on the v-th view, and svij measures the similarity between sample xi and anchor zj in v-th view. Eq.(1) can be directly solved by the adaptive neighbor strategy [Nie et al., 2014].

To learn a consensus similarity graph, the view-specific graphs can be coalesced in the following fusion manner:

where S denotes a unified graph that compatibly crosses multiple views, and the exponential parameter η controls the distribution of the view weights {φv}Vv=1. To further reveal the underlying relation between S and {Sv}Vv=1, we fix φ and set the derivation of Eq. (2) w.r.t. S to zero:

where αv can be regarded as the weight since αv ≥ 0 and ∑Vv=1 αv = 1. In Eq. (3), the equality relation of S and ∑Vv=1 αvSv can be further relaxed by introducing a flexible regression residue (i.e., S - ∑Vv=1 αvSv) to measure the mismatch between them, achieving a new fusion paradigm as:

Eq. (4) can fuse multiple graphs without the exponential parameter η. Further, considering that the poor-quality features in the original space can undermine graph structures, we propose to dynamically update the graph S according to the relations of samples and anchors in the selected feature subspace:

In contrary to previous methods [Nie et al., 2016; Hou et al., 2017] that applied an l2,1-norm on the feature projection matrix W, the l2,0-norm constraint is imposed on W to automatically select salient features without sorting features in advance. Moreover, the graph learned from the selected features can accurately explore the similarity structure and alleviate the impacts of low-quality features.

2.3 Cluster Information Inference on Graph

A membership matrix that contains the cluster structure of data is widely used since it can be regarded as the latent discriminative information in unsupervised scenarios [Zhang et al., 2023a; Lu et al., 2023]. For convenience, existing models often generate membership matrices on each view independently and coalesce them for further analyses. Nevertheless, the clusters preserved in the membership matrices might be mismatched between different views, which means that different membership matrices are not aligned column-widely [Wang et al., 2022]. As a result, the direct fusion of membership matrices might suffer from inconsistent cluster information across views. To solve this limitation, the membership matrices on different views are first generated by the FCM [Bezdek et al., 1984] to mine the view-specific cluster structures, then different membership matrices can be aligned by solving the following problem:

where the permutation matrix Tv makes U1 and Uv consistent at the level of clusters and can be directly solved by performing the SVD on UT1 Uv . We exploit membership matrices on anchors instead of all samples to explore the latent cluster structure of data, which avoids the decomposition or inverse operations of high-order matrices in the subsequent solution process. To capture the consensus cluster structure of anchors, the same fusion approach as Eq.(4) can be employed to merge the aligned membership matrices:

where ˜Uv (i.e., UvTv) denotes the aligned membership matrix, serving as the label guidance for feature selection. With the learned bipartite graph S, the label guidance (i.e., cluster information) of samples can be directly inferred from anchors, as shown in Fig. 2. Therefore, the final optimization objective of the proposed EMUFS is obtained as:

where F denotes the cluster labels of samples and simultaneously leverages the similarity and cluster information. In Eq. (8), the membership matrix and the bipartite graph are collaboratively fused to facilitate the cluster information inference on the graph. Moreover, the similarity structure is also guided by the relations between samples and anchors in the selected feature subspace, enhancing the graph quality. Consequently, similarity structure learning, cluster information inference and feature selection are incorporated into a unified framework and can benefit from each other, such that the discriminative features can be selected under the guidance of the learned structure compatible across all views.

3 Optimization and Analyses

To solve the problem in Eq. (8), an iterative optimization is devised to solve one variable by fixing other variables. Considering that the l2,0-norm optimization problem is complicated, an auxiliary variable E = W is introduced to transform Eq. (8) into the following equivalent problem:

where µ ∈ R1×1 and Π ∈ Rn×c denote the penalty parameter and Lagrange multipliers, respectively. The solution procedures are given as follows:

• U subproblem: When fixing other variables, the problem of Eq. (9) is simplified into:

Algorithm 1 Optimization procedures for EMUFS

Input: Multi-view data X = [X1, · · · ,XV ]T , the cluster number c, and the parameters λ, β and γ;

• 1: Initialize the view-weights αv = 1/V , a random feature selection matrix W, E = Π = 0, µ = 1 and ρ = 1.1;
• 2: Generate the anchor set {Zv}Vv=1 , and initialize the membership matrices {Uv}Vv=1 by FCM;
• 3: Learn the permutation matrix Tv by solving Eq. (6);
• 4: repeat
• 5: Update U by Eq. (10);
• 6: Update α by Eq. (13);
• 7: UpdateWby Eq. (15);
• 8: Update E by Eq. (16);
• 9: Update S by Eq. (19);
• 10: Update F by Eq. (19);
• 11: Update Π and µ by Eq. (20);
• 12: until Eq. (9) converges;

Output: Feature selection matrixWwith k nonzero rows.

For computational efficiency, we first ignore the constraints to calculate the latent solution U∗ and then project U∗ into the constrained space. Specifically, setting the derivative of Eq. (10) w.r.t. U to zero, the latent solution of U is obtained as: U∗ = (λST S + βI)-1 (λST F + β ∑Vv=1 αv ˜Uv). Subsequently, the optimal solution of U can be derived by solving:

Eq. (11) can be solved with a closed-form solution [Huang et al., 2015]. Unlike previous methods that directly learn the cluster information of all samples and need the O(n2 ) computational complexity at least, EMUFS explores the cluster structure of anchors first and then uses the learned bipartite graph to propagate the cluster information, avoiding the decomposition or inverse operations of n-order dense matrices.

• α subproblem: By fixing the other variables, the optimization subproblem w.r.t. α is:

Setting ψ = vec(S) ∈ Rnm×1 , ω = vec(U) ∈ Rmc×1 , Ψ = [vec(S1),· · · ,vec(SV )] ∈ Rnm×V and Ω = [vec( ˜U1),· · · ,vec( ˜UV )] ∈ Rmc×V ), thus Eq. (12) becomes:

where Q = ΨT Ψ + ΩT Ω, p = ΨT ψ + ΩT ω. Since Q is semi-definite, Eq. (13) is a quadratic convex problem and can be solved efficiently [Jiang et al., 2023].

• W subproblem: By fixing other variables except for W, Eq. (9) is simplified into:

Setting the derivative of Eq. (14) w.r.t. W to zero, we have:

where M = XXT + ZΛZT - XSZT - ZST XT .

• E subproblem: By fixing the other variables except for E, we have the following subproblem:

E can be directly solved by setting the d - k rows of W- Πµ with the smallest l2-norm to zeros.

• S subproblem: By fixing the other variables except for S, we have the following subproblem:

Noting that the optimization problem in Eq. (17) is independent for each row (i.e., si), we can calculate S by rows:

where fi and ai denote the i-th row of F and A = ∑Vv=1 αvSv, and di is a row vector with dij = ‖WT xi -WT zj‖22. Setting the derivative of Eq. (18) w.r.t. si to zero, the latent solution of si is obtained as: s∗i = (λfiUT +βai- γ2 di)(λUUT +βI)-1 . Thus, the optimal solution of si can be obtained by solving:

which can be effectively solved by [Huang et al., 2015].

• F subproblem: Fixing other variables, we can optimize F by rows:

Eq. (20) can be solved with a closed-form solution.

• Update ALM parameters: In each iteration, the penalty parameter µ and the Lagrange multipliers Π are updated as:

where ρ is a constant updated rate. During the optimization, EMUFS separately optimizes each subproblem, decreasing the objective value monotonically until convergence.

Computational Complexity

The steps for solving the problem (9) are summarized in Algorithm 1. Specifically, selecting m anchors takes O(nm), calculating {Uv}Vv=1 by FCM requires O(mdcV ), and learning the permutation matrices needs O(mc2V ). Afterward, updating U, W and S involve the inverses of matrices, requiring O(nmd+m2 c+m3 ), O(nd2+nmd+d3 ) and O(nm2+ndc+m3 ). Besides, calculating α takes O(nmV 2 ), and the optimization of E and F respectively take O(dk+dc) and O(nc). Since c and V are small constants, the computational complexity of EMUFS in each iteration is O(nm2 +nd2 +m3 +d3 ), which is linearly related to the sample scale.

4 Experiments

4.1 Experimental Settings

In this section, six real-word datasets are employed, including flower-17 1 , Leaves 2 , NUS 3 , Scene 4 , ALOI 5 and Youtube 6 . The details of each dataset are listed in Table 2. To comprehensively verify the superiority and effectiveness of EMUFS, we conduct experiments with six state-of-the-art competitors, including (1) Unsupervised Feature Selection with Structured Graph Optimization (SOGFS) [Nie et al., 2016]; (2) MultiView Clustering and Feature Learning via Structured Sparsity (MVCSS) [Wang et al., 2013]; (3) Multi-view Unsupervised Feature Selection with Adaptive Similarity and View Weight (ASVW) [Hou et al., 2017]; (4) Multi-view Feature Selection via Nonnegative Structured Graph Learning (NSGL) [Bai et al., 2020]; (5) Multilevel Projections with Adaptive Neighbor Graph for Unsupervised Multi-View Feature Selection (MAMFS) [Zhang et al., 2021]; (6) Robust Unsupervised Feature Selection via Multi-Group Adaptive Graph Representation (MGAGR) [You et al., 2023]. To ensure comparison fairness, the parameters of all competitors are tuned following their respective works. The regularization parameters for EMUFS are searched in a grid of {10-3 , 10-2 , · · · , 103 }, with the number of anchors set as m = 10% × n. The Kmeans clustering is independently executed 20 times on the selected feature subsets, and the average results, including the clustering accuracy (ACC) and the normalized mutual information (NMI), are reported to evaluate the performance.

4.2 Comparison Results

The means and standard deviations of ACC and NMI are presented in Tables 4 and 5, where the optimal and secondbest results are prominently indicated in bold and underlined formatting, respectively. The following conclusions can be drawn: (1) Across varying numbers of selected features, EMUFS consistently exhibits competitive or superior results, fully demonstrating its effectiveness in multi-view feature selection. (2) The ACC and NMI scores achieved through the EMUFS outperform those of the single-view methodology. This underscores the assertion that harnessing distinct information from multiple views enhances the selection of informative features. (3) Compared with other multi-view feature selection methods, EMUFS consistently attains superior performance, highlighting the effectiveness of collaborative utilization of the cluster structure and the similarity structure. Meanwhile, to assess the efficiency of EMUFS, Table 3 summarizes the computation complexity of each method and Fig. 3 shows the running times versus the training sample scale on the ALOI and Youtube datasets. We find that the running times of EMUFS exhibit a linear increase, while other methods emerge an exponentially increasing trend with the increased sample scale, fully validating the efficiency of propagating cluster information on the bipartite graph.

1 https://www.robots.ox.ac.uk/ vgg/data/flowers/

2 https://archive.ics.uci.edu/dataset/

3 https://lms.comp.nus.edu.sg/wp-

content/uploads/2019/research/nuswide/NUS-WIDE.html

4 http://people.csail.mit.edu/torralba/code/spatialenvelope/

5 https://aloi.science.uva.nl/

6 https://archive.ics.uci.edu/dataset/269/

4.3 Ablation Study

To investigate the significance of adaptive structure learning and inference, an ablation study is conducted to design three variants of EMUFS: EMUFS1, wherein the similarity structure is only derived from original data, overlooking the information from projection space; EMUFS2, a variation of EMUFS that excludes the collaborative fusion model, guiding feature selection by fixed graphs and membership matrices; and EMUFS3 employs the unaligned membership matrices to learn the cluster structure. The results of EMUFS and its distilled versions are depicted in Fig. 4. We can conclude that: (1) The ACC of EMUFS1 is inferior to EMUFS, indicating that the dynamic graph learning on selected feature space has an effective influence on the overall performance; (2) EMUFS

achieves superior results than EMUFS2, validating that the collaborative fusion of similarity structure and cluster information can facilitate feature selection; (3) Comparative analyses between EMUFS and EMUFS3 demonstrate that simply concatenating different membership matrices impairs the consistency of clustering centers among views.

4.4 Visualization

To visually evaluate the quality of selected features, the TSNE is employed to project the selected features into a twodimensional space [Van der Maaten and Hinton, 2008]. In this context, we select 320 samples from 20 clusters of the Leaves dataset for visualization, in which each sample has three views (i.e. View #1,#2 and #3), and each view contains 64 features. Figs. 5 (a)-(c) show the results of the original three views, while Figs. 5 (d)-(f) depict the visualizations of feature subsets selected by ASVW, MAMFS, and EMUFS, respectively. To ensure a fair evaluation, the number of selected features is set to 64 for each method. As depicted in Fig. 5, the visualizations of the original views exhibit significant overlaps between different clusters. In contrast, ASVW, MAMFS, and EMUFS achieve separable results, highlighting the significance of multi-view feature selection. Moreover, the inter-cluster distance obtained by EMUFS is larger than those of ASVW and MAMFS, demonstrating that EMUFS can select a compact subset of discriminative features.

4.5 Parameter Sensitivity and Convergence

EMUFS encompasses three intrinsic parameters, namely λ, β and γ. To assess the impacts of these parameters, we present the clustering accuracies under distinct parameter settings, alongside varying numbers of selected features, in Fig. 6.

This depiction shows that EMUFS can perform better, particularly when λ assumes a value smaller than 1. This observation effectively indicates that the adaptive structure learning and fusion indeed contribute to identifying informative features. Meanwhile, to illustrate the convergence behavior of EMUFS, Fig. 7 provides the variations of the objective function values, which shows that the objective function exhibits a rapid decrease and converges to a stable value quickly.

5 Conclusion

In this paper, we propose an efficient multi-view unsupervised feature selection with adaptive structure learning and inference (EMUFS). Unlike existing methods that exploit the unreliable similarity structures as well as overlook the cluster structures of data, EMUFS exploits the similarity structure from the selected feature space to alleviate the impacts of low-quality features and explores the cluster structure by membership matrices, so that the feature selection process can be effectively guided by the collaborative cooperation of structures. Moreover, EMUFS learns the cluster structure of samples from anchors via the information propagation on the bipartite graph, reducing the computational cost and strengthening the scalability for large-scale tasks. Extensive experiments demonstrate the effectiveness of EMUFS and its superiority against the state-of-the-art competitors.

Acknowledgments

This work was supported by the "Pioneer" and "Leading Goose" R&D Program of Zhejiang Province, China (Grant No. 2023C01022), the National Natural Science Foundation of China (Nos. 62306171 and 62176001), the Science and Technology Major Project of Shanxi (No. 202201020101006), the Natural Science Foundation of Chongqing (No. CSTB2022NSCQ-MSX1202).