Learning Rules With Attributes and Relations in Knowledge Graphs

Pouya Ghiasnezhad Omran, Zhe Wang, Kewen WangAAAI 2022

Abstract

Knowledge Graph (KG) completion often relies on rule learning to predict missing links. However, traditional path-based learners struggle to incorporate specific entity attributes (constants) due to the resulting combinatorial explosion in the search space. This paper presents HARL (Hub Augmented Rule Learning), a framework that identifies highly connected "hub" entities and transforms them into self-looping relations. This structural modification allows existing path-based algorithms to learn more precise rules involving attributes without increasing computational complexity. Experiments on FB15K and YAGO2 demonstrate that HARL discovers higher-quality rules and improves link prediction performance while maintaining scalability.

Introduction

Knowledge Graphs (KGs) are massive networks of facts stored as triples: (Subject, Predicate, Object). To fill in missing links, researchers use rule learning to discover logical patterns. Traditional scalable learners focus on "closed path rules"—sequences of relations like “If X is the child of Y, and Y is male, then X has Y as a father.”

However, most scalable systems struggle to include constants (specific entities) in these rules. For example, a rule might be much more accurate if it specifies a country: “If X is a citizen of the Netherlands and lives in Y, then Y is likely in the Netherlands.” Including every possible entity as a potential constant creates a combinatorial explosion that breaks most algorithms. This paper addresses the challenge of identifying which entities are actually useful "attributes" and incorporating them into rules efficiently.

Methodology: The HARL Framework

The authors propose a two-step approach called HARL (Hub Augmented Rule Learning) to bridge the gap between path-based relations and entity-specific attributes.

The HARL framework workflow: from Hub Discovery to Knowledge Graph enrichment.

1. Hub Discovery

Instead of testing every entity, the system automatically identifies "hubs"—entities that act more like attributes than unique nodes. They use three metrics to find these:

  • Density: The number of connections an entity possesses.
  • Entropy: The degree to which an entity helps distinguish between other entities.
  • Imbalance Degree: Whether a predicate typically links many subjects to a few specific objects (e.g., gender).

2. KG Enrichment

Once hubs are identified (e.g., the entity USA under the predicate country), they are transformed into unary predicates represented as self-loops in the graph. For example, a triple (Movie, country, USA) is transformed into a self-looping triple (Movie, country_USA, Movie). This structural modification allows path-based learners to "stay in place" to check an attribute without needing a new logic engine.

Transformation of hub entities into self-looping relations to enable path-based rule learning.

3. Rule Learning and Context-Aware Inference

The enriched graph is processed by an existing learner (RLvLR). To prevent "over-prediction," the authors introduce Context-Aware Inference. This calculates the "demand" for a fact based on the average number of relations (ANF) an entity usually has (e.g., a person typically has only two parents), rejecting predictions that exceed natural limits.

Experimental Evaluation

The researchers evaluated HARL on three standard benchmark knowledge graphs: FB15K, FB15KSE, and YAGO2 core.

Key Results

  • Rule Quality: HARL consistently found more high-quality rules than the baseline RLvLR. On FB15K, it discovered 48 high-quality concise rules compared to the baseline's 10. Adding a single hub can drastically increase rule confidence; in YAGO2, adding the hub University_College_Dublin to a citizenship rule increased confidence from 0.03 to 0.61.
  • Link Prediction: On FB15K, HARL improved the Mean Reciprocal Rank (MRR) from 0.3 to 0.36 and increased Hits@1 from 0.2 to 0.23.
  • Efficiency: Despite the extra step of hub discovery, HARL remains scalable. The time overhead was minimal (e.g., 389 seconds for HARL vs. 310 seconds for the baseline on FB15K).

Discussion and Limitations

While HARL shows significant promise, it faces challenges with sparse data. Improvements on the more difficult FB15KSE and YAGO2 datasets were more modest, suggesting hub-based rules are harder to find when connectivity is low. Additionally, the "Context-Aware Inference" relies on average counts, which may ignore natural variations (e.g., the number of citizens varies wildly between nations).

Conclusion

HARL demonstrates that treating highly connected entities as hubs and representing them as self-loops is an effective strategy for incorporating attributes into path-based rule learning. This approach enhances the specificity and accuracy of discovered rules while maintaining the scalability required for massive knowledge graphs.

Summary updated

BibTeX
@inproceedings{omran2022learning,
  author = {Pouya Ghiasnezhad Omran and Zhe Wang and Kewen Wang},
  title = {{Learning Rules With Attributes and Relations in Knowledge Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
}
Figure