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.

提出了一种基于嵌入的查询框架，使用矢量空间嵌入复杂逻辑查询，将查询表示为盒子并将合取作为盒子交集表示，而将极限作为在 DNF（析取正规形式）中转换后处理。