Structure-Internalized Rule Language Model for Faithful Knowledge Graph Reasoning

# Structure-Internalized Rule Language Model for Faithful Knowledge Graph Reasoning
Source: [https://arxiv.org/html/2608.17443](https://arxiv.org/html/2608.17443)
Xingrui ZhuoAffiliation:Key Laboratory of Knowledge Engineering with Big Data \(Hefei University of Technology\),Ministry of Education, ChinaAffiliation:School of Computer Science and Information Engineering, Hefei University of Technology, ChinaJiapu WangAffiliation:Nanjing University of Science and Technology, Chinazxr@mail\.hfut\.edu\.cn, jiapu\.wang@njust\.edu\.cn,manzonghuang@mail\.hfut\.edu\.cn, wugq@hfut\.edu\.cn, xwu@hfut\.edu\.cnManzong HuangAffiliation:Key Laboratory of Knowledge Engineering with Big Data \(Hefei University of Technology\),Ministry of Education, ChinaAffiliation:School of Computer Science and Information Engineering, Hefei University of Technology, ChinaGongqing WuThanks:Corresponding authorAffiliation:Key Laboratory of Knowledge Engineering with Big Data \(Hefei University of Technology\),Ministry of Education, ChinaAffiliation:School of Computer Science and Information Engineering, Hefei University of Technology, ChinaXindong Wu††footnotemark:Affiliation:Key Laboratory of Knowledge Engineering with Big Data \(Hefei University of Technology\),Ministry of Education, ChinaAffiliation:School of Computer Science and Information Engineering, Hefei University of 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 asreasoning evidence perception driftof 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 SIRLM111Our source codes are available at[https://github\.com/lazyloafer/SIRLM](https://github.com/lazyloafer/SIRLM)\.

## 1Introduction

Knowledge Graphs \(KGs\)\([Ji et al\. 2022](https://arxiv.org/html/2608.17443#bib.bib17)\)represent real\-world facts through structural triplets composed of entities and relations, maintaining a unified framework for storing and querying large\-scale knowledge\. However, KGs are generally incomplete, which leaves many potential facts unobserved\. Consequently, Knowledge Graph Reasoning \(KGR\)\([Liang et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib24)\)has been proposed to leverage the available KG context to infer missing facts, which provides more sufficient evidence for knowledge\-driven applications\([Huang et al\. 2026](https://arxiv.org/html/2608.17443#bib.bib13);[Luo et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib26)\)\.

Traditional KGR methods mainly focus on knowledge embedding\([Sun et al\. 2019](https://arxiv.org/html/2608.17443#bib.bib33)\)and logical rule learning\([Sadeghian et al\. 2019](https://arxiv.org/html/2608.17443#bib.bib31)\), which achieve efficient fact prediction via structural representation learning and interpretable reasoning\([Wan & Du 2021](https://arxiv.org/html/2608.17443#bib.bib37)\), respectively\. However, these methods generally rely on specific contextual instances within a KG\. When confronted with an unfamiliar KG, they often require complex rule mining or model retraining, which makes it difficult for these methods to generalize to more challenging KGR scenarios\([Zhu et al\. 2022](https://arxiv.org/html/2608.17443#bib.bib50);[Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)\.

Recently, Large Language Models \(LLMs\)\([Naveed et al\. 2025](https://arxiv.org/html/2608.17443#bib.bib28)\), pre\-trained on massive natural language corpora, have demonstrated outstanding performance in various reasoning tasks\. Latest studies have confirmed that LLMs can achieve breakthrough success on KGR tasks\([Kim et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib20);[Wang et al\. 2024a](https://arxiv.org/html/2608.17443#bib.bib38);[Zhuo et al\. 2025b](https://arxiv.org/html/2608.17443#bib.bib52)\)\. With the support of flexible in\-context learning capabilities, LLMs integrate inherent parametric knowledge with structural context of KGs and exhibit remarkable knowledge emergence\([Pan et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib29)\), thereby discovering new facts in KGs that are not explicitly observed\. More importantly, compared with traditional KGR methods, LLM\-based approaches show stronger transferability when facing previously unseen KG structures in inductive reasoning settings\([Wang et al\. 2024b](https://arxiv.org/html/2608.17443#bib.bib39);[Guo et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib11);[Zhuo et al\. 2026](https://arxiv.org/html/2608.17443#bib.bib53)\)\.

![Refer to caption](https://arxiv.org/html/2608.17443v1/challenge.png)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\.Despite significant accomplishments, existing LLM\-based KGR methods still struggle to address the representation inconsistency between structural and parametric knowledge\([Jiang et al\. 2024b](https://arxiv.org/html/2608.17443#bib.bib19)\), which constrains the ability of LLMs to grasp structural KG context during reasoning\. This limitation is reflected in the fact that most LLMs tend to select reasoning evidence from a KG based on their pre\-trained semantic preferences, rather than strictly following the structural constraints induced from the KG\. As a result, LLMs are inclined to generate reasoning logic that appears semantically plausible but is difficult to ground in a KG, leading to the reasoning bias and the faithfulness degradation of results\. We refer to this issue as thereasoning evidence perception driftproblem of LLMs over KGs, meaning that inconsistencies in knowledge representation hinder LLMs from identifying reasonable evidence from KGs, thereby limiting the effectiveness of LLM reasoning\.

Figure[1](https://arxiv.org/html/2608.17443#S1.F1)illustrates the harm that such a perception shift brings to LLMs\. In this case, LLMs tend to accept the assertion “films produced or distributed by the same company are likely to be released in the same region” based on their semantic preferences\. As a result, the evidence space is anchored to the sub\-KG marked inredin Figure[1](https://arxiv.org/html/2608.17443#S1.F1)\. However, the structural rule that can be explicitly induced from the KG, namelyrelease\_region\(X, Y\) = language\(X, Z\)∧\\landspeak\_in\(X, Z\), is instead misjudged as a weakly related evidence space \(marked ingreenin Figure[1](https://arxiv.org/html/2608.17443#S1.F1)\)\. In addition, for relation paths represented by anonymized identifiers \(marked inpurplein Figure[1](https://arxiv.org/html/2608.17443#S1.F1)\), the absence of natural language semantics often leads LLMs to deliberately ignore this structural evidence that could potentially support correct reasoning\. This preference for pre\-trained semantic cues and the neglect of structural context cause the LLM’s reasoning process to deviate from the correct KG\-grounded evidence space, ultimately producing erroneous results\.

To address the aforementioned limitation, we propose a Structure\-Internalized Rule Language Model \(SIRLM\), which enables LLMs to accurately perceive KG\-grounded evidence for faithful reasoning\. Overall, SIRLM consists of a KG tokenizer, a Structure\-Internalized Rule Generator \(SIRG\) and a neuro\-symbolic reasoner\. In this framework, SIRG serves as the core module to generate structurally grounded rules\. Therefore, we propose an in\-context learning block based on a Structural Relation Memory \(SRM\) mechanism, which allows SIRG to align pre\-trained knowledge with structural context during rule generation\. Complementing SIRG, the KG tokenizer is built upon the Structural Invariance Learning \(SIL\) principle\([Galkin et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib9);[Huang et al\. 2025a](https://arxiv.org/html/2608.17443#bib.bib15);[Zhang et al\. 2024b](https://arxiv.org/html/2608.17443#bib.bib47)\), which encodes KG elements into universal structure representations, enabling LLMs to grasp them in the form of new tokens without specific textual annotations\. Furthermore, we design the neuro\-symbolic reasoner as a rule executor based on Rule\-Constraint Message Propagation \(RCMP\), which feeds back a rule faithfulness metric composed of reasoning conclusions to SIRG, forming a closed\-loop optimization that reinforces structurally consistent reasoning\.

In terms of model training, SIRLM can seamlessly integrate with standard Supervised Fine\-Tuning \(SFT\) and post\-training frameworks of LLMs\. This capability endows SIRLM with significant transferable advantages across a wide range of cross\-scenario KGR tasks\.

Our main contributions can be summarized as follows:

1. ∙\\bulletWe propose a structure\-internalized rule language model to mitigate the reasoning evidence perception drift of LLMs over KGs, enabling reliable LLM\-based KG reasoning\.
2. ∙\\bulletWe design a structure\-internalized rule generator with a structural relation memory to coordinate LLM knowledge with KG context, together with a SIL\-based KG tokenizer and a RCMP\-based rule reasoner for universal structure representation learning and faithful rule execution feedback\.
3. ∙\\bulletSIRLM can seamlessly integrate with standard LLM training frameworks such as SFT and GRPO, achieving generalizable reasoning across unknown KGs\.
4. ∙\\bulletExtensive experimental results conducted on 36 datasets demonstrate that SIRLM exhibits remarkable reasoning capabilities in both transductive and inductive KGR scenarios\.

## 2Related Work

KGR studies have long focused on mining latent facts from KGs, providing interpretable knowledge support for downstream tasks\. Traditional KGR methods adopt structural representation learning techniques by projecting entities and relations into appropriate embedding spaces, such as Euclidean\([Bordes et al\. 2013](https://arxiv.org/html/2608.17443#bib.bib3)\), complex\([Trouillon et al\. 2016](https://arxiv.org/html/2608.17443#bib.bib36)\), or manifold spaces\([Xiao et al\. 2016](https://arxiv.org/html/2608.17443#bib.bib41)\), to infer latent associations between entities and relations\. To ensure interpretability in reasoning, some studies introduce rule\-based approaches that leverage techniques such as rule mining\([Qu et al\. 2021](https://arxiv.org/html/2608.17443#bib.bib30);[Sadeghian et al\. 2019](https://arxiv.org/html/2608.17443#bib.bib31)\), relational path retrieval\([Das et al\. 2018](https://arxiv.org/html/2608.17443#bib.bib6)\), or Markov decision processes\([Lao & Cohen 2010](https://arxiv.org/html/2608.17443#bib.bib21)\)to perform KGR while providing explicit reasoning paths\.

As KGs scale up, early embedding\-based and rule\-based methods struggle to adapt to more complex knowledge structures\. Consequently, researchers have incorporated Graph Neural Networks \(GNN\) into KGR\([Galkin et al\. 2022](https://arxiv.org/html/2608.17443#bib.bib8);[Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34);[Zhu et al\. 2022](https://arxiv.org/html/2608.17443#bib.bib50)\)\. Methods such as NBFNet\([Zhu et al\. 2021](https://arxiv.org/html/2608.17443#bib.bib49)\), RED\-GNN\([Zhang & Yao 2022](https://arxiv.org/html/2608.17443#bib.bib46)\), and InGram\([Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)exploit the message\-passing mechanism of GNNs to capture fine\-grained structural context about entities and relations, providing stronger evidence for comprehensive reasoning\. Building on this, some studies\([Galkin et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib9);[Huang et al\. 2025a](https://arxiv.org/html/2608.17443#bib.bib15);[Zhang et al\. 2024b](https://arxiv.org/html/2608.17443#bib.bib47);[Cui et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib5)\)focus on improving the generalization of KGR models to out\-of\-distribution graph structures\. These approaches aim to discover reusable minimal subgraph patterns within KGs and learn universal structural representations of entities and relations,i\.e\., Structural Invariance Learning \(SIL\)\([Galkin et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib9)\)\. This technique enables unknown KG elements to be projected into learned structural patterns, thereby enhancing model performance in complex reasoning scenarios\.

In recent years, LLM\-based KGR has emerged as a new research focus\([Wang et al\. 2024b](https://arxiv.org/html/2608.17443#bib.bib39);[Zhuo et al\. 2025a](https://arxiv.org/html/2608.17443#bib.bib51);[Zhuo et al\. 2026](https://arxiv.org/html/2608.17443#bib.bib53)\)\. By leveraging the strong knowledge emergence and in\-context learning capabilities of LLMs\([Pan et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib29)\), these approaches uncover deeper facts in KGs\. For example, methods such as KICGPT\([Wei et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib40)\)and ChatRule\([Luo et al\. 2025](https://arxiv.org/html/2608.17443#bib.bib27)\)adopt theLLM\-planning and KG\-retrievalparadigm to prompt LLMs in performing structural reasoning over given sub\-KGs\. Meanwhile, approaches such as KoPA\([Zhang et al\. 2024a](https://arxiv.org/html/2608.17443#bib.bib45)\), MKGL\([Guo et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib11)\), and KRLM\([Zhuo et al\. 2026](https://arxiv.org/html/2608.17443#bib.bib53)\)rely on fine\-tuning techniques to inject structural knowledge into the pre\-trained space of LLMs, aligning their parametric knowledge with the structural knowledge of KGs\. Despite significant development, existing LLM\-based methods still face the challenge in handling the widely observed KG\-LLM representation gaps\. Under this condition, structural knowledge that is beneficial for reasoning in KGs is often regarded by LLMs as irrelevant evidence, leading to a phenomenon known asevidence perception drift\.

The aforementioned challenge have prompted us to propose a more refined mechanism for internalizing structural knowledge, which uses structural rule generation as a feedback to guide LLMs in perceiving grounded structural logic over KGs, thereby improving model reasoning\.

## 3Preliminaries

In this section, we introduce the background and key conceptions of our study\.

### 3\.1Knowledge Graph Reasoning

We define a KG as𝒢=\(ℰ,ℛ,𝒯\)\\mathcal\{G\}=\(\\mathcal\{E\},\\mathcal\{R\},\\mathcal\{T\}\), whereℰ\\mathcal\{E\}andℛ\\mathcal\{R\}denote the sets of entities and relations, respectively\.𝒯=\{<eh,rq,et\>\|eh,et∈ℰ,rq∈ℛ\}\\mathcal\{T\}=\\\{<e\_\{h\},r\_\{q\},e\_\{t\}\>\|e\_\{h\},e\_\{t\}\\in\\mathcal\{E\},r\_\{q\}\\in\\mathcal\{R\}\\\}is the set of triples\. Each triple represents a factual statement indicating that the head entityehe\_\{h\}and the tail entityete\_\{t\}are connected via relationrqr\_\{q\}\.

KGR aims to infer new facts of the form<eh,rq,?\>∉𝒯<e\_\{h\},r\_\{q\},?\>\\notin\\mathcal\{T\}\. Given a training KG𝒢t​r=\(ℰt​r,ℛt​r,𝒯t​r\)\\mathcal\{G\}\_\{tr\}=\(\\mathcal\{E\}\_\{tr\},\\mathcal\{R\}\_\{tr\},\\mathcal\{T\}\_\{tr\}\)and a inference KG𝒢i​n​f=\(ℰi​n​f,ℛi​n​f,𝒯i​n​f\)\\mathcal\{G\}\_\{inf\}=\(\\mathcal\{E\}\_\{inf\},\\mathcal\{R\}\_\{inf\},\\mathcal\{T\}\_\{inf\}\), KGR tasks are typically categorized intotransductive\(ℰt​r=ℰi​n​f\\mathcal\{E\}\_\{tr\}=\\mathcal\{E\}\_\{inf\},ℛt​r=ℛi​n​f\\mathcal\{R\}\_\{tr\}=\\mathcal\{R\}\_\{inf\}, and𝒯t​r≠𝒯i​n​f\\mathcal\{T\}\_\{tr\}\\neq\\mathcal\{T\}\_\{inf\}\) andinductivesetting \(ℰt​r≠ℰi​n​f\\mathcal\{E\}\_\{tr\}\\neq\\mathcal\{E\}\_\{inf\}orℛt​r≠ℛi​n​f\\mathcal\{R\}\_\{tr\}\\neq\\mathcal\{R\}\_\{inf\}, and𝒯t​r≠𝒯i​n​f\\mathcal\{T\}\_\{tr\}\\neq\\mathcal\{T\}\_\{inf\}\)\. The inductive setting requires KGR models to generalize to previously unseen entities or relations, thereby ensuring strong extrapolation and generalization capabilities\.

### 3\.2Structural Invariance Learning of KG

SIL of KG derives universal structural representations for unseen entities and relations through a relational graph and a Neural Bellman\-Ford Network \(NBFNet\)\([Zhu et al\. 2021](https://arxiv.org/html/2608.17443#bib.bib49)\)\.

The relational graphis designed to characterize the structural motifs between relations in a KG\. Let the relational graph be defined as𝒢r=\(ℛ,ℛ∗,𝒯∗\)\\mathcal\{G\}\_\{r\}=\(\\mathcal\{R\},\\mathcal\{R\}^\{\*\},\\mathcal\{T\}^\{\*\}\), whereℛ\\mathcal\{R\}corresponds to the set of relations in the original KG𝒢\\mathcal\{G\}and serves as the node set of𝒢r\\mathcal\{G\}\_\{r\}\.ℛ∗\\mathcal\{R\}^\{\*\}denotes the set of motif edges to connect relation nodes\. The detailed definition of motif edges is provided inAppendix[B](https://arxiv.org/html/2608.17443#A2)\.

Under this inductive paradigm, any relation in an arbitrary KG can be mapped into𝒢r\\mathcal\{G\}\_\{r\}\. By aggregating these motif edges, we can obtain the universal structural representation for any relation\.

NBFNetis a GNN that generalizes path formulations over graph nodes\. Given a query triple<eh,rq,?\><e\_\{h\},r\_\{q\},?\>, we first performNBFNet​\(U,𝑹∗,𝒢r\)\\text\{NBFNet\}\(U,\\bm\{R\}^\{\*\},\\mathcal\{G\}\_\{r\}\), anNN\-layer NBFNet, over𝒢r\\mathcal\{G\}\_\{r\}:

NBFNet​\(U,𝑹∗,𝒢r\)=\{𝒓\(0\)j\|q=Init\(rj,U\),whereU=\{<rq,𝟏d\>\},rq,rj∈ℛ,𝒓j\|q\(n\)=Up​\(𝒓j\|q\(n−1\),Agg​\(\{Msg​\(𝒓z\|q\(n−1\),𝒓∗\)\|rz∈𝒩r∗​\(rj\)\}\|r∗∈ℛ∗,𝒓∗∈𝑹∗\)\)\\displaystyle\\text\{NBFNet\}\(U,\\bm\{R\}^\{\*\},\\mathcal\{G\}\_\{r\}\)=\\begin\{cases\}\\bm\{r\}^\{\(0\)\}\_\{j\|q\}=\\text\{\{Init\}\}\(r\_\{j\},U\),\\hskip 5\.69054pt\\text\{where \}U=\\\{<r\_\{q\},\\mathbf\{1\}^\{d\}\>\\\},r\_\{q\},r\_\{j\}\\in\\mathcal\{R\},\\\\ \\bm\{r\}^\{\(n\)\}\_\{j\|q\}=\\text\{\{Up\}\}\\Big\(\\bm\{r\}\_\{j\|q\}^\{\(n\-1\)\},\\text\{\{Agg\}\}\\big\(\\\{\\text\{\{Msg\}\}\(\\bm\{r\}\_\{z\|q\}^\{\(n\-1\)\},\\bm\{r\}^\{\*\}\)\|r\_\{z\}\\in\\mathcal\{N\}\_\{r^\{\*\}\}\(r\_\{j\}\)\\\}\|r^\{\*\}\\in\\mathcal\{R\}^\{\*\},\\bm\{r\}^\{\*\}\\in\\bm\{R\}^\{\*\}\\big\)\\Big\)\\\\ \\end\{cases\}\(1\)whereUUis a tuple set that stores conditions that satisfy non\-zero initialization nodes,1d\\textbf\{1\}^\{d\}is add\-dimensional full\-one vector,n∈\[1,N\]n\\in\[1,N\]is the layer index, and𝑹∗∈ℝ\|ℛ∗\|×d\\bm\{R\}^\{\*\}\\in\\mathbb\{R\}^\{\|\\mathcal\{R\}^\{\*\}\|\\times d\}is the randomly initialized embeddings of motif edges\.Init​\(⋅\)\\text\{\{Init\}\}\(\\cdot\),Msg​\(⋅\)\\text\{\{Msg\}\}\(\\cdot\),Agg​\(⋅\)\\text\{\{Agg\}\}\(\\cdot\), andUp​\(⋅\)\\text\{\{Up\}\}\(\\cdot\)are an indicator function, the DistMult message propagation\([Yang et al\. 2015](https://arxiv.org/html/2608.17443#bib.bib43)\), the summation aggregation operation, and a Multi\-Layer Perceptron \(MLP\), respectively\. The details of Eq\. \([1](https://arxiv.org/html/2608.17443#S3.E1)\) is provided in Eq\. \([17](https://arxiv.org/html/2608.17443#A3.E17)\)\.

According to Eq\. \([1](https://arxiv.org/html/2608.17443#S3.E1)\), we obtain the structural representations of all relations conditioned onrqr\_\{q\}, denoted as𝑹\|q=NBFNet\(U,𝑹∗,𝒢r\)\\bm\{R\}\_\{\|q\}=\\text\{NBFNet\}\(U,\\bm\{R\}^\{\*\},\\mathcal\{G\}\_\{r\}\)\. Based on this, we further compute the structural representations of all entities conditioned onehe\_\{h\}as𝑬\|h\\bm\{E\}\_\{\|h\}:

𝑬\|h=NBFNet\(\{<eh,𝒓q\|q\(N\)\>\},𝑹\|q,𝒢\),𝒓q\|q\(N\)∈𝑹\|q\.\\displaystyle\\bm\{E\}\_\{\|h\}=\\text\{NBFNet\}\(\\\{<e\_\{h\},\\bm\{r\}\_\{q\|q\}^\{\(N\)\}\>\\\},\\bm\{R\}\_\{\|q\},\\mathcal\{G\}\),\\hskip 5\.69054pt\\bm\{r\}\_\{q\|q\}^\{\(N\)\}\\in\\bm\{R\}\_\{\|q\}\.\(2\)The details of Eq\. \([2](https://arxiv.org/html/2608.17443#S3.E2)\) is provided in Eq\. \([18](https://arxiv.org/html/2608.17443#A3.E18)\)\.

Finally, we compute scores for the candidate tail entities of the query triple<eh,rq,?\><e\_\{h\},r\_\{q\},?\>:

sKG\(i\)=𝒮KG\(𝒆i\|h\(N\)\|\|𝒓q\|q\(N\)\)i∈\[1,\|ℰ\|\],\\displaystyle s\_\{\\text\{KG\}\}^\{\(i\)\}=\\mathcal\{S\}\_\{\\text\{KG\}\}\(\\bm\{e\}\_\{i\|h\}^\{\(N\)\}\|\|\\bm\{r\}\_\{q\|q\}^\{\(N\)\}\)\\hskip 5\.69054pti\\in\[1,\|\\mathcal\{E\}\|\],\(3\)where𝒆i\|h∈𝑬\|h\\bm\{e\}\_\{i\|h\}\\in\\bm\{E\}\_\{\|h\}and𝒮KG:ℝ2​d→ℝ1\\mathcal\{S\}\_\{\\text\{KG\}\}:\\mathbb\{R\}^\{2d\}\\rightarrow\\mathbb\{R\}^\{1\}is a scoring function\.

### 3\.3In\-context learning and next\-token prediction of LLM

In context learning:LetXXbe an instruction andTKNLLM\\text\{TKN\}\_\{\\text\{LLM\}\}denote the pre\-trained token embedding table of LLM\. By looking upXXinTKNLLM\\text\{TKN\}\_\{\\text\{LLM\}\}, the instruction is transformed into a sequenceTKNLLM​\[X\]=𝑿∈ℝL×F\\text\{TKN\}\_\{\\text\{LLM\}\}\[X\]=\\bm\{X\}\\in\\mathbb\{R\}^\{L\\times F\}withLLFF\-dimensional token embeddings\. The LLM aggregates each token embedding𝒙i∈𝑿\\bm\{x\}\_\{i\}\\in\\bm\{X\}together with the embeddings of all preceding tokens through the self\-attention mechanism to perform in\-context learning, thereby producing the hidden state of𝒙i\\bm\{x\}\_\{i\}, defined as𝒉i=InCon​\(𝒙i,𝑿≤i\)\\bm\{h\}\_\{i\}=\\text\{InCon\}\(\\bm\{x\}\_\{i\},\\bm\{X\}\_\{\\leq i\}\):

InCon​\(𝒙i,𝑿≤i\)=FFN​\(softmax​\(fQ​\(𝒙i\)​\[fK​\(𝑿≤i\)\]TF\)​fV​\(𝑿≤i\)\),\\displaystyle\\text\{InCon\}\(\\bm\{x\}\_\{i\},\\bm\{X\}\_\{\\leq i\}\)=\\text\{FFN\}\\Big\(\\text\{softmax\}\\big\(\\frac\{f\_\{Q\}\(\\bm\{x\}\_\{i\}\)\[f\_\{K\}\(\\bm\{X\}\_\{\\leq i\}\)\]^\{\\text\{T\}\}\}\{\\sqrt\{F\}\}\\big\)f\_\{V\}\(\\bm\{X\}\_\{\\leq i\}\)\\Big\),\(4\)wheref\{Q,K,V\}​\(⋅\):ℝF→ℝFf\_\{\\\{Q,K,V\\\}\}\(\\cdot\):\\mathbb\{R\}^\{F\}\\rightarrow\\mathbb\{R\}^\{F\}are pre\-trained linear layers andFFN​\(⋅\):ℝF→ℝF\\text\{FFN\}\(\\cdot\):\\mathbb\{R\}^\{F\}\\rightarrow\\mathbb\{R\}^\{F\}is a pre\-trained Feed Forward Network \(FFN\)\.

Next\-token prediction:Based on Eq\. \([4](https://arxiv.org/html/2608.17443#S3.E4)\), the new token generated by LLM conditioned on the input instructionXXcan be expressed as:

𝒙^z\+1←arg​max𝒙^∈TKNLLMP𝚯\(𝒙^\|InCon\(𝒙^z,\[𝑿:𝑿^≤z\]\)\),\\displaystyle\\hat\{\\bm\{x\}\}\_\{z\+1\}\\leftarrow\\underset\{\\hat\{\\bm\{x\}\}\\in\\text\{TKN\}\_\{\\text\{LLM\}\}\}\{\\text\{arg\}\\max\}P\_\{\\bm\{\\Theta\}\}\(\\hat\{\\bm\{x\}\}\|\\text\{InCon\}\(\\hat\{\\bm\{x\}\}\_\{z\},\[\\bm\{X\}:\\hat\{\\bm\{X\}\}\_\{\\leq z\}\]\)\),\(5\)where𝑿^≤z∈ℝz×F\\hat\{\\bm\{X\}\}\_\{\\leq z\}\\in\\mathbb\{R\}^\{z\\times F\}is the embeddings of the firstzzgenerated tokens and\[:\]\[:\]denotes a row\-wise concatenation operation\.InCon\(𝒙^z,\[𝑿:𝑿^≤z\]\)\\text\{InCon\}\(\\hat\{\\bm\{x\}\}\_\{z\},\[\\bm\{X\}:\\hat\{\\bm\{X\}\}\_\{\\leq z\}\]\)represents the hidden state of thezz\-th generated token𝒙^z∈𝑿^≤z\\hat\{\\bm\{x\}\}\_\{z\}\\in\\hat\{\\bm\{X\}\}\_\{\\leq z\}, which is projected through a MLP module parameterized by𝚯\\bm\{\\Theta\}to produce the generation probability of the \(zz\+1\)\-th token\.

![Refer to caption](https://arxiv.org/html/2608.17443v1/model.png)Figure 2:Overall architecture and training framework of SILRM\. Given a query triplet, we first1

convert it into an instructionXXand input the triplet into the KG tokenizer to obtain structural embeddings of entities and relations\. These structural representations are then2

tokenized along with the LLM pre\-trained tokenizer forXX\. Next, SIGR reads the aforementioned tokens and3

generates structural rules for the RCMP reasoner\. Afterwards,4

the reasoner executes rules and performs neuro\-symbolic reasoning, ultimately obtaining scores for candidate entities\.

## 4Methodology

In this section, we elaborate on the proposed SILRM in detail\. As illustrated in Figure[2](https://arxiv.org/html/2608.17443#S3.F2), SILRM consists of a structure\-internalized rule generator and a KG toolkit\. In the following, we describe our method from four aspects: the construction of the query instruction and the KG tokenizer \(Section[4\.1](https://arxiv.org/html/2608.17443#S4.SS1)\), LLM\-based in\-context learning and rule generation \(Section[4\.2](https://arxiv.org/html/2608.17443#S4.SS2)\), and rule reasoning \(Section[4\.3](https://arxiv.org/html/2608.17443#S4.SS3)\)\. Finally, we introduce how our framework seamlessly integrates with LLM SFT and post\-training strategies inSection[4\.4](https://arxiv.org/html/2608.17443#S4.SS4)\.

### 4\.1Construction of Query instruction and KG tokenizer

Given a query triplet<eh,rq,?\><e\_\{h\},r\_\{q\},?\>, we design a query instructionXXsuitable for generating structural rules using LLMs, whose detailed schema is provided inAppendix[A](https://arxiv.org/html/2608.17443#A1)\.

In the instruction schema, strings of the form<Ent ID\><\\text\{Ent ID\}\>and<Rel ID\><\\text\{Rel ID\}\>are treated as indivisible structural token identifiers, which denote specific entities and relations in a KG, respectively\.<END\><\\text\{END\}\>serves as a rule body termination\. These structural tokens are embedded via a KG tokenizerTKNKG\\text\{TKN\}\_\{\\text\{KG\}\}and are jointly processed with the pre\-trained LLM tokenizerTKNLLM\\text\{TKN\}\_\{\\text\{LLM\}\}to encode the remaining text in instructionXX\. To unify the processing of structural and textual tokens inXX, the tokenizer of the rule generator can be expressed as the combination ofTKNKG\\text\{TKN\}\_\{\\text\{KG\}\}andTKNLLM\\text\{TKN\}\_\{\\text\{LLM\}\}:

TKNRG=\[TKNLLM:TKNKG\],TKNKG=fup\(\[𝒓end:𝑬\|h:𝑹\|q\]\),\\displaystyle\\text\{TKN\}\_\{\\text\{RG\}\}=\[\\text\{TKN\}\_\{\\text\{LLM\}\}:\\text\{TKN\}\_\{\\text\{KG\}\}\],\\hskip 5\.69054pt\\text\{TKN\}\_\{\\text\{KG\}\}=f\_\{\\text\{up\}\}\(\[\\bm\{r\}\_\{\\text\{end\}\}:\\bm\{E\}\_\{\|h\}:\\bm\{R\}\_\{\|q\}\]\),\(6\)where𝒓end∈ℝd\\bm\{r\}\_\{\\text\{end\}\}\\in\\mathbb\{R\}^\{d\}is a randomly initialized embedding for<END\><\\text\{END\}\>,fup​\(⋅\):ℝd→ℝFf\_\{\\text\{up\}\}\(\\cdot\):\\mathbb\{R\}^\{d\}\\rightarrow\\mathbb\{R\}^\{F\}is a trainable linear layer, and𝑹\|q∈ℝ\|ℛ\|×d\\bm\{R\}\_\{\|q\}\\in\\mathbb\{R\}^\{\|\\mathcal\{R\}\|\\times d\}and𝑬\|h∈ℝ\|ℰ\|×d\\bm\{E\}\_\{\|h\}\\in\\mathbb\{R\}^\{\|\\mathcal\{E\}\|\\times d\}are the structural embeddings of entities and relations obtained by Eqs\. \([1](https://arxiv.org/html/2608.17443#S3.E1)\) and \([2](https://arxiv.org/html/2608.17443#S3.E2)\), respectively\. It is important to note that the pre\-trainedTKNLLM\\text\{TKN\}\_\{\\text\{LLM\}\}remain frozen and onlyTKNKG\\text\{TKN\}\_\{\\text\{KG\}\}is trained\. This allows LLMs to perceive the structural representations of the KG through newly introduced tokens\.

### 4\.2In\-context Learning and Rule Generation

To enable LLMs to generate executable rules, we design an in\-context learning strategy with the SRM mechanism and subsequently perform autoregressive relation token prediction, which ensures that the generated rules can be grounded in the corresponding KG, providing interpretable evidence for subsequent knowledge reasoning\.

In\-context learning with structural relation memory:To guide the LLM toward structure\-internalized rule generation, we adapt the pre\-trained attention layer by integrating a structural relation memory mechanism\. Given a query triplet<eh,rq,?\><e\_\{h\},r\_\{q\},?\>, we first compute a relevance score for each relationrj∈ℛr\_\{j\}\\in\\mathcal\{R\}and select the top\-KKrelation as the memory𝑹mem\\bm\{R\}\_\{\\text\{mem\}\}:

𝑹mem=\{𝒓k∈𝑹\|q\|srel\(k\)∈TopK\(\{srel\(j\)\}j=1\|ℛ\|\)\}k=1K,srel\(j\)=𝒮rel\(𝒆h\|h\(N\)\|\|𝒓q\|q\(N\)\|\|𝒓j\|q\(N\)\),\\displaystyle\\bm\{R\}\_\{\\text\{mem\}\}=\{\\\{\\bm\{r\}\_\{k\}\\in\\bm\{R\}\_\{\|q\}\|s\_\{\\text\{rel\}\}^\{\(k\)\}\\in\\text\{TopK\}\(\{\\\{s\_\{\\text\{rel\}\}^\{\(j\)\}\\\}\}\_\{j=1\}^\{\|\\mathcal\{R\}\|\}\)\\\}\}\_\{k=1\}^\{K\},\\hskip 5\.69054pts\_\{\\text\{rel\}\}^\{\(j\)\}=\\mathcal\{S\}\_\{\\text\{rel\}\}\(\\bm\{e\}\_\{h\|h\}^\{\(N\)\}\|\|\\bm\{r\}\_\{q\|q\}^\{\(N\)\}\|\|\\bm\{r\}\_\{j\|q\}^\{\(N\)\}\),\(7\)Here,𝒆h\|h\(N\)∈𝑬\|h\\bm\{e\}\_\{h\|h\}^\{\(N\)\}\\in\\bm\{E\}\_\{\|h\};𝒓q\|q\(N\),𝒓j\|q\(N\)∈𝑹\|q\\bm\{r\}\_\{q\|q\}^\{\(N\)\},\\bm\{r\}\_\{j\|q\}^\{\(N\)\}\\in\\bm\{R\}\_\{\|q\}; and𝒮rel​\(⋅\):ℝ3​d→ℝd\\mathcal\{S\}\_\{\\text\{rel\}\}\(\\cdot\):\\mathbb\{R\}^\{3d\}\\rightarrow\\mathbb\{R\}^\{d\}is a MLP scorer\.

Let the instructionXXbe tokenized byTKNRG\\text\{TKN\}\_\{\\text\{RG\}\}into the embedding sequence𝑿=\{𝒙i∈ℝd\}i=1L\\bm\{X\}=\{\\\{\\bm\{x\}\_\{i\}\\in\\mathbb\{R\}^\{d\}\\\}\}\_\{i=1\}^\{L\}, the in\-context learning operation in Eq\. \([4](https://arxiv.org/html/2608.17443#S3.E4)\) can be improved to:

InCon\(𝒙i,𝑹mem,𝑿≤i\)=FFN\(softmax\(fQ\(𝒙i\)\[fK\(𝑿≤i\):mK\(𝑹mem\)\]TF\)\[fV\(𝑿≤i\):mV\(𝑹mem\)\]\),\\displaystyle\\hskip\-5\.69054pt\\text\{InCon\}\(\\bm\{x\}\_\{i\},\\bm\{R\}\_\{\\text\{mem\}\},\\bm\{X\}\_\{\\leq i\}\)=\\text\{FFN\}\\Big\(\\text\{softmax\}\\big\(\\frac\{f\_\{Q\}\(\\bm\{x\}\_\{i\}\)\[f\_\{K\}\(\\bm\{X\}\_\{\\leq i\}\):m\_\{K\}\(\\bm\{R\}\_\{\\text\{mem\}\}\)\]^\{\\text\{T\}\}\}\{\\sqrt\{F\}\}\\big\)\[f\_\{V\}\(\\bm\{X\}\_\{\\leq i\}\):m\_\{V\}\(\\bm\{R\}\_\{\\text\{mem\}\}\)\]\\Big\),\(8\)whereFFN​\(⋅\)\\text\{FFN\}\(\\cdot\)incorporates a LoRA fine\-tuning block\([Hu et al\. 2022](https://arxiv.org/html/2608.17443#bib.bib12)\)in practical modeling andm\{K,V\}​\(⋅\):ℝd→ℝFm\_\{\\\{K,V\\\}\}\(\\cdot\):\\mathbb\{R\}^\{d\}\\rightarrow\\mathbb\{R\}^\{F\}are trainable linear layers\. Eq\. \([8](https://arxiv.org/html/2608.17443#S4.E8)\) allows the hidden state of last tokenxLx\_\{L\}to fully integrate the multi\-modal token representations inXXand the relation memory, providing semantically complete activation for the subsequent rule generation\. Its effectiveness analysis is provided inAppendix[D](https://arxiv.org/html/2608.17443#A4)\.

Next\-relation prediction for rule generation:Let the hidden state of the last token be𝒉L=InCon​\(𝒙L,𝑹mem,𝑿\)\\bm\{h\}\_\{L\}=\\text\{InCon\}\(\\bm\{x\}\_\{L\},\\bm\{R\}\_\{\\text\{mem\}\},\\bm\{X\}\), we formulate rule generation as an autoregressive next\-relation prediction process according to Eq\. \([5](https://arxiv.org/html/2608.17443#S3.E5)\)\. First, the distributionP𝚯P\_\{\\bm\{\\Theta\}\}in Eq\. \([5](https://arxiv.org/html/2608.17443#S3.E5)\) can be concretized as:

P𝚯\(𝒓\|𝒉L\)=f𝚯\(𝒉L\|\|𝒓\),𝒓∈\[𝒓end:𝑹\|q\],\\displaystyle P\_\{\\bm\{\\Theta\}\}\(\\bm\{r\}\|\\bm\{h\}\_\{L\}\)=f\_\{\\bm\{\\Theta\}\}\(\\bm\{h\}\_\{L\}\|\|\\bm\{r\}\),\\hskip 5\.69054pt\\bm\{r\}\\in\[\\bm\{r\}\_\{\\text\{end\}\}:\\bm\{R\}\_\{\|q\}\],\(9\)wheref𝚯​\(⋅\):ℝF\+d→ℝ1f\_\{\\bm\{\\Theta\}\}\(\\cdot\):\\mathbb\{R\}^\{F\+d\}\\rightarrow\\mathbb\{R\}^\{1\}is a trainable MLP module, which scores each candidate relation embedding to determine its likelihood as the next generated token\.

Then, relation tokens are generated sequentially in an autoregressive manner:

𝒓z\+1←arg​max𝒓∈\[𝒓end:𝑹\|q\]P𝚯\(𝒓\|𝒉L\+z\),𝒉L\+z=InCon\(fup\(𝒓z\),𝑹mem,\[𝑿:fup\(𝑹≤z\)\]\),\\displaystyle\\bm\{r\}\_\{z\+1\}\\leftarrow\\underset\{\\bm\{r\}\\in\[\\bm\{r\}\_\{\\text\{end\}\}:\\bm\{R\}\_\{\|q\}\]\}\{\\text\{arg\}\\max\}P\_\{\\bm\{\\Theta\}\}\(\\bm\{r\}\|\\bm\{h\}\_\{L\+z\}\),\\hskip 5\.69054pt\\bm\{h\}\_\{L\+z\}=\\text\{InCon\}\\Big\(f\_\{\\text\{up\}\}\(\\bm\{r\}\_\{z\}\),\\bm\{R\}\_\{\\text\{mem\}\},\[\\bm\{X\}:f\_\{\\text\{up\}\}\(\\bm\{R\}\_\{\\leq z\}\)\]\\Big\),\(10\)wherez∈\[0,ε−1\]z\\in\[0,\\varepsilon\-1\],ε\\varepsilondenotes the maximum rule length,𝑹≤z\\bm\{R\}\_\{\\leq z\}consists of the structural embeddings of the previously generatedzzrelations, andfup​\(⋅\):ℝd→ℝFf\_\{\\text\{up\}\}\(\\cdot\):\\mathbb\{R\}^\{d\}\\rightarrow\\mathbb\{R\}^\{F\}is a linear layer defined in Eq\. \([6](https://arxiv.org/html/2608.17443#S4.E6)\)\. The generation process terminates when𝒓z\+1=𝒓end\\bm\{r\}\_\{z\+1\}=\\bm\{r\}\_\{\\text\{end\}\}orz\+1=εz\+1=\\varepsilon\.

Through Eq\. \([10](https://arxiv.org/html/2608.17443#S4.E10)\), we can obtain the rule bodyρ=⋀z=1εrz\\rho=\\bigwedge\_\{z=1\}^\{\\varepsilon\}r\_\{z\}together with their hidden states\{𝒉L\+z\}z=1ε\{\\\{\\bm\{h\}\_\{L\+z\}\\\}\}\_\{z=1\}^\{\\varepsilon\}, which are used for subsequent rule reasoning for<eh,rq,?\><e\_\{h\},r\_\{q\},?\>\.

### 4\.3Reasoning with Rule\-constraint Message Propagation

Unlike conventional SIL methods that initialize relational graph nodes solely with a full\-one vector of the query relation, our RCMP mechanism incorporates the hidden states\{𝒉L\+z\}z=1ε\{\\\{\\bm\{h\}\_\{L\+z\}\\\}\}\_\{z=1\}^\{\\varepsilon\}of the rule path⋀z=1εrz\\bigwedge\_\{z=1\}^\{\\varepsilon\}r\_\{z\}generated in Eq\. \([10](https://arxiv.org/html/2608.17443#S4.E10)\) as additional initialization signals\. Specifically, we modify the initialization step of relation nodes in Eq\. \([1](https://arxiv.org/html/2608.17443#S3.E1)\) as follows:

𝑹^\|q=NBFNet\(\{<rq,𝟏d\>\}∪\{<rz,fdown\(𝒉L\+z\)\>\}z=1ε,𝑹^∗\),\\displaystyle\\hat\{\\bm\{R\}\}\_\{\|q\}=\\text\{NBFNet\}\(\\\{<r\_\{q\},\\mathbf\{1\}^\{d\}\>\\\}\\cup\{\\\{<r\_\{z\},f\_\{\\text\{down\}\}\(\\bm\{h\}\_\{L\+z\}\)\>\\\}\}\_\{z=1\}^\{\\varepsilon\},\\hat\{\\bm\{R\}\}^\{\*\}\),\(11\)wherefdown​\(⋅\):ℝF→ℝdf\_\{\\text\{down\}\}\(\\cdot\):\\mathbb\{R\}^\{F\}\\rightarrow\\mathbb\{R\}^\{d\}is a trainable linear layer\. Similar to Eq\. \([1](https://arxiv.org/html/2608.17443#S3.E1)\),𝑹^∗\\hat\{\\bm\{R\}\}^\{\*\}is a randomly initialized embeddings of motif edges\. Eq\. \([11](https://arxiv.org/html/2608.17443#S4.E11)\) transforms the implicit semantic signals of the rule sequence into explicit structural constraints, which enhances the contextual representation and structural discriminability of the query relation\. The details of Eq\. \([11](https://arxiv.org/html/2608.17443#S4.E11)\) is provided in Eq\. \([19](https://arxiv.org/html/2608.17443#A3.E19)\) and a theoretical analysis of RCMP is provided inAppendix[E](https://arxiv.org/html/2608.17443#A5)\.

Based on Eq\. \([11](https://arxiv.org/html/2608.17443#S4.E11)\), we obtain𝑹^\|q\\hat\{\\bm\{R\}\}\_\{\|q\}as the relation representations\. Then, we compute entity representations𝑬^\|h\\hat\{\\bm\{E\}\}\_\{\|h\}and score the candidate tail entities of<eh,rq,?\><e\_\{h\},r\_\{q\},?\>:

𝑬^\|h=NBFNet\(\{<eh,𝒓^q\|q\(N\)\>\},𝑹^\|q,𝒢\),\\displaystyle\\hat\{\\bm\{E\}\}\_\{\|h\}=\\text\{NBFNet\}\(\\\{<e\_\{h\},\\hat\{\\bm\{r\}\}\_\{q\|q\}^\{\(N\)\}\>\\\},\\hat\{\\bm\{R\}\}\_\{\|q\},\\mathcal\{G\}\),\(12\)sRCMP\(i\)=𝒮RCMP\(𝒆^i\|h\(N\)\|\|𝒓^q\|q\(N\)\),𝒆^i\|h∈𝑬^\|h\(N\),𝒓^q\|q\(N\)∈𝑹^\|q,\\displaystyle s\_\{\\text\{RCMP\}\}^\{\(i\)\}=\\mathcal\{S\}\_\{\\text\{RCMP\}\}\(\\hat\{\\bm\{e\}\}\_\{i\|h\}^\{\(N\)\}\|\|\\hat\{\\bm\{r\}\}\_\{q\|q\}^\{\(N\)\}\),\\hat\{\\bm\{e\}\}\_\{i\|h\}\\in\\hat\{\\bm\{E\}\}\_\{\|h\}^\{\(N\)\},\\hat\{\\bm\{r\}\}\_\{q\|q\}^\{\(N\)\}\\in\\hat\{\\bm\{R\}\}\_\{\|q\},\(13\)where𝒮RCMP​\(⋅\):ℝ2​d→ℝ1\\mathcal\{S\}\_\{\\text\{RCMP\}\}\(\\cdot\):\\mathbb\{R\}^\{2d\}\\rightarrow\\mathbb\{R\}^\{1\}is a MLP scorer\. The details of Eq\. \([12](https://arxiv.org/html/2608.17443#S4.E12)\) is provided in Eq\. \([20](https://arxiv.org/html/2608.17443#A3.E20)\)\.

### 4\.4Training Frameworks

During the pre\-training or SFT phase, SIRLM incorporates the KG tokenizer and RCMP reasoner into the standard LLM training framework with supervision signals\. Letρ∗\\rho^\{\*\}andete\_\{t\}represent the ground truth rule and target entity of<eh,rq,?\><e\_\{h\},r\_\{q\},?\>, respectively\. The pre\-training/SFT loss for SIRLM can be expressed as:

ℒSFT=−\[∑z=1\|ρ∗\|log⁡\(p⁡\(ρz∗\|X,ρ<z∗\)\)\+log⁡\(s​cKG\(t\)​s​cRCMP\(t\)\)−1\|𝒩\|​∑ei∈𝒩log⁡\(\(1−s​cKG\(i\)\)​\(1−s​cRCMP\(i\)\)\)\],\\displaystyle\\mathcal\{L\}\_\{\\text\{SFT\}\}=\-\\Big\[\\sum\\limits\_\{z=1\}^\{\|\\rho^\{\*\}\|\}\\log\{\\big\(p\(\\rho^\{\*\}\_\{z\}\|X,\\rho^\{\*\}\_\{<z\}\)\\big\)\}\+\\log\{\(sc\_\{\\text\{KG\}\}^\{\(t\)\}sc\_\{\\text\{RCMP\}\}^\{\(t\)\}\)\}\-\\frac\{1\}\{\|\\mathcal\{N\}\|\}\\sum\\limits\_\{e\_\{i\}\\in\\mathcal\{N\}\}\\log\{\\big\(\(1\-sc\_\{\\text\{KG\}\}^\{\(i\)\}\)\(1\-sc\_\{\\text\{RCMP\}\}^\{\(i\)\}\)\\big\)\}\\Big\],\(14\)wherep⁡\(ρz∗\|X,ρ<z∗\)p\(\\rho^\{\*\}\_\{z\}\|X,\\rho^\{\*\}\_\{<z\}\)represents the generation probability of thezz\-th relation token given the instructionXXand the firstzz\-1 generated relation tokens\.s​cKG\(t\)sc\_\{\\text\{KG\}\}^\{\(t\)\}ands​cRCMP\(t\)sc\_\{\\text\{RCMP\}\}^\{\(t\)\}are calculated by Eqs\. \([7](https://arxiv.org/html/2608.17443#S4.E7)\) and \([13](https://arxiv.org/html/2608.17443#S4.E13)\), respectively, and𝒩\\mathcal\{N\}is the negative target set of<eh,rq,?\><e\_\{h\},r\_\{q\},?\>\.

SIRLM is compatible with the post\-training paradigm of existing LLMs\. When transferring the pre\-trained SIRLM on a downstream KG, we use the GRPO framework to train SIRLM:

ℒGRPO=−1∑m=1M\|ρ\(m\)\|∑z=1\|ρ\(m\)\|\[p\(ρ\(m\)z\|X,ρ\(m\)<z\)𝒜\(m\)−βKL\(p\(ρ\(m\)z\|X,ρ\(m\)<z\)\|pref\(ρ\(m\)z\|X,ρ\(m\)<z\)\)\],\\displaystyle\\hskip\-5\.69054pt\\mathcal\{L\}\_\{\\text\{GRPO\}\}=\-\\frac\{1\}\{\\sum\\limits\_\{m=1\}^\{M\}\|\\rho^\{\(m\)\}\|\}\\sum\\limits\_\{z=1\}^\{\|\\rho^\{\(m\)\}\|\}\\Big\[p\(\\rho^\{\(m\)\}\_\{z\}\|X,\\rho^\{\(m\)\}\_\{<z\}\)\\mathcal\{A\}^\{\(m\)\}\-\\beta\\text\{KL\}\\big\(p\(\\rho^\{\(m\)\}\_\{z\}\|X,\\rho^\{\(m\)\}\_\{<z\}\)\|p\_\{\\text\{ref\}\}\(\\rho^\{\(m\)\}\_\{z\}\|X,\\rho^\{\(m\)\}\_\{<z\}\)\\big\)\\Big\],\(15\)whereppandprefp\_\{\\text\{ref\}\}represent the policy model and the reference model initialized by the pre\-trained SIRLM, respectively\.\{ρ\(m\)\}m=1M\{\\\{\\rho^\{\(m\)\}\\\}\}\_\{m=1\}^\{M\}denotes theMMrules generated by SIRLM for<eh,rq,?\><e\_\{h\},r\_\{q\},?\>through a sampling strategy andβ\\betais a fixed weight\. The advantage𝒜\(m\)=𝒲\(m\)−mean​\(\{𝒲\(m\)\}m=1M\)std​\(\{𝒲\(m\)\}m=1M\)\\mathcal\{A\}^\{\(m\)\}=\\frac\{\\mathcal\{W\}^\{\(m\)\}\-\\text\{mean\}\(\{\\\{\\mathcal\{W\}^\{\(m\)\}\\\}\}\_\{m=1\}^\{M\}\)\}\{\\text\{std\}\(\{\\\{\\mathcal\{W\}^\{\(m\)\}\\\}\}\_\{m=1\}^\{M\}\)\}of each rule is represented as the standardization of the corresponding reward𝒲\(m\)\\mathcal\{W\}^\{\(m\)\}:

𝒲\(m\)=𝕀⁡\(ϕ⁡\(ρ\(m\)\)\)Rank​\(s​cRCMP\(t\)\)−𝕀⁡\(¬ϕ⁡\(ρ\(m\)\)\),ϕ⁡\(ρ\)=\{True,ρ<\|ρ\|∈ℛ​and​ρ\|ρ\|=<END\>False,else\.\\begin\{aligned\} \\mathcal\{W\}^\{\(m\)\}=\\frac\{\\mathbb\{I\}\\big\(\\phi\(\\rho^\{\(m\)\}\)\\big\)\}\{\\text\{Rank\}\\big\(sc\_\{\\text\{RCMP\}\}^\{\(t\)\}\\big\)\}\-\\mathbb\{I\}\\big\(\\neg\\phi\(\\rho^\{\(m\)\}\)\\big\),\\hskip 5\.69054pt\\phi\(\\rho\)=\\begin\{cases\}\\text\{True\},\\rho\_\{<\|\\rho\|\}\\in\\mathcal\{R\}\\text\{ and \}\\rho\_\{\|\\rho\|\}=<\\text\{END\}\>\\\\ \\text\{False\},\\text\{else\}\\end\{cases\}\\end\{aligned\}\.\(16\)Here,Rank​\(s​cRCMP\(t\)\)\\text\{Rank\}\\big\(sc\_\{\\text\{RCMP\}\}^\{\(t\)\}\\big\)denotes the score ranking ofete\_\{t\}among all entities when<eh,rq,?\><e\_\{h\},r\_\{q\},?\>and the generated ruleρ\(m\)\\rho^\{\(m\)\}are given, where the scores​cRCMP\(t\)sc\_\{\\text\{RCMP\}\}^\{\(t\)\}is obtained by Eq\. \([13](https://arxiv.org/html/2608.17443#S4.E13)\)\.ϕ⁡\(⋅\)\\phi\(\\cdot\)is a boolean function used to examine the structure compliance of the generated rule\. It should be noted that at this time, the RCMP reasoner, as a evaluation model in GRPO, does not participate in the parameter optimization of Eq\. \([15](https://arxiv.org/html/2608.17443#S4.E15)\)\.

## 5Experiments

In this section, we demonstrate SIRLM from the following research question:RQ1\. Can SIRLM achieve significant performance across a wide range of transductive and inductive KGR scenarios?RQ2\. Does the core modules of SIRLM play a crucial role in effect enhancement, including the Multi\-Modal Query Instrction \(MMQI\) containing textual and structural tokens, the SRM mechanism in the SIRG module, and the RCMP reasoner?RQ3\. Is SIRLM sensitive to hyperparameter settings, including the number of layersNNof NBFNet, the sizeKKof structural relation memory, and the number of rule samplesMMof GRPO?RQ4\. Is SIRLM applicable to different LLM backbones?

### 5\.1Datasets, Baselines, and Experimental Settings

Datasets\. To comprehensively evaluate SIRLM, we conduct experiments on 36 KGR datasets including fourTransductivedatasets \(FB15k\-237\([Toutanova & Chen 2015](https://arxiv.org/html/2608.17443#bib.bib35)\), WN18RR\([Dettmers et al\. 2018](https://arxiv.org/html/2608.17443#bib.bib7)\), CoDEx\-M\([Safavi & Koutra 2020](https://arxiv.org/html/2608.17443#bib.bib32)\), and NELL995\([Xiong et al\. 2017](https://arxiv.org/html/2608.17443#bib.bib42)\)\), 12InductiveEntity \(IndE\) datasets\([Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34)\)created from FB15k237, WN18RR, and NELL995, and 20FullyInductive \(FullInd\) datasets created from FB15k237, NELL995, Wikidata68K\([Gesese et al\. 2022](https://arxiv.org/html/2608.17443#bib.bib10)\), and MTDEA\([Zhou et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib48)\)\. Detailed dataset descriptions are provided inAppendix[H](https://arxiv.org/html/2608.17443#A8)\.

We perform SIRLM on the aforementioned datasets using four paradigms: End\-to\-End \(E2E\) training from scratch, Pre\-Training \(PT\), SFT, and GRPO post\-training\. The training settings for each paradigm are detailed inAppendix[H](https://arxiv.org/html/2608.17443#A8)\.

Baselines\. We compare SIRLM with\(1\) conventional KG embedding methods\(TransE\([Bordes et al\. 2013](https://arxiv.org/html/2608.17443#bib.bib3)\), RotatE\([Sun et al\. 2019](https://arxiv.org/html/2608.17443#bib.bib33)\), and TuckER\([Balazevic et al\. 2019](https://arxiv.org/html/2608.17443#bib.bib1)\)\),\(2\) rule\-based methods\(NeuralLP\([Yang et al\. 2017](https://arxiv.org/html/2608.17443#bib.bib44)\), DRUM\([Sadeghian et al\. 2019](https://arxiv.org/html/2608.17443#bib.bib31)\), and RNNLogic\([Qu et al\. 2021](https://arxiv.org/html/2608.17443#bib.bib30)\)\),\(3\) GNN\-based methods\(NBFNet\([Zhu et al\. 2021](https://arxiv.org/html/2608.17443#bib.bib49)\), RED\-GNN\([Zhang & Yao 2022](https://arxiv.org/html/2608.17443#bib.bib46)\), ULTRA\([Galkin et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib9)\), and MOTIF\([Huang et al\. 2025a](https://arxiv.org/html/2608.17443#bib.bib15)\)\), and\(4\) LLM\-based methods\(KICGPT\([Wei et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib40)\), LSA\([Li et al\. 2025](https://arxiv.org/html/2608.17443#bib.bib23)\), ChatRule\([Luo et al\. 2025](https://arxiv.org/html/2608.17443#bib.bib27)\), MKGL\([Guo et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib11)\), KG\-FIT\([Jiang et al\. 2024a](https://arxiv.org/html/2608.17443#bib.bib18)\), FtG\([Liu et al\. 2025](https://arxiv.org/html/2608.17443#bib.bib25)\), and KRLM\([Zhuo et al\. 2026](https://arxiv.org/html/2608.17443#bib.bib53)\)\)\.

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 thebest,second\-best, andthird\-bestvalues, respectively\. “–” indicates that the experimental results are unavailable, and “NA” indicates that a model is not applicable to a KGR task\.TypeMethodsFB15k237CoDEx\-MWN18RRNELL99512 IndE Datasets20 FullInd DatasetsMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowEmbeddingmethodsTransE0\.3130\.4950\.3200\.4810\.2260\.5010\.4010\.501NANANANARotatE0\.3380\.5330\.3250\.4660\.4760\.5710\.4830\.565NANANANATuckER0\.3580\.5440\.3280\.4580\.4700\.5260\.5200\.624NANANANARule\-basedmethodsNeuralLP0\.2370\.3620\.3340\.4440\.4350\.5660\.3940\.4820\.4490\.623NANADRUM0\.3430\.5160\.3120\.4380\.4860\.5860\.5320\.6620\.4580\.621NANARNNLogic0\.3440\.5300\.3100\.4450\.4830\.5580\.4160\.478\-\-NANAGNN\-basedmethodsNBFNet0\.4150\.5990\.3430\.5090\.5510\.6660\.5250\.6390\.5270\.6700\.1220\.259RED\-GNN0\.3740\.5580\.3420\.4990\.5330\.6240\.5430\.6510\.5040\.6480\.151∙\\bullet0\.242∙\\bulletULTRA0\.3680\.5640\.3720\.5250\.4800\.6140\.5090\.6600\.5650\.7240\.3660\.529MOTIF0\.3570\.5500\.3610\.5170\.5290\.6280\.5140\.6550\.5820\.7390\.3730\.535LLM\-basedmethodsKICGPT0\.4120\.554\-\-0\.5490\.641\-\-NANANANALSA0\.3560\.538\-\-0\.4690\.5420\.4690\.649\-\-\-\-KG\-FIT0\.3620\.572\-\-0\.5530\.695\-\-NANANANAChatRule†\\dagger0\.3830\.5640\.3200\.4810\.4450\.5180\.5110\.6270\.5350\.6600\.3190\.472FtG0\.3920\.5420\.3950\.473\-\-0\.5380\.626NANANANAMKGL†\\dagger0\.4150\.5910\.3550\.5180\.5520\.6560\.5300\.6490\.5770\.721NANAKRLM†\\dagger0\.3940\.5680\.3670\.5260\.5520\.6590\.5330\.6510\.5780\.7370\.3790\.540OursSIRLME2E\\text\{SIRLM\}\_\{\\text\{E2E\}\}0\.4270\.5990\.3680\.5250\.5520\.6440\.5410\.6420\.5880\.7410\.3830\.545SIRLMPT\\text\{SIRLM\}\_\{\\text\{PT\}\}0\.4080\.5930\.3670\.5220\.4610\.5560\.5200\.6380\.5800\.7380\.3740\.538SIRLMSFT\\text\{SIRLM\}\_\{\\text\{SFT\}\}0\.4290\.5990\.3790\.5310\.5560\.6480\.5490\.6680\.5990\.7490\.3880\.550SIRLMGRPO\\text\{SIRLM\}\_\{\\text\{GRPO\}\}0\.4140\.5950\.3830\.5420\.5230\.6290\.5410\.6440\.5930\.7440\.3810\.544Avg\. gain \(%\)⋆\\star\+6\.66\+5\.90\+4\.13\+5\.77\+6\.92\+5\.11\+5\.45\+6\.01\+6\.84\+6\.64\+10\.30\+12\.05
- ∙\\bullet∙\\bulletRED\-GNN can only obtain experimental results on 12 FullInd datasets partitioned from FB15k237, NELL995, and Wikidata68K\.
- †\\dagger†\\daggerWe reproduce ChatRule, MKGL, and KRLM on all datasets\.
- ⋆\\star⋆\\starWe calculate the average gain of the optimal value in the four training modes of SIRLM compared to all baselines\.

Figure 3:Hit10 ofSIRLMPT\\text\{SIRLM\}\_\{\\text\{PT\}\}variants on different datasets, where the results in the IndE and FullInd scenarios are summarized as average values\.Experimental settings\. Based on previous work\([Galkin et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib9)\), we adopt Mean Recurrent Rank \(MRR\) and top\-10 Hit rate \(Hit10\) as evaluation metrics\. In the main experiment, we use Qwen2\.5\-1\.5b as the backbone of the SIRG module\. We pre\-train and fine\-tune SIRLM using 4 A100 \(40GB\) GPUs\. The more detailed settings of model hyperparameters are provided inAppendix[I](https://arxiv.org/html/2608.17443#A9)\.

### 5\.2Main Results \(RQ1\)

Table[1](https://arxiv.org/html/2608.17443#S5.T1)reports the overall performance of various methods across 36 KGR datasets under transductive, IndE, and FullInd settings\. Overall, our proposed SIRLM achieves consistently strong and competitive results, outperforming prior methods on most datasets and metrics\. Compared with embedding and rule\-based approaches, LLM\-based methods demonstrate clear advantages\. This is because LLMs are better at understanding structural context and leveraging it for effective fact inference\. GNN\-based methods, supported by their ability to learn invariant graph representations, can capture general structural semantics across different KGs and thus achieve meaningful progress on inductive tasks\.

In comparison to other baselines, LLM\-based methods generally provide a holistic performance\. However, most of them primarily focus on the transductive setting\. Consequently, we reproduce open\-source LLM\-based methods \(ChatRule, MKGL, and KRLM\) for inductive reasoning\. These methods are built upon GPT\-4o mini or LLaMA2\-7B and achieve competitive performance\. In contrast, our SIRLM, despite being based on a 1\.5B\-scale LLM, surpasses these LLM\-based approaches\. This is primarily attributed to its effective internalization of structural knowledge and stricter adherence to logical semantics\. More detailed experimental analysis can be found in Appendixes[J\.1](https://arxiv.org/html/2608.17443#A10.SS1)\.

Figure 4:Hit10 ofSIRLME2E\\text\{SIRLM\}\_\{\\text\{E2E\}\}with different NBFNet layersNNin KG tokenizer and RCMP reasoner\.
### 5\.3Ablation Experiments \(RQ2\)

This section discusses the effectiveness of different modules in SIRLM\. The experimental results are shown in Figure[3](https://arxiv.org/html/2608.17443#S5.F3)\. Overall, the effectiveness of each ablation variant is inferior to that of the full model, especially in structural knowledge learning modules such as “SRM” and “RCMP”\.Appendix[J\.2](https://arxiv.org/html/2608.17443#A10.SS2)provides detailed ablation variant settings and experimental results\.

### 5\.4Parameter Analysis \(RQ3\)

Figure 5:Hit10 ofSIRLME2E\\text\{SIRLM\}\_\{\\text\{E2E\}\}with different relation memory scaleKKandSIRLMGRPO\\text\{SIRLM\}\_\{\\text\{GRPO\}\}with different GRPO sample numberMM\.Figures[4](https://arxiv.org/html/2608.17443#S5.F4)and[5](https://arxiv.org/html/2608.17443#S5.F5)illustrate the performance of SIRLM under different configurations of the NBFNet layersNN, relation memory scaleKK, and the number of GRPO samplesNN\. When the layers in both the KG tokenizer and the RCMP reasoner is set toN=6N=6, SIRLM achieves a good balance between reasoning accuracy and memory cost\.KKis related to the relation scale in the KG\. Therefore, we uniformly setK=30K=30in our experiments\. WhenM=1M=1, the group relative advantage in Eq\. \([15](https://arxiv.org/html/2608.17443#S4.E15)\) becomes ineffective, making it difficult for SIRLM to learn high\-quality logical patterns, a phenomenon that is particularly pronounced in sparse KGs such as WN18RR v1 and CodeX\-M\. Therefore, we consistently setM=8M=8in our experiments\.

### 5\.5Adaptability Analysis of LLM backbones \(RQ4\)

Table 2:The performance ofSIRLME2E\\text\{SIRLM\}\_\{\\text\{E2E\}\}with different LLM backbones\.LLMBackboneCoDEx\-MWN18RR v1FB15k237\-25NELL995\-25MRRHit10MRRHit10MRRHit10MRRHit10Qwen2\.5\-0\.5b0\.3510\.5110\.6920\.7490\.3820\.6370\.3890\.564Qwen2\.5\-1\.5b0\.3680\.5250\.7050\.7660\.3860\.6350\.4070\.601Qwen2\.5\-7b0\.3690\.5310\.7080\.7710\.3870\.6350\.4080\.606Llama\-2\-7b0\.3620\.5280\.7110\.7810\.3870\.6320\.4050\.602This section evaluates the adaptability ofSIRLME2E\\text\{SIRLM\}\_\{\\text\{E2E\}\}across different LLM backbones\. As shown in Table[2](https://arxiv.org/html/2608.17443#S5.T2), SIRLM remains relatively stable across most backbones, with only a slight performance decline on Qwen2\.5\-0\.5B\. We attribute this gap to the limited capacity of smaller LLMs to assimilate structural knowledge\. As shown in Figure[9](https://arxiv.org/html/2608.17443#A10.F9)ofAppendix[J\.3](https://arxiv.org/html/2608.17443#A10.SS3), Qwen2\.5\-0\.5B exhibits the slowest convergence in rule\-token generation accuracy, suggesting greater difficulty in aligning structural representations within its limited parameter space\. As model capacity increases, SIRLM can more effectively internalize structural knowledge, leading to more stable reasoning performance\.

## 6Conclusion

This paper identifies a pervasive issue in LLM\-based KGR, termed reasoning evidence perception drift, caused by the misalignment between KG structural representations and LLM parametric knowledge, which undermines both reasoning effectiveness and faithfulness\. To address this issue, we propose the Structure\-Internalized Rule Language Model \(SIRLM\), which integrates a structure\-internalized rule generator with a KG tokenizer and a neuro\-symbolic reasoner\. SIRLM aligns parametric knowledge with KG structure through structural representation learning, rule generation, and faithfulness feedback, enabling evidence\-grounded reasoning over KGs\. Extensive experiments with 17 baselines on 36 KGR benchmarks show that SIRLM consistently outperforms existing methods across end\-to\-end training, pre\-training, supervised fine\-tuning, and post\-training settings\.Appendix[K](https://arxiv.org/html/2608.17443#A11)discusses its limitations and future directions\.

### AI use statement

In this work, we have not used generative AI tools for any tasks requiring disclosure, and the remaining required disclosure tasks are not applicable to this work\. We used generative AI tools only to edit the manuscript for grammar and readability\. All AI\-assisted edits were reviewed by the authors to ensure that they did not alter the technical content, scientific claims, or intended meaning\. We take responsibility for the final content of this work, including text, claims, or artifacts produced with the aid of generative AI\.

### Reproducibility statement

We confirm that our study has reproducibility\. Specifically, we have first submitted our desensitized project on anonymous GitHub \([https://github\.com/lazyloafer/SIRLM](https://github.com/lazyloafer/SIRLM)\)\. The detailed pseudocode of the algorithm is provided inAppendix[F](https://arxiv.org/html/2608.17443#A6)\. In addition, we provide specific details of the experimental conclusions in the main text, including dataset partitioning \(Appendix[H](https://arxiv.org/html/2608.17443#A8)\), hyperparameter settings \(Appendix[I](https://arxiv.org/html/2608.17443#A9)\), and ablation variant settings \(Appendix[J\.2](https://arxiv.org/html/2608.17443#A10.SS2)\)\.

## References

- Balazevic et al\. \(2019\)Ivana Balazevic, Carl Allen, and Timothy Hospedales\.TuckER: Tensor Factorization for Knowledge Graph Completion\.In*EMNLP*, pp\. 5185–5194\. ACL, 2019\.
- Barceló et al\. \(2022\)Pablo Barceló, Mikhail Galkin, Christopher Morris, and Miguel A\. Romero Orth\.Weisfeiler and Leman Go Relational\.In*LoG*, pp\. 46\. PMLR, 2022\.
- Bordes et al\. \(2013\)Antoine Bordes, Nicolas Usunier, Alberto García\-Durán, Jason Weston, and Oksana Yakhnenko\.Translating Embeddings for Modeling Multi\-relational Data\.In*NeurIPS*, pp\. 2787–2795\. Curran Associates, Inc\., 2013\.
- Corso et al\. \(2020\)Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Velickovic\.Principal Neighbourhood Aggregation for Graph Nets\.In*NeurIPS*, pp\. 13260–13271\. Curran Associates, Inc\., 2020\.
- Cui et al\. \(2024\)Yuanning Cui, Zequn Sun, and Wei Hu\.A Prompt\-Based Knowledge Graph Foundation Model for Universal In\-Context Reasoning\.In*NeurIPS*, pp\. 7095–7124\. Curran Associates, Inc\., 2024\.
- Das et al\. \(2018\)Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishnamurthy, Alex Smola, and Andrew McCallum\.Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning\.In*ICLR*\. OpenReview\.net, 2018\.
- Dettmers et al\. \(2018\)Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel\.Convolutional 2D Knowledge Graph Embeddings\.In*AAAI*, pp\. 1811–1818\. AAAI Press, 2018\.
- Galkin et al\. \(2022\)Mikhail Galkin, Etienne G\. Denis, Jiapeng Wu, and William L\. Hamilton\.NodePiece: Compositional and Parameter\-Efficient Representations of Large Knowledge Graphs\.In*ICLR*\. OpenReview\.net, 2022\.
- Galkin et al\. \(2024\)Mikhail Galkin, Xinyu Yuan, Hesham Mostafa, Jian Tang, and Zhaocheng Zhu\.Towards Foundation Models for Knowledge Graph Reasoning\.In*ICLR*, pp\. 31598–31619\. OpenReview\.net, 2024\.
- Gesese et al\. \(2022\)Genet Asefa Gesese, Harald Sack, and Mehwish Alam\.RAILD: Towards Leveraging Relation Features for Inductive Link Prediction In Knowledge Graphs\.In*IJCKG*, pp\. 82–90\. ACM, 2022\.
- Guo et al\. \(2024\)Lingbing Guo, Zhongpu Bo, Zhuo Chen, Yichi Zhang, Jiaoyan Chen, Yarong Lan, Mengshu Sun, Zhiqiang Zhang, Yangyifei Luo, Qian Li, Qiang Zhang, Wen Zhang, and Huajun Chen\.MKGL: Mastery of a Three\-Word Language\.In*NeurIPS*, volume 37, pp\. 140509–140534\. Curran Associates, Inc\., 2024\.
- Hu et al\. \(2022\)Edward J\. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen\-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen\.LoRA: Low\-Rank Adaptation of Large Language Models\.In*ICLR*\. OpenReview\.net, 2022\.
- Huang et al\. \(2026\)Manzong Huang, Chenyang Bu, Yi He, Xingrui Zhuo, and Xindong Wu\.Relink: Constructing Query\-Driven Evidence Graph On\-the\-Fly for GraphRAG\.In*AAAI*, pp\. 31202–31210\. AAAI Press, 2026\.
- Huang et al\. \(2023\)Xingyue Huang, Miguel Romero, İsmail İlkan Ceylan, and Pablo Barceló\.A Theory of Link Prediction via Relational Weisfeiler\-Leman on Knowledge Graphs\.In*NeurIPS*, pp\. 19714–19748\. Curran Associates, Inc\., 2023\.
- Huang et al\. \(2025a\)Xingyue Huang, Pablo Barceló, Michael M\. Bronstein, İsmail İlkan Ceylan, Mikhail Galkin, Juan L\. Reutter, and Miguel A\. Romero Orth\.How Expressive are Knowledge Graph Foundation Models?In*ICML*, pp\. 25021–25058\. PMLR, 2025a\.
- Huang et al\. \(2025b\)Xingyue Huang, Miguel A\. Romero Orth, Pablo Barceló, Michael M\. Bronstein, and İsmail İlkan Ceylan\.Link Prediction with Relational Hypergraphs\.*Trans\. Mach\. Learn\. Res\.*, 2025\(1\):1–42, 2025b\.
- Ji et al\. \(2022\)Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and Philip S\. Yu\.A Survey on Knowledge Graphs: Representation, Acquisition, and Applications\.*IEEE TNNLS*, 33\(2\):494–514, 2022\.
- Jiang et al\. \(2024a\)Pengcheng Jiang, Lang Cao, Cao \(Danica\) Xiao, Parminder Bhatia, Jimeng Sun, and Jiawei Han\.KG\-FIT: Knowledge Graph Fine\-Tuning Upon Open\-World Knowledge\.In*NeurIPS*, pp\. 136220–136258\. Curran Associates, Inc\., 2024a\.
- Jiang et al\. \(2024b\)Zhouyu Jiang, Ling Zhong, Mengshu Sun, Jun Xu, Rui Sun, Hui Cai, Shuhan Luo, and Zhiqiang Zhang\.Efficient Knowledge Infusion via KG\-LLM Alignment\.In*Findings of ACL*, pp\. 2986–2999\. ACL, 2024b\.
- Kim et al\. \(2023\)Jiho Kim, Yeonsu Kwon, Yohan Jo, and Edward Choi\.KG\-GPT: A General Framework for Reasoning on Knowledge Graphs Using Large Language Models\.In*Findings of EMNLP*, pp\. 9410–9421\. ACL, 2023\.
- Lao & Cohen \(2010\)Ni Lao and William W\. Cohen\.Relational retrieval using a combination of path\-constrained random walks\.*Mach\. Learn\.*, 81\(1\):53–67, 2010\.
- Lee et al\. \(2023\)Jaejun Lee, Chanyoung Chung, and Joyce Jiyoung Whang\.InGram: Inductive Knowledge Graph Embedding via Relation Graphs\.In*ICML*, volume 202, pp\. 18796–18809\. PMLR, 2023\.
- Li et al\. \(2025\)Miaomiao Li, Ke Liang, Yuping Lai, and Xinwang Liu\.Knowledge Graph Reasoning Based on Information Enhancement and Subgraph Alignment\.*IEEE TNNLS*, pp\. 1–13, 2025\.
- Liang et al\. \(2024\)Ke Liang, Lingyuan Meng, Meng Liu, Yue Liu, Wenxuan Tu, Siwei Wang, Sihang Zhou, Xinwang Liu, Fuchun Sun, and Kunlun He\.A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multi\-Modal\.*IEEE TPAMI*, 46\(12\):9456–9478, 2024\.
- Liu et al\. \(2025\)Ben Liu, Jihai Zhang, Fangquan Lin, Cheng Yang, and Min Peng\.Filter\-then\-Generate: Large Language Models with Structure\-Text Adapter for Knowledge Graph Completion\.In*COLING*, pp\. 11181–11195, 2025\.
- Luo et al\. \(2024\)Linhao Luo, Yuan\-Fang Li, Gholamreza Haffari, and Shirui Pan\.Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning\.In*ICLR*, pp\. 14400–14423\. OpenReview\.net, 2024\.
- Luo et al\. \(2025\)Linhao Luo, Jiaxin Ju, Bo Xiong, Yuan\-Fang Li, Gholamreza Haffari, and Shirui Pan\.ChatRule: Mining Logical Rules with Large Language Models for Knowledge Graph Reasoning\.In*PAKDD*, pp\. 314–325\. Springer\-Verlag, 2025\.
- Naveed et al\. \(2025\)Humza Naveed, Asad Ullah Khan, Shi Qiu, Muhammad Saqib, Saeed Anwar, Muhammad Usman, Naveed Akhtar, Nick Barnes, and Ajmal Mian\.A Comprehensive Overview of Large Language Models\.*ACM TIST*, 16\(5\):106:1–106:72, 2025\.
- Pan et al\. \(2024\)Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang, and Xindong Wu\.Unifying Large Language Models and Knowledge Graphs: A Roadmap\.*IEEE TKDE*, 36\(7\):3580–3599, 2024\.
- Qu et al\. \(2021\)Meng Qu, Junkun Chen, Louis\-Pascal Xhonneux, Yoshua Bengio, and Jian Tang\.RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs\.In*ICLR*, 2021\.
- Sadeghian et al\. \(2019\)Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang\.DRUM: End\-To\-End Differentiable Rule Mining On Knowledge Graphs\.In*NeurIPS*, pp\. 15347–15357\. Curran Associates, Inc\., 2019\.
- Safavi & Koutra \(2020\)Tara Safavi and Danai Koutra\.CoDEx: A Comprehensive Knowledge Graph Completion Benchmark\.In*EMNLP*, pp\. 8328–8350\. ACL, 2020\.
- Sun et al\. \(2019\)Zhiqing Sun, Zhi\-Hong Deng, Jian\-Yun Nie, and Jian Tang\.RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space\.In*ICLR*\. OpenReview\.net, 2019\.
- Teru et al\. \(2020\)Komal K\. Teru, Etienne G\. Denis, and William L\. Hamilton\.Inductive Relation Prediction by Subgraph Reasoning\.In*ICML*, volume 119, pp\. 9448–9457\. PMLR, 2020\.
- Toutanova & Chen \(2015\)Kristina Toutanova and Danqi Chen\.Observed Versus Latent Features for Knowledge Base and Text Inference\.In*Workshop on CVSC*, pp\. 57–66\. ACL, 2015\.
- Trouillon et al\. \(2016\)Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard\.Complex Embeddings for Simple Link Prediction\.In*ICML*, volume 48 of*JMLR Workshop and Conference Proceedings*, pp\. 2071–2080\. JMLR\.org, 2016\.
- Wan & Du \(2021\)Guojia Wan and Bo Du\.GaussianPath: A Bayesian Multi\-Hop Reasoning Framework for Knowledge Graph Reasoning\.In*AAAI*, pp\. 4393–4401\. AAAI Press, 2021\.
- Wang et al\. \(2024a\)Jiapu Wang, Kai Sun, Linhao Luo, Wei Wei, Yongli Hu, Alan Wee\-Chung Liew, Shirui Pan, and Baocai Yin\.Large language models\-guided dynamic adaptation for temporal knowledge graph reasoning\.In*NeurIPS*, pp\. 8384–8410\. Curran Associates, Inc\., 2024a\.
- Wang et al\. \(2024b\)Kai Wang, Yuwei Xu, Zhiyong Wu, and Siqiang Luo\.LLM as Prompter: Low\-resource Inductive Reasoning on Arbitrary Knowledge Graphs\.In*Findings of ACL*, pp\. 3742–3759\. ACL, 2024b\.
- Wei et al\. \(2023\)Yanbin Wei, Qiushi Huang, Yu Zhang, and James T\. Kwok\.KICGPT: Large Language Model with Knowledge in Context for Knowledge Graph Completion\.In*Findings of EMNLP*, pp\. 8667–8683\. ACL, 2023\.
- Xiao et al\. \(2016\)Han Xiao, Minlie Huang, Yu Hao, and Xiaoyan Zhu\.From One Point to A Manifold: Orbit Models for Knowledge Graph Embedding\.In*IJCAI*, pp\. 1315–1321\. ijcai\.org, 2016\.
- Xiong et al\. \(2017\)Wenhan Xiong, Thien Hoang, and William Yang Wang\.DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning\.In*EMNLP*, pp\. 564–573\. ACL, 2017\.
- Yang et al\. \(2015\)Bishan Yang, Wen\-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng\.Embedding Entities and Relations for Learning and Inference in Knowledge Bases\.In*ICLR*\. OpenReview\.net, 2015\.
- Yang et al\. \(2017\)Fan Yang, Zhilin Yang, and William W Cohen\.Differentiable Learning of Logical Rules for Knowledge Base Reasoning\.In*NeurIPS*, pp\. 2319–2328\. Curran Associates, Inc\., 2017\.
- Zhang et al\. \(2024a\)Yichi Zhang, Zhuo Chen, Lingbing Guo, Yajing Xu, Wen Zhang, and Huajun Chen\.Making Large Language Models Perform Better in Knowledge Graph Completion\.In*ACM MM*, pp\. 233–242\. ACM, 2024a\.
- Zhang & Yao \(2022\)Yongqi Zhang and Quanming Yao\.Knowledge Graph Reasoning with Relational Digraph\.In*ACM WWW*, pp\. 912–924\. ACM, 2022\.
- Zhang et al\. \(2024b\)Yucheng Zhang, Beatrice Bevilacqua, Mikhail Galkin, and Bruno Ribeiro\.TRIX: A More Expressive Model for Zero\-shot Domain Transfer in Knowledge Graphs\.In*LoG Conference*\. OpenReview\.net, 2024b\.
- Zhou et al\. \(2023\)Jincheng Zhou, Beatrice Bevilacqua, and Bruno Ribeiro\.A Multi\-Task Perspective for Link Prediction with New Relation Types and Nodes\.In*NeurIPS GLFrontiers Workshop*, 2023\.
- Zhu et al\. \(2021\)Zhaocheng Zhu, Zuobai Zhang, Louis\-Pascal A\. C\. Xhonneux, and Jian Tang\.Neural Bellman\-Ford Networks: A General Graph Neural Network Framework for Link Prediction\.In*NeurIPS*, pp\. 29476–29490\. Curran Associates, Inc\., 2021\.
- Zhu et al\. \(2022\)Zhaocheng Zhu, Mikhail Galkin, Zuobai Zhang, and Jian Tang\.Neural\-Symbolic Models for Logical Queries on Knowledge Graphs\.In*ICML*, volume 162 of*Proceedings of Machine Learning Research*, pp\. 27454–27478\. PMLR, 2022\.
- Zhuo et al\. \(2025a\)Xingrui Zhuo, Shirui Pan, Jiapu Wang, Gongqing Wu, Zan Zhang, Rui Li, Zizhong Wei, and Xindong Wu\.Progressive Prefix\-Memory Tuning for Complex Logical Query Answering on Knowledge Graphs\.In*IJCAI*, pp\. 3716–3724\. ijcai\.org, 2025a\.
- Zhuo et al\. \(2025b\)Xingrui Zhuo, Jiapu Wang, Gongqing Wu, Shirui Pan, and Xindong Wu\.Effective instruction parsing plugin for complex logical query answering on knowledge graphs\.In*ACM WWW*, pp\. 4780–4792\. ACM, 2025b\.
- Zhuo et al\. \(2026\)Xingrui Zhuo, Jiapu Wang, Gongqing Wu, Zhongyuan Wang, Jichen Zhang, Shirui Pan, and Xindong Wu\.Knowledge Reasoning Language Model: Unifying Knowledge and Language for Inductive Knowledge Graph Reasoning\.In*ICLR*, pp\. 122329–122356, 2026\.

## Appendix ADesign Details of Query Instructions

Given a query triplet\(eh,rq,?\)\(e\_\{h\},r\_\{q\},?\), we first provide its schema of a query instruction below:

Schema of the Query Instruction for Rule Generation[⬇](data:text/plain;base64,U3VwcG9zZSB5b3UgYXJlIGEgbGluZ3Vpc3RpYyBleHBlcnQgd2hvIGlzIGxlYXJuaW5nIGEgbmV3IHJ1bGUgbGFuZ3VhZ2UuIEdpdmVuIHRoZSBmb2xsb3dpbmcgaGVhZCBlbnRpdHkgYW5kIHF1ZXJ5IHJlbGF0aW9uOgoKIyMjIEhlYWQgZW50aXR5OiAoKiQ8JEVudCAkZV9oJCQ+JCopCgojIyMgUXVlcnkgcmVsYXRpb25zOiAoKiQ8JFJlbCAkcl9xJCQ+JCopCgpHZW5lcmF0ZSB0aGUgZm9sbG93aW5nIHJ1bGUgbGFuZ3VhZ2U6ICgqJDwkUmVsICRyX3EkJD4kPSRcdW5kZXJicmFjZXs8XHRleHR7UmVsIH0gcl8xPjxcdGV4dHtSZWwgfSByXzM+PFx0ZXh0e1JlbCB9IHJfMj48XHRleHR7RU5EfT59X3tcdGV4dHttYXNrIGZvciBnZW5lcmF0aW9ufX0kKik=)Supposeyouarealinguisticexpertwhoislearninganewrulelanguage\.Giventhefollowingheadentityandqueryrelation:\#\#\#Headentity:<<Entehe\_\{h\}\>\>\#\#\#Queryrelations:<<Relrqr\_\{q\}\>\>Generatethefollowingrulelanguage:<<Relrqr\_\{q\}\>\>=<Rel​r1\><Rel​r3\><Rel​r2\><END\>⏟mask for generation\\underbrace\{<\\text\{Rel \}r\_\{1\}\><\\text\{Rel \}r\_\{3\}\><\\text\{Rel \}r\_\{2\}\><\\text\{END\}\>\}\_\{\\text\{mask for generation\}\}

Our query instruction consists of a fixed text prompt along with structural representation placeholders that vary depending on the query triplet\. Specifically,<Ent​eh\><\\text\{Ent \}e\_\{h\}\>and<Rel​rq\><\\text\{Rel \}r\_\{q\}\>correspond to the structural representations ofehe\_\{h\}andrqr\_\{q\}, respectively\. The masked portion includes the structural representations of atomic relations in the rule body,<Rel​r1\><Rel​r3\><Rel​r2\><\\text\{Rel \}r\_\{1\}\><\\text\{Rel \}r\_\{3\}\><\\text\{Rel \}r\_\{2\}\>, as well as the rule termination token<END\><\\text\{END\}\>, all of which are derived fromTKNKG\\text\{TKN\}\_\{\\text\{KG\}\}in Eq\. \([6](https://arxiv.org/html/2608.17443#S4.E6)\)\.

This instruction format integrates textual tokes with the structural representations of a KG, enabling the LLM to further learn the contextual semantics of entities and relations within the structural space\. Moreover, since the structural representations provided by NBFNet inherently encode high\-order graph information, we can deliver richer structural information to the LLM using fewer tokens\. In addition, this instruction format does not rely on explicit textual names of entities and relations, making it suitable for anonymized KGR scenarios\.

We compare the instruction lengths designed by several recent LLM\-based KGR methods in Table[3](https://arxiv.org/html/2608.17443#A1.T3), demonstrating that our constructed instructions achieve more efficient utilization of computational resources\.

Table 3:Average instruction length of MKG, KRLM, and SIRLM in 36 KGR datasets\.MKGL\([Guo et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib11)\)KRLM\([Zhuo et al\. 2026](https://arxiv.org/html/2608.17443#bib.bib53)\)SIRLMAvg\. Length115\.66±\\pm3\.65120\.50±\\pm4\.1250\.73±\\pm0\.67
## Appendix BRelational Graph Construction

Unlike a typical KG, a relational graph\([Galkin et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib9);[Huang et al\. 2025a](https://arxiv.org/html/2608.17443#bib.bib15)\)is used to describe the relative states between relations\. As shown in Figure[6](https://arxiv.org/html/2608.17443#A2.F6), in our study, the motifs connecting relation nodes in a relational graph are essentially a set of relation\-oriented hyperedges that is defined asℛ∗\\mathcal\{R\}^\{\*\}in Eq\. \([1](https://arxiv.org/html/2608.17443#S3.E1)\)\.

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 theentityshared 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 aforward tripletshared 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\.In practical implementation, we use sparse matrices to construct the adjacency matrix of the relational graph\. Giving a KG𝒢=\(ℰ,ℛ,𝒯\)\\mathcal\{G\}=\(\\mathcal\{E\},\\mathcal\{R\},\\mathcal\{T\}\)defined as a graph with multiple directed edges, and its adjacency matrix can be represented as𝑨∈ℝℰ×ℛ×ℰ\\bm\{A\}\\in\\mathbb\{R\}^\{\\mathcal\{E\}\\times\\mathcal\{R\}\\times\\mathcal\{E\}\}\. Subsequently, we construct the adjacency matrix by performing the maximum scatter operation on the head and tail node dimensions, resulting in two sparse matrices𝑨h∈ℝℰ×ℛ\\bm\{A\}\_\{h\}\\in\\mathbb\{R\}^\{\\mathcal\{E\}\\times\\mathcal\{R\}\}and𝑨t∈ℝℛ×ℰ\\bm\{A\}\_\{t\}\\in\\mathbb\{R\}^\{\\mathcal\{R\}\\times\\mathcal\{E\}\}\.𝑨h\\bm\{A\}\_\{h\}represents the out\-degree edge of any relation from any node and𝑨t\\bm\{A\}\_\{t\}represents the in\-degree edge of any relation pointing to any node\. Then, the eight types of motif edges shown in Figure[6](https://arxiv.org/html/2608.17443#A2.F6)can be obtained through a sparse matrix multiplication \(spmm\) operator:

Binary edges=\{Tail\-to\-tail\(t2t\):𝑨t​2​t=spmm\(𝑨t,𝑨tT\)∈ℝℛ×ℛHead\-to\-head\(h2h\):𝑨h​2​h=spmm\(𝑨hT,𝑨h\)∈ℝℛ×ℛTail\-to\-head\(t2h\):𝑨t​2​h=spmm\(𝑨t,𝑨h\)∈ℝℛ×ℛHead\-to\-tail\(h2t\):𝑨h​2​t=spmm\(𝑨hT,𝑨tT\)∈ℝℛ×ℛ\\displaystyle\\text\{Binary edges\}=\\begin\{cases\}\\text\{\{Tail\-to\-tail\} \(\{t2t\}\): \}\\bm\{A\}\_\{t2t\}=\\text\{spmm\}\(\\bm\{A\}\_\{t\},\\bm\{A\}\_\{t\}^\{\\text\{T\}\}\)\\in\\mathbb\{R\}^\{\\mathcal\{R\}\\times\\mathcal\{R\}\}\\\\ \\text\{\{Head\-to\-head\} \(\{h2h\}\): \}\\bm\{A\}\_\{h2h\}=\\text\{spmm\}\(\\bm\{A\}\_\{h\}^\{\\text\{T\}\},\\bm\{A\}\_\{h\}\)\\in\\mathbb\{R\}^\{\\mathcal\{R\}\\times\\mathcal\{R\}\}\\\\ \\text\{\{Tail\-to\-head\} \(\{t2h\}\): \}\\bm\{A\}\_\{t2h\}=\\text\{spmm\}\(\\bm\{A\}\_\{t\},\\bm\{A\}\_\{h\}\)\\in\\mathbb\{R\}^\{\\mathcal\{R\}\\times\\mathcal\{R\}\}\\\\ \\text\{\{Head\-to\-tail\} \(\{h2t\}\): \}\\bm\{A\}\_\{h2t\}=\\text\{spmm\}\(\\bm\{A\}\_\{h\}^\{\\text\{T\}\},\\bm\{A\}\_\{t\}^\{\\text\{T\}\}\)\\in\\mathbb\{R\}^\{\\mathcal\{R\}\\times\\mathcal\{R\}\}\\\\ \\end\{cases\}Ternary edges=\{Tail\-forward\-head\(tfh\):𝑨t​f​h=spmm\(𝑨t,𝑨,𝑨h\)∈ℝℛ×ℛ×ℛTail\-forward\-tail\(tft\):𝑨t​f​t=spmm\(𝑨t,𝑨,𝑨tT\)∈ℝℛ×ℛ×ℛHead\-forward\-heaed\(hfh\):𝑨t​f​t=spmm\(𝑨hT,𝑨,𝑨h\)∈ℝℛ×ℛ×ℛHead\-forward\-tail\(hft\):𝑨h​f​t=spmm\(𝑨hT,𝑨,𝑨tT\)∈ℝℛ×ℛ×ℛ\\displaystyle\\text\{Ternary edges\}=\\begin\{cases\}\\text\{\{Tail\-forward\-head\} \(\{tfh\}\): \}\\bm\{A\}\_\{tfh\}=\\text\{spmm\}\(\\bm\{A\}\_\{t\},\\bm\{A\},\\bm\{A\}\_\{h\}\)\\in\\mathbb\{R\}^\{\\mathcal\{R\}\\times\\mathcal\{R\}\\times\\mathcal\{R\}\}\\\\ \\text\{\{Tail\-forward\-tail\} \(\{tft\}\): \}\\bm\{A\}\_\{tft\}=\\text\{spmm\}\(\\bm\{A\}\_\{t\},\\bm\{A\},\\bm\{A\}\_\{t\}^\{\\text\{T\}\}\)\\in\\mathbb\{R\}^\{\\mathcal\{R\}\\times\\mathcal\{R\}\\times\\mathcal\{R\}\}\\\\ \\text\{\{Head\-forward\-heaed\} \(\{hfh\}\): \}\\bm\{A\}\_\{tft\}=\\text\{spmm\}\(\\bm\{A\}\_\{h\}^\{\\text\{T\}\},\\bm\{A\},\\bm\{A\}\_\{h\}\)\\in\\mathbb\{R\}^\{\\mathcal\{R\}\\times\\mathcal\{R\}\\times\\mathcal\{R\}\}\\\\ \\text\{\{Head\-forward\-tail\} \(\{hft\}\): \}\\bm\{A\}\_\{hft\}=\\text\{spmm\}\(\\bm\{A\}\_\{h\}^\{\\text\{T\}\},\\bm\{A\},\\bm\{A\}\_\{t\}^\{\\text\{T\}\}\)\\in\\mathbb\{R\}^\{\\mathcal\{R\}\\times\\mathcal\{R\}\\times\\mathcal\{R\}\}\\\\ \\end\{cases\}

## Appendix CConstruction Details of the KG tokenizer and the RCMP Reasoner

Given that relational graphs contain ternary edges, there are certain differences in the construction details of NBFNet between the original KGs and the relational graphs in the KG tokenizer and the RCMP Reasoner\.

For NBFNet on a relational graph, we need to consider the positional information of the relational nodes in the hyperedges\. Therefore, Eq\. \([1](https://arxiv.org/html/2608.17443#S3.E1)\) can be concretized as

𝒓j\|q\(0\)=𝕀⁡\(rj=rq\)∗𝟏d,\\displaystyle\\bm\{r\}^\{\(0\)\}\_\{j\|q\}=\\mathbb\{I\}\(r\_\{j\}=r\_\{q\}\)\*\\bm\{1\}^\{d\},\(17\)𝒓\(n\)j\|q=σ\(𝑾r\(n−1\)\[𝒓j\|q\(n−1\)\|\|∑r∗∈ℛ∗𝒓∗⊙\(⊙rz∈𝒩r∗​\(rj\)\(𝒓z\|q\(n−1\)\+𝒑z\)\)\]\),𝒓∗∈𝑹∗,\\displaystyle\\bm\{r\}^\{\(n\)\}\_\{j\|q\}=\\sigma\\Big\(\\bm\{W\}\_\{r\}^\{\(n\-1\)\}\\Big\[\\bm\{r\}\_\{j\|q\}^\{\(n\-1\)\}\|\|\\sum\\limits\_\{r^\{\*\}\\in\\mathcal\{R\}^\{\*\}\}\\bm\{r\}^\{\*\}\\odot\\big\(\\underset\{r\_\{z\}\\in\\mathcal\{N\}\_\{r^\{\*\}\}\(r\_\{j\}\)\}\{\\odot\}\(\\bm\{r\}\_\{z\|q\}^\{\(n\-1\)\}\+\\bm\{p\}\_\{z\}\)\\big\)\\Big\]\\Big\),\\bm\{r\}^\{\*\}\\in\\bm\{R\}^\{\*\},whereσ⁡\(⋅\)\\sigma\(\\cdot\)is a ReLU activation function,⊙\\odotis the Hadamard product operator, and𝑾r\(n−1\)∈ℝd×d\\bm\{W\}\_\{r\}^\{\(n\-1\)\}\\in\\mathbb\{R\}^\{d\\times d\}and𝒑z∈ℝd\\bm\{p\}\_\{z\}\\in\\mathbb\{R\}^\{d\}is a trainable parameter matrix and a position embedding, respectively\.

For the original KG, NBFNet only processes directed binary edges, so position information can be ignored\. Therefore, Eq\. \([2](https://arxiv.org/html/2608.17443#S3.E2)\) can be concretized as

𝒆i\|h\(0\)=𝕀⁡\(ei=eh\)∗𝒓q\|q\(N\),\\displaystyle\\bm\{e\}^\{\(0\)\}\_\{i\|h\}=\\mathbb\{I\}\(e\_\{i\}=e\_\{h\}\)\*\\bm\{r\}^\{\(N\)\}\_\{q\|q\},\(18\)𝒆\(n\)i\|h=σ\(𝑾e\(n−1\)\[𝒆i\|h\(n−1\)\|\|∑rj∈ℛ∑ez∈𝒩rj​\(ei\)𝒓j\|q\(N\)⊙𝒆z\|h\(n−1\)\]\),\\displaystyle\\bm\{e\}^\{\(n\)\}\_\{i\|h\}=\\sigma\\Big\(\\bm\{W\}\_\{e\}^\{\(n\-1\)\}\\Big\[\\bm\{e\}\_\{i\|h\}^\{\(n\-1\)\}\|\|\\sum\\limits\_\{r\_\{j\}\\in\\mathcal\{R\}\}\\sum\\limits\_\{e\_\{z\}\\in\\mathcal\{N\}\_\{r\_\{j\}\}\(e\_\{i\}\)\}\\bm\{r\}\_\{j\|q\}^\{\(N\)\}\\odot\\bm\{e\}\_\{z\|h\}^\{\(n\-1\)\}\\Big\]\\Big\),where𝑾e\(n−1\)∈ℝd×d\\bm\{W\}\_\{e\}^\{\(n\-1\)\}\\in\\mathbb\{R\}^\{d\\times d\}is a trainable parameter matrix\.

Similarly, Eqs\. \([11](https://arxiv.org/html/2608.17443#S4.E11)\) and \([12](https://arxiv.org/html/2608.17443#S4.E12)\) can be concretized as Eqs\. \([19](https://arxiv.org/html/2608.17443#A3.E19)\) and \([20](https://arxiv.org/html/2608.17443#A3.E20)\), respectively:

𝒓^j\|q=∑<r,𝒗\>∈U𝕀⁡\(rj=r\)∗𝒗,where​U=\{<rq,𝟏d\>\}∪\{<rz,fdown​\(𝒉L\+z\)\>\}z=1ε\\displaystyle\\hat\{\\bm\{r\}\}\_\{j\|q\}=\\sum\\limits\_\{<r,\\bm\{v\}\>\\in U\}\\mathbb\{I\}\(r\_\{j\}=r\)\*\\bm\{v\},\\text\{ where \}U=\\\{<r\_\{q\},\\mathbf\{1\}^\{d\}\>\\\}\\cup\{\\\{<r\_\{z\},f\_\{\\text\{down\}\}\(\\bm\{h\}\_\{L\+z\}\)\>\\\}\}\_\{z=1\}^\{\\varepsilon\}\(19\)𝒓^\(n\)j\|q=σ\(𝑾^r\(n−1\)\[𝒓^j\|q\(n−1\)\|\|∑r∗∈ℛ∗𝒓^∗⊙\(⊙rz∈𝒩r∗​\(rj\)\(𝒓^z\|q\(n−1\)\+𝒑z\)\)\]\),𝒓^∗∈𝑹^∗,\\displaystyle\\hat\{\\bm\{r\}\}^\{\(n\)\}\_\{j\|q\}=\\sigma\\Big\(\\hat\{\\bm\{W\}\}\_\{r\}^\{\(n\-1\)\}\\Big\[\\hat\{\\bm\{r\}\}\_\{j\|q\}^\{\(n\-1\)\}\|\|\\sum\\limits\_\{r^\{\*\}\\in\\mathcal\{R\}^\{\*\}\}\\hat\{\\bm\{r\}\}^\{\*\}\\odot\\big\(\\underset\{r\_\{z\}\\in\\mathcal\{N\}\_\{r^\{\*\}\}\(r\_\{j\}\)\}\{\\odot\}\(\\hat\{\\bm\{r\}\}\_\{z\|q\}^\{\(n\-1\)\}\+\\bm\{p\}\_\{z\}\)\\big\)\\Big\]\\Big\),\\hat\{\\bm\{r\}\}^\{\*\}\\in\\hat\{\\bm\{R\}\}^\{\*\},𝒆^i\|h\(0\)=𝕀⁡\(ei=eh\)∗𝒓^q\|q\(N\),\\displaystyle\\hat\{\\bm\{e\}\}^\{\(0\)\}\_\{i\|h\}=\\mathbb\{I\}\(e\_\{i\}=e\_\{h\}\)\*\\hat\{\\bm\{r\}\}^\{\(N\)\}\_\{q\|q\},\(20\)𝒆^\(n\)i\|h=σ\(𝑾^e\(n−1\)\[𝒆^i\|h\(n−1\)\|\|∑rj∈ℛ∑ez∈𝒩rj​\(ei\)𝒓^j\|q\(N\)⊙𝒆^z\|h\(n−1\)\]\)\.\\displaystyle\\hat\{\\bm\{e\}\}^\{\(n\)\}\_\{i\|h\}=\\sigma\\Big\(\\hat\{\\bm\{W\}\}\_\{e\}^\{\(n\-1\)\}\\Big\[\\hat\{\\bm\{e\}\}\_\{i\|h\}^\{\(n\-1\)\}\|\|\\sum\\limits\_\{r\_\{j\}\\in\\mathcal\{R\}\}\\sum\\limits\_\{e\_\{z\}\\in\\mathcal\{N\}\_\{r\_\{j\}\}\(e\_\{i\}\)\}\\hat\{\\bm\{r\}\}\_\{j\|q\}^\{\(N\)\}\\odot\\hat\{\\bm\{e\}\}\_\{z\|h\}^\{\(n\-1\)\}\\Big\]\\Big\)\.Here,𝑾^r\(n−1\),𝑾^e\(n−1\)∈ℝd×d\\hat\{\\bm\{W\}\}\_\{r\}^\{\(n\-1\)\},\\hat\{\\bm\{W\}\}\_\{e\}^\{\(n\-1\)\}\\in\\mathbb\{R\}^\{d\\times d\}are two trainable parameter matrix\.

## Appendix DDiscussion of the SRM In\-context Layer

This section discusses the effectiveness of the proposed SRM mechanism from the perspectives of structural representation alignment and semantic drift suppression\. First, we provide the following explanation of the assumption and definitions required for subsequent analysis\.

###### Definition 1\(In\-context learning for the last token\)\.

Given a query triplet<eh,rq,?\><e\_\{h\},r\_\{q\},?\>and the corresponding instruction representation𝐗∈ℝL×F\\bm\{X\}\\in\\mathbb\{R\}^\{L\\times F\}, according to Eq\. \([4](https://arxiv.org/html/2608.17443#S3.E4)\), the hidden state of the last token𝐱L∈𝐗\\bm\{x\}\_\{L\}\\in\\bm\{X\}in the vanilla in\-context learning module can be expressed as:

𝒉Lbase=\\displaystyle\\bm\{h\}\_\{L\}^\{\\mathrm\{base\}\}=∑i≤Lαi​fV​\(𝒙i\),\\displaystyle\\sum\\limits\_\{i\\leq L\}\\alpha\_\{i\}f\_\{V\}\(\\bm\{x\}\_\{i\}\),αi=exp⁡\(ai\)∑j≤Lexp⁡\(aj\)\\displaystyle\\alpha\_\{i\}=\\frac\{\\exp\{\(a\_\{i\}\)\}\}\{\\sum\\limits\_\{j\\leq L\}\\exp\{\(a\_\{j\}\)\}\},ai=fQ​\(𝒙L\)​\[fK​\(𝒙i\)\]TF\.\\displaystyle,\\hskip 5\.69054pta\_\{i\}=\\frac\{f\_\{Q\}\(\\bm\{x\}\_\{L\}\)\{\[f\_\{K\}\(\\bm\{x\}\_\{i\}\)\]\}^\{\\text\{T\}\}\}\{\\sqrt\{F\}\}\.
Then, we introduce the structural relation memory𝐑mem=\{𝐫k∈𝐑\|q\}k=1K\\bm\{R\}\_\{\\mathrm\{mem\}\}=\{\\\{\\bm\{r\}\_\{k\}\\in\\bm\{R\}\_\{\|q\}\\\}\}\_\{k=1\}^\{K\}from Eq\. \([7](https://arxiv.org/html/2608.17443#S4.E7)\) into the in\-context learning module, the hidden state of the last token in Eq\. \([8](https://arxiv.org/html/2608.17443#S4.E8)\) can be expressed as:

𝒉LSRM=\\displaystyle\\bm\{h\}\_\{L\}^\{\\mathrm\{SRM\}\}=∑i≤Lα^i​fV​\(𝒙i\)\+∑k≤Kβk​mV​\(𝒓k\),\\displaystyle\\sum\\limits\_\{i\\leq L\}\\hat\{\\alpha\}\_\{i\}f\_\{V\}\(\\bm\{x\}\_\{i\}\)\+\\sum\\limits\_\{k\\leq K\}\\beta\_\{k\}m\_\{V\}\(\\bm\{r\}\_\{k\}\),α^i=exp⁡\(ai\)∑j≤Lexp⁡\(aj\)\+∑z≤Kexp⁡\(bz\)\\displaystyle\\hat\{\\alpha\}\_\{i\}=\\frac\{\\exp\{\(a\_\{i\}\)\}\}\{\\sum\\limits\_\{j\\leq L\}\\exp\{\(a\_\{j\}\)\}\+\\sum\\limits\_\{z\\leq K\}\\exp\{\(b\_\{z\}\)\}\},βk=exp⁡\(bk\)∑j≤Lexp⁡\(aj\)\+∑z≤Kexp⁡\(bz\),bk=fQ​\(𝒙L\)​\[mK​\(𝒓k\)\]TF\.\\displaystyle,\\hskip 5\.69054pt\\beta\_\{k\}=\\frac\{\\exp\{\(b\_\{k\}\)\}\}\{\\sum\\limits\_\{j\\leq L\}\\exp\{\(a\_\{j\}\)\}\+\\sum\\limits\_\{z\\leq K\}\\exp\{\(b\_\{z\}\)\}\},\\hskip 5\.69054ptb\_\{k\}=\\frac\{f\_\{Q\}\(\\bm\{x\}\_\{L\}\)\{\[m\_\{K\}\(\\bm\{r\}\_\{k\}\)\]\}^\{\\text\{T\}\}\}\{\\sqrt\{F\}\}\.

###### Definition 2\(Structural subspace and structural observables\)\.

Given a query triplet<eh,rq,?\><e\_\{h\},r\_\{q\},?\>, define the structural subspace constructed by SIRLM as:

𝒮=span\(\{fup\(𝒓\)\|𝒓∈𝑹\|q\}∪\{mV\(𝒓k\)\|𝒓k∈𝑹mem\}k=1K\)\.\\displaystyle\\mathcal\{S\}=\\mathrm\{span\}\(\\\{f\_\{\\mathrm\{up\}\}\(\\bm\{r\}\)\|\\bm\{r\}\\in\\bm\{R\}\_\{\|q\}\\\}\\cup\{\\\{m\_\{V\}\(\\bm\{r\}\_\{k\}\)\|\\bm\{r\}\_\{k\}\\in\\bm\{R\}\_\{\\mathrm\{mem\}\}\\\}\}\_\{k=1\}^\{K\}\)\.
Let𝚷𝒮\\bm\{\\mathrm\{\\Pi\}\}\_\{\\mathcal\{S\}\}denote the orthogonal projection operator onto𝒮\\mathcal\{S\}\. Then any𝐱∈ℝF\\bm\{x\}\\in\\mathbb\{R\}^\{F\}can be uniquely decomposed in𝒮\\mathcal\{S\}as:

𝒙=𝚷𝒮​𝒙\+𝚷𝒮⟂​𝒙,\\displaystyle\\bm\{x\}=\\bm\{\\mathrm\{\\Pi\}\}\_\{\\mathcal\{S\}\}\\bm\{x\}\+\\bm\{\\mathrm\{\\Pi\}\}\_\{\\mathcal\{S\}\}^\{\\perp\}\\bm\{x\},where𝚷𝒮​𝐱∈𝒮\\bm\{\\mathrm\{\\Pi\}\}\_\{\\mathcal\{S\}\}\\bm\{x\}\\in\\mathcal\{S\}represents the structural component of𝐱\\bm\{x\}and𝚷𝒮⟂​𝐱\\bm\{\\mathrm\{\\Pi\}\}\_\{\\mathcal\{S\}\}^\{\\perp\}\\bm\{x\}is the semantic drift component orthogonal to𝒮\\mathcal\{S\}\.

Furthermore, define:

𝒖q=𝚷𝒮​fup​\(𝒓q\|q\)‖𝚷𝒮​fup​\(𝒓q\|q\)‖2,𝒓q\|q∈𝑹\|q,\\displaystyle\\bm\{u\}\_\{q\}=\\frac\{\\bm\{\\mathrm\{\\Pi\}\}\_\{\\mathcal\{S\}\}f\_\{\\mathrm\{up\}\}\(\\bm\{r\}\_\{q\|q\}\)\}\{\{\\\|\\bm\{\\mathrm\{\\Pi\}\}\_\{\\mathcal\{S\}\}f\_\{\\mathrm\{up\}\}\(\\bm\{r\}\_\{q\|q\}\)\\\|\}\_\{2\}\},\\hskip 5\.69054pt\\bm\{r\}\_\{q\|q\}\\in\\bm\{R\}\_\{\|q\},which represents extracting a unit direction from the structural representation ofrqr\_\{q\}within the structural subspace𝒮\\mathcal\{S\}, serving as the structural anchor ofrqr\_\{q\}\.

Based on𝐮q\\bm\{u\}\_\{q\}and𝚷𝒮\\bm\{\\mathrm\{\\Pi\}\}\_\{\\mathcal\{S\}\}, two structural observables can be defined:

1. ∙\\bulletStructural alignment score:Aq​\(𝒙\)=𝒖qT​𝒙A\_\{q\}\(\\bm\{x\}\)=\\bm\{u\}\_\{q\}^\{\\mathrm\{T\}\}\\bm\{x\}, which measures the relevance of any𝒙\\bm\{x\}to𝒓q\\bm\{r\}\_\{q\}within the structural subspace𝒮\\mathcal\{S\}\.
2. ∙\\bulletSemantic drift magnitude:D𝒮​\(𝒙\)=𝒖qT​𝒙D\_\{\\mathcal\{S\}\}\(\\bm\{x\}\)=\\bm\{u\}\_\{q\}^\{\\mathrm\{T\}\}\\bm\{x\}, which measures the relevance of any𝒙\\bm\{x\}to𝒓q\\bm\{r\}\_\{q\}within the structural subspace𝒮=‖𝚷𝒮⟂​𝒙‖2\\mathcal\{S\}=\{\\\|\\bm\{\\mathrm\{\\Pi\}\}\_\{\\mathcal\{S\}\}^\{\\perp\}\\bm\{x\}\\\|\}\_\{2\}, which quantifies the component of any𝒙\\bm\{x\}orthogonal to the structural subspace𝒮\\mathcal\{S\}\.

###### Assumption A\.

Given a strictly increasing functionϕ⁡\(⋅\)\\phi\(\\cdot\)and a strictly decreasing functionψ⁡\(⋅\)\\psi\(\\cdot\), for all Top\-KKrelations selected in Eq\. \([7](https://arxiv.org/html/2608.17443#S4.E7)\), we have:

Aq\(mV\(𝒓k\)\)=ϕ\(srel\(k\)\),D𝒮\(mV\(𝒓k\)\)=ψ\(srel\(k\)\)\.\\displaystyle A\_\{q\}\(m\_\{V\}\(\\bm\{r\}\_\{k\}\)\)=\\phi\(s\_\{\\mathrm\{rel\}\}^\{\(k\)\}\),\\hskip 5\.69054ptD\_\{\\mathcal\{S\}\}\(m\_\{V\}\(\\bm\{r\}\_\{k\}\)\)=\\psi\(s\_\{\\mathrm\{rel\}\}^\{\(k\)\}\)\.
Assume there exists a thresholds0s\_\{0\}such that\{srel\(k\)\>s0\}k=1K\{\\\{s\_\{\\mathrm\{rel\}\}^\{\(k\)\}\>s\_\{0\}\\\}\}\_\{k=1\}^\{K\}\. Then for𝐡Lbase\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}, we have:

Aq\(𝒉baseL\)≤ϕ\(s0\),D𝒮\(𝒉baseL\)≥ψ\(s0\)\.\\displaystyle A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\\leq\\phi\(s\_\{0\}\),\\hskip 5\.69054ptD\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\\geq\\psi\(s\_\{0\}\)\.That is, the aggregate result of the vanilla in\-context learning module has a clear separation boundary from the structural reasoning subspace of the query triplet\.

Based on the above definitions and assumptions, we present the following proposition\.

###### Proposition 1\.

Given a query triplet<eh,rq,?\><e\_\{h\},r\_\{q\},?\>and its corresponding structural subspace𝒮\\mathcal\{S\}, let𝐡LSRM\\bm\{h\}^\{\\mathrm\{SRM\}\}\_\{L\}and𝐡Lbase\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}be the outputs obtained from the SRM\-based and vanilla in\-context learning modules, respectively\. Then, the former exhibits stronger structural representation alignment and better suppression of semantic drift than the latter, i\.e\.,

Aq\(𝒉SRML\)\>Aq\(𝒉baseL\),D𝒮\(𝒉SRML\)<D𝒮\(𝒉baseL\)\.\\displaystyle A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{SRM\}\}\_\{L\}\)\>A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\),\\hskip 5\.69054ptD\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{SRM\}\}\_\{L\}\)<D\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\.

###### Proof\.

We prove the two claims separately\.

\(I\) Structural alignment improvement\.By Definitions[1](https://arxiv.org/html/2608.17443#Thmdefinition1)and[2](https://arxiv.org/html/2608.17443#Thmdefinition2), we have

\{Aq​\(𝒉Lbase\)=∑i≤Lexp⁡\(ai\)​Aq​\(fV​\(𝒙i\)\)∑j≤Lexp⁡\(aj\)Aq​\(𝒉LSRM\)=∑i≤Lexp⁡\(ai\)​Aq​\(fV​\(𝒙i\)\)∑j≤Lexp⁡\(aj\)\+∑z≤Kexp⁡\(bz\)\+∑k≤Kβk​Aq​\(mV​\(𝒓k\)\)\\displaystyle\\begin\{cases\}A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)=\\frac\{\\sum\\limits\_\{i\\leq L\}\\exp\{\(a\_\{i\}\)\}A\_\{q\}\\big\(f\_\{V\}\(\\bm\{x\}\_\{i\}\)\\big\)\}\{\\sum\\limits\_\{j\\leq L\}\\exp\{\(a\_\{j\}\)\}\}\\\\ A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{SRM\}\}\_\{L\}\)=\\frac\{\\sum\\limits\_\{i\\leq L\}\\exp\{\(a\_\{i\}\)\}A\_\{q\}\\big\(f\_\{V\}\(\\bm\{x\}\_\{i\}\)\\big\)\}\{\\sum\\limits\_\{j\\leq L\}\\exp\{\(a\_\{j\}\)\}\+\\sum\\limits\_\{z\\leq K\}\\exp\{\(b\_\{z\}\)\}\}\+\\sum\\limits\_\{k\\leq K\}\\beta\_\{k\}A\_\{q\}\\big\(m\_\{V\}\(\\bm\{r\}\_\{k\}\)\\big\)\\end\{cases\}⇒\\displaystyle\\RightarrowAq​\(𝒉LSRM\)=∑j≤Lexp⁡\(aj\)∑j≤Lexp⁡\(aj\)\+∑z≤Kexp⁡\(bz\)​Aq​\(𝒉Lbase\)\+∑k≤Kβk​Aq​\(mV​\(𝒓k\)\)\.\\displaystyle A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{SRM\}\}\_\{L\}\)=\\frac\{\\sum\\limits\_\{j\\leq L\}\\exp\{\(a\_\{j\}\)\}\}\{\\sum\\limits\_\{j\\leq L\}\\exp\{\(a\_\{j\}\)\}\+\\sum\\limits\_\{z\\leq K\}\\exp\{\(b\_\{z\}\)\}\}A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\+\\sum\\limits\_\{k\\leq K\}\\beta\_\{k\}A\_\{q\}\\big\(m\_\{V\}\(\\bm\{r\}\_\{k\}\)\\big\)\.
Letc=∑j≤Lexp⁡\(aj\)∑j≤Lexp⁡\(aj\)\+∑z≤Kexp⁡\(bz\)c=\\frac\{\\sum\\limits\_\{j\\leq L\}\\exp\{\(a\_\{j\}\)\}\}\{\\sum\\limits\_\{j\\leq L\}\\exp\{\(a\_\{j\}\)\}\+\\sum\\limits\_\{z\\leq K\}\\exp\{\(b\_\{z\}\)\}\}, then∑k≤Kβk=1−c\\sum\\limits\_\{k\\leq K\}\\beta\_\{k\}=1\-c\. Further, defineA¯mem=∑k≤Kβk​Aq​\(mV​\(𝒓k\)\)∑k≤Kβk\\overline\{A\}\_\{\\mathrm\{mem\}\}=\\frac\{\\sum\\limits\_\{k\\leq K\}\\beta\_\{k\}A\_\{q\}\\big\(m\_\{V\}\(\\bm\{r\}\_\{k\}\)\\big\)\}\{\\sum\\limits\_\{k\\leq K\}\\beta\_\{k\}\},Aq​\(𝒉LSRM\)A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{SRM\}\}\_\{L\}\)can be rewritten as:

Aq​\(𝒉LSRM\)=Aq​\(𝒉Lbase\)\+\(1−c\)​\(A¯mem−Aq​\(𝒉Lbase\)\)\.\\displaystyle A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{SRM\}\}\_\{L\}\)=A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\+\(1\-c\)\(\\overline\{A\}\_\{\\mathrm\{mem\}\}\-A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\)\.Therefore, it suffices to prove thatA¯mem\>Aq​\(𝒉Lbase\)\\overline\{A\}\_\{\\mathrm\{mem\}\}\>A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\.

According toAssumption[A](https://arxiv.org/html/2608.17443#Thmassumption1)and the definition ofA¯mem\\overline\{A\}\_\{\\mathrm\{mem\}\}, we have:

\{Aq​\(mV​\(𝒓k\)\)=ϕ⁡\(srel\(k\)\)\>ϕ⁡\(s0\)Aq​\(𝒉Lbase\)≤ϕ⁡\(s0\)⇒A¯mem\>Aq​\(𝒉Lbase\)\.\\displaystyle\\begin\{cases\}A\_\{q\}\(m\_\{V\}\(\\bm\{r\}\_\{k\}\)\)=\\phi\(s\_\{\\mathrm\{rel\}\}^\{\(k\)\}\)\>\\phi\(s\_\{0\}\)\\\\ A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\\leq\\phi\(s\_\{0\}\)\\end\{cases\}\\Rightarrow\\overline\{A\}\_\{\\mathrm\{mem\}\}\>A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\.Therefore,Aq​\(𝒉LSRM\)\>Aq​\(𝒉Lbase\)A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{SRM\}\}\_\{L\}\)\>A\_\{q\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)is proven\.

\(II\) Suppression of semantic drift\.Following a similar procedure as in the previous proof, and based on Definitions[1](https://arxiv.org/html/2608.17443#Thmdefinition1)and[2](https://arxiv.org/html/2608.17443#Thmdefinition2), we obtain:

\{D𝒮​\(𝒉Lbase\)=‖∑i≤Lexp⁡\(ai\)​𝚷𝒮⟂​fV​\(𝒙i\)∑j≤Lexp⁡\(aj\)‖2D𝒮​\(𝒉LSRM\)=‖∑i≤Lexp⁡\(ai\)​𝚷𝒮⟂​fV​\(𝒙i\)∑j≤Lexp⁡\(aj\)\+∑z≤Kexp⁡\(bz\)\+∑k≤Kβk​𝚷𝒮⟂​mV​\(𝒓k\)‖2\\displaystyle\\begin\{cases\}D\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)=\{\\Bigg\\\|\\frac\{\\sum\\limits\_\{i\\leq L\}\\exp\{\(a\_\{i\}\)\}\\bm\{\\mathrm\{\\Pi\}\}\_\{\\mathcal\{S\}\}^\{\\perp\}f\_\{V\}\(\\bm\{x\}\_\{i\}\)\}\{\\sum\\limits\_\{j\\leq L\}\\exp\{\(a\_\{j\}\)\}\}\\Bigg\\\|\}\_\{2\}\\\\ D\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{SRM\}\}\_\{L\}\)=\{\\Bigg\\\|\\frac\{\\sum\\limits\_\{i\\leq L\}\\exp\{\(a\_\{i\}\)\}\\bm\{\\mathrm\{\\Pi\}\}\_\{\\mathcal\{S\}\}^\{\\perp\}f\_\{V\}\(\\bm\{x\}\_\{i\}\)\}\{\\sum\\limits\_\{j\\leq L\}\\exp\{\(a\_\{j\}\)\}\+\\sum\\limits\_\{z\\leq K\}\\exp\{\(b\_\{z\}\)\}\}\+\\sum\\limits\_\{k\\leq K\}\\beta\_\{k\}\\bm\{\\mathrm\{\\Pi\}\}\_\{\\mathcal\{S\}\}^\{\\perp\}m\_\{V\}\(\\bm\{r\}\_\{k\}\)\\Bigg\\\|\}\_\{2\}\\end\{cases\}⇒\\displaystyle\\RightarrowD𝒮​\(𝒉LSRM\)≤c​D𝒮​\(𝒉Lbase\)\+∑k≤Kβk​D𝒮​\(mV​\(𝒓k\)\)\.\\displaystyle D\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{SRM\}\}\_\{L\}\)\\leq cD\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\+\\sum\\limits\_\{k\\leq K\}\\beta\_\{k\}D\_\{\\mathcal\{S\}\}\\big\(m\_\{V\}\(\\bm\{r\}\_\{k\}\)\\big\)\.
LetD¯mem=∑k≤Kβk​D𝒮​\(mV​\(𝒓k\)\)∑k≤Kβk\\overline\{D\}\_\{\\mathrm\{mem\}\}=\\frac\{\\sum\\limits\_\{k\\leq K\}\\beta\_\{k\}D\_\{\\mathcal\{S\}\}\\big\(m\_\{V\}\(\\bm\{r\}\_\{k\}\)\\big\)\}\{\\sum\\limits\_\{k\\leq K\}\\beta\_\{k\}\}, thenD𝒮​\(𝒉LSRM\)D\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{SRM\}\}\_\{L\}\)admits the following upper bound:

D𝒮​\(𝒉LSRM\)≤D𝒮​\(𝒉Lbase\)\+\(1−c\)​\(D¯mem−D𝒮​\(𝒉Lbase\)\)\.\\displaystyle D\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{SRM\}\}\_\{L\}\)\\leq D\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\+\(1\-c\)\(\\overline\{D\}\_\{\\mathrm\{mem\}\}\-D\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\)\.Thus, it suffices to prove thatD¯mem<D𝒮​\(𝒉Lbase\)\\overline\{D\}\_\{\\mathrm\{mem\}\}<D\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\.

According toAssumption[A](https://arxiv.org/html/2608.17443#Thmassumption1)and the definition ofD¯mem\\overline\{D\}\_\{\\mathrm\{mem\}\}, we have:

\{D𝒮​\(mV​\(𝒓k\)\)=ψ⁡\(srel\(k\)\)<ψ⁡\(s0\)D𝒮​\(𝒉Lbase\)≥ψ⁡\(s0\)⇒D¯mem<D𝒮​\(𝒉Lbase\)\.\\displaystyle\\begin\{cases\}D\_\{\\mathcal\{S\}\}\(m\_\{V\}\(\\bm\{r\}\_\{k\}\)\)=\\psi\(s\_\{\\mathrm\{rel\}\}^\{\(k\)\}\)<\\psi\(s\_\{0\}\)\\\\ D\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\\geq\\psi\(s\_\{0\}\)\\end\{cases\}\\Rightarrow\\overline\{D\}\_\{\\mathrm\{mem\}\}<D\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)\.Therefore,D𝒮​\(𝒉LSRM\)<D𝒮​\(𝒉Lbase\)D\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{SRM\}\}\_\{L\}\)<D\_\{\\mathcal\{S\}\}\(\\bm\{h\}^\{\\mathrm\{base\}\}\_\{L\}\)is proven\. ∎

Discussion\.The proof above establishes the effectiveness of Eq\. \([8](https://arxiv.org/html/2608.17443#S4.E8)\)\. The SRM branch does not merely append extra structural representation, it actively reorganizes the hidden state by aligning its structural component and suppressing text\-only semantic bias\. Because the next\-relation predictor in Eqs\. \([9](https://arxiv.org/html/2608.17443#S4.E9)\) and \([10](https://arxiv.org/html/2608.17443#S4.E10)\) operates directly on this hidden state, the hidden\-state improvement transfers into a larger score margin for the correct structural relation, thereby promoting the generation of KG\-grounded rules\.

## Appendix EDiscussion of the RCMP Mechanism

This section discusses the effectiveness of the proposed RCMP mechanism\. Based on the theoretical foundation of the previous studies\([Huang et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib14);[Huang et al\. 2025b](https://arxiv.org/html/2608.17443#bib.bib16)\), we start with the relational Weisfeiler\-Leman \(WL\) test\([Barceló et al\. 2022](https://arxiv.org/html/2608.17443#bib.bib2)\)to analyze the effectiveness of RCMP in terms of structural invariance learning, lower bound of model expression, and stricter reasoning scenarios\.

### E\.1A Two\-stage WL Test for the SIL Mechanism

Before formally discussing the effectiveness of RCMP, we first provide a theoretical background for the WL test of the primary SIL mechanism\([Huang et al\. 2025a](https://arxiv.org/html/2608.17443#bib.bib15)\)without RCMP\. Giving a KG𝒢=\(ℰ,ℛ,𝒯\)\\mathcal\{G\}=\(\\mathcal\{E\},\\mathcal\{R\},\\mathcal\{T\}\)and a corresponding relational graph𝒢r=\(ℛ,ℛ∗,𝒯∗\)\\mathcal\{G\}\_\{r\}=\(\\mathcal\{R\},\\mathcal\{R\}^\{\*\},\\mathcal\{T\}^\{\*\}\), the WL test of the SIL mechanism can be defined as atwo\-stage coloring scheme\.

Stage 1: relation coloring on𝒢r\\mathcal\{G\}\_\{r\}\. According to Eq\. \([1](https://arxiv.org/html/2608.17443#S3.E1)\), giving a query relationrq∈ℛr\_\{q\}\\in\\mathcal\{R\}, the color of relationrj∈ℛr\_\{j\}\\in\\mathcal\{R\}at iterationnnis denoted bycolr\(n\)​\(rj\|rq\)\\mathrm\{col\}\_\{r\}^\{\(n\)\}\(r\_\{j\}\|r\_\{q\}\)and initialized by

colr\(0\)​\(rj\|rq\)=𝕀⁡\(rj=rq\)⋅𝟏\.\\displaystyle\\mathrm\{col\}\_\{r\}^\{\(0\)\}\(r\_\{j\}\|r\_\{q\}\)=\\mathbb\{I\}\(r\_\{j\}=r\_\{q\}\)\\cdot\\mathbf\{1\}\.
It is then updated as

colr\(n\+1\)\\displaystyle\\mathrm\{col\}\_\{r\}^\{\(n\+1\)\}\(rj\|rq\)=\\displaystyle\(r\_\{j\}\|r\_\{q\}\)=HASH⁡\(colr\(n\)​\(rj\|rq\),\{\{\(\{\(colr\(n\)​\(rs\|rq\),ps\)∣\(rs,ps\)∈𝒩r∗​\(rj\)\},r∗\)∣r∗∈ℛ∗\}\}\),\\displaystyle\\mathrm\{HASH\}\\\!\\left\(\\mathrm\{col\}^\{\(n\)\}\_\{r\}\(r\_\{j\}\|r\_\{q\}\),\\\{\\\!\\\!\\\{\(\\\{\(\\mathrm\{col\}^\{\(n\)\}\_\{r\}\(r\_\{s\}\|r\_\{q\}\),p\_\{s\}\)\\mid\(r\_\{s\},p\_\{s\}\)\\in\\mathcal\{N\}\_\{r^\{\*\}\}\(r\_\{j\}\)\\\},r^\{\*\}\)\\mid r^\{\*\}\\in\\mathcal\{R\}^\{\*\}\\\}\\\!\\\!\\\}\\right\),where𝒩r∗​\(rj\)\\mathcal\{N\}\_\{r^\{\*\}\}\(r\_\{j\}\)represents the set of all neighbors ofrjr\_\{j\}onr∗r^\{\*\}\. Sincer∗r^\{\*\}is a hyperedge,𝒩r∗​\(rj\)\\mathcal\{N\}\_\{r^\{\*\}\}\(r\_\{j\}\)stores each neighborrsr\_\{s\}and its positionpsp\_\{s\}onr∗r^\{\*\}\.HASH​\(⋅\)\\text\{HASH\}\(\\cdot\)is an abstract injective coloring function\([Barceló et al\. 2022](https://arxiv.org/html/2608.17443#bib.bib2)\)that compresses old colors and neighborhood information into a new color label\. As long as the input is different, the output color will be different\.

Stage 2: entity coloring on𝒢\\mathcal\{G\}\. Given a fixed numberNNof first\-stage iterations, the color of an entityeve\_\{v\}in a candidate triplet<eu,rq,ev\><e\_\{u\},r\_\{q\},e\_\{v\}\>at iterationℓ\\ellis denoted bycole\(ℓ\)​\(ev\|eu,rq\)\\mathrm\{col\}^\{\(\\ell\)\}\_\{e\}\(e\_\{v\}\|e\_\{u\},r\_\{q\}\)\. It is initialized by

cole\(0\)​\(ev\|eu,rq\)=𝕀⁡\(ev=eu\)⋅colr\(N\)​\(rq\|rq\),\\displaystyle\\mathrm\{col\}\_\{e\}^\{\(0\)\}\(e\_\{v\}\|e\_\{u\},r\_\{q\}\)=\\mathbb\{I\}\(e\_\{v\}=e\_\{u\}\)\\cdot\\mathrm\{col\}\_\{r\}^\{\(N\)\}\(r\_\{q\}\|r\_\{q\}\),and updated as

cole\(ℓ\+1\)\\displaystyle\\mathrm\{col\}\_\{e\}^\{\(\\ell\+1\)\}\(ev\|eu,rq\)=\\displaystyle\(e\_\{v\}\|e\_\{u\},r\_\{q\}\)=HASH\(cole\(ℓ\)\(ev\|eu,rq\),\{\{\(cole\(ℓ\)\(ew\|eu,rq\),colr\(N\)\(rj\|rq\)\)∣ew∈𝒩rj\(ev\),rj∈ℛ\}\}\)\.\\displaystyle\\mathrm\{HASH\}\\\!\\left\(\\mathrm\{col\}\_\{e\}^\{\(\\ell\)\}\(e\_\{v\}\|e\_\{u\},r\_\{q\}\),\\\{\\\!\\\!\\\{\(\\mathrm\{col\}\_\{e\}^\{\(\\ell\)\}\(e\_\{w\}\|e\_\{u\},r\_\{q\}\),\\mathrm\{col\}\_\{r\}^\{\(N\)\}\(r\_\{j\}\|r\_\{q\}\)\)\\mid e\_\{w\}\\in\\mathcal\{N\}\_\{r\_\{j\}\}\(e\_\{v\}\),\\ r\_\{j\}\\in\\mathcal\{R\}\\\}\\\!\\\!\\\}\\right\)\.This two\-stage WL test characterizes the separating power of the SIL mechanism\([Huang et al\. 2025a](https://arxiv.org/html/2608.17443#bib.bib15)\): it is both an upper bound and a tight characterization under injective message\-passing choices\.

### E\.2A Two\-stage WL Test for the RCMP Mechanism

This section provides a detailed elaboration on the effectiveness of the proposed RCMP based onAppendix[E\.1](https://arxiv.org/html/2608.17443#A5.SS1)\. First, we outline the overall pipeline of the proposed SIRLM asDefinition[3](https://arxiv.org/html/2608.17443#Thmdefinition3)for subsequent analysis\.

###### Definition 3\.

Giving a KG𝒢=\(ℰ,ℛ,𝒯\)\\mathcal\{G\}=\(\\mathcal\{E\},\\mathcal\{R\},\\mathcal\{T\}\)and a corresponding relational graph𝒢r=\(ℛ,ℛ∗,𝒯∗\)\\mathcal\{G\}\_\{r\}=\(\\mathcal\{R\},\\mathcal\{R\}^\{\*\},\\mathcal\{T\}^\{\*\}\), SIRLM processes a query<eu,rq,?\><e\_\{u\},r\_\{q\},?\>through the following stages:

Stage 1: structural tokenization\.We first run Eqs\. \([1](https://arxiv.org/html/2608.17443#S3.E1)\) and \([2](https://arxiv.org/html/2608.17443#S3.E2)\) to obtain structural token embeddigns of relation𝐫j\|q∈𝐑\|q\\bm\{r\}\_\{j\|q\}\\in\\bm\{R\}\_\{\|q\}and entity𝐞i\|u∈𝐄\|u\\bm\{e\}\_\{i\|u\}\\in\\bm\{E\}\_\{\|u\}\.These embeddings are used as structure\-only tokens; no entity names, relation names, or textual attributes are used\. In particular, only𝐞u\|u\\bm\{e\}\_\{u\|u\}and𝐫q\|q\\bm\{r\}\_\{q\|q\}are exposed to the rule generator as query context\.

Stage 2: structure\-aware rule generation\.Let𝒫sys\\mathcal\{P\}\_\{\\mathrm\{sys\}\}be a fixed system prompt\. For a queryrq​\(eu,?\)r\_\{q\}\(e\_\{u\},?\), define the input prompt as

Π⁡\(eu,rq\)=\[𝒫sys;𝒆u\|u;𝒓q\|q\]\.\\displaystyle\\Pi\(e\_\{u\},r\_\{q\}\)=\[\\mathcal\{P\}\_\{\\mathrm\{sys\}\};\\ \\bm\{e\}\_\{u\|u\};\\ \\bm\{r\}\_\{q\|q\}\\,\]\.LLM generates a rule consisting of a sequence of atomic relation

ρ⁡\(eu,rq\)=r1\|Π⁡\(eu,rq\),…,rZ\|Π⁡\(eu,rq\)∈ℛ\\displaystyle\\rho\(e\_\{u\},r\_\{q\}\)=r\_\{1\|\\Pi\(e\_\{u\},r\_\{q\}\)\},\\ldots,r\_\{Z\|\\Pi\(e\_\{u\},r\_\{q\}\)\}\\in\\mathcal\{R\}and corresponding hidden states

𝒉1\|Π⁡\(eu,rq\),…,𝒉Z\|Π⁡\(eu,rq\)\.\\displaystyle\\bm\{h\}\_\{1\|\\Pi\(e\_\{u\},r\_\{q\}\)\},\\ldots,\\bm\{h\}\_\{Z\|\\Pi\(e\_\{u\},r\_\{q\}\)\}\.
Atzz\-th generation iteration, the last hidden state𝐡z−1\|Π⁡\(eu,rq\)\\bm\{h\}\_\{z\-1\|\\Pi\(e\_\{u\},r\_\{q\}\)\}is computed by a LLM fed withΠ⁡\(eu,rq\)\\Pi\(e\_\{u\},r\_\{q\}\)and the previouslyz−1z\-1generated atomic relations\. The next atomic relation is then selected by a lookup over the structured relation\-token bank𝐑\|q\\bm\{R\}\_\{\|q\}:

rz\|Π⁡\(eu,rq\)=arg⁡maxrj∈R⁡Score⁡\(𝒉z−1\|Π⁡\(eu,rq\),𝒓j\|q\),\\displaystyle r\_\{z\|\\Pi\(e\_\{u\},r\_\{q\}\)\}=\\arg\\max\_\{r\_\{j\}\\in R\}\\ \\mathrm\{Score\}\\bigl\(\\bm\{h\}\_\{z\-1\|\\Pi\(e\_\{u\},r\_\{q\}\)\},\\bm\{r\}\_\{j\|q\}\\bigr\),whereScore⁡\(⋅\)\\mathrm\{Score\}\(\\cdot\)is a relation\-token lookup scorer\.

Stage 3: RCMP initialization of𝒢r\\mathcal\{G\}\_\{r\}\.For each relationr∈ℛr\\in\\mathcal\{R\}, define the accumulated rule representation as

𝒙\(r\|eu,rq\)=∑z:rz\|Π⁡\(eu,rq\)=r𝒉z\|Π⁡\(eu,rq\),\\displaystyle\\bm\{x\}\(r\|e\_\{u\},r\_\{q\}\)=\\sum\_\{z\\,:\\,r\_\{z\|\\Pi\(e\_\{u\},r\_\{q\}\)\}=r\}\\bm\{h\}\_\{z\|\\Pi\(e\_\{u\},r\_\{q\}\)\},with the convention that𝐱⁡\(r\|eu,rq\)=𝟎\\bm\{x\}\(r\|e\_\{u\},r\_\{q\}\)=\\mathbf\{0\}ifrrdoes not occur inρ⁡\(eu,rq\)\\rho\(e\_\{u\},r\_\{q\}\)\. This additive definition directly handles repeated relations, that is, every occurrence contributes its own autoregressive hidden state, and all such occurrence\-specific hidden states are accumulated\.

Giving the generated ruleρ⁡\(eu,rq\)\\rho\(e\_\{u\},r\_\{q\}\)and the accumulated rule representation𝐱\(⋅\|eu,rq\)\\bm\{x\}\(\\cdot\|e\_\{u\},r\_\{q\}\), the RCMP initialization of𝒢r\\mathcal\{G\}\_\{r\}can be concretized as

INIT~1​\(rj\|eu,rq\)=𝕀⁡\(rj=rq\)⋅𝟏\+𝒙⁡\(rj\|eu,rq\),\\displaystyle\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)=\\mathbb\{I\}\(r\_\{j\}=r\_\{q\}\)\\cdot\\mathbf\{1\}\+\\bm\{x\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\),where𝟏≠𝟎\\mathbf\{1\}\\neq\\mathbf\{0\}are fixed vectors\. Equivalently, if the query relationrqr\_\{q\}appears in the generated rule body, then its node in the relational graph is initialized by the anchor vector𝟏\\mathbf\{1\}plus the sum of all hidden states associated with occurrences ofrqr\_\{q\}inρ⁡\(eu,rq\)\\rho\(e\_\{u\},r\_\{q\}\)\. Likewise, if any non\-query relationrjr\_\{j\}appears multiple times inρ⁡\(eu,rq\)\\rho\(e\_\{u\},r\_\{q\}\), then its initialization is the sum of the hidden states associated with all of its occurrences\.

It should be emphasized that RCMP only changes the initialization strategy of the relational graph𝒢r\\mathcal\{G\}\_\{r\}in SIL withINIT~1​\(rj\|eu,rq\)\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\), while keeping𝒢r\\mathcal\{G\}\_\{r\}and all relation and entity message\-passing operators unchanged\.

###### Assumption B\.

We make the following assumptions\.

- 1\.Structure\-token invariance\. The base embeddings𝒓j\|q∈𝑹\|q\\bm\{r\}\_\{j\|q\}\\in\\bm\{R\}\_\{\|q\}and𝒆i\|u∈𝑬\|u\\bm\{e\}\_\{i\|u\}\\in\\bm\{E\}\_\{\|u\}are structurally invariants inDefinition[3](https://arxiv.org/html/2608.17443#Thmdefinition3)\.
- 2\.Equivariance of LLM generation for structural relation tokens\. For every isomorphismh=\(π,ϕ\):𝒢→𝒢′h=\(\\pi,\\phi\):\\mathcal\{G\}\\to\\mathcal\{G\}^\{\\prime\}, the autoregressive decoder and the lookup rule are equivariant with respect to the induced renaming of the structural tokens, i\.e\., 𝒉z\|Π⁡\(eu,rq\)=𝒉z\|Π⁡\(π⁡\(eu\),ϕ⁡\(rq\)\),rz\|Π⁡\(π⁡\(eu\),ϕ⁡\(rq\)\)=ϕ\(rz\|Π⁡\(eu,rq\)\)\.\\displaystyle\\bm\{h\}\_\{z\|\\Pi\(e\_\{u\},r\_\{q\}\)\}=\\bm\{h\}\_\{z\|\\Pi\(\\pi\(e\_\{u\}\),\\phi\(r\_\{q\}\)\)\},\\qquad r\_\{z\|\\Pi\(\\pi\(e\_\{u\}\),\\phi\(r\_\{q\}\)\)\}=\\phi\(r\_\{z\|\\Pi\(e\_\{u\},r\_\{q\}\)\}\)\.
- 3\.Anchor separation of relations\. Query relations are disjoint from non\-query relations, i\.e\., 𝟏\+𝒙⁡\(rj\|eu,rq\)≠𝒙⁡\(rj′\|eu′,rq′\)whenever​rj′≠rq′\.\\displaystyle\\mathbf\{1\}\+\\bm\{x\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)\\neq\\bm\{x\}\(r^\{\\prime\}\_\{j\}\|e^\{\\prime\}\_\{u\},r^\{\\prime\}\_\{q\}\)\\qquad\\text\{whenever \}r^\{\\prime\}\_\{j\}\\neq r^\{\\prime\}\_\{q\}\.Equivalently,INIT~1​\(rj\|eu,rq\)=INIT~1​\(rj′\|eu′,rq′\)\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)=\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(r^\{\\prime\}\_\{j\}\|e^\{\\prime\}\_\{u\},r^\{\\prime\}\_\{q\}\)impliesrj=rqr\_\{j\}=r\_\{q\}if and only ifrj′=rq′r^\{\\prime\}\_\{j\}=r^\{\\prime\}\_\{q\}\.
- 4\.Injective operator in RCMP\. The update, aggregation, and message functions in both the relation encoder and the entity encoder are injective, exactly as in the constructive direction ofAppendix[E\.1](https://arxiv.org/html/2608.17443#A5.SS1)\.

The next analysis shows that the proposed RCMP preserves structural invariance and refines the expressive power of the original SIL model\.

###### Proposition 2\.

UnderAssumptions[B](https://arxiv.org/html/2608.17443#Thmassumption2)1\-[B](https://arxiv.org/html/2608.17443#Thmassumption2)4, the following hold for RCMP\.

1. I\.The initializationINIT~1​\(u,q,r\)\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(u,q,r\)has relation invariance\. Consequently, RCMP computes relation invariants in the relation encoder and link invariants in the entity encoder\.
2. II\.Let col~r\(0\)​\(rj\|eu,rq\)=χ⁡\(INIT~1​\(rj\|eu,rq\)\),\\displaystyle\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(0\)\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)=\\chi\\\!\\left\(\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)\\right\),whereχ\\chiis injective, and let\(col~r,col~e\)\(\\widetilde\{\\mathrm\{col\}\}\_\{r\},\\widetilde\{\\mathrm\{col\}\}\_\{e\}\)be the two\-stage WL test of RCMP, while keeping all update rules unchanged\. Then for alln,ℓ≥0n,\\ell\\geq 0, we have col~r\(n\)​\(rj\|eu,rq\)=col~r\(n\)​\(rj′\|eu′,rq′\)⟹colr\(n\)​\(rj\|rq\)=colr\(n\)​\(rj′\|rq′\)\\displaystyle\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(n\)\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)=\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(n\)\}\(r^\{\\prime\}\_\{j\}\|e^\{\\prime\}\_\{u\},r^\{\\prime\}\_\{q\}\)\\Longrightarrow\\mathrm\{col\}\_\{r\}^\{\(n\)\}\(r\_\{j\}\|r\_\{q\}\)=\\mathrm\{col\}\_\{r\}^\{\(n\)\}\(r^\{\\prime\}\_\{j\}\|r^\{\\prime\}\_\{q\}\)and col~e\(ℓ\)​\(ev\|eu,rq\)=col~e\(ℓ\)​\(ev′\|eu′,rq′\)⟹cole\(ℓ\)​\(ev\|eu,rq\)=cole\(ℓ\)​\(ev′\|eu′,rq′\)\.\\displaystyle\\widetilde\{\\mathrm\{col\}\}\_\{e\}^\{\(\\ell\)\}\(e\_\{v\}\|e\_\{u\},r\_\{q\}\)=\\widetilde\{\\mathrm\{col\}\}\_\{e\}^\{\(\\ell\)\}\(e^\{\\prime\}\_\{v\}\|e^\{\\prime\}\_\{u\},r^\{\\prime\}\_\{q\}\)\\Longrightarrow\\mathrm\{col\}\_\{e\}^\{\(\\ell\)\}\(e\_\{v\}\|e\_\{u\},r\_\{q\}\)=\\mathrm\{col\}\_\{e\}^\{\(\\ell\)\}\(e^\{\\prime\}\_\{v\}\|e^\{\\prime\}\_\{u\},r^\{\\prime\}\_\{q\}\)\.Hence RCMP is at least as expressive as the original SIL model\.
3. III\.Assume there exist a query<eu,rq,?\><e\_\{u\},r\_\{q\},?\>and two relationsrj,rs∈ℛr\_\{j\},r\_\{s\}\\in\\mathcal\{R\}such that colr\(n\)​\(rj,rq\)=colr\(n\)​\(rs,rq\)for all​n≥0,\\displaystyle\\mathrm\{col\}\_\{r\}^\{\(n\)\}\(r\_\{j\},r\_\{q\}\)=\\mathrm\{col\}\_\{r\}^\{\(n\)\}\(r\_\{s\},r\_\{q\}\)\\quad\\text\{for all \}n\\geq 0,but INIT~1​\(rj\|eu,rq\)≠INIT~1​\(rs\|eu,rq\)\.\\displaystyle\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)\\neq\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(r\_\{s\}\|e\_\{u\},r\_\{q\}\)\.Then the refinement is strict, that is, there exists a KG and two query links that cannot be separated by any instance of SIL, but can be separated by some instance of RCMP\.

###### Proof\.

We prove the three claims as follows\.

I\.INIT~1\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}is a relation invariant\.ByAssumption[B](https://arxiv.org/html/2608.17443#Thmassumption2)1,𝑹\|q\\bm\{R\}\_\{\|q\}and𝑬\|u\\bm\{E\}\_\{\|u\}depend only on KG structure, not on concrete entity or relation names\. Since the promptΠ⁡\(eu,rq\)\\Pi\(e\_\{u\},r\_\{q\}\)is formed only by these structural tokens and a fixed system prompt,Assumption[B](https://arxiv.org/html/2608.17443#Thmassumption2)2implies that for every graph isomorphismh=\(π,ϕ\):𝒢→𝒢′h=\(\\pi,\\phi\):\\mathcal\{G\}\\to\\mathcal\{G\}^\{\\prime\}, we have

𝒉z\|Π⁡\(eu,rq\)=𝒉z\|Π⁡\(π⁡\(eu\),ϕ⁡\(rq\)\)andrz\|Π⁡\(π⁡\(eu\),ϕ⁡\(rq\)\)=ϕ⁡\(rz\|Π⁡\(eu,rq\)\)\\displaystyle\\bm\{h\}\_\{z\|\\Pi\(e\_\{u\},r\_\{q\}\)\}=\\bm\{h\}\_\{z\|\\Pi\(\\pi\(e\_\{u\}\),\\phi\(r\_\{q\}\)\)\}\\qquad\\text\{and\}\\qquad r\_\{z\|\\Pi\(\\pi\(e\_\{u\}\),\\phi\(r\_\{q\}\)\)\}=\\phi\(r\_\{z\|\\Pi\(e\_\{u\},r\_\{q\}\)\}\)for all decoding stepszz\. Therefore, for every relationrj∈ℛr\_\{j\}\\in\\mathcal\{R\}, the accumulated rule signal satisfies

𝒙⁡\(rj\|eu,rq\)=𝒙⁡\(ϕ⁡\(rj\)\|π⁡\(eu\),ϕ⁡\(rq\)\)\.\\displaystyle\\bm\{x\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)=\\bm\{x\}\(\\phi\(r\_\{j\}\)\|\\pi\(e\_\{u\}\),\\phi\(r\_\{q\}\)\)\.Since the query\-anchor caserj=rqr\_\{j\}=r\_\{q\}is mapped toϕ⁡\(rj\)=ϕ⁡\(rq\)\\phi\(r\_\{j\}\)=\\phi\(r\_\{q\}\)under the same isomorphism, the initialization satisfies

INIT~1​\(rj\|eu,rq\)=INIT~1​\(ϕ⁡\(rj\)\|π⁡\(eu\),ϕ⁡\(rq\)\)\.\\displaystyle\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)=\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(\\phi\(r\_\{j\}\)\|\\pi\(e\_\{u\}\),\\phi\(r\_\{q\}\)\)\.HenceINIT~1\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}is a relation invariant\.

Now the relation encoder follows exactly the same inductive argument used in the main manuscript\. Once the initializationINIT~1\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}is a relation invariant, every subsequent layer of the relation encoder remains a relation invariant because message, aggregation, and update only combine invariant quantities over the relational graph𝒢r\\mathcal\{G\}\_\{r\}\. Likewise, the entity encoder receives invariant relation representations and uses the same message\-passing structure as the original SIL model, so it computes link invariants\.

II\. RCMP is at least as expressive as the original SIL model\.We define the first\-stage colors of RCMP by

col~r\(0\)​\(rj\|eu,rq\)=χ⁡\(INIT~1​\(rj\|eu,rq\)\),\\displaystyle\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(0\)\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)=\\chi\\\!\\left\(\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)\\right\),Then, forn≥0n\\geq 0, we use the same first\-stage update as inAppendix[E\.1](https://arxiv.org/html/2608.17443#A5.SS1), but with the richer initial coloring:

col~r\(n\+1\)\\displaystyle\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(n\+1\)\}\(rj\|eu,rq\)=\\displaystyle\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)=HASH⁡\(col~r\(n\)​\(rj\|eu,rq\),\{\{\(\{\(col~r\(n\)​\(rs\|eu,rq\),ps\)∣\(rs,ps\)∈𝒩r∗​\(rj\)\},r∗\)∣r∗∈ℛ∗\}\}\)\.\\displaystyle\\mathrm\{HASH\}\\left\(\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(n\)\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\),\\right\.\\left\.\\\{\\\!\\\!\\\{\(\\\{\(\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(n\)\}\(r\_\{s\}\|e\_\{u\},r\_\{q\}\),p\_\{s\}\)\\mid\(r\_\{s\},p\_\{s\}\)\\in\\mathcal\{N\}\_\{r^\{\*\}\}\(r\_\{j\}\)\\\},r^\{\*\}\)\\mid r^\{\*\}\\in\\mathcal\{R\}^\{\*\}\\\}\\\!\\\!\\\}\\right\)\.Similarly, define the second\-stage colors by

col~e\(0\)​\(ev\|eu,rq\)=𝕀⁡\(ev=eu\)⋅col~r\(N\)​\(rq\|eu,rq\),\\displaystyle\\widetilde\{\\mathrm\{col\}\}\_\{e\}^\{\(0\)\}\(e\_\{v\}\|e\_\{u\},r\_\{q\}\)=\\mathbb\{I\}\(e\_\{v\}=e\_\{u\}\)\\cdot\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(N\)\}\(r\_\{q\}\|e\_\{u\},r\_\{q\}\),and forℓ≥0\\ell\\geq 0,

col~e\(ℓ\+1\)\\displaystyle\\widetilde\{\\mathrm\{col\}\}\_\{e\}^\{\(\\ell\+1\)\}\(ev\|eu,rq\)=\\displaystyle\(e\_\{v\}\|e\_\{u\},r\_\{q\}\)=HASH\(col~e\(ℓ\)\(ev\|eu,rq\),\{\{\(col~e\(ℓ\)\(ew\|eu,rq\),col~r\(N\)\(rj\|eu,rq\)\)∣ew∈𝒩rj\(ev\),rj∈ℛ\}\}\)\.\\displaystyle\\mathrm\{HASH\}\\\!\\left\(\\widetilde\{\\mathrm\{col\}\}\_\{e\}^\{\(\\ell\)\}\(e\_\{v\}\|e\_\{u\},r\_\{q\}\),\\\{\\\!\\\!\\\{\(\\widetilde\{\\mathrm\{col\}\}\_\{e\}^\{\(\\ell\)\}\(e\_\{w\}\|e\_\{u\},r\_\{q\}\),\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(N\)\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)\)\\mid e\_\{w\}\\in\\mathcal\{N\}\_\{r\_\{j\}\}\(e\_\{v\}\),\\ r\_\{j\}\\in\\mathcal\{R\}\\\}\\\!\\\!\\\}\\right\)\.\(1\) We first prove by induction onnnthat

col~r\(n\)​\(rj\|eu,rq\)=col~r\(n\)​\(rj′\|eu′,rq′\)⟹colr\(n\)​\(rj\|rq\)=colr\(n\)​\(rj′\|rq′\)\.\\displaystyle\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(n\)\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)=\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(n\)\}\(r^\{\\prime\}\_\{j\}\|e^\{\\prime\}\_\{u\},r^\{\\prime\}\_\{q\}\)\\Longrightarrow\\mathrm\{col\}\_\{r\}^\{\(n\)\}\(r\_\{j\}\|r\_\{q\}\)=\\mathrm\{col\}\_\{r\}^\{\(n\)\}\(r^\{\\prime\}\_\{j\}\|r^\{\\prime\}\_\{q\}\)\.
Forn=0n=0, injectivity ofχ\\chigivesINIT~1​\(rj\|eu,rq\)=INIT~1​\(rj′\|eu′,rq′\)\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)=\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(r^\{\\prime\}\_\{j\}\|e^\{\\prime\}\_\{u\},r^\{\\prime\}\_\{q\}\)\. According toAssumption[B](https://arxiv.org/html/2608.17443#Thmassumption2)3, such an equation preserves whether the anchor contribution𝕀⁡\(rj=rq\)⋅𝟏\\mathbb\{I\}\(r\_\{j\}=r\_\{q\}\)\\cdot\\mathbf\{1\}is present\. Therefore,𝕀⁡\(rj=rq\)=𝕀⁡\(rj′=rq′\)\\mathbb\{I\}\(r\_\{j\}=r\_\{q\}\)=\\mathbb\{I\}\(r^\{\\prime\}\_\{j\}=r^\{\\prime\}\_\{q\}\), which is exactly

colr\(0\)​\(rj\|rq\)=colr\(0\)​\(rj′\|rq′\)\.\\displaystyle\\mathrm\{col\}\_\{r\}^\{\(0\)\}\(r\_\{j\}\|r\_\{q\}\)=\\mathrm\{col\}\_\{r\}^\{\(0\)\}\(r^\{\\prime\}\_\{j\}\|r^\{\\prime\}\_\{q\}\)\.
Assume the implication holds at layernnand suppose

col~r\(n\+1\)​\(rj\|eu,rq\)=col~r\(n\+1\)​\(rj′\|eu′,rq′\)\.\\displaystyle\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(n\+1\)\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)=\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(n\+1\)\}\(r^\{\\prime\}\_\{j\}\|e^\{\\prime\}\_\{u\},r^\{\\prime\}\_\{q\}\)\.
SinceHASH\\mathrm\{HASH\}is injective, both the previous colors and the corresponding position\-aware neighbor multisets of SIL must agree\. Applying the induction hypothesis to all first\-stage colors appearing inside those multisets shows that the original colors inAppendix[E\.1](https://arxiv.org/html/2608.17443#A5.SS1)also agree\. Therefore the multisets definingcolr\(n\+1\)​\(rj\|rq\)\\mathrm\{col\}\_\{r\}^\{\(n\+1\)\}\(r\_\{j\}\|r\_\{q\}\)andcolr\(n\+1\)​\(rj′\|rq′\)\\mathrm\{col\}\_\{r\}^\{\(n\+1\)\}\(r^\{\\prime\}\_\{j\}\|r^\{\\prime\}\_\{q\}\)coincide, thus

colr\(n\+1\)​\(rj\|rq\)=colr\(n\+1\)​\(rj′\|rq′\)\\displaystyle\\mathrm\{col\}\_\{r\}^\{\(n\+1\)\}\(r\_\{j\}\|r\_\{q\}\)=\\mathrm\{col\}\_\{r\}^\{\(n\+1\)\}\(r^\{\\prime\}\_\{j\}\|r^\{\\prime\}\_\{q\}\)is proven\.

\(2\) We next prove by induction onℓ\\ellthat

col~e\(ℓ\)​\(ev\|eu,rq\)=col~e\(ℓ\)​\(ev′\|eu′,rq′\)⟹cole\(ℓ\)​\(ev\|eu,rq\)=cole\(ℓ\)​\(ev′\|eu′,rq′\)\.\\displaystyle\\widetilde\{\\mathrm\{col\}\}\_\{e\}^\{\(\\ell\)\}\(e\_\{v\}\|e\_\{u\},r\_\{q\}\)=\\widetilde\{\\mathrm\{col\}\}\_\{e\}^\{\(\\ell\)\}\(e^\{\\prime\}\_\{v\}\|e^\{\\prime\}\_\{u\},r^\{\\prime\}\_\{q\}\)\\Longrightarrow\\mathrm\{col\}\_\{e\}^\{\(\\ell\)\}\(e\_\{v\}\|e\_\{u\},r\_\{q\}\)=\\mathrm\{col\}\_\{e\}^\{\(\\ell\)\}\(e^\{\\prime\}\_\{v\}\|e^\{\\prime\}\_\{u\},r^\{\\prime\}\_\{q\}\)\.Forℓ=0\\ell=0, equality of the RCMP colors implies

𝕀⁡\(ev=eu\)=𝕀⁡\(ev′=eu′\)andcol~r\(N\)​\(rj\|eu,rq\)=col~r\(N\)​\(rj′\|eu′,rq′\)\.\\displaystyle\\mathbb\{I\}\(e\_\{v\}=e\_\{u\}\)=\\mathbb\{I\}\(e^\{\\prime\}\_\{v\}=e^\{\\prime\}\_\{u\}\)\\qquad\\text\{and\}\\qquad\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(N\)\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)=\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(N\)\}\(r^\{\\prime\}\_\{j\}\|e^\{\\prime\}\_\{u\},r^\{\\prime\}\_\{q\}\)\.By the first\-stage result proved above, we obtain

colr\(N\)​\(rq\|rq\)=colr\(N\)​\(rq′\|rq′\),\\displaystyle\\mathrm\{col\}\_\{r\}^\{\(N\)\}\(r\_\{q\}\|r\_\{q\}\)=\\mathrm\{col\}\_\{r\}^\{\(N\)\}\(r^\{\\prime\}\_\{q\}\|r^\{\\prime\}\_\{q\}\),hence

cole\(0\)​\(ev\|eu,rq\)=cole\(0\)​\(ev′\|eu′,rq′\)\.\\displaystyle\\mathrm\{col\}\_\{e\}^\{\(0\)\}\(e\_\{v\}\|e\_\{u\},r\_\{q\}\)=\\mathrm\{col\}\_\{e\}^\{\(0\)\}\(e^\{\\prime\}\_\{v\}\|e^\{\\prime\}\_\{u\},r^\{\\prime\}\_\{q\}\)\.
Assume the implication holds at layerℓ\\elland suppose

col~e\(ℓ\+1\)​\(ev\|eu,rq\)=col~e\(ℓ\+1\)​\(ev′\|eu′,rq′\)\.\\displaystyle\\widetilde\{\\mathrm\{col\}\}\_\{e\}^\{\(\\ell\+1\)\}\(e\_\{v\}\|e\_\{u\},r\_\{q\}\)=\\widetilde\{\\mathrm\{col\}\}\_\{e\}^\{\(\\ell\+1\)\}\(e^\{\\prime\}\_\{v\}\|e^\{\\prime\}\_\{u\},r^\{\\prime\}\_\{q\}\)\.Injectivity ofHASH\\mathrm\{HASH\}yields equality of the previous second\-stage colors of SIL and of the corresponding message multisets\. By the induction hypothesis onℓ\\elland the first\-stage implication already proved, the original second\-stage colors and original first\-stage relation colors also agree\. Therefore, the multisets definingc​o​lF,T\(ℓ\+1\)​\(q⁡\(u,v\)\)col^\{\(\\ell\+1\)\}\_\{F,T\}\(q\(u,v\)\)andc​o​lF,T\(ℓ\+1\)​\(q′​\(u′,v′\)\)col^\{\(\\ell\+1\)\}\_\{F,T\}\(q^\{\\prime\}\(u^\{\\prime\},v^\{\\prime\}\)\)are identical, and the assumption

cole\(ℓ\+1\)​\(ev\|eu,rq\)=cole\(ℓ\+1\)​\(ev′\|eu′,rq′\)\\displaystyle\\mathrm\{col\}\_\{e\}^\{\(\\ell\+1\)\}\(e\_\{v\}\|e\_\{u\},r\_\{q\}\)=\\mathrm\{col\}\_\{e\}^\{\(\\ell\+1\)\}\(e^\{\\prime\}\_\{v\}\|e^\{\\prime\}\_\{u\},r^\{\\prime\}\_\{q\}\)is proven\.

Therefore, the two\-stage WL test of RCMP is a refinement of the original two\-stage test of SIL onAppendix[E\.1](https://arxiv.org/html/2608.17443#A5.SS1)\. UnderAssumption[B](https://arxiv.org/html/2608.17443#Thmassumption2)4, the same constructive argument as inAppendix[E\.1](https://arxiv.org/html/2608.17443#A5.SS1)applies to the present model, because only the initialization changes while the message\-passing architecture over𝒢r\\mathcal\{G\}\_\{r\}and over the original KG remains unchanged\. Therefore, the refined two\-stage test characterizes RCMP, and the refinement of the WL tests implies that RCMP is at least as expressive as SIL\.

III\. Strictness\.Assume there exist a query triplet<eu,rq,?\><e\_\{u\},r\_\{q\},?\>and two relationsrj,rs∈ℛr\_\{j\},r\_\{s\}\\in\\mathcal\{R\}that satisfy

colr\(n\)​\(rj\|rq\)=colr\(n\)​\(rs\|rq\)butINIT~1​\(rj\|eu,rq\)≠INIT~1​\(rs\|eu,rq\)for all​n≥0\.\\displaystyle\\mathrm\{col\}\_\{r\}^\{\(n\)\}\(r\_\{j\}\|r\_\{q\}\)=\\mathrm\{col\}\_\{r\}^\{\(n\)\}\(r\_\{s\}\|r\_\{q\}\)\\qquad\\text\{but\}\\qquad\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)\\neq\\widetilde\{\\mathrm\{INIT\}\}\_\{1\}\(r\_\{s\}\|e\_\{u\},r\_\{q\}\)\\qquad\\text\{for all \}n\\geq 0\.
We then construct a new KG𝒢⋆\\mathcal\{G\}^\{\\star\}with fresh entities\{a,b,c,d,x,y\}\\\{a,b,c,d,x,y\\\}and triplets\{<x,rj,b\>,<y,rs,d\>\}\\\{<x,r\_\{j\},b\>,<y,r\_\{s\},d\>\\\}, and no other edges incident tobbordd\.

Consider two query triplets

<a,rq,b\>and<c,rq,d\>,\\displaystyle<a,r\_\{q\},b\>\\qquad\\text\{and\}\\qquad<c,r\_\{q\},d\>,for the original SIL model, the incoming relation colors attached tobbandddare the same becauserjr\_\{j\}andrsr\_\{s\}are indistinguishable by the first\-stage WL test\. Moreover, the local entity neighborhoods ofbbandddare isomorphic because each target node has exactly one incoming edge from a fresh non\-source node\. Based on the above conditions, we can obtain

cole\(ℓ\)​\(b\|a,rq\)=cole\(ℓ\)​\(d\|c,rq\)for all​ℓ≥0\.\\displaystyle\\mathrm\{col\}\_\{e\}^\{\(\\ell\)\}\(b\|a,r\_\{q\}\)=\\mathrm\{col\}\_\{e\}^\{\(\\ell\)\}\(d\|c,r\_\{q\}\)\\qquad\\text\{for all \}\\ell\\geq 0\.
For RCMP, we already havecol~r\(0\)​\(rj\|eu,rq\)≠col~r\(0\)​\(rs\|eu,rq\)\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(0\)\}\(r\_\{j\}\|e\_\{u\},r\_\{q\}\)\\neq\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(0\)\}\(r\_\{s\}\|e\_\{u\},r\_\{q\}\)\. Therefore, after a first\-stage update, the message multiset received bybbcontains

\(col~e\(0\)​\(x\|a,rq\),col~r\(N\)​\(rj\|a,rq\)\),\\displaystyle\\bigl\(\\widetilde\{\\mathrm\{col\}\}^\{\(0\)\}\_\{e\}\(x\|a,r\_\{q\}\),\\widetilde\{\\mathrm\{col\}\}^\{\(N\)\}\_\{r\}\(r\_\{j\}\|a,r\_\{q\}\)\\bigr\),whereas the one received byddcontains

\(col~e\(0\)​\(y\|c,rq\),col~r\(N\)​\(rs\|c,rq\)\)\.\\displaystyle\\bigl\(\\widetilde\{\\mathrm\{col\}\}^\{\(0\)\}\_\{e\}\(y\|c,r\_\{q\}\),\\widetilde\{\\mathrm\{col\}\}^\{\(N\)\}\_\{r\}\(r\_\{s\}\|c,r\_\{q\}\)\\bigr\)\.Based oncol~e\(0\)​\(ev\|eu,rq\)=𝕀⁡\(ev=eu\)⋅col~r\(N\)​\(rq\|eu,rq\)\\widetilde\{\\mathrm\{col\}\}\_\{e\}^\{\(0\)\}\(e\_\{v\}\|e\_\{u\},r\_\{q\}\)=\\mathbb\{I\}\(e\_\{v\}=e\_\{u\}\)\\cdot\\widetilde\{\\mathrm\{col\}\}\_\{r\}^\{\(N\)\}\(r\_\{q\}\|e\_\{u\},r\_\{q\}\), the first components are equal, but the second components are different, so the multisets in the second\-stage test are different\. Finally, we can obtain

col~e\(ℓ\)​\(b\|a,rq\)≠col~e\(ℓ\)​\(d\|c,rq\)for all​ℓ≥0\.\\displaystyle\\widetilde\{\\mathrm\{col\}\}\_\{e\}^\{\(\\ell\)\}\(b\|a,r\_\{q\}\)\\neq\\widetilde\{\\mathrm\{col\}\}\_\{e\}^\{\(\\ell\)\}\(d\|c,r\_\{q\}\)\\qquad\\text\{for all \}\\ell\\geq 0\.Again using the constructive direction ofAssumption[B](https://arxiv.org/html/2608.17443#Thmassumption2)4, there exists an instance where RCMP can separate but SIL cannot\. This proves the strict refinement\. ∎

Discussion\.The proposition identifies a novel perspective of expressiveness beyond changing the motif setℛ∗\\mathcal\{R\}^\{\*\}itself\. The original theory strengthens SIL by enriching the relational hypergraph through richer motifs\. Our construction keepsℛ∗\\mathcal\{R\}^\{\*\}fixed and instead strengthens the base coloring of the first\-stage relation process by injecting a structure\-only autoregressive rule signal\. Therefore, the gain comes from refining the initial partition of relations rather than from adding new motifs\. Moreover, the structure\-only prompting design is crucial\. The invariance statement depends on the equivariance of the generator with respect to isomorphisms, which would generally fail if one injected relation names, entity names, or arbitrary textual attributes into the prompt\.

Algorithm 1Pre\-training framework of SIRLMInput:KG𝒢=\(ℰ,ℛ,𝒯\)\\mathcal\{G\}=\(\\mathcal\{E\},\\mathcal\{R\},\\mathcal\{T\}\); relational graph𝒢r=\(ℛ,ℛ∗,𝒯∗\)\\mathcal\{G\}\_\{r\}=\(\\mathcal\{R\},\\mathcal\{R\}^\{\*\},\\mathcal\{T\}^\{\*\}\); trainable parameter set of SIRLMΩ\\Omega; learning rateη\\eta; max training stepss; batch sizebb\. Output:Optimized parameter setΩ\\Omega\.

1:

s​t​e​p=0step=0
2:for

s​t​e​p<sstep<sdo

3:Randomly select

bbquery triplets from

𝒯\\mathcal\{T\}to form

𝒯q\\mathcal\{T\}\_\{q\}
4:

ℒt​o​t​a​l=0\\mathcal\{L\}\_\{total\}=0
5:for

<eh,rq,?\><e\_\{h\},r\_\{q\},?\>in

𝒯q\\mathcal\{T\}\_\{q\}do

6:Construct the query instruction

XXof

<eh,rq,?\><e\_\{h\},r\_\{q\},?\>according to Appendix[A](https://arxiv.org/html/2608.17443#A1)

7:Obtain structural embeddings

𝑹\|q\\bm\{R\}\_\{\|q\}and

𝑬\|h\\bm\{E\}\_\{\|h\}according to Eqs \([1](https://arxiv.org/html/2608.17443#S3.E1)\) and \([2](https://arxiv.org/html/2608.17443#S3.E2)\), respectively

8:Obtain the tokenizer

TKNRG\\text\{TKN\}\_\{\\text\{RG\}\}according to Eq\. \([6](https://arxiv.org/html/2608.17443#S4.E6)\)

9:Obtain structural relation memory

𝑹mem\\bm\{R\}\_\{\\text\{mem\}\}by Eq\. \([7](https://arxiv.org/html/2608.17443#S4.E7)\)

10:Convert

XXinto token sequence using

TKNRG\\text\{TKN\}\_\{\\text\{RG\}\}and conduct in\-context learning with

11:

𝑹mem\\bm\{R\}\_\{\\text\{mem\}\}according to Eq\. \([8](https://arxiv.org/html/2608.17443#S4.E8)\)

12:Generate the rule body

ρ=⋀z=1εrz\\rho=\\bigwedge\_\{z=1\}^\{\\varepsilon\}r\_\{z\}with the hidden states

\{𝒉L\+z\}z=1ε\{\\\{\\bm\{h\}\_\{L\+z\}\\\}\}\_\{z=1\}^\{\\varepsilon\}using Eq\. \([10](https://arxiv.org/html/2608.17443#S4.E10)\)

13:Reason the missing entity in the query triplet according to Eqs\. \([11](https://arxiv.org/html/2608.17443#S4.E11)\)\-\([13](https://arxiv.org/html/2608.17443#S4.E13)\)

14:Calculate the loss

ℒSFT\\mathcal\{L\}\_\{\\text\{SFT\}\}using Eq\. \([14](https://arxiv.org/html/2608.17443#S4.E14)\)

15:

ℒt​o​t​a​l←ℒt​o​t​a​l\+ℒSFT\\mathcal\{L\}\_\{total\}\\leftarrow\\mathcal\{L\}\_\{total\}\+\\mathcal\{L\}\_\{\\text\{SFT\}\}
16:end for

17:Optimize trainable parameters according to

Ω←Ω−η∇\(ℒt​o​t​a​l\)\\Omega\\leftarrow\\Omega\-\\eta\\nabla\(\\mathcal\{L\}\_\{total\}\)
18:

s​t​e​p←s​t​e​p\+1step\\leftarrow step\+1
19:end for

20:return

Ω\\Omega

## Appendix FTraining Algorithm

Algorithm[1](https://arxiv.org/html/2608.17443#alg1)provides a complete training process forSIRLMPT\\text\{SIRLM\}\_\{\\text\{PT\}\}\. In each training iteration, we first convert a query triplet into a instruction form consisting of textual and structural tokens \(Step 6\)\. Next, we obtain the structural representaions of entities and relations to construct a tokenizer for the query instruciton \(Steps 7 and 8\)\. We then obtain the structural relation memory and conduct in\-context learning for the query instruciton \(Steps 9 and 10\), which provides the hidden states for rule generation \(Step 11\) and reasoning \(Step 12\)\. Finally, we using the reasoning loss to update the model parameters \(Step 16\) and return a pre\-trained parameter set for downstream KGR tasks\.

## Appendix GComputational Complexity

Table 4:Comparison of KRLM and SIRLM in terms of TFLOPs, memory footprint, and wall\-clock time under pre\-training and fine\-tuning settings\.MetricPre\-training\(3 transductive datasets\)Fine\-tuning\(FB15k237 v1\)Fine\-tuning\(FB15k237\-25\)KRLMSIRLMPT\\text\{SIRLM\}\_\{\\text\{PT\}\}KRLMSIRLMSFT\\text\{SIRLM\}\_\{\\text\{SFT\}\}KRLMSIRLMSFT\\text\{SIRLM\}\_\{\\text\{SFT\}\}Avg\. TFLOPs\(forward propagation 100 steps\)3\.3436±\\pm0\.45402\.0397±\\pm0\.38413\.2755±\\pm0\.52082\.0683±\\pm0\.01753\.3312±\\pm0\.48592\.2287±\\pm0\.0000Training memory36\.12 GB / GPU27\.58 GB / GPU32\.57 GB / GPU11\.38 GB / GPU32\.67 GB / GPU13\.12 GB / GPUWall\-clock time3h10m / epoch2h38m / epoch7m28s / epoch3m39s / epoch12m13s / epoch10m45s / epochThe computational complexity of SIRLM consists of three parts\. For the construction of the relational graph𝒢∗\\mathcal\{G\}^\{\*\}, since we need to dynamically construct it based on negative sampling during the training process, the time complexity of this part needs to be considered\([Huang et al\. 2025a](https://arxiv.org/html/2608.17443#bib.bib15)\)\. To construct motif edges in𝒢∗\\mathcal\{G\}^\{\*\}, we first need to compress𝑨∈ℝ\|ℰ\|×\|ℛ\|×\|ℰ\|\\bm\{A\}\\in\\mathbb\{R\}^\{\|\\mathcal\{E\}\|\\times\|\\mathcal\{R\}\|\\times\|\\mathcal\{E\}\|\}into two sparse matrices𝑨h∈ℝ\|ℰ\|×\|ℛ\|\\bm\{A\}\_\{h\}\\in\\mathbb\{R\}^\{\|\\mathcal\{E\}\|\\times\|\\mathcal\{R\}\|\}and𝑨t∈ℝ\|ℛ\|×\|ℰ\|\\bm\{A\}\_\{t\}\\in\\mathbb\{R\}^\{\|\\mathcal\{R\}\|\\times\|\\mathcal\{E\}\|\}, with a complexity of𝒪⁡\(\|ℰ\|2​\|ℛ\|\)\\mathcal\{O\}\(\|\\mathcal\{E\}\|^\{2\}\|\\mathcal\{R\}\|\)\. Next, the construction process of the four types of binary edges theoretically requires a complexity of𝒪⁡\(\|ℰ\|​\|ℛ\|2\)\\mathcal\{O\}\(\|\\mathcal\{E\}\|\|\\mathcal\{R\}\|^\{2\}\)\. In practical situations, we use the sparse operatorspmm​\(⋅\)\\text\{spmm\}\(\\cdot\)to reduce the complexity of constructing binary edges to𝒪⁡\(nnz​\(𝑿\|𝑿∈\{𝑨h,𝑨t\}\)×nnz​\(𝒀\|𝒀∈\{𝑨hT,𝑨tT\}\)\)\\mathcal\{O\}\(\\text\{nnz\}\(\\bm\{X\}\|\\bm\{X\}\\in\\\{\\bm\{A\}\_\{h\},\\bm\{A\}\_\{t\}\\\}\)\\times\\text\{nnz\}\(\\bm\{Y\}\|\\bm\{Y\}\\in\\\{\\bm\{A\}\_\{h\}^\{\\text\{T\}\},\\bm\{A\}\_\{t\}^\{\\text\{T\}\}\\\}\)\), wherennz​\(⋅\)\\text\{nnz\}\(\\cdot\)is a operator finding the number of non\-zero element in𝑿\\bm\{X\}and𝒀\\bm\{Y\}\. Similarly, the theoretical complexity and actual sparse computational complexity of constructing ternary edges are𝒪⁡\(\|ℰ\|2​\|ℛ\|2\+\|ℰ\|​\|ℛ\|3\)\\mathcal\{O\}\(\|\\mathcal\{E\}\|^\{2\}\|\\mathcal\{R\}\|^\{2\}\+\|\\mathcal\{E\}\|\|\\mathcal\{R\}\|^\{3\}\)and𝒪⁡\(nnz​\(𝑿\|𝑿∈\{𝑨h,𝑨t\}\)×nnz​\(𝑨\)×nnz​\(𝒀\|𝒀∈\{𝑨hT,𝑨tT\}\)\)\\mathcal\{O\}\(\\text\{nnz\}\(\\bm\{X\}\|\\bm\{X\}\\in\\\{\\bm\{A\}\_\{h\},\\bm\{A\}\_\{t\}\\\}\)\\times\\text\{nnz\}\(\\bm\{A\}\)\\times\\text\{nnz\}\(\\bm\{Y\}\|\\bm\{Y\}\\in\\\{\\bm\{A\}\_\{h\}^\{\\text\{T\}\},\\bm\{A\}\_\{t\}^\{\\text\{T\}\}\\\}\)\), respectively

From the perspective of the KG tokenizer and RCMP reasoner, the time complexity is upper\-bounded by the NBFNet executed on𝒢\\mathcal\{G\}, as\|ℛ\|≪\|ℰ\|\|\\mathcal\{R\}\|\\ll\|\\mathcal\{E\}\|\. For each layer on NBFNet, the reasoning time complexity is calculated as𝒪⁡\(\|𝒯\|​d\+\|ℰ\|​d2\)\\mathcal\{O\}\(\|\\mathcal\{T\}\|d\+\|\\mathcal\{E\}\|d^\{2\}\), whereddis the embedding dimension\. Therefore, for aNN\-layer NBFNet executed on𝒢\\mathcal\{G\}, its overall time complexity is𝒪⁡\(N⁡\(\|𝒯\|​d\+\|ℰ\|​d2\)\)\\mathcal\{O\}\(N\(\|\\mathcal\{T\}\|d\+\|\\mathcal\{E\}\|d^\{2\}\)\)\. Furthermore, by using the efficient relational messaging kernel in the Pytorch\-geometric library, the complexity of the NBFNet is optimized to𝒪⁡\(N​\|ℰ\|​d\)\\mathcal\{O\}\(N\|\\mathcal\{E\}\|d\)\([Galkin et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib9)\)\.

The complexity of the in\-contex learning module with the sturctural relation memory can be divided into the self\-attention matrix calculation \(𝒪⁡\(L2​F\)\\mathcal\{O\}\(L^\{2\}F\)\), the memory key\-value calculation \(𝒪⁡\(L​K​d\)\\mathcal\{O\}\(LKd\)\), and the final aggregation \(𝒪⁡\(L⁡\(L\+K\)​F\)\\mathcal\{O\}\(L\(L\+K\)F\)\), whereFFis the hidden dimensions of LLM\. BecauseL≫KL\\gg K, the complexity upper bound of the in\-contex learning module can be represented as𝒪⁡\(L⁡\(L\+K\)​F\)\\mathcal\{O\}\(L\(L\+K\)F\)\.

We further provide Table[4](https://arxiv.org/html/2608.17443#A7.T4), which shows the TFLOPs in forward propagation, memory footprint, and wall\-clock time ofSIRLMPT\\text\{SIRLM\}\_\{\\text\{PT\}\}andSIRLMSFT\\text\{SIRLM\}\_\{\\text\{SFT\}\}under the condition of batch\_size = 4 per GPU × 4 GPUs\. For the SFT paradigm, we include results on the largest inductive dataset \(FB15k237\-25\) and the smallest inductive dataset \(FB15k237 v1\) to provide a boundary of the computational cost\.

## Appendix HDatasets

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\.TypeDatasetTraining graphValidation GraphTesting GraphEntitiesRelationsTripletsEntitiesRelationsTriplets\#ValidEntitiesRelationsTriplets\#TestTransductiveFB15k237\([Toutanova & Chen 2015](https://arxiv.org/html/2608.17443#bib.bib35)\)1454123727211514541237272115175351454123727211520466CoDEx\-M\([Safavi & Koutra 2020](https://arxiv.org/html/2608.17443#bib.bib32)\)1705051185584170505118558410310170505118558410311WN18RR\([Dettmers et al\. 2018](https://arxiv.org/html/2608.17443#bib.bib7)\)40943118683540943118683530344094311868353134NELL995\([Xiong et al\. 2017](https://arxiv.org/html/2608.17443#bib.bib42)\)7453620014967874536200149678543745362001496782818IndEFB15k237 v1\([Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34)\)159418042451594180424548910931801993411FB15k237 v2\([Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34)\)2608200973926082009739116616602004145947FB15k237 v3\([Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34)\)3668215179863668215179862194250121574061731FB15k237 v4\([Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34)\)47072192720347072192720333523051219117142840WN18RR v1\([Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34)\)27469541027469541063092291618373WN18RR v2\([Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34)\)695410152626954101526218382757104011852WN18RR v3\([Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34)\)120781125901120781125901309750841163271143WN18RR v4\([Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34)\)38619794038619794093470849123342823NELL995 v1\([Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34)\)3103144687310314468741422514833201NELL995 v2\([Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34)\)256488821925648882199222086884586935NELL995 v3\([Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34)\)4647142163934647142163931851356614280481620NELL995 v4\([Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34)\)2092767546209276754687627957670731447FullIndFB15k237\-25\([Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)51901639157140972161714757164097216171475716FB15k237\-50\([Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)51901538537544452051163638794445205116363879FB15k237\-75\([Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)465913462809279218693163106279218693163106FB15k237\-100\([Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)4659134628092624776987232926247769872329NELL995\-25\([Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)4396106175782146120223074321461202230744NELL995\-50\([Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)4396106175782335119257685923351192576859NELL995\-75\([Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)260796110581578116181860615781161818607NELL995\-100\([Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)125855783217095323787931709532378793Wikidata68K\-25\([Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)1265947418733228743391113032287433911131Wikidata68K\-50\([Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)1202272824819328939672322493289396723225Wikidata68K\-75\([Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)685352287412722653430114327226534301144Wikidata68K\-100\([Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)9784674987512136371348744961213637134874496MTDEA1\-tax\([Zhou et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib48)\)1000010171781000010171781908100009165261834MTDEA1\-health\([Zhou et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib48)\)10000714371100007143711596100007141101566MTDEA2\-org\([Zhou et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib48)\)10000102323310000102323325811000011219762441MTDEA2\-sci\([Zhou et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib48)\)10000161647110000161647118301000016148521650MTDEA3\-art\([Zhou et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib48)\)10000452726210000452726230261000045280233113MTDEA3\-infra\([Zhou et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib48)\)10000242199010000242199024431000027216462405MTDEA4\-sci\([Zhou et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib48)\)10000421257610000421257613971000042125161388MTDEA4\-health\([Zhou et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib48)\)10000211553910000211553917251000020153371703In our experiments, we conduct evaluations on 36 datasets\. According to the overlap level between train KG𝒢t​r​a​i​n=\(ℰt​r​a​i​n,ℛt​r​a​i​n,𝒯t​r​a​i​n\)\\mathcal\{G\}\_\{train\}=\(\\mathcal\{E\}\_\{train\},\\mathcal\{R\}\_\{train\},\\mathcal\{T\}\_\{train\}\)and test KG𝒢t​e​s​t=\(ℰt​e​s​t,ℛt​e​s​t,𝒯t​e​s​t\)\\mathcal\{G\}\_\{test\}=\(\\mathcal\{E\}\_\{test\},\\mathcal\{R\}\_\{test\},\\mathcal\{T\}\_\{test\}\), these datasets can be divided into the following three categories:

1. ∙\\bulletTransductivedatasets thatℰt​e​s​t=ℰt​r​a​i​n\\mathcal\{E\}\_\{test\}=\\mathcal\{E\}\_\{train\}andℛt​e​s​t=ℛt​r​a​i​n\\mathcal\{R\}\_\{test\}=\\mathcal\{R\}\_\{train\}: FB15k\-237\([Toutanova & Chen 2015](https://arxiv.org/html/2608.17443#bib.bib35)\), WN18RR\([Dettmers et al\. 2018](https://arxiv.org/html/2608.17443#bib.bib7)\), CoDEx\-M\([Safavi & Koutra 2020](https://arxiv.org/html/2608.17443#bib.bib32)\), and NELL995\([Xiong et al\. 2017](https://arxiv.org/html/2608.17443#bib.bib42)\)\.
2. ∙\\bulletInductiveEntity \(IndE\) datasets thatℰt​e​s​t≠ℰt​r​a​i​n\\mathcal\{E\}\_\{test\}\\neq\\mathcal\{E\}\_\{train\}andℛt​e​s​t=ℛt​r​a​i​n\\mathcal\{R\}\_\{test\}=\\mathcal\{R\}\_\{train\}, including 12 datasets from GraIL\([Teru et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib34)\)\(FB15k237 V1, FB15k237 V2, FB15k237 V3, FB15k237 V4, WN18RR V1, WN18RR V2, WN18RR V3, WN18RR V4, NELL995 V1, NELL995 V2, NELL995 V3, and NELL995 V4\)\.
3. ∙\\bulletFullyInductive \(FullInd\) datasets thatℰt​e​s​t≠ℰt​r​a​i​n\\mathcal\{E\}\_\{test\}\\neq\\mathcal\{E\}\_\{train\}andℛt​e​s​t≠ℛt​r​a​i​n\\mathcal\{R\}\_\{test\}\\neq\\mathcal\{R\}\_\{train\}, including 20 datasets from InGram\([Lee et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib22)\)\(FB15k237\-25, FB15k237\-50, FB15k237\-75, FB15k237\-100, NELL995\-25, NELL995\-50, NELL995\-75, NELL995\-100, Wikidata68K\-25, Wikidata68K\-50, Wikidata68K\-75, and Wikidata68K\-100\) and MTDEA\([Zhou et al\. 2023](https://arxiv.org/html/2608.17443#bib.bib48)\)\(MTDEA1\-tax, MTDEA1\-health, MTDEA2\-org, MTDEA2\-sci, MTDEA3\-art, MTDEA3\-infra, MTDEA4\-sci, and MTDEA4\-health\)\.

These dataset are used to evaluate the model in the four training paradigms mentioned in Section[5\.1](https://arxiv.org/html/2608.17443#S5.SS1)\. Table[5](https://arxiv.org/html/2608.17443#A8.T5)provides detailed elemental statistics for these datasets\.

Figure 7:The length distribution of rules mined from various datasets\.Next, we discuss the rule mining approach in the data preprocessing stage\. For each complete triplet in the training KG, we extract all closed paths within three hops\. Due to the sparsity of the KG, some triplets may not have any closed paths of limited length that can be extracted\. Figure[7](https://arxiv.org/html/2608.17443#A8.F7)presents the proportion of triplets without rules \(No rule\) and the distribution of rules at different lengths across datasets\. It can be observed that datasets such as WN18RR and the MTDEA1, MTDEA2, and MTDEA4 series exhibit a relatively high proportion of rule\-less triplets\. This is one of the reasons that the performance gains of SIRLM on these datasets, as shown in Tables[1](https://arxiv.org/html/2608.17443#S5.T1),[8](https://arxiv.org/html/2608.17443#A10.T8), and[9](https://arxiv.org/html/2608.17443#A10.T9), are generally lower than on other datasets,i\.e\., the difficulty in obtaining comprehensive rule\-based contextual information from the KG\.

After extracting the closed paths, we handle triplets without any rules by directly using the query relation of the triplet as the rule body\. For the remaining triplets that contain at least one closed path, we further construct candidate rule bodies by sequentially aggregating the directed relation sequences along each closed path\. We then count the occurrence frequency of all candidate rule bodies for each triplet and select the most frequent one as the rule to be generated for that triplet,i\.e\., the masked component of the query instruction described inAppendix[A](https://arxiv.org/html/2608.17443#A1)\.

## Appendix IExperimental Hyperparameter Settings

Table 6:Hyperperameters of KRLM used in pre\-training and end\-to\-end training from scratch\.ModuleComponentParameterKG TokenizerNBFNet on𝒢r\\mathcal\{G\}\_\{r\}Layer numberN=6N=6Hidden dimd=64d=64Message functionMsg​\(⋅\)=\\textsc\{Msg\}\(\\cdot\)=DistMultAggregation functionAgg​\(⋅\)=\\textsc\{Agg\}\(\\cdot\)=SumUpdating functionUp​\(⋅\)=nn\.Linear​\(128,64\)\\textsc\{Up\}\(\\cdot\)=\\text\{nn\.Linear\}\(128,64\)Motif Edge embeddings𝑹∗=nn\.Embedding​\(8,64\)\\bm\{R\}^\{\*\}=\\text\{nn\.Embedding\}\(8,64\)NBFNet on𝒢\\mathcal\{G\}Layer numberN=6N=6Hidden dimd=64d=64Message functionMsg​\(⋅\)=\\textsc\{Msg\}\(\\cdot\)=DistMultAggregation functionAgg​\(⋅\)=\\textsc\{Agg\}\(\\cdot\)=SumUpdating functionUp​\(⋅\)=nn\.Linear​\(128,64\)\\textsc\{Up\}\(\\cdot\)=\\text\{nn\.Linear\}\(128,64\)Up\-scale layerfup​\(⋅\)f\_\{\\text\{up\}\}\(\\cdot\)nn\.Linear​\(64,1536\)\\text\{nn\.Linear\}\(64,1536\)
Score function𝒮KG​\(⋅\)\\mathcal\{S\}\_\{\\text\{KG\}\}\(\\cdot\)nn\.Linear​\(128,64\)\\text\{nn\.Linear\}\(128,64\)nn\.ReLU​\(⋅\)\\text\{nn\.ReLU\}\(\\cdot\)nn\.Linear​\(64,1\)\\text\{nn\.Linear\}\(64,1\)In\-context Learning ModuleQwen2\.5\-1\.5b backboneLoRA configurationr=64r=64α=32\\alpha=32droupout=0\.1\\text\{droupout\}=0\.1target module=\[gate\_proj, up\_proj, down\_proj\]\\text\{target module\}=\\text\{\[gate\\\_proj, up\\\_proj, down\\\_proj\]\}Memory key layermK​\(⋅\)m\_\{K\}\(\\cdot\)nn\.Linear​\(64,1536\)\\text\{nn\.Linear\}\(64,1536\)Memory value layermV​\(⋅\)m\_\{V\}\(\\cdot\)nn\.Linear​\(64,1536\)\\text\{nn\.Linear\}\(64,1536\)Scale of structural relation memoryK=30K=30Next\-relation PredictorPorject layerf𝚯​\(⋅\)f\_\{\\bm\{\\Theta\}\}\(\\cdot\)nn\.Linear​\(1600,1600\)\\text\{nn\.Linear\}\(1600,1600\)nn\.ReLU​\(⋅\)\\text\{nn\.ReLU\}\(\\cdot\)nn\.Linear​\(1600,1\)\\text\{nn\.Linear\}\(1600,1\)RCMP ReasonerNBFNet on𝒢r\\mathcal\{G\}\_\{r\}Layer numberN=6N=6Hidden dimd=64d=64Message functionMsg​\(⋅\)=\\textsc\{Msg\}\(\\cdot\)=DistMultAggregation functionAgg​\(⋅\)=\\textsc\{Agg\}\(\\cdot\)=SumUpdating functionUp​\(⋅\)=nn\.Linear​\(128,64\)\\textsc\{Up\}\(\\cdot\)=\\text\{nn\.Linear\}\(128,64\)Motif Edge embeddings𝑹^∗=nn\.Embedding​\(8,64\)\\hat\{\\bm\{R\}\}^\{\*\}=\\text\{nn\.Embedding\}\(8,64\)NBFNet on𝒢\\mathcal\{G\}Layer numberN=6N=6Hidden dimd=64d=64Message functionMsg​\(⋅\)=\\textsc\{Msg\}\(\\cdot\)=DistMultAggregation functionAgg​\(⋅\)=\\textsc\{Agg\}\(\\cdot\)=SumUpdating functionUp​\(⋅\)=nn\.Linear​\(128,64\)\\textsc\{Up\}\(\\cdot\)=\\text\{nn\.Linear\}\(128,64\)Down\-scale layerfdown​\(⋅\)f\_\{\\text\{down\}\}\(\\cdot\)nn\.Linear​\(1536,64\)\\text\{nn\.Linear\}\(1536,64\)
Score function𝒮RCMP​\(⋅\)\\mathcal\{S\}\_\{\\text\{RCMP\}\}\(\\cdot\)nn\.Linear​\(128,64\)\\text\{nn\.Linear\}\(128,64\)nn\.ReLU​\(⋅\)\\text\{nn\.ReLU\}\(\\cdot\)nn\.Linear​\(64,1\)\\text\{nn\.Linear\}\(64,1\)TrainingOptimizerAdamWNumber of negative samples512Table 7:Detailed Training parameters, wherebb,η\\eta, andMMrepresent batch size, learning rate, and GRPO sampling number, respectively\. “all” means that each epoch needs to iterate through all training queries\.DatasetsSIRLME2E\\text\{SIRLM\}\_\{\\text\{E2E\}\}\(bb,η\\eta, epoch, step\)SIRLMSFT\\text\{SIRLM\}\_\{\\text\{SFT\}\}\(bb,η\\eta, epoch, step\)SIRLMGRPO\\text\{SIRLM\}\_\{\\text\{GRPO\}\}\(bb,η\\eta,MM, 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\)FB15k237 v3\(24, 1e\-4, 10, all\)\(24, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)FB15k237 v4\(24, 1e\-4, 5, all\)\(24, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)WN18RR v1\(48, 1e\-4, 10, all\)\(48, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)WN18RR v2\(48, 1e\-4, 10, all\)\(48, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)WN18RR v3\(48, 1e\-4, 20, all\)\(48, 5e\-5, 5, all\)\(16, 1e\-5, 8, 3, all\)WN18RR v4\(48, 1e\-4, 10, all\)\(48, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)NELL995 v1\(32, 1e\-4, 5, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)NELL995 v2\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)NELL995 v3\(32, 1e\-4, 5, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)NELL995 v4\(32, 1e\-4, 5, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)FB15k237\-25\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(8, 1e\-5, 8, 3, all\)FB15k237\-50\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(8, 1e\-5, 8, 3, all\)FB15k237\-75\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(8, 1e\-5, 8, 3, all\)FB15k237\-100\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(8, 1e\-5, 8, 3, all\)NELL995\-25\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(8, 1e\-5, 8, 3, all\)NELL995\-50\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(8, 1e\-5, 8, 3, all\)NELL995\-75\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(8, 1e\-5, 8, 3, all\)NELL995\-100\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(8, 1e\-5, 8, 3, all\)Wikidata68K\-25\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)Wikidata68K\-50\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)Wikidata68K\-75\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)Wikidata68K\-100\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)MTDEA1\-tax\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)MTDEA1\-health\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)MTDEA2\-org\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)MTDEA2\-sci\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)MTDEA3\-art\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)MTDEA3\-infra\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)MTDEA4\-sci\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)MTDEA4\-health\(32, 1e\-4, 10, all\)\(32, 5e\-5, 3, all\)\(16, 1e\-5, 8, 3, all\)In Section[5\.2](https://arxiv.org/html/2608.17443#S5.SS2), we report four training paradigms of SIRLM, including End\-to\-End \(E2E\) training from scratch, Pre\-Training \(PT\), SFT, and GRPO post\-training\. The hyperparameters of the model architecture under the four paradigms are uniformly set to the values in Table[6](https://arxiv.org/html/2608.17443#A9.T6)\. In the PT paradigm, we set the learning rate to 1e\-4 and use the AdamW optimizer with a 1% warm\-up step\. The batch size per GPU is 12\. Each epoch consists of 5000 iterations and the training process is conducted for a total of 20 epochs\. More detailed training hyperparameters for the other training paradigms are provided in Table[7](https://arxiv.org/html/2608.17443#A9.T7)\.

## Appendix JDetails Experimental Analysis

### J\.1Additional Analysis of Main Experiments

Table 8:The overall performance of various methods on IndE datasets\. The colored cells represent thebest,second\-best, andthird\-bestvalues, respectively\.MethodsFB15k237 v1FB15k237 v2FB15k237 v3FB15k237 v4MRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowNeuralLP0\.3250\.4680\.3890\.5860\.4000\.5710\.3960\.593DRUM0\.3330\.4740\.3950\.5950\.4020\.5710\.4100\.593NBFNet0\.4220\.5740\.5140\.6850\.4760\.6370\.4530\.627RED\-GNN0\.3690\.4830\.4690\.6290\.4450\.6030\.4420\.621ULTRA0\.5090\.6700\.5240\.7100\.5040\.6630\.4960\.684MOTIF0\.5300\.7020\.5570\.7440\.5190\.6840\.5080\.695ChatRule†\\dagger0\.4480\.5460\.4840\.6280\.4710\.6530\.4570\.598MKGL†\\dagger0\.4750\.5950\.5080\.6810\.4860\.6430\.4710\.645KRLM†\\dagger0\.5110\.6680\.5270\.7120\.5200\.6810\.5050\.693SIRLME2E\\text\{SIRLM\}\_\{\\text\{E2E\}\}0\.5480\.7100\.5570\.7440\.5270\.7050\.5120\.708SIRLMPT\\text\{SIRLM\}\_\{\\text\{PT\}\}0\.5520\.7180\.5430\.7410\.5100\.7020\.4970\.705SIRLMSFT\\text\{SIRLM\}\_\{\\text\{SFT\}\}0\.5580\.7180\.5550\.7470\.5290\.7080\.5100\.702SIRLMGRPO\\text\{SIRLM\}\_\{\\text\{GRPO\}\}0\.5610\.7210\.5590\.7520\.5320\.7110\.5150\.714Avg\. gain⋆\\star\+12\.50%\+14\.50%\+7\.38%\+8\.87%\+6\.28%\+7\.70%\+5\.52%\+7\.52%MethodsWN18RR v1WN18RR v2WN18RR v3WN18RR v4MRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowNeuralLP0\.6490\.7720\.6350\.7490\.3610\.4760\.6280\.706DRUM0\.6660\.7770\.6460\.7470\.3800\.4770\.6270\.702NBFNet0\.7410\.8260\.7040\.7980\.4320\.5680\.6410\.694RED\-GNN0\.7010\.7990\.6900\.7800\.4270\.5240\.6510\.721ULTRA0\.6850\.7930\.6790\.7790\.4110\.5460\.6140\.720MOTIF0\.7030\.8060\.6800\.7810\.4660\.5900\.6590\.733ChatRule†\\dagger0\.6210\.6940\.6500\.6860\.3950\.4970\.5680\.649MKGL†\\dagger0\.7460\.8220\.7120\.7990\.4560\.5590\.6640\.741KRLM†\\dagger0\.7050\.7970\.6900\.7910\.4570\.5900\.6620\.737SIRLME2E\\text\{SIRLM\}\_\{\\text\{E2E\}\}0\.7050\.7660\.6990\.7890\.4560\.5620\.6580\.732SIRLMPT\\text\{SIRLM\}\_\{\\text\{PT\}\}0\.6680\.7440\.6700\.7660\.4330\.5490\.6270\.693SIRLMSFT\\text\{SIRLM\}\_\{\\text\{SFT\}\}0\.7060\.7780\.7140\.7990\.4590\.5680\.6620\.745SIRLMGRPO\\text\{SIRLM\}\_\{\\text\{GRPO\}\}0\.6950\.7620\.7080\.7910\.4540\.5660\.6620\.741Avg\. gain⋆\\star\+0\.38%\+0\.21%\+3\.78%\+3\.12%\+3\.84%\+3\.17%\+2\.71%\+3\.36%MethodsNELL995 v1NELL995 v2NELL995 v3NELL995 v4MRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowNeuralLP0\.6100\.8710\.3610\.5640\.3670\.5760\.2610\.539DRUM0\.6280\.8730\.3650\.5400\.3750\.5770\.2700\.531NBFNet0\.6480\.8620\.4210\.5990\.4620\.5780\.4040\.588RED\-GNN0\.6370\.8660\.4190\.6010\.4360\.5940\.3630\.556ULTRA0\.7570\.8780\.5750\.7610\.5630\.7550\.4690\.733MOTIF0\.7120\.8730\.5660\.7650\.5800\.7640\.5070\.740ChatRule†\\dagger0\.7190\.8060\.5290\.6900\.5520\.7320\.5280\.741MKGL†\\dagger0\.7490\.8860\.5700\.7670\.5710\.7590\.5250\.749KRLM†\\dagger0\.6790\.8980\.5680\.7610\.5610\.7550\.5540\.762SIRLME2E\\text\{SIRLM\}\_\{\\text\{E2E\}\}0\.6800\.8710\.5800\.7690\.5850\.7690\.5470\.767SIRLMPT\\text\{SIRLM\}\_\{\\text\{PT\}\}0\.7620\.9080\.5790\.7870\.5830\.7750\.5390\.764SIRLMSFT\\text\{SIRLM\}\_\{\\text\{SFT\}\}0\.7680\.8790\.5820\.7890\.5880\.7790\.5520\.771SIRLMGRPO\\text\{SIRLM\}\_\{\\text\{GRPO\}\}0\.7420\.8800\.5720\.7680\.5760\.7570\.5430\.769Avg\. gain⋆\\star\+8\.59%\+3\.99%\+9\.60%\+11\.70%\+9\.17%\+10\.23%\+12\.08%\+11\.11%
- †\\dagger†\\daggerWe reproduce the experimental metrics of ChatRule, MKGL, and KRLM\.
- ⋆\\star⋆\\starWe calculate the average gain of the optimal value in the four training modes of SIRLM compared to all baselines\.

Table 9:The overall performance of various methods on FullInd datasets\. The colored cells represent thebest,second\-best, andthird\-bestvalues, respectively\.MethodsFB15k237\-25FB15k237\-50FB15k237\-75FB15k237\-100MRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowNBFNet0\.2240\.4100\.1300\.2590\.0890\.1660\.0720\.154RED\-GNN0\.1450\.2840\.1290\.2510\.1070\.2010\.1210\.263ULTRA0\.3830\.6350\.3340\.5380\.4000\.5980\.4440\.643MOTIF0\.3880\.6350\.3400\.5440\.3990\.6070\.4390\.642ChatRule†\\dagger0\.3360\.6020\.2890\.5140\.2500\.5070\.3610\.554KRLM†\\dagger0\.3980\.6400\.3450\.5520\.4140\.6200\.4550\.655SIRLME2E\\text\{SIRLM\}\_\{\\text\{E2E\}\}0\.3860\.6350\.3450\.5400\.4110\.6230\.4440\.646SIRLMPT\\text\{SIRLM\}\_\{\\text\{PT\}\}0\.3760\.6310\.3150\.5340\.3960\.6130\.4420\.655SIRLMSFT\\text\{SIRLM\}\_\{\\text\{SFT\}\}0\.3880\.6470\.3450\.5410\.4000\.6100\.4480\.648SIRLMGRPO\\text\{SIRLM\}\_\{\\text\{GRPO\}\}0\.3960\.6490\.3470\.5460\.4200\.6260\.4490\.656Avg\. gain⋆\\star\+8\.37%\+11\.47%\+8\.58%\+10\.30%\+14\.35%\+17\.62%\+13\.37%\+17\.08%MethodsNELL995\-25NELL995\-50NELL995\-75NELL995\-100MRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowNBFNet0\.2830\.4170\.2250\.3460\.1370\.2550\.0960\.199RED\-GNN0\.2140\.2660\.1790\.1150\.2030\.3530\.2120\.385ULTRA0\.4070\.5960\.4180\.5950\.3740\.5700\.4580\.684MOTIF0\.3900\.5800\.4140\.5730\.3600\.5480\.4640\.682ChatRule†\\dagger0\.3590\.5640\.3680\.5400\.3020\.5210\.4440\.608KRLM†\\dagger0\.4010\.5960\.4320\.5980\.3670\.5590\.4890\.688SIRLME2E\\text\{SIRLM\}\_\{\\text\{E2E\}\}0\.4070\.6010\.4130\.5950\.3710\.5700\.4770\.666SIRLMPT\\text\{SIRLM\}\_\{\\text\{PT\}\}0\.3940\.5930\.3940\.5810\.3550\.5500\.4720\.668SIRLMSFT\\text\{SIRLM\}\_\{\\text\{SFT\}\}0\.4120\.6130\.4180\.5980\.3790\.5780\.4890\.667SIRLMGRPO\\text\{SIRLM\}\_\{\\text\{GRPO\}\}0\.4100\.6070\.3820\.5670\.3680\.5600\.4770\.668Avg\. gain⋆\\star\+6\.97%\+10\.98%\+7\.87%\+13\.68%\+8\.85%\+11\.03%\+12\.85%\+12\.70%MethodsWikidata68K\-25Wikidata68K\-50Wikidata68K\-75Wikidata68K\-100MRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowNBFNet0\.1540\.3010\.0620\.1050\.0720\.1720\.0140\.026RED\-GNN0\.1700\.2630\.0580\.0930\.1720\.2900\.0960\.136ULTRA0\.3210\.5350\.1400\.2800\.3800\.5300\.1680\.286MOTIF0\.3170\.5050\.1600\.3040\.3710\.5350\.1730\.284ChatRule†\\dagger0\.2560\.3720\.0900\.1260\.2660\.4830\.1070\.196KRLM†\\dagger0\.3320\.5500\.1680\.3280\.3840\.5380\.1890\.313SIRLME2E\\text\{SIRLM\}\_\{\\text\{E2E\}\}0\.3220\.5360\.1730\.3290\.4060\.5680\.1860\.304SIRLMPT\\text\{SIRLM\}\_\{\\text\{PT\}\}0\.3030\.4970\.1660\.3090\.3990\.5560\.1890\.300SIRLMSFT\\text\{SIRLM\}\_\{\\text\{SFT\}\}0\.3280\.5410\.1710\.3300\.4120\.5660\.1910\.316SIRLMGRPO\\text\{SIRLM\}\_\{\\text\{GRPO\}\}0\.3140\.5110\.1700\.3150\.3850\.5500\.1850\.307Avg\. gain⋆\\star\+6\.97%\+12\.00%\+5\.80%\+12\.40%\+13\.78%\+14\.33%\+6\.65%\+10\.92%MethodsMTDEA1\-taxMTDEA1\-healthMTDEA2\-orgMTDEA2\-sciMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowNBFNet0\.1130\.3150\.1220\.3390\.1090\.2920\.0910\.235ULTRA0\.3300\.4590\.3800\.4670\.1040\.1700\.3110\.451MOTIF0\.4160\.5220\.3850\.4730\.1060\.1700\.3260\.520ChatRule†\\dagger0\.3000\.3880\.3520\.4270\.1010\.1400\.3430\.468KRLM†\\dagger0\.3780\.5080\.3760\.4570\.0980\.1400\.3610\.526SIRLME2E\\text\{SIRLM\}\_\{\\text\{E2E\}\}0\.3990\.5280\.3900\.4750\.1010\.1420\.3850\.530SIRLMPT\\text\{SIRLM\}\_\{\\text\{PT\}\}0\.3950\.5230\.3830\.4700\.0830\.1360\.3900\.532SIRLMSFT\\text\{SIRLM\}\_\{\\text\{SFT\}\}0\.4070\.5330\.4040\.4810\.1090\.1450\.4100\.548SIRLMGRPO\\text\{SIRLM\}\_\{\\text\{GRPO\}\}0\.4010\.5300\.3840\.4730\.0970\.1400\.3990\.538Avg\. gain⋆\\star\+9\.96%\+9\.46%\+8\.10%\+4\.84%\+0\.54%\-3\.74%\+12\.36%\+10\.80%MethodsMTDEA3\-artMTDEA3\-infraMTDEA4\-sciMTDEA4\-healthMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowMRR↑\\uparrowHit10↑\\uparrowNBFNet0\.0990\.2570\.1370\.3570\.0940\.2460\.1240\.328ULTRA0\.3060\.4730\.6570\.8070\.3030\.4780\.7040\.785MOTIF0\.3150\.4690\.6830\.8270\.3090\.4830\.7030\.787ChatRule†\\dagger0\.2670\.4320\.6590\.8110\.2680\.4490\.6580\.740KRLM†\\dagger0\.3150\.4680\.6700\.8110\.3030\.4710\.6950\.776SIRLME2E\\text\{SIRLM\}\_\{\\text\{E2E\}\}0\.3280\.4990\.6860\.8340\.3110\.4890\.7100\.789SIRLMPT\\text\{SIRLM\}\_\{\\text\{PT\}\}0\.3240\.4920\.6770\.8270\.3170\.4970\.7070\.787SIRLMSFT\\text\{SIRLM\}\_\{\\text\{SFT\}\}0\.3280\.4930\.6880\.8390\.3300\.5260\.7010\.787SIRLMGRPO\\text\{SIRLM\}\_\{\\text\{GRPO\}\}0\.3330\.5100\.6760\.8300\.3210\.5140\.7060\.789Avg\. gain⋆\\star\+7\.26%\+9\.02%\+12\.68%\+11\.64%\+7\.46%\+10\.06%\+13\.32%\+10\.58%
- †\\dagger†\\daggerWe reproduce the experimental metrics of ChatRule and KRLM\.
- ⋆\\star⋆\\starWe calculate the average gain of the optimal value in the four training modes of SIRLM compared to all baselines\.

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 thebest,second\-best, andthird\-bestvalues, respectively\.MethodsFB15k237CodeX\-MWN18RRNELL99512 IndE Datasets20 FullInd DatasetsMRRHit10MRRHit10MRRHit10MRRHit10MRRHit10MRRHit10Full Model0\.4080\.5930\.3670\.5220\.4610\.5560\.5200\.6380\.5800\.7380\.3740\.538w/oMMQI0\.3890\.5790\.3600\.4990\.4580\.5250\.5140\.6270\.5700\.7210\.3640\.522w/oSRM0\.3580\.5660\.3480\.4780\.4550\.5260\.4880\.6060\.5580\.7090\.3480\.508w/oRCMP0\.3520\.5380\.3390\.4220\.4040\.5000\.5010\.6110\.5400\.6850\.3440\.502Tables[8](https://arxiv.org/html/2608.17443#A10.T8)and[9](https://arxiv.org/html/2608.17443#A10.T9)correspond to the detailed experimental results of each method in Table[1](https://arxiv.org/html/2608.17443#S5.T1)on the IndE and FullInd datasets, respectively\.

Traditional embedding\-based methods rely on initializing fixed representations of entities and relations tailored to a specific KGR scenario\.

Figure 8:The correlation trend between KG sparsity and the MRR gain of SIRLM\.As a result, they cannot accommodate unseen entities and relations in the inference KG, making them unsuitable for inductive KGR tasks\. Rule\-based approaches, while capable of handling predictions involving unseen entities under a fixed set of relation types, fail to effectively generalize rule bodies when relations are dynamic, which prevents their application to FullInd KGR settings\. In contrast, GNN\-based methods are applicable across all KGR scenarios considered in our experiments\. This advantage stems from their ability to learn structural context, enabling more structural pattern induction over the entire KG and allowing them to identify unfamiliar entities and relations through representations grounded in structural invariance\.

LLM\-based methods leverage pre\-trained knowledge and strong contextual reasoning capabilities to uncover latent facts in incomplete KGs and to recognize unseen entities and relations\. For instance, ChatRule utilizes the natural language understanding ability of LLMs to filter candidate textualized KG rules and select those that best support reasoning over a query triplet, while MKGL and KRLM project explicit KG structures into the implicit parametric knowledge of LLMs and ultimately generate potential facts through next\-entity prediction\. However, these approaches lack faithfulness constraints on the implicit reasoning process of LLMs, making them susceptible to biases arising from misalignment between structural knowledge and parametric representations, which can lead to erroneous inference outcomes\.

In contrast, our SIRLM enforces the generation of structurally grounded rules over the KG, mitigating the tendency of LLMs to overlook the underlying structural evidence in favor of pre\-trained knowledge when generating answers\. Furthermore, we observe a correlation between the performance gains of SIRLM and the sparsity of the KG\. Based on the results in Tables[8](https://arxiv.org/html/2608.17443#A10.T8)and[9](https://arxiv.org/html/2608.17443#A10.T9), Figure[8](https://arxiv.org/html/2608.17443#A10.F8)illustrates this trend\. Notably, SIRLM performs slightly worse on sparse KGs \(e\.g\., the WN18RR series dataset\) than on dense ones, which highlights an inherent limitation of structural rule\-based reasoning under sparse conditions and points to an important direction for future research\.

### J\.2Details Ablation Analysis

Section[5\.3](https://arxiv.org/html/2608.17443#S5.SS3)analyzes the ablation components of SIRLM\. To verify the universality of each component, we chose to perform ablation variants inSIRLMPT\\text\{SIRLM\}\_\{\\text\{PT\}\}training mode\. We first provide the design details of each ablation variant\.

1. ∙\\bullet\-MMQI\. This variant only provides the textual instructions of query triplets, without including structural representations of entities and relations\. Following MKGL\([Guo et al\. 2024](https://arxiv.org/html/2608.17443#bib.bib11)\), such instruction sequences contain textual strings of entities/relations along with their corresponding textual explanations\. During tokenization, we use the principal neighborhood aggregation method\([Corso et al\. 2020](https://arxiv.org/html/2608.17443#bib.bib4)\)to aggregate the text token sequences of entity/relation into word\-level token embeddings, which are then used for subsequent rule generation and reasoning\. Since the instructions do not include structural representations, the tokenizer in Eq\. \([6](https://arxiv.org/html/2608.17443#S4.E6)\) degenerates intoTKNLLM\\text\{TKN\}\_\{\\text\{LLM\}\}\. The rest of the SIRLM architecture remains unchanged\.
2. ∙\\bullet\-SRM\. This variant removes the structural relation memory in the in\-context learning module, along with its corresponding linear layers \(mK​\(⋅\)m\_\{K\}\(\\cdot\)andmV​\(⋅\)m\_\{V\}\(\\cdot\)\) in Eq\. \([8](https://arxiv.org/html/2608.17443#S4.E8)\)\. All other components remain consistent with the primary SIRLM\.
3. ∙\\bullet\-RCMP\. This variant removes\{<rz,fdown​\(𝒉L\+z\)\>\}z=1ε\{\\\{<r\_\{z\},f\_\{\\text\{down\}\}\(\\bm\{h\}\_\{L\+z\}\)\>\\\}\}\_\{z=1\}^\{\\varepsilon\}in Eq\. \([11](https://arxiv.org/html/2608.17443#S4.E11)\), reverting it back to the original SIL module\.

Table[10](https://arxiv.org/html/2608.17443#A10.T10)provides the details ablation experimental results of each ablation variant\.

### J\.3Additional Analysis on Different LLM Backbones

Section[5\.5](https://arxiv.org/html/2608.17443#S5.SS5)presents the experimental results of SIRLM across four different LLM backbones\. Overall, the results show a positive correlation between the parameter scale of the backbone and its reasoning performance\. We attribute this to the fact that larger parameter sizes enable the model to more quickly fit the newly injected structured representation space\.

To further illustrate this, Figure[9](https://arxiv.org/html/2608.17443#A10.F9)reports the convergence of rule generation accuracy for the four LLM backbones on WN18RR v1\. It is evident that the two 7B backbones \(Qwen2\.5\-7b and Llama2\-7b\) approach convergence at around 200 steps, whereas Qwen2\.5\-0\.5b and Qwen2\.5\-1\.5b backbones require approximately 400 steps to reach a similar level of convergence\.

Figure 9:Convergence of rule generation accuracy for SIRLM with different LLMs on WN18RR v1\.
### J\.4Case Study and Error Analysis

![Refer to caption](https://arxiv.org/html/2608.17443v1/case_study.png)Figure 10:Case studies of rule generation\.Red,blue, andorangedenote the query relation, the atomic relations in the ground\-truth rule, and the atomic relations in the predicted rule, respectively\.Greendenotes the target entities that need to be predicted\.To better understand the behavior of our SIRLM, we visualize several representative cases of rule generation in Figure[10](https://arxiv.org/html/2608.17443#A10.F10)\.Cases 1 and 2is a successful example where the generated rule exactly matches the ground\-truth rule, indicating that the model can accurately identify the correct multi\-hop reasoning pattern\. As a result, the correct entities “Best Academy Picture Award” and “University of Texas at Austin” appears in the top\-ranked candidates with a relatively high confidence score\.

Cases 3 and 4demonstrates that an exact match to the ground\-truth rule is not necessary for correct prediction\. Although the generated rule deviates from the annotated reasoning path, it still leads to the correct answers “Tokyo” and “Columbia Records”\. This suggests that the model can exploit alternative reasoning paths with similar structural semantics\. In these case, the generated atomic relations \(blue square\) differ from the ground\-truth atomic relations \(orange triangle\), but remain semantically similar in the representation space\.

In contrast,Cases 5 and 6reveals a limitation of the method\. The generated rule introduces irrelevant atomic relations that differ substantially from the ground truth, causing the reasoning process to deviate from the correct semantic direction and resulting in incorrect top\-ranked candidates\.

These observations indicate that the effectiveness of SIRLM critically depends on the quality of the generated rule body, that is, semantically accurate rules improve both interpretability and predictive performance, whereas semantically inconsistent rules can significantly degrade performance\.

## Appendix KLimitations and Future Work

SIRLM provides a novel modeling and training framework for LLM\-based KGR research, effectively alleviating the problem of reasoning evidence perception drift caused by the knowledge representation gap between LLMs and KGs\. However, SIRLM still has several potential limitations\. We discuss these limitations as follows and provide potential future research directions\.

Computational complexity\.As shown inAppendix[G](https://arxiv.org/html/2608.17443#A7), SIRLM needs to make real\-time relational graph updates and message passing over the entire KG during training\. Although sparse operators are adopted in practice to significantly reduce the computational cost of graph processing, the upper bound remains quadratic in the number of entities, which leads to a notable computational bottleneck for large\-scale KGs\. Therefore, in future work, we plan to introduce a query\-driven evidence graph extraction mechanism\([Huang et al\. 2026](https://arxiv.org/html/2608.17443#bib.bib13)\), such that the graph structure processed by SIRLM is closely aligned with the query triplets\. This would help eliminate the unnecessary computational overhead incurred by processing irrelevant KG context\.

Sparse KG reasoning\.The comprehensive analysis of Figures 7 and 8, as well as Tables 8 and 9, shows that there is still significant room for improvement in the reasoning performance of SIRLM on sparse KGs\. We consider that this limitation is attributed to the fact that SIRLM is a rule\-driven KGR framework\. In sparse KGs, the diversity and completeness of structural rules are inherently limited, which in turn hinders the subsequent processes of rule learning and generation by LLMs\. To address this issue, we plan to incorporate a soft rule mechanism\([Qu et al\. 2021](https://arxiv.org/html/2608.17443#bib.bib30)\)into the rule mining stage\. Specifically, instead of relying solely on hard inductive methods based on observable closed\-path patterns, we will jointly employ soft rule mining to construct approximate rules and corresponding soft labels for query triplets that lack closed\-path evidence\. These soft signals can serve as additional supervision for subsequent LLM\-based rule generation\. In this way, the contextual exploration space of LLMs over sparse KGs can be effectively expanded, thereby alleviating the limitations in rule learning caused by insufficient structural context\.