Exact yet Efficient Graph Parsing, Bi-directional Locality and the Constructivist Hypothesis (2020)

Abstract: A key problem in processing graph-based meaning representations is graph parsing, i.e. computing all possible derivations of a given graph according to a (competence) grammar. We demonstrate, for the first time, that exact graph parsing can be efficient for large graphs and with large Hyperedge Replacement Grammars (HRGs). The advance is achieved by exploiting locality as terminal edge-adjacency in HRG rules. In particular, we highlight the importance of 1) a terminal edge-first parsing strategy, 2) a categorization of a subclass of HRG, i.e. what we call Weakly Regular Graph Grammar, and 3) distributing argument-structures to both lexical and phrasal rules.

## introduction language production, though as important as language understanding, has received very limited theoretical and empirical research attention. a fundamental problem in modeling language production is parsing meaning representations, i.e. computing all possible analyses of a given meaning representation (mr) according to a (competence) grammar. in theory, the worst-case complexities of existing algorithms are exponential or high-degree polynomial w.r.t. grammar size and input length. in practice, there are few systems that can parse large but frequent mrs with a realistic, wide-coverage grammar in a reasonable time. the major contribution of this paper is an exact yet efficient method to parse mrs in the framework of graph-based semantic representations @xcite and hyperedge replacement grammar @xcite . the ability to enumerate all possible analyses of a graph facilitates surface realization, grammar induction, recursive graph embedding, etc. the advance in efficiency is from exploiting locality of hrg rules from the rarely discussed perspective of language production, a reversed direction to language understanding. we discuss locality in a sense of terminal edge-adjacency and develop a locality-centric complexity analysis of the de facto algorithm introduced by @xcite . our analysis motivates (1) a terminal edge-first parsing strategy, (2) a categorization of a subclass of hrg, i.e. what we call weakly regular graph grammar, and (3) a computational support in the constructivist hypothesis in theoretical linguistics. altogether, our analysis leads to a substantial improvement in practical graph parsing. an mr with the number of conceptual nodes ranging from 5 to 50 corresponding to a wall street journal sentence can receive a fullforest analysis in 0.089 second on average with a large-scale comprehensive grammar; even semantic graphs with c.a. 80 conceptual nodes can be processed in less than 0.5 second. ## a graph-structured syntax-semantics interface linguistically-informed graph parsing needs a precise model of the syntax-semantics interface. to this end, we need to precisely describe elementary structures corresponding to linguistic units at (morphological,) lexical and phrasal levels, and precisely describe the merge operation of two linguistic units. under the umbrella of graph-based mrs, we employ hypergraphs and hrgs @xcite to achieve the two goals. throughout this paper, we define an edgelabeled, ordered hypergraph over finite alphabet σ as a tuple @xmath0, e, ℓ), where v is a finite set of nodes, e ⊆ v + is a finite set of hyperedges, and ℓ : @xmath1. a hyperedge can connect to more than two nodes or a single node. labels can be associated to edges but not nodes. the set of nodes connected by edge e are denoted by v (e) and the set of edges connected to a b c d pron care seem really arg1 arg1 arg1 s a b c d care seem really arg1 arg1 arg1 vp a b c care seem arg1 arg1 vrp b a arg1 care node v are denoted by e(v). we use graph and hypergraph interchangeably, and similarly for edge and hyperedge. fig. 1 presents an example that contains a raising construction. the graph associated to the sentence (indicated by s ) is derived along with a syntactic tree, in which the leaves and internal nodes are associated with graphs (indicated by x ) as lexical and phrasal interpretations. the key operation in semantic composition is to glue two graphs, say g 1 and g 2 . it is obvious that not every node in g 1 is visible to g 2 and vice versa. to emphasize on this point, we augment the representation of a hypergraph (v, e, ℓ) with a list of ordered external nodes v @xmath2, e, ℓ, v x ). the number of external nodes is denoted by rank(h). graph gluing can be manipulated by an hrg @xmath3, t , p, s), where n and t are two finite disjoint alphabets of nonterminal and terminal symbols respectively, @xmath4, and p is the finite collection of rewriting rules in the form of @xmath5. the left hand side (lhs) a belongs to n , and the right hand side (rhs) r is a hypergraph fragment over n ∪ t . see γ 1 to γ 10 in fig. 1 for example. a carefully designed hrg can be linguistically elegant, in that its rules are consistent with stateof-the-art linguistic analysis. for instance, raising and control constructions receive principled analysis with rules in fig. 1 . hrg can be comparable to other popular grammar formalisms, such as combinatory categorial grammar (ccg; @xcite . see fig. 2 for an illustration. ## graph parsing with a general hrg in the framework of graph-based mrs, a key problem is graph parsing: computing all possible analyses of a given semantic graph according to a grammar. fig. 3 demonstrates the target structure of graph parsing -derivation forest. a derivation forest allows us to efficiently enumerate every derivation. coupled with a local score function that evaluates the goodness of a rule application, a graph parser can further tell the goodness of a particular derivation tree or the full forest as a whole. though essential, graph parsing is only partially understood. in this section, we summarize the state-of-the-art algorithm for graph parsing with hrgs @xcite , and then evaluate its efficiency with a wide-coverage grammar. a b c d pron care seem really arg1 arg1 arg1 a b c d care seem really arg1 arg1 arg1 g rt g lt g t 2 1 adv vrp γ 4 1 2 3 4 5:t 6 7 8 9 10 11 12 lt rt figure 3: graph parsing with an hrg. the context-freeness of hrg allows us to represent a derivation as a tree, and sets of derivations as a derivation forest, which is the output structure of graph parsing. in the derivation forest, a dashed rectangle (node) corresponds to a subgraph, which may be immediately built with different hrg rules. each rule application is separately represented as a box. necessary and sufficient information includes the brs of g t , g lt as well as g rt and the rule itself. ## conclusion we introduce several locality-centric refinements to advance graph parsing and empirically evaluate their effectiveness. we show that exact graph parsing can be efficient even for large graphs and with large graph grammars.