G raph Q IR : Unifying the Semantic Parsing of Graph Query Languages with One Intermediate Representation (2022)

Abstract: Subject to the huge semantic gap between natural and formal languages, neural semantic parsing is typically bottlenecked by its complexity of dealing with both input semantics and output syntax. Recent works have proposed several forms of supplementary supervision but none is generalized across multiple formal languages. This paper proposes a unified intermediate representation for graph query languages, named GraphQ IR. It has a natural-language-like expression that bridges the semantic gap and formally defined syntax that maintains the graph structure. Therefore, a neural semantic parser can more precisely convert user queries into GraphQ IR, which can be later losslessly compiled into various downstream graph query languages. Extensive experiments on several benchmarks including KQA Pro, Overnight, GrailQA, and MetaQA-Cypher under the standard i.i.d., out-of-distribution, and low-resource settings validate GraphQ IR’s superiority over the previous state-of-the-arts with a maximum 11% accuracy improvement.

## introduction by mapping natural language utterances to logical forms, the task of semantic parsing has been widely explored in various applications, including database query @xcite and general-purpose code generation @xcite @xcite . although the methodology has evolved from earlier statistical approaches @xcite to present seq2seq paradigm @xcite , the semantic gap between natural language and logical forms still lies as the major challenge for semantic parsing. as shown in figure 1 , in graph query languages (e.g., sparql, cypher, lambda-dcs, and newly emerged kopl, etc.), graph nodes, edges and their respective properties constitute the key semantics of the logical forms @xcite , which are very different from the expression of natural language utterances. such discrepancy significantly hinders the learning of neural semantic parsers and therefore increases the demand for labeled data @xcite . however, due to the laborious efforts and language-specific expertise required in annotation, such demand cannot always be satisfied and thus becomes the bottleneck @xcite . to overcome these challenges, many works adopt complementary forms of supervision, such as the schema of database @xcite , results of the execution @xcite @xcite , and grammar-constrained decoding algorithms @xcite @xcite . although effective, the additional resources that these methods rely on are not necessarily available in practice. by normalizing the expression (berant @xcite or enriching the structure @xcite @xcite of natural language utterances, another category of works proposes various intermediate representations like amr @xcite to ease the parsing of complex queries. however, the transition from their irs to the downstream logical forms may incur extra losses in precision @xcite . besides, these representations are usually coupled to specific data or logical forms and thus cannot be easily transferred to other tasks or languages @xcite . in industry, aside from sparql, many other graph query languages such as cypher @xcite and gremlin @xcite are equally or even more commonly used in graph database interaction @xcite . however, most graph query semantic parsing works only support sparql @xcite @xcite sparql: select (count(distinct ?e) as ?count) where { ?e instance_of ?c . ?c name "film" . ?e director ?e_1 . ?e_1 name "stanley kubrick" } cypher: match (n1)-[:director]->(n2) where n1:film and n2.@xmath0: find(stanley kubrick). relate(director,backward). filterconcept(film).count() figure 1 : a a property graph extracted from wikidata @xcite . we present a relevant user query with its corresponding logical forms in different query languages and in graphq ir. while very few works target other graph query languages. meanwhile, no existing tools or ir can support the data conversion among multiple graph query languages @xcite . such lack of interoperability has not only hindered the semantic parsing of lowresource languages but also limited the potential of querying heterogeneous databases @xcite . in this paper, we propose a unified intermediate representation for graph query languages, namely graphq ir, to resolve these issues from a novel perspective. the designs of graphq ir weigh up the semantics of both natural and formal language by (a) producing the ir sequences with composition rules consistent with modern english @xcite to close the semantic gap; and (b) maintaining the fundamental graph structures like nodes, edges, and properties, such that the ir can be automatically compiled into any downstream graph query languages without any loss. instead of directly mapping the user query to the logical form, we first parse natural language into graphq ir, then compile the ir into the target graph query languages (e.g., sparql, cypher, lambda-dcs, kopl, etc.). therefore, languagespecific grammar features that initially posed a huge obstacle to semantic parsing are now explicitly handled by the compiler. additionally, with the graphq ir as a bridge, our implemented sourceto-source compiler can support lossless translation among multiple graph query languages and thus unify the annotations of different languages for eliminating the data bottleneck. to validate the effectiveness of graphq ir, we conducted extensive experiments on benchmarks kqa pro, overnight, grailqa and metaqa-cypher. results show that our approach can consistently outperform the previous works by a significant margin. especially under the compositional and few-shot generalization settings, our approach with graphq ir can demonstrate a maximum 11% increase in accuracy over the baselines. the main contributions of our work include: ## graphq ir in this section, we formalize the grammar and the expressiveness of our graphq ir based on the definition of property graph and regular path query. then we summarize the design principles of graphq ir for bridging the semantic gap between natural and formal language as well as unifying different graph query languages. ## implementation we depict the full picture of our proposed framework in figure 2 . the neural semantic parser first maps the input natural language utterance into graphq ir. thereafter, the graphq ir sequence is fed into the compiler and parsed into an abstract syntax tree for downstream graph query language code generation. ## experiments in this section, we evaluate graphq ir on several benchmarks under different task settings. ## discussion to further explore the reasons behind the superior performance of our methods, we compute and visualize the semantic distance between the natural language utterances and their corresponding logical forms or graphq ir. specifically, to simulate how a neural semantic parser processes the sequences in the above experiments, we use a pretrained bart-base model without fine-tuning to obtain the contextualized embeddings @xcite . for each sequence, we error type # # osc example inaccurate data annotation 28 -user utterance: out of newscasts that last 110 minutes, which is the shortest? gold sparql: select ?e where { ?e instance_of ?c . ?c name "newscast" . ?e duration ?pv_1 . ?pv_1 unit "minute" . ?pv_1 value ?v_1 . filter ( ?v_1 != "110"^^xsd:double ) . ?e duration ?pv . ?pv value ?v } order by ?v limit 1 generated ir: which one has the @xmath1: select ?e where { ?e instance_of ?c . ?c name "newscast" . ?e duration ?pv_1 . ?pv_1 unit "minute" . ?pv_1 value "110"^^xsd:double . ?e duration ?pv . ?pv value ?v } order by ?v limit 1 ambiguous query expression 27 27 user utterance: how is the kid's movie the spiderwick chronicles related to john sayles? gold sparql: select distinct ?p where { ?e_1 name "the spiderwick chronicles" . ?e_1 genre ?e_3 . ?e_3 name "children's film" . ?e_2 name "john sayles" . ?e_1 ?p ?e_2 } generated ir: what is the relation @xmath2: select distinct ?p where { ?e_1 name "the spiderwick chronicles" . ?e_1 genre ?e_3 . ?e_3 name "kid film" . ?e_2 name "john sayles" . ?e_1 ?p ?e_2 } unspecified graph structure 13 9 user utterance: when did tashkent become the capital of uzbekistan? gold sparql: select distinct ?qpv where { ?e_1 name "tashkent" . ?e_2 name "uzbekistan" . ?e_1 capital_of ?e_2 . [ fact_h ?e_1 ; fact_r capital_of ; @xmath3: what is the @xmath4: select distinct ?qpv where { ?e_1 name "uzbekistan" . ?e_2 name "tashkent" . ?e_1 capital ?e_2 . [ fact_h ?e_1 ; fact_r capital ; fact_t ?e_2 ] start_time ?qpv } nonequivalent semantics 32 25 user utterance: when did joseph l. mankiewicz graduate from columbia university? gold sparql: select distinct ?qpv where { ?e_1 name "joseph l. mankiewicz" . ?e_2 name "columbia university" . ?e_1 educated_at ?e_2 . [ fact_h ?e_1 ; fact_r educated_at ; fact_t ?e_2 ] end_time ?qpv } generated ir: what is the @xmath5. @xmath6: select distinct ?qpv where { ?e_1 name "joseph l. mankiewicz" . ?e_2 name "columbia university" . ?e_1 educated_at ?e_2 . [ fact_h ?e_1 ; fact_r educated_at ; fact_t ?e_2 ] start_time ?qpv } we randomly sampled 1000 queries respectively from kqa pro and overnight's validation set. we compare the semantic distance between natural language utterances and the graphq irs (i.e., nl ⇔ ir), as well as the distance between natural language utterances and their corresponding logical forms (e.g., nl ⇔ sparql). the results are listed in ## conclusion and future work this paper proposes a novel intermediate representation, namely graphq ir, for bridging the semantic gap between natural language and graph query languages. evaluation results show that our approach with graphq ir consistently surpasses the baselines on several benchmarks covering multiple formal languages, i.e., sparql, kopl, lambda-dcs, and cypher. moreover, graphq ir also demonstrates superior generalization ability and robustness under the out-of-distribution and low-resource settings. as an early step towards the unification of semantic parsing, our work opens up several future directions. for example, many code optimization techniques (e.g., common subexpression elimination) can be incorporated into ir to improve performance further. by bringing in multiple levels of ir, our framework may also be extended to support relational database query languages like sql. moreover, since the current designs of graphq ir still require non-trivial manual efforts, the automation of such procedure, e.g., in prompt-like manners, is worth future exploration.