A Survey on Complex Question Answering over Knowledge Base: Recent Advances and Challenges

Yao et al. [9] analyzed the question syntax information and extracted four types of features from each question’s dependency parse result, i.e., the question word (qword), question focus word (qfocus), topic word (qtopic), and central verb (qverb). All the four features are combined to form a question graph, and a KB subgraph is extracted according to the topic word. All the nodes in the KB subgraph are treated as candidate answers, then question features from the question graph and candidate answers’ features form the KB subgraph are combined with pairwise concatenation to capture the semantic association. Whether a node is a corresponding answer or not is determined by a classification model based on the above features. During training, high weights are assigned to features with high semantic associations.

Methods based on feature engineering rely on manually defined and extracted features, which are time-consuming and cannot capture the whole semantic information of questions. To solve these problems, representation learning-based methods convert questions and candidate answers into vectors in the common vector space and treat KBQA as semantic matching calculation between distributed representations of questions and candidate answers. Some methods incorporate external knowledge to enrich the representations and handle the incompleteness of KB. Moreover, some methods leverage a framework of multi-hop reasoning to update these representations for complex questions.

Recent works leverage graphs to represent questions, namely query graphs, which have strong representation ability and share topology commonalities with KB. Reddy et al. [25] proposed GraphParser which takes advantage of the representational power of Combinatory Categorial Grammar (CCG) to parse questions. The proposed model creates ungrounded semantic graphs from CCG-derived semantic parses. Then these ungrounded semantic graphs are mapped to KB subgraphs through mapping edge labels to KB relations, type nodes to KB entity types, and entity nodes to KB entities. Note that math nodes remain unchanged, representing aggregation constraints. A beam search procedure is employed to find out the best semantic graph which is then converted to an executable query. GraphParser conceptualizes semantic parsing as a graph matching problem.

Inspired by [25], Yih et al. [26] proposed a framework, namely Staged Query Graph Generation (STAGG). Different from GraphParser, the nodes and edges in the query graphs are closely resemble the exact entities and relations from the KB. In other words, a query graph is a restricted subset of lambda-calculus in graph representation. Thus, it can be straightforwardly translated into an executable query. A query graph consists of four types of nodes: grounded entities which are existing entities in the KB, existential variables which are ungrounded entities, lambda variable which represents the answer, and aggregation function which conducts numerical operations over other nodes. STAGG defines three stages to generate query graphs. First of all, an existing entity linking tool is employed to obtain candidate entities and their scores. Then, STAGG explores all the relationship paths between the topic entity and the answer node. To restrict the search space, it only explores paths of length 2 when the middle existential variable can be grounded to a CVT node¹¹1A compound value type (CVT) node is a kind of auxiliary nodes in Resource Description Framework (RDF) to maintain N-ary facts. and paths of length 1 otherwise. All the paths will be scored by a deep convolutional neural network. Finally, constraint nodes are attached to the relationship path according to heuristic rules. At each of the three stages, a log-linear model is leveraged to score the current partial query graph, and the best final query graph is output to query the KB. STAGG effectively uses the KB information to crop the semantic parsing space, simplifying the difficulty of the task.

Bao et al. [2] pointed out that STAGG cannot cover some complex constraints. Thus, they extended the constraint types and operators based on STAGG, including type constraints and explicit and implicit time constraints, and systematically proposed Multiple Constraint Query Graph (MultiCG) to solve these complex questions. Generally, MultiCG still follows the framework of STAGG and only provides more rules to cover the complex questions mentioned in [2].

Yu et al. [27] assumed that poor entity linking results pull down the QA performance. To improve the recognition accuracy, they integrated entity linking and relationship path identification to make the two components enhance each other. Specifically, they proposed the Hierarchical Residual BiLSTM (HR-BiLSTM) to encode questions and all relationship paths associated with the candidate topic entities in word-level and phrase-level, and calculated the similarity scores for all the questions. Only candidate topic entities connected to those highly-scored relations will be reserved. When handling constraints in questions, HR-BiLSTM also follows the practice in STAGG.

Previous methods focus on the entity linking or constraint attachment stage, while some researchers emphasize the score function. Luo et al. [29] assumed that each semantic component in the query graph conveys only partial information of the question, and is not directly comparable with the whole question. Meanwhile, existing methods cannot capture the compositional semantics, resulting from encoding different components separately. Thus, they encoded the query graphs and questions from both local and global perspectives. With the help of dependency parsing, they split a question into different parts corresponding to different semantic components in the query graph. These parts are fed into a bidirectional GRU separately to obtain vectors, which are gathered to generate the local representation of the given question through a max-pooling operation. And another bidirectional GRU is employed to encode the original question to generate the global representation. The final question representation is the sum of the local and global representations. Similarly, different semantic components are encoded separately, and gathered to obtain the final query graph representation through a max-pooling operation. The cosine similarity between the representations of the question and the query graph replaces the score calculated in the second stage in STAGG to help rank the query graph. Maheshwari et al. [30] conducted an empirical investigation of neural query graph ranking approaches, and proposed a slot-matching model based on the self-attention mechanism, which exploits the structure of query graphs by comparing its parts with different representations of the question. Zhu et al. [31] proposed the Tree-to-Seq method to take the order of entities and relationships into consideration, and encoded query graphs with tree-based LSTM.

It is obvious that the existing framework relies on the results of the entity linking stage, but there are some questions including no topic entity, e.g., “Who died in the same place they were born in?” Hu et al. [28] proposed a State-Transition Framework (STF), which is a combination of GraphParser and STAGG. At the first step, STF labels all the entities, types, variables in the question. Then, according to the dependency parsing result of the question, STF connects these nodes through predefined four atomic operations (i.e., Connect, Merge, Expand, Fold). Meanwhile, these edges are mapped to KB relations through a CNN-based relation matching model. Upon these four operations, STF generates a semantic query graph, which is then mapped to the KB subgraph through rules to obtain the query graph. STF overcomes some shortcomings of STAGG, while it still lacks the ability to handle questions with complex aggregations.

To restrict the search space, STAGG only explores relationship paths with limited length, make it impossible to handle multi-hop questions. Some researchers propose an iterative query graph generation framework. Bhutani et al. [32] assumed that a complex query graph is constructed by several partial queries that are generated by STAGG. And the query composition is determined by the augmented pointer networks [4]. Lan et al. [33] defined three actions to construct a query graph, i.e., extend, connect, and aggregate. Specifically, an extend action extends the relationship path by one more KB relation connected to the current endpoint node, a connect action links a grounded entity to the current relationship path, and an aggregate action attaches the detected aggregation function to the current path. All three types of actions are determined by the policy network. Once an action is selected, all the possible intermediate results will be scored, and only a few will be maintained. Based on reinforcement learning, the proposed model can be trained in an end-to-end manner.

In addition to query graphs, many researchers leverage trees or high-level programming languages to represent natural language questions.

Dong et al. [34] proposed an enhanced encoder-decoder model based on the attention mechanism and reduced semantic parsing into a Seq-to-Seq problem. In addition to using a Seq-to-Seq model to convert questions to logical forms, they also proposed a Seq-to-Tree model that uses the hierarchical tree-structured decoder to capture the structure of logical forms. Xu et al. [35] pointed out that the general sequence encoder ignores useful syntactic information. Thus, they leveraged a syntactic graph to represent word order, dependency, and constituency. Meanwhile, they used the Graph-to-Seq model, in which a graph encoder encodes the syntactic graph, and the recurrent neural network decodes the logical forms based on the state vector at each time step and the context information obtained through the attention mechanism. Although these methods achieve state-of-the-art performance without relying on manually predefined rules, they both require a large number of training annotations, which are rather expensive in most KBQA scenarios.

To get rid of strong supervision, Liang et al. [24] proposed the Neural Symbolic Machine (NSM), which is a Seq-to-Seq model trained with reinforcement learning. NSM converts the natural language questions into a logical program comprised of Lisp expressions. It is based on a Manager-Programmer-Computer framework, where the manager provides weak supervision through a reward indicating whether the program answers correctly, the programmer takes questions as input and decodes a bunch of Lisp expressions, and the computer executes these expressions to obtain the answers. Specifically, the computer is a Lisp interpreter, and provides code-assistance to the programmer to restrict the decoder vocabulary and ensures the validity of expressions generated by the programmer. Once the programmer decodes a valid Lisp expression, the computer will execute it and obtain an intermediate result from the KB. All the results are stored in a key-variable memory for the followup reasoning, and the final result is output as the predicted answer. The F1 score of the answer is the terminal reward for the programmer.

In this section, we introduced the Neural Semantic Parsing-based methods, including methods that convert the Semantic Parsing into query graph generation, and methods leveraging an encoder-decoder framework. Although these methods can cover more complex questions, it is challenging to train a neural semantic parser, due to lack of gold logical forms.