Rethinking Existential First Order Queries and their Inference on Knowledge Graphs

Reasoning on knowledge graphs is a challenging task because it utilizes observed information to predict the missing one. Specifically, answering first-order logic formulas is of particular interest, because of its clear syntax and semantics. Recently, the prevailing method is query embedding which learns the embedding of a set of entities and treats logic operations as set operations. Though there has been much research following the same methodology, it lacks a systematic inspection from the standpoint of logic. In this paper, we characterize the scope of queries investigated previously and precisely identify the gap between it and the whole family of existential formulas. Moreover, we develop a new dataset containing ten new formulas and discuss the new challenges arising concurrently. Finally, we propose a new inference algorithm from fuzzy logic theory with provable reasoning capability. Empirical results show that our method succeeds in outperforming the previous methods in both the new dataset and the existing dataset.