PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Transformer for Graph-to-Sequence Learning

Deng Cai, Wai Lam

arXiv:1911.07470v2cs.CLcs.AI

TL;DR

GNN-based graph-to-sequence models rely on local propagation, limiting efficient communication across distant nodes. Graph Transformer uses self-attention with explicit relation encoding for global graph communication, and it achieves state-of-the-art results across AMR-to-text generation and syntax-based translation tasks.

  • Problem

    GNNs restrict information exchange to local neighborhoods, making long-distance graph dependencies require many layers and potentially disrupting information.

  • Method

    Graph Transformer uses multi-head attention with explicit relation encoding to enable relation-aware global communication between arbitrary graph nodes.

  • Results

    Graph Transformer achieves new state-of-the-art results on two graph-to-sequence tasks across four benchmark datasets.

  • Takeaways & Limitations

    The model provides a self-attention-based alternative to linearized sequence models and neighborhood-limited GNNs for graph-to-sequence learning.

  • Takeaways & Limitations

    For graphs with multiple shortest relation paths, training randomly samples one path while testing averages their representations.

Abstract

from arXiv · show

The dominant graph-to-sequence transduction models employ graph neural networks for graph representation learning, where the structural information is reflected by the receptive field of neurons. Unlike graph neural networks that restrict the information exchange between immediate neighborhood, we propose a new model, known as Graph Transformer, that uses explicit relation encoding and allows direct communication between two distant nodes. It provides a more efficient way for global graph structure modeling. Experiments on the applications of text generation from Abstract Meaning Representation (AMR) and syntax-based neural machine translation show the superiority of our proposed model. Specifically, our model achieves 27.4 BLEU on LDC2015E86 and 29.7 BLEU on LDC2017T10 for AMR-to-text generation, outperforming the state-of-the-art results by up to 2.2 points. On the syntax-based translation tasks, our model establishes new single-model state-of-the-art BLEU scores, 21.3 for English-to-German and 14.1 for English-to-Czech, improving over the existing best results, including ensembles, by over 1 BLEU.

Introduction

Graph-to-sequence models commonly use GNNs, whose local propagation limits efficient communication across distant nodes. Graph Transformer addresses this with global attention and explicit relation encoding, achieving stronger results across AMR generation and syntax-based translation.

  • Motivation: GNNs update node representations from adjacent nodes, requiring at least L layers to capture dependencies between nodes L hops apart.Long propagation paths can also disrupt information before distant nodes communicate.
  • Method: Graph Transformer uses multi-head attention to model dependencies directly between any two graph nodes, regardless of their distance.This replaces strictly neighborhood-based message passing with global communication.
  • Method: Explicit and separate relation encoding preserves graph structure while avoiding Levi graphs’ shared node-edge semantic space and increased representation count.Levi transformation replaces each labeled edge with two unlabeled edges and at least doubles representation vectors, increasing decoder-side complexity.
  • Results: 1.6 and 2.2 BLEU points: Graph Transformer surpasses current neural state-of-the-art methods on LDC2015E86 and LDC2017T10, respectively.The reported gains concern AMR-to-text generation.
  • Results: Graph Transformer is consistently better than competing syntax-based neural machine translation systems, including ensemble systems.The introduction reports this pattern without specifying the corresponding scores here.

Related Work

Earlier graph-to-sequence work used grammar-based, statistical, or linearized neural methods, while later approaches encoded graphs directly with neighborhood-limited GNNs. This work instead extends self-attention to graphical data with richer relation modeling.

  • Earlier approaches: Early graph-to-sequence systems used grammar-based formalisms, phrase-based machine translation, or neural sequence-to-sequence models after graph linearization.Examples include tree-to-string transduction, traveling-salesman formulations, and node-replacement grammars.
  • Graph neural networks: Direct graph encoding became an emerging approach through GNN variants that stack layers and restrict updates to first-order neighborhoods.These models differ in their information-passing schemes, including recurrent, gated, LSTM-style, and convolutional mechanisms.
  • Self-attention and graphs: Self-attention was established for sequence-to-sequence learning, but its adaptation to graphs and its performance remained unclear.Graph extension is nontrivial because graphs require modeling complex relations rather than only sequential distance.
  • Contribution: Graph Transformer is presented as the first graph-to-sequence transduction model relying entirely on self-attention to compute representations.The model extends ideas from relative position embeddings to graph relations.

Background of Self-Attention Network

Self-attention computes representations by comparing a source vector with a set of context vectors, while positional embeddings supply sequence order. This global communication perspective motivates applying attention to graphs.

  • Multi-head attention: The Transformer uses multi-head attention in encoder and decoder blocks, with each head learning a distinct attention function.Queries and values are produced from transformed source and context vectors, and attention scores use their dot product.
  • Attention computation: Attention scores are scaled and normalized with softmax to produce the final attention output.Trainable projection matrices transform vectors before score computation.
  • Attention computation: Attention vectors distribute weight over all context inputs, after which head outputs are concatenated, projected, and passed through feed-forward and normalization components.The complete procedure is denoted ATT(x, y1:m).
  • Sequence modeling: For sequences, stacked self-attention blocks iteratively build representations while allowing direct relationships between long-distance tokens.Position embeddings expose token order by being combined with word embeddings.
  • Connection to graphs: Viewing a token sequence as an unlabeled fully connected graph connects self-attention with graph neural networks and motivates the proposed graph model.Under this view, multi-head attention acts as a message-passing scheme.

Graph Transformer

Graph Transformer enables relation-aware global communication between arbitrary graph nodes while preserving graph structure through explicit relation encodings. Its encoder models multi-hop shortest-path relations, and its decoder combines graph attention with token attention and copying.

  • Global communication: Graph Transformer replaces local neighborhood propagation with direct, relation-aware communication between any pair of graph nodes.The model uses a fully connected view while encoding pairwise graph relations explicitly.
  • Graph encoder: Relation-enhanced global attention incorporates explicit relation representations into pairwise attention scores.The relation encoding is split into forward and backward components before contributing to attention computation.
  • Relation encoder: Shortest relation paths characterize relationships between arbitrary nodes, with bidirectional GRUs converting relation sequences into distributed encodings.When multiple shortest paths exist, training samples one path and testing averages their representations.
  • Graph structure: Reverse edges, self-loops, a global node, and positional embeddings provide bidirectional, whole-graph, and absolute positional information.The global node representation initializes decoder hidden states, while positional embeddings are added at the encoder input.
  • Sequence decoder: The decoder interleaves attention over encoded nodes and previously generated tokens, using a copy mechanism alongside vocabulary generation.Copying supports dates, numbers, and named entities, while the global graph representation initializes each decoding step.

Experiments

The Graph Transformer is evaluated on AMR-to-text generation and syntax-based machine translation using standard graph-to-sequence benchmarks and metrics. It consistently outperforms prior methods, including strong neural, GNN-based, and ensemble systems, without task-specific architecture tuning.

  • Evaluation setup: The experiments cover AMR-to-text generation and syntax-based machine translation, evaluated mainly with BLEU and CHRF++.AMR uses case-insensitive scores, while machine translation uses case-sensitive BLEU.
  • AMR-to-text generation: 27.4 BLEU on LDC2015E86 outperforms the previous best neural model by 2.6 BLEU points.The comparisons exclude ensembling and additional silver data.
  • AMR-to-text generation: 29.8 BLEU on LDC2017T10 improves over the best sequence-to-sequence model by 3 points and the best GNN-based model by 2.2 points.The result also surpasses a model using constituency syntax from an external parser.
  • Syntax-based machine translation: 41.0 BLEU on English-to-German exceeds previously published single models by 2.3 BLEU points.On English-to-Czech, the model exceeds the best previous single models by 2 BLEU points and surpasses prior ensemble systems.
  • Experimental consistency: The same architecture is used across experiments, with only batch size adjusted for different dataset sizes.The authors speculate that task-specific architecture tuning could yield further improvements.

More Analysis

Additional analyses examine how performance varies with graph structure and how attention distributes across graph distances. The Graph Transformer is more stable on large-diameter graphs and uses long-distance attention, supporting global communication as a source of its gains.

  • Graph Size: Performance decreases as graph size increases, but the Graph Transformer’s advantage over Guo’19 widens for relatively larger graphs.Both models show a clear drop on extremely large graphs, while the Graph Transformer remains slightly better.
  • Graph Diameter: The GNN-based model’s performance slopes downward as graph diameter increases, whereas the Graph Transformer remains more stable.The analysis defines diameter as the longest shortest path between two nodes.
  • Reentrancies: The performance gap becomes noticeably wider when graphs contain more than one reentrancy.Reentrancies occur when the same node has multiple parent nodes or participates in multiple AMR relations.
  • How Far Does Attention Look At: Nearly half of the attention heads have average attention distances larger than 2, with far-sighted heads generally increasing in deeper layers.The longest-reaching head in the first layer has an average distance over 5, while a shortest-sighted head coexists in that layer.

Conclusions

The paper concludes that Graph Transformer enables global node-to-node communication for graph-to-sequence learning. It reports new state-of-the-art results across four benchmark datasets and two graph-to-sequence tasks.

  • Conclusions: The Graph Transformer enables global node-to-node communication instead of restricting direct message passing to first-order neighborhoods.It is presented as a graph-to-sequence model based entirely on automatic attention.
  • Conclusions: The model achieves new state-of-the-art results on two typical graph-to-sequence generation tasks with four benchmark datasets.The conclusion contrasts it with recurrent models requiring graph linearization and prior graph neural network models.
Loading 1911.07470v2…