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

By Hongyu Ren, Weihua Hu, Jure Leskovec. International Conference on Learning Representations, 2020

368 citations recorded by the source corpus.

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 two large KGs and show that query2box achieves up to 25% relative improvement over the state of the art.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/66f7823be7a0adcd8ed3ecebf00e53daf45bc6bc

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Combinatorial optimization and reasoning with graph neural networks (2021, background): “Briefly put, this area is concerned with expanding the body of knowledge in a (usually closed-domain) knowledge base, typically by inferring additional links or answering logical queries (Hamilton et al., 2018; Ren et al., 2019).”
Facts as Experts: Adaptable and Interpretable Neural Memory over Symbolic Knowledge (2020, background): “…many cognitive architectures which used hybrid symbolic and subsymbolic systems (Laird et al., 2017), and more recently, compositional query languages for embedding KBs that are similar to symbolic KB query languages (Cohen et al., 2017; Hamilton et al., 2018; Ren et al., 2020; Cohen et al., 2020).”
QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering (2021, background): “On the other hand, KGs are more suited for structured reasoning (Ren et al., 2020; Ren and Leskovec, 2020) and enable explainable predictions e.g., by providing reasoning paths (Lin et al., 2019), but may lack coverage and If it is not used for hair, a round brush is an example of what?”
Deep Bidirectional Language-Knowledge Graph Pretraining (2022, neutral): “KGs offer structured background knowledge by representing entities as nodes and relations between them as edges, and also offer scaffolds for structured, multi-step reasoning about entities [8, 9, 10, 11] (§3.”
GreaseLM: Graph REASoning Enhanced Language Models for Question Answering (2022, background): “Previous research has demonstrated the signiﬁcant role KGs can play in structured reasoning and query answering (Ren et al., 2020; 2021; Ren & Leskovec, 2020).”
Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction (2021, background): “, complex logical queries with conjunctions (∧) and disjunctions (∨) [18, 45].”
Neural, symbolic and neural-symbolic reasoning on knowledge graphs (2021, methodology): “On the basis of their work, Q2B (QUERY2BOX) , proposed by Ren et al. (2020) , ﬁ lls the gap in disjunctive queries.”