Q uery2 P articles: Knowledge Graph Reasoning with Particle Embeddings (2022)

Abstract: Answering complex logical queries on incomplete knowledge graphs (KGs) with missing edges is a fundamental and important task for knowledge graph reasoning. The query embedding method is proposed to answer these queries by jointly encoding queries and entities to the same embedding space. Then the answer entities are selected according to the similarities between the entity embeddings and the query embedding. As the answers to a complex query are obtained from a combination of logical operations over sub-queries, the embeddings of the answer entities may not always follow a uni-modal distribution in the embedding space. Thus, it is challenging to simultaneously retrieve a set of diverse answers from the embedding space using a single and concentrated query representation such as a vector or a hyper-rectangle. To better cope with queries with diversified answers, we propose Query2Particles (Q2P), a complex KG query answering method. Q2P encodes each query into multiple vectors, named particle embeddings. By doing so, the candidate answers can be retrieved from different areas over the embedding space using the maximal similarities between the entity embeddings and any of the particle embeddings. Meanwhile, the corresponding neural logic operations are defined to support its reasoning over arbitrary first-order logic queries. The experiments show that Query2Particles achieves state-of-the-art performance on the complex query answering tasks on FB15k, FB15K-237, and NELL knowledge graphs.

## introduction reasoning over a factual knowledge graph (kg) is the process of deriving new knowledge or conclusions from the existing data in the knowledge graph @xcite . a recently developed sub-task of knowledge graph reasoning is complex query answering, which aims to answer complex queries over large knowledge graphs @xcite logical knowledge graph queries interpretations 𝑞 1 = 𝑉 ? . ∃𝑉: 𝑊𝑖𝑛 𝑇𝑢𝑟𝑖𝑛𝑔𝐴𝑤𝑎𝑟𝑑, 𝑉 ∧ ¬𝐶𝑖𝑡𝑖𝑧𝑒𝑛 𝐶𝑎𝑛𝑎𝑑𝑎, 𝑉 ∧ 𝐺𝑟𝑎𝑑𝑢𝑎𝑡𝑒(𝑉, 𝑉 ? ) find where the non-canadian turing award laureates graduated from. find the substances that interact with the proteins associated with diseases t1, t2, or t3. to address the challenge raised from the incompleteness of knowledge graphs, the query embedding methods are proposed @xcite @xcite . in this line of research, the queries and entities are jointly encoded into the same embedding space, and the answers are retrieved based on similarities between the query embedding and entity embeddings. in general, there are two steps in encoding a query to the vector space. first, a query is parsed into a computational graph with a directed acyclic graph (dag) structure, as shown in figure 2 (a ). then, the query representation is iteratively computed following the neural logic operations and relation projections in the dag. although the query embedding methods are robust for dealing with the incompleteness of kgs, the query2particles encodes each query into a set of vectors, called particle embeddings. the logical operations iteratively compute particle embeddings following the computational graph. the answers are determined by using the maximum similarities between the entity embeddings and any one of the resulting particle embeddings. the embedding structure used for encoding the queries can be improved. because of the multi-hop and compositional nature of complex kg queries, a single query may contain multiple sufficiently diverse answers. thus, the ideal query embedding may follow a multi-modal distribution 1 in the embedding space. for example, the answers to the query, "find entities, who are not american, were the nobel prize winners and eventually moved to the us," involve intermediate entities with different attributes, such as gender, nationality, research fields, etc. it is difficult to use a single embedding vector to find all final answer embeddings. box embedding @xcite partially solved this problem, but for complicated attributes, a single box may be too coarse, and intermediate entities are distributed far away from each other, so they are more like several disjoint clusters rather than a single big region in the embedding space. so for the query embedding methods, the capability to simultaneously encode a set of answers from different areas is necessary. to better address the diversity of answers, we propose query2particles, a new query embedding method for complex query answering. in this approach, each query is encoded into a set of vectors in the embedding space, called particle embeddings. the particle embeddings of a query are iteratively computed by following the computational graph parsed from the query. then the answers to this query are determined by using the maximum similarities between the entity embeddings and any one of the resulting particle embeddings. experimental results show that query2particle achieves state-ofthe-art performance on complex query answering over three standard knowledge graphs: fb15k, fb15k-237, and nell. meanwhile, the inference 1 a multi-modal distribution is a distribution with two or more distinct peaks in the probability density function. ## related work other query embedding approaches are closely related to our work. these query embedding methods leverage different structures to encode logical kg queries, and they can answer various scopes of logical queries. the gqe method proposed by @xcite can answer the conjunctive queries by representing queries as vector representations. @xcite used hyper-rectangles to encode and answer existential positive first-order (epfo) queries. at the same time, @xcite proposed to improve the faithfulness of the query embedding method by using centroid-sketch representations on epfo queries. the conjunctive queries and epfo queries are both subsets of firstorder logic (fol) queries. the beta embedding @xcite is the first query embed-ding method that supports a full set of operations in fol by encoding entities and queries into probabilistic beta distributions. in a contemporaneous work, @xcite uses cone embeddings to encode the fol queries. as shown in figure 3 , compared to these query embedding approaches, the q2p method can encode the fol queries to address the diversity of answers. note that, @xcite proposed to use the disjunctive normal form (dnf) to address the answer diversities resulting from the union operations. this partly solve the problem, but the diversity of the answers is not solely caused by the union operation, but a joint effort of multi-hop projections, intersection, and complement. as a result, using particle embeddings is a more general solution. query decomposition @xcite ) is another approach to answering complex knowledge graph queries. in this line of research, a complex query is decomposed into atomic queries, and the probabilities of atomic queries are modeled by link predictors. in the inference process, continuous optimization and beam search are used for finding the answers. meanwhile, the rule and path-based methods @xcite @xcite @xcite use pre-defined or learned rules to do multi-hop kg reasoning. these methods explicitly model the intermediate entities in the query. instead, the query embedding methods directly embed the complex query and retrieve the answers without explicit modeling intermediate entities. so the query embedding methods are more scalable to large knowledge graphs and complex query structures. neural link predictors @xcite @xcite are also related to this work. the link predictors learn the distributed representations of entities and relations in embedding space and use different neural structures to classify whether there exists a certain relation between two entities. the link predictors can be used for one-hop queries, but cannot be directly used for answering complex queries. ## preliminaries in this section, we formally define the complex logical knowledge graph queries and the corresponding computational graphs. the knowledge graph reasoning is conducted on a multi-relational knowledge graph @xmath0, r), where each vertex @xmath1, and each relation @xmath2: v × @xmath3, 1}. for any @xmath4, and u, @xmath5, there is a relation r between entities u and v if and only if r(u, v) = 1. ## query2particles in this section, we first introduce the particle embeddings structure and the neural logic operations, and then we present the learning of the model. ## experiments the experiments in this section demonstrate the effectiveness and efficiency of query2particles. ## conclusion in this paper, we proposed query2particles, a query embedding method for answering complex logical knowledge graph queries over incomplete knowledge graphs. the query2particle method supports a full set of fol operations. specifically, the q2p method is the first query embedding method that can directly model the union operation without any preprocessing. experimental results show that the q2p method achieves state-of-the-art performances on answering fol queries on three different knowledge graphs while using comparable inference time as the previous methods.