A survey of embedding models of entities and relationships for knowledge graph completion (2020)

Abstract: Knowledge graphs (KGs) of real-world facts about entities and their relationships are useful resources for a variety of natural language processing tasks. However, because knowledge graphs are typically incomplete, it is useful to perform knowledge graph completion or link prediction, i.e. predict whether a relationship not in the knowledge graph is likely to be true. This paper serves as a comprehensive survey of embedding models of entities and relationships for knowledge graph completion, summarizing up-to-date experimental results on standard benchmark datasets and pointing out potential future research directions.

## introduction let us revisit the classic word2vec example of a "royal" relationship between "king" and "man", and between "queen" and "woman". as illustrated in this example: v king -v man ≈ v queen -v woman , word vectors learned from a large corpus can model relational similarities or linguistic regularities between pairs of words as translations in the projected vector space @xcite . figure 1 shows another example of a relational similarity between word pairs of countries and capital cities: assume that we consider the country and capital pairs in figure 1 to be pairs of entities rather than word types. that is, we now represent country and capital entities by low-dimensional and dense vectors. the relational similarity between word pairs is presumably to capture a "is capital of" relationship between country and capital entities. also, we represent this relationship by a translation vector v is capital of in the entity vector space. thus, we expect: this intuition inspired the transe model-a well-known embedding model for kg completion or link prediction in kgs @xcite . knowledge graphs are collections of real-world triples, where each triple or fact (h, r, t) in kgs represents some relation r between a head entity h and a tail entity t. kgs can thus be formalized as directed multi-relational graphs, where nodes correspond to entities and edges linking the nodes encode various kinds of relationships @xcite . here entities are real-world things or objects such as persons, places, organizations, music tracks or movies. each relation type defines a certain relationship between entities. for example, as illustrated in figure 2 , the relation type "child of" relates person entities with each other, while the relation type "born in" relates person entities figure 1 : two-dimensional projection of vectors of countries and their capitals. this figure is drawn based on @xcite . @xcite . with place entities. several kg examples include the domain-specific kg geneontology and popular generic kgs of wordnet @xcite , yago @xcite , freebase @xcite , nell @xcite and dbpedia @xcite as well as commercial kgs such as google's knowledge graph, microsoft's satori and facebook's open graph. nowadays, kgs are used in a number of commercial applications including search engines such as google, microsoft's bing and facebook's graph search. they also are useful resources for many natural language processing tasks such as question answering @xcite , word sense disambiguation @xcite , semantic parsing @xcite and co-reference resolution @xcite . a main issue is that even very large kgs, such as freebase and dbpedia, which contain billions of fact triples about the world, are still far from complete. in particular, in english dbpedia 2014, 60% of person entities miss a place of birth and 58% of the scientists do not have a fact about what they are known for @xcite . in freebase, 71% of 3 million person entities miss a place of birth, 75% do not have a nationality while 94% have no facts about their parents @xcite . so, in terms of a specific application, question answering systems based on incomplete kgs would not provide a correct answer given a correctly interpreted question. for example, given the incomplete kg in figure 2 , it would be impossible to answer the question "where was jane born ?", although the question is completely matched with existing entity and relation type information (i.e. "jane" and "born in") in kg. consequently, much work has been devoted towards knowledge graph completion to perform link prediction in kgs, which attempts to predict whether a relationship/triple not in the kg is likely to be true, i.e. to add new triples by leveraging existing triples in the kg @xcite @xcite . for example, we would like to predict the missing tail entity in the incomplete triple (jane, born in, ?) or predict whether the triple (jane, born in, miami) is correct or not. embedding models for kg completion have been proven to give state-of-the-art link prediction performances, in which entities are represented by latent feature vectors while relation types are represented by latent feature vectors and/or matrices and/or third-order tensors @xcite . this paper: (1) surveys the embedding models for kg completion, then (2) summarizes up-todate experimental results on the standard evaluation task of entity prediction-which is also referred to as the link prediction task @xcite , and (3) points out potential future research directions. ## a general approach of embedding models for kg completion let e denote the set of entities and r the set of relation types. denote by g the knowledge graph consisting of a set of correct triples (h, r, t), such that h, @xmath0. for each triple (h, r, t), the embedding models define a score function f (h, r, t) of its plausibility. their goal here is to: choose f such that the score f (h, r, t) of a correct triple (h, r, t) is higher than the score f (h , r , t ) for example, transe defines a score function of f transe (h, r, t) = -v h + v r -v t , where h, r and t are represented by low dimensional vectors v h , v r and v t , respectively. as (tokyo, is capital of, japan) is a correct triple, while (tokyo, is capital of, portugal) and (lisbon, is capital of, japan) are incorrect ones, we would have: 1 in section 3 summarizes different prominent score functions f (h, r, t). to learn model parameters (i.e. entity vectors, relation vectors or matrices), the embedding models minimize an objective loss l. a conventional objective loss is the margin-based pairwise ranking loss @xcite : also, the negative log-likelihood (nll) of softmax regression @xcite and the nll of logistic regression @xcite are commonly used in recent kg completion research: foot_0 with: i (h,r,t) = 1 for (h, r, t) ∈ g -1 for (h, r, t) ∈ g to corrupt the head or tail entities, a common strategy is to uniformly replace the entities when sampling incorrect triples @xcite , however it results in many false negative labels @xcite . domain sampling @xcite generates corrupted triples by sampling entities from the same domain or from the set of relation-dependent entities. the "bernoulli" trick @xcite is widely used to set different probabilities for generating head or tail entities: for each relation type r, we calculate the averaged number a r,1 of heads h for a pair (r, t) and the averaged number a r,2 of tails t for a pair (h, r). we then define a bernoulli distribution with success probability λ @xmath1,1 a r,1 + a r,2 for sampling: given a correct triple (h, r, t), we corrupt this triple by replacing head entity with probability λ r while replacing the tail entity with probability (1 -λ r ). recently, @xcite and @xcite proposed adversarial learning-based strategies for sampling incorrect triples. however, they did not provide a comparison between the adversarial learning-based strategies and the "bernoulli" trick. ## evaluation task the standard evaluation task of entity prediction, i.e. the link prediction task @xcite , is proposed to evaluate embedding models for kg completion. foot_2 datasets: information about benchmark datasets for kg completion evaluation is given in fb15k and wn18 are derived from the large real-world kg freebase @xcite and the large lexical kg wordnet @xcite , respectively. toutanova and chen (2015 ) noted that fb15k and wn18 are not challenging datasets because they contain many reversible triples. @xcite showed a concrete example: a test triple (feline, hyponym, cat) can be mapped to a training triple (cat, hypernym, feline), thus knowing that "hyponym" and "hypernym" are reversible allows us to easily predict the majority of test triples. so, datasets fb15k-237 @xcite and wn18rr @xcite are created to serve as realistic kg completion datasets which represent a more challenging learning setting. fb15k-237 and wn18rr are subsets of fb15k and wn18, respectively.