# LinkLogic: A New Method and Benchmark for Explainable Knowledge Graph
Predictions

Niraj Kumar-Singh<EMAIL_ADDRESS>
Inbound Health, Mountain View, CA USA Gustavo Polleti<EMAIL_ADDRESS>
University of São Paulo, Butanta, São Paulo, Brazil Saee Paliwal
<EMAIL_ADDRESS>
Nvidia, New York, NY USA Rachel Hodos-Nkhereanye<EMAIL_ADDRESS>
BenevolentAI, Brooklyn, NY USA

###### Abstract

While there are a plethora of methods for link prediction in knowledge graphs,
state-of-the-art approaches are often black box, obfuscating model reasoning
and thereby limiting the ability of users to make informed decisions about
model predictions. Recently, methods have emerged to generate prediction
explanations for Knowledge Graph Embedding models, a widely-used class of
methods for link prediction. The question then becomes, how well do these
explanation systems work? To date this has generally been addressed
anecdotally, or through time-consuming user research. In this work, we present
an in-depth exploration of a simple link prediction explanation method we call
LinkLogic, that surfaces and ranks explanatory information used for the
prediction. Importantly, we construct the first-ever link prediction
explanation benchmark, based on family structures present in the FB13 dataset.
We demonstrate the use of this benchmark as a rich evaluation sandbox, probing
LinkLogic quantitatively and qualitatively to assess the fidelity, selectivity
and relevance of the generated explanations. We hope our work paves the way
for more holistic and empirical assessment of knowledge graph prediction
explanation methods in the future.

##  1 Introduction

Link prediction in knowledge graphs (KG) is a fairly well-developed field with
many important applications, from knowledge base completion Nickel et al.
(2016) and product recommendation He et al. (2017) to biomedical hypothesis
generation Bonner et al. (2021) Paliwal et al. (2020). Knowledge Graph
Embedding (KGE) models, in which latent representations are learned for
entities and relations, are among the most widely-used methods for these link
prediction tasks. These embeddings are optimized to be able to reconstruct the
semantic relationships present in the original graph, while enabling the
prediction of new links. Despite their success, KGE models typically behave as
black boxes from the user perspective, hindering their application in domains
where high interpretability is needed.

To address these limitations, several “KGE Explainer” (KGE-X) methods have
recently been proposed to generate explanations for KGE model predictions.
However, the field lacks consensus on how to evaluate and benchmark such
methods Doshi-Velez and Kim (2017). Evaluation to date has typically relied on
subjective assessment, via either anecdotal examples Polleti and Cozman
(2019); Gusmão et al. (2018); Zhang et al. (2019) or time-consuming user
research Bianchi et al. (2020). The lack of benchmarks has been a limiting
factor in the field, preventing rapid iteration on methods development and
obscuring any notion of state-of-the-art.

In the present work, we start by introducing a simple KGE-X method called
LinkLogic that builds on the ideas from Polleti and Cozman (2019). We then
describe the construction of the first-ever prediction explanation benchmark,
based on familial relationships from the common-sense Freebase Bollacker et
al. (2008) (FB) knowledge graph. Through various experiments, we show how this
benchmark can be used as a rich evaluation sandbox for KGE-X methods,
revealing both quantitative and qualitative insights into the behavior and
performance of LinkLogic. We underscore that this work is not intended to
demonstrate that LinkLogic is the state-of-the-art in KGE-X methods. Rather,
we provide a deep-dive analysis of explanations generated by this method,
aiming to pave the way for more robust evaluation practices of KGE-X methods.

##  2 Related Work

Rule-based systems such as AMIE+ Galárraga et al. (2015) and DRUM Sadeghian et
al. (2019) represent an alternative class of approaches relative to KGE
methods which can mine or learn first-order logic rules to infer missing links
in KGs. They are attractive due to the interpretable nature of such rules and
their ability to perform inductive reasoning. However, rule-based prediction
can be brittle and lack the nuance allowed by richer models. Further,
extracted rules describe global as opposed to local reasoning patterns and
hence can only describe how predictions are generally made, and not why a
particular link was predicted. There are also a few interesting methods such
as pLogicNet Qu and Tang (2019) and RNNLogic Qu et al. (2020) which adopt a
hybrid approach blending the predictive accuracy of KGE methods with the
interpretability of rule-based systems. However, while these methods claim to
be interpretable, they still only learn global rules and do not provide a way
to evaluate the quality of the explanations.

Path-based methods are the other primary alternative to KGE methods, with
recent approaches such as MultiHop Lin et al. (2018) and DeepPath Xiong et al.
(2017) using reinforcement learning to train an agent to reason through paths
in the KG from query to target node. These methods overcome the limitation of
rule-based systems to enable local insight into the model’s reasoning for a
given prediction. However, they are trained to traverse observed links and
hence explanation quality will be highly dependent on the completeness of the
underlying KG. Further, they can be fairly challenging and time-consuming to
train.

In contrast to rule-based and path-based systems, KGE-X methods decouple the
link prediction model from the explainer model. At the cost of some potential
gap in fidelity between the prediction and the explanation, this decoupling
enables the two components to be more specialized which could allow for better
quality predictions as well as explanations designed to have more desirable
properties, e.g. to maximize user comprehension. XKE Gusmão et al. (2018) e.g.
consists of an interpretable global surrogate model, a path-based logistic
regression, that attempts to mimic the KGE behavior. Despite XKE’s ability to
produce meaningful explanations, they usually display low fidelity. As an
attempt to produce faithful explanations, Polleti and Cozman (2019) what we
will refer as KELIX (Knowledge Embedding with Local Interpretable
Explanations) employs a local surrogate, logistic regression, trained on
binary path-based features extracted from the KGE itself. Despite its
methodological advances, KELIX was only evaluated through anecdotal examples
and has room for improvement in many dimensions (e.g. feature selection and
representation, hyperparameter tuning, etc). LinkLogic directly builds on the
ideas presented in Polleti and Cozman (2019) aiming to address some of these
limitations. More specifically: (1) explanatory features are extended from
binary features to model-informed continuous scores; (2) single hop features
are replaced by a more general framework using higher-order paths; (3) the KGE
explanation problem is reframed as explaining variation in the KGE score for
perturbed queries, solved using regression as opposed to triple
classification; and (4) surrogate model coefficients are constrained to be
non-negative to improve interpretability.

##  3 Methods

###  3.1 Notation and conventions

A knowledge graph $\mathcal{G}$ consists of a set of entities
$e\in\mathcal{E}$, relations $r\in\mathcal{R}$ and ordered triples
$(h,r,t)\in\mathcal{T}$ where $h,t\in\mathcal{E}$ correspond to the head and
tail entities linked by some relation $r\in\mathcal{R}$. Let the KGE embedding
vectors for $h$ and $t$ be h and t, respectively, both in $\mathbb{R}^{d}$.
$\mathbf{I}\in\mathbb{R}^{d\times d}$ is the identity matrix. We will use $c$
and $p$ to refer to the child and parent in the query triple ($c$, parent,
$p$), and $s$ and $p_{2}$ for any sibling or co-parent of $c$, respectively.
Scalars, vectors and matrices are denoted by lowercase italic, lowercase bold,
and uppercase bold lettering, respectively. Statistics when not otherwise
specified are reported as mean $\pm$ one standard deviation.

###  3.2 Our method: LinkLogic

Given a set of trained embeddings from a KGE model and a query triple
$(h,r,t)$, the goal of LinkLogic is to produce a ranked and scored list of
paths that best “explain” the KGE score for the query triple. The method is
based on generating local perturbations to the embeddings $\mathbf{h}$ and
$\mathbf{t}$ and then training a simple surrogate model to explain the
variation in the resulting KGE prediction scores based on variation in scores
connecting these perturbed entities to nearby paths, as detailed below.

Creating perturbed queries: Given a query triple $q=(h,r,t)$, $n$
perturbations of the query are generated. A single perturbed query $q_{i}$ =
$(\hat{{h}_{i}},{r},\hat{{t}_{i}})$ is obtained by adding Gaussian noise to h
and t, as follows:

$\hat{\textbf{h}_{i}}=\textbf{h}+\alpha\mathcal{N}(0,\sigma^{2}_{h}\mathbf{I}),\quad\hat{\textbf{t}_{i}}=\textbf{t}+\alpha\mathcal{N}(0,\sigma^{2}_{t}\mathbf{I}),$
(1)

Here, $\alpha$ is a global hyperparameter that controls the magnitude of the
perturbation, while $\sigma_{h}$ and $\sigma_{t}$ are computed per query
triple, as described in Section B.1.

Identifying candidate paths: We define a path $P$ of length $l$ in
$\mathcal{G}$ to be an ordered sequence
$\\{e_{1},r_{1},e_{2},r_{2},\dots,r_{l},e_{l+1}\\}$ with $e_{i}\in\mathcal{E}$
and $r_{i}\in\mathcal{R}$. Note that the corresponding triples
$(e_{i},r_{i},e_{i+1})$ may or may not exist in $\mathcal{T}$. We define the
path score $S(P)$ as follows:

$S(P)=\frac{1}{l}\sum_{j=1}^{l}-\log(1-f({e}_{j},{r}_{j},{e}_{j+1}))$ (2)

where $f$ is the KGE decoder-dependent scoring function represented as a
plausibility score ranging between 0 and 1. Next, let $\mathcal{P}_{l}^{a}$ be
the set of all paths up to length $l$ that start or end with entity $a$, and
let $\mathcal{P}_{l}^{a,b}$ be the set of all paths up to length $l$ that
start and end with $a$ and $b$ (in either order). To generate the candidate
list of paths, we compute $S(P)$ for
$P\in\mathcal{P}_{l}^{h}\cup\mathcal{P}_{l}^{t}\cup\mathcal{P}_{l+1}^{h,t}$
and take the top $m$ paths with the highest scores. A subset of these paths
are selected for the final explanation as described next.

Training a local surrogate model: To compute the feature scores for a single
perturbed query $\hat{q}=(\hat{h},{r},\hat{t})$, first the $h$, $t$ in
{$\mathcal{P}_{l}^{{h}}\cup\mathcal{P}_{l}^{{t}}\cup\mathcal{P}_{l+1}^{{h},{t}}$}
are replaced with $\hat{h}$ and $\hat{t}$ respectively and then path scores
$S(P)$ are computed for the corresponding set of $m$ paths from
$\mathcal{P}_{l}^{\hat{h}}\cup\mathcal{P}_{l}^{\hat{t}}\cup\mathcal{P}_{l+1}^{\hat{h},\hat{t}}$
using Equation 2, resulting in a feature matrix
$\textbf{X}\in\mathbb{R}^{\text{n}\text{x}\text{m}}$. The path scores for the
perturbed query triple $\textbf{y}\in\mathbb{R}^{n}$ are used as the dependent
variable of the surrogate model. Here, we use a simple Lasso regression model
with a non-negative weight constraint, i.e.:

$\min_{\beta_{j}\geq
0}\Big{(}\sum_{i=1}^{n}\big{(}y_{i}-\sum_{j=1}^{m}x_{ij}\beta_{j}\big{)}^{2}+\lambda\sum_{j=1}^{m}|\beta_{j}|\Big{)}$
(3)

Generating explanations: Finally, paths with positive coefficients $\beta_{j}$
are taken to be the explanation, ranked in descending order by their
coefficient values. Pseudocode is provided in Appendix B.2.

###  3.3 Baseline: Path score heuristic

In order to assess whether LinkLogic learns a meaningful ranking of candidate
paths, we compared it to a simple baseline, which we will refer to as the path
score heuristic, that ranks paths based directly on the path scores $S(P)$
from Equation 2 in descending order, for $P$ in
$\mathcal{P}_{l}^{h}\cup\mathcal{P}_{l}^{t}\cup\mathcal{P}_{l+1}^{h,t}$. When
necessary, a subset of paths was extracted by applying a threshold to the
scores.

##  4 Experiment Setup

###  4.1 FB13 and “FB14” training data preparation

To create an evaluation sandbox to assess explanation quality, we chose
Freebase 13 (FB13) Socher et al. (2013) which has interpretable entities
linked by 13 relations (see Figure A.1.1 for details) including family
relations that can be reasoned upon as described in the next section 111The
dataset was accessed from the OpenKE gituhb repo:
https://github.com/thunlp/OpenKE/tree/master/benchmarks/FB13. FB13 contains
the following relation categories: Family=child, parent, spouse;
Location=location, place-of-birth, place-of-death, nationality; Other=cause-
of-death, ethnicity, gender, institution, profession, religion. Triples from
FB13 were randomly shuffled into training, validation and test splits with
proportions 80/10/10, respectively. Additional processing is described in
Section A.1.

Among the 13 relations in FB13, there are three familial relations: parent,
child and spouse. Sibling relationships, while implicit via entities having
shared parents, are not represented explicitly. To investigate the model’s
usage of sibling relations, we created an alternative data version by adding a
new sibling relationship for a total of 14 relations, which we will refer to
as FB14. Two entities $s_{i}$ and $s_{j}$ are defined as siblings if they each
have exactly two parents $p_{k}$ and $p_{l}$ linked to both $s_{i}$ and
$s_{j}$. For all such pairs, triples $(s_{i},sibling,s_{j})$ and
$(s_{j},sibling,s_{i})$ were added for a total of 4130 new triples. These were
randomly shuffled with the same 80/10/10 proportions and appended to the
training, validation and test sets.

###  4.2 Construction of the Parents Benchmark for prediction explanations

We constructed a benchmark from the Freebase data that consisted of paths that
correctly explain each parent-child link $(c,parent,p)$ according to
commonsense reasoning. To illustrate, we start by showing an example family
from Freebase revolving around the query triple (Maria Mozart, parent, Leopold
Mozart). The family (see Figure 1) has two parents, Anna and Leopold, along
with their child, Maria and Wolfgang. In reference to the query triple, we use
$c$ for Maria, $p$ for Leopold, $p_{2}$ for Anna, and $s$ for Wolfgang. To
explain why the query triple is true, we find natural “clues” in the two-hop
paths: {Maria, parent, Anna, spouse, Leopold} and {Maria, sibling, Wolfgang,
parent, Leopold}. Given that we define siblings based on the sharing of
precisely two parents, the latter path deterministically implies that the
query triple is true, while the former path can in general be true without the
query triple being true. Further, we posit that single hops along these paths
are also reasonable components of a good explanation.

Maria ($c$)Leopold ($p$)Wolfgang ($s$)Anna
($p_{2}$)parentsiblingchildchildparentparentspouse Figure 1: Directed sub-
graph representing the Mozart family. Black and red edges are included in
FB13. The purple sibling edge highlighted was included in FB14. The link in
red shows the query triple, (Maria, parent, Leopold).

We abstracted this reasoning to construct the Parents Benchmark as shown in
Table 1. For each path category, we assigned confidence scores of either 1 or
0.5 indicating whether or not the path deterministically implies the query
triple. Additional details are described in Section A.2. The benchmark
includes at least one path for 6,260 query triples, with the distribution
shown in Figure A.2.1.

Path Category | Confidence | Dataset relevance
---|---|---
{$p$, child, $c$}1 | 1 | FB13, FB14
{$c$, sibling, $s$, parent, $p$} | 1 | FB14 only
{$p$, child, $s$} | 1 | FB13, FB14
{$c$, sibling, $s$} | 1 | FB14 only
{$c$, parent, $p_{2}$, spouse, $p$} | 0.5 | FB13, FB14
{$c$, parent, $p_{2}$} | 0.5 | FB13, FB14
{$p$, spouse, $p_{2}$} | 0.5 | FB13, FB14
Table 1: The path types included in the Parents benchmark for the query triple
$(c,\textrm{parent},p)$ where $s$ denotes any sibling of child $c$, and
$p_{2}$ corresponds to any co-parent of $c$, i.e. $(c,\textrm{parent},p_{2})$
where $p_{2}\neq p$. 1Note this is a direct (inverse) representation of the
query triple and was only used in Section 5.3.1.

###  4.3 KGE model training

The embeddings for FB13 and FB14 were trained using the ComplEx decoder
Trouillon et al. (2016) with the Deep Graph Library-Knowledge graph Embeddings
(DGL-KE) library Zheng et al. (2020). We focused on ComplEx due to its ability
to learn asymmetric relationships and favorable performance on familial
relationships (Supplementary Figure A.3.1). Hyperparameters are listed in
Section A.3, Supplementary Table A.3.1.

###  4.4 Evaluation metrics for prediction explanations

We evaluated performance based on three key desirable characteristics Duval
and Malliaros (2021) of prediction explanations: (1) The fidelity of a
LinkLogic explanation to the KGE model was assessed using the $R^{2}$ value on
a held-out set of target values for the regression from Equation 3. (2) The
selectivity was assessed based on the number of paths in an explanation. (3)
The relevance was assessed using the normalized discounted cumulative gain
Järvelin and Kekäläinen (2002) among the top k paths (NDCG@k) based on the
coefficients relative to the Parents Benchmark confidence scores in Table 1.

##  5 Results

We start with a series of quantitative studies followed by qualitative
explorations of family tree configurations and their effects on explanation
behavior.

All LinkLogic explanations were generated using the following hyperparameters:
$\alpha=1,\lambda=0.2,n=1000$ and $m=20$ features per relation type and $l=1$,
to extract one-hop and two-hop explanatory paths. With these settings, on a
128 GB CPU, it took less than 10 seconds per query triple to generate
LinkLogic prediction explanations. Randomly sampled explanations for all 13
relation types in the FB13 dataset are included in Section B.3.

###  5.1 Analysis of explanations for true and false facts across FB13

First, we sought to understand how the fidelity and complexity of the
explanations varied throughout FB13, and whether these properties would be
different when generated for true vs. false facts. We sampled 100 triples for
each of the 13 relation types, for three categories of query triples: True
facts present in FB13, False, i.e. true facts with the tail re-sampled to
another entity of the same type, and Nonsense triples, which are true triples
from FB13 with the tail re-sampled disregarding entity type, e.g. (Paul,
spouse, New York). Figure 2A shows that the KGE scores for True facts were
significantly higher than those for False and Nonsense triples (mean of 0.77,
0.03, 0.02, respectively) indicating that the KGE model was trained reasonably
well and hence would likely provide a reasonable substrate from which to
generate explanations. For each triple, we generated explanations from both
LinkLogic and the baseline path score heuristic, thresholding the latter to
either 0.90 or 0.95 KGE plausibility scores.

Figure 2: Quantitative analysis of LinkLogic explanation relevance,
selectivity, and fidelity. A KGE prediction scores, B number of paths per
explanation, and C LinkLogic fidelity, for 1300 explanations generated for
Nonsense, False, and True query triples across the 3 relation categories in
FB13. D Relevance assessment across the full Parents benchmark, E Number of
paths per explanation as a function of the number of siblings, and F LinkLogic
fidelity versus the number of siblings present in the family. For the path
score heuristic, 0.90 and 0.95 correspond to the KGE score threshold at which
paths were selected.

Figure 2B shows that while the heuristic path scoring method produced more
than one path on average regardless of the triple’s truthiness, LinkLogic
tended to only produce explanations for True triples (mean of 1.9, 0.2, and
0.2 paths for True, False and Nonsense, respectively). Among the LinkLogic
explanations, we also quantified the fidelity of each explanation to the KGE
scores (see 4.4 for details and Figure B.3.1 for an example). Overall, we
observed a trend consistent with Figure 2B, where fidelity was significantly
higher for True facts compared with those in the False and Nonsense categories
(mean 0.29, 0.01, and 0.02 respectively, $t_{1299}>$35, $p<0.0001$). Figure 2C
shows the fidelity for the three truth categories, broken into the three
categories of relations in FB13: Family, Location and Other. Notably, for True
triples, we observed the highest fidelity for the Family category, versus the
Location and Other category. We hypothesized that this is due to the higher-
confidence nature of certain familial relationships. On the other hand, the
Location relationships can share information amongst themselves, but this
relation tends to be noisy and error-prone. Finally, the remaining relations
are relatively independent from one another and hence would often lack paths
in the graph from which to explain their existence. Nonetheless, we observe
nontrivial explanations across most relation types (see Supplementary Tables
B.4.1 to B.4.12).

###  5.2 Analysis of explanations across the Parents Benchmark

To assess the relevance of selected paths, we computed NDCG@k on explanation
coefficients (see Section 4.4 for rationale), varying k from 1-7, for all
triples in the Parents Benchmark. As shown in Figure 2D, LinkLogic explanation
relevance outperforms that of the path score heuristic by roughly 40% at
$k=1$. This difference is particularly prominent at small k, with the margin
decreasing as k increases.

Recognizing that the number of explanations in the benchmark depends on the
number of siblings that links c to p in the query (c, parent, p), we
investigated the properties of explanations as a function of the number of
siblings. We found that the number of explanatory paths selected by LinkLogic
remained relatively constant, whereas the path score heuristic, as expected,
identified more paths as the number of siblings increased (Figure 2E),
resulting in highly redundant explanations. We also observed a striking
pattern in fidelity (Figure 2F): explanation fidelity substantially increased
between families with zero and one siblings but plateaued with additional
siblings. These results indicate that LinkLogic was selective in identifying
paths that sufficiently explain the query triple in the presence of redundant
evidence through additional siblings.

###  5.3 Qualitative evaluation through family tree experimentation

Next we describe a series of experiments with family tree configurations in
order to derive further qualitative insights into the properties of LinkLogic.
These experiments have in common the shared task of explaining the query
triple ($c$, parent, $p$), while differing in either the set of paths
available at explanation time, or further, in the set of relations available
at training time. Note that in order to properly compare the statistics of
selected paths across query triples, we restricted the analysis in this
section to 895 query triples corresponding to families in FB13 where the child
entity $c$ has a single sibling.

Experiment | Coefficient | LinkLogic Explanation
---|---|---
FB13, Child=True | 0.983 |  leopold_mozart $\xrightarrow{\text{child}}$ maria_mozart
0.534 |  maria_mozart $\xrightarrow{\text{parent}}$ anna_mozart
FB13, Child=False | 0.550 |  maria_mozart $\xrightarrow{\text{parent}}$ anna_mozart $\xrightarrow{\text{spouse}}$ leopold_mozart
0.329 |  leopold_mozart $\xrightarrow{\text{child}}$ wolfgang_mozart
0.312 |  maria_mozart $\xrightarrow{\text{parent}}$ anna_mozart
0.300 |  leopold_mozart $\xrightarrow{\text{spouse}}$ anna_mozart $\xrightarrow{\text{child}}$ maria_mozart
0.061 |  leopold_mozart $\xrightarrow{\text{ethnicity}}$ bavarians
FB14, Child=False | 0.451 |  leopold_mozart $\xrightarrow{\text{child}}$ wolfgang_mozart
0.423 |  maria_mozart $\xrightarrow{\text{sibling}}$ wolfgang_mozart $\xrightarrow{\text{parent}}$ leopold_mozart
0.352 |  maria_mozart $\xrightarrow{\text{parent}}$ anna_mozart $\xrightarrow{\text{spouse}}$ leopold_mozart
0.172 |  maria_mozart $\xrightarrow{\text{parent}}$ anna_mozart
0.062 |  leopold_mozart $\xrightarrow{\text{location}}$ augsburg
Table 2: LinkLogic explanations generated for the query (Maria Mozart, parent,
Leopold Mozart). Child=True means that the query-inverse triple is available
as a prediction explanation. Child=False indicates that this query-inverse has
been removed. FB14 Child=False contains the sibling relation and does not have
the query-inverse triple.

####  5.3.1 Tautologies: “I am your mother because you are my child”

We provided LinkLogic with the “query-inverse” one-hop path {p, child, c} as
one of the available explanation features. This path, while using a different
relation embedding than the query triple, is nonetheless deterministic by
being an exact inverse that is guaranteed to be true. Therefore, as a sanity
check, we would expect a reasonable prediction explanation system to identify
this feature as highly important in the explanation. Indeed, we observed that
the query-inverse triple was almost always the top-ranked path (95% of the
time), with a substantially higher coefficient than any other feature (mean of
0.93 compared with the $2^{nd}$-ranked feature with mean of 0.38,
$t_{(5157)}$=150, p$<$0.001). Prediction explanations also frequently included
a $2^{nd}$ path, {$c$, parent, $p_{2}$} through the co-parent $p_{2}$ (Figure
3A). The explanation for the Mozart query exemplifies these results; see first
row of Table 2.

####  5.3.2 Removing the direct link: “You are your father’s daughter”

We removed the query-inverse child path from the set of features available to
the model at explanation time to explore LinkLogic behavior in the absence of
this tautology. We continued to allow the model to use other paths involving
child relations. We observed that the top-ranked path for the Mozart example
(second row of Table 2) is now a two-hop path through the co-parent, Anna,
followed by a one-hop path linking the parent Leopold to his son, Wolfgang.
Systematic analysis across the 895 query triples reveals that the explanation
statistics changed rather substantially relative to the previous
configuration, as shown in Figure 3A. The two most frequent paths align with
the top-ranked paths from the Mozart example. Overall we observe a greater
variety of explanation paths, most of which are indeed relevant in explaining
the query triple.

Figure 3: Most frequently occurring paths in LinkLogic prediction explanations
for parent relationships, based on various configurations: A before and after
removing the direct child link, and B before and after adding the sibling
relation to training. $p$=parent, $c$=child, $s$=sibling, $p_{2}$=co-parent,
$x$=any entity that is not $p,c,s,$or $p_{2}$.

####  5.3.3 Providing a new vocabulary for siblings: “Meet your new brother”

While we observed a newfound reliance in the explanations on these links from
the parent p to the sibling s ({p, child, s} path in Figure 3A) , the
configurations described thus far do not include any (correct) two-hop paths
linking c and p through s due to the lack of an explicit sibling
representation in FB13. Hence, in our next experiment, we asked whether the
KGE model identified any relation between true siblings, forcing the creation
of an artificial two-hop path linking c and p through s. Re-training the model
on FB14, i.e. with explicit sibling triples, resulted in sibling-related paths
being prioritized in explanations (purple bars, Figure 3B). Specifically, we
saw the reliance of LinkLogic on the correct 2-hop path through the sibling to
the parent, {$c$, sibling, $s$, parent, $p$}, as expected. Of note, once the
two-hop path through s was available to the model, this deterministic path was
used even more frequently than the noisier two-hop through $p_{2}$. These
behaviors are reflected in the final row of Table 2 where the two top-ranked
paths involve the sibling, Wolfgang, with a lower coefficient for the two-hop
path through the co-parent, Anna.

Figure 4: A Scatter plot of real and imaginary parts of the FB13 spouse
relation embedding against FB13 children relation embedding , B Scatter plot
of only the real parts of the FB14 spouse (green) and sibling (yellow)
relation embedding against the FB14 children relation. C Scatter plots of real
and imaginary parts of the FB14 sibling embeddings versus the FB14 spouse
embeddings. D The change in coefficient of those spouse links (FB13) that were
correctly identified as siblings (FB14).

Interestingly, LinkLogic trained on FB13 (without sibling), artificially
generated pseudo-sibling relations using the existing relation spouse, which
were then used in prediction explanations for 10 query triples. Our hypothesis
was that the model generated a stand-in vocabulary to describe the
relationship between c and sibling s, using another symmetric relation
(spouse). For example, in the explanation for the query triple (Anne Frank,
parent, Edith Frank Hollander) as shown in Supplementary Figure B.5.1, the
model used explanation (Anne Frank, spouse, Margot Frank), creating a pseudo-
sibling relationship between these true sibling entities. When trained on FB14
(which includes the sibling relation), the model correctly assigned 6 of these
10 pseudo-siblings to the sibling relationship.

In the relation embeddings themselves, qualitatively, we see higher covariance
between the spouse–sibling relationship versus the spouse–child relationship
between Figure 4A and B, and a separation of information between the sibling-
child relationship and spouse-child relationship (yellow and green markers in
Figure 4B). The dispersion of the imaginary part of the child embeddings
compared to the spouse embedding in 4A shows that the imaginary part of the
complex embeddings successfully differentiates between those relationships
that are symmetric (e.g. spouse) versus asymmetric relationships (e.g. child).
For the sibling–spouse relationship shown in Figure 4C, we see a zeroing of
the spouse and sibling ComplEx embedding component, as both relations are
symmetric. Finally, in Figure 4D, we see a significant difference in
coefficient between the FB13 pseudo-sibling edges and the correctly-assigned
FB14 sibling edges (U=1.0, p=0.004).

##  6 Discussion

In this work, we introduced a method for explaining KGE link predictions that
builds on an existing method KELIX, while providing various practical
modifications. Using family structures in FB13, we also developed a novel
evaluation framework and benchmark for rigorously testing KGE-X methods.
Applying this framework, we were able to quantify explanation relevance and
show substantial improvements over a heuristic baseline. We observed
consistently high fidelity in explaining true facts while observing a
“reluctance” of the model to produce explanations for false facts. We also
demonstrated the selectivity of LinkLogic explanations even when presented
with an over-abundance of options from which to choose, exemplified by
families with many siblings.

Through experimenting with family tree configurations, we observed a number of
interesting model behaviors. First, in analyzing explanations before and after
removing the $\\{p,child,c\\}$ path from the feature set, we saw the
explanation characteristics shift toward higher-order and more varied paths.
The observed behavior suggests a level of flexibility which may be beneficial
for adapting this method to user-facing products. We also explored the usage
of sibling entities and relationships. The high prevalence of paths to sibling
entities even without the sibling relationship (in FB13 dataset) suggests that
a level of inference is possible in the LinkLogic explanations. The generation
of pseudo-siblings that were then correctly identified as siblings (as
demonstrated using the FB14 dataset) further illustrates the flexibility of
the model to use inferred information for prediction explanation.

We note a couple key limitations of this study. First, we focused on a
relatively narrow experimental space, studying performance with one decoder
trained on one dataset, focusing on one explanation task, and comparing to one
baseline. To reiterate, this was an intentional deep-dive as a means to help
us understand and reason about model behavior while establishing a novel
evaluation framework. In future work we plan to scale this analysis across
these additional dimensions in order to further contextualize LinkLogic
relative to other methods and evaluate performance on more difficult tasks.
Second, our analysis is based on a random split of the triples in the training
data, however the familial relationships are each represented by two distinct
directed edges, e.g. $(p,spouse,p_{2})$ and $(p_{2},spouse,p)$. Hence, most
familial links will have been represented in at least one direction in the
training data, meaning that this study has focused primarily on observed
links. While this can be useful for model introspection, we plan to study the
usage of inferred links more carefully by creating robust data splits in
future.

We foresee many interesting extensions to LinkLogic. First, while here we only
focus on explaining why a link is true, it is also possible to set up the
model to explain why a link is not true by simply changing the labels in the
regression problem from $-log(1-f)$ to $-log(f)$ for small plausibility
scores, e.g. $f<0.5$. Similarly, one could extend LinkLogic to leverage such
negative examples in prediction explanations by constructing features of the
form $-log(f)$ instead of $-log(1-f)$. This would enable explanations akin to
statements like “I believe the ground will be dry because I know that it is
not raining.” Finally, LinkLogic is currently restricted to using a limited
set of decoders that ensure local smoothness under perturbation. However, this
is easily addressed by replacing the linear regression model with a nonlinear
alternative, e.g. based on decision trees.

With the recent emergence of highly performant and flexible large language
models, it would be interesting to evaluate such models’ abilities to generate
meaningful explanations from KGE-based link predictions. This may be possible,
e.g. using a retrieval-augmented generation approach. However, such approaches
would have no notion of fidelity to the KGE model, and hence would not be
useful for introspecting the base model. LinkLogic, on the other hand, is
designed to have fidelity to the underlying KGE model and hence can be used
not just to generate meaningful explanations, but also to gain insight into
the performance and characteristics of the underlying model.

As machine learning systems are increasingly being applied to support high-
stakes decision making, methods for explaining black box models are crucial.
We hope that our work proves to be an important step toward prying open the
black box and enabling more rigorous evaluation of an emerging class of such
methods.

## References

  * Bianchi et al. (2020) Federico Bianchi, Gaetano Rossiello, Luca Costabello, Matteo Palmonari, and Pasquale Minervini.  Knowledge graph embeddings and explainable AI.  _CoRR_ , abs/2004.14843, 2020.  URL https://arxiv.org/abs/2004.14843.
  * Bollacker et al. (2008) Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor.  Freebase: A Collaboratively Created Graph Database For Structuring Human Knowledge.  Technical report, Metaweb Technologies, 2008.
  * Bonner et al. (2021) Stephen Bonner, Ian P Barrett, Cheng Ye, Rowan Swiers, Ola Engkvist, Andreas Bender, Charles Tapley Hoyt, and William Hamilton.  A review of biomedical datasets relating to drug discovery: A knowledge graph perspective.  _arXiv preprint arXiv:2102.10062_ , 2021.
  * Doshi-Velez and Kim (2017) Finale Doshi-Velez and Been Kim.  Towards a rigorous science of interpretable machine learning, 2017.  URL http://arxiv.org/abs/1702.08608.  cite arxiv:1702.08608.
  * Duval and Malliaros (2021) Alexandre Duval and Fragkiskos D Malliaros.  Graphsvx: Shapley value explanations for graph neural networks.  _arXiv preprint arXiv:2104.10482_ , 2021.
  * Galárraga et al. (2015) Luis Galárraga, Christina Teflioudi, Katja Hose, and Fabian M Suchanek.  Fast rule mining in ontological knowledge bases with amie+.  _The VLDB Journal_ , 24(6):707–730, 2015.
  * Gusmão et al. (2018) Arthur C. Gusmão, Alvaro C. Correia, Glauber De Bona, and Fabio G. Cozman.  Interpreting Embedding Models of Knowledge Bases : A Pedagogical Approach.  In _2018 ICML Workshop on Human Interpretability in Machine Learning (WHI 2018)_ , pages 79–86, 2018.
  * He et al. (2017) Ruining He, Wang-Cheng Kang, and Julian McAuley.  Translation-based recommendation.  In _Proceedings of the Eleventh ACM Conference on Recommender Systems_ , RecSys ’17, pages 161–169, New York, NY, USA, 2017. ACM.  ISBN 978-1-4503-4652-8.  doi: 10.1145/3109859.3109882.  URL http://doi.acm.org/10.1145/3109859.3109882.
  * Järvelin and Kekäläinen (2002) Kalervo Järvelin and Jaana Kekäläinen.  Cumulated gain-based evaluation of ir techniques.  _ACM Transactions on Information Systems (TOIS)_ , 20(4):422–446, 2002.
  * Lin et al. (2018) Xi Victoria Lin, Richard Socher, and Caiming Xiong.  Multi-hop knowledge graph reasoning with reward shaping.  _arXiv preprint arXiv:1808.10568_ , 2018.
  * Nickel et al. (2016) M. Nickel, K. Murphy, V. Tresp, and E. Gabrilovich.  A review of relational machine learning for knowledge graphs.  _Proceedings of the IEEE_ , 104(1):11–33, Jan 2016.  ISSN 0018-9219.  doi: 10.1109/JPROC.2015.2483592.
  * Paliwal et al. (2020) S. Paliwal, A. de Giorgio, D. Neil, J. B. Michel, and A. M. Lacoste.  Preclinical validation of therapeutic targets predicted by tensor factorization on heterogeneous graphs.  _Sci Rep_ , 10(1):18250, 10 2020.
  * Polleti and Cozman (2019) G. P. Polleti and F. G. Cozman.  Faithfully explaining predictions of knowledge embeddings.  _2019 Encontro Nacional de Inteligência Artificial e Computacional_ , 2019.
  * Qu and Tang (2019) Meng Qu and Jian Tang.  Probabilistic logic neural networks for reasoning.  _arXiv preprint arXiv:1906.08495_ , 2019.
  * Qu et al. (2020) Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang.  Rnnlogic: Learning logic rules for reasoning on knowledge graphs.  _arXiv preprint arXiv:2010.04029_ , 2020.
  * Sadeghian et al. (2019) Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang.  Drum: End-to-end differentiable rule mining on knowledge graphs.  _arXiv preprint arXiv:1911.00055_ , 2019.
  * Socher et al. (2013) Richard Socher, Danqi Chen, Christopher D Manning, and Andrew Ng.  Reasoning with neural tensor networks for knowledge base completion.  In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 26. Curran Associates, Inc., 2013.  URL https://proceedings.neurips.cc/paper/2013/file/b337e84de8752b27eda3a12363109e80-Paper.pdf.
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard.  Complex embeddings for simple link prediction.  _CoRR_ , abs/1606.06357, 2016.  URL http://arxiv.org/abs/1606.06357.
  * Xiong et al. (2017) Wenhan Xiong, Thien Hoang, and William Yang Wang.  Deeppath: A reinforcement learning method for knowledge graph reasoning.  _arXiv preprint arXiv:1707.06690_ , 2017.
  * Zhang et al. (2019) Wen Zhang, Bibek Paudel, Wei Zhang, Abraham Bernstein, and Huajun Chen.  Interaction embeddings for prediction and explanation in knowledge graphs.  In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_ , WSDM ’19, pages 96–104, New York, NY, USA, 2019\. ACM.  ISBN 978-1-4503-5940-5.  doi: 10.1145/3289600.3291014.  URL http://doi.acm.org/10.1145/3289600.3291014.
  * Zheng et al. (2020) Da Zheng, Xiang Song, Chao Ma, Zeyuan Tan, Zihao Ye, Jin Dong, Hao Xiong, Zheng Zhang, and George Karypis.  Dgl-ke: Training knowledge graph embeddings at scale.  In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’20, page 739–748, New York, NY, USA, 2020. Association for Computing Machinery.

## Appendix

##  A Methods and experimental setup

###  A.1 FB13 data processing details

As described in the main text, edges were split randomly into training,
validation, and test sets. The largest connected component was then identified
in the training set, and the small fraction of edges not connected to this
component were filtered out. Edges from the validation and test sets linked to
entities that were no longer represented in the filtered training set were
accordingly removed. This resulted in a final count of 276,690, 34,287 and
34,292 edges in the training, validation and test sets, respectively.

Entity types are not explicitly represented in the FB13 data but are implicit
based on the types of relationships connecting them. To enable experimentation
with entity types, simple heuristics were applied to assign each entity to a
single entity type among the following types: Person, Location, Institution,
Profession, Ethnicity, CauseOfDeath, Religion, and Gender. See code for
details. https://github.com/niraj17singh/LinkLogic.

Figure A.1.1: Distribution of different relation types in the FB13 and FB14
dataset

###  A.2 Details for construction of prediction explanation benchmark

For each query triple $(c,parent,p)$ in FB14, individual paths matching each
path category were identified and extracted for the benchmark. Due to the
bidirectional nature of the familial relationships, e.g.
$(h,\textit{spouse},t)\implies(t,\textit{spouse},h)$, all paths present in the
graph representing the conceptually equivalent information were included in
the benchmark. Paths were included in the benchmark regardless of whether the
corresponding edges were split in (or across) training, validation and test
sets, with these edge splits noted as metadata in the benchmark.

Figure A.2.1: The distribution of benchmark path count per query triple in the
Parents Benchmark.

s

###  A.3 KGE training

The KGE training was performed using the DGLKE Zheng et al. [2020], the code
publicly available on github. The hyperparameters used to train the ComplEx
decoder are shown in Table A.3.1. Mean reciprocal rank (MRR) per relation on
the test set is shown in Figure A.3.1.

Hyperparameters | Value
---|---
model_name | ComplEx
batch_size | 1000
neg_sample_size | 200
hidden_dim | 400
lr | 0.1
max_step | 50000
batch_size_eval | 16
neg_adversarial_sampling | True
regularization_coef | 2e-06
Table A.3.1: Hyperparameters used for training the ComplEx decoder on FB13 and
FB14 datasets. Figure A.3.1: Comparison of Mean Reciprocal Rank (MRR) for all
the relations in the FB13 and FB14 dataset using ComplEx decoder.

##  B LinkLogic supplementary information

###  B.1 Computing LinkLogic noise scaling parameters

The noise scaling parameters $\sigma_{h}$ and $\sigma_{t}$ from Equation 1 are
computed at runtime based on the distance of $\mathbf{h}$ and $\mathbf{t}$ to
neighboring embeddings. More specifically, neighbors of h are found by
generating the top $k$ predictions $\\{e_{1},e_{2},\dots,e_{k}\\}$ for the
query $(h,r,?)$ and subsequently finding the top $k$ predictions for each
query $(?,r,e_{i})$, where $e_{i}\in\\{e_{1},e_{2},\dots,e_{k}\\}$. This leads
to a total of $k^{2}$ neighbors
$\\{\tilde{{h}}_{1},\tilde{{h}}_{2}\dots\tilde{{h}}_{k^{2}}\\}$. Similarly,
the neighbors of $t$ can be obtained as
$\\{\tilde{{t}}_{1},\tilde{{t}}_{2}\dots\tilde{{t}}_{k^{2}}\\}$. Given the
embeddings of each $e\in\mathcal{E}$ as $\textbf{e}\in\mathcal{R}^{d}$,
$\sigma_{h}$ and $\sigma_{t}$ is identified using the following equations:

$\displaystyle\sigma_{h}=\sqrt{\frac{\sum_{j=1}^{k^{2}}\sum_{i=1}^{d}|\tilde{\textbf{h}}_{ji}-\textbf{h}_{i}|^{2}}{dk^{2}}}$
(4)
$\displaystyle\sigma_{t}=\sqrt{\frac{\sum_{j=1}^{k^{2}}\sum_{i=1}^{d}|\tilde{\textbf{t}}_{ji}-\textbf{t}_{i}|^{2}}{dk^{2}}}$
(5)

###  B.2 Pseudocode

Algorithm 1 provides a pseudocode representation of the LinkLogic method. We
denote the KGE decoder as f and the trained entity and relation embeddings as
embeddings as input to the function LinkLogic in the pseudocode. All other
inputs are consistent with the naming used in Section 3.

Algorithm 1 LinkLogic

1:function LinkLogic(embeddings, $n$, $l$, $k$, $f$, $\lambda$, $\alpha$,
$q=(h,r,t)$)

2: $\sigma_{h},\sigma_{t}$ = compute_sigmas(embeddings, $q$, $k$)

3: perturbed_queries = perturb_queries(embeddings, $q$, $\sigma_{h}$,
$\sigma_{t}$, $n$)

4: paths = select_paths($q$, $l$)

5: features = compute_features(perturbed_queries, paths, $f$)

6: labels = compute_labels(perturbed_queries, $f$)

7: coef = train_surrogate_model(features, labels, $\lambda$)

8: explanation = extract_nonzero_paths(features, coef)

9: return explanation

10:end function

###  B.3 Example computation of LinkLogic fidelity

For a given query $(\textrm{Maria Mozart},parent,\textrm{Leopold Mozart})$,
Figure B.3.1 shows the path scores for the $n=1000$ perturbed queries on the
x-axis and the predictions from the surrogate model on the y-axis. The
fidelity of the LinkLogic explanation is quantified using the $R^{2}$ score,
i.e, the variance explained by the surrogate model. In this example
$R^{2}=0.703$.

Figure B.3.1: A scatter plot of path scores for 1000 perturbed queries on the
$x$-axis and prediction of the surrogate model on $y$-axis.

###  B.4 Sample explanations on FB13 dataset

The LinkLogic explanations for 5 randomly sampled triples for all the
relations in the FB13 dataset (except for parent) are shown in Table B.4.1 to
B.4.12.

####  B.4.1 Familial relations

The LinkLogic explanations for the familial relations: spouse, and child are
shown in Table B.4.1 and B.4.2 respectively. We observe that in order to
explain spouse relation, LinkLogic uses reversed spouse paths, whereas it uses
parents links to explain child links. This indicates that the ComplEx
embeddings learn the bidirectional nature of spouse and inverse relation
between parents and child.

####  B.4.2 Location relations

The LinkLogic explanations for the location-based relations: location,
place_of_birth, place_of_death, and nationality are shown in Table B.4.3,
B.4.4, B.4.5 and B.4.6 respectively. We observe that in order to explain the
triples with location relation, the highest ranked paths use other location-
based paths for e.g. using place_of_birth and place_of_death.

####  B.4.3 Other relations

The LinkLogic explanations for the other relations: gender, ethnicity,
religion, institution, profession and cause_of_death, are shown in Table
B.4.7, B.4.8, B.4.9, B.4.10, B.4.11 and B.4.12 respectively.

Query | Coefficient | LinkLogic Explanation
---|---|---
moses $\xrightarrow{\text{spouse}}$ zipporah | 1.341 |  zipporah $\xrightarrow{\text{spouse}}$ moses
0.138 |  moses $\xrightarrow{\text{place\\_of\\_birth}}$ egypt
julia_lennon $\xrightarrow{\text{spouse}}$ freddie_lennon | 1.21 |  freddie_lennon $\xrightarrow{\text{spouse}}$ julia_lennon
0.209 |  julia_lennon $\xrightarrow{\text{child}}$ john_lennon
louis_xii_of_france $\xrightarrow{\text{spouse}}$ joan_of_france | 0.907 |  joan_of_france $\xrightarrow{\text{spouse}}$ louis_xii_of_france
0.259 |  louis_xii_of_france $\xrightarrow{\text{child}}$ renee_of_france
0.165 |  joan_of_france $\xrightarrow{\text{parent}}$ louis_xi_of_france
0.069 |  louis_xii_of_france $\xrightarrow{\text{spouse}}$ mary_tudor
0.04 |  louis_xii_of_france $\xrightarrow{\text{place\\_of\\_birth}}$ chateau_de_blois
ruth_hussey $\xrightarrow{\text{spouse}}$ bob_longenecker | 1.05 |  bob_longenecker $\xrightarrow{\text{spouse}}$ ruth_hussey
0.13 |  ruth_hussey $\xrightarrow{\text{cause\\_of\\_death}}$ surgical_complications
0.108 |  ruth_hussey $\xrightarrow{\text{place\\_of\\_birth}}$ providence
0.087 |  bob_longenecker $\xrightarrow{\text{institution}}$ pennsylvania_state_university
0.058 |  ruth_hussey $\xrightarrow{\text{location}}$ los_angeles_county
0.054 |  ruth_hussey $\xrightarrow{\text{location}}$ providence
0.013 |  ruth_hussey $\xrightarrow{\text{place\\_of\\_birth}}$ los_angeles_county
louis_xviii_of_france $\xrightarrow{\text{spouse}}$ marie_josephine | 0.497 |  marie_josephine $\xrightarrow{\text{parent}}$ maria_antonietta_of_spain
0.396 |  marie_josephine $\xrightarrow{\text{spouse}}$ louis_xviii_of_france
0.217 |  louis_xviii_of_france $\xrightarrow{\text{parent}}$ louis_dauphin_de_france
0.195 |  louis_xviii_of_france $\xrightarrow{\text{parent}}$ marie_josephe_of_saxony
0.082 |  marie_josephine $\xrightarrow{\text{parent}}$ victor_amadeus_iii_of_sardinia
Table B.4.1: LinkLogic explanations for five randomly selected examples for the spouse relation in the FB13 dataset. Query | Coefficient | LinkLogic Explanation
---|---|---
james_r_keene $\xrightarrow{\text{child}}$ foxhall_p_keene | 1.342 |  foxhall_p_keene $\xrightarrow{\text{parent}}$ james_r_keene
ptolemy_ii_philadelphus $\xrightarrow{\text{child}}$ lysimachus | 0.828 |  lysimachus $\xrightarrow{\text{parent}}$ ptolemy_ii_philadelphus
0.373 |  lysimachus $\xrightarrow{\text{spouse}}$ arsinoe_ii_of_egypt
0.077 |  ptolemy_ii_philadelphus $\xrightarrow{\text{child}}$ arsinoe_i_of_egypt
malietoa_tanumafili_i $\xrightarrow{\text{child}}$ malietoa_tanumafili_ii | 0.941 |  malietoa_tanumafili_ii $\xrightarrow{\text{parent}}$ malietoa_tanumafili_i
0.746 |  malietoa_tanumafili_i $\xrightarrow{\text{parent}}$ malietoa_laupepa
robert_owen $\xrightarrow{\text{child}}$ robert_dale_owen | 1.145 |  robert_dale_owen $\xrightarrow{\text{parent}}$ robert_owen
0.269 |  robert_owen $\xrightarrow{\text{location}}$ powys
william_jennings_bryan $\xrightarrow{\text{child}}$ ruth_bryan_owen | 1.24 |  ruth_bryan_owen $\xrightarrow{\text{parent}}$ william_jennings_bryan
0.327 |  william_jennings_bryan $\xrightarrow{\text{institution}}$ illinois_college
Table B.4.2: LinkLogic explanations for five randomly selected examples for the child relation in the FB13 dataset. Query | Coefficient | LinkLogic Explanation
---|---|---
richard_lieber $\xrightarrow{\text{location}}$ indianapolis | 0.796 |  richard_lieber $\xrightarrow{\text{place\\_of\\_birth}}$ indianapolis
hilary_p_jones $\xrightarrow{\text{location}}$ virginia | 0.495 |  hilary_p_jones $\xrightarrow{\text{place\\_of\\_birth}}$ hanover_county
0.289 |  hilary_p_jones $\xrightarrow{\text{place\\_of\\_birth}}$ virginia
john_k_tarbox $\xrightarrow{\text{location}}$ lawrence_massachusetts | 0.663 |  john_k_tarbox $\xrightarrow{\text{place\\_of\\_birth}}$ lawrence_massachusetts
0.279 |  john_k_tarbox $\xrightarrow{\text{place\\_of\\_birth}}$ methuen
john_ball_1818 $\xrightarrow{\text{location}}$ county_dublin | 0.46 |  john_ball_1818 $\xrightarrow{\text{place\\_of\\_birth}}$ county_dublin
0.319 |  john_ball_1818 $\xrightarrow{\text{place\\_of\\_birth}}$ dublin
theodore_lyman_1833 $\xrightarrow{\text{location}}$ boston_massachusetts | 0.605 |  theodore_lyman_1833 $\xrightarrow{\text{place\\_of\\_death}}$ nahant
0.049 |  theodore_lyman_1833 $\xrightarrow{\text{place\\_of\\_birth}}$ waltham
0.035 |  theodore_lyman_1833 $\xrightarrow{\text{place\\_of\\_birth}}$ boston_massachusetts
john_ball_1818 $\xrightarrow{\text{location}}$ county_dublin | 0.117 |  john_ball_1818 $\xrightarrow{\text{institution}}$ st_marys_college_oscott
Table B.4.3: LinkLogic explanations for five randomly selected examples for the location relation in the FB13 dataset. Query | Coefficient | LinkLogic Explanation
---|---|---
gaspara_stampa $\xrightarrow{\text{place\\_of\\_birth}}$ padua | 1.016 |  gaspara_stampa $\xrightarrow{\text{location}}$ padua
eugene_viollet-le-duc $\xrightarrow{\text{place\\_of\\_birth}}$ paris | 0.233 |  eugene_viollet-le-duc $\xrightarrow{\text{place\\_of\\_death}}$ lausanne
r_m_hare $\xrightarrow{\text{place\\_of\\_birth}}$ somerset | 0.838 |  r_m_hare $\xrightarrow{\text{location}}$ somerset
0.206 |  r_m_hare $\xrightarrow{\text{institution}}$ balliol_college_oxford
0.058 |  r_m_hare $\xrightarrow{\text{place\\_of\\_death}}$ oxfordshire
0.008 |  r_m_hare $\xrightarrow{\text{institution}}$ rugby_school
george_law_curry $\xrightarrow{\text{place\\_of\\_birth}}$ philadelphia | 0.284 |  george_law_curry $\xrightarrow{\text{profession}}$ newspaper
0.167 |  george_law_curry $\xrightarrow{\text{location}}$ pennsylvania
0.154 |  george_law_curry $\xrightarrow{\text{place\\_of\\_death}}$ portland
samuel_gridley_howe $\xrightarrow{\text{place\\_of\\_birth}}$ boston_massachusetts | 0.402 |  samuel_gridley_howe $\xrightarrow{\text{child}}$ laura_e_richards
0.265 |  samuel_gridley_howe $\xrightarrow{\text{institution}}$ harvard_medical_school
0.054 |  samuel_gridley_howe $\xrightarrow{\text{place\\_of\\_death}}$ massachusetts
0.039 |  samuel_gridley_howe $\xrightarrow{\text{spouse}}$ julia_ward_howe
Table B.4.4: LinkLogic explanations for five randomly selected examples for the place_of_birth relation in the FB13 dataset. Query | Coefficient | LinkLogic Explanation
---|---|---
pope_john_i $\xrightarrow{\text{place\\_of\\_death}}$ ravenna | 0.506 |  pope_john_i $\xrightarrow{\text{place\\_of\\_birth}}$ tuscany
0.434 |  pope_john_i $\xrightarrow{\text{place\\_of\\_birth}}$ ravenna
0.275 |  pope_john_i $\xrightarrow{\text{location}}$ ravenna
georges_damboise $\xrightarrow{\text{place\\_of\\_death}}$ lyon | 0.137 |  georges_damboise $\xrightarrow{\text{place\\_of\\_birth}}$ lyon
giuseppe_cesare_abba $\xrightarrow{\text{place\\_of\\_death}}$ brescia | 0.782 |  giuseppe_cesare_abba $\xrightarrow{\text{location}}$ brescia
0.223 |  giuseppe_cesare_abba $\xrightarrow{\text{place\\_of\\_birth}}$ brescia
0.02 |  giuseppe_cesare_abba $\xrightarrow{\text{nationality}}$ italy
jackie_coogan $\xrightarrow{\text{place\\_of\\_death}}$ santa_monica_california | 0.415 |  jackie_coogan $\xrightarrow{\text{spouse}}$ betty_grable
0.342 |  jackie_coogan $\xrightarrow{\text{location}}$ santa_monica_california
0.023 |  jackie_coogan $\xrightarrow{\text{cause\\_of\\_death}}$ cardiovascular_disease
0.013 |  jackie_coogan $\xrightarrow{\text{place\\_of\\_birth}}$ los_angeles
eddie_laughton $\xrightarrow{\text{place\\_of\\_death}}$ hollywood | 0.241 |  eddie_laughton $\xrightarrow{\text{place\\_of\\_birth}}$ sheffield
0.072 |  eddie_laughton $\xrightarrow{\text{cause\\_of\\_death}}$ pneumonia
Table B.4.5: LinkLogic explanations for five randomly selected examples for the place_of_death relation in the FB13 dataset. Query | Coefficient | LinkLogic Explanation
---|---|---
nikolai_erdman $\xrightarrow{\text{nationality}}$ russia | 0.318 |  nikolai_erdman $\xrightarrow{\text{location}}$ moscow
johanna_senfter $\xrightarrow{\text{nationality}}$ germany | 0.226 |  johanna_senfter $\xrightarrow{\text{place\\_of\\_death}}$ oppenheim
0.069 |  johanna_senfter $\xrightarrow{\text{place\\_of\\_birth}}$ oppenheim
emilio_de_bono $\xrightarrow{\text{nationality}}$ italy | 0.345 |  emilio_de_bono $\xrightarrow{\text{place\\_of\\_birth}}$ cassano_dadda
0.088 |  emilio_de_bono $\xrightarrow{\text{place\\_of\\_death}}$ verona
louis_of_spain $\xrightarrow{\text{nationality}}$ spain | 0.229 |  louis_of_spain $\xrightarrow{\text{parent}}$ philip_v_of_spain
0.21 |  louis_of_spain $\xrightarrow{\text{place\\_of\\_birth}}$ madrid
0.065 |  louis_of_spain $\xrightarrow{\text{place\\_of\\_death}}$ madrid
0.057 |  louis_of_spain $\xrightarrow{\text{spouse}}$ louise_elisabeth_of_orleans
0.026 |  louis_of_spain $\xrightarrow{\text{parent}}$ maria_luisa_of_savoy
horace-benedict $\xrightarrow{\text{nationality}}$ switzerland | 0.524 |  horace-benedict $\xrightarrow{\text{child}}$ albertine_necker_de_saussure
0.116 |  horace-benedict $\xrightarrow{\text{place\\_of\\_death}}$ geneva
Table B.4.6: LinkLogic explanations for five randomly selected examples for the nationality relation in the FB13 dataset. Query | Coefficient | LinkLogic Explanation
---|---|---
maria_montessori $\xrightarrow{\text{gender}}$ female | 0.095 |  maria_montessori $\xrightarrow{\text{child}}$ mario_montessori_sr
nance_oneil $\xrightarrow{\text{gender}}$ female | 0.057 |  nance_oneil $\xrightarrow{\text{location}}$ englewood
nicola_rescigno $\xrightarrow{\text{gender}}$ female | 0.023 |  nicola_rescigno $\xrightarrow{\text{place\\_of\\_death}}$ viterbo
jayne_mansfield $\xrightarrow{\text{gender}}$ female | 0.033 |  jayne_mansfield $\xrightarrow{\text{profession}}$ nude_glamour_model
0.03 |  jayne_mansfield $\xrightarrow{\text{place\\_of\\_birth}}$ bryn_mawr
winnifred_quick $\xrightarrow{\text{gender}}$ female | 0.005 |  winnifred_quick $\xrightarrow{\text{place\\_of\\_birth}}$ plymouth
Table B.4.7: LinkLogic explanations for five randomly selected examples for the gender relation in the FB13 dataset. We note that there is a strong gender bias in the FB13 data (with roughly 7 times as many males as females) which seems to have caused the KGE model to have a poor representation of the gender relation (details not shown). Query | Coefficient | LinkLogic Explanation
---|---|---
ayya_khema $\xrightarrow{\text{ethnicity}}$ germans | 0.091 |  ayya_khema $\xrightarrow{\text{place\\_of\\_birth}}$ berlin
0.034 |  ayya_khema $\xrightarrow{\text{religion}}$ judaism
walter_winchell $\xrightarrow{\text{ethnicity}}$ jew | 0.103 |  walter_winchell $\xrightarrow{\text{place\\_of\\_death}}$ hibbing
julian_tuwim $\xrightarrow{\text{ethnicity}}$ poles | 0.224 |  julian_tuwim $\xrightarrow{\text{place\\_of\\_death}}$ zakopane
0.087 |  julian_tuwim $\xrightarrow{\text{institution}}$ university_of_warsaw
stephen_i_of_hungary $\xrightarrow{\text{ethnicity}}$ hungarian_people | 0.291 |  stephen_i_of_hungary $\xrightarrow{\text{place\\_of\\_birth}}$ esztergom
0.212 |  stephen_i_of_hungary $\xrightarrow{\text{parent}}$ geza_of_hungary
| 0.031 |  stephen_i_of_hungary $\xrightarrow{\text{location}}$ esztergom
keenan_wynn $\xrightarrow{\text{ethnicity}}$ irish_american | 0.383 |  keenan_wynn $\xrightarrow{\text{parent}}$ ed_wynn
0.045 |  keenan_wynn $\xrightarrow{\text{place\\_of\\_birth}}$ new_york_state
0.031 |  keenan_wynn $\xrightarrow{\text{cause\\_of\\_death}}$ pancreatic_cancer
Table B.4.8: LinkLogic explanations for five randomly selected examples for the ethnicity relation in the FB13 dataset. Query | Coefficient | LinkLogic Explanation
---|---|---
ali_ibn_hussayn $\xrightarrow{\text{religion}}$ shia_islam | 0.309 |  ali_ibn_hussayn $\xrightarrow{\text{child}}$ muhammad_al-baqir
0.163 |  ali_ibn_hussayn $\xrightarrow{\text{parent}}$ husayn_ibn_ali
0.111 |  ali_ibn_hussayn $\xrightarrow{\text{religion}}$ islam
alexander_heriot $\xrightarrow{\text{religion}}$ anglicanism | 0.18 |  alexander_heriot $\xrightarrow{\text{institution}}$ wadham_college_oxford
catherine_mcauley $\xrightarrow{\text{religion}}$ roman_catholic_church | 0.129 |  catherine_mcauley $\xrightarrow{\text{location}}$ county_dublin
charles_iv_of_spain $\xrightarrow{\text{religion}}$ catholicism | 0.152 |  charles_iv_of_spain $\xrightarrow{\text{child}}$ maria_louisa
0.069 |  charles_iv_of_spain $\xrightarrow{\text{place\\_of\\_birth}}$ portici
0.037 |  charles_iv_of_spain $\xrightarrow{\text{child}}$ ferdinand_vii_of_spain
joseph_mccarthy $\xrightarrow{\text{religion}}$ roman_catholic_church | 0.31 |  joseph_mccarthy $\xrightarrow{\text{location}}$ appleton
Table B.4.9: LinkLogic explanations for five randomly selected examples for the religion relation in the FB13 dataset. Query | Coefficient | LinkLogic Explanation
---|---|---
john_l_sullivan_1899 $\xrightarrow{\text{institution}}$ dartmouth_college | 0.225 |  john_l_sullivan_1899 $\xrightarrow{\text{place\\_of\\_death}}$ exeter_new_hampshire
0.22 |  john_l_sullivan_1899 $\xrightarrow{\text{place\\_of\\_birth}}$ manchester
0.042 |  john_l_sullivan_1899 $\xrightarrow{\text{location}}$ manchester
ludwig_friedlander $\xrightarrow{\text{institution}}$ university_of_konigsberg | 0.307 |  ludwig_friedlander $\xrightarrow{\text{place\\_of\\_birth}}$ konigsberg
0.25 |  ludwig_friedlander $\xrightarrow{\text{institution}}$ humboldt_university_of_berlin
0.153 |  ludwig_friedlander $\xrightarrow{\text{place\\_of\\_death}}$ strasbourg
0.11 |  ludwig_friedlander $\xrightarrow{\text{institution}}$ university_of_leipzig
leonard_carmichael $\xrightarrow{\text{institution}}$ harvard_university | 0.341 |  leonard_carmichael $\xrightarrow{\text{institution}}$ tufts_university
kate_fleming $\xrightarrow{\text{institution}}$ college_of_william_and_mary | 0.271 |  kate_fleming $\xrightarrow{\text{place\\_of\\_birth}}$ arlington
0.26 |  kate_fleming $\xrightarrow{\text{cause\\_of\\_death}}$ drowning
0.205 |  kate_fleming $\xrightarrow{\text{place\\_of\\_death}}$ seattle
0.1 |  kate_fleming $\xrightarrow{\text{location}}$ washington_united_states
edward_mills_purcell $\xrightarrow{\text{institution}}$ harvard_university | 0.122 |  edward_mills_purcell $\xrightarrow{\text{institution}}$ purdue_university
0.076 |  edward_mills_purcell $\xrightarrow{\text{place\\_of\\_death}}$ cambridge_massachusetts
Table B.4.10: LinkLogic explanations for five randomly selected examples for the institution relation in the FB13 dataset. Query | Coefficient | LinkLogic Explanation
---|---|---
jeff_porcaro $\xrightarrow{\text{profession}}$ session_musician | 0.347 |  jeff_porcaro $\xrightarrow{\text{profession}}$ drummer
0.164 |  jeff_porcaro $\xrightarrow{\text{location}}$ hartford_connecticut
0.122 |  jeff_porcaro $\xrightarrow{\text{profession}}$ record_producer
pavel_sergeevich_alexandrov $\xrightarrow{\text{profession}}$ mathematician | 0.328 |  pavel_sergeevich_alexandrov $\xrightarrow{\text{institution}}$ moscow_state_university
cyril_gordon_martin $\xrightarrow{\text{profession}}$ engineer | 0.253 |  cyril_gordon_martin $\xrightarrow{\text{place\\_of\\_death}}$ woolwich
george_jessel $\xrightarrow{\text{profession}}$ actor | 0.133 |  george_jessel $\xrightarrow{\text{spouse}}$ lois_andrews
yolanda_king $\xrightarrow{\text{profession}}$ actor | 0.109 |  yolanda_king $\xrightarrow{\text{profession}}$ lgbt_social_movements
0.073 |  yolanda_king $\xrightarrow{\text{place\\_of\\_birth}}$ montgomery
0.053 |  yolanda_king $\xrightarrow{\text{parent}}$ coretta_scott_king
0.037 |  yolanda_king $\xrightarrow{\text{place\\_of\\_death}}$ santa_monica_california
Table B.4.11: LinkLogic explanations for five randomly selected examples for the profession relation in the FB13 dataset. Query | Coefficient | LinkLogic Explanation
---|---|---
dick_turpin $\xrightarrow{\text{cause\\_of\\_death}}$ capital_punishment | 0.516 |  dick_turpin $\xrightarrow{\text{cause\\_of\\_death}}$ hanging
john_f_collins $\xrightarrow{\text{cause\\_of\\_death}}$ pneumonia | 0.161 |  john_f_collins $\xrightarrow{\text{location}}$ boston_massachusetts
0.059 |  john_f_collins $\xrightarrow{\text{profession}}$ mayor
kazuo_ohno $\xrightarrow{\text{cause\\_of\\_death}}$ respiratory_failure | 0.427 |  kazuo_ohno $\xrightarrow{\text{place\\_of\\_death}}$ yokohama
robert_mcgehee $\xrightarrow{\text{cause\\_of\\_death}}$ stroke | 0.155 |  robert_mcgehee $\xrightarrow{\text{institution}}$ university_of_texas_at_austin
0.085 |  robert_mcgehee $\xrightarrow{\text{location}}$ mississippi
0.006 |  robert_mcgehee $\xrightarrow{\text{place\\_of\\_birth}}$ mississippi
robert_ludlum $\xrightarrow{\text{cause\\_of\\_death}}$ myocardial_infarction | 0.35 |  robert_ludlum $\xrightarrow{\text{place\\_of\\_death}}$ naples_florida
0.04 |  robert_ludlum $\xrightarrow{\text{institution}}$ wesleyan_university
Table B.4.12: LinkLogic explanations for five randomly selected examples for
the cause_of_death relation in the FB13 dataset.

###  B.5 Anne Frank family

Figure B.5.1 shows the family tree of Anne Frank. Section 5.3.3 uses this as
reference to compare the embeddings for siblings and spouse in the FB14
dataset.

Anne ($c$)Edith ($p$)Margot ($s$)Otto
($p_{2}$)parentsiblingchildchildparentparentspouse Figure B.5.1: Directed sub-
graph representing the Frank family. The link in red shows the query triple.