  Deep extreme classification (XC) aims to train an encoder architecture and an
accompanying classifier architecture to tag a data point with the most relevant
subset of labels from a very large universe of labels. XC applications in
ranking, recommendation and tagging routinely encounter tail labels for which
the amount of training data is exceedingly small. Graph convolutional networks
(GCN) present a convenient but computationally expensive way to leverage task
metadata and enhance model accuracies in these settings. This paper formally
establishes that in several use cases, the steep computational cost of GCNs is
entirely avoidable by replacing GCNs with non-GCN architectures. The paper
notices that in these settings, it is much more effective to use graph data to
regularize encoder training than to implement a GCN. Based on these insights,
an alternative paradigm RAMEN is presented to utilize graph metadata in XC
settings that offers significant performance boosts with zero increase in
inference computational costs. RAMEN scales to datasets with up to 1M labels
and offers prediction accuracy up to 15% higher on benchmark datasets than
state of the art methods, including those that use graph metadata to train
GCNs. RAMEN also offers 10% higher accuracy over the best baseline on a
proprietary recommendation dataset sourced from click logs of a popular search
engine. Code for RAMEN will be released publicly.
