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

Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 4100–4110 July 5 - 10, 2020. c⃝2020 Association for Computational Linguistics 4100 Exact yet Efficient Graph Parsing, Bi-directional Locality and the Constructivist Hypothesis Yajie Ye1 and Weiwei Sun12 1Wangxuan Institute of Computer Technology 1The MOE Key Laboratory of Computational Linguistics 2Center for Chinese Linguistics Peking University {yeyajie,ws}@pku.edu.cn 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 Gram- mars (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 pars- ing 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. 1 Introduction Language production, though as important as lan- guage understanding, has received very limited theoretical and empirical research attention. A fundamental problem in modeling language pro- duction is parsing meaning representations, i.e. computing all possible analyses of a given mean- ing representation (MR) according to a (compe- tence) grammar. In theory, the worst-case com- plexities 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 realis- tic, wide-coverage grammar in a reasonable time. The major contribution of this paper is an ex- act yet efficient method to parse MRs in the framework of graph-based semantic representa- tions (Koller et al., 2019) and Hyperedge Replace- ment Grammar (Drewes et al., 1997). The abil- ity 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 under- standing. We discuss locality in a sense of termi- nal edge-adjacency and develop a locality-centric complexity analysis of the de facto algorithm in- troduced by Chiang et al. (2013). 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 hypoth- esis in theoretical linguistics. Altogether, our anal- ysis leads to a substantial improvement in practical graph parsing. An MR with the number of concep- tual nodes ranging from 5 to 50 corresponding to a Wall Street Journal sentence can receive a full- forest analysis in 0.089 second on average with a large-scale comprehensive grammar; Even seman- tic graphs with c.a. 80 conceptual nodes can be processed in less than 0.5 second. 2 A Graph-Structured Syntax-Semantics Interface Linguistically-informed graph parsing needs a pre- cise model of the syntax-semantics interface. To this end, we need to precisely describe elementary structures …

Content truncated to 500 words