SEHFS: Structural Entropy-Guided High-Order Correlation Learning for Multi-View Multi-Label Feature Selection

This paper proposes SEHFS, a novel multi-view multi-label feature selection method that leverages structural entropy to construct encoding trees for capturing high-order feature correlations and employs a hybrid information-theoretic and matrix-based framework to overcome local optima and eliminate redundancy.

The Gist

Imagine you are trying to organize a massive, chaotic library. But this isn't just any library; it's a Multi-View Multi-Label library.

Here's what that means in plain English:

• Multi-View: You have the same book described in five different languages (English, French, Chinese, etc.). Each language gives you a slightly different perspective on the story.
• Multi-Label: A single book isn't just "Science Fiction." It might be "Science Fiction," "Space Opera," "Philosophy," and "Romance" all at once.
• The Problem: The library is huge. There are millions of books (features), and many of them are just copies of each other or say the same thing in different ways (redundancy). You need to pick the best few books to represent the whole collection without losing the story.

Existing methods for organizing this library are like a librarian who only looks at two books at a time. They ask, "Does Book A relate to Book B?" If yes, they keep them together. But they miss the bigger picture: "Do Books A, B, and C all tell a specific story together that none of them could tell alone?"

This is where the new method, SEHFS, comes in.

The Core Idea: The "Tree of Secrets"

The authors propose a new way to organize the library using a concept called Structural Entropy. Let's break down the two main tricks they use:

1. The "Encoding Tree" (Finding the Hidden Patterns)

Imagine you have a group of friends.

• Old Method (Mutual Information): You ask, "Who knows who?" You find that Alice knows Bob, and Bob knows Charlie. You stop there. You miss that Alice, Bob, and Charlie are actually part of a secret club that only makes sense when you look at all three of them together.
• SEHFS Method (Structural Entropy): Instead of just looking at pairs, SEHFS builds a family tree (an encoding tree) of the data.
  • It looks at the whole group and asks, "If I had to explain this whole group to someone, what is the most efficient way to do it?"
  • If three features (books) are essentially saying the exact same thing (high redundancy), SEHFS puts them in the same branch of the tree. It treats them as one unit.
  • If features are unique and add new value, it keeps them on separate branches.

The Analogy: Think of a noisy party.

• Old methods try to find pairs of people talking.
• SEHFS realizes that a whole corner of the room is just repeating the same joke. It groups that whole corner into a single "cluster" and silences the redundancy, while keeping the unique conversations happening elsewhere. This allows it to understand high-order correlations—complex relationships that only exist when you look at the whole group, not just pairs.

2. The "Global View" (Balancing Consensus and Uniqueness)

Now, remember the library has books in five different languages (Views).

• The Challenge: If you just mix all the languages together, you get a mess. If you treat them completely separately, you lose the common story.
• The SEHFS Solution: They build a Global View Matrix. Imagine a translator who creates a "Master Summary" of the story.
  • Shared Semantic Matrix: This is the "Common Ground." It captures what all languages agree on (the core truth of the story).
  • View-Specific Matrices: This captures the "Unique Flavor." It remembers that the French version has a specific poetic nuance the English version missed.

SEHFS uses a mathematical framework to balance these two. It ensures the "Master Summary" is accurate (Consistency) while making sure no unique flavor from any specific language is lost (Complementarity).

Why is this better?

1. Avoiding Local Traps: Old methods often get stuck in "local optima." Imagine trying to find the highest peak in a foggy mountain range. Old methods might climb a small hill and think, "Great, I'm at the top!" SEHFS uses the "Tree" structure to see the whole mountain range, ensuring it finds the actual highest peak (Global Optimum).
2. Handling Complexity: Real-world data is messy. Things are connected in complex, non-linear ways (like a web, not a straight line). SEHFS is designed to untangle these complex webs, whereas older methods try to force them into straight lines.

The Results

The authors tested this on eight different "libraries" (datasets) ranging from gene analysis to image recognition.

• The Outcome: SEHFS consistently picked the best "books" (features) to represent the data.
• The Proof: In a head-to-head race against seven other top methods, SEHFS won almost every time, especially in the most complex, large-scale scenarios. It was better at predicting labels (like correctly tagging a photo as "Beach," "Sunset," and "Vacation" all at once) and less likely to make mistakes.

Summary

SEHFS is like a super-intelligent librarian who:

1. Doesn't just look at pairs of books, but understands the entire story of a group of books (High-Order Correlation).
2. Groups repetitive books together to save space (Redundancy Elimination).
3. Creates a perfect summary that respects both the common story and the unique details of every language version (Global/Local Balance).

It's a smarter, more efficient way to cut through the noise and find the signal in our increasingly complex, multi-dimensional world.

Technical Summary

1. Problem Statement

The paper addresses the challenges inherent in Multi-View Multi-Label Feature Selection (MVMLFS). While Multi-View Multi-Label (MVML) learning is crucial for real-world scenarios (e.g., medical imaging, image classification), existing methods face two primary limitations:

1. Inability to Capture High-Order Correlations: Most existing information-theoretic methods rely on Mutual Information (MI), which is fundamentally limited to capturing pairwise (low-order) relationships. They fail to model complex, high-order structural dependencies where features interact in groups (synergy or redundancy) that cannot be explained by pairwise interactions alone.
2. Optimization Limitations: Traditional information-theoretic approaches often rely on heuristic search strategies, making them prone to converging to local optima rather than finding the global optimal feature set. Additionally, they struggle to balance the consistency (shared information) and complementarity (unique information) across different views effectively.

2. Methodology: SEHFS

The authors propose SEHFS (Structural Entropy Guided High-Order Correlation Learning), a novel framework that integrates information theory with matrix factorization. The method consists of two core components:

A. Structural Entropy-Guided Feature Selection

Instead of using pairwise Mutual Information, SEHFS utilizes Structural Entropy to model the feature graph.

• Concept: The feature graph is converted into a structural-entropy-minimizing encoding tree.
• Mechanism:
  • Features with strong high-order redundancy are grouped into a single cluster (node) within the encoding tree.
  • Inter-cluster correlations are minimized.
  • This process quantifies the "information cost" of high-order dependencies, effectively learning correlations beyond pairwise interactions.
• Theoretical Proof: The paper demonstrates theoretically that minimizing structural entropy yields a tighter bound on joint entropy than second-order approximations (standard MI) in two extreme scenarios:
  • Maximum Synergy (XOR case): Where pairwise MI is zero, but high-order dependency exists. Structural entropy captures this; MI fails.
  • Maximum Redundancy: Where features are identical. Structural entropy correctly compresses them into one cluster; MI-based approximations often over-correct or fail.
• Implementation: An assignment matrix $W$ is learned to map features to label clusters, serving as the feature selection matrix.

B. Information-Matrix Fusion Framework

To address the multi-view complexity and local optima issues, SEHFS adopts a fusion framework:

1. Global View Matrix Reconstruction: The method reconstructs a global view matrix ($X_f$) by integrating:
   • Shared Semantic Matrix ($S$): Captures consistency across views (common structure).
   • View-Specific Contribution Matrices ($H_v$): Captures complementarity (unique information per view).
2. Regularization:
   • Graph Laplacian Regularization: Ensures the shared semantic matrix aligns with the label matrix structure.
   • Optimization: The framework balances global optimization (via matrix reconstruction) and local optimization (via feature selection), mitigating the risk of local optima common in pure heuristic searches.

C. Optimization Algorithm

The objective function is non-convex and involves multiple variables ($X_f, W, S, H_v, \alpha_v$). The authors propose an iterative alternating optimization algorithm (Algorithm 1) using multiplicative gradient descent and projected gradient descent to update variables until convergence.

3. Key Contributions

1. High-Order Correlation Learning: Introduction of a structural entropy-guided regularization term that successfully learns high-order feature correlations and eliminates redundancy, overcoming the pairwise limitation of traditional MI-based methods.
2. Novel Fusion Framework: Development of a framework that fuses information theory (structural entropy) with matrix methods (semantic reconstruction). This balances global consistency and local complementarity while improving optimization stability.
3. Theoretical and Empirical Validation:
   • Theoretical proof showing structural entropy's superiority over low-order approximations in synergy and redundancy scenarios.
   • An effective solution to the alternative optimization problem with proven convergence.

4. Experimental Results

The method was evaluated on eight datasets from various domains (e.g., EMOTIONS, YEAST, VOC07, MIRFlickr, SCENE, OBJECT, Corel5K, IAPRTC12) and compared against seven state-of-the-art baselines (including DHLI, GRAFS, MSFS, SRFS, etc.).

• Performance Metrics: Average Precision (AP), Coverage (Cov), Hamming Loss (HL), and Ranking Loss (RL).
• Key Findings:
  • Superiority: SEHFS achieved the best performance in 87.5% of the total evaluation cases across all datasets and metrics.
  • Hamming Loss: It achieved a 100% best-rate on the Hamming Loss metric.
  • Scalability: SEHFS showed significant advantages on large-scale, multi-view datasets (e.g., SCENE, Corel5K), outperforming baselines by an average of 7.24%.
  • Ablation Studies: Removing the structural entropy term (SEHFS-W) caused a ~9.7% drop in performance, confirming its critical role. Similarly, removing the shared semantic matrix (SEHFS-S) or graph Laplacian (SEHFS-L) significantly degraded results, validating the necessity of the fusion framework.
  • Convergence: The objective function was shown to decrease monotonically and converge rapidly (within ~50 iterations) across datasets.

5. Significance

• Paradigm Shift: The paper moves feature selection from a reliance on pairwise statistics (Mutual Information) to a structural, high-order perspective (Structural Entropy), offering a more robust way to handle complex, nonlinear data relationships.
• Robustness: By balancing global matrix reconstruction with local feature selection, the method is less prone to local optima and better suited for noisy, high-dimensional multi-view data.
• Practical Impact: The method provides a more effective tool for applications like medical image analysis and multimedia retrieval, where features often exhibit complex, group-based dependencies that traditional methods miss.

In conclusion, SEHFS represents a significant advancement in MVMLFS by theoretically and empirically demonstrating that structural entropy is a superior measure for capturing high-order feature correlations, leading to more accurate and robust feature selection.