Link Prediction (LP) is the problem of inferring new facts in a Knowledge Graph from the already known ones. Recent advances in Machine Learning have led researchers to develop LP models that represent Knowledge Graph elements as vectors in an embedding space. This approach has led to greatly encouraging results, often outperforming traditional approaches; its main shortcoming is its opaqueness, hindering both our understanding and our trust in these models. In this context, we discuss the Kelpie explainability framework. Kelpie can be applied to any embedding-based LP model and can identify the combinations of training facts that have enabled the prediction of a given link. Kelpie can extract two complementary types of explanations, that we dub necessary and suficient .
nationality nationality nationality president_of president_of president_of are leveraging to perform their predictions: in the LP field, this would provide a pathway to gain a deeper understanding of our models, to identify biases or errors in our KGs, and most importantly to decide whether our models can be trusted or not.
In this paper we discuss the Kelpie framework for explaining embedding-based link
predictions, that we originally present in [
A Knowledge Graph (KG) is a labeled directed graph = (ℰ , ℛ, ) where ℰ is the set of nodes, or entities, in the graph; ℛ is its set of labels, or relations; and ⊆ ℰ × ℛ × ℰ is its set of edges linking entities via relations, i.e., its set of facts. In any fact 〈h, r, t〉 the first entity h is the head, r is the relation, and the second entity t is the tail.
Models for embedding-based Link Prediction (LP) typically define a scoring function that estimates the plausibility of any fact using the embeddings of its head, relation and tail. In training, models learn embeddings to optimize the plausibility of the known facts: in prediction, new links are identified by finding which entities, if added to incomplete triples as heads or tails, yield the best scores. A tail prediction ⟨ℎ, , ⟩ is the process that finds to be the best scoring tail for the incomplete triple ⟨ℎ, , ?⟩, i.e., = argmax∈ℰ (ℎ, , ). Head predictions are defined symmetrically. In the following we focus on tail predictions; all our formulations 1https://github.com/AndRossi/Kelpie can be adapted for head predictions analogously.
LP literature usually relies on datasets sampled from real-world KGs, and in which the set of
extracted facts is split into a training set , a validation set , and a test set . In
evaluation, head and tail predictions are performed on each fact in ; in each prediction, the
target entity, i.e, the expected answer, is ranked against all the others in ℰ . The obtained ranks
are then aggregated into standard global metrics: Hits@K (H@K), that measures the fraction
of ranks with value ≤ , and Mean Reciprocal Rank (MRR), that averages the inverse of all
the obtained ranks . Both H@K and MRR are always between 0 and 1; higher values convey
better results. Discussions on the pros and cons of such methodologies can be found in [
For some predictions there can exist more than one correct answer (e.g., in case of 1-to- relations). In this event we follow the common practice called filtered setting of excluding such alternative answers when computing the rank of the target entity.
For a given prediction Kelpie defines two explanation types: necessary and suficient . We indicate with the generic candidate explanation (either necessary or suficient) and with * the explanation we want to identify and return. We use the subscripts (e.g., ) and to denote necessary and suficient explanations respectively. We give definitions of * and * w.r.t. tail predictions 〈ℎ, , 〉, as head predictions can be handled analogously. ∙ * is the smallest set of training facts featuring ℎ such that, removing * from and retraining the model from scratch, the top ranking tail for ⟨ℎ, , ?⟩ changes to any ̸= . ∙ * is the smallest set of training facts featuring ℎ such that, given a set of random entities ⊆ ℰ such that is not the top ranking tail for any ⟨, , ?⟩ prediction, if we add the facts in * to any ∈ and retrain the model from scratch, the top ranking tail for ⟨, , ?⟩ changes to . When this happens, we say that the entities have been converted.
For instance, in the previous example of the tail prediction ⟨_, , ⟩, the set {⟨_, _, ⟩, ⟨_, , ⟩} is a necessary explanation if removing these facts from Barack_Obama the predicted changes from to any other entity. Analogously, the single-sized set {⟨_, _, ⟩} constitutes a suficient explanation if adding it to any non-American entities, e.g., Édith_Piaf, changes their predicted nationality to USA.
The high-level architecture of Kelpie is shown in Figure 2. We briefly describe the Kelpie modules w.r.t. tail predictions ⟨ℎ, , ⟩; head predictions can be handled analogously. Pre-filter. This module analyzes the set of training facts mentioning ℎ, that we call ℎ, in order identify and discard the least promising ones: its overall goal is to reduce the search space for the following steps, preventing combinatorial explosion when ℎ is featured in too many facts. ℎ The Pre-Filter achieves this goal by computing for each fact in a promisingness value based ℎ on the graph topology, and by returning the subset ℱ of the top promising facts. Intuitively, topologically closer entities often bear a stronger semantic relationship: so, for any ⟨ℎ, , ⟩ (or ⟨, , ℎ⟩) connecting ℎ to an entity close to we compute promisingness as the length of the shortest non-oriented path connecting to ; lower values convey better promisingness !&"#$%
Pre-Filter ℱ!&"#$%
∗
Relevance Engine
(and thus higher priority in the filtering). Consider again the example in Figure 1 (left) and
suppose we want to explain the tail prediction ⟨_, , ⟩:
∙ ⟨ _, _, ⟩ has promisingness 0 (the best possible value).
∙ ⟨ _, _, ⟩ has promisingness 1.
∙ ⟨ _, , _⟩ has promisingness 2, as the shortest path from
_ to has length 2: [〈Bill_Gates, born_in, Seattle〉, 〈Seattle, located_in, USA〉].
Explanation Builder. This module explores the space of the candidate explanations that can
be obtained by combining the Pre-Filtered facts, with the goal of identifying the smallest that is
relevant enough for the prediction to explain. The notion of relevance of an explanation embodies
the likelihood of yielding changes in predictions, and it is quantified by the Relevance Engine
described in the next paragraph. Suppose that in the example in Figure 1 (left) only the facts 1 =
⟨_, _, ⟩ and 2 = ⟨_, _, ⟩
survive the Pre-Filtering. The Explanation Builder starts by exploring short explanations, such
as, 1 = {1} and 2 = {2}; then, it iteratively builds longer ones, such as 3 = {1, 2},
until either * is found with relevance higher than a user-specified threshold, or early stopping
policies are enacted. In the latter case, the best explanation seen so far is returned. Among
same-sized explanations (e.g., 1 and 2), a prioritization mechanism based on an of-line
heuristic is used. For details about early stopping and exploration priority, we refer the reader
to Algorithm 3 in [
Relevance Engine. This module aims at estimating how adding or removing training facts from ℎ would afect the prediction to explain. Ideally, the relevance of any candidate explanation could be computed by retraining the model after adding or removing its facts from ; in practice this is unfeasible, so Kelpie introduces the novel ML process of Post-Training (PT). PT consists in using an already trained model to obtain an alternate version, i.e., a mimic, of an entity and of the corresponding embedding. Given , PT amounts to: (i) replicating the training facts mentioning , , and potentially injecting additions/removals; (ii) training a new embedding to optimize the plausibility of those facts, while keeping all the other embeddings and parameters in the model frozen. Compared to a full training, PT is a lightweight process as it optimizes only one embedding and uses a training set that is several orders of magnitude smaller than the entire . For any entity Kelpie can post-train two types of mimics: ∙ A homologous mimic ′ has its embedding initialized randomly, and then post-trained on an exact replica of . As a result, we expect ′ to behave similarly to the original entity . ∙ A non-homologous mimic −′ (or ′+ ) initialized randomly as well, and then post-trained sEKelpie -0.490 -0.321 -0.920 -0.857 -0.540 -0.356 -0.920 -0.904 -0.740 -0.580 +0.319+0.516+0.259+0.434+0.128+0.218+0.117+0.169+0.048 +0.109 n raT DP -0.380 -0.258 -0.900 -0.859 -0.460 -0.303 -0.770 -0.701 -0.670 -0.533 +0.273 +0.461 +0.183 +0.350 +0.051 +0.080 +0.082 +0.116 +0.036 +0.117
on a set of facts that replicates with the removal (or addition) of a set of facts. After the post-training is over, the mimic is expected to approximate the behaviour that the original entity would have displayed if the injected variation had been present since the beginning. Examples of homologous and non-homologous mimics are in Figure 1 (center and right respectively). When explaining any tail prediction ⟨ℎ, , ⟩, we can thus estimate the efect of adding (or removing) from ℎ the facts of any candidate explanation by comparing the outcomes obtained using a homologous mimic ℎ′ and a non-homologous mimic mimic ℎ′+ (or ℎ′+ ).
In this section we briefly report the main experimental results of Kelpie. For a deeper report on
the experimental evaluation of the system, see [
Setup. Our experiments have been run on a server with 88 CPUs Intel Core(TM) i7-3820,
516GB RAM and 4 16GB NVIDIA Tesla P100 GPUs. We consider the 5 best-established dataset
in LP literature: FB15k and FB15k-237, sampled from Freebase; WN18 and WN18RR, sampled
from WordNet; and YAGO3-10, sampled from YAGO3. We consider 3 models representative
for the 3 diferent families of the taxonomy in [
Necessary Explanations Sufficient Explanations
FB15k WN18 FB15k-237 WN18RR YAGO3-10 FB15k WN18 FB15k-237 WN18RR YAGO3-10 AVG STD AVG STD AVG STD AVG STD AVG STD AVG STD AVG STD AVG STD AVG STD AVG STD goal of converting a diferent set of 10 random entities. Then, for each prediction ⟨ℎ, , ⟩ we add the explanation facts to all entities in the corresponding set, we re-train the model, and we measure how the addition of the explanation facts has improved the tail rank of in each ⟨, , ⟩ prediction. We measure such improvements in terms of ∆ @1 and ∆ : more positive values correspond to higher efectiveness.
We use as baselines two data poisoning systems, namely Criage [
Since Criage and DP are limited to explanations with only 1 fact, we have also experimented
with a single-fact version of Kelpie; we have obtained results comparable to the best baselines
but almost always worse than "full" Kelpie. This demonstrates the efectiveness of post-training
at identifying the most relevant facts, as well as the utility of supporting fact combinations.
Explanations Lengths. We report in Table 2, for each scenario, model and dataset, the average
(AVG) and the standard deviation (STD) of the lengths of our explanations. We observe that
necessary explanations tend to always be longer than suficient ones, for the same datasets and
models. Necessary explanations should encompass all the facts supporting a prediction, so that
removing them disables the prediction. Suficient explanations, on the other hand, just need
to to extend the same prediction to other entities: so, it is usually enough for them to include
just a few facts (or even just one) as pieces of evidence for the prediction. We also observe that,
in many cases, the average explanation lengths are lesser than 2, suggesting that Kelpie can
identify minimal explanations, as expected (extensive experiments on minimality are in [
Guided by our explanations, we have found that, in YAGO3-10, people playing for a football team are born in same city unnaturally often (thus providing data bias) and that personal data are significantly scarce, making birthplace prediction very challenging: the correct predictions, in this regard, seem to be afected even by the slight preference that football players may have towards teams from their birthplace. This type of observations can allow researchers to intervene on LP datasets to make them better adhere to the semantics of the real world.
So far few works have addressed directly the interpretability of embedding-based LP models.
The works most related to ours are Criage [
One of the aspects that make the interpretability of LP models so challenging is the large
variety of ML architectures. In time, researchers have tried to bypass this problem in a variety
of ways. Some authors have chosen to support specific architectures [
We have discussed Kelpie, a full-fledged explainability framework for embedding-based LP models. Kelpie explanations highlight the most relevant training samples that have enabled our predictions; they are based on the fundamental notions of necessity and suficiency, and they can encompass combinations of multiple training samples. In the sparkling topic of LP on Knowledge Graphs, interpretability is a strikingly desirable property; yet, it is hardly ever guaranteed by current state-of-the-art systems and frameworks. The efectiveness of Kelpie explanations, measured through extensive experiments, shows that Kelpie largely surpasses pre-existing methods across almost all scenarios in literature; furthermore, as demonstrated, Kelpie explanations can be precious in identifying unbalances and biases in LP datasets.
The work by Donatella Firmani has been supported in part by SEED PNR FLOWER grant 2021.