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

Abstract

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.

ICLR 2020

References in corpus (4)

• A Review of Relational Machine Learning for Knowledge Graphs
• RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space
• Embedding Logical Queries on Knowledge Graphs
• Improved Representation Learning for Predicting Commonsense Ontologies

Cited by in corpus (30)

• On the Opportunities and Risks of Foundation Models
• Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction
• Beta Embeddings for Multi-Hop Logical Reasoning in Knowledge Graphs
• Tackling Over-Smoothing for General Graph Convolutional Networks
• QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering
• Self-Supervised Hyperboloid Representations from Logical Queries over Knowledge Graphs
• ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs
• BoxE: A Box Embedding Model for Knowledge Base Completion
• Facts as Experts: Adaptable and Interpretable Neural Memory over Symbolic Knowledge
• Improving Local Identifiability in Probabilistic Box Embeddings
• Complex Query Answering with Neural Link Predictors
• Interstellar: Searching Recurrent Architecture for Knowledge Graph Embedding
• SMORE: Knowledge Graph Completion and Multi-hop Reasoning in Massive Knowledge Graphs
• Logic Embeddings for Complex Query Answering
• Role-Aware Modeling for N-ary Relational Knowledge Bases
• Probabilistic Entity Representation Model for Reasoning over Knowledge Graphs
• Message Passing Query Embedding
• NQE: N-ary Query Embedding for Complex Query Answering over Hyper-Relational Knowledge Graphs
• Benchmarking the Combinatorial Generalizability of Complex Query Answering on Knowledge Graphs
• Query Embedding on Hyper-relational Knowledge Graphs
• Neural, Symbolic and Neural-Symbolic Reasoning on Knowledge Graphs
• Learning Syllogism with Euler Neural-Networks
• Embedding Ontologies via Incorporating Extensional and Intensional Knowledge
• Modeling Fine-Grained Entity Types with Box Embeddings
• Knowledge Sheaves: A Sheaf-Theoretic Framework for Knowledge Graph Embedding
• LNN-EL: A Neuro-Symbolic Approach to Short-text Entity Linking
• SQALER: Scaling Question Answering by Decoupling Multi-Hop and Logical Reasoning
• Regex Queries over Incomplete Knowledge Bases
• Towards Robust Reasoning over Knowledge Graphs
• Learning User Representations with Hypercuboids for Recommender Systems