Dimensionality reduction of graph-based semantic data objects [machine learning task]
In representation learning, knowledge graph embedding (KGE), also referred to as 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 semantic meaning. Leveraging their embedded representation, knowledge graphs (KGs) can be used for various applications such as link prediction, triple classification, entity recognition, clustering, and relation extraction.
Definition.
A knowledge graph formula_1 is a collection of entities formula_2, relations formula_3, and facts formula_4. A "fact" is a triple formula_5 that denotes a link formula_6 between the head formula_7 and the tail formula_8 of the triple. Another notation that is often used in the literature to represent a triple (or fact) is formula_9. This notation is called 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 translates each entity and relation of a knowledge graph, formula_10 into a vector of a given dimension formula_11, called embedding dimension. In the general case, we can have different embedding dimensions for the entities formula_11 and the relations formula_13. The collection of embedding vectors for all the entities and relations in the knowledge graph can then be used for downstream tasks.
A knowledge graph embedding is characterized by four different aspects:
Embedding procedure.
All the different knowledge graph embedding models follow roughly the same procedure to learn the semantic meaning of the facts. First of all, to learn an embedded representation of a knowledge graph, the embedding vectors of the entities and relations are initialized to random values. Then, starting from a training set until a stop condition is reached, the algorithm continuously optimizes the embeddings. Usually, the stop condition is given by the overfitting over the training set. For each iteration, is sampled a batch of size formula_14 from the training set, and for each triple of the batch is sampled a random corrupted fact—i.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. At the end of the algorithm, the learned embeddings should have extracted the semantic meaning from the 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 is
 input: The training set formula_15, 
 entity set formula_16, 
 relation set formula_3, 
 embedding dimension formula_13
 output: Entity and relation embeddings
 initialization: "the entities" formula_19 "and relations" formula_20 "embeddings (vectors) are randomly initialized"
 while stop condition do
 formula_21 // From the training set randomly sample a batch of size b
 for each formula_22 in formula_23 do
 formula_24 // sample a corrupted fact of triple
 formula_25 
 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 ;chem ;Q ;/chem ; as the set of all ranked predictions of a model, it is possible to define three different performance indexes: [Email] MR, and MRR.
[Email]
[Email] or in short, [Email] is a performance index that measures the probability to find the correct prediction in the first top K model predictions. Usually, it is used formula_26. [Email] reflects the accuracy of an embedding model to predict the relation between two given triples correctly.
[Email]
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.
formula_28
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 formula_29 is summed, and so on.
Mean reciprocal rank is generally used to quantify the effect of search algorithms.
formula_30
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. 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) formula_31, the knowledge graph embedding model produces, for each entity and relation present in the knowledge graph a continuous vector representation. formula_22 is the corresponding embedding of a triple with formula_33 and formula_34 , where formula_11 is the embedding dimension for the entities, and formula_13 for the relations. The score function of a given model is denoted by formula_37 and measures the distance of the embedding of the head from the embedding of tail given the embedding of the relation, or 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 the gaps of the knowledge graph describing a particular domain thoroughly. In particular, these models use a three-way (3D) tensor, which is then factorized into low-dimensional vectors that are the entities and relations embeddings. The third-order tensor is a suitable methodology to represent a knowledge graph because it records only the existence or the absence of a relation between entities, and for this reason 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-dimensional 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. 
Geometric models.
The geometric space defined by this family of models encodes the relation as a geometric transformation between the head and tail of a fact. For this reason, to compute the embedding of the tail, it is necessary to apply a transformation formula_40 to the head embedding, and a distance function formula_41 is used to measure the goodness of the embedding or to score the reliability of a fact.
formula_42
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 formula_40 in the geometric space in which it is defined.
Pure translational models.
This class of models is inspired by the idea of translation invariance introduced in word2vec. A pure translational model relies on the fact that the embedding vector of the entities are close to each other after applying a proper relational translation in the geometric space in which they are defined. In other words, given a fact, when the embedding of head is added to the embedding of relation, the expected result should be the embedding of the tail. The closeness of the entities embedding is given by some distance measure and quantifies the reliability of a fact.
Translational models with additional embeddings.
It is possible to associate additional information to each element in the knowledge graph and their common representation facts. Each entity and relation can be enriched with text descriptions, weights, constraints, and others in order to improve the overall description of the domain with a knowledge graph. During the embedding of the knowledge graph, this information can be used to learn specialized embeddings for these characteristics together with the usual embedded representation of entities and relations, with the cost of learning a more significant number of vectors.
Roto-translational models.
This family of models, in addition or in substitution of a translation they employ a rotation-like transformation.
Deep learning models.
This group of embedding models uses deep neural network to learn patterns from the knowledge graph that are the input data. These models have the generality to distinguish the type of entity and relation, temporal information, path information, underlay structured information, and resolve the limitations of distance-based and semantic-matching-based models in representing all the features of a knowledge graph. The use of deep learning for knowledge graph embedding has shown good predictive performance even if they are more expensive in the training phase, data-hungry, and often required a pre-trained embedding representation of knowledge graph coming from a different embedding model.
Convolutional neural networks.
This family of models, instead of using fully connected layers, employs one or more convolutional layers that convolve the input data applying a low-dimensional filter capable of embedding complex structures with few parameters by learning nonlinear features.
Capsule neural networks.
This family of models uses capsule neural networks to create a more stable representation that is able to recognize a feature in the input without losing spatial information. The network is composed of convolutional layers, but they are organized in capsules, and the overall result of a capsule is sent to a higher-capsule decided by a dynamic process routine.
Recurrent neural networks.
This class of models leverages the use of recurrent neural network. The advantage of this architecture is to memorize a sequence of fact, rather than just elaborate single events.
Model performance.
The machine learning task for knowledge graph embedding that is more often used to evaluate the embedding accuracy of the models is the link prediction. Rossi et al. produced an extensive benchmark of the models, but also other surveys produces similar results. The benchmark involves five datasets FB15k, WN18, FB15k-237, WN18RR, and YAGO3-10. More recently, it has been discussed that these datasets are far away from real-world applications, and other datasets should be integrated as a standard benchmark.