1 Related Work↩︎

1.1 Logical Rule Learning↩︎

Logical rule learning is one of the main paradigms for KG reasoning, alongside embedding-based and path-based methods [1]. Compared with embedding-based and path-based methods, rule-based reasoning provides higher interpretability by deriving conclusions through explicit logical formulas. Rule-based reasoning applies predefined logical axioms and inference rules to derive new factual knowledge from existing KGs. Owing to this interpretability, substantial research has focused on developing methods for efficiently discovering high-quality logical rules from KGs.

Logical rule learning has evolved through three methodological stages. Early approaches primarily relied on inductive logic programming and association rule mining. Foundational systems such as FOIL [2] and AMIE [3] generate Horn clauses by generalizing from specific instances, while other approaches are tailored to large graphs [4]. Subsequent research explored path-based methods, including AnyBURL [5], which sample and evaluate relational paths from KGs to construct logical rules. While these methods offer interpretability, their dependence on observed instances limits their ability to generalize to semantically valid rules that occur infrequently in the data.

Neural-symbolic integration paradigms were introduced to address the inefficiencies of discrete search. Early work in this direction, such as Neural Theorem Provers (NTPs) [6], introduced differentiable reasoning mechanisms. To reduce the computational demands of these approaches, subsequent research introduced optimizations including adaptive path selection [7] and dynamic rule subsetting [8]. Despite these improvements, scalability challenges continued to hinder practical deployment. Consequently, recent research has shifted toward neural-logic frameworks that reformulate rule learning as a continuous optimization problem. Neural-LP [9] introduced an attention-based controller for sequential rule construction, while hybrid architectures such as RNNLogic [10] jointly learn a rule generator and a reasoning predictor for the iterative refinement of rule embeddings. NCRL [11] employs a compositional learning strategy, combining rule components through neural representation learning to improve expressiveness.

Despite these advances, existing rule learning methods still focus mainly on chain-like structures, thereby overlooking graph-like structures that can model complex relational patterns in KGs. Moreover, generating graph-like rules is computationally challenging due to the exponential growth of the rule space. To bridge this gap, we leverage diffusion models to generate graph-like rules that capture complex relational patterns for KG reasoning.

1.2 Diffusion Models↩︎

Diffusion models have demonstrated generative capabilities across a range of domains [12]. They have also been applied to graph-structured data generation, including molecular design, where they model complex constrained output spaces [13]–[15]. This ability to model structured patterns under combinatorial constraints makes diffusion models suitable for KG reasoning tasks, which involve discovering valid relational paths within structured graphs.

Recent applications of diffusion models to KG reasoning can be grouped into two trajectories. The first strand operates at the instance level, reformulating KG reasoning as a conditional generation task in which denoising processes progressively recover target entities or facts [16]–[19]. While this paradigm learns the distribution of valid facts and achieves competitive performance, it remains confined to instance-level prediction and does not explicitly capture schema-level logical patterns in KGs. The second trajectory applies diffusion processes in continuous latent spaces to learn fact distributions and model relational uncertainty [20]. This line of work improves representational flexibility and can model complex relational patterns. However, because these methods focus on refining entity representations rather than discovering schema structures, they provide limited interpretability.

While both paradigms demonstrate the adaptability of diffusion models to KG reasoning, neither directly generates explicit rules beyond the instance level, and therefore neither explicitly captures schema-level logical patterns. However, directly applying diffusion models to rule generation is challenging because standard reconstruction losses are not aligned with discrete rule-quality metrics. To address this issue, we employ RL to optimize the diffusion model using rule-quality metrics as reward signals, enabling the diffusion process to be applied to graph-like rule generation.

2 Preliminaries↩︎

This section formalizes the key concepts used in this work. We begin by reviewing the basic structure of KGs and logical rules. We then introduce the concept of graph-like rules. Finally, we present four quantitative metrics for evaluating rule quality.

Definition 1 (Knowledge Graph, KG). A KG \(\mathcal{G}\) is formally defined as a relation-labeled directed graph \(\mathcal{G}=(\mathcal{E}, \mathcal{R}, \mathcal{F})\), where \(\mathcal{E}\) denotes the entity set, \(\mathcal{R}\) denotes the relation set, and \(\mathcal{F}\) denotes the fact set. Specifically, \(\mathcal{F} = \{(e_h,r,e_t)|e_h,e_t \in \mathcal{E}, r\in \mathcal{R}\}\) is the set of factual triples.

Definition 2 (Logical Rule). A logical rule \(\rho\) represents a logical implication between a head predicate and a body composed of conjunctive predicates. It has the following general form: \[\rho: \rho_h \leftarrow \rho_b\] where \(\rho_h\) denotes the rule head, typically formulated as a single atom such as \(r_h(e_i, e_j)\), and \(\rho_b\) denotes the rule body, which is formed by a conjunction of atoms. Semantically, the rule asserts that if the body \(\rho_b\) is true, then the head \(\rho_h\) is also true.

Definition 3 (Graph-like Rule). A graph-like rule is a logical rule whose body \(\rho_b\) forms a directed graph. As illustrated in Fig. 1, we categorize such rules into four basic types based on the connectivity pattern of the rule body: linear rule (Fig. 1 (a)), which represent sequential dependencies; branching structure (Fig. 1 (b)), which capture conjunctive paths; node-cycling structures (Fig. 1 (c)), which model node-centric cycles; and edge-cycling structures (Fig. 1 (d)), which represent relation-centric cycles. These basic structures can be combined to form more complex hybrid rule patterns.

Definition 5 (Support). The support of a logical rule \(\rho\), denoted as \(Supp_{\rho}^{\mathcal{G}}\), is the number of distinct entity pairs \((e_i, e_j)\) in \(\mathcal{G}\) for which both \(\rho_b\) and \(\rho_h\) hold. \[Supp_{\rho}^{\mathcal{G}} := \#\{(e_i, e_j) \in \mathcal{G} : \mathbb{I}_{\rho_b}(e_i, e_j) \land \rho_h(e_i, e_j)\} \label{equ95support}\tag{1}\]

Definition 6 (Coverage). The coverage of a rule \(\rho\) quantifies its prevalence among facts of the head relation. It is defined as the proportion of entity pairs connected by \(\rho_h\) that also satisfy \(\rho_b\). \[Cov_{\rho}^{\mathcal{G}} := \frac{Supp_{\rho}^{\mathcal{G}}}{\#\{(e_i, e_j) \in \mathcal{G} : \rho_h(e_i, e_j)\}} \label{equ95cover}\tag{2}\]

Definition 7 (Confidence). The confidence of a rule \(\rho\) measures the proportion of body groundings that also support the rule head. It is defined as follows: \[Conf_{\rho}^{\mathcal{G}} := \frac{Supp_{\rho}^{\mathcal{G}}}{\#\{(e_i, e_j) \in \mathcal{G} : \mathbb{I}_{\rho_b}(e_i, e_j)\}} \label{equ95conf}\tag{3}\]

Definition 8 (PCA Confidence). PCA Confidence quantifies the precision of a rule \(\rho\) under the Partial Completeness Assumption (PCA) [3]. It restricts the denominator to body groundings whose subject entity has at least one observed fact under the head relation, and is defined as follows: \[PCA\text{-}Conf_{\rho}^{\mathcal{G}} := \frac{Supp_{\rho}^{\mathcal{G}}}{\#\{{(e_i, e_j') \in \mathcal{G} : \mathbb{I}_{\rho_b}(e_i, e_j') \land \rho_h(e_i, e_j')\}}} \label{equ95pcaconf}\tag{4}\]

3 Methods↩︎

This section presents GRiD, a framework that formulates graph-like rule discovery as a conditional discrete diffusion process over rule-body adjacency matrices. By leveraging a diffusion model, GRiDlearns a distribution over KG rules conditioned on the target relation, thereby reducing dependence on explicit combinatorial search. GRiDoperates in two stages: it is first pre-trained via SL to capture structural priors from subgraphs sampled from KG meta-graph and then fine-tuned with RL to optimize non-differentiable rule-quality metrics. An overview of the pipeline is provided in Fig. 2. The following sections detail the discrete diffusion framework, the two-stage training process, and the inference pipeline.

3.1 Discrete Diffusion Framework↩︎

GRiD adopts a discrete diffusion paradigm to model the symbolic structure of graph-like rules. While continuous latent representations may introduce ambiguity when reconstructing such structures, operating in the discrete space preserves their structural constraints. Accordingly, GRiD reformulates rule discovery as a conditional discrete diffusion process. The following subsections detail this framework, beginning with the discrete state formulation and followed by formal descriptions of the forward and reverse diffusion processes.

3.1.1 Discrete State Formulation↩︎

The process is conditioned on the rule head \(\rho_h\), which provides the semantic target, while the rule body \(\rho_b\) is modeled as the adjacency matrix to be generated.

Discrete Matrix Representation. The rule body of graph-like rules is a directed graph, as defined in Def. [Def:32graph-like32rules], and can therefore be represented as a matrix. Formally, the rule body adjacency matrix \(\mathbf{A}\) is defined as: \[\mathbf{A} \in \{0, 1, \dots, |\mathcal{R}|, \emptyset\}^{S \times S}\] Here, \(S\) denotes the maximum number of allowed nodes and \(\mathcal{R}\) denotes the relation set of the KG. Each entry \(\mathbf{A}[i,j] \in \{0, 1, \dots, |\mathcal{R}|,\emptyset\}\) specifies the relation type from node \(i\) to node \(j\), with a value of \(0\) indicating no relation and \(\emptyset\) indicating padding. To accommodate variable-length rules, unused rows and columns are padded with a null token \(\emptyset\), enabling fixed-dimensional processing for batch training.

Conditional Formulation. Generation is conditioned by two factors: the target head relation \(r_h\) and the diffusion timestep \(t\). The relation \(r_h\) is embedded into a static vector \(\mathbf{r}_h \in \mathbb{R}^d\), while \(t\) is encoded via sinusoidal embeddings into a time-varying vector \(\mathbf{t} \in \mathbb{R}^d\). These embeddings are concatenated to form a unified conditioning vector \(\mathbf{c}_t\): \[\label{eq:condition95vec} \mathbf{c}_t = [\mathbf{t} \mathbin{;} \mathbf{r}_h] \in \mathbb{R}^{2d}\tag{5}\] The learning objective is to approximate the conditional distribution \(p_\theta(\mathbf{A} | \mathbf{c}_t)\), so that the generated rule body is conditioned on \(r_h\) while respecting structural constraints at each diffusion step.

3.1.2 Forward Diffusion Process.↩︎

The forward diffusion process progressively corrupts a clean rule-body adjacency matrix \(\mathbf{A_0}\) into noise over \(T\) timesteps. Following the D3PM framework [21], the forward process is specified by a sequence of categorical transition matrices \(\{\mathbf{Q}_t\}_{t=1}^T\). At each timestep \(t\), the diffusion process factorizes across all edge positions. Each entry of \(\mathbf{A}_t\) is represented as a \(K\)-dimensional one-hot categorical variable and evolves independently according to a categorical Markov transition: \[q(\mathbf{A}_t \mid \mathbf{A}_{t-1}) = \textit{Cat}(\mathbf{A}_t \mid \mathbf{A}_{t-1} \mathbf{Q}_t)\] Here, \(\textit{Cat}(\mathbf{A}_t \mid \mathbf{P})\) denotes a collection of independent categorical distributions over all edge entries, where each probability vector is given by the corresponding row of \(\mathbf{P}\), and \(Q_t \in \mathbb{R}^{K \times K}\) is a row-stochastic transition matrix over the \(K = |\mathcal{R}| + 1\) edge types, including the no edge category. In this work, we adopt a uniform corruption scheme defined as follows: \[\mathbf{Q}_t = (1 - \beta_t)\mathbf{I} + \beta_t \frac{\mathbf{1}\mathbf{1}^\top}{K}\] where \(\beta_t \in [0,1]\) represents the noise schedule. Here, \(\mathbf{1} \in \mathbb{R}^{K}\) denotes an all-ones column vector, and \(\mathbf{1}\mathbf{1}^\top \in \mathbb{R}^{K \times K}\) defines a uniform categorical transition. Under this construction, each edge is left unchanged with probability \(1-\beta_t\) and is resampled uniformly from all \(K\) edge types with probability \(\beta_t\). Using the Markov property, the marginal distribution at timestep \(t\) admits a closed form as follows: \[q(\mathbf{A}_t \mid \mathbf{A}_0)= \mathrm{Cat}\!\left(\mathbf{A}_t \;\middle|\; \mathbf{A}_0\mathbf{Q}^{(t)}\right), \quad \mathbf{Q}^{(t)} = \prod_{i=1}^{t} \mathbf{Q}_i,\] which converges to a uniform categorical distribution as \(t\) increases, thereby removing information about the original rule structure.

3.1.3 Reverse Diffusion Process.↩︎

This process iteratively denoises a noisy rule structure to reconstruct a clean rule-body adjacency matrix \(\mathbf{A}_0\) from an initial state \(\mathbf{A}_T\). The reverse transition \(p_\theta(\mathbf{A}_{t-1}|\mathbf{A}_t, \mathbf{c}_t)\) is parameterized by a Graph Transformer \(f_\theta\), which takes the noisy adjacency matrix \(\mathbf{A}_t\) and the conditioning vector \(\mathbf{c}_t\) (Eq. 5 ) as input and outputs categorical logits for all edge types.

To condition generation on the current noise level and target relation, \(\mathbf{c}_t\) is injected into each network layer via Feature-wise Linear Modulation (FiLM) [22]. For the \(l\)-th layer, the node representation \(\mathbf{H}^{(l)}\) is modulated as follows:

\[\mathbf{H}^{(l)} = \boldsymbol{\gamma}(\mathbf{c}_t) \odot \text{LayerNorm}(\mathbf{H}^{(l)}) + \boldsymbol{\beta}(\mathbf{c}_t)\] where \(\odot\) denotes element-wise multiplication, \(\boldsymbol{\gamma}(\cdot)\) and \(\boldsymbol{\beta}(\cdot)\) are learned affine projections of \(\mathbf{c}_t\). This modulation enables the message-passing dynamics to adapt to both the timestep \(t\) and the target relation \(r_h\).

Finally, the modulated representations are projected to produce a probability distribution over the \(K\) edge categories for each edge: \[p_\theta(\mathbf{A}_{t-1} \mid \mathbf{A}_t, \mathbf{c}_t) \propto \textit{Cat}\!\left(\mathbf{A}_{t-1} \;\middle|\; f_\theta(\mathbf{A}_t, \mathbf{c}_t) \right)\] By iteratively sampling from this distribution, GRiD generates a rule body conditioned on the target relation while preserving structural constraints.

3.2 Phase A: SL Pre-training↩︎

To obtain a structurally informed initialization, we pre-train GRiD to reconstruct subgraphs sampled from the KG meta-graph. The subgraph training set is constructed through random-walk sampling and topological augmentation on the KG, as detailed in Appendix 15.

Training Objective. The objective is to train the denoising network \(f_\theta\) to recover the clean adjacency matrix \(\mathbf{A}_0\) from a corrupted state. Specifically, given a noisy input \(\mathbf{A}_t\) and the conditioning vector \(\mathbf{c}_t\), we minimize a weighted cross-entropy loss between the predicted edge-type distribution and the clean adjacency matrix: \[\mathcal{L}_{recon} = - \frac{\sum_{i,j} M_{ij} \sum_{k=0}^{K-1}\mathbb{I}(\mathbf{A}_0[i,j] = k) \log p_\theta\left(\mathbf{A}_0[i,j] = k \mid \mathbf{A}_t, \mathbf{c}_t\right)}{\sum_{i,j} M_{ij}} \label{eq:ce95loss}\tag{6}\] Here, \(\mathbf{M} \in \{0,1\}^{S \times S}\) is a binary mask, where \(M_{ij}=0\) for padding positions and \(M_{ij}=1\) otherwise. This ensures that the optimization focuses only on valid structural entries.

In addition to the reconstruction loss, we use the diffusion model to predict a scalar score \(\hat{v}_{\rho_i}\) for each rule. The overall supervised pre-training objective is therefore defined as \[\mathcal{L}_{SL} = \mathcal{L}_{recon} + \lambda_{Q} \frac{1}{B} \sum_{i=1}^{B}\left(\hat{v}_{\rho_i} - v_{\rho_i}^*\right)^2\] where \(\lambda_Q=0.1\) is a fixed hyperparameter that balances structural reconstruction and semantic regularization. The target quality score \(v_{\rho_i}^*\) is defined as the min-max normalized sum of coverage and confidence (\(Cov_{\rho_i}^{\mathcal{G}} + Conf_{\rho_i}^{\mathcal{G}}\)) over the training set, thereby accounting for both rule recall and precision. This auxiliary objective aligns the learned representations with rule-quality signals and provides a warm start for subsequent RL fine-tuning.

Training Pipeline. Each supervised pre-training iteration corresponds to a single diffusion step conditioned on the target relation. Concretely, we first sample a batch of rule structures \(\{(\mathbf{A}^i_0, r_h)\}_{i=1}^B\) from the training set, where \(B\) denotes the batch size. A diffusion timestep \(t\) is then drawn uniformly from \(\{1,\dots,T\}\), and the corresponding noisy structure \(\mathbf{A}_t\) is obtained through the forward diffusion process. Conditioned on the vector \(\mathbf{c}_t\), GRiD predicts both the edge-type distributions and an auxiliary quality score for the corrupted structure. The supervised loss \(\mathcal{L}_{SL}\) is then computed and back-propagated to update the model parameters \(\theta\).

3.3 Phase B: RL Fine-tuning↩︎

While SL pre-training establishes the structural prior from KG subgraphs, it does not directly optimize rule-quality metrics such as coverage and confidence. Inspired by a recent study [23], the pre-trained model is fine-tuned using RL to address this mismatch, which frames the sequential denoising process as a policy optimization problem.

Policy and Reward Formulation. We formulate the denoising process as a Markov Decision Process, where the denoising Graph Transformer acts as a stochastic policy \(\pi_\theta(\mathbf{A}_{t-1} \mid \mathbf{A}_t, \mathbf{c}_t)\). The state corresponds to the noisy rule-body matrix \(\mathbf{A}_t\), and the action is the sampled denoised matrix \(\mathbf{A}_{t-1}\). Since intermediate noisy states lack direct rule-quality labels, the reward \(R(\rho)\) is assigned only upon generating the complete rule \(\rho\). To quantify rule quality, we define \(R(\rho)\) as the geometric mean of coverage (Eq. 2 ), confidence (Eq. 3 ), and PCA confidence (Eq. 4 ): \[R(\rho) = \left( Cov_{\rho}^{\mathcal{G}} \cdot Conf_{\rho}^{\mathcal{G}} \cdot PCA\text{-}Conf_{\rho}^{\mathcal{G}} \right)^{1/3} \label{equ:reward}\tag{7}\] This composite metric balances rule generality and predictive precision, providing a reward signal for optimization.

Policy Optimization. Since the intermediate states do not have direct rule-quality labels, we formulate the objective as maximizing the expected episode-level reward \(J(\theta) = \mathbb{E}_{\rho \sim \pi_\theta}[R(\rho)]\) using the REINFORCE algorithm. To reduce variance, we incorporate a baseline \(b\), updated by an exponential moving average, to compute the advantage \(\hat{A} = R(\rho) - b\). The optimization objective \(\mathcal{L}_{RL}\) combines the policy gradient with entropy regularization to discourage premature convergence to deterministic transitions and encourage exploration:

\[{!}{ \displaystyle \mathcal{L}_{RL}(\theta) = - \frac{1}{B} \sum_{i=1}^B \sum_{t=1}^T \left( \hat{A}_i \log \pi_\theta(\mathbf{A}_{t-1}^{(i)} \mid \mathbf{A}_t^{(i)}, \mathbf{c}_t^{(i)}) + \lambda_H \mathcal{H}(\pi_\theta(\cdot \mid \mathbf{A}_t^{(i)},\mathbf{c}_t^{(i)})) \right) }\] Here, \(\hat{A}_i\) acts as a trajectory-level weight for episode \(i\), reinforcing steps that lead to higher-quality rules, while the entropy term \(\mathcal{H}\) encourages exploration at each timestep.

3.4 Inference Pipeline↩︎

After training, the diffusion model is used as a conditional generator of graph-like rule bodies for a given target relation \(r_h\). Inference proceeds via iterative denoising followed by structural parsing and filtering. Specifically, we initialize the process from a noisy adjacency matrix \(\mathbf{A}_T\), where each entry is sampled from the \(K\) edge categories. For \(t = T, \dots, 1\), the model iteratively samples \[\mathbf{A}_{t-1} \sim p_\theta(\mathbf{A}_{t-1} \mid \mathbf{A}_t, \mathbf{c}_t),\] where the conditioning vector \(\mathbf{c}_t = [\mathbf{t} \mathbin{;} \mathbf{r}_h]\) encodes the timestep and target relation. This denoising process yields a discrete adjacency matrix \(\mathbf{A}_0\), which is then parsed into a graph-like rule body.

To form a rule, the node with zero in-degree is identified as the head variable \(e_h\). The node with zero out-degree that is topologically farthest from \(e_h\) is designated as the tail variable \(e_t\). The remaining edges compose the rule body that predicts \(r_h(e_h,e_t)\). Finally, KG structural constraints are applied to filter invalid structures, retaining valid graph-like rules for downstream reasoning.

4 Experiment↩︎

4.1 Experimental settings↩︎

Tasks. We evaluate the performance and efficiency of GRiD on KGC tasks. The objective is to predict a missing target entity \(e_t\) for a given query \((e_h, r_q, ?)\). KGC tasks assess the capability of GRiDto extract high-quality logical rules for KG reasoning. The full KGC pipeline is detailed in Appendix 10.

Datasets. Our evaluation spans six benchmark datasets representing diverse scales and domains: two large-scale KGs, YAGO3-10 [24] and FB15K-237 [25], alongside four domain-specific datasets: Family [26], Kinship [27], UMLS [27], and WN-18RR [28]. Detailed statistics are provided in Table 4 in Appendix 7.

Dataset Preparation. Each dataset is randomly split into training and test sets with a ratio of 9:1. To avoid information leakage, all test triples are strictly excluded from the training data.

Baselines. We compare GRiD against 16 representative baselines spanning three paradigms under identical experimental settings: five embedding approaches, including TransE [29], DistMult [30], ComplEx [31], RotatE [32], and SpeedE [33]; three GNN-based methods, including CompGCN [34], NBFNet [35], and A\(^{*}\)Net [36]; and eight rule-based systems, including AnyBURL [5], AMIE [3], Neural-LP [9], DRUM [37], RNNLogic [10], RLogic [38], NCRL [11], and ChatRule [39]. Detailed descriptions of these baselines are provided in Appendix 8.

Metrics. Following standard KGC evaluation protocols, we adopt filtered ranking, where triples \((e_h,r_q,e^\star)\) with \(e^\star \neq e_t\) are removed from the candidate set if they exist in the KG. We report Hit@1, Hit@10, and Mean Reciprocal Rank (MRR).

Rule Application. For each relation \(r\), both chain-like and graph-like rules are used to compute the final scoring matrix, \(\mathbf{S}_r = (1-\alpha),\mathbf{S}^{\mathrm{chain}}_r + \alpha,\mathbf{S}^{\mathrm{graph}}_r\), where the fusion weight is \(\alpha = 0.1\). The detailed scoring and aggregation procedure is described in Appendix 10.

4.2 Knowledge Graph Completion Results↩︎

Overall Results. As summarized in Table 1, GRiD achieves consistently strong KGC performance across six benchmarks. It outperforms most rule-based baselines in the majority of settings and remains competitive with representative embedding and GNN-based baselines, while producing explicit logical rules. On large-scale KGs such as FB15K-237 and YAGO3-10, several rule-based approaches encounter scalability limitations, whereas GRiD still achieves the best or second-best results.

Impact of KG Structure. We observe that graph-like rules are particularly beneficial on KGs where rich relational structure leads to ambiguous predictions under simple chain-based reasoning, such as FB15K-237 and YAGO3-10. In such settings, chain-like rules often yield ambiguous candidate rankings, while graph-like rules introduce additional conjunctive constraints that help disambiguate candidate entities. Conversely, on KGs with tightly constrained relational semantics (e.g., kinship or lexical hierarchies), chain‑like rules already capture most reliable patterns, leaving less room for improvement from graph‑like rules. A detailed quantitative analysis of KG structural properties and their relationship to performance is provided in Appendix 14.

Case Study. To further illustrate the differences between the learned logical rules, representative examples of chain-like and graph-like rules are presented in Table 5. Graph-like rules impose stricter conjunctive constraints by requiring the joint satisfaction of multiple relational conditions. For example, the rule \(\textit{isCitizenOf}(x,y) \leftarrow \textit{LivesIn}(x,y) \wedge \textit{WorksAt}(x,y)\) integrates two complementary relational signals through the shared variables \((x, y)\). In contrast, chain-like rules are characterized by a single linear relational dependency. The complementary effects of these rule types are quantitatively examined through ablation studies on rule type and further elaborated in Appendix 12.

4.3 Ablation Studies↩︎

We conduct ablation studies to assess several design choices of GRiD, focusing on four key questions: (Q1) Effectiveness of Graph-like Rules: Do graph-like rules provide complementary inferential evidence beyond chain-like rules? (Q2) Sensitivity to Fusion Weight: Under which fusion weights do graph-like rules provide the largest performance gains? (Q3) Necessity of RL: Is RL fine-tuning essential for rule discovery? (Q4) Size of Graph-like Rules: Is a small graph size sufficient for complex KGs?

(Q1) Effectiveness of Graph-like Rules. To address Q1, we investigate whether graph-like rules provide complementary inferential evidence beyond chain-like rules. We compare three configurations: Chain-only, Graph-only, and their Combination, while maintaining a constant total number of rules for a controlled comparison. As shown in Table 2, the combined configuration consistently outperforms either individual type, indicating that graph‑like rules capture relational patterns distinct from those encoded by chain‑like rules. Graph-like rules in isolation achieve lower KGC performance because their stricter constraints reduce coverage in sparse KGs, which is consistent with the sparsity of KG observations.

(Q2) Sensitivity to Fusion Weight. To address Q2, we investigate the fusion weights under which graph-like rules complement chain-like rules. While chain‑like rules capture the majority of effective patterns, adding a small proportion of graph‑like rules consistently improves the chain‑only baseline. As illustrated in Fig. 3, performance gains are observed when graph-like rules are assigned a constrained fusion weight, approximately \(0.1\)-\(0.2\). Conversely, assigning excessive weight to graph-like rules degrades performance because of their lower rule coverage. These findings indicate that graph-like rules are most effective when incorporated as a controlled complementary signal rather than as the dominant reasoning paradigm.

(Q3) Necessity of RL. To address Q3, we compare GRiD trained with only supervised pre-training against two RL-fine-tuned variants on YAGO3-10: one using a geometric-mean reward and the other using the sum of rule-quality metrics. As shown in Fig. 4, RL fine-tuning yields consistent improvements of approximately 10% across all metrics, indicating that direct optimization toward rule quality helps align generation with reasoning objectives. Moreover, the geometric-mean reward outperforms metric summation, suggesting that balanced multi-criteria optimization provides a more effective training signal in this setting.

(Q4) Size of Graph-like Rules. To address Q4, we conduct KGC experiments with different graph-size limits \(S\). As shown in Table 3, \(S=6\) consistently achieves the best MRR across all datasets. This result is consistent with the compositional nature of logical rules: longer rules often provide limited additional utility because they can be expressed by composing shorter rules. Moreover, rules operate at the schema level and are therefore not related to instance-level neighbor density. Consequently, a small \(S\) can improve efficiency while preserving sufficient expressiveness for the rule patterns considered in this work.

4.4 Efficiency Analysis↩︎

We assess the efficiency of GRiD from both theoretical and empirical perspectives. Theoretically, the computational complexity is dominated by the Graph Transformer in the denoising network and scales quadratically with the rule size \(S\). Since graph-like rule bodies are compact (typically \(S \le 6\)), this overhead remains limited in practice (see Appendix 11 for the detailed derivation).

Empirically, as reported in Table 6, GRiD requires limited training time and GPU memory. On YAGO3-10, SL pre-training and RL fine-tuning require 1.34 s and 18.76 s per epoch, respectively. Peak GPU memory consumption is 11.41 GB on FB15K-237 and 5.52 GB on YAGO3-10. Once rules are generated offline, inference proceeds via sparse-matrix operations, which support scalable rule application on large-scale KGs.

5 Conclusion↩︎

This paper introduces GRiD, a framework that reformulates rule discovery as a discrete diffusion process conditioned on the target relation. By shifting from iterative search to generative modeling, GRiD reduces the dependence on exhaustive search in the combinatorial rule space. By combining SL pre-training for structural priors with RL fine-tuning that directly optimizes rule quality metrics, GRiD generates graph-like rules for KG reasoning. Experiments show that the rules generated by GRiD support KGC across six benchmark datasets. Furthermore, ablation studies show the complementary effects of graph-like rules and chain-like rules. Future research will explore generating rules directly from underlying KG distributions to mitigate sampling bias and developing structural evaluation metrics that provide more precise guidance for the diffusion process.

6 Acknowledgements↩︎

This study was supported by the National Natural Science Foundation of China (NSFC, 72571284, 72421002), Hunan Provincial Fund for Distinguished Young Scholars (2025JJ20073), Science and Technology Innovation Program of Hunan Province (2023RC3009), Innovation Research Foundation of National University of Defense Technology (JS24-05), and the Major Science and Technology Projects in Changsha, China (kq2301008).

7 Dataset Description↩︎

• Family [26] captures relations among family members.

• Kinship [27] contains kinship relations among members of the Alyawarra tribe from Central Australia.

• UMLS [27] contains biomedical concepts as entities and treatment and diagnosis relations.

• WN-18RR [28] is a lexical dataset whose entities refer to word senses and whose relations define lexical connections.

• FB15K-237 [25] is derived from Freebase, an online collection of structured data extracted from multiple sources.

• YAGO3-10 [24] is a subset of YAGO, a large semantic knowledge base constructed from multiple sources.

8 Baseline Description↩︎

Embedding Baselines.

• TransE [29]. TransE models relations as translations between entity embeddings.

• DistMult [30]. DistMult uses diagonal bilinear scoring for entity-relation interactions.

• ComplEx [31]. ComplEx uses complex embeddings to capture symmetric and antisymmetric relations.

• RotatE [32]. RotatE models relations as rotations in complex space.

• SpeedE [33]. SpeedE is a lightweight Euclidean geometric KGE model for efficient KGC.

GNN-based Baselines.

• CompGCN [34]. CompGCN jointly embeds nodes and relations via compositional GCN aggregation.

• NBFNet [35]. NBFNet learns Bellman-Ford-style path representations for link prediction.

• A\(^{*}\)Net [36]. A\(^{*}\)Net extends NBFNet with A\(^{*}\)-like heuristic search to guide the reasoning process.

Rule-based Baselines.

• AnyBURL [5]. AnyBURL mines Horn rules via anytime bottom-up path sampling.

• AMIE [3]. AMIE mines Horn rules in large KBs under PCA for counterexamples.

• Neural-LP [40]. Neural-LP learns logical rules through differentiable tensor operations.

• DRUM [37]. DRUM extends Neural-LP with RNNs to model longer rule chains.

• RNNLogic [10]. RNNLogic uses an RNN-based generator to propose logical rules for KG reasoning.

• RLogic [38]. RLogic introduces recursive logical rule learning through predicate representation learning.

• NCRL [11]. NCRL is a neural compositional rule learning method that uses attention mechanisms for recursive reasoning.

• ChatRule [39]. ChatRule uses prompts to guide LLMs in generating logical rules with KG structural validation.

9 Rule Comparsion↩︎

Representative chain-like and graph-like rules generated by GRiD on YAGO3-10 are presented in Table 5. Here, we analyze graph-like rules according to the four rule-body types in Fig. 1.

Linear Rule Body (Fig 1 (a)). This type represents a sequential variable chain. The rule \((x, y) \leftarrow\) \((x, z_1) \wedge\) \((z_1, z_2) \wedge\) \((z_2, y)\) demonstrates this structure, where inference follows a single path from \(x\) to \(y\) through the workplace of the advisor and its location. This rule captures citizenship through the institutional affiliation of the advisor.

Branching Rule Body (Fig 1 (b)). This type contains a branching node connected to multiple nodes. The rule \((x, y) \leftarrow\) \((x, z_1) \wedge\) \((z_1, z_2) \wedge\) \((z_1, y)\) branches at node \(z_1\), which connects to both \(z_2\) and \(y\). This rule captures citizenship through familial and relational dependencies.

Node-Cyclic Rule Body (Fig 1 (c)). This type contains shared intermediate nodes that form cycles. The rule \((x, y) \leftarrow\) \((x, z_1) \wedge\) \((y, z_1) \wedge\) \((x, z_2) \wedge\) \((y, z_2)\) connects \(x\) and \(y\) through the shared capital \(z_1\) and language \(z_2\), reflecting how shared attributes can indicate hierarchical relationships.

Edge-Cyclic Rule Body (Fig 1 (d)). This type contains multiple edges between the same entity pair. The rule \((x, y) \leftarrow\) \((x, y) \wedge\) \((x, y)\) forms an edge cycle in which two relations connect \(x\) and \(y\), showing how multiple co-location signals support citizenship inference.

10 KGC Pipeline↩︎

This section summarizes how the generated rules are applied to the KGC task, with the full pipeline illustrated in Algorithm 5. For each relation \(r \in \mathcal{R}\), we construct a CSR sparse adjacency matrix \(\mathbf{M}_r \in \{0,1\}^{|\mathcal{E}|\times|\mathcal{E}|}\), where \(\mathbf{M}_r[i,j]=1\) if \((e_i,r,e_j)\in\mathcal{F}\). Let \(\mathbf{M}^{\mathrm{gt}}_r\) denote the ground-truth matrix used for rule-quality computation and filtered ranking. For each head relation \(r\), the generated rule set \(\Omega_r\) is partitioned into chain-like rules \(\Omega_r^{\mathrm{chain}}\) and graph-like rules \(\Omega_r^{\mathrm{graph}}\).

For a chain-like rule, the body reachability matrix is obtained by successive sparse matrix multiplication. For a graph-like rule, we decompose the rule body into chain components, ground each component independently, and apply element-wise conjunction to retain entity pairs that satisfy all structural constraints. The function \(\mathrm{Score}(\cdot)\) computes the scalar rule quality \(s(\rho)\) from coverage, confidence, and PCA-confidence, as defined in Eqs. 2 4 . After all rules for relation \(r\) are grounded and scored, their evidence is aggregated into \(\mathbf{S}^{\mathrm{chain}}_r\) and \(\mathbf{S}^{\mathrm{graph}}_r\), which are then combined using the fusion weight \(\alpha\). Given a query \((e_h,r,?)\), the row vector \(\mathbf{S}_r[e_h,:]\) provides scores for candidate tail entities. We follow the filtered ranking protocol by masking all known valid tail entities except the target entity \(e_t^\star\). The final performance is reported using Hit@K and MRR: \[\mathrm{Hit@K}=\frac{1}{|Q|}\sum_{q\in Q}\mathbb{I}(\mathrm{rank}_q\le K), \quad \mathrm{MRR}=\frac{1}{|Q|}\sum_{q\in Q}\frac{1}{\mathrm{rank}_q}.\]

11 Complexity and Cost Analysis↩︎

We analyze the computational complexity of the three phases of GRiD: SL pre-training, RL fine-tuning, and inference. Wall-clock time and peak memory usage across six benchmark datasets are reported in Table 6.

SL Pre-training. The cost of is dominated by the Graph Transformer, with a per-epoch complexity of \(O(|\mathcal{D}_{pre}| \cdot S^2)\). The single-step denoising objective avoids iterative sampling, and the quadratic term introduces limited overhead because rule bodies are compact (\(S \le 6\)). This bound follows the common practice of restricting chain-like rules to 4 nodes [5], [11] and adding 2 auxiliary nodes, since complex rules can generally be decomposed into smaller substructures. As reported in Table 6, the per-epoch time is 8.61 s on FB15K-237 and 1.34 s on the larger but sparser YAGO3-10.

RL Fine-tuning. This phase requires full generation to compute rewards, with a complexity of \(O(N_{RL} \cdot T \cdot S^2)\) for \(N_{RL}\) sampled rules and \(T\) diffusion steps. Generation is linear in \(T\), and the small rule size \(S\) keeps the computational graph compact, thereby limiting GPU memory consumption. As reported in Table 6, RL fine-tuning is the most time-consuming phase, requiring 18.76 s per epoch on YAGO3-10, while peak memory reaches 11.41 GB on FB15K-237 and 5.52 GB on YAGO3-10. These figures indicate that GRiD can be trained on consumer-grade GPUs.

Inference. Inference is performed offline and is decoupled from diffusion-model training. KGC inference uses symbolic rule application with sparse matrix operations. Applying a rule of length \(L\) requires sparse matrix multiplications, with practical complexity proportional to the number of nonzero entries in the involved relation matrices. Thus, rule application scales with sparse matrix operations and is independent of generation latency. Table 6 shows that the full training and inference pipeline is feasible across all datasets, ranging from under two minutes on WN-18RR to approximately two hours on YAGO3-10.

12 Sensitivity Analysis of Fusion Weight↩︎

This section evaluates the fusion parameter \(\alpha\), which controls the relative contribution of chain-like and graph-like rules in the integrated scoring function. Given fixed chain-like and graph-like rules, \(\alpha\) is varied at the scoring stage as follows: \[\mathbf{S} = (1-\alpha)\cdot \mathbf{S}_{r}^{\text{chain}} + \alpha \cdot \mathbf{S}_{r}^{\text{graph}}\] As shown in Fig. 6, \(\alpha=0\) denotes chain-only reasoning, whereas \(\alpha=1\) denotes graph-only reasoning. Results across all datasets show that combining both rule types yields competitive or better KGC performance than using either rule type alone, indicating that they capture complementary relational patterns. Chain-only reasoning remains stable, suggesting that chain-like rules capture the dominant logical regularities in existing KGs. Adding a small proportion of graph-like rules consistently improves the chain-only baseline. The best performance across metrics is typically obtained with \(\alpha \in [0.1, 0.2]\), indicating that graph-like rules provide complementary information beyond chain-like rules.

13 Multi-seed Robustness Analysis↩︎

To assess the sensitivity of GRiD to random seeds, we evaluate KGC performance across five distinct seeds. Table 8 reports per-seed results for all datasets, and Table 1 presents the mean scores used in the main experiments. Overall, GRiD shows stable performance across seeds. On small- and medium-scale datasets, such as Family and Kinship, the variance in MRR and Hits@\(k\) is close to zero. On more complex datasets, such as FB15K-237 and YAGO3-10, the variance remains low, with values below 1.5 across all metrics, indicating limited performance variation due to random initialization. These results indicate that GRiD is stable under different random seed initializations.

14 Impact of KG Structural Properties↩︎

To examine when graph-like rules provide advantages over chain-like rules, we analyze the dataset-level structural indicators in Table 9, including schema-level connectivity (BF_Schema), relation frequency imbalance (Gini), relation co-occurrence tendency (NPIM), and the many-to-many (N-to-N) ratio. For each relation, we compare KGC performance using only chain-like rules and only graph-like rules, and report Graph Better as the proportion of relations for which graph-like rules outperform chain-like rules.

In Family and Kinship, graph-like rules do not outperform chain-like rules for any relation, despite the high N-to-N ratios of these datasets. This suggests that a many-to-many structure alone is insufficient to explain the usefulness of graph-like rules. The regular kinship semantics of these datasets allow short chain-like rules to capture effective reasoning patterns. WN-18RR shows a similar pattern: although graph-like rules improve some relations, its negative NPIM value and lexical semantics indicate limited relation co-occurrence, which reduces the applicability of graph constraints.

In contrast, UMLS, FB15K-237, and YAGO3-10 have Graph Better values of 17.4%, 20.7%, and 27.0%, respectively. Their high Gini coefficients indicate skewed relation distributions. In such KGs, chain-like rules may match multiple candidate patterns, whereas graph-like rules add conjunctive constraints to reduce ambiguity. The higher Graph Better value of YAGO3-10, compared with FB15K-237, is consistent with the higher Gini coefficient of YAGO3-10.

Overall, graph-like rules are most beneficial when additional structural constraints can reduce the ambiguity of chain-based reasoning, whereas their advantage is limited when relation semantics are already precise and regular.

15 Rule Dataset Construction↩︎

This section describes the construction of supervised pre-training data, which provides the diffusion model with valid, semantically grounded graph-like rules derived from KGs rather than random structures. We construct training rules in two stages. First, we sample chain-like rules via random walks on KGs as structural primitives. We then augment these chains into graph-like rules by injecting auxiliary nodes and relations according to the four graph-like rule types in Fig. 1.

Chain-like Rule Sampling. Given a KG \(\mathcal{G}\), we extract triples \((e_h, r_h, e_t)\), where \(r_h\) is the target relation. For each triple, we perform a random walk of fixed length \(l\) from the head entity \(e_h\). At each step, the next entity is selected uniformly from the neighbors of the current entity: \[P(e_i \mid e_{i-1}) = \frac{1}{|N(e_{i-1})|}\] The resulting relation sequence along the path from \(e_h\) to \(e_t\) forms a relation chain, which is converted into a chain-like rule body by replacing entities with logical variables.

Graph-like Rule Augmentation. After obtaining chain-like rules, we transform them into graph-like rules. For each rule, we uniformly sample one predefined graph topology from Fig. 1 and inject auxiliary nodes and relations accordingly. Depending on the topology, one or two auxiliary variables are introduced to form non-chain structures, such as branching or cyclic dependencies. Auxiliary relations are sampled from \(\mathcal{R}\) to preserve relation-level validity. Each chain is augmented once to produce one graph-like rule, yielding a controlled training set.

Training Instance Definition. Each constructed rule yields one supervised training instance consisting of a rule body and a target relation. The rule body is represented as an adjacency matrix \(\mathbf{A}_0\), as defined in Section 3.1.1, and the target relation \(r_h\) serves as the generation condition. These instances form the dataset for supervised pre-training.

References↩︎