Gated Graph Sequence Neural Networks

Yujia LiDaniel TarlowMarc BrockschmidtRichard Zemel

article2015ICLR3,678 citations

Introduces Gated Graph Sequence Neural Networks, modernizing graph neural architectures with gated recurrent units to learn representations and generate sequential outputs across graph-structured tasks such as program verification.

Listen

The paper introduces Gated Graph Sequence Neural Networks, a neural network architecture designed to learn features from graph-structured inputs and produce sequential outputs. Graph data arises in many domains, and tasks such as reasoning over relations or describing program memory states require models that can both process graphs and emit ordered sequences rather than single classifications. Prior Graph Neural Networks handled only fixed outputs and imposed convergence constraints that limited their practicality.

The work adapts those networks by replacing the propagation rule with Gated Recurrent Units, removing the contraction-map requirement, incorporating node annotations, and extending the model to a sequence of gated steps that can update both outputs and internal node states. Experiments evaluate the resulting models on transformed bAbI reasoning tasks, two new graph-algorithm problems, and a program-verification benchmark that maps heap snapshots to separation-logic formulas describing data structures.

On four single-step bAbI tasks the gated models reach 100 percent accuracy with only 50 training examples, while recurrent and LSTM baselines either require several times more data or fail to reach the same threshold. On path-finding and two sequence-output algorithm tasks the gated sequence networks attain 99–100 percent accuracy with 50–250 examples; the same baselines remain near chance. In the verification setting the model predicts correct logical invariants at 89.96 percent accuracy across held-out formulas, matching or slightly exceeding a heavily engineered feature-based system while using no manual feature design. The predicted invariants suffice to verify correctness of several list-manipulating programs inside an existing theorem prover.

These results indicate that the architecture supplies useful inductive bias for graph problems that involve ordering or enumeration, reduces reliance on domain-specific engineering, and can be trained end-to-end from modest amounts of synthetic data. The approach therefore offers a practical route to automated invariant inference and to other sequence-generation tasks on graphs.

Further work is needed to incorporate temporal order, handle higher-arity relations, accept less-structured inputs, and condition generation dynamically on a query. Additional data and evaluation on larger programs would strengthen before deployment in production verification tools. The reported experiments rest on synthetic or transformed data whose distribution may differ from real-world instances, so performance on naturally occurring graphs remains to be quantified.

Microsoft University of Toronto graph algorithms graph neural networks knowledge base Gated Graph Sequence Neural Networks graph-structured inputs graph-level classification

arXiv: 1511.05493 yujiali/ggnn

Paper: The Graph Neural Network Model, Franco Scarselli et al. (2009). Reading the foundational Graph Neural Network paper first is essential because the source paper directly modifies and extends its architecture with modern gated units.

Paper: Semi-Supervised Classification with Graph Convolutional Networks, Thomas N. Kipf et al. (2017). This paper builds directly on the source's graph neural network foundation to introduce efficient spectral graph convolutions for semi-supervised node classification.
Paper: How Powerful are Graph Neural Networks?, Keyulu Xu et al. (2019). This study extends the representational analysis established in earlier graph neural networks like the source paper to evaluate and improve their expressive power.
Paper: Graph Attention Networks, Petar Veličković et al. (2018). Following the source paper, this work introduces attention mechanisms to graph neural networks, replacing fixed message-passing weights with dynamically learned neighborhood importance.
Paper: Inductive Representation Learning on Large Graphs, William L. Hamilton et al. (2017). This work extends the message-passing paradigm introduced in the source paper to an inductive framework capable of generating embeddings for entirely unseen nodes.
Paper: Representation Learning on Graphs with Jumping Knowledge Networks, Keyulu Xu et al. (2018). This paper builds on the neighborhood aggregation techniques of the source model by introducing jumping knowledge connections to adaptively leverage multiple depths.
Paper: GNNExplainer: Generating Explanations for Graph Neural Networks, Rex Ying et al. (2019). This work directly extends the predictive capabilities of graph neural networks developed in the source paper by providing an optimization framework to explain their outputs.
Paper: Simplifying Graph Convolutional Networks, Felix Wu et al. (2019). This paper takes the graph convolutional concepts initiated in the source literature and strips away their nonlinear layers to demonstrate a simpler, faster linear model.
Paper: Predict then Propagate: Graph Neural Networks meet Personalized PageRank, Johannes Gasteiger et al. (2019). Following the graph neural network foundations of the source paper, this work integrates personalized PageRank propagation to prevent oversmoothing in deep architectures.

Cover for Gated Graph Sequence Neural Networks

Abstract

Graph-structured data appears frequently in domains including chemistry, natural language semantics, social networks, and knowledge bases. In this work, we study feature learning techniques for graph-structured inputs. Our starting point is previous work on Graph Neural Networks (Scarselli et al., 2009), which we modify to use gated recurrent units and modern optimization techniques and then extend to output sequences. The result is a flexible and broadly useful class of neural network models that has favorable inductive biases relative to purely sequence-based models (e.g., LSTMs) when the problem is graph-structured. We demonstrate the capabilities on some simple AI (bAbI) and graph algorithm learning tasks. We then show it achieves state-of-the-art performance on a problem from program verification, in which subgraphs need to be matched to abstract data structures.

Topics

graph algorithms graph neural networks knowledge base natural languages optimization optimization problems program verification representation learning social networks gated recurrent unit

Keywords

Gated Graph Sequence Neural Networks graph-structured inputs graph-level classification sequence prediction tasks node representations recursive neural networks pointer networks memory networks graph kernels

1 INTRODUCTION
2 GRAPH NEURAL NETWORKS
2.1 PROPAGATION MODEL
2.2 OUTPUT MODEL AND LEARNING
3 GATED GRAPH NEURAL NETWORKS
3.1 NODE ANNOTATIONS
3.2 PROPAGATION MODEL
3.3 OUTPUT MODELS
4 GATED GRAPH SEQUENCE NEURAL NETWORKS
5 EXPLANATORY APPLICATIONS
5.1 BABI TASKS
5.1.1 SINGLE STEP OUTPUTS
5.1.2 SEQUENTIAL OUTPUTS
5.2 LEARNING GRAPH ALGORITHMS
6 PROGRAM VERIFICATION WITH GGS-NNs
6.1 FORMALIZATION
6.2 FORMULATION AS GGS-NNs
6.3 MODEL SETUP DETAILS
6.4 BATCH PREDICTION DETAILS
6.5 EXPERIMENTS.
7 RELATED WORK
8 DISCUSSION
ACKNOWLEDGEMENTS
REFERENCES
A CONTRACTION MAP EXAMPLE
A.1 NONLINEAR CASE
B WHY ARE RNN AND LSTM SO BAD ON THE SEQUENCE PREDICTION TASKS?
C NESTED PREDICTION DETAILS

Knowls

Knowl 1 — Gated Graph Neural Network Propagation Model
model/method
Gated Graph Neural Networks (GG-NNs) propagate node representations across a directed graph $G = (V, E)$ with edge types $l_e \in \{1, \dots, L_E\}$ . Each node $v \in V$ maintains a hidden state vector $h_v^{(t)} \in \mathbb{R}^D$ at timestep $t$ . The initial state $h_v^{(1)}$ is formed by copying the initial node annotation vector $x_v$ into the leading dimensions and padding remaining dimensions with zeros:
$h_v^{(1)} = [x_v^\top, 0]^\top$
Information is passed along both incoming and outgoing edges using edge-type-specific parameter matrices aggregated into $a_v^{(t)} \in \mathbb{R}^{2D}$ :
$a_v^{(t)} = A_{v:}^\top \left[ {h_1^{(t-1)}}^\top, \dots, {h_{|V|}^{(t-1)}}^\top \right]^\top + b$
where $A \in \mathbb{R}^{D|V| \times 2D|V|}$ is structured as $[A^{(\text{out})}, A^{(\text{in})}]$ , with submatrix parameters tied based on edge type and direction, and $A_{v:} \in \mathbb{R}^{D|V| \times 2D}$ selects the blocks corresponding to node $v$ .

Node hidden states are updated using Gated Recurrent Unit (GRU) equations unrolled for a fixed number of steps $T$ :
$z_v^t = \sigma\left( W^z a_v^{(t)} + U^z h_v^{(t-1)} \right)$ $r_v^t = \sigma\left( W^r a_v^{(t)} + U^r h_v^{(t-1)} \right)$ $\tilde{h}_v^{(t)} = \tanh\left( W a_v^{(t)} + U \left( r_v^t \odot h_v^{(t-1)} \right) \right)$ $h_v^{(t)} = (1 - z_v^t) \odot h_v^{(t-1)} + z_v^t \odot \tilde{h}_v^{(t)}$
where $\sigma(\cdot)$ denotes the logistic sigmoid function, $\odot$ represents element-wise vector multiplication, and $W^z, U^z, W^r, U^r, W, U$ are learnable weight matrices. Parameters are learned via backpropagation through time (BPTT).
Knowl 2 — GG-NN Output Models for Node Selection and Graph-Level Prediction
model/method
Gated Graph Neural Networks support two primary single-step output modes based on the final node hidden states $h_v^{(T)}$ and node annotations $x_v$ :
1. Node Selection Output: When the target output is a specific node in graph $V$ , a scoring function $g(h_v^{(T)}, x_v)$ computes a scalar score for each node $v \in V$ , normalized using a softmax function over all nodes:
$p(v) = \frac{\exp(g(h_v^{(T)}, x_v))}{\sum_{u \in V} \exp(g(h_u^{(T)}, x_u))}$
1. Graph-Level Representation and Classification: For whole-graph prediction tasks, a graph representation vector $h_G$ is computed via a soft-attention mechanism over all nodes:
$h_G = \tanh \left( \sum_{v \in V} \sigma(i(h_v^{(T)}, x_v)) \odot \tanh(j(h_v^{(T)}, x_v)) \right)$
where $i$ and $j$ are neural networks mapping the concatenation of $h_v^{(T)}$ and $x_v$ to real-valued vectors, $\sigma(\cdot)$ acts as a soft attention mask identifying task-relevant nodes, and $\odot$ denotes element-wise multiplication. The resulting vector $h_G$ is passed to an output layer for classification or regression.
Knowl 3 — Gated Graph Sequence Neural Networks (GGS-NNs)
model/method
Gated Graph Sequence Neural Networks (GGS-NNs) generate sequential outputs $o^{(1)}, \dots, o^{(K)}$ from graph inputs by unrolling a sequence of GG-NN steps.

At output step $k \in \{1, \dots, K\}$ , the graph state is represented by a matrix of node annotations $\mathcal{X}^{(k)} = [x_1^{(k)}; \dots; x_{|V|}^{(k)}] \in \mathbb{R}^{|V| \times L_V}$ . Two GG-NN networks (or two output heads over a shared propagation model) are utilized:
- $\mathcal{F}_o^{(k)}$ , which computes the step output $o^{(k)}$ given $\mathcal{X}^{(k)}$ .
- $\mathcal{F}_X^{(k)}$ , which predicts updated node annotations $\mathcal{X}^{(k+1)}$ for the next step from the final node hidden states $H^{(k,T)}$ of step $k$ .
Node annotations for step $k+1$ are updated independently per node:
$x_v^{(k+1)} = \sigma\left( j(h_v^{(k,T)}, x_v^{(k)}) \right)$
where $j$ is a neural network taking the concatenated vector $[h_v^{(k,T)}, x_v^{(k)}]$ and outputting real-valued scores.

Training operates in two regimes:
- Observed Intermediate Annotations: When ground-truth intermediate annotations $\mathcal{X}^{(k)}$ are provided (e.g., tracking visited/explained nodes), the sequence model decomposes into single-step GG-NNs trained independently and chained sequentially at test time.
- Latent Intermediate Annotations: When intermediate annotations are unavailable during training, $\mathcal{X}^{(k)}$ are treated as latent hidden variables and the whole architecture is trained jointly end-to-end by backpropagating through the entire output sequence.
Knowl 4 — Program Invariant Inference via Separation Logic Formula Prediction
algorithm
To automatically infer program invariants over memory heaps, a GGS-NN processes a heap graph $G = (V, E)$ (where nodes represent heap addresses and directed edges represent pointer fields) with program variable labels, outputting a separation logic formula of the form $\exists x_1, \dots, x_n. a_1 * \dots * a_m$ . Atomic predicates $a_i$ describe inductive heap structures such as list segments $ls(x, y)$ , binary trees $tree(x)$ , or empty structures $none(x)$ .

Three explicit node annotation bits are used: is-named (node is labeled by a program variable or an existential variable), active (currently focused root node), and is-explained (node belongs to an already predicted structural invariant).
Input: Heap graph $G$ with named program variables
Output: Separation logic formula string
procedure PredictSeparationLogicFormula(G)
     $\mathcal{X} \leftarrow$ initialize node annotations from $G$ (is-named on for program variables, active and is-explained off)
     $\mathcal{H} \leftarrow$ initialize node hidden vectors by 0-extending $\mathcal{X}$
    while Graph-level classifier indicates existential quantifier needed do
         $t \leftarrow$ fresh variable name
         $v \leftarrow$ select node via Node Selection GG-NN
         $\mathcal{X} \leftarrow$ turn on is-named bit for node $v$ in $\mathcal{X}$
        print " $\exists t.$ "
    end while
    for each node $v_\ell$ with is-named bit set in $\mathcal{X}$ do
         $\mathcal{H} \leftarrow$ initialize node hidden vectors, turn on active bit for $v_\ell$ in $\mathcal{X}$
         $pred \leftarrow$ predict predicate $\in \{ls, tree, none\}$ via Graph-level Classification GG-NN
        if $pred = ls$ then
             $\ell_{end} \leftarrow$ select list end node via Node Selection GG-NN
            print " $ls(\ell, \ell_{end}) *$ "
        else
            print " $pred(\ell) *$ "
        end if
         $\mathcal{X} \leftarrow$ update node annotations (is-explained bits) via Node Annotation GG-NN
    end for
end procedure
Knowl 5 — Multi-Graph Batch Prediction for Program Invariant Inference
model/method
In automatic program verification, a single invariant formula must hold across multiple heap graphs $g \in \{1, \dots, M\}$ representing different execution states or runs of a program. GGS-NNs perform batch prediction by executing individual GGS-NN pipelines on each graph simultaneously and aggregating predictions across the batch:
1. Node Selection Aggregation: For selecting a variable named $t$ across graphs, let $V_g(t)$ denote the node corresponding to variable $t$ in graph $g$ , and let $o_{V_g(t)}^g$ denote the node score output by the model on graph $g$ . Aggregate scores are computed by summation:
$o_t = \sum_g o_{V_g(t)}^g \iff p(\text{select} = t) = \prod_g p_g(\text{select} = V_g(t))$
Softmax is then applied over candidate variable names using $o_t$ .
1. Graph-Level Classification Aggregation: Discrete classification logits (e.g., predicate type selection) are summed across graphs:
$p(\text{class} = k) \propto \prod_g p_g(\text{class} = k)$
1. Node Annotation Updates: Annotations $\mathcal{X}_g$ are updated independently per graph while synchronizing updates on shared variable names.
Knowl 6 — Recursive GGS-NN Prediction of Nested Separation Logic Formulas
algorithm
To handle nested data structures (such as lists of lists where each node's val pointer points to another heap data structure), the separation logic prediction procedure uses a recursive GGS-NN pipeline that generates nested predicates containing lambda abstractions $\lambda t. \dots$ .
Input: Heap graph $G$ with named program variables
Output: Nested separation logic formula string
procedure OuterLoop(G)
     $\mathcal{X} \leftarrow$ initialize node annotations from $G$
    for each variable name $var$ do
         $v_\ell \leftarrow$ node associated with $var$ in $G$
         $\mathcal{X} \leftarrow$ turn on active bit for $v_\ell$ in $\mathcal{X}$
        PredictNestedFormula( $G$ , $\mathcal{X}$ , $var$ )
    end for
end procedure
procedure PredictNestedFormula(G, $\mathcal{X}$ , $var$ )
     $\mathcal{H} \leftarrow$ initialize node vectors by 0-extending $\mathcal{X}$
    while Graph-level classifier indicates existential quantifier needed do
         $e \leftarrow$ fresh existentially quantified variable name
         $v \leftarrow$ select node via Node Selection GG-NN
         $\mathcal{X} \leftarrow$ turn on is-named bit for $v$ in $\mathcal{X}$
        print " $\exists e.$ "
    end while
    if $var$ is a lambda variable name then
        print " $\lambda var.$ "
    end if
     $pred \leftarrow$ predict predicate $\in \{ls, tree, none\}$ via Graph Classification GG-NN
    if $pred = ls$ then
         $\ell_{end} \leftarrow$ select list end node via Node Selection GG-NN
         $var_{end} \leftarrow$ variable name associated with $\ell_{end}$
        print " $ls(var, var_{end},$ "
    else if $pred = tree$ then
        print " $tree(var,$ "
    else
        print " $none(var) *$ "
        return
    end if
     $\mathcal{X} \leftarrow$ update node annotations in $\mathcal{X}$ (mark current structure nodes as is-explained, mark nodes pointed to by val as active)
     $t \leftarrow$ fresh lambda variable name
    PredictNestedFormula( $G$ , $\mathcal{X}$ , $t$ )
    print " $) *$ "
end procedure
Knowl 7 — Contraction Mapping Property Limits Long-Range Propagation in Standard GNNs
theoretical result
Standard Graph Neural Networks (GNNs) trained with the Almeida-Pineda algorithm require the transition operator $T(h)$ to be a contraction mapping in the Euclidean metric with parameter $\rho < 1$ :
$\|T(h) - T(h')\| < \rho \|h - h'\|$
For a 1-hidden-unit cycle graph of $N$ nodes updated via $h_i^{(t)} = \sigma(m_i h_{i-1}^{(t-1)} + b_i)$ , this contraction constraint bounds the partial derivatives of the state transition function by $\rho$ :
$\left| \frac{\partial h_i^{(t)}}{\partial h_{i-1}^{(t-1)}} \right| < \rho$
Applying the chain rule across a propagation chain of length $t$ on the cycle yields:
$\left| \frac{\partial h_t^{(t)}}{\partial h_1^{(1)}} \right| = \prod_{\tau=2}^t \left| \frac{\partial h_\tau^{(\tau)}}{\partial h_{\tau-1}^{(\tau-1)}} \right| < \rho^{t-1}$
Since $\rho < 1$ , the gradient of a node's state with respect to an input state $t$ steps away decays exponentially to zero as $\rho^{t-1} \to 0$ . This contraction map constraint prevents standard GNNs from retaining long-range dependencies across graphs, motivating the GG-NN design of unrolling the recurrence for fixed $T$ steps with GRU gating.

Knowl 8 — Sample Efficiency of GG-NNs on bAbI Reasoning Tasks

data/table

GG-NNs were compared against sequence-based RNN and LSTM models on symbolic representations of four single-step bAbI artificial intelligence reasoning tasks (Task 4: Two Argument Relations, Task 15: Basic Deduction, Task 16: Basic Induction, and Task 18: Size Reasoning). Models were trained on increasing sample sizes (50, 100, 250, 500, 950 examples) until reaching $\ge 95\%$ accuracy over 10 random datasets.

Task	RNN	LSTM	GG-NN
bAbI Task 4	97.3 $\pm$ 1.9 (250)	97.4 $\pm$ 2.0 (250)	100.0 $\pm$ 0.0 (50)
bAbI Task 15	48.6 $\pm$ 1.9 (950)	50.3 $\pm$ 1.3 (950)	100.0 $\pm$ 0.0 (50)
bAbI Task 16	33.0 $\pm$ 1.9 (950)	37.5 $\pm$ 0.9 (950)	100.0 $\pm$ 0.0 (50)
bAbI Task 18	88.9 $\pm$ 0.9 (950)	88.9 $\pm$ 0.8 (950)	100.0 $\pm$ 0.0 (50)

Accuracy is given as mean percent $\pm$ standard deviation, with numbers in parentheses indicating the minimum training examples required to achieve the reported accuracy. GG-NNs used node hidden dimensions $D \in \{3, 4, 5, 6\}$ and under 600 parameters per network, reaching 100.0% accuracy on all four tasks with only 50 training examples. Standard RNN and LSTM baselines (50-dimensional embeddings, 5k-30k parameters) failed to solve Tasks 15, 16, and 18 even with 950 training examples.

Knowl 9 — GGS-NN Performance on Graph Algorithm Learning Tasks

data/table

GGS-NNs were evaluated against RNN and LSTM baselines on three sequential prediction tasks: bAbI Task 19 (Path Finding), Shortest Path generation on random graphs, and Eulerian Circuit traversal on 2-regular connected graphs with distractors.

Task	RNN	LSTM	GGS-NNs
bAbI Task 19	24.7 $\pm$ 2.7 (950)	28.2 $\pm$ 1.3 (950)	71.1 $\pm$ 14.7 (50) / 92.5 $\pm$ 5.9 (100) / 99.0 $\pm$ 1.1 (250)
Shortest Path	9.7 $\pm$ 1.7 (950)	10.5 $\pm$ 1.2 (950)	100.0 $\pm$ 0.0 (50)
Eulerian Circuit	0.3 $\pm$ 0.2 (950)	0.1 $\pm$ 0.2 (950)	100.0 $\pm$ 0.0 (50)

Accuracy is reported in percent $\pm$ standard deviation across 10 datasets, with required training set size shown in parentheses. GGS-NNs ( $D = 20$ , 5 propagation steps) achieved 100.0% accuracy on Shortest Path and Eulerian Circuit with 50 examples, and 99.0% accuracy on bAbI Task 19 with 250 examples. Sequence-based RNN and LSTM models failed across all three tasks due to long sequence lengths and the permuted, non-sequential nature of graph edge inputs.

Knowl 10 — Program Invariant Inference Accuracy on Separation Logic Benchmarks
empirical result
GGS-NNs were evaluated on predicting separation logic formulas from heap graphs across a synthetic dataset of 327 ground-truth formulas (with 3 program variables and 498 heap graphs per formula, totaling ~160,000 combinations) split 6:2:2 across formulas for train/validation/test sets.

Without manual feature engineering, GGS-NN achieved a formula prediction accuracy of 89.96% on unseen test formulas, exceeding the 89.11% accuracy of a baseline model relying on hand-engineered features.

When integrated into an automated verification framework, the invariants predicted by GGS-NN successfully enabled a theorem prover to prove memory safety and correctness for seven benchmark pointer-manipulating C programs:
- Traverse1: $\text{ls}(\text{lst}, \text{curr}) * \text{ls}(\text{curr}, \text{NULL})$
- Traverse2: $\text{curr} \neq \text{NULL} * \text{lst} \neq \text{NULL} * \text{ls}(\text{lst}, \text{curr}) * \text{ls}(\text{curr}, \text{NULL})$
- Concat: $a \neq \text{NULL} * a \neq b * b \neq \text{curr} * \text{curr} \neq \text{NULL} * \text{ls}(\text{curr}, \text{NULL}) * \text{ls}(a, \text{curr}) * \text{ls}(b, \text{NULL})$
- Copy: $\text{ls}(\text{curr}, \text{NULL}) * \text{ls}(\text{lst}, \text{curr}) * \text{ls}(\text{cp}, \text{NULL})$
- Dispose: $\text{ls}(\text{lst}, \text{NULL})$
- Insert: $\text{curr} \neq \text{NULL} * \text{curr} \neq \text{elt} * \text{elt} \neq \text{NULL} * \text{elt} \neq \text{lst} * \text{lst} \neq \text{NULL} * \text{ls}(\text{elt}, \text{NULL}) * \text{ls}(\text{lst}, \text{curr}) * \text{ls}(\text{curr}, \text{NULL})$
- Remove: $\text{curr} \neq \text{NULL} * \text{lst} \neq \text{NULL} * \text{ls}(\text{lst}, \text{curr}) * \text{ls}(\text{curr}, \text{NULL})$
Knowl 11 — Limitations of GGS-NNs for Natural Language and Dynamic Reasoning
limitation
The GGS-NN model exhibits three primary limitations:
1. Loss of Temporal Sequence and Higher-Order Relations: Mapping sequential stories directly to static graphs discards the chronological ordering of story events and cannot directly represent ternary or higher-order relations without additional structures such as factor graphs.
2. Requirement for Pre-Parsed Symbolic Inputs: The model cannot operate directly on raw natural language text and requires external parsing into symbolic graph representations.
3. Upfront Fact Consumption vs. Dynamic Querying: The network consumes all input facts to compute node embeddings before receiving the question, requiring it to precompute and encode all possible deductive consequences into node vectors rather than dynamically retrieving relevant facts guided by a query.

Coverage note — None was omitted; all primary contributions, models, theoretical analyses, algorithms, experimental benchmarks, and limitations are covered.

References

1.Almeida, Luis B. A learning rule for asynchronous perceptrons with feedback in a combinatorial environment. In Artificial neural networks, pp. 102–111. IEEE Press, 1990.
2.Bahdanau, Dzmitry, Cho, Kyunghyun, and Bengio, Yoshua. Neural machine translation by jointly learning to align and translate. CoRR, abs/1409.0473, 2014.
3.Bottou, Léon. From machine learning to machine reasoning. Machine learning, 94(2):133–149, 2014.
4.Brockschmidt, Marc, Chen, Yuxin, Cook, Byron, Kohli, Pushmeet, and Tarlow, Daniel. Learning to decipher the heap for program verification. In Workshop on Constructive Machine Learning at the International Conference on Machine Learning (CMLICML), 2015.
5.Bruna, Joan, Zaremba, Wojciech, Szlam, Arthur, and LeCun, Yann. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203, 2013.
6.Cho, Kyunghyun, Van Merriënboer, Bart, Gulcehre, Caglar, Bahdanau, Dzmitry, Bougares, Fethi, Schwenk, Holger, and Bengio, Yoshua. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv:1406.1078, 2014.
7.Di Massa, Vincenzo, Monfardini, Gabriele, Sarti, Lorenzo, Scarselli, Franco, Maggini, Marco, and Gori, Marco. A comparison between recursive neural networks and graph neural networks. In International Joint Conference on Neural Networks (IJCNN), pp. 778–785. IEEE, 2006.
8.Domke, Justin. Parameter learning with truncated message-passing. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2937–2943. IEEE, 2011.
9.Duvenaud, David, Maclaurin, Dougal, Aguilera-Iparraguirre, Jorge, Gómez-Bombarelli, Rafael, Hirzel, Timothy, Aspuru-Guzik, Alán, and Adams, Ryan P. Convolutional networks on graphs for learning molecular fingerprints. arXiv preprint arXiv:1509.09292, 2015.
10.Goller, Christoph and Kuchler, Andreas. Learning task-dependent distributed representations by back-propagation through structure. In IEEE International Conference on Neural Networks, volume 1, pp. 347–352. IEEE, 1996.
11.Gori, Marco, Monfardini, Gabriele, and Scarselli, Franco. A new model for learning in graph domains. In International Joint Conference onNeural Networks (IJCNN), volume 2, pp. 729–734. IEEE, 2005.
12.Hammer, Barbara and Jain, Brijnesh J. Neural methods for non-standard data. In European Symposium on Artificial Neural Networks (ESANN), 2004.
13.Hinton, Geoffrey E. Representing part-whole hierarchies in connectionist networks. In Proceedings of the Tenth Annual Conference of the Cognitive Science Society, pp. 48–54. Erlbaum., 1988.
14.Hoare, Charles Antony Richard. An axiomatic basis for computer programming. Communications of the ACM, 12(10):576–580, 1969.
15.Kashima, Hisashi, Tsuda, Koji, and Inokuchi, Akihiro. Marginalized kernels between labeled graphs. In Proceedings of the International Conference on Machine Learning, volume 3, pp. 321–328, 2003.
16.Kingma, Diederik and Ba, Jimmy. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
17.Kumar, Ankit, Irsoy, Ozan, Su, Jonathan, Bradbury, James, English, Robert, Pierce, Brian, Ondruska, Peter, Gulrajani, Ishaan, and Socher, Richard. Ask me anything: Dynamic memory networks for natural language processing. arXiv preprint arXiv:1506.07285, 2015.
18.Lusci, Alessandro, Pollastri, Gianluca, and Baldi, Pierre. Deep architectures and deep learning in chemoinformatics: the prediction of aqueous solubility for drug-like molecules. J Chem Inf Model, 2013.
19.Micheli, Alessio. Neural network for graphs: A contextual constructive approach. IEEE Transactions on Neural Networks, 20(3):498–511, 2009.
20.O’Hearn, Peter, Reynolds, John C., and Yang, Hongseok. Local reasoning about programs that alter data structures. In 15th International Workshop on Computer Science Logic (CSL’01), pp. 1–19, 2001.
21.Perozzi, Bryan, Al-Rfou, Rami, and Skiena, Steven. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701–710. ACM, 2014.
22.Pineda, Fernando J. Generalization of back-propagation to recurrent neural networks. Physical review letters, 59(19):2229, 1987.
23.Piskac, Ruzica, Wies, Thomas, and Zufferey, Damien. GRASShopper - complete heap verification with mixed specifications. In 20st International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’14), pp. 124–139, 2014.
24.Reynolds, John C. Separation logic: A logic for shared mutable data structures. In 7th IEEE Symposium on Logic in Computer Science (LICS’02), pp. 55–74, 2002.
25.Scarselli, Franco, Gori, Marco, Tsoi, Ah Chung, Hagenbuchner, Markus, and Monfardini, Gabriele. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61–80, 2009.
26.Shervashidze, Nino, Schweitzer, Pascal, Van Leeuwen, Erik Jan, Mehlhorn, Kurt, and Borgwardt, Karsten M. Weisfeiler-lehman graph kernels. The Journal of Machine Learning Research, 12: 2539–2561, 2011.
27.Socher, Richard, Lin, Cliff C, Manning, Chris, and Ng, Andrew Y. Parsing natural scenes and natural language with recursive neural networks. In Proceedings of the 28th international conference on machine learning (ICML-11), pp. 129–136, 2011.
28.Sperduti, Alessandro and Starita, Antonina. Supervised neural networks for the classification of structures. IEEE Transactions on Neural Networks, 8(3):714–735, 1997.
29.Stoyanov, Veselin, Ropson, Alexander, and Eisner, Jason. Empirical risk minimization of graphical model parameters given approximate inference, decoding, and model structure. In International Conference on Artificial Intelligence and Statistics, pp. 725–733, 2011.
30.Sukhbaatar, Sainbayar, Szlam, Arthur, Weston, Jason, and Fergus, Rob. End-to-end memory networks. arXiv preprint arXiv:1503.08895, 2015.
31.Tai, Kai Sheng, Socher, Richard, and Manning, Christopher D. Improved semantic representations from tree-structured long short-term memory networks. arXiv preprint arXiv:1503.00075, 2015.
32.Uwents, Werner, Monfardini, Gabriele, Blockeel, Hendrik, Gori, Marco, and Scarselli, Franco. Neural networks for relational learning: an experimental comparison. Machine Learning, 82(3):315–349, 2011.
33.Vinyals, Oriol, Fortunato, Meire, and Jaitly, Navdeep. Pointer networks. arXiv preprint arXiv:1506.03134, 2015.
34.Weston, Jason, Bordes, Antoine, Chopra, Sumit, and Mikolov, Tomas. Towards ai-complete question answering: a set of prerequisite toy tasks. arXiv preprint arXiv:1502.05698, 2015.

Citation

MLA

Li, Y., et al. “Gated Graph Sequence Neural Networks”. arXiv, 2015, http://arxiv.org/abs/1511.05493v4.

APA

Li, Y., Tarlow, D., Brockschmidt, M., & Zemel, R. (2015). Gated Graph Sequence Neural Networks. arXiv. http://arxiv.org/abs/1511.05493v4

Chicago

Li, Y., D. Tarlow, M. Brockschmidt, and R. Zemel. 2015. “Gated Graph Sequence Neural Networks”. arXiv. http://arxiv.org/abs/1511.05493v4.

Harvard

Li, Y. et al. (2015) “Gated Graph Sequence Neural Networks”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1511.05493v4.

Vancouver

1. Li Y, Tarlow D, Brockschmidt M, Zemel R (2015) Gated Graph Sequence Neural Networks. arXiv

BibTeX

@article{li2015gated,
  title = {Gated Graph Sequence Neural Networks},
  author = {Li, Yujia and Tarlow, Daniel and Brockschmidt, Marc and Zemel, Richard},
  year = {2015},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1511.05493v4},
  eprint = {1511.05493}
}

Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Published with permission

Gated Graph Sequence Neural Networks

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Gated Graph Neural Network Propagation Model

Knowl 2 — GG-NN Output Models for Node Selection and Graph-Level Prediction

Knowl 3 — Gated Graph Sequence Neural Networks (GGS-NNs)

Knowl 4 — Program Invariant Inference via Separation Logic Formula Prediction

Knowl 5 — Multi-Graph Batch Prediction for Program Invariant Inference

Knowl 6 — Recursive GGS-NN Prediction of Nested Separation Logic Formulas

Knowl 7 — Contraction Mapping Property Limits Long-Range Propagation in Standard GNNs