PaperlayerView exact revision on arXiv

Source-linked AI summary

Iteratively Learning Embeddings and Rules for Knowledge Graph Reasoning

Wen Zhang, Bibek Paudel, Liang Wang, Jiaoyan Chen, Hai Zhu, Wei Zhang, Abraham Bernstein, Huajun Chen

arXiv:1903.08948v1cs.AIcs.CL

TL;DR

Knowledge graph reasoning needs both scalable embeddings and precise rules, yet sparse entities weaken embeddings and graph search makes rule learning inefficient. IterE iteratively learns embeddings and rules, injecting rule-inferred triples into embedding training and using embeddings for rule induction. Experiments report improved sparse-entity embeddings and link prediction alongside more efficient, high-quality rule learning, with benefits between the two components during learning and prediction.

  • Problem

    Embedding-based reasoning struggles with sparse entity representations, while rule learning faces inefficient graph search over a huge space.

  • Method

    IterE iteratively learns embeddings and rules, using embeddings for axiom induction and injecting axiom-inferred triples into embedding learning.

  • Results

    IterE achieves better link prediction, improves sparse entity embedding quality, and learns high-quality rules more efficiently than conventional rule-learning systems.

  • Takeaways & Limitations

    Rules and embeddings benefit each other during learning and prediction by combining deductive rule inference with inductive embedding-based reasoning.

  • Takeaways & Limitations

    Results are less obvious on WN18-sparse and WN18RR-sparse because these datasets contain few relations and yield limited learned rules.

Abstract

from arXiv · show

Reasoning is essential for the development of large knowledge graphs, especially for completion, which aims to infer new triples based on existing ones. Both rules and embeddings can be used for knowledge graph reasoning and they have their own advantages and difficulties. Rule-based reasoning is accurate and explainable but rule learning with searching over the graph always suffers from efficiency due to huge search space. Embedding-based reasoning is more scalable and efficient as the reasoning is conducted via computation between embeddings, but it has difficulty learning good representations for sparse entities because a good embedding relies heavily on data richness. Based on this observation, in this paper we explore how embedding and rule learning can be combined together and complement each other's difficulties with their advantages. We propose a novel framework IterE iteratively learning embeddings and rules, in which rules are learned from embeddings with proper pruning strategy and embeddings are learned from existing triples and new triples inferred by rules. Evaluations on embedding qualities of IterE show that rules help improve the quality of sparse entity embeddings and their link prediction results. We also evaluate the efficiency of rule learning and quality of rules from IterE compared with AMIE+, showing that IterE is capable of generating high quality rules more efficiently. Experiments show that iteratively learning embeddings and rules benefit each other during learning and prediction.

1 INTRODUCTION

Knowledge graph reasoning combines embeddings and rules, but each faces a distinct weakness: sparse entities challenge embeddings, while graph search makes rule learning inefficient. IterE addresses both through iterative embedding, axiom induction, and axiom injection.

  • Motivation: Embedding-based reasoning scales to many relations or triples, whereas rule-based reasoning provides precise and interpretable deductive inference.
  • Motivation: Sparse entities have much worse link prediction results than frequent entities because embedding quality is strongly related to entity frequency.Figure 1 reports this relationship using mean reciprocal rank on FB15k-237.
  • Motivation: Rule learning faces an exponential search space when determining rule structures and searching for supporting triples.With 10 relations and 100 entities, a three-relation rule can have 10^3 structures and up to 10^15 supports.
  • IterE framework: IterE learns embeddings and rules together so rules can add triples for sparse entities while embeddings convert rule learning from graph search into vector calculations.The framework is designed to make the strengths of the two approaches complement their respective difficulties.
  • IterE framework: IterE contains embedding learning, axiom induction, and axiom injection, with embeddings trained on original triples and rule-inferred triples.These components are conducted iteratively during training, and axiom injection uses deductive rule groundings to add information about sparse entities.
  • Evaluation: Experiments report better link prediction and high-quality rule learning, supporting mutual benefits between embedding and rule learning.The evaluation examines sparse embedding quality, prediction, rule-learning efficiency and quality, and iterative training effects.

2 PRELIMINARIES

The preliminaries define knowledge graphs, embedding assumptions, rules, rule injection, and OWL2 axioms. IterE uses these foundations to select semantically meaningful rule structures and incorporate inferred information into embedding learning.

  • Knowledge graph embedding: A knowledge graph consists of entities, relations, and triples written as (subject entity, relation, object entity).A triple is represented as (s,r,o), with s and o entities and r a relation.
  • Knowledge graph embedding: Knowledge graph embeddings represent entities and relations in continuous vector spaces and score the likelihood that a triple is true.Different score functions follow different vector-space assumptions.
  • Knowledge graph embedding: The translation-based assumption models true triples with vs + vr close to vo, while the linear-map assumption models vsMr close to vo.IterE adopts the linear-map assumption because it supports meaningful rule conclusions through relation embeddings.
  • Rules learning: A rule has a head and a conjunction of positive or negative atoms in its body; replacing variables with concrete entities produces a grounding.A grounding whose triples all exist in the knowledge graph is a support for the rule, and learned rules receive confidence scores.
  • Rules learning: Rule injection incorporates logical rules into another learning system by adding regularizers or constraints to learned representations.IterE uses propositionalization to obtain new information about sparse entities through rules.
  • OWL 2 Web Ontology Language Axioms: IterE selects seven OWL2 object property expression axiom types because they involve binary relations and can infer new triples.The selected axioms are translated into rule forms that guide the structures of learned rules; unselected axioms mainly support consistency checking.

3 METHOD

IterE jointly learns embeddings and axioms in an iterative framework, using inferred triples to improve embeddings and embeddings to guide efficient axiom induction.

  • Framework: IterE alternates embedding learning, axiom induction, and axiom injection to make embedding and rule learning complement each other.The framework can be applied to knowledge graph embedding methods based on the linear map assumption.
  • Embedding Learning: Embedding learning uses existing triples, axiom-inferred triples, and randomly corrupted negative triples as labeled training inputs.Existing triples receive label 1, negative triples label 0, and inferred triples receive their predicted truth values.
  • Axiom Injection: Axiom injection adds triples inferred from high-scoring axioms about sparse entities, then returns the updated graph to embedding learning.A maximum inferred-triple limit is used to avoid distribution shifts and unstable embedding training.
  • Axiom Induction: Axiom induction generates a pruned pool of candidate axioms and scores them from relation embeddings using rule conclusions under the linear map assumption.The method first generates possible axioms, then predicts each axiom’s confidence score from relation-embedding calculations.
  • Axiom Pool Generation: The pruning strategy traverses axiom templates, randomly selects k related triples to complete partial axioms, and retains axioms with more than one support.The choice of k balances search-space growth against coverage of highly possible axioms; with p = 0.5 and t = 0.95, the example upper bound is 6.
  • Axiom Pool Generation: Axiom scores are calculated after the candidate pool is generated, so the fixed pool only needs to be generated once during learning.This separates expensive candidate generation from repeated embedding-based score calculation.

4 EXPERIMENT

The experiments test whether axioms improve sparse-entity embeddings and whether embeddings make rule learning more efficient and improve learned-rule quality.

  • Embedding Evaluation: The first experiment evaluates whether axioms improve sparse-entity embedding quality using link prediction.Link prediction quality is evaluated with the mean reciprocal rank metric described for entity results.
  • Rule Evaluation: The second experiment evaluates whether embeddings reduce rule-learning difficulty through learning efficiency and learned-rule quality.The evaluation considers learning time and the number and percentage of high-quality rules.
  • Overall Evaluation: The experiments examine whether embedding learning and rule learning benefit each other during learning and prediction.This is the paper’s stated cross-component evaluation goal.

4.1 Dataset

Experiments use sparse variants of four established knowledge graph datasets, retaining validation and test triples involving sparse entities to evaluate link prediction in sparse settings.

  • Datasets: Four datasets—WN18-sparse, WN18RR-sparse, FB15k-sparse, and FB15k-237-sparse—are used for evaluation.They derive from commonly used WordNet and Freebase benchmarks.
  • Sparse construction: Sparse variants retain validation and test triples containing at least one sparse entity.This construction targets link prediction involving sparse entities.
  • Datasets: The datasets’ statistics are reported in Table 3.

4.2 Training Details

Training uses fixed embedding and axiom-induction settings, iterating between embedding learning and axiom processing under dataset-specific limits and thresholds.

  • Embedding learning: Embeddings use six negative samples, diagonal relation matrices with d scalars, and uniform initialization U(−0.1, 0.1).
  • Axiom induction: Axiom induction uses p = 0.5, t = 0.95, and k = 6, with larger axiom pools for datasets containing more diverse relations.
  • Axiom injection: Axiom injection selects axioms above dataset-specific score thresholds and caps inferred triples to avoid noise, distribution shifts, and unstable embedding training.
  • Iterative training: Each iteration trains embeddings for 10 epochs, then performs axiom induction and injection; maximum iterations are 10 or 50 depending on the dataset.
  • Hyperparameters: Final hyperparameters use embedding dimension d = 200, with dataset-specific λ, θ, and m values.The selected settings differ across WN18-sparse, WN18RR-sparse, FB15k-sparse, and FB15k-237-sparse.

4.3 Embedding Evaluation

Embedding quality is evaluated through filtered and raw link prediction, comparing IterE and IterE+axioms with established embedding baselines on sparse knowledge graphs.

  • Evaluation setup: Link prediction evaluates missing subject or object entities using MRR and Hit@n, where higher values indicate better results.
  • Evaluation setup: Subject and object candidates are ranked by their triple scores, and the true entity’s rank forms the prediction result.
  • Evaluation setup: Filtered evaluation removes known true triples from candidate rankings, whereas raw evaluation performs no filtering.
  • Baselines: TransE, DistMult, ComplEx, and ANALOGY serve as embedding baselines.
  • Results: IterE is competitive with ANALOGY and outperforms baselines on WN18RR-sparse and FB15k-237-sparse, while slightly improving on the other datasets.
  • Results: IterE+axioms improves over IterE on all datasets, especially FB15k-237-sparse, showing additional value from deductive predictions for sparse entities.

4.4 Rule Evaluation

Rule evaluation compares IterE with AMIE+ on learning efficiency and rule quality, finding that embedding-based pruning yields faster learning and more high-quality rules.

  • Evaluation metrics: Rule learning is evaluated by learning time, high-quality rule count and percentage, and head coverage.
  • Efficiency: IterE learns rules more efficiently than AMIE+, costing 10 times less on FB15k-sparse and FB15k-237-sparse.
  • Efficiency: On FB15k-237-sparse, axiom pool generation takes 4.55 of IterE’s 4.72 seconds, while axiom score calculation takes 0.17 seconds.
  • Rule quality: IterE generates more high-quality rules and a higher percentage than AMIE+ on every dataset.
  • Threshold analysis: At threshold 0.9, FB15k-sparse selects 23.4% of axioms while covering 46.4% of high-quality axioms; FB15k-237-sparse selects 53.9% and covers 76.5%.
  • Threshold analysis: The WN18-sparse and WN18RR-sparse threshold results are less obvious because these datasets contain few relations and yield limited learned rules.
  • Conclusion: Overall, embeddings help reduce rule-search space while improving rule quality and embedding-based reliability scores.

4.5 Iterative learning

Iterative training improves link prediction while injecting additional triples into embedding learning. The changing number of injected triples also indicates that embedding learning affects subsequent axiom learning.

  • Iterative learning: The number of triples injected into embedding learning generally increases during training before becoming stable.
  • Iterative learning: Hit@10 and MRR generally improve as training iterations increase.The reported link prediction results become better over successive iterations.
  • Iterative learning: Fewer subOP and equivalentOP triples are injected in iteration 4 than iteration 3.The paper attributes this change to previously high-scoring axioms receiving lower scores in the next iteration.
  • Iterative learning: The authors conclude that iterative learning benefits both embedding quality and axiom learning.Embedding quality improves during training, while changing axiom scores show that embedding learning affects rule learning.

4.6 Case study

The case study shows how axioms infer triples involving sparse entities and inject them into embedding training. This improves sparse-entity prediction and can further improve results when axioms are used at prediction time.

  • Case study: IterE infers and injects triples involving sparse entities into embedding learning during training.The example triple about Jenny_McCarthy is inferred from a spouse relation and a type-of-union relation.
  • Case study: The Jenny_McCarthy subject prediction rank improves from 4199 with ANALOGY to 33 with IterE.
  • Case study: The object prediction rank remains 2 from ANALOGY to IterE, then improves to 1 with IterE plus axioms.
  • Case study: Adding axiom-inferred triples improves related sparse-entity predictions without hurting non-sparse entities in the reported examples.The paper links this to the deductive ability of axioms to ensure the truth value of triples involving sparse entities.

5 RELATED WORK

Related work covers embedding and rule learning, including approaches that use embeddings to guide rule learning. IterE differs by learning embeddings and rules together so that each contributes to the other's learning.

  • Embedding Learning: Knowledge graph embedding represents entities and relations in continuous vector spaces to preserve graph semantics.
  • Embedding Learning: Embedding methods may use descriptions, types, images, paths, or rules as additional information during learning.
  • Embedding Learning: Prior embedding methods with rules generally keep rule learning detached from embedding learning.
  • Rule learning: Prior rule-learning work studies multiple rule types, including Horn rules, closed path rules, predicate cycles, and semantic association rules.
  • Rule learning: Rule confidence is commonly calculated with standard or PCA confidence by searching for rule supports across the knowledge graph.
  • Rule learning: Some methods use embeddings to prune candidate rules, complete the graph, or score rules, whereas IterE learns embeddings and rules simultaneously.

6 CONCLUSION AND FUTURE WORK

The paper proposes IterE to iteratively learn embeddings and rules in one model, allowing their advantages to contribute to each other's learning. Future work will combine inductive and deductive reasoning and unify different reasoning types.

  • Conclusion: IterE iteratively learns embeddings and rules in one model to obtain mutual benefits between them.
  • Future work: Future work will investigate combining inductive and deductive reasoning and developing models that unify different kinds of reasoning.
Loading 1903.08948v1…