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

Wanfu Gao, Jun Gao, Qingqi Han, Hanlin Pan, Kunpeng Liu

TL;DR

This paper introduces GRW-SCMF, a novel multi-label feature selection method that leverages graph random walks to capture complex, implicit relationships between features and labels. By aligning feature and label spaces in a shared low-dimensional representation, it achieves superior performance in identifying relevant features for multi-label classification tasks.

What Problem Does This Paper Address?

In the era of big data, datasets often exhibit a high number of features and multiple labels per instance. This complexity makes it challenging to select the most informative features for classification. Traditional feature selection methods often struggle with:

  • Implicit and Nonlinear Relationships: They tend to focus on direct, linear associations between features and labels, missing deeper, indirect, and nonlinear connections that are crucial for accurate prediction.
  • Feature-Label Space Misalignment: Existing approaches often treat the feature space and label space independently, leading to a disconnect that hinders effective learning.
  • Scalability: High dimensionality can lead to computational bottlenecks and increased storage requirements.

This paper aims to address these challenges by proposing a method that can effectively capture complex feature-label dependencies and align the feature and label spaces in a unified manner.

Methods

The proposed method, GRW-SCMF (Graph Random Walk with Structured Correlation Matrix Factorization), combines two key innovations:

  • Graph Random Walk on a Composite Graph: A novel graph is constructed that includes feature nodes, label nodes, and edges representing feature-feature, label-label, and feature-label relationships. A random walk is performed on this graph, allowing information to propagate and capture both direct and indirect associations between features and labels. This is achieved by dynamically generating interaction sequences and weighting them based on distance and mutual information.
  • Feature-Label Space Alignment via Low-Rank Representation: The method employs a low-rank matrix factorization approach to learn a shared low-dimensional latent semantic space. This space is designed to represent both features and labels, ensuring that samples with similar features also have similar labels. The objective function is formulated to simultaneously reconstruct the original data, capture the implicit relationships learned from the random walk, and align the feature and label representations in the shared space. Regularization terms are used to control model complexity and enhance generalization.

Datasets

The authors evaluated their method on seven benchmark multi-label datasets:

  • Web Text Datasets: Arts, Business, Education, Health (from the MULAN library)
  • Other Domains: Emotions (music genres), Flags (image data), Yeast (biological data)

These datasets were chosen to represent a variety of domains and complexities, including those with a large number of distinct label combinations.

Key Insights and Ideas

  • Random Walks as a Bridge: The random walk on the composite graph is a powerful mechanism for uncovering "hidden" relationships between features and labels that linear methods would miss. It allows for the propagation of information across different types of nodes, effectively bridging the gap between feature and label spaces.
  • Unified Representation is Key: By learning a shared low-dimensional space for both features and labels, the method ensures that the selected features are relevant not just to individual labels but also to the overall label structure. This alignment is crucial for improving multi-label classification performance.
  • Combining Strengths: The GRW-SCMF method effectively combines the strengths of random walks (capturing implicit, nonlinear relationships) with those of low-rank matrix factorization (learning structured representations and aligning spaces). This synergy leads to a more robust and comprehensive feature selection approach.

Key Results

The paper reports strong performance across various datasets and evaluation metrics:

  • Superior Classification Performance: GRW-SCMF consistently outperformed seven state-of-the-art multi-label feature selection methods on both Micro-F₁ and Macro-F₁ scores when evaluated using SVM and 3NN classifiers.
  • Robustness: The method demonstrated outstanding performance across diverse datasets, including image, music, text, and biological data, indicating its generalizability.
  • Effectiveness of Components: Ablation studies confirmed that both the random walk component and the feature-label alignment component are critical for achieving optimal performance.
  • Fast Convergence: The optimization process for the proposed objective function was shown to converge quickly.

Limitations and Future Work

  • Parameter Sensitivity: While the method shows stability with a sufficient number of instances, parameter sensitivity was observed, and Bayesian optimization was used to find optimal settings. Further research could explore more adaptive parameter tuning strategies.
  • Computational Complexity: While the method aims to reduce computational time through feature selection, the random walk and matrix factorization steps can still be computationally intensive for extremely large datasets.
  • Future Directions: The authors suggest exploring the application of their method to other machine learning tasks and investigating more advanced graph construction techniques.

Summary updated

Abstract

The rapid growth in feature dimension may introduce implicit associations between features and labels in multi-label datasets, making the relationships between features and labels increasingly complex. Moreover, existing methods often adopt low-dimensional linear decomposition to explore the associations between features and labels. However, linear decomposition struggles to capture complex nonlinear associations and may lead to misalignment between the feature space and the label space. To address these two critical challenges, we propose innovative solutions. First, we design a random walk graph that integrates feature-feature, label-label, and feature-label relationships to accurately capture nonlinear and implicit indirect associations, while optimizing the latent representations of associations between features and labels after low-rank decomposition. Second, we align the variable spaces by leveraging low-dimensional representation coefficients, while preserving the manifold structure between the original high-dimensional multi-label data and the low-dimensional representation space. Extensive experiments and ablation studies conducted on seven benchmark datasets and three representative datasets using various evaluation metrics demonstrate the superiority of the proposed method\footnote{Code: https://github.com/Heilong623/-GRW-}.
BibTeX
@inproceedings{gao2025graph,
  author = {Wanfu Gao and Jun Gao and Qingqi Han and Hanlin Pan and Kunpeng Liu},
  title = {{Graph Random Walk with Feature-Label Space Alignment: A Multi-Label Feature Selection Method}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/575},
}
Figure