Abstract
Partial Label Learning (PLL) aims to learn from the data where each training example is associated with a set of candidate labels, among which only one is correct. The key to deal with such problem is to disambiguate the candidate label sets and obtain the correct assignments between instances and their candidate labels. In this paper, we interpret such assignments as instance-to-label matchings, and reformulate the task of PLL as a matching selection problem. To model such problem, we propose a novel Graph Matching based Partial Label Learning (GM-PLL) framework, where Graph Matching (GM) scheme is incorporated owing to its excellent capability of exploiting the instance and label relationship. Meanwhile, since conventional one-to-one GM algorithm does not satisfy the constraint of PLL problem that multiple instances may correspond to the same label, we extend a traditional one-to-one probabilistic matching algorithm to the many-to-one constraint, and make the proposed framework accommodate to the PLL problem. Moreover, we also propose a relaxed matching prediction model, which can improve the prediction accuracy via GM strategy. Extensive experiments on both artificial and real-world data sets demonstrate that the proposed method can achieve superior or comparable performance against the state-of-the-art methods.
Introduction
In many real-world scenarios, obtaining perfectly labeled data is difficult. Instead, we often encounter "partial labels"—a set of candidate labels where only one is correct. For example, in an image of a news event, a caption might mention three people, but a face-detection algorithm doesn't know which name belongs to which face. This is the core challenge of Partial Label Learning (PLL).
The primary task in PLL is "disambiguation": identifying the true label hidden among the decoys. Existing methods often rely on simple local heuristics, like $k$-nearest neighbors, which can ignore broader structural patterns or the "dissimilarity" between instances. This paper moves beyond local neighborhoods by treating the entire labeling task as a global matching problem.
The GM-PLL Framework
The authors introduce GM-PLL (Graph Matching based Partial Label Learning). Their approach treats the instance space and the label space as two separate graphs, reformulating PLL as a matching selection problem.
Graph Formulation and Many-to-One Matching
Instances are nodes in one graph, and potential labels are nodes in another. Edges between instances represent their similarity or dissimilarity. Standard graph matching is typically "one-to-one" (one node matches exactly one other). However, in classification, many different instances can share the same label (e.g., many photos of "tigers"). The authors extended traditional probabilistic matching algorithms to handle this many-to-one constraint.
Affinity Matrix and Prediction
The "brain" of the model is the Affinity Matrix ($K$), which encodes prior knowledge about which instance-label assignments are compatible. Crucially, it considers both similarity and dissimilarity; if two images are very dissimilar, they are unlikely to share the same label. For unseen test data, a relaxed matching prediction model is used. It first estimates a candidate label set for the new instance using its neighbors and then applies the graph matching strategy to pick the most confident label.
Experimental Evaluation
The model was evaluated on nine controlled UCI datasets (manually corrupted with "false positive" labels) and six real-world datasets, including face naming (Lost, Soccer Player, Yahoo! News), image classification (MSRCv2), facial age estimation (FG-NET), and audio classification (BirdSong).
Performance and Robustness
GM-PLL consistently outperformed or matched eight state-of-the-art PLL algorithms. On the Lost dataset, it achieved a classification accuracy 40.5% higher than the classical PL-KNN method. As shown in the experimental results across various datasets, GM-PLL's performance remains stable even as the proportion of partial-label examples increases, demonstrating significant robustness against label ambiguity.
Conclusion
GM-PLL reformulates PLL as a graph matching problem, allowing the model to leverage complex structural relationships. By extending graph matching to support many-to-one constraints and utilizing dissimilarity information, the framework effectively disambiguates noisy candidate label sets. While the prediction stage is more computationally intensive than simpler models, the gains in accuracy and robustness make it a powerful tool for complex real-world labeling tasks.
Summary updated