Enhancing Complex Reasoning in Knowledge Graph Question Answering through Query Graph Approximation (2025)

Abstract: Knowledge-grounded Question Answering (QA) aims to provide answers to structured queries or natural language questions by leveraging Knowledge Graphs (KGs). Existing approaches are mainly divided into Knowledge Graph Question Answering (KGQA) and Complex Query Answering (CQA). Both approaches have limitations: the first struggles to utilize KG context effectively when essential triplets related to the questions are missing in the given KGs, while the second depends on structured first-order logic queries. To overcome these limitations, we propose a novel framework termed Aqua-QA. Aqua-QAapproximates query graphs from natural language questions, enabling reasoning over KGs. We evaluate Aqua-QA on challenging QA tasks where KGs are incomplete in the context of QA, and complex logical reasoning is required to answer natural language questions. Experimental results on these datasets demonstrate that Aqua-QA outperforms existing methods, showcasing its effectiveness in handling complex reasoning tasks in knowledge-grounded QA settings.

## introduction knowledge graphs (kgs) are structured representations of factual knowledge, typically encoded as triples in the form of @xcite , known as facts @xcite . a prominent set of applications leveraging kgs includes answering structured queries and answering natural language questions, both grounded in the kgs. to achieve this, graph query languages such as sparql are interpreted and executed by a query engine, which traverses the kg based on the given structured query to retrieve the answers. however, in this context, the incompleteness of kgs @xcite goes beyond missing facts to include the absence of essential facts required * equal contribution. for the query engine to perform a traversal. thus, simply traversing the kgs often fails to retrieve answers or misses important ones @xcite , although answers can still be indirectly inferred from existing facts within the kgs. to reason answers that can be logically derived from incomplete kgs, query embedding methods @xcite @xcite @xcite have been proposed. these methods encode query graphs-constructed from first-order logic (fol) queries-by parameterizing entities, relations, and logical operators such as conjunction, disjunction, and negation. as they distill the core semantics of the questions into a structured form, query graphs can be seen as self-contained representations, compactly capturing structural semantics and reasoning intent @xcite . effectively encoding them helps mitigate kg incompleteness by leveraging available facts without relying heavily on connectivity. however, query embedding methods require well-defined fol inputs despite the challenges of converting natural language into fol @xcite . as a result, these models struggle to reason when a natural language question is poorly translated into an fol query. in contrast, knowledge graph question answering (kgqa) aims to directly answer natural language questions by reasoning over kgs. from the widely used benchmarks in kgqa, webqsp @xcite , and cwq @xcite , ensure that all essential facts required to answer each question are present within the corresponding kg. namely, kgs are complete in the context of qa. in addition, such datasets do not consider negation operations, the identification of which is critical to logical reasoning @xcite . these assumptions have shaped kgqa approaches toward retrieving supportive information (e.g., triples @xcite , paths @xcite , or subgraphs @xcite ) to aid in answering questions. however, similar to graph query languages, the retrieval approaches require traversal over the kgs, which suffer from the aforementioned limitation due to incompleteness. furthermore, when questions involve multiple logical operators, especially the negation operation, retrieving a larger portion of the kgs becomes necessary to capture indirect paths or extended multi-hop connections. this leads to the inclusion of noisy information and an intractably large volume of retrieved data, undermining the key advantage of retrieval approaches, which reduces the reasoning space. additionally, when natural language questions do not contain explicit mentions that directly correspond to entities or relations in the kgs, it becomes challenging to identify the topic entity-the starting point of retrieval-or to translate the question into fol. this increases the likelihood of retrieving irrelevant information or an fol query that does not capture the intent of the question, which impairs the reasoning accuracy. to address the above problems, we propose aqua-qa, a novel approach that leverages the contextual information in natural language questions to approximate query graphs, bypassing the traversal of kgs for kgqa. for the approximation of query graphs, we introduce three key components: align module, query decomposition module, and relation extraction module. align module extracts both kg information, such as entity and relation, and structural information, including logical operators and question type, in the form of embeddings. query decomposition module decomposes complex questions into sub-questions, serving as anchor or variable nodes that represent unknown entities in the intermediate reasoning steps within the query graph. relation extraction module extracts relations that constitute the question as discrete tokens. finally, the extracted information is combined to construct a sequence that serves as a query graph, and reasoner performs prediction using a pretrained knowledge graph embedding (kge) method based on the constructed sequence. to capture negation nuances, we introduce an additional layer and special token for negated relations. extensive experiments on three datasets demonstrate that our model consistently outperforms baselines on complex questions with multiple logical operators and missing facts. ## methodology in this section, we introduce aqua-qa, which leverages contextual information of natural language to approximate a query graph and perform reasoning based on it. our methodology consists of 1) an align module, 2) a query decomposition module, and 3) a relation extraction module, which effectively approximate a structured query from a given question. moreover, we propose 4) a reasoner that leverages a pretrained kge method to infer the answer entity using the outputs from components 1), 2), and 3). the overall framework is illustrated in figure 1 , and the illustration of the align module is in figure 6 . ## experiments in this section, we empirically validate the effectiveness of aqua-qa, answering the following research questions. rq1: can aqua-qa achieve better qa performance than baselines across multiple datasets? rq2: how does each module in aqua-qa affect performance? rq3: can aqua-qa effectively deal with the challenges as follows: 1) incompleteness of kgs, where essential facts for answering questions may be missing, 2) complexity of questions with multiple logical operators, 3) ambiguity in questions that lack terms directly corresponding to entities in kgs? ## conclusion we propose aqua-qa, a framework that directly approximates query graphs from natural language questions without requiring structured inputs. this approach addresses limitations such as the incompleteness of kgs, where the information necessary to answer a given question is not explicitly provided within the kgs. it also handles the complexity inherent in natural language questions. our experiments demonstrate the effectiveness of aqua-qa in these extreme settings, highlighting its robustness in multiple datasets and its ability to capture the structural intent of complex questions. by outperforming existing methods, aqua-qa advances knowledge-grounded qa, providing a flexible framework for complex reasoning.