Expanding End-to-End Question Answering on Differentiable Knowledge Graphs with Intersection (2021)

Abstract: End-to-end question answering using a differentiable knowledge graph is a promising technique that requires only weak supervision, produces interpretable results, and is fully differentiable. Previous implementations of this technique (Cohen et al, 2020) have focused on single-entity questions using a relation following operation. In this paper, we propose a model that explicitly handles multiple-entity questions by implementing a new intersection operation, which identifies the shared elements between two sets of entities. We find that introducing intersection improves performance over a baseline model on two datasets, WebQuestionsSP (69.6% to 73.3% Hits@1) and ComplexWebQuestions (39.8% to 48.7% Hits@1), and in particular, improves performance on questions with multiple entities by over 14% on WebQuestionsSP and by 19% on ComplexWebQuestions.

## introduction knowledge graphs (kgs) are data structures that store facts in the form of relations between entities. knowledge graph-based question answering (kgqa) is the task of learning to answer questions by traversing facts in a knowledge graph. traditional approaches to kgqa use semantic parsing to parse natural language to a logical query, such as sql. annotating these queries, however, can be expensive and require experts familiar with the query language and kg ontology. end-to-end question answering (e2eqa) models overcome this annotation bottleneck by requiring only weak supervision from question-answer pairs. these models learn to predict paths in a knowledge graph using only the answer as the training signal. in order to train an e2eqa model in a fully differentiable way, @xcite proposed differentiable knowledge graphs as a way to represent kgs as tensors and queries as differentiable mathematical operations. previous implementations of e2eqa models using differentiable knowledge graphs @xcite have focused on single-entity questions using a relation following operation. for example, to answer "where was natalie portman born?", the model could predict a path starting at the natalie portman entity and following a place of birth relation to the correct answer. while this follow operation handles many questions, it often struggles on questions with multiple entities. for example, to answer "who did natalie portman play in star wars episode ii?", it is not enough to identify all the characters natalie portman has played, nor all the characters in star wars episode ii. instead, the model needs to find what character natalie portman has played that is also a character in star wars. this can be solved through intersection. an intersection of two sets a and b returns all elements in a that also appear in b. this example is illustrated in figure 1 . in this paper, we propose to explicitly handle multiple-entity questions in e2eqa by learning intersection in a dynamic multi-hop setting. our intersection models learn to both follow relations and intersect sets of resulting entities in order to arrive at the correct answer. we find that our mod-els score 73.3% on webquestionssp and 48.7% on complexwebquestions, and in particular, improve upon a baseline on questions with multiple entities from 56.3% to 70.6% on webquestionssp and 36.8% to 55.8% on complexwebquestions. ## related works traditional approaches to kgqa have used semantic parsing @xcite to parse natural language into a logical form. collecting semantic parsing training data can be expensive and is done either manually @xcite or using automatic generation @xcite which is not always representative of natural questions @xcite . another line of work in kgqa uses embedding techniques to implicitly infer answers from knowledge graphs. these methods include graft-net @xcite , which uses a graph convolutional network to infer answers from subgraphs, pullnet @xcite , which improves graft-net by learning to retrieve subgraphs, and embedkgqa @xcite , which incorporates knowledge graph embeddings. emql @xcite is a query embedding method using set operators, however these operators need to be pretrained for each kb. transfernet @xcite ) is a recent model that trains kgqa in a differentiable way, however it stores facts as an n x n matrix, where n is the number of entities, so it runs into scaling issues with larger knowledge graphs. our approach to kgqa based on @xcite has three main advantages: other methods using embedding techniques (embedkgqa, emql) or less efficient representations (transfernet) are more memory intensive and not easily distributed. our approach can incorporate new entities easily without affecting trained models. ## datasets we use two datasets in our experiments: webquestionssp @xcite is an english question-answering dataset of 4,737 questions (2,792 train, 306 dev, 1,639 test) that are answerable using freebase @xcite . during training, we exclude 30 training set questions with no answer, and during evaluation, we exclude 13 test set questions with no answer and count them as failures in our hits@1 score. all questions are answerable by 1 or 2 hop chains of inference, so we set our models to a maximum of 2 hops. to create a subset of freebase, we identify all question entities and relations in webquestionssp and build a subgraph containing all facts reachable from 2 hops of the question entities, as done in previous works @xcite . this creates a sub-graph of 17.8 million facts, 9.9 million entities, and 670 relations. we create inverse relations for each relation (e.g., place of birth returns a person's birthplace; inv-place of birth returns people born in that location), for a total of 1,340 relations. complexwebquestions @xcite is an extended version of webquestionssp with 34,689 questions (27,649 train, 3,509 dev, 3,531 test) in english requiring complex reasoning. during training, we exclude 163 questions that are missing question or answer entities, and during evaluation, we exclude 21 examples from the test set for the same reasons and count them as failures in the hits@1 score. we limit our model to 2 hops for training efficiency. to create a subset of freebase, we identify all question entities and relations in the dataset and build a subgraph containing all facts reachable within 2 hops of the question entities. this results in a subgraph of 43.2 million facts, 17.5 million entities, and 848 relations (1,696 including inverse relations). ## conclusions in this paper, we expand an end-to-end question answering model using differentiable knowledge graphs to learn an intersection operation. we show that introducing intersection improves performance on webquestionssp and complexwebquestions. this improvement comes primarily from better handling of questions with multiple entities, which improves by over 14% on webquestionssp, and by 19% on complexwebquestions. in future work, we plan to expand our model to more operations, such as union or difference, to continue improving model performance on complex questions. classification with probabilistic categorial grammars. in proceedings of the twenty-first conference on uncertainty in artificial intelligence, uai'05, page 658-666, arlington, virginia, usa. auai press.