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

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