summaries: This paper studies a problem of graph translation, which aims at learning a graph translator to translate an input graph to a target graph. The authors propose an adversarial training framework to learn the graph translator, where a discriminator is trained to discriminate between the true target graph and the translated graph, and the translator is optimized by fooling the discriminator. The authors conduct experiments on both synthetic and real-world datasets. The results prove the effectiveness and the efficiency of the proposed approach over many baselines.

summaries: In this work the authors tackle the problem of generating a given graph to a target output graph.  To achieve this they develop a novel deep graph generative model. The authors place a lot of emphasis on scalability. This is indeed a major computational bottleneck in prior work, allowing the deep generative models to generate graphs with few tenths of nodes.   The authors propose an architecture that consists of a graph translator, and a conditional graph discriminator. The GAN approach is able to give significant insights into the conditional distribution p(G|H) where H is the input graph. For the graph translator, the authors design novel graph encoders and decoders. The proposed encoder-decoder achieve the best possible results, compared to using established encoder/decoders as shown in ablation study.  The authors analyze the computational complexity of their work, and while they do not discuss the computational complexities of the other methods, it is clear from the experiments that their method scales better (e.g., Figure 4). To evaluate the output of the architecture, they use a variety of different graph characteristics. The proposed method outperforms the state-of-the-art. Furthermore, the proposed method is able to detect interesting anomalies as illustrated in the appendix  (hacker detection).

abstractText: Deep graph generation models have achieved great successes recently, among which however, are typically unconditioned generative models that have no control over the target graphs given an input graph. In this paper, we propose a novel GraphTranslation-Generative-Adversarial-Networks (GT-GAN) that transforms the input graphs into their target output graphs. GT-GAN consists of a graph translator equipped with innovative graph convolution and deconvolution layers to learn the translation mapping considering both global and local features. A new conditional graph discriminator is proposed to classify the target graphs by conditioning on input graphs while training. Extensive experiments on multiple synthetic and realworld datasets demonstrate that our proposed GT-GAN significantly outperforms other baseline methods in terms of both effectiveness and scalability. For instance, GT-GAN performs at least 10 and 15 time faster than GraphRNN and RandomVAE, respectively, when the size of the graph is around 50.

authors:
James Atwood
Don Towsley

title: Diffusion-convolutional neural networks

authors:
James Atwood
Siddharth Pal
Don Towsley
Ananthram Swami

title: Sparse diffusion-convolutional neural networks

venue: In NIPS,

authors:
Yunsheng Bai
Hao Ding
Yang Qiao
Agustin Marinovic
Ken Gu
Ting Chen
Yizhou Sun
Wei Wang

title: Unsupervised inductive graph-level representation learning via graph-graph proximity

venue: International Joint Conferences on Artificial Intelligence,

authors:
Joost Bastings
Ivan Titov
Wilker Aziz
Diego Marcheggiani
Khalil Sima’an

title: Graph convolutional encoders for syntax-aware neural machine translation

venue: arXiv preprint arXiv:1704.04675,

authors:
Daniel Beck
Gholamreza Haffari
Trevor Cohn

title: Graph-to-sequence learning using gated graph neural networks

venue: arXiv preprint arXiv:1806.09835,

authors:
Aleksandar Bojchevski
Oleksandr Shchur
Daniel Zügner
Stephan Günnemann

title: Netgan: Generating graphs via random walks

venue: arXiv preprint arXiv:1803.00816,

authors:
Béla Bollobás
Christian Borgs
Jennifer Chayes
Oliver Riordan

title: Directed scale-free graphs

venue: In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms,

title: Power and centrality: A family of measures

venue: American journal of sociology,

authors:
Joan Bruna
Wojciech Zaremba
Arthur Szlam
Yann Lecun

title: Spectral networks and locally connected networks on graphs

venue: In International Conference on Learning Representations (ICLR2014),

authors:
Yu Chen
Lingfei Wu
Mohammed J Zaki

title: Reinforcement learning based graph-to-sequence model for natural question generation

venue: arXiv preprint arXiv:1908.04942,

authors:
Hanjun Dai
Yingtao Tian
Bo Dai
Steven Skiena
Le Song

title: Syntax-directed variational autoencoder for structured data

venue: arXiv preprint arXiv:1802.08786,

authors:
Michaël Defferrard
Xavier Bresson
Pierre Vandergheynst

title: Convolutional neural networks on graphs with fast localized spectral filtering

authors:
Kien Do
Truyen Tran
Svetha Venkatesh

title: Graph transformation policy network for chemical reaction prediction

venue: In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

title: Centrality in social networks conceptual clarification

venue: Social networks,

authors:
Yuyang Gao
Lingfei Wu
Houman Homayoun
Liang Zhao

title: Dyngraph2seq: Dynamic-graph-tosequence interpretable learning for health stage prediction in online health forums

authors:
Daniel Gildea
Giorgio Satta
Xiaochang Peng

title: Cache transition systems for graph parsing

venue: Computational Linguistics,

authors:
Justin Gilmer
Samuel S Schoenholz
Patrick F Riley
Oriol Vinyals
George E Dahl

title: Neural message passing for quantum chemistry

venue: arXiv preprint arXiv:1704.01212,

authors:
Marco Gori
Gabriele Monfardini
Franco Scarselli

title: A new model for learning in graph domains

venue: In Neural Networks,

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

authors:
Phillip Isola
Jun-Yan Zhu
Tinghui Zhou
Alexei A Efros

title: Image-to-image translation with conditional adversarial networks

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Wengong Jin
Regina Barzilay
Tommi Jaakkola

title: Junction tree variational autoencoder for molecular graph generation

venue: arXiv preprint arXiv:1802.04364,

authors:
Wengong Jin
Kevin Yang
Regina Barzilay
Tommi Jaakkola

title: Learning multimodal graph-tograph translation for molecular optimization

venue: arXiv preprint arXiv:1812.01070,

title: Global graph kernels using geometric embeddings

venue: In ICML 2014,

authors:
Thomas N Kipf
Max Welling

title: Variational graph auto-encoders

venue: arXiv preprint arXiv:1611.07308,

authors:
Thomas N. Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

venue: In International Conference on Learning Representations (ICLR),

authors:
Paul L Krapivsky
Sidney Redner

title: Organization of growing random networks

venue: Physical Review E,

authors:
Matt J Kusner
Brooks Paige
José Miguel Hernández-Lobato

title: Grammar variational autoencoder

venue: In International Conference on Machine Learning,

authors:
Yujia Li
Daniel Tarlow
Marc Brockschmidt
Richard Zemel

title: Gated graph sequence neural networks

venue: International Conference on Learning Representations,

authors:
Yujia Li
Oriol Vinyals
Chris Dyer
Razvan Pascanu
Peter Battaglia

title: Learning deep generative models of graphs

venue: arXiv preprint arXiv:1803.03324,

authors:
Mathias Niepert
Mohamed Ahmed
Konstantin Kutzkov

title: Learning convolutional neural networks for graphs

venue: In ICML,

authors:
Giannis Nikolentzos
Polykarpos Meladianos
Antoine Jean-Pierre Tixier
Konstantinos Skianis
Michalis Vazirgiannis

title: Kernel graph convolutional neural networks

venue: arXiv preprint arXiv:1710.10689,

authors:
Xiaochang Peng
Daniel Gildea
Giorgio Satta

title: Amr parsing with cache transition systems

venue: In Thirty-Second AAAI Conference on Artificial Intelligence,

authors:
Bidisha Samanta
Abir De
Niloy Ganguly
Manuel Gomez-Rodriguez

title: Designing random graph models using variational autoencoders with applications to chemical design

venue: arXiv preprint arXiv:1802.05283,

authors:
Franco Scarselli
Marco Gori
Ah Chung Tsoi
Markus Hagenbuchner
Gabriele Monfardini

title: The graph neural network model

venue: IEEE Transactions on Neural Networks,

authors:
Michael L Seltzer
Dong Yu
Yongqiang Wang

title: An investigation of deep neural networks for noise robust speech recognition

venue: In Acoustics, Speech and Signal Processing (ICASSP),

authors:
Nino Shervashidze
Pascal Schweitzer
Erik Jan van Leeuwen
Kurt Mehlhorn
Karsten M Borgwardt

title: Weisfeiler-lehman graph kernels

venue: Journal of Machine Learning Research,

authors:
Martin Simonovsky
Nikos Komodakis

title: Graphvae: Towards generation of small graphs using variational autoencoders

venue: arXiv preprint arXiv:1802.03480,

authors:
Linfeng Song
Yue Zhang
Zhiguo Wang
Daniel Gildea

title: A graph-to-sequence model for amr-to-text generation

venue: arXiv preprint arXiv:1805.02473,

authors:
Mingming Sun
Ping Li

title: Graph to graph: a topology aware approach for graph structures learning and generation

venue: In The 22nd International Conference on Artificial Intelligence and Statistics,

authors:
Petar Veličković
William Fedus
William L Hamilton
Pietro Liò
Yoshua Bengio
R Devon Hjelm

title: Deep graph infomax

venue: arXiv preprint arXiv:1809.10341,

authors:
Yuxuan Wang
Wanxiang Che
Jiang Guo
Ting Liu

title: A neural transition-based approach for semantic dependency graph parsing

authors:
Bo Wu
Yang Liu
Bo Lang
Lei Huang

title: Dgcnn: Disordered graph convolutional neural network based on the gaussian mixture model

authors:
Kun Xu
Lingfei Wu
Zhiguo Wang
Vadim Sheinin

title: Graph2seq: Graph to sequence learning with attention-based neural networks

venue: arXiv preprint arXiv:1804.00823,

authors:
Kun Xu
Lingfei Wu
Zhiguo Wang
Mo Yu
Liwei Chen
Vadim Sheinin

title: Exploiting rich syntactic information for semantic parsing with graph-to-sequence model

venue: arXiv preprint arXiv:1808.07624,

authors:
Jiaxuan You
Rex Ying
Xiang Ren
William Hamilton
Jure Leskovec

title: Graphrnn: Generating realistic graphs with deep auto-regressive models

heading: 1 INTRODUCTION

text:
In recent years, deep learning on graphs has seen a surge of interests, especially for graph representation and recognition tasks such as node-level classification (Li et al., 2016; Kipf & Welling, 2017; Veličković et al., 2017; Gilmer et al., 2017; Hamilton et al., 2017) and graph-level classification (Niepert et al., 2016; Atwood et al., 2016; Wu et al., 2017). Because of the successes in graph neural networks, researchers have recently started to explore the use of deep generative models for graph synthesis on practical applications such as designing new chemical molecular structures (Simonovsky & Komodakis, 2018; You et al., 2018). This has led to many of the recent advances in deep graph generative models where some of these approaches are domain dependent models (Kusner et al., 2017; Dai et al., 2018) for generating graphs with physical constrains, while some others consider the generation of generic graphs (Li et al., 2018; Samanta et al., 2018; Jin et al., 2018a).
However, there are two main drawbacks of existing deep graph generative models. First, one significant limitation of the previous approaches is that most of these models are only suitable for small graphs with 40 or fewer nodes, which is mainly due to their one-node-per-step generation manner. More importantly, most of the existing graph generation models are unconditioned and thus ignore rich input graph information for generating a new graph. In many applications, it is crucial to guide the graph generation process by conditioning on an input graph, which can be cast as a graph translation learning problem – translating the input graph to the output graph.
One straightforward way is to build a translation system by using a graph encoder-decoder architecture. However, there are several challenges for this type of approaches: 1) how to learn one-to-more mapping between the input graph and the target graphs. Different from the plain graph generation problem, a conditional graph synthesis task is to learn a distribution of target graphs conditioning on the input graph, which aims to capture the underlying implicit properties of the graphs, such as their scale-free characteristic. 2) how to jointly learn both local and global information for translation. One needs to not only learn the translation mapping in the local information (i.e. neighborhood pattern of each node), but also in the global property of the whole graph (e.g.,node degree distribution or graph density).
To address the aforementioned challenges, we present a novel neural network architecture – GraphTranslation-Generative-Adversarial-Nets (GT-GAN). We first propose a conditional graph GAN architecture that consists of an encoder-decoder translator and a conditional graph discriminator to learn the one-to-more mapping (a conditional distribution) for graph translation. To jointly embed
the local and global information, we present a novel graph encoder including both the edge and the node convolution layers. In addition, we further propose a novel graph U-net with graph skips and dedicated graph deconvolution layers including both the edge and the node deconvolution layers. Finally, GT-GAN is scalable with at most quadratic computation and memory consumption in terms of the number of nodes in a graph, making it suitable for at least modest-scale graphs (with hundreds of nodes, compared to the tens of nodes in most of existing graph generative models).
We highlight our main contributions as follows:
• We develop a generic framework GT-GAN consisting of a novel graph translator and conditional graph discriminator for learning a conditional distribution of target graphs given the input graphs.
• We propose a novel graph encoder consisting of “edge convolution” layers that extract various relations among nodes containing both local and global information, and “node convolution” layers that embed the node representations based on the extracted relations.
• We propose a novel graph decoder consisting of the “edge deconvolution” and “node deconvolution” layers, which can decode the node representations first into the latent relations of the target graph and then generate the final target graph. The graph skip-connection is also utilized to map the learned latent relations between the input and target graphs.
• Extensive experiments have been conducted on both synthetic and real-world datasets on eight performance metrics to demonstrate the effectiveness and efficiency of the proposed model.

heading: 2 RELATED WORKS

text:
Graph Neural Networks. The recent surge of research into GNN (Graph Neural Networks) can be generally divided into two categories: Graph Recurrent Networks and Graph Convolutional Networks. Graph Recurrent Networks originate from early work by Gori et al. (2005); Scarselli et al. (2009) and are based on recursive neural networks that have been extended by modern deep learning techniques such as gated recurrent units (Li et al., 2016). The other category, Graph Convolutional Networks, originate from spectral graph convolutional neural networks (Bruna et al., 2014), which were then extended by Defferrard et al. (2016) using fast localized convolutions, and further approximated by an efficient architecture for a semi-supervised setting proposed by Kipf & Welling (2017). Selfattention mechanism and subgraph-level information are also explored later to further improve the representation power of learned node embeddings (Veličković et al., 2017; 2018; Bai et al., 2019).
Graph generation. Most of the existing GNN based graph generation for general graphs have been proposed in the last two years and are based on VAE (Simonovsky & Komodakis, 2018; Samanta et al., 2018) and generative adversarial nets (GANs) (Bojchevski et al., 2018), among others (Li et al., 2018; You et al., 2018). Most of these approaches generate nodes and edges sequentially to form a whole graph, leading to the issues of being sensitive to the generation order and very time-consuming for large graphs. Differently, GraphRNN (You et al., 2018) builds an autoregressive generative model on these sequences with LSTM model and has demonstrated its good scalability.
Data Translation involved Graphs. A variety of graph-to-sequence models have been proposed to cope with different tasks including machine translation (Beck et al., 2018; Bastings et al., 2017), semantic parsing (Xu et al., 2018a;b; Song et al., 2018), and question generation (Chen et al., 2019), and health status prediction (Gao et al., 2019). The sequence-to-graph algorithms are generally popular with those working on NLP methods, including generating dependency graphs (Gildea et al., 2018; Wang et al., 2018) and AMR structures (Peng et al., 2018). A few of very recent attempts have also been made to develop graph-to-graph translation models. Jin et al. (2018b) proposed a domain-specific graph translation model to deal with molecular optimization task by utilizing the domain knowledge - junction tree and molecule graph. Do et al. (2019) dealt with the chemical reaction product prediction problem by predicting the reaction sequences based on the input graph of molecules. Sun & Li (2019) proposed a RNN based model for encoding and decoding the directed acyclic graph (converted from regular graphs), which can be viewed as a contemporary work to our work. However, this method is trained following the encoder-decoder architecture but in a supervised setting instead of learning a distribution of graphs. More importantly, it is difficult to scale to even modest-scale graph due to its one-node-per-step generation manner.

heading: 3 THE OVERALL ARCHITECTURE OF GT-GAN

text: In this section, we first present our problem formulation of graph translation problem. We then propose our new GT-GAN model for graph translation and discuss each component in detail in the subsequent sections.

heading: 3.1 PROBLEM FORMULATION FOR DEEP GRAPH TRANSLATION

text:
Our goal is to learn an end-to-end translation mapping from an input graph to a target graph. Let an input graph GX = (V, E , A, S) such that V is the set of N nodes, E ⊆ V × V is the set of edges, and A ∈ RN×N is an adjacency matrix (binary or weighted), where GX can be weighted or unweighted, directed or undirected. Let S ∈ RN×F be a node feature matrix with each row representing a node feature vector Si. Denote ei,j ∈ E as an edge from the node vi ∈ V to vj ∈ V; Ai,j ∈ A therefore denotes the corresponding weight of the edge ei,j . Similarly, we define a target graph GY = (V ′, E ′, A′, S′) that shares the same node sets and node features with GX but with different topology and connection weights. Formally, graph translation is to learn a translator from an input graph GX ∈ GX with a random noise U to generate a target graph GY ∈ GY , where GX and GY denote the domains of the input and target graphs, respectively. The translation mapping is denoted as T : U,GX → GY . Note that since our aim is to learn a conditional distribution of the target graphs given an input graph, we can cast the graph translation as a conditional graph generation problem, where an input graph can be mapped into any target graph that may have different topologies yet follow the same distribution. In contrast, the graph generation, that are designed to learn a distribution of graphs and generate a new graph sample based on this distribution, typically uses variational autoencoder framework for graph generation. Therefore, the previous graph generation frameworks such as graphVAE (Simonovsky & Komodakis, 2018) and GraphRNN (You et al., 2018) do not directly fit into "translation" setting.
The Proposed GT-GAN Framework. Fig.1 shows our proposed generic GAN framework for graph translation that consists of a graph translator T and a conditional graph discriminator D. In this figure we assume the node feature has only one dimension for simplicity. Since our task is to train a conditional generator with “one-to-many mapping" instead of a deterministic one, the noise U is introduced by the dropout function (Seltzer et al., 2013) in each convolution and deconvolution layer, as shown (in green lines) in Fig.1. Our graph translator T is trained to produce target graphs that cannot be distinguished from “real” ones by our conditional graph discriminator D. Specifically, the generated target graph GY ′ = T (GX , U) cannot be distinguished from the real one, GY , based on the current input graph GX . T and D undergo an adversarial training process based on input and target graphs by solving the following the loss function:
L(T ,D) = EGX ,GY [logD(GY |GX)] + EGX ,U [log(1−D(T (GX , U)|GX))], (1)
where T tries to minimize this objective while an adversarial D tries to maximize it, i.e. T ∗ = arg minT maxD L(T ,D). We also mix the GAN loss with the L1 loss to enforce sparsity similarity, which is also found useful in image translation problem (Isola et al., 2017),
Ll1(T ) = EA,A′,U [‖A′ − T (GX , U)‖1], (2)
where T (GX , U) refers to the adjacent matrix of generated graph. The training process is a trade-off between Ll1 and L(T ,D), which jointly enforces T (GX , U) and GY to follow a similar, but not necessarily identical topological pattern. Specifically, Ll1 makes T (GX , U) share the same rough outline of sparsity pattern as GY , while L(T ,D) allows T (GX , U) to vary to some degree. Thus, the optimal objective T ∗ of the translator, which generates graphs that are as “real” as possible, is defined as:
T ∗ = arg min T max D L(T ,D) + Ll1(D), (3)
The graph translator T is an encoder-decoder architecture, where we propose a new graph encoder to obtain the node representations of the input graph and propose the graph deconvolution with skips to generate the target graph, as shown in Fig.1, which we elaborated in the followings sections.
3.2 GRAPH ENCODER
The graph encoder aims to learn the representations of nodes based on the node features and graph topology of the input graph. One of crucial challenges is to learn both local and global information in the graph embedding. For instance, when learning translation between two scale-free graphs, one needs to translate both the local information (i.e. n-hop neighborhood of each node) and the scale-free property (i.e. node degree distributions of whole graph) from an input graph to a target graph.
The Proposed Graph Convolution. To learn the local information, the proposed encoder learns each node representation based on its n-hop neighbors. To learn the global information, it learns each node representation by looking for more “virtual neighbors”
regarding the latent relations from the aspect of the whole graph. As shown in Fig 2, though Node 1 and 2 are separated far away in the original network, they have the similarities in some properties, such as neighborhood structure and node degree. These nodes are treated as virtually connected ("virtual neighbors"). Thus, we first propose the “edge convolution” layers to learn a group of multimode relations from the topology of the input graph, which can include both the n-hop connections and the latent relations that are derived from their adjacent edges/relations. And then the “node convolution” layer is used to embed each node representations by aggregating its “virtual neighbors” that related to each latent relations. Fig.3 illustrates the details of these matrix operations involving graph convolution.
In each “edge convolution” layer, each node pair’s latent relation is computed by its adjacent edges or the extracted adjacent relations from the last layer. In the directed graph, each node has incoming edge(s) and out-going edge(s). Thus, there are two learnable parametric vectors φ and ψ as convolution filters for two directions to convolute the adjacent edges/relations for each node pairs. The relation El,mi,j in the mth relation mode of the lth layer is learned by the out-going edges/relations of node vi and the in-coming edges/relations of node vj ,
El,mi,j = ∑Rl−1
n=1 (σ( ∑N k1=1 El−1,ni,k1 φ l,m k1 ) + σ( ∑N k2=1 El−1,nk2,j ψ l,m k2 )) (4)
where E1,1i,j ≡ Ai,j and φl,m ∈ RN×1 refers to the filter vector to be learned and φ l,m k1 refers to the element of φl,m that is related to node vk1 . Rl−1 refers to the number of relation modes extracted for the (l − 1)th layer of the graph encoder. After learning the various modes of relations, the “node convolution“ layer learns each node’s representations by aggregating its “virtual neighbors” in terms of each mode of relation. The mth feature vector of node representation tensor H̄mi ∈ R1×F for node vi is computed as:
H̄mi = ∑Rl−1
n=1 (σ( ∑N k1=1 El−1,ni,k1 µ m k1Sk1) + σ( ∑N k2=1 El−1,nk2,i ν m k2Sk2)), (5)
where H̄i ∈ RRl×F and Rl refers to the number of feature vectors in the “node convolution” layer. Here µm, νm ∈ RN×1 refer to the filter vectors for the two directions to be learned and µmk1 refers to the element of µ
m that is related to node vk1 . H̄i is then flattened and transformed into a node representation vector Hi ∈ R1×C by a fully connected layer. C is the length of the node representation. Note that our graph encoder is designed for a directed graph, and it is easily generalized to an undirected graph, where the weight vector is shared by both directions.

heading: 3.3 GRAPH DECODER

text:
The decoder aims to generate the edges of the target graph by taking the extracted latent information of the input graph. It is straightforward to directly use the embedded node representation of the last layer to generate the target graph. However, the extracted information from each layer in the encoder could also be useful for generating the target graph. Thus, we consider all possible information learned in the encoder to be fed into a graph decoder.
Motivated by these observations, we propose a graph U-Net consisting of graph skips and dedicated graph deconvolution layers. The graph deconvolution decodes the single node (or edge) information to yield its incoming and outgoing adjacent edges as a mirrored graph convolution process. In addition, several skips are implemented to map the learned information of each layer in the encoder to mirror the corresponding layers in the decoder. Similar Graph U-Net was proposed in (Gao & Ji, 2019). The key difference is that their U-Net is barely a graph embedding method by using the old graph topology from pooling part to embed nodes during unpooling part. However, our Graph U-Net can not only do node embedding in graph encoder but also generate the new graph’s topology in the graph decoder, which is necessary for the graph translation problem.
The proposed Graph Deconvolution. The proposed graph deconvolution technique incorporates both “node deconvolution” and “edge deconvolution” layers. First, the “node deconvolution” layer are used to generate the latent multi-mode relations of the target graph based on the learned latent node representations. As shown in Fig. 2(c), “node deconvolution” is a reversed process of the “node” convolution. Since each node has an influence to its relations connecting to other nodes. Then the relation E1,mi,j between node vi and node vj in the mth relation mode of the lth “node” deconvolution layer in the decoder can be computed as follows:
E1,mi,j = ∑C
n=1 (σ(Hni µ̄ m j ) + σ(H n j ν̄ m i )), (6)
where σ(Hni µ̄ m j ) means the deconvolution contribution of node vi to its relation with node vj made by the nth element of its node representations, and µ̄mj represents the element of the deconvolution filter vector µ̄m ∈ R1×N that is related to node vj . We can now recursively apply our proposed “edge deconvolution“ layer to decode the latent relation between each pair of nodes from the upper layer to those of lower layer. As a reversed way of “edge” convolution, the relation of each pair of nodes in the (l − 1)th layer can make contribution to generating itself and its adjacent relations in the lth layer, as shown in Fig. 2(d). Thus, the relation El,mi,j between node vi and node vj in the lth layer is computed as follows:
El,mi,j = ∑R′l−1
n=1 (σ(φ̄l,mj ∑N k1=1 El−1,ni,k1 ) + σ(ψ̄ l,m j ∑N k2=1 El−1,nk2,j )), (7)
where φ̄l,m ∑N
k1=1 El−1,ni,k1 is interpreted as the decoded contribution of node i to its relations with
node vj , and φ̄l,m refers to the element of deconvolution filter vector that is related to node vj . R′l−1 refers to the number of relation modes extracted by the (l − 1)th layer in the graph decoder. The output of the last “edge” deconvolution layer denotes the edges of the target graph.
Skips for graph deconvolution. Based on the graph deconvolution above, it is possible to utilize skips to link the extracted latent relation sets of each layers in the graph encoder with those in the graph decoder. Specifically, the output of the lth “edge deconvolution” layer with Rl channels in the decoder is concatenated with the output of the lth “edge convolution” layer with R′l channels in encoder to form joint Rl +R′l channels, which are then input into the (l + 1)th deconvolution layer.

heading: 3.4 CONDITIONAL GRAPH DISCRIMINATOR

text: The graph discriminator must distinguish between the “translated” target graph and the “real” ones based on the input graphs, as this helps to train the generator in an adversarial way. Technically, this requires the discriminator to accept two graphs simultaneously as inputs (a target graph and an input graph or a generated graph and an input graph), and classify the two graphs as either related or not. Thus, we propose a conditional graph discriminator (CGD) which leverages the same graph convolution layers in the translator for the graph classification, as shown in Fig.1. Specifically, the input and target graphs are both ingested by CGD and stacked into a N ×N × 2 tensor which can be considered a 2-channel input. After obtaining the node representations, the graph-level embedding is computed by summing these node embeddings. Finally, a softmax layer is implemented to distinguish the input graph-pair from the real graph or generated graph.

heading: 3.5 COMPUTATIONAL COMPLEXITY ANALYSIS

text: The graph encoder and decoder shares the same time complexity. Without loss of generality, we assume all the hidden layers have the same number of feature maps as M . P is the length of the fully connected layer in CGD. The worst-case total complexity of GT-GAN (i.e., the dense graph) is now O(9N2M2 + 3N2M2 +N2MP ), where the first, second, and third terms represent “edge convolutions”, “node convolutions”, and fully connected layers in the graph discriminator, respectively. Similarly, the total memory consumption for GT-GAN is O((9NM2 + 9N2M) + (3NM2 + 3NM) + (N2MP + P )). In practice, many graphs are likely be sparse, thus it further reduces the computational and memory cost to O(N) by using sparse matrix-vector operations (You et al., 2018), which paves the way toward modest scale graphs with hundreds or thousands of nodes, compared to most of existing graph generation methods, which often have O(N3) or even O(N4).

heading: 4 EXPERIMENT

text: This section reports the results of extensive experiments and ablation studies carried out to test the performance of GT-GAN on two synthetic and two real-world datasets. All experiments were conducted on a 64-bit machine with Nvidia GPU (GTX 1070,1683 MHz, 8 GB GDDR5). The code and data utilized are available at https://github.com/anonymous1025/Deep-Graph-Translation-.

heading: 4.1 DATASETS

text:
The experimental settings for each dataset were as follows. The rules for generating synthetic input-target graph pairs and the process of collecting the real-world graphs is provided in Appendix.
Two synthetic datasets: Two groups of synthetic datasets were used to validate the performance of the proposed GT-GAN: a scale-free graph dataset and a Poisson-random graph dataset. Each group has five subsets with different graph sizes (number of nodes): 10, 20, 50, 100 and 150. Each subset consists of 5000 input-target graph pairs; 2500 pairs were used for training and the remaining 2500 for testing.
User authentication datasets. The goal of this application was to forecast future potential malicious authentication graphs given the user’s normal authentication graph. Each user authentication graph is a directed weighted graph, where nodes represent computers and the weights of the edges represent the authentication activities at certain frequencies. There are 78 pairs of graphs (malicious and normal behavior) of graph size 50 and 315 pairs of graphs of graph size 300 from 97 users in two subsets. We performed a 2-fold cross-validations and 3-fold cross-validation, respectively, for the two subsets.
Internet of Things (IOT) datasets . This application focused IOT network malware confinement prediction (predicting optimal network operation given a compromised one). There are three subsets of graph pairs with different sizes (20, 40 and 60), where the nodes represent devices and the node attributes indicating the compromised status of the nodes. The weights of the edges represent the distance between two devices. There are 334 pairs of input (compromised IOT) and target graphs (optimal IOT) in each subset and each is divided into two parts for the 2-fold cross-validation.

heading: 4.2 BASELINE METHODS

text: We compare our GT-GAN against five state-of-the-art graph generation methods: 1) GraphRNN (You et al., 2018) is a new graph generation method based on sequential generation with the LSTM model; 2) GraphVAE (Simonovsky & Komodakis, 2018) is a probability-based graph generation method for small graphs; 3) GraphGMG (Li et al., 2018)is a framework based upon graph neural networks for small single graphs; 4) RandomVAE (Samanta et al., 2018) was described earlier; and 5) S-Generator is the part of our full model GT-GAN, which essentially is a graph translator with L1 loss but no discriminator. We propose this S-Generator model in order to evaluate the necessity of the proposed GT-GAN framework to learn the one-to-many mappings. All the comparison methods were trained on the malicious graphs without conditioning on the input graphs due to the models’ inherent capability limitations. The datasets were assigned to each comparison model for the experiment based on their scalability in terms of graph size.

heading: 4.3 EVALUATION RESULTS ON SYNTHETIC DATASETS

text:
Results for the synthetic datasets. To evaluate the similarity between the generated and real target graphs for scale-free dataset, we selected eight performance metrics: 1) two metrics are distances between generated and real graph in terms of Eigenvector centrality (En-dist) (Bonacich, 1987) and Closeness centrality (C-dist) (Freeman, 1978), where the lower the distance, the better the performance; 2) two metrics are similarity score based on the graph kernels of Weisfeiler Lehman kernel(wl-sim) (Shervashidze et al., 2011) and Lovasz Theta Kernel(lt-sim) (Johansson & et al, 2014), where the higher the score, the better the performance; 3) four metrics are used to evaluate the the node degree distribution correlation between the generated and real target graphs by: Jensen-Shannon distances (JS), the Hellinger Distance (HD), the Bhattacharyya Distance (BD) and the Wasserstein Distances (WD), where the lower the score, the better the performance.
As shown in table 1, our GT-GAN consistently outperforms all other baselines by a large margin, especially when the graph size becomes large (i.e.having the superiority of 34.6% than other methods when size is 150). The “Inf” entries represent distance over 1000. S-Generator is generally the second best methods in terms of these four evaluation metrics, highlighting the effectiveness of our proposed graph encoder and decoder.
To verify whether GT-GAN can indeed discover the underlying ground-truth translation rules between input-target pairs, we draw the node degree distribution curve for three pairs of generated and real target graphs by GT-GAN, as shown in Fig. 4. The curves of the generated graphs closely follow
the power-law rule and become even closer to the real graphs as the graph size increases, which is consistent with the findings in Table 1. This demonstrates that our GT-GAN model successfully learns the inherent properties of scale-free graphs during translation. Similar observations for the evaluation metrics (e.g. average degree, repository and density) of the Poisson random datasets and remaining scale-free subsets can be found in Appendixes B and C.

heading: 4.4 EVALUATION RESULTS ON REAL APPLICATION DATASETS

text:
Results for the user authentication datasets. For the real world dataset, we design an indirect evaluation metric inspired from a real-world classification problem: label imbalance issues. For example, we may want to build a classifier to determine whether an authentication graph of a user is malicious (positive) or normal (negative), but this user has few malicious records. For this difficult task, the graphs (i.e., malicious graphs) generated by GT-GAN, which has been trained on other users’ records, can be utilized as positive samples to train the classifier. Specifically, when evaluating, the test set is further split evenly into two subsets. The first subset is used to train a graph classifier, as proposed by Nikolentzos et al. (2017), using only the normal graphs plus the generated malicious graphs. The second subset, which contains both the normal and real malicious graphs can then be used to validate the trained classifier. In addition, a “gold standard” classifier trained on both normal and real malicious graphs acts as the “best-possible-performer” and is used to evaluate all the different generative models to judge how “real” the graphs they generate are. We refer readers to the detailed evaluations in Appendix E.
Table 2: User authentication datasets
Size Method P R AUC F1
50
RandomVAE 0.32 0.51 0.26 0.39 GraphRNN 0.34 0.36 0.50 0.36
S-Generator 0.72 0.61 0.74 0.66 GT-GAN 0.79 0.68 0.78 0.73 Gold Standard 0.97 0.97 0.97 0.97 300 S-Generator 0.77 0.58 0.62 0.66
GT-GAN 0.84 0.66 0.79 0.74 Gold Standard 0.98 0.96 0.97 0.97
Table 3: IOT datasets
Size Method R2 MSE P ACC
20 GraphRNN 0.16 1775.58 0.23 83.97% GraphVAE 0.39 2109.64 0.32 81.19% GT-GAN 0.67 370.91 0.85 92.00% 40 GraphRNN 0.44 1950.46 0.29 70.54% GraphVAE 0.73 2410.57 0.16 66.60% GT-GAN 0.69 408.50 0.86 93.94% 60 GraphRNN 0.52 1831.43 0.04 61.07% GraphVAE 0.00 2453.61 0.04 50.64% GT-GAN 0.62 566.88 0.80 94.63%
As shown in Table 2, classifiers trained by the graphs generated by GT-GAN can classify normal and hacked behaviors effectively with AUC above 0.78, which is well above the 0.5 obtained using a random model. GT-GAN significantly outperforms other methods by around 25%, 16%, 24.5% and 22.1%, respectively, on the four metrics: precision (P), recall (R), AUC and F1-score for the trained classifier. GT-GAN performs consistently better than other methods when the graph size rises from 50 to 300. In addition, GT-GAN clearly outperformed the S-Genertor in this evaluation setting. This confirms that using a translator alone to learn a deterministic output given an input graph is not sufficient to capture the generic distribution of the target graphs. In addition, the four direct evaluation mentioned above are also tested and the results can be found in Appendix C.
Results on IOT dataset. Table 3 compared the performance of GT-GAN and other comparison methods for the IOT dataset by examining the edges of the generated and real target graphs for four metrics: MSE (mean squared error), R2 (coefficient of determination score), Pearson Correlation (P) of adjacent matrix, and ACC (Accuray) for the correct existence of edges among all the pairs of nodes. The results show that GT-GAN performed almost the best for all the three subsets. GT-GAN got highest Pearson Correlation of around 0.8 for all three subsets compared to the other methods
which had Pearson Correlations below 0.4. Due to the L1-loss required to maintain the topology pattern similarity, GT-GAN also outperformed the comparison methods with around 8% ,26% and 40% superiority in ACC for the three subsets, respectively, and had the smallest MSE, at just one tenth of those achieved by comparison methods.

heading: 4.5 ABLATION STUDY ON THE GRAPH ENCODERS AND DECODER

text:
To further validate the superiority of the proposed graph convolution and deconvolution layers, an ablation experiment was conducted by replacing the encoder and decoder with node embedding and decoder methods normaly used. The graph encoder was replaced by the GCN (Kipf & Welling, 2017), DCNN (Atwood & Towsley, 2016) and Graph U-NET (Gao & Ji, 2019), both of which consider edge and node features for graph embedding. The graph decoder was replaced by the decoder in VGAE (Kipf & Welling, 2016). There were thus three method combinations for comparison.
Table. 4 shows the results of the ablation study of the proposed encoder and decoder on part of the scale-free (Scale), user authentication (Auth) and IOT datasets. There are two major findings here. First, the encoder of GT-GAN outperformed both the GCN- and DCNN- based encoders by a large margin on these datasets, especially for the real-world datasets, where the edges of the graphs can have a very complex meaning. For example, on Auth-I, GT-GAN performed 43%, 50%, 31%, and 38% better on average, when compared with the GCN and DCNN encoders in terms of precision, recall, AUC and F1-scores, respectively. Second, the proposed decoder in GT-GAN was deemed both effective and irreplaceable for graph generation. For example, on IOT-III, GT-GAN performed 6.97%, 45.00%, and 83.33% better than the decoder in VGAE in terms of ACC, P and R2, respectively, as well as a low MSE below 1000.

heading: 4.6 MODEL SCALABILITY ANALYSIS

text: We compare the scalability of GT-GAN against three graph generation methods as shown in Fig.5. Our GT-GAN model significantly outperforms other state-of-the-art baselines in terms of both computational time and memory consumption. As the graph size increases up to 50, both computational time and the memory consumption of the GT-GAN remains almost constant. In contrast, the runtime and memory consumption of RandomVAE and the runtime of GraphVAE increase super-linearly as the graph size increases, making it hard to scale even to a graph size of 50. Interestingly, the runtime and memory consumption of GraphRNN also increases only slightly as the graph size increases. However, our GT-GAN model achieves around ten times speedups while requiring almost half of memory, compared to GraphRNN, highlighting the strong linear complexity of GT-GAN in practice.

heading: 5 CONCLUSIONS

text: This paper focuses on a new problem: deep graph translation. To achieve this, we propose a novel GT-GAN which translates an input graph to a target graph. To learn both global and local mapping between graphs, a new graph encoder-decoder model have been proposed while preserving the graph patterns in various scales. Extensive experiments have been conducted on the synthetic and real-world dataset to compare with the state-of-the-art graph generation models. Experimental results show that our GT-GAN can discover the ground-truth translation rules, and significantly outperform other baselines in terms of both effectiveness and scalability. This paper opens a thread of research for deep graph translation in many practical applications.

heading: A MORE DESCRIPTIONS AND EXPERIMENTS FOR SCALE FREE DATASET

text:
Generation of graph pairs. Each input graph is generated as a directed scale-free network, whose degree distribution follows power-law property Bollobás et al. (2003). A node will be selected as target node with probability proportional to its in-degree, which will be linked to a new source node with probability of 0.41. Similarly, a node will be selected as source node with probability proportional to its out-degree, which will be linked to a new target node with probability of 0.54. Then, in the target graph, each weight between two connected nodes will be added by m, where m could be any value larger than 1. Thus, both input and target graphs are scale-free graphs.
Indirect evaluation and ablation study. Other than directly measuring the node degree distribution similarity between the generated and real target graphs, we also conduct an indirect evaluation as done for user authentication dataset. Table 5 shows the average results of graph classifiers: Precision, Recall, AUC, and F1-measure for different methods. For small graphs (e.g., nodes less then 10), the power-law property of scale-free networks is less obvious compared to the larger size graphs, which may explain why the tasks on smaller scalefree graphs are more difficult. However, when the sizes of graph increase, GT-GAN become more close to the performance of “Gold Standard” with average difference of 10%, 4%, 5% and 9% on F1 accordingly, and significantly outperforms other methods by large margin up to 51%, 35%, 10%, and 19% on F1, respectively.
Table 6 shows the ablation study on dataset of Scale-III and Scale-IV in both metric evaluation and indirect distribution evaluation.
Fig. 10 shows 18 examples of the node degree distribution curve in generated and real target graphs for scale free dataset from size 50 to 150.

heading: B DESCRIPTIONS AND EXPERIMENTS FOR POISSON RANDOM DATASET

text:
Generation for graph pairs. Each input graph is generated by Krapivsky & Redner (2001), which is a directed growing random network. Then for an input graph withE number of edges, we randomly add kE number of edges on it to form the target graph, where k follows the Poisson distribution with the mean of 5.
Experiment results. For Poisson random graphs, the distributions of k in the real target graphs and those generated graphs are compared. The mean of edge increasing ratio k for generated graphs by our GT-GAN is 3.6, compared
to the real value of 5, which implies that the GT-GAN generally is able to discover the underlying
increasing ratio between input and target graphs. More evaluation results (e.g. degree and repository) can be found in Appendix B. We draw the probability density curve of the proportion k. Fig. 6 shows the distribution of the k in graphs generated by GT-GAN and the real graphs. The distribution plot is drew based on 3000 samples. Both of the two distribution have main degree values in the range from 2 to 7, while there is difference in the max frequency due to the limit of the samples amount. However, it prove that the proposed GT-GAN do learn the distribution type of translation parameter k in this task.
Results for indirect evaluation on Poisson Random graphs are listed in Table 7. Though the Poisson random task is easier than scale-free graphs, the GT-GAN still outperforms others on AUC and F1, and its performance is highly close to the “Gold Standard”. Table 8 shows the distance measurement between generated graphs and real graphs in several metrics. For the metric "degree", we use Wasserstein distances to measure the distance of two degree distribution. For other metrics, we calculate the MSE between generated graphs and real graphs.

heading: C DESCRIPTION OF IOT DATASET

text: There are three sets of IoT nodes at different amount (20, 40 and 60) encompassing temperature sensors connected with Intel ATLASEDGE Board and Beagle Boards (BeagleBone Blue), communicating via Bluetooth protocol. Benign and malware activities are executed on these devices to generate the initial attacked networks as the input graphs. Benign activities include MiBench and SPEC2006, Linux system programs, and word processor. The real target graphs are generated by the classical malware confinement methods: stochastic controlling with malware detection.

heading: D MORE EXPERIMENTAL RESULTS FOR USER AUTHENTICATION GRAPH SET

text:
About Original Dataset This dataset includes the authentication activities of 97 users on their accessible computers and servers in an enterprise computer network (Kent, 2015). Each user account generates a log file recording the computer accessing history, which could be formulated as a directed weighted graph called authentication graph, where nodes represent computers and the directed edges weights represent the authentication activities with certain frequencies. This data set spans one calendar year of contiguous activity spanning 2012 and 2013. It originated from 33.9 billion raw event logs (1.4 terabytes compressed) collected across the LANL enterprise network of approximately 24,000 computers. Here we consider two sub dataset. First is the user log-on activity set. This data represents authentication events collected from individual Windows-based desktop computers, servers, and Active Directory servers. Another dataset presents specific events taken from the authentication data that present known red team compromise events, as we call malicious event. The red team data can used as ground truth of bad behavior which is different from normal user. Each graph can represent the log-on activity of one user in a time window. The event graphs are defined like this: The
node refers to the computers that are available to a user and the edge represents the log-on activity from one computer to another computer of the user.
Table 9: MSE of Graph properties measurements for user authentication dataset
Dataset Method Density Reciprocity Ave-Degree
Auth-I RandomVAE 0.0005 0.0000 6.4064 GraphRNN 0.0032 0.0000 2.7751 S-Generator 0.0244 0.0342 24.130 GCN+decoder 0.0006 0.0000 0.3510 DCNN+decoder 0.0000 0.0000 0.0137 Encoder+VGAE 1.1050 0.0000 0.1052 GT-GAN 0.0003 0.0000 0.0002 Auth-II S-Generator 0.0113 0.0010 8.6839 DCNN+decoder 0.0000 0.0000 0.0039 GT-GAN 0.0004 0.0000 0.0006
Direct evaluation of User authentication Graph Set. For the user authentication graphs, the real target graphs and those generated are compared under well-recognized graph metrics including degree of nodes, reciprocity, and density. We calculate the distance of degree distribution and Mean Sqaured Error (MSE) for reciprocity and density. Table 9 shows the mean square error of the generated graphs and real graphs for all users evaluated for both graph generation methods and ablation models.
Case Studies on the generated target graphs. Fig.7 shows the example of User 049 with regular activity graph, real malicious activity graph and malicious activity graph generated by our GT-GAN from left to right. Only those of edges with difference among them are drawn for legibility. It can be seen that, the hacker performed attacks on Computer 192, which has been successfully simulated by our GT-GAN. In addition, GT-GAN also correctly identified that the Computer 192 is the end node (i.e., with only incoming edges) in this attack. This is because GT-GAN can learn both the global hacking patterns (i.e., graph density, modularity) but also can learn local properties for specific nodes (i.e., computers). GT-GAN even successfully predicted that the hacker connect from Computers 0 and 1, with Computers 7 and 14 as false alarms. For User006 in Fig. 8, the red team attackers make more connections on Node 36 compared to user’s regular activity, as marked in red rectangle. GT-GAN leans how to choose the Node 36 and it generated more connections too in the Node 36.

heading: E APPENDIX E: FLOWCHART OF INDIRECT EVALUATION PROCESS

text: Fig. 9 shows the process of the indirect evaluation process for evaluating whether the generated and the real target graphs follow the same distribution.

heading: F ARCHITECTURE PARAMETER FOR GT-GAN MODEL

text:
Graph Translator: Given the graph size (number of nodes) N of a graph. The output feature map size of
each layer through graph generator can be expressed as: N ×N × 1→ N ×N × 5→ N ×N × 10→ N × 1× 10→ N ×N × 10→ N ×N × 5→ N ×N × 1 Discriminator: Given the graph size (number of nodes) N of a graph. The output feature map size of each layer through graph discriminator can be expressed as: N ×N × 1→ N ×N × 5→ N ×N × 10→ N × 1× 10→ 1× 1× 10 For the edge to edge layers, the size of two kernels in two directions are N × 1 and 1×N . For the node to edge layer, the kernel size is 1×N


summaries: The authors propose a variant of gating functions for recurrent neural networks and feed-forward layers of Transformer and apply it to variety of tasks including toy tasks such as sorting, tree traversal and more realistic tasks such as machine translation. The gating function is applied recursively for N number of steps and depth of recursion is learned softly in data-driven function. Authors show similar or slightly better performance of their approach when applied to LSTM and Transformer compared to vanilla LSTM and Transformer.

summaries: This paper proposes a neural sequence modelling unit called METAGROSS.  In principle, the aim of this unit is to introduce recursive parametrization of  gating functions, building on the gated RNN paradigm.  The authors motivate this work by arguing that while gated-RNNs tackle vanishing gradient problems and facilitate learning long-range dependencies in sequences, improvements can be made with respect to learning on hierarchically-structured data.  The authors propose a method to do so by also learning the depth of the parametrization, and claim that the inductive bias that emerges from this configuration is beneficial to learning such tasks.

abstractText: This paper proposes METAGROSS (Meta Gated Recursive Controller), a new neural sequence modeling unit. Our proposed unit is characterized by recursive parameterization of its gating functions, i.e., gating mechanisms of METAGROSS are controlled by instances of itself, which are repeatedly called in a recursive fashion. This can be interpreted as a form of meta-gating and recursively parameterizing a recurrent model. We postulate that our proposed inductive bias provides modeling benefits pertaining to learning with inherently hierarchically-structured sequence data (e.g., language, logical or music tasks). To this end, we conduct extensive experiments on recursive logic tasks (sorting, tree traversal, logical inference), sequential pixel-by-pixel classification, semantic parsing, code generation, machine translation and polyphonic music modeling, demonstrating the widespread utility of the proposed approach, i.e., achieving state-of-the-art (or close) performance on all tasks.

authors:
David Alvarez-Melis
Tommi S Jaakkola

title: Tree-structured decoding with doubly-recurrent neural networks. 2016

authors:
Dzmitry Bahdanau
Kyunghyun Cho
Yoshua Bengio

title: Neural machine translation by jointly learning to align and translate

venue: arXiv preprint arXiv:1409.0473,

authors:
Dzmitry Bahdanau
Philemon Brakel
Kelvin Xu
Anirudh Goyal
Ryan Lowe
Joelle Pineau
Aaron Courville
Yoshua Bengio

title: An actor-critic algorithm for sequence prediction

venue: arXiv preprint arXiv:1607.07086,

authors:
Shaojie Bai
J Zico Kolter
Vladlen Koltun

title: An empirical evaluation of generic convolutional and recurrent networks for sequence modeling

venue: arXiv preprint arXiv:1803.01271,

title: Trellis networks for sequence modeling

venue: arXiv preprint arXiv:1810.06682,

authors:
Nicolas Boulanger-Lewandowski
Yoshua Bengio
Pascal Vincent

title: Modeling temporal dependencies in high-dimensional sequences: Application to polyphonic music generation and transcription

venue: arXiv preprint arXiv:1206.6392,

authors:
Samuel R Bowman
Christopher Potts
Christopher D Manning

title: Recursive neural networks can learn logical semantics

venue: arXiv preprint arXiv:1406.1827,

authors:
Samuel R Bowman
Jon Gauthier
Abhinav Rastogi
Raghav Gupta
Christopher D Manning
Christopher Potts

title: A fast unified model for parsing and sentence understanding

venue: arXiv preprint arXiv:1603.06021,

authors:
Shiyu Chang
Yang Zhang
Wei Han
Mo Yu
Xiaoxiao Guo
Wei Tan
Xiaodong Cui
Michael Witbrock
Mark A Hasegawa-Johnson
Thomas S Huang

title: Dilated recurrent neural networks

venue: In Advances in Neural Information Processing Systems,

authors:
Kyunghyun Cho
Bart Van Merriënboer
Caglar Gulcehre
Dzmitry Bahdanau
Fethi Bougares
Holger Schwenk
Yoshua Bengio

title: Learning phrase representations using rnn encoder-decoder for statistical machine translation

venue: arXiv preprint arXiv:1406.1078,

authors:
Jihun Choi
Kang Min Yoo
Sang-goo Lee

title: Learning to compose task-specific tree structures

authors:
Junyoung Chung
Caglar Gulcehre
KyungHyun Cho
Yoshua Bengio

title: Empirical evaluation of gated recurrent neural networks on sequence modeling

venue: arXiv preprint arXiv:1412.3555,

authors:
Junyoung Chung
Sungjin Ahn
Yoshua Bengio

title: Hierarchical multiscale recurrent neural networks

venue: arXiv preprint arXiv:1609.01704,

authors:
Li Dong
Mirella Lapata

title: Language to logical form with neural attention

venue: arXiv preprint arXiv:1601.01280,

authors:
Chris Dyer
Adhiguna Kuncoro
Miguel Ballesteros
Noah A Smith

title: Recurrent neural network grammars

venue: arXiv preprint arXiv:1602.07776,

authors:
Salah El Hihi
Yoshua Bengio

title: Hierarchical recurrent neural networks for long-term dependencies

venue: In Advances in neural information processing systems,

authors:
Alex Graves
Greg Wayne
Ivo Danihelka

title: Neural turing machines

venue: arXiv preprint arXiv:1410.5401,

authors:
Danijar Hafner
Alexander Irpan
James Davidson
Nicolas Heess

title: Learning hierarchical information flow with recurrent neural modules

authors:
Serhii Havrylov
Germán Kruszewski
Armand Joulin

title: Cooperative learning of disjoint syntax and semantics

venue: arXiv preprint arXiv:1902.09393,

authors:
Tianyu He
Xu Tan
Yingce Xia
Di He
Tao Qin
Zhibo Chen
Tie-Yan Liu

title: Layer-wise coordination between encoder and decoder for neural machine translation

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Long short-term memory

venue: Neural computation,

authors:
Po-Sen Huang
Chong Wang
Sitao Huang
Dengyong Zhou
Li Deng

title: Towards neural phrasebased machine translation

venue: arXiv preprint arXiv:1706.05565,

authors:
Athul Paul Jacob
Zhouhan Lin
Alessandro Sordoni
Yoshua Bengio

title: Learning hierarchical structures on-the-fly with a recurrent-recursive model for sequences

venue: In Proceedings of The Third Workshop on Representation Learning for NLP,

authors:
Jan Koutnik
Klaus Greff
Faustino Gomez
Juergen Schmidhuber

title: A clockwork rnn

venue: arXiv preprint arXiv:1402.3511,

authors:
Tao Lei
Yu Zhang
Sida I Wang
Hui Dai
Yoav Artzi

title: Simple recurrent units for highly parallelizable recurrence

venue: In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,

authors:
Shuai Li
Wanqing Li
Chris Cook
Ce Zhu
Yanbo Gao

title: Independently recurrent neural network (indrnn): Building a longer and deeper rnn

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Zhuohan Li
Di He
Fei Tian
Wei Chen
Tao Qin
Liwei Wang
Tie-Yan Liu

title: Towards binaryvalued gates for robust lstm training

venue: arXiv preprint arXiv:1806.02988,

authors:
Wang Ling
Edward Grefenstette
Karl Moritz Hermann
Tomáš Kočiskỳ
Andrew Senior
Fumin Wang
Phil Blunsom

title: Latent predictor networks for code generation

venue: arXiv preprint arXiv:1603.06744,

authors:
Liyuan Liu
Haoming Jiang
Pengcheng He
Weizhu Chen
Xiaodong Liu
Jianfeng Gao
Jiawei Han

title: On the variance of the adaptive learning rate and beyond

authors:
Shujie Liu
Nan Yang
Mu Li
Ming Zhou

title: A recursive recurrent neural network for statistical machine translation

venue: In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),

authors:
Minh-Thang Luong
Christopher D Manning

title: Stanford neural machine translation systems for spoken language domains

title: lamtram: A toolkit for language and translation modeling using neural networks

authors:
Maxim Rabinovich
Mitchell Stern
Dan Klein

title: Abstract syntax networks for code generation and semantic parsing

venue: arXiv preprint arXiv:1704.07535,

authors:
Marc’Aurelio Ranzato
Sumit Chopra
Michael Auli
Wojciech Zaremba

title: Sequence level training with recurrent neural networks

venue: arXiv preprint arXiv:1511.06732,

authors:
Adam Santoro
Ryan Faulkner
David Raposo
Jack Rae
Mike Chrzanowski
Theophane Weber
Daan Wierstra
Oriol Vinyals
Razvan Pascanu
Timothy Lillicrap

title: Relational recurrent neural networks

title: Learning complex, extended sequences using the principle of history compression

venue: Neural Computation,

authors:
Yikang Shen
Zhouhan Lin
Chin-Wei Huang
Aaron Courville

title: Neural language modeling by jointly learning syntax and lexicon

authors:
Yikang Shen
Shawn Tan
Alessandro Sordoni
Aaron Courville

title: Ordered neurons: Integrating tree structures into recurrent neural networks

venue: arXiv preprint arXiv:1810.09536,

authors:
Richard Socher
Alex Perelygin
Jean Wu
Jason Chuang
Christopher D Manning
Andrew Ng
Christopher Potts

title: Recursive deep models for semantic compositionality over a sentiment treebank

venue: In Proceedings of the 2013 conference on empirical methods in natural language processing,

authors:
Kyungwoo Song
JoonHo Jang
Il-Chul Moon

title: Bivariate beta lstm

venue: arXiv preprint arXiv:1905.10521,

authors:
Ilya Sutskever
Oriol Vinyals
Quoc V Le

title: Sequence to sequence learning with neural networks. In Advances in neural information processing

authors:
Kai Sheng Tai
Richard Socher
Christopher D Manning

title: Improved semantic representations from tree-structured long short-term memory networks

venue: arXiv preprint arXiv:1503.00075,

authors:
Yi Tay
Anh Tuan Luu
Siu Cheung Hui

title: Recurrently controlled recurrent networks

authors:
Ke Tran
Arianna Bisazza
Christof Monz

title: Recurrent memory networks for language modeling

venue: arXiv preprint arXiv:1601.01272,

title: The importance of being recurrent for modeling hierarchical structure

venue: arXiv preprint arXiv:1803.03585,

authors:
Trieu H Trinh
Andrew M Dai
Minh-Thang Luong
Quoc V Le

title: Learning longer-term dependencies in rnns with auxiliary losses

venue: arXiv preprint arXiv:1803.00144,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Ashish Vaswani
Samy Bengio
Eugene Brevdo
Francois Chollet
Aidan N. Gomez
Stephan Gouws
Llion Jones
Łukasz Kaiser
Nal Kalchbrenner
Niki Parmar
Ryan Sepassi
Noam Shazeer
Jakob Uszkoreit

title: Tensor2tensor for neural machine

venue: translation. CoRR,

authors:
Yau-Shian Wang
Hung-Yi Lee
Yun-Nung Chen

title: Tree transformer: Integrating tree structures into self-attention

venue: arXiv preprint arXiv:1909.06639,

authors:
Yijun Wang
Yingce Xia
Li Zhao
Jiang Bian
Tao Qin
Guiquan Liu
Tie-Yan Liu

title: Dual transfer learning for neural machine translation with marginal distribution regularization

authors:
Pengcheng Yin
Graham Neubig

title: A syntactic neural model for general-purpose code generation

venue: arXiv preprint arXiv:1704.01696,

title: Tranx: A transition-based neural abstract syntax parser for semantic parsing and code generation

venue: arXiv preprint arXiv:1810.02720,

authors:
Dani Yogatama
Phil Blunsom
Chris Dyer
Edward Grefenstette
Wang Ling

title: Learning to compose words into sentences with reinforcement learning

venue: arXiv preprint arXiv:1611.09100,

heading: 1 INTRODUCTION

text:
Sequences are fundamentally native to the world we live in, i.e., language, logic, music and time are all well expressed in sequential form. To this end, the design of effective and powerful sequential inductive biases has far-reaching benefits across many applications. Across many of these domains, e.g., natural language processing or speech, the sequence encoder lives at the heart of many powerful state-of-the-art model architectures.
Models based on the notion of recurrence have enjoyed pervasive impact across many applications. In particular, the best recurrent models operate with gating functions that not only ameliorate vanishing gradient issues but also enjoy fine-grain control over temporal compositionality (Hochreiter & Schmidhuber, 1997; Cho et al., 2014). Specifically, these gating functions are typically static and trained via an alternate transformation over the original input.
In this paper, we propose a new sequence model that recursively parameterizes the recurrent unit. More concretely, the gating functions of our model are now parameterized repeatedly by instances of itself which imbues our model with the ability to reason deeply1 and recursively about certain inputs. To achieve the latter, we propose a soft dynamic recursion mechanism, which softly learns the depth of recursive parameterization at a per-token basis. Our formulation can be interpreted as a form of meta-gating since temporal compositionality is now being meta-controlled at various levels of abstractions.
Our proposed method, Meta Gated Recursive Controller Units (METAGROSS), marries the benefits of recursive reasoning with recurrent models. Notably, we postulate that this formulation brings about benefits pertaining to modeling data that is instrinsically hierarchical (recursive) in nature, e.g., natural language, music and logic, an increasingly prosperous and emerging area of research (Shen et al., 2018; Wang et al., 2019; Choi et al., 2018). While the notion of recursive neural networks is not new, our work is neither concerned with syntax-guided composition (Tai et al., 2015; Socher et al., 2013; Dyer et al., 2016) nor unsupervised grammar induction (Shen et al., 2017; Choi et al., 2018; Havrylov et al., 2019; Yogatama et al., 2016). Instead, our work is a propulsion on a different frontier, i.e., learning recursively parameterized models which bears a totally different meaning.
1This is meant literally.
Overall, the key contributions of this work are as follows:
• We propose a new sequence model. Our model is distinctly characterized by recursive parameterization of recurrent gates, i.e., compositional flow is controlled by instances of itself, á la repeatedly and recursively. We propose a soft dynamic recursion mechanism that dynamically and softly learns the recursive depth of the model at a token-level.
• We propose a non-autoregressive parallel variation of METAGROSS,that when equipped with the standard Transformer model (Vaswani et al., 2017), leads to gains in performance.
• We evaluate our proposed method on a potpourri of sequence modeling tasks, i.e., logical recursive tasks (sorting, tree traversal, logical inference), pixel-wise sequential image classification, semantic parsing, neural machine translation and polyphonic music modeling. METAGROSS achieves state-of-the-art performance (or close) on all tasks.

heading: 2 META GATED RECURSIVE CONTROLLERS (METAGROSS)

text:
This section introduces our proposed model. METAGROSS is fundamentally a recurrent model. Our proposed model accepts a sequence of vectors X ∈ R`×d as input. The main unit of the Metagross unit ht = Metagrossn(xt, ht−1) is defined as follows:
fnt = σs(αt Metagrossn+1(xt, ht−1) + (1− αt) FFn (xt, ht−1)) ont = σs(βt Metagrossn+1(xt, h n t−1) + (1− βt) FOn (xt, ht−1))
znt = σr(F Z n (xt, ht)) cnt = (1− ft) ht−1 + (ft) zt hnt = ot ct hnt = ht + xt
where σr is a nonlinear activation such as tanh. σs is the sigmoid activation function. In a nutshell, the Metagross unit recursively calls itself until a max depth L is hit. When n = L, ft and ot are parameterized by:
fLt = σs(F F L (xt, ht−1))
oLt = σs(F O L (xt, ht−1))
where fLt , o L t is the forget and output gate of METAGROSS at time step t while at the maximum depth L. We also include an optional residual connection hnt = ht + xt to facilitate gradient flow down the recursive parameterization of METAGROSS.

heading: 2.1 SOFT DYNAMIC RECURSION

text:
We propose learning the depth of recursion in a data-driven fashion. To learn αt, βt, we use the following:
αt = Fα(xt) and βt = Fβ(xt)
where F∗(xt) = Wxt + b is a simple linear transformation layer applied to sequence X across the temporal dimension. Intuitively, α, β control the extent of recursion, enabling a soft depth pertaining to the hierarchical parameterization. Alternatively, we may also consider a static variation where:
αt = Fα( ∑̀ t=0 xt) and βt = Fβ( ∑̀ t=0 xt)
where the same value of α, β is computed based on global information from the entire sequence. Note that this strictly cannot be used for autoregressive decoding. Finally, we note that it is also possible to assign α ∈ R, β ∈ R to be trainable scalar parameters.

heading: 2.2 LEVEL-WISE PARAMETERIZATION

text:
Intuitively, F ∗n∀∗ ∈ F,O,Z are level-wise parameters of METAGROSS. We parameterize Fn with either level-wise RNN units or simple linear transformations.
F ∗n(xt) = RNN ∗ n(xt, h n t−1) or F ∗ n(xt) =W ∗ nxt + b ∗ n
Overall, METAGROSS is agnostic to the choice of F ∗n(xt) and even the RNN unit. Note that for RNN, the hidden states are initialized with zero and each level uses a new initial hidden state.

heading: 2.3 PARALLEL NON-AUTOREGRESSIVE VARIATION

text:
We postulate that METAGROSS can also be useful as a non-autoregressive parallel model. This can be interpreted as a form of recursive feed-forward layer that is used in place of recurrent METAGROSS for speed benefits. In early experiments, we find this a useful enhancement to state-of-theart Transformer (Vaswani et al., 2017) models. The non-autoregressive variant of METAGROSS is written as follows:
fnt = σs(αt Metagrossn+1(xt) + (1− αt) FFn (xt)) ont = σs(βt Metagrossn+1(xt) + (1− βt) FOn (xt)) znt = σr(F Z n (xt)) hnt = (f n t xt) + (ot znt ) hnt = ht + xt
More concretely, we dispense with the reliance on the previous hidden state. This can be used in place of any position-wise feed-forward layer. In this case, note that F ∗n(xt) are typically positionwise functions as well.

heading: 3 EXPERIMENTS

text: We conduct experiments on a suite of diagnostic synthetic tasks and real world tasks.

heading: 3.1 LOGIC AND RECURSIVE TASKS

text:
We evaluate our model on three diagnostic logical tasks as follows:
• Task 1 (SORT SEQUENCES) - The input to the model is a sequence of integers. The correct output is the sorted sequence of integers. Since mapping sorted inputs to outputs can be implemented in a recursive fashion, we evaluate our model’s ability to better model recursively structured sequence data. Example input output pair would be 9, 1, 10, 5, 3→ 1, 3, 5, 9, 10. • Task 2 (TREE TRAVERSAL) - We construct a binary tree of maximum depth N . The goal
is to generate the postorder tree traversal given the inorder and preorder traversal of the tree. Note that this is known to arrive at only one unique solution. The constructed trees have random sparsity where we assign a probability p of growing the tree up to maximum
depth N . Hence, the trees can be of varying depths2. This requires inferring hierarchical structure and long-term reasoning across sequences. We concatenate the postorder and inorder sequences, delimiteted by a special token. We evaluate on n ∈ {3, 4, 5, 8, 10}. For n = {5, 8}, we ensure that each tree traversal has at least 10 tokens. For n = 10, we ensure that each path has at least 15 tokens. Example input output pair would be 13, 15, 4, 7, 5, X, 13, 4, 15, 5, 7→ 7, 15, 13, 4, 5.
• Task 3 (LOGICAL INFERENCE) - We use the standard logical inference dataset3 proposed in (Bowman et al., 2014). This is a classification task in which the goal is to determine the semantic equivalence of two statements expressed with logic operators such as not, and, and or. The language vocabulary is of six words and three logic operators. As per prior work (Shen et al., 2018), the model is trained on sequences with 6 or less operations and evaluated on sequences of 6 to 12 operations.
For Task 1 and Task 2, we frame these tasks as a Seq2Seq (Sutskever et al., 2014) task and evaluate models on exact match accuracy and perplexity (P) metrics. We use a standard encoder-decoder architecture with attention (Bahdanau et al., 2014). We vary the encoder module with BiLSTMs, Stacked BiLSTMs (3 layers) and Ordered Neuron LSTMs (Shen et al., 2018). For Task 3 (logical inference), we use the common setting in other published works.
Results on Sorting and Tree Traversal Table 1 reports our results on the Sorting and Tree Traversal task. All models solve the task with n = 3. However, the task gets increasingly harder with a greater maximum possible length and largely still remains a challenge for neural models today. The relative performance of METAGROSS is on a whole better than any of the baselines, especially pertaining to perplexity. We also found that S-BiLSTMs are always better than LSTMs on this task and Ordered LSTMs are slightly worst than vanilla BiLSTMs. However, on sorting, ON-LSTMs are much better than standard BiLSTMs and S-BiLSTMs.
# Operations Model 7 8 9 10 11 12 Tree-LSTM† (Tai et al., 2015) 93 90 87 89 86 87 LSTM (Bowman et al., 2014) 88 85 80 78 71 69 RRNet (Jacob et al., 2018) 84 81 78 74 72 71 ON-LSTM (Shen et al., 2018) 91 87 86 81 78 76 METAGROSS 97 95 93 92 90 88
Table 2: Experimental results on Logical Inference task. † denotes models with access to ground truth syntax. Results reported from (Shen et al., 2018). METAGROSS achieves state-of-the-art performance.
Results on Logical Inference Table 2 reports our results on logical inference task. We compare with mainly other published work. METAGROSS is a strong and competitive model on this task, outperforming ON-LSTM by a wide margin (+12% on the longest nunber of operations). Performance of our model also exceeds Tree-LSTM, which has access to ground truth syntax. Our model achieves state-of-the-art performance on this dataset even when considering models with access to syntactic information.
2Note that all our models solves the problem entirely when the tree is fixed and full. Hence, random trees provide a necessary challenge.
33https://github.com/sleepinyourhat/vector-entailment.

heading: 3.2 PIXEL-WISE SEQUENTIAL IMAGE CLASSIFICATION

text:
We evaluate our model on its ability to model and capture long-range dependencies. More specifically, the sequential pixel-wise image classification problem treats pixels in images as sequences. We use the well-established pixel-wise MNIST and CIFAR-10 datasets. We use 3 layered METAGROSS of 128 hidden units each.
Model |θ| MNIST CIFAR DilatedGRU (Chang et al., 2017) - 99.00 - IndRNN (Li et al., 2018a) - 99.00 - r-LSTM (Trinh et al., 2018) - 98.52 72.20 Transformer (Trinh et al., 2018) - 98.90 62.20 TrellisNet (Bai et al., 2018b) 8.0M 99.20 73.42 TrellisNet (Our run) 8.0M 97.59 55.83 METAGROSS 0.9M 99.04 73.01 METAGROSS] 0.9M 99.09 73.95

heading: 3.3 SEMANTIC PARSING / CODE GENERATION

text:
We evaluate METAGROSS on semantic parsing (GEO, ATIS, JOBS) and code generation (DJANGO). We run our experiments on the publicly released code4 of (Yin & Neubig, 2018), replacing the recurrent decoder with our METAGROSS decoder. Hyperparameter details followed the codebase of (Yin & Neubig, 2018) quite strictly.
the ablative benefits of METAGROSS.

heading: 3.4 NEURAL MACHINE TRANSLATION

text:
We conduct experiments on two IWSLT datasets which are collections derived from TED talks. Specifically, we compare on the IWSLT 2014 German-English and IWSLT 2015 EnglishVietnamese datasets. We compare against a suite of published results and strong baselines. For our method, we replaced the multi-head aggregation layer in the Transformer networks (Vaswani et al., 2017) with a parallel non-autoregressive adaptation of METAGROSS. The base models are all linear layers. For our experiments, we use the standard implementation and hyperparameters in Tensor2Tensor5 (Vaswani et al., 2018), using the small (S) and base (B) setting for Transformers. Model averaging is used and beam size of 8/4 and length penalty of 0.6 is adopted for De-En and En-Vi respectively. For our model, max depth is tuned amongst {1, 2, 3}. We also ensure to compare, in an ablative fashion, our own reported runs of the base Transformer models.
4https://github.com/pcyin/tranX 5https://github.com/tensorflow/tensor2tensor
Model BLEU (Luong & Manning, 2015) 23.30 Att-Seq2Seq (Bahdanau et al., 2014) 26.10 NPMT (Huang et al., 2017) 27.69 NPMT + LM (Huang et al., 2017) 28.07 Transformer B (Vaswani et al., 2017) 28.43 Transformer B + METAGROSS 30.81
Table 6: Experimental results on Neural Machine Translation on IWSLT 2015 En-Vi.
Results on Neural Machine Translation Table 5 reports results on IWSLT 2014 de-en task. Our proposed model performs very competitively (37.09 BLEU), outperforming many well-established baselines. Our results also show that equipping Transformer models with METAGROSS can also lead to improvements in performance. Notably there is a +0.69 BLEU improvement on Transformer Base and +0.42 BLEU improvement for Transformer Small. On the other hand, our method achieves 30.81 BLEU on the IWSLT 2015 En-Vi dataset, with +2.38 improvement in BLEU from the standard Transformer Base model.

heading: 3.5 POLYPHONIC MUSIC MODELING

text: We evaluate METAGROSS on the polyphonic music modeling. We use three well-established datasets, namely Nottingham, JSB Chorales and Piano Midi (Boulanger-Lewandowski et al., 2012). The input to the model are 88-bit sequences, each corresponding to the 88 keys of the piano. The task is evaluated on the Negative Log-likelihood (NLL). We compare with a wide range of published works (Chung et al., 2014; Bai et al., 2018a; Song et al., 2019)

heading: 3.6 ANALYSIS AND DISCUSSION

text: This section reports some analysis and discussion regarding the proposed model.

heading: 3.6.1 EFFECT OF MAXIMUM DEPTH AND BASE UNIT

text:
Table 8 reports some ablation studies on the semantic parsing and code generation tasks. We observe that the base unit and optimal maximum depth used is task dependent. For ATIS dataset, using the linear transform as the base unit performs the best. Conversely, the linear base unit performs worse than the recurrent base unit (LSTM) on the DJANGO dataset.
On a whole, we also observed this across other tasks, i.e., the base unit and maximum depth of METAGROSS is a critical choice for most tasks. Table 9 reports the optimal max depth N and best base unit for each task.

heading: 3.6.2 ANALYSIS OF SOFT DYNAMIC RECURSION

text:
Figure 6 illustrates the depth gate values on CIFAR and MNIST datasets. These values reflect the α and β values in METAGROSS, signifying how the parameter tree is being constructed during training. This is reflected as L and R in the figures representing left and right gates. Firstly, we observe that our model indeed builds data-specific parameterization of the network. This is denoted by how METAGROSS builds different6 trees for CIFAR and MNIST.
Figure 7: Dynamic Recursion on CIFAR.
recursion over time if necessary. We find that compelling.
0 50 100 150 200 250 Temporal
0.0
0.2
0.4
0.6
0.8
Ac tiv
at io
n
L R LL LR RL RR LLR LLL RRL RRR
Figure 8: Dynamic Recursion on Music.
6Though not depicted, we also found that the probability of each node expanding to children has low variance across batches in the same dataset.
The adaptive recursive depth is made more intriguing by observing how the recursive parameterization alters on CIFAR and Music datasets. From Figure 8 we observe that the structure of the network changes in a rhythmic fashion, in line with our intuition of musical data. When dealing with pixel information, the tree structure changes adaptively according to the more complex information processed by the network.

heading: 4 RELATED WORK

text:
The study of effective inductive biases for sequential representation learning has been a prosperous research direction. This has spurred on research across multiple fronts, starting from gated recurrent models (Hochreiter & Schmidhuber, 1997; Cho et al., 2014), convolution (Bai et al., 2018a) to the recently popular self-attention based models (Vaswani et al., 2017).
The intrinsic hierarchical structure native to many forms of sequences have long fascinated and inspired many researchers (Socher et al., 2013; Bowman et al., 2014; 2016; Dyer et al., 2016). The study of recursive networks, popularized by (Socher et al., 2013) has provided a foundation for learning syntax-guided composition in language processing research. Along the same vein, (Tai et al., 2015) proposed Tree-LSTMs which guide LSTM composition with grammar. Recent attempts have been made to learn this process without guidance nor syntax-based supervision (Choi et al., 2018; Shen et al., 2017; Havrylov et al., 2019; Yogatama et al., 2016). Ordered Neuron LSTMs (Shen et al., 2018) proposed structured gating mechanisms, imbuing the recurrent unit with a tree-structured inductive bias. (Tran et al., 2018) shows that recurrence is important for modeling hierarchical structure. Notably, learning hierachical representations across multiple time-scales (El Hihi & Bengio, 1996; Schmidhuber, 1992; Koutnik et al., 2014; Chung et al., 2016; Hafner et al., 2017) have also demonstrated reasonable success.
Learning an abstraction and controller over a base recurrent unit is also another compelling direction. First proposed by Fast Weights (Schmidhuber, 1992), several recent works explore this notion. HyperNetworks (Ha et al., 2016) learns to generate weights for another recurrent unit, i.e., a form of relaxed weight sharing. On the other hand, RCRN (Tay et al., 2018) explicitly parameterizes the gates of a RNN unit with other RNN units. Recent attempts to speed up the recurrent unit are also reminiscent of this particular notion (Bradbury et al., 2016; Lei et al., 2018).
The marriage of recursive and recurrent architectures is also notable. This direction is probably the closest relevance to our proposed method, although with vast differences. (Liu et al., 2014) proposed Recursive Recurrent Networks for machine translation which are concerned with the more traditional syntactic supervision concept of vanilla recursive nets. (Jacob et al., 2018) proposed RRNet, which learns hierarchical structures on the fly. RR-Net proposes to learn to split or merge nodes at each time step, which makes it reminiscent of (Choi et al., 2018; Shen et al., 2018). (AlvarezMelis & Jaakkola, 2016) proposed doubly recurrent decoders for tree-structured decoding. The core of their method is a depth and breath-wise recurrence which is similar to our model. However, METAGROSS is concerned with learning gating controllers which is different from the objective of decoding trees.
Our work combines the idea of external meta-controllers (Schmidhuber, 1992; Ha et al., 2016; Tay et al., 2018) with recursive architectures. In particular, our recursive parameterization is also a form of dynamic memory which gives our model improved expressiveness in similar spirit to memoryaugmented recurrent models (Santoro et al., 2018; Graves et al., 2014; Tran et al., 2016).

heading: 5 CONCLUSION

text: We proposed Meta Gated Recursive Controller Units (METAGROSS) a sequence model characterized by recursive parameterization of gating functions. Our proposed method achieves very promising and competitive results on a spectrum of benchmarks across multiple modalities (e.g., language, logic, music). We propose a non-autoregressive variation of METAGROSS, which allows simple drop-in enhancement to state-of-the-art Transformers. We study and visualise our network as it learns a dynamic recursive parameterization, shedding light on the expressiveness and flexibility to learn dynamic parameter structures depending on the data.