Source-linked AI summary
Graph2Seq: Graph to Sequence Learning with Attention-based Neural Networks
Kun Xu, Lingfei Wu, Zhiguo Wang, Yansong Feng, Michael Witbrock, Vadim Sheinin
TL;DR
Graph2Seq addresses the difficulty of converting graph-structured inputs into accurate sequences, where sequence-only models can lose structural information. It combines directed-neighborhood graph encoding with attention-based sequence decoding, and reports state-of-the-art performance across bAbI, Shortest Path, and Natural Language Generation tasks.
Problem
Seq2Seq models are designed for sequence inputs, but many tasks are naturally represented as graphs whose structure is lost when converted into sequences.
Method
Graph2Seq combines a graph encoder for bi-directional node and graph embeddings with an attention-based RNN decoder that aligns node representations with generated sequence elements.
Results
Graph2Seq achieves state-of-the-art performance across three graph-to-sequence tasks and significantly outperforms graph neural networks, Seq2Seq, and Tree2Seq baselines.
Takeaways & Limitations
Bi-directional node aggregation supports representations of directed acyclic, directed cyclic, and sequence-styled graphs, while attention substantially enhances generation for larger graphs.
Abstract
from arXiv · showhide
The celebrated Sequence to Sequence learning (Seq2Seq) technique and its numerous variants achieve excellent performance on many tasks. However, many machine learning tasks have inputs naturally represented as graphs; existing Seq2Seq models face a significant challenge in achieving accurate conversion from graph form to the appropriate sequence. To address this challenge, we introduce a novel general end-to-end graph-to-sequence neural encoder-decoder model that maps an input graph to a sequence of vectors and uses an attention-based LSTM method to decode the target sequence from these vectors. Our method first generates the node and graph embeddings using an improved graph-based neural network with a novel aggregation strategy to incorporate edge direction information in the node embeddings. We further introduce an attention mechanism that aligns node embeddings and the decoding sequence to better cope with large graphs. Experimental results on bAbI, Shortest Path, and Natural Language Generation tasks demonstrate that our model achieves state-of-the-art performance and significantly outperforms existing graph neural networks, Seq2Seq, and Tree2Seq models; using the proposed bi-directional node embedding aggregation strategy, the model can converge rapidly to the optimal performance.
1 INTRODUCTION
Graph2Seq addresses the mismatch between graph-structured inputs and sequence-only models by combining a graph encoder with an attention-based sequence decoder. Its directed-neighborhood aggregation and node attention support graph-to-sequence tasks, with strong results across three task families.
- Motivation: Seq2Seq models are limited to sequence inputs, while many tasks require graphs to represent complex pair-wise relationships.Examples include semantic graph-to-text generation, robot path planning, and bAbI path finding.
- Motivation: Converting graphs into sequences can lose structural information, especially when the input is naturally graph-structured.This information loss can reduce Seq2Seq performance on graph-to-sequence problems.
- Approach: Graph2Seq uses a graph encoder to learn node and graph embeddings, followed by an attention-based RNN decoder that aligns output predictions with graph nodes.The decoder uses graph embeddings as its initial hidden state and context vectors associated with nodes and previous predictions.
- Approach: The graph encoder uses bi-directional aggregation for directed and undirected graphs, while attention learns alignments between nodes and sequence elements for large graphs.These are presented as the model’s principal architectural contributions.
- Results: Graph2Seq achieves state-of-the-art performance on three graph-to-sequence tasks and significantly outperforms graph neural networks, Seq2Seq, and Tree2Seq models.The reported tasks are bAbI, Shortest Path, and Natural Language Generation.
2 RELATED WORK
Related work spans graph representation learning, graph neural networks, and encoder-decoder models. Graph2Seq extends neighborhood aggregation to directed graphs and combines node representations into graph embeddings for general graph-to-sequence learning.
- Graph Representation Learning: Graph representation learning maps graph nodes into low-dimensional vector spaces using matrix-factorization or random-walk-based approaches.Matrix-factorization methods are transductive, whereas random-walk methods explore neighborhood information.
- Graph Representation Learning: GraphSAGE learns inductive node embeddings by aggregating local-neighborhood information from node attributes or degrees.It can generate embeddings for previously unseen data.
- Graph2Seq’s Distinction: Graph2Seq extends GraphSAGE by separating forward and backward neighbors and using distinct aggregation functions for directed graphs.It also introduces pooling-based and supernode-based graph-embedding schemes.
- Neural Networks on Graphs: Graph neural networks extend neural architectures such as RNNs and CNNs to learn representations of nodes or entire graphs.Many earlier approaches have difficulty scaling to large graphs.
- Encoder-Decoder Models: Graph2Seq differs from prior specialized graph-to-sequence work by targeting general-purpose applications and designing graph-embedding techniques for its decoder.The related approaches often use domain-specific information or directly apply existing GNNs.
3 GRAPH-TO-SEQUENCE MODEL
The model encodes node attributes and directed neighborhoods into bi-directional node representations, constructs graph embeddings, and decodes sequences with attention over node states. Multiple aggregation and graph-embedding choices provide the main architectural components.
- Architecture: Graph2Seq consists of a graph encoder, a sequence decoder, and node attention that uses graph and node embeddings during sequence generation.The encoder first creates node embeddings and then constructs graph embeddings.
- Node Embedding Generation: Node encoding begins with attribute vectors and separates each node’s neighbors into forward and backward sets according to edge direction.The two neighborhood types represent outgoing and incoming connections.
- Node Embedding Generation: The encoder repeatedly aggregates neighborhood representations, combines them with each node’s current state, and updates the node representation through a nonlinear layer.Distinct aggregators are learned at different hops, and final forward and backward states are concatenated.
- Aggregator Architectures: Mean, LSTM, and pooling aggregators are examined, with pooling using element-wise max operations to capture information across neighborhoods.The aggregator must handle unordered neighbor sets; max-pooling is described as capturing different neighborhood information.
- Graph Embedding: Graph embeddings are formed either by pooling transformed node embeddings or by adding a supernode that receives directed edges from the other nodes.The pooling approach considers max-, min-, and average-pooling.
- Attention-Based Decoder: The decoder computes each context vector as a weighted sum of node representations, with alignment scores depending on the previous decoder state and the corresponding node.The alignment model is jointly trained with the rest of the system, and inference uses beam search with size 5.
4 EXPERIMENTS
Experiments evaluate Graph2Seq on bAbI Path Finding, Shortest Path, and WikiSQL natural-language generation, alongside sequence, tree, and graph-based baselines. Results show strong performance from graph encoding, bidirectional aggregation, and attention, especially as graph size or complexity increases.
- bAbI Task 19: Graph2Seq makes perfect predictions on bAbI Task 19, outperforming LSTM, GGS-NN, and GCN with the proposed decoder.The comparison highlights the value of directly encoding graph structure and modeling information flow in both directions.
- Shortest Path Task: Graph2Seq achieves 100% accuracy on SP-S and substantially better performance than GGS-NN on the larger SP-L dataset.GGS-NN degrades on larger graphs, whereas dual-direction aggregation maintains Graph2Seq performance as graph size grows.
- Natural Language Generation Task: Graph2Seq significantly outperforms Seq2Seq, Tree2Seq, and Graph2Seq baselines on WikiSQL natural-language generation.The results support using a graph encoder for SQL queries, whose structure is treated as graph-shaped despite its sequential expression.
- Aggregator Impact: Graph2Seq-MA performs best on SDPDAG and SDPSEQ, while also outperforming other variants on more complicated structured data.Its bidirectional aggregator captures information from both directions; one-direction variants are comparable on SDPDCG.
- Hop Size Impact: Graph2Seq-MA reaches optimal performance with about half the hop size required by one-direction variants, while all variants converge as hop size increases.Smaller hop sizes can reduce computation and runtime for large graphs, and even one-direction variants outperform GCN at matched hop sizes.
- Attention Impact: Attention improves every Graph2Seq variant by at least 14.9%, enabling the model to handle larger graphs without compressing all information into one fixed vector.The attention mechanism operates during decoding over node embeddings.
5 CONCLUSION
Graph2Seq addresses graph-to-sequence learning with a flexible encoder-decoder model and performs strongly across synthetic and real application tasks.
- Graph2Seq uses an encoder-decoder architecture for graph-to-sequence learning.
- Bi-directional node embedding aggregation supports representations for directed acyclic, directed cyclic, and sequence-styled graphs.
- Graph2Seq significantly outperforms existing graph neural networks, Seq2Seq, and Tree2Seq baselines across three synthetic and real application tasks.
- Attention over node representations improves the model’s ability to produce correct target sequences from large graphs.
- The authors expect Graph2Seq to be broadly applicable because symbolic data is often represented as graphs while desired outputs are sequences.
A PSEUDO-CODE OF THE GRAPH-TO-SEQUENCE ALGORITHM
The algorithm generates node representations by iteratively aggregating directed neighborhood information in forward and backward directions, then concatenates the final representations.
- Algorithm 1 takes a graph, initial node features, hop count, weight matrices, nonlinear activation, aggregators, and neighborhood functions as input.
- At hop zero, forward and backward node representations are initialized with the input node feature vectors.
- The final node representation is the concatenation of the forward and backward representations after the last iteration.
- Each node’s forward representation aggregates information from its forward neighborhood, while its backward representation aggregates information from its backward neighborhood.
- At each iteration, aggregated neighborhood information is combined with the node’s current representation and transformed through a nonlinear fully connected layer.
B STRUCTURED REPRESENTATION OF THE SQL QUERY
For the natural language generation task, Graph2Seq, Seq2Seq, and Tree2Seq require the SQL query to be represented as a graph, sequence, or tree.
- The SQL query is converted into a graph for Graph2Seq, a sequence for Seq2Seq, and a tree for Tree2Seq.
B.1 SEQUENCE REPRESENTATION
The SQL query sequence is constructed with a fixed template containing selection, aggregation, splitting symbols, and conditions.
- The sequence template begins with SELECT, an aggregation function, a split symbol, and the selected column.
- It then appends WHERE, the first condition, additional split symbols, and subsequent conditions.
B.2 TREE REPRESENTATION
The SQL query is represented as a tree and as a graph, providing two structural views of the same query.
- The SQL query has a tree representation.
- In the tree, SELECT LIST and WHERE CLAUSE are the root's two child nodes.
- The SQL query also has a graph representation.
B.3 GRAPH REPRESENTATION
The SQL-to-graph transformation creates nodes and edges for SELECT elements, aggregation functions, conditions, shared constraints, and logical operators.
- SELECT Clause: The transformation creates a SELECT node connected to nodes for selected columns.Aggregation functions add an aggregation node connected to the relevant column node.
- SELECT Clause: Aggregation functions such as count or max are represented by nodes labeled with the function names.
- WHERE Clause: Each WHERE condition is converted into nodes, and constraint nodes sharing a text attribute are integrated.The example integrates repeated constraint nodes such as >val0.
- WHERE Clause: Logical-operator nodes such as AND, OR, and NOT connect with the column nodes involved in the conditions.
C MORE RESULTS ON THE IMPACT OF HOP SIZE
Hop size controls how much graph neighborhood information node embeddings aggregate, with performance improving until dataset-dependent saturation; bidirectional aggregation and attention are especially useful for large graphs.
- Node Embedding Generation: The node-embedding generator depends on the aggregator, hop size K, and neighborhood function.The hop size and neighborhood function determine which neighbors are aggregated for each node embedding.
- Hop Size: Graph2Seq-MA-F and Graph2Seq-MA-B reach best performance at hop size 7 on SDP100 and 85 on SDP1000.Further increases do not improve overall performance in either dataset.
- Hop Size: The best hop size for Graph2Seq-MA-F approximately matches graph diameter, enabling each node to aggregate all reachable-node information.The average graph diameters are 6.8 for SDP100 and 80.2 for SDP1000.
- Bidirectional Aggregation: 99.2% accuracy is achieved by Graph2Seq-MA on SDP100 once hop size exceeds 4, versus over 7 for Graph2Seq-MA-F.Graph2Seq-MA reaches peak performance at approximately the graphs' average radii.
- Bidirectional Aggregation: Bidirectional information lets Graph2Seq-MA achieve best performance with less graph traversal than Graph2Seq-MA-F or Graph2Seq-MA-B.This can reduce computation and runtime for large graphs.
- Attention: Removing attention decreases performance by at least 9.8% on SDP100 and 14.9% on SDP1000.The attention mechanism helps the model handle larger graphs by avoiding compression into only a fixed-length vector.