Neural Message Passing for Multi-label Classification

Jack Lanchantin, Arshdeep Sekhon, Yanjun Qi

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:

  1. 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.
  2. 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.
Overview of the LaMP architecture showing the two-stage message passing process from input features to final label predictions.

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.

Comparison of LaMP variants against state-of-the-art baselines across multiple datasets. Bold values indicate the best performance.

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

BibTeX
@inproceedings{lanchantin2019neural,
  author = {Jack Lanchantin and Arshdeep Sekhon and Yanjun Qi},
  title = {{Neural Message Passing for Multi-label Classification}},
  booktitle = {ECML/PKDD},
  year = {2019},
  doi = {10.1007/978-3-030-46147-8\_9},
}
Figure