Elamur Research⌕
☰
home / papers / 2018 / Graph-to-Sequence Learning using Gated Graph Neural Networks

Graph-to-Sequence Learning using Gated Graph Neural Networks

Summary

Many NLP tasks require turning a graph into text. Examples include generating sentences from semantic graphs or translating a source sentence annotated with a syntactic tree. Earlier methods had drawbacks. Grammar-based systems need node–token alignments, and linearising the graph throws away structure. Earlier neural models still leaned on RNN encoders. The authors propose a graph-to-sequence (g2s) encoder-decoder whose encoder is a Gated Graph Neural Network (GGNN). It is paired with a Levi graph transformation that turns every labelled edge into an extra node. This keeps the number of parameters small regardless of how many edge labels exist, and it gives edges their own context-dependent hidden states that the decoder can attend to. Reverse and self-loop edges plus root-distance positional embeddings preserve both bidirectional information flow and hierarchy. The model is tested on AMR-to-text generation and on syntax-aware NMT (English–German, English–Czech), where it beats strong s2s baselines without any RNN encoder. For NMT, adding edges between adjacent words replaces sequential modelling. The work shows that linguistic biases can be injected through input graph transformations alone, without redesigning the network.

Key points

  • Architecture:
    • The encoder is a GGNN with tied parameters across layers, extended with bias terms and neighbourhood normalisation.
    • The decoder is a 2-layer LSTM with bilinear (Luong) attention.
    • The model is implemented in MXNet on the Sockeye toolkit, with code at github.com/beckdaniel/acl2018_graph2seq.
  • Levi graph transformation:
    • AMR has roughly 100 edge labels, which would make per-label GGNN parameters explode. After the transformation, only three edge types remain: default, reverse and self.
    • There is no need to collapse any edge labels, which sets this approach apart from the earlier work of Bastings et al. (2017) and of Marcheggiani and Titov (2017).
  • English–Czech single-model results:
    • g2s+ (the variant with sequential edges) reached 9.8 BLEU, compared with 8.9 for s2s and 9.6 for BiRNN+GCN from Bastings et al. (2017).
    • The ensembles score 11.7 BLEU, against 11.3 for s2s.
    • Single models have about 38–39M parameters each.
  • chrF++ results: On this metric, PB-SMT scored best among single models (36.4) for both language pairs. On En-Cs, the s2s baseline also beat g2s+ on chrF++, so the gains do not hold across all metrics.
  • Limitations noted by the authors:
    • The number of GGNN layers is fixed, regardless of graph size.
    • Nodes and edge labels share one vocabulary and embedding space.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Topics: Machine translation

Cited by

85 papers of our library cite it (of the 140884 whose bibliographies we read); 9 of them have a page here, 76 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/p18-1026

@inproceedings{beck2018graph,
  title = {{Graph-to-Sequence Learning using Gated Graph Neural Networks}},
  author = {Beck, Daniel and Haffari, Gholamreza and Cohn, Trevor},
  booktitle = {Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2018},
  doi = {10.18653/v1/p18-1026},
  url = {https://doi.org/10.18653/v1/p18-1026}
}

References

47 references, 22 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. We proposed a novel encoder-decoder architecture for graph-to-sequence learning, outperforming baselines in two NLP tasks: generation from AMR graphs and syntax-based NMT. Our approach addresses shortcomings from previous work, including loss of information from lineari-Roee Aharoni and Yoav Goldber… find our card
  2. Laura Banarescu, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf Hermjakob, Kevin Michel Galley, Mark Hopkins, Kevin Knight, and Daniel Marcu. 2004. What’s in a translation rule? In Proceedings of NAACL. pages 273–280. find our card
  3. Knight, Philipp Koehn, Martha Palmer, and Nathan Schneider. 2013. Abstract Meaning Representation for Sembanking. In Proceedings of the 7th Linguistic Annotation Workshop and Interoperability with Discourse. pages 178–186. find our card
  4. Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N. Dauphin. 2017. Convolutional Sequence to Sequence Learning. arXiv preprint . find our card
  5. Joost Bastings, Ivan Titov, Wilker Aziz, Diego Marcheggiani, and Khalil Sima’an. 2017. Graph Convolutional Encoders for Syntax-aware Neural Machine Translation. In Proceedings of EMNLP. pages 1947–1957. find our card
  6. Marco Gori, Gabriele Monfardini, and Franco Scarselli. 2005. A New Model for Learning in Graph Domains. In Proceedings of IJCNN. volume 2, pages 729–734. find
  7. Ondej Bojar, Yvette Graham, and Amir Kamran. 2017. Results of the WMT17 Metrics Shared Task. In Proceedings of WMT. volume 2, pages 293–301. find our card
  8. Yvette Graham, Nitika Mathur, and Timothy Baldwin. 2014. Randomized Significance Tests in Machine Translation. In Proceedings of WMT. pages 266– 274. find
  9. Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2014. Spectral Networks and Locally Connected Networks on Graphs. In Proceedings of ICLR. page 14. find
  10. Jonathan Gross and Jay Yellen, editors. 2004. Handbook of Graph Theory. CRC Press. find
  11. Kazuma Hashimoto and Yoshimasa Tsuruoka. 2017. Neural Machine Translation with Source-Side Latent Graph Parsing. In Proceedings of EMNLP. pages 125–135. find
  12. Tianqi Chen, Mu Li, Yutian Li, Min Lin, Naiyan Wang, Minjie Wang, Tianjun Xiao, Bing Xu, Chiyuan Zhang, and Zheng Zhang. 2015. MXNet: A Flexible and Efficient Machine Learning Library for Heterogeneous Distributed Systems. In Proceedings of the Workshop on Machine Learning Systems. pages 1–6. find our card
  13. Felix Hieber, Tobias Domhan, Michael Denkowski, David Vilar, Artem Sokolov, Ann Clifton, and Matt Post. 2017. Sockeye: A Toolkit for Neural Machine Translation. arXiv preprint pages 1–18. find
  14. David Chiang, Jacob Andreas, Daniel Bauer, Karl Moritz Hermann, Bevan Jones, and Kevin Knight. 2013. Parsing Graphs with Hyperedge Replacement Grammars. In Proceedings of ACL. pages 924–932. find
  15. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long Short-Term Memory. Neural Computation 9(8):1735–1780. find
  16. Bevan Jones, Jacob Andreas, Daniel Bauer, Karl Moritz Hermann, and Kevin Knight. 2012. Semantics-Based Machine Translation with Hyperedge Replacement Grammars. In Proceedings of COLING. pages 1359–1376. find our card
  17. Kyunghyun Cho, Bart van Merrienboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014. Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation. In Proceedings of EMNLP. pages 1724–1734. find
  18. Steven Kearnes, Kevin McCloskey, Marc Berndl, Vijay Pande, and Patrick Riley. 2016. Molecular Graph Convolutions: Moving Beyond Fingerprints. Journal of Computer-Aided Molecular Design 30(8):595–608. find
  19. Frank Drewes, Hans Jörg Kreowski, and Annegret Habel. 1997. Hyperedge Replacement Graph Grammars. Handbook of Graph Grammars and Computing by Graph Transformation . find
  20. Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. 2017. On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima. In Proceedings of ICLR. pages 1–16. find
  21. David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparraguirre, Rafael Gómez-Bombarelli, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. 2015. Convolutional Networks on Graphs for Learning Molecular Fingerprints. In Proceedings of NIPS. pages 2215–2223. find
  22. Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In Proceedings of ICLR. pages 1–15. find
  23. Akiko Eriguchi, Kazuma Hashimoto, and Yoshimasa Tsuruoka. 2016. Tree-to-Sequence Attentional Neural Machine Translation. In Proceedings of ACL. find
  24. Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In Proceedings of ICLR. find our card
  25. Akiko Eriguchi, Yoshimasa Tsuruoka, and Kyunghyun Cho. 2017. Learning to Parse and Translate Improves Neural Machine Translation. In Proceedings of ACL. find our card
  26. Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondrej Bojar, Alexandra Constantin, and Evan Herbst. 2007. Moses: Open source toolkit for statistical machine translation. In Proc… find
  27. Jeffrey Flanigan, Chris Dyer, Noah A. Smith, and Jaime Carbonell. 2016. Generation from Abstract Meaning Representation using Tree Transducers. In Proceedings of NAACL. pages 731–739. find our card
  28. Ioannis Konstas, Srinivasan Iyer, Mark Yatskar, Yejin Choi, and Luke Zettlemoyer. 2017. Neural AMR: Sequence-to-Sequence Models for Parsing and Generation. In Proceedings of ACL. pages 146–157. find our card
  29. Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. 2017. Modeling Relational Data with Graph Convolutional Networks pages 1–12. find
  30. Friedrich Wilhelm Levi. 1942. Finite Geometrical Systems. find
  31. Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016. Neural Machine Translation of Rare Words with Subword Units. In Proceedings of ACL. pages 1715–1725. find
  32. Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. 2016. Gated Graph Sequence Neural Networks. In Proceedings of ICLR. 1, pages 1– 20. find
  33. Linfeng Song, Xiaochang Peng, Yue Zhang, Zhiguo Wang, and Daniel Gildea. 2017. AMR-to-text Generation with Synchronous Node Replacement Grammar. In Proceedings of ACL. pages 7–13. find our card
  34. Yang Liu, Qun Liu, and Shouxun Lin. 2006. Tree-to-string alignment template for statistical machine translation. In Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL - ACL ’06. pages 609–616. find our card
  35. Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014. Dropout: A Simple Way to Prevent Neural Networks from Overfitting. Journal of Machine Learning Research 15:1929–1958. find
  36. Minh-Thang Luong, Hieu Pham, and Christopher D. Manning. 2015. Effective Approaches to Attention-based Neural Machine Translation. In Proceedings of EMNLP. pages 1412–1421. find
  37. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention Is All You Need. In Proceedings of NIPS. find
  38. Diego Marcheggiani and Ivan Titov. 2017. Encoding Sentences with Graph Convolutional Networks for Semantic Role Labeling. In Proceedings of EMNLP. find our card
  39. Dekai Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics 23(3):377–403. find our card
  40. Kenji Yamada and Kevin Knight. 2001. A Syntax-based Statistical Translation Model. In Proceedings of ACL. pages 523–530. find our card
  41. Franz Josef Och and Hermann Ney. 2002. Discriminative training and maximum entropy models for statistical machine translation. In Proceedings of the 40th Annual Meeting on Association for Computational Linguistics - ACL ’02. page 295. https://doi.org/10.3115/1073083.1073133. ↗ our card
  42. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2001. Bleu: a method for automatic evaluation of machine translation. In Proceedings of ACL. pages 311–318. find our card
  43. Xiaochang Peng, Linfeng Song, and Daniel Gildea. 2015. A Synchronous Hyperedge Replacement Grammar based approach for AMR parsing. In Proceedings of CoNLL. pages 32–41. find
  44. Maja Popović. 2017. chrF ++: words helping character n-grams. In Proceedings of WMT. pages 612–618. find our card
  45. Nima Pourdamghani, Kevin Knight, and Ulf Hermjakob. 2016. Generating English from Abstract Meaning Representations. In Proceedings of INLG. volume 0, pages 21–25. find our card
  46. Nils Reimers and Iryna Gurevych. 2017. Reporting Score Distributions Makes a Difference: Performance Study of LSTM-networks for Sequence Tagging. In Proceedings of EMNLP. pages 338–348. find our card
  47. Franco Scarselli, Marco Gori, Ah Ching Tsoi, and Gabriele Monfardini. 2009. The Graph Neural Network Model. IEEE Transactions on Neural Networks 20(1):61–80. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/beck-2018-graph-sequence-learning-gated-graph/