Multi-level Community-awareness Graph Neural Networks for Neural Machine Translation (2022)

Abstract: Neural Machine Translation (NMT) aims to translate the source- to the target-language while preserving the original meaning. Linguistic information such as morphology, syntactic, and semantics shall be grasped in token embeddings to produce a high-quality translation. Recent works have leveraged the powerful Graph Neural Networks (GNNs) to encode such language knowledge into token embeddings. Specifically, they use a trained parser to construct semantic graphs given sentences and then apply GNNs. However, most semantic graphs are tree-shaped and too sparse for GNNs which cause the over-smoothing problem. To alleviate this problem, we propose a novel Multi-level Community-awareness Graph Neural Network (MC-GNN) layer to jointly model local and global relationships between words and their linguistic roles in multiple communities. Intuitively, the MC-GNN layer substitutes a self-attention layer at the encoder side of a transformer-based machine translation model. Extensive experiments on four language-pair datasets with common evaluation metrics show the remarkable improvements of our method while reducing the time complexity in very long sentences.

## introduction self-attention mechanisms, introduced by transformers @xcite , have been ubiquitous in neural machine translation (nmt). it encodes the relative information of a position based on other positions in the same sequence. recent works have seen the rising trend of improving the self-attention module such as @xcite . one of the serious self-attention weaknesses is its inefficiency at computing long sentences due to quadratic complexity. following this problem, performer @xcite estimates a full- * corresponding author rank-attention matrix with fast attention via positive orthogonal random features approach (fa-vor+), that trade-offs the time complexity from o(t 2 d) to o(t d 2 logd). however, as they scale the model larger such as @xcite , the quadratic dimensional space d exponentially scales much faster than that of the sequence length t . in addition, linear transformer @xcite reported a comparable performance with the transformer, while speeding up on autoregressive inference time with a linear dot-product of kernel feature maps. several studies replace self-attention with an attention-free module, which significantly speeds up the training time. attention free transformer (atf) @xcite eliminates the dot-product attention with weighted element-wise multiplication, which linearizes the time complexity to o(t d). fnet @xcite is a pre-trained model with discrete fourier transform that speeds up 80% training time on gpu but still achieves 92-97% of the accuracy of bert @xcite . these works make a trade-off between the accuracy and the performance to reduce the computational cost. another line of work constructs a content-based sparse graph to select keys that have high similarity meanings to queries. routing transformer @xcite applies k-means clustering to cluster both queries and keys. meanwhile, reformer (kitaev et al., 2020) uses locality-sensitive hashing (lsh) to select key-value pairs for each query. unlike previous work, in this paper, we follow the intuition that self-attention is assumption-free on the structural input, and thus it is hard to induce task-based generalization on small-scale data. as a result, we propose semantic-based sparse attention that utilizes the semantic graph construction of the universal conceptual cognitive annotation (ucca) @xcite parser, which is implemented based on message passing neural networks (mpnn). the vital benefit of ucca is that it is not relatively defined to a specific language, or in another word, it provides a universal structure across languages. we hypothesize that the translation task will benefit from this characteristic. according to @xcite , because ucca is a connected acyclic graph (or tree) whose in-degree node usually is one or two, the attention-based computation will smooth the token embeddings to a high similarity score. this problem is referred to as the over-smoothing problem, leading to the bad convergence when the mpnn model is trained deeper. to alleviate the issue, we introduce a set of transformation rules to convert the tree-based ucca into a community-centric graph (ccg). as illustrated in figure 1 , the ccg (on the right) presents two different communities that somehow discover local relationships between words and word roles in a community. moreover, we can theoretically prove that the ccg structure is stronger than the tree-based ucca (see section 3.2). to capture the global relationships across communities, we propose multi-level explorations (me) to probe multilevel structures in a graph. henceforth, we combine ccg and me into multi-level communityawareness graph neural networks (mc-gnn). this mc-gnn layer will substitute a self-attention layer in the transformer encoder. mc-gnn is theoretically faster than the transformer, thanks to the sparse attention. ## method in this section, we firstly provide notations and theory of community-awareness graph (ccg). we then provide the proof that ccg is stronger than tree graph. we next present details of mc-gnn, and finally explain how mc-gnn is incorporated into a nmt model. ## experiments we provide hyper-parameter settings, datasets, parser settings, and our code at https:// github.com/nqbinh17/mc-gnn . ## conclusion mc-gnn gains significant improvements across many translation tasks without changing the architecture, while parameters and the time complexity are reduced. however, there are several limitations in the proposed methods. first, the accuracy of the ucca parser is below 80%, which can cause some unexpected behaviors and hamper the nmt performance. second, mc-gnn does not support every language as self-attention, since the ucca parser is unavailable in every language. third, we experimented with the graph decoder where a tar-get sentence is treated as a dense graph and built incrementally during the decoding phase @xcite . although the time complexity of dense graphs and self-attention are o(t 2 d), dense graphs are sparse tensor computations, which is extremely memory inefficient and unparallelable. thus, we dropped this approach due to limited resources.