Abstract
In modern multilabel classification problems, each data instance belongs to a small number of classes from a large set of classes. In other words, these problems involve learning very sparse binary label vectors. Moreover, in large-scale problems, the labels typically have certain (unknown) hierarchy. In this paper we exploit the sparsity of label vectors and the hierarchical structure to embed them in low-dimensional space using label groupings. Consequently, we solve the classification problem in a much lower dimensional space and then obtain labels in the original space using an appropriately defined lifting. Our method builds on the work of (Ubaru & Mazumdar, 2017), where the idea of group testing was also explored for multilabel classification. We first present a novel data-dependent grouping approach, where we use a group construction based on a low-rank Nonnegative Matrix Factorization (NMF) of the label matrix of training instances. The construction also allows us, using recent results, to develop a fast prediction algorithm that has a logarithmic runtime in the number of labels. We then present a hierarchical partitioning approach that exploits the label hierarchy in large scale problems to divide up the large label space and create smaller sub-problems, which can then be solved independently via the grouping approach. Numerical results on many benchmark datasets illustrate that, compared to other popular methods, our proposed methods achieve competitive accuracy with significantly lower computational costs.
Introduction
Extreme Multilabel Classification (XMLC) presents a significant challenge in modern machine learning. Applications such as tagging Wikipedia articles or product recommendation involve label spaces ($d$) that can reach millions, while any single instance typically only belongs to a very small subset ($k$) of these labels. This extreme sparsity is a defining characteristic of the problem.
Standard One-versus-All (OvA) approaches, which train a separate classifier for every label, become computationally infeasible at this scale. While tree-based and embedding-based methods have been proposed, they often struggle with high training latency or expensive "lifting" steps to recover labels from compressed representations. This paper introduces He-NMFGT, a framework that leverages hierarchical partitioning and data-driven group testing to achieve high accuracy with logarithmic prediction time and efficient training.
Methodology: He-NMFGT
The core of the proposed approach is Multilabel Group Testing (MLGT). Instead of training $d$ classifiers, the system trains $m$ classifiers ($m \ll d$) on groups of labels. The framework introduces three primary innovations to optimize this process.
Data-dependent Grouping (NMF-GT)
Unlike previous group testing methods that relied on random groupings, NMF-GT uses Symmetric Nonnegative Matrix Factorization (symNMF) on the label correlation matrix. By grouping labels that frequently co-occur in the training data, the individual binary classifiers become more accurate, as they capture meaningful semantic clusters.
Hierarchical Partitioning
For datasets with millions of labels, performing NMF on the full correlation matrix is computationally prohibitive. The authors employ graph partitioning techniques to decompose the massive label space into smaller, independent sub-problems. These sub-problems are then solved in parallel using the grouping approach.
Training and Fast Decoding
The training phase involves constructing a group testing matrix $A$ and training $m$ binary classifiers. For prediction, the system utilizes the SAFFRON framework from coding theory to achieve $O(k \log d)$ prediction time, identifying relevant labels almost instantaneously.
Experimental Results
The researchers evaluated He-NMFGT on a variety of benchmarks, ranging from medium-scale (Mediamill, Bibtex) to extreme-scale (WikiLSHTC with 325k labels, Amazon-670K).
Efficiency and Speed
He-NMFGT demonstrated significant advantages in prediction latency. On the WikiLSHTC dataset, it achieved a prediction time of 0.8ms per instance, outperforming SLEEC (5.7ms) and Parabel (1.2ms). Training efficiency was also competitive, often reaching the accuracy of OvA methods using only 15-20% of the training data.
Accuracy
On large-scale datasets like Wiki10 and Amazon-670K, the method achieved Precision@k scores that were competitive with or superior to state-of-the-art methods like Parabel and PfastreXML. The data-dependent grouping proved particularly effective in maintaining high precision while reducing the number of required classifiers.
Conclusion and Future Work
He-NMFGT offers a scalable solution for XMLC by treating classification as a sparse signal recovery problem. By exploiting label correlations through NMF and managing scale via hierarchical partitioning, it bypasses the linear complexity of traditional methods.
Future work includes optimizing the symNMF process, which remains computationally intensive, and refining partition boundaries to better capture cross-partition correlations. Additionally, migrating the implementation from MATLAB to C++ could further enhance real-time performance for web-scale applications.
Summary updated