Type-aware Embeddings for Multi-Hop Reasoning over Knowledge Graphs

1 Introduction

In recent years, the multi-hop reasoning problem of answering first-order logic queries (FOL) on large-scale incomplete knowledge graphs (KGs) [Pan et al., 2016] has gained a lot of attention in the AI community. A major challenge for traditional subgraph matching methods for query answering is that KGs are inevitably incomplete and noisy. Indeed, when schema [Wiharja et al., 2020] and triples are incomplete in the KG, correct answers are not guaranteed to be found under normal deductive reasoning, leading to empty or wrong answers. Another problem is their intrinsic high computational complexity as they need to keep track of all intermediate entities occurring on reasoning paths, leading to an exponential blow-up. For instance, to answer the query "List the presidents of Asian countries that have held the Summer Olympics" shown in Fig. 1, we require two traversing-steps (many more for other queries): one to identify countries that have held the summer Olympics and another one to identify Asian countries, each producing intermediate countries.

∗Contact Authors

To address these challenges, a query embedding (QE) approach to query answering has been recently introduced as an alternative to subgraph matching methods. The main idea is to embed entities and queries into a joint low-dimensional vector space such that entities that answer the query are close to the embedding of the query. Several QE models for query answering, showing very promising performance, have been proposed so far [Hamilton et al., 2018; Ren et al., 2020; Ren and Leskovec, 2020; Zhang et al., 2021; Choudhary et al., 2021b; Luus et al., 2021]. However, these models fail to leverage semantic knowledge inherently available in KGs, such as entity description [Yao et al., 2019; Daza et al., 2021] or entity type information [Niu et al., 2020; Pan et al., 2021]. Advantages of introducing type information are that: 1) it can enhance the representation of entities or relations; e.g., the types sports and event can enrich the representation of the entity Summer Olympics in the context of sport events (cf. Fig. 1). 2) It can also help tackling the inductive query answering problem where entities used in test queries cannot be observed at training time; e.g., consider the queries in Figure 1: "List the presidents of Asian countries that have held the Summer Olympics" and "List the presidents of European countries that have held the Winter Olympics", which are generated from two KGs with disjoint sets of entities: Train KG and Test KG, respectively. Even if the entities Summer Olympics and Winter Olympics are different, they have similar type information, such as sports and event. Consequently, after using type information to represent entities, the model associated to the query generated from Train KG is also effective on the query generated from Test KG.

The goal of this paper is to introduce a type-aware plugand-play model which makes full use of type information in the knowledge graph, and can be easily embedded into existing QE-based models. To this aim, we propose a novel TypE-aware Message Passing (TEMP) model, which contains two key components. 1) Type-aware Entity Representations (TER), aggregating type information of entities to strengthen their vector representation (cf. Section 4.1). 2) Type-aware Relation Representations (TRR), using entity type information to construct a global type graph to enhance the relation representation, and simultaneously integrate it with its type representation and existing entity type information (cf. Section 4.2). Importantly, some queries have variable nodes in the query paths (see Figure 1), which increase the difficulty of subsequent reasoning steps in the chain, as variable nodes are unknown. To address this, the TRR component uses a bidirectional mechanism for the anchor node to supervise the relations in the query path, and vice versa. Furthermore, as mentioned, after using type information to represent entities and relations, the model becomes inherently inductive as the occurrence of new entities or relations will not affect the type-based representations.

Our main contributions can be summarized as follows:

• We propose TEMP, a novel type-aware plug-and-play model for multi-hop reasoning over KGs, that can be easily incorporated into the existing QE-based models.
• We design a new bidirectional integration mechanism that incorporates the pairwise dependencies among {entity, relation, type} information, even in the absence of schema axioms like domain and range.
• Extensive experiments demonstrate that after incorporating TEMP into four state-of-the-art baselines, their generalization, deductive and inductive reasoning abilities are significantly improved across three benchmark datasets consistently.

Data, code, and an extended version with appendix is available at https://github.com/SXUNLP/QE-TEMP

2 RelatedWork

Query Embeddings. QE models first embed entities and FOL queries into a joint low-dimensional vector space, and subsequently compute a similarity score between the entity representation and query representation in the latent embedding space. In general, according to the type of embedding spaces, QE-based methods can be divided into four categories: (i) geometric-based methods, such as GQE [Hamilton et al., 2018], Q2B [Ren et al., 2020], HypE [Choudhary et al., 2021b], and ConE [Zhang et al., 2021], where logical queries and KG entities are embedded into a geometric vector space as points, boxes, hyperbolic, and cone shapes, respectively; (ii) distribution-based methods, such as BETAE [Ren and Leskovec, 2020], embedding queries to beta distributions with bounded support, and PERM [Choudhary et al., 2021a], using Gaussian densities to reason over KGs; (iii) logic-based methods, relating so-called set logic with FOL [Luus et al., 2021]; (iv) neural-based methods, e.g., EMQL [Sun et al., 2020] using neural retrieval to implement logical operations.

Considering QE-based methods are the mainstream in the current CQA field, we mainly focus on how to construct a plug-and-play model to embed the type information for existing QE-based methods.

OtherMethods. Besides the QE-based approach, the pathbased approach is another method for CQA, but it faces an exponential growth of the search space with the number of hops. For instance, CQD [Arakelyan et al., 2021] uses a beam search method to explicitly track intermediate entities, and repeatedly combines scores from a pretrained link predictor via t-norms to search answers while tracking intermediaries. However, CQD does not support the full set of FOL queries.

InductiveKGCompletion (KGC). In the context of KGC, there have been some works on inductive settings where test entities are not seen in the training stage. Based on the source of information used, they can be split into two categories: Using graph structure information, e.g., subgraph or topology structures [Teru et al., 2020; Chen et al., 2021; Wang et al., 2021], or using external information, e.g., textual descriptions of entities [Daza et al., 2021]. However, all these methods focus on the inductive KGC task, which can be seen as answering simpler one-hop queries.

Type-aware Tasks. Type information was previously used in other tasks such as KGC or entity typing [Yao et al., 2019; Zhao et al., 2020; Daza et al., 2021; Niu et al., 2020; Pan et al., 2021]. However, these works cannot be directly used for answering FOL queries because this requires multi-hop reasoning, producing intermediate uncertain entities.

3 Background

In this paper, a knowledge graph [Pan et al., 2016] is represented in a standard format for graph-structured data such as RDF. A knowledge graph G is a tuple (E,R, C, T ), where E is a set of entities, R is a set of relation types, C is a set of entity types, and T is a set of triples. Triples in T are either relation assertions (h, r, t), where h, t ∈ E are respectively the head and tail entities of the triple, and r ∈ R is the edge of the triple connecting head and tail, or entity type assertions (e, type, c), where e ∈ E is an entity, c ∈ C is an entity type and type is the instance-of relation [Pan, 2009].

We consider FOL queries that use existential quantification (∃), conjunction (∧), disjunction (∨) and negation (¬) operations. We will work with FOL queries in Disjunctive Normal Form, i.e. represented as a disjunction of conjunctions. To introduce FOL queries, we assume that Va ⊂ E represents a set of non-variable input anchor entities, V1, . . . , Vm denote existentially quantified variables and V? is the target variable. A FOL query Q is a formula of the following form:

where ci = ei1 ∧ . . . ∧ eik, k ≤ m such that each eij is of one of the following forms: r(Va, V ), ¬r(Va, V ), r(V,V ′ ) or ¬r(V, V ′ ), with Va ∈ Va, V ∈ {V?, V1, . . . , Vm}, V ′ ∈ {V1, . . . , Vm}, V ̸= V ′ .

The dependency graph (DG) of a query Q is a graphical representation of Q, where nodes correspond to variable or non-variable arguments in Q and edges correspond to relations in Q. Figure 1 shows an example of a DG.

We are interested in the multi-hop reasoning problem of answering queries Q on KGs, which aims to find a set of entities JQK ⊆ E such that a ∈ JQK iff Q[a] holds true.

4 Semantically-enriched Embeddings

Our model TEMP is composed of two sub-models: Typeaware Entity Representations (TER), which uses type information of an entity to enrich its vector representation, and Type-aware Relation Representations (TRR), which further integrates entity representations, relation types, and relation representations to strengthen the entity and relation vector representations simultaneously. Interestingly, as we only leverage type information to perform an in-depth characterization of entities and relations without modifying the training target of existing QE-based models, TEMP can be easily embedded into them in a plug-and-play fashion.

4.1 TER: Type-aware Entity Representations

The main intuition behind TER is that the types of an entity provide valuable information about what it represents in the KG. For instance, if an entity contains types such as sports/multi event tournament, time/event, olympics/olympic games, it is plausible to infer that the corresponding entity represents Olympics. To capture this intuition, we design an iterative multi-highway layer [Srivastava et al., 2015] to aggregate the type information in entity type assertions to get a more accurate and comprehensive representation of it 1 . Let His ∈ Rd×n denote the hidden state of type information of an entity in iteration i ≥ 1, where d and n respectively represent the vector size and the number of types of an entity. The highway-based type fusion representation of a given entity can be calculated as follows:

1 See appendix for other aggregation alternatives.

H1 s is the initial feature of types of an entity, σ is an elementwise sigmoid function, {Wi,W ′ i }∈ Rd×d , {bi, b′i }∈ Rd×1 are learnable matrices, and g∈ Rd×n is the reset gate. After iterating K times (we set K=2), the final message HK s ∈ Rd×n (undergoing a linear operation to obtain ˜ HK s ∈ Rd×1 ) is taken as the representation for the types of a given entity. We further concatenate the initial entity and its type aggregation representation to get an enhanced entity representation.

where [·] is the concatenation function, W ′ ∈ Rd×d and b′ ∈ Rd×1 are the parameters to learn. He ∈ Rd×1 is the final representation of the entity. It is important to note that for inductive reasoning, we will not concatenate with the initial entity information H0 s as the entities seen during training are not presented in the test phase. The process is shown in top center of Figure 2.

4.2 TRR: Type-aware Relation Representations

Performing TER on entities is useful for queries without existentially quantified variables. However, for queries with chained existential variables (chain of variable nodes in the DG) it is not enough to only perform TER on the anchor entity or target variable. Intuitively, the problem is that in the long-chain reasoning process, the correlation between the anchor entity and target variable may not be strong enough after several relation projections. Besides, continuous relational projections may cause exponential growth in the search space, further increasing the complexity of the model.

We start by observing that the types of a relation are correlated with its representation in the KG. For example, assuming a relation r has types government/ political appointer and organization/role, then we can plausibly infer that the relation r represents President of. In long-chain queries, typeenhancement on relations can help to reduce the answer entity space and cascading errors caused by multiple projections. However, in most existing KGs, relations lack specific type annotations (such as domain and range). We address this problem by building, based on the original KG, a novel type graph with types as nodes and relations as edges (see bottom left of Fig. 2). In a subsequent step, we aggregate the type information on the type graph to obtain the type embedding corresponding to a specific relation. Finally, we integrate the entity representation, the aggregated type information of a relation and its representation by a bidirectional attention mechanism, so that the intermediate variable nodes can perceive the message of anchor or target nodes and of the relations in the chain of reasoning (see right of Fig. 2). This will help to avoid the weakening of the connection between anchor and target entity caused by long-chain reasoning.

Step 1: Type Graph Construction

We formally define a type graph Gtp. Let G = (E,R, C, T ) be a KG. For a relation r ∈ R, Tr ⊆ T denotes the set of relation assertions in which r occurs. For a relation assertion t ∈ ⋃r∈R Tr , hd(t) and tl(t) respectively denote the head and tail entities of t, and tpt(hd(t)) = {c | (hd(t), type, c) ∈ T } denotes the set of types of the head of t; tpt(tl(t)) is defined analogously. Since r may occur in multiple relation assertions, we will compute the type information of r by taking the intersection of the types of the head and tail entities of relation assertions in which r occurs. For r ∈ R, we define

In addition, we define Gtp = (V,E, T) by setting V = ⋃r∈R tp hd r (G) ∪ tp tl r (G) , E = R, and (v, r, v′ ) ∈ T if there exists t ∈ Tr such that v = tpt(hd(t)) and v′ = tpt(tl(t)).

Step 2: Relation Type Aggregation

For a given relation r ∈ E, we define the types associated with a relation as tpr(Gtp) = tp hd r (G) ∪ tp tl r (G). We fix an arbitrary linear order on the elements of tpr(Gtp), and denote by tpir (Gtp) the i-th type, for all 1 ≤ i ≤ |tpr(Gtp)|. Note that not all types in tpr(Gtp) are relevant for answering a given query. For example, assume that the relation has part contains the types {vehicle, animal, universe}. For the query "What organs are parts of a cat?", we should give type animal more attention, but for the query "What components are parts of a car?" we should concentrate on the type vehicle. So, instead of simply concatenating (or averaging) all the type information associated to a relation, we model the relation type aggregation as an attention neural network, defined as:

Hs is the vector representation of the aggregated type information tpr(Gtp); His ∈ Rd×1 is the vector representation of the i-th type tpir (Gtp), which is initialized to a uniform distribution with dimension d, 1 ≤ i ≤ |tpir (Gtp)|; ai ∈ Rd×1 is a positive weight vector that satisfies ∑ni=1 [ai]j = 1 for all 1 ≤ j ≤ d; and MLP(·) : Rd → Rd is a multi-layer perceptron network.

Step 3: Pairwise Representation Integration

When embedding queries, integrating the information of entities, relations, and types can help to smooth decision boundaries, but this needs to be done in a way that the intended match of the query into the KG is captured. For example, for the query "Which countries have held the Summer Olympics?", we need to concentrate on Held connections from Summer Olympics, rather than e.g., Watch connections. Analogously, we should only consider Held connections starting at Summer Olympics, rather than e.g., at World Cup. To properly capture this restriction in the triple {He , Hr , Hs } (He and Hs defined as in Equations (4) and (5), and Hr is the initialization relation vector), we introduce a bidirectional attention mechanism [Zhang et al., 2020] to integrate each state of pairwise representation pairs: entityrelation, entity-type, and relation-type. Here, we show how to do this for entity-relation pair. Bidirectional integration representation between He and Hr can be calculated as follows:

{W1,W2} ∈ R2d×2d and {b1, b2} ∈ R2d×1 are learnable parameters. We use element-wise subtraction ⊖ and multiplication ⊗ to build better matching representations [Tai et al., 2015]. G er ∈ R2d×1 is the result of integrating entity relation information. Through bidirectional integration of entities and relations, we simultaneously get a relation-aware entity representation and an entity-aware relation representation, capturing the interaction between entities and relations.

We then use a gated mechanism to combine the results produced by bidirectional fusion as it better regulates the information flow [Srivastava et al., 2015]. Take the entity fusion representation as an example, using the relation-aware entity G er and type-aware entity G es representations as input, the final representation of entity is computed as

{W3, W4} ∈ R2d×2d and {b3, b4} ∈ R2d×1 are the parameters to learn. g is the reset gate, and ˜ G e ∈ R2d×1 is the final entity representation.

To transform the fused feature to the original vector size, we use one linear layer: He = W5˜ G e + b5, where W5 ∈ Rd×2d and b5 ∈ Rd×1 are learnable parameters. He is the final entity representation enhanced by relation and type.

5 Experiments

Our aim is to analyse the impact of adding TEMP to existing QE models on their generalization, deductive and inductive reasoning abilities.

Datasets and Queries. For generalization and deductive reasoning, we use three standard benchmark KGs with official training/validation/test splits: FB15k [Bordes et al., 2013], FB15k-237 [Toutanova and Chen, 2015], and NELL995 (NELL) [Xiong et al., 2017], and two query datasets: one with 9 query structures without negation from Query2Box (Q2B) [Ren et al., 2020] and another with 14 (9 positive + 5 with negation) from BETAE [Ren and Leskovec, 2020]. To test inductive reasoning, we use the datasets FB15k-237-V2 and NELL-V3 provided by GraIL [Teru et al., 2020], ensuring that the test and training sets have a disjoint set of entities. Note that we generate queries over these datasets as done for BETAE datasets. We choose Hit@K and Mean Reciprocal Rank (MRR) as two evaluation metrics 2 .

Baselines. We embed TEMP on four state-of-the-art baselines for complex QA on KGs: Q2B, BETAE, GQE [Hamilton et al., 2018], and LOGICE [Luus et al., 2021].

Generalization. The goal is to find non-trivial answers to FOL queries over incomplete KGs, i.e. answers cannot get using subgraph matching. We follow the evaluation protocol in [Ren and Leskovec, 2020]. Briefly, three KGs are built: Gtrain containing only training triples, Gvalid containing Gtrain plus validation triples, and Gtest containing Gvalid as well as test triples. The models are trained using Gtrain to evaluate the generalization ability because queries have at least one edge to predict to find an answer.

2 Refer to appendix for details on datasets, queries, and metrics.

Deductive Reasoning. The goal is to test the ability of finding answers only using standard reasoning. Following [Sun et al., 2020], we train models using the full KG (Gtrain ∪ Gvalid ∪ Gtest), so only inference (not generalization) is used to get correct answers.

Inductive Reasoning. All baseline models have inductive ability at the query level as they can answer queries with structures that are not seen during training. For example, the Q2B and BETAE datasets consider five query structures during the training and validation phase and four 'unseen' structures are used during testing. However, it is not known whether they have entity-level inductive ability, i.e. during testing, the query structure has entities that do not appear in the training phase. We will analyse this for the first time.

5.1 Main Results

We compare the performance of the four baseline models with their counterparts after adding our TEMP model in four different aspects: 1) generalization, 2) deductive reasoning, 3) inductive reasoning, and 4) queries with negation.

Generalization. Table 1(a) shows that for long-chain queries 2p and 3p, the improvement brought by TEMP exceeds that of short-chain 1p, confirming the suitability of type information for dealing with long-chain queries. In addition, TEMP-enhanced models also achieve improvements on queries ip/pi/2u/up, which do not occur in the training KG, showing that type information is also helpful to improve inductive ability at the query-level structure. Notably, for GQE, adding type information can shorten the gap or even surpass the state-of-the-art baseline models (without TEMP).

Deductive Reasoning. Table 1(b) shows that after adding type information, the reasoning ability of the baselines are significantly improved on all datasets consistently. Specifically, the improvement of embedding models based on geometric operations (GQE, Q2B) is more significant than that of BETAE or LOGICE. Remarkably, Q2B + TEMP surpasses the state-of-the-art baseline models (without TEMP). The main reason for the modest gain for BETAE and LOGICE is that they impose excessive restrictions on the embedding of entities and relations. For instance, in LOGICE, the logic embeddings with bounded support change the type-enriched vector representations, thus affecting the effect of type information.

Inductive Reasoning. Table 2 shows that the addition of TEMP significantly outperforms all baselines in the (entitylevel) inductive setting, by 12.2%, 6.8%, 10.7%, and 12.8%, in terms of Hits@10 in the FB15k-237-V2 dataset. The main reason is that in TEMP entity and relation representations are mainly characterized by the type information. So, newly emerging entities or relations can be captured through their type information, making unnecessary the coupling between entities and entity set, and relations and relation set.

Queries with Negation. Table 3 shows the results of BETAE and LOGICE on queries with negation in the BETAE dataset. The main reason for the small gains is that, unlike BETAE and LOGICE, TEMP does not have specific mechanisms to deal with negation. Specifically, TEMP lacks mechanisms to associate type information to the negation of a relation, i.e., a way to 'negate' a type. Boosting queries with negation using type information is left as an interesting future work.

5.2 Ablation Studies

We select GQE and Q2B, as they benefit the most by adding type information, and conduct ablation experiments on the three datasets to study the effect of separately using typeenhancement on entities or relations, see Table 4. We further study different implementations of entity and relation type aggregation models, see Figure 3 and Figure 4.

Type-enhancement on relations is consistently better than on entities, this is explained by the fact that enhancing relation representations is more helpful for queries with long chains of existentially quantified variables as it better deals with cascading errors introduced by relation projections. We also show that using type-enhancement on both entities and relations usually leads to even better performance.

6 Conclusions

We proposed TEMP, a type-aware plug-and-play model for answering FOL queries on incomplete KGs. We experimentally show that TEMP can significantly improve four stateof-the-art models in terms of generalization, deductive and inductive reasoning abilities across three benchmark datasets consistently.

Acknowledgments

This work has been supported by the National Key Research and Development Program of China (No.2020AAA0106100), by the National Natural Science Foundation of China (No.61936012), by the Chang Jiang Scholars Program (J2019032), by a Leverhulme Trust Research Project Grant (RPG-2021-140), and by the Centre for Artificial Intelligence, Robotics and Human-Machine Systems (IROHMS) at Cardiff University.