FastGRAIL: Anchor-graph-based fast adaptive partial multi-label learning with label correlations

Partial Multi-Label Learning (PMLL) has emerged as an innovative paradigm for harnessing ambiguously multi-labeled data, where each instance is associated with a set of candidate labels, and only a subset of which is credible. While model-driven adaptive graph disambiguation offers a promising approach to handle the ambiguity inherent in PMLL's set-valued label space, its practical deployment faces two critical limitations. First, constructing instance-level adaptive adjacency matrices incurs prohibitively high computational costs in large-scale scenarios. Second, existing methods often neglect label correlations, which are essential for accurate disambiguation. To address these challenges, we propose a novel Fast Adaptive Graph Disambiguation Framework via Anchors and Label Correlations (FastGRAIL). Specifically, we first introduce compositional anchor-and-instance-level adjacency matrix, constructed by representative anchors, as well as the label correlations to facilitate label disambiguation, and get a label confidence matrix. Furthermore, an efficient optimization algorithm is designed within a unified framework to address multiple subproblems. Moreover, we derive a generalization bound for FastGRAIL, which shows that lower disambiguation noise leads to a tighter bound, and that accurate label disambiguation is necessary for good generalization. Finally, extensive evaluations across 14 datasets show that FastGRAIL achieves a 2.4–15.2% improvement in key metrics over state-of-the-art methods while scaling sub-linearly with data size, confirming its superior efficiency and robustness. Code is available at https://github.com/fulfi11ing/FastGRAIL_PMLL.