Deep Partial Multi-Label Learning with Graph Disambiguation

1 Introduction

The rapid growth of deep learning allows us to tackle increasingly sophisticated problems. Among them, multi-label learning (MLL), which assigns multiple labels to an object, is a fundamental and intriguing task in various real-world applications such as image retrieval [Lai et al., 2016], autonomous vehicles [Chen et al., 2019a], and sentiment analysis [Yilmaz et al., 2021]. Typically, these tasks require precisely labeled data, which is expensive and time-consuming due to the complicated structure and the high volume of the output space.

∗Corresponding author.

To address this issue, plenty of works have studied different weakly-supervised settings of MLL, including semisupervised MLL [Shi et al., 2020], multi-label with missing labels [Durand et al., 2019; Huynh and Elhamifar, 2020], and single-labeled MLL [Xu et al., 2022]. While these learning paradigms mainly battle the rapid growth of data volume, they overlook the intrinsic difficulty and ambiguity in multilabel annotation. For example, it is hard for a human annotator to identify an Alaskan Malamute from a Siberian Husky. One potential solution is to randomly decide the binary label value. However, it may involve uncontrollable label noise that has a negative impact on the training procedure. Another strategy is to leave it missing, but then, we may lose critical information. Recently, partial multi-label learning (PML) [Xie and Huang, 2018] has been proposed to alleviate this problem. In PML, the annotators are allowed to provide a candidate label set that contains all potentially relevant labels as well as false-positive labels.

A straightforward approach to learning from PML data is to regard all candidate labels as valid ones, and then, offthe-shelf multi-label methods can be applied. Nevertheless, the presence of false-positive labels can highly impact predictive performance. To cope with this issue, many PML methods [Xie and Huang, 2018; Yu et al., 2018; He et al., 2019; Sun et al., 2019; Li et al., 2020; Lyu et al., 2020; Yan et al., 2021; Xie and Huang, 2022] have been developed. Amongst them, graph-based PML methods [Wang et al., 2019; Li and Wang, 2020; Xu et al., 2020; Lyu et al., 2020; Zhang and Fang, 2021] have been popular. In practice, graphbased algorithms demonstrate a good ability to obtain relatively precise confidence of candidate labels by aggregating information from the nearest neighbors. However, we observe that most of them adopt linear classifier, which is powerless to deal with complicated tasks and high data volumes.

Therefore, there is an urgent need for developing an effective deep model to boost the performance of graph PML methods. However, there are two main challenging issues. First, existing graph-based PML methods typically require propagating labels over the whole training dataset. It restricts their scalability when employing deep classifiers since the deep models are trained in batch mode. Second, it is well acknowledged that there exist label correlations in multi-label datasets, which also helps disambiguate the candidate labels. For example, if labels Amusement Park and Mickey Mouse are identified as true, it is very likely that label Disney is true as well. Thus, it is required to exploit the label correlations to improve the disambiguation ability in a unified framework.

In this work, we propose a novel deep Partial multi-Label model with grAph disambIguatioN (PLAIN). In PLAIN, we involve both instance- and label-level similarities to disambiguate the candidate labels set, which simultaneously leverages instance smoothness as well as label correlations. Then, we build a deep multi-label classifier to fit the relatively credible pseudo-labels generated through disambiguation. Instead of separately training in two stages like previous works [Wang et al., 2019; Zhang and Fang, 2021], we propose an efficient optimization framework that iteratively propagates the labels and trains the deep model. Moreover, we give a careful analysis of the risk functions such that proper risk functions are chosen for improved robustness. Empirical results on nine synthetic datasets and three real-world PML datasets clearly verify the efficiency and effectiveness of our method. More theoretical and empirical results can be found in Appendix 1 .

2 RelatedWorks

Multi-Label Learning. MLL [Liu et al., 2022; Wei et al., 2022] aims at assigning each data example multiple binary labels simultaneously. An intuitive solution, the one-versus-all method (OVA) [Zhang and Zhou, 2014], is to decompose the original problem into a series of single-labeled classification problems. However, it overlooks the rich semantic information and dependencies among labels, and thus fails to obtain satisfactory performance. To solve this problem, many MLL approaches are proposed, such as embedding-based methods [Yu et al., 2014; Shen et al., 2018], classifier chains [Read et al., 2011], tree-based algorithms [Wei et al., 2021], and deep MLL models [Yeh et al., 2017; Chen et al., 2019b; Bai et al., 2020]. Nevertheless, these methods typically require a large amount of fully-supervised training data, which is expensive and time-consuming in MLL tasks. To this end, some works have studied different weakly-supervised MLL settings. For example, semi-supervised MLL [Niu et al., 2019; Shi et al., 2020] leverages information from both fullylabeled and unlabeled data. Multi-label with missing labels [Durand et al., 2019; Wei et al., 2018; Xu et al., 2022] allows providing a subset of ground-truth. In noisy MLL [Veit et al., 2017], the binary labels may be flipped to the wrong one. Nevertheless, though these settings relieve the burden of multi-label annotating, they ignore the inherent difficulty of labeling, i.e. the labels can be ambiguous.

Partial Multi-Label Learning. PML learns from a superset of ground-truth labels, where multiple labels are possible to be relevant. To tackle the ambiguity in the labels, the pioneering work [Xie and Huang, 2018] estimates the confidence of each candidate label being correct via minimizing confidence-weighted ranking loss. Some works [Yu et al., 2018; Sun et al., 2019; Li et al., 2020; Gong et al., 2022] recover the ground-truth by assuming the true label matrix is low-rank. Recently, graph-based methods [Wang et al., 2019; Xu et al., 2020; Lyu et al., 2020; Xie and Huang, 2020; Zhang and Fang, 2021; Xu et al., 2021; Tan et al., 2022] have attracted much attention from the community due to the good disambiguation ability. For instance, PARTICLE [Zhang and Fang, 2021] identifies the credible labels through an iterative label propagation procedure and then, applies pair-wise ranking techniques to induce a multi-label predictor. Although graph-based models have shown promising results, we observe that most of them adopt linear classifiers, which significantly limits the model expressiveness. Besides, they typically separate the graph disambiguation and model training into two stages, which makes the multi-label classifier error-prone; in contrast, the proposed PLAIN is an end-toend framework.

1 https://arxiv.org/abs/2305.05882

Some studies have also developed deep PML models, such as adversarial PML model [Yan and Guo, 2019] and mutual teaching networks [Yan et al., 2021]. However, it remains urgent to combine the graph and deep models together such that the model enjoys high expressiveness as well as good disambiguation ability. It should also be noted that the recent popular graph neural networks (GNN) model [Wu et al., 2021] is not suitable for PML. The reason is that GNN aims at better representation learning (at an instance-level), while in PML, the graph structure is used to alleviate the label ambiguity.

3 Method

We denote the d-dimensional feature space as X ⊂ Rd , and the label space as Y = {1, 2, . . . , L} with L class labels. The training dataset D = {(xi, Si)|1 ≤ i ≤ n} contains n examples, where xi ∈ X is the instance vector and Si ⊂ Y is the candidate label set. Without loss of generality, we assume that the instance vectors are normalized such that ||xi||2 = 1. Besides, we denote ˜ Si ⊂ Y as the ground-truth label set, which is a subset of Si. For simplicity, we define yi, ˜ yi ∈ {0, 1}L as the binary vector representations of Si and ˜ Si. When considering the whole dataset, we also denote the candidate label matrix by Y = [y1, . . . , yn]⊤ ∈ Rn×L.

In what follows, we first introduce the learning target of our model that integrates label correlations to boost disambiguation ability. Then, we provide an efficient optimization framework for our deep propagation network.

3.1 Learning Objective

Our ultimate goal is to estimate a multi-label predictor f : X ↦→ [0, 1]L fromD. In this work, we assume that its output ˆ y = f(x) satisfies the following properties,

1. ˆ y is close to the candidate vector y;
2. ˆ y satisfies the instance-level similarity. That is, if two instances are close to each other, then their label vectors are likely to be close too;
3. ˆ y satisfies the label-level similarity. That is, if two labels co-occur in the training data frequently, then they tend to co-exist at many instances.

These properties coincide with our goals. The first property is natural since the only thing we can trust is the candidate label set. The second one has been widely adopted to disambiguate the ground-truth label from the false-positive labels. The last one exploits the label correlations to further promote the performance. In this paper, we adopt a graph-based model to achieve these goals. Generally speaking, the graph structure can be collected in various ways. One direct strategy is to use prior knowledge. For instance, for data mining tasks, social networks [Qiu et al., 2018] can be used to depict instance similarity. The label similarity can also be estimated using an external knowledge graph [Lee et al., 2018].

However, we notice that there is no available graph structure in existing public PML datasets. Hence, we propose to construct the instance graph Ax ∈ Rn×n and the label graph Ay ∈ RL×L in a data-driven way. To obtain Ax , we adopt a monomial kernel [Iscen et al., 2017] as the distance metric and calculate a sparse instance affinity matrix S ∈ Rn×n with elements,

Here Nk(xi) saves the indices of k-nearest neighbors of xi. ρ > 0 controls the weights of similarity. Then, we get a symmetrized instance graph by Ax = S + S⊤.

Inspired by HALE [Lyu et al., 2020], we build the label graph Ay by means of the label co-occurrence statistics from the training data, whose elements are given by,

where I(·) is an indicator function returning 1 if the event is true and 0 otherwise. It is worth noting that HALE simply calculates the average co-occurrence by dividing the instance number, which overlooks the existence of false-positive labels. In our method, we penalize it by the counts of instances that are assigned the labels as the candidates. In other words, if one label is assigned to too many instances, its cooccurrence statistics are less reliable.

Next, we impose the instance-level similarity property on the model output by means of a Laplacian regularizer,

where ˆ Y = [ˆ y1, . . . , ˆ yn]⊤ is the predicted label matrix. Lx = I -D- 12 x AxD- 12 x is the Laplacian matrix of instance graph. Dx = diag[dx1 , . . . , dxn ] is a diagonal matrix with dxi = ∑nj=1 axij . The objective in Eq. (1) enforces two data examples to have similar predicted labels if they have a large affinity score. Similarly, we can introduce the label-level similarity by,

Finally, we involve a candidate consistency term to get the following objective,

where ||·||F is the Frobenius norm. η, α, and β are all positive hyperparameters.

In summary, the main goal of our objective is to utilize the instance- and label-level similarity to recover reliable label confidences and address the problem of false positives, while simultaneously enjoying an extra performance improvement by exploiting label correlations.

3.2 Deep Propagation Network

If a linear model is adopted, the parameters can be directly obtained by optimizing J (f(X), Y ) with gradient descent. However, in deep models, it is not the case. When we update the model using a mini-batch of data, the instance-level manifold regularizer can involve unexpected gradient updating on the nearest neighbors of these data. Then, the training time will increase rapidly. To remedy this problem, we propose an efficient optimization framework for training a deep model from PML data. Specifically, we maintain a smooth pseudo-label matrix Z, which minimizes the propagation error while being close to the model output ˆ Y . In the sequel, we elaborate the training procedure of our model. The training procedure is also summarized in Algorithm 1.

Propagation Step

At t-th epoch, we first propagate the label information from candidates Y and the model output ˆ Y to the intermediate ones. In graph-based methods, the output label is required to be smooth enough. Therefore, we use the Frobenius norm as the measure to ensure the closeness of Z and ˆ Y . Formally, we estimate Z by,

We can derive its gradient by,

which is followed by the matrix properties that ∂||Z-Y ||2F ∂Z =

2(Z - Y ) and ∂tr(Z⊤LxZ) ∂Z = (Lx + L⊤x )Z. We have Lx+L⊤x = 2Lx because Lx is symmetric. The optimal condition ∂LLP ∂Z = 0 typically requires solving a Sylvester system, which can be time-consuming. Therefore, we solve this problem by gradient descent Z = Z - γ ∂LLP(Z) ∂Z , where γ > 0 is the learning rate. Note that in MLL datasets, negative labels usually dominate, which makes all the pseudo-labels tend to concentrate at a small value. To cope with this issue, we further perform column-wise min-max normalization on Zt to obtain a balanced output.

Model Updating Step

Given an instance vector x, we first feed it into a deep neural model ˆ y = f(x; θ). Then, we update the model parameters to fit the pseudo-labels,

where l(·, ·) is the loss function. Recall that in Eq. (2), we enforce Z to be close to ˆ Y using the Frobenius norm. Hence, a natural choice of loss is to reuse the mean squared error (MSE), which is adopted by most graph-based PML algorithms [Wang et al., 2019; Xu et al., 2020; Zhang and Fang, 2021]. However, in PML tasks, the disambiguated labels can still be noisy and the MSE loss leads to heavy overfitting. This is largely overlooked by previous works.

To tackle this problem, we shall have a closer look at the risk function. While MSE penalize too much on prediction mistakes, other robust surrogate losses can be considered, such as mean absolute error (MAE). However, we notice that MAE violates our smooth prediction assumption. To this end, we adopt the widely-used binary cross-entropy loss (BCE) for multi-label learning,

where σ(·) is the sigmoid function. On one hand, BCE loss approximately grows linearly for largely negative values, which makes it less sensitive to outliers. On the other hand, BCE outputs relatively smooth output such that the smoothness is preserved.

In effect, we can go further on the risk. A plethora of works [Ghosh et al., 2017; Feng et al., 2020] has demonstrated that

Algorithm 1 The pseudo-code of PLAIN

Output: The deep MLL network parameter θ Input: Training dataset D, instance graph Ax , label graph

Ay , hyperparameters γ, α, β and η, iteration number T

• 1: Z ←Y
• 2: Lx ← I -D- 1 2 x AxD- 1 2 x
• 3: Ly ← I -D- 1 2 y AyD- 1 2 y
• 4: for epoch t = 1, 2, 3, . . . do
• 5: for batch j = 1, 2, . . . in D do
• 6: Sample a mini-batch data (Xj , Zj )
• 7: ˆ Y j ← f(Xj ; θ)
• 8: θ ← OPTIMIZE(l( ˆ Y j , Zj ; θ))
• 9: end for
• 10: ˆ Y ← f(X; θ)
• 11: for iter i = 1, 2, . . . , T do
• 12: Z ←Z -γ ∂LLP(Z) ∂Z
• 13: end for
• 14: end for

BCE is still less robust since it is unbounded. Let us consider the probabilistic output σ(ˆ yi) of the deep model. Then the BCE loss is equivalent to a negative log loss on σ(ˆ yi). If the predicted probability of the label is close to zero, the loss can grow quickly to infinity. Previous works have suggested that bounded loss on the probabilistic output is theoretically more robust than unbounded ones. One common choice of bounded loss is the probabilistic MSE loss (PMSE), i.e. l(ˆ yi, zi) = ||σ(ˆ yi) - zi||22 . In that case, the training criterion is consistent with our propagation error. Empirically, both PMSE and BCE loss perform well, and thus, we instantiate our model using BCE loss when comparing it with other methods. In Section 4.4, we present a comparison between these losses, which clearly verifies our conjectures.

Fast Implementation. To efficiently build the instance graph from training data, we employ a quick similarity search python package Faiss [Johnson et al., 2017] to find the nearest neighbors. The sparse matrix multiplication LxZ can be efficiently implemented by the Scipy package. In Appendix A, we provide a detailed analysis of the complexity and convergence properties to show the efficacy of our method.

4 Experiments

In this section, we present the main empirical results of PLAIN compared with state-of-the-art baselines. More experimental results are shown in Appendix B.

4.1 Datasets

We employe a total of twelve synthetic as well as real-world datasets for comparative studies. Specifically, the synthetic ones are generated from the widely-used multi-label learning datasets. A total of nine benchmark multi-label datasets 2 are used for synthetic PML datasets generation, including Emotions, Birds, Medical, Image, Bibtex, Corel5K, Eurlex-dc, Eurlex-sm, NUS-WIDE. Note that NUS-WIDE is a largescale dataset, and we preprocess it as in [Lyu et al., 2020]. For each data example in MLL datasets, we randomly select r irrelevant labels and aggregate them with the ground-truth labels to obtain a candidate set. For example, given an instance xi and its ground-truth label set ˜ Si, we select r labels from its complementary set Y - ˜ Si. If there are less than r irrelevant labels, i.e. |Y - ˜ Si| < r, we simply set the whole training set Y as the candidate set for xi. Following the experimental settings in [Lyu et al., 2020], we choose r ∈ {1, 2, 3}, resulting in 27 (3 × 9) synthetic datasets. Furthermore, we conducted experiments on three real-world PML datasets [Zhang and Fang, 2021], including Music-emotion, Music-style, Mirflickr. These three datasets are derived from the image retrieval task [Huiskes and Lew, 2008], where the candidate labels are collected from web users and then further verified by human annotators to determine the ground-truth labels.

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

4.2 Baselines and Implementation Details

We choose six benchmark methods for comparative studies, including two MLL methods ML-KNN [Zhang and Zhou, 2007], GLOCAL [Zhu et al., 2018], and four state-of-the-art PML methods PML-NI [Xie and Huang, 2022], PARTICLE [Zhang and Fang, 2021], HALE [Lyu et al., 2020], and PMLlc [Xie and Huang, 2018]. In particular, PARTICLE and HALE are two advanced graph-based PML methods. PARTICLE [Zhang and Fang, 2021] adopts an instance-level label propagation algorithm to disambiguate the candidate labels. HALE [Lyu et al., 2020] regards the denoising procedure as a graph-matching procedure.

The parameter setups for the used methods are as follows. We fix k = 10 for all kNN-based methods, including PLAIN. For the baselines, we fix or fine-tune the hyperparameters as the suggested configurations in respective papers. For our PLAIN method, the deep model is comprised of three fully-connected layers. The hidden sizes are set as [64, 64] for those datasets with less than 64 labels, and [256, 256] for those datasets with more than 64 and less than 256 labels. For the remaining datasets, we set the hidden sizes as [512, 512]. The trade-off parameters α and β are hand-tuned from {0.001, 0.01, 0.1}. η is selected from {0.1, 1, 10}. Following [Iscen et al., 2017], we set ρ = 3. We train our deep model via stochastic gradient descent and empirically set the learning rate as 0.01 for both propagation and deep model training procedures. The number of maximum iterations is set as T = 200 for small-scale datasets and T = 50 for the large-scale NUS-WIDE dataset. Besides, weight decay is applied with a rate of 5e-5 to avoid overfitting.

For performance measure, we use three widely-used multilabel metrics, ranking loss, average precision and hamming loss [Zhang and Zhou, 2014]. Finally, we perform ten-fold cross-validation on each dataset and the mean metric values as well as the standard deviations are reported.

4.3 Experimental Results

Table 1 reports the experimental results on real-world datasets. Table 3 lists the results on synthetic datasets, where the parameter is configured with r = 3. The results of r = 1, 2 are consistent with those of r = 3 and thus are omitted. To better understand the superiority of the proposed method, we summarize the win/tie/loss counts on all synthetic datasets in Table 2. We also report the statistical testing results in Appendix B for analyzing the relative performance amongst competing algorithms. Based on these results, we can draw the following observations:

Table 3: Comparison of PLAIN with baselines on nine synthetic PML datasets (r = 3), where the best results are shown in bold face.

• The proposed PLAIN method significantly outperforms all other competing approaches. For example, on the Music-emotion and Mirflicker datasets, in terms of average precision, PLAIN achieved results superior to those of the best baselines by 6.07% and 6.94% respectively.
• According to Table 2, out of 486 statistical comparisons, six competing algorithms, and three evaluation metrics, PLAIN beats the competing methods in 82.30% cases. In particular, PLAIN wins or ties the baselines in 95.68% cases regarding average precision.
• ML-KNN and GLOCAL obtain inferior performance on many datasets, such as Medical and Eurlex-dc. The reason is that these tailoredMLLmodels regard all the candidate labels as the ground-truth and thus tend to overfit the false-positive labels.
• Two PML methods PML-NI and HALE are strong base-
• lines. In particular, PML-NI achieved the second-best results on most datasets. However, PLAIN performs significantly better than them, since their performance is restricted to the linear classifier.
• On large-scale dataset NUS-WIDE, PLAIN still outperforms other methods, which validates the effectiveness of PLAIN in handling high-volume of data.

4.4 Further Analysis

Complexity Analysis. In Table 4, we report the running time of different training stages of PLAIN, including the graph building step, label propagation step (one epoch) and the deep model training step (one epoch), on datasets with various scales. First of all, we can see that the instance graph can be fast built in a few microseconds on all datasets, with the help of Faiss package [Johnson et al., 2017]. Moreover, by utilizing the sparse property of instance graph and the fast computation ability of GPUs, the time complexity of label propagation is at the same magnitude as that of deep model training. In particular, on those datasets with fewer labels, such as Music-emotion and Image, the propagation phase is as fast as the deep model traveling the whole training dataset. In Figure 2, (a) and (b) show the parameter sensitivities of PLAIN to T and γ. We can observe that PLAIN is stable with varying values of T and γ. Specifically, PLAIN obtains high average precision even with small T and small γ. But when T = 0 (without label propagation), our PLAIN model degenerates to the trivial DNN model and thus, the performance degrades. It should also be noted that when T is too large, the performance of PLAIN slightly drops because the model tends to overfit. In summary, the proposed PLAIN model requires only a few gradient steps in the label propagation phase and can be efficiently trained.

Comparison between Loss Functions. As discussed in section 3.2, mean square error (MSE) is error-prone to the label noise. Hence, we conducted experiments to compare the performance of different loss functions, including MSE, MAE, BCE and probabilistic MSE (PMSE). The results are shown in Figure 2 (c). We can see that MAE demonstrates inferior performance and low convergence. Despite its robustness, it tends to produce harsh predictions and is opposite to the graph techniques which generate smooth outputs. MSE obtains good performance, but underperforms BCE and PMSE, since it easily overfits the false-positive labels. Finally, both BCE and PMSE demonstrate good empirical results. These observations suggest that a robust loss function is essential in successful learning from PML data.

Ablation Analysis. An ablation study would be informative to see how different components of the proposed PLAIN contribute to the prediction performance. Thus, we compare PLAIN with three variants: 1) a pure deep neural network model (DNN) that treats the candidate labels as valid ones; 2) the PLAIN model without considering label-level similarity (PLAIN w/o LS); 3) the PLAIN model without considering instance-level similarity (PLAIN w/o IS). Figure 3 reports the results on one real-world dataset as well as two synthetic datasets. In general, both graph regularizers improve the simple DNN model on most datasets and evaluation metrics. Then, by integrating the two regularizers, our PLAIN model consistently achieves the best performance. These results clearly verify the superiority of the proposed method.

5 Conclusion

In this work, we proposed a novel deep partial multi-label learning model PLAIN that copes with several limitations in existing graph-based PML methods. At each training epoch, we first involve both the instance- and label-level similarities to generate pseudo-labels via label propagation. We then train the deep model to fit the disambiguated labels. Moreover, we analyzed the time complexity and the robustness of PLAIN from both theoretical and empirical perspectives. Comprehensive experiments on synthetic datasets as well as real-world PML datasets clearly validate the efficiency, robustness, and effectiveness of our proposed method. Our work demonstrates that combining the graph and deep models together leads to high expressiveness as well as good disambiguation ability. We hope our work will increase attention toward a broader view of graph-based deep PML methods.

Acknowledgments

This work is supported by the National Key R&D Program of China (No. 2022YFB3304100) and by the Zhejiang University-China Zheshang Bank Co., Ltd. Joint Research Center. Gengyu Lyu is supported by the National Key R&D Program of China (No. 2022YFB3103104) and the China Postdoctoral Science Foundation (No. 2022M720320). Haobo Wang also wants to thank the support of the NSFC Grants (No. 62206247) and the Fundamental Research Funds for the Central Universities.