<figure><img src="image_1.png" /></figure>

HAL
open science

# PParabel: Parallel Partitioned Label Trees for Extreme Classification

Jiaqi Lu, Jun Zheng, Wenxin Hu

<figure><img src="image_2.png" /></figure>

## To cite this version:

Jiaqi Lu, Jun Zheng, Wenxin Hu. PParabel: Parallel Partitioned Label Trees for Extreme Classification. 16th IFIP International Conference on Network and Parallel Computing (NPC), Aug 2019, Hohhot, China. pp.82-92, 10.1007/978-3-030-30709-7_7. hal-03770549

HAL Id: hal-03770549

https://inria.hal.science/hal-03770549v1

Submitted on 6 Sep 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_4.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# PParabel: Parallel Partitioned Label Trees for Extreme Classification

Jiaqi Lu¹, Jun Zheng², and Wenxin Hu²

¹ School of Computer Science and Software Engineering,
East China Normal University, 3663 Zhong Shan Rd. N., Shanghai, China

² The Computer Center,
East China Normal University, 3663 Zhong Shan Rd. N., Shanghai, China
wxhu@cc.ecnu.edu.cn

**Abstract.** Extreme classification consists of extreme multi-class or multi-label predictions, whose objective is to learn classifiers that can label each data point with the most relevant labels. Recently, some approaches such as 1-vs-all method have been proposed to accomplish the task. However, their training time is linear with the number of classes, which makes them unrealistic in real-world applications such as text and image tagging. In this work, we are motivated to present a two-stage thread-level parallelism which is based on Partitioned Label Trees for Extreme Classification (Parabel). Our method is able to train the tree nodes in different parallel ways according to their number of labels. We compare our algorithm with recent state-of-the-art approach on some publicly available real-world datasets which have up to 670,000 labels. The experimental results demonstrate that our algorithm achieves the shortest training time.

**Keywords:** Extreme multi-label classification · Thread-level parallelism · OpenMP.

## 1 Introduction

Extreme classification was coined by John Langford<fnref n="3" /> and Manik Varma<fnref n="4" /> in 2013. It is the emerging research field in machine learning which solves classification problems in presence of a large number of categories (which are also called classes or labels) [8]. And the number of these categories is often more than $10^5$. To be specific, extreme classification consists of extreme multi-class (only one label is correct) or multi-label predictions (more than one label is relevant to the given item).

In this work, we focus on extreme multi-label classification where the label set has dimensionality of the order of hundreds of thousands or even millions, because this task has been of more and more significance in real-world applications such as text tagging. The goal in extreme multi-label classification is to

<footnote n="3">³ http://hunch.net/~jl/</footnote>

<footnote n="4">⁴ http://manikvarma.org/</footnote>
learn a classifier which can annotate a new instance with relevant labels from the extremely large label set. Take web tagging as an example, the pages in Wikipedia are all tagged with several relevant labels. Extreme multi-label classification can be used to learn a classifier to automatically label new pages by training on the existing pages. Furthermore, extreme multi-label classification can effectively address machine learning problems in web-scale data mining, such as recommendation systems and ad landing pages' queries [1, 10, 11]. Due to its capability for dealing with web-scale data, extreme multi-label classification has attracted more and more attention in recent years.

The popular approaches to extreme multi-label classification can be divided into two categories, namely 1-vs-all approaches [2, 9, 12, 13] and tree-based approaches [5, 6, 10, 11]. 1-vs-all approaches train a classifier for each label and they usually take months to train on large datasets on a standard desktop [11]. It is intolerable since extreme multi-label classification has been applied in real-world applications such as recommendation systems and ad landing pages' queries which are required to quickly predict the labels of items and give users an immediate answer. To overcome this, DiSMEC [2] and PPDSparse [12] take advantage of distributed systems and partition the training jobs on several computing nodes. Although it is effective, the cost of hardware is heavy. Taking dataset, WikiLSHTC-325K 5, as an example, it has 1,778,351 training instances and 325,056 categories. On this dataset, DiSMEC needs 3 hours train on 1000 cores. While for PPDSparse, it takes much shorter training time (i.e. 353seconds on 100 cores). If we reduce the hardware cost and train on a single core, tree-based approaches can train much faster. For example, PfastreXML [5] only needs 7.42 hours on a single core relative to 749 hours for DiSMEC. However, tree-based approaches have not been parallel to accelerate the training process. So is Parabel which is the fastest 1-vs-all approach built with tree structure [11]. To overcome this, we analyze the data independence between nodes and propose PParabel method to accelerate the training process which is the fastest method on one core [11].

Our contributions are shown as follows:

* We analyze the hierarchy of Parabel and find that each label only exists in one node on the same level which means nodes on the same level have data independence. With data independence, we can make the training process parallel at each level.

* We parallelize the training process in two stages. In the first stage, we parallelize the training process of nodes on the same level. In the second stage, we parallelize the k-means in nodes with OpenMP according to the number of labels in nodes.

* We conduct our training process in a thread-level parallelism way and apply OpenMP to accelerate our training. We can enable PParabel work on standard desktops to minimize hardware costs.

* We shorten the training time from one day to just one hour without appending more machines.

<footnote n="5">5 http://manikvarma.org/downloads/XC/XMLRepository.html</footnote>
The rest of the paper is organized as follows. Section 2 introduces the existing approaches to extreme multi-label classification. Section 3 describes the detail of our proposed PParabel method. Section 4 reports our experiments and we will analyze the results. At the end of this paper, we conclude our work and indicate future directions.

## 2 Related Work

The existing approaches to solving the extreme multi-label classification task can be divided into four categories, namely 1-vs-all approaches [2, 9, 12, 13], label-embedding approaches [3, 4, 14], tree-based approaches [5, 6, 10, 11] and deep learning based approaches [7].

1-vs-all approaches: 1-vs-all approaches train a separate classifier per label on the whole dataset. This kind of approach leads to training time linear in the number of classes. Therefore, when it comes to big datasets, the training costs can be heavy [11]. But this kind of method ignores the relevance between labels which makes each label independent and easy to be parallelized. DiSMEC [2] and PPDSparse [12] took advantage of the irrelevance between labels and scaled the training progress in large-scale distributed settings. Despite it can make the method easy to be parallelized, the cost of hardware is heavy.

Label-embedding approaches: Label-embedding approaches make the assumption that label matrix is low-rank. Therefore, it can be projected into low dimensional space. In this way, effective number of labels can be reduced. However, since the training points follow a power-law distribution, it will lead to low accuracy [2]. Moreover, embedding approaches need long time for training and prediction even on small embedding dimensions, let alone large datasets.

To overcome these limitations, SLEEC [3] was proposed. It learned local embedding instead of global embedding. To be specific, it used kNN method to preserve nearest neighbors in the label space. However, SLEEC ignores to model the label structure. [15] proposed a deep embedding method for extreme multi-label classification to overcome this. The deep embedding method uses label graph to depict the label structure. In the label graph, an edge exists if the two labels are active at the same sample. With the label graph established, DeepWalk method is used to make word2vec representation for all nodes in the graph. Then the distance between features and labels can be computed and all the training points can be clustered.

Tree-based approaches: Tree-based approaches usually have two types: decision trees and label trees. FastXML [10] is a state-of-the-art classifier for extreme multi-label classification. It recursively partitioned a parent's feature space between its children. To learn the hierarchy, FastXML optimizes the normalized Discounted Cumulative Gain (nDCG).

Another popular tree-based approach is PfastreXML [5]. The algorithm replaces the nDCG loss with its propensity scored variant. It also assigns higher rewards for accurate tail label predictions. In this way, it can improve tail label
prediction which is the most challenging factor of extreme multi-label classification.

Unlike the above two methods, Parabel [11] learned a few balanced label hierarchies. The root node of each hierarchy contains the whole set of labels. Each label tree recursively partitions the nodes into two balanced nodes until the number of labels in the leaf nodes is smaller than a threshold. When it comes to leaf nodes, a classifier will be learned for each label. It can be conducted on a single core with the shortest training time while matching its prediction accuracy with other methods. Although Parabel learned balanced label trees in a parallel way, it didn't optimize the node partition process in a parallel way to save time.

Deep learning based approaches: Deep learning based approach is a new way for extreme multi-label classification. Although it has achieved great success in other areas, it has not been applied to extreme classification until 2017. The first attempt is XML-CNN [7]. It utilizes the CNN model to learn a rich number of feature representations. Unlike the traditional CNN model, XML-CNN adopts a dynamic max pooling scheme to get more than one feature. Therefore, it can capture more fine-grained features.

Nowadays, the most popular approach is 1-vs-all approach since we can make log-time training and prediction. But how can we reduce the hardware cost and accelerate the training process is still a problem. Therefore, we are motivated to propose our solution in the next section.

## 3 Methodology: Parallel Partitioned Label Trees (PParabel)

Our method is designed to accelerate the node partition process parallel. There are two main components in our method, label trees and idle threads. Label trees are used for training the model. Internal nodes in label trees are processed parallel in idle threads. Fig. 1 shows the main structure of PParabel. The proposed method is described in the algorithmic format in algorithm 1. Detailed information is shown as follows. As we all know, every node in the tree which

<figure><img src="image_5.png" /><figcaption>Fig. 1. The main structure of PParabel.</figcaption></figure>
is learnt by Parabel is partitioned into two groups, and not a single label can be appeared in two groups. In other words, the split of different nodes is independent. Therefore, we can use its independence to make Parabel parallel. Each node is carried on a single thread.

For each label tree, we load feature matrix $X = x_1, x_2, ..., x_n$ and label matrix $Y = y_1, y_2, ..., y_n$. Then we represent the label representation in the way Parabel did. We average the feature vectors of instances which are positive to the label as the representation of label. With all labels represented, we put all label representations in the root node and start partitioning. We parallelize the partition process in a two-stage way which will be discussed in section 3.1 and section 3.2. For each node partition, we apply k-means to split the node into two nodes. We first randomly choose two label representations as centroids. After that, we calculate the distance between centroids and labels. For nodes on top levels, we parallelize the calculating distance with OpenMP. If it is not converged, we calculate the new centroids and repeat the k-means clustering. When the k-means clustering is converged, we split the labels into two nodes according to the resulting clusters. All these child nodes will be sent to idle threads to further split. The partition process will not stop until the number of labels in any leaf nodes is smaller than a threshold.

We also implement a two-stage parallelization which executes different strategies according to different nodes on different levels. In the following, we will elaborate more details about the two-stage parallelization. The first stage parallelization is applied to all nodes. The second is applied to nodes on top levels.

**Algorithm 1** PParabel - Parallel Partitioned Label Trees for Extreme Classification

**Input:** Feature matrix **X**, label matrix **Y**

**Output:** Balanced tree with the number of leaf nodes' labels smaller than a threshold

1: Load single copy of feature matrix **X**=$x_1, x_2, ..., x_n$ and label matrix **Y**=$y_1, y_2, ..., y_n$

2: Compute the label representation by averaging the feature vectors of instances which are positive to the label.

3: **while** the number of labels in any leaf node is larger than the threshold **do**

4: **if** node is on top levels **then**

5: Calculate the distance between the cluster centroids and labels with OpenMP.

6: **else**

7: Execute K-means in its own thread

8: **end if**

9: Partition the internal node into new nodes $node_1, node_2, ...$ according to the resulting clusters.

10: Assign the new nodes $node_1, node_2, ...$ to idle threads

11: **end while**

12: Sort all nodes in an ascending order according to their numbers.

13: **return** balanced tree
## 3.1 First-stage parallelization

In this stage, training process of each node is carried on a single thread. And we parallelize the training process of nodes on the same level. The notion behind is that each node is split into two nodes with totally different labels. When it comes to splitting these two child nodes, they do not affect each other. In other words, siblings do not have data dependency.

## 3.2 Second-stage parallelization

Since each tree node is halved, the training time of child nodes will also be halved. In other words, the time child nodes take for training should be half of the time their parent takes. We make the analysis to demonstrate this and we will discuss this in section 4.3. To maximize the usage of threads and speedup the training process, we parallelize the k-means, which is used to split the parent node into two parts, for the nodes on top layers with OpenMP. Here, we set the first five layers as top layer. Since calculating the distance between labels and cluster centroids is the most time consuming step in k-means, we parallelize this process with OpenMP. For the rest nodes which are on the sixth or after sixth layers, since their label sets are not large enough and there is no idle thread, they do not need to parallelize the k-means.

# 4 Experiments

## 4.1 Dataset Description

<table><caption>Table 1. Dataset Statistics</caption><thead><tr><td>Dataset</td><td>Number of Train Points</td><td>Number of Test Points</td><td>Label Dimensionality</td><td>Feature Dimensionality</td></tr></thead><tbody><tr><td>EURLex-4K</td><td>15,539</td><td>3,809</td><td>3,993</td><td>5,000</td></tr><tr><td>WikiLSHTC-325K</td><td>1,778,351</td><td>587,084</td><td>325,056</td><td>1,617,899</td></tr><tr><td>Wiki-500K</td><td>1,813,391</td><td>783,743</td><td>501,070</td><td>2,381,304</td></tr><tr><td>Amazon-670K</td><td>490,449</td><td>153,025</td><td>670,091</td><td>135,909</td></tr></tbody></table>

We carry out experiments on publicly available datasets from the Extreme Classification repository<fnref n="6" />. The detailed information of these datasets is shown in Table 1. All these datasets are processed from their original sources such as Wikipedia and Amazon. To figure out the effectiveness of the algorithm on different scale dataset, we choose one small dataset (EURLex-4K with 3,993 labels) and three large scale datasets (WikiLSHTC-325K, Wiki-500K and Amazon-670K) which include hundreds of thousands labels along with million train points.

<footnote n="6">⁶ http://manikvarma.org/downloads/XC/XMLRepository.html</footnote>
## 4.2 Evaluation Metrics

We use precision at k and speedup as the metrics for comparison. Precision at k is a commonly used metrics in extreme multi-label classification to show the classification accuracy. And speedup is used to show the effectiveness of the parallelization. For a predicted score vector $\hat{y} \in R^L$ and the ground truth label vector $y \in \{0, 1\}^L$, the precision at k is defined as:

$$P@k := \frac{1}{k} \sum_{l \in \text{rank}_k(y)} y_l \qquad (1)$$

The speedup is defined as:

$$S = \frac{T_s}{T_p} \qquad (2)$$

where $T_s$ is the time that the experiment takes in a serial way and $T_p$ is the time that the experiment takes in a parallel way. Higher value of S means more effectiveness of the algorithm.

## 4.3 Results

<figure><img src="image_6.png" /><figcaption>Fig. 2. Average training time of each tree level for four datasets.</figcaption></figure>
Fig. 2 shows the average split time of each level. As we can see, the average split time of second-layer nodes is about half of the root node. The average split time of third-layer nodes is about half of the second-layer nodes. So are the fourth layer and fifth layer. When it comes to layers after fifth layer, the split time is almost the same. The reason is that the original label set has been divided into more than 32 parts and the k-means process in these nodes can be quickly converged. As we can see, k-means process is the most time consuming step in top level nodes. When it comes to other levels, a large number of node partition is the most time consuming step. Therefore, we can parallelize the k-means process with OpenMP on top levels to accelerate the training.

All experiments are run on two Intel Xeon E5-2620 v4 2.10 GHz CPUs. Each CPU has 8 physical cores. There are no hyper threads per core. While the proposed method is based on Parabel, the precision@k and speedup are calculated between the Parabel, PParabel and fastXML. For Parabel and PParabel, the number of balanced trees trained is three and two algorithms use squared hinge loss. But fastXML trains fifty trees in order to achieve high accuracy. Table 2 shows the results on extreme classification datasets. It turns out that the prediction accuracy of PParabel is almost the same as Parabel. It is much better than fastXML which trains much more trees to increase the accuracy. Since we just parallelize the partition process before learning classifiers, the precision@k should be the same theoretically. However, choosing random starting points may result in different clustering results. This may explain why precision@k of Parabel and PParabel are slightly different.

Table 2 also shows the training time of three algorithms which run on these datasets. It can be seen that as the number of threads increases, the training time of PParabel gets shorter and shorter. But when the number of threads increases more than 10, the training time will not decrease much. We can also reduce the training time from 27 hours to 1 hour just using one machine. It is great to shorten the training time while using much fewer machines.

Fig. 3 shows the speedup of different threads on four datasets. The number of threads for PParabel varies from 2 to 15. Both Parabel and fastXML are run with a single thread. We set the maximum threads 15 since we want to make sure that every thread can work on different processor separately which make parallelization happen. PParabel uses multi-threads, while Parabel and fastXML use just one thread. And all these experiments are run in this situation.

The maximum speedup of Parabel is around 9 which is achieved in EURLex-4K dataset. And the maximum speedup of fastXML is around 57 which is achieved in Amazon-670K dataset. As it can be seen, the speedup gain per thread is getting down with the number of threads increasing. The reason is that to protect the data consistency, we need to block other completed threads until the current thread finishes writing. When the number of threads increases, the chance of being blocked is getting bigger and bigger which wastes a lot of time to communicate. Therefore, the speedup gain per thread is getting down with the number of threads increasing. But the speedup is achieved almost lin-
early with the threads number increasing. In this consideration, to maximize the
performance, the optimal number of threads is around 15.

<figure><img src="image_7.png" /><figcaption>Fig. 3. Speedup of different threads on four datasets.</figcaption></figure>

5 Conclusion

In this paper, we have discussed the hardware cost and training time of four
typical kinds of approaches to extreme multi-label classification. In order to re-
duce the hard-ware cost and speedup the training process, we have proposed
PParabel algorithm based on Parabel. Our main contribution is employing a
two-stage thread-level parallelism. Moreover, we analyze the data independence
of nodes on the same level to make sure the training process can be successfully
parallelized. The experiment results show that our method is successful to ac-
celerate the training process. All our experiments are conducted on a standard
desktop. However, the speedup is achieved almost linearly with the thread num-
ber increasing. In the future work, we will study more sufficient approaches in
thread level.
<table><caption>**Table 2.** results on extreme classification datasets.</caption><thead><tr><th>Method</th><th>P1(%)</th><th>P3(%)</th><th>P5(%)</th><th>Training time(hr)</th><th>Method</th><th>P1(%)</th><th>P3(%)</th><th>P5(%)</th><th>Training time(hr)</th></tr></thead><tbody><tr><td colspan="4">EURLex-4K</td><td></td><td colspan="4">Wiki-500K</td></tr><tr><td>fastXML</td><td>71.36</td><td>59.90</td><td>50.39</td><td>0.0590</td><td>fastXML</td><td>49.27</td><td>33.30</td><td>25.63</td><td>27.72</td></tr><tr><td>Parabel</td><td>82.25</td><td>68.71</td><td>57.53</td><td>0.0136</td><td>Parabel</td><td>68.52</td><td>48.42</td><td>38.55</td><td>6.37</td></tr><tr><td>PParabel-t=2</td><td></td><td></td><td></td><td>0.0070</td><td>PParabel-t=2</td><td></td><td></td><td></td><td>3.88</td></tr><tr><td>PParabel-t=3</td><td></td><td></td><td></td><td>0.0054</td><td>PParabel-t=3</td><td></td><td></td><td></td><td>2.75</td></tr><tr><td>PParabel-t=4</td><td></td><td></td><td></td><td>0.0041</td><td>PParabel-t=4</td><td></td><td></td><td></td><td>1.96</td></tr><tr><td>PParabel-t=5</td><td></td><td></td><td></td><td>0.0034</td><td>PParabel-t=5</td><td></td><td></td><td></td><td>1.53</td></tr><tr><td>PParabel-t=6</td><td></td><td></td><td></td><td>0.0029</td><td>PParabel-t=6</td><td></td><td></td><td></td><td>1.43</td></tr><tr><td>PParabel-t=7</td><td></td><td></td><td></td><td>0.0027</td><td>PParabel-t=7</td><td></td><td></td><td></td><td>1.30</td></tr><tr><td>PParabel-t=8</td><td>81.31</td><td>68.33</td><td>57.04</td><td>0.0024</td><td>PParabel-t=8</td><td>67.97</td><td>48.83</td><td>38.02</td><td>1.19</td></tr><tr><td>PParabel-t=9</td><td></td><td></td><td></td><td>0.0022</td><td>PParabel-t=9</td><td></td><td></td><td></td><td>1.09</td></tr><tr><td>PParabel-t=10</td><td></td><td></td><td></td><td>0.0019</td><td>PParabel-t=10</td><td></td><td></td><td></td><td>1.02</td></tr><tr><td>PParabel-t=11</td><td></td><td></td><td></td><td>0.0019</td><td>PParabel-t=11</td><td></td><td></td><td></td><td>0.96</td></tr><tr><td>PParabel-t=12</td><td></td><td></td><td></td><td>0.0018</td><td>PParabel-t=12</td><td></td><td></td><td></td><td>1.01</td></tr><tr><td>PParabel-t=13</td><td></td><td></td><td></td><td>0.0017</td><td>PParabel-t=13</td><td></td><td></td><td></td><td>0.995</td></tr><tr><td>PParabel-t=14</td><td></td><td></td><td></td><td>0.016</td><td>PParabel-t=14</td><td></td><td></td><td></td><td>1.09</td></tr><tr><td>PParabel-t=15</td><td></td><td></td><td></td><td>0.0015</td><td>PParabel-t=15</td><td></td><td></td><td></td><td>1.12</td></tr><tr><td colspan="4">WikiLSHTC-325K</td><td></td><td colspan="4">Amazon-670K</td></tr><tr><td>fastXML</td><td>49.75</td><td>33.10</td><td>24.45</td><td>4.556</td><td>fastXML</td><td>36.99</td><td>33.28</td><td>30.53</td><td>2.263</td></tr><tr><td>Parabel</td><td>65.04</td><td>43.23</td><td>32.05</td><td>0.651</td><td>Parabel</td><td>44.90</td><td>39.81</td><td>35.99</td><td>0.302</td></tr><tr><td>PParabel-t=2</td><td></td><td></td><td></td><td>0.585</td><td>PParabel-t=2</td><td></td><td></td><td></td><td>0.174</td></tr><tr><td>PParabel-t=3</td><td></td><td></td><td></td><td>0.458</td><td>PParabel-t=3</td><td></td><td></td><td></td><td>0.117</td></tr><tr><td>PParabel-t=4</td><td></td><td></td><td></td><td>0.248</td><td>PParabel-t=4</td><td></td><td></td><td></td><td>0.109</td></tr><tr><td>PParabel-t=5</td><td></td><td></td><td></td><td>0.178</td><td>PParabel-t=5</td><td></td><td></td><td></td><td>0.082</td></tr><tr><td>PParabel-t=6</td><td></td><td></td><td></td><td>0.163</td><td>PParabel-t=6</td><td></td><td></td><td></td><td>0.071</td></tr><tr><td>PParabel-t=7</td><td></td><td></td><td></td><td>0.154</td><td>PParabel-t=7</td><td></td><td></td><td></td><td>0.065</td></tr><tr><td>PParabel-t=8</td><td>64.08</td><td>42.54</td><td>31.46</td><td>0.138</td><td>PParabel-t=8</td><td>44.38</td><td>39.28</td><td>35.44</td><td>0.059</td></tr><tr><td>PParabel-t=9</td><td></td><td></td><td></td><td>0.129</td><td>PParabel-t=9</td><td></td><td></td><td></td><td>0.055</td></tr><tr><td>PParabel-t=10</td><td></td><td></td><td></td><td>0.125</td><td>PParabel-t=10</td><td></td><td></td><td></td><td>0.051</td></tr><tr><td>PParabel-t=11</td><td></td><td></td><td></td><td>0.126</td><td>PParabel-t=11</td><td></td><td></td><td></td><td>0.049</td></tr><tr><td>PParabel-t=12</td><td></td><td></td><td></td><td>0.119</td><td>PParabel-t=12</td><td></td><td></td><td></td><td>0.047</td></tr><tr><td>PParabel-t=13</td><td></td><td></td><td></td><td>0.120</td><td>PParabel-t=13</td><td></td><td></td><td></td><td>0.0426</td></tr><tr><td>PParabel-t=14</td><td></td><td></td><td></td><td>0.119</td><td>PParabel-t=14</td><td></td><td></td><td></td><td>0.0428</td></tr><tr><td>PParabel-t=15</td><td></td><td></td><td></td><td>0.110</td><td>PParabel-t=15</td><td></td><td></td><td></td><td>0.040</td></tr></tbody></table>
**Acknowledgement.** We thank all viewers who provided the thoughtful and constructive comments on this paper. The third author is the corresponding author. We are grateful to Dr. Manik Varma and his group for their preprocessed datasets. We also thank ECNU Public Platform for Innovation (001) for their equipment to carry out our experiments.

## References

1. Agrawal, R., Gupta, A., Prabhu, Y., Varma, M.: Multi-label learning with millions of labels: Recommending advertiser bid phrases for web pages. In: Proceedings of the 22nd in-ternational conference on World Wide Web (WWW), pp. 13-24. ACM, New York(2013)

2. Babbar, R., Schölkopf, B.: DiSMEC: Distributed Sparse Machines for Extreme Multi-label Classification. In: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining (WSDM), pp. 721-729. ACM, New York(2017)

3. Bhatia, K., Jain, H., Kar, P., Varma, M., Jain, P.: Sparse Local Embeddings for Extreme Multi-label Classification. In: Proceedings of the 28th International Conference on Neural Information Processing Systems (NIPS), vol. 1, pp. 730-738. MIT Press Cambridge, MA(2015)

4. Choromanska, A.E., Langford, J.: Logarithmic Time Online Multi-class prediction. In: Proceedings of the 28th International Conference on Neural Information Processing Sys-tems(NIPS), vol. 1, pp. 55-63. MIT Press Cambridge, MA(2015)

5. Jain, H., Prabhu, Y., Varma, M.: 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 (KDD), pp. 935-944. ACM, New York(2016)

6. Jasinska, K., Dembczynski, K., Busa-Fekete, R., Pfannschmidt, K., Klerx, T., Hullermeier, E.: Extreme F-Measure Maximization using Sparse Proba-bility Estimates. In: Proceedings of the 33rd International Conference on Machine Learning (ICML), vol. 48, pp. 1435-1444(2016)

7. Liu, J., Chang, W.C., Wu, Y., Yang, Y.: Deep Learning for Extreme Multi-label Text Classi-fication. In: Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR), pp. 115-124. ACM, New York(2017)

8. Mouhamadou, M.C.: Efficient extreme classification. Data Structures and Algorithms. [cs.DS]. Université Pierre et Marie Curie - Paris VI(2014)

9. Niculescu-Mizil, A., Abbasnejad, E.: Label Filters for Large Scale Multilabel Classification. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1448-1457 (2017)

10. Prabhu, Y., Varma, M.: FastXML: a fast, accurate and stable tree-classifier for extreme multi-label learning. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD), pp. 263-272. ACM, New York(2014)

11. Prabhu, Y., Kag, A., Harsola, S., Agrawal, R., Varma, M.: Parabel: Partitioned Label Trees for Extreme Classification with Application to Dynamic Search Advertising. In: Proceedings of the 2018 World Wide Web Conference(WWW), pp. 993-1002. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva(2018)
12. Yen, I.E.H., Huang, X., Dai, W., Ravikumar, P., Dhillon, I., Xing, E.: PPDsparse: A Parallel Primal-Dual Sparse Method for Extreme Classification. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 545-553. ACM, New York (2017)

13. Yen, I.E.H., Huang, X., Zhong, K., Ravikumar, P., Dhillon, I.S.: PD-Sparse: A primal and dual sparse approach to extreme multiclass and multilabel classification. In: Proceedings of the 33rd International Conference on Machine Learning (ICML), vol. 48, pp. 3069-3077. JMLR.org(2016)

14. Yu, H., Jain, P., Kar, P., Dhillon, I.S.: Large-scale Multi-label Learning with Missing Labels. In: Proceedings of the 31st International Conference on Machine Learning (ICML), vol. 32, pp. I-592-I-601. JMLR.org(2014)

15. Zhang, W., Yan, J., Wang, X., Zha, H.: Deep Extreme Multi-label Learning. In: Proceedings of the 2018 ACM on International Conference on Multimedia Retrieval (ICMR), pp. 100-107. ACM, New York (2018)