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

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 complex query into a sequence of mini-queries according to its computation graph and perform logical operations on the answer sets of mini-queries to get answers. However, most of them assume that answer sets satisfy an individual distribution (e.g., Uniform, Beta, or Gaussian), which is often violated in real applications and limit their performance. In this paper, we propose a Neural-based Mixture Probabilistic Query Embedding Model (NMP-QEM) that encodes the answer set of each mini-query as a mixed Gaussian distribution with multiple means and covariance parameters, which can approximate any random distribution arbitrarily 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 Gaussian 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.

## introduction answering fol queries on kgs is a fundamental problem in kgs. it aims to find answer entities of given complex queries using operators including existential quantification(∃), conjunction(∧), disjunction(∨), and negation(¬), which has attracted great attention from both academic and industry recently @xcite @xcite . early methods transform a fol query into a computation graph like figure 2 node represents a set of entities and each edge represents a logical operation. then, these methods traverse the kg according to the computation graph to identify the answer set @xcite @xcite . 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 intermediate 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 @xcite @xcite @xcite . these methods divide a query into a sequence of mini-queries according to its computation graph, and perform logical operations on the answer set of each mini-query to get the answer. existing qe methods differ in their way of modeling answer sets and logical operations, which can be divided into geometry-based and distributionbased categories. geometry-based models represent each answer set as a "region" (e.g., box or cone) in euclidean spaces, while distribution-based models usually leverage an individual distribution (e.g., beta or gaussian) to represent each answer set. compared with early methods, qe methods do not need to track all intermediate entities, and can use the nearest neighbor search in the embedding space to quickly discover answers. though having achieved promising performance, most existing qe methods assume that answer sets satisfy an individual distribution. for example, geometry-based models @xcite ) assume that answer sets satisfy a uniform distribution in a region, and distribution-based models assume that answer sets satisfy the gaussian distribution @xcite or beta distribution @xcite . in the real kgs, distributions of answer sets are often very complicated. as shown in the left of figure 1 , the embedding vectors of the answer set to the query (us, location_contains, ?) in nell995 @xcite are scattered across two class centers: city-related center containing (e.g., new york, joplin, pittsburgh) and college-related center containing (e.g., cambridge, yale university, brooklyn college). similarly, shown in the right of figure 1 , the embedding vectors of the answer set to the query (sport_baseball, plays_sport_reverse, ?) in freebase @xcite are scattered across three class centers: pitcher-related center, coach-related center, and catcher-related center, which indicate different positions among baseball players. obviously, it is difficult to model the answer set of each query with only one individual distribution, which limits the performance of existing methods. inspired by the above insights, this paper proposes a neural-based mixture probabilistic query embedding model (nmp-qem), which uses mixed gaussian distribution with multiple means and covariance parameters to encode the answer set of each query. since mixed gaussian distributions can approximate any random distribution arbitrarily well @xcite , the proposed nmp-qem can model more complicated answer sets' distribution in real kgs. furthermore, due to the unboundedness of gaussian random variables, the closed form of the negation operators of mixed gaussian distributions is hard to define, which prevents answering the queries with negation. to tackle this problem, we propose neuralbased logical operators of projection, intersection and negation for mixed gaussian distributions, so that the proposed nmp-qem can answer all the fol queries. to summarize, the contributions of our works are as follows: ## related work in this section, we briefly review the related work. to answer complex logical queries on kgs, pathbased methods @xcite start from anchor entities and require traversing the intermediate entities on the path, which leads to exponential computation cost. query embedding models are another line of work. roughly speaking, existing query embedding methods can be divided into two categoriesgeometry-based models and distribution-based models. geometry-based models usually represent answer sets as "regions" e.g., points, boxes, or cones in euclidean spaces, and then design set operations upon them. for example, query2box @xcite represents entities as points and queries as boxes. if a point is inside a box, then the corresponding entity is the answer to the query. geometric shapes provide a natural and easy way to represent sets and logical relations among them. to better handle the queries with negation, recently @xcite use the closure of cones to design the negation operation. while @xcite directly uses mlp to define the negation operation and embed the query and the entities in the same vector space with single-point vectors. distribution-based models usually embed entities and queries as an individual distribution e.g., beta, gaussian. @xcite uses beta distributions defined on the [0, 1] interval to model entities, queries, and design neural logical operators that support full first-order logic. @xcite encodes entities as a multivariate gaussian density with mean and covariance parameters, and defines the closed logical operations upon the gaussian distribution. although it defines the logical operators for mixture input during chaining the queries, this model can not deal with the negation operation. besides, it needs to calculate the inverse of the large matrix and solve a linear system, which requires huge memory and is very time-consuming. although these qe models make significant progress in answering fol queries on kgs, they overlook that the distribution of answer sets in real kgs is often complicated. thus, the proposed nmp-qem models answer sets of queries with mixed gaussian distributions instead of individual distributions, in order to approximate any distributions well in real applications. ## preliminaries in this section, we first give the formal definition of answering fol queries on kgs. a kg can be denoted as @xmath0; r), where @xmath1, and @xmath2: v × @xmath3; f alse}, indicating whether the relation r holds between a pair of entities or not. the goal of answering fol queries on kgs is to answer first-order logical (fol) queries on kgs. we can define them as follows: definition 1 (first-order logic queries) a firstorder logic query q is formed by an anchor entity set v a ⊆ v, an unknown target variable v ? and a series of existentially quantified variables v 1 , . . . , v k . in its disjunctive normal form (dnf) @xcite , it is written as a disjunction of conjunctions: specifically, c i represents a conjunctive query of one or several literals: and the literals represent a relation or its negation: it is worth noting that the union operation is unnecessary, as @xcite shows that a union operator becomes intractable in distance-based metrics, and can be implemented using intersection and negation. ## methods overall, the architecture of the nmp-qem and the corresponding computation graph are shown in figure 2. to get answers, the complex query is divided into a sequence of mini-queries according to its computation graph. then we use the neural-based operators to embed the entity and do logical operations between the answer set of each mini-query. in this query, the basketball players of america may play different positions (e.g., center, pg) and players who win the nba championship may also come from different countries (e.g., spain, france). in the following subsections, we will introduce the details of the proposed method. ## experiments in this section, we first introduce the experiment settings including datasets, baselines and evaluation protocols. secondly, we compare nmp-qem with competitive models on answering fol queries over kgs and demonstrate its superiority. thirdly, we reduce training queries to four types (1p/2i/2in/inp) to observe the further generalization of the model. then, we analyze the impact of two important parameters on the proposed model. finally, we do the case study to exploit how the nmp-qem models the answer sets in nell995. ## limitations in this section, we discuss the limitations of the proposed model. as mentioned above, (amayuelas et al., 2021) used the vector to represent relation and defines the projection as the concatenation of the relation vector and query embedding. @xcite used few parameters to represent the projection operators. compared with these methods, our model may have more parameters and need more time during the training. this is because we define the neural-based projection operators p for each relation. so, if the amount of relation is too much, the parameters will increase accordingly. the