Appendix

For the first property, the probabilistic negation operatorN takes the reciprocal of the parameters of the input Beta embeddings. Here we discuss the computation complexity of representing any given FOL query using the De Morgan'slaws(DM) andthedisjunctivenormal form (DNF). GivenaFOL queryq,representing q with DNF may in the worst case creates exponential number of atomic formulas. Given the three KGs, and its training/validation/test edge splits, which is shown in Table 5, we first createGtrain, Gvalid, Gtest as discussed in Sec. Then for each query structure, we use pre-order traversal starting from the target node/answer to assign an entity/relation to each node/edge iteratively until we instantiate every anchor nodes (the root of the query structure). After the instantiation of a query, we could perform post-order traversal to achievetheanswersofthisquery. Specifically, as shown in Figure 1, we only consider query structures with intersection for the derivation of queries with negation.