TL;DR
This paper introduces "Generate-on-Graph" (GoG), a novel framework that empowers Large Language Models (LLMs) to answer questions even when the Knowledge Graph (KG) is incomplete. GoG treats LLMs as both an intelligent agent exploring the KG and a knowledge generator, effectively bridging the gap between internal LLM knowledge and external, potentially incomplete, factual data.
What Problem Does This Paper Address?
Large Language Models (LLMs) have shown remarkable capabilities, but they often suffer from insufficient knowledge and a tendency to "hallucinate" (generate incorrect or fabricated information). To combat this, researchers have explored integrating LLMs with Knowledge Graphs (KGs), which provide structured factual information. However, most existing methods are evaluated on KGs that are assumed to be complete, meaning they contain all necessary facts for answering questions. This is unrealistic, as real-world KGs are often incomplete. When KGs are incomplete, LLMs struggle to find answers, and current methods don't effectively leverage both the LLM's internal knowledge and the incomplete KG. This paper addresses this gap by proposing a new task, Incomplete Knowledge Graph Question Answering (IKGQA), and a method, Generate-on-Graph (GoG), to handle it.
Methods
The core of the proposed solution is the Generate-on-Graph (GoG) method, which operates on a Thinking-Searching-Generating framework. This framework treats the LLM as both an agent and a knowledge source:
- Thinking: The LLM first analyzes the question and decides on the next step: whether to search the KG or generate new information.
- Searching: The LLM acts as an agent, using predefined tools (like a SPARQL query engine) to explore the KG. It identifies relevant entities and relations, filtering out irrelevant information. This step involves "Exploring" (finding all relations) and "Filtering" (selecting the most relevant ones).
- Generating: If direct answers cannot be found through searching, the LLM leverages its internal knowledge to generate new factual triples. This involves retrieving relevant existing triples, generating new ones, and then verifying them. This "Generate" action is crucial for handling missing information in the KG.
GoG iteratively applies these steps until a satisfactory answer is found or it determines the answer is unknown.
Datasets
The authors construct new datasets for the IKGQA task by taking two existing KGQA datasets:
- WebQuestionSP (WebQSP)
- Complex WebQuestion (CWQ)
They simulate incomplete KGs by randomly deleting crucial triples from the original KGs, creating versions with varying degrees of incompleteness (e.g., IKG-20%, IKG-40%, etc.). They selected 1,000 samples from each dataset for their IKGQA benchmark.
Key Insights and Ideas
- Real-world KGs are incomplete: The paper highlights that evaluating KGQA on complete KGs is a simplification and doesn't reflect real-world scenarios.
- LLMs as both Agent and KG: The core innovation is treating the LLM not just as a tool to query a KG, but as an active agent that can explore and generate knowledge, effectively acting as a dynamic KG itself.
- The "Generate" action is critical: When facts are missing from the KG, the ability to generate new, plausible triples is essential for answering questions. This is where GoG significantly differs from previous methods.
- IKGQA is a more challenging and realistic benchmark: The proposed IKGQA task and datasets provide a better evaluation of LLMs' ability to integrate internal and external knowledge under realistic conditions.
Key Results
GoG demonstrates superior performance compared to existing methods on both complete and incomplete KG settings across the CWQ and WebQSP datasets.
- State-of-the-art performance: GoG achieves state-of-the-art results on both CWQ and WebQSP, outperforming other prompt-based, semantic parsing, and retrieval-augmented methods, especially in incomplete KG scenarios.
- Significant improvement on IKG: GoG shows a substantial improvement in Hits@1 scores on incomplete KGs, highlighting its effectiveness in handling missing information. For example, on CWQ with IKG-40%, GoG achieved an average improvement of 5.0% over other methods.
- Robustness across LLMs: GoG performs well with various LLM backbones (GPT-3.5, GPT-4, Qwen-1.5, Llama-3), with GPT-4 showing particularly strong results.
- Effectiveness of the "Generate" action: Ablation studies show that the "Generate" action significantly boosts GoG's performance, confirming its importance for IKGQA.
Limitations and Future Work
- Hallucination: The paper acknowledges that LLMs can still hallucinate during the "Generate" action, which is an inherent limitation of current LLM technology.
- Performance with extreme incompleteness: GoG's performance can be lower than simple CoT prompting when KGs are extremely incomplete.
- Future Work: The authors suggest further research into how different LLMs leverage their strengths in playing specific roles (agent vs. knowledge source) and exploring ways to mitigate hallucination.
Summary updated