Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

The 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.

There are a few drawbacks of this paper: 
(1) Accuracy gains of 1% are not that impressive especially due to associated increases in cost
(2) Some obvious questions which arise are left unresolved:
    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?
    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)?
(3) Minor issues:
    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
    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 
    c) Head labels might be semantically more complex than tail labels. Does it help to put head labels in more clusters than tail ones?
    d) Why is averaging duplicate label scores better than other alternatives, e.g. taking max over them ?
    e)  line 53: one-vs-reset -> one-vs-rest
        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
        line 78: imbalance -> imbalanced

[1] Simultaneous Learning of Trees and Representations for Extreme Classification and Density Estimation
Yacine Jernite, Anna Choromanska, David Sontag
[2] Choromanska, A. and Langford, J. Logarithmic time online
multiclass prediction
limitations_and_societal_impact: Yes limitations have been addressed. Negative societal impact is not applicable.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.

main_review: Originality: The subject is not particularly new, the formalization uses standard tools (binary matrices), the proofs are quite straightforward.

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

Quality: 
* 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. 

* 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. 

* 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.

Significance: 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.
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: Strengths:
+ The paper has a clear motivation and introduced technique is applicable to a wide range of extreme classification label tree-based methods.
+ The organization of this paper is good, and it's easy to read and understand. 
+ Solid empirical study on the synthetic dataset by grouping many labels into one, performance evaluation, and comparison with random baseline.
+ 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.

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

Other comments:
* 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?
* There is no comment on the value of lambda in the synthetic experiment. It was equal to lambda, right? 
* Which dataset is the source for the examples in Table 2?
---
Edit 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.
limitations_and_societal_impact: The limitations were addressed and no issues with negative social impact were found.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
main_review: The proposed method appears to technically make sense through the derivation and the evaluations. Novelty-wise, it is acceptable.

The major downside is the presentation, which is pretty rough with a lot of grammatical errors and typos. 

Also 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.

---

I'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.
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_title: null

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)