PaperlayerView exact revision on arXiv

Source-linked AI summary

BoxE: A Box Embedding Model for Knowledge Base Completion

Ralph Abboud, İsmail İlkan Ceylan, Thomas Lukasiewicz, Tommaso Salvatori

arXiv:2007.06267v2cs.AIcs.LG

TL;DR

Existing KBC embedding models face limits in expressiveness, inference patterns, higher-arity relations, and logical-rule integration. BoxE represents entities as points and relations as position-specific boxes, achieving full expressiveness, broad rule support, and state-of-the-art performance across KGC and KBC settings.

  • Problem

    Existing KBC embedding models can be theoretically inexpressive and lack support for important inference patterns, higher-arity relations, and logical rules.

  • Method

    BoxE represents entities as points and each relation as one hyper-rectangle per arity position, while supporting injection of rich logical-rule languages.

  • Results

    BoxE achieves state-of-the-art performance across knowledge graph completion and knowledge base completion tasks, is fully expressive, and rule injection improves KBC performance.

  • Takeaways & Limitations

    BoxE combines theoretical expressiveness, higher-arity support, rule integration, and inductive capacity in a single model for KBC.

  • Takeaways & Limitations

    Rule injection can hinder performance when the underlying model makes many false predictions, because rule application propagates additional false conclusions.

Abstract

from arXiv · show

Knowledge base completion (KBC) aims to automatically infer missing facts by exploiting information already present in a knowledge base (KB). A promising approach for KBC is to embed knowledge into latent spaces and make predictions from learned embeddings. However, existing embedding models are subject to at least one of the following limitations: (1) theoretical inexpressivity, (2) lack of support for prominent inference patterns (e.g., hierarchies), (3) lack of support for KBC over higher-arity relations, and (4) lack of support for incorporating logical rules. Here, we propose a spatio-translational embedding model, called BoxE, that simultaneously addresses all these limitations. BoxE embeds entities as points, and relations as a set of hyper-rectangles (or boxes), which spatially characterize basic logical properties. This seemingly simple abstraction yields a fully expressive model offering a natural encoding for many desired logical properties. BoxE can both capture and inject rules from rich classes of rule languages, going well beyond individual inference patterns. By design, BoxE naturally applies to higher-arity KBs. We conduct a detailed experimental analysis, and show that BoxE achieves state-of-the-art performance, both on benchmark knowledge graphs and on more general KBs, and we empirically show the power of integrating logical rules.

1 Introduction

Knowledge base completion addresses incomplete knowledge bases by predicting missing facts from learned entity and relation embeddings. BoxE is introduced to overcome existing models’ limits in expressiveness, inference patterns, relation arity, and logical-rule integration.

  • Motivation: Knowledge bases contain many missing facts, motivating models that infer plausible facts from known information.Freebase, for example, has 71% of individuals lacking a connection to a place of birth.
  • Limitations: Existing KBC models can be theoretically inexpressive, fail to capture hierarchies, and primarily target binary knowledge graphs.These limitations also make logical-rule injection difficult and restrict support for higher-arity relations.
  • BoxE: BoxE represents relations as explicit regions and entities as points, scoring facts by entity positions relative to relation boxes.This spatial representation naturally exposes properties such as relation subsumption and disjointness.
  • Contributions: BoxE achieves state-of-the-art performance across knowledge graph and knowledge base completion tasks and is fully expressive.The paper presents full expressiveness as a first for translation-based models, to the authors’ knowledge.
  • Contributions: BoxE captures and injects rich logical rules, with rule injection significantly improving KBC performance on a subset of NELL.The paper separately analyzes generalized inference patterns and rule languages.

2 Knowledge Base Completion: Problem, Properties, and Evaluation

KBC predicts new facts from existing facts in a finite relational knowledge base, with knowledge graphs as the binary-relation special case. Evaluation ranks true facts against corrupted alternatives using MR, MRR, and Hits@K, while expressiveness and inference patterns characterize model capacity.

  • Definitions: A knowledge base is a finite set of facts over entities and relations, while a knowledge graph restricts all relations to arity two.Facts have the form r(e1, ..., en), and KG facts are triples r(eh, et).
  • Definitions: Knowledge base completion predicts new facts from existing facts, including facts with relations of varying arity.Knowledge graph completion is the binary-relation case of KBC.
  • Evaluation: Evaluation compares true test facts with corrupted facts formed by replacing an entity with one absent from the data splits.Models are optimized to rank true facts above corrupted facts.
  • Evaluation: MR is average rank, MRR is average inverse rank, and Hits@K is the proportion of facts ranked within K.These metrics quantify ranking quality against corrupted counterparts.
  • Properties: A fully expressive model can classify any specified disjoint sets of true and false facts, but expressiveness does not guarantee inductive generalization.Non-fully-expressive models may underfit, whereas fully expressive models may memorize.
  • Properties: Inference patterns are logical properties whose learned application enables principled predictions from existing facts.Symmetry, for example, supports predicting r(e2, e1) when r(e1, e2) holds.

3 Related Work

Prior KBC methods include translational, bilinear, and region-based models, with different trade-offs in expressiveness, inference-pattern support, and relation arity. Existing approaches generally address only subsets of these requirements, especially for higher-arity or different-arity knowledge bases.

  • Scope: Neural models are excluded from the related-work comparison because their expressiveness and inductive capacity are difficult to analyze.The paper focuses its comparison on analyzable embedding approaches.
  • Translational models: Translational models represent entities as points and relations as translations, but TransE lacks full expressiveness and cannot model several relation patterns or higher-arity facts.Its limitations include one-to-many, many-to-one, many-to-many, symmetric relations, and binary-only support.
  • Bilinear models: Bilinear models represent relations through bilinear products, with variants differing in matrix structure and symmetry behavior.DistMult cannot capture non-symmetric relations, while ComplEx uses complex-valued diagonal matrices to capture anti-symmetry.
  • Higher-arity KBC: Higher-arity models extend several binary KGC architectures, but generalizations such as m-TuckER and GETD do not support relations with different arities.Other approaches use transformations or convolutions to address higher-arity completion.
  • Region-based models: Region-based models define spatial regions where properties such as class membership hold, supporting entity classification, hierarchies, and query-answer sets.Boxes represent sets of objects or answer regions in systems such as Query2Box.

4 Box Embeddings for Knowledge Base Completion

BoxE embeds entities with base positions and translational bumps, and represents each relation position with an axis-aligned box. Its dynamic embeddings and box-based scoring support higher-arity facts while allowing compact representation of complex fact configurations.

  • Representation: BoxE represents relations as axis-aligned d-dimensional boxes and entities as points in Euclidean space.Facts are evaluated by the positions of entity embeddings relative to relation boxes.
  • Representation: Each entity has a base vector and a translational bump that shifts co-occurring entities to fact-specific final embeddings.Thus, an entity can have different final embeddings relative to different facts.
  • Representation: An n-ary relation uses n boxes, one for each argument position, and a fact holds when each final entity embedding lies in its corresponding box.Unary relations have no translational bumps, so base and final embeddings coincide.
  • Representation: Translational bumps can compactly encode all configurations of the sample knowledge graph by forcing entity embeddings into or out of relation boxes.The example has 42 potential facts and 2^42 possible configurations.
  • Scoring function: BoxE’s distance function favors points inside target boxes, penalizes outside points, and incorporates box size into scoring.It uses low inside-box distances and stronger outside-box gradients, with continuity preserved by subtracting κ.
  • Scoring function: The scoring function sums L-x norms of the distances across all entity positions and relation boxes.This aggregates position-to-box compatibility over every argument of a fact.

5 Model Properties

BoxE is fully expressive and supports rich joint inference patterns through box configurations, while also allowing provable injection of positive logical rules. These properties provide stronger inductive capacity and rule interpretability than prior models.

  • Expressiveness: BoxE is fully expressive, requiring d = |E|n−1|R| dimensions and d = |E||R| for knowledge graphs.The proof uses translational bumps to alter one fact while preserving the correctness of others.
  • Expressiveness: BoxE is the first translation-based model proved to be fully expressive.
  • Inference patterns and generalizations: BoxE captures generalized inference patterns by representing relations with box configurations, including symmetry, inverses, hierarchies, intersections, anti-symmetry, and mutual exclusion.Symmetry uses equal relation boxes, hierarchies use box subsumption, and anti-symmetry and mutual exclusion use disjointness.
  • Inference patterns and generalizations: BoxE can capture any finite set of consistent rules combining inverse, symmetry, hierarchy, intersection, mutual exclusion, and anti-symmetry rules.This rule language strictly combines multiple rule types rather than restricting the model to one generalized inference pattern.
  • Interpretability: BoxE’s jointly captured rules can be read from its box configuration, supporting richer interpretability of learned behavior and scores.The paper connects stronger rule capturing directly with superior model interpretability.
  • Rule injection: BoxE can be injected with any finite set of rules from the positive language of inverse, symmetry, hierarchy, and intersection rules.Unlike several existing approaches, BoxE is described as explicitly and provably enforcing these rules through constrained embeddings.

6 Experimental Evaluation

BoxE is evaluated on binary KGC benchmarks, higher-arity KBC datasets, and rule injection, achieving competitive or state-of-the-art performance across these settings.

  • Evaluation scope: BoxE is evaluated on KGC, higher-arity KBC, and rule injection tasks.The experiments cover benchmark knowledge graphs, datasets with relations up to arity six, and SportsNELL ontology injection.
  • 6.1 Knowledge graph completion: BoxE is competitive across all three KGC benchmarks and state of the art on YAGO3-10.It performs best among translational models on FB15k-237, is less competitive with RotatE in WN18RR MRR, and significantly surpasses RotatE and TuckER on YAGO3-10.
  • 6.2 Higher-arity knowledge base completion: BoxE achieves state-of-the-art performance on both higher-arity datasets, JF17K and FB-AUTO.These datasets contain relations with arities up to 6 and 5, respectively, including facts with varying arities.
  • 6.2 Higher-arity knowledge base completion: BoxE’s higher-arity performance is attributed primarily to unique boxes for every relation-arity position.This structure represents entity sets at each position more naturally when relation arities vary.
  • 6.3 Rule injection: BoxE+RI significantly outperforms plain BoxE on both full and filtered SportsNELL evaluation sets.The filtered set excludes facts directly deducible from training facts through the ontology, testing the effect of rule injection on inductive capacity.
  • 6.3 Rule injection: Rule injection can hinder evaluation when poor predictions generate additional false positives through rule application.The paper therefore emphasizes combining rule injection with models that have strong inductive capacity and expressiveness.

7 Summary

BoxE combines theoretical expressiveness, inductive capacity, higher-arity support, rule injection, and strong empirical performance for KBC.

  • BoxE achieves state-of-the-art performance for knowledge graph completion and higher-arity and different-arity KGC.The paper also empirically validates rule injection as improving BoxE’s inductive bias and capacity.

Broader Impact

The work targets incomplete knowledge with automated inference based largely on interpretable logical patterns, while BoxE scoring scales linearly with relation arity.

  • BoxE predictions rely mostly on interpretable and explainable logical patterns for completing knowledge bases.The paper connects this interpretability with support for automated inference in application domains.
  • BoxE scoring runs in O(nd), implying linear scaling with the arity of relations in a knowledge base.The runtime follows from computing entity representations and distances across all relation positions.
  • BoxE requires (|E| + n|R|)d parameters for a knowledge base with |E| entities and |R| relations of arity n.The model stores two d-dimensional vectors per entity and two d-dimensional vectors per relation box.

B Proof of Theorem 5.1 (Full Expressiveness)

The proof establishes BoxE’s full expressiveness by changing one fact’s truth value while preserving every other fact, then extends the construction to arbitrary and non-uniform arities.

  • The induction step makes a selected true fact false by shifting one entity representation outside its relation box and modifying other embeddings and boxes.The construction applies dimension-specific bump and box changes.
  • The proof begins with a knowledge graph containing every possible fact as true, represented using zero entity and bump vectors and unit boxes.This supplies the induction base case for the full-expressiveness construction.
  • The construction preserves all other true facts after the selected fact is falsified.Head and tail box adjustments compensate for the induced changes in entity representations.
  • All false facts remain false after the induction step, so every fact configuration is expressible and BoxE is fully expressive.For knowledge graphs, the construction uses d = |E||R| dimensions.
  • For maximum arity n, full expressiveness requires d = |E|^(n−1)|R| dimensions, and the proof generalizes to higher-arity relations.Non-uniform arities are handled by adding parameters to lower-arity relations and basing correctness on the original facts.
  • The analysis studies generalized inference patterns as rule languages formed by unions of allowed rule types.The considered rule types include symmetry, anti-symmetry, inversion, composition, hierarchy, intersection, and mutual exclusion.

C.1 Proof of Theorem 5.2: BoxE

BoxE captures generalized inference patterns except composition, with a recursive box-growth procedure for intersections and broader limitations in competing models.

  • BoxE captures each generalized inference pattern except composition, which it cannot capture explicitly as an inference pattern.The paper separately analyzes BoxE’s ability to represent these logical structures.
  • Generalized intersection: The intersection procedure returns a valid BoxE configuration that captures exactly the provided patterns within their deductive closure.Recursive calls ensure that box growth does not violate previously captured rules.
  • Generalized intersection: Each box-growth operation strictly reduces the number of distinct boundaries, ensuring termination of the recursive intersection procedure.The resulting number of recursive calls is upper bounded by O(|R|^2 p log |R|).
  • BoxE limitation: BoxE’s translational bumps enable full expressiveness but prevent it from capturing composition because entity-specific bumps are unknown for abstract variables.Other BoxE rules remain capturable because corresponding relation boxes receive identical bumps for the same variable.
  • Translational models: Translational models cannot capture hierarchies, and they fail to capture generalized intersections despite capturing some other patterns.The hierarchy limitation follows from the equal-radius decision regions used by TransE and RotatE.
  • Bilinear models: Bilinear models have pattern-specific limitations: TuckER fails on intersections and generalized mutual exclusion, while DistMult and ComplEx cannot capture composition.Other capabilities vary across symmetry, anti-symmetry, inversion, and mutual exclusion.

D Proof of Theorem 5.3 (Inference Patterns as Rule Languages)

The proof constructs BoxE configurations that jointly capture consistent rule sets spanning symmetry, inversion, anti-symmetry, hierarchy, intersection, and mutual exclusion. Individual generalized patterns require fewer dimensions, while capturing their joint language requires d = O(|R|^2) dimensions.

  • Step 1: Defining the relation intersection graph: Symmetry and inversion rules are encoded through shared relation-box nodes, making the corresponding boxes identical.Symmetry shares a relation’s head and tail nodes; inversion shares the appropriate head and tail nodes across relations.
  • Step 3: Hierarchies and intersections: Hierarchy and intersection rules are added by computing their deductive closure and encoding the resulting constraints in the relation intersection graph.The construction preserves the symmetry and inversion encodings while extending the graph with hierarchy and intersection edges.
  • Step 2: Anti-symmetry: Anti-symmetry is captured by adding a disjointness dimension whose head and tail box ranges do not intersect.Subsequent rule-based box growth preserves this disjointness under the consistency assumption.
  • Step 4: Mutual exclusion: Mutual exclusion rules are captured by dedicating one additional dimension to each rule and recursively preserving hierarchy and intersection constraints.Consistency ensures that these additional dimensions do not introduce contradictions with previously captured rules.
  • Dimensionality: Individual generalized patterns can require constant dimensions, while generalized intersection requires O(|R| log(|R|)) dimensions.The larger joint requirement reflects the added complexity of capturing multiple generalized patterns together, including possible cycles.

E Proof of Theorem 5.4 (Rule Injection)

The rule-injection proof modifies a randomly initialized BoxE configuration by enforcing symmetry and inversion through box sharing, then reconfiguring boxes for hierarchy and intersection rules. This injection is guaranteed to preserve the encoded rules and runs in near-quadratic time in the number of relations.

  • Rule injection: Arbitrary sets of hierarchy, intersection, symmetry, and inversion rules can be injected into BoxE.The proof adapts the generalized inference-pattern construction to a concrete randomly initialized box configuration.
  • Rule injection: Symmetry and inversion rules are injected through box sharing, with symmetry setting r(1) = r(2) and inversion sharing corresponding boxes.The sharing operation can be performed in linear time in the number of symmetry and inversion rules.
  • Rule injection: The box reconfiguration procedure enforces hierarchy and intersection rules and their deductive closure while maintaining box sharing.Maintaining box sharing preserves the already injected symmetry and inversion rules.
  • Complexity: The worst-case runtime for injecting all hierarchy and intersection rules is O(|R|d), independent of the number of such rules.Under d = O(|R| log(|R|)), the procedure runs in near-quadratic time with respect to |R|.
  • Complexity: Rule injection for symmetry, inversion, hierarchy, and intersection rules is therefore efficiently supported by BoxE.The stated bound is near-quadratic in |R|, which the passage notes is typically small.

F.2 Hyperparameter settings for BoxE experiments

The experiments tune BoxE across standard, higher-arity, rule-injection, and dimensionality settings, using Adam with negative sampling and reporting benchmark comparisons. Fixed box sizes were detrimental, while strong performance remained attainable at restricted dimensionality.

  • Hyperparameter settings: BoxE experiments use Adam to optimize negative-sampling loss, with tuning over learning rate, dimensionality, margin, distance order, and negative examples.Points and boxes are projected into the bounded hypercube [−1, 1]^d using tanh.
  • Hyperparameter settings: Inverse-relation data augmentation was only marginally beneficial on YAGO3-10, yielding a slightly improved MR.The augmentation adds a distinct inverse fact r′(e2, e1) for every fact r(e1, e2).
  • Box sizing: Fixed or softly bounded box sizes yielded no improvements and were mostly detrimental to performance.The experiments further indicate that box-size variability is important for predictive performance.
  • Dimensionality: At d = 50, BoxE maintains very strong YAGO3-10 validation performance and rivals RotatE with uniform negative sampling.At d = 100, it performs near-optimally and is already state-of-the-art on YAGO3-10.

G.2 Box volume information for BoxE following training on YAGO3-10

After training on YAGO3-10, BoxE’s relation-box volumes reflect relation popularity, implicit entity types, and relation cardinality patterns. Symmetric relations receive near-identically sized head and tail boxes, consistent with BoxE’s symmetry encoding.

  • Box volumes and relation properties: More popular relations tend to have larger relation boxes, consistent with boxes representing entity classes.The less popular hasWebsite relation has mean volume about 0.15 and occurs in 68 training facts.
  • Box volumes and relation properties: Box sizes also correlate with implicit entity types rather than relation popularity alone.playsFor has smaller boxes despite appearing over 300,000 times, whereas isLeaderOf has a tail-box volume exceeding 1 with fewer than 1,000 facts.
  • Box volumes and relation properties: Relative head and tail box sizes reflect relation cardinality: larger tail boxes suggest one-to-many relations, while larger head boxes suggest many-to-one relations.Similar head and tail sizes correspond to many-to-many or one-to-one relations.
  • Symmetry: Symmetric relations such as hasNeighbor and isMarriedTo have near-identically sized head and tail boxes.This matches the necessary condition that symmetric relations have identical head and tail boxes.
  • Interpretation: The volume patterns support BoxE’s interpretability for inference patterns, entity classes, and relation types.The passage contrasts these modeled properties with the capabilities of other models.
  • Rule injection: Injecting the SportsNELL ontology makes BoxE+RI reach peak performance within 500 epochs, while standard BoxE remains unconverged after 2000 epochs.The learning curves use MRR across the 2000 training epochs.
Loading 2007.06267v2…