# Efficient Loss-Based Decoding on Graphs For Extreme Classification

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2018.

## Built on by (most cited first, 7 of 7)

- [A Survey on Extreme Multi-label Learning](https://mlsanity.com/paper/2210.03968/) (2022)
- [Label Encoding for Regression Networks](https://mlsanity.com/paper/2212.01927/) (2022)
- [MatchXML: An Efficient Text-label Matching Framework for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2308.13139/) (2023)
- [Learning Structured Representations by Embedding Class Hierarchy with Fast Optimal Transport](https://mlsanity.com/paper/2410.03052/) (2024)
- [The Role of Codeword-to-Class Assignments in Error-Correcting Codes: An Empirical Study](https://mlsanity.com/paper/2302.05334/) (2023)
- [Label Embedding via Low-Coherence Matrices](https://mlsanity.com/paper/2305.19470/) (2023)
- [Beyond one-hot encoding? Journey into compact encoding for large multi-class segmentation](https://mlsanity.com/paper/2510.00667/) (2025)

## Abstract (arXiv)

In extreme classification problems, learning algorithms are required to map instances to labels from an extremely large label set. We build on a recent extreme classification framework with logarithmic time and space, and on a general approach for error correcting output coding (ECOC) with loss-based decoding, and introduce a flexible and efficient approach accompanied by theoretical bounds. Our framework employs output codes induced by graphs, for which we show how to perform efficient loss-based decoding to potentially improve accuracy. In addition, our framework offers a tradeoff between accuracy, model size and prediction time. We show how to find the sweet spot of this tradeoff using only the training data. Our experimental study demonstrates the validity of our assumptions and claims, and shows that our method is competitive with state-of-the-art algorithms.