To Understand Representation of Layer-aware Sequence Encoders as Multi-order-graph
Authors: Sufeng Duan
hai zhao
Rui Wang
Venue:  (2021)
Keywords: multigraph
Transformer
natural language process

Abstract: In this paper, we propose a unified explanation of representation for layer-aware neural sequence encoders, which regards the representation as a revisited multigraph called multi-order-graph (MoG), so that model encoding can be viewed as a processing to capture all subgraphs in MoG. The relationship reflected by Multi-order-graph, called $n$-order dependency, can present what existing simple directed graph explanation cannot present. Our proposed MoG explanation allows to precisely observe every step of the generation of representation, put diverse relationship such as syntax into a unifiedly depicted framework. Based on the proposed MoG explanation, we further propose a graph-based self-attention network empowered Graph-Transformer by enhancing the ability of capturing subgraph information over the current models. Graph-Transformer accommodates different subgraphs into different groups, which allows model to focus on salient subgraphs. Result of experiments on neural machine translation tasks show that the MoG-inspired model can yield effective performance improvement.

Under review as a conference paper at ICLR 2021
To UNDERSTAND REPRESENTATION OF LAYER-AWARD SEQUENCE ENCODERS AS MULTI-ORDER-GRAPH
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we propose a unified explanation of representation for layer-aware neural sequence encoders, which regards the representation as a revisited multi- graph called multi multi-order-graph (MoG), so that model encoding can be viewed as processing capture all subgraphs MoG. The relationship reflected by Multi-order-grappe -raph, called n-order dependency. can present what existing simple directed graph explanation cannot present. Our proposed MoG explanation allows to precisely observe every step of the generation of representation, put diverse re- lationship such as syntax into a unifiedly depicted framework. Based on the pro- posed MoG explanation, empowered Graph-Transfor information over the current models. Graph--Transfommrr accommodates differ- ent subgraphs into different groups, which allows model to focus on salient sub- graphs. Result of experiments on neural machine translation tasks show that the MoG-inspired model can yield effective performance improvement.
further propose graph-based self-attentio network by enhancing the ability of capturing subgraph
INTRODUCTION
Vaswani al.) (2017) propose self-attention (SAN)-based neural network (called Transformer) for neural machine translation (NMT). As state-of-the-art NMT model, several variants of the Trans- former have been proposed for further performance improvement (Shaw al. 2018 He al. 2018) and for other natural language process tasks such as language model (Devlin et al. 2019), parsing (Kitaev & Klein 2018 Zhou & Zhao 2019), etc.
Similar as recurrent neural network (RNN)-based (Kalchbrenner & Blunsom 2013 Bahdanau al. 2013 Sutskever et al. 2014) model, SAN- models try to make representation of one word containing information of the rest sentence in every layer. Empirically, one layer alone cannot result in satisfactory result, in the meantime, staking layers may greatly increase the complexity of model
(Hao et al. 2019 Yang al. 2019 Guo al. 2019).
Better understanding the representations may help better solve the problem and further improve performance of SAN-based models. It is common model the representation as a simple directed graph, which views words as nodes and relationships between words as edges. However, such under- standing of representations may be still insufficient model various and complicated relationship among words such as syntax and semantics, let alone presenting unified explanation for the repre- sentations given by SAN- or RNN- Wang et al. (0188). In addition, simple directed graph mostly models the relationship among words but incapable of modeling the relationship among phrases or clauses.
models (Eriguchi et al.) 2016 Aharoni & Goldberg [017]]
To overcome the shortcomings of modeling the representation the hope of helping further improve SAN-based model, in this paper, we propose a novel ex- planation that representation generated by SAN-based model can be viewed as a multigraph called multi-order--ee graph (MoG). In MoG. a set of nodes and edges between these nodes form a subgraph. Meanwhile, one edge not only connects words, but also connects subgraphs which words belong to. Thus we call the relationship reflected by MoG n-order dependency, where n is the number precisely observe every
simple directed graph and then
of words involved in this relationship. With such an explanation,

---

Under review as a conference paper at ICLR 2021
step of the generation of representation, unify various complicated relationship such syntax into n-order dependency and understand the model encoding eventually.
Inspired by proposed explanation, we further propose graph-based based SAN empowered Graph- Transformer by enhancing the ability of capturing subgraph information over the current SAN-based sequence encoder. First of all, we generally define a full representation the fusing result of all concerned subgraph representations. Then let the representation of one layer split into two parts, previous representation and incremental representation. The previous representation reflects full representation from previous layer, and the incremental representation reflects new information generated in this layer. Based on this, the encoding process modified to adapt to such representa- tion division. We split the original self-attention into three independent parts to generate incremental representation. Our method accommodates subgraphs of different orders into different parts of in- cremental representation, and reduces the information redundancy. To fuse the full representation, We consider three fusing strategies in terms of different weighting schemes so that let the model focus on salient parts of the representation.
2 SIILTI-ORDER-GAAE EXPLANATION
In graph theory, directed multigraph (or pseudograph) is graph has multiple parallel edges, and these edges have the same end nodes. Two vertices may be connected by more than one directed edge. In fact, multigraph is enough reflect representation generated by model after encoding. while definition of edge cannot reflect relationship between subgraphs and the process of generation. In this paper, we propose a multigraph called multi-order-grapp (MoG) for representation of input, which defines edges to reflect relationship between nodes more accurately.
2.1 ENCODING OF MODELS
General speaking, encoding of sentence is a process to transfer a sequence of words to a sequence of vectors. During encoding, model is treated stable function independent of data without change of parameters. Representation generated by model only reflects information of input sentence.
2.2 MULTTI-ORDER-GII
We generally define MoG as G EV, SE,SNNTN TN) over a given sentence S = {si } in which nodes V {V1,..., Un reflect words of S, edges E {ei, Cm reflect relationship between words of 5, SN {sn1, sm, sn, E V, 1 < I m) } is the set of source node of each edge in E and TN- {tn,, ..., tm tn, V, < j S m) is the set of target node of each edge in E. Node E V in G can access other nodes in one step. Information captured from S is splited into two parts, (1) Word information, which are contained in V/ and reflects word, (2) Relationship information, which are contained in E and reflect relationship of word-pairs.
Note that E in G is the most difference between MoG and standard multigraph. As mentioned above, MoG revises the definition of edges to reflect relationship between subgraphs of G. In Section 2.4tionn2.4pp we will discuss the definition of edge ej E E, subgraph and relationship between edges and subgraphs in detail.
2.3 NODE AND WORD
Similar as simple directed graph, nodes in MoG reflect word of input sentence, which means number of nodes in MoG is equal to the number of words of input. Words are represented by nodes of MoG. Without relationship between words, MoG is just a set of graphs which have only one node and no edge. Obviously, one word is independent of others, and model cannot enrich word information.
2.4
EDGE AND SUBGRAPII
In this section, we define edge, subgraph and relationship between edge and subgraph in MoG.
subgraph of G is a graph whose vertex set is a subset of V, and whose edge set is a subset of E. We define Subg {subf, "... ,.., sudg) the set of all subgraphs of G. Subgraph can be defined as
2

---

Under review as a conference paper at ICLR 2021
suby = (VT, ET. SNY, TN Order of subgraph subf. which is equal to [V i..., the number of nodes in it, and also means number of the words involved in this subgraph. The simplest subgraph has one node and no edge, and order of it is 1.
Edge in MoG connects two nodes which is same as simple direct graph. However, edges in MoG reflect not only relationship between words, but also the relationship between subgraphs. Given one node-pair, several edges are generated because nodes may belong to different subgraph-pairs. p(u;, Vi V jo,, U/ E Vi( is the conditional probability present one relationship between vs and oj. It indicates that edge ej is determined by four variables, (1) source node sy of edge ej. (2) target node ing of edge ej. (3) subgraph subg in which snj E V (4) subgraph subg in which tny E V/
When ej is generated, e, will connect subf and subf and generate a novel subgraph, which we call this subgraph related subgraph of ej and use sub R(j to represent it, where R(j) is a function to
get the identifier of related subgraph of ej. To reflect importance of ej and complexity of sub myy we define order of ej. which is represented by 0j and equal to the order of sub Ru)) We can use a 6-tuple
cj = {sm,, tn subg subl. Sub 0j)
to present edge ej. If we only focus on source and target node, we can use (snj - tmj, 0j) for Ej-
a
b
e
(6--9,21
U
Je-stu
U
a
a
a
Dioh 21
ro-bb P) 11--0
(b) Loop.
(c) Overlap of nodes.
(d) Overlap of nodes and edges.
(a) No loop over- lap.
Figure 1: Generation of different kinds of subgraph.
Figure [ shows generation of four kinds of subgraph. To make the process of generating subgraph clear to understand, we only focus on subgraph without loop and overlap, which is the most simple kind of subgraph. Obviously, subgraphs and edges cannot be generated in random order. The order in which edges are generated is the order in which related subgraph of these edges are generated, which is also the order in which all subgraphs are generated. It also means that the process of subgraph (edge) generation is an iterative process, in which one subgraph (edge) relies on previous generated subgraphs (edges).
We define an operation to express the process of generating subgraphs,
sub; (sub;) -> Um U (sub;) + Un-
This operation means that one new edge (Um, Un, sub, subj, subk, VV|+VV)) and one new subgraph suby are generated, where [V/| and IV, are orders of sub; and suby. Um E sub; is the source node
of new edge, Un. E sub; is the target node of new edge and sub, is generated by connecting sub; and suby. Note that the commutative property, distributive property and associative property do not apply in this formula. For an example, the process of generating subgraph in Figure ((a) can be expressed as (((suba) v. U (subb) vb) vb U (sube) v.) va U ((suba) va U (sube) + v.) + vas
where suba, sub,, subc, suba and sub. are subgraphs with only one node. It also means that this process can be expressed as binary tree. Especially, given sentence, if we add words to one subgraph according to the order of word in the sentence, this subgraph can reflect the order of the sentence.
3

---

Under review as a conference paper at ICLR 2021
Input Order 1
Layer Order 1~2
Layer Order 1-4
Order
Order
Order
Order
Order
Layer-level Iteration
Sentence-level Iteration
Figure 2: Iteration.
As mentioned above, relationship which e, reflects is not only relationship between words but also relaitonship between subgraphs. In this paper, we call this relationship, which is a combination of relationship between words and between subgraphs, n-order dependency where n is equal to oj- In fact, n-order dependency relationship can conveniently model quite a lot of relationships among words, typically, various syntax.
2.5 FOUR KEY QUESTIONS FOR MODELS
Based on the proposed MoG explanation, effective model should better generate edges and cap- ture subgraphs iteratively, which triggers the following four basic questions.
How to preserve subgraph information? Neural models have to vector for this purpose. which lets the dimension of vectors become an important factor to define the vector accommodation.
How implement iterative encoding? Two kinds of iteration are shown in Figure 2 Sentence- level iteration allows model to encode words one by one as used in RNN-based model. With sentence-level iteration, the order of subgraph is the sentence length. All layer-aware models imple- ment layer iteration by generating representations in one layer to feed next layer.
How capture edges and subgraphs? RNN- models use recurrent networks, convo- lutional neural network based models (Gehring et al. 2017: Dauphin et al. 2017) use convolua- tion+gating blocks, and SAN-based models use self-attention.
Which architecture will be selected? A proper architecture can focus on advantages of solutions of other three questions.
These four questions are correlated to each other. Using vector causes dimension of vector im- portant. Iteration makes number of layer important and affects architecture of model. Methods to generate edges is related to proper iteration and architecture.
Inspired by the MoG explanation for the representations and following the path well answering the related four questions, may further improve the encoder design. Thus propose graph-aware Transformer as follows.
3 GRAPH-TRANSFORMER
3.1 MULTI-ORDER-GRANN IN THE TRANSFORMER
SAN-based models use self-attention to capture edges and subgraphs, and use layer-level iteration only. Regarding representation as a MoG G, we can use one-dimensional matrix to contain all information of G, which means that may use matrix with the same shape representation to represent a subgraph. Given representation for set subgraphs, one representation can be expanded into of subgraph-pair. Given representations r. and rb, usubbf...sull subgraphs contained in ra and (subf. su. } are m subgraphs contained 75 T. Σn subf Tb Σ; sub,.
Self-attention has to get an attention matrix M using query and key accoring to Equation 3 In the i-th layer of SAN-based model, representation of word 8m generated by this layer ri and

---

Under review as a conference paper at ICLR 2021
NUIL
Previous information
Lincar
Vulti-Head Attertion
Middle
Ourput
Order
& Norm
Add
Incremental Information
Input
incremental information
Vulti-Head Attantion
Middle
Norm
Ordar
Multi-Heed Attection
High
Order
Postiional Encoding
Figure 3: Graph- Transformer
attention matrix is M;, To calculate matrix Mi, if la is query and ra is key,
(rb) =
sub;)
sub")
Σ Σ subf (sub))
Value in M, reflects relationship between two words which be reflect edge in MoG. Equation (T) shows that relationship of all subgraph- pairs which are extended from ra and r. can be calculated and subgraphs by connecting old subgraphs from ra and r& also generated.
In the i-th layer, representations used as query, key and value are from the i - 1-th layer, which means that subgraphs generated by i 1-th layer will affect the largest order of subgraphs in i-th layer. Connecting two input subgraphs of the largest order will generate a subgraph of the largest order in i-th layer, which makes the largest order of subgraphs increases exponentially layers increases and the largest order of subgraphs in i-th layer is 2'.
However, SAN-based model cannot accurately capture subgraphs and obtain information of input because the largest order of subgraphs is limited by the number of layers. Information obtained by -layer model cannot be complete if the length of input exceeds 2".
Naturally, models always capture subgraphs of low order repeatedly. A generated subgraph is always contained in representation and used generate new subgraphs. As result, the earlier subgraph is generated, the more times it will be generated. It increases weight of subgraphs of low-order in latent way. Besides, saving multiple information of subgraphs one vectors makes model difficult to distinguish them and extract salient subgraphs from vectors.
3.2 ARCHITECTURE OF GRAPH-TRANSFON TRANSFORMER
Figure is the architecture of our graph- TranhhTTaafformrr. First, we define a full representation for the fusing results of all concerned subgraph information. We split full representation generated by one layer into previous representation and incremental representation to group subgraphs. Previous representatin is full representation from previous layer which also the sum of input previous and incremental representations. Incremental representation is designed for new information generated by one layer. To generate incremental representation, we split self-attention into three parts gen- erate subgraphs of different order. A gate is used to adjust weights of different groups of subgraphs. The sum of previous and incremental representations
final representation of one layer.
3.3 SELF-ATTENTION GROUP FOR SUBGRAPIS OF DIFFERENT ORDER
The original SAN-based model uses input representation query, key and value to calculate self- attention. Split input representation into previous representation and incremental representation, obvious that calculation of self-attention can be viewed the sum of four parts
ry = (rp + rz) (rp +x) = =Tp T + rp + Tp + -
where T full representation, rр is previous representation and r; is incremental representation. Note that Tp also the ry of the previous layer, which means that Tр r has been calculated by previous layer and makes subgraphs be generated repeatedly. is also the key to increase the weight of subgraphs of low-order. To avoid redundancy, we only calculate other three parts of self-attention. There three levels for the subgraph order.
5

---

Under review as a conference paper at ICLR 2021
High order. Subgraphs generated by r2 rr. belong to high order, and part of self-attention is used to process subgraph of high order, which uses imput incremental representation as its query, key and value. In the i-th layer, the order of subgraph is in the range of 2' to 2'.
Middle order. Subgraphs generated by Tp r. and Ti "p belong to middle order and other two parts of self-attention. The second part of self-attentin uses input incremental representation as query and input previous representation as key and value. The third part of self-attention uses input previous representation as query and input incremental representation as key and value. In the i-th layer, the order of subgraph is in the range of 2 to 2
Low order. Subgraphs generated by rp rr belong low order. As discuss above, it is no need to calculate Tp Tp again. Instead of self-attention, we use a linear function for transformation of vector space. The subgraph order is in the range of I to 2
To reduce number of parameters and avoid overfitting, in three parts of self-attention, while it is difficult to train such a model because different group of subgraphs requires different vector spaces. We can also drop the dimension of model in self- attention. To keep the least effect over the performance, we reduce dimension of model to half of original dimension.
share vector of query, key and value
3.4 FUSION OF REPRESENTATIONS
To get the full representation, introduce three fusing strategies to combine previous and incre- mental representation. Calculating the sum is the most simple strategy. However, this strategy depends the quality of previous representation and incremental representation. Besides, model gives four groups of subgraphs equal weights, which cannot weight important subgraphs.
Representations generated by self-attention are new subgraphs which have not been weight by model. Viewing these three parts of representation as one group, we can use a gate to calculate their importance and merge them.
w = Sigmoid + im + it), = (ia + im) + is
w).
where in. im and weight, model can explicitly distinguish new and old subgraph and pay attention on important group of subgraph. Disadvantage of this method is that the model cannot distinguish subgraph of high and middle order. We call this method weight-gate.
subgraph of high order, middle order and low order. With gate to assign
Wang et al. (2018a) propose a fusion function based on self-attention with hops for fusion of rep- resentation of different layers. Similar as Wang et al. (2018a). we use self-attention to generate a matrix of weight which stands for relationship between representations. To assign weight of four representations, we concatenate four representations to form new sequence R and calculate the matrix of relationship between different representation.
R sof soofr RR Rn.)
where Rg is the representation sequence, Rg. R₂ and R, are vector of query, key and value, dg is the dimension of model. This method can capture relationships between representations and weight them. Weight of one group will be larger it is more important than others. To make sum weight equal to 1. representation is divided by 4. We call this method self-gate. Self-gate can weight all representations by model while according to the function of self-attention, self-gate will generate subgraphs of higher order which makes model deeper and more difficult be trained.
4 EXPERIMENTS AND RESULTS
4.1 NEURAL MACHINE TRANSLATION
In this paper, evaluate model four machine translation tasks, IWSLT14 German-Englnn (De-En), WMT14 English- (En-De), WMT14 English-Freet Eigglihh-Frenhhhe (En-Fr) and WMT16 English- Romanian(En-Roo
Our baselines for En-De, En-Fr and En-Ro are Transformer-base,, and baseline for De-En is Transformer-small. Without the proposed graph mechanism, model is variant of the Trans-

---

Under review as a conference paper at ICLR 2021
De-En
En-De
En-Fr
En-Ro
Model
BLEU
BLEU
BLEU
BLEU
Existing NMT systems
Transformer (small)
(He et al. (2018))
32.9
Transformer (base)
He et al. (2018)
27.3
Transformer (base)
Shaw et al. (2018)
26.5
38.2
He et al. (2018)
35.1 (+2.2)
28.3 (+1.0)
Shaw al. (2018)
26.8 (+0.3)
38.7 (+0.5)
Our NMT systems
Transformer(smmn (mmll))
36.5
(ransformer(base)
27.1
40.1
33,9
Croah--Tannformer
37.1 (+0.6)
27.5 (+0.4)
"+half-dim & gate
37.2 (+0.7)
28.2
40.8 (G0.7)
34.67)
Multi-BLEU scores De-En, En-De, En-Fr and En-Ro. The baselines Transformer- small and Transformer-base, respectively.
Table 1:
De-En
En-De
Model
BLEU
#Para
#Speed
BLEU
#Para
#Speed
#PPL.
Transformer(small)
36.5
42M
50K
Transformer(basc)
27.1
66M
137K
4.92
Graph-Transfomin Transformer
37.1
50M
42K
27.5
77M
112K
4.92
+half-dim
37.5
47M
39K
27.4
71M
107K
4.95
+gate
37.3
57M
39K
28.0
80M
109K
4.94
+self-gate
36.9
53M
30K
27.6
77M
91K
+shared-qkv & gate
37.1
51M
40K
27.7
75M
121K
4.91
+half-dim & gate +half-dim &atte &shared-gkv
37.2
50M
35K
28.2
74M
111K
4.89
37.5
47M
38K
27.7
70M
115K
4.93
Table 2: Multi-BLEU scores of ablations on De-En and En-De. #Para, #Speed, #Mem and #PPL denote the size of model paragraphs, training speed (tokens/second), GPU memory model used (GB) and perplexity respectively.
former with three parts of self-attention. We test several methods such as half-dimension (half-dim), weight-gate (gate), shared-query-key-varr
(shared-qkv) and self-gate (self-gate). We further com- pare our model with Shaw et al. (2018) and He et al. (2018).
Shaw al. (0188) introduce relative position encoding which adds the relative distance into the representation.
He al. 2018 propose method coordinate the learning of hidden representations of the encoder and decoder together layer by layer.
Table D compares our Graph-Transformer with the baseline, showing that our model enhances both tasks and outperforms all baselines. For De-En tasks, our model with half salf-dimension gets the best performance of 37.5 BLEU points with 47 million parameters. For En-De tasks, our model with half-dimension and weight-gate gets the best performance of 28.2 BLEU points outperforming the Transformer-base by 1.1 BLEU points with 74 million paramenters. For En-Fr and En-Ro, model with half-dimension and weight-gate gets hte performance of 40.8 BLEU points out- performing the Transformer- base by 0.7 BLEU points and 34.63 BLEU points outperforming the Transformer- bease by 0.7 BLEU points respectively. With baseline of 27.1 BLEU point En-De and 40.1 BLEU point on En-Fr, the improvement Graph- Transformer is better than Shaw et al. 2018 and He et al. (2018) En-De and En-Fr tasks.
Fusion methods perform differently on De-En and En-De, For De-En tasks, self-gate gets the lowest performance of 36.9 BLEU points. For En-De tasks, calculating the gets the lowest performance

---

Under review as a conference paper at ICLR 2021
32
boseline
model
balf-dim
30
self-grte half-dim-gote
0.4
BLEU
Weight
28
0.2
26
0-10
10.20
20-30
30-40
24
0
10:50
30+
10
20
30
40
50
50+
2
3
4
10
Length of Sentence
Layers
(a) BLEU points of different lengths.
(b) Subgraph weights vs. sentence lengths in different layers.
Figure 4: The effect of sentence length and layers on performance
of 27.5. For both tasks, weight-gate is the most effective among all fusing methods. Using weight- gate to weight different groups of subgraphs has shown indeed helpful.
Figure 4(a)
shows the relationship between performance and length of input sentences. With the longer input sentences, all our methods outperform baseline.
(() that how weight of subgraph of high order change in different layers with different length of sentence. This result based on one 12-layer model with combination of -if--iimnsioon and gate. The trend of weight change means that our model will pay more attention subgraphs of higher order higher layers of model. In the appendix, Figure 5(h) means that the trend of weight change is independent of number of layers.
4.2 NAMET-ENTITY RECOGNITION, PART-OF- TAGGING, TEXT SUMMARIZATION
We also conduct new experiments on Named-entity recognition (NER), part-of-speech tagging (POS tagging) and text summarization. We use CoNLL-2003 Sangg & Meulder (2003) dataset, Wall Street Journal (WSJ) Corpus and Annotated Gigaword Napoles et al. (2012) corpus as benchmark of NER task, POS tagging task and text summarization respectively. In these experiments, former as the baseline and evaluate our model with halfdim-gate. Table shows the result of NER and POS tagging. Table shows the result of text summarization.
the Trans-
NER (FI)
POS tagging (FI)
Transformer Transforrn (halfdim&gatte)
80.2
96.40
80.3 (+0.1)
96.45 (+0.05)
Table 3: Results of NER and POS tagging
ROUGE-1
ROUGE-2
ROUGE-L
Transformer (base)
36.84
18.01
34.31
Graph- ToaphhTransfommrr (halfdim&gatte)
37.38 (+0.54)
18.59 (+0,58)
34.58 (+0.27)
Table 4: Results of text summarization.
For NER and POS tagging tasks, Shaph-Transfomen improves the performance tiny. For text sum- marization, our model with halfdim-gat outperforms the baseline on all evaluation metries.
In NER and POS tagging tasks, lengths of sentences in the dataset is often short and make the advantages of Graph- Transformer useless. As we discussed in Section 3.1 the largest order of subgraphs generated by model is limited by the number of layer while is also limited by the length of sentence. Subgraphs of high order will generated early and weight of these subgraphs will be increased in following layer.
8

---

Under review as a conference paper at ICLR 2021
5 ANALYSIS OF RESULT
According MoG explanation and the design of Graph-Transformer not calculating subgraph of low order can avoid generating subgraph repeatedly, It ensures that every subgraph to only be generated once and has the same weight, so that the model performance should be slightly improved. Meanwhile, weighting subgraphs allows model to figure out salient subgraphs. Without weighting subgraph, our model can only outperform baseline 0.4 BLEU points in En-De task, and outperform baseline more than 0.9 BLEU points after weighting subgraph by weight-gate, which is the same as we expected and indicates the reasonableness of our MoG explanation.
Fusion Methods. Table | compares different fusion methods, in which weight-gate gets the best performance, while self-gate is not the best one as expected. Calculating sum of representation only makes every subgraph be generated once and have the same weight while it cannot allow model to figure out salient subgraphs. This method also performs worst.
Self-gat weight every group of subgraphs which cannot be done by weight- gate. However, using self-attention and representation, self-gate will generate new subgraphs of high order and unnecessary redundancy. Self-gate also makes model deeper and difficult to train.
Although weight-gan gath cannot distinguish every subgraph in representation. it makes model focus on specific parts. In fact, using the same query. key and value produce representations, there some stable relationship between them. Dividing them into two groups can mostly distinguish this relationship and allow model to capture it.
Dimension of Models. Table shows that model with half dimension can get a similar or better result compared with model with full dimension. Larger model dimension enables vector to accom- modate more features. Our results do not mean larger dimension is unimportant. Though we use less parameters, our model can capture subgraph more accurately. Our model can distinguish subgraph with different orders with three independent parts of self-attention,
Besides, more parameters usually let model more difficultly trained and more easily be overfitting. Thus half dimension setting helps the resulted model to outperform the model with full dimension.
RELATED WORK
Several variants have been proposed to improve performance of the original SAN-based model. Shaw et al. (2018) proposed relative position representations in the self-attention mechanism to re- place the absolute position encoding and it enhances the ability of capturing local information of the input sentence. He et al. (2018) shared the parameters of each layer between the encoder and decoder coordinate the learning between encoder and decoder. BERT (Devlin et al. 2019) is a lan- guage model which is to pre-train deep bidirectional representations from unlabeled text by jointly conditioning on both left and right context in all layers. Dai al. (2019) enabled the Transformer to learn dependency beyond a fixed length without disrupting temporal coherence, KedzorlKedziorski al. (2019) propose Graph-based model on text generation. [Zhu al. (2019) use graph structures for AMR. Cai & Lam 2020 propose a graph structure network for AMR.
CONCLUSIONS
This paper presents unified explanation for representations given by sequence encoders, especially, the SAN empowered Transformer. Instead of simple directed graph modeling in previous work, we re-define multigraph into multi-order-grapp to accommodate broad categories of complicated relationships inside the representations. MoG connects not only words but also subgraphs. With the built relationship by MoG, which is called n--order dependency, we can understand diverse rela- tionships inside representations as complicated as syntax in a unified way. Inspired by the proposed MoG explanation, we further propose graph-Transforme to enhance the ability of capturing sub- graph information on the SAN-based encoder. Experimental results indicate that our proposed MoG explanation for representations is empirically reasonable.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Roce Aharoni and Yoav Goldberg. Towards string-to-tree neural machine translation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Pupers), Vancouver, Canada, July 2017. Association for Computational Linguistics.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Con- ference Track Proceedings, 2015.
Deng Cai and Wai Lam. Graph transformer for graph-to-seques learning. In The Thirty- Fowrth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applica- fions of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp-
7464 7471. AAAI Press, 2020.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoe Le, and Ruslan Salakhutdinov. Transformer-XL. XL: Attentive language models beyond a fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, Florence, Italy, July 2019. Association for Computational Linguisties.
Yann N. Dauphin, Angela Fan, Michael Auli, and David Grangier. Language modeling with gated convolutional networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 933-999399939 133-941.77 PMLR, 2017.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLTT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume (Long and Short Papers), pp. 4171-4186. Association for Computational Linguistics, 2019.
Akiko Eriguchi, Kazuma Hashimoto, and Yoshimasa Tsuruoka. Tree-to-sequence attentional neural machine translation. In Proceedings of the 54th Anmual Meeting of the Association for Compu- tational Linguistics (Volume 1: Long Papers), Berlin, Germany, August 2016. Association for Computational Linguistics.
Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N. Dauphin. Convolutional sequence to sequence learning. Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference Machine Learning, ICML. 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 1243-1252, PMLR, 2017.
Qipeng Guo, Xipeng Qiu, Pengfei Liu, Yunfan Shao, Xiangyang Xue, and Zheng Zhang. Star- transformer. In Proceedings of the 2019 Conference of the North American Chapter of the As- sociation for Computational Linguisties: Human Language Technologies, Volume I (Long and Short Papers), Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.
Jie Hao, Xing Wang, Baosong Yang. Longyue Wang, Jinfeng Zhang, and Zhaopeng Tu. Modeling recurrence for transformer. In Proceedings of the 2019 Conference of the North American Chap- of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), Minneapolis, Minnesota, June 2019. Association for Computational Linguisties.
Tianyu He, Xu Tan, Yingce Xia, Di He, Tao Qin, Zhibo Chen, and Tie-Yan Liu. Layer-wise coordi- nation between encoder and decoder for neural machine translation. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Biancha Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Infor- mation Processing Systems 2018, NeurIPS 2018, 3-8 December 2018 Montréal, Canada, pp- 7955-7965, 2018.
10

---

Under review as a conference paper at ICLR 2021
Nal Kalchbrenner and Phil Blunsom. Recurrent continuous translation models. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, Seattle, Washington, USA, October 2013. Association for Computational Linguistics.
Nikita Kitaev and Dan Klein. Constitueney parsing with self-attentive encoder. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Melbourne, Australia, July 2018. Association for Computational Linguistics.
Rik Mancel-Kedziooski Dhanush Bekal, Yi Luan, Mirella Lapata, and Hannaneh Hajishirzi. Text Generation from Knowledge Graphs with Graph Transformers. In Proceedings of the 2019 Con- ference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Volume I (Long and Short Papers), pp. 2284-222 2293, Minneapolis, Min- nesota, June 2019. Association for Computational Linguistics.
Zhouhan Lin, Minwei Feng, Cícero Nogueira dos Santos, Mo Yu, Bing Xiang, Bowen Zhou, and Yoshua Bengio. A structured self-attentive sentence embedding. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Courtney Napoles, Matthew R. Gormley, and Benjamin Van Durme. Annotated gigaword. In James Fan. Raphael Hoffman, Aditya Kalyanpur, Sebastian Riedel, Fabian M. Suchanek, and Partha Pra- tim Talukdar (eds.). Proceedings of the Joint Workshop on Automatic Knowledge Base Con- struction and Web-scale Knowledge Extraction, AKBC- CRCC-WEKEXOO @ NAACL-HLT 2012, Montrèal, Canada, June 7-8, 2012, pp. 95-100. Association for Computational Linguistics, 2012.
Erik F. Tjong Kim Sang and Fien De Meulder. Introduction to the conll-2003 shared task: Language- independent named entity recognition. In Walter Daclemans and Miles Osborne (eds.), Proceed- ings of the Seventh Conference on Natural Language Learning, CoNLL Held in cooperation with HLT-NAACL 2003, Edmonton, Canada, May 31 June 2003, pp.
ACL,, 2003.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representa- tions. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), New Orleans, Louisiana, June 2018. Association for Computational Linguistics.
Ilya Sutskever, Oriol Vinyals, and Quoe V. Le. Sequence to sequence learning with neural networks. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q Wein- berger (eds.). Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pp. 3104-3112 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Gareett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp- 5998 6008, 2017.
Qiang Wang, Fuxue Li, Tong Xiao, Yanyang Li, Yinqiao Li. and Jingbo Zhu. Multi-layer represen- tation fusion for neural machine translation. In Proceedings of the 27th International Conference on Computational I Linguistics, Santa Fe, New Mexico, USA, August 201 1018a. Association for Com- putational Linguistics.
Xinyi Wang, Hieu Pham, Pengcheng Yin, and Graham Neubig. tree-based decoder for neural machine translation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October-November 2018b. Association for Computa- tional Linguistics.
Baosong Yang, Longyue Wang, Derek F. Wong, Lidia S. Chao, and Zhaopeng Tu. Convolutional self-attention networks. In Proceedings of the 2019 Conference of the North American Chap- of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), Minneapolis, Minnesota, June 2019. Association for Computational Linguisties.
11

---

Under review as a conference paper at ICLR 2021
Junru Zhou and Hai Zhao. Head-Driven Phrase Structure Grammar parsing on Penn Treebank. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, Florence, Italy, July 2019. Association for Computational Linguistics.
Jie Zhu, Junhui Li, Muhua Zhu, Longhua Qian, Min Zhang, and Guodong Zhou. Modeling graph structure in transformer for better amr-to-text generation. In Kentaro Inui, Jing Jiang, Vincent Ng, Empirical Methods in Natural
and Xiaojun Wan (eds.), Proceedings of the 2019 Conference Language Processing and the 9th Interaational Joint Conference on Natural Language Process- ing, EMNLP-IJCNIPP 2019, Hong Kong, China, November 3-7, 2019, pp- 1458-5467, Associa- tion for Computational Linguisties, 2019.
A APPENDIX
A.1 BACKGROUND OF GRAAPH-TRANSFORMERR
Transformer (Vaswani et 2017) is state-of-the-ar NMT model empowered by self-attention net- works (SANs) (Lin et al. 2017). in which an encoder consists of one self-attention layer and position- -ssse feed-forward layer, decoder contains one self-attention layer, one encoder-decoder attention layer, and one position-wise feed-forward layer. SAN-based model is also used in other tasks such as language model (Devlin et al. 2019), parsing (Kitaev & Klein 2018 Zhou & Zhao 2019), etc. SAN-based model uses residual connections around the sublayers followed by layer normalization layer.
The encoder reads input sentence, which is word sequence (21. }. and encodes it as a context vector c. Decoder trained to predict the next word given the context vector generated by encoder and all previously predicted words {yı.-.., 1t-1)- The decoder defines a probability the translation by decomposing the joint probability into the ordered conditionals,
Ty
p(y) = II p(u
Yuı, ... .))
Scaled dot-product attention is the key component in Transformer. The input of attention contains queries (Q), keys (K), and values (V) of input sequences. The attention is generated using queries and keys like Equation
QKT
Attention(Q, K, V) softmax
JV.
Van
Different from RNN-based models which process words/subwords one by one, dot-product attention allows Transformer generate the representation in parallel.
Vaswani et al. (017) also propose multi-head attention which generates representation of sentence by dividing queries, keys, and values to different heads and gets representative information from different subspaces.
Quality of encoding sentence and generating representation can influence performance of NMT model significantly. RNN-hased and SAN-based models use different mechanisms to implement encoding, thus show different natures for the resulted representation. RNN-based model is good at capturing localness information and not good at parallelization and long-range dependency captur- ing, while SAN-based model is better at capturing long-range dependencies with excellent paral- lelization.
A.2 DATASETS OF EXPERIMENTS
IWSLT14 Ferman-Engllste IWSLT14 De-En dataset contains 153K training sentence pairs. We use 7K data from the training set validation set and use the combination of dev2010, dev2012, tst2010, tst2011 I and tst2012 as test set with 7K sentences which are preprocessed by scrip BPE algorithm is used to process words into subwords, and number of subword tokens is 10K.
12

---

Under review as a conference paper at ICLR 2021
Parameter
DE-EN
EN-DE
Layers
6
Dimension
512
512
Head
8
FF
1024
1024
Dropout
0.3
0.1
Table 5: Hyperparameters for our experiments. FF is short for feed-forward layer.
WMT14 Gerlish We use the WMT14 En-De dataset with 4.5M sentence pairs for training. We use the combination of newstest2012 and newstes12013 as validation set and newstesr2014 4 as test set which are preprocessed by script] The sentences longer than 250 are removed from the training dataset. Dataset is segmented by BPE so that number of subwords in the shared vocabulary 40K.
A.3 HYPERPARAMETERS OF EXPERIMENT
The hyperparameters for our experiments are shown Table For De-En, we follow the setting of Transformer-small. For En-De, we follow the setting of "Transformer-base.
A.4 TRAINING OF EXPERIMENT
Our models for En-De, En-Fr and En-Ro are trained on one CPU (Intel i7-5960X) and four nVidia RTX TITAN GPUs, and models for De-En are trained on one CPU (Intel i7-5960X) and one n Vidia RTX TITAN X GPU. The implementation of model for NMT tasks is based on fairseq-0.6.2. 10-9 and the learning rate setting
We choose Adam optimizer with 31 0.9, 82 0.98, strategy, which are all the same as Vaswani et al. (2017).
d-0.5 min(step 0.5 step warmuppter -15)
where d is the dimension of embeddings, slep is the step number of training and wornopptee is the step number of warmup. When the number of step is smaller than the step of warmup, the learning rate increases linearly and then decreases.
We use beam search decoder for De-En task with beam width 6. For En-De, following Vaswani al. (2017), the width for beam search is 6 and the length penalty is 0.2. The batch size is 1024 for De- En and 4096 for En-De. We evaluate the translation results by using multiBLEU.
A.5 AN EXAMPLE OF MODELING SYNTAX IN MOG
Figure 7 shows an example of modeling syntax MoG. Similar as this example, one syntactic tree can be viewed as one subgraph of MoG. Generating a syntactic tree can be viewed process of generating subgraph. We can use an equation to express example,
subsens =(((suboo) + UD (subas) + vdo) Udo
U ([subRomone) + URomnns U (subure) + Uthe) + URomone) + Udo
(4)
U (subas) Vas
where subsens is the subgraph reflect whole sentence.
A.6 LAYER-LEVEL. AND SENTENCE-LEVER ITERATION
As discussed in Section 2.4 process of subgraph (edge) generation is an iterative process, in which one subgraph (edge) relies on previous generated subgraphs (edges). Here is one question for this operation,
* Where did previous generated subgraphs come from?
13

---

Under review as a conference paper at ICLR 2021
0.6
0-10
10-20
20-30
30-40
40-50
504
0.5
Weight
Weight
0.5
0.4
0-10
10:20
0.4
20-30
30-40
40-50
50+
2
3
2
3
4
5
6
Layers
Layers
(a) 5 layers.
(b) layers.
0.5
0.5
Weight
Weight
0.4
0.4
0.3
0.3
20:30
30-40
20-30
30-40
40:30
30
40-50
50+
0.2
2
3
4
7
3
5
7
8
Layers
Layers
(c) 7 layers.
(d) layers.
0.4
0.4
Weight
Weight
0.2
0.2
0:10
10:20
0-10
10:20
40-50
0
2
5 7
2
3 4
5
6
7
8
10
11
Layers
Layers
(e) 9 layers.
(1) 10 layers.
0.4
0.4
Weight
Weight
N
0.2
0.2
0-10
-
10-30
0-10
10-20
20:30
30-40
20:30
30-40
0
40.50
50+
0
40.50
50+
2 3 4 5 7 8 9
10
11
12
2
3
4
5 6 7
8 9 1011
Layers
Layers
(g) 11 layers.
(h) 12 layers.
Figure 5: Subgraph weights in models with different layers on WMT14 En-De.
14

---

Under review as a conference paper at ICLR 2021
Capture Suegraph
Capture Subgraph
Input Order
Layer Order
Layer 2
Input
Order
Layer
Layer Order 1-4
Figure 6: An example of layer-level iteration in Figure Note that in one layer, layer-level iteration only operates once which only takes output of previous layer as input and generates new subgraphs.
root
advel
mark
Do
do
as
root
mark
Do
as
the
Romans
do
the
Romans
Do U
do
Do
do
Do
do
Do
do
as
U
as
Romans
U the
Romans
the
the
Romans
the
Romans
Figure An example of modeling syntax in MoG.
which can also be transferred another question,
Where will subgraphs generated be used to capture new subgraphs?
Two kinds of iteration are answers the question. Layer-level iteration means that one layer uses subgraph generated by previous layer to capture subgraph, and generated subgraph will be used in next layer. Sentence-level iteration means that one layer uses subgraphs generated in the same layer at previous time step, and generated subgraph will be used in the same layer at next time step.
Note that layer-level iteration is not the opposite of sentence-level iteration. They can be used together in one model, can exist independently in one model. However, in most of layer-aware model with multiple layers, layer-level iteration necessary.
A.7 MoG EXPLANATION FOR RNN
MoG also explain encoding of RNN-based model, and analysing RNN-based model with four questions in Section 2.5 good start. Considering the various variants of RNN, we focus on GRU-based model and give explanation of GRU-based model as example.
15

---

Under review as a conference paper at ICLR 2021
How to preserve subgraph information? GRU-based model uses vector to preserve subgraph information same as other neural models.
How to implement iterative encoding? GRU-based model uses Layer-level iteration and Sentence-level iteration, which means that (1) GRU-based model can capture order infor- mation directly from the encoding. (2) one layer is enough to capture subgraphs of largest order theoretically.
How to capture edges and subgraphs? GRU-based model uses one GRU cell to capture edges and subgraphs. The key component in GRU cell capture edges is gate.
Which architecture will be selected?? Architecture of GRU-based model is simple which is only stack of GRU layer.
Given input sentence (21...., one layer of GRU-based model encodes words sequentially and representation of one word depends on representation of previous words
h (111-,,i111 c² q(thi,....hh)
(5)
where hi E is a hidden state of i-th layer time step t, and c is vector generated from the sequence of the hidden states of i-th layer. f and q are some nonlinear functions. Time is also position of words in the sentence.
The GRU transition equations are the following
of oW!! h
6(21),
r oW, 1/- h b(())
(6)
h tanh W (W (1 1 - // (1)),
h4 (1 =)) @ - + + hi
where zf and rī is the update gate and reset gate of f-th time step i-th layer respectively, and hū is the hidden state of t-th time step in i-th layer.
Besides, the LSTM transition equation are the following
inf = o(W (nn) (n) h
1- + U + ((m))
fi (W -(() 1/ (17), of (W! M U. Mis 1100),
" = manh(W," h; U + ((()).
df in! o of + o
hf of o tanh(ct)
where inj. fi and of are the input gate, forget gate and output gate of (-th time step in i-th layer respectively, ej is the state of cell and hf is the hidden state of 1-th time step in i-th layer.
LSTM and GRU are depended on gate
Wi + Unh,
Given representation for a set of subgraphs, one representation-pait can be expanded into set of sube) subgraph-pair. Given representation ra and rb (subq, .u.dgg are subgraphs contained in r. and ...ubb h } are m subgraphs contained in T'
Ta = Σ sub Tb = Σ sub
(9)
16

---

Under review as a conference paper at ICLR 2021
Equation of gate can be transferred to
m
Wra Urp + W
Σ
sulif + U
Σ
sull +
j
1
m W
sub.
+
n U
subj + b
m
n
(10)
subf
suby
m
W
+
subg
sube
W
U
which means that calculating relationship between Ta and can be transferred to calculating rela- tionship all subgraph- pairs of ra and rb. Relationship of subţ and sub,, is calculated by gate. New representation generated by LSTM GRU is also set of subgraph information.
Note that weights of edges always decrease with the increase of subgraphs. It causes that the earlier subgraph is generated, the larger its weight is, which is similar SAN-based model. Different from RNN-based model, weight of subgraph is reflected by the number of times is repeatedly generated.
RNN-based model uses layer-level and centence-level iteration. Different from SAN-based model which uses more layers to generate subgraphs of higher order, RNN-based model can generate subgraphs of largest order in one layer. Therefore, design of deeper model is more suitable for SAN-based model. Even if the SAN-based model cannot capture subgraph of higher order, it can also adjust and balance the weight of subgraph using more layers.
A.8 USING MoG EXPLANATION TO SOLVE EXISTING PROBLEMS
A.8.1 WHAT IS -ENODDING IN SAN-BASED MODEL?
Position-encoding is a component to mark the position of words. In SAN-based model, position encoding is implemented as one-dimensional vector which can also be viewed as special feature, and is combined into the representation of input which becomes one part of word information discussed in Section 2.2. Encoding input sentence can generate relationship between different positions while it cannot reflect order of input sentence directly. Relationship between positions is contained in representation, which is also contained in edge from the perspective of MoG.
Position and order of words two related property while they not exactly the same. In some cases, these two property cannot be converted to each other. Position an absolutely fixed property which exist independent from other positions, while order is relatively property which must depend on other words. In NLP, position of words can be converted to order of words because the input sentence is usually a continuous uninterrupted one-dimensional word sequence and the value of position is often one integer which can obtain order by comparing the value of position. It is also the reason why SAN-based model try to use position-encoding to make use of the order of the sequence.
Although there are various methods to indicate the location information in position-encoding and it is easy for human to convert position to order, it is difficult for SAN-based model to effectively obtain the order of sequence from location information. We conduct an experiment on IWSLT 14 De-En to show that SAN-based model views position-encoding as a feature and cannot capture indirect order information of sequence which we put position-encoding. In our experiment, we replace well organized and designed position-encoding with another position-encodiig which is designed by us. Without any well organized functions to generate vector for position-encoding we full all vector of position-encoding with random value in range from 0 to 1, which means that there is no meaningful information in position-encoding Table [ shows the result of experiment that position-encoding with random value does not impact performance negatively.
17

---

Under review as a conference paper at ICLR 2021
Transformer 36.5
Transformer (no PE)
Transformer (random PE)
MultiBLEU
21.5
36.8
Table 6: Results of experiments on IWSLT 14 De-En about position-encoding Word PE is short for
position-encee .ettioon..
This evidence shows that here is no need add position information to position-encoding because model views position-encoding as feature instead of converting them to order of sequence. It also shows that MoG cannot capture sequential information using position-encoding.
Position-encoding is still necessary for Traph-Tranffommer. Position-ensn eeniiiin-nncoding is still the only com- ponent for Graph-Trrasfommn to capture position information which is same as the original Transformer. If one sentence contains one word multiple times, model can distinguish them at least. However, position-encoding cannot solve the problem that SAN-based model cannot capture local- ness information. Position is not order.
A.8.2 WHY DOES PERFORMANCE OF MODEL DECREASE WHEN THE SENTENCE IS TOO LONG?
First, given sentence, the MoG to reflect all relationship between words is definite and fixed, and cannot change. Performance of model reflects the ability to capture information for rebuilding this MoG from input sentence.
When the sentence is too long, models cannot capture enough information. As mentioned above, RNN-based model and SAN-based model cannot capture all subgraphs to rebuild the entire multi- graph for different reason. Therefore, whether RNN-based model or SAN-based model, there should be special length of sentence. If sentence is longer than this length, performance will drop very quickly.
Besides, in the training data, the proportion of long sentences is often very low, which makes model fail to learn long sentences.
A.8.3 WHY PRE-TRAINING DATA CAN IMPROVE PERFORMANCE OF MODEL?
According MoG explanation, word information cannot be enriched. In most of models, word information is generated by embeddings. A pre- pre-training data feeds model better word information which can improve performance. Relationship information generated by using word information can also be more precise.
A.8.4 WHAT IS NECESSARY TO DO DURING DESIGNING A NOVEL ENCODER?
novel method to capture all subgraphs to rebuild the multigraph from the input sentence. Re- fer to RNN-based model and SAN-based model, and four basic questions in Section 2.5 we can summarize as follows.
A proper architecture of model.
A novel method should proposed to calculate relationship between two given represen- tations.
This function should satisfy the modified law of distribution. Namely, given ra Σ. r? and rb Σ" r). function f should satisfy the law of distribution
f(ra, ΣΣ
w woy frf, r
(11)
where wi is the weight for one relationship value.
Several relationship can be added to one representation.
f does satisfy the exchange law. Namely (a, s(b,a).
18

---

Under review as a conference paper at ICLR 2021
Several iterative processes should be proposed for generating representation. Generated representation should be feed to model for input representation and generate new represen- tation.
A.8.5 IS INFORMATION MODEL GENERATED ALL BENEFIT THE PERFORMANCE?
No. Some subgraph information like a- > b- a- b- > influences the performance model.
is one kind of noise which
19


Reviews:
[{"review_id": "b8f4NCCbNkW", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper proposes a new multigraph architecture called Multi-Order-Graph to explain the representation generation process in neural sequence encoders (Self-Attention or SAN based models). The main contribution of this MoG is the introduction of n-order dependency which can model not only relationships between words but also high order relationships such as syntax and semantics between subgraphs. Taking inspiration from MoG explanation, a self-attention powered Graph Transformer is proposed which beats the Transformer baselines on NMT tasks (English-German and German-English).\n\n-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\nPros: \n\n+ The proposed idea of representing the encoding process as generation of a Multi-Order-Graph is novel and is able to provide good insights for SAN-based models.\n\n+ Proposed Graph Transformer uses self-attention and also attends over different order of subgraphs (low-order, middle-order and high-order). Since these subgraphs represent high order relationships (syntax, semantics etc.), the model is able to pay attention to salient subgraphs.\n\n+ This paper could fuel further research in the explainability of neural sequence encoders and SAN based models.\n\n------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\nCons: \n\n- The key concern about the paper is the lack of rigorous experimentation to study the usefulness of the proposed method. Only two datasets are used for NMT task. There has been a lot of improvement on base Transformer models (cited in the paper), still there is no comparison with them.\n\n- This paper claims that with the proposed MoG explanation it is possible to model high order relationships such as Syntax and Semantics. However, there is no example provided for this. Even some cherry picked examples would have helped in visualising the behaviour.\n\n------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nOverall, I would like to see the paper at the conference. The idea of modelling the relationships as a Multi-Order-Graph is certainly novel and can fuel further research. However, due to the current state of experimentation I am voting for **rejecting** the paper.  I am willing to increase the score if the concerns are addressed by authors in the rebuttal period. \n\n------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nQuestions and Suggestions:\n\n1. I would like to see comparisons with models like Transformer(big), [Shaw et al.](https://arxiv.org/pdf/1803.02155.pdf), [He et al.](https://papers.nips.cc/paper/8019-layer-wise-coordination-between-encoder-and-decoder-for-neural-machine-translation.pdf). I would also encourage usage of some more datasets for the experimentation, for example En-Fr, En-Ro. Datasets can be found in the papers linked above.\n\n2. It would be interesting to see how different components of the Graph Transformer affect perplexity.\n\n3. What is Transformer(small)? I am sorry but I am not aware of this variation. It would be good if you could provide a reference for this particular variation of the model.\n\n4. In Fig 4a, it is evident that self-gate works better at encoding longer sentences. It would be good to see some discussion on this in the paper.\n\n5. Which dataset is used for Fig 4?\n\n6. In fig 4b, we can notice a sudden decrease in subgraph weight at layer 4 for 12 layered model. In figure 5, similar trend can be seen for different layered model except for 9 and 10 layered model. What is the significance of this behaviour?\n\n7. I would encourage the authors to provide the implementation for the model proposed in this paper. \n\n------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nMinor Comments/Typos:\n+ Section 2.4: source node of edge Snj -> Snj, source node of edge Ej\n+ Section 2.4: target node of edge Tnj -> Tnj, target node of edge Ej\n+ Section 3.3: the order of subgraph is in the range of 2^(n-1) to 2^(n) -> the order of subgraph is in range 2^(i-1) to 2^(i)\n   Similar mistake is in Middle-Order and Low-Order section. \n+ Section 7: MoG connects only only words but also subgraphs -> MoG connects not only words but also subgraphs. \n+ A.5.3: Rlationship information generated -> Relationship information generated\n\nPost Rebuttal Comments: Authors have addressed most of my concerns and as a result I have increased the rating from 5 to 6. Thanks!", "extra_scores": {}, "extra_text": {}}, {"review_id": "_hN00kyWYhs", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\nThe authors propose a new Transformer variant for neural machine translation. Compared with the standard Transformer framework, this work explains the representation generation process of the encoder via a multi-ordered-graph MoG and develops a novel Graph-Transformer method based on MoG, which is capable of capturing diverse relationships within the sequence. Empirical results over benchmark datasets validate the effectiveness of the proposed method. \n\n### Pros\nThis work appears originally in its new explanation of the representation generation process. Specifically, the main pros are summarized below.  \n1.\tIt provides a multi-ordered-graph MoG explanation for the representation generation of Transformer encoder. MoG is capable of capturing diverse relations of the sequence compared with standard simple directly graph explanation.  \n2.\tIt develops a novel method, dubbed Graph-Transformer, by combining MoG and Transformer, which generates layer-wise representation from the previous representation and incremental representation aspects explicitly. \n3.\tIt implements two fusion strategies, i.e., weight-gate and self-gate, for layer-wise information aggregation. Ablation study is also conducted to investigate the effectiveness of them. \n\n### Cons\nMy primary questions/concerns are listed below. \n1.\tThe experiments are limited with only two benchmark datasets. Since Transformer has been demonstrated to be effective in many NLP tasks, it would be better to include more datasets or even other tasks except neural machine translation for a comprehensive comparison. \n2.\tThe selection of the baseline seems unfair. As stated in Section A.5.1, position-encoding can be viewed as a specific MoG because it builds edges between nodes. Therefore, methods that focus on position-encoding should also be included for comparison. For your reference, Transformer-XL[1] and [2] are two tailored solutions for this purpose. \n3.\tIt is unclear about the model’s efficiency, i.e., memory-efficiency and learning efficiency. The idea to split the layer-wise full representation into previous representation and incremental representation is interesting. However, it also inevitably increases the model complexity. The authors should provide more discussions about the model complexity to improve the quality further.\n4.\tIn Figure 3, why position-encoding is needed? MoG is already capable of capturing the sequential information by merging subgraphs. More explanation is welcomed for this configuration. \n\n### Clarify\nThis work is well organized and easy to follow. However, the readability can be improved by addressing the following suggestions. \n1.\tThe layer-level iteration in Figure 2 is difficult to understand; it would be better to give a toy example with a real sentence for a better explanation. \n2.\tIn the second sentence of Section 2.4, r is not defined. In my understanding, each generated edge $e_j$ constructs a unique sub-graph, then what is r stand for?    \n\n[1] Dai, Zihang, et al. “Transformer-XL: Attentive language models beyond a fixed-length context”, ACL, 2019. \n[2] Wang Benyou, et al. “Encoding word order in complex embeddings”, ICLR, 2020. \n \n\n### Response to Rebuttal\nThank authors for taking the time to clarifications and considering my comments.\n\nWe appreciate authors' efforts to add additional experiments results in Table 1 and Table2. However, the performance improvements are marginal (more or less 0.7) and speed of Graph Transformer is slower than transformer.\n\nEven though additional explanations about positional encoding (Appendix 8.1) can resolve our concerns, layer iteration (Figure 6) are not still clear for us, e.g., what are orange blue, yellow nodes? how layer iterations are used in graph transformer? Authors should refine its main context to increase understanding instead of adding lengthy Appendix for us. This such paper presentation and organization are not clear to understand.\n\nConsidering the above points, we still remain our decision.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6IXdGoRZ7a", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper has propose the layer-aware graph transformer to enhance the ability of capturing heterogeneous information of the current models. The experimental results has justified the effectiveness of proposed model.\n\nThe multi-order graph structure is innovative and contribute to the expression of generating subgraphs. Such operations has benefited for questions the proposed in section 2.5, which I believe could bring up insightful idea to the community. However, there are still some parts that should be given an extended clear statement.\n\n1, it is not clear how the \"unified explanation\" is defined and delivered in the graph-transformer model? Does it contribute the the model performance? MoG seems doesn't make a well-defined explainability to reflect the quantitative model explanation.\n\n2, How MoG 'observe' every step of generation of embedding? Is there any model transparency defined?  \n\n3, Could the model be more generalized to other downstream task besides NMT?\n\n4, It is not cleared that in the 2.2, whether it could be overlaps between SN and TN? If so, the number of generation of kinds of subgraph could be very large.\n\n5, The experimental parts lack of detail procedure. How to extract the relations within each sentence? Also the performance of the proposed model may highly be dependent over the quality of MoG construction, which may limit the generalization ability of the model.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes to explain the representation for layer-aware neural sequence encoders with multi-order-graph (MoG). Based on the MoG explanation, it further proposes Graph-Transformer as a graph-based self-attention network empowered Transformer. As commented by the authors, a main purpose of Graph-Transformer is to show an example application of the MoG explanation.

During the discussion period, after reading the paper and checking the code, the AC had raised a serious concern: There is a big gap between the MoG motivation and the actual implementation. The AC had urged the referees to take a careful look at the implementation details, in particular, Lines 524-561 in the attached code: "supplement/fairseq-0.6.2_halfdim_gate⁩ ▸ ⁨fairseq⁩ ▸ ⁨models⁩ ▸transformer.py". The AC had made the following comments to the referees: "Whether the performance gain of Graph-Transformer over Transformer is due to the MoG explanation is highly unclear. There is no direct evidence, such as appropriate visualization, to support that. In a high-level description, instead of using a usual skip connection that would combine beforex and x, the actual implementation is to 1) define increamental_x = x - beforex, 2) let increamental_x attend on beforex to produce x1, let beforex attend on increamental_x to produce x2, and let increamental_x attend on increamental_x to produce x3, 3) combine beforex, x1, x2, x3 in a certain way to produce the layer output."

Reviewer 2 responded to the AC's concern: "After examining the transformer.py and Section 2 & 3, we cannot understand why the output of self-attentions could be regarded as MoG subgraphs? The authors did not explain the connection. In their code, the graph transformer seems to just utilize 3 multi-head attentions (line 539-541) in their encoder. Using MoG to interpret the outputs of three attentions (line 539-541) is not very convincing. The link is weak. We agree with your comments."

To summarize, the link between the actual implementation in the code and all the MoG explanations is quite weak, and the technical novelty of the actual implementation is not strong enough for an ICLR publication. Therefore, the AC recommends Reject.





Decision: Reject