Generate-on-Graph: Treat LLM as both Agent and KG for Incomplete Knowledge Graph Question Answering

Yao Xu, Shizhu He, Jiabei Chen, Zihao Wang, Yangqiu Song, Hanghang Tong, Guang Liu, Jun Zhao, Kang Liu

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

Abstract

To address the issues of insufficient knowledge and hallucination in Large Language Models (LLMs), numerous studies have explored integrating LLMs with Knowledge Graphs (KGs). However, these methods are typically evaluated on conventional Knowledge Graph Question Answering (KGQA) with complete KGs, where all factual triples required for each question are entirely covered by the given KG. In such cases, LLMs primarily act as an agent to find answer entities within the KG, rather than effectively integrating the internal knowledge of LLMs and external knowledge sources such as KGs. In fact, KGs are often incomplete to cover all the knowledge required to answer questions. To simulate these real-world scenarios and evaluate the ability of LLMs to integrate internal and external knowledge, we propose leveraging LLMs for QA under Incomplete Knowledge Graph (IKGQA), where the provided KG lacks some of the factual triples for each question, and construct corresponding datasets. To handle IKGQA, we propose a training-free method called Generate-on-Graph (GoG), which can generate new factual triples while exploring KGs. Specifically, GoG performs reasoning through a Thinking-Searching-Generating framework, which treats LLM as both Agent and KG in IKGQA. Experimental results on two datasets demonstrate that our GoG outperforms all previous methods.
BibTeX
@inproceedings{xu2024generate,
  author = {Yao Xu and Shizhu He and Jiabei Chen and Zihao Wang and Yangqiu Song and Hanghang Tong and Guang Liu and Jun Zhao and Kang Liu},
  title = {{Generate-on-Graph: Treat LLM as both Agent and KG for Incomplete Knowledge Graph Question Answering}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2024},
  doi = {10.18653/v1/2024.emnlp-main.1023},
}
Figure