Topology-Aware Reasoning over Incomplete Knowledge Graph with Graph-Based Soft Prompting

Shuai Wang; Xixi Wang; Yinan Yu

cs.CLApr 14, 2026

Topology-Aware Reasoning over Incomplete Knowledge Graph with Graph-Based Soft Prompting

Authors: Shuai Wang, Xixi Wang, Yinan Yu

Organizations: Chalmers University of Technology and University of Gothenburg, Sweden · Technical University of Denmark, Kgs. Lyngby, Denmark

Abstract

Large Language Models (LLMs) have shown remarkable capabilities across various tasks but remain prone to hallucinations in knowledge-intensive scenarios. Knowledge Base Question Answering (KBQA) mitigates this by grounding generation in Knowledge Graphs (KGs). However, most multi-hop KBQA methods rely on explicit edge traversal, making them fragile to KG incompleteness. In this paper, we proposed a novel graph-based soft prompting framework that shifts the reasoning paradigm from node-level path traversal to subgraph-level reasoning. Specifically, we employ a Graph Neural Network (GNN) to encode extracted structural subgraphs into soft prompts, enabling LLM to reason over richer structural context and identify relevant entities beyond immediate graph neighbors, thereby reducing sensitivity to missing edges. Furthermore, we introduce a two-stage paradigm that reduces computational cost while preserving good performance: a lightweight LLM first leverages the soft prompts to identify question-relevant entities and relations, followed by a more powerful LLM for evidence-aware answer generation. Experiments on four multi-hop KBQA benchmarks show that our approach achieves state-of-the-art performance on three of them, demonstrating its effectiveness. Code is available at the repository: https://github.com/Wangshuaiia/GraSP.

Figures & tables

Figure 1: An example of reasoning over an incomplete knowledge graph. Existing methods (middle) solely rely on explicit edges and fail to perform multi-hop reasoning under graph incompleteness (e.g. missing edges). Our method (bottom) overcomes this limitation by exploiting implicit relations in the graph structure.

Method	IKGWQ	CWQ-IKG	WebQSP-IKG
ToG Sun et al. (2024)	58.6 ±2.4	59.2 ±2.3	70.2 ±1.7
DoM Liu et al. (2026)	59.1 ±1.3	60.7 ±1.5	75.8 ±1.8
GoG Xu et al. (2024)	60.3 ±3.4	61.4 ±2.7	78.1 ±2.4
iQUEST Wang and Yu (2025)	60.1 ±1.6	59.7 ±1.4	79.3 ±1.2
KBQA-o1 Luo et al. (2025)	61.1 ±1.2	63.9 ±2.6	80.1 ±0.9
LMP Wan et al. (2025)	62.7 ±2.2	64.3 ±1.4	80.6 ±1.7

Table 1: Performance comparison on three incomplete KGQA datasets (Hits@1). We re-implemented all baselines using GPT-5.2 for fair comparison. “ ± ” denotes the standard variation. “ ∗ ” (

p<0.05

), “ ∗∗ ” (

p<0.01

), and “ ∗∗∗ ” (

p<0.001

) denote statistically significant improvements over LMP under the t -test.

Method	Incomplete KG Benchmarks			Standard KBQA Benchmarks
Method	IKGWQ	CWQ-IKG	WebQSP-IKG	CWQ	WebQSP	WebQuestion	GrailQA
GraSP (GPT-20B as $\text{LLM}_{\text{select}}$ )	65.52	68.57	83.91	82.58	93.63	84.32	83.99
Without Soft Prompt	61.68	63.92	79.64	78.72	89.42	81.28	78.46
Triplet-based Representation	62.37	65.41	81.26	79.63	92.13	82.26	80.74
Text-based Soft Prompt	63.18	66.02	82.17	80.15	92.41	83.55	81.63
GraSP (Qwen-30B-A3B as $\text{LLM}_{\text{select}}$ )	64.42	67.12	81.23	82.28	93.16	84.07	83.46

Table 2: Ablation study of the graph-based soft prompting.

Figure 3: Results on CWQ under Knowledge Graph Incompleteness.

Method	Incomplete KG Benchmarks			Standard KBQA Benchmarks
Method	IKGWQ	CWQ-IKG	WebQSP-IKG	CWQ	WebQSP	WebQuestion	GrailQA
Qwen3-0.6B (freeze)	48.36	51.42	66.75	61.73	69.14	58.05	62.48
Qwen3-0.6B (Finetune)	58.21 (+9.85)	60.93 (+9.51)	77.46 (+10.71)	71.31 (+9.58)	81.14 (+12.00)	68.52 (+10.47)	69.87 (+7.39)
Qwen3-8B (freeze)	57.84	60.91	77.62	72.55	81.54	72.31	65.38
Qwen3-8B (Finetune)	64.13 (+6.29)	67.39 (+6.48)	82.48 (+4.86)	80.85 (+8.30)	88.86 (+7.32)	78.40 (+6.09)	79.16 (+13.78)
GPT-20B (freeze)	60.08	63.24	78.37	77.21	86.34	78.28	76.13

Table 3: Performance comparison with different

\text{LLM}_{\text{select}}

settings.

	CWQ	WebQSP	WebQuestion	GrailQA
1-Hop	79.07	90.87	82.01	81.29
2-Hop	82.58	93.63	84.32	83.99
3-Hop	76.47	85.98	80.21	78.66

Table 4: Performance comparison of different hop settings on four standard benchmarks.

Method	Metrics	1-Hop	2-Hop	3-Hop
ToG	# LLM call	2.2	5.6	8.3
ToG	Run time (s)	3.16	11.76	17.51
LMP	# LLM call	2.3	4.9	7.3
LMP	Run time (s)	3.45	9.76	15.38
Ours	# LLM call	1.3 + 1.1	3.6 + 2.2	5.3 + 2.6
	Run time (s)	2.50	4.75	7.60

Table 5: Comparison of LLM call counts and runtime across different hop settings for our method and baseline approaches. For our method, calls to the lightweight LLM are shown in green , while calls to the powerful LLM are shown in red .

Dataset	Train	Test	Complexity	Reasoning	Annotation
IKGQA	-	200	Incomplete KG	Multi-hop	Ans. only
CWQ-IKG	27,689	1,000	Incomplete KG	Multi-hop	Ans. only
WebQSP-IKG	3,098	1,000	Incomplete KG	Multi-hop (most)	Ans. only
CWQ	27,689	3,531	Complex Qs	Multi-hop	SPARQL, Ans.
WebQSP	3,098	1,639	Moderate Qs	Multi-hop (most)	SPARQL, Ans.
WebQuestion	3,778	2,032	Simple–Moderate Qs	Single-hop (most)	Ans. only

Table 6: Overview of datasets.

Method	Multi-hop reasoning			Generalization
Method	CWQ	WebQSP	WebQuestion	GrailQA
EmbedKGQA Saxena et al. (2022)	55.7	67.0	60.3	52.2
ToG Sun et al. (2024)	69.5	82.1	72.8	69.4
KBQA-o1 Luo et al. (2025)	72.0	88.3	82.5	72.9
KG-Agent Jiang et al. (2025)	72.2 ∗	83.3 ∗	–	86.1 ∗
iQUEST Wang and Yu (2025)	73.8 ∗	88.9 ∗	81.2 ∗	73.5 ∗

Table 7: Performance comparison on four KBQA datasets. Results marked with ‘*’ are taken directly from the corresponding original papers. Bold numbers indicate the best performance , while underlined numbers denote the second-best (Hits@1).

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Method	CWQ	WebQSP
RoG Luo et al. (2024b)	62.6 ∗	85.7 ∗
GNN-RAG ( 2024 )	62.8 ∗	82.8 ∗
PoG Tan et al. (2025)	65.1	86.2
LightPROF Ao et al. (2025)	59.3 ∗	83.8 ∗
MemQ Xu et al. (2025a)	80.3 ∗	84.1 ∗
KaeDe Bu et al. (2025)	88.3 ∗	91.1 ∗

Appendix

Table 8: Comparison with different baselines.

Select LLM	CWQ	WebQSP	WebQuestion	GrailQA
Qwen3-0.6B	61.73	69.14	58.05	62.48
Qwen3-0.6B (Finetune)	71.31	81.14	68.52	69.87
Qwen3-1.7B	66.24	74.53	60.72	63.28
Qwen3-1.7B (Finetune)	73.40	84.51	71.96	72.58
Qwen3-4B	69.66	79.68	69.01	63.09
Qwen3-4B (Finetune)	77.07	86.83	76.52	77.16

Appendix

Table 9: Performance comparison of different select LLMs.

Answer LLM	CWQ	WebQSP	WebQuestion	GrailQA
Qwen3-8B	54.58	68.97	64.88	52.17
Qwen-30B-A3B	61.91	75.65	69.49	64.18
GPT-oss-20b	67.90	79.98	71.74	72.88
LLaMA3.3-70B	68.81	79.76	74.97	70.82
GPT-oss-120b	75.03	84.75	79.42	78.01
GPT-4o	77.64	90.95	82.39	79.82

Appendix

Table 10: Performance comparison of different answer LLMs.

Explore similar work

Explore-over-Graph: Hybrid Embedding-LLM Reasoning for Knowledge Graph Question Answering under Incompleteness
Sep 30, 2026Ola El Khatib, Djellel DifallahKnowledge Graph Question Answering Multi-Hop QA
New York University Abu Dhabi, UAE
Foresight-over-Graph: Reasoning Beyond Local Horizons for Knowledge Base Question Answering
Oct 6, 2026Yang Hong, Yajun Yang, Xin Wang +2Multi-Hop QA LLM Reasoning with Graphs
Tianjin University, Tianjin, China · Beijing Jiaotong University, Beijing, China
KG-Hopper: Empowering Compact Open LLMs with Knowledge Graph Reasoning via Reinforcement Learning
Mar 22, 2026Shuai Wang, Yinan YuLLM Reasoning with Graphs Knowledge Graph Question Answering
Department of Computer Science and Engineering, Chalmers University of Technology and University of Gothenburg, SE-41296 Gothenburg, Sweden

Sep 30, 2026J/K move · Enter open · S save

Explore-over-Graph: Hybrid Embedding-LLM Reasoning for Knowledge Graph Question Answering under Incompleteness

Ola El Khatib, Djellel Difallah

New York University Abu Dhabi, UAE

Knowledge Graph Question Answering Multi-Hop QA LLM Reasoning with Graphs

Open paper AskPDF arXiv

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

Explore similar work

Explore-over-Graph: Hybrid Embedding-LLM Reasoning for Knowledge Graph Question Answering under Incompleteness

Foresight-over-Graph: Reasoning Beyond Local Horizons for Knowledge Base Question Answering

KG-Hopper: Empowering Compact Open LLMs with Knowledge Graph Reasoning via Reinforcement Learning