Source-linked AI summary
Generating Graph-Like Logical Rules for Knowledge Graph Reasoning via Diffusion Models
Haoxiang Cheng, Yunfei Wang, Chao Chen, Kewei Cheng, Zhipeng Lin, Haoxuan Li, Changjun Fan, Shixuan Liu
TL;DR
Existing KG rule mining largely focuses on chain-like rules, leaving graph-like relational patterns difficult to discover amid combinatorial search and rule-quality objectives that diffusion reconstruction losses do not directly optimize. GRiD generates graph-like rules with target-conditioned discrete diffusion, using supervised pre-training for structural priors and reinforcement learning guided by rule-quality metrics. Across six benchmarks, it achieves competitive KG completion performance, and ablations find graph-like rules complement chain-like rules.
Problem
Rule mining largely focuses on chains, while graph-like rules face combinatorial search costs; diffusion reconstruction losses also do not directly optimize non-differentiable rule-quality metrics.
Source: §1 · p. 2Method
GRiD generates target-conditioned graph-like rule bodies with discrete diffusion, using supervised pre-training for structural priors and reinforcement learning to optimize rule-quality metrics.
Source: §1 · p. 2, §4.3 · p. 6Results
GRiD achieves strong KG completion performance across six benchmarks, outperforming most rule-based baselines in the majority of settings while remaining competitive with representative embedding and GNN baselines.
Source: §5.2 · p. 8Takeaways & Limitations
Ablation studies show that graph-like rules complement chain-like rules in KG completion.
Source: §1 · p. 2, §6 · p. 9PCA confidence is scoped to body groundings whose subject entity has at least one observed fact under the head relation.
Source: §3 · p. 4
Abstract
from arXiv · showhide
Logical rules constitute a cornerstone of knowledge graph (KG) reasoning, valued for their interpretability and ability to model relational patterns. However, existing rule mining methods predominantly focus on simple chain-like rules and therefore neglect the richer relational information encoded in graph-like structures, such as cycles and branches. This limitation is further exacerbated by computational bottlenecks caused by the combinatorial explosion of the search space, which is especially challenging for graph-like rules. Meanwhile, generative approaches such as diffusion models, despite their success in other domains, cannot be directly applied to rule mining because their training objectives are not aligned with the goal of learning high-quality rules, and non-differentiable KG rule quality metrics cannot directly guide model optimization. To address these limitations, we propose GRiD, a framework that reformulates graph-like rule discovery as a discrete generative process conditioned on the target relation. GRiD employs a two-phase training strategy. First, supervised pre-training enables GRiD to capture structural priors from subgraphs sampled from the KG meta-graph. Subsequently, reinforcement learning is applied to fine-tune GRiD through policy gradient optimization guided directly by non-differentiable rule-quality metrics. Experiments on six benchmark datasets show that GRiD achieves competitive performance on KG completion tasks. Ablation studies confirm the efficiency and robustness of GRiD and further show that graph-like rules complement chain-like rules in KG completion. Our code and datasets are available in https://github.com/Haoxiang-Cheng/GRiD.
1 Introduction
Knowledge graphs are incomplete, and logical rules offer interpretable reasoning through explicit relational dependencies. Existing methods largely favor chain-like rules, while graph-like rules can express richer constraints but expand an already combinatorial search space; GRiD uses diffusion with supervised pre-training and reinforcement-learning fine-tuning to generate such rules.
1 Introduction
- Logical rules provide interpretable reasoning by making relational dependencies explicit, and are often induced from observed path instances.Such instance-grounded induction yields transparent and verifiable reasoning paths.Source: §1 · p. 2
- Graph-like rules enforce multiple relational constraints simultaneously, while chain-like rules can leave ambiguous candidate predictions.The paper illustrates this distinction with a rule that combines workplace and graduation relations to infer birthplace.Source: §1 · p. 2
- Graph-like rule mining expands the search space from O(|R|^L) for chains to O((L|R|)^L), creating a computational bottleneck.The paper also notes substantial overhead from traversing large KG instances in search-based approaches.Source: §1 · p. 2
- Diffusion reconstruction losses do not directly optimize discrete rule-quality measures such as confidence and coverage.These measures cannot be directly back-propagated, so the standard training objective may not align generation with semantically meaningful rules.Source: §1 · p. 2
- GRiD combines supervised pre-training for structural priors with reinforcement-learning fine-tuning guided by rule-quality metrics.The approach reformulates rule discovery as a conditional generative process, addressing the mismatch between diffusion reconstruction objectives and non-differentiable rule-quality measures.Source: §1 · p. 2
2 Related Work
Prior rule-learning approaches developed from logic programming and association mining toward path-based and neural-logic methods, but remained limited in capturing non-linear graph-like structures. Diffusion models have been applied to KG facts and representations, yet the cited approaches do not directly generate explicit schema-level rules; GRiD’s motivation is to apply diffusion to graph-like rule generation with quality-guided reinforcement learning.
2.1 Logical Rule Learning
- Rule learning progressed from inductive logic programming and association mining to path-based methods, which still depend on relational paths or schema-level sequences.FOIL and AMIE generalize from instances; AnyBURL samples and evaluates KG paths.Source: §2.1 · pp. 2–3
- Neural-logic approaches recast rule learning as optimization, including sequential construction, iterative generator-predictor refinement, and compositional rule learning.The cited examples include Neural-LP [43], RNNLogic [29], and NCRL [7], while scalability challenges continued to hinder practical deployment.Source: §2.1 · p. 3
- Existing rule-learning methods still focus mainly on chains, while graph-like rules capture complex relational patterns at the cost of an exponentially growing search space.The section motivates diffusion-based generation as an alternative to this search burden.Source: §2.1 · p. 3, Figure 1 · p. 3
2.2 Diffusion Models
- Diffusion models have been used to generate constrained graph-structured data, including molecules, providing precedent for structured-pattern generation.The section describes this capability as relevant to discovering valid relational paths in structured graphs.Source: §2.2 · p. 3
- Diffusion applications to KG reasoning primarily generate facts or refine entity representations rather than explicit schema-level rules.The section distinguishes instance-level generation [20? ] from continuous latent-space approaches.Source: §2.2 · p. 3
- Standard diffusion reconstruction losses are misaligned with discrete rule-quality metrics, motivating reinforcement learning to optimize rule generation using those metrics as rewards.The paper positions this mismatch as the challenge in applying diffusion to graph-like rule generation.Source: §2.2 · p. 3
3 Preliminaries
The preliminaries define knowledge graphs and logical rules, then distinguish graph-like rules by the topology of their bodies. They also introduce rule-quality measures, including PCA confidence, whose denominator is restricted by an observed-head-fact condition.
3 Preliminaries
- A knowledge graph is a relation-labeled directed graph comprising entities, relations, and factual triples.A logical rule expresses a head predicate as implied by a conjunction of body predicates.Source: §3 · p. 4
- Graph-like rules have directed-graph bodies categorized as linear, branching, edge-cycling, or node-cycling structures.These basic structures can be combined into more complex hybrid patterns.Source: §3 · p. 4, Figure 2 · p. 4
- Support counts entity pairs satisfying both the rule body and head, while coverage measures the share of head-relation pairs that also satisfy the body.Confidence measures the proportion of body groundings that support the head; PCA confidence restricts its denominator to groundings whose subject has an observed head-relation fact.Source: §3 · p. 4
4 Methods
GRiD generates graph-like rule bodies through conditional discrete diffusion, with supervised pre-training to learn structural priors and reinforcement learning to optimize rule quality. Its inference pipeline denoises sampled graph structures and filters them into valid rules.
4 Methods
- GRiD models graph-like rule discovery as conditional discrete diffusion over rule-body adjacency matrices, then uses supervised pre-training and reinforcement-learning fine-tuning.The process is conditioned on the target relation; pre-training uses KG meta-graph subgraphs, while fine-tuning uses rule-quality metrics.Source: §4 · p. 4, Figure 3 · p. 5
4.1.1 Discrete State Formulation.
- The rule body is represented as a directed-graph adjacency matrix, conditioned on the target relation and diffusion timestep.The matrix encodes edge relations, with padding for unused nodes to support fixed-dimensional processing.Source: §4.1.1 · pp. 4–5
4.1.2 Forward Diffusion Process.
- Forward diffusion progressively corrupts the clean rule-body matrix through categorical transitions, leaving edges unchanged or resampling them uniformly according to the noise schedule.As the timestep increases, the marginal distribution converges to uniform categorical noise.Source: §4.1.2 · p. 5
4.1.3 Reverse Diffusion Process.
- The reverse process uses a Graph Transformer to predict edge-category distributions from the noisy matrix and conditioning vector, then iteratively samples a rule body.Feature-wise modulation lets message passing adapt to the timestep and target relation.Source: §4.1.3 · pp. 5–6
4.2 Phase A: SL Pre-training
- Supervised pre-training teaches the denoiser to reconstruct clean adjacency matrices from corrupted KG subgraphs and adds an auxiliary prediction of rule quality.The objective balances structural reconstruction with a quality score based on normalized coverage and confidence.Source: §4.2 · p. 6
4.3 Phase B: RL Fine-tuning
- RL fine-tuning treats denoising as a stochastic policy and rewards completed rules using the geometric mean of coverage, confidence, and PCA confidence.The policy-gradient objective includes entropy regularization to encourage exploration.Source: §4.3 · p. 6
4.4 Inference Pipeline
- At inference, GRiD starts from a noisy adjacency matrix, iteratively denoises it conditioned on the target relation, and parses the result into a rule body.The head and tail variables are selected from graph degree and topology, and structural constraints filter invalid rules.Source: §4.4 · p. 6
5 Experiment
GRiD performs strongly across six KGC benchmarks, with graph-like rules especially useful where relational structure makes chain-based predictions ambiguous. Ablations find complementary rule types, a useful fusion-weight range, gains from RL fine-tuning, and strong performance with small graph-size limits; rule generation costs are incurred offline.
5.1 Experimental settings
- The evaluation uses six datasets, 16 baselines, filtered Hit@1, Hit@10, and MRR, with each dataset split 9:1 into training and test sets.The six datasets are YAGO3-10, FB15K-237, Family, Kinship, UMLS, and WN-18RR.Source: §5.1 · p. 7
5.2 Knowledge Graph Completion Results
- GRiD outperforms most rule-based baselines in most settings and is competitive with embedding and GNN methods across six benchmarks, while producing explicit rules.On FB15K-237 and YAGO3-10, it achieves the best or second-best results despite scalability limits faced by several rule-based approaches.Source: §5.2 · p. 8
5.3 Ablation Studies
- The combined rule configuration consistently outperforms either rule type alone, while graph-like rules alone perform worse because stricter constraints reduce coverage in sparse KGs.The comparison holds the total number of rules constant.Source: Table 2 · p. 8, §5.3 · p. 8
- Adding graph-like rules improves chain-only reasoning, with best performance typically at α around 0.1–0.2; larger weights degrade performance as supported groundings decrease.The fusion weight varies at scoring time while the generated rule sets remain fixed.Source: Figure 4 · p. 8, §5.3 · p. 8
- S=6 achieves the best MRR across all datasets, consistent with longer rules adding limited utility because they can be composed from shorter rules.The authors state that a small S can improve efficiency while preserving sufficient expressiveness for the rule patterns considered.Source: §5.3 · pp. 8–9, Table 3 · p. 9
- Approximately 10% improvement across all metrics is reported for RL fine-tuning on YAGO3-10, and geometric-mean rewards outperform summed rule-quality metrics.The comparison is against supervised pre-training alone and includes two RL reward variants.Source: §5.3 · p. 8, Figure 5 · p. 9
5.4 Efficiency Analysis
- Rule generation is offline; on YAGO3-10, SL pre-training takes 1.34 s per epoch and RL fine-tuning 18.76 s, while peak GPU memory is 11.41 GB on FB15K-237 and 5.52 GB on YAGO3-10.After rule generation, inference uses sparse-matrix grounding and aggregation.Source: §5.4 · p. 9
6 Conclusion
The paper concludes that GRiD uses target-relation-conditioned discrete diffusion, combining supervised pre-training and RL fine-tuning to generate graph-like rules. Across six benchmarks, those rules support KGC, and the ablations find that graph-like and chain-like rules have complementary effects.
6 Conclusion
- GRiD formulates rule discovery as target-relation-conditioned discrete diffusion, using supervised pre-training for structural priors and RL fine-tuning for rule-quality metrics.The paper identifies future work on reducing sampling bias and developing structural evaluation metrics.Source: §6 · p. 9
- Experiments show that GRiD-generated rules support KGC across six benchmark datasets, and ablations show complementary effects between graph-like and chain-like rules.Source: §6 · p. 9
Appendix A Dataset Description
The appendix describes six benchmark datasets spanning large knowledge graphs and domain-specific settings, then catalogs embedding, GNN, and rule-based baselines.
Appendix A Dataset Description
- The six datasets cover family and kinship relations, biomedical concepts, lexical connections, Freebase, and YAGO.Family, Kinship, UMLS, and WN-18RR are domain-specific; FB15K-237 and YAGO3-10 are larger knowledge graphs.Source: Appendix A · p. 11
Appendix B Baseline Description
- Embedding baselines include TransE, DistMult, ComplEx, RotatE, and SpeedE, with distinct geometric or scoring formulations.The descriptions include translation, diagonal bilinear scoring, complex embeddings, complex-space rotations, and Euclidean geometry.Source: Appendix B · p. 11
- GNN baselines include CompGCN, NBFNet, and A∗Net, which use compositional aggregation, neural path aggregation, and heuristic path search.A∗Net extends NBFNet with A∗-like heuristics to prioritize informative paths.Source: Appendix B · p. 11
- Rule-based baselines range from path-sampling and Horn-rule miners to differentiable, recurrent, recursive, and LLM-prompted rule learners.The listed methods are AnyBURL, AMIE, Neural-LP, DRUM, RNNLogic, RLogic, NCRL, and ChatRule.Source: Appendix B · p. 11
Appendix C Impact of KG Structural Properties
The structural analysis relates when graph-like rules help to KG properties, while the rule comparison illustrates four generated rule-body structures.
Appendix C Impact of KG Structural Properties
- The analysis considers schema connectivity, relation-frequency imbalance, co-occurrence tendency, and the many-to-many ratio alongside Graph Better.Graph Better is the proportion of relations where graph-like rules outperform chain-like rules.Source: Appendix C · p. 11
- Graph-like rules help most when added structural constraints disambiguate chain-based reasoning, but offer less advantage with regular semantics or weak co-occurrence.Kinship patterns are already captured by chains, while WN-18RR has weak relation co-occurrence (NPIM = -0.07); UMLS, FB15K-237, and YAGO3-10 show richer ambiguity and higher Graph Better values.Source: Appendix C · p. 11
Appendix D Rule Comparison
- GRiD’s examples illustrate linear, branching, edge-cyclic, and node-cyclic rule bodies on YAGO3-10.The examples include sequential paths, a branching shared node, two relations connecting the same pair, and cycles through shared intermediate nodes.Source: Appendix D · p. 11
Appendix E Multi-seed Robustness Analysis
The appendix reports stable results across random seeds and describes how generated rules are grounded, scored, and used to rank filtered KGC predictions.
Appendix E Multi-seed Robustness Analysis
- Across five random seeds, GRiD’s results remain stable, with small 95% confidence intervals and variance close to zero on small datasets and below 1.5 on more complex datasets.The authors interpret this as insensitivity to random initialization.Source: Appendix E · pp. 11–12, Table 6 · p. 12
- The appendix identifies Table 5 as presenting representative chain-like and graph-like rules learned on YAGO3-10.The table caption identifies the examples’ dataset and rule categories.Source: Table 5 · p. 12
Appendix F KGC Pipeline
- The KGC pipeline grounds chain rules by sparse matrix multiplication and graph-like rules by conjoining grounded chain components.Rule quality is computed from coverage, confidence, and PCA-confidence; candidate tails are ranked under filtered evaluation, with Hit@K and MRR reported.Source: Appendix F · p. 12
Appendix G Rule Dataset Construction
Supervised pre-training examples are built from sampled KG walks and augmented into graph-like rule bodies conditioned on the target relation.
Appendix G Rule Dataset Construction
- For each training triple, fixed-length random walks become chain-like rule bodies, and each chain is augmented once using a sampled Fig. 2 topology.Entities are replaced with logical variables, auxiliary variables and relation labels are added, and the rule-body adjacency matrix is conditioned on the triple’s target relation.Source: Appendix G · p. 12