PaperlayerView exact revision on arXiv

Source-linked AI summary

Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings

Hongyu Ren, Weihua Hu, Jure Leskovec

arXiv:2002.05969v2cs.LGcs.CLstat.ML

TL;DR

Complex logical queries over incomplete knowledge graphs require representing potentially large answer sets and supporting disjunction, which prior point-based methods do not adequately address. Query2Box uses box embeddings and DNF decomposition to handle arbitrary EPFO queries, achieving strong generalization and up to 25% relative improvement over state-of-the-art baselines. The paper also proves that direct single-embedding handling of arbitrary EPFO queries would require dimensionality proportional to the number of KG entities.

  • Problem

    Prior methods represent queries as single points and support only conjunction and existential quantification, leaving answer-set representation and disjunction unresolved.

  • Method

    Query2Box embeds conjunctive queries as boxes, transforms arbitrary EPFO queries into DNF, and represents each conjunctive component with an individual box.

  • Results

    Up to 25% relative improvement in accuracy over state-of-the-art baselines is reported across three KG benchmarks, including unseen query structures and union operations.

  • Takeaways & Limitations

    Query2Box provides scalable and accurate reasoning over all EPFO query types while modeling answer sets and extending conjunctive-query embedding methods to disjunction.

  • Takeaways & Limitations

    Directly embedding arbitrary EPFO queries as single points or boxes requires query-embedding dimensionality proportional to the number of KG entities, making that approach non-scalable.

Abstract

from arXiv · show

Answering complex logical queries on large-scale incomplete knowledge graphs (KGs) is a fundamental yet challenging task. Recently, a promising approach to this problem has been to embed KG entities as well as the query into a vector space such that entities that answer the query are embedded close to the query. However, prior work models queries as single points in the vector space, which is problematic because a complex query represents a potentially large set of its answer entities, but it is unclear how such a set can be represented as a single point. Furthermore, prior work can only handle queries that use conjunctions ($\wedge$) and existential quantifiers ($\exists$). Handling queries with logical disjunctions ($\vee$) remains an open problem. Here we propose query2box, an embedding-based framework for reasoning over arbitrary queries with $\wedge$, $\vee$, and $\exists$ operators in massive and incomplete KGs. Our main insight is that queries can be embedded as boxes (i.e., hyper-rectangles), where a set of points inside the box corresponds to a set of answer entities of the query. We show that conjunctions can be naturally represented as intersections of boxes and also prove a negative result that handling disjunctions would require embedding with dimension proportional to the number of KG entities. However, we show that by transforming queries into a Disjunctive Normal Form, query2box is capable of handling arbitrary logical queries with $\wedge$, $\vee$, $\exists$ in a scalable manner. We demonstrate the effectiveness of query2box on three large KGs and show that query2box achieves up to 25% relative improvement over the state of the art.

1 INTRODUCTION

Query2Box addresses the limits of point-based query embeddings by representing query answer sets as boxes and handling arbitrary EPFO queries through DNF transformation. It targets scalable reasoning over incomplete knowledge graphs while retaining strong generalization and accuracy.

  • Motivation: Subgraph matching is exponential in query size and sensitive to missing relations, limiting its scalability and robustness on modern knowledge graphs.Vector-space query embedding reduces answering to nearest-entity retrieval and is more robust to missing relations.
  • Motivation: Prior query-embedding methods use single points, making answer sets and set intersections difficult to represent and excluding disjunctions from their supported query language.They handle conjunction and existential quantification but not disjunction.
  • Query2Box: Query2Box represents queries as axis-aligned hyper-rectangles, so enclosed points correspond to answer entities and conjunctions can be modeled through box intersections.The framework computes query embeddings through projection and intersection operations over embedded KG entities.
  • Query2Box: DNF transformation represents an EPFO query as a set of conjunctive-query boxes, enabling scalable handling of arbitrary combinations of conjunction, disjunction, and existential quantification.Each DNF conjunctive query is embedded separately, and the resulting boxes represent the disjunctive query.
  • Results: Up to 25% relative improvement in accuracy over state-of-the-art baselines is reported across EPFO query answering benchmarks.The evaluation covers three standard KG benchmarks and includes query structures unseen during training and union operations.

2 FURTHER RELATED WORK

Query2Box differs from related embedding work by applying box embeddings to logical reasoning over massive heterogeneous knowledge graphs. This extends tractable query handling beyond conjunctive queries while improving accuracy and generalization.

  • KG query embeddings: Query2Box extends KG embedding approaches from conjunctive queries to the broader class of Existential Positive First-order queries.EPFO queries include conjunction, disjunction, and existential quantification.
  • Structured embeddings: Unlike structured-embedding work that models individual entities and pairwise relations with geometric objects, Query2Box uses boxes for logical reasoning over knowledge graphs.Related methods use regions, densities, or orderings for structured representations.
  • Box embeddings: Although box embeddings have modeled ontology concepts and uncertainty, Query2Box applies them to logical reasoning in massive heterogeneous knowledge graphs.The distinction is the reasoning setting rather than box embeddings themselves.

3 QUERY2BOX: LOGICAL REASONING OVER KGS IN VECTOR SPACE

QUERY2BOX represents logical queries as boxes in a vector space and executes geometric operators over them to answer complex KG queries. It handles disjunction scalably by converting EPFO queries into DNF and aggregating the resulting conjunctive-query boxes.

  • Vector-space reasoning: QUERY2BOX learns entity embeddings and parameterized geometric operators, then executes a query’s computation graph in vector space to identify enclosed answer entities.Queries are processed from anchor nodes through projection and intersection operators until the target embedding is obtained.
  • Geometric operators: Projection expands and translates boxes, while intersection produces a smaller box inside the input boxes, matching the corresponding set operations.Projection follows relations from a set; intersection retains entities common to multiple sets.
  • Box embeddings: Boxes represent sets of entities as axis-aligned hyper-rectangles whose interiors can contain entity embeddings.Unlike point embeddings, boxes provide a region for modeling multiple active entities.
  • Handling disjunction: Theorem 1 shows that modeling arbitrary EPFO queries with a single embedding and distance threshold requires VC dimension at least M for M disjoint conjunctive-query answer sets.For real-world KGs, M can be approximately the number of entities; FB15k has M = 13,365 versus |V| = 14,951.
  • Handling disjunction: QUERY2BOX avoids this dimensionality barrier by transforming EPFO queries into DNF, reasoning over each conjunctive branch, and aggregating distances by the closest box.The computation graphs move union operations to the final step, and the branch computations can be parallelized.

4 EXPERIMENTS

The experiments evaluate QUERY2BOX on complex, incomplete-KG queries across three benchmarks, emphasizing missing-edge answers, varied query structures, and generalization beyond training structures. QUERY2BOX consistently outperforms GQE and ablations, while attention-based intersections, complex-query training, and adaptive box sizes each contribute to performance.

  • Evaluation protocol: Experiments target answers to complex logical queries that require imputing one or more missing KG edges.Evaluation focuses on answers unavailable through direct traversal of the incomplete knowledge graph.
  • Query generation: Models are trained on 5 of 9 query structures and evaluated on all 9, including structures unseen during training.The evaluation includes projections, intersections, and unions across diverse query forms.
  • Query generation: Complex structures such as 2p, 3p, ip, pi, and up often have more than 10 times as many answers as 1p queries.This motivates evaluating representations that can model large answer sets.
  • Main results: On FB15k, FB15k-237, and NELL995, Q2B achieves 9.8%, 3.8%, and 5.9% higher H@3 than the best baselines, respectively.These correspond to 25%, 15%, and 24% relative improvements, and Q2B also outperforms GQE-DOUBLE with the same number of parameters.
  • Ablation studies: On FB15k-237, Q2B gains more than 4% and 2% absolute H@3 over Q2B-AVG and Q2B-DEEPSETS on intersection queries.The result supports the importance of the attention mechanism for modeling intersections.
  • Ablation studies: Explicit training on complex queries improves reasoning, while shared box offsets perform poorly across query types.Q2B variants trained beyond 1p achieve up to 10% absolute average H@3 improvement on FB15k; adaptive offsets better model queries with different answer-set sizes.

5 CONCLUSION

QUERY2BOX models sets of entities and reasons over EPFO queries in vector space. It transforms queries into DNF, embeds conjunctive components as boxes, and retrieves entities nearest to those boxes.

  • QUERY2BOX models and reasons over sets of entities while handling EPFO queries in vector space.
  • Given a logical query, QUERY2BOX transforms it into DNF and embeds each conjunctive query into a box.
  • QUERY2BOX outputs entities closest to their nearest boxes and handles EPFO query types scalably and accurately.

A PROOF OF THEOREM 1

The proof establishes that representing arbitrary EPFO disjunctions with a single embedding requires a distance-function class with VC dimension at least M. This result is independent of the specific query-embedding algorithm.

  • The proof considers disjunctions of subsets of M conjunctive queries and assigns one entity vector to each query's answer entities.
  • The required embeddings must model every subset query using a distance threshold that separates its corresponding answer entities.
  • The requirement is equivalent to fitting any binary labeling of M points, so the distance-function class must have VC dimension at least M.

B DETAILS ABOUT COMPUTING M IN THEOREM 1

The computation of M constructs many conjunctive queries with pairwise-disjoint answer sets on FB15k. Combining 1p and 2i queries yields M = 13,365.

  • The procedure starts with 308,006 FB15k 1p queries, of which 129,717 have more than one answer entity.
  • It forms 2i queries by randomly sampling two multi-answer 1p queries and taking their conjunction.
  • 13,365 conjunctive queries have pairwise-disjoint denotation sets after processing both 1p and 2i query collections.

C EXPERIMENTS ON LINK PREDICTION

The link-prediction experiment compares QUERY2BOX with TransE and query2box-1p on three datasets. Because simple link prediction lacks multi-hop reasoning and large answer sets, only modest gains are expected.

  • Table 4 compares performance on the simple link-prediction task across three datasets.
  • QUERY2BOX is comparable or slightly better than TransE on simple link prediction, including when trained on diverse queries.
  • Simple link prediction does not require multi-hop reasoning or modeling large answer sets, limiting the expected benefit of box embeddings.

E DETAILS OF NELL995 DATASET

The NELL995 knowledge graph is rebuilt with validation and test triples incorporated, then new validation and test splits are sampled from the resulting graph.

  • E DETAILS OF NELL995 DATASET: Validation and test sets are combined with training data to form the whole NELL995 knowledge graph.This preprocessing follows Allen et al. (2019).
  • E DETAILS OF NELL995 DATASET: New validation and test splits each randomly select 20,000 triples from the whole knowledge graph.
  • E DETAILS OF NELL995 DATASET: Entities appearing only in validation and test sets, but not in training, are filtered out.

F DATASET STATISTICS

The experiments report statistics for three datasets and their generated logical queries, using a specified joint-training configuration for all query structures.

  • F DATASET STATISTICS: Basic statistics are reported for the three datasets used in the experiments.
  • F DATASET STATISTICS: Generated logical queries are summarized by their training, validation, and test counts across query structures.
  • F DATASET STATISTICS: Models jointly train all query types with 400-dimensional embeddings, minibatches of 512 queries per structure, and 128 negative entities per query.Training uses one sampled answer entity per query and Adam with learning rate 0.0001 for 250 epochs.

H ANALYSIS OF LEARNED BOX OFFSET SIZE

The learned box offset size correlates with the number of entities contained in corresponding 1p queries, with one-to-many relations tending to produce larger boxes.

  • H ANALYSIS OF LEARNED BOX OFFSET SIZE: Box size, measured by the L1 norm of the box offset, strongly correlates with the average number of entities contained in corresponding 1p queries.
  • H ANALYSIS OF LEARNED BOX OFFSET SIZE: One-to-many relations tend to have larger offset embeddings than relations associated with fewer contained entities.Table 7 lists the ten relations with the smallest and largest box sizes in FB15k.
  • H ANALYSIS OF LEARNED BOX OFFSET SIZE: The analysis interprets larger boxes as modeling sets containing more entity points.

I MRR RESULTS

The results section presents MRR comparisons for QUERY2BOX against GQE and several variants across FB15k, FB15k-237, and NELL995.

  • I MRR RESULTS: Table 8 reports MRR results for QUERY2BOX versus GQE on FB15k, FB15k-237, and NELL995.
  • I MRR RESULTS: Table 9 reports MRR results for QUERY2BOX versus several variants on FB15k, FB15k-237, and NELL995.
Loading 2002.05969v2…