Title: LEARNING GRAPHICAL STATE TRANSITIONS

Abstract: Graph-structured data is important in modeling relationships between multiple entities, and can be used to represent states of the world as well as many data structures. Li et al. (2016) describe a model known as a Gated Graph Sequence Neural Network (GGS-NN) that produces sequences from graph-structured input. In this work I introduce the Gated Graph Transformer Neural Network (GGT-NN), an extension of GGS-NNs that uses graph-structured data as an intermediate representation. The model can learn to construct and modify graphs in sophisticated ways based on textual input, and also to use the graphs to produce a variety of outputs. For example, the model successfully learns to solve almost all of the bAbI tasks (Weston et al., 2016) , and also discovers the rules governing graphical formulations of a simple cellular automaton and a family of Turing machines.

1. INTRODUCTION:

Many different types of data can be formulated using a graph structure. One form of data that lends itself to a graphical representation is data involving relationships (edges) between entities (nodes). Abstract maps of places and paths between them also have a natural graph representation, where places are nodes and paths are edges. In addition, many data structures can be expressed in graphical form, including linked lists and binary trees.

Substantial research has been done on producing output when given graph-structured input (Kashima et al., 2003; Shervashidze et al., 2011; Perozzi et al., 2014; Bruna et al., 2013; Duvenaud et al., 2015) . Of particular relevance to this work are Graph Neural Networks (Gori et al., 2005; Scarselli et al., 2009) , or GNNs, which extend recursive neural networks by assigning states to each node in a graph based on the states of adjacent nodes. Recently Li et al. (2016) have modified GNNs to use gated state updates and to produce output sequences. The resulting networks, called GG-NNs and GGS-NNs, are successful at solving a variety of tasks with graph-structured input.

The current work further builds upon GG-NNs and GGS-NNs by allowing graph-structured intermediate representations, as well as graph-structured outputs. This is accomplished using a more flexible graph definition, along with a set of graph transformations which take a graph and other information as input and produce a modified version of the graph. This work also introduces the Gated Graph Transformer Neural Network model (GGT-NN), which combines these transformations with a recurrent input model to incrementally construct a graph given natural language input, and can either produce a final graph representing its current state, or use the graph to produce a natural language output.

Extending GG-NNs in this way opens up a wide variety of applications. Since many types of data can be naturally expressed as a graph, it is possible to train a GGT-NN model to manipulate a meaningful graphical internal state. In this paper I demonstrate the GGT-NN model on the bAbI task dataset, which contains a set of stories about the state of the world. By encoding this state as a graph and providing these graphs to the model at training time, a GGT-NN model can be trained to construct the correct graph from the input sentences and then answer questions based on this internal graph. I also demonstrate that this architecture can learn complex update rules by training it to model a simple 1D cellular automaton and arbitrary 4-state Turing machines. This requires the network to learn how to transform its internal state based on the rules of each task. On the left, the desired graph we wish to represent, in which there are 6 node types (shown as blue, purple, red, orange, green, and yellow) and two edge types (shown as blue/solid and red/dashed). Node 3 and the edge between nodes 6 and 7 have a low strength. On the right, depictions of the node and edge matrices: annotations, strengths, state, and connectivity correspond to x v , s v , h v , and C, respectively. Saturation represents the value in each cell, where white represents 0, and fully saturated represents 1. Note that each node's annotation only has a single nonzero entry, corresponding to each node having a single well-defined type, with the exception of node 3, which has an annotation that does not correspond to a single type. State vectors are shaded arbitrarily to indicate that they can store network-determined data. The edge connectivity matrix C is three dimensional, indicated by stacking the blue-edge cell on top of the red-edge cell for a given sourcedestination pair. Also notice the low strength for cell 3 in the strength vector and for the edge between node 6 and node 7 in the connectivity matrix.

2. BACKGROUND:

2.1 GRU Gated Recurrent Units (GRU) are a type of recurrent network cell introduced by Cho et al. (2014) .

Each unit uses a reset gate r and an update gate z, and updates according to

r (t) = σ W r x (t) + U r h (t-1) + b r z (t) = σ W z x (t) + U z h (t-1) + b z h (t) = φ Wx + U r (t) h (t-1) + b h (t) = z h (t-1) + (1 -z) h (t)

where σ is the logistic sigmoid function, φ is an activation function (here tanh is used), x (t) is the input vector at timestep t, h (t) is the hidden output vector at timestep t, and W, U, W r , U r , W z , U z , b, b r and b z are learned weights and biases. Note that denotes elementwise multiplication.

2.2. GG-NN AND GGS-NN:

The Gated Graph Neural Network (GG-NN) is a form of graphical neural network model described by Li et al. (2016) . In a GG-NN, a graph G = (V, E) consists of a set V of nodes v with unique values and a set E of directed edges e = (v, v ) ∈ V × V oriented from v to v . Each node has an annotation x v ∈ R N and a hidden state h v ∈ R D , and each edge has a type y e ∈ {1, • • • , M }.

GG-NNs operate by first initializing the state h v of each node to correspond to the annotation x v . Then, a series of propagation steps occur. In each step, information is transferred between nodes across the edges, and the types of edge determine what information is sent. Each node sums the input it receives from all adjacent nodes, and uses that to update its own internal state, in the same manner as a GRU cell. Finally, the states of all nodes are used either to create a graph-level aggregate output, or to classify each individual node.

GGS-NNs extend GG-NNs by performing a large number of propagation-output cycles. At each stage, two versions of the GG-NN propagation process are run. The first is used to predict an output for that timestep, and the second is used to update the annotations of the nodes for the next timestep. This allows GGS-NNs to predict a sequence of outputs from a single graph.

a) b) c) d) e)

Figure 2: Summary of the graph transformations. Input and output are represented as gray squares. a) Node addition (T add ), where the input is used by a recurrent network (white box) to produce new nodes, of varying annotations and strengths. b) Node state update (T h ), where each node receives input (dashed line) and updates its internal state. c) Edge update (T C ), where each existing edge (colored) and potential edge (dashed) is added or removed according to the input and states of the adjacent nodes (depicted as solid arrows meeting at circles on each edge). d) Propagation (T prop ), where nodes exchange information along the current edges, and update their states. e) Aggregation (T repr ), where a single representation is created using an attention mechanism, by summing information from all nodes weighted by relevance (with weights shown by saturation of arrows).

3. DIFFERENTIABLE GRAPH TRANSFORMATIONS:

In this section, I describe some modifications to the graph structure to make it fully differentiable, and then propose a set of transformations which can be applied to a graph structure in order to transform it. In particular, I redefine a graph G = (V, C) ∈ Γ as a set V of nodes v, and a connectivity matrix C ∈ R |V|×|V|×Y , where Y is the number of possible edge types. As before, each node has an annotation x v ∈ R N and a hidden state h v ∈ R D . However, there is an additional constraint that N j=1 x v,j = 1. One can then interpret x v,j as the level of belief that v should have type j out of N possible node types. Each node also has a strength s v ∈ [0, 1]. This represents the level of belief that node v should exist, where s v = 1 means the node exists, and s v = 0 indicates that the node should not exist and thus should be ignored.

Similarly, elements of C are constrained to the range [0, 1], and thus one can interpret C v,v ,y as the level of belief that there should be a directed edge of type y from v to v . (Note that it is possible for there to be edges of multiple types between the same two nodes v and v , i.e. it is possible for C v,v ,y = C v,v ,y = 1 where y = y .) Figure 1 shows the values of x v , s v , h v , and C corresponding to a particular graphical structure.

There are five classes of graph transformation: a) Node addition (T add ), which modifies a graph by adding new nodes and assigning them annotations x v and strengths s v based on an input vector. b) Node state update (T h ), which modifies the internal state of each node using an input vector (similar to a GRU update step). Optionally, different input can be given to nodes of each type, based on direct textual references to specific node types. This version is called a direct reference update (T h,direct ). c) Edge update (T C ), which modifies the edges between each pair of nodes based on the internal states of the two nodes and an external input vector. d) Propagation (T prop ), which allows nodes to trade information across the existing edges and then update their internal states based on the information received. e) Aggregation (T repr ), which uses an attention mechanism to select relevant nodes and then generates a graph-level output.

Each transformation has its own trainable parameters. Together, these transformations can be combined to process a graph in complex ways. An overview of these operations is shown in Figure 2 .

For details about the implementation of each of these transformations, see Appendix B.

4. GATED GRAPH TRANSFORMER NEURAL NETWORK (GGT-NN):

In this section I introduce the Gated Graph Transformer Neural Network (GGT-NN), which is constructed by combining a series of these transformations. Depending on the configuration of the transformations, a GGT-NN can take textual or graph-structured input, and produce textual or graph- structured output. Here I describe one particular GGT-NN configuration, designed to build and modify a graph based on a sequence of input sentences, and then produce an answer to a query.

EQUATION

When run, the model performs the following: For each sentence k, each word is converted to a one-hot vector w (k) l , and the sequence of words (of length L) is passed through a GRU layer to produce a sequence of partial-sentence representation vectors p (k) l . The full sentence representation vector i (k) is initialized to the last partial representation vector p (k) L . Furthermore, a direct-reference input matrix D (k) is set to the sum of partial representation vectors corresponding to the words that directly reference a node type, i.e.

D (k) n = l∈Rn p (k) l

where R n is the set of words in sentence k that directly refer to node type n. This acts like an attention mechanism, by accumulating the partial representation vectors for the words that directly reference each type, and masking out the vectors corresponding to other words.

Next, a series of graph transformations are applied, as depicted in Algorithm 1. Depending on the task, direct reference updates and per-sentence propagation can be enabled or disabled. The output function f output will depend on the specific type of answer desired. If the answer is a single word, f output can be a multilayer perceptron followed by a softmax operation. If the answer is a sequence of words, f output can use a recurrent network (such as a GRU) to produce a sequence of outputs. Note that transformations with different superscripts (T h and T query h , for instance) refer to similar transformations with different learned weights.

Since the processing of the input and all of the graph transformations are differentiable, at this point the network output can be compared with the correct output for that query and used to update the network parameters, including both the GRU parameters used when processing the input and the internal weights associated with each transformation.

4.1. SUPERVISION:

As with many supervised models, one can evaluate the loss based on the likelihood of producing an incorrect answer, and then minimize the loss by backpropagation. However, based on initial experiments, the model appeared to require additional supervision to extract meaningful graphstructured data. To provide this additional supervision, I found it beneficial to provide the correct graph at each timestep and train the network to produce that graph. This occurs in two stages, first when new nodes are proposed, and then when edges are adjusted. For the edge adjustment, the edge loss between a correct edge matrix C * and the computed edge matrix C is given by

L edge = -C * • ln(C) -(1 -C * ) • ln(1 -C).

The node adjustment is slightly more complex. Multiple nodes are added in each timestep, but the order of those nodes is arbitrary, and only their existence is important. Thus it should be possible for the network to determine the optimal ordering of the nodes. In fact, this is important because there is no guarantee that the nodes will be ordered consistently in the training data. Vinyals et al. (2016) demonstrate a simple method for training a network to output unordered sets: the network produces a sequence of outputs, and these outputs are compared with the closest order-ing of the training data, i.e., the ordering of the training data which would produce the smallest loss when compared with the network output. Vinyals et al. show that when using this method, the network arbitrarily chooses an ordering which may not be the optimal ordering for the task. However, in this case any ordering should be sufficient, and I found the arbitrary orderings selected in this way to work well in practice. In particular, letting s * π(v) and x * π(v) denote the correct strength and annotations of node v under ordering π, the loss becomes

L node = -max π |Vnew| v=|Vold|+1 s * π(v) ln(s v ) + (1 -s * π(v) ) ln(1 -s v ) + x * π(v) • ln(x v ).

At this point the correct values C * , s * π(v) and x * π(v) are substituted into the graph for further processing. Note that only the edges and the new nodes are replaced by the supervision. The hidden states of all existing nodes are propagated without adjustment.

4.2. OTHER TRANSFORMATION CONFIGURATIONS:

The structure described in Algorithm 1 is designed for question-answering tasks. However, due to the composability of the individual graph transformations, other configurations could be used to solve other tasks that operate on structured data.

For instance, if a task consists of tracking relationships between a fixed set of objects, one could construct a version of the model that does not use the new-nodes transformation (T add ), but instead only modifies edges. If the task was to extract information from an existing graph, a structure similar to the GGS-NNs could be built by using only the propagation and aggregation transformations. If the task was to construct a graph based on textual input, the query processing steps could be omitted, and instead the final graph could be returned for processing. And if information should be gathered from a sequence of graphs instead of from a single graph, the query processing steps could be modified to run in parallel on the full sequence of graphs and extract information from each graph. This last modification is demonstrated in Appendix D.

5. EXPERIMENTS:



5.1. BABI TASKS:

I evaluated the GGT-NN model on the bAbI tasks, a set of simple natural-language tasks, where each task is structured as a sequence of sentences followed by a query (Weston et al., 2016) . The generation procedure for the bAbI tasks includes a "Knowledge" object for each sentence, representing the current state of knowledge after that sentence. I exposed this knowledge object in graph format, and used this to train a GGT-NN in supervised mode. The knowledge object provides names for each node type, and direct reference was performed based on these names: if a word in the sentence matched a node type name, it was parsed as a direct reference to all nodes of that type. For details on this graphical format, see Appendix C.

5.1.1. ANALYSIS AND RESULTS:

I trained two versions of the GGT-NN model for each task: one with and one without direct reference. Tasks 3 and 5, which involve a complex temporal component, were trained with intermediate propagation, whereas all of the other tasks were not because the structure of the tasks made such complexity unnecessary. Most task models were configured to output a single word, but task 19 (pathfinding) used a GRU to output multiple words, and task 8 (listing) was configured to output a strength for each possible word to allow multiple words to be selected without having to consider ordering.

Results are shown in Tables 1 and 2 . The GGT-NN model was able to reach 95% accuracy in all but one of the tasks, and reached 100% accuracy in eleven of them (see Table 2 ). Additionally, for fourteen of the tasks, the model was able to reach 95% accuracy using 500 or fewer of the 1000 training examples (see Table 1 ).

The only task that the GGT-NN was unable to solve with 95% accuracy was task 17 (Positional Reasoning), for which the model was not able to attain a high accuracy. Task 17 has a larger number of possible entities than the other tasks: each entity consists of a color (chosen from five options) and a shape (chosen from four shapes), for a total of 20 unique entities that must be represented separately. Additionally, the stories are much shorter than those in other tasks (2 facts for each set of 8 questions). It is likely that these additional complexities caused the network performance to suffer.

For comparison, accuracy on the bAbI tasks is also included for a simple sequence-to-sequence LSTM model and for a variety of existing state-of-the-art approaches (see the GGT-NN model was trained with full graph information, and the MemNN model was trained with information on which sentences were relevant to the query. All other models were trained end-to-end without additional supervision.

Since the GGT-NN and MemNN models are both strongly supervised, it is interesting to note that each approach outperforms the other on a subset of the tasks. In particular, the GGT-NN model with direct reference attains a higher level of accuracy on the following tasks, with an improvement of 0.4-64% depending on the task: task 5 (0.4%), task 7 (15%), task 8 (9%), task 17 (0.5%), task 18 (2.9%), and task 19 (64%). This may indicate that a graphical representation is superior to a list of sentence memories for solving these tasks. On the other hand, the MemNN model outperforms the GGT-NN model (0.1-2.9% greater accuracy) on tasks 3, 4, 10, 12, 14, and 15.

Of particular interest is the performance on task 19, the pathfinding task, for which the GGT-NN model with direct reference performs better than all but one of the other models (DMN+), and shows a large improvement over the performance of the MemNN model. This is reasonable, since pathfinding is a task that is naturally suited to a graphical representation. The shortest path between two nodes can be easily found by sending information across all paths away from one of the nodes in a distributed fashion, which the GGT-NN model allows. Note that the preexisting GGS-NN model (discussed in Section 2.2) was also able to successfully learn the pathfinding task, but required the input to be preprocessed into graphical form even when evaluating the model, and thus could not be directly evaluated on the textual form of any of the bAbI tasks (Li et al., 2016) . The current results demonstrate that the proposed GGT-NN model is able to solve the pathfinding task when given textual input.

Similarly, both variants of the GGT-NN model show improvement over many other models on task 16, the induction task. Solving the induction task requires being able to infer relationships based on similarities between entities. (One example from this task: Lily is a swan. Lily is white. Bernhard is green. Greg is a swan. What color is Greg? A:white.) In a graphical setting, this can be done by following a sequence of edges (Greg → swan → Lily → white), and the performance of the GGT-NN model indicates that this task is particularly suited to such a representation.

In general, the GGT-NN model with direct reference performs better than the model without it. The model with direct reference reaches 95% accuracy on 19/20 of the bAbI tasks, while the model without direct reference reaches that level of accuracy on 9/20 of the tasks (see Table 2 ). Additionally, when compared to the direct-reference model, the model without direct reference requires more training examples in order to reach the accuracy threshold (see Table 1 ). This indicates that, although the model can be used without direct reference, adding direct reference greatly improves the training of the model.

5.2. RULE DISCOVERY TASKS:

To demonstrate the power of GGT-NN to model a wide variety of graph-based problems, I applied the GGT-NN to two additional tasks. In each task, a sequence of data structures were transformed into a graphical format, and the GGT-NN was tasked with predicting the data for the next timestep based on the current timestep. No additional information was provided as textual input; instead, the network was tasked with learning the rules governing the evolution of the graph structure over time.

5.2.1. CELLULAR AUTOMATON TASK:

The first task used was a 1-dimensional cellular automaton, specifically the binary cellular automaton known as Rule 30 (Wolfram, 2002) . Rule 30 acts on an infinite set of cells, each with a binary state (either 0 or 1). At each timestep, each cell deterministically changes state based on its previous state and the states of its neighbors. In particular, the update rules are Current neighborhood 111 110 101 100 011 010 001 000 Next value 0 0 0 1 1 1 1 0

Cell states can be converted into graphical format by treating the cells as a linked list. Each of the cells is represented by a node with edges connecting it to the cell's neighbors, and a value edge is used to indicate whether the cell is 0 or 1. This format is described in more detail in Appendix C.

5.2.2. TURING MACHINES:

The second task was simulating an arbitrary 2-symbol 4-state Turing machine. A Turing machine operates on an infinite tape of cells, each containing a symbol from a finite set of possible symbols. It has a head, which points at a particular cell and can read and write the symbol at that cell. It also has an internal state, from a finite set of states. At each timestep, based on the current state and the contents of the cell at the head, the machine writes a new symbol, changes the internal state, and can move the head left or right or leave it in place. The action of the machine depends on a finite set of rules, which specify the actions to take for each state-symbol combination. Note that the version of Turing machine used here has only 2 symbols, and requires that the initial contents of the tape be all 0 (the first symbol) except for finitely many 1s (the second symbol).

When converting a Turing machine to graphical format, the tape of the machine is modeled as a linked list of cells. Additionally, each state of the machine is denoted by a state node, and edges between these nodes encode the transition rules. There is also a head node, which connects both to the current cell and to the current state of the machine. See Appendix C for more details.

The GGT-NN model was trained on 1000 examples of the Rule 30 automaton with different initial states, each of which simulated 7 timesteps of the automaton, and 20,000 examples of Turing machines with different rules and initial tape contents, each of which simulated 6 timesteps of the Turing machine. Performance was then evaluated on 1000 new examples generated with the same format. The models were evaluated by picking the most likely graph generated by the model, and comparing it with the correct graph. The percent accuracy denotes the fraction of the examples for which these two graphs were identical at all timesteps. In addition to evaluating the performance on identical tasks, the generalization ability of the models was also assessed. The same trained models were evaluated on versions of the task with 20 and 30 timesteps of simulation.

Results are shown in Table 3 . The models successfully learned the assigned tasks, reaching high levels of accuracy for both tasks. Additionally, the models show the ability to generalize to large inputs, giving a perfect output in the majority of extended tasks. For visualization purposes, Figure 3 shows the model at various stages of training when evaluated starting with a single 1 cell.

6. COMPARISON WITH RELATED WORK:

Many methods have been proposed for combining neural networks with graphs. These methods generally require the input to the network to be in graphical format. For instance, GNNs and GGS-NNs take a graph as input, and propagate information between nodes according to the graph structure (Gori et al., 2005; Scarselli et al., 2009; Li et al., 2016) . Similarly, graph convolutional networks extract information from an existing graph structure by using approximations to spectral graph convolutions (Kipf & Welling, 2016) . These methods are similar to GGT-NNs in that they all store information in the nodes of a graph and use edges to determine how information flows. However, they all use a graph with fixed structure, and can only accept graphical data. The GGT-NN model, on the other hand, allows the graph structure to be built and modified based on unstructured input. Giles et al. (1992) describe a method for extracting a finite state machine from a trained recurrent neural network by quantizing the hidden states of the network, recording all possible state transitions, and using them to construct a minimal directed graph representing the state machine. This method, however, requires postprocessing of the network to extract the graph, and is limited to extracting graphs that represent state machines. Additionally, although the FSM extraction method described by Giles et al. (1992) and the GGT-NN model both produce graphs using neural networks, the goals are different: the FSM extraction method aims to learn a single graph that can classify sequences, whereas the GGT-NN model aims to learn a neural network that can manipulate graphs.

The lifted relational neural network (LRNN) is another approach to working with structured data (Sourek et al., 2015) . LRNNs require the input to be formatted as a combination of weighted predicate logic statements, encompassing both general rules and specific known facts. For each training example, the statements are used to construct a "ground neural network", with a connection pattern determined by the dependencies between the statements. LRNNs can learn to extract information by adjusting the weights of each statement, but require the rules to be composed by hand based on the task structure. Furthermore, unlike in GGT-NNs, a LRNN has no internal state associated with the objects it describes (which are instead represented by single neurons), and the relationships between objects cannot be constructed or modified by the network.

Multiple recent architectures have included differentiable internal states. Memory Networks, as described in Weston et al. (2014) , and the fully differentiable end-to-end memory networks, described in Sukhbaatar et al. (2015) , both utilize a differentiable long-term memory component, consisting of a set of memories that are produced by encoding the input sentences. To answer a query, an attention mechanism is used to select a subset of these memories, and the resulting memories are processed to produce the desired output. Differentiable Neural Computers (DNCs), described in Graves et al. (2016) , interact with a fixed-size memory using a set of read and write "heads", which can be moved within the memory either by searching for particular content or by following temporal "links of association" that track the order in which data was written.

Memory networks and DNCs share with the GGT-NN model the ability to iteratively construct an internal state based on textual input, and use that internal state to answer questions about the underlying structured data. However, in these models, the structure of the internal state is implicit: although the network can store and work with structured data, the actual memory consists of a set of vectors that cannot be easily interpreted, except by monitoring the network access patterns. The GGT-NN model, on the other hand, explicitly models the internal state as a graph with labeled nodes and edges. This allows the produced graph to be extracted, visualized, and potentially used in downstream applications that require graph-structured input.

Hierarchical Attentive Memory (HAM) is a memory-based architecture that consists of a binary tree built on top of an input sequence (Andrychowicz & Kurach, 2016) . A recurrent controller accesses the HAM module by performing a top-down search through the tree, at each stage choosing to attend to either the left or right subtrees. Once this process reaches a leaf, the value of the leaf is provided to the controller to use in predicting the next output, and this leaf's value can be updated with a new value. This architecture is especially suited toward sequence-based tasks, and has been shown to generalize to longer sequences very efficiently due to the tree structure. However, it is unclear whether a HAM module would work well with non-sequential structured data, since the tree structure is fixed by the network.

One advantage of the GGT-NN model over existing works is that it can process data in a distributed fashion. Each node independently processes its surroundings, which can be beneficial for complex tasks such as pathfinding on a graph. This is in contrast to memory networks, DNCs, and HAM modules, which are restricted to processing only a fixed number of locations in a given timestep.

On the other hand, the distributed nature of the GGT-NN model means that it is less time and space efficient than these other networks. Since every node can communicate with every other node, the time and space required to run a GGT-NN step scales quadratically with the size of the input. A DNC or memory network, on the other hand, either scales linearly (since it attends to all stored data or memories) or is constant (if restricted to a fixed-size memory), and a HAM module scales logarithmically (due to the tree structure).

7. CONCLUSION:

The results presented here show that GGT-NNs are able to successfully model a wide variety of tasks using graph-structured states and potentially could be useful in solving many other types of problems. The specific GGT-NN model described here can be used as-is for tasks consisting of a sequence of input sentences and graphs, optionally followed by a query. In addition, due to the modular nature of GGT-NNs, it is possible to reconfigure the order of the transformations to produce a model suitable for a different task.

The GGT-NN architecture has a few advantages over the architectures described in existing works.

In contrast to other approaches to working with structured data, GGT-NNs are designed to work with unstructured input, and are able to modify a graphical structure based on the input. And in contrast to memory networks or DNCs, the internal state of the network is explicitly graph structured, and complex computations can be distributed across the nodes of the graph.

One downside of the current model is that the time and space required to train the model increase very quickly as the complexity of the task increases, which limits the model's applicability. It would be very advantageous to develop optimizations that would allow the model to train faster and with smaller space requirements, such as using sparse edge connections, or only processing some subset of the nodes at each timestep. Another promising direction of future work is in reducing the level of supervision needed to obtain meaningful graphs, for example by combining a few examples that have full graph-level supervision with a larger set of examples that do not have graph-level information, or using additional regularization to enable the GGT-NN model to be trained without any graph information.

There are exciting potential uses for the GGT-NN model. One particularly interesting application would be using GGT-NNs to extract graph-structured information from unstructured textual descriptions. More generally, the graph transformations provided here may allow machine learning to interoperate more flexibly with other data sources and processes with structured inputs and outputs.

Published as a conference paper at ICLR 2017 In particular, the propagation section focuses on information sent and received by the first node only.

In that section the strengths of the edges in the connectivity matrix determine what information is sent to each of the other nodes. Light gray connections indicate the value zero, corresponding to situations where a given edge is not present.

APPENDIX B GRAPH TRANSFORMATION DETAILS:

In this section I describe in detail the implementations of each type of differentiable graph transformation.1 A diagram of the implementation of each transformation is shown in Figure 4 . Note that it is natural to think of these transformations as operating on a single graphical state, and each modifying the state in place. However, in the technical descriptions of these transformations, the operations will be described as functions that take in an old graph and produce a new one, similarly to unrolling a recurrent network over time.

B.1 NODE ADDITION:

The node addition transformation T add : Γ × R α → Γ takes as input a graph G and an input vector a ∈ R α , and produces a graph G with additional nodes. The annotation and strength of each new node is determined by a function

f add : R α × R β → R × R N × R β

, where α is the length of the input vector, β is the length of the internal state vector, and as before N is the number of node types.

The new nodes are then produced according to

EQUATION

starting with h 0 initialized to some learned initial state, and recurrently computing s v and x v for each new node, up to some maximum number of nodes. Based on initial experiments, I found that implementing f add as a GRU layer followed by 2 hidden tanh layers was effective, although other recurrent networks would likely be similarly effective. The node hidden states h v are initialized to zero. The recurrence should be computed as many times as the maximum number of nodes that might be produced. The recurrent function f add can learn to output s v = 0 for some nodes to create fewer nodes, if necessary.

Note that in order to use information from all of the existing nodes to produce the new nodes, the input to this transformation should include information provided by an aggregation transformation T repr , described in section B.5.

B.2 NODE STATE UPDATE:

The node state update transformation T h : Γ × R α → Γ takes as input a graph G and an input vector a ∈ R α , and produces a graph G with updated node states. This is accomplished by performing a GRU-style update for each node, where the input is a concatenation of a and that node's annotation vector x v and the state is the node's hidden state, according to

r v = σ (W r [a x v ] + U r h v + b r ) , z v = σ (W z [a x v ] + U z h v + b z ) , h v = tanh (W[a x v ] + U (r h v ) + b) , h v = z v h v + (1 -z v ) h v B.2.1 DIRECT REFERENCE UPDATE

For some tasks, performance can be improved by providing information to nodes of a particular type only. For instance, if the input is a sentence, and one word of that sentence directly refers to a node type (e.g., if nodes of type 1 represent Mary, and Mary appears in the sentence), it can be helpful to allow all nodes of type 1 to perform an update using this information. To accomplish this, T h can be modified to take node types into account. (This modification is denoted T h,direct .) Instead of a single vector a ∈ R α , the direct-reference transformation takes in A ∈ R N ×α , where A n ∈ R α is the input vector for nodes with type n. The update equations then become

a v = x v A r v = σ (W r [a v x v ] + U r h v + b r ) , z v = σ (W z [a v x v ] + U z h v + b z ) , h v = tanh (W[a v x v ] + U (r h v ) + b) , h v = z v h v + (1 -z v ) h v B.3 EDGE UPDATE

The edge update transformation T C : Γ × R α → Γ takes a graph G and an input vector a ∈ R α , and produces a graph G with updated edges. For each pair of nodes (v, v ), the update equations are

c v,v = f set (a, x v , h v , x v , h v ) r v,v = f reset (a, x v , h v , x v , h v ) C v,v = (1 -C v,v ) c v,v + C v,v (1 -r v,v ).

The functions f set , f reset : R α×2N ×2D → [0, 1] Y are implemented as neural networks. (In my experiments, I used a simple 2-layer fully connected network.) c v,v ,y gives the level of belief in [0, 1] that an edge from v to v of type y should be created if it does not exist, and r v,v ,y gives the level of belief in [0, 1] that an edge from v to v of type y should be removed if it does. Setting both to zero results in no change for that edge, and setting both to 1 toggles the edge state.

B.4 PROPAGATION:

The propagation transformation T prop : Γ → Γ takes a graph G = G (0) and runs a series of T propagation steps (as in GG-NN), returning the resulting graph G = G (T ) . The GG-NN propagation step is extended to handle node and edge strengths, as well as to allow more processing to occur to Published as a conference paper at ICLR 2017

In a few of the tasks, specific entities had multi-word representations. While this works for normal input, it makes it difficult to do direct reference, since direct reference is checked on an individual word level. These tasks were modified slightly so that the entities are referred to with single words (e.g. "red square" instead of "red square").

An example of a graph produced from the bAbI tasks is given in Figure 5 .

C.2 CELLULAR AUTOMATON:

The cellular automaton task was mapped to graphical format as follows: Nodes have 5 types: zero, one, init-cell, left-cell, and right-cell. Edges have 2 types: value, and next-r. There is always exactly one "zero" node and one "one" node, and all of the cell nodes form a linked list, with a "value" edge connecting to either zero or one, and a "next-r" edge pointing to the next cell to the right (or no edge for the rightmost cell).

At the start of each training example, there are 13 timesteps with input of the form "init X" where X is 0 or 1. These timesteps indicate the first 13 initial cells. Afterward, there are 7 "simulate" inputs. At each of these timesteps, one new left-cell node is added on the left, one new right-cell node is added on the right, and then all cells update their value according to the Rule 30 update rules.

An example of the graphical format for the cellular automaton task is given in Figure 6 .

C.3 TURING MACHINE:

For the Turing machine task, nodes were assigned to 8 types: state-A, state-B, state-C, state-D, head, cell, 0, and 1. Edges have 16 types: head-cell, next-left, head-state, value, and 12 types of the form rule-R-W-D, where R is the symbol read (0 or 1), W is the symbol written (0 or 1), and D is the direction to move afterward (Left, Right, or None). State nodes are connected with rule edges, which together specify the rules governing the Turing machine. Cell nodes are connected to adjacent cells with next-left edges, and to the symbol on the tape with value edges. Finally, the head node is connected to the current state with a head-state edge, and to the current cell of the head with a head-cell edge.

At the start of each training example, each of the rules for the Turing machine are given, in the form "rule state-X R W state-Y D". Next, the initial state is given in the format "start state-X", and the initial contents of the tape (of length 4) are given sequentially in the format "input symbol-X", with the position for the head to start marked by "input symbol-X head". Finally, there are 6 "run" inputs, after each of which the head node updates its edges and the cell at the head updates its value according to the rules of the Turing machine. If the head leaves the left or right of the tape, a new node is introduced there.

An example of the graphical format for the Turing machine task is given in Figure 7 .

APPENDIX D GRAPH SEQUENCE INPUT:

The model described in Section 4 conditions the output of the model on the final graph produced by the network. This is ideal when the graph represents all of the necessary knowledge for solving the task. However, it may also be desirable for each graph to represent a subset of knowledge corresponding to a particular time, and for the output to be based on the sequence of graphs produced. For instance, in the third bAbI task (which requires reasoning about the temporal sequence of events) each graph could represent the state of the word at that particular time, instead of representing the full sequence of events prior to that time. In Appendix C, section C.1, I describe a transformation to the tasks which allows all information to be contained in the graph. But this adds complexity to the graphical structure. If it were possible for the model to take into account the full sequence of graphs, instead of just the final one, we could maintain the simplicity of the graph transformation.

To this end, I present an extension of the GGT-NN model that can produce output using the full graphical sequence. In the extended model, the graphical output of the network after each input sentence is saved for later use. Then, when processing the query, the same set of query transformations are applied to every intermediate graph, producing a sequence of representation vectors h answer 1 , . . . , h answer K . These are then combined into a final summary representation vector h answer summary

:

The code for each transformation, and for the GGT-NN model itself, is available at https://github. com/hexahedria/gated-graph-transformer-network.

Figures and Tables:

Figure1: Diagram of the differentiable encoding of a graphical structure, as described in section 3. On the left, the desired graph we wish to represent, in which there are 6 node types (shown as blue, purple, red, orange, green, and yellow) and two edge types (shown as blue/solid and red/dashed). Node 3 and the edge between nodes 6 and 7 have a low strength. On the right, depictions of the node and edge matrices: annotations, strengths, state, and connectivity correspond to x v , s v , h v , and C, respectively. Saturation represents the value in each cell, where white represents 0, and fully saturated represents 1. Note that each node's annotation only has a single nonzero entry, corresponding to each node having a single well-defined type, with the exception of node 3, which has an annotation that does not correspond to a single type. State vectors are shaded arbitrarily to indicate that they can store network-determined data. The edge connectivity matrix C is three dimensional, indicated by stacking the blue-edge cell on top of the red-edge cell for a given sourcedestination pair. Also notice the low strength for cell 3 in the strength vector and for the edge between node 6 and node 7 in the connectivity matrix.

Figure 3: Visualization of network performance on the Rule 30 Automaton task. Top node (purple) represents zero, bottom node (blue) represents 1, and middle nodes (green, orange, and red) represent individual cells. Blue edges indicate adjacent cells, and gold edges indicate the value of each cell. Three timesteps occur between each row.

Figure 4: Diagram of the operations performed for each class of transformation. Graph state is shown in the format given by Figure 1. Input and output are shown as gray boxes. Black dots represent concatenation, and + and × represent addition and multiplication, respectively. 1 -# represents taking the input value and subtracting it from 1. Note that for simplicity, operations are only shown for single nodes or edges, although the operations act on all nodes and edges in parallel.In particular, the propagation section focuses on information sent and received by the first node only. In that section the strengths of the edges in the connectivity matrix determine what information is sent to each of the other nodes. Light gray connections indicate the value zero, corresponding to situations where a given edge is not present.

Figure 5: Diagram of one sample story from the bAbI dataset (Task 2), along with a graphical representation of the knowledge state after the italicized sentence.

Figure 6: Diagram of one example from the automaton task, along with a graphical representation of the automaton state after the fourth simulate command (italicized).

Figure 7: Diagram of an example from the Turing machine task, with a graphical representation of the machine state after the second run command (italicized).

Number of training examples needed before the GGT-NN model could attain ≤ 5% error on each of the bAbI tasks. Experiments were run with 50, 100, 250, 500, and 1000 examples. "GGT-NN + direct ref." denotes the performance of the model with direct reference, and "GGT-NN" denotes the performance of the model without direct reference. Dashes indicate that the model was unable to reach the desired accuracy with 1000 examples.

Table content: <table><tr><td/><td>Task</td><td/><td/><td>GGT-NN + direct ref</td><td>GGT-NN</td><td/><td/><td>Task</td><td/><td colspan="2">GGT-NN + direct ref</td><td>GGT-NN</td></tr><tr><td colspan="4">-Single Supporting Fact</td><td>100</td><td>1000</td><td/><td colspan="3">11 -Basic Coreference</td><td colspan="2">100</td><td>1000</td></tr><tr><td colspan="4">-Two Supporting Facts</td><td>250</td><td>-</td><td/><td colspan="2">12 -Conjunction</td><td/><td colspan="2">500</td><td>1000</td></tr><tr><td colspan="5">-Three Supporting Facts 1000</td><td>-</td><td/><td colspan="3">13 -Compound Coref.</td><td colspan="2">100</td><td>1000</td></tr><tr><td colspan="3">-Two Arg. Relations</td><td/><td colspan="2">1000 1000</td><td/><td colspan="3">14 -Time Reasoning</td><td colspan="2">1000</td><td>-</td></tr><tr><td colspan="4">-Three Arg. Relations</td><td>500</td><td>-</td><td/><td colspan="3">15 -Basic Deduction</td><td colspan="2">500</td><td>500</td></tr><tr><td colspan="3">-Yes/No Questions</td><td/><td>100</td><td>-</td><td/><td colspan="3">16 -Basic Induction</td><td colspan="2">100</td><td>500</td></tr><tr><td colspan="2">-Counting</td><td/><td/><td>250</td><td>-</td><td/><td colspan="4">17 -Positional Reasoning</td><td>-</td><td>-</td></tr><tr><td colspan="2">-Lists/Sets</td><td/><td/><td>250</td><td>1000</td><td/><td colspan="3">18 -Size Reasoning</td><td colspan="2">1000</td><td>-</td></tr><tr><td colspan="3">-Simple Negation</td><td/><td>250</td><td>-</td><td/><td colspan="2">19 -Path Finding</td><td/><td colspan="2">500</td><td>-</td></tr><tr><td colspan="4">-Indefinite Knowledge</td><td>1000</td><td>-</td><td/><td colspan="3">20 -Agent's Motivations</td><td colspan="2">250</td><td>250</td></tr><tr><td/><td/><td colspan="3">1,000 examples</td><td/><td/><td/><td colspan="3">10,000 examples</td><td/><td/></tr><tr><td>Task</td><td>GGT-NN + direct ref</td><td>GGT-NN</td><td>LSTM</td><td>MemNN</td><td>MemN2N</td><td>EntNet</td><td>NTM</td><td>D-NTM</td><td>MemN2N*</td><td>DNC</td><td>DMN+</td><td>EntNet</td></tr><tr><td/><td>0</td><td colspan="2">0.7 50.0</td><td>0</td><td>0</td><td colspan="2">0.7 31.5</td><td>4.4</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td/><td>0</td><td colspan="2">5.7 80.0</td><td>0</td><td colspan="4">8.3 56.4 54.5 27.5</td><td>0.3</td><td>0.4</td><td colspan="2">0.3 0.1</td></tr><tr><td/><td colspan="3">1.3 12.0 80.0</td><td colspan="5">0 40.3 69.7 43.9 71.3</td><td>2.1</td><td>1.8</td><td colspan="2">1.1 4.1</td></tr><tr><td/><td>1.2</td><td colspan="2">2.2 39.0</td><td>0</td><td>2.8</td><td>1.4</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td/><td colspan="3">1.6 10.9 30.0</td><td colspan="2">2.0 13.1</td><td>4.6</td><td>0.8</td><td>1.7</td><td>0.8</td><td>0.8</td><td colspan="2">0.5 0.3</td></tr><tr><td/><td>0</td><td colspan="2">7.7 52.0</td><td>0</td><td colspan="3">7.6 30.0 17.1</td><td>1.5</td><td>0.1</td><td>0</td><td colspan="2">0 0.2</td></tr><tr><td/><td>0</td><td colspan="6">5.6 51.0 15.0 17.3 22.3 17.8</td><td>6.0</td><td>2.0</td><td>0.6</td><td>2.4</td><td>0</td></tr><tr><td/><td>0</td><td colspan="2">3.3 55.0</td><td colspan="4">9.0 10.0 19.2 13.8</td><td>1.7</td><td>0.9</td><td>0.3</td><td colspan="2">0 0.5</td></tr><tr><td/><td colspan="3">0 11.6 36.0</td><td colspan="4">0 13.2 31.5 16.4</td><td>0.6</td><td>0.3</td><td>0.2</td><td colspan="2">0 0.1</td></tr><tr><td>10</td><td colspan="3">3.4 28.6 56.0</td><td colspan="5">2.0 15.1 15.6 16.6 19.8</td><td>0</td><td>0.2</td><td colspan="2">0 0.6</td></tr><tr><td>11</td><td>0</td><td colspan="2">0.2 28.0</td><td>0</td><td>0.9</td><td colspan="2">8.0 15.2</td><td>0</td><td>0</td><td>0</td><td colspan="2">0 0.3</td></tr><tr><td>12</td><td>0.1</td><td colspan="2">0.7 26.0</td><td>0</td><td>0.2</td><td>0.8</td><td>8.9</td><td>6.2</td><td>0</td><td>0</td><td>0.2</td><td>0</td></tr><tr><td>13</td><td>0</td><td>0.8</td><td>6.0</td><td>0</td><td>0.4</td><td>9.0</td><td>7.4</td><td>7.5</td><td>0</td><td>0</td><td colspan="2">0 1.3</td></tr><tr><td>14</td><td colspan="3">2.2 55.1 73.0</td><td>1.0</td><td colspan="4">1.7 62.9 24.2 17.5</td><td>0.2</td><td>0.4</td><td>0.2</td><td>0</td></tr><tr><td>15</td><td>0.9</td><td colspan="2">0 79.0</td><td>0</td><td colspan="3">0 57.8 47.0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>16</td><td>0</td><td colspan="2">0 77.0</td><td>0</td><td colspan="8">1.3 53.2 53.6 49.6 51.8 55.1 45.3 0.2</td></tr><tr><td>17</td><td colspan="7">34.5 48.0 49.0 35.0 51.0 46.4 25.5</td><td colspan="3">1.2 18.6 12.0</td><td colspan="2">4.2 0.5</td></tr><tr><td>18</td><td colspan="3">2.1 10.6 48.0</td><td colspan="2">5.0 11.1</td><td>8.8</td><td>2.2</td><td>0.2</td><td>5.3</td><td>0.8</td><td colspan="2">2.1 0.3</td></tr><tr><td>19</td><td colspan="6">0 70.6 92.0 64.0 82.8 90.4</td><td colspan="2">4.3 39.5</td><td>2.3</td><td>3.9</td><td colspan="2">0 2.3</td></tr><tr><td>20</td><td>0</td><td>1.0</td><td>9.0</td><td>0</td><td>0</td><td>2.6</td><td>1.5</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr></table>



Table content: <table/>

: a simple sequence-to-sequence LSTM model, as implemented inWeston et al. (2016), a modified Memory Network model(MemNN, Weston et al., 2016), End-To-End Memory Network (MemN2N,Sukhbaatar et al., 2015), Recurrent Entity Network (EntNet,Henaff et al., 2016), Neural Turing Machine (NTM,Graves et al., 2014), Dynamic NTM (D-NTM,Gulcehre et al., 2016), a larger version of the MemN2N model with weight tying and nonlinearity (MemN2N*,Sukhbaatar et al., 2015), Differentiable Neural Computer (DNC,Graves et al., 2016), and Dynamic Memory Network (DMN+,Xiong et al., 2016). Although the GGT-NN model was trained using only 1,000 training examples, results using 10,000 examples have also been reproduced here for comparison. Also, it is important to note that the GGT-NN and MemNN models were trained with strong supervision:

Table content: <table/>

Accuracy of GGT-NN on the Rule 30 Automaton and Turing Machine tasks.

Table content: <table><tr><td>1000 iterations</td><td>2000 iterations</td><td>3000 iterations</td><td>7000 iterations</td><td>Ground truth</td></tr></table>

Peer review (iclr2017):
The main contribution of this paper seems to be an introduction of a set of differential graph transformations which will allow you to learn graph->graph classification tasks using gradient descent. This maps naturally to a task of learning a cellular automaton represented as sequence of graphs. In that task, the graph of nodes grows at each iteration, with nodes pointing to neighbors and special nodes 0/1 representing the values. Proposed architecture allows one to learn this sequence of graphs, although in the experiment, this task (Rule 30) was far from solved. This idea is combined with ideas from previous papers (GGS-NN) to allow the model to produce textual output rather than graph output, and use graphs as intermediate representation, which allows it to beat state of the art on BaBi tasks.