Label Confidence Recovery with High-order Label Correlation in Partial Multi-label Learning

1 Introduction

Multi-label learning addresses the tasks where each training instance can be associated with multiple class labels [Zhang and Zhou, 2014; Zhang and Wu, 2015]. Unfortunately, in many real-world scenarios, it is extremely challenging to annotate precise supervision due to various reasons such as limitations in annotator expertise or the uncertainty of crowdsourcing. Among them, one common scenario is that each instance is annotated with a candidate label set containing relevant labels but also irrelevant ones. To handle this, the emergent task, namely partial multi-label learning (PML), has recently attracted much more attention in the community [Xie and Huang, 2018; Fang and Zhang, 2019; Zhang and Fang, 2021].

∗Corresponding author

Recently, many PML methods have been proposed. One basic problem of PML is how to disambiguate candidate labels while training a multi-label classifier. Roughly, existing methods can be broadly categorized by their disambiguation strategies. Some methods treat each label independently and perform disambiguation by estimating label confidence from candidate annotations or exploiting structural information in the feature space [Zhang and Fang, 2021; Xie et al., 2021; Sun et al., 2019; Yu et al., 2018]. For example, PARTICLE [Zhang and Fang, 2021] estimates labeling confidence via iterative label propagation, and PML-MD [Xie et al., 2021] adaptively learns confidence weights through meta-learning. More recently, many methods recognize that label correlations are inherent in multi-label data and can provide valuable structural signals for disambiguation. For example, GLC [Sun et al., 2022] captures pairwise label correlations through low-rank representation and manifold regularization, while PLAIN [Wang et al., 2023] constructs a label correlation graph to propagate information across label pairs. These pairwise correlation-based methods have demonstrated that exploiting label correlations is valuable for PML disambiguation.

Labels in multi-label data often exhibit joint dependencies among three or more labels instead of pairwise relationships, which are referred to as high-order label correlations [Read et al., 2011; Zhang and Zhang, 2010]. In real-world scenarios, labels frequently co-occur in semantic groups, such as beach, ocean, and sunset in image annotation, and such collective patterns are difficult to capture through pairwise modeling alone. Moreover, high-order correlations offer distinct advantages for disambiguation in partial settings. Since noise labels are introduced randomly, the likelihood of them forming consistent high-order correlations diminishes rapidly as the order increases, while ground-truth label correlations maintain stable co-occurrence patterns, resulting in an increasingly pronounced gap between them. As illustrated in Figure 1, the relative frequency gap between ground-truth and noise combinations becomes more pronounced as the order increases, confirming that high-order patterns provide stronger disambiguation signals than pairwise ones.

In this paper, to exploit this property, we propose REHCPML, a novel PML framework that leverages high-order label correlations for effective disambiguation. The framework operates in two phases. First, we mine frequent co-occurrences to identify global high-order label correlations. Second, we perform high-order disambiguation by selecting semantically relevant correlations and propagating their structural evidence to constituent labels for confidence refinement. Specifically, for each instance, we compute semantic alignment between the instance and each identified correlation, employ differentiable Gumbel-Softmax [Jang et al., 2017] pruning to select relevant correlations, and broadcast their accumulated evidence to individual labels. Labels supported by multiple relevant correlations receive amplified confidence for disambiguation.

In summary, the main contributions are as follows:

• We propose to exploit high-order label correlations for PML disambiguation by mining frequent co-occurrence patterns.
• We design a differentiable pruning mechanism to select instance-relevant correlations and broadcast their structural evidence to constituent labels for confidence refinement.
• Extensive experiments on both real-world PML and UCI multi-label datasets demonstrate the effectiveness of the proposed method.

2 RelatedWork

In this section, we briefly review the most relevant works on PML. Existing methods can be broadly categorized into two main paradigms according to their optimization strategies: two-stage methods and unified methods.

Two-stage methods decompose the PML problem into sequential stages of label disambiguation followed by classifier training [Xie and Huang, 2018; Fang and Zhang, 2019; Zhang and Fang, 2021]. Confidence-based disambiguation strategies estimate the relevance of each candidate label before model training. For example, PARTICLE [Zhang and Fang, 2021] develops a probabilistic model that iteratively updates label confidences through expectation-maximization. PML-LRS [Sun et al., 2019] utilizes low-rank and sparse decomposition to recover ground-truth label matrices from noisy candidate sets. Other feature-induced methods [Yu et al., 2018; Xu et al., 2024] leverage instance features to guide disambiguation. Meta-learning strategies have also been introduced, as exemplified by PML-MD [Xie et al., 2021] which adaptively estimates confidences using meta-learning techniques. Other methods comprise multi-subspace representation [Li et al., 2020], self-representation models [Lyu et al., 2023], label distribution recovery [Xu et al., 2020; Xu et al., 2021; Lyu et al., 2020; Kou et al., 2025], and noisy label identification [Xie and Huang, 2021; Lyu et al., 2021].

Unified methods attempt joint optimization to enable mutual reinforcement between confidence estimation and classifier training [Wang et al., 2019; Li and Wang, 2020; Yan et al., 2021]. Progressive enhancement methods iteratively refine pseudo-label distributions through alternating optimization [Xu et al., 2021]. Alternative paradigms include adversarial training [Yan and Guo, 2021], mutual information maximization [Gong et al., 2021], and self-distillation mechanisms [Xu et al., 2022; Gong et al., 2022]. Recently, methods exploiting label correlations have gained prominence [Zhao et al., 2022; Li et al., 2022; Kou et al., 2024]. For example, WPML3CP [Li et al., 2024] captures label correlations from both measuring and modeling perspectives by employing Wasserstein distance. GLC [Sun et al., 2022] integrates global and local label correlation through low-rank representation and label manifold regularization. Recently, graph-based methods [Chen et al., 2020; Wang et al., 2023; Hang and Zhang, 2023; He et al., 2019] have also emerged as effective paradigms, and multi-view methods [Chen et al., 2020; Wu et al., 2020; Liu et al., 2024; Wen et al., 2024; Sun et al., 2021] have been developed to handle scenarios with multiple feature representations.

Despite considerable progress, existing PML methods primarily focus on pairwise label correlations for disambiguation. However, we observe that high-order label correlations can provide even stronger disambiguation evidence in partial settings. Motivated by this, we propose to model high-order label correlations and design a broadcasting mechanism that propagates structural evidence from high-order patterns to individual labels for effective disambiguation.

3 The ProposedMethod

In this section, we introduce the proposed REHC-PML method.

Task definition. Formally, given a training set D = (xi, Si)ni=1 with features xi ∈ Rd and candidate label sets Si ⊆ {1, . . . , l}, the unobserved ground-truth labels Y ∗ i ⊆ {1, . . . , l} satisfy Y ∗ i ⊆ Si for all i. The objective of partial multi-label learning is to learn a predictor f : Rd → [0, 1]l fromD that correctly recovers the labels for unseen instances.

3.1 Overview of REHC-PML

As established in Section 1, high-order label correlations offer superior disambiguation evidence: ground-truth correlations manifest as frequent co-occurrences across candidate sets, while noise-induced patterns remain sparse. To exploit this property, we propose REHC-PML. As illustrated in Algorithm 1, the framework operates in two phases. In the first phase, we mine frequent high-order co-occurrences from candidate sets to identify global high-order label correlations. In the second phase, we adopt a self-training strategy that iteratively performs disambiguation and trains the classifier.

3.2 Global High-Order Correlations Construction

In the first phase, we construct a global set K of highorder label correlations by mining frequent co-occurrence patterns from candidate sets. The intuition is that when multiple ground-truth labels share correlations, they co-occur frequently across candidate sets, while random noise generates sporadic combinations. By identifying frequently co-occurring labels, we can capture potential high-order label correlations for disambiguation.

We begin by enumerating all possible label co-occurrences up to a maximum order pmax. Given the candidate label set Si for instance xi, we enumerate all label subsets

where σ denotes a potential high-order label correlation and |σ| denotes the number of labels involved (the order of the correlation [Huang et al., 2017; Zhang and Zhang, 2010]).

Then, we aggregate these correlations across all instances and compute the global frequency for each unique correlation

where I(·) is the indicator function. This frequency measures how often the label subset σ appears across candidate sets. High frequency indicates that the labels in σ consistently cooccur, suggesting they may share a ground-truth high-order correlation.

To focus on recurrent co-occurrence patterns and reduce computational complexity, we retain only the most frequent label subsets for each order. For each order p ∈ {1, . . . , pmax}, we select the top-Kp label subsets with the highest frequencies. This filtering step prunes extremely rare correlations while preserving more frequent ones. The result is a global set of high-order label correlations

where M = ∑pmax p=1 Kp denotes the total number of retained correlations. Each σj ∈ K represents a high-order label correlation identified through frequent co-occurrence, serving as potential structural evidence for disambiguation.

3.3 Self-Training with High-Order Propagation

In the second phase, we adopt a self-training strategy to optimize the framework, which iteratively generates pseudo-labels and trains the classifier on these refined targets. The key challenge lies in how to generate high-quality pseudo-labels that effectively distinguish ground-truth labels from noise. To this end, we design a high-order guided propagation mechanism that leverages the structural evidence from the global set of high-order label correlations K to refine label confidence.

High-Order Guided Pseudo-Label Generation

Although the global set K captures high-order label correlations through frequent co-occurrence patterns, not all correlations in K are relevant to every instance. We design a highorder guided propagation mechanism that dynamically selects instance-relevant correlations and broadcasts their structural evidence to boost the confidence of constituent labels.

Semantic Relevance Computation. To determine which correlations σj ∈ K are relevant to a instance xi, we compute a relevance score measuring their semantic alignment as

Algorithm 1 Training Procedure of REHC-PML

Input: Training set D = {(xi, Si)}ni=1, max order pmax, top-K thresholds {Kp}pmax p=1 , self-training probability ρ, confidence threshold θ, number of epochs T Output: Trained classifier f 1: 2: // Phase 1: Construct Global High-Order Correlations 3: for i = 1 to n do 4: Enumerate co-occurrences Ki via Eq.(1) 5: end for 6: Compute frequencies freq(σ) for all unique σ via Eq.(2) 7: for p = 1 to pmax do 8: Retain top-Kp frequent order-p correlations 9: end for 10: Construct global set K = {σ1, . . . , σM} 11: Build membership matrix C ∈ {0, 1}M×l 12: 13: // Phase 2: Self-Training with High-Order Propagation 14: Initialize classifier f, projection network g, label embeddings E, auxiliary network h 15: for t = 1 to T do 16: for each mini-batch B ⊂ D do 17: Compute correlation representations {hσj }Mj=1 via Eq.(5) 18: for each (xi, Si) ∈ B do 19: Compute relevance scores {si,j}Mj=1 via Eq.(4) 20: Generate pruning mask mi via Eq.(6) 21: Compute structural support vi =miC 22: Refine label confidence {˜ yi,k}lk=1 via Eq.(8) 23: end for 24: if rand() < ρ then 25: Generate pseudo-labels ˆ Yi,k via Eq.(9) 26: Compute loss L via Eq.(10) with pseudo-labels 27: else 28: Compute loss L via Eq.(10) with candidate labels only 29: end if 30: Update all parameters via gradient descent on L 31: end for 32: end for 33: return Trained classifier f

where g(xi) ∈ Rde is the instance representation obtained via a non-linear projection network g : Rd → Rde (implemented as a multi-layer perceptron) [Bengio et al., 2013], de denotes the embedding dimension, and hσj ∈ Rde is the correlation representation. The representation of σj is computed as a weighted sum of its constituent label embeddings as

where E ∈ Rl×de is a learnable label embedding matrix and fattn : Rde → R is a learned attention function [Vaswani et al., 2017] that identifies the most representative labels within each correlation. A high relevance score indicates that the high-order correlation represented by σj strongly correlates with the semantic content of the instance.

Differentiable Correlation Pruning. Based on the relevance scores, we prune irrelevant correlations from K to derive an instance-specific subset Ki ⊆ K. To implement this pruning in a differentiable manner, we employ the GumbelSoftmax relaxation [Jang et al., 2017; Maddison et al., 2017]

as a learnable gating mechanism. The pruning mask mi ∈ {0, 1}M is generated as

where ς(·) denotes the sigmoid function, ϵj = -log(-log(uj)) with uj ∼ Uniform(0, 1) denotes the Gumbel noise, τ > 0 is the temperature parameter, and STE(·) denotes the Straight-Through Estimator that enables gradient flow through the discrete sampling. Here mi,j = 1 indicates that correlation σj is selected for instance i, while mi,j = 0 signifies that the correlation is pruned. This effectively reduces K to a sparse, instance-adaptive subset of relevant correlations.

Correlation-to-Label Broadcasting. With the pruning mask mi, we propagate the retained high-order correlations to individual labels for confidence refinement. Intuitively, if a label is contained in multiple retained correlations, it receives stronger support and is more likely to be a ground-truth label. To quantify this support, we compute a structural vote vector vi ∈ Rl , where vi,k counts how many retained correlations contain label k, representing the accumulated structural evidence from high-order label correlations as

where C ∈ {0, 1}M×l is a composition matrix encoding membership relationships, with Cj,k = 1 if label k ∈ σj and 0 otherwise.

Then, we use this structural signal to refine the label confidence. Specifically, we combine vi with a base confidence ˆ ybase i,k estimated by an auxiliary network from instance features as follows

where γ controls the activation threshold, and β controls the boosting intensity. This formulation ensures that only labels supported by sufficient retained combinations (i.e., vi,k > γ) receive meaningful amplification, effectively distinguishing ground-truth labels from noise.

Classifier Training with Pseudo-Labels

The refined confidence scores are converted to hard pseudolabels according to

where θ is the confidence threshold and I(k ∈ Si) ensures that the pseudo-labels remain within the candidate set. The classifier is then trained to align with these refined targets.

The classification loss L combines consistency with candidate labels and alignment with pseudo-labels as

where f(xi)k denotes the classifier output for label k, and λ balances the two terms. To balance optimization stability and computational efficiency, the self-training phase (i.e., including the pseudo-label term) is stochastically activated with probability ρ at each iteration. The complete training procedure is summarized in Algorithm 1.

4 Experiments

In this section, we conduct comprehensive experiments to evaluate the effectiveness of the proposed REHC-PML method.

4.1 Experimental Settings

Datasets. We evaluate REHC-PML on six real-world PML datasets and eight UCI multi-label datasets. The realworld datasets include mirflickr, music emotion, music style, YeastBP, YeastCC, and YeastMF, which inherently contain candidate label annotations from practical scenarios such as image annotation and biological function prediction. For the UCI multi-label datasets, we include bibtex, bookmarks, bow-train, computers, delicious, enron, entertainment, and nuswide. Detailed characteristics of all datasets are summarized in Table 1.

To simulate the partial multi-label learning scenario on UCI datasets, we construct candidate label sets by augmenting the ground-truth labels with randomly sampled irrelevant labels following the standard protocol [Zhang and Fang, 2021; Xie et al., 2021]. Specifically, for each instance xi, we add m% · ∥y∗ i ∥0 irrelevant labels to the ground-truth label set y∗ i to form the candidate label set Si, where m ∈ {50, 100, 150} controls the noise ratio. All experiments are conducted with 5-fold cross-validation, and we report the mean and standard deviation across folds.

Baseline Methods. We compare REHC-PML against nine state-of-the-art PML methods covering both two-stage and unified paradigms: PARTICLE [Zhang and Fang, 2021], PML-NI [Xie and Huang, 2021], PML-MD [Xie et al., 2021], GLC [Sun et al., 2022], PAMB [Liu et al., 2023], PLAIN [Wang et al., 2023], PARD [Hang and Zhang, 2023], WPML3CP [Li et al., 2024], and PML-FSMIR [Gao et al., 2025]. For fair comparison, all baseline methods are implemented using their publicly available code with recommended hyperparameter settings. Detailed descriptions of baseline methods are provided in the Appendix A1 .

EvaluationMetrics. Following standard practice in multilabel learning [Zhang and Zhou, 2014; Liu et al., 2021], we adopt five widely-used evaluation metrics: Average Precision (AP), Coverage Error (CE), Hamming Loss (HL), One Error (OE), and Ranking Loss (RL) [F¨urnkranz et al., 2008]. The symbols ↑ and ↓ indicate that larger and smaller values correspond to better performance, respectively.

4.2 Results on Real-world Datasets

Table 2 presents the experimental results on six real-world PML datasets. The best performance is highlighted in boldface. We observe that REHC-PML consistently achieves superior or competitive performance across all datasets and evaluation metrics. Specifically, REHC-PML achieves the best Average Precision on five out of six datasets, with notable improvements on mirflickr, YeastBP, and YeastMF compared to other baseline methods. The only exception is the music emotion dataset, where PLAIN performs slightly better. These results indicate that modeling high-order label correlations through frequent co-occurrence mining effectively captures the inherent structural patterns in candidate label sets, leading to more accurate label disambiguation. In terms of ranking-based metrics (i.e., Coverage Error, One Error, and Ranking Loss), REHC-PML consistently outperforms baseline methods on most datasets, especially on those with complex label structures such as YeastBP and YeastCC, demonstrating the success of the high-order to low-order broadcasting mechanism in label ranking. Regarding Hamming Loss, WPML3CP achieves competitive results, particularly on the Yeast datasets, due to its Wasserstein distance-based formulation optimized for dense label distributions. However, REHC-PML remains competitive and achieves the best Hamming Loss on mirflickr and music style. Additionally, some baseline methods (i.e., PARTICLE and PAMB) exhibit high variance across different datasets, while REHC-PML demonstrates stable performance with consistently low variance, suggesting that the proposed high-order correlation-based framework provides robust structural guidance for label disambiguation.

4.3 Results on UCI Datasets

To further evaluate the robustness of REHC-PML under varying noise levels, we conduct experiments on UCI multi-label datasets with noise ratios m ∈ {50, 100, 150}. Due to space constraints, we present representative results for selected datasets with m = 150 in Table 3. Complete results are provided in Appendix B 1 . The selected UCI datasets are particularly challenging due to their large size or high label dimensionality. These characteristics pose significant challenges for PML methods in terms of both disambiguation accuracy and computational time. Notably, entries marked with "-" indicate that the corresponding methods failed to produce results within reasonable time constraints due to their computational complexity on these large-scale datasets.

1 https://github.com/yuanchaodai/IJCAI2026 REHC-PML Appendix

From Table 3, we observe that REHC-PML achieves consistently superior performance across all eight datasets. Most notably, REHC-PML ranks first in Average Precision on all datasets, with substantial improvements on delicious (+11.8% over the second-best PMLNI) and bookmarks (+5.2% over PMLNI). For the Coverage Error and Ranking Loss, PARD achieves slightly better results on computers, while REHC-PML excels on most datasets. We attribute this to the relatively small average label cardinality of these datasets, where pairwise label correlations may suffice for effective ranking. However, on datasets with richer label structures such as delicious (19.02 average labels), REHC-PML significantly outperforms PARD, confirming the advantage of high-order label correlations for complex PML scenarios.

4.4 Statistical Analysis

To further substantiate the effectiveness of REHC-PML, we conduct pairwise t-tests between our proposed method and each baseline across 30 datasets and 5 evaluation metrics (150 pairwise comparisons per baseline). It is worth noting that incomplete results (denoted as '-' in the experimental tables) are excluded from the statistical comparisons. Table 4 summarizes the win/tie/loss counts at the 0.05 significance level. The results demonstrate that REHC-PML achieves statistically significant improvements in the overwhelming majority of comparisons. Specifically, REHC-PML significantly outperforms GLC in 96.7% (145/150) of tests, PLAIN in 95.3% (143/150) of tests, and PML-NI in 88.0% (132/150) of tests. Against the state-of-the-art method PML-FSMIR, REHC-PML wins in 90.0% (81/90) of comparisons.

Furthermore, the Friedman test is used to statistically compare the relative performance among all competing methods. Table 6 reports the Friedman statistic FF in terms of each evaluation metric. The results demonstrate that all five Friedman statistics substantially exceed the critical value of 1.955 at the 0.05 significance level. Average Precision exhibits the highest discriminative power (FF = 20.920), followed by One Error

(FF = 15.025), Hamming Loss (FF = 13.680), Ranking Loss (FF = 12.629), and Coverage Error (FF = 11.171). Notably, REHC-PML consistently achieves the best mean rank across all metrics, demonstrating that our proposed high-order correlation-based framework delivers robust and reliable performance improvements over existing PML baselines.

4.5 Ablation Study

To validate the contribution of different components, we conduct an ablation study on six real-world PML datasets. Table 5 presents the Average Precision for four variants, where we evaluate three key components: (a) high-order label correlation structure, (b) attention-based semantic aggregation, and (c) Gumbel-Softmax structural pruning. The results show that each component contributes to the overall performance. Specifically, Variant I leads to the most significant performance degradation, indicating that modeling high-order label correlations is crucial for effective label disambiguation. The Gumbel-Softmax structural pruning also contributes positively (Variant III), particularly on music emotion and music style, demonstrating that differentiable correlation selection effectively filters out noisy label co-occurrence patterns. These results collectively validate the effectiveness of each proposed component in the REHC-PML framework.

4.6 Parameter Analysis

We investigate the sensitivity of two key hyperparameters: the maximum correlation order pmax and the pseudo-label loss weight λ. As shown in Figure 2, the left column demonstrates that performance generally improves as pmax increases from 1 to 3, confirming that modeling high-order label correlations enhances disambiguation. The right column shows that λ exhibits relatively stable performance across a wide range (10-2 to 102 ), with optimal values typically around λ = 1. This suggests that our method is robust to the balance between candidate label consistency and pseudo-label alignment.

5 Conclusion

This paper proposes REHC-PML to address the limitation of existing PML methods that neglect high-order label correlations. By mining high-confidence label combinations and broadcasting them to constituent labels, our method provides structural guidance for disambiguation. Experiments on six real-world and eight UCI datasets demonstrate superior performance across multiple metrics, particularly on datasets with complex label structures. The results validate that high-order co-occurrence patterns offer more effective disambiguation than instance-level or pairwise methods. Future work will explore more effective structural pruning methods and higherorder optimization techniques.

Acknowledgments

We would like to acknowledge support for this project from the National Natural Science Foundation of China (No.62276113) and the Graduate Innovation Fund of Jilin University (No.2026CX208).