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.
As a reviewer I am expert in learning in structured data domains. Because of that I completely disagree that the proposed title of the paper is not misleading. In fact, both the input and the output of the proposed system are not graphs. Moreover, the intermediate representations are always complete graphs, so there is no graph to graph transformation here. It is the internal topology of the encoder and decoder that corresponds to a complete graph and not the nature of the processed data. 
The main intended contribution of the paper is to define a system able to capture the dependencies among input features as well as output labels, so to improve the multi-label classification task addressed by the system. This is obtained by defining a recurrent model with a complete graph topology to both encode the input and decode the output. The decoding part starts from the assumption of independence among the output labels and then, via interaction with the encoded representation of the input, eventually turns to an output where relevant statistical dependences among output labels emerge with decoding. Since both encoding and decoding are recurrent models (with no enforced guarantee to have stable points), the paper proposes to unfold the recursion for a fixed predefined number of time steps.
Presentation of the proposal is generally good, although there are some issues that are not clear. For example, the same weights indices are used for matrices belonging to the encoding and decoding, making the reader to believe that such matrices are shared. In addition, the sentence about model parameters at page 5 is a bit ambiguous and it is not sufficient to resolve the presentation problem. 
The discussion at the end of page 4 on the fact that a sequential representation for the input components is not natural is actually out of place for the specific application task selected for presentation. In fact, words in a sentence have an order. The fact that such order is lost with the bag-of-word representation is a problem of preprocessing, not of the nature of the data. In general, however, it is true that forcing an order is not natural. 
Going in the merit of the proposal, the number of parameters for the decoder scales quadratically with the number of output labels (fully connected graph). In domains with a large numbers of labels (e.g. thousands) there may be concerns on two different aspects: i) computational burden may grow significantly even if the average number of labels per item is small; ii) proper propagation of information on dependencies among labels may require to use a large value for T (graph hops), i.e. there is a dependency between size of label graph and "useful" value for T.  On this issue, by the way, figures 3 and 4 seem to report incongruent results since, because of symmetries in the model topology, equal and  reciprocal influences between input components (and output labels) would have been expected, but these are not observed in the figures. 
Analogous considerations could be done for the encoder when the size of the input is large.
Concerning experimental results, no statistical significance test is performed, so it is not clear to me if the shown improvements are actually significant. Speed-up in training and testing seem at least to give some advantage with respect to other competing approaches, however the scaling problem described above for the decoder (and encoder) may lead to much worst performances in those special cases.
The addressed problem is covered by a large literature, involving many different approaches. It would have been nice to report, for the selected datasets, the best performance (and computation times) obtained by, for example,  probabilistic graphical models or SVM-based models.
The paper seems to refer most of the relevant recent neural-based approaches.
I think the paper is relevant for ICLR (although there is no explicit analysis of the obtained hidden representations) and of interest for a good portion of attendees. 
Minor issues: 
- two rows before Section 2.2.1: \mathbb{h}_*^2  should be \mathbb{h}_*^1
- equations 4, 5, 9, 10, 14: matrices W are indexed in such a way to assume that each input word/label is associated to a different matrix (i.e., set of parameters). Is this really the case ? How is then managed the fact that different inputs may have a different number of components ? how is a specific matrix assigned to a specific word ? I guess this is a presentation mistake, otherwise there are relevant issues that are completely not addressed by the presentation.
- equation (10): since the output should be interpreted as a probability, why not using a softmax? sigmoidal units by themselves do not guarantee that the outputs sum to 1. I guess you do not have this problem because you adopt batch normalisation. This however is conceptually not nice since there is no uniformity across the dataset. Moreover, the softmax function has a nice probabilistic interpretation in the family of the exponential distributions.
- "[...] we use add a positional encoding..."
- Multi-head Attention: apart for the not so clear description, the equation involving the softmax is missing.
- "[..] the the attention and feedforward layers."
- "[..] the the sum of the total true..."