Graph Parsing (State of the Art)

Background and Motivation

Graphs exceeding the formal complexity of rooted trees are of growing relevance to much NLP research. We interpret the term graph parsing broadly as mapping from surface strings to graph-structured target representations, which typically provide some level of syntactico-semantic analysis. Although formally well-understood in graph theory, there is substantial variation in the types of linguistic graphs, as well as in the interpretation of various structural properties. To provide a common terminology and transparent statistics across different collections of graphs in NLP, we propose to establish a ‘catalogue’ of graph banks and associated parsing results.

We anticipate a bit of a cottage industry in linguistic graph banks and graph processing tasks over the next few years, which may make it difficult to keep track of contentful similarities and differences across frameworks and approaches. This page is intended to stimulate community work towards an up-to-date resource combining the following components: (a) formal definitions of (relevant) structural graph properties; (b) in-depth descriptions of how these apply to different graph banks; (c) constantly growing surveys of graph bank statistics; and (d) a continuously evolving record of state-of-the-art processing results. Of these, components (a) and (b) are provided by Kuhlmann & Oepen (2016; in press), while (c) and (d) are maintained below.

This page was initiated by Marco Kuhlmann and Stephan Oepen, and for the time being (mid-May 2016) is very much a work in progress. We intend to have a first complete draft available for community review by early June 2016.

AMR: Abstract Meaning Representation

Abstract Meaning Representation (AMR) eschews explicit syntactic derivations and consideration of the syntax–semantics interface; it rather seeks to directly annotate “whole-sentence logical meanings” (Banarescu et al. 2013). Node labels in AMR name abstract concepts, which in large parts draw on the ontology of OntoNotes predicate senses and corresponding semantic roles. Nodes are not overtly related to surface lexical units, and thus are unordered. Although AMR has its roots in semantic networks and earlier knowledge representation approaches (Langkilde and Knight 1998), larger-scale manual AMR annotation is a recent development only. We sample two variants of AMR, viz. (a) the graphs as annotated in AMRBank 1.0 (LDC2014T12), and (b) a normalized version that we call AMR−1, where so-called “inverse roles” (like ARG0-of) are reversed. Such inverted edges are frequently used in AMR in order to render the graph as a single rooted structure, where the root is interpreted as the top-level focus.1 In Section 3 below, we map this interpretation to our concept of top nodes for both AMR and AMR−1. Flanigan et al. (2014) published the first parser targeting AMR, and the state of the art has been repeatedly updated since.

Property	AMR	AMR-1
number of graphs	10309	10309
average number of tokens	20.62	20.62
average number of nodes per token	0.67	0.67
number of edge labels	135	100
percentage of graphs that are trees	52.48	18.60
percentage of graphs with treewidth one	52.72	52.72
average treewidth	1.524	1.524
maximal treewidth	4	4
average edge density	1.065	1.065
percentage of nodes that are reentrant	5.23	18.95
percentage of graphs that are cyclic	3.15	0.71
percentage of graphs that are not connected	0.00	0.00
percentage of graphs that are multi-rooted	0.00	77.50
percentage of non-top roots	47.78	19.39

CCD: Combinatory Categorial Grammar Dependencies

Hockenmaier and Steedman (2007) construct CCGbank from a combination of careful interpretation of the syntactic annotations in the PTB with additional, manually curated lexical and constructional knowledge. In CCGbank (LDC2005T13), the strings of the venerable PTB Wall Street Journal (WSJ) corpus are annotated with pairs of (a) CCG syntactic derivations and (b) sets of semantic bi-lexical dependency triples, which we term CCD. The latter “include most semantically relevant non-anaphoric local and long-range dependencies” and are suggested by the CCGbank creators as a proxy for predicate–argument structure. While CCD has mainly been used for contrastive parser evaluation (Clark and Curran [2007], Fowler and Penn [2010]; inter alios), there is current work that views each set of triples as a directed graph and parses directly into these target representations (Du, Sun, and Wan 2015).

Property	CCD
number of graphs	39604
average number of tokens	23.47
average number of nodes per token	0.88
number of edge labels	6
percentage of graphs that are trees	1.45
percentage of graphs with treewidth one	29.27
average treewidth	1.742
maximal treewidth	5
average edge density	1.070
percentage of nodes that are reentrant	28.09
percentage of graphs that are cyclic	1.28
percentage of graphs that are not connected	12.53
percentage of graphs that are multi-rooted	99.67
percentage of non-top roots	47.78
average edge length	2.582
percentage of graphs that are noncrossing	48.23
percentage of graphs with pagenumber at most two	98.64