DRS at MRP 2020: Dressing up Discourse Representation Structures as Graphs (2020)

Abstract: Discourse Representation Theory (DRT) is a formal account for representing the meaning of natural language discourse. Meaning in DRT is modeled via a Discourse Representation Structure (DRS), a meaning representation with a model-theoretic interpretation, which is usually depicted as nested boxes. In contrast, a directed labeled graph is a common data structure used to encode semantics of natural language texts. The paper describes the procedure of dressing up DRSs as directed labeled graphs to include DRT as a new framework in the 2020 shared task on Cross-Framework and Cross-Lingual Meaning Representation Parsing. Since one of the goals of the shared task is to encourage unified models for several semantic graph frameworks, the conversion procedure was biased towards making the DRT graph framework somewhat similar to other graph-based meaning representation frameworks.

## introduction graphs are a common data structure for representing meaning of natural language sentences or texts. several shared tasks on semantic parsing have been organized, and the target meaning representations of the shared tasks were predominantly encoded as directed labeled graphs: foot_0 semantic dependency graphs @xcite , abstract meaning representation @xcite , and universal conceptual cognitive annotation @xcite . some of these graphs are presented in figure 1 . recently, @xcite packaged several meaning representation graphs in a uniform graph abstraction and serialization for cross-framework meaning representation parsing. parallel to these developments our point of departure is discourse representation theory (drt, @xcite , a well-studied framework for studying formal semantics beyond sentences. its meaning representation structures, discourse representation structure (drs), are directly translatable into formal logic. a sample drs, in its traditional box format, is illustrated in figure 2 . we will discuss the drs in more details in section 2. obviously, drss are meaning representation structures, but they are different from the already mentioned graph-based meaning representations in two aspects. first, drss are not inherently graphs. a drs is more like a formula of predicate logic which is further organized in sub-formulas and governed with additional operations that account for co-reference and presupposition. that's why drss are usually not considered as graphbased meaning representations. for example, drt was not among the frameworks of the shared task on cross-framework meaning representation parsing @xcite since the meaning representations at the shared task were all uniformly formatted as graphs. @xcite excluded drss when surveying sentence meaning representations as they "limit @xcite to meaning representations whose backbone structure can be described as a graph over words (possibly with added non-lexical nodes) [. . . ]". the second main contrast between drss and several of the graph-based meaning representations is that drss are very different from syntactic structures. drss have roots in formal semantics, and they are geared to account for negation, quantification, and semantic scope rather than for syntactic in a nutshell, to embrace drss in the second edition of the shared task on cross-framework (and cross-lingual) meaning representation pars-2 for instance, this fact is another reason for excluding drss from the survey by @xcite : "we do not include primarily logical representations which are too distant from sentence structures; this leaves out some prominent frameworks such as the groningen meaning bank [. . . ]". ing (mrp 2020; @xcite , we investigate the conversion of drss from clausal form (the form adapted to semantic parsing, see figure 1e ) into graphs. while doing so, our goal is to (i) make drgs structurally as close as possible to the graphs of other frameworks in mrp 2020 (see figure 1 ), and (ii) keeping redundant information in drgs to a minimum to prevent graphs of extensive size and to avoid inflation of the evaluation score. our efforts contribute to unified parsing models and evaluation tools across the frameworks. hopefully, it will also save the time of participants by preventing them from developing a completely new parsing model for drgs. the rest of the paper is organized as follows. first, section 2 briefly describes the building blocks of drss, and then section 3 outlines already existing approaches of converting drss into graphs. in addition to the existing ones, section 4 introduces several candidate graph-based encodings of drss. in section 5, we compare several class type symbol sdrs signature examples entity t c constant now, house, senate r discourse referent x 1 , x 2 , e 1 , e 2 , t 1 , t 2 b box label b1, b2, b3, b4, b5 predicate b s semantic role agent, name, time m comparison relation ≺, = c concept house.n.05, act.v.01 discourse connective r discourse relation contrast o drs operator negation, presupposition drg formats on the computational feasibility of finding maximum common edge subgraph (mces) because the computational feasibility is crucial for evaluating the meaning representation graphs against the gold standard. in the end, based on the findings of the mces experiment and our desire for similarity with other graph-based frameworks, we select the specific drg format that is included in mrp 2020. ## discourse representation structures drt is a framework that dates back to the early 1980s @xcite . since then, the framework has gone through several extensions and modifications to account for certain semantic or pragmatic phenomena. throughout the paper we use drss that are derived from the parallel meaning bank (pmb, @xcite . one such drs is presented in figure 2 . the drs signature is given in the pmb incorporates several extensions to drss. on a micro level, the extensions aim to make drss language-neutral by disambiguating non-logical symbols with wordnet @xcite synsets and verbnet @xcite roles, where the verbnet roles are used in combination with neo-davidsonian event semantics @xcite . on a macro level, presuppositions are modeled and explicitly represented following @xcite and projective drt @xcite while discourse is analyzed following segmented drt @xcite and flattened by treating discourse relations and drs operators in a unified way. due to these extensions, all boxes are labeled with identifiers. let's decipher what the drs in figure 2 is expressing. it consists of two parts: a set of boxes and a set of discourse connectives applied to box labels (i.e., identifiers). boxes can be seen as sub-formulas whose separation is relevant for finegrained semantics. each box includes a (possibly empty) set of discourse referents stacked on a (possibly empty) set of conditions. the example sentence contains two clauses, corresponding to boxes b2 and b4, that are related with each other via the contrast discourse relation. both b2 and b4 presuppose the existence of entities x 1 (for the house) and x 2 (for the senate), which are further characterized with concepts (using wordnet synsets) and the naming semantic role. the presuppositions are put in separate boxes labeled with b1 and b3. the presupposition relations are explicitly stated with the binary presupposition drs operator. since we use a flat visualization of drss, b5, which is negated and nested in b4 (expressed by negation(b4, b5)), is depicted outside b4. in addition to modeling verb argument structure via neo-davidsonian event semantics and semantic roles, the drs also contains information about tense. 3 3 related work there have been several approaches to represent drss as graphs. these representations are put side-by-side in figure 3 . the work by @xcite doesn't aim to convert drss into graphs as such, but it proposes to augment object-oriented knowledge representation (ookr) graphs with additional scope information to establish correspondence with drss. although the correspondence is incomplete, e.g., some ookr graphs might have no corresponding drs. the augmentation of @xcite doesn't cover drss with discourse relations, presuppositions (e.g., b1 to b2 in figure 2 ) or with an embedded box that contains base and complex conditions (like b4 in figure 2 ). nevertheless, for demonstration purposes, we still present power (1999)'s augmented graph for a felicitous, simplified drs of figure 2 . @xcite proposed converting drss into graphs, calling them discourse representation graphs (drgs). their goal was to facilitate word-level alignment between surface forms and the corresponding drss to generate texts from drss. the graph encoding, with several simplifications, is exemplified in figure 3b . 4 the simplifications decrease the number of nodes and out-4 originally basile and bos (2013) use more labels for edges that expresses type-specific information of nodes. for example, they use different edge labels to distinguish the first argument position of b from the only argument position of c while in the paper we use the same label for both. @xcite also encodes o as a reified node that introduces of-signature labels in the graph. the encoding can be seen as node-centric since the most frequent signature symbols, namely the symbols of type b and c, are modeled as labeled nodes. argument positions (a) of binary predicates are distinguished via edge labels. we call this drg format bb * . to evaluate the output of their drs parser, @xcite converted drss into graphs, demonstrated in figure 3c . this graph encoding, in contrast to bb * , is edge-centric as the symbols of type b and c are used as edge labels. moreover, compared to bb * , the encoding contains more unlabeled nodes since b and c are also modeled with reified nodes. we call @xcite al. (2018 2019) was also based on clausal form of drss. ## more graph-based encodings of drs as illustrated in the previous section, there is no agreement on how drss should be converted into graphs (or whether they should be converted at all). the range of graph encodings in figure 3 presents anything but an exhaustive list. some encoding can even be further refined and compressed without affecting the readability or expressivness. for instance, as explained in footnote 4, bb * represents a refined version of drgs proposed by @xcite . l18 can also be further compressed by discarding reified concept nodes and their outgoing a1 edges, e.g., replacing b5 in general, the choices in which drg formats might differ are several. here we will discuss some of them, namely (see also or implicitly (imp). whether a node (corresponding to b, c, or r) is in a particular b, can be depicted via an explicit connecting edge or implicitly via graph configuration. here we would like to elaborate more on (i). the box membership in drt directly accounts for a semantic scope. like discourse referents, conditions are also members of boxes. so, we also need to express the box membership of condition predicates in the graphs. all the encodings in figure 3 explicitly express box membership. for instance, agent(e 1 , x 1 ) belonging to b2 is expressed via connecting b2 to the agent node (see figure 3b ) or via the outgoing agent edge from b2 to c3. explicating all box memberships via labeled edges drg encoding args b c in-box in the pmb annotation, for almost any discourse referent, there exists the most specific concept among the concepts applied to it. for example, a discourse referent might have only two concepts, male.n.02 and person.n.01, applied to it, but among these concepts there exists the most specific concept, namely male.n.02, as male.n.02 is a hyponym of person.n.01 according to wordnet. the c choice exploits this annotation property of concepts in the pmb and labels the node of a discourse referent with the corresponding most specific concept. this type of encoding of c is shown in figure 4 . figure 4 also depicts a -• b • c • i drg encoding with implicit box membership of b. though all the box membership edges of b are made implicit in the encoding example, this is not the case in general. for example, attributive and predicative adjectives usually introduce b1, attribute, x1, s1 clause, where x1 is the attributed entity which is not necessarily introduced in the same b1 box as the attributing state s1. another example is a construction with a locative preposition and a definite noun phrase, e.g., hid a parcel under the bed, whose drs contains the following fragment: as we have shown, there are at least a dozen ways to dress up drss as graphs. some of the drg formats are verbose, some can employ default rules to ignore certain redundancies, some require out-of-signature symbols, and some prefer labeled edges over labeled nodes. there isn't enough space to illustrate the graphs listed in ## matching & evaluating drgs in graph-based semantic parsing, system outputs are conventionally evaluated against the gold standard graphs by finding the maximum common edge subgraph (mces) for each pair of produced and gold graphs, and then calculating macro-average f-score @xcite . in general, the mces problem is np-complete, and finding the maximum subgraph shared between two relatively large graphs is sometimes computationally infeasible. in this section, we experiment on how computationally expensive is the mces problem for each drg design. ## conclusion there have been several approaches that encoded drss as graphs (surveyed in section 3), but their objectives were to transform drss in a suitable format for particular applications rather than exploring and comparing different types of drg encodings. this paper fills this gap. we have systematically characterized a dozen of drg encodings and contrasted them with each other, and compared them to the drs clausal form from an evaluation perspective. we opt for the a -• b • c • i drg encoding (see figure 4 ) to represent drss at the mrp 2020 shared task. despite the encoding being lossy, it represents an excellent trade-off due to the advantages it brings: (a) the encoding has at least 23% fewer edges than other encodings, which makes the drgs more compact and easier to read; (b) given that scope information inflates drss, learning relatively compact drgs seems a good starting point for the shared task; (c) only less than 0.25% drss are lost when applying the encoding; (d) it doesn't employ the out-of-signature labels a1 and a2; (e) for the drgs obtained from the averageperforming drs parsers, the evaluation tool can find exact maximal matches for at least 98.4% of drg pairs. when abstracting from the reification of the roles as nodes, the chosen drg encoding and the graphs of other frameworks in mrp 2020 have abstractly parallel graph topologies for linguistically parallel predicate-argument structures.