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