# Bonsai -- Diverse and Shallow Trees for Extreme Multi-label Classification

arXiv: https://arxiv.org/abs/1904.08249 · HTML: https://mlsanity.com/paper/1904.08249/

## Key facts

- Cited by 61 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2019.

## Built on by (most cited first, 30 of 61)

- [Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2110.00685/) (2021)
- [LightXML: Transformer with Dynamic Negative Sampling for High-Performance Extreme Multi-label Text Classification](https://mlsanity.com/paper/2101.03305/) (2021)
- [ECLARE: Extreme Classification with Label Graph Correlations](https://mlsanity.com/paper/2108.00261/) (2021)
- [DeepXML: A Deep Extreme Multi-Label Learning Framework Applied to Short Text Documents](https://mlsanity.com/paper/2111.06685/) (2021)
- [DECAF: Deep Extreme Classification with Label Features](https://mlsanity.com/paper/2108.00368/) (2021)
- [NGAME: Negative Mining-aware Mini-batching for Extreme Classification](https://mlsanity.com/paper/2207.04452/) (2022)
- [Extreme Multi-label Learning for Semantic Matching in Product Search](https://mlsanity.com/paper/2106.12657/) (2021)
- [The Effect of Metadata on Scientific Literature Tagging: A Cross-Field Cross-Model Study](https://mlsanity.com/paper/2302.03341/) (2023)
- [Multi-granular Legal Topic Classification on Greek Legislation](https://mlsanity.com/paper/2109.15298/) (2021)
- [On Missing Labels, Long-tails and Propensities in Extreme Multi-label Classification](https://mlsanity.com/paper/2207.13186/) (2022)
- [ELIAS: End-to-End Learning to Index and Search in Large Output Spaces](https://mlsanity.com/paper/2210.08410/) (2022)
- [Open Vocabulary Extreme Classification Using Generative Models](https://mlsanity.com/paper/2205.05812/) (2022)
- [CascadeXML: Rethinking Transformers for End-to-end Multi-resolution Training in Extreme Multi-label Classification](https://mlsanity.com/paper/2211.00640/) (2022)
- [SemEval-2025 Task 5: LLMs4Subjects -- LLM-based Automated Subject Tagging for a National Technical Library's Open-Access Catalog](https://mlsanity.com/paper/2504.07199/) (2025)
- [Top-k eXtreme Contextual Bandits with Arm Hierarchy](https://mlsanity.com/paper/2102.07800/) (2021)
- [InceptionXML: A Lightweight Framework with Synchronized Negative Sampling for Short Text Extreme Classification](https://mlsanity.com/paper/2109.07319/) (2021)
- [Propensity-scored Probabilistic Label Trees](https://mlsanity.com/paper/2110.10803/) (2021)
- [Label Disentanglement in Partition-based Extreme Multilabel Classification](https://mlsanity.com/paper/2106.12751/) (2021)
- [A Survey on Extreme Multi-label Learning](https://mlsanity.com/paper/2210.03968/) (2022)
- [PINA: Leveraging Side Information in eXtreme Multi-label Classification via Predicted Instance Neighborhood Aggregation](https://mlsanity.com/paper/2305.12349/) (2023)
- [SemSup-XC: Semantic Supervision for Zero and Few-shot Extreme Classification](https://mlsanity.com/paper/2301.11309/) (2023)
- [Towards Memory-Efficient Training for Extremely Large Output Spaces -- Learning with 500k Labels on a Single Commodity GPU](https://mlsanity.com/paper/2306.03725/) (2023)
- [Recent Advances in Hierarchical Multi-label Text Classification: A Survey](https://mlsanity.com/paper/2307.16265/) (2023)
- [Generalized test utilities for long-tail performance in extreme multi-label classification](https://mlsanity.com/paper/2311.05081/) (2023)
- [Fine-grained Generalization Analysis of Vector-valued Learning](https://mlsanity.com/paper/2104.14173/) (2021)
- [Long-tailed Extreme Multi-label Text Classification with Generated Pseudo Label Descriptions](https://mlsanity.com/paper/2204.00958/) (2022)
- [Hypergraph Foundation Model](https://mlsanity.com/paper/2503.01203/) (2025)
- [Annif at SemEval-2025 Task 5: Traditional XMTC augmented by LLMs](https://mlsanity.com/paper/2504.19675/) (2025)
- [DNB-AI-Project at SemEval-2025 Task 5: An LLM-Ensemble Approach for Automated Subject Indexing](https://mlsanity.com/paper/2504.21589/) (2025)
- [Curiosity Meets Cooperation: A Game-Theoretic Approach to Long-Tail Multi-Label Learning](https://mlsanity.com/paper/2510.17520/) (2025)

## Abstract (arXiv)

Extreme multi-label classification (XMC) refers to supervised multi-label learning involving hundreds of thousand or even millions of labels. In this paper, we develop a suite of algorithms, called Bonsai, which generalizes the notion of label representation in XMC, and partitions the labels in the representation space to learn shallow trees. We show three concrete realizations of this label representation space including : (i) the input space which is spanned by the input features, (ii) the output space spanned by label vectors based on their co-occurrence with other labels, and (iii) the joint space by combining the input and output representations. Furthermore, the constraint-free multi-way partitions learnt iteratively in these spaces lead to shallow trees. By combining the effect of shallow trees and generalized label representation, Bonsai achieves the best of both worlds - fast training which is comparable to state-of-the-art tree-based methods in XMC, and much better prediction accuracy, particularly on tail-labels. On a benchmark Amazon-3M dataset with 3 million labels, bonsai outperforms a state-of-the-art one-vs-rest method in terms of prediction accuracy, while being approximately 200 times faster to train. The code for Bonsai is available at urlhttps://github.com/xmc-aalto/bonsai