Knowledge Transfer for Out-of-Knowledge-Base Entities : A Graph Neural Network Approach

1 Introduction

Knowledge bases such as WordNet [Miller, 1995] and Freebase [Bollacker et al., 2008] are used for many applications including information extraction, question answering, and text understanding. These knowledge bases can be viewed as a set of relation triplets, i.e., triplets of the form (h, r, t) with an entity h called the head entity, a relation r, and an entity t called the tail entity [Bordes et al., 2013; Nguyen et al., 2016]. Some examples of relation triplets are (Philip-K.-Dick, write, Do-Androids-Dream-of-ElectricSheep?) and (Do-Androids-Dream-of-Electric-Sheep?, is-a, Science-fiction). Although a knowledge base contains millions of such triplets, it is known to suffer from incompleteness [Nickel et al., 2016]. Knowledge base completion (KBC) thus aims to predict the information missing in knowledge bases.

In recent years, embedding-based KBC models have been successfully applied to large-scale knowledge bases[Wang et al., 2014b; Lin et al., 2015; Ji et al., 2015; Xiao et al., 2016b; Nguyen et al., 2016; Guu et al., 2015]. These models build the distributed representations (or, vector embeddings) of entities and relations observed in the training data, and use various vector operations over the embeddings to predict missing relation triplets.

In this paper, we address the out-of-knowledge-base (OOKB) entity problem in embedding-based KBC. This problem arises when new entities (OOKB entities) occur in the relation triplets that are given to the system after training. As these entities were unknown to the system at training time, the system does not have their embeddings, and hence does not have a means to predict the relations for these entities. The OOKB entity problem thus asks how to perform KBC involving such OOKB entities. Although it can be solved by retraining the embeddings using the added relation triplets containing the OOKB entities, a solution avoiding costly retraining is desirable.

This problem is of practical importance because OOKB entities crop up whenever new entities, such as events and products, are produced, which happens everyday. For example, suppose we find an OOKB entity "Blade-Runner" in a new triplet (Blade-Runner, based-on, Do-AndroidsDream-of-Electric-Sheep?). We want to infer more facts (viz. triplets) about Blade-Runner from the knowledge we already have, and answer questions such as "Is Blade Runner science fiction?" If the knowledge base contains a triplet (DoAndroids-Dream-of-Electric-Sheep?, is-a, Science-fiction), it should help us estimate that the answer is yes. Figure 1 illustrates this example schematically.

There have been some attempts to obtain the embeddings for OOKB entities using external resources [Wang et al., 2014a; Fang et al., 2016; Zhong et al., 2015]. Although these approaches may be useful, they require additional computation over large resources, which may not be always feasible. By contrast, we pursue a KBC model that exploits existing triplets in the knowledge base, without relying on external resources. Indeed, the Blade Runner example above suggests the possibility of inferring new facts about OOKB entities without the help of external resources.

To solve the OOKB entity problem, we apply graph neural networks (Graph-NNs) [Scarselli et al., 2009; Li et al., 2015] to a knowledge graph, which is a graph obtained by regarding entities as nodes and triplets as edges. A Graph-NN is a neural network architecture defined on a graph structure and composed of two models called the propagation model and output model. The propagation model manages how information propagates between nodes in the graph. In the propagation model, we first obtain the embedding vectors of the neighborhood of a given node (entity) e and then convert these vectors into a representation vector of e using a pooling function such as the average. In other words, each node is embedded as a vector in continuous space, which is also used to calculate the vectors of the neighborhood nodes. This mechanism enables the vector for an OOKB entity to be composed from its neighborhood vectors at test time. The output model defines the task-oriented objective function over node vectors. This allows us to use an existing embedding-based KBC model as the output model. In this paper, we use TransE [Bordes et al., 2013] as the output model, but we can adopt other embedding-based KBC methods.

Our main contributions can be summarized as follows:

• We propose a new formulation of the problem of OOKB entities in KBC.
• We propose a Graph-NN suitable for the KBC task with OOKB entities.
• We verify the effectiveness of our models in both the standard and the "OOKB" entity settings.

2 OOKB Entity Problem in Knowledge Base Completion

2.1 Knowledge Graph

Let E be a set of entities and R be a set of relations. Define the fact, or relation triplet, to be a triplet of form (h, r, t) where h, t ∈ E and r ∈ R. Let Ggold ⊂ E ×R× E be the set of gold facts, i.e., the set of all relation triplets that hold for pairs of entities in E and relations in R. If a triplet is in Ggold, we say it is a positive triplet; otherwise, it is a negative triplet. The goal of knowledge completion is to identify Ggold, when only its proper subset, or an "incomplete" knowledge base, G ⊂ Ggold is accessible.

A knowledge base G is often called knowledge graph because each triplet in G can be regarded as a (labeled) edge in a graph; i.e., the entities in a triplet correspond to the end nodes and the relation gives the label of the edge.

2.2 KBC: Triplet Classification

Triplet classification is a typical KBC task introduced by [Socher et al., 2013] 1 and has since been a standard benchmark for KBC methods [Wang et al., 2014b; Ji et al., 2015; Xiao et al., 2016a; Yoon et al., 2016; Nguyen et al., 2016].

In this task, existing knowledge base G is assumed to be incomplete, in the sense that some of triplets that must be present in G are missing; i.e., G ̸= Ggold.

Let H = (E ×R× E)\G be the set of triplets not present in G. Because G is incomplete, two cases are possible for each triplet x ∈ H; either x is a positive triplet (i.e., x ∈ Ggold), or x is a negative triple (i.e., x ̸∈ Ggold). For the former case, x is not in G only because of the incompleteness, and the knowledge base must be updated to contain x. We thus encounter the problem of determining which of the above two possible cases each triplet not present in G falls into. This problem is called triplet classification.

Viewed as a machine learning problem, triplet classification is a classifier induction task in which E and R are given, and knowledge base G forms the training set (with only positive examples), with H being the test set. The set H can be divided into the set of positive test examples H ∩ Ggold = Ggold\G and the set of negative test examples H\Ggold.

In the standard triplet classification, E and R are limited to the entities and relations that appear in G. That is, E = E(G) and R = R(G), where E(G) = {h | (h, r, t) ∈ G} ∪ {t | (h, r, t) ∈ G} and R(G) = {r | (h, r, t) ∈ G} denote the entities and relations appearing in G, respectively.

2.3 OOKB Entity Problem

We now introduce a new task in KBC, called the OOKB entity problem.

In addition to the knowledge base G observed at training time, new triplets Gaux are given at test time, with E(Gaux) ̸⊂ E(G) and R(Gaux) ⊆ R(G). Thus, Gaux contains new entities EOOKB = E(Gaux)\E(G), but no new relations are involved. We call EOOKB OOKB entities. It is assumed that every triplet in Gaux contains exactly one OOKB entity from EOOKB and one entity fromE(G); that is, the additional triplets Gaux represent edges bridging E(G) and EOOKB in the combined knowledge graph G ∪ Gaux. In this setting, E = E(G) ∪ EOOKB ̸= E(G), and the task is to correctly identify missing relation triplets that involve the OOKB entities EOOKB. Because the embeddings for these entities are missing, they must be computed from those for entities in G. In other words, we want to design a model by which the information we already have in G can be transferred to OOKB entities EOOKB, with the help of the added knowledge Gaux.

3 ProposedModel

3.1 Graph-NNs

Graph-NNs are neural networks defined on a graph structure. Although there exist graph-NNs that encode an entire graph into a vector [Cao et al., 2016; Defferrard et al., 2016], here we focus on the one that provides the means to encode nodes and edges into vectors, as this is more suitable for KBC.

1 A similar task had been around for general graphs under the name of link prediction.

According to [Scarselli et al., 2009; Li et al., 2015], a graph-NN consists of two models, the propagation model and the output model. The propagation model determines how to propagate information between nodes in a graph. The output model defines an objective function according to given tasks using vector-represented nodes and edges. In this paper, we modify the propagation model to be suitable for knowledge graphs. For the output model, we use the embedding-based KBC model TransE [Bordes et al., 2013].

3.2 PropagationModel on a Knowledge Graph

Let G be a knowledge graph, e ∈ E(G) be an entity, and ve ∈ Rd be the d-dimensional representation vector of e. Li et al. define the propagation model by the following equation [Li et al., 2015]:

where head neighborhood Nhead and tail neighborhood Ntail are Nhead(e) = {(h, r, e) | (h, r, e) ∈ G} and Ntail(e) = {(e, r, t) | (e, r, t) ∈ G} in a knowledge graph G, respectively. In addition, Thead, Ttail : Rd ×E(G)×R(G)×E(G) → Rd are called transition functions [Li et al., 2015] and used to transform the vector of a neighbor node for its incorporation in the current vector ve, depending on the property of the edge between them.

We generalize the propagation function using the following pooling function P :

Here, Shead(e) contains the representation vectors of neighborhood Nhead(e), and Stail(e) contains those for Ntail(e). The difference between Eq. (1) and ours (Eqs. (2)-(4)) is the use of the pooling function in place of the summation. The candidates for functions Thead, Ttail, and P are described below.

Transition Function The aim of transition function T (including both Thead and Ttail) is to modify the vector of a neighbor node to reflect the relations between the current node and the neighbor. The examples of the transition function are listed here:

where A ∈ Rd×d is a matrix of model parameters and tanh and ReLU are elementwise hyperbolic tangent and rectified linear unit functions. In addition, we can use other neural network techniques, such as batch-normalization [Ioffe and Szegedy, 2015], residual connection [He et al., 2016], and long short termmemory [Li et al., 2015].

We can also make the transition function dependent on the relation between the current node (entity) and the neighbor, such as in the following:

Note that the parameter matrices are now defined individually for each combination of node e, the current neighbors (h or t), and the relation r between them.

In the experiments of Section 4, we use the following transition functions:

where BN indicates batch normalization [Ioffe and Szegedy, 2015].

Pooling Function Pooling function P is a function that maps a set of vectors to a vector, i.e., P : 2Rd → Rd . Its objective is to extract shared aspects from a set of vectors. For S = {xi ∈ Rd }Ni=1 , some simple pooling functions are as follows:

where max is the elementwise max function. Sum pooling was used in [Scarselli et al., 2009; Li et al., 2015]; see also Eq. (1).

Stacking and Unrolling Graph Neural Networks As explained above, the propagation models decide how to propagate information from a node to its neighborhood. Applying this propagation model repeatedly, we can broadcast information of a node to farther nodes, i.e., each node can receive further information. Broadcasting can be implemented in one of two ways: stacking or unrolling.

The unrolled Graph-NN is discussed in [Scarselli et al., 2009; Li et al., 2015]. In the unrolled Graph-NN, the propagation model uses the same model parameters in every propagation. The propagation procedures are the same as described in Eqs. (2)-(4).

The stacked Graph-NN is constructed in a similar manner to the well-known stacking technique [Vincent et al., 2010]. In particular, the propagation process in the stacked GraphNN uses different model parameters depending on time step n. The transition function at each time step n, indicated by superscript n, is as follows.

where

where T (n) head and T (n) tail are transition functions depending on head/tail and time.

3.3 Output Model: Score and Objective Functions

We use a TransE-based objective function as the output model. TransE [Bordes et al., 2013] is one of the basic embedding-based models for KBC, and we use it for its simplicity and ease of training. Notice however that our architecture is not limited to TransE, and adopting other embeddingbased models for the output model is equally straightforward.

Below, we explain the score function of TransE and its commonly used pairwise-margin objective functions. We then describe the modified objective function we used in our experiments, called the absolute-margin objective.

Score Function The (implausibility) score function f evaluates the implausibility of a triplet (h, r, t); smaller scores indicate that the triplet is more likely to hold. In TransE, the score function is defined by f(h, r, t) = ‖vh + vr - vt‖, where vh, vr, and vt are the embedding vectors of the head, relation, and tail, respectively. This score function states that for a positive triplet (h, r, t), the sum of the head and relation vectors vh + vr must be close to the tail vector vt, i.e., vh + vr ∼ vt. This score function is modified and extended in [Wang et al., 2014b; Lin et al., 2015; Ji et al., 2015; Xiao et al., 2016b]. As mentioned earlier, all these models can be used as our output model.

Pairwise-MarginObjective Function The objective (loss) function defines the quantity to be minimized through optimization. The following pairwise-margin objective function is commonly used with KBC methods including TransE [Bordes et al., 2013; Xiao et al., 2016b]:

where [x]+ is the hinge function [x]+ = max(0, x) and scalar τ ∈ R is a threshold (called margin), with (hi, ri, ti) denoting a positive triplet and (h′i , ri, t′i ) denoting a negative triplet. This objective function requires score f(h′i , ri, t′i ) to be greater than score f(hi, ri, ti) by at least τ. If the difference is smaller than τ, then the optimization changes the parameters to meet the requirement. In contrast, if the difference is greater than τ , the parameters are not updated.

The pairwise-margin objective thus pays attention to the difference in scores between positive-negative triplet pairs.

Absolute-Margin Objective Function Instead of the pairwise-margin objective, in this paper, we employ the following objective function, which we call the absolute-margin objective.

where τ is a hyperparameter, again called the margin. This objective function considers positive and negative triplets separately in the first and the second terms, not jointly as in the pairwise-margin objective. The scores for the positive triplets will be optimized towards zero, whereas the scores of the negative triplets are going to be at least τ. This objective function not only is easy to optimize, but also obtained good results in our preliminary experiments. We thus used this objective function for the experiments in Section 4.

4 Experiments

4.1 Implementation and Hyperparameters

We implemented our models using the neural network library Chainer (http://chainer.org/). The code and dataset are available at https://github.com/takuo-h/GNN-for-OOKB. All networks were trained by stochastic gradient descent with backpropagation; specifically, we used the Adam optimization method [Kingma and Ba, 2014]. The step size of Adam was α1/(α2 · k + 1.0), where k indicates the number of epochs performed, α1 = 0.01, and α2 = 0.0001. The mini-batch size was 5, 000 and the number of training epochs was 300 in every experiment. Moreover, the dimension of the embedding space was 200 in the standard triplet classification and 100 in other settings.

In the preliminary experiments, we tried several activation functions and pooling functions, and found the following hyperparameter settings on account of both computational time and performance. We used Eqs. (5)-(6) as transision functions in both the standard and OOKB settings. As the pooling function, we used the max pooling function in the standard triplet classification, and tried three pooling functions, max, sum, average, in the OOKB setting. The results of the preliminary experiments were reflected in our selection of the absolute-margin objective function over the pairwise-margin objective function as well as the margin value τ = 300 in the absolute-margin objective function (Eq. (8)). The absolutemargin objective function converged faster than the pairwisemargin objective function. Because the task is a binary classification of triplets into positive (i.e., the relations that must be present in the knowledge base) and negative triplets (those that must not), we determined the threshold value for output scores between these classes using the validation data.

To deal with the limited available computational resources (e.g., GPU memory), we sampled the neighbor entities randomly when an entity has too many of them. Indeed, there were some entities that appeared in a large number of the triplets, and thus had many neighbors; when the neighborhood size exceeded 64, we randomly chose 64 entities from the neighbors.

4.2 Standard Triplet Classification

We compared our model with the previous KBC models in the standard setting, in which no OOKB entities are involved.

Datasets We used WordNet11 and Freebase13 [Socher et al., 2013] for evaluation. The data files were downloaded from http://cs.stanford.edu/people/danqi/. These datasets are subsets of two popular knowledge graphs, WordNet [Miller, 1995] and Freebase [Bollacker et al., 2008]. The specifications on these datasets are shown in Table 1. Both datasets contain training, validation, and test sets. The validation and test sets include positive and negative triplets. In contrast, the training set does not contain negative triplets. As usual with the case in which negative triplets are not available, corrupted triplets are generated from positive triplets are used as a substitute for negative triplets. From a positive triplet (h, r, t) in knowledge base G, a corrupted triplet is generated by substituting a random entity sampled from E(G) for h or t. Specifically, to generate corrupted triplets, we used the "Bernoulli" trick, a technique also used in [Wang et al., 2014b; Lin et al., 2015; Ji et al., 2015; Ji et al., 2016].

Result The results are shown in Table 2. Our model showed state-of-the-art performance on the WordNet11 dataset. On the Freebase13 dataset, it did not perform as well as the stateof-the-art KBC methods, although it was slightly better than TransE on which our model was built on.

4.3 OOKB Entity Experiment

Datasets We processed theWordNet11 dataset to construct several datasets for our OOKB entity experiment.

In total, nine datasets were constructed with different numbers and positions of OOKB entities sampled from the test set. The process consists of two steps: choosing OOKB entities and filtering and splitting triplets.

1. Choosing OOKB entities. To choose the OOKB entities, we first selected N = 1, 000, 3, 000, and 5, 000 triplets from the WordNet11 test file.

For each of these three sets, we chose the initial candidates for the OOKB entities (denoted by I) in three different ways (thereby yielding nine datasets in total); these settings are called Head, Tail, and Both. In the Head setting, all head entities in the N triplets are regarded as candidate OOKB entities. The Tail setting is similar, but with the tail entities regarded as candidates. In the Both setting, all entities appearing as either a head or tail are the candidates.

The final OOKB entities are the entities e ∈ I that appear in a triplet (e, r, e′ ) or (e′ , r, e) in the WordNet11 training set, with e′ ̸∈ I. Note that the entities h, t ̸∈ I are contained in the knowledge bases we already have and not in the OOKB entities. This last process filters out candidate OOKB entities that do not have any connection with the training entities.

1. Filtering and splitting triplets. Using the selectedOOKB entities, the original training dataset was split into the training dataset and the auxiliary datasets for the OOKB entity problem. That is, triplets that did not contain the OOKB entities were placed in the OOKB training set, and triplets containing one OOKB entity and one nonOOKB entity were placed in the auxiliary set. Triplets that contained two OOKB entities were discarded.

For the test triplets, we used the same first N triplets in the WordNet11 test file that we used in Step 1, with the exception that the triplets that did not contain any OOKB entities were removed. For the validation triplets, we simply removed the triplets containing OOKB entities from the WordNet11 validation set.

The details of the generated OOKB datasets are shown in Table 3. We denote each of the nine datasets by {Head, Tail, Both}-{1,000, 3,000, 5,000}, respectively, where the first part represents the position of OOKB entities and the second part represents the number of triplets used for generating the OOKB entities.

Result Using the nine datasets generated fromWordNet11, we verified the effectiveness of our proposed model.

We used the following simple method as the baseline in this experiment. Given an OOKB entity u, we first obtained the embedding vectors of the neighborhood (determined by the triplets in the auxiliary knowledge) using TransE, and then converted these vectors into the representation vector of u using a pooling function: sum, max, or average. Note that because all the neighborhood entities of u are in the training knowledge base, their vectors can be computed using standard KBC methods. We followed the original paper [Bordes et al., 2013] of TransE for the hyperparameter and other settings.

The results are shown in Table 4. The column labeled "pooling" indicates which pooling function was used. As the table shows, our model outperforms the baselines considerably. In particular, Graph-NN with average pooling outperforms the other methods on all datasets. Graph-NN with max pooling also shows good accuracy, but in several settings, such as Tail-3000, it was outperformed by the baseline model with average pooling.

4.4 Stacking and Unrolling Graph-NNs

Stacking and unrolling are important techniques because they enable us to broadcast node information to distant nodes. In this experiment, we illustrate the effect of stacking and unrolling in the standard triplet classification task. The dataset is WordNet11, used for standard triplet classification.

Accuracy Comparison Table 5 shows the performance of the stacked and unrolled Graph-NNs. The parameter "depth" indicates how many times the propagation model is iteratively applied. Note that when depth = 1, the two models reduce to the vanilla Graph-NN, for which the result was 87.8%, as also shown in Table 2. These results imply that the stacking and unrolling techniques do not improve performance. We believe this is because of the power of the embedding models, i.e., we can embed information about distant nodes into a continuous space.

5 Conclusion

In this paper, we proposed a new KBC task in which entities unobserved at training time are involved. For this task, we proposed a Graph-NN tailored to KBC with OOKB entities. We conducted two triplet classification tasks to verify the effectiveness of our proposed model. In the OOKB entity problem, our model outperformed the baselines considerably. Our model also showed state-of-the-art performance on WordNet11 in the standard KBC setting.

Acknowledgments

We thank the anonymous reviewers for valuable comments. This work was partially supported by JSPS Kakenhi Grant 15H02749.