Source-linked AI summary
Graph-to-Sequence Learning using Gated Graph Neural Networks
Daniel Beck, Gholamreza Haffari, Trevor Cohn
TL;DR
Prior graph-to-sequence methods either linearize graphs or depend on limitations such as edge-label parameter growth, motivating a structure-preserving alternative. The paper combines GGNN encoding with a Levi graph transformation that gives nodes and edges hidden representations, and reports better performance than strong baselines on AMR generation and syntax-based NMT.
Problem
Earlier graph-to-sequence approaches rely on linearization or edge-label parameterizations that can discard graph information or cause parameter explosion.
Method
The model uses a GGNN encoder with a Levi graph transformation that turns edges into nodes and supplies graph-specific hidden representations.
Results
The architecture outperforms baselines in AMR generation and syntax-based NMT.
Takeaways & Limitations
Graph transformations can address graph-network deficiencies and add linguistic biases without changing the underlying model architecture.
Takeaways & Limitations
The NMT experiments did not tune the architecture, and the authors speculate that tuning could yield better results.
Abstract
from arXiv · showhide
Many NLP applications can be framed as a graph-to-sequence learning problem. Previous work proposing neural architectures on this setting obtained promising results compared to grammar-based approaches but still rely on linearisation heuristics and/or standard recurrent networks to achieve the best performance. In this work, we propose a new model that encodes the full structural information contained in the graph. Our architecture couples the recently proposed Gated Graph Neural Networks with an input transformation that allows nodes and edges to have their own hidden representations, while tackling the parameter explosion problem present in previous work. Experimental results show that our model outperforms strong baselines in generation from AMR graphs and syntax-based neural machine translation.
1 Introduction
Graph-to-sequence learning covers tasks such as realizing semantic graphs and translating syntax-annotated sources into sequences. Earlier grammar-based and neural approaches require alignments or linearization, whereas the proposed model preserves graph structure and outperforms strong baselines across AMR generation and syntax-based NMT.
- Motivation: Graph-to-sequence learning maps graph representations of meaning or syntax into output sequences for generation and translation.Examples include realizing semantic graphs into surface forms and transforming tree-annotated source sentences into translations.
- Limitations of prior work: Grammar-based methods require node-token alignments, while linearized neural methods discard parts of the original graph structure.Automatically generated alignments can propagate grammar-construction errors.
- Proposed approach: The proposed g2s model uses Gated Graph Neural Networks to incorporate full graph structure without information loss.The model also transforms edges into nodes to address parameter explosion and provide graph-specific edge representations.
- Evaluation: The model is benchmarked on AMR generation and syntax-based NMT, outperforming strong s2s baselines in both tasks.For NMT, sequential edges between contiguous words replace the need for standard RNN encoders.
- Evaluation: Graph transformations add linguistic biases to inputs without requiring changes to the model architecture.This supports the claimed generality of the approach across graph-to-sequence settings.
2 Neural Graph-to-Sequence Model
The model replaces a conventional sequence encoder with a GGNN that propagates information over graph structure, while retaining attention and recurrent decoding components. Reverse edges, self-loops, and positional embeddings support bidirectional propagation and preserve hierarchy information.
- Gated graph encoding: GGNNs extend graph networks with gating mechanisms analogous to Gated Recurrent Units and support learning through modern backpropagation.The architecture is motivated by limitations of earlier fixed-point recurrent graph networks.
- Gated graph encoding: A directed graph is represented with node and edge sets plus node-label and edge-label vocabularies, and input nodes are mapped to embeddings.The paper formally defines its GGNN over this labelled graph representation.
- Architecture: The encoder is a GGNN that receives node embeddings and produces node hidden states using graph structure as context.Attention uses a bilinear mechanism and decoding uses a two-layer LSTM, following standard s2s components.
- Architecture: The model can incorporate graph structure directly instead of relying on graph linearization, while alternative attention and decoder mechanisms remain possible.This distinguishes the graph encoder from the standard s2s sequence-processing setup.
- Graph context: Reverse edges and self-loops are added so information propagates more evenly in rooted directed acyclic graphs.Positional embeddings indexed by distance from the root preserve hierarchy after reverse connections make propagation effectively bidirectional.
3 Levi Graph Transformation
The Levi graph transformation converts original edges into nodes, addressing GGNN parameter growth and giving edges instance-specific hidden states. The transformed graph retains limited practical edge labels through added reverse and self-loop connections and can be applied independently of the model architecture.
- Motivation: GGNNs require three linear transformations per edge type, so many labels can cause parameter explosion; grouping labels loses information.AMR contains around 100 predicates that correspond to edge labels.
- Motivation: Edge labels also need graph-specific representations because their interpretation can depend on the surrounding graph content.The paper gives two ARG1 edges whose surface realizations differ according to context.
- Transformation: The Levi transformation turns each original edge into an additional node and connects it to the incident nodes in a bipartite graph.The new node vocabulary combines original node and edge labels, while the transformed graph has no labelled original edges.
- Benefits: Because original edge labels become embeddings, the transformation avoids parameter explosion and produces hidden states that the decoder can attend to.This addresses both the parameterization problem and the absence of instance-specific edge states.
- Implementation: In practice, reverse and self-loop edges leave only three practical edge labels: default, reverse, and self.The transformed graphs, rather than the illustrative original graphs, are fed into the architecture.
- Scope: The transformation applies to any graph and is independent of the model architecture, although broader applications are left for future investigation.The authors speculate it may also benefit other graph-based encoders such as GCNs.
4 Generation from AMR Graphs
The AMR generation experiments compare linearised-graph s2s baselines with g2s models on test-set generation, using multiple evaluation metrics and repeated runs. The g2s approach significantly outperforms corresponding s2s baselines, and an example suggests that preserving reentrancies reduces overgeneration.
- Experimental setup: AMR generation uses rooted DAGs, making generation nontrivial because the graphs lack gold-standard alignment information.The experiments use the LDC2017T10 corpus and its default training, development, and test split.
- Models: The s2s baselines encode linearised graphs with a BiLSTM followed by a unidirectional LSTM, while g2s models use an 8-layer GGNN encoder.Dimensionalities are fixed at 512 for the s2s models and mostly 512 for g2s, with a 576-dimensional GGNN encoder to maintain comparable parameter counts.
- Training and evaluation: Models are trained with Adam, batch size 16, early stopping on development perplexity, and 0.5 dropout on source embeddings.Each model is run five times with different random seeds; results include the median model and a five-model ensemble.
- Training and evaluation: Evaluation reports case-insensitive BLEU and sentence-level CHRF++, using bootstrap resampling and Wilcoxon signed-rank testing respectively.The evaluation design addresses concerns about relying solely on BLEU with bootstrap resampling.
- Results: The g2s approach significantly outperforms corresponding s2s baselines for both individual models and ensembles while using comparable parameter counts and no scoping heuristics.Table 1 reports that all score differences between the authors’ models and corresponding baselines are significant at p<0.05.
- Results and analysis: In a reentrancy example, the s2s output overgenerates “India and China,” whereas the g2s output avoids overgeneration and nearly matches the reference.The example is presented as evidence that retaining full graphical structure benefits AMR generation, alongside the quantitative results.
5 Syntax-based Neural Machine Translation
The section evaluates graph-to-sequence models for syntax-based NMT using dependency trees, with sequential connections added to preserve word order. The resulting g2s+ models outperform baselines on BLEU, although CHRF++ favors PB-SMT.
- Experimental setup: The experiments use source dependency trees for English-German and English-Czech translation in a medium-resource setting.English is tokenised and parsed, while German and Czech are segmented with BPE.
- Experimental setup: Dependency trees are transformed into Levi graphs, and g2s+ additionally connects words according to their original surface order.Reverse and self-loop edges are also included in the full graph representation.
- Results and analysis: The g2s models without sequential information lag behind baselines, while g2s+ models outperform them on BLEU under the same parameter budget.The improvement holds for both single-model and ensemble scenarios.
- Results and analysis: The g2s+ results show that sequential biases can be incorporated without RNNs or architectural modification.The same architecture was used as in AMR generation, with encoder dimensionality adjusted to match baseline capacity.
- Results and analysis: CHRF++ favors PB-SMT for both language pairs and shows improved s2s performance for English-Czech.The authors report that CHRF++ correlates better with human judgments than BLEU and leave the differing trends for future work.
6 Related work
Prior graph-to-sequence research includes grammar-based transduction, graph neural networks, and syntax-aware NLP applications. The paper positions its GGNN-based generation model against these approaches while retaining full graph structure.
- Graph-to-sequence modelling: Early graph-to-sequence approaches used Hyperedge Replacement Grammars to map graph portions to output token sequences.Prior work included parsing algorithms, complexity analysis, and semantic-based machine translation experiments.
- Neural networks for graphs: Graph Neural Networks and Gated Graph Neural Networks were developed for reasoning over general graphs, including node classification and path finding.The paper applies GGNNs instead to string generation from input graphs.
- Neural networks for graphs: Graph Convolutional Networks provide an alternative neural representation, while GGNNs combine tied layer-wise parameters with gating mechanisms.The paper describes GGNNs as capable of propagating information across longer graph distances without increasing parameter count through additional layers.
- Applications: Applications include AMR generation and syntax-aware NMT, with earlier work using grammars, linearisation, source syntax, target syntax, or latent syntactic variables.The paper identifies Bastings et al. (2017) as the most similar prior work for its syntax-based NMT experiments.
7 Discussion and Conclusion
The proposed graph-to-sequence architecture outperforms baselines on AMR generation and syntax-based NMT while addressing information loss and parameter explosion. Its graph transformations support edge and linguistic-bias information, but fixed-depth GGNNs and shared node-edge representations remain limitations.
- The architecture outperforms baselines on AMR generation and syntax-based NMT while addressing linearisation-related information loss and parameter explosion.
- Levi graph transformation represents edges as nodes, allowing the decoder to attend to edges and added sequential dependency-tree connections.
- Graph transformations add linguistic biases through extra node or edge information without changing the underlying model architecture.
- GGNNs use a fixed number of layers despite variable graph sizes, limiting adaptation to input graph diameter.
- Levi transformation places edge labels and nodes in a shared vocabulary and semantic space, although these are different entities.
A Simplification and Anonymisation for AMR graphs
AMR preprocessing simplifies graphs and anonymises entities and dates before graph transformation. The procedure removes selected semantic details, replaces names with indexed placeholders, clusters entity types, and reconstructs dates using recorded mappings.
- Preprocessing uses original LDC alignments and simplifies the AMR graph before converting it to a bipartite equivalent.
- Simplification: Sense information is removed from concepts, and wikification subgraphs beginning with :wiki are deleted.
- Entity anonymisation: Named-entity subgraphs are replaced by indexed anonymised nodes, with aligned surface tokens replaced by the same concept name during training.
- Entity clustering: Entities are clustered into four coarse-grained types in both graph and surface forms, such as country 0 becoming loc 0.
- Date anonymisation: Date entities are anonymised into separate day, month, and year tokens, then rendered at test time using predicted tokens and a recorded map.
B Model Hyperparameters
The implementation is based on Sockeye for neural machine translation, with unspecified hyperparameters inherited from Sockeye defaults.
- The implementation uses the Sockeye toolkit for Neural Machine Translation.
- Hyperparameters not specifically reported in the paper are set to Sockeye's default values.
- The section records additional hyperparameters for completeness beyond the paper's specifically mentioned settings.
B.1 Vocabulary
The appendix specifies vocabulary thresholds, sequence limits, attention, encoder, and dimensionality settings for AMR and NMT experiments.
- Vocabulary: AMR source nodes and target surface tokens use minimum frequency 2; NMT uses 2 for source and 1 for BPE-token targets.
- Architecture: Baseline encoders use a BiLSTM followed by a unidirectional LSTM, while every decoder uses a 2-layer LSTM.
- Attention: The attention module uses a bilinear general scoring function.
- Sequence length: Training maximum sequence length is 200 for AMR, 100 for NMT s2s baselines, and 200 for NMT g2s models.
- Dimensionality: All dimensionalities are 512 except GGNN hidden states: 576 for AMR g2s and 448 for NMT g2s+ models.
B.3 Training
Training uses shared optimization, regularization, checkpointing, and decoding settings across s2s baselines and g2s/g2s+ models, with selected batch-size and stopping choices based on development performance. Models are trained with cross-entropy, early stopping, and beam-search decoding, with AMR-specific unknown-token replacement.
- Training setup: Training uses batch size 16 and bucketing with bucket size 10; the smaller batch improved AMR development results but increased training time.The authors report that the medium-sized datasets kept the slower training time manageable.
- Training control: Models are optimized with cross-entropy, checkpointed after each full training epoch, and stopped early when dev perplexity fails to improve for eight checkpoints.A maximum of 30 epochs or checkpoints is imposed, although every model stopped earlier.
- Regularization and initialization: Input embeddings receive 0.5 dropout, weights use Xavier initialization, and LSTM forget biases are initialized to 0.
- Optimization: All models use Adam with a 0.0003 initial learning rate, halving it after three epochs or checkpoints without dev-perplexity improvement, plus gradient clipping at 1.0.
- Decoding: Decoding uses beam search with beam size 5; ensembles average stepwise log probabilities and attention scores across five models, while AMR replaces unknown tokens using highest-attention nodes before deanonymization.