Enhancing Complex Question Answering over Knowledge Graphs through Evidence Pattern Retrieval

Wentao Ding, Jinmao Li, Liangchuan Luo, Yuzhong Qu

Abstract

Information retrieval (IR) methods for Knowledge Graph Question Answering (KGQA) typically involve two stages: subgraph extraction and answer reasoning. However, current subgraph extraction methods often underestimate the critical importance of structural dependencies among evidence facts, leading to the inclusion of irrelevant noise. We propose Evidence Pattern Retrieval (EPR), a framework that explicitly models these structural dependencies during the extraction phase. By indexing atomic adjacency patterns of resource pairs and employing dense retrieval, EPR constructs candidate evidence patterns that are then scored and selected to extract high-quality subgraphs. Our experimental results demonstrate that EPR significantly improves performance, achieving a 13.2-point F1 score increase on the ComplexWebQuestions dataset and maintaining competitive results on WebQuestionsSP.

Introduction

Knowledge Graph Question Answering (KGQA) is a vital task in natural language processing, requiring systems to find precise answers to natural language queries within massive, structured datasets. Traditionally, KGQA follows two paradigms: Semantic Parsing (SP) and Information Retrieval (IR).

While SP methods translate questions into formal queries (like SPARQL), they often require expensive, manually annotated logical forms. IR methods are more flexible, extracting a relevant subgraph and reasoning over it. However, IR methods frequently suffer from a "noise" problem. They often treat evidence as a "bag of facts," pulling in entities and relations that appear relevant on the surface but lack the specific structural connectivity required to answer complex, multi-hop questions. This paper introduces Evidence Pattern Retrieval (EPR) to bridge the gap between IR flexibility and the structural precision of SP.

The Problem: Structural Irrelevance

Current IR-based KGQA models struggle with complex constraints. For example, if a question asks for a "country bordering Germany containing the city Stadhuis," a standard IR model might extract facts about Austria because it borders Germany and contains many cities. However, if none of those cities are "Stadhuis," the structural dependency is broken. The authors argue that the specific structural layout—the way entities and relations connect—is a powerful signal for denoising that current methods overlook.

Methodology: Evidence Pattern Retrieval (EPR)

To address the structural gap, EPR shifts the focus from individual facts to "Evidence Patterns" (EPs). An Evidence Pattern is essentially a structural template where entities not mentioned in the question are replaced by variables, defining the "shape" of the required evidence.

1. Atomic Patterns (APs)

Because the search space for all possible subgraphs is infinite, EPR breaks complex patterns into "Atomic Patterns." These are defined as pairs of adjacent resources (Entity-Relation or Relation-Relation pairs). By indexing these atoms, the system makes the search for complex structures computationally feasible.

2. Two-Stage Retrieval and Ranking

The EPR pipeline operates in two primary stages:

  • Atomic Retrieval: Using a BERT-based bi-encoder and a Faiss index, the system performs dense retrieval to identify the most relevant atomic building blocks for a given question.
  • Pattern Construction & Ranking: An iterative algorithm combines these atoms into candidate Evidence Patterns. A cross-encoder then ranks these candidates to identify the single most likely structural template.

3. Subgraph Extraction and Reasoning

Once the top-ranked pattern is selected, it is instantiated within the Knowledge Graph to extract a clean, high-quality subgraph. This subgraph is then passed to a reasoning model (such as a Neural State Machine) to produce the final answer.

Experimental Results

The researchers evaluated EPR on two industry-standard benchmarks: ComplexWebQuestions (CWQ) and WebQuestionsSP (WebQSP).

  • State-of-the-Art Performance: On ComplexWebQuestions, EPR achieved a 61.2 F1 score, representing a massive 13.2-point improvement over the previous best IR method (UniKGQA). It even outperformed several Semantic Parsing methods that rely on gold query annotations.
  • Denoising Capabilities: The "Answer Cover Rate"—the frequency with which the correct answer is present in the extracted subgraph—reached nearly 80% on CWQ, significantly outperforming heuristic-based extraction methods.
  • Data Efficiency: The ranking model for these patterns proved remarkably stable. Even when trained on only 20% of the available data, the model maintained high performance, suggesting that structural patterns are more universal and easier for models to learn than raw natural language mappings.

Discussion and Limitations

EPR demonstrates that structural dependency is a powerful tool for filtering noise in KGQA. However, the approach faces certain challenges:

  • Combinatorial Explosion: For highly complex questions, the number of ways to combine atomic patterns can grow significantly, necessitating more optimized enumeration strategies.
  • Generalization: The model's performance drops when encountering relations not seen during training (zero-shot scenarios), falling from ~62 F1 to ~20 F1.
  • Numerical Reasoning: EPR currently lacks a mechanism for handling numerical constraints, such as "cities with a population over 1 million."

Conclusion

Evidence Pattern Retrieval (EPR) represents a significant advancement for IR-based KGQA. By explicitly modeling the structural dependencies of evidence, EPR effectively denoises the subgraph extraction process, leading to substantial performance gains on complex reasoning tasks. Future work will focus on improving zero-shot generalization and integrating numerical reasoning into the pattern retrieval framework.

Summary updated

Abstract

Information retrieval (IR) methods for KGQA consist of two stages: subgraph extraction and answer reasoning. We argue current subgraph extraction methods underestimate the importance of structural dependencies among evidence facts. We propose Evidence Pattern Retrieval (EPR) to explicitly model the structural dependencies during subgraph extraction. We implement EPR by indexing the atomic adjacency pattern of resource pairs. Given a question, we perform dense retrieval to obtain atomic patterns formed by resource pairs. We then enumerate their combinations to construct candidate evidence patterns. These evidence patterns are scored using a neural model, and the best one is selected to extract a subgraph for downstream answer reasoning. Experimental results demonstrate that the EPR-based approach has significantly improved the F1 scores of IR-KGQA methods by over 10 points on ComplexWebQuestions and achieves competitive performance on WebQuestionsSP.
BibTeX
@inproceedings{ding2024enhancing,
  author = {Wentao Ding and Jinmao Li and Liangchuan Luo and Yuzhong Qu},
  title = {{Enhancing Complex Question Answering over Knowledge Graphs through Evidence Pattern Retrieval}},
  booktitle = {WWW},
  year = {2024},
  url = {https://openreview.net/forum?id=ndzErs0RfF},
}
Figure