Pseudo-Label Reconstruction for Partial Multi-Label Learning

1 Introduction

In the domain of machine learning, entities from the real world are often encapsulated as data points, each comprised of features and a corresponding label. In conventional classification tasks, labels are exclusive, allowing only a single label to be assigned to each data point. However, numerous real-world items possess multiple layers of meaning. Consider a film that might encompass genres like science fiction, war, and adventure, or a news piece that could be categorized under politics, economics, and sports. Multi-label learning (MLL) [Liu et al., 2021], which permits the assignment of multiple discrete labels to a single data point, has thus gained significant attention in machine learning circles and is utilized in a range of practical applications [Tahzeeb and Hasan, 2022], including: text classification, image recognition and protein function prediction. However, the process of acquiring datasets with accurate labels is not only costly but also difficult. More often, we may end up with just a candidate set of labels, some of which are relevant and others are just noise. This noise will blur the classification decision boundary, reducing the effectiveness of MLL.

∗Corresponding author

To address this challenge, Xie and Huang [Xie and Huang, 2018] propose the concept of partial multi-label learning (PML) as an innovative framework, whose objective is to build a model capable of assigning labels to new instances with noisy labels. The main challenge in PML is detecting noisy labels and building accurate classification models, which traditional multi-label learning (MLL) algorithms fail to address. For example, ML-KNN [Zhang and Zhou, 2007] and LIFT [Zhang and Wu, 2014] cannot effectively handle noisy labels, leading to poor performance on noisy datasets.

In recent years, the development of PML methods can be broadly categorized into two types: two-stage methods and end-to-end methods [Chen et al., 2024]. In two-stage methods, noisy labels are first identified and then the classifier is trained. Such as, DRAMA [Wang et al., 2019] constructs a label confidence matrix based on the feature manifold and candidate label set, utilizing it directly to train a multi-output regression model. PARTICLE [Zhang and Fang, 2020] applies label propagation to integrate information from K-nearest neighbors, establishes a confidence threshold for labels, and subsequently trains the MLC classifier. In contrast, end-toend methods optimize reliable labels and the classifier simultaneously. Examples include PML-DNDC [Hu et al., 2023] employs dual noise elimination, simultaneously removing label and feature noise to enhance classifier training by exploring label dependencies and promoting label similarity among classifiers. PML-ND [Zhong et al., 2024] employs negative label information to guide label propagation process to induce ground-truth labels with high credibility.

These methods address PML problems, but several critical limitations remain: 1) Existing approaches largely overlook the discriminative instance correlations embedded within candidate labels, primarily because noise contamination prevents direct extraction of meaningful correlations between instances. 2) Current disambiguation methods produce pseudolabels that inadequately capture the intrinsic consistency relationship between feature representations and label semantics, leading to suboptimal classification performance.

To address these limitations, this paper proposes a novel PML method based on pseudo-label reconstruction (PMLPLR). Specifically, we first introduce an innovative orthogonal candidate label reconstruction approach that leverages subspace reconstruction techniques to effectively mitigate both noise interference and complex label correlations within candidate label sets. This reconstruction is then jointly optimized with instance features to extract more robust and semantically meaningful instance correlations that better reflect true label relationships. Subsequently, these refined instance correlations serve as reconstruction coefficients to generate high-quality pseudo-labels that better approximate groundtruth labels. Finally, through local manifold learning, the reconstructed pseudo-labels propagate consistency relationships between features and labels, ensuring the final pseudolabels align more closely with the underlying true label distribution. The main framework is illustrated in Figure 1.

2 RelatedWork

2.1 Multi-Label Learning

In multi-label learning (MLL), each example is associated with multiple valid labels, and various approaches are extensively studied. Some methods transform MLL into binary classification problems, treating each label independently [Zhang et al., 2024]. To enhance performance, many studies explore label correlation, including pairwise and highorder dependencies. Recently, integrating manifold learning with MLL has gained increasing attention. Hou et al. [Hou et al., 2016] investigate the manifold structure in the label space, assuming that correlated instances share labels. Zhang et al. [Zhang et al., 2019] employ manifold learning and sparse feature selection to obtain a low-dimensional embedding for label information. Zhao et al. [Zhao et al., 2022b] combine manifold and subspace learning to mitigate noise and handle missing labels, reconstructing a more robust feature and label space. However, MLL typically assumes that each instance is precisely labeled, which is often unrealistic [Wang et al., 2024; Wang et al., 2023; Wang et al., 2021; Wen et al., 2023; Wen et al., 2022; Wen et al., 2018]. In noisy MLL, binary labels may be flipped to incorrect values. While these approaches reduce the burden of multi-label annotation, they neglect the inherent challenge of labeling-specifically, that labels themselves can be ambiguous.

2.2 Partial Multi-Label Learning

Compared to MLL, PML presents greater challenges, requiring learning in imperfect environments and training highprecision classifiers. Current PML research primarily centers on label disambiguation-identifying true labels within candidate sets. Existing approaches typically employ explicit learning strategies to remove noisy labels through various techniques. Some methods leverage low-rank and sparse decomposition to separate ground-truth labels from noise [Sun et al., 2019; Sun et al., 2024], while others estimate candidate label credibility via label propagation or enhancement techniques [Zhang and Fang, 2020; Xu et al., 2020; Xu et al., 2023; Lin et al., 2025; Chen et al., 2024]. Many approaches utilize feature information to identify noise [Yu et al., 2018; Xie and Huang, 2021; Wang et al., 2019; Lyu et al., 2021], with the most common practice being the application of correlation or manifold constraints on labels [Li et al., 2021; Lyu et al., 2020; Li et al., 2022; Hu et al., 2023]. Feature selection has recently emerged as a popular disambiguation strategy [Wang et al., 2022; Hao et al., 2023; Han et al., 2025; Wu et al., 2025], while other researchers harness label correlations or cluster assignments [Zhao et al., 2022a; Sun et al., 2021; Qian et al., 2024a; Wang et al., 2025; Fang et al., 2025]. Various deep learning algorithms have also been deployed to mine data distributions and mitigate noise impact [Hang and Zhang, 2023; Xie and Huang, 2022; Qian et al., 2024b].

3 ProposedMethod

In this section, we introduce PML-PLR and its feasibility optimization. Define some common variables as: X = [x1, x2, · · · , xn] ∈ Rd×n denotes feature matrix of n instances with d-dimensional features. Y ∈ {0, 1}l×n represents a candidate label matrix with noisy information, where l is the number of label classes. If Yij = 1 then the i-th label is associated with the j-th instance. If Yij = 0, the opposite. Each instance correspond to a set of candidate labels with unrelated labels incorrectly labeled as 1, which is called noisy label. The goal of PML is to minimize the impact of noisy information to make correct label predictions.

3.1 Learning Objective

Our ultimate goal is to induce a multi-label predictor f : X ↦→ [0, 1]l , which can assign an appropriate set of labels to unseen instances. The main objectives of this paper are as follows:

1. Learning more consistent instance-level correlation, which allows the model to obtain more accurate correlation between instances.
2. Learning label-instance relationships for pseudo-label reconstruction, which makes the generated pseudo-labels more consistent with instances and the real label distribution.

3.2 Instance-level Consistent Correlation Learning

The correlation between learning instances is typically measured using the feature similarity between each pair of instances. Common methods include the Gaussian kernel function, cosine similarity, and Pearson correlation coefficient. In order to learn instance-level correlation with higher consistency between features and labels, we first use the distance relationships of each instance's features to preliminarily learn the instance-level correlation. The formula is :

where, 1 is an n-dimensional all-1 row vector, C ∈ Rn×n represents the captured instance correlation matrix, each element cij reflects the influence of j-th instance on i-th instance. To enhance the consistency of instance-level correlation, we choose to use label information to jointly learn correlation. We believe that both features and labels are used to describe instances, and label information contains more discriminative instance correlation. We use label self-mapping to capture the correlation between instances without losing this discriminability. The formula is expressed as follows:

However, since label Y contains noise, C learned by the second item in the above method is not accurate enough. And due to the correlation between labels, some labels are highly related, leading to situations where two labels almost always appear together. To reduce the influence of label correlation and noise on instance-level correlation learning, for the second item, we select a more representative latent label space to learn more robust instance-level correlation. The formula is:

where H ∈ Rm×n (m ≤ l) represents the potential label space matrix, and P ∈ Rm×l is the indication matrix mapping the original label matrix to the latent label space. The constraint PP⊤ = Im ensures no distortion during dimensionality reduction, with the row vectors of P forming an orthogonal basis, meaning the column vectors of H are orthogonal components of Y in m-dimensional space. To mitigate information loss and dimensional sensitivity, we introduce a regularization term to preserve information flow. Specifically, we add a reconstruction term to retain key information from the original label matrix and a ℓ1-norm sparsity constraint to prevent overfitting due to noisy labels. The updated formula is as follows:

where α is a regularization parameter controlling the importance of preserving the original label structure. By updating Eq.(2), the learning formula of the final instance-level correlation is as follows:

3.3 Pseudo-label Reconstruction

In order to obtain better classification prediction results, pseudo-label learning should maintain high consistency between instances and labels while minimizing noise. Furthermore, to maximize the effectiveness of previously obtained instance-level correlation in subsequent pseudo-label reconstruction, we need to reduce the influence of incorrect instance correlations present in the original labels. We achieve this by utilizing a rotation transformation to alter the instance distribution, thereby weakening the instance correlations embedded in the original labels. This rotation-based approach is formulated as follows:

where F = [f1, f2, · · · , fn] ∈ Rl×n represents the pseudolabel matrix and Q ∈ Rn×n represents the orthogonal projection transformation matrix. By constraining Q to be orthogonal, the resulting pseudo-label matrix F preserves the essential structure while minimizing the misleading correlations inherited from the original label matrix Y. The constraint of 0l×n ≤ F ≤ Y can ensure that the main structure of the pseudo-label is consistent with the original label.

Next, we use the previously learned instance-level correlation C as the reconstruction coefficient to reconstruct the pseudo-labels, endowing them with the correct instance correlations. This approach follows the principle that similar instances should have similar labels. For the i-th instance fi, the instance-level correlation with other instances is used as label weight to reconstruct it. We can obtain reconstructed pseudo-label ˜fi:

To enhance the consistency between pseudo-labels and instances, we employ nearest neighbor relationships to constrain distances between pseudo-labels and their reconstructed counterparts. This approach ensures labels conform to the data's local manifold structure while propagating labelinstance relationships. The neighbor correlation is computed:

where N(xi) denotes the set of k nearest neighbors of sample xi, and σ = 1n ∑ni=1 ∥xi-x(k) i ∥2 is the bandwidth parameter of the Gaussian kernel, which controls how the distance between samples affects their similarity. The main goal of this section is to first weaken the instance-level correlation in the original labels using orthogonal mapping, then use the previously learned, more consistent instance-level correlation to reconstruct the pseudo-labels, and apply local manifold constraints to restore the instance-level correlation of the pseudolabels. The relationship between the label and the instance is propagated by reconstructing the pseudo-label. The overall formula for this section is expressed as follows:

3.4 Kernel Nonlinear Classifier

For the classifier part, we represent ϕ(·) : Rd → Rh as a feature mapping from the feature space to some h-dimensional high-dimensional Hilbert space, and then we can train the ridge regression model. Further using the deviation term b ∈ Rc in the prediction function, the prediction function with kernel extension can be expressed as g(xi) = W⊤ϕ(xi)+b. Supervised training using the pseudo-label F, then the classification model can be expressed as:

By defining a matrix E = [ϵ1, ϵ2, . . . , ϵ3]⊤∈ Rl×n the above problem can be re-written in the following matrix form:

where Φ = [ϕ(x1), ϕ(x2), . . . , ϕ(xn)]∈ Rh×n . To facilitate optimization, we restate Eq.(11) as:

3.5 Overall Objective Function

By combining the Eq.(5) (consistent correlation learning), Eq.(9) (pseudo-label learning and reconstruction) and Eq.(12) (classifier), the final objective function of the model is obtained as follows:

3.6 Optimization

For the above optimization problem, ADMM [Feng et al., 2020] is adopted to solve it. In other words, we use alternate optimization to solve Eq.(13), details are as follows:

Update P and H

Removing the items that are irrelevant to P and H, and fix C. Then, the sub-optimization as:

Then we apply the augmented Lagrange multiplier method to get the following Lagrange function:

where µ is a very large number. With P and E fixed, since PP⊤ = Im, H can be solved in a closed form :

With H and E fixed, for P, the sub-optimization can be converted to:

where Tr(·) is the trace norm. It is noted that the problem in Eq.(17) corresponds to the classic orthogonal procrustes problem [Cai et al., 2010], which can be approximated by singular value decomposition (SVD). Let R = 2YC⊤H⊤ + u(Y-E)H⊤, then we utilize SVD to decompose R, i.e., R = UΣV⊤, optimization of P can be obtained by:

With H and P fixed, the variables E can be optimized by solving following problem:

which is a typical LASSO regression problem [Mirone and Paleo, 2017], and we apply PGD algorithm to optimize it. The proximal operator of Eq.(19) is:

where Z = Et - 1L ∇L(E(t) ), E(t) represents the solution from the t-th iteration, and ∇L(E) is the gradient of the objective function L(E), L is the Lipschitz constant of ∇L(E) and t denotes the number of iteration. Problem of Eq.(20) can be iteratively updated by the soft-thresholding operator:

where Soft[b, ν] = sign(b)max{|b| -ν, 0}. In addition, the Lipschitz constant of ∇L(E) is 1, so we set L = 1.

Update C

Removing the items that are irrelevant toC, the suboptimization for C is simplified as:

where Lk is the Laplacian matrix of K, G ∈ Rn×n represents the distance matrix, for each element Gij = ∥xi -xj∥22 . Taking the derivative of Eq.(22) and setting the derivative to zero, we obtain the following equation:

Then, we can obtain the optimization result variable for the first step of optimizing C :

Then the optimization of C can be transformed into:

Eq (25) can be solved using the technique reported in [Huang et al., 2015] or be solved via off-the-shelf QP tools.

Update Q

For Q optimization, which also is a classical orthogonal problem, Q can be solved as: first compute the singular-value decomposition (SVD) of matrix Y⊤F as Y⊤F = MΣN⊤ and then let Q = MN⊤.

Update W and b

We add a bias term b to the classifier, so that classifier W becomes: Wm = [W; b] : the feature matrix Φ becomes: Φm = [Φ; 1h]. The optimization can be reformulated as:

After taking the derivation and making the derivation result zero, the updated formula of Wm is simplified as follows:

Update F

Removing the items that are irrelevant to F, and fixW, b,Q and C. Then, the suboptimization for F is simplified as:

For the 0l×n ≤ F ≤ Y constraint, it can be decomposed into two non-negative constraints, F ≥ 0 and Y - F ≥ 0. Next, the Lagrange multiplier method is applied to solve it:

where Ω and Θ represent the Lagrange multiplier. Taking the derivative of Eq.(29) and setting the derivative to zero, we obtain the following equation:

Based on condition of Karush-Kuhn-Tucker (KKT), it can be given that: ΩijFij = 0 and Θij(Y-F)ij = 0 the update rules for F can be obtained as:

where A = 2F + βFC⊤Lk + βFL⊤k C, B = W⊤mΦ + YQ, eps is a tiny value to prevent the denominator from being 0. The update for Θ is based on the complementary condition: Θij = max(0, Fij - Yij ).

4 Experiments

4.1 Datasets

To evaluate the generalization performance of our proposed PML-PLR method, a total of 25 datasets are used for comparative study. Specifically, the experiments are conducted on 4 real-world PML datasets and 21 synthetic PML datasets generated from 8 multi-label datasets. Detailed characteristics of all datasets are summarized in Table 1. For the 3 real-world PML datasets, including Music emotion , Music style, Mirflickr and YeastBP 1 . For the 8 multi-label data sets, including Emotions, Birds, Medical, Image, Scene, Yeast2 , Health and Reference [Zhong et al., 2024], We synthesize PML datasets by randomly adding unrelated labels together with their underlying truth labels to form a candidate tag set. The noise is added by randomly introducing false positive labels. For example, in the emotions dataset, the average number of ground-truth labels are 1.86 (avg.#GLs), and after adding noise, the average number of positive labels become 4 (avg.#CLs), resulting in an average of 2.14 noise labels per instance. It is worth noting that due to the page limit, most of the following experimental synthetic datasets are based on the experimental Settings in parentheses, that is, 8 synthetic datasets.

4.2 Baselines and Implementation Details

We select seven benchmark methods for comparison, including two MLL methods ML-KNN [Zhang and Zhou, 2007] and LIFT [Zhang and Wu, 2014], five state-of-the-art PML methods PML-LENFN [Chen et al., 2024], PAMB [Liu et al., 2023], PML-NI [Xie and Huang, 2021], PARTIAL [Zhang and Fang, 2020] and FPML [Yu et al., 2018]. We set the corresponding parameters according to the recommendations in the respective literature. The parameters α, β and λ in the PML-PLR are selected using grid search from {10-4 , 10-3 , 10-2 , 10-1 , 100 }. Cross-validation is employed to select the optimal latent space dimension m. Five widely-used multi-label metrics are employed to evaluate each comparing method, including Hamming Loss, Ranking Loss, One-Error, Coverage and Average Precision. Detailed definitions on them can be found in [Zhang and Zhou, 2013].

1 http://palm.seu.edu.cn/zhangml/

2 http://mulan.sourceforge.net/datasets.html

4.3 Experimental Results

Due to page limitations, Tables 2 and 4 only present the results under the experimental settings in parentheses in Table 1. Table 2 reports the results of the experiment on real-world datasets. Table 4 shows the results on synthetic datasets. After analyzing the experimental results, we can draw the following conclusions:

• It turns out from Table 2 and Table 4 that we conduct 36 cases (12 datasets × 3 metrics = 36 cases) of experiments and PML-PLR performs best 31 cases (real world dataset 11 cases, synthetic dataset 20 cases), accounting for 86.11%. This proves that PML-PLR performs best on both real-world and synthetic datasets.
• MLL algorithms excel in classification on low-noise datasets, while PML algorithms perform better on highnoise datasets due to their denoising focus. PML-PLR outperforms both MLL and PML algorithms in all settings, highlighting the effectiveness of its pseudo-label reconstruction and the model's robust classification.

Under a total of 25 experimental settings, the Friedman test [Demˇsar, 2006] is used to assess the relative performance of the methods, with Table 3 showing the Friedman statistic FF and the critical value. The post-hoc Nemenyi test evaluates statistical significance of performance differences. Figure 2 presents critical difference (CD) diagrams for each metric, where PML-PLR (highlighted with a red line) serves as the control method. Methods whose performance differences do not exceed the CD value are connected by blue lines, indicating no significant statistical difference. The results clearly highlight PML-PLR's significant superiority, as it achieves the lowest average rank across all metrics, with few or no other methods connected to it via the CD threshold.

4.4 Further Analysis

Convergence analysis: Figure 3 (a) shows the convergence curve of the model in multiple data sets. The result shows that with the increase of the number of iterations, the loss value decreases rapidly and finally stabilizes at a low value, indicating that the model converges to a satisfactory solution. Parameter sensitivity analysis: Figure 3 (b), (c) and (d) show the sensitivity experimental results of the three parameters α, β, λ in the model. The results show that each parameter has an optimal value and PML-PLR performs stably across a wide range of parameters, making it capable of robust classification performance under various conditions.

Ablation analysis: Figure 4 shows the ablation results on two datasets, comparing PML-PLR with its three degraded versions: no pseudo-label learning (PL-free, which directly uses candidate labels for classifier training ), no reconstruction (R-free, which sets parameter β=0), and no consistent correlation (C-free, which extracts correlation only from feature matrix X). The results clearly demonstrate that PMLPLR significantly outperforms all degraded algorithms across multiple evaluation metrics, validating the effectiveness and necessity of each component in our proposed framework. The performance drop when removing any single component highlights their complementary nature in addressing the challenges of partial multi-label learning.

5 Conclusion

This paper presents a novel PML method, PML-PLR, which jointly extracts instance-level correlation from candidate labels and features, and then uses the instance correlation as reconstruction coefficient to reconstruct pseudo-labels. Through local manifold learning, the reconstructed pseudolabels are used to propagate the consistency relationship between labels and instances, thereby improving the accuracy of pseudo-labels. Extensive experiments demonstrate the superiority of the model.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grant No. 62176065, No. 62302172, in part by the Guangdong Provincial National Science Foundation under Grant No. 2022A1515011277.