Deep Graph Matching for Partial Label Learning

1 Introduction

In Partial Label Learning (PLL), each instance is associated with a set of candidate labels, among which only one is the ground-truth label [Wang et al., 2019a; Wang et al., 2022; Feng and An, 2019; Lyu et al., 2020a]. This learning problems is motivated in domains where a large number of ambiguously labeled examples are available while it is expensive to acquire complete and explicit labels, such as web mining [Luo and Orabona, 2010; Wang et al., 2019b], image classification [Cour et al., 2009; Zeng et al., 2013; Chen et al., 2017], crowdsourcing [Liu and Dietterich, 2012; Liu et al., 2018; Wang et al., 2020], etc.

Formally speaking, let X = Rd denote the d-dimensional input space, and Y = {1, 2, . . . , q} denote the output space with q class labels. The task of PLL is to induce a multiclass classifier f : X ↦→ Y from the training data D = {(xi, Si)}(1 ≤ i ≤ n) with n examples, where the instance xi ∈ X is described as a d-dimensional feature vector, the candidate label set Si = {yi1 , yi2 , . . . , yi|Si| } ⊆ Y is associated with the instance xi and |Si| represents the number of candidate labels for instance xi.

∗ indicates equal contributions.

† is the corresponding author.

Obviously, a successful PLL model rely heavily on its superior capability of disambiguating ambiguous labels. Therefore, most of existing PLL approaches [Lyu et al., 2020b] focus on how to effectively disambiguate the candidate label set and obtain the correct "instance-label" matching {(xi, yi)|1 ≤ i ≤ n} for model induction. Among these methods, [Hullermeier and Beringer, 2005] and [Zhang and Yu, 2015] adopt an averaging disambiguation strategy, which assumes each candidate label contributes equally to the learning model and assigns label for unseen instance by (weighted) averaging the outputs from all candidate labels. [Yu and Zhang, 2016] and [Feng and An, 2018] employ another disambiguation strategy named identification disambiguation, which views the ground-truth label as a latent variable first, and then refines it iteratively during the model training phase. Intuitively, the above two kinds of strategies serve for the model design from different perspective, where the former focuses on exploiting the similarity of k-nearest neighbor instances while the latter pays more attention to leveraging the distinctions of varying candidate labels.

Recently, [Lyu et al., 2021] integrates the two kinds of relationships, formulated as "instance-label" matching consistent by a predefined instance-label affinity matrix K, and propose a graph matching PLL approach, formulated as:

where, p ∈ R∑ni=1 |Si|×1 is the row-wise vectorized replica of label confidence matrix P ∈ Rn×q and the non-candidate labels have been removed when generating p. K ∈ R∑ni=1 |Si|×∑ni=1 |Si| is the instance-label affinity matrix that encodes "instance-label" matching consistent.

Although this approach has achieved competitive performance on solving PLL problem, it still suffers from some shortcomings: (i) The integrated relationship in K is manually predetermined from original features instead of learning from structural representations, which inevitably decreases the performance of the learned model. (ii) The predefined affinity matrix K characterizes the co-occurrence confidence of different "instance-label" matchings, formulated with a large scale of (∑n |Si|)2 , which significantly increases the computational cost of learning model and reduces its learning efficiency on large scale data sets.

To overcome the above shortcomings, in this paper, we propose a DeepGNN-based Graph mAtching PLL (D-GAP) approach, where the Deep Graph Neural Network (Deep-GNN) and Graph Matching (GM) are simultaneously incorporated owing to their excellent performance of excavating and exploiting the structural information of training data. Specifically, we first construct all instances and labels into two different graphs (instance graph and label graph) respectively, and then integrate them into a unified matching graph by connecting each instance to its candidate labels. Afterwards, the graph attention mechanism is adopted to aggregate and update all nodes state on the instance graph to form structural representations for each instance. Owing to the inherent characteristics of PLL problem that the prior pairwise-label relationship is always missing (i.e., the labels have no significant correlations), we remove the edges in the label graph and discard the updates to all label nodes. Finally, we conduct affinity estimation for each "instance-label" matching on the unified matching graph, and design a progressive cross-entropy loss to maximize the affinity scores between each instance and its ground-truth label.

Notably, compared with previous PLL methods, our proposed D-GAP has the following superiorities:

• Each instance node is updated via aggregating its knearest neighbors to obtain its intrinsic structural representation, which well filters potential outliers and builds more reliable "instance-label" relationship.
• Our employed "instance-label" matching affinity relationships are learned from the above structural data representations, instead of manually predetermined and remaining fixed during the training phase, which guides the proposed approach to gain higher performance.
• Such "instance-label" matching affinity relationship replaces previous "instance-label" matching consistency relationship, which significantly reduces the computational cost fromO ((∑n |Si|)2 ) to O(∑n |Si|) and improve its efficiency of learning from large-scale data.

2 RelatedWork

2.1 Averaging Disambiguation Strategy

Averaging disambiguation-based PLL approaches usually assume that each candidate label has equal contribution to the learning model and they make prediction for unseen instances by averaging the outputs from all candidate labels. [Cour et al., 2011] proposes a convex learning approach, which identifies the ground-truth label from the ambiguous label set by averaging the outputs of all candidate labels. [Hullermeier and Beringer, 2005] adopts an instance-based model, which assigns predictive labels by the voting results of its k-nearest neighbors' candidate labels. Considering the different contributions of k-nearest-neighbor instances, [Zhang and Yu, 2015] employs minimum error reconstruction criterion and they improve the prediction accuracy via k-nearest neighbors'

weighted-voting results. Obviously, the above approaches mainly focus on leveraging instance relationship while ignoring the latent label relationship, which leads to a shortcoming that the output of the ground-truth label is overwhelmed by that of other false positive labels.

2.2 Identification Disambiguation Strategy

Identification disambiguation-based PLL approaches usually pay attention to the differences of candidate labels and directly identify the ground-truth label from the ambiguous candidate label set. Existing PLL approaches following such strategy often regard the ground-truth label as a latent variable first, and then refine the latent variable and the model parameter iteratively by utilizing Expectation-Maximization procedure [Jin and Ghahramani, 2003]. Among these approaches, some of them usually incorporate the maximum likelihood criterion and obtain the optimal label via maximizing the outputs of candidate labels [Liu and Dietterich, 2012]. Others often utilize the maximum margin criterion and identify the ground-truth label according to maximizing the margin between the outputs of candidate labels and that of the non-candidate labels [Yu and Zhang, 2016]. The above approaches focus on identifying the unique ground-truth label, which avoid its outputs overwhelmed by other false positive labels and lead a better label disambiguation performance.

2.3 Disambiguation Free Strategy

Disambiguation free-based approaches usually attempt to learn from partial label data by fitting the data to some offthe-shelf learning techniques, where they can directly predict labels for unseen instances without conducting disambiguation operation. [Zhang et al., 2017] proposes an ErrorCorrecting Output Codes based PLL algorithm named PLECOC, which transfers the PLL problem into binary learning problem. [Wu and Zhang, 2018] proposes another disambiguation-free algorithm called PALOC, which enables binary decomposition for partial label data without relying on extra manipulations. Despite extensive experiments have empirically demonstrated that the above approaches can achieve competitive performance with the other disambiguation based PLL approaches, such strategy has still not been widely adopted in constructing other PLL model, since it relies heavily on the fitting degrees between the partial label data and the employed off-the-shelf learning techniques.

3 The ProposedMethod

D-GAP is a novel PLL framework based on deep graph matching scheme, which aims to excavate the structural information of training data and establish an accurate assignment relationship between instance space X and label space Y. To better introduce our motivation and make our subsequent descriptions easily understanding, we illustrate the D-GAP approach as a GM structure in Figure 1 in advance.

3.1 Assignment Graph Construction

As depicted in Figure 1, both instance space and label space are formulated as two distinct graphs G(i) = (V(i) , E(i) ) of size m(i) , where i ∈ {1, 2}, and m(1) = n, m(2) = q. The nodes V(i) in the two graphs represent the instances and labels respectively, while the edges E(i) encode their similarities. Specifically, in the instance graph G(1) , we described each instance node v(1) r ∈ V(1) (1 ≤ r ≤ n) by a d(1) - dimensional vector xr, and then the edges e(1) ∈ E(1) between each pair of instance nodes can be produced as:

where N (v(1) r ) denotes the k-nearest neighbors (measured by Euclidean distance) of v(1) r , and e(1) rs = 1 indicates a directed edge from v(1) s to v(1) r , e(1) rs = 0 otherwise. Note that, when constructing instance graph, we drop the edges that connect two instances with completely different candidate labels (i.e., Sr ∩ St = ∅), which avoids the interference of false positive instances.

In the label graph G(2) , each label node v(2) r′ ∈ V(2) (1 ≤ r′ ≤ q) is represented by a d(2) -dimensional vector

and the edges e(2) ∈ E(2) are generated following:

where the edges between different labels are dropped owing to the inherent characteristic of PLL problem that the prior pairwise-label relationship does not hold. Note that, once the label relationship can be obtained, the proposed D-GAP can still be easily extended to satisfy the problem.

After obtaining the above two graphs, we incorporate them into a unified matching graph by connecting each instance to its candidate labels, where the edges encode the "instancelabel" matching affinity relationship. Thereafter, the task of PLL is transferred to a matching (edge) selection problem between each instance and its candidate labels. And the goal of D-GAP is to obtain the accurate "instance-label" matching (edge) between G(1) and G(2) .

3.2 Modeling "Instance-Label"Matching Affinity

In order to achieve accurate "instance-label" matching between G(1) and G(2) , we apply Deep-GNN to the unified matching graph to excavate structural representation of training data, and then incorporate GM scheme to model the "instance-label" matching affinity relationship by utilizing the structural representation data.

Instance Space Given the original instance node feature {x1, x2, . . . , xn} ∈ Rd(1)×n , we employ an attention-based DeepGNN architecture (GAT) [Veliˇckovi´c et al., 2018] to compute the hidden representation of each instance node {x′1 , x′2 , . . . , x′n } ∈ Rd(1)′ ×n by attending over its k-nearest neighbors, where GAT is incorporated owing to its excellent performance on measuring the different contributions of knearest neighbors when updating graph nodes. During the process of model construction, we first transform the input features xr into higher-level features Wxr to obtain sufficient expressive power, where the shared linear transformation is parameterized by a weight matrix W ∈ Rd(1)′ ×d(1) . Then, the attention coefficient ars that encodes the importance of node vs's features to node vr can be computed as:

where h(·) = LeakyReLU(h⊤·) is a single-layer feedforward neural network, parameterized by a weight vector h ∈

R2d(1)′ , and applying with the LeakyReLU nonlinearity. ·⊤ represents transposition and || is the concatenation operation. After obtaining the attention coefficients ars, we further employ multi-head attention mechanism [Vaswani et al., 2017] to stabilize the learning process, and L independent attention mechanisms execute the transformation of xr → x′r |L1 , then their features are averaged, resulting the final output feature representation:

where alrs is the attention coefficient computed by the l-th attention mechanism (hl ), andW l is the corresponding input linear transformation's weight matrix.

Label Space Due to the lack of pairwise-label relationship in PLL, each node in label graph G(2) can only be updated by itself. Therefore, when given the original label node feature {y1, y2, . . . , yq}, to obtain sufficient expressive power, we obtain their structural representations by directly transferring the input yr′ to the corresponding higher-level

where H ∈ Rd(2)×d(2)′ is the linear transform matrix. Here, we emphasize again that once the label relationship can be obtained, the label graph can be easily extended to be updated to obtain more expressively structural label representations.

"Instance-Label" Matching Affinity After obtaining the structural representations from both feature and label space, we incorporate the GM scheme to model the"instance-label" matching affinity relationship, where the affinities between each instance and its candidate labels are calculated by

where ys′ ∈ Sr and d(1)′ = d(2)′ . Furthermore, we dig out the superiority of our designed "instance-label" matching affinity relationship. On one hand, compared with previous instance-label relationship that directly constructed from original training data, our "instance-label" matching affinity relationship is designed from the learned structural training data, which can provide more robust "instance-label" relationship for model induction. On the other hand, compared with the "instance-label" matching consistency relationship in [Lyu et al., 2021], which describes the co-occurrence confidence of two different "instance-label" matchings, our "instance-label" matching affinity relationship directly characterizes the matching confidence between each instance and its candidate labels, which significantly reduces the computational complexity by an order of magnitude (from O ((∑n |Si|)2 ) to O(∑n |Si|)). Therefore, our proposed DGAP is not only effective but also efficient.

3.3 Progressive Cross-Entropy Loss

Due to the existence of noisy labels in candidate label set, if we directly employ the standard cross-entropy loss to induce a model, it will naturally overfit these noisy labels, thereby achieving poor learning performance. To address this issue, motivated by [Lv et al., 2020], we design a progressive crossentropy loss to guide the learning process,

where ℓ is the standard cross-entropy loss, zrs is a weight value that encodes the confidence of the s-th label being the ground-truth label of the r-th instance, uSr s is the s-th element of uSr and uSr is a vector that {i}yi∈Sr -th elements in uSr equals 1 and others equal 0. During the training process, we optimize the matching affinity ors and the weight zrs in an iteration manner. In order to put more weights on possible labels, the weight zrs is directly estimated by using current "instance-label" matching affinity, i.e.,

In this fashion, the correct "instance-label" matchings are aggregately and progressively identified. And under the ideal situation, the label with weight 1 (i.e., zrs = 1) indicates we have identified the ground-truth label successfully.

4 Experiments

4.1 Experimental Settings

To evaluate the performance of the proposed D-GAP method, we implement experiments on four UCI data sets and six realworld data sets: (1) Synthetic data sets. Under different configurations of two controlling parameters (i.e. p and r), four UCI data sets generate 84 (7 × 3 × 4) synthetic data sets [Cour et al., 2011], where p ∈ {0.1, 0.2, . . . , 0.7} is the proportion of partial-label examples and r ∈ {1, 2, 3} is the number of false candidate labels. (2) Real-world data sets. These data sets are collected from four task domains: (A) Facial Age Estimation [FG-NET]; (B) Object Classification [MSRCv2]; (C) Bird Sound Classification [BirdSong]; (D) Automatic Face Naming [Lost] [SoccerPlayer] [YahooNews]. Table 1 summarize the characteristics of these data sets, including the number of examples (EXP*), the number of features (FEA*), and the whole/average number of class labels (CL*/AVG-CL*).

Meanwhile, we employ nine baselines for comparative studies: PL-KNN [Hullermeier and Beringer, 2005], CLPL [Cour et al., 2011], LSB-CMM [Liu and Dietterich, 2012], IPAL [Zhang and Yu, 2015], M3PL [Yu and Zhang, 2016], PL-ECOC [Zhang et al., 2017], PRODEN [Lv et al., 2020] and GM-PLL [Lyu et al., 2021], where the configured parameters are set via the suggestions in respective literatures.

In our experiments, we focus on how to select more accurate "instance-label" matchings during the training process, thus our experiments are biased on evaluating the disambiguation capability of learning model. With regard to the predictions for unseen examples, we just maximize the weighted voting results of their k-nearest neighbors from training examples like [Zhang and Yu, 2015]. We adopt tenfold cross-validation to train the model and record the experimental results in Figure 2, Table 2 and 3.

4.2 Experimental Results Synthetic Data Sets

Figure 2 illustrates the accuracy of each comparing method on 84 synthetic data sets as p increases from 0.1 to 0.7 with the step-size of 0.1. Out of 756 (9 approaches × 84 data sets) statistical comparisons show that:

• Among these comparing approaches, D-GAP achieves superior performance against LSB-CMM, CLPL, PLAGGD and M3PL in all cases. And compared with PLKNN, PL-ECOC, IPAL and GM-PLL, it also achieves superior performance in 97.4%, 93.2%, 99.2% and 96.7% cases, respectively.
• Among these synthetic data sets, D-GAP outperforms all comparing approaches on Vehicle, Satimage and Nuswide data sets. Especially for the large-scale Nuswide data set, D-GAP also shows superior performance in terms of both effectiveness and efficiency.
• Overall, among 756 statistical comparisons, D-GAP outperforms other approaches in 747 cases and achieves comparable performance in 5 cases (total: 99.4%).

Real-World Data Sets

The comparison results on real-world data sets are reported in Table 3-2. According to Table 3-2, it is clear to observe that:

• Compared with the approaches with different disambiguation strategies, D-GAP outperforms averagingbased approaches in 97.9% cases, identification-based approaches in 91.7% cases and disambiguation-free approaches in 83.3% cases, respectively.
• For different data sets, D-GAP achieves the best performance on most data sets, including Lost, MSRCv2, SoccerPlayer, YahooNews and FG-NET data sets.
• Among 108 statistical comparisons, D-GAP outperforms other comparing methods in 99 cases and achieves comparable performance in 6 cases (total: 97.2%).

4.3 Computational Complexity

Due to page limit, we illustrates the time complexity comparison between D-GAP and other comparing approaches in Technical Appendix. Our proposed D-GAP is highly efficient, and we attribute its efficiency to two aspects: (i) The GAT operation is efficient. The single attention operation can be parallelized across all edges and nodes, and multi-head attention can also be parallelized due to its fully independence. Thus, the time complexity can be directly expressed as O(nd(1)d(1)′ + nkd(1)′ ). (ii) The employed "instancelabel" relationship is efficient. The previous matching consistency relationship with complexity of O((∑n |Si|)2 ) is replaced by matching affinity relationship with complexity of O(∑n |Si|), which significantly reduces the computational cost and improves the efficiency of learning model.

4.4 Parameter and Convergence Analysis

We study the sensitivity of D-GAP with respect to its two parameters: k and L. Figure 3(a)-(b) shows the performance of D-GAP under different parameter configurations on Lost data set. From Figure 3, we can find that the values of k and L have great influence on the performance of the proposed framework. We set k among {3, 5, 8, 10, 15, 20} and L among {3, 5, 10, 20, 30} via cross-validation. Meanwhile, we conduct the convergence analysis of D-GAP on both Lost and MSRCv2 data sets. Figure 3(c)-(d) illustrate the convergence curves of the optimization process of D-GAP. We can observe that the loss gradually decreases as t increases. Therefore, the convergence of D-GAP is empirically demonstrated.

5 Conclusion

In this paper, we proposed a DeepGNN-based graph matching PLL approach, where both DeepGNN and GM are employed to model a robust "instance-label" matching affinity relationship for model induction. Compared with previous PLL approaches, our employed matching affinity relationship is learned from structural data representations, which can guide the model to obtain more accurate "instance-label" matchings. Meanwhile, such matching affinity relationship alleviates the high computation consumption problem in previous graph matching PLL approaches, which extends the learning power to large-scale data sets. Extensive experiments have also demonstrated the effectiveness and efficiency of our proposed approach.

Acknowledgements

This work was supported in part by the Fundamental Research Funds for the Central Universities (No. 2020YJS036), the National Natural Science Foundation of China (No. 61872032, No. 62072027, No. 62076021), the Beijing Natural Science Foundation(No. 4202058, No. 4202057, No. 4202060), and in part by the National Key Research and Development Project (No. 2018AAA0100300).