Parsing Graphs with Regular Graph Grammars

Proceedings of the 6th Joint Conference on Lexical and Computational Semantics (*SEM 2017), pages 199–208, Vancouver, Canada, August 3-4, 2017. c⃝2017 Association for Computational Linguistics Parsing Graphs with Regular Graph Grammars Sorcha Gilroy University of Edinburgh s.gilroy@sms.ed.ac.uk Adam Lopez University of Edinburgh alopez@inf.ed.ac.uk Sebastian Maneth Universit¨at Bremen smaneth@uni-bremen.de Abstract Recently, several datasets have become available which represent natural language phenomena as graphs. Hyperedge Re- placement Languages (HRL) have been the focus of much attention as a for- malism to represent the graphs in these datasets. Chiang et al. (2013) prove that HRL graphs can be parsed in polynomial time with respect to the size of the in- put graph. We believe that HRL are more expressive than is necessary to represent semantic graphs and we propose the use of Regular Graph Languages (RGL; Cour- celle 1991), which is a subfamily of HRL, as a possible alternative. We provide a top- down parsing algorithm for RGL that runs in time linear in the size of the input graph. 1 Introduction NLP systems for machine translation, summariza- tion, paraphrasing, and other tasks often fail to preserve the compositional semantics of sentences and documents because they model language as bags of words, or at best syntactic trees. To pre- serve semantics, they must model semantics. In pursuit of this goal, several datasets have been pro- duced which pair natural language with composi- tional semantic representations in the form of di- rected acyclic graphs (DAGs), including the Ab- stract Meaning Representation Bank (AMR; Ba- narescu et al. 2013), the Prague Czech-English Dependency Treebank (Hajiˇc et al., 2012), Deep- bank (Flickinger et al., 2012), and the Univer- sal Conceptual Cognitive Annotation (Abend and Rappoport, 2013). To make use of this data, we require models of graphs. Consider how we might use compositional semantic representations in machine translation Anna fehlt ihrem Kater Anna’s cat misses her miss arg0 arg1 cat poss Anna Figure 1: Semantic machine translation using AMR (Jones et al., 2012). The edge labels identify ‘cat’ as the object of the verb ‘miss’, ‘Anna’ as the subject of ‘miss’ and ‘Anna’ as the possessor of ‘cat’. Edges whose head nodes are not attached to any other edge are interpreted as node labels. (Figure 1), a two-step process in which seman- tic analysis is followed by generation. Jones et al. (2012) observe that this decomposition can be modeled with a pair of synchronous gram- mars, each defining a relation between strings and graphs. Necessarily, one projection of this synchronous grammar produces strings, while the other produces graphs, i.e., is a graph grammar. A consequence of this representation is that the complete translation process can be realized by parsing: to analyze a sentence, we parse the in- put string with the string-generating projection of the synchronous grammar, and read off the syn- chronous graph from the resulting parse. To gen- erate a sentence, we parse the graph, and read off the synchronous string from the resulting parse. In this paper, we focus on the latter problem: …

Content truncated to 500 words