@inproceedings{el-khatib-difallah-2026-explore,
title = "Explore-over-Graph: Hybrid Embedding{--}{LLM} Reasoning for Knowledge Graph Question Answering under Incompleteness",
author = "El Khatib, Ola and
Difallah, Djellel",
editor = "Zhang, Yue and
Xu, Ruifeng and
Purwarianti, Ayu and
Rong, Tong and
Suzuki, Jun",
booktitle = "Findings of the {A}ssociation for {C}omputational {L}inguistics: {IJCNLP}-{AACL} 2026",
month = nov,
year = "2026",
address = "Hengqin, China",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/2026.findings-aacl.98/",
pages = "1962--1975",
ISBN = "979-8-89176-444-6",
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-over-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."
}<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="el-khatib-difallah-2026-explore">
<titleInfo>
<title>Explore-over-Graph: Hybrid Embedding–LLM Reasoning for Knowledge Graph Question Answering under Incompleteness</title>
</titleInfo>
<name type="personal">
<namePart type="given">Ola</namePart>
<namePart type="family">El Khatib</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Djellel</namePart>
<namePart type="family">Difallah</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2026-11</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Findings of the Association for Computational Linguistics: IJCNLP-AACL 2026</title>
</titleInfo>
<name type="personal">
<namePart type="given">Yue</namePart>
<namePart type="family">Zhang</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ruifeng</namePart>
<namePart type="family">Xu</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ayu</namePart>
<namePart type="family">Purwarianti</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Tong</namePart>
<namePart type="family">Rong</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Jun</namePart>
<namePart type="family">Suzuki</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Hengqin, China</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
<identifier type="isbn">979-8-89176-444-6</identifier>
</relatedItem>
<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-over-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.</abstract>
<identifier type="citekey">el-khatib-difallah-2026-explore</identifier>
<location>
<url>https://aclanthology.org/2026.findings-aacl.98/</url>
</location>
<part>
<date>2026-11</date>
<extent unit="page">
<start>1962</start>
<end>1975</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T Explore-over-Graph: Hybrid Embedding–LLM Reasoning for Knowledge Graph Question Answering under Incompleteness
%A El Khatib, Ola
%A Difallah, Djellel
%Y Zhang, Yue
%Y Xu, Ruifeng
%Y Purwarianti, Ayu
%Y Rong, Tong
%Y Suzuki, Jun
%S Findings of the Association for Computational Linguistics: IJCNLP-AACL 2026
%D 2026
%8 November
%I Association for Computational Linguistics
%C Hengqin, China
%@ 979-8-89176-444-6
%F el-khatib-difallah-2026-explore
%X 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-over-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.
%U https://aclanthology.org/2026.findings-aacl.98/
%P 1962-1975
Markdown (Informal)
[Explore-over-Graph: Hybrid Embedding–LLM Reasoning for Knowledge Graph Question Answering under Incompleteness](https://aclanthology.org/2026.findings-aacl.98/) (El Khatib & Difallah, Findings 2026)
ACL