Source-linked AI summary
DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, Daisy Zhe Wang
TL;DR
Inductive link prediction must handle unseen entities, while prior representation-learning methods cannot do so and are not easily explainable. DRUM learns differentiable logical rules for inductive, interpretable link prediction and outperforms previous models on benchmark knowledge bases.
Problem
Prior representation-learning methods cannot handle inductive link prediction with previously unseen entities, while black-box models are difficult for humans to explain.
Method
DRUM is a fully differentiable rule-mining model that learns rule structures and confidence scores, using low-rank tensor approximation and bidirectional RNNs.
Results
DRUM outperforms previous models on benchmark knowledge bases for link prediction and rule quality, including Neural-LP across evaluated settings.
Takeaways & Limitations
DRUM supports inductive and interpretable link prediction while sharing information across rules for different relations.
Takeaways & Limitations
The compact formulation can inevitably mine incorrect rules with high confidence, reflecting restricted expressive power in the obtained rules.
Abstract
from arXiv · showhide
In this paper, we study the problem of learning probabilistic logical rules for inductive and interpretable link prediction. Despite the importance of inductive link prediction, most previous works focused on transductive link prediction and cannot manage previously unseen entities. Moreover, they are black-box models that are not easily explainable for humans. We propose DRUM, a scalable and differentiable approach for mining first-order logical rules from knowledge graphs which resolves these problems. We motivate our method by making a connection between learning confidence scores for each rule and low-rank tensor approximation. DRUM uses bidirectional RNNs to share useful information across the tasks of learning rules for different relations. We also empirically demonstrate the efficiency of DRUM over existing rule mining methods for inductive link prediction on a variety of benchmark datasets.
1 Introduction
Knowledge bases remain incomplete, motivating inference from existing graph elements through representation learning or logical rule mining. DRUM addresses inductive and interpretability challenges with fully differentiable rule mining and reports stronger benchmark performance than prior models.
- Knowledge bases remain incomplete because human knowledge, web corpora, and extraction algorithms have limitations.
- Existing knowledge-graph completion approaches learn entity and relation representations or mine logical rules from frequent graph patterns.
- Rule mining transfers reasoning to unseen facts, whereas representation learning methods require retraining on the whole knowledge base in the illustrated unseen-entity scenario.
- Logical rules provide interpretable predictions that can support human oversight, debugging, trustworthiness, and expert-added knowledge transfer.
- DRUM jointly learns logical rule structures and confidence scores through an end-to-end differentiable model for inductive logic programming.
2 Problem Statement
The paper formulates rule mining as learning connected, closed first-order Horn rules and their confidence values from a knowledge graph. This requires searching discrete relation structures and continuous confidence parameters.
- A knowledge graph is modeled as facts consisting of a subject, relation, and object over entity and relation sets.
- A rule is connected when every atom shares a variable with another atom and closed when every variable appears in at least two atoms.
- The mining task seeks closed and connected Horn clauses because these constraints support meaningful, human-understandable rules and prevent unrelated relations.
- The target rule chains body relations from x to y and assigns a confidence value α to the implication.
- Learning each rule requires searching a discrete space for body relations while optimizing a continuous confidence value.
3 Related work
Prior rule-mining methods include ILP, metric-based counting, embedding-based approaches, and differentiable models. Their limitations include negative-example requirements, poor scalability, predefined metrics, fixed rule lengths, or entity embeddings.
- Traditional ILP methods learn Horn clauses but require both positive and negative examples and do not scale to large knowledge bases containing mostly positive facts.
- AMIE+ and Ontological Pathfinding accelerate counting with predefined confidence and support metrics, but remain limited by discrete counting and metric design.
- Embedding-based rule mining can capture compositional relational semantics through learned relation representations and matrix multiplication.
- RESCAL- and TensorLog-based differentiable methods learn rules by constructing and chaining relation operators to score triples.
- Neural LP uses an LSTM and attention to learn variable rule lengths, but its formulation is described as constrained in rule confidence and can mine incorrect high-confidence rules.
- Other differentiable approaches learn entity embeddings and combine them with rules for link prediction, so they are excluded from the experiments.
4 Methodology
The methodology develops differentiable rule mining by representing rule confidence structures through adjacency-matrix products, then extends this formulation with low-rank tensor approximation and bidirectional RNNs. The resulting design supports variable-length rules, expressive rule sets, and information sharing across head relations, while addressing limitations of earlier formulations.
- 4.1 A Compact Differentiable Formulation: DRUM begins with a vanilla differentiable formulation that represents relation chains through products of knowledge-graph adjacency matrices.For a pair of entities, the resulting scalar counts length-T paths traversing specified relations, enabling rule learning through suitable coefficients.
- 4.1 A Compact Differentiable Formulation: Directly optimizing rule coefficients is over-parameterized, with O(|R|^T) parameters and few observed head-relation pairs.This parameter regime cannot provide useful results, motivating a more compact parameterization.
- 4.1 A Compact Differentiable Formulation: A compact reformulation reduces parameters to T|R| but initially learns only rules of a fixed length T.Introducing an identity relation allows templates of length T or smaller using only T(|R| + 1) free parameters.
- 4.1 A Compact Differentiable Formulation: The compact formulation has restricted confidence expressiveness and can inevitably assign high confidence to incorrect rules.Theorem 1 implies high-confidence intermediate rules between sufficiently distant rules, and confidence values may not directly indicate rule importance.
- 4.2 DRUM: DRUM interprets the compact formulation as rank-one tensor estimation and generalizes it to rank L, which can learn any specified rule set without unrelated rules.The confidence values for rules of length T or smaller form a T-dimensional tensor, motivating low-rank approximation.
- 4.2 DRUM: Bidirectional RNNs generate rule coefficients while sharing recurrent networks across head predicates, allowing information about relation-order patterns to transfer between learning tasks.The forward and backward hidden states capture both directions of atom ordering, and a fully connected network produces the coefficients.
5 Experiments
The experiments evaluate DRUM for statistical relation learning, knowledge graph completion, and rule quality. Across these settings, DRUM outperforms Neural LP and produces rules judged more accurate and better ordered, while embedding comparisons have interpretability limitations.
- Experimental setup: DRUM is evaluated on statistical relation learning, knowledge base completion, and the quality and interpretability of learned rules.Experiments use benchmark datasets and compare DRUM primarily with Neural LP, including DRUM-1 and DRUM-4 rank variants.
- Statistical Relation Learning: DRUM outperforms Neural LP for maximum rule lengths T = 2 and T = 3, with more than seven percent improvement on some UMLS metrics.The authors attribute the performance to higher-rank confidence approximation and bidirectional LSTM ordering information.
- Knowledge Graph Completion: DRUM outperforms Neural LP on all reported metrics across both WN18RR and FB15K-237 in transductive link prediction.On WN18RR, DRUM achieves state-of-the-art Hit@1, Hit@3, and MRR among the compared methods, including embedding-based models.
- Knowledge Graph Completion: In the inductive setting, DRUM surpasses Neural LP, while TransE scores are very close to zero.DRUM is about 1 percent better than Neural LP for Hits@1 and Hits@3 in this experiment.
- Quality and Interpretability of the Rules: Human annotation finds that DRUM rules appear better sorted and more accurate, whereas two of Neural LP’s three top rules are incorrect.Annotators counted correct rules before the first perceived error and inspected top-ranked rules for the family dataset.
- Quality and Interpretability of the Rules: Neural LP’s rank-one confidence estimator can give high confidence to incorrect rules that share a body atom with the highest-confidence rule.This shared-atom effect can make confidence values poor indicators of rule importance and reduce interpretability.
6 Conclusion
The paper presents DRUM as a fully differentiable rule-mining algorithm for inductive and interpretable link prediction. Its objective uses only positive examples under the Open World Assumption, with negative sampling and integration with representation learning left for future work.
- 6 Conclusion: DRUM is a fully differentiable rule-mining algorithm for inductive and interpretable link prediction.The conclusion describes empirical success across multiple tasks and benchmark datasets.
- 6 Conclusion: DRUM is trained only on positive examples under the Open World Assumption of knowledge bases.The authors identify negative sampling as a possible future extension.
- 6 Conclusion: Combining differentiable rule mining with representation learning is identified as another direction for future work.
A Proof of Theorem 1
Theorem 1 establishes a sequence connecting two length-T rules through rules whose consecutive distances are one. The sequence preserves a confidence lower bound and yields a distance bound between the original rules.
- There exist ℓ intermediate length-T rules R1, R2, · · ·, Rℓ connecting Ro and Rs.
- Each consecutive rule pair differs by distance 1, where distance counts mismatched atoms.
- Every intermediate confidence value satisfies αl ≥ min(αo, αs).
- The constructed sequence has length d(Ro, S∗) + d(Rs, S∗) + 1 before excluding the endpoint rules.
- The triangle inequality gives d(Ro, Rs) ≤ d(Ro, S∗) + d(Rs, S∗), implying d(Rs, Ro) ≤ ℓ + 1.
B Extension to the table 2: Comparison with other reasoning methods
Table 8 presents a comparison of statistical relation learning with other reasoning methods.
- Table 8 compares statistical relation learning with other reasoning methods.
C Extension to the table 4: WN18 dataset results
Table 9 presents transductive link prediction results.
- Table 9 reports transductive link prediction results.
D Extension to the table 7: top 10 rules obtained by each system
Table 10 gives examples of top rules learned by each system on the family dataset.
- Table 10 lists examples of top rules obtained by each system learned on the family dataset.