  Partition-based methods are increasingly-used in extreme multi-label
classification (XMC) problems due to their scalability to large output spaces
(e.g., millions or more). However, existing methods partition the large label
space into mutually exclusive clusters, which is sub-optimal when labels have
multi-modality and rich semantics. For instance, the label "Apple" can be the
fruit or the brand name, which leads to the following research question: can we
disentangle these multi-modal labels with non-exclusive clustering tailored for
downstream XMC tasks? In this paper, we show that the label assignment problem
in partition-based XMC can be formulated as an optimization problem, with the
objective of maximizing precision rates. This leads to an efficient algorithm
to form flexible and overlapped label clusters, and a method that can
alternatively optimizes the cluster assignments and the model parameters for
partition-based XMC. Experimental results on synthetic and real datasets show
that our method can successfully disentangle multi-modal labels, leading to
state-of-the-art (SOTA) results on four XMC benchmarks.
