Title: NEURAL MESSAGE PASSING FOR MULTI-LABEL CLASSIFICATION

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

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.

2. METHOD: MPED NETWORKS:

2.1 BACKGROUND: MESSAGE PASSING NEURAL NETWORKS 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 v t i ∈ R d of node i ∈ G is updated based on messages m t i from its neighboring nodes {v t j∈N (i) } defined by neighborhood N (i):

EQUATION

EQUATION

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 (Veličković 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 v t i are obtained by a weighted sum of all neighboring nodes {v t j∈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 α t ij for pair of nodes (v t i , v t j ) are computed using some attention function a(•):

EQUATION

where e t ij represents the importance of node j for node i. For our attention function, we used a scaled dot product with node-wise linear transformations W q ∈ R d×d on node v t i and (Vaswani et al., 2017) :

W u ∈ R d×d on y 1 y 2 y 3 y 4 c 1 c 2 c 3 y 5 x x 1 2 x 3 h 1 h 5 h 4 h 3 h 2 h 1 h 5 h 4 h 3 h 2 c 2 c 3 c 1 e12 e13 e14 e15 e12 e13

EQUATION

Attention coefficients e t ij are then normalized across all neighboring nodes of node i using a softmax function:

α t ij = softmax j (e t ij ) = α t ij = exp(e t ij ) k∈N (i) exp(e t ik )

.

(5)

In our method, we use a so called attention message function M t atn to produce the message from node j to node i using the learned attention weights α t ij and another transformation matrix W v ∈ R d×d . Then we compute the full message m t i by linearly combining messages from all nodes j ∈ N (i) with a residual connection on the current v t i :

EQUATION

EQUATION

Lastly, node v t i is updated to state v t+1 i using message m t i by a multi-layer perceptron (MLP) update function U mlp with matrices W r ∈ R 2d×d , W b ∈ R 2d×d , and a residual connection on m t i :

EQUATION

EQUATION

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.

2.2. MPED: MESSAGE PASSING ENCODER-DECODER NETWORK FOR MLC:

Notations: We define the following notations, used throughout the paper.

Let D = {(x n , y n )} N n=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 {x 1 , x 2 , ..., x S }, and outputs y are a set of L labels {y 1 , y 2 , ..., y L }. MLC involves predicting the set of binary labels {y 1 , y 2 , ..., y L }, y i ∈ {0, 1} given input x.

Input features are represented as embedded vectors {c t=0 1 , c t=0 2 , ..., c t=0 S }, c t i ∈ R d , using embedding matrix W x ∈ 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 {h t=0

1 , h t=0 2 , ..., h t=0 L }, h t i ∈ R d , using embedding matrix W y ∈ R L×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 G ENC using embedding vectors {c t 1:S }, and labels are represented as nodes in decoder graph G DEC using embedding vectors {h t 1:L }. MPED networks use three MPNN modules with attention to pass messages within G ENC , from G ENC to G DEC , and within G DEC to model the joint prediction of labels.

The first module, MPNN xx , is used to update input component nodes {c t 1:S } by passing messages within the encoder (between input nodes). The second module, MPNN xy , is used to update output label nodes {h t 1:L } by passing messages from the encoder to decoder (from input nodes {c t 1:S } to output nodes {h t 1:L }). The third module, MPNN yy , is used to update output label nodes {h t 1: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, {ŷ 1 , ŷ2 , ..., ŷL }. An overview of our model is shown in Fig. 1 .

2.3. ENCODER: MODELING FEATURE INTERACTIONS VIA INPUT COMPONENT TO:

COMPONENT MESSAGE PASSING For a particular input x, we first assume that the input features {x 1:S } are nodes on a graph, we call G ENC . G ENC = (V, E), V = {x 1:S }, and E includes all undirected pairwise edges connecting node c i and node c j . MPNN xx , parameterized by W xx , is used to pass messages between the input embeddings in order to update their states. x i 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 G ENC are represented as embedding vectors {c t 1 , c t 2 , ..., c t S }, where the initial states {c 0 1:S } are obtained using embedding matrix W x on the input components {x 1 , x 2 , ..., x S }. The embeddings are then updated by MPNN xx using message passing for T time steps to produce {c T 1 , c T 2 , ..., c T S }. To update input embedding c t i , MPNN xx uses attention message function M t atn (Eq. 6) on all neighboring input embeddings {c t j∈N (i) } to produce messages m t i , and MLP update function U mlp (Eq. 8) to produce updated embedding c t+1 i :

EQUATION

EQUATION

If there exists a known G ENC graph, message m t i 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 graph, we assume a fully connected G ENC graph, which means N (i) = {j = i}. Inputs with a sequential ordering can be modelled as a fully connected graph using positional embeddings (Battaglia et al., 2018) .

2.4. DECODER:

Similar to the input components in the encoder, we assume that the labels {y 1:L } are nodes on a decoder graph called G DEC . Nodes on G DEC are represented as embedding vectors {h t 1 , h t 2 , ..., h t L }, where the initial states {h 0 1:L } are obtained using label embedding matrix W y . The decoder MPNNs update the label embeddings {h t 1:L } by passing messages from the encoder to the decoder, and then pass messages within the decoder. MPNN xy , is used to pass messages from input embeddings {c T 1:S } to label embeddings, and then MPNN yy is used to pass messages between label embeddings.

2.4.1. UPDATING LABEL EMBEDDINGS THROUGH INPUT TO LABEL MESSAGE PASSING:

In order to update the label nodes given a particular input x, the decoder uses MPNN xy , parameterized by W xy , to pass messages from input x to labels y. At the equation level, this module is identical to MPNN xx except that it updates the i th label node's embedding h i using the embeddings of all the components of an input. That is, we update each h t i by using a weighted sum of all input embeddings {c T 1:S }, in which the weights represent how important an input component is to the i th 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 h t i , MPNN xy uses attention message function M t atn on all embeddings of the input {c T 1:S } to produce messages m t i , and another MLP update function U mlp to produce the updated intermediate embedding state h t i :

EQUATION

EQUATION

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

2.4.2. UPDATING LABEL EMBEDDINGS THROUGH LABEL TO LABEL MESSAGE PASSING:

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 {h t 1:L } using message passing and update them accordingly. To do this we use a a third message passing module, MPNN yy . At the equation level, this layer is identical to MPNN xx except that it replaces the input embeddings with label embeddings. In other words, label embedding h t i is updated by a weighted combination through attention of all its neighbor label nodes {h t j∈N (i) }.

To update each label embedding h t i , MPNN yy uses attention message function M t atn on all neighbor label embeddings {h t j∈N (i) } to produce message m t i , and MLP update function U t mlp to compute updated embedding h t+1 i :

EQUATION

EQUATION

)

If there exists a known G DEC graph, message m t i 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 G DEC graph, we assume a fully connected graph, which means N (i) = {j = i}.

In our implementation, the label embeddings are updated by MPNN xy and MPNN xx for T time steps to produce {h T 1 , h T 2 , ..., h T L }.

2.5. READOUT LAYER (MLC PREDICTIONS FROM THE DECODER):

The last module of the decoder predicts each label {ŷ 1 , ...ŷ L }. A readout function R projects each of the L label embeddings h T i using projection matrix W o ∈ R L×d , where row W o i ∈ R d 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:

EQUATION

In MPED networks we use binary the mean cross entropy on the individual label predictions to train the model. p(y i |{y j =i }, c T 1:S ; W) is approximated in MPED networks by jointly representing {y 1:L } using message passing from {c T 1:S } and from the embeddings of all neighboring labels {y j∈N (i) }.

2.6. MODEL DETAILS:

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 •,k j is of dimension d/K. The generated representations are concatenated (denoted by ) and linearly transformed by matrix W z ∈ R d×d . Multi-head attention changes message passing function M atn , but update function U mlp stays the same.

EQUATION

m t i = v t i + K k=1 j∈N (i) M k atn (v t i , v t j ; W ) W z (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

W q • , 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 W y are shared with the readout projection matrix W o . In other words, W y is used to produce the initial node vectors for G DEC , and then is used again to calculate the pre-sigmoid output values for each label, so W o ≡ W y . This was shown beneficial in Seq2Seq models for machine translation (Press and Wolf, 2016) .

2.7. ADVANTAGES OF MPED MODELS:

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

O(ρ) O(S • d 2 ) O(ρ • d 2 ) MPED O(1) O(1) O(S 2 • d) O(L 2 • d)

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

2.8. CONNECTING TO RELATED TOPICS:

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 (Veličković 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.

3. EXPERIMENTS:

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 G DEC (by using a known label graph), ( 2) MPED Edgeless G DEC (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 MPNN xx 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 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.

4. CONCLUSION:

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. (Read et al., 2009; Demšar, 2006) 5.1 DATASETS

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.

5.2. MODEL HYPERPARAMETERS:

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.

5.3. EVALUATION METRICS:

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 ŷ. Subset Accuracy (ACC) requires an exact match of the predicted labels and the true labels: ACC(y, ŷ) = I[y = ŷ].

Hamming Accuracy (HA) evaluates how many labels are correctly predicted in ŷ: HA(y, ŷ) = 1 L L j=1 I[yj = ŷj]. Example-based F1 (ebF1) measures the ratio of correctly predicted labels to the sum of the total true and predicted labels: 

5.4. BACKGROUND OF MULTI-LABEL CLASSIFICATION::

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 (2 L ), 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 :

EQUATION

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:

EQUATION

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:

EQUATION

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:

EQUATION

5.5. SEQ2SEQ MODELS:

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 GENC is processed with a fixed T =3 time steps, and the decoder time steps are varied. We do not compare time steps for the SIDER dataset since it is too small, and we only evaluate using T =1.

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.

5.6. DRAWBACKS OF AUTOREGRESSIVE MODELS:

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.

5.7. MODEL VARIATIONS:



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. 

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

Figures and Tables:

measures treat each label yj as a separate two-class prediction problem, and compute the number of true positives (tpj), false positives (f pj), and false negatives (f nj) for a label. Macro-averaged F1 (maF1) measures the label-based F1 averaged over all labels: p j +f n j . Micro-averaged F1 (miF1) measures the label-based F1 averaged over each sample: L j=1 2tp j L j=1 2tp j +f p j +f n j . High maF1 scores usually indicate high performance on less frequent labels. High miF1 scores usually indicate high performance on more frequent labels.

Figure 2: Average Across Metrics for T =1, T =2, and T =3 GDEC time steps. In these experiments, the encoder

Figure 3: Label-To-Label Attention Weights. On the left are the positive labels, and on the right are all labels. These are taken from the layer 2 Label-To-Label attentions on a sample from Reuters-21578 (same input sample as shown in 4.

Figure 4: Input to Label Attention Weights. On the left are the positive labels, and on the right are all input components (words). These are taken from the layer 1 Input to Label attentions on a sample from Reuters-21578.

Figure 1: MPED Networks. Given input x, we encode its components {x1, x2, x3} as embedded input nodes {c t 1 , c t 2 , c t 3 } of encoder graph G ENC . Similarly, we encode labels {y1, y2, ..., y5} as embedded label nodes {h t 1 , h t 2 , ..., h t 5 } of decoder graph G DEC .MPNNxx is used to pass messages between the input nodes and update input nodes. MPNNxy is used to pass messages from the input nodes to the labels nodes and update the label nodes. MPNNyy is used to pass messages between the label nodes and update label nodes. Finally, readout function R performs node-level classification on label nodes to make binary label predictions {ŷ1, ŷ2, ..., ŷ5}.

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td>t</td></tr><tr><td/><td/><td/><td/><td>t</td><td>e11 e12</td><td>t</td><td>t</td></tr><tr><td/><td/><td>t</td><td>t</td><td>t</td><td/><td>t</td><td>t</td><td>t</td><td>R</td></tr><tr><td/><td/><td/><td/><td/><td>e13</td><td/></tr><tr><td/><td/><td>t</td><td/><td>t</td><td/><td>t</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>t</td><td>t</td></tr><tr><td/><td/><td/><td/><td/><td/><td>t</td></tr><tr><td colspan="3">MPNN XX</td><td/><td>MPNN XY</td><td/><td/><td>MPNN YY</td></tr><tr><td>node v t j . Scaling by</td><td>√</td><td colspan="5">d is used to mitigate training issues</td></tr></table>

The biggest advantage of MPED networks is constant training and testing times.

Table content: <table><tr><td>Model</td><td>Training Time Cost (# sequential operations)</td><td>Testing Time Cost (# sequential operations)</td><td>Encoder Layer Space Cost</td><td>Decoder Layer Space Cost</td></tr><tr><td>RNN Seq2Seq</td><td>O(S + ρ)</td><td/><td/><td/></tr></table>

Model Complexities. S represents the input sequence length, ρ represents the number of positive labels, L represents total number of labels, and d is the size of the model's hidden state.

Table content: <table/>

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. Results. Across all 7 datasets, MPED produces similar or better average metric scores to baseline models. MPED results in a mean of 1.7x and 5.0x training and testing speedups, respectively, over the previous state-of-the-art probabilistic MLC method, RNN Seq2Seq. Speedups over RNN Seq2Seq model are shown in minutes per epoch in parentheses for the MPED model. Bold numbers show the best performing method(s).

Table content: <table><tr><td>Dataset</td><td>Model</td><td colspan="2">ACC HA</td><td colspan="4">ebF1 miF1 maF1 Average Train Time</td><td>Test Time</td></tr><tr><td>Reuters</td><td>MPED</td><td colspan="5">0.834 0.997 0.902 0.871 0.503 0.822</td><td>0.788 (1.5x)</td><td>0.116 (2.1x)</td></tr><tr><td/><td>MPED Prior GDEC</td><td colspan="5">0.827 0.997 0.899 0.870 0.507 0.820</td><td>0.788</td><td>0.116</td></tr><tr><td/><td>MPED Edgeless GDEC</td><td colspan="5">0.828 0.997 0.898 0.873 0.495 0.818</td><td>0.738</td><td>0.111</td></tr><tr><td/><td>MPED Autoregressive</td><td colspan="5">0.835 0.997 0.899 0.868 0.496 0.819</td><td>0.618</td><td>0.374</td></tr><tr><td/><td>RNN Seq2Seq</td><td colspan="5">0.837 0.996 0.900 0.861 0.496 0.818</td><td>1.187</td><td>0.242</td></tr><tr><td/><td>RNN Seq2Seq (Nam et al)</td><td colspan="5">0.828 0.996 0.894 0.858 0.457 0.807</td><td>-</td><td>-</td></tr><tr><td/><td>MP BR</td><td colspan="5">0.824 0.997 0.891 0.870 0.463 0.809</td><td>0.595</td><td>0.102</td></tr><tr><td/><td>BR (Nam et al)</td><td colspan="5">0.750 0.995 0.840 0.818 0.308 0.742</td><td>-</td><td>-</td></tr><tr><td>Bibtex</td><td>MPED</td><td colspan="5">0.178 0.987 0.443 0.444 0.362 0.483</td><td>0.376 (2.1x)</td><td>0.08 (2.1x)</td></tr><tr><td/><td>MPED Prior GDEC</td><td colspan="5">0.178 0.987 0.437 0.440 0.331 0.475</td><td>0.376</td><td>0.08</td></tr><tr><td/><td>MPED Edgeless GDEC</td><td colspan="5">0.176 0.987 0.416 0.449 0.329 0.472</td><td>0.310</td><td>0.013</td></tr><tr><td/><td>MPED Autoregressive</td><td colspan="5">0.197 0.984 0.432 0.419 0.315 0.470</td><td>0.206</td><td>0.208</td></tr><tr><td/><td>RNN Seq2Seq</td><td colspan="5">0.195 0.985 0.393 0.384 0.282 0.448</td><td>0.778</td><td>0.165</td></tr><tr><td/><td>MP BR</td><td colspan="5">0.168 0.987 0.410 0.430 0.355 0.470</td><td>0.193</td><td>0.011</td></tr><tr><td/><td>InfNet SPEN (Tu &amp; Gimpel)</td><td>-</td><td>-</td><td>0.422 -</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td/><td>SPEN (Belanger &amp; McCallum)</td><td>-</td><td>-</td><td>0.422 -</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td/><td>BR (Belanger &amp; McCallum)</td><td>-</td><td>-</td><td>0.389 -</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Delicious</td><td>MPED</td><td colspan="5">0.007 0.982 0.368 0.380 0.200 0.388</td><td>3.172 (1.1x)</td><td>0.473 (3.2x)</td></tr><tr><td/><td>MPED Prior GDEC</td><td colspan="5">0.009 0.982 0.369 0.381 0.197 0.388</td><td>3.172</td><td>0.473</td></tr><tr><td/><td>MPED Edgeless GDEC</td><td colspan="5">0.007 0.982 0.332 0.358 0.187 0.373</td><td>2.965</td><td>0.316</td></tr><tr><td/><td>MPED Autoregressive</td><td colspan="5">0.014 0.973 0.322 0.325 0.167 0.360</td><td>1.158</td><td>5.129</td></tr><tr><td/><td>RNN Seq2Seq</td><td colspan="5">0.008 0.980 0.320 0.329 0.166 0.361</td><td>3.349</td><td>1.497</td></tr><tr><td/><td>MP BR</td><td colspan="5">0.005 0.982 0.354 0.378 0.195 0.383</td><td>0.502</td><td>0.043</td></tr><tr><td/><td>InfNet SPEN (Tu &amp; Gimpel)</td><td>-</td><td>-</td><td>0.375 -</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td/><td>SPEN (Belanger &amp; McCallum)</td><td>-</td><td>-</td><td>0.375 -</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td/><td>BR (Belanger &amp; McCallum)</td><td>-</td><td>-</td><td>0.378 -</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td colspan="2">Bookmarks MPED</td><td colspan="5">0.247 0.991 0.394 0.370 0.277 0.456</td><td>9.664 (1.2x)</td><td>1.849 (1.3x)</td></tr><tr><td/><td>MPED Prior GDEC</td><td colspan="5">0.246 0.991 0.392 0.370 0.277 0.455</td><td>9.664</td><td>1.849</td></tr><tr><td/><td>MPED Edgeless GDEC</td><td colspan="5">0.245 0.991 0.350 0.354 0.256 0.439</td><td>8.501</td><td>1.534</td></tr><tr><td/><td>MPED Autoregressive</td><td colspan="5">0.252 0.988 0.347 0.304 0.209 0.420</td><td>7.146</td><td>5.74</td></tr><tr><td/><td>RNN Seq2Seq</td><td colspan="5">0.273 0.990 0.362 0.329 0.237 0.438</td><td>11.863</td><td>2.411</td></tr><tr><td/><td>MP BR</td><td colspan="5">0.241 0.991 0.382 0.364 0.275 0.451</td><td>8.022</td><td>1.312</td></tr><tr><td/><td>InfNet SPEN (Tu &amp; Gimpel)</td><td>-</td><td>-</td><td>0.376 -</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td/><td>SPEN (Belanger &amp; McCallum)</td><td>-</td><td>-</td><td>0.344 -</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td/><td colspan="2">MLP BR (Belanger &amp; McCallum) -</td><td>-</td><td>0.338 -</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>RCV1</td><td>MPED</td><td colspan="5">0.655 0.993 0.881 0.871 0.705 0.821</td><td colspan="2">98.346 (1.2x) 1.003 (1.7x)</td></tr><tr><td/><td>MPED Prior GDEC</td><td colspan="5">0.651 0.992 0.880 0.867 0.701 0.818</td><td>98.346</td><td>1.003</td></tr><tr><td/><td>MPED Edgeless GDEC</td><td colspan="5">0.650 0.993 0.883 0.875 0.721 0.824</td><td>90.142</td><td>0.884</td></tr><tr><td/><td>MPED Autoregressive</td><td colspan="5">0.660 0.992 0.881 0.868 0.715 0.823</td><td>40.366</td><td>1.928</td></tr><tr><td/><td>RNN Seq2Seq</td><td colspan="5">0.655 0.992 0.880 0.865 0.698 0.818</td><td>119.82</td><td>1.727</td></tr><tr><td/><td>MP BR</td><td colspan="5">0.640 0.992 0.870 0.864 0.642 0.802</td><td>69.957</td><td>0.593</td></tr><tr><td/><td>MLP BR (Nam et al)</td><td colspan="5">0.584 0.991 0.844 0.840 0.657 0.783</td><td>-</td><td>-</td></tr><tr><td>TFBS</td><td>MPED</td><td colspan="5">0.038 0.961 0.209 0.325 0.238 0.354</td><td colspan="2">187.14 (2.5x) 13.048 (4.2x)</td></tr><tr><td/><td>MPED Prior GDEC</td><td colspan="5">0.023 0.962 0.201 0.319 0.227 0.347</td><td>187.14</td><td>13.048</td></tr><tr><td/><td>MPED Edgeless GDEC</td><td colspan="5">0.027 0.962 0.077 0.238 0.139 0.288</td><td>126.83</td><td>12.295</td></tr><tr><td/><td>MPED Autoregressive</td><td colspan="5">0.057 0.963 0.201 0.354 0.245 0.364</td><td>163.04</td><td>114.87</td></tr><tr><td/><td>MP BR</td><td colspan="5">0.035 0.961 0.203 0.315 0.147 0.332</td><td>111.33</td><td>7.715</td></tr><tr><td/><td>RNN Seq2Seq</td><td colspan="5">0.114 0.961 0.249 0.311 0.199 0.367</td><td>459.41</td><td>54.651</td></tr><tr><td>SIDER</td><td>MPED</td><td colspan="5">0.007 0.748 0.766 0.795 0.667 0.597</td><td>0.027 (2.5x)</td><td>0.003 (21x)</td></tr><tr><td/><td>MPED Edgeless GDEC</td><td colspan="5">0.007 0.749 0.765 0.795 0.663 0.596</td><td>0.025</td><td>0.002</td></tr><tr><td/><td>MPED Autoregressive</td><td colspan="5">0.007 0.755 0.719 0.771 0.602 0.571</td><td>0.025</td><td>0.137</td></tr><tr><td/><td>MP BR</td><td colspan="5">0.007 0.749 0.766 0.793 0.667 0.596</td><td>0.021</td><td>0.002</td></tr><tr><td/><td>RNN Seq2Seq</td><td colspan="5">0.000 0.593 0.356 0.389 0.207 0.309</td><td>0.068</td><td>0.063</td></tr></table>

MLC Model Significance Using the Nemenyi Test

Table content: <table/>

Peer review (iclr2019):
 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. Though interesting, I recommend rejection for several reasons: 1) The technical contribution has limited novelty. One (very recent) reference this paper misses is "Hierarchical Graph Representation Learning with Differentiable Pooling" by Ying et al. (2018), which uses a very similar mechanism. The field is moving quickly, so references get missed sometimes, however from what I can tell, the graph-coarsening idea presented here isn*t that technically distinct from Ying el al.*s. The Mrowca et al. (2018) "Flexible Neural Representation for Physics Prediction" is also fairly similar and should probably at least be cited. 2) There aren*t strong baselines. This approach is based on GNNs, and the Graph2MLP results, which is similar to previous GNN graph-level classification methods, are fairly strong too. My suspicion is that with some more tuning and tweaking, the results here would be similar to those of Ying et al., Velickovic et al. (2017)*s Graph Attention Nets, and other models which use what Gilmer et al. (2017) terms the "readout" function for MLC. Without testing some of these other approaches, how can readers be sure this is approach has value over other approaches? The reviews by Gilmer et al. (2017) and Battaglia et al. (2018) summarize a bunch of alternatives that could be tried, some of which use similar encoder/decoder setups (not with the attentional pooling, however, as far as I know). 3) The writing is fairly dense for what is a fairly straightforward idea. And the paper is over 8.5 pages, with key details in the Appendix. I believe this approach could be quite powerful, and there was clearly a lot of excellent work that went into this project. But because the GNN area is very active, the bar is high. With a little more innovation on the model side (can the same core model be useful for things beyond MLC as well? I*m guessing it could), better baselines, better scholarship, and condensing the writing, I think this paper can be an important step forward.