Adaptive Collaborative Correlation Learning-based Semi-Supervised Multi-Label Feature Selection

In this paper, we denote matrices with boldface uppercase letters and vectors with boldface lowercase letters. For an arbitrary matrix ${\mathbf{M}}\in\mathbb{R}^{n\times p}$, $m_{ij}$ indicates the $i$th row and $j$th column entry of $\mathbf{M}$, $\mathbf{m}_{i.}$ and $\mathbf{m}_{.j}$ denote its $i$th row and $j$th column, respectively. We use $\|\mathbf{M}\|_{F}=\sqrt{\sum_{i=1}^{n}\sum_{j=1}^{p}\left|m_{ij}\right|^{2}}$ to denote the Frobenius norm of ${\mathbf{M}}$. The ${\ell_{2,1}}$-norm of $\mathbf{M}$ is defined as $\|\mathbf{M}\|_{2,1}=\sum_{i=1}^{n}{\sqrt{\sum_{j=1}^{p}{m_{ij}^{2}}}}=\sum_{i=1}^{n}{\|\mathbf{m}_{i.}\|_{2}}$, where $\|\mathbf{m}_{i.}\|_{2}$ indicates the $\ell_{2}$-norm of the $i$th row vector $\mathbf{m}_{i.}$. Let $\operatorname{Tr}{(\mathbf{M})}$ and $\mathbf{M}^{T}$ respectively represent the trace and the transpose of ${\mathbf{M}}$. Besides, ${\mathbf{H}}={\mathbf{I}}-\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}$ is a centering matrix, where $\mathbf{I}$ is an identity matrix and ${\mathbf{1}_{n}}\in\mathbb{R}^{n\times 1}$ is a column vector of ones.

Let $\mathbf{X}=\left[\mathbf{X}_{l},\mathbf{X}_{u}\right]\in\mathbb{R}^{d\times n}$ be a given data matrix with $d$ dimensional features and $n$ instances, where $\mathbf{X}_{l}\in\mathbb{R}^{d\times n_{1}}$ is the labeled data, $\mathbf{X}_{u}\in\mathbb{R}^{d\times n_{2}}$ is the unlabeled data and ${n_{1}+n_{2}=n}$. The corresponding label matrix of $\mathbf{X}$ is denoted by $\mathbf{Y}=\left[\begin{array}[]{c}\mathbf{Y}_{l}\\ \mathbf{Y}_{u}\end{array}\right]\in\mathbb{R}^{n\times c}$ with $c$ categories, where $\mathbf{Y}_{l}\in\mathbb{R}^{n_{1}\times c}$ and $\mathbf{Y}_{u}\in\mathbb{R}^{n_{2}\times c}$ denote the labels of $\mathbf{X}_{l}$ and $\mathbf{X}_{u}$, respectively. In $\mathbf{Y}_{l}$, ${y_{ij}=1}$ indicates the $i$th instance is labeled as the $j$th class, otherwise it is 0. The label matrix $\mathbf{Y}_{u}$ of the unlabeled data is set to $0$. In semi-supervised multi-label feature selection, our aim is to select $k$ informative features from the given dataset, which is much less than the total number of features in it. The framework of Access-MFS is shown in Fig. 1.

In order to learn a mapping function from samples with high dimensional features to the desired information (such as classification label or latent features), the least squares regression model has been extensively applied in various machine learn tasks including classification, regression and dimension reduction [30, 31]. Given the input dataset $\mathcal{D}=\{(\mathbf{X},\mathbf{Y})\}$, where $\mathbf{X}\in\mathbb{R}^{d\times n}$ and $\mathbf{Y}\in\mathbb{R}^{n\times c}$ are the data matrix and the corresponding label matrix, respectively, the traditional least squares regression model is defined as follows:

where $\mathbf{W}\in\mathbb{R}^{d\times c}$ is a projection matrix, $\Omega(\|\mathbf{W}\|)$ indicates certain regularization on $\mathbf{W}$ and $\lambda$ is a regularization parameter. However, the abovementioned model cannot be directly applied to semi-supervised multi-label feature selection. Eq. (1) cannot be solved when only a subset of the labels in the label matrix $\mathbf{Y}$ is known. Furthermore, to select the dicriminative features and avoid the trivial solution, a column full rank constraint is typically imposed on $\mathbf{W}$ in Eq. (1). This approach disregards the redundancy of selected features. In order to deal with these two issues, we propose a generalized regression model with an extended uncorrelated constraint for semi-supervised multi-label feature selection, which is formulated as follows:

where $\mathbf{F}=\left[\begin{array}[]{c}\mathbf{F}_{l}\\ \mathbf{F}_{u}\end{array}\right]\in\mathbb{R}^{n\times c}$ is a predicted label matrix and $\mathbf{W}^{T}\mathbf{R}\mathbf{W}=\mathbf{I}$ is an extended uncorrelated constraint. In Eq. (2), $\mathbf{F}$ is comprised of the predicted label $\mathbf{F}_{l}$ for the labeled data $\mathbf{X}_{l}$ and $\mathbf{F}_{u}$ for the unlabeled data $\mathbf{X}_{u}$. We employ the predicted label matrix $\mathbf{F}$ as an optimization variable in Eq. (2), simultaneously ensuring that the predicted label $\mathbf{F}_{l}$ is consistent with the ground-truth label $\mathbf{Y}_{l}$ of $\mathbf{X}_{l}$. Besides, $\ell_{2,1}$-norm is applied to $\mathbf{W}$ to induce row sparsity, facilitating feature selection. Then, we can select the top $k$ features by calculating the $\ell_{2}$ norm of each row in $\mathbf{W}$ and then sorting them in descending order.

To select the discriminative and uncorrelated features, we propose an extended uncorrelated constraint on $\mathbf{W}$, denoted as $\mathbf{W}^{T}\mathbf{R}\mathbf{W}=\mathbf{I}$. Here, $\mathbf{R}$ is defined as $\mathbf{X}\mathbf{H}\mathbf{X}^{T}+\lambda\mathbf{D}+\theta\mathbf{X}\mathbf{L}_{s}\mathbf{X}^{T}$, where the matrix $\mathbf{D}\in\mathbb{R}^{d\times d}$ is diagonal, with the $i$th diagonal entry given by $\mathbf{D}(i,i)=\frac{1}{2\sqrt{\|\mathbf{w}_{i.}\|_{2}^{2}+\epsilon}}$ ($\epsilon$ is a small constant to avoid division by 0). Additional, $\mathbf{L}_{s}=\mathbf{D}_{s}-\mathbf{S}$ represents the Laplacian matrix of instance similarity matrix $\mathbf{S}$, $\mathbf{D}_{s}$ is the degree matrix of $\mathbf{S}$, and $\theta$ is a trade-off parameter. The uncorrelated constraint we proposed consists of three terms obtained by expanding $\mathbf{R}$. The first term aims to promote the orthonormality of the projected dimensions, which makes the low-dimensional instances to be uncorrelated. The second term is added to the first term to avoid the singularity of $\mathbf{X}\mathbf{H}\mathbf{X}^{T}$. The third term is advantageous in reducing the variance among samples within the same neighborhood under the graph structure. When $\lambda=\theta=0$, the proposed constraint reduces to the traditional uncorrelated constraint. The proposed constraint is beneficial to select discriminative features that are also uncorrelated.

For semi-supervised multi-label feature selection [22, 23, 16, 28], the sample similarity structure and the label correlations serve as two crucial priors. Most existing methods use a predefined graph approach to capture the sample similarity or the label correlations. However, the presence of noise and outliers within the original feature space can undermine the reliability of the resulting graph. Besides, in semi-supervised settings where some labels are unknown, this approach cannot fully ascertain the label correlations. In this paper, we maintain the sample similarity structure and investigate label correlations by adaptively learning both the instance similarity graph and the label similarity graph. Guided by two fundamental assumptions that similar instances tend to have similar labels, and that samples close to each other in high-dimensional space should also be close in low-dimensional space, we formulate the instance similarity graph learning as follows:

where $\mathbf{S}$ is the instance similarity matrix, $\mathbf{f}_{i.}$ in the predicted label matrix $\mathbf{F}$ denotes the label of the $i$th instance $\mathbf{x}_{.i}$, and $\alpha$ is a regularization parameter to control the sparsity of $\mathbf{S}$. The first two terms of Eq. (LABEL:New3) are designed to learn the instance similarity matrix from the perspectives of the label space and the feature space respectively. The third term serves as a regularization to prevent the trivial solution where each row in $\mathbf{S}$ contains only one element with a value of 1, while all other elements are 0. By defining the Laplacian matrix $\mathbf{L}_{s}=\mathbf{D}_{s}-\mathbf{S}$, where $\mathbf{D}_{s}$ is a diagonal matrix with its $i$th diagonal element equals to the sum of the $i$th row of $\mathbf{S}$, we can simplify Eq. (LABEL:New3) as follows:

Furthermore, in order to explore label correlations, we operate under the assumption that a stronger positive correlation between two labels leads to greater similarity in the predicted labels. This assumption guides the learning of the label similarity graph, which can be expressed as follows:

where $\mathbf{P}\in\mathbb{R}^{c\times c}$ denotes the label similarity matrix, $\mathbf{f}_{.i}$ is the $i$th label vector corresponding to the $i$th column of $\mathbf{F}$, and $\beta$ is a regularization parameter. From Eq. (5), it is evident that a larger $p_{ij}$ value indicates greater similarity between $\mathbf{f}_{.i}$ and $\mathbf{f}_{.j}$, and the converse is also true. We define the Laplacian matrix $\mathbf{L}_{p}=\mathbf{D}_{p}-\mathbf{P}$, where $\mathbf{D}_{p}$ is a diagonal matrix with the $i$th diagonal entry is $\sum_{j=1}^{c}p_{ij}$. Then, Eq. (5) can be rewritten as

By jointly utilizing Eqs. (LABEL:New4) and (6), we are able to collaboratively learn both the sample similarity matrix and the label similarity matrix in an adaptive manner, rather than relying on the predefined method. This is helpful to enhance the performance of feature selection.

By combining Eqs. (2), (LABEL:New4) and (6) together, the proposed semi-supervised multi-label feature selection method Access-MFS is summarized as follows:

where $\Xi=\{\mathbf{W},\mathbf{b},\mathbf{F},\mathbf{S},\mathbf{P}\}$, and $\theta$ and $\mu$ are two trade-off hyper-parameters. These two regularization parameters $\alpha$ and $\beta$ can be automatically determined during the optimization process.

In our Access-MFS method, we integrate feature selection, the collaborative learning of the instance similarity graph and the label similarity graph, and the label learning into a unified framework, enabling these different learning tasks to promote each other. Access-MFS can offer two key benefits: First, the proposed extended regression model not only maintains consistency between the predicted labels and the ground-truth of the labeled data but also selects discriminative and uncorrelated features. Second, Access-MFS is capable of adaptively learning the instance and label similarity graphs that are more reliable than those generated by predefined methods. This collaborative learning of the two similarity-induced graphs can preserve the local structures of the feature space and label space concurrently.

When other variables are fixed, we can disregard the terms that do not involve $\mathbf{W}$ in Eq. (8). Then, $\mathbf{W}$ can be obtained by solving the following problem:

According to [33], we have $\frac{\partial\|\mathbf{W}\|_{2,1}}{\partial\mathbf{W}}=2\mathbf{D}\mathbf{W}$. Then, Eq. (9) can be transformed into the following equivalent form:

Based on the matrix calculus theory, Eq (10) can be further derived as follows:

Since the constraint $\mathbf{W}^{T}\mathbf{R}\mathbf{W}=\mathbf{I}$ and $\mathbf{F}$ is fixed, Eq. (11) simplifies to the following problem.

Let $\mathbf{A}=\mathbf{R}^{\frac{1}{2}}\mathbf{W}$ and $\mathbf{B}=\mathbf{R}^{-\frac{1}{2}}\mathbf{X}\mathbf{H}\mathbf{F}$. Then, Eq. (12) is transformed into

According to [34], the optimal solution for Eq. (13) can be obtained as $\mathbf{A}=\mathbf{V}_{l}\mathbf{V}_{r}^{T}$, where $\mathbf{V}_{l}$ and $\mathbf{V}_{r}$ respectively denote the left and right singular matrices derived from the compact singular value decomposition (C-SVD) of $\mathbf{B}$. Hence, the optimal solution for Eq. (12) is derived as

In Eq. (14), as $\mathbf{R}$ contains $\mathbf{D}$, which is related to $\mathbf{W}$, we can update $\mathbf{W}$ and $\mathbf{D}$ alternatively to obtain the final optimal solution. The detailed procedure of solving problem (12) is listed in Algorithm 1.

By ignoring other fixed variables, we can solve the following problem to obtain $\mathbf{F}$.

Let $\mathbf{U}$ be a diagonal matrix, where the $i$th diagonal entry $u_{ii}$ is defined as 1 if the $i$-th sample $\mathbf{x}_{.i}$ is labeled, and 0 otherwise. Then, we have $\|{\mathbf{F}_{l}-\mathbf{Y}_{l}}\|_{F}^{2}=\operatorname{Tr}((\mathbf{F}-\mathbf{Y})^{T}\mathbf{U}(\mathbf{F}-\mathbf{Y}))$. By following a similar deductive process as outlined in (11), problem (15) can be transformed into the following equivalent trace form:

where $\mathbf{Q}=\theta\mathbf{L}_{s}+\mathbf{H}+\mathbf{U}$, $\mathbf{C}=\mathbf{H}\mathbf{X}^{T}\mathbf{W}+\mathbf{U}\mathbf{Y}$.

Take the derivation of Eq.(16) w.r.t. ${\mathbf{F}}$ and set it to 0, we can obtain

The optimal solution ${\mathbf{F}}$ for Eq. (17) can be obtained by using the proposed algorithm in [35].

While $\mathbf{W}$, $\mathbf{F}$ and $\mathbf{P}$ are fixed, the optimization problem in Eq. (8) is equivalent to solve Eq. (LABEL:New3). By setting a matrix $\mathbf{M}=(m_{ij})_{n\times n}$, where $m_{ij}=\frac{1}{2}\|\mathbf{f}_{i.}-\mathbf{f}_{j.}\|_{2}^{2}+\frac{1}{2}\|\mathbf{W}^{T}\mathbf{x}_{.i}-\mathbf{W}^{T}\mathbf{x}_{.j}\|_{2}^{2}$, Eq. (LABEL:New3) is transformed into

Note that Eq. (18) is independent for each row. Hence, for each $i$, we can rewritten Eq. (18) by using the method of completing the square as follows:

Then, the Lagrangian function of Eq. (19) is written as:

where $\psi$ and $\bm{\varphi}=[\varphi_{1},\varphi_{2},\cdots,\varphi_{n}]^{T}$ are the Lagrangian multipliers. Based on the KKT conditions, we have ${s}_{ij}+\frac{m_{ij}}{2\alpha}-\psi-\varphi_{j}=0$ and $s_{ij}\varphi_{j}=0$. Then, we can get ${s}_{ij}=(\psi-\frac{m_{ij}}{2\alpha})_{+}$, where $(z)_{+}=max(z,0)$.

In practice, each sample tends to be similar to its neighbours. Therefore, we aim for $\mathbf{s}_{i.}$ to have $k_{s}$ nonzero values, indicating that the $i$th sample is similar to its $k_{s}$ closest neighbours. Assuming that $m_{i1},m_{i2},\cdots,m_{in}$ are arranged in ascending order, we prefer ${s}_{ik_{s}}>0$ and ${s}_{ik_{s}+1}=0$. As a result, we have $\alpha=\frac{m_{ik_{s}+1}}{2\psi}$. Besides, according to the constraint $\mathbf{s}_{i.}\mathbf{1}_{n}=1$, we get $\psi=\frac{1}{k_{s}}+\frac{\sum_{j=1}^{k_{s}}m_{ij}}{2k_{s}\alpha}$. By substituting $\psi$ into the obtained $\alpha$, we can calculate the regularization parameter as $\alpha=\frac{k_{s}m_{ik_{s}+1}-\sum_{j=1}^{k_{s}}m_{ij}}{2}$. Then, we achieve the optimal solution ${s}_{ij}$ as follows:

With other variables fixed, $\mathbf{P}$ can be optimized by solving the following problem:

Let ${\mathbf{G}}$ be a ${c\times c}$ matrix with its $(i,j)$th entry $g_{ij}=\frac{1}{2}\|\mathbf{f}_{.i}-\mathbf{f}_{.j}\|_{2}^{2}$. Then, Eq. (22) is transformed into

Given that the optimization of each row in $\mathbf{P}$ is independent, Eq. (23) can be addressed by optimizing each individual subproblem as follows:

Following a similar procedure to that used in solving Eq. (19), we can determine the regularization parameter $\beta=\frac{k_{p}g_{ik_{p}+1}-\sum_{j=1}^{k_{p}}g_{ij}}{2}$, where $k_{p}$ denotes the number of nonzero elements in $\mathbf{p}_{i.}$. Furthermore, the optimal solution ${p}_{ij}$ is formulated as follows:

Up to this point, we have obtained the updated expression of $\mathbf{W}$, $\mathbf{F}$, $\mathbf{S}$ and $\mathbf{P}$. The detailed optimization procedure of Access-MFS is summarized in Algorithm 2.

Due to the objective function in Eq. (8) not being convex w.r.t. four variables $\mathbf{W}$, $\mathbf{F}$, $\mathbf{S}$ and $\mathbf{P}$ simultaneously, we address this by dividing it into four sub-objective functions, namely, Eqs. (9), (15), (18), and (22), each of which is separately solved with other variables fixed. Therefore, the convergence of Algorithm 2 can be demonstrated by proving that each sub-objective function decreases monotonically. We first present the following theorem to prove the monotonic decrease of the objective function in Eq. (9) when updating $\mathbf{W}$ with $\mathbf{F}$, $\mathbf{S}$ and $\mathbf{P}$ are fixed.

We can prove this theorem based on the property in [33] and the result in [34]. Due to space constraints, the detailed proof of Theorem 1 is provided in the supplementary material.

Besides, as Eq. (15) is equivalent to Eq. (16), we only need to demonstrate that the objective function in Eq.(16) with respect to ${\mathbf{F}}$ is a monotonically decreasing function. It is easy to verify that the matrix $\mathbf{Q}$ and the Laplacian matrix $\mathbf{L}_{p}$ are both positive semidefinite. Consequently, the quadratic forms $\mathbf{F}^{T}\mathbf{Q}\mathbf{F}-2\mathbf{F}^{T}\mathbf{C}$ and $\mathbf{F}\mathbf{L}_{p}\mathbf{F}^{T}$ are convex. Hence, the objective function in Eq.(16) is convex. According to [35], we can easily obtain that the objective function in Eq.(16) monotonically decrease by using the updating rules in Algorithm 2. Additionally, the objective functions in Eqs. (18) and (22) are convex w.r.t. $\mathbf{S}$ and $\mathbf{P}$, and possess closed-form solutions, ensuring the convergence of the updates for $\mathbf{S}$ and $\mathbf{P}$, respectively. Therefore, we can conclude that the objective function in Eq.(8) monotonically decreases with each iteration of Algorithm 2. Moreover, the convergence behavior of Algorithm 2 is further demonstrated through experiments.

In Algorithm 2, four variables are updated alternately by solving Eqs. (9), (15), (18), and (22). The optimization of Eq. (9) is further transformed into solve Eq. (13). According to [34], the time complexity for updating $\mathbf{W}$ in Eq. (13) is $\mathcal{O}(d^{3})$. For updating $\mathbf{F}$, a proposed algorithm in [35] is applied into solve Eq. (15). Based on [35], we can calculate the computational complexity for updating $\mathbf{F}$, which is $\mathcal{O}(n^{2}c+c^{2}n)$. Eq. (18) is solved by updating $\mathbf{S}$ row by row. According to the closed form solution of $\mathbf{S}$ in Eq. (21), the time complexity of updating $\mathbf{S}$ is $\mathcal{O}(nk_{s}d)$. The optimization $\mathbf{P}$ in Eq. (22) is similar to solving $\mathbf{S}$. In the same way, we can determine the time complexity of $\mathbf{P}$ as $\mathcal{O}(ck_{p}n)$. Therefore, the total computational complexity of Algorithm 2 is $\mathcal{O}((d^{3}+n^{2}c+c^{2}n+nk_{s}d+ck_{p}n)T)$, where $T$ is the number of iteration.

In this section, we demonstrate the superior performance of the proposed method Access-MFS compared with other competing methods in terms of AP, MaF, RL and OE. Table II summarizes the experimental results of various methods on eight multi-label datasets based on AP and MaF metrics, with a fixed ratio of labeled instances at 40%, selecting 30 features for the Parkinson dataset and 150 features for the remaining datasets. Due to space constraints, the experimental results regarding RL and OE can be found in Table 1 of the supplementary material. From Table II, we can see that the proposed method Access-MFS consistently outperforms other methods across all datasets. As to VirusGO, Parkinson and Recreation datasets, Access-MFS achieves an average improvement of over 10% in both AP and MaF metrics compared to all other methods. On Medical dataset, Access-MFS gains over 32% and 15% average improvement in terms of AP and MaF, respectively. As to Slashdot datasets, Access-MFS outperforms other methods with more than 13% improvement in average AP and MaF. On Computer dataset, Access-MFS obtains over 2.5% average improvement in both AP and MaF. On Langlog and Enron datasets, Access-MFS achieves an average improvement of over 3.6% in AP and still outperforms all other methods in MaF. Besides, Table 1 in the supplementary material also shows that the proposed Access-MFS is still better than other methods on all datasets in terms of RL and OE. Furthermore, compared to the baseline method All-Fea, Access-MFS is superior across all datasets in terms of AP, MaF, RL, and OE, demonstrating the effectiveness of Access-MFS. Access-MFS also shows better performance than the supervised method LEFS on all datasets, indicating the effectiveness of the proposed semi-supervised learning strategy in enhancing feature selection performance.

Due to the difficulty in determining the optimal number of selected features, we also present the performance (AP, MaF, RL and OE) of different methods as the number of selected features varies. Since the page limitation, we only report the experimental results for AP and MaF. The results for RL and OE can be found in Figs. 1 and 2 of the supplementary material. Figs. 2 and 3 respectively show the AP and MaF values for different numbers of selected features, with the labeled instance ratio fixed at 40%. As illustrated in these two figures, the proposed Access-MFS method outperforms other methods in most cases, with the number of selected features varying from 5 to 55 on Parkinson dataset and from 100 to 200 on the other datasets. Furthermore, we also investigate the performance of different methods with varying ratios of labeled instances. Figs. 4 and 5 respectively show the AP and MaF of different methods when the ratio of labeled instances ranges from 10% to 50%. The experimental results for RL and OE with varying ratios of labeled instances can be found in Figs. 3 and 4 of the supplementary material, respectively. From these figures, we can see that our method achieves better performance in most cases. In addition, our method performs better as the ratio of labeled instances increases, indicating that our approach effectively leverages labeled information to guide the collaborative learning of sample and label similarity graphs, ultimately enhancing feature selection performance. The superior performance of the proposed method is attributed to the adaptive collaborative learning of similarity graphs from both the sample and label perspectives, which are embedded into a generalized regression model with an extended uncorrelated constraint and a consistency constraint between predicted and existing labels.

In this section, we conduct experiments to investigate the sensitivity of the proposed Access-MFS to three parameters, i.e., $\lambda$, $\theta$, and ${\mu}$. Fig. 6 shows the performance variations w.r.t. AP on Enron and Recreation datasets when two of the parameters $\lambda$, $\theta$, and ${\mu}$ are varied while the third is kept fixed. We can observe that the parameters $\lambda$ and $\theta$ are relatively more sensitive compared to the parameter ${\mu}$. Besides, when ${\mu}$ is fixed, the proposed method achieves prominent performances with the parameter combinations of $\lambda=10$ or $1$ and $\theta=10$ in most cases. Hence, We can empirically fine-tune $\lambda$ and $\theta$ within a narrower range discussed to achieve a better performance.

The theoretical convergence of the proposed Access-MFS algorithm has been established in Section 5.1. This subsection provides experimental validation of its convergence and analyzes the speed of convergence. Fig. 7 displays the convergence curves of Access-MFS on VirusGo, Parkinson, Enron and Recreation datasets, demonstrating the variation of the objective function value with the number of iterations. As illustrated in Fig. 7, the convergence curves steeply fall within a few iterations and approach stability almost within 10 iterations. The experimental results demonstrate that the proposed method can converge effectively.