Injecting Semantics for Explaining Link Predictions

Chapter 1
Introduction
1.1 Context
As the flood of data continues to grow, Knowledge Graphs (KGs) have emerged as a
critical tool to organize, interpret, and navigate this deluge of information. A KG is a
multi-relational graph composed of entities and relations, which are represented as nodes
and different types of edges, respectively. In a KG, the knowledge is stored in the form of
triples, where each triple consists of an entity (the subject), a relation (the predicate), and
another entity (the object). This formal representation provides a method to encapsulate
complex knowledge domains into an understandable and accessible form both to humans
and machines. To harness even greater potential from these structures, KGs can be
enriched with formal ontologies that also provide advanced inference capabilities.
Examples of KGs in the enterprise domain include the Google Knowledge Graph [125],
which enhances its search engine’s results with information boxes; the LinkedIn Knowl-
edge Graph [106], which uses representations of members, jobs, titles, skills, companies,
geographical locations, and schools to power recommendation features; the Uber’s KG
[49], focused on “Uber Eats” delivery service; Amazon’s Product Graph [32], a key com-
ponent of their product recommendation system; Microsoft’s Academic Knowledge Graph
[37], used for academic research and literature exploration; and IKEA’s Knowledge Graph
[65], which improves their e-commerce system by structuring product data and enabling
smarter recommendations. In the open-source world there exists several web-scale KGs.
Examples include DBpedia [4], which is a crowd-sourced effort to extract structured in-
formation from Wikipedia; Wikidata, which is a free and open knowledge base editable
by both humans and machines, YAGO [54], an ontology project that structures data from
a variety of sources, including Wikipedia; Freebase [13], a large-scale collaborative effort
that has been incorporated into Google’s Knowledge Graph; OpenCyc, which contributes
to the Cyc project by aiming to compile a comprehensive ontology and knowledge base of
common sense knowledge; and BabelNet [91], which presents a vast, multilingual semantic
1
network and ontology.
Despite their effectiveness in structuring information, KGs often suffer from incom-
pleteness [143] due to inherent difficulties in data collection and the dynamic nature of
the real-world phenomena they reflect, and most importantly, due to the complex and
often automated construction process of KGs. This underlines the importance of Link
Prediction (LP) and triple classification tasks, which aim is to infer missing relationships
and classify new triples as true or not, respectively.
Many LP models are grounded on complex Machine Learning (ML) methods with
Knowledge Graph Embeddings (KGEs) being a prevalent approach (see [140] for a recent
survey). The trend of using embeddings in KGs originated from the groundbreaking study
by Bordes et al. [14], who demonstrated an impressive scalability that was previously un-
achievable. KGEs map the entities and relationships from the KGs into a low-dimensional
vector space. While the nature of this space is often continuous, it can also be complex
or in other forms. The intuition behind KGEs is that the geometric properties of the
embeddings would reflect the relationships among entities and relations. These systems
have already found successful applications across a wide range of downstream tasks, such
as information retrieval [144] and sentiment analysis [151].
ML models, like KGEs, demonstrated their effectiveness. However, they often operate
as “black boxes”. Their internal workings remain obscure. This limits users’ under-
standing and trust in the predictions that are made. This opacity can be particularly
problematic in contexts where understanding the basis of predictions is crucial, such as
healthcare or financial decision-making, where decisions based on these predictions can
have significant consequences. For instance, in the healthcare sector, LP tasks might in-
volve predicting potential connections between specific drugs and side effects [22]. In such
cases, not only the predictions themselves but also their underlying rationale is essential.
Healthcare professionals need to understand the reasoning to make informed decisions
about patient treatment and safety, and not merely rely on the predictive outcome. As
an additional example, Pezekshpour et al. [103] have recently brought attention to the
fact that explainability frameworks for LP can assist in identifying biases and potential
errors within the original KGs.
To address this opacity, the field of Explainable Artificial Intelligence (XAI) [88] has
come into the spotlight. XAI aims to make the decisions of AI and ML models more
transparent and understandable, enhancing human trust and comprehension across all AI
applications.
Some existing solutions aim at providing explanations for predicted links. Given a
predicted triple⟨s,p,o⟩, the generated explanations generally consist of subsets of rel-
evant triples, i.e. training triples that have enabled the model to predict o as object.
However, these methods often generate a large number of candidate explanations. This
large volume of candidates can represent computational challenges for the algorithm, due
2
to the necessity of performing complex evaluation for each candidate explanation. Fur-
thermore, existing methods may have room for improvement in terms of the end to end
effectiveness of the explanations. This can be measured in various ways, such as through
the evaluation metrics discussed in detail in Chapter 5. Lastly, these methods may offer
limited adaptability regarding explanation granularity, i.e., the level of detail provided in
the explanations. Some users might prefer a brief, high-level explanation, while others
might require a more detailed account.
Recognizing these limitations, this thesis proposes to enhance existing explanation-
generation strategies by incorporating semantics into the search process. With this en-
hancement, we expect to increase the system’s efficiency and to extract more effective
explanations by focusing directly on the most relevant candidate solutions. In the follow-
ing sections, we will outline the scope of this study and the specific research goals.
1.2 Research Scope
In this thesis, we focus on the problem of explaining LP generated by KGE models. We
consider KGEs due to their ability to scale on very large KGs.
The scope of our research is primarily centered around KGs that are sufficiently anno-
tated, particularly with regard to the entity class information, as for the case of DBPedia
1
.
The reason behind this is that our proposed approach relies heavily on semantics injection
to guide the process for generating explanations. Specifically, the semantic information,
such as entity classes, assists us in grouping triples.
It should be noted that this thesis does not intend to explore every possible way of
generating explanations for KGs or every possible type of LP model because the proposed
approach is suitable for explaining link prediction systems based on KGE. Furthermore,
we are primarily interested in developing strategies that address the following challenges:
reducing the number of candidate explanations, enhancing explanation significance, and
providing various levels of explanation granularity. (Details on the challenges are provided
in Section 1.3).
1.3 Research Goals
In real-world applications, KGs often scale to massive proportions. For instance, as of
March 2023, Google’s Knowledge Graph boasted over 800 billion triples on 8 billion enti-
ties [129]. This scale underscores the importance of enhancing the scalability of existing
explanation methods. Ensuring scalability should not entail sacrificing the correctness
of the explanations. We identified three specific research goals to address the gaps of
1
https://www.dbpedia.org/
3
the existing solutions, such as [113, 104]. Firstly, we seek to the decrease the number
of candidate explanations. Moreover, we wish to optimize the end to end effectiveness
of the explanations, and lastly we aim at generating explanations at different levels of
granularity. In the rest of the section we delve into the details of each goal.
The first goal is to decrease the number of candidate explanations. In the following,
we report an assumption on a desired characteristic of an explanation and we explain
how it can be leveraged to support the first goal. In certain instances, a prediction might
include, as candidate explanations, subsets containing triples having the same shape. For
example, for the predicted triple<actor, actedIn, movie>, a candidate explanation might
consist in the set of the other movies featuring the same actor. All the triples in such
candidate would share the shape <actor, actedIn, movieX>, where movieX represents
different movies. This similarity would be particularly noticeable in datasets where, for
each entity, multiple instances of the same relation are recorded. In other words, for each
entity, there’s a small variety of unique relations, but each of these relations is associated
with a significant number of triples. Recognizing this, our strategy aims to guide the
search directly towards subsets of similar triples, thus avoiding an exhaustive traversal
through each individual element. The underlying assumption is that multiple pieces of
evidence, specifically subsets containing triples having the same shape provide more robust
and reliable explanations than a single triple with that same shape. However, we also
acknowledge that a subset is not always a better explanation than an individual triple,
as it may contain unrelated triples thus diminishing the overall relevance. Therefore, our
aim is to directly focus on highly relevant subsets to reduce the number of candidate
explanations without sacrificing the correctness of the explanation. This goal is related
to finding a clever grouping of candidate explanations.
Our second goal involves optimizing the explanation end to end effectiveness. An
ideal explanation could be a subset that can be further split into smaller subsets each
representing a different kind of evidence. Drawing from the previous actor example, we
suppose to have the predicted triple <actor, actedIn, science fiction movie>. An ideal
explanation for this prediction might consist of three subsets: one featuring the actor’s
involvement in cyberpunk movies (a sub-genre of science fiction), another presenting the
actor’s appearances in time-travel movies (another sub-genre of science fiction), and a
final subset revealing that the actor had worked with well-known science fiction directors.
This would provide multiple pieces of evidence within each subset, thus enhancing the
robustness of the explanation. Essentially, this is akin to clustering, where each subset,
or cluster, is internally homogeneous, but distinctly different from other clusters. We aim
to generate explanations that embody this structure, as they offer multi-faceted insights
with each facet being adequately supported. Hence, we believe this structure will provide
better performance.
Finally, the third goal is to generate explanations at different levels of granularity.
4
Current methods often connect specific entities. We aim to go beyond this level and offer
more abstracted explanations that encapsulate broader patterns or concepts. For exam-
ple, instead of illustrating the specific movies a given actor has acted in, an explanation
at a higher level of granularity would represent the generalized relationship, such as<Ac-
tor, actedIn, Movie>. This level of explanation signals the actor’s general involvement in
movies without specifying which particular movies. By accommodating this level of ab-
straction, the system can provide comprehensive and interpretable explanations suitable
for a variety of user needs.
All these three goals are intrinsically connected to finding an intelligent way of group-
ing candidate explanations. We believe that by finding effective grouping methods, we
can decrease the number of candidates, optimize the end to end effectiveness of the ex-
planations, and offer varying levels of granularity.
1.4 Thesis Outline
The subsequent chapters of this thesis are structured as follows. Chapter 2 lays the
foundation by introducing fundamental concepts essential for this thesis. It begins with
an exploration of KGs and their primary purpose, focusing specifically on LP as a task
of interest. Subsequently, the field of XAI is discussed, illustrating various approaches.
Specifically, a taxonomy of state-of-the-art techniques is presented. The chapter then
proceeds to delve into the concept of quotient graph, which forms the basis of our proposed
approach.
Chapter 3 comprehensively reviews existing approaches related to the explanation
of LP outcomes. Various methodologies and frameworks employed in these domains are
discussed, providing insights into the current research landscape. Furthermore, we provide
more detailed basics on one of the presented approaches, Kelpie.
Chapter 4 outlines our proposed approach, which involves injecting semantics into
the search strategy of Kelpie. We elucidate how we employ the quotient graph as an al-
ternative representation, substituting the original formulation for searching explanations.
Additionally, we propose different formulations of the quotient with varying the level of
granularity.
Following the theoretical exposition, Chapter 5 focuses on the experimental evaluation.
We introduce the DBpedia50k dataset [124], utilized as a benchmark for evaluating the
proposed approach. Furthermore, we establish Kelpie as the baseline for comparison,
and define the evaluation metrics employed, namely ∆ MRR and ∆ H@1, along with the
number of relevances computed to extract explanations (#relevances). We present the
results and analysis derived from our experiments. To quantitatively assess the various
quotient formulations and compare them to the baseline, we employ the aforementioned
evaluation metrics. Additionally, we qualitatively evaluate the outcomes, specifically with
5
respect to our third goal which centers on generating explanations at different levels of
granularity. This chapter provides a comprehensive understanding of the performance
and trade-offs associated with different levels of abstraction.
Finally, Chapter 6 concludes this dissertation by summarizing our achievements. We
discuss the limitations encountered during the research and present future research direc-
tions.
6