  One of the fundamental problems in Artificial Intelligence is to perform
complex multi-hop logical reasoning over the facts captured by a knowledge
graph (KG). This problem is challenging, because KGs can be massive and
incomplete. Recent approaches embed KG entities in a low dimensional space and
then use these embeddings to find the answer entities. However, it has been an
outstanding challenge of how to handle arbitrary first-order logic (FOL)
queries as present methods are limited to only a subset of FOL operators. In
particular, the negation operator is not supported. An additional limitation of
present methods is also that they cannot naturally model uncertainty. Here, we
present BetaE, a probabilistic embedding framework for answering arbitrary FOL
queries over KGs. BetaE is the first method that can handle a complete set of
first-order logical operations: conjunction ($\wedge$), disjunction ($\vee$),
and negation ($\neg$). A key insight of BetaE is to use probabilistic
distributions with bounded support, specifically the Beta distribution, and
embed queries/entities as distributions, which as a consequence allows us to
also faithfully model uncertainty. Logical operations are performed in the
embedding space by neural operators over the probabilistic embeddings. We
demonstrate the performance of BetaE on answering arbitrary FOL queries on
three large, incomplete KGs. While being more general, BetaE also increases
relative performance by up to 25.4% over the current state-of-the-art KG
reasoning methods that can only handle conjunctive queries without negation.
