Label Disentanglement in Partition-based Extreme Multilabel Classification
Authors: Xuanqing Liu
Wei-Cheng Chang
Hsiang-Fu Yu
Cho-Jui Hsieh
Inderjit S Dhillon
Venue: NeurIPS 2021 Poster (2021)
Keywords: Extreme multilabel classification

Abstract: 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.

Label Disentanglement in Partition-based Extreme Multilabel Classification
Xuanqing Liu" Department of Computer Science UCLA xqliu@cs. weliu@cssuula..de. ucla.edu
Wei-Cheng Chang Amazon Inc. wei weicheng. cmu@gmail com
Hsiang-Fu Yu Amazon Inc. rofu. yu@gaiu@@mai.coo
Cho-Jui Hsich Department of Computer Science UCLA chohsieh@cs ucla. edu
Inderjit Dhillon
Amazon Inc & UT Austin inderjit@ce wtwxastees.... edu
Abstract
Partition-based methods increasingly-use 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 semanties. For instance, the label "Apple" be the fruit 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 optimization problem, with the objective of maximizing precision rates. This leads to an efficient algorithm to form flexible and overlapped label clusters, and 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-modes labels, leading to state-of-the-art (SOTA) results four XMC benchmarks.
Introduction
The eXtreme Multi-label Classification (XMC) task is to find relevant labels from an enormous output space of candidate labels, where the size is in the order of millions more (II B
5 etc.)
This problem is of interest in both academia and industry: for instance, tagging a web page given its contents from tens of thousands of categories [6;; finding few products that customer will purchase from among an enormous catalog on online retail stores 77: or recommending profitable keywords given an item/product from millions of advertisement keywords [8]
The XMC problem challenging not only because the data scalability (e.g., the number of instances, features, and labels are of the scale of millions or more), but also due to the label sparsity issue where there is little training signal for long-tailed labels. To tackle these issues, most prevailing XMC algorithms
a partition-bact based approach. Instead of ranking the entire set of millions of labels, they partition the label space into smaller mutually-exclusin clusters. Each instance is only mapped one few label clusters based matching model, and then ranking is only conducted within the smaller subset of labels. Some exemplars are Parabel { eXtreme Text (9) AttentionXML. [0]
XR-Linear [II] and X- Transformer [1]
Work done while Xuanqing was interning at Amazon Inc. Code will be released at htthttts///gthhhi com/
amzn pecos
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Partitioning labels into mutually-exxllsse clusters may not be ideal. When labels are semantically complex and multi-modal, it is more natural assign a label multiple semantic clusters. In product categorization, for instance, the tag "belt" can be related to vehicle belt (under "vehicle accessories" category), or man's s belt (under "clothing" category). Assigning "belt" to just one of the clusters but not the other is likely to cause mismatch for certain queries. To solve this problem, we reformulate the label clustering step as an assignment problem, where each label can be assigned to multiple clusters to allow disentanglement of mixed semantics. Further, we formulate learning optimal assignments by maximizing the precision as an optimization problem, and propose efficient solvers that automatically learn good label assignment based on the current matching models. With this formulation, we apply our algorithm to alternatively refine label assignments and matching model in existing partition- based XMC methods to boost their performance. Similar idea be found in 13 14 however, our tree structures are constructed in one pass with hierarchical k-means. Our contributions be summarized below:
We propose novel way to obtain label assignments that disentangle multi-modal labels to multiple clusters.
Unlike previous methods that partition the label set before training, propose an optimization- based framework that allows optimizing label assignment with the matching and ranking modules inside partition-based based XMC solver. Our method is plug-and- play it is orthogonal to the models so most of the partition-based methods can benefit from our method.
Our proposed solution yields consistent improvements over two leading partition-based methods, XR-Linear [T]] and X-Transformer [12]. Notably, with the concatenation of tfidf features and X-Transformer embeddings, we achieve new SOTA results on four XMC benchmark datasets.
2 Related Work
2.1 XMC literature
Sparse Linear Models Sparse linear one-versus-rest (OVR) methods such as DiSMEC [4] ProXML [13. PDSparse [66,, PPDSparse 17 explore parallelism speed up the algorithm and
reduce the model size by truncating model weights to encourage sparsity. OVR approaches are also building blocks for many other XMC approaches. For example, in Parabel [8], SLICE [18]
X- X-Transformer
[2]. linear OVR classifiers with negative sampling are used.
Partition-based Methods The efficiency and scalability of sparse linear models can be further improved by incorporating different partitioning techniques on the label spaces. For instance, Parabel [8] partitions the labels through balanced 2-means label tree using label features constructed from the instances. Other approaches attempt to improve on Parabel, for instance, eXtremeTexx [9].
Bonsai [1)] NAPKINXC [20). and XR-Lincar [I]] relax two main constraints in Parabel by: 1)
allowing multi-way instead of binary partitions of the label set at each intermediate node, and 2)
removing strict balancing constraints on the partitions. More recently, AttentionXMLL [I0] uses BiLSTMs and label-aware attention replace the linear functions Parabel, and warm-up training the models with hierarchical label trees. In addition, AttentionXML considers various negative sampling strategies on the label space to avoid back-propagating the entire bottleneck classifier layer.
Graph-based Methods SLICE 18 uses an approximate nearest neighbor (ANN) graph as an indexing structure over the labels. For a given instance, the relevant labels can be found quickly via ANN search. SLICE then trains linear OVR classifiers with negative samples induced from ANN. Graph-based partitions can be viewed as extension of tree-based partitions, where at each layer of the tree, random edges are allowed to connect two leaf nodes to further improve connectivity. Nevertheless, such construction of overlapping tree structures is fully unsupervised, and is agnostic to the data distribution or training signals of the downstream XMC problem.
2.2 Overlapped Clustering
Finding overlapped clusters has been studied in the unsupervised learning literature 21 22 For example, Cleuziou et al. [22] extend K K-means with multi- mulli-assignments based coverage, but

---

tends to yield imbalanced clusters. This issue was later improved by Lu et al. (23 with sparsity constraints. Recently, Whang al. [24] propose variants of k-mean objectives with flexible clustering assignment constraints to trade-off the degree of overlapping. However, all these unsupervised approach cannot be optimized with existing partition- -aased XMC methods.
Go
Matcher
=2
G
10
C2=
Ranker
U.B.B.R.. A.B.A......... #
= =
S4
Root node
Intermediate node
Leaf node
* Label
this example)
Figure 1:
An illustration of partition-bal -ased XMC models. The matcher is a tree structured model similar to Parabel XR-Linear. In this diagram, the hierarchical label tree has depth of 3, branching factor of 2, number clusters 4, and number of labels == 16.
3 Background of partition-based XMC
The XMC problem can be characterized as follows: given an input instance æ E R' and set of labels T. = {1, .....,,7. L.). find model that retrieves top relevant labels L efficiently. The model parameters are estimated from the training dataset {(z;, y:) i = 1...., n where
{0, 1] denotes the relevant labels for æ; from the label space L. We further denote X E Rand as the feature matrix and Y E 1R= as the label matrix.
Partition- based XMC methods rely on label space partitioning to screen out irrelevant labels before running the ranking algorithm. They often have the following three components (depicted in Figure [[):
The cluster assignments, where set of labels are assigned each cluster. Assuming there are K ..... }
to denote the labels assigned to cluster i, and UK S L. The clusters are constructed by K means on label features, such that the clusters (S, ;=1 exclusive and unaware of the matcher M and ranker R. since clustering typically performed only once before the matcher and ranker are trained. On the contrary, as we will see shortly, our new method provides way refine cluster assignments based the matcher and is able to effectively unveil multimodal labels.
clusters, we use S, = {Gi ......
{ are mutually
The matcher, which matches the input data æ; IRdd to a small set of candidate label clusters
M: 2. + S2.. St), b b.k. K.
Each label set Sè contains small fraction of labels few hundreds), and b is called the beam size. One recursive implementation of matcher is seen in XR-Linear [II] where inside the matcher, there a tree constructed by recursive K K-means clustering. On each level of the tree, a maximum of nodes is selected according to the scores obtained from linear models. After that, all siblings of nodes will be expanded at the next level repeat this process recursively until b leaves obtained, which results in the match set {S1, Sz.... Sp}. J. See the "Matcher" block in Figure [
The ranker, which ranks the candidate labels collected from the matcher, with > denoting the ranking order:
R :M(())) + l()) > ((2) x .... B(w))
b
(2)
where L22) (.. (())) USS.
S.
Lastly, top-k labels returned the final prediction. See the "Ranker" block of Figure [
Partition-basee XMC typically assumes labels in the same cluster are similar, and thus when training the ranker, they focus distinguishing the labels (and the corresponding samples) within each cluster.

---

Taking the widely used linear ranker as an example, they often assign a weight vector for each label. The weight vector we for label can be obtained by the following training objective:
min
Σ
C(a, we; +1) + Σ
(( we: w);-
(3)
BED pastiive
where ((.,)) is the loss function (e.g., squared- hinge loss); D Possiiive and D Dnegative are the positive and negative samples for label l. In XMC, is not efficient to collect all non-positive data D prssitive as the negative part to train wy; instead, they often sample the "hard negatives" which is a tiny subset Dnegative C D \ D positive Different negative sampling changes the loss function and the final results. For instance, in Parabel [8] and XR-L.near [TT] 'D uegativv are the examples having similar labels but not e itself, based on the intuition that the learning can be more efficient by separating similar but different labels. In other words,
Prositive {a. | E yi Dnegative = {ax; 1 E y: but "similar").
(4)
The label similarity information is hidden in the cluster assignments ....... ,K, with the assumption that similar labels are clustered.
4
Proposed Method
4.1
Motivation
The central idea of the partition-based XMC methods is partition labels into disjoint clusters, such that labels in each cluster share similar semantics. This relies on the unimodal assumption that each label only represents a pure, uniform semantic across all positive samples. However, observe in practice that this assumption may not hold in general. Given labels that have multi-modal semantics, is natural to seek method disentangle their semantics from each other and treat each semantic as a separate label, and further assign them to different clusters. To achieve this, we weaken the requirement that label clusters under leaf nodes are mutually exclusive S, n Sy 2, to a more suitable, limited overlapping: for any label & E {1,2...., L}, it can appear at most A-times among {Si, Skk
Although allowing label clusters to overlap with each other does not explicitly disentangle the semantics of label, it paves the way for learning multiple versions of weights for the same label. Take the linear model in Eq. (3) for simplicity, label l is seen in both cluster S and Sp. so we will have two weight vectors w a and wa for the same label. w. and wn trained separately in Eq. (3). where they have different negative examples DA negative and D Deg negative Recall in Eq. (4) the negative part of the data relics on the label similarity induced from clusters SA and Sp. Therefore, WA and w B will eventually converge two different solutions this is how the semantics are disentangled when we assign label to multiple clusters.
4.2
Optimization-basse Label Assignment Approaches
How assign label to multiple clusters? Previous methods consider clustering as a preprocessing step and apply unsupervised methods, such as K-means, to partition the label space. In contrast, we formulate label assignments as an optimization problem to maximize the precision rate for XMC. which allows learning a matcher-aware clustering assignment as well as alternative updates between cluster assignments and the matcher.
As mentioned before, our goal is to learn Si,...,Sy SK to cover all the labels, and the sets can be overlapping. To find the best label assignments, it is natural maximize the precision rate. Many previous methods in information retrieval obtain ranking functions by optimizing (surrogates) Precision/Recall [25] 26). Here our goal is find a good combination of matcher and cluster assignments in the context of partition prrtition-bascee based XMC, so the objective is totally different.
To formally define precision, first define the output of matcher represented by matrix M E RRaK,
[1, if x; is matched to leaf cluster Sy, Mij 0, otherwise.
(5)
For beam size b, every row of M has exactly b nonzero entries. At the same time, the cluster assignments Sk can be parameterized by the clustering matrix C E {0, 1) 1)48 so that

---

Ciy = if and only if label-i is seen in cluster S,, otherwise C₁ = O. With this notation, the candidate labels generated by matcher is given by Y Binary(MMC Y RaxL, where Binary (A) A)= = La is the element-wise indicator function.
Now consider the number of true positíves in top-k predictions (TP@k), it is upper bounded by the intersection between matcher predictions Y and the ground truth Y. i.c.
Y (60 Tr
TPak = [Tpp-k Y
6
where denotes the #nnz elements in sparse matrix; the inequality is due to the error of ranker hidden in Top-k(-); and from the fact that both Y and Y are binary.
In this paper, we consider following scenarios that simplifies our analysis
Perfect ranker: the ranker does not make any mistake, so the gap in Eq. (6) vanishes.
Probably correct ranker: for any positive label e+ Y, it is ranked top-k with constant probability p, i.e. IP(E*= E Top-k(Y))
Y)= = p. Then we have TP@k p- Dr(Y Y).
In both cases, the precision is proportional Tr(YT)) We can then formulate the problem of learning the best cluster assignment as
maximize $1.52....5
Tr(Y Binary(MMC
S.C. Lees S X, aA E (1,2,...,.
(7)
U (1,...2....))
Note that {S,,... Sk} are hidden in C. The first constraint ensures we cover the whole label set and the second constraint mitigates the case of degenerated clusters where some S,' 's have too many labels, resulting in significantly increased time complexity. The parameter À the only hyperparameter to be tuned. In practice, we find À is stable across datasets and for simplicity experiments. We also show the sensitivity our algorithm with respect to À in Section 5.2
select À for all the
The optimization problem is combinatorial and hard to solve. In fact, we show this is NP-complete: Theorem 1. Problem is NP-complete.
This can be proved by polynomial time reduction from the set cover problem Problem 7 and the proof is deferred to the Appendix A.I To develop an efficient algorithm, we approximate the objective function of 7 with continuous, ReLU-like function
Binary(MC'
max(MC' -0) MC
(8)
where the first approximation comes from replacing binary function ReL.U; the second equality because both M and C are positive all entries. A special case when beam size 1. In that case M MCT is binary matrix, so Binary(MC. simplified problem:
MCT. We then consider the following
Tr(Y Tr(Y MC s.t. Σ Sp..g..,Sk
maximige
(9)
UKK (1,.1.,....)))
This problem be solved efficiently with closed form solution:
Theorem 2. Problem 9 has a closed form solution
C Proj(Y M).
(10)
where the Proj(-) operator selects the top-À elements for each row of the matrix.
The above result can be easily derived since the objective fuunction is linear and the constraint is row-wise norm constraint. The detailed proof can be found in the Appendix A.2]
But is 10 also a good solution to the original problem ? In fact, we show that this solution, despite not being optimal for 7 is provably better than any non-overlapping cluster partitioning, which is used in almost all the existing partition- based XMC methods.
Theorem 3. For any clustering matrix C' corresponding to non-overlapping partition of the label set, we have Tr(Y T (M
> Tr(Y Binary(MC )).
The proof can found in the Appendix A.3 This theorem implies our partitioning can achieve higher precision over any existing non-overlapping clustering for any ranker.
5

---

Practical Implementation After C' (or equivalently {()) is determined, we finetune the matcher M to accommodate the new deployment of label clusters. Note that most of the existing partition-based XMC starts from unsupervised label clustering and then alternate between getting new (overlapping) clustering and finetune the matcher. Our algorithm can plug-in into most of these methods by adding one or more loops of alternative cluster assignments and matcher updates. Given the current matcher, the cluster assignments are updated based on the proposed formulation (1O), and then the matcher will be retrained following the same procedure used in the original partition-based XMC solver. The whole routine is exhibited in Algorithm [] Since we use a balanced K-means label clustering initialization,
found that after one step update in Line 6 of Algorithm | { J is still not too imbalanced in our experiments. It's possible to add cluster size constraints in Problem
(9) to enforee the label partition to be balanced, as discussed in Appendix A.4 but we do not find practical need for such constraints.
Algorithm Our proposed framework.
1: Input: training data (X, Y), any -based XMC algorithm XMC-part.
2: Output: the trained model (i.e., matcher M, ranker R, label clusters (5.)
K 3: Initialize { with balanced K-means using label features.
4: Initialize M XMC-part((( ((S,)
5: Compute matcher prediction matrix M- = (M by Eq. (
6: Update label clustering: {8. k {8.) by Eq. (IO).
7: XX Fol Following two lines are called "alternative update" hereafter.
8: Finetune the matcher given new clusters: M t AKC-part((S.),
9: Train the ranker with updated clusters and matcher: R XMC ((C)
Deduplication at inference time. To perform inference with the new model, we need to deduplicate the scores from the same labels but in different clusters. This happens because we use beam search to efficiently search 6 paths from root node to leaves. Refer to Figure | where b = 2 is shown (S) and S3 selected), if both S and S3 contain a same label lduplicate but different scores $1 and 83, then we average them together with the final score s( ((Euupiicss) (s1 + 83). In this sense, our algorithm can be interpreted as finer- gner-grained ensemble which ensembles the scores inside tree, rather than ensembling multiple, independently trained trees.
5 Experimental Results
Our proposed framework serves as a generic plugin for any partition-based XMC methods and we show its efficacy on multiple experiment setups. First, we verify that the proposed method improves over the baselines on synthetic datasets where we simulate labels with mixed semantics. Next, we test the sensitivity of hyperparameter X, followed by experiments real-world XMC benchmark datasets. We end this section with an ablation study.
Datasets. We consider four publicly available XMC benchmark datasets 2 10 for our experiments. See Table for data statistics. To obtain sate-of-the-art (SOTA) results in Table 3 we concatenate the dense neural embeddings (from fine-tuned X- X-Transformer [12 11) and sparse TF-IDF features (from AttentionXML [10) as the input features to train the models.
Evaluation Metric. We measure the performance with precision metrics (P@k) as well as Propensity-
based scores (PSP@k) (5), which are widely-used the XMC literature [27 g 28
I8 12
Specifically, for predicted score vector ý E R- and a ground truth label vector y E (0, 1),
P@k 1 I EvErani (9) yı; PSP@k = E Pork(t))
Ymek(t). the latter focuses more on the tail labels.
Models. As we introduce a new technique that is generally applicable, our method must be combined with existing partition-based XMC algorithms. We take XR-Linear [ as the backbone for all experiments except Section 5.3 To get SOTA results in large-scale real datasets, we change the
backbone to X- X-Transformer [2] in Section [.3 The implementation details for combining our method with XR-Linear and X- TTaansformer are discussed in the Ap.eedii
Sarame-praaeetes. Our technique depends on hyperparameter X, which is tested in a standalone section. For hyperparameters in the XMC model, we mostly follow the default settings in the corresponding software. The details about hyperparameters are listed in the Appendix[A.6

---

Dataset
74m
Rest
L
L
π2
Wiki10-31K
14,146
6,616
30,938
18.64
8.52
101, 19,9
AmazonCat-133 1,186,239
306,782
13,330
5.04
448.57
203,882
Amazon-670K 490,449
153,025
670,091
5,45
3.99
135,909
Amazon-3M 1,717,899
742,507
2,812,281
36.04
22.02
337,067
Table 1: XMC data statistics, 7m and Tia are the number of instances in training and testing splits. L the number labels and L the average number of labels in each instance. the average number of positive data of each label. duar is the sparse TFIDF feature dimension. These four datasets and the sparse TF-IDF features are downloaded from bttps://giiiae com/yourhh/Attentioxx. Atteetionntttii which are the same used in AttentionXML [10]
com/yourh/ and X- X-Transformer [12].
WIki10-31K
Amazon-67000
9emmprove over bateline
Hard Medium Easy
%imppove over baseline
14
Medium
2.0-
Easy
1.-
Marge5
Figure 2: The relative precision @ gain over baseline XR-Linear model when adding our proposed overlapping clusters. The precision values are shown in the Appendix A.7
5.1 Synthetic datasets by grouping true labels
In this experiment, we create a synthetic data derived from public datasets by deliberately entangling some labels. The motivation is to the capability of disentangling different semantics from fused labels. Specifically, we designed several methods to mix up labels in the order of easy, medium and hard. The grouping is done without replacement: suppose dataset has L labels, and want to entangle every & labels into a fake one, then after this process we will get an artificial dataset with [. labels. Below are three implementations are going to evaluate:
Easy mode: we run balanced & 1-means clustering on the original label space of size L, that each cluster contains about & labels. After that, we represent each cluster with separate label, and the label embedding is the cluster centroid.
Medium mode:
balanced 32k --mans clustering the label space. Different from the setting above, now each cluster contains 32k labels. Next, we randomly group the 32k labels in to 32 subsets, with A labels each.
Hard mode: the most difficult mode is randomly shuffle labels into subsets, with & labels in each subset.
We label the difficulty of three modes based on the idea that when similar labels are entangled together, it is less issue for the bascline model, so the accuracy drop negligible; Whereas unrelated labels are bundled together, our method starts to shine. See Figure 2 for the relative performance improvement
XR-Linear. Several conclusions can be made from this figure: first, the improvements are all positive, meaning our method consistently beats the baseline XR-Linear model all scenarios; secondly, by comparing Wiki10-31K with Amazon-670K, we see Amazon- 670K shows an upwards in performance gain. This is mainly because the larger label space of Amazon-670k renders this problem even harder after combining labels, so our method exhibits big edge over baselines. How are the labels disentangled to different clusters? We attach a random example from our dataset Table 2 This example shows that our method can indeed separate labels with fused semantics, improving the quality of both matcher and ranker.
7

---

Methods
PGR.
PSP@1
P@1
3SP@
PSP@5
Wikil031KK
AmazonCat- 13K
AnnexML 3
93.54
63.30
DiSMEC
84.13
74.72
65.94
10.60
12.37
13.61
93.81
79.08
64.06
51.41
61.02
65.86
Parabel
84.19
72.46
63.37
11.69
12.47
13.14
93.02
79.14
64.51
50.92
64.00
72.10
extremeText 9
83.66
73.28
64.51
92.50
78.12
63.51
Bonsai [19
84.52
73.76
64.69
11.85
13.44
14.75
92.98
79.13
64.46
51.30
64.60
72.48
XML-CNN
66.23
56.11
9.39
10.00
26.26
77.06
67.10
AltentioNMMI. [0
87.47
78.48
69:37
15.57
16.80
17.82
95.92
82.41
67.31
53.76
68.72
76.38
XR-LINEAR
[
85.13
74.96
66.05
94.54
79.87
64.67
X-Tranffomee
78.51
68
15.12
17.99
96.48
66.32
76.45
Ours
88.85
79.52
70:67
15.23
16.81
18:42
96,48
83.55
68,36
50.46
66.76
77.01
Amazon: 6 670K
Amazznn 3M
36.61
24.67
53
49.30
14:07
15.98
DISMEC
44.78
39.72
36.17
26.26
30. 14
33.89
47.34
44.99
42.
Parubel 8
44.91
39.77
35.98
26.36
29.95
33.17
47.42
44.66
42.55
12.80
15.50
17.55
TextmeText 9
42.54
37.93
34.63
42.20
39.28
37.24
Bomsai [19
45.58
40.39
36.60
27.08
30.79
34.11
48.45
45.65
43.49
13.79
16.71
18.87
XML-
30.00
17.43
21.66
AltentionMM.. [T0]
47.58
42.61
38.92
30.29
33.85
37.13
50.86
48.04
45.83
15.52
18.45
20.60
XR-LINEAR
[1]
42.51
37.32
33.60
46.65
43.38
41.05
Transformer 12
42.96
51.20
45.07
23.65
Ours
50.70
45.40
41.55
36.39
39.15
41.96
52,70
49.92
47.71
18.79
21.90
24.10
Table 3: Comparing the Precision @k (P@k) and Propensity-bassed scores (PSP@k) for = 1, 3.5 on four datasets. First place is marked red; second place is marked blue. Our method is trained with same concatenation of dense neural and sparse TF-IDF features, where the former is from fine-tuned X-Transformer 112 TTI. Used plugin upon existing X- X-Transformer models, our proposed framework achieves new SOTA results on three out of four datasets.
5.2 Hyperparameter sensitivity (A)
In real applications, we never know the number of semantics label has either because the label space is huge, or it is uneconomical. In this section, we check the sensitivity of model performance on hyperparameter A. To this end, we consider four different datasets and choose À = [1, 2, 6}. The results are exhibited in Figure 3 From the figure above, we observe that the performance generally improves as we increase our prior on the number of different meanings each labels. However, since the benefits diminishes quickly, we choose À 2 for all the following experiments in this paper.
Fused label: "tanks" and "fashion scarves"
65.5
Cluster ID
Input text
65.0
Chiffon Butterfly Print on Black
Pre:
64.5
Pre
Silk Long Scarf 21x; (Clearance): ... offers you one of delightful styles as you desire.
96
1
AMAZON-670K
AMAZON-3M
36.5
This Scuba Yoke Fill Station device allows person to fill high pressure nitrogen/compressed air tanks from scuba tank...
36.0
42.5
103
35.5
Preces
42.0
Preces
Table 2: An example of how fused label is dis- entangled into two labels, both then falling into different clusters (cluster ids are 96 and 103), fi- nally labeled correctly despite the fusion of labels.
Figure 3: Precision @ (y-axis) versus different ranging from 0 to 6. We generally see that higher À converts to better performance, but it plateaus at 4.
5.3
Real datasets
The above experiments showed that our method is indeed better at disentangling complex meanings from labels. In real scenarios, it is certainly not the case that every label will have tens of underlying semantics. On the contrary, they behave more like a mix of both unimodal and multimodal labels.
However, in this experiment, we will show that our method is still favorable. We conduct experiments to show that our method can successfully boost the performance of existing partition- based XMC models, including Xi-Linear [I] and X- X-Tannsformer M.

---

In Table g we combine the proposed method with competitive linear models XR-Linear on four XMC benchmark datasets. We assume only the TF-IDF features are given and assume the single model setting without any ensemble. Our method consistently improves the performance over the baseline XR-Linear. Moreover, we tested how finetuning increases the accuracies (by comparing No/Yes in "alternative update?" column). The results prove that it is indeed necessary to train both the model parameters and cluster map in an alternative fashion (i.e., see Algorithm [
Next, we repeat the same process but based on the current SOTA X- Trannformmr model. The results are shown in Table 3 Notice that our method reuses the same dense+sparse features as in the X- Transformer model, and the results are the ensemble of 9 models [1]]. From Table 3 we can observe that our method achieves new SOTA precision results with a significant margin while still maintaining good PSP scores, comparing with other strong algorithms such as Parabel, AttentionXMLL XR-Linear and X-Transformer. Notably, the numbers show that our method more suitable for large label space (such Amazon-3M) compared with smaller label space (e.g., AmazonCat- 13K).
To benchmark the training and inference overhead due repeated clustering and training in our method, we report the relative training and inference time under different X's shown in T We remark that our method is more economical when the underlying model is inherently slow to train. On Amazon-3M for example, our framework only introduces 1.1% training overhead and 21.1% inference overhead over the X- X-Transformer models.
In Appendix A.8 we provided one more experiment on the real-world datasets that compares our method with random baseline. The random baseline is constructed by duplicating the same amount of labels to random clusters, as opposed to our precision maximization algorithm.
Method
Alteraaivve update?
Prec
Prec@:3
Prec
Wiki10-3IK
Method
Extra training time
Extra inference time
XR-Linear
N/A
84,
72.85
64.09
+Ours
No
84.52
74.23
65.41
Wikil0-31K
(baseline: Tira 0m300s Tix = 0.7mm/pts) 2.32x
+Ours
Yes
84.57
74.55
65.59
+Ours
2.40x 4.80
+Ours (A
5.58x
AmazonCaat Cat- 133
XR-Lincar
N/A
92.53
78.45
63.85
AmazonCat 13K
(baseline: Turn 1m37s, Text = 0.2ms/pts) 3.05x
+Ours
No
90.63
78. 12
63.86
+Ours (A = 1)
0,71 1,59x
+Ours
Yes
92.90
79.04
64.35
+Ours
4.54x
Amazon-6700
Amazon-670K
(baseline: Tea 1m30s. Th 0.4ms/pts) 0.47x
XR-Linear
N/A
44.17
35.38
Ours (2- = 1)
0.07x
+Ours
No
43.22
38. 19
34.10
2)
0.96x
0.60x
+Ours
Yes
44,82
39.93
36.34
Amazon-3M
(baseline: Tim 13m19s Tu. 0. 0.5ms/pts)
Amazon.3M 1M
Ours (A = 1)
0.33x
1.12x
XR-Lineur
Ours (A 2)
1.63x
2.51x
+Ours
No
46.95
44.24
42.18
+Ours
Yes
47.51
44.76
42.67
Table 5: Extra training time and inference time (in ms/pts, which is millisecond per data point) of our method compared to the baseline XR-Linear. Our method posts negligible overhead for big model. For X- Transformer on Amazon-3MM -M,, we only have 1.1% training overhead and 21.1% inference over-
Table 4: Experiments with XR-Linear. Our method called "XR-Linear+Ours", we also tested the finetune step detailed in Algo- rithm [L7). When joinly train option is dis- abled, the matcher M won't be updated despite head.
the creation of new cluster map.
Conclusion
In this paper, we have proposed a simple way to disentangle the semantics reside in the labels of XMC problems. We have shown how to do this in indirect way that builds overlapping label clusters. We proposed an optimization algorithm to solve both parts: the matcher model, the ranker and cluster assignments. In experiments, we tested under various cases and the results indicate that our method is exceptionally good when the label space is huge (such as Amazon-3M) or when the label contains many different meanings (such as the artificial data created).
Acknowledgement
This work supported in part by NSF under 19S-190,,27, 11S-2008173, IIS-2048280 and by Army Research Laboratory under agreement number W91 INF-20-2-0158.
9

---

References
[1] Hsiang-Fu Yu, Prateek Jain, Purushottam Kar, and Inderjit Dhillon. Large-scale multi-lahel learning with missing labels. In International conference machine learning (ICML), pages 593-601, 2014.
[2] K. Bhatia, K. Dahiya, H. Jain, A. Mittal, Y. Prabhu, and M. Varma. The extreme classification repository: Multi-labe datasets and code, 2016.
[3] Yukihiro Tagami. AnnexML: Approximate nearest neighbor search for extreme multi-label classification. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 455-464, 2017.
[4] Rohit Babbar and Bernhard Schölkopf. DiSMEC: distributed sparse machines for extreme multi-label classification. In WSDDM, 2017.
[5] Himanshu Jain, Yashoteja Prabhu, and Manik Varma. Extreme multi-label loss functions for recommendation, tagging, ranking & other missing label applications. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 235-944, 2016.
[6] Ioannis Partalas, Aris Kosmopoulos, Nicolas Baskiotis, Thierry Artieres, George Paliouras, Eric Gaussier, Ion Androutsopoulos, Massih-Reza Amini, and Patrick Galinari. LSHTC: A benchmark for large-scale text classification. arXiv preprint /rXiv::503.00000 1503008881, 2015.
[7] Tharun Kumar Reddy Medini, Qixuan Huang, Yiqiu Wang, Vijai Mohan, and Anshumali Shrivastava. Extreme classification in log memory using count-min sketch: A case study of amazon search with 50m products. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 32, pages 13265-13275. Curran Associates, Inc., 2019.
[8] Yashoteja Prabhu, Anil Kag, Shrutendra Harsola, Rahul Agrawal, and Manik Varma. Parabel: Partitioned label trees for extreme classification with application to dynamic search advertising. In WWW, 2018
[9] Marek Wydmuch, Kalina Jasinska, Mikhail Kuznetsov, Róbert Busa-Fekete, and Krzysztof Dembezynski. A no-regret generalization of hierarchical softmax to extreme multi-label classification. In NIPS, 2018
[10] Ronghui You, Zihan Zhang, Ziye Wang, Suyang Dai, Hiroshi Mamitsuka, and Shanfeng Zhu. AttentionXMLL: Label tree-based attention aware deep model for high bigh-performance extreme multi-label text classification. In Advances in Neural Information Processing Systems, pages 5812-5822 2019.
[11] Hsiang-Fu Yu, Kai Zhong, and Inderjit Dhillon. PECOS: Prediction for enormous and correlated output spaces. arXiv preprint arXiv:2010.05878 2020.
[12] Wei-Cheng Chang, Hisian-FFu Yu, Kai Zhong, Yiming Yang, and Inderjit S Dhillon. Taming pretrained transformers for extreme multi-label text classification. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 3163-3171 2020.
[13] Yacine Jernite, Anna Choromanska, and David Sontag. Simultaneous learning of trees and representations for extreme classification and density estimation. In International Conference on Machine Learning, pages 1665-1674. PMLR, 2017.
[14] Anna Choromanska and John Langford. Logarithmic time online multiclass prediction. arXiv preprini arXiv: 1406. 1822, 2014.
[15] Rohit Babbar and Bernhard Schölkopf. Data scarcity, robustness and extreme multi-label classification. Machine Learning, pages 1-23, 2019.
[16] Ian EH Yen, Xiangru Huang, Kai Zhong, Pradeep Ravikumar, and Inderjit S Dhillon. PD- Sparse: A primal and dual sparse approach to extreme multiclass and multilabel classification. In International Conference on Machine Learning (ICML), 2016.
10

---

[17] Ian EH Yen, Xiangru Huang, Wei Dai, Pradeep Ravikumar, Inderjit Dhillon, and Eric Xing, PPDsparse: A parallel primal-dual sparse method for extreme classification. In KDD. ACM, 2017.
[18) Himanshu Jain, Venkatesh Balasubramanian, Bhanu Chunduri, and Manik Varma. SLICE: Scal- able linear extreme classifiers trained on 100 million labels for related searches. In Proceedings of the Twelfth ACM International Conference Web Search and Data Mining, pages 236..36. ACM, 2019.
[19] Sujay Khandagale, Han Xiao, and Rohit Babbar. BONSAI-diverse and shallow trees for extreme multi-label classification. arXiv preprin! / 19009994449999 2019.
[20] Kalina Yosinska-Kobure Marek Wydmuch, Krzysztof Dembezynski, Mikhail Kuznetsov, and Robert Busa-Fekete. Probabilistic label trees for extreme multi- classification. arXiv preprint arXiv:2009.112118 2020.
[21] Arindam Banerjee, Chase Krumpelman, Joydeep Ghosh, Sugato Basu, and Raymond Mooney, Model-based overlapping clustering. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 532-537, 2005.
[22] Guillaume Cleuziou. An extended version of the k-means method for overlapping clustering. In 2008 19th International Conference on Pattern Recognition, pages 1-4, IEEE, 2008
[23] Haibing Lu, Yuan Hong. W Nick Street, Fei Wang, and Hanghang Tong. Overlapping clustering with sparseness constraints. In 2012 IEEE 12th International Conference on Data Mining Workshops, pages 486-494, IEEE, 2012.
[24] Joyce Jiyoung Whang, Yangyang Hou, Inderjit Dhillon, and David F Gleich. eon-exhaustivee overlapping k-means. IEEE Transactions on Patlern Analysis and Machine Intelligence (PAMI), 40(11):2644-66)) 2019.
[25] Purushottam Kar, Harikrishna Narasimhan, and Prateek Jain. Surrogate functions for maximiz- ing precision at the top. In International Conference Machine Learning, pages 189-198. PMLR, 2015.
[26] Aditya K Menon, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Multilabel reductions: what is my loss optimising? In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, pages 10600-10611, Curran Associates, Inc., 2019.
[27] Jingzhou Liu, Wei-Cheng Chang, Yuexin Wu, and Yiming Yang. Deep learning for extreme multi-label text classification. In Proceedings of the 40th International ACM SIGIR Conference on Research and Development Information Retrieval, pages 125-124. ACM, 2017.
[28] Sashank Reddi, Satyen Kale, Felix Yu, Dan Holtmann- Rice, Jiecao Chen, and Sanjiv Kumar. Stochastic negative mining for learning with large output spaces. In AISTATS, 2019.
[29] J Bijsterbosch and A Volgenant. Solving the rectangular assignment problem and applications. Annals of Operations Research, 181(1):443446 2010.
[30] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), 2019.
[31] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A robustly optimized BERT pretraining approach. arXiv preprint arXiv: /907. 1692, 2019.
[32] Zhilin Yang, Zihang Dai, Yiming Yang. Jaime Carbonell, Ruslan Salakhutdinov, and Quoc V
Le. XLNet: Generalized autoregressive pretraining for language understanding. In NIPS, 2019.


Reviews:
[{"review_id": "urdKglYtqQ", "reviewer": "Reviewer_2ebq", "summary": "In extreme Multi-label classification (XML) a large range of methods based their prediction on partitioning whether the input space or label space.  The paper addresses this partitioning phase, proposing a \"disentangled partitioning\", allowing overlapping clustering of labels. The proposed model consists to use two matrices, the first one M corresponding to the classification of the examples to each cluster (the matcher) and the second one C indicating the assignment of the labels to each cluster.  The goal is to optimize those matrices ensuring that  MC is close to the label matrix under constraints to ensure that each label is present up to lambda time in different clusters (the disentanglement factor). After a formal analysis of the problem, the authors propose a simple algorithm to optimize the matrix C, using existing approaches to learn the matcher. To validate the approach authors first propose an experiment merging artificially labels for clustering. The second series of experiments evaluate the performances wrt SOTA algorithms and varying the disentanglement parameter.\n", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The subject is not particularly new, the formalization uses standard tools (binary matrices), the proofs are quite straightforward.\n\nClarity: The paper can be quite difficult to read and is not always clear particularly in the experimental section when we are not sure of the backend used.  For instance, Table 5 is not clear enough the caption mentioning X-transformer and XR-linear. Another example, the constraint lambda is claimed to be an upper limit of the number of times that a label appears in clusters, however, equation 10 seems to select each label exactly lambda times. \n\nQuality: \n* The first major flaw of the paper concerns the adequation of the thesis of the paper and the experiments conducted. The authors claim to provide a model allowing to disentangle the semantics, but no experiments are showing exactly this fact. Experiments show better precision in different settings, but I am not convinced that the performances are due to disentanglement rather than redundancy of the labels.  There is no guarantee that for a given label its two assigned clusters differ semantically. Additional results showing the distance between clusters sharing some labels or with some kind of orthogonality measure between overlapping clusters should have been provided to support the author's thesis. \n\n* Concerning the core experiment Table 3, most of the table is not informative. The proposed approach uses other algorithms as backend, thus the only interesting lines are those concerning the backend algorithm (x-transformer) and the proposed plugin approach to measure the improvement of the proposal.  Further experiments should have been conducted with other usual backends (AnnexML, DiSmec at least) to fully assess the benefits of the approach. Moreover, to the best of my knowledge, X-transformer and X-linear (the two studied backends) do not use ensembling in the presented results. It would have been fairer to compare to results using ensembling allowing thus a similar expressive power wrt to the redundancy of the labels. \n\n* Concerning the proposed solution to problem 9, the solution seems too naive: it consists to assign to each label the lambda clusters where it is the most present. I am not sure that this solution does not lead to very correlated clusters (see above) and leads effectively to semantic disentanglement. The approximation made by Eq 8. seems too wide to lead to efficient solutions.\n\nSignificance: The addressed problem is interesting but the proposed approach seems too naive to work in generic cases. More experiments are needed to assess the impact of the plugin and to show that it provides significant improvement to semantic disentanglement.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "rwxMmMl4Xe", "reviewer": "Reviewer_3RKd", "summary": "This paper studies the extreme multi-label classification problem. Specifically, on top of the existing partition-based approaches that partition the label space into mutually exclusive clusters, the paper proposes a solution to relax this assumption by disentangle the multi-modal labels with non-exclusive clustering as an optimization approach. Evaluations are reported on four datasets against the existing baselines. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed method appears to technically make sense through the derivation and the evaluations. Novelty-wise, it is acceptable.\n\nThe major downside is the presentation, which is pretty rough with a lot of grammatical errors and typos. \n\nAlso in the reported evaluations (Table 3), why are the evaluation data using propensity scores far less impressive than those using precision scores? In fact, the paper states that “our proposed framework achieves new SOTA results on three out of four datasets”. This is misleading and confusing. More precisely, if precision is used, the proposed method achieves SOTA results for all the four datasets while if propensity is used, the proposed method only achieves SOTA results for two out of the four datasets.\n\n---\n\nI've read carefully the authors' rebuttal as well as the other reviews. Overall, though I see and agree to some of the concerns raised by the other reviewers, I like this work and thus stay with the original review.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not appear to address the limitation and the societal impact explicitly. One limitation is clearly that the complexity goes up when $\\lambda$ increases even a little bit, which actually was verified in the evaluations even though just for $\\lambda$ = 1 or 2.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "WLq081Qq6U", "reviewer": "Reviewer_h4mU", "summary": "The authors propose a new method for partitioning labels space that can be used with a family of currently popular partition-based/label tree-based extreme multi-label classifiers, which organize labels in the form of the tree. The proposed method introduces redundancy of labels in the different label clusters, which are mutually exclusive to the clusters in many methods. The problem of label assignment is formulated as maximization of matcher's (part of classifier predicting clusters for labels) precision, which is optimized by adding new labels to the cluster after initial training with clusters with mutually exclusive labels. The new partitioning method is applied to XL-Linear and X-TRANSFORMERS in the experimental study, resulting in a steady improvement in predictive performance on four popular benchmark datasets.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n+ The paper has a clear motivation and introduced technique is applicable to a wide range of extreme classification label tree-based methods.\n+ The organization of this paper is good, and it's easy to read and understand. \n+ Solid empirical study on the synthetic dataset by grouping many labels into one, performance evaluation, and comparison with random baseline.\n+ New method combined with X-TRANSFORMERS models (ensemble of 9 of them) leads to SOTA results on standard benchmarks while only slightly increasing computational complexity.\n\nWeaknesses:\n- The scope of the contribution is a bit limited, the idea and the results are not surprising. It's a small iterative improvement to the formula of label tree-based methods.\n- Empirical study uses only four datasets, where Amazon-670K and Amazon-3M are datasets representing exactly the same problem. I lack comparison, at least on the popular Wikipedia-500K benchmark.\n\nOther comments:\n* I think most of the tail labels are unimodal, and redundancy just improves their chances to be in one of the clusters returned by the matcher (what is basically the objective in the proposed approach). Since there is no penalty for assigning labels to up to additional lambda clusters in the optimization objective, I believe most of the labels, if not all of them, end up being redundant, even labels with only one data point in the train set? Maybe different values of lambda should be used for different labels?\n* There is no comment on the value of lambda in the synthetic experiment. It was equal to lambda, right? \n* Which dataset is the source for the examples in Table 2?\n---\nEdit after the authors' response: I believe that the authors did a good job providing additional experiments and discussing my and other reviewers' comments. I'm raising my rating to 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations were addressed and no issues with negative social impact were found.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical issues were found.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "DQZlZ3oq2yw", "reviewer": "Reviewer_Rv3e", "summary": "Label partitioning approaches are well-explored in Extreme Classification (XC) literature whose core idea is to cluster semantically similar labels together and then to sample the negative labels only from a small number of relevant clusters. Although this has been shown to significantly speed up the training and prediction routines, most existing partitioners simplistically assume that each label belongs to exactly one cluster. This could degrade prediction accuracies since labels in XC can often be multi-modal with multiple associated semantics. This paper addresses this issue by relaxing the single cluster assumption and thus allowing each label to instead end up in \\lambda different clusters. This is achieved though a novel cluster assignment algorithm which is shown to be theoretically well-defined and leads to small but consistent accuracy gains. The proposed algorithm has the added advantage of being plug-and-play, i.e. it can be used with many matching and ranking models based on label partitioning. Enough experiments have been conducted on simulated and real datasets to demonstrate the accuracy gains and discuss the associated increases in costs.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper introduces a neat and novel idea in label partitioning for XC which is easily adoptable within many models. As demonstrated in experiments, the approach could lead to small (< 1%) accuracy gains in different models and across datasets despite a modest 2x increment in training and prediction costs. Due to this, the paper could have decent amount of impact in XC applications.\n\nThe intuitions for the core ideas are well presented and easy to understand and appreciate. The idea of overlapping label partitions is novel and worth more exploration in XC. The proposed partitioning algorithm is novel and the theoretical contributions are simple but well motivated. The empirical results address most of the pragmatic concerns. In summary, the technical contributions are sound and sufficient. The paper is mostly well-written and easy to follow.\n\nThere are a few drawbacks of this paper: \n(1) Accuracy gains of 1% are not that impressive especially due to associated increases in cost\n(2) Some obvious questions which arise are left unresolved:\n    a) What is the effect on accuracy and convergence due to multiple iterations of model training and cluster mapping? Does it continuously improve performance or hurt it after some iterations. In general, what is the prescription here?\n    b) Although it is clear that overlapping clusters lead to accuracy gains, it is however unclear whether these gains are due to improvements in matching module (due to semantically well separated clusters) or  in the ranking module (due to more and diverse negative labels to learn from)?\n(3) Minor issues:\n    a) There has been some prior work in XC on co-optimizing clustering and XML objectives, e.g. [1,2]. Although these are point-partitioning approaches, they are worth mentioning for the sake of completeness\n    b) Line 167: The second constraint is not intended to mitigate the case of degenerated clusters as mentioned here. In fact, as noted in the Line 199, cluster imbalance is avoided due to good initialization from balanced k=2 means clustering \n    c) Head labels might be semantically more complex than tail labels. Does it help to put head labels in more clusters than tail ones?\n    d) Why is averaging duplicate label scores better than other alternatives, e.g. taking max over them ?\n    e)  line 53: one-vs-reset -> one-vs-rest\n        lines 73-74: in my understanding, SLICE graph construction is not unsupervised or agnostic to data distribution since it uses centroid classifiers as label representations during graph construction\n        line 78: imbalance -> imbalanced\n\n[1] Simultaneous Learning of Trees and Representations for Extreme Classification and Density Estimation\nYacine Jernite, Anna Choromanska, David Sontag\n[2] Choromanska, A. and Langford, J. Logarithmic time online\nmulticlass prediction", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes limitations have been addressed. Negative societal impact is not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a simple plug-in technique to improve the performance of label-partition based extreme classification algorithm. The improvements in performance are small but consistent.The paper is clear and easy to follow.  On the downside, the contribution is a bit limited and the method does incur a computational overhead, which might be significant for more efficient XC algorithms. The theoretical results in the paper are rather obvious, and under unrealistic assumptions, but they do help motivate the method.  The paper is also missing a comparison on the Wikipedia 500K dataset which is a standard dataset in the extreme classification. 



Decision: Accept (Poster)