Source-linked AI summary
RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs
Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, Jian Tang
TL;DR
Learning high-quality logic rules for knowledge-graph reasoning is difficult because prior approaches face large search spaces or sparse rewards. RNNLogic treats rules as latent variables and jointly trains a rule generator with a reasoning predictor using EM. Experiments on four datasets establish its effectiveness, while training assumes triplets outside the observed set are incorrect.
Problem
Learning logic rules matters for interpretable, precise, and reusable knowledge-graph reasoning, but existing methods face large search spaces or sparse rewards.
Method
RNNLogic treats logic rules as latent variables and jointly trains a rule generator with a reasoning predictor through EM-based optimization.
Results
Experiments on four datasets prove RNNLogic’s effectiveness, with the rule generator and reasoning predictor collaborating to outperform multiple rule-learning and reinforcement-learning baselines.
Takeaways & Limitations
RNNLogic explicitly learns reusable logic rules while using predictor feedback to reduce search and address sparse-reward optimization.
Takeaways & Limitations
Training assumes that any triplet outside the observed triplet set is incorrect.
Abstract
from arXiv · showhide
This paper studies learning logic rules for reasoning on knowledge graphs. Logic rules provide interpretable explanations when used for prediction as well as being able to generalize to other tasks, and hence are critical to learn. Existing methods either suffer from the problem of searching in a large search space (e.g., neural logic programming) or ineffective optimization due to sparse rewards (e.g., techniques based on reinforcement learning). To address these limitations, this paper proposes a probabilistic model called RNNLogic. RNNLogic treats logic rules as a latent variable, and simultaneously trains a rule generator as well as a reasoning predictor with logic rules. We develop an EM-based algorithm for optimization. In each iteration, the reasoning predictor is first updated to explore some generated logic rules for reasoning. Then in the E-step, we select a set of high-quality rules from all generated rules with both the rule generator and reasoning predictor via posterior inference; and in the M-step, the rule generator is updated with the rules selected in the E-step. Experiments on four datasets prove the effectiveness of RNNLogic.
1 INTRODUCTION
Knowledge graphs are incomplete collections of real-world facts, making missing-fact prediction through reasoning fundamental. This paper learns logic rules for that task, addressing the challenge of searching a large rule space with a probabilistic generator–predictor framework.
- Knowledge graphs store facts as entity-relation-entity triplets but remain incomplete because collecting all facts is impossible.
- Logic rules can improve reasoning interpretability and precision while also generalizing across domains and data.
- Learning high-quality logic rules is challenging because the candidate search space is large.
- RNNLogic jointly trains a recurrent rule generator and a reasoning predictor, treating logic rules as a latent variable.
- The generator proposes rules for reasoning, while the predictor evaluates answers and supplies feedback that helps reduce the search space.
2 RELATED WORK
Prior work learns rules through path enumeration, differentiable logic programming, reinforcement-learning path search, or implicit embedding patterns. RNNLogic instead couples explicit rule generation with reasoning and updates the generator using predictor feedback.
- Traditional methods enumerate relational paths as candidate rules and learn a quality weight for each rule.
- Reinforcement-learning methods search reasoning paths with agents, but their reward can be extremely sparse when paths fail to reach the correct answer.
- The paper uses “set” as shorthand for a multiset of rules.
- RNNLogic’s EM optimization alternates predictor exploration, posterior identification of high-quality rules, and generator updates consistent with those rules.
- Embedding methods can learn some simple composition, symmetric, and inverse rules, whereas RNNLogic explicitly generates more complicated logic rules.
- RNNLogic dynamically updates its rule generator from reasoning-predictor feedback, applying this boosting-like idea to knowledge graph reasoning.
3 MODEL
RNNLogic models logic rules as latent variables and jointly trains a rule generator with a reasoning predictor. An EM-based procedure selects high-quality rules while the predictor scores rule-based reasoning, optionally combined with knowledge graph embeddings.
- Model formulation: RNNLogic treats query-explanatory logic rules as latent variables, jointly modeling them with a rule generator and reasoning predictor.The generator defines a prior over rule sets, while the predictor defines the likelihood of answers conditioned on rules, queries, and graphs.
- Rule generator: The rule generator uses an RNN to generate compositional rules from the query relation without the query entity.This relation-only generation allows rules to generalize across entities; generation stops at a special end relation.
- Reasoning predictor: The reasoning predictor scores candidate answers by aggregating grounding paths found by generated rules and converts scores into probabilities with softmax.Each candidate answer can receive contributions from multiple rules and their grounding paths.
- Optimization: Each iteration updates the reasoning predictor, selects high-quality rules by posterior inference, and updates the generator through an EM-based procedure.In practice, top-K rules are used as a MAP estimate, yielding a hard-assignment EM variant that performs better empirically than posterior sampling.
- Reasoning predictor: The predictor can combine logic-rule scores with knowledge graph embedding scores, with η controlling the embedding contribution.This produces a more powerful candidate-answer score before softmax prediction.
4 EXPERIMENT
Experiments across four knowledge-graph datasets compare RNNLogic with rule-learning, embedding-based, and reinforcement-learning methods. RNNLogic performs competitively with few rules, under sparse data, and across embedding dimensions, while EM outperforms REINFORCE and generated rules are meaningful and diverse.
- Comparison with baselines: RNNLogic achieves much better results than statistical relational, neural differentiable, and reinforcement-learning rule-learning methods.The paper attributes these gains to collaboration between the rule generator and reasoning predictor and to EM-based optimization addressing sparse rewards.
- Comparison with baselines: RNNLogic with embeddings outperforms most compared methods in most cases, while its embedding-free variant is competitive when training triplets are limited.The embedding-free results are especially competitive on WN18RR, Kinship, and UMLS.
- RNNLogic+: RNNLogic+ without embeddings is competitive on FB15k-237 and WN18RR, outperforming all other methods on WN18RR using only 100 or 200 rules per relation.The rule counts are 100 per relation on FB15k-237 and 200 per relation on WN18RR.
- RNNLogic+: Adding embeddings significantly improves RNNLogic+ on both datasets, and the method achieves the best result on WN18RR.The paper describes logic rules and knowledge-graph embeddings as complementary sources of information.
- Rule quality and robustness: RNNLogic achieves much better results across different numbers of selected rules and remains competitive with only 10 rules per relation.Rules are selected by prior probability from the generator, with beam search used to infer the top rules.
- Rule quality and robustness: RNNLogic w/o embeddings achieves the best results as training triplets decrease, with its improvement over RotatE becoming more significant under greater data sparsity.The experiment evaluates reduced training data on Kinship and UMLS.
- Rule quality and robustness: RNNLogic significantly outperforms RotatE at every embedding dimension, with the paper attributing the improvement mainly to learned logic rules.The comparison uses RNNLogic with embeddings and RotatE.
- Optimization: EM consistently outperforms REINFORCE for optimizing the rule generator in the w/o emb. setting on Kinship and UMLS.The comparison results are reported in Table 4.
5 CONCLUSION
The paper proposes RNNLogic for learning logic rules in knowledge graph reasoning by jointly learning a rule generator and reasoning predictor with an EM-based optimization algorithm. Experiments support its effectiveness, while future work targets more complicated rules and other reasoning problems.
- RNNLogic treats explanatory logic rules as a latent variable and jointly learns a rule generator with a reasoning predictor.
- The model uses an EM-based algorithm to optimize the rule generator.
- Future work will study generating more complicated rules beyond compositional rules and extending RNNLogic to tasks such as question answering.
A PROOFS
This appendix presents proofs for propositions used in RNNLogic's optimization algorithm. Proposition 1 approximates the posterior over rule sets so that sampling becomes tractable.
- The appendix provides proofs for propositions used in RNNLogic's optimization algorithm.
- Direct posterior sampling in the E-step is intractable because of the partition function, so Proposition 1 supplies a more tractable approximation.
A.1 PROOF OF PROPOSITION 1
The proof derives an approximation to the posterior over fixed-size rule subsets by bounding the reasoning-predictor term. The resulting variational distribution is multinomial, enabling independent rule sampling and maximum-posterior hard assignments.
- Proposition 1 considers a fixed-size subset of generated rules and approximates its log-posterior using rule scores and generator probabilities.
- The proof bounds the posterior contribution involving candidate-answer scores under the condition that the maximum absolute score is below 1.
- The approximation constructs q(zI) proportional to the exponentiated sum of rule scores H(rule) and the subset correction γ(zI).
- The resulting q(zI) is a multinomial distribution whose rule probabilities are normalized exponentiated H(rule) values.
- Sampling from q(zI) amounts to independently drawing K rules, while hard-assignment EM selects the K rules with highest probability under the approximating distribution.
B MORE ANALYSIS OF THE EM ALGORITHM
The EM analysis frames optimization through an evidence lower bound for the latent-rule likelihood. The E-step tightens this bound by approximating the posterior over generated rule subsets, and the M-step updates the generator; these updates increase the lower bound and likelihood.
- The appendix explains why EM can optimize the rule generator's objective.
- The latent-rule likelihood is lower-bounded by an expectation over a variational distribution q(zI).
- In the E-step, q(zI) is optimized to reduce KL divergence from the posterior, while the M-step optimizes generator parameters against the lower bound.
- The E-step restricts q(zI) to size-K subsets of generated rules, making posterior approximation tractable through Proposition 1.
- The M-step estimates the lower-bound expectation by sampling a rule set from q(zI) and optimizing the terms relevant to the generator.
- Performing the E-step and M-step increases the evidence lower bound and thereby pushes up the log-likelihood with respect to the generator.
C DETAILS ABOUT PARAMETERIZATION AND IMPLEMENTATION
RNNLogic parameterizes compositional logic rules as relation sequences generated by an LSTM-based rule generator, while a reasoning predictor scores candidate answers using rule and path weights.
- Reasoning Predictor: The reasoning predictor uses a rule set to score candidate answers and predict the correct answer.
- Reasoning Predictor: Candidate answers are discovered by grounding logic rules, and each candidate receives a score based on its grounding paths.
- Reasoning Predictor: Rule and path contributions are represented by scalar weights ψ_w(rule) and φ_w(path).
- Reasoning Predictor: The rule weight uses the number of relational paths from the query head to the correct tail, measuring the rule's contribution to correct answers.Random or zero initialization produced similar results.
- Reasoning Predictor: Path weights can be fixed to 1 or computed from entity and relation embeddings in the complex space.
- Reasoning Predictor: The embedding-based path score rotates the starting entity embedding through relation operators, measures distance to the ending entity, and applies a sigmoid transformation.The Hadamard product acts as a rotation operator, with δ as a hyperparameter.
- Rule Generator: Compositional rules are represented as relation sequences ending with the special relation r_END.
- Rule Generator: The LSTM-based rule generator sequentially produces the next relation and its probability from the current relation sequence.It initializes hidden states, updates them with LSTM gates, and applies a softmax over relations.
D.1 DATASET STATISTICS
The paper summarizes the statistics of its knowledge-graph datasets in Table 6.
- Table 6 reports the statistics of the datasets used in the experiments.
D.2 EXPERIMENTAL SETUP OF RNNLOGIC
RNNLogic is evaluated using validation-selected configurations, augmented training graphs, generated rules, and an EM procedure that selects high-quality rules for optimization.
- Experimental Setup: Hyperparameters are tuned on the validation set, and the optimal configuration is used for testing.
- Data Preprocessing: Each training triplet is augmented with its inverse, while the sampled triplet forms the query-answer pair and the remaining triplets form the background graph.
- Rule Generator: Rule-generator maximum lengths are 4 for FB15k-237, 5 for WN18RR, and 3 for Kinship and UMLS.Beam search generates high-probability rules.
- EM Optimization: During EM optimization, 1000 rules are sampled per instance and 300 are identified as high-quality in the E-step.
- Evaluation: At test time, the generator produces 1000 rules and the reasoning predictor uses them to predict the answer.
- Learned Rules: The paper presents additional rules learned on FB15k-237 and UMLS in Table 7.
- Relation to REINFORCE: REINFORCE weights all generated rules by a reasoning-predictor reward, such as the probability assigned to the correct answer.
- Relation to REINFORCE: EM instead maximizes the log-probability of rules selected in the E-step, coinciding with REINFORCE when selected rules receive reward 1 and others receive 0.