Bring Your Own KG : Self-Supervised Program Synthesis for Zero-Shot KGQA (2024)

Abstract: We present BYOKG, a universal question-answering (QA) system that can operate on any knowledge graph (KG), requires no human-annotated training data, and can be ready to use within a day—attributes that are out-of-scope for current KGQA systems. BYOKG draws inspiration from the remarkable ability of humans to comprehend information present in an unseen KG through exploration—starting at random nodes, inspecting the labels of adjacent nodes and edges, and combining them with their prior world knowledge. Exploration in BYOKG leverages an LLM-backed symbolic agent that generates a diverse set of query-program exemplars, which are then used to ground a retrieval-augmented reasoning procedure to synthesize programs for arbitrary questions. BYOKG is effective over both small- and large-scale graphs, showing dramatic gains in zero-shot QA accuracy of 27.89 and 59.88 F1 on GrailQA and MetaQA, respectively. We further find that performance of BYOKG reliably improves with continued exploration as well as improvements in the base LLM, notably outperforming a state-of-the-art fine-tuned model by 7.08 F1 on a sub-sampled zero-shot split of GrailQA. Lastly, we verify our universality claim by evaluating BYOKG on a domain-specific materials science KG and show that it improves zero-shot performance by 46.33 F1.

## introduction the ability to query structured data stores such as knowledge graphs (kgqa) via natural language is crucial for making the information within them accessible @xcite . however, most prior works that aim to create such interfaces assume the availability of some training data (queryprogram pairs) @xcite @xcite @xcite , which, in practice, might be unrealistic. for example, in scientific domains such as materials science and clinical decision-making, training data may be completely unavailable due to high collection costs or stringent privacy regulations @xcite . further, even when training data is available, models trained on one dataset may not generalize o.o.d. to other datasets of the same kg @xcite . in this work, we, therefore, set out to answer the following question-can we develop a universal qa system that is ready for use with any kg, within a reasonable amount of time (e.g., 24 hours), and without any training data? to achieve this, a model must efficiently and accurately learn to reason over a kg with no prior knowledge of the query distribution or the kg semantics. byokg takes inspiration from the human tendency to be curious-seeking challenges and developing knowledge even in the absence of well-defined rewards @xcite . given a new kg, a human practitioner begins familiarizing themselves with the graph by inspecting random nodes and analyzing the various properties 1 found in the node neighborhoods. as this process continues (crucially, without a task-specific information need in mind), the practitioner develops an intuition for the set of questions that can be answered with the information present in the kg. to mechanize this human tendency, byokg consists of an exploration module, which combines random walks over the kg nodes with a set of graph operations (e.g. count, argmax, >=, etc.) to produce programs of varying degrees of complexity (stage 1; fig. 1 ). our explorer is symbolic in nature and has the goal of maximizing diversity within the generated programs, akin to curiosity1 for e.g., https://prop-explorer.toolforge.org/ . ## results exploration leads to substantial gains in the unsupervised setting. on both grailqa with the freebase kg ( byokg exhibits better compositional generalization than pangu. on grailqa, byokg outperforms pangu by 4.03 f1 ( byokg with exploration is competitive with supervised icl. we observe that byokg + x is able to nearly match byokg + t 10k (row 4 and 7 in byokg with exploration leads to more consistent performance across generalization splits versus supervised methods. in ## analyses in this section, we present detailed analyses of byokg. we first study the efficacy of graph exploration and its effect on downstream qa performance. we then conduct several ablations to validate the design choices made in byokginverse-consistency and l2m for question generation, inverse-consistency during reasoning, prompting with kg schema descriptions, as well as candidate pruning. on metaqa, we find that while exploration can find all schema items and sub-expressions, it misses nearly 30% of program patterns in the test distribution while the training set has perfect coverage. on grailqa, both sub-expression and pattern coverage are much lower than training, with x observing 5x fewer test patterns and 1.6x fewer test sub-expressions than the training data. these gaps explain the difference in performance between supervised methods and byokg + x , which is completely zero-shot ( ## conclusion we introduce byokg-a universal kgqa system to work with any target kg and without any humanannotated training data. byokg mimics curiositydriven learning in humans by first exploring the unseen kg, followed by using the acquired knowledge to answer questions. our method combines llms with graph traversal to explore the kg and then reason over the explored paths to answer arbitrary user queries over the graph. we further introduce techniques to improve zero-shot performance with llms, including an inverse-consistency reranking method. on two popular datasets and kgs, we demonstrate the efficacy of byokg and present detailed analyses of the several design choices.