Unified View Imputation and Feature Selection Learning for Incomplete Multi-view Data

1 Introduction

Multi-view data describes the same sample from different perspectives or forms, often represented by high-dimensional features [Liu et al., 2018; Zhang et al., 2021]. In practical applications, acquiring labels for multi-view data is typically difficult due to the considerable amount of time and effort required. High-dimensional, unlabeled multi-view data presents challenges for machine learning applications, such as the curse of dimensionality, performance degradation in downstream tasks, and high computational costs. The recently developed dimensionality reduction technique, multiview unsupervised feature selection (MUFS), aims to tackle these difficulties by selecting informative features from multiview data in an unsupervised manner [Zhang et al., 2019; Shi et al., 2023].

∗Corresponding Author

The existing MUFS approaches can generally be divided into two categories. The first category of methods sequentially connects features from multiple views into a vector, and subsequently employs single-view feature selection methods such as LPscore [He et al., 2005], EGCFS [Zhang et al., 2020], and FSDK [Nie et al., 2023]. The second category of methods directly selects features from multi-view data by considering the correlations among different views. Typically, CvLP-DCL [Tang et al., 2021] learns view-specific and view-common label spaces and constructs a cross-view similarity graph to capture consensus and diversity information from multiple views. TLR-MFS [Yuan et al., 2022] enforces a tensor low-rank constraint on the similarity graph matrix to leverage high-order consensus information among different views in the feature selection procedure. [Cao and Xie, 2024] fully utilizes neighbor information of differing views to construct a similarity graph for feature selection. However, previous studies assumed that each sample is present across all views, which may not hold in real-world scenarios. For example, in Alzheimer's disease detection, many patients only have features from magnetic resonance imaging (MRI) and lack positron emission tomography (PET) scans due to the high cost of PET imaging [Cai et al., 2018]. There are few studies on unsupervised feature selection in incomplete multi-view data. [Xu et al., 2021] proposed a crossview feature selection method for incomplete multi-view data. This method first fills missing samples with mean values and then uses weighted non-negative matrix factorization on the imputed data to select features. The previously mentioned MUFS methods, when applied to incomplete multi-view data, consist of two sequential stages: first, the imputation of missing data, and then the subsequent selection of features from the imputed multi-view data.

However, the aforementioned methods miss out on the potential synergy by treating imputation and feature selection as two separate processes. Local structural information gleaned from feature selection could guide the imputation process and, conversely, the refined imputation could lead to improved feature selection performance. Furthermore, although these methods have leveraged samples' local structure information-indicating that samples close to each other in high-dimensional space also remain close in low-dimensional space, they have overlooked the exploration of the intrinsic locality of the feature space. Specifically, the capacity for features to be sparsely represented by similar features is a crucial aspect that could enhance feature selection performance.

To address the aforementioned issues, we propose a novel MUFS method named UNified view Imputation and Feature selectIon lEaRning (UNIFIER), which consists of three key components: 1) An adaptive dual-graph learning module that selects discriminative features by leveraging the local structures of both the feature and sample spaces. 2) A bi-level cooperative missing view completion module that effectively utilizes local structure graphs at both the feature and sample levels to impute missing views in samples. 3) A dynamic sample quality assessment module that automatically weighs samples to mitigate the effects of outliers and unreliable restored data. Fig. 1 illustrates the framework of the proposed method UNIFIER. The main contributions of this paper are as follows:

• To the best of our knowledge, this is the first work to integrate multi-view unsupervised feature selection and missing view imputation into a unified learning framework, enabling a seamless synergy between these two processes that culminates in enhanced feature selection performance.
• Simultaneous investigation of the local structures in both the feature and sample spaces is conducted to facilitate missing view imputation and discriminative feature selection. Additionally, a dynamic sample quality assessment based on half-quadratic minimization is proposed, which can alleviate the impact of outliers and unreliable restored data.
• An efficient alternative iterative algorithm is developed to solve the proposed UNIFIER method, and comprehensive experimental results demonstrate the superiority of UNIFIER over several state-of-the-art (SOTA) methods.

2 ProposedMethod

We first summarize some notations throughout this paper. For any matrix M = (mij) ∈ Rp×q , the i-th row and the j-th column of M are denoted as mi· and m·j, respectively. Its Frobenius norm and ℓ2,1-norm are respectively defined as ‖M‖F = √∑pi=1 ∑qj=1 m2ij and ‖M‖2,1 = ∑pi=1 √∑qj=1 m2ij . Tr(M) andM⊤ represent the trace and transpose of M, respectively. In the following, we will introduce three modules of the proposed method UNIFIER in detail.

Adaptive Dual-graph Learning for MUFS. Given a multi-view dataset X = {X(v) ∈ Rn×dv }Vv=1 , where X(v)

Missing sample / feature Observed sample / feature

Figure 1. The framework of the proposed method UNIFIER.

represents the feature matrix of the v-th view, n and dv denote the number of samples and dimensions of X(v) , and V is the number of views. In order to select discriminative features from the given multi-view dataset, a comprehensive exploration of the local structures within both the feature and sample spaces is conducted. By extending the concept of data self-representation [Liu et al., 2021b] to the feature level, it is reasonable to assume that each feature can be reconstructed by a linear combination of a small set of representative features. This can be formalized as follows:

where W(v) ∈ Rdv×dv is the sparse representation graph or feature weight matrix in the v-th view. The i-th row of Wv indicates the contribution of the i-th feature x(v) ·i to the reconstruction of all other features, thereby reflecting the importance of the i-th feature in Xv . Moreover, we employ the ℓ2,1-norm regularization ‖W(v) ‖2,1 to induce sparsity within Wv , which encourages the weights of less significant features to approach zero. Consequently, each feature is selectively associated with only the most representative features, effectively capturing the local structure of the feature space.

Furthermore, according to the spectral graph theory [Dong et al., 2012], if two samples x(v) i· and x(v) j· are similar in high-dimensional space, they will also be similar in lowdimensional space. This allows us to preserve the local geometric structure of the sample space by adaptively learning the nearest neighborhood graph, which can be formulated as follows:

where S(v) is the similarity matrix of the v-th view and ξv is a regularization parameter. The constraint ‖s(v) ·i ‖0 = k is enforced to ensure that x(v) i· is exclusively connected to its k nearest neighbors.

By combiningEqs. (1) and (2), we can obtain the following adaptive dual-graph learning-based MUFS module:

where α(v) is the viewweight. Eq. (3) can simultaneously use the local structure information of both the feature and sample spaces to improve the feature selection performance.

Bi-level Cooperative Missing View Completion. In the context of an incomplete multi-view scenario, where some samples are present in certain views but absent in others, we use ˚X(v) ∈ Rm×dv and ˙X(v) ∈ R(n-m)×dv to represent the feature matrices of missing samples and available samples in X(v) , respectively. Unlike these two-step methods, which sequentially address missing value imputation followed by feature selection, we integrate feature selection and missing view imputation into a unified optimization process. To this end, we incorporate the missing data as a variable into the learning process described by Eq. (3), which will undergo alternate optimization with other variables until convergence. The corresponding objective function is presented below.

where ˚K(v) ∈ Rn×m and ˙K(v) ∈ Rn×(n-m) serve as two indicator matrices, and m denotes the number of missing samples. These matrices are used to project the learned missing samples and available samples into a complete multi-view data ˜X(v) , and their specific definitions are as follows:

In Eq. (4), the missing data ˚X(v) is imputed with collaborative guidance from the sample-level and feature-level graphs obtained from Eq. (3). This imputation, in turn, enhances the learning of local both sample and feature structures. These two processes boost each other in an interplay manner to recover incomplete multi-view data and achieve better feature selection performance.

Dynamic Sample Quality Assessment. Due to the sensitivity of the Frobenius norm-based loss function to outliers [Nie et al., 2010], we adopt the Geman-McClure estimator L(z) = γz2 γ+z2 (γ is the scale parameter) [Barron, 2019] as the loss function in Eq. (4), aiming to reduce the influence of outliers. However, the objective function based on the GemanMcClure loss function is difficult to solve. To cope with this, we replace L(z) with the following equivalent expression according to the half-quadratic minimization theory [Nikolova and Chan, 2007].

where e is an auxiliary variable, and ψ(e) = γ(√e - 1)2 is the dual potential function of Geman-McClure loss function.

Then, the final objective function of the proposed UNIFIER is formulated as

In Eq. (7), e(v) i can assess the quality of the i-th sample ˜x(v) i· based on the optimization result in Eq. (18). Specifically, if ˜x(v) i· is an outlier or an unreliable restored sample, the reconstruction error ‖˜x(v) i· - ˜x(v) i· W(v) ‖22 will be large. As a result, the corresponding weight of ˜x(v) i· will be small, and vice versa. Furthermore, e(v) i is updated adaptively, enabling the automatic assignment of weights to samples of varying qualities.

3 Optimization

Since Eq. (7) is not jointly convex to all four groups of variables, includingW(v) , ˚X(v) , S(v) and e(v) , we propose to optimize them alternatively, i.e., by fixing three groups of variables and optimizing the remaining one alternately.

Update W(v) by Fixing Others. When other variables are fixed, the objective function w.r.t. W(v) becomes:

Algorithm 1 Iterative Algorithm of UNIFIER

Input:Incomplete multi-view data {X(v) ∈ Rn×dv }Vv=1 ; the parameters α(v) and λ; the number of selected features h.

• 1: Initialize D(v) , e(v) , ˚X(v) and S(v) (v = 1, . . . , V ).
• 2: while not convergent do
• 3: Update {W(v) }Vv=1 via Eq. (10);
• 4: Update {D(v) (i, i) = 1/(2√‖w(v) i· ‖22 + ϵ)}Vv=1 ;
• 5: Update {˚X(v) }Vv=1 by solving Eq. (13);
• 6: Update {S(v) }Vv=1 via Eq. (16);
• 7: Update {e(v) }Vv=1 via Eq. (18);
• 8: end while

Output:Sorting the ℓ2-norm of the rows of {W(v) }Vv=1 in descending order and selecting the top h features fromX(v) .

By using the matrix trace property, we can optimize problem (8) by solving its equivalent form:

where D(v) is a diagonal matrix with its i-th diagonal entry given by D(v) (i, i) = 1/2√‖w(v) i· ‖22 + ϵ ( ϵ is a small constant to prevent the denominator from vanishing, ϵ is set to 10-20 in the experiment), L(v) is the Laplacian matrix of S(v) , and E(v) = diag(√e(v) ).

By taking the derivative of Eq. (9) w.r.t. W(v) and setting it to zero, we can obtain the solution of W(v) as follows:

Update ˚X(v) by Fixing Others. After fixing the other variables, the objective function w.r.t. ˚X(v) is reduced to:

Incorporating the equality constraint ˜X(v) = ˙K(v) ˙X(v) + ˚K(v)˚X(v) into the objective function and removing the irrelevant terms w.r.t ˚X(v) , we can reformulate problem (11) as follows:

where H(v) = E(v)E(v)⊤ , R(v) = ˚K(v)⊤ H(v) ˙K(v) ˙X(v) . Taking the derivative of Eq. (12) w.r.t. ˚X(v) and setting it

to zero, we can obtain:

where A(v) = ˚K(v)⊤ L(v)˚K(v) , Q(v) = I - W(v) - W(v)⊤ +W(v)W(v)⊤ , P(v) = α(v)˚K(v)⊤ H(v)˚K(v) , F(v) = -α(v)R(v)Q(v) - ˚K(v)⊤ L(v) ˙K(v) ˙X(v)W(v)W(v)⊤ . Problem (13) is a generalized Sylvester matrix equation, which can be solved according to the method proposed in [Zhang and Yin, 2017].

Update S(v) by Fixing Others. By fixing the other variables, the optimization problemw.r.t S(v) in Eq. (7) becomes independent for different i, allowing us to optimize S(v) by separately solving each s(v) ·i as follows:

By defining a vector b(v) i with the j-th entry as b(v) ij = 12 ‖˜x(v) i· W(v) -˜x(v) j· W(v) ‖22 , problem (14) can be transformed into:

Then, following the same derivation process in [Nie et al., 2019], we can get the optimal solution of s(v) ij as follows:

Besides, the regularization parameter ξv is determined as (kb(v) i,k+1 -∑kt=1 b(v) it )/2 to ensure that s(v) ·i only has k nonzero entries.

Update e(v) by Fixing Others. When other variables are fixed, the objective function w.r.t. e(v) becomes:

By taking the derivative of Eq. (17) w.r.t. e(v) i and setting it to zero, we can get the solution of e(v) i as follows:

Algorithm 1 summarizes the detailed steps to solve Eq. (7). In Algorithm 1, D(v) is initialized as an identity matrix, e(v) i is set as 1/n for all views, {˚X(v) }lv=1 is initialized by the mean values of ˙X(v) , and S(v) is initialized by constructing the k-nearest neighbor graph according to [Li et al., 2019].

4 AlgorithmAnalysis

Time complexity analysis. In Algorithm 1, the updates for W(v) , ˚X(v) , S(v) and ev are performed alternately. In each iteration, updating W(v) costs O(max(n, dv)ndv + d3v ) and updating ˚X(v) costs O((max(m, dv)mdv)t), where t denotes the iteration number of conjugate gradient descent. The updates of S(v) and ev only involve element-based operations, thus their computational cost can be ignored. In summary, the time complexity of each iteration in Algorithm 1 is O(∑Vv=1 [(max(n, dv)ndv + (max(m, dv)mdv)t + d3v )]).

Convergence analysis. Following the similar derivation in [Hou et al., 2013], it is easy to demonstrate that updating W(v) by solving problem (9) leads to a monotonic decrease in the objective value of Eq. (7). Besides, the convergence of optimizing ˚X(v) can be guaranteed according to [Zhang and Yin, 2017]. Moreover, the closed-form solutions of Eqs. (16) and (18) demonstrate the convergence of the updates for S(v) and e(v) . Thus, the objective function value of Eq. (7) will monotonically decrease in each iteration until convergence.

5 Experiments

Datasets. We evaluate the performance of the proposed UNIFIER on six real-world multi-view datasets, including two text datasets: BBCSport [Wen et al., 2019] and BBC4views [Chen et al., 2021]; a face image dataset: Yale [Liu et al., 2021a]; two object image datasets: Aloi [Rocha and Goldenstein, 2013] and Caltech101-20 [Huang et al., 2019]; and a handwritten digit image dataset: USPS2View [Liu et al., 2016]. A detailed description of the datasets is summarized in Table 1. To simulate the incomplete multi-view setting, we follow the method in [Lin et al., 2022] by randomly removing ⌊n×r⌋ instances from each view, with r representing the missing data ratio and ⌊·⌋ denoting the round-down operator. In the experiment, we vary the value of r over the range of {0.1, 0.15, 0.2, 0.25, 0.3}.

Comparison methods. We compare UNIFIER with the following SOTA methods:

1. AllFea utilizes all the original features.
2. LPscore [He et al., 2005] measures the importance of each feature by considering the locality-preserving power.
3. EGCFS [Zhang et al., 2020] embeds between-class scatter matrix maximization into adaptive graph learning.
4. NSGL [Bai et al., 2020] simultaneously learns the similarity graph and pseudo labels to select features.
5. HMUFS [Shen et al., 2020] utilizes an indicator matrix to exclude unobserved data from feature selection.
6. FSDK [Nie et al., 2023] proposes a fast sparse discriminative K-means method for feature selection.
7. CVFS [Xu et al., 2021] combines Hilbert-Schmidt Independence Criterion to perform cross-view feature selection.
8. CvLP-DCL [Tang et al., 2021] learns cross-view similarity graphs for feature selection.
9. TLR-MFS [Yuan et al., 2022] uses tensor low-rank regularization to learn similarity graphs and select features.
10. JMVFG [Fang et al., 2023] integrates feature selection and multi-view graph learning into a unified framework.
11. CFSMO [Cao and Xie, 2024] introduces multi-order similarity learning for the selection of relevant features.

Since most comparison methods cannot be directly utilized with incomplete data, we fill the missing data with the mean values of features before employing these methods. To ensure a fair comparison, we tune the parameters of all methods using a grid search strategy and report the best performance. The parameters α(v) and λ of our method are set within the range of {10-3 , 10-2 , 10-1 , 1, 10, 102 , 103 }. To simplify, the weight parameters for each view are set to be the same and the scale parameter γv of Geman-McClure function is set to 1. As determining the optimal number of selected features is still a challenging problem, we vary the proportion of selected features from {0.1, 0.2, 0.3, 0.4, 0.5}. We adopt a commonly used approach to assess MUFS [Tang et al., 2021; Zhang et al., 2019], employing clustering performance to evaluate the quality of selected features. In this paper, we run the graph-based multi-view clustering algorithm (GMC) [Wang et al., 2019] 30 times on the selected features and use two widely recognized metrics, namely clustering accuracy (ACC) and normalized mutual information (NMI), to measure performance. As GMC is not sensitive to initialization, we only present the average results and omit the standard deviation.

Performance Comparison Table 2 summarizes the performance of UNIFIER and other compared methods on six benchmark datasets, where we achieve the best ACC and NMI in all cases. As can be seen, on two text datasets BBCS and BBC4, UNIFIER outperforms other competitors with average improvements of 21.91% and 24.89% in terms of ACC and NMI, respectively. For two object image datasets Aloi and Cal20, UNIFIER achieves average improvements of 14.08% and 16.64% in ACC and NMI, respectively. And in terms of ACC and NMI, the average improvements of U- NIFIER on the handwritten image dataset USPS are 13.78% and 13.85%, respectively. Additionally, for the face image dataset Yale, UNIFIER continues to outperform other compared methods, respectively showing average improvements of 11.97% and 8.55% in ACC and NMI.

Furthermore, to comprehensively validate the effectiveness of UNIFIER, we also present the results of all methods across various feature selection ratios and missing ratios. In Figs. 2 and 3, the x-axis (FR) denotes the feature selection ratio, while the y-axis represents the ACC and NMI values of comparative methods, respectively, with the missing ratio fixed at 0.2. It can be observed that UNIFIER yields the best performance in most cases compared with other methods when feature selection ratio varies from 0.1 to 0.5. Additionally, in Figs. 4 and 5, the x-axis (MR) indicates the missing ratio, while the y-axis shows the ACC and NMI results of the comparison methods, respectively, with a fixed feature selection ratio of 0.4. As observed, UNIFIER consistently outperforms other comparison methods in most situations. The superior performance of the proposed method is attributed to the integration of feature selection, missing view imputation, and exploration of local structures within both sample and feature spaces in a unified learning framework, where these three components mutually enhance each other. Additionally, the dynamic sample quality assessment module in UNIFIER helps mitigate the impact of unreliable restored data and outliers.

Parameters Sensitivity and Convergence The objective function in Eq.(7) involves three parameters: α(v) , λ, and ξv. The regularization parameter ξv is automatically determined during the process of solving S(v) in Eq.(16). Hence, we only investigate the performance variation of our method at different values of α(v) and λ. Fig. 6 shows how the ACC and NMI results of our method vary with different parameter combinations. We can observe that the parameter λ is somewhat sensitive for our method, while the parameter α(v) exhibits even more sensitive than λ. Moreover, in most cases, our method achieves prominent performances with the parameter combinations of α(v)=0.01 or 0.001 and λ=100. Therefore, we can empirically fine-tune α(v) and λ based on the smaller range discussed previously. Fig. 7 illustrates the variation in the objective values of Eq.(7) across different iterations on the BBCS and USPS datasets. It is evident that the proposed optimization algorithm converges rapidly within 20 iterations.

Ablation Study In this section, we conduct ablation experiments to show the significance of the component terms in the proposed UNIFIER. Two variants of UNIFIER are conducted as follows:

(1) UNIFIER-I (without the bi-level collaborative missing view completion module):

In UNIFIER-I, the missing samples in X(v) are first filled with the means of the features, followed by the same feature selection process as in UNIFIER.

(2) UNIFIER-II (without the dynamic sample quality assessment module):

Table 3 shows the ablation experiment results on six datasets. We can observe a significant decrease in the performance of UNIFIER-I compared to UNIFIER in terms of ACC and NMI. This underscores the benefit of integrating feature selection with missing view completion to improve performance. Furthermore, UNIFIER outperforms UNIFIER-II, highlighting the effectiveness of the dynamic sample quality assessment module in mitigating the influence of unreliable restored data and outliers.

6 Conclusions

In this paper, we have proposed a novel MUFS method for incomplete multi-view data, addressing the limitation of current methods that treat missing data imputation and feature selection as two separate processes. The proposed method UNIFIER integrates feature selection, missing view completion, and the exploration of both local sample and feature structures into a unified learning framework. Furthermore, UNIFIER can automatically assign lower weights to lowquality samples, which is beneficial for alleviating the impact of unreliable restored data and outliers. Experiment results on benchmark datasets demonstrated the superior performance of UNIFIER compared with SOTA methods. In our future work, we will extend our framework to conduct parallel and incremental unsupervised feature selection on large-scale incomplete multi-view datasets.

Acknowledgments

This work was supported by the Natural Science Foundation Project of Sichuan Province (No. 24NSFSC0508), the Youth Fund Project of Humanities and Social Science Research of Ministry of Education (No. 21YJCZH045), and the National Natural Science Foundation of China (No. 62176221).