Neural-based Mixture Probabilistic Query Embedding for Answering FOL queries on Knowledge Graphs

Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 3001 - 3013 December 7-11, 2022 ©2022 Association for Computational Linguistics Neural-based Mixture Probabilistic Query Embedding for Answering FOL queries on Knowledge Graphs Xiao Long1, Liansheng Zhuang1∗, Li Aodi1, Shafei Wang2, Houqiang Li1 1University of Science and Technology of China, Hefei 230026, China 2Peng Cheng Laboratory, Shenzhen 518000, China longxiao1997@mail.ustc.edu.cn; lszhuang@ustc.edu.cn Abstract Query embedding (QE)—which aims to embed entities and first-order logical (FOL) queries in a vector space, has shown great power in answering FOL queries on knowledge graphs (KGs). Existing QE methods divide a com- plex query into a sequence of mini-queries according to its computation graph and per- form logical operations on the answer sets of mini-queries to get answers. However, most of them assume that answer sets satisfy an in- dividual distribution (e.g., Uniform, Beta, or Gaussian), which is often violated in real appli- cations and limit their performance. In this pa- per, we propose a Neural-based Mixture Proba- bilistic Query Embedding Model (NMP-QEM) that encodes the answer set of each mini-query as a mixed Gaussian distribution with multi- ple means and covariance parameters, which can approximate any random distribution ar- bitrarily well in real KGs. Additionally, to overcome the difficulty in defining the closed solution of negation operation, we introduce neural-based logical operators of projection, intersection and negation for a mixed Gaus- sian distribution to answer all the FOL queries. Extensive experiments demonstrate that NMP- QEM significantly outperforms existing state- of-the-art methods on benchmark datasets. In NELL995, NMP-QEM achieves a 31% relative improvement over the state-of-the-art. 1 Introduction Answering FOL queries on KGs is a fundamental problem in KGs. It aims to find answer entities of given complex queries using operators includ- ing existential quantification(∃), conjunction(∧), disjunction(∨), and negation(¬), which has at- tracted great attention from both academic and in- dustry recently (Sun et al., 2019; Li et al., 2017; Dalvi and Suciu, 2007; Dong et al., 2020). Early methods transform a FOL query into a computation graph like Figure 2(a), where each ∗*Corresponding author. node represents a set of entities and each edge rep- resents a logical operation. Then, these methods traverse the KG according to the computation graph to identify the answer set (Lin et al., 2018; Guo et al., 2018; Saxena et al., 2020; Sun et al., 2019). However, this type of approach suffers two major challenges. First, it has difficulties identifying the correct answers when some links are missing in KGs. Second, it needs to traverse all the intermedi- ate entities on reasoning paths, which may lead to exponential computation costs. Recently, query embedding (QE) methods have attracted much attention and keep them close enough (Hamilton et al., 2018; Ren et al., 2020; Guu et al., 2015; Zhang et al., 2021; Amayuelas et al., 2021). These methods divide a query into a sequence of mini-queries according to its computa- tion graph, and perform logical operations on the answer set of each mini-query to get the answer. Existing QE methods …

Content truncated to 500 words