Neural Compositional Rule Learning for Knowledge Graph Reasoning

Kewei Cheng, Nesreen Ahmed, Yizhou Sun

TL;DR

Neural Compositional Rule Learning (NCRL) is an end-to-end neural model that learns logical rules for Knowledge Graph (KG) reasoning by treating them as hierarchical compositions. By recursively merging small chunks of a relationship path into a single "head" relation using a novel recurrent attention unit, NCRL achieves state-of-the-art accuracy while being up to 100x faster than existing baselines.

The Challenge of Knowledge Graph Reasoning

Knowledge Graphs (KGs) like Freebase or YAGO are massive networks of facts, typically represented as triplets (e.g., (UCLA, locatedIn, Los Angeles)). Because these graphs are inherently incomplete, researchers rely on automated "reasoning" to fill in the missing gaps.

The gold standard for this reasoning process is learning logical rules (e.g., hasGrandma(x,y) ← hasMother(x,z) ∧ hasMother(z,y)). These rules are highly desirable because they are interpretable and can naturally generalize to entirely new data.

Generalizing logical rules from a training graph to an unseen test graph.

However, existing methods face a significant "Goldilocks" problem:

  1. Symbolic methods (like Inductive Logic Programming) are highly precise but computationally expensive, making them unable to scale to the millions of entities found in modern KGs.
  2. Neural-symbolic methods (like Neural-LP) scale much better but often fail at "systematic generalization." They struggle when asked to reason on graphs that are larger or feature longer reasoning paths than what they were exposed to during training.

The authors of this paper identify a critical missing ingredient in current neural-symbolic models: compositionality. Most existing models treat a path of relations as a flat, linear sequence. This ignores the reality that logical rules are naturally hierarchical and built from smaller, reusable sub-rules.

The NCRL Approach: Hierarchical Compositionality

To address this, the authors propose Neural Compositional Rule Learning (NCRL). Instead of attempting to learn a complex rule all at once, NCRL breaks the problem down into manageable, hierarchical steps:

Comparison of a correct hierarchical compositional tree versus an incorrect flat structure.
  • Path Sampling: The model begins by taking random walks through the Knowledge Graph to extract paths between entities.
  • Hierarchical Structure Learning: NCRL uses a sliding window to examine small segments of a path (e.g., two relations at a time). A Recurrent Neural Network (RNN) encodes these segments, and a selection mechanism determines which segment is the most "meaningful" to merge first.
  • Recurrent Attention Unit: This is the core innovation of the paper. It takes a selected segment and uses an attention mechanism to "match" it against all known relations in the KG. For example, if the segment (hasMother ∧ hasMother) closely aligns with the semantics of hasGrandma, the model replaces that two-step segment with the single hasGrandma predicate.
  • The "Null" Predicate: Real-world KGs are messy, and a composition might not perfectly match an existing relation. To handle this, NCRL includes a "null" predicate. This allows the model to maintain the internal representation of a complex path without forcing it into an incorrect label.
  • Recursive Reduction: This merging process repeats recursively until the entire multi-step path is reduced to a single predicted "head" relation.

Key Insights and Performance

The model was rigorously evaluated on two main fronts: standard Knowledge Graph Completion (using benchmarks like Family, UMLS, Kinship, WN18RR, FB15K-237, and YAGO3-10) and Systematic Generalization (using CLUTRR and GraphLog to test reasoning on longer, unseen path lengths).

The results highlight several major advantages of the NCRL architecture:

  • Compositionality Drives Generalization: By learning how to merge two relations into one, the model masters a fundamental "building block" of logic. This allows it to solve 10-step reasoning problems during testing even if it only saw 3-step problems during training. On the CLUTRR dataset, while standard RNNs and Transformers saw their accuracy plummet as path lengths increased, NCRL remained nearly perfect (1.0 accuracy) even on 10-hop paths.
  • Efficiency Through Sparsity: Unlike previous neural logic models that perform massive, memory-intensive matrix multiplications across the entire graph, NCRL operates strictly on sampled paths. This makes it significantly more memory-efficient.
  • Unprecedented Speed: NCRL is roughly 100x faster than state-of-the-art baselines like RNNLogic and DRUM. On the massive YAGO3-10 dataset, where many competing models crashed due to memory limits, NCRL successfully finished training in just 190 seconds.
  • State-of-the-Art Accuracy: It achieved SOTA or comparable results across all KG completion tasks. Notably, it demonstrated a massive improvement on the WN18RR dataset, achieving a Mean Reciprocal Rank (MRR) of 0.67 compared to the previous best of 0.47.

Limitations and Future Work

While powerful, NCRL currently has a few limitations. It is primarily designed for "chain-like" Horn rules (a simple, linear path from entity A to entity B). It does not yet handle more complex rule bodies that might feature branching structures or multiple variables. Additionally, because it relies on path sampling, the model's performance is tied to the quality of the random walks; if the sampler misses critical paths, the model cannot learn the associated rules.

Future work will likely focus on extending this hierarchical merging logic to more complex, non-linear rule structures, and exploring how this compositional approach could be applied to broader domains like natural language reasoning.

Summary updated

Abstract

Learning logical rules is critical to improving reasoning in KGs. This is due to their ability to provide logical and interpretable explanations when used for predictions, as well as their ability to generalize to other tasks, domains, and data. While recent methods have been proposed to learn logical rules, the majority of these methods are either restricted by their computational complexity and can not handle the large search space of large-scale KGs, or show poor generalization when exposed to data outside the training set. In this paper, we propose an end-to-end neural model for learning compositional logical rules called NCRL. NCRL detects the best compositional structure of a rule body, and breaks it into small compositions in order to infer the rule head. By recurrently merging compositions in the rule body with a recurrent attention unit, NCRL finally predicts a single rule head. Experimental results show that NCRL learns high-quality rules, as well as being generalizable. Specifically, we show that NCRL is scalable, efficient, and yields state-of-the-art results for knowledge graph completion on large-scale KGs. Moreover, we test NCRL for systematic generalization by learning to reason on small-scale observed graphs and evaluating on larger unseen ones.
BibTeX
@inproceedings{cheng2023neural,
  author = {Kewei Cheng and Nesreen Ahmed and Yizhou Sun},
  title = {{Neural Compositional Rule Learning for Knowledge Graph Reasoning}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=F8VKQyDgRVj},
}
Figure