PaperlayerView exact revision on arXiv

Source-linked AI summary

Structure-Internalized Rule Language Model for Faithful Knowledge Graph Reasoning

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

arXiv:2608.17443v1cs.AI

TL;DR

LLM-based knowledge graph reasoning struggles to align KG structure with parametric knowledge, causing reasoning evidence perception drift and weaker faithfulness. SIRLM addresses this with structure-internalized rule generation, a KG tokenizer, and a neuro-symbolic reasoner, and consistently outperforms existing methods across 36 benchmarks.

  • Problem

    LLM-based KGR methods struggle to align KG structural representations with parametric knowledge, causing evidence perception drift and undermining reasoning effectiveness and faithfulness.

  • Method

    SIRLM combines a structure-internalized rule generator with structural relation memory, a KG tokenizer, and a neuro-symbolic rule reasoner to ground LLM reasoning in KG structure.

  • Results

    SIRLM consistently outperforms existing methods across 36 KGR benchmarks in transductive and inductive reasoning scenarios.

  • Takeaways & Limitations

    SIRLM provides a structure-grounded approach for reliable LLM-based knowledge graph reasoning and generalizable reasoning across unknown KGs.

  • Takeaways & Limitations

    SIRLM still has significant room for improvement on sparse KGs because limited structural rules hinder rule learning and generation.

Abstract

from arXiv · show

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.

1 INTRODUCTION

SIRLM addresses LLM reasoning evidence perception drift over knowledge graphs by integrating structural representations, rule generation, and faithful rule execution. It supports standard LLM training frameworks and demonstrates reasoning capabilities across transductive and inductive KGR scenarios.

  • Problem: Existing LLM-based KGR methods struggle with structural–parametric representation inconsistency, causing evidence selection to follow semantic preferences instead of KG structural constraints.This limits LLMs’ ability to grasp structural KG context during reasoning.
  • Proposed Method: SIRLM mitigates reasoning evidence perception drift by enabling LLMs to accurately perceive KG-grounded evidence for faithful reasoning.Its framework comprises a KG tokenizer, Structure-Internalized Rule Generator, and neuro-symbolic reasoner.
  • Proposed Method: SIRG uses structural relation memory to coordinate LLM knowledge with KG context, while SIL-based tokenization and RCMP-based reasoning support universal structure representation learning and faithful rule execution feedback.The neuro-symbolic reasoner feeds rule faithfulness metrics composed of reasoning conclusions back to SIRG for closed-loop optimization.
  • Training and Generalization: SIRLM integrates with standard LLM training frameworks such as SFT and GRPO, enabling generalizable reasoning across unknown KGs.The framework is designed for transferable performance across cross-scenario KGR tasks.
  • Experimental Results: 36 datasets demonstrate SIRLM’s remarkable reasoning capabilities in both transductive and inductive KGR scenarios.The experiments evaluate the model across a wide range of KGR settings.

2 RELATED WORK

Related work progresses from embedding-based and rule-based KGR toward GNN-based structural modeling and, more recently, LLM-based structural reasoning. These developments motivate internalizing structural knowledge through rule generation as feedback for grounded reasoning over KGs.

  • Traditional KGR: Traditional KGR projects entities and relations into Euclidean, complex, or manifold embedding spaces to infer latent associations.Some studies additionally target interpretability through rule-based reasoning, as indicated by the passage.
  • GNN-based KGR: GNN-based KGR uses message passing to capture fine-grained structural context about entities and relations in increasingly complex KGs.Examples include NBFNet, RED-GNN, and InGram.
  • LLM-based KGR: LLM-based KGR leverages knowledge emergence and in-context learning to uncover deeper KG facts through structural reasoning.KICGPT and ChatRule exemplify LLM-planning combined with KG retrieval over given sub-KGs.
  • Motivation: The identified challenge motivates structural rule generation as feedback to help LLMs perceive grounded structural logic over KGs and improve reasoning.This mechanism is presented as a more refined approach to internalizing structural knowledge.

3 PRELIMINARIES

This section defines knowledge graphs and knowledge graph reasoning, distinguishing transductive and inductive settings. It also introduces structural invariance learning, NBFNet-based representations, and the in-context learning framework underlying the model.

  • Knowledge Graph Reasoning: A knowledge graph G = (E, R, T) contains entities, relations, and triples representing factual connections between head and tail entities.Each triple has the form <e_h, r_q, e_t>, with entities in E and relations in R.
  • Knowledge Graph Reasoning: KGR infers missing facts <e_h, r_q, ?>, using transductive settings with shared entities and relations or inductive settings involving unseen entities or relations.Inductive KGR requires extrapolation and generalization beyond the training knowledge graph.
  • Structural Invariance Learning: Structural invariance learning derives universal structural representations for unseen entities and relations by mapping relations into a motif-based relational graph and aggregating motif edges.NBFNet performs path-based message propagation over the relational graph to obtain relation representations conditioned on a query relation, followed by entity representations conditioned on the query head.
  • In-Context Learning: In-context learning converts an instruction into token embeddings, whose hidden states aggregate preceding tokens through self-attention before next-token generation.The model architecture tokenizes structural entity and relation representations alongside the instruction, generates structural rules, executes them with neuro-symbolic reasoning, and scores candidate entities.

4 METHODOLOGY

SIRLM combines a structure-internalized rule generator with a KG toolkit to generate KG-grounded rules and execute them for faithful reasoning. Its methodology covers structural tokenization, relation-memory-guided rule generation, rule-constrained message propagation, and integration with SFT and GRPO.

  • Method overview: SIRLM comprises a structure-internalized rule generator and a KG toolkit spanning query instruction construction, KG tokenization, in-context rule generation, rule reasoning, and LLM training integration.The framework is organized into Sections 4.1–4.3 and its training integration is described afterward.
  • Query instruction and KG tokenizer: Structural entity, relation, and termination identifiers are embedded by a trainable KG tokenizer and jointly processed with frozen pretrained LLM tokens.The KG tokenizer introduces structural representations while TKNLLM remains frozen and only TKNKG is trained.
  • In-context learning and rule generation: A structural relation memory selects top-K relevant relations, and autoregressive next-relation prediction generates executable rules grounded in the corresponding KG.Generation terminates when the END relation is produced or the maximum rule length ε is reached.
  • Rule reasoning: RCMP initializes relation nodes with hidden states from generated relations, transforming rule-sequence semantics into structural constraints for contextual representation and candidate-tail scoring.This augments the conventional query-relation initialization with generated-rule hidden states.
  • Training integration: SIRLM incorporates the KG tokenizer and RCMP reasoner into supervised pre-training or SFT, and uses GRPO post-training with rule rewards and structural-compliance evaluation.During GRPO evaluation, RCMP checks generated-rule structure but does not participate in parameter optimization.

5 EXPERIMENTS

SIRLM is evaluated across 36 transductive and inductive KGR datasets using four training paradigms and standard ranking metrics. It achieves strong performance across most datasets and metrics, while ablations and backbone studies examine module contributions and adaptability.

  • Datasets: SIRLM is tested on 36 datasets spanning four transductive, 12 IndE, and 20 FullInd datasets.The datasets are constructed from FB15k237, WN18RR, NELL995, Wikidata68K, CoDEx-M, and MTDEA.
  • Experimental settings: Experiments evaluate End-to-End, Pre-Training, SFT, and GRPO training paradigms.The training settings for each paradigm are provided in Appendix H.
  • Overall performance: SIRLM achieves consistently strong and competitive results, outperforming prior methods on most datasets and metrics.The evaluation covers transductive, IndE, and FullInd settings and uses MRR and Hit10.
  • Overall performance: Despite using a 1.5B-scale LLM, SIRLM surpasses reproduced LLM-based approaches ChatRule, MKGL, and KRLM in inductive reasoning.Those baselines use GPT-4o mini or LLaMA2-7B backbones, whereas SIRLM is based on a 1.5B-scale LLM.
  • Ablation study: Removing any module reduces performance, with especially pronounced degradation for the structural knowledge modules SRM and RCMP.The ablation results are reported in Figure 3, with detailed settings in Appendix J.2.
  • Backbone adaptability: SIRLM remains relatively stable across most LLM backbones, with only a slight performance decline on Qwen2.5-0.5B.The smaller model also shows the slowest convergence in rule-token generation accuracy, suggesting greater difficulty aligning structural representations.

6 CONCLUSION … C CONSTRUCTION DETAILS OF THE KG TOKENIZER AND THE RCMP REASONER

The paper identifies reasoning evidence perception drift in LLM-based KGR and proposes SIRLM to align KG structure with parametric knowledge through structure-internalized rule generation. Its appendices detail structural instructions, relational-graph construction, and tokenizer/reasoner adaptations for hyperedges.

  • 6 CONCLUSION: SIRLM addresses reasoning evidence perception drift by integrating a structure-internalized rule generator, KG tokenizer, and neuro-symbolic reasoner.The drift arises from misalignment between KG structural representations and LLM parametric knowledge, undermining reasoning effectiveness and faithfulness.
  • A DESIGN DETAILS OF QUERY INSTRUCTIONS: Query instructions combine fixed textual prompts with structural placeholders for entities, query relations, rule-body relations, and the termination token.The structural representations are derived from TKNKG in Eq. (6), with the masked segment covering atomic rule relations and < END >.
  • A DESIGN DETAILS OF QUERY INSTRUCTIONS: Structural instruction representations expose contextual entity and relation semantics while encoding high-order graph information with fewer tokens and without explicit textual names.The format is designed to improve structural information delivery and computational efficiency in LLM-based KGR.
  • B RELATIONAL GRAPH CONSTRUCTION: Relational graphs represent relative states between relations through relation-oriented hyperedges defined as R∗ in Eq. (1).These hyperedges connect relation nodes and differ from the edges of a typical KG.
  • B RELATIONAL GRAPH CONSTRUCTION: The relational-graph adjacency matrix is constructed from a KG using sparse matrices and maximum scatter operations over head and tail node dimensions.This produces sparse matrices Ah and At for representing relation connectivity from nodes.
  • C CONSTRUCTION DETAILS OF THE KG TOKENIZER AND THE RCMP REASONER: NBFNet requires different construction details on relational graphs because ternary hyperedges carry positional information for relational nodes.The relational-graph formulation therefore introduces position embeddings and trainable parameter matrices, whereas original-KG processing can ignore position information.

D DISCUSSION OF THE SRM IN-CONTEXT LAYER … II. Let

The analysis shows that SRM improves structural alignment and suppresses semantic drift, while RCMP preserves structural invariance and strictly refines SIL’s expressive power through structure-only rule signals. Together, the results establish stronger KG-grounded reasoning without changing the underlying message-passing operators or motif set.

  • D DISCUSSION OF THE SRM IN-CONTEXT LAYER: SRM outputs exhibit stronger structural representation alignment and better semantic-drift suppression than vanilla in-context learning outputs.The proposition compares SRM-based and vanilla in-context learning modules with respect to both structural alignment and drift suppression.
  • D DISCUSSION OF THE SRM IN-CONTEXT LAYER: SRM reorganizes hidden states by aligning structural components and suppressing text-only semantic bias, improving the score margin for correct structural relations.The analysis attributes improved KG-grounded relation generation to this hidden-state transformation.
  • E.1 A TWO-STAGE WL TEST FOR THE SIL MECHANISM: The two-stage WL test for SIL is both an upper bound and a tight characterization under injective message-passing choices.The test first colors relations on the relational graph and then colors entities on the KG.
  • E.2 A TWO-STAGE WL TEST FOR THE RCMP MECHANISM: RCMP generates structure-aware rules from structural tokens, accumulates occurrence-specific hidden states, and uses them to initialize the relational graph.No entity names, relation names, or textual attributes are used as rule-generator context; repeated relation occurrences contribute separately.
  • E.2 A TWO-STAGE WL TEST FOR THE RCMP MECHANISM: RCMP changes only relational-graph initialization while preserving the graph, relation and entity message-passing operators, under structural-token invariance and generation equivariance assumptions.These assumptions support the subsequent invariance and expressiveness analysis.
  • 3. Anchor separation of relations. Query relations are disjoint from non-query relations, i.e.: Under the stated assumptions, RCMP initialization is relation-invariant, yielding relation invariants in the relation encoder and link invariants in the entity encoder.The result follows from structural-token invariance, equivariant LLM generation, anchor separation, and injective RCMP operators.
  • II. Let: RCMP is at least as expressive as SIL because its refined two-stage WL test preserves the original test’s distinctions while enriching relation initialization.The message-passing architecture remains unchanged, so the constructive characterization continues to apply.
  • II. Let: RCMP is strictly more expressive in some cases: it separates query links that no SIL instance can separate when their relation initializations differ.The construction keeps the motif set fixed and gains expressiveness by refining the initial relation partition with structure-only autoregressive rule signals.

F TRAINING ALGORITHM · G COMPUTATIONAL COMPLEXITY

SIRLMPT trains by converting sampled query triplets into structurally tokenized instructions, applying relation-memory-augmented in-context learning and rule-based reasoning, then optimizing the accumulated SFT loss. Its computational cost covers relational-graph construction, NBFNet-bounded structural reasoning, and in-context learning with structural relation memory.

  • F TRAINING ALGORITHM: The training pipeline converts each query instruction into tokens, augments in-context learning with structural relation memory, and reasons over the missing entity.These operations correspond to Algorithm 1 steps 9–13, including the structural memory, in-context learning, missing-entity reasoning, and SFT-loss calculation.
  • F TRAINING ALGORITHM: Each training iteration samples b query triplets, constructs textual-structural instructions, and derives structural embeddings for the queried relation and head entity.The tokenizer is then obtained from these embeddings before subsequent memory construction and in-context learning.
  • F TRAINING ALGORITHM: After summing per-query SFT losses into Ltotal, SIRLM updates its trainable parameters with Ω←Ω−η∇(Ltotal) and increments the training step.The algorithm repeats this process until the maximum training step s and returns the optimized parameter set Ω.
  • G COMPUTATIONAL COMPLEXITY: Relational-graph construction dynamically accounts for negative sampling and begins by compressing A into sparse matrices Ah and At with complexity O(|E|2|R|).The subsequent motif-edge construction includes separate theoretical and sparse computational complexities for higher-order edges.
  • G COMPUTATIONAL COMPLEXITY: The KG tokenizer and RCMP reasoner are upper-bounded by NBFNet on G because |R| ≪|E|, yielding O(N(|T|d + |E|d2)) for an N-layer network.Here d denotes the embedding dimension, and each NBFNet layer costs O(|T|d + |E|d2).
  • G COMPUTATIONAL COMPLEXITY: The structural-memory in-context module combines self-attention O(L2F), memory key-value calculation O(LKd), and aggregation O(L(L + K)F).Because L ≫K, its upper-bound complexity is represented as O(L(L + K)F), where F is the LLM hidden dimension.
  • G COMPUTATIONAL COMPLEXITY: Table 4 evaluates SIRLMPT and SIRLMSFT using TFLOPs, memory footprint, and wall-clock time with batch size = 4 per GPU × 4 GPUs.For SFT, the comparison uses FB15k237-25 and FB15k237 v1 as the largest and smallest inductive datasets, respectively.

H DATASETS

The experiments evaluate SIRLM on 36 datasets grouped by train–test KG overlap into transductive, inductive entity, and fully inductive settings. Preprocessing mines closed paths within three hops and constructs rules for triplets with or without extracted paths.

  • Dataset categories: 36 datasets are divided by train–test KG overlap into transductive, inductive entity, and fully inductive categories.Transductive datasets share entities and relations between training and test KGs, whereas inductive entity datasets share relations but not entities.
  • Dataset categories: The transductive category includes FB15k-237, WN18RR, CoDEx-M, and NELL995, while the inductive entity category includes 12 GraIL datasets.The listed inductive entity variants cover FB15k237, WN18RR, and NELL995 versions V1–V4.
  • Rule mining: Rule mining extracts all closed paths within three hops for each complete training-KG triplet, although KG sparsity can leave some triplets without extractable paths.Figure 7 reports the proportions of triplets without rules and the rule-length distributions across datasets.
  • Rule mining: Triplets without extracted rules use the query relation as the rule body; others select the most frequent candidate rule body formed from directed relation sequences along closed paths.Candidate rule bodies are constructed by sequentially aggregating relation sequences for each closed path.

I EXPERIMENTAL HYPERPARAMETER SETTINGS · J DETAILS EXPERIMENTAL ANALYSIS

The paper evaluates SIRLM under four training paradigms with shared architectural hyperparameters. For pre-training, it specifies AdamW optimization, a 1e-4 learning rate, 1% warm-up, and a per-GPU batch size of 12.

  • I EXPERIMENTAL HYPERPARAMETER SETTINGS: SIRLM is evaluated with four training paradigms: End-to-End (E2E), Pre-Training (PT), SFT, and GRPO post-training.These paradigms are reported in Section 5.2.
  • I EXPERIMENTAL HYPERPARAMETER SETTINGS: The model architecture hyperparameters are uniformly set across all four training paradigms according to Table 6.The shared settings apply to E2E, PT, SFT, and GRPO post-training.
  • I EXPERIMENTAL HYPERPARAMETER SETTINGS: 1e-4 is the learning rate used in the PT paradigm.This setting is specified for pre-training.
  • I EXPERIMENTAL HYPERPARAMETER SETTINGS: AdamW is the optimizer used in the PT paradigm.The optimizer is paired with the reported pre-training learning rate.
  • I EXPERIMENTAL HYPERPARAMETER SETTINGS: 1% warm-up is used during PT training.The warm-up is described as a warm-up step setting.
  • I EXPERIMENTAL HYPERPARAMETER SETTINGS: 12 is the batch size per GPU in the PT paradigm.The passage reports this as the per-GPU batch size.

J.1 ADDITIONAL ANALYSIS OF MAIN EXPERIMENTS · J.2 DETAILS ABLATION ANALYSIS · J.3 ADDITIONAL ANALYSIS ON DIFFERENT LLM BACKBONES

SIRLM improves faithfulness by enforcing structurally grounded rule generation, while its gains depend on KG density and backbone scale. Ablations isolate the contributions of structural representations, structural relation memory, and rule-constrained propagation, and larger backbones converge faster.

  • J.1 ADDITIONAL ANALYSIS OF MAIN EXPERIMENTS: Structural representations enable broader structural pattern induction and recognition of unfamiliar entities and relations through structural invariance.This contrasts with traditional embedding methods that initialize fixed entity and relation representations for specific KGR scenarios.
  • J.1 ADDITIONAL ANALYSIS OF MAIN EXPERIMENTS: SIRLM enforces structurally grounded rules over KGs, reducing LLMs’ tendency to prioritize pretrained knowledge over structural evidence.This design couples reasoning with KG-grounded evidence rather than relying solely on parametric knowledge.
  • J.2 DETAILS ABLATION ANALYSIS: The ablation results are summarized using average MRR and Hit10 across IndE and FullInd scenarios.Table 10 reports the performance of the ablation variants on different datasets.
  • J.1 ADDITIONAL ANALYSIS OF MAIN EXPERIMENTS: SIRLM’s performance gains correlate with KG sparsity, but it performs slightly worse on sparse datasets such as the WN18RR series.The results highlight a limitation of structural rule-based reasoning under sparse conditions.
  • J.2 DETAILS ABLATION ANALYSIS: The ablation study evaluates SIRLMPT variants that remove textual structural representations, structural relation memory, or rule-constrained message propagation.The -MMQI, -SRM, and -RCMP variants respectively isolate these components while retaining the remaining SIRLM design where specified.
  • J.3 ADDITIONAL ANALYSIS ON DIFFERENT LLM BACKBONES: Reasoning performance positively correlates with the parameter scale of the LLM backbone.Larger backbones are attributed to fitting the newly injected structured representation space more quickly.
  • J.3 ADDITIONAL ANALYSIS ON DIFFERENT LLM BACKBONES: Around 200 steps, Qwen2.5-7b and Llama2-7b approach rule-generation convergence, whereas Qwen2.5-0.5b and Qwen2.5-1.5b require approximately 400 steps.Figure 9 reports these convergence trends on WN18RR v1.

J.4 CASE STUDY AND ERROR ANALYSIS

The case studies show that SIRLM can generate exact or semantically alternative reasoning rules that yield correct predictions, but irrelevant rule relations cause errors. Overall, predictive effectiveness and interpretability depend critically on the semantic quality of the generated rule body.

  • Successful rule generation: Cases 1 and 2 generate rules exactly matching the ground-truth multi-hop pattern, placing the correct entities among top-ranked candidates with relatively high confidence.The correct entities are “Best Academy Picture Award” and “University of Texas at Austin”.
  • Alternative reasoning paths: Cases 3 and 4 produce rules that deviate from the annotated path yet correctly predict “Tokyo” and “Columbia Records” through alternative paths with similar structural semantics.The differing atomic relations remain semantically similar in the representation space.
  • Failure cases: Cases 5 and 6 introduce irrelevant atomic relations, diverting reasoning from the correct semantic direction and producing incorrect top-ranked candidates.These generated relations differ substantially from the ground-truth rule.
  • Error analysis: SIRLM’s effectiveness depends critically on rule-body quality: semantically accurate rules improve interpretability and prediction, whereas inconsistent rules significantly degrade performance.The case analysis links rule semantics to both faithful reasoning behavior and predictive outcomes.

K LIMITATIONS AND FUTURE WORK

SIRLM alleviates reasoning evidence perception drift but retains limitations in computational scalability and sparse-KG reasoning. Future work targets more efficient evidence extraction and improved handling of limited structural rules.

  • Overall limitations: SIRLM alleviates reasoning evidence perception drift caused by the knowledge representation gap between LLMs and KGs, but still has several potential limitations.The paper frames these limitations as directions for future research.
  • Computational complexity: SIRLM performs real-time relational graph updates and message passing over the entire KG during training, creating a computational bottleneck for large-scale KGs.Sparse operators reduce graph-processing cost in practice, but the upper bound remains quadratic in the number of entities.
  • Sparse KG reasoning: SIRLM still has significant room for improvement on sparse KGs because limited structural-rule diversity and completeness hinder rule learning and generation by LLMs.The paper attributes this limitation to SIRLM’s rule-driven KGR framework and proposes query-driven evidence graph extraction as a future direction for computational efficiency.
Loading 2608.17443v1…