New method improves question answering on incomplete knowledge graphs
Explore-on-Graph: Hybrid Embedding-LLM Reasoning for Knowledge Graph Question Answering under Incompleteness
Computation and Language
Summary
Many question-answering systems use knowledge graphs, which are like big maps of facts, to help find answers. But when these maps are missing some connections, usual methods struggle to find the right answers. The authors developed XoG, a way to fill in missing parts of the map by using patterns in the types of entities and relations, plus AI reasoning, to better explore and answer questions. This approach works well even when knowledge graphs are incomplete and also uses less computational effort than similar methods.
What this means in practice
- •For knowledge graph developers: Improve question answering over partial or incomplete knowledge graphs by recovering plausible missing facts during query processing.
- •For natural language interface builders: Reduce the token usage and improve reliability when integrating language models with knowledge sources for multi-step question answering.
Authors
Ola El Khatib, Djellel Difallah
Abstract
Large language models (LLMs) are increasingly combined with knowledge graphs (KGs) to ground reasoning in structured evidence. However, most LLM-based KGQA methods rely on traversing existing graph edges and become unreliable when reasoning paths are broken by missing facts. Alternatives that ask LLMs to generate missing knowledge risk introducing hallucinated evidence. We introduce XoG (eXplore-on-Graph), a framework for multi-hop question answering over incomplete KGs that recovers missing reasoning paths from learned graph structure rather than LLM parametric knowledge. XoG combines type-level entity-relation statistics to identify candidate relations with KG embeddings to retrieve plausible missing entities, using the LLM as a semantic selector and reasoner. These mechanisms are integrated into an iterative planning-exploration-reasoning process. Experiments on WebQSP, CWQ, and the Wikidata-based BRINK benchmark show that XoG remains competitive on complete KGs and consistently outperforms comparable methods without task-specific KGQA training under KG incompleteness. These gains persist across multiple LLM backbones, indicating that stronger LLMs alone do not resolve missing graph evidence. XoG also reduces LLM token consumption by up to 33% compared with a closely related planning-based approach.