Structure-Internalized Rule Language Model for Faithful Knowledge Graph Reasoning

Xingrui Zhuo; Jiapu Wang; Manzong Huang; Gongqing Wu; Xindong Wu

cs.AIAug 18, 2026

Structure-Internalized Rule Language Model for Faithful Knowledge Graph Reasoning

Authors: Xingrui Zhuo, Jiapu Wang, Manzong Huang, Gongqing Wu, Xindong Wu

Organizations: Key Laboratory of Knowledge Engineering with Big Data (Hefei University of Technology), Ministry of Education, China · School of Computer Science and Information Engineering, Hefei University of Technology, China · Nanjing University of Science and Technology, China

Abstract

Knowledge Graph Reasoning (KGR) aims to discover latent facts by leveraging the structural evidence available in KGs, posing a challenge to the structural semantic understanding capability of KGR models. Recent studies have demonstrated that Large Language Models (LLMs) can achieve remarkable progress on KGR tasks via flexible in-context learning. However, the inherent representation inconsistency between KG structural context and LLM parametric knowledge remains inadequately addressed. This limitation prevents LLMs from effectively perceiving reasoning evidence that aligns with KG constraints, which undermines both the effectiveness and faithfulness of reasoning. We refer to this problem as reasoning evidence perception drift of LLMs over KGs. To address this problem, we propose a Structure-Internalized Rule Language Model (SIRLM), which centers on structural rule generation to couple the parametric learning of structural knowledge with the faithfulness evaluation of reasoning logic, enabling LLMs to anchor tightly to KG-grounded evidence. Specifically, we first design a Structure-Internalized Rule Generator (SIRG), which incorporates an in-context learning block augmented with a structural relation memory to coordinate structural and parametric knowledge. Furthermore, we equip SIRG with a KG tokenizer based on structural invariance learning and a neuro-symbolic reasoner based on rule-constrained message propagation. These components provide SIRG with learnable structural representations and faithful rule-execution feedback, respectively. Our SIRLM can be seamlessly integrated into standard LLM training paradigms, such as SFT and GRPO. Extensive experiments against 17 state-of-the-art KGR methods on 36 datasets demonstrate the significant superiority of SIRLM.

Figures & tables

Figure 1: Case of reasoning evidence perception drift of LLMs over KGs. LLM select incorrect reasoning evidence based on its semantic preference, resulting in its inability to follow KG-grounded reasoning logic to arrive at correct reasoning conclusions.

Figure 2: Overall architecture and training framework of SILRM. Given a query triplet, we first 1 convert it into an instruction $X$ and input the triplet into the KG tokenizer to obtain structural embeddings of entities and relations. These structural representations are then 2 tokenized along with the LLM pre-trained tokenizer for $X$ . Next, SIGR reads the aforementioned tokens and 3 generates structural rules for the RCMP reasoner. Afterwards, 4 the reasoner executes rules and performs neuro-symbolic reasoning, ultimately obtaining scores for candidate entities.

Type	Methods	FB15k237		CoDEx-M		WN18RR		NELL995		12 IndE Datasets		20 FullInd Datasets
Type	Methods	MRR $\uparrow$	Hit10 $\uparrow$	MRR $\uparrow$	Hit10 $\uparrow$	MRR $\uparrow$	Hit10 $\uparrow$	MRR $\uparrow$	Hit10 $\uparrow$	MRR $\uparrow$	Hit10 $\uparrow$	MRR $\uparrow$	Hit10 $\uparrow$
Embedding methods	TransE	0.313	0.495	0.320	0.481	0.226	0.501	0.401	0.501	NA	NA	NA	NA
	RotatE	0.338	0.533	0.325	0.466	0.476	0.571	0.483	0.565	NA	NA	NA	NA
	TuckER	0.358	0.544	0.328	0.458	0.470	0.526	0.520	0.624	NA	NA	NA	NA
Rule-based methods	NeuralLP	0.237	0.362	0.334	0.444	0.435	0.566	0.394	0.482	0.449	0.623	NA	NA
	DRUM	0.343	0.516	0.312	0.438	0.486	0.586	0.532	0.662	0.458	0.621	NA	NA

Table 1: The overall performance of various methods on different datasets, where the MRR and Hit10 in the IndE and FullInd scenarios are summarized as average values. The colored cells represent the best , second-best , and third-best values, respectively. “–” indicates that the experimental results are unavailable, and “NA” indicates that a model is not applicable to a KGR task.

Figure 3: Hit10 of

\text{SIRLM}_{\text{PT}}

variants on different datasets, where the results in the IndE and FullInd scenarios are summarized as average values.

Figure 4: Hit10 of

\text{SIRLM}_{\text{E2E}}

with different NBFNet layers

N

in KG tokenizer and RCMP reasoner.

Figure 5: Hit10 of

\text{SIRLM}_{\text{E2E}}

with different relation memory scale

K

and

\text{SIRLM}_{\text{GRPO}}

with different GRPO sample number

M

LLM Backbone	CoDEx-M		WN18RR v1		FB15k237-25		NELL995-25
LLM Backbone	MRR	Hit10	MRR	Hit10	MRR	Hit10	MRR	Hit10
Qwen2.5-0.5b	0.351	0.511	0.692	0.749	0.382	0.637	0.389	0.564
Qwen2.5-1.5b	0.368	0.525	0.705	0.766	0.386	0.635	0.407	0.601
Qwen2.5-7b	0.369	0.531	0.708	0.771	0.387	0.635	0.408	0.606
Llama-2-7b	0.362	0.528	0.711	0.781	0.387	0.632	0.405	0.602

Table 2: The performance of

\text{SIRLM}_{\text{E2E}}

with different LLM backbones.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Model	MKGL ( Guo et al., 2024 )	KRLM ( Zhuo et al., 2026 )	SIRLM
Avg. Length	115.66 $\pm$ 3.65	120.50 $\pm$ 4.12	50.73 $\pm$ 0.67

Appendix

Table 3: Average instruction length of MKG, KRLM, and SIRLM in 36 KGR datasets.

Figure 6: Motif edges of relations in a KG, whcih can be grouped into three binary edges and four ternary edges. A binary edge represents the state of the entity shared by two ordered relations, including (1) tail-to-tail : a shared tail entity, (2) head-to-head : a shared head entity, (3) tail-to-head : the tail entity of the previous relation being the head entity of the next relation, and (4) head-to-tail : the head entity of the previous relation being the tail entity of the next relation. A ternary edge represents the state of a forward triplet shared by two ordered relations, which is a hyperedge containing three relation nodes, including (5) tail-forward-head : the forward triplet as the tail of the previous relation and the head of the next relation, (6) tail-forward-tail : the forward triplet as the shared tail of two relations, (7) head-forward-head : the forward triplet as the shared head of two relations, and (8) head-forward-tail : the forward triplet as the head of the previous relation and the tail of the next relation.

Metric	Pre-training (3 transductive datasets)		Fine-tuning (FB15k237 v1)		Fine-tuning (FB15k237-25)
Metric	KRLM	$\text{SIRLM}_{\text{PT}}$	KRLM	$\text{SIRLM}_{\text{SFT}}$	KRLM	$\text{SIRLM}_{\text{SFT}}$
Avg. TFLOPs (forward propagation 100 steps)	3.3436 $\pm$ 0.4540	2.0397 $\pm$ 0.3841	3.2755 $\pm$ 0.5208	2.0683 $\pm$ 0.0175	3.3312 $\pm$ 0.4859	2.2287 $\pm$ 0.0000
Training memory	36.12 GB / GPU	27.58 GB / GPU	32.57 GB / GPU	11.38 GB / GPU	32.67 GB / GPU	13.12 GB / GPU
Wall-clock time	3h10m / epoch	2h38m / epoch	7m28s / epoch	3m39s / epoch	12m13s / epoch	10m45s / epoch

Appendix

Table 4: Comparison of KRLM and SIRLM in terms of TFLOPs, memory footprint, and wall-clock time under pre-training and fine-tuning settings.

Type	Dataset	Training graph			Validation Graph				Testing Graph
Type	Dataset	Entities	Relations	Triplets	Entities	Relations	Triplets	#Valid	Entities	Relations	Triplets	#Test
Transductive	FB15k237 ( Toutanova & Chen, 2015 )	14541	237	272115	14541	237	272115	17535	14541	237	272115	20466
	CoDEx-M ( Safavi & Koutra, 2020 )	17050	51	185584	17050	51	185584	10310	17050	51	185584	10311
	WN18RR ( Dettmers et al., 2018 )	40943	11	86835	40943	11	86835	3034	40943	11	86835	3134
	NELL995 ( Xiong et al., 2017 )	74536	200	149678	74536	200	149678	543	74536	200	149678	2818
IndE	FB15k237 v1 ( Teru et al., 2020 )	1594	180	4245	1594	180	4245	489	1093	180	1993	411

Appendix

Table 5: Element statistics of KGR dataset. “ Triplets ” represents the number of total triplets contained in a training/validation/testing graph. “ #Valid ” and “ #Test ” are the number of evaluation triplets in the validation and testing graph, respectively.

Figure 7: The length distribution of rules mined from various datasets.

Module	Component	Parameter
KG Tokenizer	NBFNet on $\mathcal{G}_{r}$	Layer number $N=6$ Hidden dim $d=64$ Message function $\textsc{Msg}(\cdot)=$ DistMult Aggregation function $\textsc{Agg}(\cdot)=$ Sum Updating function $\textsc{Up}(\cdot)=\text{nn.Linear}(128,64)$ Motif Edge embeddings $\bm{R}^{*}=\text{nn.Embedding}(8,64)$
	NBFNet on $\mathcal{G}$	Layer number $N=6$ Hidden dim $d=64$ Message function $\textsc{Msg}(\cdot)=$ DistMult Aggregation function $\textsc{Agg}(\cdot)=$ Sum Updating function $\textsc{Up}(\cdot)=\text{nn.Linear}(128,64)$
	Up-scale layer $f_{\text{up}}(\cdot)$	$\text{nn.Linear}(64,1536)$
	Score function $\mathcal{S}_{\text{KG}}(\cdot)$	$\text{nn.Linear}(128,64)$ $\text{nn.ReLU}(\cdot)$ $\text{nn.Linear}(64,1)$
In-context Learning Module	Qwen2.5-1.5b backbone	Default configuration
	LoRA configuration	$r=64$ $\alpha=32$ $\text{droupout}=0.1$ $\text{target module}=\text{[gate\_proj, up\_proj, down\_proj]}$

Appendix

Table 6: Hyperperameters of KRLM used in pre-training and end-to-end training from scratch.

Datasets	$\text{SIRLM}_{\text{E2E}}$ ( $b$ , $\eta$ , epoch, step)	$\text{SIRLM}_{\text{SFT}}$ ( $b$ , $\eta$ , epoch, step)	$\text{SIRLM}_{\text{GRPO}}$ ( $b$ , $\eta$ , $M$ , epoch, step)
FB15k237	(12, 5e-4, 10, all)	(12, 1e-4, 3, all)	(8, 1e-5, 8, 1, all)
CoDEx-M	(24, 1e-4, 10, all)	(24, 5e-5, 3, all)	(8, 1e-5, 8, 1, all)
WN18RR	(12, 5e-4, 10, all)	(12, 1e-4, 3, all)	(8, 1e-5, 8, 3, all)
NELL995	(12, 5e-4, 10, all)	(12, 1e-4, 3, all)	(8, 1e-5, 8, 1, all)
FB15k237 v1	(24, 1e-4, 10, all)	(24, 5e-5, 3, all)	(16, 1e-5, 8, 3, all)
FB15k237 v2	(24, 1e-4, 10, all)	(24, 5e-5, 3, all)	(16, 1e-5, 8, 3, all)

Appendix

Table 7: Detailed Training parameters, where

b

\eta

, and

M

represent batch size, learning rate, and GRPO sampling number, respectively. “all” means that each epoch needs to iterate through all training queries.

Methods	FB15k237 v1		FB15k237 v2		FB15k237 v3		FB15k237 v4
Methods	MRR $\uparrow$	Hit10 $\uparrow$	MRR $\uparrow$	Hit10 $\uparrow$	MRR $\uparrow$	Hit10 $\uparrow$	MRR $\uparrow$	Hit10 $\uparrow$
NeuralLP	0.325	0.468	0.389	0.586	0.400	0.571	0.396	0.593
DRUM	0.333	0.474	0.395	0.595	0.402	0.571	0.410	0.593
NBFNet	0.422	0.574	0.514	0.685	0.476	0.637	0.453	0.627
RED-GNN	0.369	0.483	0.469	0.629	0.445	0.603	0.442	0.621
ULTRA	0.509	0.670	0.524	0.710	0.504	0.663	0.496	0.684

Appendix

Table 8: The overall performance of various methods on IndE datasets. The colored cells represent the best , second-best , and third-best values, respectively.

Methods	FB15k237-25		FB15k237-50		FB15k237-75		FB15k237-100
Methods	MRR $\uparrow$	Hit10 $\uparrow$	MRR $\uparrow$	Hit10 $\uparrow$	MRR $\uparrow$	Hit10 $\uparrow$	MRR $\uparrow$	Hit10 $\uparrow$
NBFNet	0.224	0.410	0.130	0.259	0.089	0.166	0.072	0.154
RED-GNN	0.145	0.284	0.129	0.251	0.107	0.201	0.121	0.263
ULTRA	0.383	0.635	0.334	0.538	0.400	0.598	0.444	0.643
MOTIF	0.388	0.635	0.340	0.544	0.399	0.607	0.439	0.642
ChatRule $\dagger$	0.336	0.602	0.289	0.514	0.250	0.507	0.361	0.554

Appendix

Table 9: The overall performance of various methods on FullInd datasets. The colored cells represent the best , second-best , and third-best values, respectively.

Methods	FB15k237		CodeX-M		WN18RR		NELL995		12 IndE Datasets		20 FullInd Datasets
Methods	MRR	Hit10	MRR	Hit10	MRR	Hit10	MRR	Hit10	MRR	Hit10	MRR	Hit10
Full Model	0.408	0.593	0.367	0.522	0.461	0.556	0.520	0.638	0.580	0.738	0.374	0.538
w/o MMQI	0.389	0.579	0.360	0.499	0.458	0.525	0.514	0.627	0.570	0.721	0.364	0.522
w/o SRM	0.358	0.566	0.348	0.478	0.455	0.526	0.488	0.606	0.558	0.709	0.348	0.508
w/o RCMP	0.352	0.538	0.339	0.422	0.404	0.500	0.501	0.611	0.540	0.685	0.344	0.502

Appendix

Table 10: The overall performance of ablation variants on different datasets, where the MRR and Hit10 in the IndE and FullInd scenarios are summarized as average values. The colored cells represent the best , second-best , and third-best values, respectively.

Figure 8: The correlation trend between KG sparsity and the MRR gain of SIRLM.

Figure 9: Convergence of rule generation accuracy for SIRLM with different LLMs on WN18RR v1.

Figure 10: Case studies of rule generation. Red , blue , and orange denote the query relation, the atomic relations in the ground-truth rule, and the atomic relations in the predicted rule, respectively. Green denotes the target entities that need to be predicted.

LLM Reasoning with Graphs

Large language model reasoning with graphs uses structured relationships to support multi-step inference, evidence retrieval, and planning.

See all 200 papers

Aug 2, 2026

The Graph Language: How Knowledge Graphs Speak to Large Language Models

Large Language Models (LLMs) excel at reasoning but benefit from grounding provided by Knowledge Graphs (KGs). However, integrating these paradigms is challenging. We introduce GRALAN, which enables KGs to speak directly in the LLM's semantic space through relational tokens that preserve graph structure. GRALAN-s trainable language mediator generates structured tokens for any frozen LLM, creating a foundation for knowledge-intensive applications. We demonstrate its effectiveness in question-answering by re-framing the task as entity classification over question-focused subgraphs. Experiments show that GRALAN significantly outperforms existing methods, particularly on complex multi-hop reasoning tasks, establishing a new paradigm for KG-LLM integration that maintains structural fidelity while leveraging LLMs' reasoning capabilities.

Giuseppe Pirrò

DeMaCS, University of Calabria

LLM Grounding Knowledge Augmentation for Language Models LLM Reasoning with Graphs Knowledge Graph Question Answering

Ask PDF

Feb 25, 2026

RADAR: Reasoning as Discrimination with Aligned Representations for LLM-based Knowledge Graph Reasoning

Knowledge graph reasoning (KGR) infers missing facts, with recent advances increasingly harnessing the semantic priors and reasoning abilities of Large Language Models (LLMs). However, prevailing generative paradigms are prone to memorizing surface-level co-occurrences rather than learning genuine relational semantics, limiting out-of-distribution generalization. To address this, we propose RADAR, which reformulates KGR from generative pattern matching to discriminative relational reasoning. We recast KGR as discriminative entity selection, where reinforcement learning enforces relative entity separability beyond token-likelihood imitation. Leveraging this separability, inference operates directly in representation space, ensuring consistency with the discriminative optimization and bypassing generation-induced hallucinations. Across four benchmarks, RADAR achieves 5-6% relative gains on link prediction and triple classification over strong LLM baselines, while increasing task-relevant mutual information in intermediate representations by 62.9%, indicating more robust and transferable relational reasoning.

Bo Xue, Yuan Jin, Luoyi Fu +2

Shanghai Jiao Tong University, Shanghai, China

Graph Reasoning KG Completion LLMs for Graph Learning Knowledge Graph Question Answering

Ask PDF

Nov 6, 2025

KGFR: A Foundation Retriever for Generalized Knowledge Graph Question Answering

Large language models (LLMs) excel at reasoning but struggle with knowledge-intensive questions due to limited context and parametric knowledge. However, existing methods that rely on finetuned LLMs or GNN retrievers are limited by dataset-specific tuning and scalability on large or unseen graphs. We propose the LLM-KGFR collaborative framework, where an LLM works with a structured retriever, the Knowledge Graph Foundation Retriever (KGFR). KGFR encodes relations using LLM-generated descriptions and initializes entities based on their roles in the question, enabling zero-shot generalization to unseen KGs. To handle large graphs efficiently, it employs Asymmetric Progressive Propagation (APP)- a stepwise expansion that selectively limits high-degree nodes while retaining informative paths. Through node-, edge-, and path-level interfaces, the LLM iteratively requests candidate answers, supporting facts, and reasoning paths, forming a controllable reasoning loop. Experiments demonstrate that LLM-KGFR achieves strong performance while maintaining scalability and generalization, providing a practical solution for KG-augmented reasoning.

Yuanning Cui, Zequn Sun, Wei Hu +1

School of Computer Science, Nanjing University of Information Science and Technology, Nanjing 210044, China · State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China · National Institute of Healthcare Data Science, Nanjing University, Nanjing 210093, China +2

Multi-Hop QA LLM Grounding LLM Reasoning with Graphs Graph-Based Retrieval Graph Foundation Models Knowledge Graph Question Answering

Ask PDF

Abstract

LLM Reasoning with Graphs

Explore similar work

The Graph Language: How Knowledge Graphs Speak to Large Language Models

RADAR: Reasoning as Discrimination with Aligned Representations for LLM-based Knowledge Graph Reasoning

KGFR: A Foundation Retriever for Generalized Knowledge Graph Question Answering