In representation learning, knowledge graph embedding (KGE), also called knowledge representation learning (KRL), or multi-relation learning, is a machine learning task of learning a low-dimensional representation of a knowledge graph's entities and relations while preserving their meaning. Leveraging their embedded representation, knowledge graphs can be used for various applications such as link prediction, triple classification, entity recognition, clustering, and relation extraction.
Definition A knowledge graph is a collection of entities , relations , and facts . A fact is a triple that denotes a link between the head and the tail of the triple. Another notation that is often used in the literature to represent a triple (or fact) is . This notation is called the Resource Description Framework (RDF). A knowledge graph represents the knowledge related to a specific domain; leveraging this structured representation, it is possible to infer a piece of new knowledge from it after some refinement steps. However, nowadays, people have to deal with the sparsity of data and the computational inefficiency to use them in a real-world application.
The embedding of a knowledge graph is a function that translates each entity and each relation into a vector of a given dimension , called embedding dimension. It is even possible to embed the entities and relations with different dimensions. The embedding vectors can then be used for other tasks.
A knowledge graph embedding is characterized by four aspects:
Representation space: The low-dimensional space in which the entities and relations are represented. Scoring function: A measure of the goodness of a triple-embedded representation. Encoding models: The modality in which the embedded representation of the entities and relations interact with each other. Additional information: Any additional information coming from the knowledge graph that can enrich the embedded representation. Usually, an ad hoc scoring function is integrated into the general scoring function for each additional piece of information.
Embedding procedure All algorithms for creating a knowledge graph embedding follow the same approach. First, the embedding vectors are initialized to random values. Then, they are iteratively optimized using a training set of triples. In each iteration, a batch of size triples is sampled from the training set, and a triple from it is sampled and corruptedi.e., a triple that does not represent a true fact in the knowledge graph. The corruption of a triple involves substituting the head or the tail (or both) of the triple with another entity that makes the fact false. The original triple and the corrupted triple are added in the training batch, and then the embeddings are updated, optimizing a scoring function. Iteration stops when a stop condition is reached. Usually, the stop condition depends on the overfitting of the training set. At the end, the learned embeddings should have extracted semantic meaning from the training triples and should correctly predict unseen true facts in the knowledge graph.
Pseudocode The following is the pseudocode for the general embedding procedure. algorithm Compute entity and relation embeddings input: The training set , entity set , relation set , embedding dimension output: Entity and relation embeddings
initialization: the entities and relations embeddings (vectors) are randomly initialized
while stop condition do // Sample a batch from the training set for each in do // Sample a corrupted fact
end for Update embeddings by minimizing the loss function end while
Performance indicators These indexes are often used to measure the embedding quality of a model. The simplicity of the indexes makes them very suitable for evaluating the performance of an embedding algorithm even on a large scale. Given Q as the set of all ranked predictions of a model, it is possible to define three different performance indexes: Hits@K, MR, and MRR.
Hits@K Hits@K or in short, H@K, is a performance index that measures the probability to find the correct prediction in the first top K model predictions. Usually, it is used . Hits@K reflects the accuracy of an embedding model to predict the relation between two given triples correctly.
Hits@K
Larger values mean better predictive performances.
Mean rank (MR) Mean rank is the average ranking position of the items predicted by the model among all the possible items.
The smaller the value, the better the model.
Mean reciprocal rank (MRR) Mean reciprocal rank measures the number of triples predicted correctly. If the first predicted triple is correct, then 1 is added, if the second is correct is summed, and so on.
Mean reciprocal rank is generally used to quantify the effect of search algorithms.
The larger the index, the better the model.
Applications Machine learning tasks Knowledge graph completion (KGC) is a collection of techniques to infer knowledge from an embedded knowledge graph representation. In particular, this technique completes a triple inferring the missing entity or relation. The corresponding sub-tasks are named link or entity prediction (i.e., guessing an entity from the embedding given the other entity of the triple and the relation), and relation prediction (i.e., forecasting the most plausible relation that connects two entities).
Triple Classification is a binary classification problem. Given a triple, the trained model evaluates the plausibility of the triple using the embedding to determine if a triple is true or false. The decision is made with the model score function and a given threshold. Clustering is another application that leverages the embedded representation of a sparse knowledge graph to condense the representation of similar semantic entities close in a 2D space.
Real world applications The use of knowledge graph embedding is increasingly pervasive in many applications. In the case of recommender systems, the use of knowledge graph embedding can overcome the limitations of the usual reinforcement learning, as well as limitations of the conventional collaborative filtering method. Training this kind of recommender system requires a huge amount of information from the users; however, knowledge graph techniques can address this issue by using a graph already constructed over a prior knowledge of the item correlation and using the embedding to infer from it the recommendation. Drug repurposing is the use of an already approved drug, but for a therapeutic purpose different from the one for which it was initially designed. It is possible to use the task of link prediction to infer a new connection between an already existing drug and a disease by using a biomedical knowledge graph built leveraging the availability of massive literature and biomedical databases. Knowledge graph embedding can also be used in the domain of social politics.
Models
Given a collection of triples (or facts) , the knowledge graph embedding model produces, for each entity and relation present in the knowledge graph a continuous vector representation. is the corresponding embedding of a triple with and , where is the embedding dimension for the entities, and for the relations. The score function of a given model is denoted by and measures the distance of the embedding of the head from the embedding of tail given the embedding of the relation. In other words, it quantifies the plausibility of the embedded representation of a given fact.
Rossi et al. propose a taxonomy of the embedding models and identifies three main families of models: tensor decomposition models, geometric models, and deep learning models.
Tensor decomposition model The tensor decomposition is a family of knowledge graph embedding models that use a multi-dimensional matrix to represent a knowledge graph, that is partially knowable due to gaps of the graph describing a particular domain thoroughly. In particular, these models use a third-order (3D) tensor, which is then factorized into low-dimensional vectors that are the embeddings. A third-order tensor is suitable for representing a knowledge graph because it records only the existence or absence of a relation between entities, and so is simple, and there is no need to know a priori the network structure, making this class of embedding models light, and easy to train even if they suffer from high-dimensionality and sparsity of data.
Bilinear models This family of models uses a linear equation to embed the connection between the entities through a relation. In particular, the embedded representation of the relations is a bidimensional matrix. These models, during the embedding procedure, only use the single facts to compute the embedded representation and ignore the other associations to the same entity or relation. DistMult: Since the embedding matrix of the relation is a diagonal matrix, the scoring function can not distinguish asymmetric facts. ComplEx: As DistMult uses a diagonal matrix to represent the relations embedding but adds a representation in the complex vector space and the hermitian product, it can distinguish symmetric and asymmetric facts. This approach is scalable to a large knowledge graph in terms of time and space cost. ANALOGY: This model encodes in the embedding the analogical structure of the knowledge graph to simulate inductive reasoning. Using a differentiable objective function, ANALOGY has good theoretical generality and computational scalability. It is proven that the embedding produced by ANALOGY fully recovers the embedding of DistMult, ComplEx, and HolE. SimplE: This model is the improvement of canonical polyadic decomposition (CP), in which an embedding vector for the relation and two independent embedding vectors for each entity are learned, depending on whether it is a head or a tail in the knowledge graph fact. SimplE resolves the problem of independent learning of the two entity embeddings using an inverse relation and average the CP score of and . In this way, SimplE collects the relation between entities while they appear in the role of subject or object inside a fact, and it is able to embed asymmetric relations.
Non-bilinear models
HolE: HolE uses circular correlation to create an embedded representation of the knowledge graph, which can be seen as a compression of the matrix product, but is more computationally efficient and scalable while keeping the capabilities to express asymmetric relation since the circular correlation is not commutative. HolE links holographic and complex embeddings since, if used together with Fourier, can be seen as a special case of ComplEx. TuckER: TuckER sees the knowledge graph as a tensor that could be decomposed using the Tucker decomposition in a collection of vectorsi.e., the embeddings of entities and relationswith a shared core. The weights of the core tensor are learned together with the embeddings and represent the level of interaction of the entries. Each entity and relation has its own embedding dimension, and the size of the core tensor is determined by the shape of the entities and relations that interact. The embedding of the subject and object of a fact are summed in the same way, making TuckER fully expressive, and other embedding models such as RESCAL, DistMult, ComplEx, and SimplE can be expressed as a special formulation of TuckER.