Introduction
Multi-label classification (MLC) is a fundamental task in machine learning where each instance can be associated with multiple labels simultaneously. A critical challenge in MLC is effectively modeling the dependencies between labels. For example, in document tagging, the presence of the label "Elections" significantly increases the probability of the label "Politics."
Traditional methods like Binary Relevance ignore these dependencies, while sequential models such as Classifier Chains or Seq2Seq architectures model them step-by-step. However, sequential models are inherently non-parallelizable, require a fixed label ordering, and are prone to error propagation. This paper introduces Label Message Passing (LaMP), a graph-based approach that treats labels as nodes in a network, enabling parallelized and interpretable label dependency modeling.
Methodology: Label Message Passing (LaMP)
LaMP leverages Message Passing Neural Networks (MPNNs) to capture interactions between input features and labels, as well as among the labels themselves. The architecture consists of two primary stages:
- Feature-to-Label Message Passing (FMP): Input features (e.g., text embeddings or image regions) are transformed into feature nodes. An attention mechanism allows each label node to selectively aggregate information from relevant parts of the input.
- Label-to-Label Message Passing (LaMP): This core component models label correlations. Label nodes exchange messages across a graph. If the label structure is unknown, a fully connected graph with self-attention is used to learn dependencies dynamically. If a prior hierarchy or graph is available, it can be used to constrain the message passing.
The model is trained with auxiliary "intermediate probes"—classifiers attached to the label nodes at each message-passing step—to encourage the refinement of predictions throughout the process.
Experimental Setup
The authors evaluated LaMP across eight diverse datasets spanning different domains:
- Text: Reuters-21578, RCV1-V2, Bibtex, Bookmarks, Delicious.
- Biology: TFBS (transcription factor binding sites).
- Chemistry: SIDER (drug side effects).
- Images: NUS-WIDE.
These datasets vary in label set size (from 27 to 983) and density, providing a robust benchmark for the model's versatility.
Key Results
LaMP demonstrates competitive or superior performance compared to state-of-the-art baselines like RNN Seq2Seq and SPEN. Notably, LaMP excels in Macro-F1 scores, suggesting it is particularly effective at identifying rare labels that sequential models might overlook.
Beyond accuracy, LaMP offers significant computational advantages. By avoiding sequential bottlenecks, it achieves a 1.7x speedup in training and a 5.0x speedup in inference compared to Seq2Seq models. Furthermore, the attention weights provide a "glass-box" view of the model's reasoning, allowing researchers to visualize which input features drive specific label predictions and interactions.
Conclusion and Future Work
LaMP provides a scalable, parallelizable, and interpretable framework for multi-label classification. While it slightly trails Seq2Seq models in "Subset Accuracy"—likely because Seq2Seq explicitly optimizes for the entire label sequence—its gains in F1 metrics and speed make it a powerful alternative.
Future research will focus on scaling LaMP to Extreme Multi-Label Classification (XMLC) scenarios with millions of labels, potentially through graph sparsification techniques, and further refining the Feature-to-Feature message passing to better capture complex input structures.
Summary updated