PaperlayerView exact revision on arXiv

Source-linked AI summary

Knowledge Graph Embedding with Iterative Guidance from Soft Rules

Shu Guo, Quan Wang, Lihong Wang, Bin Wang, Li Guo

arXiv:1711.11231v1cs.AI

TL;DR

Prior KG embedding methods often injected hard logic rules only once, leaving interactions between embedding learning and inference under-modeled and requiring laborious rule creation. RUGE iteratively predicts soft labels for unlabeled triples and rectifies embeddings using observed triples, inferred labels, and automatically extracted rules. On Freebase and YAGO link prediction, it consistently outperformed baselines, including one-time rule-injection methods, while soft rules with moderate confidence remained beneficial.

  • Problem

    Previous methods mainly used one-time hard-rule injection and did not model interactive embedding-learning and logical-inference processes, while soft rules were under-studied.

  • Method

    RUGE alternates soft-label prediction for unlabeled triples with embedding rectification using labeled triples, predicted soft labels, and automatically extracted soft rules.

  • Results

    RUGE significantly and consistently outperformed baselines on Freebase and YAGO link prediction, including one-time rule-injection methods.

  • Takeaways & Limitations

    Automatically extracted soft rules benefit KG embedding, including rules with moderate confidence, and iterative injection improves their utility.

  • Takeaways & Limitations

    RUGE restricts rules to Horn clauses whose conclusions contain a single atom and whose premises are conjunctions of atoms.

Abstract

from arXiv · show

Embedding knowledge graphs (KGs) into continuous vector spaces is a focus of current research. Combining such an embedding model with logic rules has recently attracted increasing attention. Most previous attempts made a one-time injection of logic rules, ignoring the interactive nature between embedding learning and logical inference. And they focused only on hard rules, which always hold with no exception and usually require extensive manual effort to create or validate. In this paper, we propose Rule-Guided Embedding (RUGE), a novel paradigm of KG embedding with iterative guidance from soft rules. RUGE enables an embedding model to learn simultaneously from 1) labeled triples that have been directly observed in a given KG, 2) unlabeled triples whose labels are going to be predicted iteratively, and 3) soft rules with various confidence levels extracted automatically from the KG. In the learning process, RUGE iteratively queries rules to obtain soft labels for unlabeled triples, and integrates such newly labeled triples to update the embedding model. Through this iterative procedure, knowledge embodied in logic rules may be better transferred into the learned embeddings. We evaluate RUGE in link prediction on Freebase and YAGO. Experimental results show that: 1) with rule knowledge injected iteratively, RUGE achieves significant and consistent improvements over state-of-the-art baselines; and 2) despite their uncertainties, automatically extracted soft rules are highly beneficial to KG embedding, even those with moderate confidence levels. The code and data used for this paper can be obtained from https://github.com/iieir-km/RUGE.

Introduction

RUGE addresses limitations of one-time, hard-rule injection by iteratively combining embedding learning with soft-rule inference. It learns from observed triples, iteratively labeled triples, and automatically extracted rules, improving link prediction on Freebase and YAGO.

  • Motivation: Knowledge graph embedding maps entities and relations into a low-dimensional continuous vector space while preserving graph structure.This simplifies manipulation and provides semantic information for downstream applications.
  • Limitations of prior work: Earlier joint approaches injected logic rules once and did not model interactions between embedding learning and logical inference.The paper argues that iterative refinement can use predictions to infer facts and inferred facts to improve embeddings.
  • Soft rules: Soft rules encode likely but non-necessary relationships, can be extracted automatically, and were insufficiently studied by previous methods.Their confidence levels represent uncertainty rather than universal validity.
  • RUGE framework: RUGE alternates soft-label prediction for unlabeled triples with embedding rectification using labeled and newly labeled triples.The framework simultaneously uses observed triples, unlabeled triples, and automatically extracted soft rules with different confidence levels.
  • Results: RUGE significantly and consistently improves over state-of-the-art baselines on link prediction across Freebase and YAGO.The reported gains are attributed to iterative rule injection and include benefits from automatically extracted soft rules, even at moderate confidence levels.

Related Work

Related work combines KG embeddings with logic rules, relation paths, or broader distributed-representation methods. RUGE differs by iteratively injecting rule knowledge and handling soft rules.

  • KG embedding: KG embedding research develops translation-based, compositional, and neural-network techniques for representing entities and relations.These methods learn distributed representations for knowledge-graph components.
  • Logic-rule integration: Some prior KG systems use logic rules to refine embedding predictions, but their rules do not improve the learned embeddings.Other methods jointly learn from triples and propositionalized FOL rules, while lifted injection reduces propositionalization cost.
  • Iterative injection: Relation-path approaches incorporate path-based logical information in a one-time manner, whereas RUGE injects rule knowledge iteratively and handles soft rules.This distinction concerns how logical information interacts with embedding learning over time.
  • Related representation learning: Outside KGs, prior work injects ontological or first-order logic knowledge into word embeddings, order embeddings, and neural networks.These studies demonstrate that logic rules can enhance distributed representation learning in other settings.

Rule-Guided Knowledge Graph Embedding

RUGE jointly learns from observed triples, rule-inferred unlabeled triples, and automatically extracted soft rules through alternating soft-label prediction and embedding rectification. This iterative process transfers rule knowledge into embeddings while retaining efficient, flexible training.

  • Learning Resources: RUGE learns simultaneously from labeled triples, unlabeled triples, and soft rules with different confidence levels.Unlabeled triples are rule conclusions that are not directly observed but may be inferred with high probability.
  • Learning Resources: Soft rules are propositionalized into valid groundings whose premises are observed triples and whose unobserved conclusions form the unlabeled training set.The framework restricts rules to Horn clauses with conjunctive premises and a single-atom conclusion.
  • Modeling Triples and Rules: RUGE scores triples with ComplEx embeddings and maps each score to a continuous truth value used by both embedding learning and rule reasoning.Entities and relations are represented as complex-valued vectors, and the score uses a multi-linear dot product.
  • Soft Label Prediction: Soft-label prediction projects current embedding truth values onto rule-constrained labels, balancing fidelity to embeddings with satisfaction of rules at their confidence levels.Higher-confidence rules impose less tolerance for constraint violations, and the resulting optimization problem is convex.
  • Embedding Rectification: Embedding rectification updates the embeddings using observed triples with hard labels and inferred triples with soft labels, while cross-entropy and L2 regularization guide learning.The updated embeddings are intended to remain compatible with labeled triples while absorbing rule knowledge carried by unlabeled triples.
  • Iterative Learning Procedure: Mini-batch alternation captures interaction between inference and representation learning, while the method remains nearly as efficient per iteration as ComplEx when unlabeled batches and inner epochs are small.Rule mining and propositionalization add one-time preprocessing costs before training.

Experiments

RUGE is evaluated for link prediction on FB15K and YAGO37 using automatically extracted Horn-clause rules, with comparisons against basic and one-time rule-injection baselines. It significantly outperforms these baselines while remaining relatively efficient and benefiting from a broad range of soft-rule confidence thresholds.

  • Experimental Setup: The evaluation uses link prediction on FB15K and YAGO37, with entities predicted after replacing either the head or tail of each test triple.Performance is reported using MRR, MED, and HITS@N under the standard filtered ranking protocol.
  • Datasets and Rule Extraction: 454 rules are extracted from FB15K and 16 from YAGO37 using AMIE+ with rule length at most 2 and confidence at least 0.8.The resulting valid groundings number 96,724 on FB15K and 72,670 on YAGO37, producing 74,707 and 69,680 unlabeled triples, respectively.
  • Link Prediction Results: RUGE significantly and consistently outperforms basic embedding models and one-time rule-injection baselines on FB15K and YAGO37 across all reported metrics.The comparison includes TransE, DistMult, HolE, ComplEx, PTransE, and KALE.
  • Link Prediction Results: 11%/18% improvement in MRR/HITS@1 over ComplEx on FB15K and 3%/6% on YAGO37.The improvements are larger on FB15K, which provides more relations and extracted rules.
  • Influence of Confidence Levels: 0.8 is the best confidence threshold on FB15K, while thresholds from 0.35 to 0.9 still outperform ComplEx by a large margin.Higher thresholds reduce the number of extracted rules, whereas lower thresholds may introduce less credible rules.
  • Comparison of Runtime: Training time per iteration increases from 11.4 to 14.1 seconds on FB15K and from 49.5 to 55.2 seconds on YAGO37.RUGE remains efficient despite integrating additional rules, and preprocessing requires much less time than PTransE.

Conclusion

RUGE learns entity and relation embeddings through iterative guidance from automatically extracted soft rules. On Freebase and YAGO, it improves link prediction over state-of-the-art baselines, including when rules have moderate confidence.

  • Conclusion: RUGE alternates soft-label prediction for unlabeled triples with embedding rectification using labeled and unlabeled triples.The model learns simultaneously from labeled triples, unlabeled triples, and soft rules with different confidence levels.
  • Conclusion: Link prediction results on Freebase and YAGO show significant and consistent improvements over state-of-the-art baselines.Automatically extracted soft rules remain beneficial even at moderate confidence levels.

Supplementary Material

The supplementary material identifies the paper's authors.

  • Supplementary Material: The paper is authored by Shu Guo, Quan Wang, Lihong Wang, Bin Wang, and Li Guo.

A Solving the Soft Label Prediction Problem

Soft label prediction assigns labels to unlabeled triples using current embeddings and grounded soft rules. The resulting optimization balances embedding-based truth values with rule consistency through slack penalties and has a convex, closed-form solution.

  • Problem Formulation: The procedure predicts a soft label s(xu) ∈ [0, 1] for each unlabeled triple using current embeddings and all rule groundings.The soft labels are optimized jointly over the unlabeled triples.
  • Optimization Problem: The optimization constrains weighted rule violations with nonnegative slack variables and bounds every soft label between 0 and 1.The rule confidence λp scales the violation constraint, while ξpq represents slack.
  • Optimization Problem: The optimization is convex and has closed-form solutions.This provides an analytically solvable soft-label prediction stage for the iterative procedure.

Proof of Convexity

The optimization problem is convex because its objective is separately quadratic in each s(xu) and linear in each ξpq, while all constraints are linear.

  • The objective function is quadratic with respect to each s(xu) and linear with respect to each ξpq.
  • Each valid grounding contains only one unlabeled triple, namely the conclusion triple, so its conditional truth value depends linearly on one s(xu).
  • Because the objective and constraints are convex-compatible, the whole optimization problem is convex.

Closed-Form Solutions

The optimization problem is rewritten into an equivalent form and solved by exploiting its separable quadratic structure under bounded truth-value constraints.

  • The optimization problem in Eq. (A-1) can be equivalently rewritten in another form.
  • The hinge operator [x]+ is defined as max(x, 0), and the constraints ensure π(gpq|S) remains at most 1.
  • Because each π(gpq|S) is linear in one s(xu), the resulting P is an upward parabola in each s(xu).
  • The optimal solutions are obtained by considering the bounds 0 ≤ s(xu) ≤ 1, with truncation enforcing solutions to remain within [0, 1].
Loading 1711.11231v1…