R el W alk - A Latent Variable Model Approach to Knowledge Graph Embedding (2021)

Abstract: Embedding entities and relations of a knowledge graph in a low-dimensional space has shown impressive performance in predicting missing links between entities. Although progresses have been achieved, existing methods are heuristically motivated and theoretical understanding of such embeddings is comparatively underdeveloped. This paper extends the random walk model of word embeddings to Knowledge Graph Embeddings (KGEs) to derive a scoring function that evaluates the strength of a relation R between two entities h (head) and t (tail). Moreover, we show that marginal loss minimisation, a popular objective used in much prior work in KGE, follows naturally from the log-likelihood ratio maximisation under the probabilities estimated from the KGEs according to our theoretical relationship. We propose a learning objective motivated by the theoretical analysis to learn KGEs from a given knowledge graph. Using the derived objective, accurate KGEs are learnt from FB15K237 and WN18RR benchmark datasets, providing empirical evidence in support of the theory.

## introduction knowedge graphs (kgs) such as freebase @xcite organise information in the form of graphs, where entities are represented by the vertices and the relations between two entities are represented by the edges that connect the corresponding vertices. despite the best efforts to create complete and large-scale kgs, most kgs remain incomplete and do not represent all the relations that exist between entities @xcite . in particular, new entities are constantly being generated, and new relations are formed between new as well as existing entities. therefore, it is unrealistic to assume that a real-world kg would be complete at any given time point. developing approaches for kg completion is an important research field associated with kgs. kg components can be embedded into numerical formats by learning representations (a.k.a embeddings) for the entities and relations in a given kg. the learnt kges can be used for link prediction, which is the task of predicting whether a particular relation exists between two given entities in the kg. specifically, given kges for entities and relations, in link prediction, we predict r that is most likely to exist between h and t according to some scoring formula. thus, by embedding entities and relations that exist in a kg in some (possibly lower-dimensional and latent) space, we can infer previously unseen relations between entities, thereby expanding a given kg. kge can be seen as a two-step process. given a kg represented by a set of relational triples (h, r, t), where a semantic relation r holds between a head entity h and a tail entity t, first a scoring function is defined that measures the relational strength of a triple (h, r, t). second,the entity and relation embeddings that optimise the defined scoring function are learnt using some optimisation method. despite the wide applications of entity and relation embeddings created via kge methods, the existing scoring functions are heuristically motivated to capture some geometric requirements of the embedding space. for example, transe @xcite assumes that the entity and relation embeddings co-exist in the same (possibly lower dimensional) vector space and translating (shifting) the head entity embedding by the relation embedding must make it closer to the tail entity embedding, whereas complex @xcite models the asymmetry in relations using the component-wise multi-linear inner-product among entity and relation embeddings. theoretical understanding of kge methods is under developed. for example, it is not clear how the heuristically defined kge objectives relate to the generative process of a kg. providing such a theoretical understanding of the kge process will enable us to develop kge methods that address the weaknesses in the existing kge methods. for this purpose, we propose relational walk (relwalk), a theoretically motivated generative approach for learning kges. we are particularly interested in the semantic relationships that exist between entities such as the is-ceo-of relation between a person such as jeff bezos and a company such as amazon inc. we model kge as a random walk over the kg. specifically, a random walker at the vertex corresponding to the (head) entity h will uniformly at random select one of the outgoing edges corresponding to the semantic relation r, which will lead it to the vertex corresponding to the (tail) entity t. continuing this random walk will result in a traversal over a path in the kg. based on this random walk model we derive a relationship between the probability of r holding between h and t, p(h, t | r), and their kges r, h and t. interestingly, the derived relationship is not covered by any of the previously proposed heuristically-motivated scoring functions, providing the first-ever kge method with a provable generative explanation. we show that the margin loss, a popular training objective in prior work on kge, naturally emerges as the log-likelihood ratio computed from the derived p(h, t | r). based on this result, we derive a training objective that is optimised for learning kges that satisfy our theoretical relationship. this enables us to empirically verify the theoretical relationships that we derived from the proposed random walk process. using fb15k237 and wn18rr benchmarks, we evaluate the learnt kges on link prediction and triple classification. although we do not obtain state-of-the-art (sota) performance on these benchmark datasets, kges learnt using relwalk perform consistently well on both tasks, providing empirical support to the theoretical analysis conducted in this paper. we re-emphasise that our main objective in this paper is to study kges from an interpretable theoretical perspective and not necessarily improving sota. to this end, we study the relationship between the concentration of the partition function as predicted by our theoretical analysis and the performance of the learnt kges. we observe that when the partition function is narrowly distributed, we are able to learn accurate kges. moreover, we empirically verify that the learnt relation embedding matrices satisfy the orthogonality property as expected by the theoretical analysis. ## related work at a high-level of abstraction, kge methods can be seen as differing in their design choices for the following two main problems: (a) how to represent entities and relations, and (b) how to model the interaction between two entities and a relation that holds between them. next, we briefly discuss prior proposals to those two problems (refer to @xcite ; nguyen (2017); @xcite for an extended survey on kge). a popular choice for representing entities is to use vectors @xcite @xcite , whereas relations have been represented by vectors, matrices @xcite @xcite or tensors @xcite . complex @xcite introduced complex vectors for kges to capture the asymmetry in semantic relations. @xcite further improved compiex by imposing non-negativity and entailment constraints to complex. ## relational walk let us consider a kg, d, where the knowledge is represented by relational triples (h, r, t) ∈ d. here, r is a relational predicate with two arguments, where h (head) and t (tail) entities respectively filling the first and second arguments. in this work, we assume relations to be asymmetric in general (if (h, r, t) ∈ d then it does not necessarily follow that (t, r, h) ∈ d). the goal of kge method score function relation f (h, r, t) parameters unstructured @xcite ||h -t|| ℓ 1/2 none structured @xcite ||r 1 h -r 2 t|| ℓ1,2 r 1 , r 2 ∈ r d×d transe @xcite ||h + r -t|| ℓ 1/2 @xmath0, r, t @xmath1, r, t @xmath2 kge is to learn embeddings for the relations and entities in the kg such that the entities that participate in similar relations are embedded closely to each other in the entity embedding space, while at the same time relations that hold between similar entities are embedded closely to each other in the relational embedding space. we call the learnt entity and relation embeddings collectively as kges. we assume that entities and relations are embedded in the same vector space, allowing us to perform linear algebraic operations using the embeddings in the same vector space. following our aforementioned modelling of a knowledge base as a graph, let us consider a random walker who is at a vertex corresponding to some entity h. this entity will have one or more semantic relations with other entities in the kg. the random walker will uniformly at random pick one of the outgoing edges corresponding to a particular semantic relation r, and follow it to land on the entity t. this one-step of the random walk thus generates a tuple (h, r, t) in the kg. the random walker proceeds by using t as the new starting point. multiple steps of this random walk trace a single path in the kg. to illustrate a random walk over a kg, let us assume that we are currently at the vertex corresponding to the company entity amazon inc. possible outgoing edges at amazon inc. would correspond to semantic relations such as has-ceo, is-headquarted-at, founded-in etc., where amazon inc. is the head entity. if there are only three such outgoing relations at amazon inc., then the random walker will pick any one of those relations with a probability 1/3. for example, by selecting has-ceo, is-headquarted-at or founded-in the random walker would arrive at entities respectively jeff bezos, seattle or 1994. let us assume that the random walker selected the has-ceo relation and landed at jeff bezos. the random walker might subsequently continue its random walk from jeff bezos following the relation born-in and transiting to new mexico, us. prior work studying inferences in kgs have successfully used random walk models similar to what we describe here @xcite @xcite . let us consider a random walk characterised by a time-dependent knowledge vector c k , where k is the current time step. the knowledge vector represents the knowledge we have about a particular group of entities and relations that express some facts about the world. for example, when we are talking about amazon inc., we will use the knowledge associated with amazon inc. such as its ceo, location of the headquarters, when it was founded etc. therefore, it is intuitive to assume that the entities associated with amazon inc. with some set of semantic relations can be generated from this knowledge vector. each entity and relation has time-independent latent representations that capture their correlations with c k . for entities h and t, we denote their representations by d-dimensional vectors respectively h, @xmath5. we assume the task of generating a relational triple (h, r, t) in a given kg to be a two-step process as described next. first, given the current knowledge vector at time k, @xmath6, we assume that the probability of an entity h satisfying the first argument of r to be given by the loglinear entity production model in (1). here, r 1 ∈ r d×d is a relation-specific orthogonal matrix that evaluates the appropriateness of h for the first argument of r. for example, if r is the is-ceo-of relation, we would require a person as the first argument and a company as the second argument of r. however, note that the role of r 1 extends beyond simply checking the types of the entities that can fill the first argument of a relation. for our example above, not all people are ceos and r 1 evaluates the likelihood of a person to be selected as the first argument of the ceo-of relation. z c is a normalisation coefficient such that @xmath7, c) = 1, where the vocabulary v is the set of all entities in the kg. after generating h, the state of our random walker changes to @xmath8, and we next gener-ate the second argument of r with the probability given by (2). here, r 2 ∈ r d×d is a relation-specific orthogonal matrix that evaluates the appropriateness of t as the second argument of r. z c is a normalisation coefficient such that @xmath9, c ) = 1. following our previous example of is-ceo-of relation, r 2 evaluates the likelihood of an organisation to be a company with a ceo position. importantly, r 1 and r 2 are representations of the relation r and independent of the entities. therefore, we consider (r 1 and r 2 ) to collectively represent the embedding of r. orthogonality of r 1 , r 2 is a requirement for the mathematical proof and also acts as a regularisation constraint to prevent overfitting by restricting the relational embedding space @xcite . intuitively, orthogonality of the relation embedding matrices ensures that the length of the head and tail entity embeddings are not altered during the generation of the tuple. orthogonal transformation has been shown to improve the performance of relation representation in prior work. for example, @xcite apply orthogonal transformation that extends rotate @xcite to model complex relations (e.g., n-to-n). for relationships in word embedding space, ethayarajh (2019) use orthogonal transformation for analogical reasoning between words. the performance of hypernymy prediction through orthogonal projections has been improved as shown in @xcite . the knowledge vector c k performs a slow random walk (meaning c k+1 is obtained from c k by adding a small random displacement vector) such that the head and tail entities of a relation are generated under similar knowledge vectors. more specifically, we assume that ||c k -c k+1 || ≤ 2 for some small 2 > 0. this is a realistic assumption for generating the two entity arguments in the same relational triple because, if the knowledge vectors were significantly different in the two generation steps, then it is likely that the corresponding relations are also different, which would not be coherent with the above-described generative process. moreover, we assume that the knowledge vectors are distributed uniformly in the unit sphere and denote the distribution of knowledge vectors by c. to relate kges with the connections in the graph, we must estimate the probability that h and t satisfy the relation r, p(h, t | r), which can be ob-tained by taking the expectation of p(h, t | r, c, c ) w.r.t. c, c ∼ c given by (3). lemma 1 (concentration lemma). if the entity embedding vectors satisfy the bayesian prior @xmath10, where v is from the spherical gaussian distribution, and s is a scalar random variable, which is always bounded by a constant κ, then the entire ensemble of entity embeddings satisfies that: for @xmath11, and δ = exp(-ω(log 2 n)), where @xmath12. refer to appendix a for the proof of the concentration lemma. we empirically investigate the relationship between the performance of the kges and the degree to which lemma 1 is satisfied in subsection 5.1. under the conditions required to satisfy lemma 1, the following main theorem of this paper holds: theorem 1. suppose that the entity embeddings satisfy (1). then, we have proof sketch: let f be the event that both c and c are within (1 ± z )z. then, from lemma 1 and the union bound, event f happens with probability at least 1 -2 exp(-ω(log 2 n)). the r.h.s. of ( 5 ) can be split into two parts t 1 and t 2 according to whether f happens or not. t 1 can be approximated as given by ( 12 ). on the other hand, t 2 can be shown to be a constant, independent of d, given by ( 13 ). the vocabulary size n of real-world kgs is typically over 10 5 , for which t 2 becomes negligibly small. therefore, it suffices to consider only t 1 . because of the slowness of the random walk we have c ≈ c . using the law of total expectation we can write t 1 as follows: plugging (51) back in ( 14 ) provides the claim of the theorem. detailed proof is shown in appendix b. the relationship given by ( 9 ) indicates that head and tail entity embeddings are first transformed respectively by r 1 and r 2 , and the squared ℓ 2 norm of the sum of the transformed vectors is proportional to the probability p(h, t | r). ## learning kg embeddings in this section, we derive a training objective from theorem 1 that we can then optimise to learn kges. the goal is to empirically validate the theoretical result by evaluating the learnt kges. kgs represent information about relations between two entities in the form of relational triples. the joint probability p(h, r, t) given by theorem 1 is useful for determining whether a relation r exists between two given entities h and t. for example, if we know that with a high probability that r holds between h and t, then we can append (h, r, t) to the kg. the task of expanding kgs by predicting missing links between entities or relations is known as the link prediction problem @xcite . in particular, if we can automatically append such previously unknown knowledge to the kg, we can expand the kg and address the knowledge acquisition bottleneck. to derive a criteria for determining whether a link must be predicted among entities and relations, let us consider a relational triple (h, r, t) ∈ d that exists in a given kg d. we call such relational triples as positive triples because from the assumption it is known that r holds between h and t. on the other hand, consider a negative relational triple (h , r, t ) ∈ d formed by, for example, randomly perturbing a positive triple. a popular technique for generating such (pseudo) negative triples is to replace h or t with a randomly selected different instance of the same entity type. as an alternative for random perturbation, @xcite proposed a method for generating negative instances using adversarial learning. here, we are not concerned about the actual method used for generating the negative triples but assume a set of negative triples, d, generated using some method, to be given. given a positive triple (h, r, t) ∈ d and a negative triple (h , r, t ) ∈ d, we would like to learn kges such that a higher probability is assigned to (h, r, t) than that assigned to (h , r, t ). we can formalise this requirement using the likelihood ratio given by ( 16 ). here, η > 1 is a threshold that determines how higher we would like to set the probabilities for the positive triples compares to that of the negative triples. if a positive triple (h, r, t) is correctly assigned a higher probability than a negative triple p(h , r, t ), ## empirical validation to empirically evaluate the theoretical result stated in theorem 1, we learn kges (denoted by rel-walk) by minimising the marginal loss objective derived in section 4. we use the fb15k237, fb13 (subsets of freebase) and wn18rr (a subset of wordnet) datasets, which are standard benchmarks for kge. we use the standard training, validation and test splits. statistics about the datasets and training details are in appendix d. relwalk is implemented in the open-source toolkit openke @xcite and the code and learnt kges will are publicly available foot_0 . we conduct two evaluation tasks: link prediction (predict the missing head or tail entity in a given triple (h, r, ?) or (?, r, t)) @xcite and triple classification (predict whether a relation r holds between h and t in a given triple in we note that our goal in this paper is not to claim sota for kge but to provide a theoretical understanding with empirical validation. to this end, the experimental results support our theoretical claim and emphasise the importance of theoretically motivating the kge scoring function design process. ## conclusion we proposed relwalk, a generative model of kge and derived a theoretical relationship between the probability of a triple consisting of head, tail entities and the relation that exists between those two entities, and the embedding vectors for the two entities and embeddings matrices for the relation. in relwalk, we represented entities by vectors and relations by matrices. we then proposed a learning objective based on the theoretical relationship we derived to learn entity and relation embeddings from a given knowledge graph. experimental results on a link prediction and a triple classification tasks show that relwalk outperforms several previously proposed kge learning methods. the key assumptions of relwalk are validated by empirically analysing the relationship between such assumptions and the performance of the learnt embeddings from a kg. moreover, we studied the compressibility of the learnt relation embeddings and discovered that using only 60% of the components, we can approximate the relation embeddings without any significant loss in performance.