Graph Random Walk with Feature-Label Space Alignment: A Multi-Label Feature Selection Method

1 Introduction

In recent years, with the exponential growth of feature dimension, feature selection in high-dimensional datasets has become a critical task. By eliminating irrelevant and redundant features while retaining important and relevant ones, feature selection effectively reduces computational time and storage costs [Li et al., 2017]. As a result, feature selection methods have been widely applied across various domains, including text mining [Jin et al., 2023], image annotation [Kong et al., 2012], music classification [Silla Jr et al., 2008], microarray data analysis [Bommert et al., 2022], and biomarker discovery in proteomics [Tang et al., 2021]. Generally, feature selection methods can be categorized into three main types: filter-based methods, wrapper-based methods, and embedded methods [Yao et al., 2017].

∗Corresponding author

Filter-based methods operate independently of the learning method [Zhang et al., 2021]. In contrast, wrapper-based methods [Al-Yaseen et al., 2022] iteratively evaluate and select subsets of features to identify the optimal feature subset. Embedded methods, on the other hand, integrate the feature selection process directly into the learning method [Yamada et al., 2020]. Among embedded methods, many methods leverage sparse regularization to impose constraints that enhance the structural information of the data, thereby capturing the underlying structure more accurately and improving the generalization ability of the method. However, a key challenge for feature selection methods in multi-label learning problems is computing the relevance between features and labels.

The goal of multi-label learning is to assign multiple correct labels to a given instance [Zhu et al., 2018], which poses new challenges compared to traditional single-label learning. Some studies address multi-label problems by transforming them into multiple single-label problems [Lee and Kim, 2015; Lee and Kim, 2017], but these methods often overlook the correlations between labels. Other methods handle multilabel problems by creating label sets [Wang et al., 2021b], grouping related labels together and converting the multilabel problem into a multi-class problem. However, these methods struggle to accurately capture the complex highorder correlations between features and labels in multi-label datasets.

In the real-world scenarios, a label can be associated with multiple other labels, making it inadequate to consider only pairwise label correlations [Zhang and Gao, 2021; Lim and Kim, 2020]. Consequently, the complex and deep relationships between labels have become a key focus of research [Yu et al., 2021; Li et al., 2024]. Traditional multilabel feature selection methods primarily focus on the internal correlations within the feature set and the label set. Although some methods attempt to consider the associations between features and labels, this consideration remains insufficient [Wang et al., 2021a]. For instance, linear decomposition methods such as Non-negative Matrix Factorization (NMF) may lead to the loss of nonlinear relationships within the data. This issue becomes more pronounced in real-world scenarios with complex dependencies. In the constructed composite diagram shown in Figure 1, indirect relationships between features and labels are established through the propagation of relevant nodes. Our method is specifically designed to focus on capturing these indirect relationships. To more comprehensively capture the nonlinear and indirect relationships between subsets of features and subsets of labels, we propose a novel multi-label feature selection method. The main contributions of this work are as follows:

• We propose a random walk strategy on a feature-label composite graph constructed using mutual information, which captures both direct and implicit indirect associations between features and labels, thereby facilitating a comprehensive representation of the high-dimensional structures within the data.
• By aligning the low-rank representations of similar samples in the feature space and label space, we ensure that the shared latent space after low-rank decomposition effectively captures the structural consistency between the two spaces.
• Extensive experiments conducted on seven datasets validate the effectiveness of the proposed method.

2 RelatedWork

In the field of multi-label feature selection, numerous methods have been proposed to capture the correlations between features and labels [Sun et al., 2021]. With the increasing dimensionality of data, the diversity of labels also rises. Based on the depth of consideration given to label correlations, these methods are typically categorized into three types [Liu et al., 2023], first-order strategies, second-order strategies, and high-order strategies.

First-order strategies address multi-label problems using single-label methods but ignore the correlations between labels [Lee and Kim, 2015; Lin et al., 2015]. Although this method simplifies the modeling process, it fails to capture label dependencies, making it challenging to identify key features within label relationships. Second-order strategies address this limitation to some extent by modeling pairwise relationships between labels [Xiong et al., 2021; Qian et al., 2022]. However, since label relationships often extend beyond simple pairwise connections, these methods only capture the associations between features and a subset of labels, falling short of comprehensively reflecting the complex dependencies between features and all labels.

In contrast, high-order strategies [Wu et al., 2020; Huang et al., 2016] go further by considering the correlations between features and all possible label subsets, thus providing a more comprehensive modeling of the complex dependencies among labels. However, these methods focus on uncovering the direct dependencies between variables and fail to effectively capture implicit indirect correlations, which limits their ability to characterize deep, latent relationships.

Manifold learning [Fan et al., 2021; Cohen et al., 2023] has been employed to ensure the consistency between feature correlation and label correlation. This method assumes that samples with similar features should have similar labels, thereby achieving alignment between feature and label similarity. The core idea is to uncover the intrinsic structure of high-dimensional data through its low-dimensional latent representations. [Tang et al., 2019] proposed a graph-based manifold regularization method to capture the manifold structure of the data, applying the resulting latent representations to unsupervised feature selection. However, these methods fail to adequately address the alignment problem between the lowdimensional representations of the feature space and the label space.

In recent years, random walk techniques have seen increasing exploration and application in the field of feature selection. The Random Walk Feature Selection (RWFS) method [Feng et al., 2017] is based on the Optimal Feature Selection (OPFS) technique, which identifies feature subsets and integrates random walk methods with predefined thresholds to filter out redundant features. The Pattern-Based Local Random Walk (PBLRW) method [Song et al., 2019] constructs local random walk models through feature combinations and assigns transition probabilities based on the strength of these combinations. However, the randomwalk operations in these methods remain limited to the feature space, neglecting label dependencies, and fail to fully leverage their capacity for capturing higher-order relationships.

3 The ProposedMethod

We propose a multi-label feature selection method based on Graph Random Walk and Structured Correlation Matrix Factorization (GRW-SCMF). By incorporating graph random walk, the method captures both the direct correlations and implicit indirect correlations between features and labels. Furthermore, in the shared low-dimensional representation, it aligns similar samples in the feature space and label space to ensure consistency. The framework is shown in Figure 2.

3.1 RandomWalk Graph

In this paper, we construct a composite graph G = (V,E), where the vertex set V consists of two types of vertices: feature vertices Vf and label vertices Vl. The edge set E includes the following three types of edges:

1. Feature-feature edges Eff ,
2. Label-label edges Ell,
3. Feature-label edges Efl.

The adjacency matrices of the feature graph Afeatures and the label graph Alabels are calculated using the Gaussian kernel as follows:

Here, ∥X:,i -X:,j∥2 and ∥Y:,i - Y:,j∥2 represent the Euclidean distances between features and labels, respectively, and σ is the scale parameter of the Gaussian kernel.

The association between features and labels is represented by the mutual information matrix MI, which is defined as follows:

where p(x, y) denotes the joint probability distribution of feature X and label Y , and p(x) and p(y) represent the marginal probability distributions of X and Y , respectively.

To construct the transition probability matrices Pfeatures, Plabels, and Plf (the transpose of which is Pfl), we normalize the adjacency matrices of the feature graph Afeatures and label graph Alabels, as well as the connection matrix MI between features and labels.

3.2 RandomWalkMethod

The random walk starts from a randomly selected feature vertex v ∈ Vf and updates its state according to the following rules:

1. When the current node is a feature node (v ∈ Vf ):
2. With a probability of pjump, it jumps to a label node u ∈ Vl. The target node is determined based on the transition probability Pfl(v, u), which is calculated as follows:

• Otherwise, with a probability of 1 - pjump, it jumps to another feature node u ∈ Vf . The target node is determined based on the transition probability Pfeatures(v, u), which is calculated as follows:

1. When the current node is a label node (v ∈ Vl):
2. With a probability of pjump, it jumps to a feature node u ∈ Vf . The target node is determined based on the transition probability Plf(v, u), which is calculated as

• Otherwise, with a probability of 1 - pjump, it jumps to another label node u ∈ Vl. The target node is determined based on the transition probability Plabels(v, u), which is calculated as follows:

3.3 Feature-Label Relationship Update Rule

Implicit indirect relationships refer to the potential high-order associations between feature nodes and label nodes that are transmitted through intermediate nodes (other features and labels). These relationships are difficult to capture using traditional linear decomposition methods. To address this issue, RWMI leverages random walks to dynamically generate interaction sequences between feature and label nodes, effectively capturing such indirect relationships.

Specifically, during each random walk, we record each pair of feature nodes f ∈ Vf and label nodes l ∈ Vl, and calculate their distance d(f, l) in the walk sequence, which represents the number of steps separating them. The association weight RW(f, l) is updated according to the following formula:

where decay factor is a distance decay factor that controls the influence of the number of steps on the weight, and MI(f, l) is the mutual information between feature f and label l, which mitigates uncertainties caused by randomness, ensuring that the results of the RW matrix are more accurate and robust.

Through multiple random walks, RW not only captures the direct associations between features and labels but also computes implicit indirect relationships via the intermediate nodes in the walk sequences. This process constructs a feature-label association matrix that represents high-order associations, which is further scaled to the [0, 1] range via Min-Max normalization.

The procedure is detailed in Algorithm 1.

3.4 Objective Function

In multi-label data, the diversity of labels may introduce inaccurate or noisy label information, making it prone to incorporating irrelevant and redundant information when directly utilizing the original feature and label matrices for feature selec-

Algorithm 1 Random Walk Mutual Information (RWMI)

Require: X (features), Y (labels), n walks, walk length, jump prob, decay factor

Ensure: Normalized RWMI matrix

• 1: Construct adjacency matrices Afeatures, Alabels fromX, Y .
• 2: Calculate and normalize mutual information matrix MI between X and Y .
• 3: Compute transition probability matrices: Pfeatures, Plabels, Pfeature to label, Plabel to feature.
• 4: Initialize RWMI matrix.
• 5: for i = 1 to n walks do
• 6: Start randomwalk from a node.
• 7: for j = 1 to walk length do
• 8: Move between feature and label nodes based on probabilities and jump prob.
• 9: end for
• 10: UpdateRWMI matrix using decay factor and steps between feature-label pairs, and normalize it afterward.
• 11: end for

tion. To address this issue, we learn a shared low-dimensional latent semantic space for both the feature and label spaces. This low-dimensional space matrix condenses the critical information from features and labels while effectively reducing the influence of redundancy and noise. The objective function can be written as:

The feature matrix X ∈ Rn×d represents the highdimensional feature space of the samples, while the multilabel matrix Y ∈ Rn×c describes the label distribution of the samples. To uncover the shared distribution structure between the feature space and the label space, we introduce a low-dimensional latent semantic matrix V ∈ Rn×k , which captures the low-dimensional shared representations of both spaces. The matrices Q ∈ Rk×d and B ∈ Rk×c are the lowdimensional representation coefficient matrices for features and labels, respectively, mapping the original data into the shared representation V . Specifically, matrix V encodes the embedding relationships of features and labels in k latent semantic clusters. By applying non-negative matrix factorization (NMF) on Y , the c labels can be effectively clustered, revealing the complex internal distribution structure of multilabel data.

The term ∥Rw -QT B∥2F introduced in the objective function (10) enhances the model's ability to capture the complex relationships between features and labels. Here, the matrix Rw is the feature-label implicit association matrix computed using the Random Walk Mutual Information (RWMI) method, which effectively captures indirect relations and latent dependencies in high-dimensional data. In contrast, QT B is the feature-label association matrix learned based on the low-dimensional shared semantic space. As it is derived from low-dimensional linear decomposition, it primarily captures linear relationships and direct associations. By combining the explicit modeling capability of linear decomposition with the implicit relationship mining power of random walks, this term significantly improves the model's ability to represent high-order nonlinear relationships between features and labels. Furthermore, this term ensures that the low-dimensional representation space preserves the manifold structure of the original high-dimensional data, aligning with the latest concepts in manifold learning, which posit that high-dimensional data often lie on a low-dimensional manifold.

This term can be regarded as an alignment constraint, aiming to ensure the consistency between the feature space and the label space in the low-dimensional representation. Specifically, XQT represents the low-dimensional mapping of features in the shared semantic space V , while YBT represents the low-dimensional mapping of labels in the same space V . Furthermore, to preserve the associations between features and labels, similar feature samples and label samples should be mapped to locations close to each other in the lowdimensional space. This ensures the learning of a common low-dimensional space that effectively captures the relationship between features and labels.

The Frobenius norm of V imposes a regularization constraint in the low-dimensional shared semantic space, reducing redundancy and unnecessary complexity, thereby enhancing the model's ability to capture important low-dimensional relationships between features and labels. Moreover, incorporating this term as a regularization on QT B effectively controls the model complexity and reduces the risk of overfitting. By smoothing the solution space, it further improves the generalization ability of the model. Additionally, computing the row-wise ℓ2 norm of QT B provides a measure of feature importance.

Thus, our final objective function is formulated as follows:

4 Solution Strategy

This section presents the optimization method for solving the proposed objective function.

4.1 Optimization Scheme

Because the objective function includes an l2,1-norm regularization term, which is non-smooth and cannot be directly solved, and is also non-convex with respect to the variables V , Q, and B, it presents a significant challenge [Boyd and Vandenberghe, 2004]. Theoretically, this is due to the fact that the Hessian matrix, composed of the second-order partial derivatives of the objective function, is not positive semi-definite. Therefore, to optimize the objective function, we have designed a relaxation update method based on the alternatingmultiplier-based scheme [Nie et al., 2010] to achieve an approximate local optimum of the objective function.

We use 2Tr(W T DW) to approximate ∥W∥2,1, where W = QT B. Here, D is a diagonal matrix whose elements are iteratively computed during the method's execution. The parameter c is introduced to mitigate perturbations in nondifferentiable problems. The elements of D are defined as:

To integrate non-negative constraint conditions into the objective function, we introduce Lagrangian multipliers ψ, φ, and µ to constrain V , Q, and B respectively. Specifically, ψ ∈ Rn×k + , φ ∈ Rk×d + , and µ ∈ Rk×c + . Consequently, the original function (14) is equivalent to the following function:

Transform the squared Frobenius norm into the form of a matrix trace:

We can obtain the following expressions by differentiating with respect to V , Q, and B:

By employing the Karush-Kuhn-Tucker (KKT) conditions for optimization, we derive the following set of equations:

In the case of multiple variables with constraints on each variable, we alternately update each variable to ensure that each optimization step adheres to the constraint conditions. We take the partial derivatives with respect to V , Q, and B respectively.

After obtaining each parameter of the objective function, we can rank all features of X in descending order based on the values of ∥(Q⊤B)i∥2 (for i = 1, . . . , d).

5 Experiments

5.1 Experimental Setup

Datasets. To validate the effectiveness of the proposed method under complex relationships, our experimental evaluation employs multi-label datasets from the MULAN library [Tsoumakas et al., 2011], including the web text datasets Arts, Business, Education, and Health. Additionally, the datasets encompass the Emotions dataset for music genres, the Flags dataset for image data, and the Yeast dataset for biological data. The Arts, Business, Education, and Health datasets feature a large number of distinct label combinations, reflecting complex underlying relationships with the features. Meanwhile, the Emotions, Flags, and Yeast datasets highlight characteristics from different domains. Table 1 summarizes the characteristics of the datasets used in the experiments.

Comparing Methods. We compare a broad and representative set of multi-label feature selection methods: (1) Statistical methods: PPT+MI [Doquire and Verleysen, 2011] and PPT+CHI [Read, 2008], which perform feature selection based on mutual information and χ2 statistics, respectively; (2) Latent representation learning: LRDG [Zhang et al., 2024], which incorporates dynamic graph constraints; (3) Label relevance-based methods: MIFS [Jian et al., 2016], which selects features in a low-dimensional space, and LRFS [Zhang et al., 2019], which leverages conditional mutual information to capture label relationships; (4) Sparse constraint-based methods: RALM-FS [Cai et al., 2013], which employs the l2,0-norm for sparse solutions; (5) Latent shared structure-based methods: SSFS [Gao et al., 2023], which models the shared latent structure between features and labels.

Evaluating Methods. Analogous to method [Hu et al., 2020], we select the top 20% of ranked features from each dataset, with a step size of 1% (for the Flags dataset, all features were used as it only has 19 features). Three commonly used classifiers were employed: Linear SVM, k-Nearest Neighbors (k=3), and MLkNN (k=10). Specifically, both the Linear SVM and kNN classifiers provided Micro-F1 and Macro-F1 scores, while the MLkNN classifier yields Hamming Loss (HL) and Zero-One Loss (ZOL) [Kou et al., 2023; Li et al., 2023].

Parameter Selection. In this method, we employ Bayesian optimization to determine the optimal combination of parameters. The search range for the regularization parameters is set to {0.01, 0.1, 0.3, 0.5, 0.7, 0.9, 1.0}. For the randomwalk method, the range for nwalks is set to {100, 1000, 10000}, the range for walk length is set to {10, 20, 30}, and the ranges for jump prob and decay factor are both set to {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9}.

5.2 Experimental Results

Feature Selection Performance. We selected seven benchmark multi-label datasets for our experiments and compared our method with seven state-of-the-art multi-label feature selection methods. The experimental results are presented in the tables, where our method outperforms the others. In Tables 2 and 3, the best-performing method for each dataset is highlighted in bold. Clearly, our method is not limited to any specific type of dataset and demonstrates outstanding performance across image, music, text, and biological datasets. Except for the Macro-F1 score of the 3NN classifier on the Health dataset, where our method slightly underperforms compared to the RALM-FS method, our method outperforms the seven other methods in all other scenarios. In Figure 3, we present the performance of different methods on a specific dataset. From the early stages, the proposed method demonstrates its ability to select highly discriminative features. The outstanding results in HL and ZOL metrics validate its effectiveness in capturing both direct and indirect relationships between features and labels. Furthermore, the superior performance in Macro-F1 and Micro-F1 scores clearly highlights the efficacy of low-dimensional alignment.

Parameter Analysis. In our proposed method, there exist five weight parameters, α , β , γ , δ and ϵ, that influence performance outcomes. The Figure 4 illustrates how these five parameters affect the Micro-F1 scores computed using SVM on the Arts dataset. We initially divided the dataset into seven equal parts and then individually adjusted each parameter while keeping the other parameters fixed at 0.5 [Jian et al., 2018], conducting a grid search over a predefined range. It is evident that the results exhibit an upward trend and become increasingly stable as the number of selected features increases. However, due to different parameter configurations, slight variations may occur under the same number of selected features, leading to minor discrepancies in the results. Therefore, we can infer that our method demonstrates stability, provided there is a sufficiently large number of instances.

Ablation Study. To evaluate the effectiveness of the newly introduced components, we conducted ablation experiments on the Emotions, Yeast, and Arts datasets, considering various combinations of these components, as shown in Table 4. In these experiments, the random walk component (RW) captures implicit indirect relationships through randomwalk, while the feature-label alignment component (FLA) aligns features and labels in a low-dimensional common space. The results demonstrate that removing either component adversely affects the SVM's Micro-F1 performance, underscoring the importance of both introduced components. Therefore, it can be inferred that the contribution of each component is crucial for achieving optimal model performance.

Convergence. Figure 5 illustrates the convergence of our method on the Arts and Business datasets. The chosen stopping criterion is: |zt - zt-1| < c or ∣∣∣ zt-zt-1 zt-1 ∣∣∣ < c. The Xaxis represents the number of iterations, and the Y-axis is similar to the stopping criterion but uses absolute values. It is evident from the figure that the optimization process converges quickly.

6 Conclusion

We propose a random walk method based on a feature-label composite graph and incorporate it into a multi-label feature selection method. Through random walks on the featurelabel composite graph, we capture direct and indirect correlation between features and labels. Additionally, we leverage low-dimensional representation coefficients to align the low-dimensional variable space while preserving the manifold structure. Experimental results demonstrate the effectiveness and robustness of our method.

Acknowledgments

This work was supported by the Science Foundation of Jilin Province of China under Grant YDZJ202501ZYTS286, and in part by Changchun Science and Technology Bureau Project under Grant 23YQ05.