G amma E : Gamma Embeddings for Logical Queries on Knowledge Graphs (2022)

Abstract: Embedding knowledge graphs (KGs) for multi-hop logical reasoning is a challenging problem due to massive and complicated structures in many KGs. Recently, many promising works projected entities and queries into a geometric space to efficiently find answers. However, it remains challenging to model the negation and union operator. The negation operator has no strict boundaries, which generates overlapped embeddings and leads to obtaining ambiguous answers. An additional limitation is that the union operator is non-closure, which undermines the model to handle a series of union operators. To address these problems, we propose a novel probabilistic embedding model, namely Gamma Embeddings (GammaE), for encoding entities and queries to answer different types of FOL queries on KGs. We utilize the linear property and strong boundary support of the Gamma distribution to capture more features of entities and queries, which dramatically reduces model uncertainty. Furthermore, GammaE implements the Gamma mixture method to design the closed union operator. The performance of GammaE is validated on three large logical query datasets. Experimental results show that GammaE significantly outperforms state-of-the-art models on public benchmarks.

## introduction most important advances encode knowledge into large-scale graph data to model real-world knowledge graphs (kgs), such as wikidata @xcite , microsoft academic @xcite , medical domain @xcite . a knowledge graph aims to represent entities and describe relations between concepts and entities. multi-hop reasoning on kgs is a fundamental task of predicting answer entities of a graph query. though previous methods have provided significant insight, this domain exists many challenging works due to complicated query structures and incomplete graph data. since most real-world kgs consists of multiple unobserved edges and nodes, multi-hop reasoning cannot easily find the answering query. knowledge graph reasoning can be represented by the first-order logic (fol) queries with basic operators, such as the existential quantifier (∃), conjunction (∧), disjunction (∨), and negation (¬). one regular set of such graph queries is the conjunctive query, which only consists of existential quantifiers (∃) and conjunctions (∧) @xcite . for example, a conjunctive query, such as "who are nobel laureates from germany?", is calculated on open-domain kgs. the laureates are existentially quantified variables in this query, where some laureates connect the nobel prize to germany. in terms of this task, we aim to predict potential answers that can involve missing edges. besides, it is difficult to find all possible query structures since any graph query can be satisfied by many subgraphs. current methods @xcite @xcite address these problems by projecting entities and relations into a low-dimensional geometric space. these methods could quickly discover answers, since there is no need to track all intermediate entities. this research direction provides an effective solution for encoding semantic positions of entities by using their neighbor information. it is imperative that the solution is not required to track all intermediate entities, and only uses the nearest neighbor information in the geometric space to quickly get answers. however, geometric embeddings of the union operator cannot locate in a closed space, that is, the union of two embedding boxes is not a box or the same structure. thus, fol operations have difficulty in running the union operator @xcite . due to the non-smooth distance function, the distance between entities is difficult to calculate in the boxing space @xcite . other approaches apply the density function to encode entities and relations @xcite . though these models can solve all fol queries, they cannot efficiently handle the union operator (∨) due to its non-closure property in the density space. besides, previous methods utilize the disjunctive normal form (dnf) transformation which requires more computational steps. thus, we aim to address the limitation and then implement the gamma density function for encoding entities and relations. another point is that our work can effectively process a stream of disjunctive queries. here we propose a gamma embedding (gam-mae) probabilistic model to encode entities and relations for multi-hop reasoning on kgs. in the gamma density space, all fol operations, such as existential quantifier (∃), intersection (∧), union (∨), and negation (¬), are closed and follow gamma distributions. the linear property of the gamma density can dramatically improve the computation efficiency for discovering answers. the contributions of our work are summarized as follows: our results have implications for encoding entities and relations, advancing the science of multihop reasoning, and improving our understanding of general knowledge graph. the rest of the paper is organized as follows: section 2 shows the related work in multi-hop reasoning over kgs. next, sections 3 and 4 theoretically demonstrate gamma embeddings and define its fol operations. the experimental setup and results are explicitly shown in section 5. finally, section 6 makes a clear conclusion and section 7 briefly presents its limitations. ## related work this work is closely related to query embedding approaches @xcite @xcite @xcite . most related models are applied for multi-hop reasoning over kgs @xcite @xcite @xcite @xcite @xcite . based on their embedding methods, these models can be categorized into two branches, namely geometric embedding models and probabilistic embedding models. the geometric embedding models assign adaptive geometric shapes for entities and relations with different structures @xcite @xcite . these models map fol queries into low-dimensional spaces and don't need to model the intermediate entities, which dramatically reduces the computation costs. they can effectively deal with a subset of fol operations, while @xcite proposed a novel cone embedding for entities, and can handle all fol operations. meanwhile, @xcite encode complex queries into multiple vectors, named particle embeddings. it also efficiently deals with all fol operations. these models have strict borders relying on a non-smooth distance function, which difficultly handles multiple answers and easily ignores some correct entities. however, our model utilizes gamma density to create linear space for each entity and relation, and build a soft-smooth distance function for alleviating the boundary effect. another method is to encode entities into the probabilistic density for performing multi-hop logical reasoning. @xcite @xcite . in vector embeddings, transg @xcite firstly models the uncertainties of entities and relations by using the gaussian mixture model. their work doesn't be implemented into multi-hop reasoning on kgs. betae @xcite firstly embeds entities and relations with the probabilistic density, which can handle all fol operations. since their union is non-closure, betae potentially leads to generate ambiguous entities between the two boxes. perm @xcite applies the gaussian den-sity for representing entities and relations, and uses gaussian mixture models for complex queries, i.e, long chains. however, perm cannot handle the negation operator, and needs to spend large computational costs on learning knowledge graph representations. our work firstly uses gamma density to map entities and relations into linear space, and dramatically increases the performance and robustness. also, gammae efficiently finds the answers with closed and smooth forms. ## preliminaries a knowledge graph (kg) is a directed graph @xmath0, e, r), where v is the set of entities, e is the set of triplets, and r denotes the set of relations. a direct triplet of a kg is represented as (e 1 , r, e 2 ) ∈ e, that is, a relation r linking the entity e 1 to the entity e 2 , where e 1 , e 2 ∈ v and @xmath1. for each triplet, it has a relational binary function, i.e, r(e 1 , e 2 ) = true if and only if (e 1 , r, e 2 ) exists. first-order logic queries. the first-order logic (fol) queries contain four basic operators, namely existential quantifier (∃), conjunction (∧), disjunction (∨), and negation (¬). a first-order logic query q consists of a non-variable anchor entity set v a ⊆ v , existential quantified set {v 1 , v 2 , ..., v k }, and a target set v t , i.e, query answers. the logical form of a disjunctive query q can be written as here, c i is a conjunctive query with one or more literals b ij . and b ij is an atomic formula or a negation. computation graphs. each query can generate its corresponding computation graph, where entities are mapped into nodes, and relations with atomic formulas are calculated by logical operators. these logical operators are defined as follows: ## gamma embeddings for logical reasoning to address the multi-hop reasoning on incomplete kgs, we propose a novel model gammae, which encodes both entities and queries into gamma distributions. next, the related probabilistic logical operators are transformed into relation projection, intersection, union, and negation. gammae provides an efficient method to handle arbitrary fol queries. the schematics of gammae answering graph queries are explicitly illustrated in fig. 1 . ## experiment gammae is evaluated on three large-scale kg benchmark datasets, including fb15k @xcite , fb15k-237 @xcite , and nell995 @xcite . the experiment demonstrates gammae on various tasks: 1. gammae can efficiently handle all fol queries. 2. gammae outperforms the state-of-the-art baselines on the tasks. 3. the uncertainty of gamma embeddings is well controlled. 4. all fol operators are closed, especially the union and negation. datasets. for multi-hop reasoning, gammae is studied on three standard benchmark datasets (details are shown in appendix d.1): based on previous experimental settings @xcite @xcite , we evaluate gammae on fol queries without negation, and negation queries. gammae focuses on answering queries involved with incomplete kgs. the training and testing queries consist of five conjunctive structures (1p/2p/3p/2i/3i) and five structures with negation (2in/3in/inp/pni/pin). additionally, to evaluate the inference ability of the model, four extra query structures, namely ip/pi/2u/up, could show the ability to answer complicated queries with unseen structures during training. please refer to appendix d.1 for more details about query structures. baseline. we compare gammae with state-ofthe-art models, including gqe @xcite , query2box (q2b) @xcite , be-tae @xcite , and cone @xcite . gqe and q2b are trained only on five conjunctive structures (1p/2p/3p/2i/3i) as they cannot solve negation queries. for fair comparison, we assign the same dimensionality to the embeddings of these methods. ## conclusion in this paper, we propose a novel embedding model, namely gammae, to handle arbitrary fol queries and efficiently realize multi-hop reasoning on kgs. given a query q, gammae can map it onto the gamma space for reasoning it by probabilistic logical operators on the computation graph. compared to previous methods, its union operator uses the gamma mixture model to avoid the disjunctive normal form and de morgan's laws. furthermore, gammae significantly improves the perfor-mance of the negation operator due to alleviating the boundary effect. extensive experimental results show that gammae outperforms state-of-the-art models on multi-hop reasoning over arbitrary logical queries as well as modeling the uncertainty. overall, gammae aims to promote graph embeddings for logical queries on kgs.