Title: GRAPHSEQ2SEQ: GRAPH-SEQUENCE-TO-SEQUENCE FOR NEURAL MACHINE TRANSLATION

Abstract: Though sequential modeling has been shown to be effective, the dependency graph among words contains additional semantic information, and thus can be utilized for sentence modeling. In this paper, we propose a Graph-Sequence-to-Sequence (GraphSeq2Seq) model to fuse the dependency graph among words into the traditional Seq2Seq framework. For each sample, the sub-graph of each word is encoded to a graph representation, which is then utilized to sequential encoding. At last, a sequence decoder is leveraged for output generation. Since above model fuses different features by contacting them together to encode, we also propose a variant of our model that regards the graph representations as additional annotations in attention mechanism (Bahdanau et al., 2014) by separately encoding different features. Experiments on several translation benchmarks show that our models can outperform existing state-of-the-art methods, demonstrating the effectiveness of the combination of Graph2Seq and Seq2Seq.

1. INTRODUCTION:

Neural machine translation (NMT) is a hot topic in Natural Language Processing. Most of NMT models belong to the encoder-decoder framework (Sutskever et al., 2014; Cho et al., 2014) which encodes the source language to a representation vector and then decodes the vector to the target language. When both the input and output are sequential words, the models based on this framework are also called Sequence-to-Sequence (Seq2Seq) models (Sutskever et al., 2014; Bahdanau et al., 2014) . More importantly, the dependency graph among words is also critical for sentence modeling in the machine translation, since it contains additional semantic information (Bastings et al., 2017) . Even the sequential sentence may serialize closely-related elements far away, the dependency graph can involve all of the elements closely, which is helpful for sentence modeling. However, most of existing Seq2Seq models do not well exploit this dependency graph information. How to effectively combine the dependency graph and the sequential information to improve the translation quality, therefore, becomes a challenging problem.

To address this problem, we propose a Graph-Sequence-to-Sequence (GraphSeq2Seq) model by fusing the dependency graph among words into the Seq2Seq framework. For each sentence, we first utilize a dependency parser to obtain the dependency graph among words. Each sentence has a graph and each word has a sub-graph. Then the sub-graph is embedded to a representation for the word, and it is passed to a bidirectional sequence encoder. Finally, a decoder with attention mechanism generates the outputs. Since above model fuses different features by contacting them together to encode, we propose a variant of our model that tries another strategy by separately encoding different features. We evaluate GraphSeq2Seq model and its variant model on several machine translation benchmarks. Experiment results show our models outperforms existing stateof-the-art methods, demonstrating the effectiveness of the combination of Graph2Seq and Seq2Seq.

The main contributions of this paper are as follows.

• We propose a GraphSeq2Seq model by combining Graph2Seq model and Seq2Seq model.

The dependency graph information and sequential information are helpful for sentence modeling to generate high-quality translations. • Our GraphSeq2Seq model passes the embedding of the sub-graph of a word to a bidirectional sequence encoder. Besides, a variant of GraphSeq2Seq model is also deployed which leverages features separately to calculate the context vectors in attention mechanism. • Experiment results on four translation benchmarks show the better performance of our models than state-of-the-arts, demonstrating the effectiveness of combining dependency graph information and sequence information.

2. BACKGROUND:

We consider the problem that this paper is trying to address as how to combine Seq2Seq model and Graph2Seq model to improve the translation quality. Given an input sentence X = {x 1 , x 2 , ..., x n } and its dependency graph for each word G = {g 1 , g 2 , ..., g n }, our models combine X and G to generate the output sequence Y = {y 1 , y 2 , ..., y m }. Three sets of input-output pairs (X, Y ) are assumed to be available for training, validating and testing. The graph G is parsed from the sentence X. The trained model is evaluated by computing the average task-specific score R( Ŷ , Y ) on the test set, where Ŷ is the prediction.

2.1. SEQUENCE-TO-SEQUENCE MODELS:

Seq2Seq Models (Bahdanau et al., 2014; Neubig, 2017) are general based on Recurrent Neural Networks (RNN) encoder-decoder framework (Sutskever et al., 2014; Cho et al., 2014) . Seq2Seq models is widely used for the Machine Translation task, but it has been also used for a variety of other tasks, including Summarization, Conversational Modeling, and Image Captioning etc. Rush et al. (2015) utilized sequence-to-sequence encoder-decoder Long Short-Term Memory (LSTM) with attention to train a neural model for summarization task. Shang et al. (2015) proposed a neural network-based response generator for Short Text Conversation using the encoder-decoder framework. As long as the problem can be phrased as encoding input data in one format and decoding it into another format, Seq2Seq can be utilized to address it.

Given a sequence X, an encoder reads it into hidden state vector h. Generally, a bidirectional RNN (Schuster & Paliwal, 1997) is utilized. For the input sequence with ordering from x 1 to x T , the forward RNN calculates a sequence of its forward hidden states {

-→ h 1 , • • • , -→ h T }.

Meanwhile, reversing the input as the order from x T to x 1 , the backward RNN calculates a sequence of its backward hidden states { ← -

h 1 , • • • , ← - h T }.

Then we obtain the final hidden states by concatenating them as h j = { -→ h j , ←h j } which saves the summaries of both the preceding words and the following words.

Attention mechanism (Bahdanau et al., 2014) aims to find the parts of inputs that should be focused. Thus, the context vector c is calculated by a weighted sum of the final hidden states:

EQUATION

where the weight α t,j is computed by an alignment model. Its details can be found in Bahdanau et al. (2014) .

Given the predicted preceding words {y 1 , y 2 , • • • , y t-1 }, context vector c t , and the RNN hidden state s t , the decoder calculates a probability of the next word y t :

EQUATION

where g(•) is a softmax activation function and

EQUATION

here, f is a non-linear function. It can be a logistic function, an LSTM unit, or a Gated Recurrent Unit (GRU).

Recently, Byte Pair Encoding (BPE) is utilized for word segmentation Sennrich et al. (2016) to overcome the out-of-vocabulary problem and rare in-vocabulary problem. Both of Edunov et al. (2018) and Deng et al. (2018) achieve state-of-the-art results, where they utilize BPE on both source side and target side. However, our GraphSeq2Seq cannot apply BPE on the source side. Thus, we do not choose this kind of methods for comparison.

2.2. GRAPH-TO-SEQUENCE MODELS:

Graph2Seq models (Cohn et al., 2018; Gildea et al., 2018) are generally utilized to address the generation of graph-structured data (such as Abstract Meaning Representation (AMR) (Banarescu et al., 2013) and dependency graph (Chen et al., 2017) ) to text. It is to recover a text representing the same meaning as an input graph. Flanigan et al. (2016) converted input graphs to trees by splitting reentrances, and then translated the trees into sentences with a tree-to-string transducer. Graph convolutional networks (GCN) (Kipf & Welling, 2016) are used for semantic role labeling (Marcheggiani & Titov, 2017) and neural machine translation (Bastings et al., 2017) . Graph state LSTM (Gildea et al., 2018; Song et al., 2018) adopts gated operations for making updates, while GCN uses a linear transformation.

A graph consists of triples (i, j, l), where i and j are indices of the incoming and outgoing nodes, l is their edge label. For a sub-graph g(n) of the n-th node x n , Gildea et al. ( 2018) described incoming representation and outgoing representation as:

EQUATION

EQUATION

where x i is the node representation and e l is the edge representation, [•] is a concat operation for them. W and b are the weight and bias to encode the representations. Then Gildea et al. (2018) adopted a graph state LSTM to encode each sub-graph as:

EQUATION

EQUATION

EQUATION

EQUATION

EQUATION

EQUATION

where i n (t), o n (t) and f n (t) are the input, output and forget gates. W , Ŵ , U , Û and b are model parameters. Besides, the incoming hidden and outgoing hidden also consider the graph structure so that they are represented by (i, n, l)∈g in (n) h i (t -1) and (n, j, l)∈g out (n) h j (t -1). Then the hidden vectors are adopted in the decoder.

3. GRAPH-SEQUENCE-TO-SEQUENCE MODEL:

This section introduces the details about our GraphSeq2Seq model. Fig. 1 is an overview of our model. Given an input sentence X, GraphSeq2Seq 1) gets the sub-graph g n including the incoming nodes x i and outgoing nodes x o for each word x n , and uses a graph state LSTM (Gildea et al., 2018) to encode g n ; 2) fuses the word representation, sub-graph state, incoming and outgoing representations into a full graph representation; 3) regards the graph representation as the input of a bidirectional sequence encoder (Schuster & Paliwal, 1997) ; 4) with an attention mechanism (Bahdanau et al., 2014) , the decoder generates the output words Y .

Figure 1 : An overview for our GraphSeq2Seq model by combining Graph2Seq (Gildea et al., 2018) and Seq2Seq (Bahdanau et al., 2014) .

3.1. SUB-GRAPH ENCODER:

Given an input sentence X, we use a dependency parser Spacy1 which is a free open-source library for Natural Language Processing in Python to extract the dependency graph G among words. For each word, there is exactly another one word corresponding to it. Then we get a triple (i, j, l), where i and j are indices of the source (incoming) and target (outgoing) nodes, l is their dependency which is seen as the edge label in the graph. So each word has a sub-graph consisting of several triples from the whole graph. In the sub-graph g(n) of the n-th node x n , incoming representation and outgoing representation are x in n and x out n calculated by Eq. 4 and Eq. 5. Then through the sub-graph encoder, we get h n (t), c n (t) = gsLST M (x in n , x out n , h in n , h out n , c n (t -1)), (12) where gsLSTM is the graph state LSTM (Gildea et al., 2018) described in Section 2.2, and the incoming hidden h in n and outgoing hidden h out n also consider the graph structure with different weights so that

EQUATION

EQUATION

The final incoming hidden h in n , outgoing hidden h out n , and the final sub-graph hidden h n contains different information. We concat them trying to build a final graph representation. Since these hidden features may loss some information of the initial node representation, we adopt a highway network (Srivastava et al., 2015) to transform and keep the initial node representation x n by

EQUATION

where H n is the output of the highway network which not only contains the transformed information but also carries the initial information. Finally, through the sub-graph encoder, we get the final representation which is a concat as

EQUATION

3.2. BIDIRECTIONAL SEQUENCE ENCODER AND THE DECODER WITH ATTENTION:

Aforementioned final representation r for each node is utilized as a sequence input of a bidirectional LSTM (Schuster & Paliwal, 1997) encoder as traditional Seq2Seq models (Bahdanau et al., 2014) . Given an representation sequence with ordering from r 1 to r n , the forward hidden state and backward hidden state of r n is -→

EQUATION

where LST M f is a forward LSTM and LST M b is a backward LSTM. Note that, for the backward LSTM, we feed the reversed input as the order from x n to x 1 . Then we obtain the final hidden states by concatenating them as h j = { -→ h j , ←h j } which saves the summaries of both the preceding words and the following words. Finally, a decoder with the attention mechanism (Bahdanau et al., 2014) described in Section 2.1 is leveraged to generate outputs.

3.3. A VARIANT MODEL:

Aforementioned GraphSeq2Seq model utilizes the output of the graph encoder to be the input of sequence encoder. However, the output of the graph encoder consists of different features, such as the hidden feature h in n for incoming sub-graph, the hidden feature h out n for outgoing sub-graph, and the node representations x n . The original GraphSeq2Seq model directly concats these features to encode them together, which may lost some information. Here, we try to reserve the information by encoding these features separately. The main difference is that the original model is to encode the concated representation of the sub-graph by using only one Bi-LSTM, while the variant model leverages three Bi-LSTMs to respectively encode the specific representations of the sub-graph, including the incoming feature, the outgoing feature, and the node representation. As shown in Fig. 2 , after the sub-graph encoder, we get the hidden feature for each node. Then we rebuild the sub-graph for the current node. For the rebuilded sub-graph, its outgoing hidden feature is the input of a Graph Out Bi-LSTM, while its incoming hidden feature is for a Graph in Bi-LSTM. For the current node, its node representation is utilized for a Node Sequence Bi-LSTM. Thus, final hidden states are the concat [

--→ h out n , ← -- h out n , -→ h in n , ← - h in n , -→ H n , ← - H n ].

After that, a traditional attention mechanism (Bahdanau et al., 2014) as presented in Section 2.1 is utilized to generate outputs.

4. EXPERIMENTS:

In this section, we evaluate our model on IWSLT 2014 German-to-English, IWSLT 2014 Englishto-German (Cettolo et al., 2014) , IWSLT 2015 English-to-Vietnamese (Cettolo et al., 2015) , and WMT 2016 English-to-Czech (DBL, 2016) machine translation benchmarks. This section describes the details of the experiments, including the detailed implementations2 , comparison results and discussions. Experiment results show our GraphSeq2Seq are better than existing methods on the three benchmarks. The variant model is mostly better than existing methods. Furthermore, we also demonstrate the benefit of combining Graph2Sqe (Gildea et al., 2018) and Seq2Seq (Bahdanau et al., Table 1 : Performance comparison on IWSLT2014 German-English dataset.

Method BLEU Greedy Search Beam search MIXER (Ranzato et al., 2015) 20.73 21.83 BSO (Wiseman & Rush, 2016) 23.83 25.48 LL (Bahdanau et al., 2017) 26.17 27.61 RF-C+LL (Bahdanau et al., 2017) 27.70 28.30 AC+LL (Bahdanau et al., 2017) 27.49 28.53 NPMT (Huang et al., 2018) 28.57 29.92 NPMT+LM (Huang et al., 2018) N/A 30.08 Coaching GBN (Chen et al., 2018) N/A 30.18

Seq2Seq (Bahdanau et al., 2014) 26.90 28.79 Graph2Seq (Gildea et al., 2018) 19 2014). Besides, our GraphSeq2Seq is trained faster than the state-of-the-art method NMPT (Huang et al., 2018) .

4.1. IWSLT 2014 GERMAN-TO-ENGLISH:

This subsection presents the detailed implementations and evaluation results on the IWSLT 2014 German-to-English machine translation benchmark (Cettolo et al., 2014) . Its dataset consists of 153K training samples, 7K validation samples, and 7K test samples. We use the same procedure for preprocessing and dataset splits as in Gildea et al. (2018) ; Huang et al. (2018) . The German and English vocabulary sizes are 32,010 and 22,823 as in Huang et al. (2018) . With the words that are out of the vocabularies, we leverage an <UNK> symbol to replace them.

Implementation We use Tensorflow3 to implement the proposed models. All input sentences are padded to the same length with an additional mask variable storing the real length of each input. The hidden vector size for sub-graph encoder is 300. Three layers of the highway network (Srivastava et al., 2015) are set to transform and carry the initial node representation. One layer of the bidirectional LSTM (Schuster & Paliwal, 1997) is used for sequence encoding. For the decoder, two layers of LSTM are used to decode the passed informationThe regularization dropout with probability 0.5 is set as in Huang et al. (2018) . We trained our models with Adam (Kingma & Ba, 2014) with an initial learning rate 0.001. The batch size is set to 32, and for decoding, we use greedy search and beam search with a beam size of 10 as in Huang et al. (2018) .

Comparison Results:

We compare our GraphSeq2Seq model and its variant with existing methods including MIXER (Ranzato et al., 2015) , BSO (Wiseman & Rush, 2016) , LL (Bahdanau et al., 2017) , RF-C+LL (Bahdanau et al., 2017) , AC+LL (Bahdanau et al., 2017) , NPMT (Huang et al., 2018) , NPMT+LM (Huang et al., 2018) , Coaching GBN (Chen et al., 2018) , Seq2Seq (Bahdanau et al., 2014) , and Graph2Seq (Gildea et al., 2018) . We leverage BLEU (Papineni et al., 2002) which is a method for automatic evaluation of machine translation to evaluate our models. The higher the BLEU score is, the better the translations are. Table 1 summaries the performance comparison on IWSLT2014 German-to-English dataset. GraphSeq2Seq achieves better results than the compared methods. Compared with the state-of-the-art methods NPMT and NPMT+LL (Huang et al., 2018) , GraphSeq2Seq achieves 0.49 BLEU gains in the greedy setting and 0.58 BLEU gains using beam search. Even GraphSeq2Seq does not get much gains, it is much faster than NPMT and NPMT+LM. It takes about 16 hours to run to convergence (22 epochs) on a machine with one TITAN X GPU, while Huang et al. (2018) notes that NPMT takes about 2-3 days to run to convergence (40 epochs) on four M40 GPUs. Therefore, our GraphSeq2Seq is at least 8 times faster than NPMT. Besides, Huang et al. (2018) also reports the state-of-the-art performance on this dataset, and our Graph-Seq2Seq achieves 0.48 BLEU gains on beam search. Comparing with Seq2Seq and Graph2Seq, GraphSeq2Seq achieves at least 2.16 gains on greedy search and 1.87 gains using beam search, which significantly demonstrates the effectiveness of the combination of Seq2Seq and Graph2Seq.

For the variant of GraphSeq2Seq, it is slightly lower than GraphSeq2Seq but achieves comparable performance with NPMT. BoW+GCN (Bastings et al., 2017) 35.4 7.5 CNN+GCN (Bastings et al., 2017) 36.1 8.7 BiRNN+GCN (Bastings et al., 2017) 38.8 9.6

Seq2Seq (Bahdanau et al., 2014) 38.2 9.93 Graph2Seq (Gildea et al., 2018) 36 (Bastings et al., 2017) , GraphSeq2Seq increases the BLEU scores by 1.4 (BLEU 1 ) and 1.51 (BLEU), where the BLEU 1 means the score for 1-grams and BLEU is for up to 4-grams. Our GraphSeq2Seq is much better than Seq2Seq Graph2Seq which demonstrates the effectiveness of their combination.

4.5. DISCUSSIONS:

This subsection is to discuss the effectiveness of our GraphSeq2Seq model including 1) quantitative analysis on graph and sequence information, 2) the impact of highway layers, and 3) the impact of the weight in sub-graph encoder.

Quantitative analysis on graph and sequence information This experiment is used to verify the quantitative analysis of our GraphSeq2Seq with random graph and sequence noises based on IWSLT2014 German-English dataset. As shown in Table 5 , the random noises change from 0% to 75%, where 75% indicates that 75% of graph and sequence information are noises. 100% is not performed because it is meaningless in real life. Table 5 shows that the BLEU scores go to bad from 29.06 (Greedy) and 30.66 (Beam) to 17.38 and 20.28 when the sequence noise varies from 0% to 75%. For the graph noise, we have a similar observation that the BLEU scores go to bad from 29.06 (Greedy) and 30.66 (Beam) to 24.19 and 26.08 when the graph noise varies from 0% to 75%. It demonstrates that both graph and sequence information are effective in our GraphSeq2Seq, and the performance relies on their qualities. The impact of highway layers In GraphSeq2Seq model, we leverage a highway network (Srivastava et al., 2015) to transform and carry the initial information for input words as presented in Section 3.1. It is necessary to discuss whether the highway layers have contributions to the performance. Therefore, we conduct several experiments with different settings of highway layers. Table 6 reports the performance of GraphSeq2Seq on test set and it is training with different numbers of highway layers. Compared with no highway layers, GraphSeq2Seq using one highway layer improves BLEU from 28.13 and 29.78 to 28.84 and 30.13 respectively on greedy and beam search settings. Nearly 0.5 increment on BLEU demonstrates fusing highway layers contributes to the final performance. We test GraphSeq2Seq by varying layer numbers from 0 to 5 and find using 3 highway layers achieves the best performance. With too many highway layers, the performance may be worse than that without highway layers. A plausible reason is that using too many highway layers increases so many parameters that it needs to carefully adjust the hyperparameters and needs more epochs to run to convergence.

The impact of the weight in sub-graph encoder A weight is used in our sub-graph encoder to learn the incoming and outgoing hidden features as presented in Eq. 13 and 14. Here we discuss whether the weight contributes to the performance. Table 7 shows the performance comparisons for GraphSeq2Seq with or without this weight based on the same hyperparameters. Experiment results on three translation datasets shows that performances of using the weight are much better than the performances that without the weight. It almost improves 1 BLEU score which is a relatively big contribution to the performance of GraphSeq2Seq.

:

https://spacy.io

We will release our code on Github upon the acceptance.

https://www.tensorflow.org

CONCLUSION AND FUTURE WORKWe proposed GraphSeq2Seq, a machine translation model that combines the Seq2Seq model and Graph2Seq model. Besides the effective sequential modeling, it utilizes the dependency graph which contains additional semantic information for sentence modeling. Experiment results show promising performance of our GraphSeq2Seq on IWSLT2014 English-to-German, German-to-English, IWSLT2015 English-to-Vietnamese, and WMT 2016 English-to-Czech machine translation benchmarks. In performance comparison, GraphSeq2Seq is much better than Seq2Seq and Graph2Seq demonstrating the effectiveness of their combination. It also outperforms the state-of-the-art methods NPMT(Huang et al., 2018), BiRNN+GCN(Bastings et al., 2017) and Coaching GBN(Chen et al., 2018) as well as being trained almost 8 times faster than NPMT.In future work, we will 1) apply GraphSeq2Seq to larger datasets and more natural language generation tasks; 2) explore the graph structure among words and sentences to address the paragraph-level translation task.

Figures and Tables:

Figure 2: A variant for the encoder part of GraphSeq2Seq model. It encodes the features separately with three different Bi-LSTMs, while the original model is to encode the features by using only one Bi-LSTM.

Performance comparison on WMT 2016 English-Czech dataset.

Table content: <table><tr><td>Method</td><td>BLEU1 BLEU</td></tr></table>

Comparison ResultsBastings et al. (2017) provide three baselines for Graph Convolutional Networks (GCN), each with a different encoder: a bag-of-words encoder, a convolutional encoder, and a BiRNN. They use predicted syntactic dependency trees of source sentences to produce representations of words that are sensitive to their syntactic neighborhoods. As shown in Table4, our GraphSeq2Seq performs better than the compared methods. Compared with the state-of-theart method BiRNN+GCN

Table content: <table><tr><td/><td>.0</td><td>8.22</td></tr><tr><td>GraphSeq2Seq (Ours)</td><td>40.2</td><td>11.11</td></tr><tr><td>GraphSeq2Seq-Variant (Ours)</td><td>39.6</td><td>10.7</td></tr></table>

Quantitative analysis of our GraphSeq2Seq on BLEU scores with random graph and sequence noises based on IWSLT2014 German-English dataset. The random noises change from 0% to 75%. Note that 75% indicates that 75% of graph and sequence information are noises.

Table content: <table><tr><td/><td>0%</td><td>25%</td><td>50%</td><td>75%</td></tr><tr><td>Graph Noises</td><td colspan="4">Greedy 29.06 27.61 24.96 24.19 Beam 30.66 29.22 26.87 26.08</td></tr><tr><td>Sequence Noises</td><td colspan="4">Greedy 29.06 26.11 24.09 17.38 Beam 30.66 27.97 25.58 20.28</td></tr></table>

The impact of highway layers on the performance (BLEU) of GraphSeq2Seq on IWSLT2014 German-English dataset. GraphSeq2Seq is training with different numbers of highway layers.

Table content: <table><tr><td colspan="2">Highway Layers</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr><tr><td>BLEU</td><td colspan="7">Greedy Search 28.13 28.84 28.72 29.06 28.43 26.76 Beam Search 29.78 30.13 30.00 30.66 30.02 28.03</td></tr></table>

The impact of the weight for graph encoding on the performance (BLEU) of GraphSeq2Seq. weight w/ weight w/o weight w/ weight w/o weight w/ weight

Table content: <table><tr><td/><td colspan="2">German-English</td><td colspan="2">English-German</td><td colspan="2">English-Vietnamese</td></tr><tr><td colspan="2">w/o Greedy Search 27.59</td><td>28.84</td><td>25.11</td><td>26.02</td><td>26.65</td><td>28.45</td></tr><tr><td>Beam Search</td><td>29.13</td><td>30.13</td><td>26.60</td><td>27.32</td><td>28.35</td><td>29.26</td></tr></table>

Peer review (iclr2019):
 This paper proposes a method for combining the Graph2Seq and Seq2Seq models into a unified model that captures the benefits of both. The paper thoroughly describes in series of experiments that demonstrate that the authors* proposed method outperforms several of the other NMT methods on a few translation tasks. I like the synthesis of methods that the authors* present. It is a logical and practical implementation that seems to provide solid benefits over the existing state of the art. I think that many NMT researchers will find this work interesting. Table 4 begs the question, "How does one choose the number of highway layers?" I presume that the results in that table are from the test data set. Using the hold out data set, which number gives the best value? The paper*s readability suffers from poor grammar in some places. This fact may discourage some readers. The authors should fix the missing parentheses in Eqns. (6)-(9).