Gated Graph Sequence Neural Networks

Yujia Li; Daniel Tarlow; Marc Brockschmidt; Richard Zemel

Source-linked AI summary

Gated Graph Sequence Neural Networks

Yujia Li, Daniel Tarlow, Marc Brockschmidt, Richard Zemel

arXiv:1511.05493v4Nov 17, 2015cs.LGcs.AIcs.NEstat.ML

TL;DR

Graph learning had focused mainly on single-output predictions, leaving graph problems requiring output sequences insufficiently addressed. The paper introduces Gated Graph Sequence Neural Networks, demonstrating their capabilities across graph tasks and state-of-the-art program-verification performance while matching hand-engineered accuracy.

Problem
Existing graph feature-learning models mainly produced single outputs, leaving graph problems requiring output sequences insufficiently supported.
Method
The paper extends Graph Neural Networks with gated recurrent units and sequence generation, producing Gated Graph Sequence Neural Networks.
Results
The model illustrates capabilities on bAbI and graph-algorithm tasks and replaces hand-engineered program-verification features at no cost in accuracy.
Takeaways & Limitations
Results support desirable inductive biases for GGS-NNs across problems with intrinsic graph structure.
Takeaways & Limitations
The bAbI task translation omits temporal order and ternary or higher-order relations, limiting direct application to arbitrary natural language.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper introduces Gated Graph Sequence Neural Networks, extending Graph Neural Networks to produce sequences from graph inputs while representing both the graph and sequence-generation state. It demonstrates the model on bAbI and graph algorithm tasks and applies it to computer-program verification.

Contribution: The main contribution is extending Graph Neural Networks from single outputs to sequences such as graph paths, node enumerations, and mixed global classifications.Many graph-input problems require structured sequences rather than only graph-level classifications.
Model: GGS-NNs learn representations of both the input graph and the internal state encoding the partial and remaining output sequence.For path generation, this state can encode both the path produced so far and the remaining path.
Model: The model adapts the Graph Neural Network framework with minor changes, including modern recurrent-neural-network practices.These adaptations support feature learning during sequence generation.
Experiments and application: Experiments illustrate the model’s capabilities on bAbI tasks and graph algorithm learning tasks, followed by an application to computer-program verification.The verification setting concerns learning mathematical descriptions of program data structures for properties such as memory safety.

2 GRAPH NEURAL NETWORKS

Graph Neural Networks represent graph-structured inputs through iterative node-representation propagation followed by differentiable output mappings. Their training is end-to-end, while convergence-based learning can limit expressivity because propagation parameters must define a contraction map.

Graph representation: GNNs define node representations on graph-structured inputs G = (V, E), focusing here on directed edges while allowing adaptation to undirected graphs.Each node v has an embedding h_v ∈ R^D.
Architecture: GNNs first propagate representations across nodes and then map each representation with its corresponding label to an output.The complete system is differentiable end-to-end, so parameters are learned jointly using gradient-based optimization.
Propagation: The original GNN procedure initializes node representations arbitrarily and repeatedly applies a recurrence until convergence.The recurrence is indexed by timestep t, and variants include positional graph forms, node-specific updates, and alternative neighborhood representations.
Learning limitations: The Almeida-Pineda learning procedure differentiates through the converged propagation solution without storing intermediate states.It requires propagation to be a contraction map to ensure convergence, which may limit model expressivity.

3 GATED GRAPH NEURAL NETWORKS

Gated Graph Neural Networks adapt graph neural networks for non-sequential outputs by replacing fixed-point computation with GRU-based recurrence unrolled for T steps and trained by backpropagation through time. They also use node annotations and extend graph representations and output models to support task-relevant node and graph-level predictions.

Architecture: GG-NNs use Gated Recurrent Units, unroll recurrence for T steps, and apply backpropagation through time instead of Almeida-Pineda fixed-point optimization.This removes the need to constrain parameters for convergence, but requires more memory.
Node annotations: Node annotations provide initialization inputs, allowing GG-NNs to incorporate node labels into hidden states.Annotations are copied into the first dimensions of each node state and padded with zeros.
Node annotations: In reachability, annotations mark source s and target t, while propagation can copy s’s annotation along forward edges to reachable nodes.Setting the forward-edge propagation matrix entry at position (0,0) to 1 makes the first representation dimension propagate from s.
Propagation: The propagation model uses graph-induced sparse, edge-type- and direction-specific communication followed by GRU-like updates with reset and update gates.The recurrent update combines information from neighboring nodes with each node’s previous hidden state.
Outputs: GG-NNs support node selection through node scores and graph-level outputs through a soft-attention representation over task-relevant nodes.Node selection applies a softmax over node scores, while graph-level representations are computed from node states and annotations.

4 GATED GRAPH SEQUENCE NEURAL NETWORKS

Gated Graph Sequence Neural Networks (GGS-NNs) apply several gated graph neural networks sequentially to produce output sequences. They support separate or shared propagation models and training with observed or latent intermediate node annotations.

Architecture: GGS-NNs operate several GG-NNs in sequence to produce output sequence o(1) . . . o(K).At each output step, node annotations are updated and passed to the next step.
Architecture: A simpler variant shares one propagation model across steps while using separate output models, making training and evaluation faster.It can achieve similar performance in many cases but may underperform when desired propagation behaviors differ across steps.
Training: Training either specifies all intermediate annotations X (k) or trains the full model end-to-end from X (1), graphs, and target sequences.Observed annotations can exploit domain knowledge, whereas latent-annotation training is more general.
Observed annotations: With observed annotations, sequence prediction decomposes during training into separate single-step GG-NN tasks and feeds predicted annotations between steps at test time.This setup is analogous to training directed graphical models with fully observed data.
Latent annotations: With latent annotations, intermediate node annotations are hidden units and the whole sequence model is trained jointly by backpropagation.This approach applies when intermediate annotations are unavailable during training.

5 EXPLANATORY APPLICATIONS

This section demonstrates GGS-NNs on selected bAbI reasoning tasks and two graph algorithm tasks, using graph representations derived from symbolic stories. GGS-NNs achieve strong data efficiency and outperform sequence-based baselines on several tasks, while the transformation loses temporal and higher-order relational information.

Scope: The section evaluates GGS-NNs on selected bAbI tasks and two graph algorithm learning tasks.The bAbI tasks cover basic reasoning, while the graph tasks include shortest paths and Eulerian circuits.
bAbI transformation: Each symbolic bAbI story is converted into a graph whose nodes represent entities, edges represent labeled relations, and question arguments initialize node annotations.Questions become task-specific outputs, with separate GG-NNs used for tasks containing multiple question types.
Limitations: The transformation discards temporal order, does not easily represent ternary or higher-order relations, and cannot be directly applied to arbitrary natural language.Relaxing these restrictions is left for future work.
bAbI results: For bAbI Tasks 4, 15, 16, and 18, GG-NNs achieve perfect test accuracy with only 50 training examples, whereas RNN/LSTM baselines require more data or fail.The GGNN models contain fewer than 600 parameters, while the RNN and LSTM baselines contain around 5k and 30k parameters, respectively.
Graph algorithm results: With only 50 training examples, GGS-NNs achieve much better test accuracy than RNN and LSTM on the graph algorithm task, which both sequence baselines fail.The graph tasks generate shortest-path questions on random graphs and Eulerian-circuit questions on random two-regular connected graphs.

6 PROGRAM VERIFICATION WITH GGS-NNS

The section applies GGS-NNs to infer separation-logic heap invariants from program memory graphs, addressing the challenge of describing data structures for program verification. The approach achieves 89.96% accuracy without feature engineering and supports verification of list-manipulating and more sophisticated programs.

Program verification: GGS-NNs infer separation-logic formulas from heap graphs extracted from program memory states, enabling static analyses to check properties such as memory safety.The predicted formulas describe candidate data structures, which static program-analysis tools can validate for sufficiency.
Heap representation: Heap states are represented as directed, possibly cyclic graphs whose labeled edges encode pointer fields and whose nodes represent memory addresses.The model focuses on pointer values while ignoring non-pointer values.
Formula prediction: The output language restricts separation logic to existentially quantified compositions of list segments, binary trees, and no-data-structure predicates.Synthetic datasets pair heap graphs satisfying enumerated formulas with their corresponding formulas.
Formula prediction: Formula generation proceeds sequentially by declaring existential variables, selecting their heap nodes, and predicting the data-structure predicate rooted at each named node.The procedure uses is-named, active, and is-explained node annotations; annotations can be observed during training but not at test time.
Results: 89.96% accuracy was achieved without feature engineering, compared with 89.11% for an earlier classification-based approach requiring manual, problem-specific features.The newer model used very little domain knowledge.
Results: The inferred invariants were successfully used in a verification framework to prove list-manipulating programs correct, and extensions handled sorting and nested data structures.The batch-prediction setup combines multiple heap snapshots or runs into one formula consistent with all inputs.

7 RELATED WORK

The paper situates GG-NNs among GNNs, structured prediction, recursive and graph-based models, and attention mechanisms. It emphasizes explicit graph structure, sequence outputs, and learned mechanisms for node selection and coverage.

Graph neural networks: GNNs are the closest related work, while Micheli’s model mainly differs in its output model; the paper also aims to publicize GNNs as useful neural variants.GNNs have been applied in several domains but are described as not widespread in the ICLR community.
Structured and recursive models: GG-NNs adapt ideas from truncated belief propagation and Tree LSTMs by replacing standard recurrences with GRU updates to improve long-term propagation.The analogy concerns training truncated iterations for good fixed-step results and using GRU updates instead of standard GNN recurrence.
Graph-based learning: Graph kernels support graph-structured learning, while prior approaches either convert graphs into random-walk sequences, graph vectors, or classifiers rather than learning kernels and sequence outputs.The passage explicitly notes no known work that learns both the kernels and outputs sequences.
Pointer networks: Compared with pointer networks, GNNs expose graph structure and can represent nodes without required properties such as spatial location, potentially strengthening generalization.Pointer networks require node properties, whereas explicit graph structure makes GNNs less general but may improve generalization.
Attention and alignment: GG-NNs relate to attention models through context-based node focus and node annotations that track which program-verification nodes have already been explained.These mechanisms help ensure that each input node has been used over the process described in the passage.

8 DISCUSSION

The discussion argues that GGS-NNs learn task-relevant background knowledge in their weights and exhibit useful inductive biases for graph-structured problems. It also identifies limitations in relation handling, input structure, and question timing while outlining broader applications.

What is being learned?: GGS-NNs learn background knowledge absent from the graph encoding, storing the resulting inference capability in neural network weights.The task encoding simplifies parsing into graph form but does not provide background knowledge or inference rules.
Discussion: The models have desirable inductive biases across problems with intrinsic graph structure, but limitations must be overcome for broader applicability.The authors believe GGS-NNs may be useful in many additional graph-structured settings.
Limitations: Current limitations include restricted relation representations and reliance on structured symbolic inputs; proposed remedies include edge-specific GG-NNs, factor graphs, and latent vectors.The authors note that experimentation is needed to determine the best approach for less structured inputs.
Limitations: Because the question is supplied only after all facts are consumed, the network must derive and store all potentially relevant consequences before answering.The authors suggest introducing the question initially so the model can dynamically derive only the facts needed for the answer.
Future applications: Future work targets learnable systems for program semantics, more complex graph algorithms, and reasoning over knowledge bases and databases.More generally, the authors view graph neural networks as combining structured representations with deep-learning algorithms.

A CONTRACTION MAP EXAMPLE

The section analyzes a linear one-hidden-unit cycle-structured GNN by imposing a Euclidean contraction condition on its propagation update. This condition constrains the propagation parameters and prevents the model from maintaining long-range dependencies in this simple setting.

Setup: The example considers a linear one-hidden-unit GNN arranged as an N-node cycle, ignoring edge and node labels.The setup is equivalent to LV = 1 and LE = 1.
Propagation update: The propagation dynamics are written as a joint update over all node hidden states using parameters mi and bi.The hidden states cycle around the node indices, with hj referring to hN+j when j ≤ 0.
Contraction condition: Under a Euclidean contraction mapping, there exists ρ < 1 that bounds the update’s behavior for any pair of hidden-state vectors.The contraction restriction is imposed directly on the propagation update T.
Parameter constraint: The contraction condition immediately implies |mi| < ρ for every node i.This follows by evaluating the contraction inequality on an elementary vector differing from the zero vector at position i − 1.
Information propagation: Because node labels control which mi and bi values are used, contraction prevents this simple GNN from maintaining long-range dependencies.The conclusion follows from expanding the update and using mi < ρ for all i.

A.1 NONLINEAR CASE

For the nonlinear update T(h) = σ(Mh + b), the contraction condition bounds each Jacobian entry by ρ. On the special cycle graph, influence across timesteps decays as ρ^(t−1), approaching zero exponentially when ρ < 1 and making long-range dependencies difficult to model.

Nonlinear update: For T(h) = σ(Mh + b), the contraction-map condition bounds every entry of T’s Jacobian matrix by ρ.Here, σ is any nonlinear function.
Cycle-graph structure: The special cycle-graph structure makes each node update depend only on its corresponding predecessor, with all other partial derivatives equal to 0.This sparsity is used when applying the update across timesteps.
Influence decay: ρ^(t−1) is the resulting derivative of a node’s influence after t−1 steps, and it approaches 0 exponentially fast when ρ < 1.Consequently, the impact of one node on another far away decays exponentially, making long-range dependencies difficult to model.

B WHY ARE RNN AND LSTM SO BAD ON THE SEQUENCE PREDICTION TASKS?

RNNs and LSTMs perform poorly on sequence-prediction tasks because graph inputs become long token sequences requiring long-range memory. Their sequential processing also mismatches tasks whose outputs are invariant to input-edge order, whereas GGS-NNs handle such static graph structure better.

RNN and LSTM performance is very poor on bAbI task 19, shortest path, and Eulerian circuit sequence-prediction tasks, with Eulerian circuit failures most dramatic.
The Eulerian-circuit example is transformed into a token sequence of close to 80 tokens before prediction begins.The input graph contains a target cycle and a smaller distractor graph, with edges presented in both directions.
Some predictions require long-range memory, such as using the first edge and early tokens to determine the third prediction step.LSTMs retain long-range memory better than RNNs, but still face difficulty.
The output sequence does not follow input order because these graph tasks lack sequential nature and remain unchanged when edges are randomly permuted.This applies to the Eulerian-circuit, bAbI task 19, and shortest-path tasks.
GGS-NNs handle this type of static graph data better than RNNs and LSTMs, although applying them to temporal sequential data remains future work.

C NESTED PREDICTION DETAILS

The paper extends GGS-NNs to predict nested separation-logic formulas for data structures such as lists of lists. The procedure iterates over named variables, updates node annotations to track explained and active regions, and recursively predicts nested predicates.

Nested data structures: Nested data structures are represented by nested separation-logic predicates, such as ls(x, y, λt →ls(t, NULL)) for a list of lists.The lambda expression requires each node’s val target to satisfy a nested list predicate.
Prediction procedure: The outer loop activates the node associated with each named variable and invokes nested-formula prediction for that variable.Algorithm 2 computes initial labels, turns on the active bit, and calls PREDICTNESTEDFORMULA once per variable.
Prediction procedure: Before recursive prediction, the model marks current-structure nodes as “is-explained” and val-pointer targets as “active”.These annotations provide context for predicting the nested structure reached through each node’s val pointer.
Learned annotations: The annotation model learns the explained and active-node behavior from data rather than relying on hard-coded rules.This learned annotation mechanism is part of the nested prediction procedure.