Out-of-Sample Representation Learning for Knowledge Graphs (2020)

Abstract: Many important problems can be formulated as reasoning in knowledge graphs. Representation learning has proved extremely effective for transductive reasoning, in which one needs to make new predictions for already observed entities. This is true for both attributed graphs(where each entity has an initial feature vector) and non-attributed graphs (where the only initial information derives from known relations with other entities). For out-of-sample reasoning, where one needs to make predictions for entities that were unseen at training time, much prior work considers attributed graph. However, this problem is surprisingly under-explored for non-attributed graphs. In this paper, we study the out-of-sample representation learning problem for non-attributed knowledge graphs, create benchmark datasets for this task, develop several models and baselines, and provide empirical analyses and comparisons of the proposed models and baselines.

## introduction multi-relational graphs are a prevalent form of graphs where each edge has a label and a direction associated with it. many prediction problems can be formulated as reasoning within a multirelational graph. for example, figure 1 depicts a job recommendation system that has been formulated in these terms. a notable example of multirelational graphs is knowledge graphs (kgs) with several applications in natural language processing and information retrieval including search, question answering and commonsense reasoning. much prior work has considered transductive kg reasoning in which predictions are made at test time for only those entities that were observed during training. these are known as in-sample entities. in figure 1 , predicting if a 1 is expert in s 2 is an example of transductive reasoning. conversely, we consider out-of-sample kg reasoning. we make predictions for previously unseen or out-of-sample entities based on their relations with the in-sample entities. this is more challenging than transductive reasoning as it requires generalizing to unseen entities. in figure 1 , predicting whether a 3 is a good fit for the previously unseen job posting j new given j new 's relations with insample entities (observed at test time) is an example of out-of-sample reasoning. representation learning has proved effective for reasoning in kgs @xcite @xcite . it has been extensively studied for transductive reasoning in attributed graphs (where each entity has an initial feature vector) and non-attributed kgs (where the only initial information derives from known relations with other entities) as well as simple graphs (in which there is only a single relation). one prominent family of work is based on extensions of the convolution operator to non-euclidean domains @xcite @xcite . a second family models relations as translations (or rotations) from subject to object entities @xcite @xcite . a third approach represents the facts in a kg as a 3rd order tensor and factorizes this tensor to produce entity and relation embeddings @xcite @xcite . out-of-sample representation learning has also been extensively studied for attributed kgs @xcite and attributed simple graphs @xcite @xcite . however, for non-attributed kgs, it remains under-explored. the main challenge of out-of-sample representation learning for non-attributed kgs is that an entity representation must be learned using only the relations the entity participates in. @xcite develop such a model for non-attributed simple graphs but extending their work to kgs is not straightforward. out-of-sample representation learning in non-attributed graphs is an important problem for high-throughput production systems, as it is not tractable to adapt the transductive approaches and use additional rounds of gradient descent to incorporate new entities at test time. the contributions of this work are as follows: 1) we formally define out-of-sample representation learning for kgs, 2) we create benchmark datasets for this problem, 3) we propose several baselines, 4) we extend current transductive kg representation learning approaches by developing new training algorithms that can support the incorporation of out-of-sample entities at test time via aggregation functions to compute representations, and 5) we provide a thorough experimental comparison of the baselines and the proposed approaches. ## background and notation lower-case letters denote scalars, bold lower-case letters denote vectors, and bold upper-case letters denote matrices. for a vector z z @xmath0, we represent by z z z[i] (@xmath1. let v and r represent a set of entities and relations respectively. we represent a triple as (v, r, u), where @xmath2, @xmath3, and @xmath4. let ζ represent the set of all triples on entities v and relations r that are facts (e.g., (montreal, locatedin, canada)). a (non-attributed) knowledge graph (kg) g ⊂ ζ is a subset of ζ. hereafter, whenever we refer to a kg, we assume a non-attributed kg. transductive kg reasoning: in transductive kg reasoning, a model is learned for a kg g with entities v and relations r such that the model can make predictions about any triple (v, r, u) where v, @xmath5. kg embedding models map entities and relations to hidden representations known as embeddings and define a function φ from the embeddings of the entities and the relation in a triple to a score corresponding to the degree of belief the model has for the relation holding between the entities. typically, the embeddings can be formulated as two matrices z z z @xmath6, each row of z z z rel corresponds to the embedding for a relation, and d ent and d rel represent entity and relation embedding sizes. one can look up the embedding for a particular entity v by multiplying the transpose of z z z ent to the onehot encoding of v and for a particular relation r by multiplying the transpose of z z z rel to the one-hot encoding of r. a large number of approaches define z z z ent and z z z rel as matrices with directly learnable parameters. other approaches define encoders that produce these two matrices typically through several rounds of message passing among entities. algorithm 1 outlines one epoch of training for learning the embeddings as well as the parameters of the φ function. the training is performed using stochastic gradient descent with mini-batches. for each batch (line 2), the nextbatch function extracts a set of positive triples from the kg and creates n negative triples per positive triple by corrupting the positive triple according to the procedure introduced in @xcite . n is known as the negative ratio. for each triple (v, r, u) in the batch, the embeddings for v, r and u are looked up and the score for the triple is computed according to φ. then the embeddings and the parameters of φ are updated based on the predicted scores, the labels of the triples, and a loss function l. algorithm 1 transductive training (one epoch) inputs n : negative ratio, l : loss function 1: for @xmath7: triples, labels ← nextbatch (batch, n) 3: scores ← [] 4: distmult @xcite : in distmult, z z z @xmath8. for a triple (v, r, u), let z z z v , z z z r , z z z @xmath9, r and u respectively where each embedding is obtained by looking up the z z z ent and z z z rel matrices. distmult defines the score for the triple as φ(z z z v , z z z r , z z z u ) = z z z v , z z z r , z z z u , i.e. the sum of the element-wise product of the head, relation, and tail embeddings. ## out-of-sample kg reasoning we define out-of-sample reasoning for kgs as: definition 1. out-of-sample reasoning for kgs is the problem of training a model on a kg g with entities v and relations r such that at the test time, the model can be used for making predictions about any out-of-sample entity @xmath10, r, u) : @xmath11, @xmath12, r, v) : @xmath13, @xmath14. according to the definition, g v is observed only at the test time and so during training, the model does not observe any triples involving v. to develop a representation learning model for out-ofsample reasoning in kgs, one needs to learn i) embeddings for the in-sample entities in v and the relations in r, ii) a function φ from triples to scores, and iii) a function from g v and the in-sample entity and relation embeddings to an embedding for v that can be used to make further predictions about v. one possible way of extending transductive models such as distmult to the out-of-sample domain is by following the standard training procedure outlined in algorithm 1 and then defining an aggregation function with no learnable parameters which, at inference time, provides an embedding for an out-of-sample entity v based on the embeddings of the entities and relations in g v . a simple aggregation function, for instance, can be the average of the embeddings for entities {u : ∃r s.t. ## datasets we created datasets for out-of-sample representation learning over kgs using wn18rr @xcite and fb15k-237 @xcite , two standard datasets for kg completion. wn18rr is a subset of wordnet @xcite and fb15k-237 is a subset of freebase @xcite . we call the two datasets own18rr and ofb15k-237 respectively, where "o" in the beginning of the name stands for "out-of-sample". the statistics for these datasets can be found in we outline the steps we took for creating the datasets. ## experiments and results to measure the performance of different models, for any out-of-sample entity v in the test set with triples g v , we create |g v | queries where in the i-th query, we use our learned model to compute an embedding for v given all except the i-th triple in g v and use that embedding to make a prediction about the i-th triple. figure 2 represents statistics on the number of triples used to compute the embedding of the out-of-sample entities in the test set for both own18rr and ofb15k-237. if the i-th triple is of the form (v, r, u), then we create the query (v, r, ?) and find the ranking our model assigns to u (the correct answer to the query) among entities @xmath15, r, u ) ∈ g v (the (v, r, u ) ∈ g v constraint is known as the filtered setting). we follow a similar procedure for the case where the i-th triple is of the form (u, r, v). let κ (v,r,?),u represent the rank of u for query (v, r, ?). we report filtered mean reciprocal rank (mrr) computed as: ## conclusion we studied out-of-sample representation learning for non-attributed multi-relational graphs -a problem that is surprisingly poorly studied. we created two benchmarks for this task and outlined the procedure we followed for creating these datasets to facilitate the creation of more datasets in the future. we also developed several baselines, a new training algorithm, and two aggregation models for out-of-sample representation learning. future work includes developing new training strategies, testing other aggregation functions, combining the aggregation functions with other transductive models, extending out-of-sample reasoning to temporal kg completion and knowledge hypergraph completion (e.g., extending the proposed training algorithm and aggregation functions to the temporal or hypergraph versions of distmult or simple @xcite ) transferring the knowledge learned over one graph to a new graph with new entities (similar to @xcite ), studying the similarities and differences between out-of-sample representation learning and out-of-vocabulary word embedding, and testing the proposed models on relational domains other than knowledge graphs.