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