PaperlayerView exact revision on arXiv

Source-linked AI summary

Beta Embeddings for Multi-Hop Logical Reasoning in Knowledge Graphs

Hongyu Ren, Jure Leskovec

arXiv:2010.11465v1cs.AIcs.DBcs.LG

TL;DR

Large, incomplete knowledge graphs make multi-hop FOL reasoning difficult, and prior embedding methods omit negation and do not naturally model uncertainty. BetaE uses bounded-support Beta distributions with probabilistic logical operators to answer arbitrary FOL queries. It reports up to 25.4% relative accuracy improvement and accurate negation-query answering across incomplete KGs.

  • Problem

    Large and incomplete KGs challenge multi-hop FOL reasoning, while prior methods support only a subset of operators, especially excluding negation, and do not naturally model uncertainty.

  • Method

    BetaE embeds entities and queries as Beta distributions on [0, 1] and applies neural operators for projection, intersection, negation, and disjunction.

  • Results

    Up to 25.4% relative accuracy improvement is reported, and BetaE accurately answers arbitrary FOL queries containing negation on large, incomplete KGs.

  • Takeaways & Limitations

    BetaE combines full-FOL query answering with probabilistic uncertainty modeling in incomplete knowledge graphs.

  • Takeaways & Limitations

    BetaE’s at-most-bimodal Beta embeddings cannot model some union-based queries.

Abstract

from arXiv · show

One of the fundamental problems in Artificial Intelligence is to perform complex multi-hop logical reasoning over the facts captured by a knowledge graph (KG). This problem is challenging, because KGs can be massive and incomplete. Recent approaches embed KG entities in a low dimensional space and then use these embeddings to find the answer entities. However, it has been an outstanding challenge of how to handle arbitrary first-order logic (FOL) queries as present methods are limited to only a subset of FOL operators. In particular, the negation operator is not supported. An additional limitation of present methods is also that they cannot naturally model uncertainty. Here, we present BetaE, a probabilistic embedding framework for answering arbitrary FOL queries over KGs. BetaE is the first method that can handle a complete set of first-order logical operations: conjunction ($\wedge$), disjunction ($\vee$), and negation ($\neg$). A key insight of BetaE is to use probabilistic distributions with bounded support, specifically the Beta distribution, and embed queries/entities as distributions, which as a consequence allows us to also faithfully model uncertainty. Logical operations are performed in the embedding space by neural operators over the probabilistic embeddings. We demonstrate the performance of BetaE on answering arbitrary FOL queries on three large, incomplete KGs. While being more general, BetaE also increases relative performance by up to 25.4% over the current state-of-the-art KG reasoning methods that can only handle conjunctive queries without negation.

1 Introduction

KG reasoning seeks answers to complex FOL queries despite large, incomplete graphs. BetaE represents queries and entities as Beta distributions, supports the full set of FOL operators, and reports improved performance over less expressive methods.

  • Motivation: Knowledge-graph reasoning answers FOL queries using existential quantification, conjunction, disjunction, and negation over noisy, incomplete graphs.Real-world KGs can be large-scale, noisy, and incomplete.
  • Challenges: Multi-hop traversal is computationally difficult because query paths can cause exponential growth in time and space, while missing edges can make answers unreachable.Embedding methods avoid tracking all intermediate entities and can use nearest-neighbor search.
  • Limitations of prior work: Prior embedding approaches support only existential positive FOL queries and generally cannot model negation because complements of their closed geometric regions are not closed regions.These methods typically represent queries as points or boxes in Euclidean space.
  • BetaE: BetaE embeds entities and queries as Beta distributions on [0, 1], using neural operators that support existential quantification, conjunction, disjunction, and negation.The bounded support permits complement modeling by reversing high- and low-density regions, while distribution parameters represent uncertainty.
  • Results: Up to 25.4% relative accuracy improvement is reported for arbitrary conjunctive queries, while BetaE also accurately answers FOL queries containing negation.Experiments use standard KG datasets and compare with methods limited to EPFO queries.

2 Related Work

Prior KG embedding work addresses missing edges and multi-hop reasoning, but query-answering methods cover only a subset of FOL. BetaE extends probabilistic embedding to arbitrary FOL queries while targeting uncertainty in multi-hop reasoning.

  • Prior approaches: Earlier KG embedding methods implicitly impute missing edges and embed logical queries as geometric shapes for iterative reasoning.Embedding-based execution avoids tracking every intermediate entity and supports nearest-neighbor answer retrieval.
  • Uncertainty modeling: Earlier uncertainty-aware KG models use Gaussian or mixture distributions mainly for link prediction, leaving their generalization to multi-hop logical reasoning unclear.BetaE instead aims to learn probabilistic embeddings for multi-hop reasoning with logical operators.
  • Scope of BetaE: Existing methods for answering multi-hop logical queries model only a subset of FOL, whereas BetaE uses probabilistic embeddings for arbitrary FOL queries.Related work also includes rule- and path-based methods for improving link prediction.

3 Preliminaries

FOL queries are represented as computation graphs whose nodes denote entity sets or distributions and whose edges apply logical transformations. The framework defines projection, intersection, complement, and a bounded-support Beta embedding for these operations.

  • Knowledge graphs: A KG consists of entities V and relation types R, with each relation represented as a directed binary function over entity pairs.The graph is written G = (V, R).
  • FOL queries: Valid queries use existential quantification, conjunction, disjunction, and negation, and are represented in disjunctive normal form as disjunctions of conjunctions.A query contains anchor entities, existentially quantified variables, and one target variable.
  • Computation graph: A computation graph represents atomic formulas with relation projection, merges branches by intersection, and transforms negation by complement; its root denotes the answer entities.Each node represents a distribution over a set of KG entities and each edge applies a logical transformation.
  • Logical operations: Relation projection maps a set S through relation r to adjacent entities ∪v∈S A_r(v), while intersection combines entity sets.The intersection is ∩_i S_i.
  • Logical operations: Negation maps S ⊆ V to its complement V \ S, and disjunction can be represented through intersection and complement using De Morgan’s laws.The computation graph therefore does not require a separate union operator.
  • Limitation and scope: Symbolic traversal yields entities satisfying the query but cannot handle noisy or missing KG edges, motivating probabilistic embeddings for scalable incomplete-graph reasoning.The paper excludes universal quantification because it is described as inapplicable to real-world KGs.

4 Probabilistic Embeddings for Logical Reasoning

BETAE represents entities and queries as bounded-support Beta distributions, then applies probabilistic logical operators to support arbitrary FOL reasoning while modeling uncertainty. Its fixed-size distributional representations and scalable inference address large, incomplete KGs, with union remaining theoretically limited.

  • 4.1 Beta Embeddings for Entities and Queries: BETAE embeds entities and queries as high-dimensional collections of independent Beta distributions on [0, 1].Learnable parameters are assigned to entity embeddings, while query embeddings are computed by applying probabilistic operators along the query computation graph.
  • 4.2 Probabilistic Logical Operators: The framework defines relation projection, intersection, and negation operators over Beta embeddings; union is implemented through intersection and complement.Each operator transforms one or more Beta embeddings into a new Beta embedding, enabling arbitrary combinations of logical operations.
  • 4.2 Probabilistic Logical Operators: Relation projection maps an input Beta embedding to a fixed-size embedding for entities reachable through a relation, making potentially large result sets scalable to represent.A relation-specific multilayer perceptron performs the transformation, and the target distribution covers the relation-traversed entity set.
  • 4.2 Probabilistic Logical Operators: Weighted PDF products implement intersection, with learned attention weights producing a normalized Beta embedding whose parameters are weighted combinations of the inputs.The operator exhibits zero-forcing behavior, so its effective support approximates the intersection of the input supports; closure preserves fixed representation complexity.
  • 4.2 Probabilistic Logical Operators: Negation reciprocates Beta shape parameters, reversing high- and low-density regions while satisfying double-negation and repeated-intersection properties.The resulting operator is closed within the Beta embedding space and follows key rules of real logical operations.
  • 4.3 Learning Beta Embeddings: BETAE ranks entities by summed per-dimension KL divergence and trains query embeddings to approach answers while separating randomly sampled negatives.The asymmetric divergence is chosen so query embeddings cover the modes of answer-entity embeddings; inference ranks entities using locality-sensitive hashing.
  • 4.3 Learning Beta Embeddings: BETAE's De Morgan modeling of union is at most bi-modal, so some theoretically possible union queries cannot be represented, although high dimensionality can alleviate the issue in practice.The method remains linear in the number of union operations, but does not represent every possible entity subset.

5 Experiments

BETAE is evaluated on arbitrary FOL queries over incomplete knowledge graphs, including negation, unseen query structures, and uncertainty-related tasks. It outperforms less general baselines on EPFO queries and captures query uncertainty through probabilistic embeddings.

  • Evaluation setup: BETAE is evaluated on three standard incomplete KGs, focusing on non-trivial answers that require imputing at least one missing edge.The evaluation uses FB15k, FB15k-237, and NELL995, ranking non-trivial answers with MRR and H@K metrics.
  • Evaluation setup: The benchmark includes five conjunctive structures, five structures with negation, and additional unseen structures for testing generalization.The unseen evaluation structures are ip, pi, 2u, and up.
  • EPFO queries: BETAE achieves 9.4%, 5.0%, and 7.4% relative MRR improvements over Q2B on FB15k, FB15k-237, and NELL995, respectively.On EPFO queries, BETAE performs better than both baselines across all three datasets.
  • Disjunction modeling: BETAE’s DNF modeling slightly outperforms De Morgan modeling, while De Morgan modeling generalizes well despite not being trained on 2u and up queries.Unlike the baselines, BETAE can use both approaches because it supports negation.
  • Queries with negation: BETAE handles arbitrary FOL queries with negation and generalizes well despite negation-containing training queries being substantially less frequent.The number of several negation query types during training is reported as 10 times smaller than the number of conjunctive queries.
  • Modeling uncertainty: BETAE achieves up to 77% better correlation than Q2B between embedding uncertainty and answer-set cardinality.For BETAE, uncertainty is represented by differential entropy; for Q2B, it is represented by box size, using Spearman and Pearson correlations.
  • Modeling uncertainty: Using differential entropy, BETAE classifies queries with and without answers on NELL with an ROC-AUC score of 0.844.The evaluation uses 4,000 queries without answers and 4,000 queries with more than five answers for each of 12 query structures.

6 Conclusion

The paper concludes that BETAE embeds queries into Beta distributions using probabilistic logical operators executed along computation graphs. It reports scalable handling of arbitrary logical queries, improved performance over less general methods, and effective uncertainty modeling.

  • Conclusion: BETAE embeds queries into Beta distributions and applies probabilistic logical operators by following each query’s computation graph.The approach is presented as scalable for multi-hop reasoning over knowledge graphs.
  • Conclusion: Experiments show that BETAE outperforms prior methods on arbitrary logical queries while modeling query uncertainty.The prior methods handle only a subset of first-order logic.

Broader Impact

BETAE is presented as a method that handles all logical operators for multi-hop reasoning over large heterogeneous KGs. The paper also identifies risks from random or adversarially manipulated graph structure.

  • BETAE handles all logical operators in large heterogeneous KGs.The paper states this expands the scalability and capability of multi-hop reasoning over real-world KGs and heterogeneous networks.
  • Random or adversarially manipulated KGs may lead BETAE to make undesirable predictions.The authors note that such manipulation can deteriorate embedding-based methods and potentially mislead users.

A Proof for Proposition 1

The proposition establishes fixed-point behavior for probabilistic negation and idempotence of probabilistic intersection. Its proof follows directly from how the two operators transform Beta-distribution parameters, while De Morgan and DNF representations can create exponential query growth.

  • Applying probabilistic negation twice returns the original Beta embedding: N(N(S)) = S.The negation operator takes reciprocal parameters, so applying it twice recovers the input.
  • Intersecting identical Beta embeddings returns that same embedding: I({S, S, . . . , S}) = S.The intersection operator uses a weighted product of PDFs, with output parameters given by linear interpolation of the inputs.
  • DNF conversion can create exponentially many atomic formulas for some FOL queries.The example (q11 ∨q12) ∧(q21 ∨q22) · · · ∧(qn1 ∨qn2) produces 2^n formulas in DNF.

C Query Generation and Statistics

The evaluation queries are generated from established query structures, with additional structures for realistic negation cases. Dataset statistics and query-generation counts are reported alongside the KG splits and answer-count statistics.

  • Query generation: The benchmark starts from nine EPFO query structures and instantiates entities and relations by traversing each structure.Pre-order traversal assigns entities and relations, while post-order traversal completes the instantiated query representation.
  • Dataset and query statistics: Table 5 reports knowledge-graph dataset statistics and training, validation, and test edge splits.The generation procedure constructs corresponding training, validation, and test graphs for the three KGs.
  • Query generation: Five additional negation structures are derived from the nine EPFO structures, using negation together with intersection.The paper restricts negation-query derivation to structures containing intersection because this combination is described as realistic.

D Experimental Details

Experiments use PyTorch implementations with tuned hyperparameters for BETAE and two baselines. Each method is run for 300k iterations on a single NVIDIA GeForce RTX 2080 TI GPU, with settings documented in Table 8.

  • Implementation: The experiments implement BETAE and baselines GQE and Q2B in PyTorch.The implementation uses the Q2B repository for the two baseline methods.
  • Hyperparameter tuning: Hyperparameters are tuned over embedding dimensions, learning rates, batch sizes, negative-sample sizes, margins, and BETAE projection structures.The searched embedding dimensions are 200, 400, and 800, while Table 8 lists the selected settings for each method.
  • Compute: Each method runs for 300k iterations on a single NVIDIA GeForce RTX 2080 TI GPU.This specifies the compute setting used for each single experiment.

E Additional Experimental Results

Additional experiments report BETAE’s performance on EPFO queries across standard and large-answer datasets, and evaluate how well its embeddings capture query uncertainty.

  • BETAE significantly improves MRR over two baselines across all three datasets for EPFO queries.The comparison is reported in Table 1.
  • BETAE remains better than both baselines on EPFO queries that may have more than 5,000 answers.These results are reported for the dataset proposed in.
  • BETAE’s learned embedding has a higher Pearson correlation with query answer counts than Q2B’s embedding.For BETAE, uncertainty is represented by differential entropy; Q2B uses box size.
  • Table 9 reports H@1 results for BETAE, Q2B, and GQE on EPFO queries involving existential quantification, conjunction, and disjunction.
  • Table 10 reports MRR results showing higher performance than Q2B and GQE on all three KGs.
Loading 2010.11465v1…