Year: 2018

Abstract:
Multi-label classification (MLC) is the task of assigning a set of target labels for a given sample. Modeling the combinatorial label interactions in MLC has been a long-haul challenge. Recurrent neural network (RNN) based encoder-decoder models have shown state-of-the-art performance for solving MLC. However, the sequential nature of modeling label dependencies through an RNN limits its ability in parallel computation, predicting dense labels, and providing interpretable results. In this paper, we propose Message Passing Encoder-Decoder (MPED) Networks, aiming to provide fast, accurate, and interpretable MLC. MPED networks model the joint prediction of labels by replacing all RNNs in the encoder-decoder architecture with message passing mechanisms and dispense with autoregressive inference entirely. The proposed models are simple, fast, accurate, interpretable, and structure-agnostic (can be used on known or unknown structured data). Experiments on seven real-world MLC datasets show the proposed models outperform autoregressive RNN models across five different metrics with a significant speedup during training and testing time.

heading: 1 INTRODUCTION
text: Multi-label classification (MLC) is receiving increasing attention in tasks such as text categorization and image classification. Accurate and scalable MLC methods are in urgent need for applications like assigning topics to web articles, classifying objects in an image, or identifying binding proteins on DNA. The most common and straightforward MLC method is the binary relevance (BR) approach that considers multiple target labels independently (Tsoumakas and Katakis, 2006). However, in many MLC tasks there is a clear dependency structure among labels, which BR methods ignore.
Accordingly, probabilistic classifier chain (PCC) models were proposed to model label dependencies and formulate MLC in an autoregressive sequential prediction manner (Read et al., 2009). One notable work in the PCC category was from Nam et al. (2017) which implemented a classifier chain using a recurrent neural network (RNN) based sequence to sequence (Seq2Seq) architecture, Seq2Seq MLC. This model uses an encoder RNN encoding elements of an input sequence, a decoder RNN predicting output labels one after another, and beam search that computes the probability of the next T predictions of labels and then chooses the proposal with the max combined probability.
However, the main drawback of classifier chain models is that their inherently sequential nature precludes parallelization during training and inference. This can be detrimental when there are a large number of positive labels as the classifier chain has to sequentially predict each label, and often requires beam search to obtain the optimal set. Aside from time-cost disadvantages, PCC methods have several other drawbacks. First, PCC methods require a defined ordering of labels for the sequential prediction, but MLC output labels are an unordered set, and the chosen order can lead to prediction instability (Nam et al., 2017). Secondly, even if the optimal ordering is known, PCC methods struggle to accurately capture long-range dependencies among labels in cases where the number of positive labels is large (i.e., dense labels). For example, the Delicious dataset has a median of 19 positive labels per sample, so it can be difficult to correctly predict the labels at the end of the prediction chain. Lastly, many real-world applications prefer interpretable predictors. For instance, in the task of predicting which proteins (labels) will bind to a DNA sequence based binding site, users care about how a prediction is made and how the interactions among labels influence the predictions1.
1An important task is modelling what is known as “co-binding” effects, where one protein will only bind if there is another specific protein already binding, or similarly will not bind if there is another already binding.
Message Passing Neural Networks (MPNNs) (Gilmer et al., 2017) introduce a class of methods that model joint dependencies of variables using neural message passing rather than an explicit representation such as a probabilistic classifier chain. Message passing allows for efficient inference by modelling conditional independence where the same local update procedure is applied iteratively to propagate information across variables. MPNNs provide a flexible method for modeling multiple variables jointly which have no explicit ordering (and can be modified to incorporate an order, as explained in section 3). To handle the drawbacks of BR and PCC methods, we propose a modified version of MPNNs for MLC by modeling interactions between labels using neural message passing.
We introduce Message Passing Encoder-Decoder (MPED) Networks aiming to provide fast, accurate, and interpretable multi-label predictions. The key idea is to replace RNNs and to rely on neural message passing entirely to draw global dependencies between input components, between labels and input components, and between labels. The proposed MPED networks allow for significantly more parallelization in training and testing. The main contributions of this paper are:
• Novel approach for MLC. To the authors’ best knowledge, MPED is the first work using neural message passing for MLC. • Accurate MLC. Our model achieves similar, or better performance compared to the previous state of the art across five different MLC metrics. We validate our model on seven MLC datasets which cover a wide spectrum of input data structure: sequences (English text, DNA), tabular (bag-of-words), and graph (drug molecules), as well as output label structure: unknown and graph. • Fast. Empirically our model achieves an average 1.7x speedup over the autoregressive seq2seq
MLC at training time and an average 5x speedup over its testing time. • Interpretable. Although deep-learning based systems have widely been viewed as “black boxes”
due to their complexity, our attention based MPED models provide a straightforward way to explain label to label, input to label, and feature to feature dependencies.

heading: 2 METHOD: MPED NETWORKS

heading: 2.1 BACKGROUND: MESSAGE PASSING NEURAL NETWORKS
text: Message Passing Neural Networks (MPNNs) (Gilmer et al., 2017) are a generalization of graph neural networks (GNNs) (Gori et al., 2005; Scarselli et al., 2009), where variables are represented as nodes on a graph G and joint dependencies are modelled using message passing rather than explicit representations, which allows for efficient inference. MPNNs model the joint dependencies using message function M t and node update function U t for T time steps, where t is the current time step. The hidden state vti ∈ Rd of node i ∈ G is updated based on messages mti from its neighboring nodes {vtj∈N (i)} defined by neighborhood N (i):
mti = ∑
j∈N (i)
M t(vti ,v t j), (1)
vt+1i = U t(vti ,m t i). (2)
After T updates, a readout function R is used on the updated nodes for a prediction (e.g., node classification or graph classification) on the graph G.
Many possibilities exist for functions M t and U t. For example, one can pass messages using neural attention in which nodes are able to attend over their neighborhoods differentially (Veličković et al., 2017). This allows for the network to learn different weights for different nodes in a neighborhood, without depending on knowing the graph structure a priori. In this formulation, messages for node vti are obtained by a weighted sum of all neighboring nodes {vtj∈N (i)} where the weights are obtained by attention (Bahdanau et al., 2014). In our implementation, we implement neural message passing with attention. In the rest of the paper, we use “graph attention” and “neural message passing” interchangeably. Neural message passing with attention works as follows.
Attention weights αtij for pair of nodes (v t i , v t j) are computed using some attention function a(·):
etij = a(v t i ,v t j), (3)
where etij represents the importance of node j for node i. For our attention function, we used a scaled dot product with node-wise linear transformations Wq ∈ Rd×d on node vti and Wu ∈ Rd×d on
node vtj . Scaling by √ d is used to mitigate training issues (Vaswani et al., 2017):
a(vti ,v t j) = (Wqvti) >(Wuvtj)√ d . (4)
Attention coefficients etij are then normalized across all neighboring nodes of node i using a softmax function:
αtij = softmaxj(e t ij) = α t ij = exp(etij)∑ k∈N (i) exp(e t ik) . (5)
In our method, we use a so called attention message function M tatn to produce the message from node j to node i using the learned attention weights αtij and another transformation matrix W
v ∈ Rd×d. Then we compute the full message mti by linearly combining messages from all nodes j ∈ N (i) with a residual connection on the current vti :
Matn(v t i ,v t j ;W ) = α t ijW vvtj , (6)
mti = v t i + ∑ j∈N (i) Matn(v t i ,v t j ;W ). (7)
Lastly, node vti is updated to state v t+1 i using message m t i by a multi-layer perceptron (MLP) update function Umlp with matrices Wr ∈ R2d×d,Wb ∈ R2d×d, and a residual connection on mti:
Umlp(m t i;W ) = ReLU(W rmti + b1) >Wb + b2, (8)
vt+1i = m t i + Umlp(m t i;W ). (9)
It is important to note that matrices W are shared (i.e., separately applied) across all nodes. This can be viewed as 1-dimensional convolution with kernel and stride sizes of 1. Weight sharing across nodes is a key aspect of MPNNs, where node dependencies are learned in an order-invariant manner.

heading: 2.2 MPED: MESSAGE PASSING ENCODER-DECODER NETWORK FOR MLC
text: Notations: We define the following notations, used throughout the paper. Let D = {(xn,yn)}Nn=1 be the set of data samples with inputs x ∈ X and outputs y ∈ Y . Inputs x are a (possibly ordered) set of S components {x1, x2, ..., xS}, and outputs y are a set of L labels {y1, y2, ..., yL}. MLC involves predicting the set of binary labels {y1, y2, ..., yL}, yi ∈ {0, 1} given input x. Input features are represented as embedded vectors {ct=01 , ct=02 , ..., ct=0S }, cti ∈ Rd, using embedding matrix Wx ∈ Rδ×d, where d is the embedding size, δ is the vocabulary size, and t represents the ‘state’ of the embedding after t updates. Similarly, labels are represented as an embedded vectors {ht=01 ,ht=02 , ...,ht=0L }, hti ∈ Rd, using embedding matrix Wy ∈ RL×d, where L is the number of labels, and t represents the ‘state’ of the embedding after t updates.
Setup: In MLC, each output label is determined by a joint probability of other labels and the input features. Our goal is to achieve the performance of explicit joint probability methods such as PCCs (Eqs. 22 and 23), at the test speed of BR methods (Eq. 21).
We introduce Message Passing Encoder-Decoder (MPED) networks, where we formulate MLC using an encoder-decoder architecture. In MPED Networks, input components are represented as nodes in encoder graph GENC using embedding vectors {ct1:S}, and labels are represented as nodes in decoder graph GDEC using embedding vectors {ht1:L}. MPED networks use three MPNN modules with attention to pass messages within GENC, from GENC to GDEC, and within GDEC to model the joint prediction of labels.
The first module, MPNNxx, is used to update input component nodes {ct1:S} by passing messages within the encoder (between input nodes). The second module, MPNNxy, is used to update output label nodes {ht1:L} by passing messages from the encoder to decoder (from input nodes {ct1:S} to output nodes {ht1:L}). The third module, MPNNyy, is used to update output label nodes {ht1:L} by passing messages within the decoder (between label nodes). Once messages have been passed to update input and label nodes, a readout function R is then used on the label nodes to make a binary classification prediction for each label, {ŷ1, ŷ2, ..., ŷL}. An overview of our model is shown in Fig. 1.

heading: 2.3 ENCODER: MODELING FEATURE INTERACTIONS VIA INPUT COMPONENT TO COMPONENT MESSAGE PASSING
text: For a particular input x, we first assume that the input features {x1:S} are nodes on a graph, we call GENC. GENC = (V,E), V = {x1:S}, and E includes all undirected pairwise edges connecting node ci and node cj . MPNNxx, parameterized by Wxx, is used to pass messages between the input embeddings in order to update their states. xi can be any component of a particular input (e.g. words in a sentence, patches of an image, nodes of a known graph, or tabular features).
Nodes on GENC are represented as embedding vectors {ct1, ct2, ..., ctS}, where the initial states {c01:S} are obtained using embedding matrix Wx on the input components {x1, x2, ..., xS}. The embeddings are then updated by MPNNxx using message passing for T time steps to produce {cT1 , cT2 , ..., cTS}. To update input embedding cti, MPNNxx uses attention message function M t atn (Eq. 6) on all neighboring input embeddings {ctj∈N (i)} to produce messages m t i, and MLP update function Umlp (Eq. 8) to produce updated embedding ct+1i :
mti = c t i + ∑ j∈N (i) Matn(c t i, c t j ;Wxx), (10)
ct+1i = m t i + Umlp(m t i;Wxx). (11)
If there exists a known GENC graph, message mti for node i is computed using its neighboring nodes j ∈ N (i), where the neighborsN (i) are defined by the graph. If there is no known graph, we assume a fully connected GENC graph, which means N (i) = {j 6= i}. Inputs with a sequential ordering can be modelled as a fully connected graph using positional embeddings (Battaglia et al., 2018).

heading: 2.4 DECODER
text: Similar to the input components in the encoder, we assume that the labels {y1:L} are nodes on a decoder graph called GDEC. Nodes on GDEC are represented as embedding vectors {ht1,ht2, ...,htL}, where the initial states {h01:L} are obtained using label embedding matrix Wy . The decoder MPNNs update the label embeddings {ht1:L} by passing messages from the encoder to the decoder, and then pass messages within the decoder. MPNNxy, is used to pass messages from input embeddings {cT1:S} to label embeddings, and then MPNNyy is used to pass messages between label embeddings.

heading: 2.4.1 UPDATING LABEL EMBEDDINGS THROUGH INPUT TO LABEL MESSAGE PASSING
text: In order to update the label nodes given a particular input x, the decoder uses MPNNxy, parameterized by Wxy, to pass messages from input x to labels y. At the equation level, this module is identical to MPNNxx except that it updates the ith label node’s embedding hi using the embeddings of all the components of an input. That is, we update each hti by using a weighted sum of all input embeddings {cT1:S}, in which the weights represent how important an input component is to the ith label node
and the weights are learned via attention. Messages are only passed from the encoder nodes to the decoder nodes, and not vice versa (i.e. encoder to decoder message passing is directed).
More specifically, to update label embedding hti, MPNNxy uses attention message function M t atn on all embeddings of the input {cT1:S} to produce messages mti, and another MLP update function Umlp to produce the updated intermediate embedding state ht ′
i :
mti = h t i + S∑ j=1 Matn(h t i, c T j ;Wxy), (12)
ht ′
i = m t i + Umlp(m t i;Wxy). (13)
The key advantage of input-to-label message passing with attention is that each label node can attend to different input nodes (e.g. different words in the sentence).

heading: 2.4.2 UPDATING LABEL EMBEDDINGS THROUGH LABEL TO LABEL MESSAGE PASSING
text: At this point, the decoder can make an independent prediction for each label conditioned on x. However, in order to make more accurate predictions, we model interactions between the label nodes {ht′1:L} using message passing and update them accordingly. To do this we use a a third message passing module, MPNNyy. At the equation level, this layer is identical to MPNNxx except that it replaces the input embeddings with label embeddings. In other words, label embedding ht ′
i is updated by a weighted combination through attention of all its neighbor label nodes {ht′j∈N (i)}.
To update each label embedding ht ′ i , MPNNyy uses attention message function M t′
atn on all neighbor label embeddings {ht′j∈N (i)} to produce message m t i, and MLP update function U t′
mlp to compute updated embedding ht+1i :
mt ′ i = h t′ i + ∑
j∈N (i)
Matn(h t′ i ,h t′ j ;Wyy), (14)
ht+1i = m t′ i + Umlp(h t′ i ,m t′ i ;Wyy). (15)
If there exists a known GDEC graph, message mti for node i is computed using its neighboring nodes j ∈ N (i), where the neighbors N (i) are defined by the graph. If there is no known GDEC graph, we assume a fully connected graph, which means N (i) = {j 6= i}. In our implementation, the label embeddings are updated by MPNNxy and MPNNxx for T time steps to produce {hT1 ,hT2 , ...,hTL}.

heading: 2.5 READOUT LAYER (MLC PREDICTIONS FROM THE DECODER)
text: The last module of the decoder predicts each label {ŷ1, ...ŷL}. A readout function R projects each of the L label embeddings hTi using projection matrix W
o ∈ RL×d, where row Woi ∈ Rd is the learned output vector for label i. The calculated vector of size L × 1 is then fed through an element-wise sigmoid function to produce probabilities of each label being positive:
ŷi = R(h T i ;W o) = sigmoid(Woih T i ). (16)
In MPED networks we use binary the mean cross entropy on the individual label predictions to train the model. p(yi|{yj 6=i}, cT1:S ;W) is approximated in MPED networks by jointly representing {y1:L} using message passing from {cT1:S} and from the embeddings of all neighboring labels {yj∈N (i)}.

heading: 2.6 MODEL DETAILS
text: Multi-head Attention In order to allow a particular node to attend to multiple other nodes (or multiple groups of nodes) at once, MPED uses multiple attention heads. Inspired by Vaswani et al. (2017), we use K independent attention heads for each W· matrix during the message computation, where each matrix column W·,kj is of dimension d/K. The generated representations are concatenated (denoted by ‖) and linearly transformed by matrix Wz ∈ Rd×d. Multi-head attention changes
message passing function Matn, but update function Umlp stays the same.
et,kij = (W q,kvti) >(Wu,kvtj)/ √ d (17)
αt,kij = exp(et,kij )∑
j∈N (i) exp(e t,k ij )
(18)
Mkatn(v t i ,v t j ;W ) = α t,k ij W v,kvtj , (19)
mti = v t i + (∥∥∥∥∥ K
k=1 [ ∑ j∈N (i) Mkatn(v t i ,v t j ;W ) ]) Wz (20)
Graph Time Steps To learn more complex relations among nodes, we compute T time steps of embedding updates. This is essentially a stack of T MPNN layers. Matrices Wq· ,W u · ,W v · ,W r · ,W b · ,W z · , are not shared across time steps (but are shared across nodes).
Label Embedding Weight Sharing To enforce each label’s input embedding to correspond to that particular label, the label embedding matrix weights Wy are shared with the readout projection matrix Wo. In other words, Wy is used to produce the initial node vectors for GDEC, and then is used again to calculate the pre-sigmoid output values for each label, so Wo ≡Wy . This was shown beneficial in Seq2Seq models for machine translation (Press and Wolf, 2016).

heading: 2.7 ADVANTAGES OF MPED MODELS
text: Speed. In MPED models, the joint probability of labels isn’t explicitly estimated using the chain rule. This enables making predictions in parallel and decreases test time drastically, especially when the number of labels is large. We model the joint probability implicitly using the MPED decoder, at the benefit of a substantial speedup. Time complexities of different types of models are compared in Table 1. The biggest advantage of MPED networks is constant training and testing times.
Handling dense label predictions. Motivated by the drawbacks of autoregressive models for MLC (Section 5.6), the proposed MPED model removes the dependencies on a chosen label ordering and beam search. This is particularly beneficial when the number of positive output labels is large (i.e. dense). MPED networks predict the output set of labels all at once, which is made possible by the fact that inference doesn’t use a probabilistic chain, but there is still a representation of label dependencies via label to label attention. As an additional benefit, as noted by Belanger and McCallum (2016), it may be useful to maintain ‘soft’ predictions for each label in MLC. This is a major drawback of the PCC models which make ‘hard’ predictions of the positive labels, defaulting all other labels to 0.
Flexibility Many input or output types are instances where the relational structure is not made explicit, and must be inferred or assumed (e.g., text corpora, or MLC labels)(Battaglia et al., 2018). MPED networks allow for greater flexibility of input structures (known structure such as sequence or graph, or unknown such as tabular), or output structures (e.g., known graph vs unknown structure).
Interpretability. One advantage of MPED models is that interpretability is “built in” via neural attention. Specifically, we can visualize 3 aspects: input-to-input attention (input dependencies), input-to-label attention (input/label dependencies), and label-to-label attention (label dependencies).

heading: 2.8 CONNECTING TO RELATED TOPICS
text: Structured Output Predictions The use of graph attention in MPED models is closely connected to the literature of structured output prediction for MLC. Ghamrawi and McCallum (2005) used conditional random fields (Lafferty et al., 2001) to model dependencies among labels and features for MLC by learning a distribution over pairs of labels to input features. In another research direction, recently proposed SPENs (structured prediction energy network (Belanger and McCallum, 2016; Tu and Gimpel, 2018)) and Deep Value Networks (Gygli et al., 2017) tackled MLC by optimizing
different variants of structured loss formulations. In contrast to SPEN and related methods which use an iterative refinement of the output label predictions, our method is a simpler feed forward block to make predictions in one step, yet still models dependencies through attention mechanisms on embeddings. However, we plan to expand MPED models by adding a structured loss formulation.
Graph Neural Networks (GNNs) Passing embedding messages from node to neighbor nodes connects to a large body of literature on graph neural networks (Battaglia et al., 2018) and embedding models for structures (Dai et al., 2016). The key idea is that instead of conducting probabilistic operations (e.g., product or re-normalization), the proposed models perform nonlinear function mappings in each step to learn feature representations of structured components. Neural message passing networks (Gilmer et al., 2017), graph attention networks (Veličković et al., 2017) and neural relation models (Battaglia et al., 2016) follow similar ideas to pass the embedding from node to neighbor nodes or neighbor edges. There have been many recent works extending the basic GNN framework to update nodes using various message passing, update, and readout functions (Kipf and Welling, 2016; Hamilton et al., 2017; Duvenaud et al., 2015; Li et al., 2015; Gilmer et al., 2017; Battaglia et al., 2016; Kearnes et al., 2016; Zheng et al., 2018). We refer the readers to (Battaglia et al., 2018) for a survey. However, none of these have used GNNs for MLC.

heading: 3 EXPERIMENTS
text: In the appendix, we have added the details of training/hyperparameters (5.2), datasets (5.1), evaluation metrics (5.3), and explained how we selected baseline models from previous work (5.8). We explain our own MPED variations in 5.7 and previous work baselines in section 5.8.
In short, we compare MPED to (1) MPED Prior GDEC (by using a known label graph), (2) MPED EdgelessGDEC (by removing label-to-label message passing), (3) MPED Autoregressive (by predicting labels sequentially), (4) MP BR (binary relevance MLP output used on the mean of MPNNxx embeddings), and the baselines reported in related works. We compare our models on seven real world datasets, which vary in the number of samples, number of labels, input type (sequential, tabular, graph), and output type (unknown, known label graph), as summarized in Table 3.
Across all datasets, MPED outperforms or achieves similar results as the baseline models. Most importantly, we show that autoregressive models are not crucial in MLC for most metrics, and non-autoregressive models result in a significant speedup at test time.
Accuracy (across different input and output types) Table 2 shows the performance of different models across the 7 datasets. Significance across models is shown in Appendix Table 4. For subset accuracy (ACC), autoregressive models perform the best, but at a small margin of increase. However, autoregressive models that predict only positive labels are targeted at maximizing subset accuracy, but they perform poorly on other metrics. For all other metrics, autoregressive models are not essential.
One important observation is that for most datasets, MPED outperforms the autoregressive models in both miF1 (frequent labels) and more importantly, maF1 (rare labels). Since maF1 favors models which can predict the rare labels, this shows that autoregressive models with beam search often make the wrong predictions on the rare labels (which are ordered last in the sequence during training). MPED is a solid choice across all metrics as it comes the closest to subset accuracy as the autoregressive models, but also performs well in other metrics.
While MPED does not explicitly model label dependencies as autoregressive or structured prediction models do, it seems as though the attention weights do learn some dependencies among labels (Visualizations, Tables 3 and 4). This is indicated by the fact that MPED, which uses label-to-label attention, mostly outperforms the ones which don’t, indicating that it is learning label dependencies. Table 2 shows 3 time step models results, but a comparison of time steps is shown in Figure 2.
Speed Table 2 shows the per epoch train and test times for each model. All models are trained and tested on the same GPU using a batch size of 32. At test time, since the autoregressive model cannot be parallelized, MPED and other non-autoregressive models are significantly faster. During training, the autoregressive model can be parallelized because the true labels are fed as the previous label. Since the autoregressive models only predict the ρ positive labels, they can be faster at training time, whereas the MPED model is predicting the probability for all labels. MPED results in a mean of 1.7x and 5.0x training and testing speedups, respectively, over Seq2Seq autoregressive models. Interpretability We present visualizations of the input-to-label and label-to-label attention weights (averaged across the 4 attention heads) in the Appendix. In the visualizations, we show the positive
labels only, and the darker lines show higher attention weights to the corresponding label or word. The attention weights clearly learn certain relationships between input-label pairs as well as the label-label pairs, which is all done in an unsupervised manner. In future work, we plan to add a structured prediction loss function which will likely improve the attention mechanisms and the model’s ability to estimate the joint probability.

heading: 4 CONCLUSION
text: In this work we present Message Passing Encoder-Decoder (MPED) Networks which achieve a significant speedup at close to the same performance as autoregressive models for MLC. We open a new avenue of using neural message passing to model label dependencies in MLC tasks. In addition, we show that our method is able to handle various input data types (sequence, tabular, graph), as well various output label structures (known vs unknown). One of our future extensions is to adapt the current model to predict more dynamic outputs.

heading: 5 APPENDIX:

heading: 5.1 DATASETS
text: We test our method against baseline methods on seven different multi-label sequence classification datasets. The datasets are summarized in Table 3. We use Reuters-21578, Bibtex (Tsoumakas et al., 2009), Delicious (Tsoumakas et al.), Bookmarks (Katakis et al.), RCV1-V2 (Lewis et al., 2004), our own DNA protein binding dataset (TFBS) from Consortium et al. (2012), and SIDER (Kuhn et al., 2015), which is side effects of drug molecules. As shown in the table, each dataset has a varying number of samples, number of labels, positive labels per sample, and samples per label. For BibTex and Delicious, we use 10% of the provided training set for validation. For the TFBS dataset, we use 1 layer of convolution at the first layer to extract “words” from the DNA characters (A,C,G,T), as commonly done in deep learning models for DNA.
For datasets which have sequential ordering of the input components (Reuters, RCV1), we add a positional encoding to the word embedding as used in Vaswani et al. (2017) (sine and cosine functions of different frequencies) to encode the location of each word in the sentence. For datasets with no ordering or graph stucture (Bibtex, Delicious, Bookmarks, which use bag-of-word input representations) we do not use positional encodings. For inputs with an explicit graph representation (SIDER), we use the known graph structer.

heading: 5.2 MODEL HYPERPARAMETERS
text: We validate our model on seven MLC datasets. These datasets cover a wide spectrum of input data types, including: raw English text (sequential form), bag-of-words (tabular form), and drug molecules (graph form).
For all 6 datasets except SIDER, we use the same MPED model with T=3 time steps, d = 512, and K=4 attention heads. Since SIDER is significantly smaller, we use T=1 time step, d = 64, and K=4 attention heads. We trained our models on an NVIDIA TITAN X Pascal with a batch size of 32. We used Adam (Kingma and Ba, 2014) with betas= (0.9, 0.999), eps=1e-08, and a learning rate of 0.0002 for each dataset. We used dropout of p = 0.2 for all models. The MPED models also use layer normalization (Ba et al., 2016) around each of the attention and feedforward layers. The non-autoregressive models are trained with binary cross-entropy on each label and the autoregressive models are trained with cross entropy across all possible labels at each position.

heading: 5.3 EVALUATION METRICS
text: Multi-label classification methods can be evaluated with many different metrics which each evaluate different strengths or weaknesses. We use the same 5 evaluation metrics from Nam et al. (2017).
All of our autoregressive models predict only the positive labels before outputting a stop signal. This is a special case of PCC models (explained as PCC+ in section 5.4), which have been shown to outperform the binary prediction of each label in terms of performance and speed. These models use beam search at inference time with a beam size of 5. For the non-autoregressive models, to convert the labels to {0, 1} we chose the best threshold on the validation set from the same set of thresholds used in Tu and Gimpel (2018).
Example-based measures are defined by comparing the target vector y to the prediction vector ŷ. Subset Accuracy (ACC) requires an exact match of the predicted labels and the true labels: ACC(y, ŷ) = I[y = ŷ]. Hamming Accuracy (HA) evaluates how many labels are correctly predicted in ŷ: HA(y, ŷ) = 1
L ∑L j=1 I[yj =
ŷj ]. Example-based F1 (ebF1) measures the ratio of correctly predicted labels to the sum of the total true and predicted labels: 2 ∑L
j=1 yj ŷj∑L j=1 yj+ ∑L j=1 ŷj .
Label-based measures treat each label yj as a separate two-class prediction problem, and compute the number of true positives (tpj), false positives (fpj), and false negatives (fnj) for a label. Macro-averaged F1 (maF1) measures the label-based F1 averaged over all labels: 1
L ∑L j=1 2tpj 2tpj+fpj+fnj . Micro-averaged F1 (miF1)
measures the label-based F1 averaged over each sample: ∑L
j=1 2tpj∑L j=1 2tpj+fpj+fnj . High maF1 scores usually
indicate high performance on less frequent labels. High miF1 scores usually indicate high performance on more frequent labels.

heading: 5.4 BACKGROUND OF MULTI-LABEL CLASSIFICATION:
text: MLC has a rich history in text (McCallum; Ueda and Saito, 2003), images (Tsoumakas and Katakis, 2006; Elisseeff and Weston, 2002), bioinformatics (Tsoumakas and Katakis, 2006; Elisseeff and Weston, 2002), and many other domains. MLC methods can roughly be broken into several groups, which are explained as follows.
Label powerset models (LP) (Tsoumakas and Vlahavas, 2007; Read et al., 2011), classify each input into one label combination from the set of all possible combinations Y = {{1}, {2}, ..., {1, 2, ..., L}}. LP explicitly models the joint distribution by predicting the one subset of all positive labels. Since the label set Y grows exponentially in the number of total labels (2L), classifying each possible label set is intractable for a modest L. In addition, even in small L tasks, LP suffers from the “subset scarcity problem” where only a small amount of the label subsets are seen during training, leading to bad generalization.
Binary relevance (BR) methods predict each label separately as a logistic regression classfier for each label (Zhang and Zhou, 2005; Godbole and Sarawagi, 2004). The naïve approach to BR prediction is to predict all labels independently of one another, assuming no dependencies among labels. That is, BR uses the following conditional probability parameterized by learned weights W :
PBR(Y |X;W ) = L∏ i=1 p(Yi|X1:S ;W ) (21)
Probabilistic classifier chain (PCC) methods (Dembczynski et al., 2010; Read et al., 2009) are autoregressive models that estimate the true joint probability of output labels given the input by using the chain rule, predicting one label at a time:
PPCC(Y |X;W ) = L∏ i=1 p(Yi|Y1:i−1, X1:S ;W ) (22)
Two issues with PCC models are that inference is very slow if L is large, and the errors propagate as L increases (Montañes et al., 2014). To mitigate the problems with both LP and PCC methods, one solution is to only predict the true labels in the LP subset. In other words, only predicting the positive labels (total of ρ for a particular sample) and ignoring all other labels, which we call PCC+. Similar to PCC, the joint probability of PCC+ can be computed as product of conditional probabilities, but unlike PCC, only ρ < L terms are predicted as positive:
PPCC+(Y |X;W ) = ρ∏ i=1 p(Ypi |Yp1:i−1 , x1:S ;W ) (23)
This can be beneficial when the number of possible labels L is large, reducing the total number of prediction steps. However, in both PCC and PCC+, inference is done using beam search, which is a costly dynamic programming step to find the optimal prediction.
MPED methods approximate the following factored formulation, where N (Yi) denotes the neighboring nodes of Yi.
PG2G(Y |X;W ) = L∏ i=1 p(Yi|{YN (Yi)}, X1:S ;W ). (24)

heading: 5.5 SEQ2SEQ MODELS
text: In machine translation (MT), sequence-to-sequence (Seq2Seq) models have proven to be the superior method, where an encoder RNN reads the source language sentence into an encoder hidden state, and a decoder RNN
translates the hidden state into a target sentence, predicting each word autoregressively (Sutskever et al., 2014). Bahdanau et al. (2014) improved this model by introducing “neural attention” which allows the decoder RNN to “attend” to every encoder word at each step of the autoregressive translation.
Recently, Nam et al. (2017) showed that, across several metrics, state-of-the-art MLC results could be achieved by using a recurrent neural network (RNN) based encoder-to-decoder framework for Equation 23 (PCC+). They use a Seq2Seq RNN model (Seq2Seq Autoregressive) which uses one RNN to encode x, and a second RNN to predict each positive label sequentially, until it predicts a ‘stop’ signal. This type of model seeks to maximize the ‘subset accuracy’, or correctly predict every label as its exact 0/1 value.
Vaswani et al. (2017) eliminated the need for the recurrent network in MT by introducing the Transformer. Instead of using an RNN to model dependencies, the Transformer explicitly models pairwise dependencies among all of the features by using attention (Bahdanau et al., 2014; Xu et al.) between signals. This speeds up training time because RNNs can’t be fully parallelized but, the transformer still uses an autoregressive decoder.

heading: 5.6 DRAWBACKS OF AUTOREGRESSIVE MODELS
text: Autoregressive models have been proven effective for machine translation and MLC (Sutskever et al., 2014; Bahdanau et al., 2014; Nam et al., 2017). However, predictions must be made sequentially, eliminating parallelization. Also, beam search is typically used at test time to find optimal predictions. But beam search is limited by the time cost of large beams sizes, making it difficult to optimally predict many output labels (Koehn and Knowles, 2017).
In addition to speed constraints, beam search for autoregressive inference introduces a second drawback: initial wrong predictions will propagate when using a modest beam size (e.g. most models use a beam size of 5). This can lead to significant decreases in performance when the number of positive labels is large. For example, the Delicious dataset has a median of 19 positive labels per sample, and it can be very difficult to correctly predict the labels at the end of the prediction chain.
Autoregressive models are well suited for machine translation because these models mimic the sequential decoding process of real translation. However, for MLC, the output labels have no intrinsic ordering. While the joint probability of the output labels is independent of the label ordering via autoregressive based inference, the chosen ordering can make a difference in practice (Vinyals et al., 2015; Nam et al., 2017). Some ordering of labels must be used during training, and this chosen ordering can lead to unstable predictions at test time.
Our non-autoregressive version connects to Gu et al. (2017) who removed the autoregressive decoder in MT with the Non-Autoregressive Transformer. In this model, the encoder makes a proxy prediction, called “fertilities”, which are used by the decoder to predict all translated words at once. The difference between their model and ours is that we have a constant label at each position, so we don’t need to marginalize over all possible labels at each position.

heading: 5.7 MODEL VARIATIONS
text: MPED: In the full MPED model, we use 3 encoder time steps and 3 decoder time steps with node to node attention in both the encoder and decoder graphs, and K=4 attention heads.
MPED Prior GDEC: The same as MPED except that we use a prior representation of GDEC rather than fully connected. For Reuters, Bibtex, Delicious, and Bookmarks we have extracted label graphs using label similarity (using fixed WUP scores) from WordNet. For RCV1, we use the topological graph from the RCV1 dataset. For TFBS, we use String-DB (Szklarczyk et al., 2016) to obtain the label graph representing TF-TF protein interactions.
MPED Edgeless GDEC: In this baseline, we remove MPNNyy, and only use MPNNxy to pass messages from the inputs to the labels, and not between labels. This model assumes no dependencies among output labels.
MPED Autoregressive: Instead of predicting all labels simultaneously and modelling label dependencies using graph attention, the MPED Autoregressive variation models p(yi+1|y1:i, x1:S ;W ) by predicting each positive label yi sequentially and using attention on {cT1:S} and the previously predicted labels (ŷ1, ..., ŷi) until a stop signal is predicted (see PCC+ in Appendix). While it is possible to predict the probability for each label (i.e. regular PCC), this is extremely time consuming when the number of possible labels is large (and in general, doesn’t increase performance (Nam et al., 2017)).
BR: The mean node output of a MPNNxx is used as the input to a 2 layer multilayer perceptron (MLP) readout module. This model assumes no dependencies among output labels.
RNN Seq2Seq: A 3-layer RNN Seq2Seq model with attention. This is similar to RNN Seq2Seq from Nam et al. (2017) (RNNm in their paper), except with 3 layers.

heading: 5.8 BASELINE COMPARISONS
text: For Reuters and RCV1-V2, we compare against the MLP and autoregressive model used in (Nam et al., 2017), which use these two datasets. MLP: standard MLP without the self attention input representation. RNN Seq2Seq: RNN PCC+ autoregressive model from (Nam et al., 2017), which is a GRU encoder/decoder model with pretrained word embeddings. We omit the binary relevance RNN since it was shown that it doesn’t perform well and is extremely slow.
For BibTex, Delicious, Bookmarks, we compare against the models from Belanger and McCallum (2016) and Tu and Gimpel (2018), which use these three datasets. They only evaluate using ebF1, so this is the only metric for which we compare our model with theirs. MLP (Belanger and McCallum, 2016): Standard 2-layer MLP. SPEN (Belanger and McCallum, 2016): original structured prediction energy network. InfNet SPEN (Tu and Gimpel, 2018): improved SPEN model, which uses an inference network to estimate ŷ.
5.9 VISUALIZATIONS

Review summaries:
The paper describes an approach for using graph neural networks (GNN) to perform multi-label classification (MLC). The main idea is to use attentional pooling to project an input graph into a "label graph", whose nodes correspond to labels on some MLC problem. Multiple rounds of self-attention/message-passing hops can be performed on the input graph and label graph. Each output label is binary-valued, and is predicted from its corresponding node in the label graph. They evaluate on 6 multi-label sequence classification datasets, and report strong perform over baselines.