Injecting Semantics for Explaining Link Predictions

KGs, while effective for organizing information, frequently encounter incompleteness issues [143] due to challenges in data collection, (semi-)automatic KG construction and the dynamic nature of the real world. Indeed, KGs are often constructed through automated complex processes. Therefore, the general field of KG refinement emerged to tackle this issue. Link Prediction (LP) and Triple Classification stand out as two pivotal tasks in the field. The aim of such tasks roughly corresponds to infer missing triples and to classify new ones as true or not, respectively. Moving forward, our main emphasis will be directed towards the task of Link Prediction (LP).
To ground our exploration of LP models in a formal context, we first establish a few key conventions. A KG is defined as a directed edge-labeled graph G = (V, E, L), as reported in 2.1.1. LP is the task of exploiting the existing triples in a KG to infer missing ones. This could involve predicting the appropriate entity that completes a tail prediction, represented as ⟨s, p, ?⟩, or a head prediction, denoted as ⟨?, p, o⟩. Broadly, in any predictive task, the entity that we’re aware of is referred to as the source entity, and the one we’re trying to predict is the target entity. For the remainder of this chapter, our focus will predominantly revolve around tail predictions.
Over time, a variety of link prediction (LP) methodologies have been explored, mostly grounded on Machine Learning (ML) solutions. Some of these are based on observable attributes, making use of techniques like Rule Mining [42, 1, 41, 74, 85, 84] or utilizing the Path Ranking Algorithm, as discussed in [76, 75]. In recent years, researchers have started to experiment with identifying hidden features of the graph. They do this by learning to create vector representations of the graph’s elements, a concept commonly referred to as Knowledge Graph Embeddings (KGEs).
Embeddings, in a broad sense, are numerical vectors that can represent various types of elements. Depending on the specific domain, these could include words, people, products, and more. These embeddings are automatically learned based on how the corresponding elements appear and interact with each other in datasets that reflect real-world conditions. For instance, word embeddings, which represent words based on their co-occurrence in text, have become a common tool in language processing [86].
KGEs are similar in purpose, but they represent the entities and relations within a KG. These embeddings encapsulate the original graph structure, allowing for the identification of potential new connections within it. Hereafter we will interchangeably use the expression graph as synonym of KG and we will also adopt the following notation, we’ll use italics for KG elements and bold for their corresponding embeddings. For instance, e may represent a general entity within the graph, while e would represent its corresponding embedding. We will use lowercase letters for one-dimensional embeddings and uppercase for those with two or more dimensions. All link prediction (LP) models that rely on embeddings define a scoring function Φ(s, p, o) to gauge the likelihood of a particular triple ⟨s, p, o⟩ by using the embeddings of its constituent elements. Unless specified otherwise, we’ll operate under the assumption that the higher the scoring function’s value, the more plausible the triple is.
KGEs are grounded on ML solutions. Hence, G is further split into a training set Gtrain , a validation set Gval and a test set Gtest. The training set Gtrain is used to train the model. The validation set Gval assists in tuning the hyperparameters. The test set Gtest evaluates the model’s predictive performance on unseen data. In the training phase, embeddings are typically initialized at random and then optimized with algorithms like back-propagation through gradient descent. Some models can also learn additional shared parameters that aren’t specific to any particular KG element, such as the weights of neural layers. The ultimate goal of the training process is to identify the values for embeddings and shared parameters that maximize the likelihood of true triples and minimize that of false ones. As such, a loss function is needed in order to assess the scores of all triples in Gtrain. The training requires also negative examples. However, KGs often capture only positive knowledge and as a result negative examples are often missing. To overcome the issue, the positive samples are frequently corrupted to create a set of supposedly false triples Gcorr . These are also included in the loss function, with the aim of minimizing their scores. This combination of positive and negative samples often results in implementing a triplet loss function. Corrupting a triple means replacing its head or tail with a random entity. Over time, different strategies have been proposed for this purpose, such as Bernoulli distribution sampling [141], self-adversarial algorithms [130], or Noise Contrastive Estimation (NCE) [48]. However, given the inherent incompleteness of KGs, models need to operate under the Open World Assumption. This means that any unseen triples, even those derived from corruption, cannot be definitively labeled as false. The methods mentioned above for generating negative examples, while necessary for the training process, can introduce what are known as false negatives. In practice, models are nevertheless trained on these false negatives, as there is currently no foolproof way to generate only true negatives. This issue still underlines the need for more sophisticated techniques for negative sample generation.
The following discussion outlines the predominant LP strategies that are based on embedding methods. The nature of LP systems is highly variable, depending on the modeling of the optimization problem; thus, we report in Figure 2.6 the innovative taxonomy proposed recently by [112]. This taxonomy delineates three principal categories of models, each of which is further divided into subgroups marked by distinct colors. The main categories of models are: (1) Tensor Decomposition; (2) Geometric; and (3) Deep Learning. Subsequently, we proceed to examine each of these categories individually.