ECLARE: Extreme Classification with Label Graph Correlations
Anshul Mittal

Noveen Sachdeva∗

Sheshansh Agrawal

me@anshulmittal.org
IIT DelhiIndianosachde@ucsd.edu
UC San Diego
USA

sheshansh.agrawal@microsoft.com
Microsoft Research
India

Sumeet Agarwal

Purushottam Kar

Manik Varma

sumeet@iitd.ac.in
IIT Delhi
Indiapurushot@cse.iitk.ac.in
IIT Kanpur
Microsoft ResearchIndiamanik@microsoft.com
Microsoft Research
IIT Delhi
India

CCS CONCEPTS• Computing methodologies → Machine learning; Supervised
learning by classification.

KEYWORDS
Extreme multi-label classification; product to product recommendation; label features; label metadata; large-scale learning
ACM Reference Format:
Anshul Mittal, Noveen Sachdeva, Sheshansh Agrawal, Sumeet Agarwal,
Purushottam Kar, and Manik Varma. 2021. ECLARE: Extreme Classification
with Label Graph Correlations. In Proceedings of the Web Conference 2021
∗ Work done during an internship at Microsoft Research India

This paper is published under the Creative Commons Attribution 4.0 International(CC-BY 4.0) license. Authors reserve their rights to disseminate the work on theirpersonal and corporate Web sites with the appropriate attribution.
WWW ’21, April 19–23, 2021, Ljubljana, Slovenia© 2021 IW3C2 (International World Wide Web Conference Committee), publishedunder Creative Commons CC-BY 4.0 License.
ACM ISBN 978-1-4503-8312-7/21/04.
https://doi.org/10.1145/3442381.3449815

LF-AmazonTitles-131K

103

LF-WikiSeeAlsoTitles-320K

Number of training points(Log. Scale)

Deep extreme classification (XC) seeks to train deep architecturesthat can tag a data point with its most relevant subset of labels froman extremely large label set. The core utility of XC comes from predicting labels that are rarely seen during training. Such rare labels
hold the key to personalized recommendations that can delight andsurprise a user. However, the large number of rare labels and small
amount of training data per rare label offer significant statisticaland computational challenges. State-of-the-art deep XC methods attempt to remedy this by incorporating textual descriptions of labels
but do not adequately address the problem. This paper presents
ECLARE, a scalable deep learning architecture that incorporates
not only label text, but also label correlations, to offer accurate
real-time predictions within a few milliseconds. Core contributionsof ECLARE include a frugal architecture and scalable techniques totrain deep models along with label correlation graphs at the scale ofmillions of labels. In particular, ECLARE offers predictions that are
2–14% more accurate on both publicly available benchmark datasets
as well as proprietary datasets for a related products recommendation task sourced from the Bing search engine. Code for ECLARE isavailable at https://github.com/Extreme-classification/ECLARE

Number of training points(Log. Scale)

ABSTRACT

103

102

102

101

101

100
0

20000

40000

60000

80000 100000 120000

Label ID

100
0

50000

100000 150000 200000 250000 300000

Label ID

Figure 1: Number of training data points per label for two
datasets. Labels are ordered from left to right in increasingorder of popularity. In both datasets, 60–80% labels have < 5
training points (indicated by the bold horizontal line).

(WWW ’21), April 19–23, 2021, Ljubljana, Slovenia. ACM, New York, NY,
USA, 12 pages. https://doi.org/10.1145/3442381.3449815

1

INTRODUCTION

Overview. Extreme multi-label classification (XC) involves tagging
a data point with the subset of labels most relevant to it, from an extremely large set of labels. XC finds applications in several domains
including product recommendation [28], related searches [15], related products [31], etc. This paper demonstrates that XC methods
stand to benefit significantly from utilizing label correlation data,by presenting ECLARE, an XC method that utilizes textual label
descriptions and label correlation graphs over millions of labels
to offer predictions that can be 2–14% more accurate than thoseoffered by state-of-the-art XC methods, including those that utilize
label metadata such as label text.
Rare Labels. XC applications with millions of labels typically findthat most labels are rare with very few training data points taggedwith those labels. Fig 1 exemplifies this on two benchmark datasets
where 60–80% labels have < 5 training points. The reasons behindrare labels are manifold. In several XC applications, there may exist
an inherent skew in the popularity of labels, e.g, it is natural for
certain products to be more popular among users in an e-commercesetting. XC applications also face missing labels [16, 50] wheretraining points are not tagged with all the labels relevant to them.
This can be due to the inability of a human user to exhaustively markall products of interest to them, or biases in the recommendation
platform (e.g. website, app) itself which may present or impress
upon its users, certain products more often than others.

WWW ’21, April 19–23, 2021, Ljubljana, Slovenia

Need for Label Metadata. Rare labels are of critical importancein XC applications. They allow highly personalized yet relevant
recommendations that may delight and surprise a user, or else allow precise and descriptive tags to be assigned to a document, etc.
However, the paucity of training data for rare labels makes it challenging to predict them accurately. Incorporating label metadata
such as textual label descriptions [31], label taxonomies [21, 29, 38]
and label co-occurrence into the classification process are possible
ways to augment the available information for rare labels.
Key Contributions of ECLARE. This paper details ECLARE, an
XC method that performs collaborative learning that especiallybenefits rare labels, by incorporating multiple forms of label metadata such as label text as well as label correlation graphs that are
dynamically inferred. Critical to ECLARE are augmentations to thearchitecture and learning pipeline that scale to millions of labels:(1) Introduce a framework that allows collaborative extreme learning using label-label correlation graphs that are dynamicallygenerated using asymmetric random walks. This is in contrast
to existing approaches that often perform collaborative learningon static user-user or document-document graphs [12, 14, 48].
(2) Introduce the use of multiple representations for each label: onelearnt from label text alone (LTE), one learnt collaboratively
from label correlation graphs (GALE), and a label-specific refinement vector. ECLARE proposes a robust yet inexpensive
attention mechanism to fuse these multiple representations togenerate a single one-vs-all classifier per label.
(3) Propose critical augmentations to well-established XC training
steps, such as classifier initialization, negative sampling, shortlist creation (GAME), label clustering, etc, in order to incorporate
label correlations in a systematic and scalable manner.
(4) Offer an end-to-end training pipeline incorporating the above
components in an efficient manner which can be scaled to tasks
with millions of labels and offer up to 14% performance boost
on standard XC prediction metrics.
Comparison to State-of-the-art. Experiments indicate that apartfrom significant boosts on standard XC metrics (see Tab 2), ECLARE
offers two distinct advantages over existing XC algorithms, including those that do use label metadata such as label text (see Tab 6)(1) Superior Rare Label Prediction: In the first example in Tab 6,
for the document “Tibetan Terrier”, ECLARE correctly predicts
the rare label “Dog of Osu” that appeared just twice in the
training set. All other methods failed to predict this rare label.
It is notable that this label has no common tokens (words) withthe document text or other labels which indicates that relying
solely on label text is insufficient. ECLARE offers far superior
performance on propensity scored XC metrics which place moreemphasis on predicting rare labels correctly (see Tabs 2 and 3).
(2) Superior Intent Disambiguation: The second and third examples in Tab 6 further illustrate pitfalls of relying on label text
alone as metadata. For the document “85th Academy Awards”,
all other methods are incapable of predicting other award ceremonies held in the same year and make poor predictions. On
the other hand, ECLARE was better than other methods at picking up subtle cues and associations present in the training datato correctly identify associated articles. ECLARE offers higher
precision@1 and recall@10 (see Tabs 2 and 3).

Mittal and Sachdeva, et al.

2

RELATED WORK

Summary. XC algorithms proposed in literature employ a varietyof label prediction approaches like tree, embedding, hashing andone-vs-all-based approaches [1, 2, 4, 6, 8, 10, 11, 15–19, 22, 26, 31,
35–37, 40, 41, 44–47, 49]. Earlier works learnt label classifiers using fixed representations for documents (typically bag-of-words)
whereas contemporary approaches learn a document embeddingarchitecture (typically using deep networks) jointly with the label
classifiers. In order to operate with millions of labels, XC methods frequently have to rely on sub-linear time data structures for
operations such as shortlisting labels, sampling hard negatives,
etc. Choices include hashing [28], clustering [6, 36, 49], negative
sampling [30], etc. Notably, most XC methods except DECAF [31],GLaS [10], and X-Transformer [6] do not incorporate any form oflabel metadata, instead treating labels as black-box identifiers.
Fixed Representation. Much of the early work in XC used fixedbag-of-words (BoW) features to represent documents. One-vs-all
methods such as DiSMEC [1], PPDSparse [45], ProXML [2] decompose the XC problem into several binary classification problems,
one per label. Although these offered state-of-the-art performance
until recently, they could not scale beyond a few million labels.
To address this, several approaches were suggested to speed up
training [15, 22, 36, 47], and prediction [19, 33] using tree-basedclassifiers and negative sampling. These offered high performanceas well as could scale to several millions of labels. However, thesearchitectures were suited for fixed features and did not support
jointly learning document representations. Attempts, such as [15],to use pre-trained features such as FastText [20] were also not very
successful if the features were trained on an entirely unrelated task.
Representation Learning. Recent works such as X-Transformer [6],ASTEC [8], XML-CNN [26], DECAF [31] and AttentionXML [49]propose architectures that jointly learn representations for the
documents as well as label classifiers. For the most part, these methods outperform their counterparts that operate on fixed document
representations which illustrates the superiority of task-specificdocument representations over generic pre-trained features. However, some of these methods utilize involved architectures such asattention [6, 49] or convolutions [26]. It has been observed [8, 31]that in addition to being more expensive to train, these architectures also suffer on XC tasks where the documents are short texts,
such as user queries, or product titles.
XC with Label Metadata. Utilizing label metadata such as label
text, label correlations, etc. can be critical for accurate prediction ofrare labels, especially on short-text applications where documents
have textual descriptions containing only 5-10 tokens which are notvery descriptive. Among existing works, GLaS [10] uses label correlations to design a regularizer that improved performance over rarelabels, while X-Transformer [6] and DECAF [31] use label text aslabel metadata instead. X-Transformer utilizes label text to performsemantic label indexing (essentially a shortlisting step) along witha pre-trained-then-fine-tuned RoBERTa [27] architecture. On theother hand, DECAF uses a simpler architecture to learn both label
and document representations in an end-to-end manner.

ECLARE: Extreme Classification with Label Graph Correlations

𝛼𝑙3

𝒜

ℰ
𝐑

…
ReLU
ℰ 𝐯 = 𝐯 + 𝜆 ⋅ 𝐑 ⋅ RELU 𝐯
Text Embedding Block𝛼𝑙2 𝛼𝑙1

Faux𝐀…
Sigmoid…

…
Sigmoid…

…
Sigmoid
…

𝐓

𝐓

𝐓

…
ReLU
𝐳ො𝑙𝟑

…
ReLU

…
ReLU

𝐳ො𝑙1
𝐳ො𝑙𝟐
Attention Block

Figure 2: The building blocks of ECLARE. (Left) The embedding block is used in document and label embeddings.
(Right) The attention block is used to fuse multiple label representations into a single label classifier (see Fig 3).

Collaborative Learning for XC. Given the paucity of data forrare labels, the use of label text alone can be insufficient to ensure
accurate prediction, especially in short-text applications such as
related products and related queries search, where the amount oflabel text is also quite limited. This suggests using label correlations to perform collaborative learning on the label side. User-useror document-document graphs [12, 14, 24, 34, 42, 43, 48, 51] havebecome popular, with numerous methods such as GCN [24], LightGCN [14], GraphSAGE [12], PinSage [48], etc. utilizing graph neuralnetworks to augment user/document representations. However, XC
techniques that directly enable label collaboration with millionsof labels have not been explored. One of the major barriers forthis seems to be that label correlation graphs in XC applications
turn out to be extremely sparse, e.g, for the label correlation graph
ECLARE constructed for the LF-WikiSeeAlsoTitles-320K dataset,nearly 18% of labels had no edges to any other label. This precludes
the use of techniques such as Personalised Page Rank (PPR) [25, 48]
over the ground-truth to generate a set of shortlisted labels fornegative sampling. ECLARE solves this problem by first mining
hard-negatives for each label using a separate technique, and subsequently augmenting this list by adding highly correlated labels.

3𝐱ොChevron

SoftMaxλ…

WWW ’21, April 19–23, 2021, Ljubljana, Slovenia

ECLARE: EXTREME CLASSIFICATIONWITH LABEL GRAPH CORRELATIONS

Summary. ECLARE consists of four components 1) a text embedding architecture adapted to short-text applications, 2) one-vs-allclassifiers, one per label that incorporate label text as well as label
correlations, 3) a shortlister that offers high-recall label shortlists
for data points, allowing ECLARE to offer sub-millisecond prediction times even with millions of labels, and 4) a label correlationgraph that is used to train both the one-vs-all classifiers as well as
the shortlister. This section details these components as well as atechnique to infer label correlation graphs from training data itself.
Notation. Let 𝐿 denote the number of labels and 𝑉 the dictionary
size. All 𝑁 training points are presented as (x𝑖 , y𝑖 ). x𝑖 ∈ R𝑉 is abag-of-tokens representation for the 𝑖 th document i.e. 𝑥𝑖𝑡 is the
TF-IDF weight of token 𝑡 ∈ [𝑉 ] in the 𝑖 th document. y𝑖 ∈ {−1, +1}𝐿is the ground truth label vector with 𝑦𝑖𝑙 = +1 if label 𝑙 ∈ [𝐿] is

ReLU

Fur
for STOP
Women

ℰ𝐷
𝐱ො 0

Document Text Embedding𝐱ො = RELU ℰ𝐷 𝐱ො 0

𝐱ො 0 = 𝐄𝐱 = σ𝑡∈ 𝑉 𝑥𝑡 ⋅ 𝐞𝑡

𝐰𝑙

𝒜
𝐳ො𝑙3
Dog

𝛼𝑙3

𝛼𝑙1

𝐳ො𝑙1

of STOP
Osu

𝛼𝑙2

𝐳ො𝑙2

ℰ𝐺

ℰ𝐿
𝐳ො𝑙0

𝐆

LTE
𝐳ො𝑙1 = ℰ𝐿 𝐳ො𝑙0 , 𝐳ො𝑙0 = 𝐄𝐳𝑙
0𝐳ො𝑙𝟐 = ℰ𝐺 σ𝑚∈ 𝐿 𝐆𝑙𝑚 ⋅ 𝐳ො𝑚
GALE
3
3
2
2
1
Classifier 𝐰𝑙 = 𝛼𝑙 ⋅ 𝐳ො𝑙 ⊕ 𝛼𝑙 ⋅ 𝐳ො𝑙 ⊕ 𝛼𝑙 ⋅ 𝐳ො𝑙1

Figure 3: (Left) Document Embedding: ECLARE uses thelight-weight embedding block E (see Fig 2) to embed documents, ensuring rapid processing at test time (see Fig 6). Stopwords such as for, of ) are discarded. (Right) Label classifiers:
ECLARE incorporates multiple forms of label metadata including label text (LTE) and label correlation graphs (GALE),
fusing them with a per-label refinement vector ẑ𝑙3 using theattention block (see Fig 2) to create a one-vs-all classifier w𝑙for each label 𝑙 ∈ [𝐿]. Connections to and from the attention
block are shown in light gray to avoid clutter. A separate instance of the embedding block is used to obtain document
embeddings (E𝐷 ), LTE (E𝐿 ) and GALE (E𝐺 ) embeddings.

relevant to the 𝑖 th document and 𝑦𝑖𝑙 = −1 otherwise. For each label𝑙 ∈ [𝐿], its label text is similarly represented as z𝑙 ∈ R𝑉 .

3.1

Document Embedding Architecture

ECLARE learns 𝐷-dimensional embeddings for each vocabulary
token E = [e1, . . . , e𝑉 ] ∈ R𝐷×𝑉 and uses a light-weight embedding
block (see Fig 2) implementing a residual layer. The embedding
block E contains two trainable parameters, a weight matrix R and ascalar weight 𝜆 (see Fig 2). Given a document x ∈ R𝑉 as a sparse bagof-words vector, ECLARE performs a rapid embedding (see Fig 3) by
first using the token embeddings to obtain an initial representationx̂0 = Ex ∈ R𝐷 , and then passing this through an instantiation E𝐷
of the text embedding block, and a ReLU non-linearity, to obtainthe final representation x̂. All documents (train/test) share the sameembedding block E𝐷 . Similar architectures have been shown to bewell-suited to short-text applications [8, 31].

3.2

Label Correlation Graph

XC applications often fail to provide label correlation graphs directly as an input. Moreover, since these applications also face extreme label sparsity, using label co-occurrence alone yields fractured
correlations as discussed in Sec 2. For example, label correlations
gleaned from products purchased together in the same session, or
else queries on which advertisers bid together, may be very sparse.
To remedy this, ECLARE infers a label correlation graph using the
ground-truth label vectors i.e. y𝑖 , 𝑖 ∈ [𝑁 ] themselves. This ensuresthat ECLARE is able to operate even in situations where the application is unable to provide a correlation graph itself. ECLARE
adopts a scalable strategy based on random walks with restarts (seeAlgorithm 1) to obtain a label correlation graph G𝑐 ∈ R𝐿×𝐿 that

WWW ’21, April 19–23, 2021, Ljubljana, Slovenia

Algorithm 1 Label Correlation Graph Genration. 𝑁 , 𝐿 denotethe number of training points and labels. 𝜔 and 𝑝 denote the walklength and restart probability. Y = [y1, . . . , y𝑁 ] ∈ {−1, +1}𝐿×𝑁 is
a matrix giving the relevant training labels for each document. For
any set 𝑆, Unif(𝑆) returns a uniformly random sample from 𝑆. The
subroutine WalkFrom performs a walk starting at the label 𝑙.
1: procedure WalkFrom(𝑙, Y, 𝜔, 𝑝)2:v ← 0 ∈ R𝐿

⊲ Initialize visit counts
𝜆 ←𝑙⊲ Start the walk from the label 𝑙
4:for 𝑡 = 1; 𝑡 ≤ 𝜔; 𝑡++ do5:
𝜙 ← Unif([0, 1])⊲ Random number in [0, 1]
6:
if 𝜙 ≤ 𝑝 then7:
𝜆 =𝑙⊲ Restart if need be8:𝛿 ← Unif({𝑖⊲ Sample a relevant doc
 : 𝑌𝜆𝑖 = +1})
9:
𝜆 ← Unif( 𝑗 : 𝑌 𝑗𝛿 = +1 )⊲ Sample a relevant label
10:v[𝜆]++⊲ Update the visit counts
11:
return v
12: procedure RandomWalk(𝐿, Y, 𝜔, 𝑝)
13:
G𝑐 ← 00⊤ ∈ R𝐿×𝐿
⊲ Initialize visit counts
14:
for 𝑙 = 1; 𝑙 ≤ 𝐿; 𝑙++ do
15:
G𝑙𝑐 ← WalkFrom(𝑙, Y, 𝜔, 𝑝)⊲ Update row 𝑙 of G𝑐

Mittal and Sachdeva, et al.
Kangal Dog

Kangal Dog
Anatolian
Shepherd

Anatolian
Shepherd
Akbash Dog

Akbash Dog

Kangal Dog
Sarabi Mastiff

Gaddi Kutta

Aksaray
Malaklisi Dog

Bully Kutta

Tibetan Mastiff

Sarabi Mastiff

Gaddi Kutta

return G𝑐

Akbash Dog

Aksaray
Malaklisi Dog

Bully Kutta

Aksaray
Malaklisi Dog

Tibetan Mastiff
Bully Kutta

3:

16:

documents
Legendlabelsknown co-occurrencesinferred correlations

Documents

LabelsGround-truth labelling

Tibetan Mastiff

Random Walks

Discovered Label Correlations(different colors denote
distinct restarts)(edge colors correspond to therestart that discovered them)

Figure 4: An execution of Algorithm 1 on a subset of the
LF-WikiSeeAlsoTitles-320K dataset starting from the label“Kangal Dog”. (Left) ECLARE uses document-label associations taken from ground-truth label vectors (black color)
to infer indirect correlations among labels. (Middle) Random walks (with distinct restarts colored differently) infer diverse correlations. (Right) These inferred correlations(marked with the color of the restart that discovered them)augment the meager label co-occurrences present in the
ground truth (marked with dotted lines).

augments the often meager label co-occurrence links (see Fig 4)
present in the ground truth. Non-rare labels (the so-called head
and torso labels) pose a challenge to this step since they are often
correlated with several labels and can overwhelm the rare labels.
ECLARE takes two precautions to avoid this:(1) Partition: Head labels (those with > 500 training points) aredisconnected from the graph by setting G𝑐ℎℎ = 1 and G𝑐ℎ𝑡 = 0 =G𝑐𝑡ℎ for all all head labels ℎ ∈ [𝐿] and 𝑡 ≠ ℎ (see Fig 5).
(2) Normalization: G𝑐 is normalized to favor edges to/from rarelabels as G = A−1/2 ·G𝑐 ·B−1/2 , where A, B ∈ R𝐿×𝐿 are diagonal
matrices with the row and column-sums of G𝑐 respectively.
Algorithm 1 is used with a restart probability of 80% and a random
walk length of 400. Thus, it is overwhelmingly likely that several
dozens of restarts would occur for each label. A high restart probability does not let the random walk wander too far thus preventing
tenuous correlations among labels from getting captured.

3.3

LegendHead label
Non-head label
Meta label cluster
Label correlation edge
Metalabel correlation edge

Figure 5: To avoid head labels from distorting label correlation patterns, labels with > 500 training points are forcibly
disconnected from the label correlation graph and also clustered into head meta-labels separately. Consequently, theGALE and GAME steps have a trivial action on head labels.

Label Representation and Classifiers

As examples in Tab 6 discussed in Sec 4 show, label text alone
may not sufficiently inform classifiers for rare labels. ECLARE
remedies this by learning high-capacity one-vs-all classifiers W =[w1, . . . , w𝐿 ] ∈ R𝐷×𝐿 with 3 distinct components described below.
Label Text Embedding (LTE). The first component incorporates
label text metadata. A separate instance E𝐿 of the embedding blockis used to embed label text. Given a bag-of-words representationz𝑙 ∈ R𝑉 of a label, the LTE representation is obtained as ẑ𝑙1 = E𝐿 (ẑ𝑙0 )where as before, we have the “initial” representation ẑ𝑙0 = Ez𝑙 . The
embedding block E𝐿 is shared by all labels. We note that the DECAF
method [31] also uses a similar architecture to embed label text.

Graph Augmented Label Embedding (GALE). ECLARE augments the LTE representation using the label correlation graph
G constructed earlier and a graph convolution network (GCN) [24].
This presents a departure from previous XC approaches. A typicalgraph convolution operation consists of two steps which ECLARE
effectively implements at extreme scales as shown below(1) Convolution: initial label representations are convolved in aÍ
0 . Note thatscalable manner using G as z̃𝑙2 = 𝑚 ∈ [𝐿] 𝐺𝑙𝑚 · ẑ𝑚
due to random restarts used by Algorithm 1, we have 𝐺𝑙𝑙 > 0
for all 𝑙 ∈ [𝐿] and thus z̃𝑙2 contains a component from ẑ𝑙0 itself.
(2) Transformation: Whereas traditional GCNs often use a simple
non-linearity as the transformation, ECLARE instead uses a

ECLARE: Extreme Classification with Label Graph Correlations

separate instance E𝐺 of the embedding block to obtain the
GALE representation of the label as ẑ𝑙2 = E𝐺 ( z̃𝑙2 ).
ECLARE uses a single convolution and transformation operation
which allowed it to scale to applications with millions of nodes.
Recent works such as LightGCN [14] propose to accelerate GCNs
by removing all non-linearities. Despite being more scalable, using
LightGCN alone was found to offer imprecise results in experiments. This may be because ECLARE also uses LTE representations.
Thus ECLARE can be seen as improving upon existing architectures
such as LightGCN by performing higher order label-text augmen𝜅 (Í𝜅0tations for 𝜅 = 0, . . . , 𝑘 as ẑ𝑙𝜅+1 = E𝐺𝑚 ∈ [𝐿] 𝐺𝑙𝑚 · ẑ𝑚 ) whereÎ𝜅𝜅𝜅
G = 𝑗=1 G encodes the 𝜅−hop neighborhood, and E𝐺 is a separate embedding block for each order 𝜅. Thus, ECLARE’s architecture
allows parallelizing high-order convolutions. Whereas ECLARE
could be used with larger orders 𝑘 > 1, using 𝑘 = 1 was found toalready outperform all competing methods, as well be scalable.
Refinement Vector and Final Classifier. ECLARE combines the
LTE and GALE representations for a label with a high-capacity
per-label refinement vector ẑ𝑙3 ∈ R𝐷 (ẑ𝑙𝑘+2 for a general value of 𝑘)
to obtain a one-vs-all classifier w𝑙 (see Fig 3). To combine ẑ𝑙1, ẑ𝑙2, ẑ𝑙3 ,ECLARE uses a parameterized attention block A (see Fig 2) to learnlabel-specific attention weights for the three components. This isdistinct from previous works such as DECAF which use weightsthat are shared across labels. Fig 9 shows that ECLARE benefits fromthis flexibility, with the refinement vector ẑ𝑙3 being more dominant
for popular labels that have lots of training data whereas the label
metadata based vectors ẑ𝑙2, ẑ𝑙1 being more important for rare labelswith less training data. The attention block is explained below (seealso Fig 2). Note that ECLARE uses 𝑘 = 1.
𝑡 (x) = 𝜎 (T · ReLU(x))
hiq𝑙 = 𝑡 (ẑ𝑙1 ); . . . ; 𝑡 (ẑ𝑙𝑘+2 )hi
exp(A · q𝑙 )𝛼𝑙1, . . . , 𝛼𝑙𝑘+2 =∥exp(A · q𝑙 )∥ 1
w𝑙 = 𝛼𝑙1 · ẑ𝑙1 + . . . + 𝛼𝑙𝑘+2 · ẑ𝑙𝑘+2
The attention block is parameterized by the matrices T ∈ R𝐷×𝐷 andA ∈ R (𝑘+2)×(𝑘+2)𝐷 . q𝑙 ∈ R (𝑘+2)𝐷 concatenates the transformed
components before applying the attention layer A. The above attention mechanism can be seen as a scalable
paramaterized approx
imation (requiring only O 𝑑 2 + 𝑘 2 𝐷 additional parameters) of amore expensive label-specific attention scheme which would haverequired learning 𝐿 × (𝑘 + 2) parameters.

3.4

Meta-labels and the Shortlister

Despite being accurate, if used naively, one-vs-all classifiers requireΩ (𝐿𝐷) time at prediction and Ω (𝑁 𝐿𝐷) time to train. This is infeasible with millions of labels. As discussed in Sec 2, sub-linear
structures are a common remedy in XC methods to perform label
shortlisting during prediction [4, 6, 8, 15, 22, 36, 45]. These shortlisting techniques take a data point and return a shortlist of O (log 𝐿)labels that is expected to contain most of the positive labels forthat data point. However, such shortlists also help during training
since the negative labels that get shortlisted for a data point are

WWW ’21, April 19–23, 2021, Ljubljana, Slovenia

𝐱ො
ReLU

ℰ𝐷
TibetanTerrier

L15 𝒮 L12
L15 𝒮 L12
L8
L8
L2
L2
L10 L6 L4L10 L6 L4
L17
L17
L16 L9L16 L9
L14
L14
L3
L3
L11 L18 L1
L11 L18 L1
L5
L5 ShortL7
L7
listing
L13 GAME
L13 failure

ℛ
𝐰𝟔, 𝐳
𝐰7, 𝐳
𝐰𝟑, 𝐳
𝐰 𝟏𝟔 , 𝐳𝐰𝟗, 𝐳𝐰1 , 𝐳𝐰14 , 𝐳𝐰11 , 𝐳Doc Emb. Shortlisting + GAME (red ⇒ relevant) Ranking + GAME

Figure 6: Prediction Pipeline: ECLARE uses a low-cost prediction pipeline that can make millisecond-level predictions
with millions of labels. Given a document/query x, its text
embedding x̂ (see Fig 3) is used by the shortlister S to obtain
the O (log 𝐿) most probable labels while maintaining highrecall using label correlation graphs via GAME. Label classifiers (see Fig 3) for only the shortlisted labels are then usedby the ranker R to produce the final ranking of labels.

arguably the most challenging and likely to get confused as being
positive for that data point. Thus, training is done only on positive and shortlisted negative labels, bringing training time down
to O (𝑁 𝐷 log 𝐿). Similar to previous works [31, 35], ECLARE uses
a clustering-based shortlister S = {C, H} where C = {𝐶 1, . . . , 𝐶𝐾 }is a balanced partitioning of the 𝐿 labels into 𝐾 clusters. We referto each cluster as a meta label. H = [h1, . . . , h𝐾 ] ∈ R𝐷×𝐾 is a set ofone-vs-all classifiers, learnt one per meta label.
Graph Assisted Multi-label Expansion (GAME). ECLARE incorporates graph correlations to further to improve its shortlister. Let M ∈ {0, 1}𝐿×𝐾 denote the cluster assignment matrix i.e.
𝑀𝑙𝑚 = 1 if label 𝑙 is in cluster 𝑚. We normalize M so that eachcolumn sums to unity. Given a data point x and a beam-size 𝐵, its
embedding x̂ (see Fig 3) is used to shortlist labels as follows(1) Find the top 𝐵 clusters, say 𝑃 = {𝑚˜ 1, . . . , 𝑚˜ 𝐵 } ⊂ [𝐾] according
to the meta-label scores h𝑚1 , x̂ ≥ h𝑚2 , x̂ ≥ . . .. Let p̃ ∈ R𝐾
be a vector containing scores for the top 𝐵 clusters passed
through a sigmoid i.e. 𝑝˜𝑚 = 𝜎 (⟨h𝑚 , x̂⟩) if 𝑚 ∈ 𝑃 else 𝑝˜𝑚 = 0.
(2) Use the induced cluster-cluster correlation matrix G𝑀 = M⊤ GM
to calculate the “GAME-ified” scores p = G𝑀 · p̃.
(3) Find the top 𝐵 clusters according to p, say 𝑚 1, . . . , 𝑚𝐵 , retain
their scores and set scores of other clusters in p to 0. Return the
shortlist S( x̂) = {𝑚 1, . . . , 𝑚𝐵 } and the modified score vector p.
Note that this cluster re-ranking step uses an induced cluster correlation graph and can bring in clusters with rare labels missedby the one-vs-all models h𝑚 . This is distinct from previous works
which do not use label correlations for re-ranking. Since the clusters are balanced, the shortlisted clusters always contain a total of|S( x̂)| = 𝐿𝐵/𝐾 labels. ECLARE uses 𝐾 = 217 clusters and a beam
size of 𝐵 ≈ 30 − 50 (see Sec 4 for a discussion on hyperparameters).

3.5

Prediction with GAME

The prediction pipeline for ECLARE is depicted in Fig 6 and involves
3 steps that repeatedly utilize label correlations via GAME.

WWW ’21, April 19–23, 2021, Ljubljana, Slovenia(1) Given a document x, use the shortlister S to get a set of 𝐵
meta labels S( x̂) and their corresponding scores p ∈ R𝐾 .
(2) For shortlisted labels, apply the one-vs-all classifiers w𝑙to calculate the ranking score vector r̃ ∈ R𝐿 with 𝑟˜𝑙 =𝜎 (⟨w𝑙 , x̂⟩) if 𝑙 ∈ 𝐶𝑚 for some 𝑚 ∈ S( x̂) else 𝑟˜𝑙 = 0.
(3) GAME-ify the one-vs-all scores to get r = G · r̃ (note that G
is used this time and not G𝑀 ). Make final predictions using
the joint scores 𝑠𝑙 := 𝑟𝑙 · 𝑝𝑚 if 𝑙 ∈ 𝐶𝑚 , 𝑚 ∈ S( x̂) else 𝑠𝑙 = 0.

3.6

Efficient Training: the DeepXML Pipeline

Summary. ECLARE adopts the scalable DeepXML pipeline [8] thatsplits training into 4 modules. In summary, Module I jointly learns
the token embeddings E, the embedding block E𝐷 and the shortlister S. E remains frozen hereon. Module II refines P and uses
it to retrieve label shortlists for all data points. After performing
initialization in Module III, Module IV uses the shortlists generated
in Module II to jointly fine-tune E𝐷 and learn the one-vs-all classifiers W, implicitly learning the embedding blocks E𝐿 , E𝐺 and theattention block A in the process.
Module I. Token embeddings E ∈ R𝐷×𝑉 are randomly initializedusing [13], the residual block within E𝐷 is initialized to identity.
After creating label clusters (see below), each cluster is treated as ameta-label yielding a meta-XC problem on the same training points,
but with 𝐾 meta-labels instead of the original 𝐿 labels. Meta-labelÍtext is created for each 𝑚 ∈ [𝐾] as u𝑚 = 𝑙 ∈𝐶𝑚 z𝑙 . Meta labels arealso endowed with the meta-label correlation graph G𝑀 = M⊤ GM
where M ∈ {0, 1}𝐿×𝐾 is the cluster assignment matrix. One-vs-all
meta-classifiers H = [h1, . . . , h𝐾 ] ∈ R𝐷×𝐾 are now learnt to solve
this meta XC problem. These classifiers have the same form as thosefor the original problem with 3 components, LTE, GALE, (with corresponding blocks Ẽ𝐿 , Ẽ𝐺 ) and refinement vector, with an attention
block Ã supervising their combination (parameters within Ã are
initialized randomly). However, in Module-I, refinement vectors
are turned off for h𝑙 to force good token embeddings E to be learnt
without support from refinement vectors. Module I solves the meta
XC problem while training E𝐷 , Ẽ𝐿 , Ẽ𝐺 , Ã, E, implicitly learning H.
Meta-label Creation with Graph Augmented Label Centroids.
Existing approaches such as Parabel or DECAF cluster labels by
creating a label centroid for each label 𝑙 by aggregating features forÍ
training documents associated with that label as c𝑙 = 𝑖:𝑦𝑖𝑙 =+1 x𝑖 .
However, ECLARE recognizes that missing labels often lead to an
incomplete ground truth, and thus, poor label centroids for rarelabels in XC settings [2, 17]. Fig 8 confirms this suspicion. ECLARE
addresses this by augmenting the label centroids using the label coÍ
occurrence graph G to redefine the centroids as ĉ𝑙 = 𝐿𝑗=1 𝐺𝑙 𝑗 · c𝑙 .
Balanced hierarchical binary clustering [36] is now done on theselabel centroids for 17 levels to generate 𝐾 = 217 label clusters. Notethat since token embeddings have not been learnt yet, the raw TFIDF documents vectors x𝑖 ∈ R𝑉 are used instead of x̂𝑖 ∈ R𝐷 .
Module II. The shortlister is fine-tuned in this module. LabelÍ
centroids are recomputed as ĉ𝑙 = 𝐿𝑗=1 𝐺𝑙 𝑗 · c𝑙 where this time,Íc𝑙 = 𝑖:y𝑖 =+1 Ex𝑖 using E learnt in Module I. The meta XC prob𝑙lem is recreated and solved again. However, this time, ECLARE

Mittal and Sachdeva, et al.

allows the meta-classifiers h𝑚 to also include refinement vectors
to better solve the meta-XC problem. In the process of re-learning
H, the model parameters E𝐷 , Ẽ𝐿 , Ẽ𝐺 , Ã are fine-tuned (E is frozen
after Module I). The shortlister S thus obtained is thereafter used
to retrieve shortlists S( x̂𝑖 ) for each data point 𝑖 ∈ [𝑁 ]. However,distinct from previous work such as Slice [15], X-Transformer [6],DECAF [31], ECLARE uses the GAME strategy to obtain negative
samples that take label correlations into account.
Module III. Residual blocks within E𝐷 , E𝐿 , E𝐺 are initialized to
identity, parameters within A are initialized randomly, and theshortlister S and token embeddings E are kept frozen. RefinementÍvectors for all 𝐿 labels are initialized to ẑ𝑙3 = 𝑚 ∈ [𝐿] 𝐺𝑙𝑚 · Ez𝑚 .
We find this initialization to be both crucial (see Sec 4) as well
as distinct from previous works such as DECAF which initialized its counterpart of refinement vectors using simply Ez𝑙 . Suchcorrelation-agnostic initialization was found to offer worse results
than ECLARE’s graph augmented initialization.
Module IV. In this module, the embedding blocks E𝐷 , E𝐿 , E𝐺 are
learnt jointly with the per-label refinement vectors ẑ𝑙3 and attention
block A, thus learning the one-vs-all classifiers w𝑙 in the process,However, training is done in O (𝑁 𝐷 log 𝐿) time by restricting training to positives and shortlisted negatives for each data point.
Loss Function and Regularization. ECLARE uses the binary
cross entropy loss function for training in Modules I, II and IV
using the Adam [23] optimizer. The residual weights R in the various embedding blocks E𝐷 , E𝐿 , E𝐺 , Ẽ𝐿 , Ẽ𝐺 as well as the weights Tin the attention block were all subjected to spectral regularization[32]. All ReLU layers in the architecture also included a dropout
layer with 20% rate.
Key Contributions in Training. ECLARE markedly departs fromexisting techniques by incorporating label correlation information
in a scalable manner at every step of the learning process. Rightfrom Module I, label correlations are incorporated while creating
the label centroids leading to higher quality clusters (see Fig 8
and Table 7). The architecture itself incorporates label correlation
information using the GALE representations. It is crucial to initialize the refinement vectors ẑ𝑙3 properly for which ECLARE uses agraph-augmented initialization. ECLARE continues infusing label
correlation during negative sampling using the GAME step. Finally,
GAME is used multiple times in the prediction pipeline as well.
As the discussion in Sec 4 will indicate, these augmentations are
crucial to the performance boosts offered by ECLARE.

4EXPERIMENTS

Datasets and Features. ECLARE was evaluated on 4 publicly available1 benchmark datasets, LF-AmazonTitles-131K, LF-WikiSeeAlsoTitles-320K, LF-WikiTitles-500K and LF-AmazonTitles-1.3M. These
datasets were derived from existing datasets e.g. Amazon-670K,
by taking those labels for which label text was available and performing other sanitization steps such as reciprocal pair removal(see [31] for details). ECLARE was also evaluated on proprietary
1 Extreme Classification Repository [3]ECLARE: Extreme Classification with Label Graph Correlations

WWW ’21, April 19–23, 2021, Ljubljana, Slovenia

Table 1: Dataset Statistics. A ‡ sign denotes information that was redacted for proprietary datasets. The first four rows are
public datasets and the last two rows are proprietary datasets. Dataset names with an asterisk ∗ next to them correspond to
product-to-category tasks whereas others are product-to-product tasks.
Train Documents
𝑁

Labels𝐿

Tokens𝑉

LF-AmazonTitles-131K
LF-WikiSeeAlsoTitles-320K
LF-WikiTitles-500K∗
LF-AmazonTitles-1.3M

294,805
693,082
1,813,391
2,248,619

131,073
312,330
501,070
1,305,265

40,00040,00080,000128,000

LF-P2PTitles-2M
LF-P2PTitles-10M

2,539,009
6,849,451

1,640,898
9,550,772‡‡

DatasetTest Instances
𝑁′

Average Labels
per Document

Average Points
per label

Average Tokens
per Document

Average Tokens
per Label

2.29
2.11
4.74
22.20

5.15
4.68
17.15
38.24

7.46
3.97
3.72
9.00

7.15
3.92
4.16
9.45

‡
‡

‡
‡

‡
‡

‡
‡

Short text dataset statistics
134,835
177,515
783,743
970,237
Proprietary dataset
1,088,146
2,935,479

datasets P2P-2M and P2P-10M, both mined from click logs of theBing search engine, where a pair of products were considered similar if the Jaccard index of the set of queries which led to a clickon them was found to be more than a certain threshold. ECLARE
used the word piece tokenizer [39] to create a shared vocabulary
for documents and labels. Please refer to Tab 1 for dataset statistics.
Baseline algorithms. ECLARE’s performance was compared tostate-of-the-art deep extreme classifiers which jointly learn document and label representations such as DECAF [31], AttentionXML[49], Astec [8], X-Transformer [6], and MACH [28]. DECAF and
X-Transformer are the only methods that also use label text andare therefore the most relevant for comparison with ECLARE. For
the sake of completeness, ECLARE was also compared to classifiers
which use fixed document representations like DiSMEC [1], Parabel [36], Bonsai [22], and Slice [15]. All these fixed-representation
methods use BoW features, except Slice which used pre-trained
FastText [5] features. The GLaS [10] method could not be included
in our analysis as its code was not publicly available.
Evaluation. Methods were compared using standard XC metrics,
namely Precision (P@𝑘) and Propensity-scored precision (PSP@𝑘) [17].
Recall (R@𝐾) was also included since XC methods are typicallyused in the shortlisting pipeline of recommendation systems. Thus,
having high recall is equally important as having high precision.
For evaluation, guidelines provided on the XML repository [3] were
followed. To be consistent, all models were run on a 6-core Intel
Skylake 2.4 GHz machine with one Nvidia V100 GPU.
Hyper-parameters. A beam size of 𝐵 = 30 was used for the dataset
LF-AmazonTitles-131K and 𝐵 = 50 for all other datasets. Embedding dimension 𝐷 was set to 300 for datasets with < 400K labels
and 512 otherwise. The number of meta-labels 𝐾 = |C| was fixed
to |C| = 217 for all other datasets except for LF-AmazonTitles-131K
where |C| = 215 was chosen since the dataset itself has around 217
labels. The default PyTorch implementation of the Adam optimizer
was used. Dropout with probability 0.2 was used for all datasets.
Learning rate was decayed by a decay factor of 0.5 after an intervalof 0.5× epoch length. Batch size was taken to be 255 for all datasets.
ECLARE Module-I used 20 epochs with an initial learning rate of
0.01. In Modules-II and IV, 10 epochs were used for all datasets withan initial learning rate of 0.008. While constructing the label correlation graph using random walks (see Algorithm 1), a walk lengthof 400 and restart probability of 80% were used for all datasets.
Results on benchmark datasets. Tab 2 demonstrates that ECLARE
can be significantly more accurate than existing XC methods. In
particular, ECLARE could be upto 3% and 10% more accurate ascompared to DECAF and X-Transformer respectively in terms of
P@1. It should be noted that DECAF and X-Transformer are theonly XC methods which use label meta-data. Furthermore, ECLARE
could outperform Astec which is specifically designed for rare labels, by up to 7% in terms of PSP@1, indicating that ECLARE offers
state-of-the-art accuracies without compromising on rare labels. To
further understand the gains of ECLARE, the labels were divided
into five bins such that each bin contained an equal number of positive training points (Fig 7). This ensured that each bin had an equal
opportunity to contribute to the overall accuracy. Fig 7 indicatesthat the major gains of ECLARE come from predicting rare labels
correctly. ECLARE could outperform all other deep-learning-based
XC methods, as well as fixed-feature-based XC methods by a significant margin of at least 7%. Moreover, ECLARE’s recall could be up
to 2% higher as compared to all other XC methods.
Results on Propreitary Bing datasets. ECLARE’s performance
was also compared on the proprietary datasets LF-P2PTitles-2M
and LF-P2PTitles-10M. Note that ECLARE was only compared withthose XC methods that were able to scale to 10 million labels on asingle GPU within a timeout of one week. ECLARE could be up to
14%, 15%, and 15% more accurate as compared to state-of-the-art
methods in terms of P@1, PSP@1 and R@10 respectively. Pleaserefer to Tab 3 for more details.
Ablation experiments. To scale accurately to millions of labels,
ECLARE makes several meticulous design choices. To validate theirimportance, Tab 5 compares different variants of ECLARE:(1) Label-graph augmentations: The label correlation graph G isused by ECLARE in several steps, such as in creating meaningful
meta labels, negative sampling, shortlisting of meta-labels, etc.
To evaluate the importance of these augmentations, in ECLARENoGraph, the graph convolution component G was removed

WWW ’21, April 19–23, 2021, Ljubljana, Slovenia

Mittal and Sachdeva, et al.

Table 2: Results on public benchmark datasets. ECLARE
could offer 2-3.5% higher P@1 as well as upto 5% higher
PSP@1 which focuses on rare labels. Additionally, ECLARE
offered up to 3% better recall than leading XC methods.
Method

PSP@1

PSP@5

P@1

P@5

R@10

Prediction
Time (ms)

LF-AmazonTitles-131K
ECLARE
DECAF
Astec
AttentionXML
Slice
MACH
X-Transformer
SiameseBonsaiParabelDiSMECXT
AnneXML

33.18
30.85
29.22
23.97
23.08
24.97
21.72
13.3
24.75
23.27
25.86
22.37
19.23

ECLARE
DECAF
Astec
AttentionXML
Slice
MACH
SiameseBonsaiParabelDiSMECXT
AnneXML

21.36
16.73
13.69
9.45
11.24
9.68
10.1
10.69
9.24
10.56
8.99
7.24

44.1
41.42
39.49
32.57
31.89
34.72
27.09
13.36
34.86
32.14
36.97
31.64
32.26

40.46
38.4
37.12
32.25
30.43
33.49
29.95
13.81
34.11
32.6
35.14
31.41
30.05

19.63
18.65
18.24
15.61
14.84
16.45
13.07
5.81
16.63
15.61
17.24
15.48
16.02

53.51
51.2
49.87
42.3
41.16
44.75
35.59
14.69
45.17
41.63
46.84
42.11
45.57

0.1
0.1
2.34
5.19
1.58
0.23
15.38
0.2
7.49
0.69
5.53
9.12
0.11

35.62
32.51
28.18
20.56
24.45
22.69
10.34
23.61
20.95
24.81
21.73
23.06

0.12
0.09
2.67
7.08
1.85
0.52
0.17
14.82
0.8
11.02
12.86
0.13

31.66
31.29
29.7
26.26
20.21
19.08
29.66
28.43
22.51
26.79

0.32
0.16
2.61
29.53
1.45
2.09
39.03
0.89
5.94
0.12

30.59
32.02
31.58
25.8
22.65
23.81
28.04
27.34
26.73
26.48
26.27

0.14
0.09
2.7
9
1.76
0.8
17.38
0.81
11.71
7.56
0.13

LF-WikiSeeAlsoTitles-320K
25.46
21.01
17.5
11.73
15.2
12.53
9.59
13.79
11.8
14.82
11.82
11.75

28.82
25.14
22.72
17.56
18.55
18.06
10.69
19.31
17.68
19.12
17.04
16.3

14.65
12.86
11.43
8.52
9.68
8.99
4.51
9.55
8.59
9.87
8.6
8.84

LF-AmazonTitles-1.3M
ECLARE
DECAF
Astec
AttentionXML
Slice
MACH
BonsaiParabelDiSMECXT
AnneXML

22.94
22.07
21.47
15.97
13.96
9.32
18.48
16.94
13.67
15.42

ECLARE
DECAF
Astec
AttentionXML
Slice
MACH
BonsaiParabelDiSMECXT
AnneXML

21.58
19.29
18.31
14.8
13.9
13.71
16.58
15.55
15.88
14.1
13.91

30.29
29.3
27.86
22.54
19.14
13.26
25.95
24.13
19.06
21.91

49.46
50.67
48.82
45.04
34.8
35.68
47.87
46.79
40.6
47.79

39.62
40.35
38.44
36.25
27.71
28.35
38.34
37.65
32.01
36.91

LF-WikiTitles-500K
19.84
19.96
18.56
13.88
13.82
12
16.4
15.35
15.89
14.38
13.75

44.36
44.21
44.4
40.9
25.48
37.74
40.97
40.41
39.42
38.13
39

16.91
17.36
17.49
15.05
10.98
13.26
15.66
15.42
14.85
14.66
14.55

from all training steps such as GAME, except while generating the label classifiers (GALE). ECLARE-NoGraph was foundTable 3: Results on proprietary product-to-product (P2P)
recommendation datasets. ECLARE could offer significant
gains – upto 14% higher P@1, 15% higher PSP@1 and 7%
higher R@10 – than competing classifiers.
Method

PSP@1

PSP@3

PSP@5

P@1

P@3

P@5

R@10

39.25
36.65
33.33
32.44

33.15
31.45
28.74
28.06

54.44
48.46
46.07
42.84

39.93
25.75
27.49
27.77

36.9
23.99
25.85
26.1

35.82
20.9
22.3
22.81

LF-P2PTitles-2M
ECLARE
DECAF
Astec
Parabel

41.97
36.65
32.75
30.21

44.92
40.14
36.3
33.85

ECLARE
DECAF
Astec
Parabel

35.52
20.51
20.31
19.99

37.91
21.38
22.16
22.05

49.46
45.15
41
38.46

43.79
40.27
36.34
35.26

LF-P2PTitles-10M
39.91
22.85
24.23
24.33

43.14
28.3
29.75
30.22

Table 4: An ablation study exploring the benefits of the
GAME step for other XC methods. Although ECLARE still
provides the leading accuracies, existing methods show consistent gains from the use of the GAME step.
Method

PSP@1

PSP@5

P@1

P@5

PSP@1

PSP@5

P@1

P@5

LF-AmazonTitles-131K
Original
ECLARE
ParabelAttentionXML

23.27
23.97

32.14
32.57

|
32.6
32.25

With GAME
33.18
24.81
24.63

15.61
15.61

44.1
34.94
34.48

40.46
33.24
32.59

19.63
16.51
16.25

LF-WikiSeeAlsoTitles-320K
Original
ECLARE
ParabelAttentionXML

9.24
9.45

11.8
11.73

|
17.68
17.56

8.59
8.52

With GAME
21.36
10.28
10.05

25.46
13.06
12.59

28.82
17.99
17.49

14.65
9
8.77

to be up to 3% less accurate than ECLARE. Furthermore, in avariant ECLARE-PPR, inspired by state-of-the-art graph algorithms [25, 48], negative sampling was performed via Personalized Page Rank. ECLARE could be up to 25% more accurate than
ECLARE-PPR. This could be attributed to the highly sparse label correlation graph and justifies the importance of ECLARE’slabel correlation graph as well as it’s careful negative sampling.
(2) Label components: Much work has been done to augment(document) text representations using graph convolution networks (GCNs) [12, 14, 24, 34, 42, 43, 51]. These methods could
also be adapted to convolve label text for ECLARE’s GALE
component. ECLARE’s GALE component was replaced by aLightGCN [14] and GCN [24] (with the refinement vectors inplace). Results indicate that ECLARE could be upto 2% and 10%
more accurate as compared to LightGCN and GCN. In anothervariant of ECLARE, the refinement vectors ẑ𝑙3 were removed(ECLARE-NoRefine). Results indicate that ECLARE could be up
to 10% more accurate as compared to ECLARE-NoRefine whichindicates that the per-label (extreme) refinement vectors are
essential for accuracy.
(3) Graph construction: To evaluate the efficacy of ECLARE’sgraph construction, we compare it to ECLARE-Cooc where

ECLARE: Extreme Classification with Label Graph Correlations

WWW ’21, April 19–23, 2021, Ljubljana, Slovenia

LF-AmazonTitles-131K

Table 5: An ablation study exploring alternate design decisions. Design choices made by ECLARE for its components
were found to be optimal among popular alternatives.

Precision@5

20

ECLARE
DECAF
Astec
MACH
ParabelAttentionXML
Slice

15
10

PSP@1

PSP@3

PSP@5

P@1

P@3

P@5

40.22
30.94
38.39
39.95
39.63
14.42
37.45
39.33
29.99
38.02
39.38
37

27.25
21.12
25.59
26.9
26.64
11.04
25.45
26.41
21.6
25.54
26.57
24.86

19.67
15.52
18.44
19.39
19.24
8.75
18.46
19.05
16.32
18.49
19.22
17.93

28.82
21.76
26.31
28.54
28.24
5.21
26.11
27.73
24.83
27.59
27.77
20.31

19.36
14.61
17.64
19.06
18.88
3.82
17.59
18.48
16.61
18.5
18.64
13.51

14.65
11.14
13.35
14.4
14.3
3.5
13.35
13.99
12.66
13.99
14.14
10.22

LF-AmazonTitles-131K
50complete
54321(#131K) (#68K) (#28K) (#18K) (#11K) (#4K)(1.96) (4.72) (7.38) (12.11) (31.32)

Quantiles(Increasing Freq.)

15

Precision@5

MethodLF-WikiSeeAlsoTitles-320K
ECLARE
DECAF
Astec
MACH
ParabelAttentionXML
Slice

10

5

0

complete
54321(#312K)(#195K) (#74K) (#31K) (#9K) (#1K)(1.49) (3.94) (9.14) (30.98) (200.78)

Quantiles(Increasing Freq.)

Figure 7: Analyzing the performance of ECLARE and othermethods on popular vs rare labels. Labels were divided into
5 bins in increasing order of popularity. The plots show theoverall P@5 for each method (histogram group “complete”)
and how much each bin contributed to this value. ECLARE
clearly draws much of its P@5 performance from the binwith the rarest labels (histogram group 5), i.e ECLARE’s superiority over other methods in terms of P@5 comes frompredicting challenging rare labels and not easy-to-predict
popular labels. ECLARE’s lead over other methods is also
more prominent for rare bins (histogram groups 4, 5).

we consider the label co-occurrence graph generated by Y⊤ Y
instead of the random-walk based graph G used by ECLARE.
ECLARE-Cooc could be up to 2% less accurate in terms of PSP@1
than ECLARE. This shows that ECLARE’s random-walk graphindeed captures long-term dependencies thereby resulting in
improved performance on rare labels. Normalizing a directed
graph, such as the graph G𝑐 obtained by Algorithm 1 is a nontrivial problem. In ECLARE-PN, we apply the popular Perron
normalization [7] to the random-walk graph G𝑐 . Unfortunately,
ECLARE-PN leads to a significant loss in propensity-scoredmetrics for rare labels. This validates the choice of ECLARE’s
normalization strategy.
(4) Combining label representations: The LTE and GALE components of ECLARE could potentially be combined using strategies different from the attention mechanism used by ECLARE. A
simple average/sum of the components, (ECLARE-SUM) could

ECLAREECLARE-GCN
ECLARE-LightGCN
ECLARE-Cooc
ECLARE-PN
ECLARE-PPR
ECLARE-NoGraph
ECLARE-NoLTEECLARE-NoRefine
ECLARE-SUM
ECLARE-k=2
ECLARE-8K

33.54
24.02
31.36
32.82
32.49
12.51
30.49
32.3
28.18
31.45
32.23
29.98

ECLAREECLARE-GCN
ECLARE-LightGCN
ECLARE-Cooc
ECLARE-PN
ECLARE-PPR
ECLARE-NoGraph
ECLARE-NoLTEECLARE-NoRefine
ECLARE-SUM
ECLARE-k=2
ECLARE-8K

21.36
13.76
19.05
20.96
20.42
4.83
18.44
20.16
20.27
20.59
20.12
13.42

39.35
29.32
36.79
38.67
38.15
16.42
36.09
37.88
33.14
36.73
38.06
35.08

44.44
34.02
41.58
43.72
43.25
20.25
41.13
42.87
38.3
41.65
43.23
39.71

LF-WikiSeeAlsoTItles-320K
23.5
15.88
21.24
23.1
22.56
5.53
20.49
22.22
21.26
22.48
22.38
15.03

25.46
17.67
23.14
25.07
24.59
7.12
22.42
24.16
22.8
24.36
24.43
16.47

be up to 2% worse, which corroborates the need for the attention
mechanism for combining heterogeneous components.
(5) Higher-order Convolutions: Since the ECLARE framework
could handle higher order convolutions 𝑘 > 1 efficiently, we validated the effect of increasing the order. Using 𝑘 = 2 was foundto hurt precision by upto 2%. Higher orders e.g. 𝑘 = 3, 4 etc. wereintractable at XC scales as the graphs got too dense. The drop in
performance when using 𝑘 = 2 could be due to two reasons: (a)at XC scales, exploring higher order neighborhoods would add
more noise than information unless proper graph pruning isdone afterward and (b) ECLARE’s random-walk graph creation
procedure already encapsulates some form of higher order proximity which negates the potential for massive benefits whenusing higher order convolutions.
(6) Meta-labels and GAME: ECLARE uses a massive fanout of|C| = 217 meta-labels in its shortlister. Ablations with |C| = 213(ECLARE-8K) show that using a smaller fanout can lead to
upto 8% loss in precision. Additionally Tab 4 shows that incorporating GAME with other XC methods can also improvetheir accuracies (although ECLARE continues to lead by a wide
margin). In particular incorporating GAME in Parabel and AttentionXML led to up to 1% increase in accuracy. This validates
the utility of GAME as a general XC tool.
Analysis. This section critically analyzes ECLARE’s performancegains by scrutinizing the following components:

WWW ’21, April 19–23, 2021, Ljubljana, Slovenia

Mittal and Sachdeva, et al.

Table 6: A subjective comparison of the top 5 label predictions by ECLARE and other algorithms on the WikiSeeAlso-350K
and P2PTitles-2M datasets. Predictions typeset in black color were a part of the ground truth whereas those in light gray color
were not. ECLARE is able to offer precise recommendations for extremely rare labels missed by other methods. For instance,
the label “Dog of Osu” in the first example is so rare that it occurred only twice in the training set. This label does not have
any token overlaps with its document or co-occurring labels either. This may have caused techniques such as DECAF that
rely solely on label text, to miss such predictions. The examples also establish that incorporating label co-occurrence allows
ECLARE to infer the correct intent of a document or a user query. For instance, in the second example, all other methods,
including DECAF, either incorrectly focus on the tokens “Academy Awards” in the document title and start predicting labels
related to other editions of the Academy Awards, or else amorphous labels about entertainment awards in general. On theother hand, ECLARE is able to correctly predict other labels corresponding to award ceremonies held in the same year as
the 85th Academy awards, as well as the rare label “List of . . . Best Foreign Language Film”. Similarly, in the third example,
ECLARE correctly determines that the user is interested in faux fur coats and not necessarily in the brand Draper’s & Damon’s
itself whereas methods such as DECAF that rely solely on label and document text, focus on the brand name alone and start
predicting shirts and jackets of the same brand which are irrelevant to the user query.
Algorithm

Predictions
LF-WikiSeeAlsoTitles-320K

Document
ECLARE
DECAF
Astec
ParabelAttentionXML

Tibetan Terrier
Tibetan Spaniel, Tibetan kyi apso, Lhasa Apso, Dog of Osu, Tibetan Mastiff
Fox Terrier, Tibetan Spaniel, Terrier, Bull Terrier, Bulldog
Standard Tibetan, List of domesticated Scottish breeds, List of organizations of Tibetans in exile, Tibet, Riwoche horse
Tibet, List of organizations of Tibetans in exile, List of domesticated Scottish breeds, History of Tibet, Languages of Bhutan
List of organizations of Tibetans in exile, List of domesticated Scottish breeds, Dog, Bull Terrier, Dog crossbreed

Document

85th Academy Awards

ECLARE

List of submissions to the 85th Academy Awards for Best Foreign Language Film, 33rd Golden Raspberry Awards, 19th Screen Actors
Guild Awards, 67th Tony Awards, 70th Golden Globe Awards
DECAF
List of American films of 1956, 87th Academy Awards, List of American films of 1957, 1963 in film, 13th Primetime Emmy Awards
Astec
65th Tony Awards, 29th Primetime Emmy Awards, 32nd Golden Raspberry Awards, 64th Primetime Emmy Awards, 18th Screen
Actors Guild Awards
1928 in film, 1931 in film, 1930 in film, 48th Academy Awards, 26th Primetime Emmy Awards, 31st European Film Awards
ParabelAttentionXML 29th Primetime Emmy Awards, 62nd British Academy Film Awards, 60th Primetime Emmy Awards, 65th Tony Awards, 29th Golden
Raspberry Awards
P2PTitles-2M
Document

Draper’s & Damon’s Women’s Chevron Faux Fur Coat Tan L

ECLARE

Grey Wolf Faux Fur Coat XXL / Grey, Big on Dots Faux-Fur Coat by LUXE, Avec Les Filles Bonded Faux-Fur Long Coat Size Large
Black, Roaman’s Women’s Short Faux-Fur Coat (Black) 1X, Dennis Basso Faux Fur Jacket with Stand Collar Size XX-Small Cappuccino
Draper’s & Damon’s Women’s Petite Cabana Big Shirt Blue P-L, Draper’s & Damon’s Women’s Petite Top It Off Stripe Jacket Blue
P-L, Draper’s & Damon’s Women’s Petite Standing Ovation Jacket Black P-L, Draper & Damon Jackets & Coats | Draper & Damons
Size L Colorful Coat Wpockets | Color: Black/Green | Size: L, Draper’s & Damon’s Women’s Impressionist Textured Jacket Multi L
Draper’s & Damon’s Women’s Petite Cabana Big Shirt Blue P-L, Draper’s & Damon’s Women’s Petite Top It Off Stripe Jacket Blue
P-L, Draper’s & Damon’s Women’s Impressionist Textured Jacket Multi L, Draper’s & Damon’s Women’s Embroidered Tulle Jacket
Dress Blue 14, Draper’s & Damon’s Women’s Petite Standing Ovation Jacket Black P-L
Draper’s & Damon’s Women’s Impressionist Textured Jacket Multi L, Draper’s & Damon’s Women’s Over The Rainbow Jacket Multi
P-L, Draper’s & Damon’s Women’s Petite Painted Desert Jacket White P-M, Draper Women’s Drapers & Damons Pants Suit - Pant
Suit | Color: Black | Size: L, Draper’s & Damon’s Women’s Petite Floral & Stripe Knit Mesh Jacket Scarlet Multi P-L

DECAF

Astec

Parabel(1) Clustering: As is evident from Fig 8, ECLARE’s offers significantly better clustering quality. Other methods such as DECAF
use label centroids over an incomplete ground truth, resulting inclusters of seemingly unrelated labels. For e.g. the label “Bulldog”
was clustered with “Great house at Sonning” by DECAF and thelabel “Dog of Osu” was clustered with “Ferdinand II of Aragon”
which never co-occur in training. However ECLARE clusters
much more relevant labels together, possibly since it was ableto (partly) complete the ground truth using it’s label correlationgraph G. This was also verified quantitatively by evaluating theclustering quality using the standard Loss of Mutual Information metric (LMI) [9]. Tab 7 shows that ECLARE has the least
LMI compared to other methods such as DECAF and those suchas MACH that use random hashes to cluster labels.
(2) Component Contribution: ECLARE chooses to dynamicallyattend on multiple (and heterogeneous) label representationsin its classifier components, which allows it to capture nuanced

ECLARE: Extreme Classification with Label Graph Correlations

DECAF

ECLARE

WWW ’21, April 19–23, 2021, Ljubljana, Slovenia

Dog of Osu

Dog of Osu

Tibetan Spaniel

Ferdinand II of
AragonTibetan terrier

Table 7: An ablation study showing loss of mutual information (lower is better) using various clustering strategies aswell as fanouts. Lowering the number of metalabels 𝐾 =|C| hurts performance. Competing methods that do notuse graph-augmented clustering offer poor LMI, especially
MACH that uses random hashes to cluster labels.

Bulldog
Bulldog

Great House at
Sonning

DatasetCompanion Dog
Group

LF-AmazonTitles-131K
LF-WikiSeeAlsoTitles-320K

SjambokFigure 8: A comparison of meta-label clusters created by
ECLARE compared to those created by DECAF. Note that theclusters for DECAF are rather amorphous, combing labelswith diverse intents whereas those for ECLARE are much
more focused. We note that other methods such ASTEC and
AttentionXML offered similarly noisy clusters. It is clearthat clustering based on label centroids that are augmented
using label correlation information creates far superior clusters that do not contain noisy and irrelevant labels.

LF-AmazonTitles-1.3M

45|| 3 z3|||| 1 z1 + 2 z2||

Norm. x Attenton wts.

40
35
30
25

ECLARE|C| = 217

ECLARE|C| = 215

DECAF

MACH

5.44
3.96

5.82
11.31

7.40
5.47

29.68
35.31

and GALE are crucial for rare labels whereas the (extreme) refinement vector ẑ𝑙3 is more important for data-abundant popularlabels.
(3) Label Text Augmentation: For the document “Tibetan Terrier”, ECLARE could make correct rare label predictions like
“Dog of Osu” even when the label text exhibits no token similarity with the document text or other co-occurring labels. Other
methods such as DECAF failed to understand the semantics ofthe label and mis-predicted the label “Fox Terrier” wrongly relying on the token “Terrier”. We attribute this gain to ECLARE’slabel correlation graph as “Dog of Osu” correlated well with thelabels “Tibetan Spaniel”, “Tibetan kyi apso” and “Tibetan Mastiff” in G. Several such examples exist in the datasets. In anotherexample from the P2P-2M dataset, for the product “Draper’s& Damon’s Women’s Chevron Fauz Fur Coat Tan L”, ECLARE
could deduce the intent of purchasing “Fur Coat” while other
XC methods incorrectly fixated on the brand “Draper’s & Damon’s”. Please refer to Tab 6 for detailed examples.

20

5

15

This paper presents the architecture and accompanying training
and prediction techniques for the ECLARE method to perform extreme multi-label classification at the scale of millions of labels. The
specific contributions of ECLARE include a framework for incorporating label graph information at massive scales, as well as criticaldesign and algorithmic choices that enable collaborative learning
using label correlation graphs with millions of labels. This includes
systematic augmentations to standard XC algorithmic operations
such as label-clustering, negative sampling, shortlisting, and reranking, to incorporate label correlations in a manner that scales totasks with millions of labels, all of which were found to be essential
to the performance benefits offered by ECLARE. The creation oflabel correlation graphs from ground truth data alone and its use
in a GCN-style architecture to obtain multiple label representations is critical to ECLARE’s performance benefits. The proposed
approach greatly outperforms state-of-the-art XC methods on multiple datasets while still offering millisecond level prediction times
even on the largest datasets. Thus, ECLARE establishes a standard
for incorporating label metadata into XC techniques. These findings
suggest promising directions for further study including effective
graph pruning for heavy tailed datasets, using higher order convolutions (𝑘 > 1) in a scalable manner, and performing collaborative
learning with heterogeneous and even multi-modal label sets. This

10
5

100

101

102

103

Label Bin ID
Increasing Freq.

104

Figure 9: Analysing the dominance of various components
in the label classifier w𝑙 for rare vs popular labels. For rarelabels (on the left), components that focus on label metadata
i.e. ẑ𝑙1, ẑ𝑙2 gain significance whereas for popular labels (on theright), the unrestricted refinement vector ẑ𝑙3 becomes dominant. This illustrates the importance of graph augmentation
for data-scarce labels for which the refinement vectors cannot be trained adequately owing to lack of training data.

variations in the semantics of each label. To investigate the contribution of the label text and refinement classifiers, Fig. 9 plots
the average product of the attention weight and norm of eachcomponent. It was observed that the label text components LTE

CONCLUSIONWWW ’21, April 19–23, 2021, Ljubljana, Slovenia

has the potential to enable generalisation to settings where labels
include textual objects such as (related) webpages and documents,
but also videos, songs, etc.

ACKNOWLEDGMENTS
The authors thank the reviewers for helpful comments that improved the presentation of the paper. They also thank the IIT Delhi
HPC facility for computational resources. AM is supported by a
Google PhD Fellowship.

REFERENCES[1] R. Babbar and B. Schölkopf. 2017. DiSMEC: Distributed Sparse Machines for
Extreme Multi-label Classification. In WSDM.
[2] R. Babbar and B. Schölkopf. 2019. Data scarcity, robustness and extreme multilabel classification. ML (2019).
[3] K. Bhatia, K. Dahiya, H. Jain, A. Mittal, Y. Prabhu, and M. Varma. 2016. The extreme classification repository: Multi-label datasets and code. http://manikvarma.
org/downloads/XC/XMLRepository.html[4] K. Bhatia, H. Jain, P. Kar, M. Varma, and P. Jain. 2015. Sparse Local Embeddings
for Extreme Multi-label Classification. In NIPS.
[5] P. Bojanowski, E. Grave, A. Joulin, and T. Mikolov. 2017. Enriching Word Vectors
with Subword Information. Transactions of the Association for Computational
Linguistics (2017).
[6] W-C. Chang, H.-F. Yu, K. Zhong, Y. Yang, and I. Dhillon. 2020. Taming Pretrained
Transformers for Extreme Multi-label Text Classification. In KDD.
[7] F. Chung. 2005. Laplacians and the Cheeger inequality for directed graphs. Annalsof Combinatorics 9, 1 (2005), 1–19.
[8] K. Dahiya, D. Saini, A. Mittal, A. Shaw, K. Dave, A. Soni, H. Jain, S. Agarwal, andM. Varma. 2021. DeepXML: A Deep Extreme Multi-Label Learning Framework
Applied to Short Text Documents. In WSDM.
[9] I. S. Dhillon, S. Mallela, and R. Kumar. 2003. A Divisive Information-Theoretic
Feature Clustering Algorithm for Text Classification. JMLR 3 (2003), 1265–1287.
[10] C. Guo, A. Mousavi, X. Wu, Daniel N. Holtmann-Rice, S. Kale, S. Reddi, and S.
Kumar. 2019. Breaking the Glass Ceiling for Embedding-Based Classifiers forLarge Output Spaces. In Neurips.
[11] V. Gupta, R. Wadbude, N. Natarajan, H. Karnick, P. Jain, and P. Rai. 2019. Distributional Semantics Meets Multi-Label Learning. In AAAI.
[12] W. Hamilton, Z. Ying, and J. Leskovec. 2017. Inductive representation learningon large graphs. In NIPS. 1024–1034.
[13] K. He, X. Zhang, S. Ren, and J. Sun. 2015. Delving deep into rectifiers: Surpassing
human-level performance on imagenet classification. In Proceedings of the IEEE
international conference on computer vision. 1026–1034.
[14] X. He, K. Deng, X. Wang, Y. Li, Y. Zhang, and M. Wang. 2020. LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation. In
Proceedings of the 43rd International ACM SIGIR Conference on Research andDevelopment in Information Retrieval (SIGIR ’20).
[15] H. Jain, V. Balasubramanian, B. Chunduri, and M. Varma. 2019. Slice: Scalable
Linear Extreme Classifiers trained on 100 Million Labels for Related Searches. In
WSDM.
[16] H. Jain, Y. Prabhu, and M. Varma. 2016. Extreme Multi-label Loss Functions for
Recommendation, Tagging, Ranking and Other Missing Label Applications. In
KDD.
[17] V. Jain, N. Modhe, and P. Rai. 2017. Scalable Generative Models for Multi-label
Learning with Missing Labels. In ICML.
[18] A. Jalan and P. Kar. 2019. Accelerating Extreme Classification via Adaptive
Feature Agglomeration. IJCAI (2019).
[19] K. Jasinska, K. Dembczynski, R. Busa-Fekete, K. Pfannschmidt, T. Klerx, and E.
Hullermeier. 2016. Extreme F-measure Maximization using Sparse Probability
Estimates. In ICML.
[20] A. Joulin, E. Grave, P. Bojanowski, and T. Mikolov. 2017. Bag of Tricks for Efficient
Text Classification. In Proceedings of the European Chapter of the Association for
Computational Linguistics.
[21] Bhargav Kanagal, Amr Ahmed, Sandeep Pandey, Vanja Josifovski, Jeff Yuan,
and Lluis Garcia-Pueyo. 2012. Supercharging Recommender Systems Using
Taxonomies for Learning User Purchase Behavior. VLDB (June 2012).
[22] S. Khandagale, H. Xiao, and R. Babbar. 2019. Bonsai - Diverse and Shallow Trees
for Extreme Multi-label Classification. CoRR (2019).
[23] P. D. Kingma and J. Ba. 2014. Adam: A Method for Stochastic Optimization. CoRR
(2014).
[24] T. N. Kipf and M. Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations,
ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings.

Mittal and Sachdeva, et al.

[25] J. Klicpera, A. Bojchevski, and S. Günnemann. 2018. Predict then Propagate:
Graph Neural Networks meet Personalized PageRank. In International Conference
on Learning Representations.
[26] J. Liu, W. Chang, Y. Wu, and Y. Yang. 2017. Deep Learning for Extreme Multi-label
Text Classification. In SIGIR.
[27] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer
Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019. RoBERTa: A
Robustly Optimized BERT Pretraining Approach. arXiv:1907.11692.
[28] T. K. R. Medini, Q. Huang, Y. Wang, V. Mohan, and A. Shrivastava. 2019. Extreme
Classification in Log Memory using Count-Min Sketch: A Case Study of Amazon
Search with 50M Products. In Neurips.
[29] Aditya Krishna Menon, Krishna-Prasad Chitrapura, Sachin Garg, Deepak Agarwal, and Nagaraj Kota. 2011. Response Prediction Using Collaborative Filteringwith Hierarchies and Side-Information. In KDD.
[30] T. Mikolov, I. Sutskever, K. Chen, G. Corrado, and J. Dean. 2013. Distributed
Representations of Words and Phrases and Their Compositionality. In NIPS.
[31] A. Mittal, K. Dahiya, S. Agrawal, D. Saini, S. Agarwal, P. Kar, and M. Varma. 2021.
DECAF: Deep Extreme Classification with Label Features. In WSDM.
[32] T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida. 2018. Spectral Normalization
for Generative Adversarial Networks. In ICLR.
[33] A. Niculescu-Mizil and E. Abbasnejad. 2017. Label Filters for Large Scale Multilabel Classification. In AISTATS.
[34] A. Pal, C. Eksombatchai, Y. Zhou, B. Zhao, C. Rosenberg, and J. Leskovec. 2020.
PinnerSage: Multi-Modal User Embedding Framework for Recommendationsat Pinterest. In KDD ’20 (Virtual Event, CA, USA) (KDD ’20). Association for
Computing Machinery, New York, NY, USA, 2311–2320. https://doi.org/10.1145/
3394486.3403280[35] Y. Prabhu, A. Kag, S. Gopinath, K. Dahiya, S. Harsola, R. Agrawal, and M. Varma.
2018. Extreme multi-label learning with label features for warm-start tagging,ranking and recommendation. In WSDM.
[36] Y. Prabhu, A. Kag, S. Harsola, R. Agrawal, and M. Varma. 2018. Parabel: Partitioned label trees for extreme classification with application to dynamic searchadvertising. In WWW.
[37] Y. Prabhu and M. Varma. 2014. FastXML: A Fast, Accurate and Stable Treeclassifier for eXtreme Multi-label Learning. In KDD.
[38] Noveen Sachdeva, Kartik Gupta, and Vikram Pudi. 2018. Attentive Neural Architecture Incorporating Song Features for Music Recommendation. In RecSys.
[39] M. Schuster and K. Nakajima. 2012. Japanese and korean voice search. In 2012
IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP).
IEEE, 5149–5152.
[40] W. Siblini, P. Kuntz, and F. Meyer. 2018. CRAFTML, an Efficient Clustering-based
Random Forest for Extreme Multi-label Learning. In ICML.
[41] Y. Tagami. 2017. AnnexML: Approximate Nearest Neighbor Search for Extreme
Multi-label Classification. In KDD.
[42] P. Tang, M. Jiang, B. Xia, J. W. Pitera, Welser J., and N. V. Chawla. 2020. Multi-Label
Patent Categorization with Non-Local Attention-Based Graph Convolutional
Network. In AAAI, 2020.
[43] P. Velićković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. 2018.
Graph Attention Networks. ICLR (2018).
[44] M. Wydmuch, K. Jasinska, M. Kuznetsov, R. Busa-Fekete, and K. Dembczynski.
2018. A no-regret generalization of hierarchical softmax to extreme multi-label
classification. In NIPS.
[45] E.H. I. Yen, X. Huang, W. Dai, I. Ravikumar, P.and Dhillon, and E. Xing. 2017.
PPDSparse: A Parallel Primal-Dual Sparse Method for Extreme Classification. In
KDD.
[46] E.H. I. Yen, X. Huang, K. Zhong, P. Ravikumar, and I. S. Dhillon. 2016. PDSparse: A Primal and Dual Sparse Approach to Extreme Multiclass and Multilabel
Classification. In ICML.
[47] I. Yen, S. Kale, F. Yu, D. Holtmann R., S. Kumar, and P. Ravikumar. 2018. Loss
Decomposition for Fast Learning in Large Output Spaces. In ICML.
[48] R. Ying, R. He, K. Chen, P. Eksombatchai, W. Hamilton, and J. Leskovec. 2018.
Graph convolutional neural networks for web-scale recommender systems. In
Proceedings of the 24th ACM SIGKDD International Conference on Knowledge
Discovery & Data Mining. 974–983.
[49] R. You, S. Dai, Z. Zhang, H. Mamitsuka, and S. Zhu. 2018. AttentionXML: Extreme
Multi-Label Text Classification with Multi-Label Attention Based Recurrent
Neural Networks. CoRR (2018).
[50] H. Yu, P. Jain, P. Kar, and I. S. Dhillon. 2014. Large-scale Multi-label Learningwith Missing Labels. In ICML.
[51] Z. Zhang, P. Cui, and W. Zhu. 2020. Deep learning on graphs: A survey. IEEE
Transactions on Knowledge and Data Engineering (2020).