Knowledge graph embedding

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.

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. A knowledge graph \mathcal{G} = \{E, R, F\} is a collection of entities E , relations R , and facts F . A fact is a triple (h, r, t) \in F that denotes a link r \in R between the head h \in E and the tail t \in E of the triple. Another notation that is often used in the literature to represent a triple (or fact) is \langle \text{head}, \text{relation}, \text{tail} \rangle . 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 d , 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. input: The training set S = \{(h, r, t)\} , entity set E , relation set R , embedding dimension k output: Entity and relation embeddings initialization: the entities e and relations r embeddings (vectors) are randomly initialized while stop condition do S_{batch} \leftarrow sample(S, b) // Sample a batch from the training set for each (h, r, t) in S_{batch} do (h', r, t') \leftarrow sample(S') // Sample a corrupted fact T_{batch} \leftarrow T_{batch} \cup \{((h,r, t), (h', r, t')) \} end for Update embeddings by minimizing the loss function end while 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 k=10 . Hits@K reflects the accuracy of an embedding model to predict the relation between two given triples correctly. Hits@K = \frac \in [0, 1] Larger values mean better predictive performances. MR = \frac{1} \sum_{q \in Q}{q} The smaller the value, the better the model. MRR = \frac{1} \sum_{q \in Q}{\frac{1}{q}} \in [0, 1] The larger the index, the better the model. Given a collection of triples (or facts) \mathcal{F} = \{ \langle \text{head}, \text{relation}, \text{tail} \rangle \} , the knowledge graph embedding model produces, for each entity and relation present in the knowledge graph a continuous vector representation. (h, r, t) is the corresponding embedding of a triple with h,t \in {\rm I\!R}^{d} and r \in {\rm I\!R}^{k} , where d is the embedding dimension for the entities, and k for the relations. The score function of a given model is denoted by \mathcal{f}_{r}(h, t) 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. \mathcal{f}_{r}(h, t) = \delta(\tau(h, r), t) Geometric models are similar to the tensor decomposition model, but the main difference between the two is that they have to preserve the applicability of the transformation \tau in the geometric space in which it is defined. TransE : Uses a scoring function that forces the embeddings to satisfy a simple vector sum equation in each fact in which they appear: h + r = t . The embedding will be exact if each entity and relation appears in only one fact, and so in practice is poor at representing one-to-many, many-to-one, and asymmetric relations. TransH : A modification of TransE for representing types of relations, by using a hyperplane as a geometric space. In TransH, the relation embedding is on a different hyperplane depending on the entities it interacts with. So, to compute, for example, the score function of a fact, the embedded representation of the head and tail need to be projected using a relational projection matrix on the correct hyperplane of the relation. TransR : A modification of TransH that uses different spaces embedding entities versus relations, thus separating the semantic spaces of entities and relations. TransR also uses a relational projection matrix to translate the embedding of the entities to the relation space. TransD: In TransR, the head and the tail of a given fact could belong to two different types of entities. For example, in the fact (\text{Obama}, \text{president of}, \text{USA}) , Obama is a person and USA is a country. Matrix multiplication is an expensive procedure in TransR to compute the projection. In this context, TransD uses two vectors for each entity-relation pair to compute a dynamic mapping that substitutes the projection matrix while reducing the dimensional complexity. The first vector is used to represent the semantic meaning of the entities and relations, the second to compute the mapping matrix. TransA: All the translational models define a score function in their representation space, but they oversimplify this metric loss. Since the vector representation of the entities and relations is not perfect, a pure translation of h + r could be distant from t , and a spherical equipotential Euclidean distance makes it hard to distinguish which is the closest entity. TransA, instead, introduces an adaptive Mahalanobis distance to weights the embedding dimensions, together with elliptical surfaces to remove the ambiguity.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1376502793 under CC BY-SA 4.0; modifications have been made.