Conversational Semantic Parsing using Dynamic Context Graphs (2023)

Abstract: In this paper we consider the task of conversational semantic parsing over general purpose knowledge graphs (KGs) with millions of entities, and thousands of relation-types. We focus on models which are capable of interactively mapping user utterances into executable logical forms (e.g., Sparql) in the context of the conversational history. Our key idea is to represent information about an utterance and its context via a subgraph which is created dynamically, i.e., the number of nodes varies per utterance. Rather than treating the subgraph as a sequence, we exploit its underlying structure and encode it with a graph neural network which further allows us to represent a large number of (unseen) nodes. Experimental results show that dynamic context modeling is superior to static approaches, delivering performance improvements across the board (i.e., for simple and complex questions). Our results further confirm that modeling the structure of context is better at processing discourse information, (i.e., at handling ellipsis and resolving coreference) and longer interactions.

## introduction general purpose knowledge graphs (kg), like wikidata @xcite structure information in a semantic network of entities, attributes, and relationships, allowing machines to tap into a vast knowledge base of facts. knowledge base question answering (kbqa) is the task of retrieving answers from a kg, given natural language questions. a popular approach to kbqa (see @xcite and the references therein) is based on semantic parsing which maps questions to logical form queries (e.g., in sparql) that return an answer once executed against the kg. existing work (e.g., @xcite @xcite has mostly focused on answering questions in isolation, whereas we consider the less studied task of conversational 1. who starred in mathias kneissl ? select ?x where { wd:q3298576 wdt:p161 ?x . ?x wdt:p31 wd:q502895 . } rainer werner fassbinder, volker schlöndorff, hanna schygulla 2. who was the director of that work of art ? select ?x where { wd:q3298576 wdt:p57 ?x . ?x wdt:p31 wd:q502895 . } reinhard hauff 3. does dubashi have that person as actor ? ask { wd:q76025 wdt:p161 wd:q24807818 . } no 4. which works of art are rainer werner fassbinder or laura esquivel a screenwriter of ? select ?x where { { ?x wdt:p58 wd:q44426 . ?x wdt:p31 wd:q838948 . } union { ?x wdt:p58 wd:q230586 . ?x wdt:p31 wd:q838948 . } } the american soldier, lili marleen, love is colder than death ... q3298576: mathias kneissl, q76025: reinhard hauff, q24807818: dubashi, q44426: rainer werner fassbinder q230586: laura esquivel, q838948: work of art, q502895: common name, p161: cast member, p31: instance of, p57: director, p58: screenwriter figure 1 : example interaction from spice dataset @xcite with utterances, corresponding sparql queries, and answers returned after executing the queries on the wikidata graph engine. the bottom block shows the kg elements (i.e., graph nodes) involved in this interaction. in addition to challenges arising from processing contextual information, the semantic parsing task itself involves linking entities, types, and predicates to elements in the kg (e.g., mathias kneissl to q3298576) whose topology is often complex with a large number of nodes. moreover, unlike relational databases, the schema of an entity is not static but dynamically instantiated @xcite . for example, the entity type person can have hundreds of relations but only a fraction of these will be relevant for a specific utterance. therefore, to generate faithful queries, we cannot rely on memorization and should instead make use of local schema instantiation. in general, narrowing down the set of entities and relations is critical to parsing utterances requiring complex reasoning (i.e., where numerical and logical operators apply over sets of entities). existing work @xcite handles the aforementioned challenges by adopting various simplifications and shortcuts. for instance, since it is not feasible to encode the entire kg, only a subgraph relevant to the current utterance is extracted and subsequently linearized and treated as a sequence. entity type information that is not directly accessible via neighboring subgraphs is obtained through a global lookup (essentially a reverse index of all types in the kg). this solution is computationally expensive, as the lookup is performed practically for every user utterance, and does not scale well (the index would have to be recreated every time the kg changed). in this paper we propose a modeling approach to conversational semantic parsing which relies on dynamic context graphs. our key idea is to represent information about an utterance and its context through a dynamically generated subgraph, wherein the number of nodes varies for each utterance. moreover, rather than treating the subgraph as a sequence, we exploit its underlying structure and encode it with a graph neural network @xcite . to improve generalization, we learn implicit node embeddings by aggregating information from neighboring nodes whose embeddings are in turned initialized through a pretrained model @xcite . in addition, we introduce context-dependent type linking, based on the entity and its surrounding context which further helps with type disambiguation. experimental evaluation on the spice dataset @xcite demonstrates that modeling context dynamically is superior to static approaches, improving performance across the board (i.e., for simple and complex questions requiring comparative or quantitative reasoning). our results further confirm that modeling the structure of context is better at processing discourse information, (i.e., at handling ellipsis and resolving coreference) and longer interactions with multiple turns. ## related work previous work on semantic parsing for kbqa @xcite has focused on mapping stand-alone utterances to logical form queries. various approaches have been proposed to this effect which broadly follow three modeling paradigms. ranking methods first enumerate candidate queries from the kb and then select the query most similar to the utterance as the semantic parse @xcite @xcite . coarse-to-fine methods @xcite @xcite perform semantic parsing in two stages, by first predicting a query sketch, and then filling in missing details. finally, generation methods @xcite first rank candidate parses and then predict the final parse by conditioning on the utterance and best retrieved logical forms. our task is most related to conversational textto-sql parsing, as manifested in datasets like sparc @xcite , cosql @xcite , and atis @xcite . sparc and cosql cover multiple domains and include multi-turn user and system interactions. these datasets are challenging in requiring generalization to unseen databases, but the conversation length is fairly short and the databases relatively small-scale. atis contains utterances paired with sql queries pertaining to a us flight booking task; it exemplifies several long-range discourse phenomena @xcite , however, it covers a single domain with a simple database schema. graph-based methods have been previously employed in semantic parsing primarily to encode the database schema, so as to enable the parser to globally reason about the structure of the output query @xcite . other work @xcite uses relational graph networks to jointly represent the database schema and syntactic dependency information from the questions. in the context of conversational semantic parsing, cai and wan (2020) use a graph encoder to model how the elements of the database schema interact with information in preceding context. along similar lines, @xcite , use a graph neural network with a dynamic memory decay mechanism to model the interaction of the database schema and the utterances in context as the conversation proceeds. all these approaches encode the schema of relational databases which are significantly smaller in size (e.g., number of entities and types of relations) compared to large-scale kgs, where encoding the entire graph in memory is not feasible. closest to our work are methods which cast conversational kgqa as a semantic parsing task @xcite . these approaches build hand-crafted grammars that are not directly executable to a kg engine. furthermore, they assume the kg can be fully encoded in memory which may not be feasible in real-world settings. @xcite develop a parser which is executable with a real kg engine (e.g., blazegraph) but simplify the task by considering only limited conversation context. ## problem formulation given a general purpose knowledge graph, such as wikidata, our task is to map user utterances to formal executable queries, sparql in our case. we further assume an interactive setting where users converse with the system in natural language and the system responds while taking into account what has already been said (see figure 1 ). the system's response is obtained upon executing the query against a graph query engine. let g denote the underlying kg and i a single interaction. i consists of a sequence of turns where each turn is represented by ⟨x t , a t , y t ⟩ denoting an utterance-answer-query triple at time t (see blocks in figure 1 ). a user utterance x t is a sequence of tokens ⟨x 1 , x 2 , . . . , x |xt| ⟩, where |x t | is the length of the sequence and each ## model our modeling approach combines three components. we first ground named entities in the user utterance to kg entities, and use these linked entities to extract a subgraph that functions as context (section 4.1). the second component is responsible for type linking in the context of current and previously mentioned named entities (section 4.2). and finally, our semantic parser learns to map user utterances into sparql queries (section 4.3). ## experimental setup dataset we performed experiments on spice (perez-beltrachini et al., 2023), a recently released large-scale dataset foot_3 for conversational semantic parsing built on top of the csqa benchmark @xcite . spice consists of user-system interactions where natural language questions are paired with sparql parses and answers provided by the system correspond to sparql execution results (see figure 1 ). we present summary statistics of the dataset in ## results in this section, we evaluate the performance of our semantic parser on the spice test set. we report results on individual question types and overall. we also analyze our system's ability to handle different discourse phenomena like ellipsis and coreference as well as interactions of varying length. the effect of dynamic context we compare dcg gl , a version of our model which adopts a global lookup for type liking similar to bertsp gl and differs only in how contextual information is encoded. as we can see, our graphbased model performs better, reaching an f1 score of 72.3% compared to 59% obtained by bertsp gl which is limited by the way it encodes contextual information. recall, that bertsp gl linearizes the subgraph context, splits into subsequences and feeds it to the model chunk-by-chunk. our model alleviates this problem by efficiently encoding the kg information with a graph neural network, preserving dependencies captured in its structure. as a result, dcg gl performs better on most question types, including simple questions, and reasoning-style questions. we further compare dcg gl against a variant which uses context-dependent type linking instead (dcg cl ). we find that context-dependent type linking is slightly worse than global lookup which is expected given that it does not have access to the full list of kg types. in general, we observe that results with exact match (em) are lower than f1 or accuracy. em is a stricter metric, it does not allow for any deviation from the goldstandard sparql. however, it is possible for two queries to have different syntax but equivalent meaning, and for partially well-formed queries to evaluate to partially accurate results. in contrast to em, f1 and accuracy give partial credit and thus obtain higher scores. ## conclusions in this paper, we present a semantic parser for kbqa which interactively maps user utterances into executable logical forms, in the context of previous utterances. our model represents information about utterances and their context as kg subgraphs which are created dynamically and encoded using a graph neural network. we further propose a context-dependent approach to type linking which is efficient and scalable. our experiments reveal that better modeling of contextual information improves performance, in terms of entity and type linking, resolving coreference and ellipsis, and keeping track of the interaction history as the conversation evolves. directions for future work are many and varied. in experiments, we use an off-the shelf ner system, however, jointly learning a semantic parser and an entity linker would be mutually beneficial, avoiding error propagation. given that it is prohibitive to encode the entire kg, we encode relevant subgraphs on the fly. we could further explicitly model the relationship between kg entities and question tokens which previous work has shown is promising @xcite . finally, it would be interesting to adapt our model so as to handle non-i.i.d generalization settings.