# Can Persistent Homology provide an efficient alternative for Evaluation of
Knowledge Graph Completion Methods?

Anson Bastos<EMAIL_ADDRESS>IIT, HyderabadIndia ,  Kuldeep Singh
<EMAIL_ADDRESS>Zerotha Research and Cerence GmbHGermany ,
Abhishek Nadgeri<EMAIL_ADDRESS>Zerotha Research and RWTH
AachenGermany ,  Johannes Hoffart<EMAIL_ADDRESS>SAPGermany ,  Toyotaro
Suzumura<EMAIL_ADDRESS>The University of TokyoJapan and  Manish Singh
<EMAIL_ADDRESS>IIT HyderabadIndia

(2023)

###### Abstract.

In this paper we present a novel method, Knowledge Persistence
($\mathcal{KP}$), for faster evaluation of Knowledge Graph (KG) completion
approaches. Current ranking-based evaluation is quadratic in the size of the
KG, leading to long evaluation times and consequently a high carbon footprint.
$\mathcal{KP}$ addresses this by representing the topology of the KG
completion methods through the lens of topological data analysis, concretely
using persistent homology. The characteristics of persistent homology allow
$\mathcal{KP}$ to evaluate the quality of the KG completion looking only at a
fraction of the data. Experimental results on standard datasets show that the
proposed metric is highly correlated with ranking metrics (Hits@N, MR, MRR).
Performance evaluation shows that $\mathcal{KP}$ is computationally efficient:
In some cases, the evaluation time (validation+test) of a KG completion method
has been reduced from 18 hours (using Hits@10) to 27 seconds (using
$\mathcal{KP}$), and on average (across methods & data) reduces the evaluation
time (validation+test) by $\approx$ 99.96%.

††journalyear: 2023††conference: Proceedings of the Web Conference 2023; APRIL
30 - MAY 4, 2023; Texas, USA††booktitle: Proceedings of the Web Conference
2023 (WWW ’23), APRIL 30 - MAY 4, 2023, Texas, USA††doi:
10.XXXXX/YYYYY.3449917††isbn: 978-Y-4500-YYYY-7/21/04††copyright:
rightsretained

##  1\. Introduction

Publicly available Knowledge Graphs (KGs) find broad applicability in several
downstream tasks such as entity linking, relation extraction, fact-checking,
and question answering (Ji et al., 2021; Singh et al., 2018). These KGs are
large graph databases used to express facts in the form of relations between
real-world entities and store these facts as triples (subject, relation,
object). KGs must be continuously updated because new entities might emerge or
facts about entities are extended or updated. Knowledge Graph Completion (KGC)
task aims to fill the missing piece of information into an incomplete triple
of KG (Ji et al., 2021; Gesese et al., 2019; Bastos et al., 2021).

Several Knowledge Graph Embedding (KGE) approaches have been proposed to model
entities and relations in vector space for missing link prediction in a KG
(Wang et al., 2017). KGE methods infer the connectivity patterns (symmetry,
asymmetry, etc.) in the KGs by defining a scoring function to calculate the
plausibility of a knowledge graph triple. While calculating plausibility of a
KG triple $\uptau=(e_{h},r,e_{t})$, the predicted score by scoring function
affirms the confidence of a model that entities $e_{t}$ and $e_{h}$ are linked
by $r$.

For evaluating KGE methods, ranking metrics have been widely used (Ji et al.,
2021) which is based on the following criteria: given a KG triple with a
missing head or tail entity, what is the ability of the KGE method to rank
candidate entities averaged over triples in a held-out test set (Mohamed et
al., 2020)? These ranking metrics are useful as they intend to gauge the
behavior of the methods in real world applications of KG completion. Since
2019, over 100 KGE articles have been published in various leading conferences
and journals that use ranking metrics as evaluation
protocol111https://github.com/xinguoxia/KGE#papers.

Limitations of Ranking-based Evaluation: The key challenge while computing
ranking metrics for model evaluation is the time taken to obtain them. Since
the (most of) KGE models aim to rank all the negative triples that are not
present in the KG (Bordes et al., 2011; Bordes et al., 2013), computing these
metrics takes a quadratic time in the number of entities in the KG. Moreover,
the problem gets alleviated in the case of hyper-relations (Zhang et al.,
2021) where more than two entities participate, leading to exponential
computation time. For instance, Ali et al. (2021) spent 24,804 GPU hours of
computation time while performing a large-scale benchmarking of KGE methods.

There are two issues with high model evaluation time. Firstly, efficiency at
evaluation time is not a widely-adapted criterion for assessing KGE models
alongside accuracy and related measures. There are efforts to make KGE methods
efficient at training time (Wang et al., 2021d, 2022). However, these methods
also use ranking-based protocols resulting in high evaluation time. Secondly,
the need for significant computational resources for the KG completion task
excludes a large group of researchers in universities/labs with restricted GPU
availability. Such preliminary exclusion implicitly challenges the basic
notion of various diversity and inclusion initiatives for making the Web and
its related research accessible to a wider community. In past, researchers
have worked extensively towards efficient Web-related technologies such as Web
Crawling (Broder et al., 2003), Web Indexing (Lim et al., 2003), RDF
processing (Galárraga et al., 2014), etc. Hence, for the KG completion task,
similar to other efficient Web-based research, there is a necessity to develop
alternative evaluation protocols to reduce the computation complexity, a
crucial research gap in available KGE scientific literature. Another critical
issue in ranking metrics is that they are biased towards popular entities and
such popularity bias is not captured by current evaluation metrics (Mohamed et
al., 2020). Hence, we need a metric which is efficient than popular ranking
metrics and also omits such biases.

Motivation and Contribution: In this work, we focus on addressing above-
mentioned key research gaps and aim for the first study to make KGE evaluation
more efficient. We introduce Knowledge Persistence($\mathcal{KP}$), a method
for characterizing the topology of the learnt KG representations. It builds
upon Topological Data Analysis (Wasserman, 2018) based on the concepts from
Persistent Homology(PH) (Edelsbrunner et al., 2000), which has been proven
beneficial for analyzing deep networks (Rieck et al., 2018; Moor et al.,
2020). PH is able to effectively capture the geometry of the manifold on which
the representations reside whilst requiring fraction of data (Edelsbrunner et
al., 2000). This property allows to reduce the quadratic complexity of
considering all the data points (KG triples in our case) for ranking. Another
crucial fact that makes PH useful is its stability with respect to
perturbations making $\mathcal{KP}$ robust to noise (Hensel et al., 2021)
mitigating the issues due to the open-world problem. Thus we use PH due to its
effectiveness for limited resources and noise (Turkeš et al., 2022).
Concretely, the following are our key contributions:

  1. (1)

We propose ($\mathcal{KP}$), a novel approach along with its theoretical
foundations to estimate the performance of KGE models through the lens of
topological data analysis. This allows us to drastically reduce the
computation factor from order of $\mathcal{O}(|\mathcal{E}|^{2})$ to
$\mathcal{O}(|\mathcal{E}|)$. The code is here.

  2. (2)

We run extensive experiments on families of KGE methods (e.g., Translation,
Rotation, Bi-Linear, Factorization, Neural Network methods) using standard
benchmark datasets. The experiments show that $\mathcal{KP}$ correlates well
with the standard ranking metrics. Hence, $\mathcal{KP}$ could be used for
faster prototyping of KGE methods and paves the way for efficient evaluation
methods in this domain.

In the remainder of the paper, related work is in section 2. Section 3 briefly
explains the concept of persistent homology. Section 4 describes the proposed
method. Later, section 5 shows associated empirical results and we conclude in
section 7.

##  2\. Related Work

Broadly, KG embeddings are classified into translation and semantic matching
models (Wang et al., 2017). Translation methods such as TransE (Bordes et al.,
2013), TransH (Wang et al., 2014), TransR (Lin et al., 2015) use distance-
based scoring functions. Whereas semantic matching models (e.g., ComplEx
(Trouillon et al., 2016), Distmult (Yang et al., 2015), RotatE (Sun et al.,
2018)) use similarity-based scoring functions.

Kadlec et al. (2017) first pointed limitations of KGE evaluation and its
dependency on hyperparameter tuning. (Sun et al., 2020) with exhaustive
evaluation (using ranking metrics) showed issues of scoring functions of KGE
methods whereas (Nayyeri et al., 2019) studied the effect of loss function of
KGE performance. Jain et al. (2021) studied if KGE methods capture KG semantic
properties. Work in (Pezeshkpour et al., 2020) provides a new dataset that
allows the study of calibration results for KGE models. Speranskaya et al.
(2020) used precision and recall rather than rankings to measure the quality
of completion models. Authors proposed a new dataset containing triples such
that their completion is both possible and impossible based on queries.
However, queries were build by creating a tight dependency on such queries for
the evaluation as pointed by (Tiwari et al., 2021). Rim et al. (2021) proposed
a capability-based evaluation where the focus is to evaluate KGE methods on
various dimensions such as relation symmetry, entity hierarchy, entity
disambiguation, etc. Mohamed et al. (2020) fixed the popularity bias of
ranking metrics by introducing modified ranking metrics. The geometric
perspective of KGE methods was introduced by (Sharma et al., 2018) and its
correlation with task performance. Berrendorf et al. (2020) suggested the
adjusted mean rank to improve reciprocal rank, which is an ordinal scale.
Authors do not consider the effect of negative triples available for a given
triple under evaluation. (Tiwari et al., 2021) propose to balances the number
of negatives per triple to improve ranking metrics. Authors suggested the
preparation of training/testing splits by maintaining the topology. Work in
(Li et al., 2021) proposes efficient non-sampling techniques for KG embedding
training, few other initiatives improve efficiency of KGE training time (Wang
et al., 2021d, 2022, c), and hyperparameter search efficiency of embedding
models (Zhang et al., 2022; Wang et al., 2021a; Tu et al., 2019).

Overall, the literature is rich with evaluations of knowledge graph completion
methods (Jain et al., 2020; Bansal et al., 2020; Tabacof and Costabello, 2019;
Safavi and Koutra, 2020). However, to the best of our knowledge, extensive
attempts have not been made to improve KG evaluation protocols’ efficiency,
i.e., to reduce run-time of widely-used ranking metrics for faster
prototyping. We position our work orthogonal to existing attempts such as
(Sharma et al., 2018), (Tiwari et al., 2021), (Mohamed et al., 2020), and (Rim
et al., 2021). In contrast with these attempts, our approach provides a
topological perspective of the learned KG embeddings and focuses on improving
the efficiency of KGE evaluations.

Figure 1. Calculating Knowledge Persistence($\mathcal{KP}$) score from the
given KG and KG embedding method. The KG is sampled for
positive($\mathcal{G}^{+}$) and negative($\mathcal{G}^{-}$) triples (step
one), keeping the order $\mathcal{O}(|\mathcal{E}|)$. The edge weights
represent the score obtained from the KG embedding method. In step two, the
persistence diagram (PD) is computed using filtration process explained in
Figure 2. In final step, a Sliced Wasserstein distance (SW) is obtained
between the PDs of $\mathcal{G}^{+}$ and $\mathcal{G}^{-}$ to get the
$\mathcal{KP}$ score. However, ranking metrics run the KGE methods over all
the $\mathcal{O}(|\mathcal{E}|^{2})$ triples as explained in bottom left part
of the figure(red box).

##  3\. Preliminaries

We now briefly describe concepts used in this paper.
Ranking metrics have been used for evaluating KG embedding methods since the
inception of the KG completion task (Bordes et al., 2013). These metrics
include the Mean Rank (MR), Mean Reciprocal Rank (MRR) and the cut-off hit
ratio (Hits@N (N=1,3,10)). MR reports the average predicted rank of all the
labeled triples. MRR is the average of the inverse rank of the labelled
triples. Hits@N evaluates the fraction of the labeled triples that are present
in the top N predicted results.

Persistent Homology (PH) (Edelsbrunner et al., 2000; Hensel et al., 2021):
studies the topological features such as components in 0-dimension (e.g., a
node), holes in 1-dimension (e.g., a void area bounded by triangle edges) and
so on, spread over a scale. Thus, one need not choose a scale beforehand. The
number(rank) of these topological features(homology group) in every dimension
at a particular scale can be used for downstream applications. Consider the
simplicial complex ( e.g., point is a 0-simplex, an edge is a 1-simplex, a
triangle is a 2-simplex ) $C$ with weights $a_{0}\leq a_{1}\leq a_{2}\dots
a_{m-1}$, which could represent the edge weights, for example, the triple
score from the KG embedding method in our case. One can then define a
Filtration process (Edelsbrunner et al., 2000), which refers to generating a
nested sequence of complexes $\phi\subseteq C_{1}\subseteq C_{2}\subseteq\dots
C_{m}=C$ in time/scale as the simplices below the threshold weights are added
in the complex. The filtration process (Edelsbrunner et al., 2000) results in
the creation(birth) and destruction(death) of components, holes, etc. Thus
each structure is associated with a birth-death pair $(a_{i},a_{j})\in R^{2}$
with $i\leq j$. The persistence or lifetime of each component can then be
given by $a_{j}-a_{i}$. A persistence diagram (PD) summarizes the
(birth,death) pair of each object on a 2D plot, with birth times on the x axis
and death times on the y axis. The points near the diagonal are shortlived
components and generally are considered noise (local topology), whereas the
persistent objects (global topology) are treated as features. We consider
local and global topology to compare two PDs (i.e., positive and negative
triple graphs in our case).

##  4\. Problem Statement and Method

###  4.1. Problem Setup

We define a KG as a tuple $KG=(\mathcal{E},\mathcal{R},\mathcal{T}^{+})$ where
$\mathcal{E}$ denotes the set of entities (vertices), $\mathcal{R}$ is the set
of relations (edges), and
$\mathcal{T}^{+}\subseteq\mathcal{E}\times\mathcal{R}\times\mathcal{E}$ is a
set of all triples. A triple $\uptau=(e_{h},r,e_{t})\in\mathcal{T}^{+}$
indicates that, for the relation $r\in\mathcal{R}$, $e_{h}$ is the head entity
(origin of the relation) while $e_{t}$ is the tail entity. Since $KG$ is a
multigraph; $e_{h}=e_{t}$ may hold and $|\\{r_{e_{h},e_{t}}\\}|\geq 0$ for any
two entities. The KG completion task predicts the entity pairs $\langle
e_{i},e_{j}\rangle$ in the KG that have a relation $r^{c}\in\mathcal{R}$
between them.

###  4.2. Proposed Method

Figure 2. For a KGE method, the positive triple graph $\mathcal{G}^{+}$ is
used as input (leftmost graph with edge weights) and filtration process is
applied on the edge weights (calculated by KGE method) for the graph. The
filtration starts with only nodes as first step, and based on the edge
weights, edges are added to the nodes. The persistence diagram is given on the
right with red dots indicating 0-dimensional homology (components) and the
blue dots indicating 1-dimensional homology (cycles). Persistent Diagram
generated from this filtration process is a condensed 2D representation of
$\mathcal{G}^{+}$. A similar process is repeated for $\mathcal{G}^{-}$.

In this section we describe our approach for evaluating KG embedding methods
using the theory of persistent homology (PH) . This process is divided into
three steps ( Figure 1), namely: (i) Graph construction, (ii) Filtration
process and (iii) Sliced Wasserstein distance computation. The first step
creates two graphs (one for positive triples, another for negative triples)
using sampling($\mathcal{O(\mathcal{V})}$ triples), with scores calculated by
a KGE method as edge weights. The second step considers these graphs and,
using a process called ”filtration,” converts to an equivalent lower dimension
representation. The last step calculates the distance between graphs to
provide a final metric score. We now detail the approach.

####  4.2.1. Graph Construction

We envisioned KGE from the topological lens while proposing an efficient
solution for its evaluation. Previous works such as (Sharma et al., 2018)
proposed a KGE metric only considering embedding space. However, we intend to
preserve the topology (graph structure and its topological feature) along with
the KG embedding features. We first construct graphs of positive and negative
triples. We denote a graph as $(\mathcal{V},\mathcal{E})$ where $\mathcal{V}$
is the set of $N$ nodes and $\mathcal{E}$ represents the edges between them.
Consider a KG embedding method $\mathcal{M}$ that takes as input the triple
$\uptau=(h,r,t)\in\mathcal{T}$ and gives the score $s_{\uptau}$ of it being a
right triple. We construct a weighted directed graph $\mathcal{G}^{+}$ from
positive triples $\uptau\in\mathcal{T}^{+}$ in the train set, with the
entities as the nodes and the relations between them as the edges having
$s_{\uptau}$ as the edge weights. Here, $s_{\uptau}$ is the score calculated
by KGE method for a triple and we propose to use it as the edge weights. Our
idea is to capture topology of graph ($\mathcal{G}^{+}$) with representation
learned by a KG embedding method. We sample an order of
$\mathcal{O}(|\mathcal{E}|)$ triples, $|\mathcal{E}|$ being the number of
entities to keep computational time linear. Similarly, we construct a negative
graph $\mathcal{G}^{-}$ by sampling the same number of unknown triples as the
positive samples. One question may arise if $\mathcal{KP}$ is robust to
sampling, that we answer theoretically in Theorem 4.5 and empirically in
section 6. Note, here we do not take all the negative triples in the graphs
and consider only a fraction of what the ranking metrics need. This is a
fundamental difference with ranking metrics. Ranking metrics use all the
unlabeled triples as negatives for ranking, thus incurring a computational
cost of $O(|\mathcal{E}|^{2})$.

####  4.2.2. Filtration Process

Having constructed the Graphs $\mathcal{G}^{+}$ and $\mathcal{G}^{-}$, we now
need some definition of a distance between them to define a metric. However,
since the KGs could be large with many entities and relations, directly
comparing the graphs could be computationally challenging. Therefore, we
allude to the theory of persistent homology (PH) to summarize the structures
in the graphs in the form of the persistence diagram (PD). Such summarizing is
obtained by a process known as filtration (Zomorodian and Carlsson, 2005). One
can imagine a PD as mapping of higher dimensional data to a 2D plane upholding
the representation of data points and we can then derive computational
efficiency for distance comparison between 2D representations. Specifically,
we compute the 0-dimensional topological features (i.e., connected-
nodes/components) for each graph ($\mathcal{G}^{-}$ and $\mathcal{G}^{+}$) to
keep the computation time linear. We also experimented using the 1-dimensional
features without much empirical benefit.

Consider the positive triple graph $\mathcal{G}^{+}$ as input (cf., Figure 2).
We would need a scale (as pointed in section 3) for the filtration process.
Once the filtration process starts, initially, we have a graph structure
containing only the nodes (entities) and no edges of $\mathcal{G}^{+}$. For
capturing topological features at various scales, we define a variable $a$
which varies from $-\infty$ to $+\infty$ and it is then compared with edge
weights ($s_{\uptau}$). A scale allows to capture topology at various
timesteps. Thus, we use the edge weights obtained from the scores
($s_{\uptau}$) of the KGE methods for filtration. As the filtration proceeds,
the graph structures (components) are generated/removed. At a given scale $a$,
the graph structure ($(\mathcal{G}^{+}_{sub})_{a}$) contains those edges
(triples) for which $s_{\uptau}\leq a$. Formally, this is expressed as:

$(\mathcal{G}^{+}_{sub})_{a}=\\{(\mathcal{V},\mathcal{E}^{+}_{a})|\mathcal{E}^{+}_{a}\subseteq\mathcal{E},s_{\uptau}\leq
a\ \forall\uptau\in\mathcal{E}^{+}_{a}\\}$

Alternatively, we add those edges for which score of the triple is greater
than or equal to the filtration value, i.e., $s_{\uptau}\geq a$ defined as

$(\mathcal{G}^{+}_{super})_{a}=\\{(\mathcal{V},\mathcal{E}^{{a}^{+}})|\mathcal{E}^{{a}^{+}}\subseteq\mathcal{E},s_{\uptau}\geq
a\ \forall\uptau\in\mathcal{E}^{{a}^{+}}\\}$

One can imagine that for filtration, graph $\mathcal{G}^{+}$ is subdivided
into $(\mathcal{G}^{+}_{sub})_{a}$ and $(\mathcal{G}^{+}_{super})_{a}$ as the
filtration adds/deletes edges for capturing topological features. Hence,
specific components in a sub-graphs will appear and certain components will
disappear at different scale levels (timesteps) $a=1,3,5$ and so on. Please
note, Figure 2 explains creation of PD for $(\mathcal{G}^{+}_{sub})_{a}$. A
similar process is repeated for $(\mathcal{G}^{+}_{super})_{a}$. This
expansion/contraction process enables capturing topology at different time-
steps without worrying about defining an optimal scale (similar to
hyperparameter). Next step is the creation of persistent diagrams of
$(\mathcal{G}^{+}_{sub})_{a}$ and $(\mathcal{G}^{+}_{super})_{a}$ where the
x-axis and y-axis denotes the timesteps of appearance/disappearance of
components. For creating a 2D representation graph, components of graphs which
appear(disappear) during filtration process at $a_{x}(a_{y})$ are plotted on
$(a_{x},a_{y})$. The persistence or lifetime of each component can then be
given by $a_{y}-a_{x}$. At implementation level, one can view PDs($\in
R^{N\times 2}$) of $(\mathcal{G}^{+}_{sub})_{a}$ and
$(\mathcal{G}^{+}_{super})_{a}$ as tensors which are concatenated into one
common tensor representing positive triple graph $\mathcal{G}^{+}$. Hence,
final PD of $\mathcal{G}^{+}$ is a concatenation of PDs of
$(\mathcal{G}^{+}_{sub})_{a}$ and $(\mathcal{G}^{+}_{super})_{a}$. This final
persistent diagram represents a summary of the local and global topological
features of the graph $\mathcal{G}^{+}$. Following are the benefits of a
persistent diagram against considering the whole graph: 1) a 2D summary of a
higher dimensional graph structure data is highly beneficial for large graphs
in terms of the computational efficiency. 2) The summary could contain fewer
data points than the original graph, preserving the topological information.
Similarly, the process is repeated for negative triple graph $\mathcal{G}^{-}$
for creating its persistence diagram. Now, the two newly created PDs are used
for calculating the proposed metric score.

####  4.2.3. Sliced Wasserstein distance computation

To compare two PDs, generally the Wasserstein distance between them is
computed (Fasy et al., 2020). As the Wasserstein distance could be
computationally costly, we find the sliced Wasserstein distance (Carrière et
al., 2017) between the PDs, which we empirically observe to be eight times
faster on average. The Sliced Wasserstein distance($SW$) between measures
$\mu$ and $\nu$ is:

$SW_{p}(\mu,\nu)=\left(\int_{S^{d-1}}W^{p}_{p}(R_{\mu}(.,\theta),R_{\nu}(.,\theta))\right)^{\frac{1}{p}}$

where $R_{\mu}(.,\theta)$ is the projection of $\mu$ along $\theta$, $W$ is
initial Wasserstein distance. Generally a Monte Carlo average over $L$ samples
is done instead of the integral. The $SW$ distance takes
$\mathcal{O}(LNd+LNlog(N))$ time which can be improved to linear time
$\mathcal{O}(Nd)$ for $SW_{2}$ (i.e., Euclidean distance) as a closed form
solution (Nadjahi et al., 2021). Thus,

(1) $\mathcal{KP}(\mathcal{G}^{+},\mathcal{G}^{-})=SW(D^{+},D^{-})$

where $D^{+},D^{-}$ are the persistence diagrams for
$\mathcal{G}^{+},\mathcal{G}^{-}$ respectively. Since the metric is obtained
by summarizing the Knowledge graph using Persistence diagrams we term it as
Knowledge Persistence($\mathcal{KP}$). As $\mathcal{KP}$ correlates well with
ranking metrics (sections 4.2.4 and 5), higher $\mathcal{KP}$ signifies a
better performance of the KGE method.

####  4.2.4. Theoretical justification

This section briefly states the theoretical results justifying the proposed
method to approximate the ranking metrics. We begin the analysis by assuming
two distributions: One for the positive graph’s edge weights(scores) and the
other for the negative graph. We define a metric ”PERM” (Figure 3), that is a
proxy to the ranking metrics while being continuous(for the definition of
integrals and derivatives) for ease of theoretical analysis. The proof
sketches are given in the appendix.

Figure 3. Figure gives an intuition of the metric PERM which is designed to be
a proxy to the ranking metrics for ease of theoretical analysis. For a given
positive triple $\tau$ with score $x_{\tau}$ the expected rank($ER(\tau)$) is
defined as the area under the curve of the negative distribution from
$x_{\tau}$ to $\infty$(shown in the shaded area above). PERM is then defined
as the expectation of the expected rank under the positive distribution.

###### Definition 4.1 (Expected Ranking(ER)).

Consider the positive triples to have the distribution $D^{+}$ and the
negative triples to have the distribution $D^{-}$. For a positive triple with
score $a$ its expected ranking(ER) is defined as,
$ER(a)=\int_{x=a}^{x=\infty}D^{-}(x)dx$

###### Definition 4.2 (PERM).

Consider the positive triples to have the distribution $D^{+}$ and the
negative triples to have the distribution $D^{-}$. The PERM metric is then
defined as, $PERM=\int_{x=-\infty}^{x=\infty}D^{+}(x)ER(x)dx$

It is easy to see that PERM has a monotone increasing correspondence with the
actual ranking metrics. That is, as many of the negative triples get a higher
score than the positive triples, the distribution of the negative triples will
shift further right of the positive distribution. Hence, the area under the
curve would increase for a given triple(x=a). We just established a monotone
increasing correspondence of PERM with the ranking metrics, we now need show
that there exists a one-one correspondence between PERM and $\mathcal{KP}$.
For closed-form solutions, we work with normalised distributions (can be
extended to other distributions using (Sakia, 1992)) of KGE score under the
following mild consideration: As the KGE method converges, the mean
statistic($m_{\nu}$) of the scores of the positive triples consistently lies
on one side of the half-plane formed by the mean statistic($m_{\mu}$) of the
negative triples, irrespective of the data distribution.

###### Lemma 4.0.

$\mathcal{KP}$ has a monotone increasing correspondence with the Proxy of the
Expected Ranking Metrics(PERM) under the above stated considerations as
$m_{\nu}$ deviates from $m_{\mu}$

The above lemma shows that there is a one-one correspondence between
$\mathcal{KP}$ and PERM and by definition PERM has a one-one correspondence
with the ranking metrics. Therefore, the next theorem follows as a natural
consequence:

###### Theorem 4.4.

$\mathcal{KP}$ has a one-one correspondence with the ranking metrics under the
above stated considerations.

The above theorem states that, with high probability, there exists a
correlation between $\mathcal{KP}$ and the ranking metrics under certain
considerations and proof details are in the appendix. In an ideal case, we
seek a linear relationship between the proposed measure and the ranking
metric. This would help interpret whether an increase/decrease in the measure
would cause a corresponding increase/decrease in the ranking metric we wish to
simulate. Such interpretation becomes essential when the proposed metric has
different behavior from the existing metric. While the correlation could be
high, for interpretability of the results, we would also like the change in
$\mathcal{KP}$ to be bounded for a change in the scores(ranking metrics). The
below theorem gives a sense for this bound.

###### Theorem 4.5.

Under the considerations of theorem 4.4, the relative change in $\mathcal{KP}$
on addition of random noise to the scores is bounded by a function of the
original and noise-induced covariance matrix as
$\frac{\Delta\mathcal{KP}}{\mathcal{KP}}\leq
max((1-|\Sigma_{\mu_{1}}^{+1}\Sigma_{\mu_{2}}^{-1}|^{\frac{3}{2}}),(1-|\Sigma_{\nu_{1}}^{+1}\Sigma_{\nu_{2}}^{-1}|^{\frac{3}{2}}))$,
where $\Sigma_{\mu_{1}}$ and $\Sigma_{\nu_{1}}$ are the covariance matrices of
the positive and negative triples’ scores respectively and $\Sigma_{\mu_{2}}$
and $\Sigma_{\nu_{2}}$ are that of the corrupted scores.

Theorem 4.5 gives a bound on the change in $\mathcal{KP}$ while inducing noise
in the KGE predictions. Ideally, the error/change would be 0, and as the noise
is increased(and the ranking changed), gradually, the $\mathcal{KP}$ value
also changes in a bounded manner as desired.

##  5\. Experimental Setup

For de-facto KGC task (c.f., section 4.1), we use popular KG embedding methods
from its various categories: (1) Translation: TransE (Bordes et al., 2013),
TransH (Wang et al., 2014), TransR (Lin et al., 2015) (2) Bilinear, Rotation,
and Factorization: RotatE (Sun et al., 2018) TuckER (Balažević et al., 2019),
and ComplEx (Trouillon et al., 2016), (3) Neural Network based: ConvKB (Nguyen
et al., 2018). The method selection and evaluation choices are similar to
(Mohamed et al., 2020; Rim et al., 2021) that propose new metrics for KG
embeddings. All methods run on a single P100 GPU machine for a maximum of 100
epochs each and evaluated every 5 epochs. For training/testing the KG
embedding methods we make use of the pykg2vec (Yu et al., 2021) library and
validation runs are executed 20 times on average. We use the standard/best
hyperparameters for these datasets that the considered KGE methods reported
(Bordes et al., 2013; Wang et al., 2014; Lin et al., 2015; Sun et al., 2018;
Balažević et al., 2019; Trouillon et al., 2016; Yu et al., 2021).

###  5.1. Datasets

We use standard English KG completion datasets: WN18, WN18RR, FB15k237, FB15k,
YAGO3-10 (Ali et al., 2021; Sun et al., 2018). The WN18 dataset is obtained
from Wordnet (Miller, 1995) containing lexical relations between English
words. WN18RR removes the inverse relations in the WN18 dataset. FB15k is
obtained from the Freebase (Bollacker et al., 2007) knowledge graph, and
FB15k237 was created from FB15k by removing the inverse relations. The dataset
details are in the Table 1. For scaling experiment, we rely on large scale
YAGO3-10 dataset (Ali et al., 2021) and due to brevity, results for Yago3-10
are in appendix ( cf., Figure 6 and table 9).

###  5.2. Comparative Methods

Considering ours is the first work of its kind, we select some competitive
baselines as below and explain ”why” we chose them. For evaluation, we report
correlation (Chok, 2010) between $\mathcal{KP}$ and baselines with ranking
metrics (Hits@N (N= 1,3,10), MRR and MR).

Conicity (Sharma et al., 2018): It finds the average cosine of the angle
between an embedding and the mean embedding vector. In a sense, it gives
spread of a KG embedding method in space. We would like to observe instead of
topology, if calculating geometric properties of a KG embedding method be an
alternative for ranking metric.

Average Vector Length: This metric was also proposed by Sharma et al. (2018)
to study the geometry of the KG embedding methods. It computes the average
length of the embeddings.

Graph Kernel (GK): we use graph kernels to compare the two
graphs($\mathcal{G}^{+},\mathcal{G}^{-}$) obtained for our approach. The
rationale is to check if we could get some distance metric that correlates
with the ranking metrics without persistent homology. Hence, this baseline
emphasizes a direct comparison for the validity of persistent homology in our
proposed method. As an implementation, we employ the widely used shortest path
kernel (Borgwardt and Kriegel, 2005) to compare how the paths(edge
weights/scores) change between the two graphs. Since the method is
computationally expensive, we sample nodes (Borgwardt et al., 2007) and apply
the kernel on the sampled graph, averaging multiple runs.

Table 1. (Open-Source)Benchmark Datasets for Experiments. Dataset | Triples | Entities | Relations
---|---|---|---
FB15K | 592,213 | 14.951 | 1,345
FB15K-237 | 272,115 | 14,541 | 237
WN18 | 151,442 | 40,943 | 18
WN18RR | 93,003 | 40,943 | 11
Yago3-10 | 1,089,040 | 123,182 | 37

Metrics FB15K FB15K237 WN18 WN18RR Hits1($\uparrow$) Hits3($\uparrow$)
Hits10($\uparrow$) MR($\downarrow$) MRR($\uparrow$) Hits1($\uparrow$)
Hits3($\uparrow$) Hits10($\uparrow$) MR($\downarrow$) MRR($\uparrow$)
Hits1($\uparrow$) Hits3($\uparrow$) Hits10($\uparrow$) MR($\downarrow$)
MRR($\uparrow$) Hits1($\uparrow$) Hits3($\uparrow$) Hits10($\uparrow$)
MR($\downarrow$) MRR($\uparrow$) Conicity -0.156 -0.170 -0.202 0.085 -0.183
0.509 0.379 0.356 -0.352 0.424 -0.052 -0.096 -0.123 0.389 -0.096 -0.267 -0.471
-0.510 0.266 -0.448 AVL 0.339 0.325 0.261 -0.423 0.308 -0.527 -0.149 -0.158
0.188 -0.284 0.805 0.825 0.856 -0.884 0.840 -0.272 -0.456 -0.488 0.303 -0.438
GK(train) -0.825 -0.852 -0.815 0.952 -0.843 -0.903 -0.955 -0.972 0.970 -0.965
-0.645 -0.648 -0.669 0.611 -0.663 -0.518 -0.808 -0.840 0.591 -0.779 GK(test)
-0.285 -0.318 -0.247 0.629 -0.300 -0.031 -0.130 -0.123 0.101 -0.095 -0.579
-0.565 -0.569 0.412 -0.575 -0.276 -0.589 -0.658 0.470 -0.549 $\mathcal{KP}$
(Train) 0.482 0.418 0.449 -0.072 0.433 0.773 0.711 0.702 -0.714 0.745 0.769
0.769 0.782 -0.682 0.780 0.500 0.809 0.852 -0.755 0.777 $\mathcal{KP}$ (Test)
0.786 0.731 0.661 -0.669 0.721 0.825 0.870 0.864 -0.861 0.871 0.875 0.887
0.909 -0.884 0.899 0.482 0.816 0.863 -0.683 0.776

Table 2. Pearson’s linear correlation ($r$) scores computed from the metric
scores with respect to the ranking metrics on the standard KG embedding
datasets. The KG methods are evaluated after training. Green values are the
best.

##  6\. Results and Discussion

We conduct our experiments in response to the following research questions:
RQ1: Is there a correlation between the proposed metric and ranking metrics
for popular KG embedding methods? RQ2: Can the proposed metric be used to
perform early stopping during training? RQ3: What is the computational
efficiency of proposed metric wrt ranking metrics for KGE evaluation?

$\mathcal{KP}$ for faster prototyping of KGE methods: Our core hypothesis in
the paper is to develop an efficient alternative (proxy) to the ranking
metrics. Hence, for a fair evaluation, we use the triples in the test set for
computing $\mathcal{KP}$. Ideally, this should be able to simulate the
evaluation of the ranking metrics on the same (test) set. If true, there
exists a high correlation between the two measures, namely the $\mathcal{KP}$
and the ranking metrics. Table 2 shows the linear correlations between the
ranking metrics and our method & baselines. We report the linear(Pearson’s)
correlation because we would like a linear relationship between the proposed
measure and the ranking metric (for brevity, other correlations are in
appendix Tables 7, 8). This would help interpret whether an increase/decrease
in the measure would cause a corresponding increase/decrease in the ranking
metric that we wish to simulate. Specifically we train all the KG embedding
methods for a predefined number of epochs and evaluate the finally obtained
models to get the ranking metrics and $\mathcal{KP}$. The correlations are
then computed between $\mathcal{KP}$ and each of the ranking metrics. We
observe that $\mathcal{KP}$(test) configuration (triples are sampled from the
test set) achieves the highest correlation coefficient value among all the
existing geometric and kernel baseline methods in most cases. For instance, on
FB15K, $\mathcal{KP}$(test) reports high correlation value of 0.786 with
Hits@1, whereas best baseline for this dataset (AVL) has corresponding
correlation value as 0.339. Similarly for WN18RR, $\mathcal{KP}$(test) has
correlation value of 0.482 compared to AVL with -0.272 correlation with
Hits@1. Conicity and AVL that provide geometric perspective shows mostly low
positive correlation with ranking metrics whereas the Graph Kernel based
method shows highly negative correlations, making these methods unsuitable for
direct applicability. It indicates that the topology of the KG induced by the
learnt representations seems a good predictor of the performance on similar
data distributions with high correlation with ranking metric (answering RQ1).
Furthermore, the results also report a configuration $\mathcal{KP}$(train) in
which we compute $\mathcal{KP}$ on the triples of the train set and find the
correlation with the ranking metrics obtained from the test set. Here our
rationale is to study whether the proposed metric would be able to capture the
generalizability of the unseen test (real world) data that is of a similar
distribution as the training data. Initial results in Table 2 are promising
with high correlation of $\mathcal{KP}$(train) with ranking metric. Hence, it
may enable the use of $\mathcal{KP}$ in settings without test/validation data
while using the available (possibly limited) data for training, for example,
in few-shot scenarios. We leave this promising direction of research for
future.

###  6.1. $\mathcal{KP}$ as a criterion for early stopping

Does $\mathcal{KP}$ hold correlation while early stopping? To know when to
stop the training process to prevent overfitting, we must be able to estimate
the variance of the model. This is generally done by observing the
validation/test set error. Thus, to use a method as a criterion for early
stopping, it should be able to predict this generalization error. Table 2
explains that $\mathcal{KP}$(Train) can predict the generalizability of
methods on the last epoch, it remains to empirically verify that
$\mathcal{KP}$ also predicts the performance at every interval during the
training process. Hence, we study the correlations of the proposed method with
the ranking metrics for individual KG embedding methods in the intra-method
setting. Specifically, for a given method, we obtain the $\mathcal{KP}$ score
and the ranking metrics on the test set and compute the correlations at every
evaluation interval. Results in Table 3 suggest that $\mathcal{KP}$ has a
decent correlation in the intra-method setting. It indicates that
$\mathcal{KP}$ could be used in place of the ranking metrics for deciding a
criterion on early stopping if the score keeps persistently falling (answering
RQ2).

Datasets FB15K237 WN18RR KG methods r $\rho$ $\tau$ r $\rho$ $\tau$ TransE
0.955 0.861 0.709 0.876 0.833 0.722 TransH 0.688 0.570 0.409 0.864 0.717 0.555
TransR 0.975 0.942 0.811 0.954 0.967 0.889 Complex 0.938 0.788 0.610 0.833
0.933 0.833 RotatE 0.896 0.735 0.579 0.774 0.983 0.944 TuckER 0.906 0.676
0.527 0.352 0.25 0.167 ConvKB 0.086 0.012 0.007 0.276 0.569 0.422

Table 3. Correlation scores computed between $\mathcal{KP}$ and the ranking
metric(Hits@10) on the standard KG embedding datasets with the methods
evaluated at every interval as the training progresses. Here, r: Pearson
correlation co-efficient, $\rho$: Spearman’s correlation co-efficient, $\tau$:
Kendall’s Tau.

What is the relative error of early stopping between $\mathcal{KP}$ and
Ranking Metric? To further cross-validate our response to RQ2, we now compute
the absolute relative error between the ranking metrics of the best models
selected by $\mathcal{KP}$ and the expected ranking metrics. Ideally, we would
expect the performance of the model obtained using this process on unseen test
data(preferably of the same distribution) to be close to the best achievable
result, i.e., the relative error should be small. This is important as if we
were to use any metric for faster prototyping, it should also be a good
criterion for model selection(selecting a model with less generalization
error) and being efficient. Table 4 shows that the relative error is marginal,
of the order of $10^{-2}$, in most cases(with few exceptions), indicating that
$\mathcal{KP}$ could be used for early stopping. The deviation is higher for
some methods, such as ConvKB, which had convergence issues. We infer from
observed behavior that if the KG embedding method has not converged(to good
results), the correlation and, thus, the early stopping prediction may suffer.
Despite a few outliers, the promising results shall encourage the community to
research, develop, and use KGE benchmarking methods that are also
computationally efficient.

Datasets FB15K237 WN18RR KG methods hits@1 hits@10 MRR hits@1 hits@10 MRR
TransE 0.006 0.006 0.007 0.000 0.007 0.004 TransH 0.045 0.015 0.019 0.130
0.018 0023 TransR 0.074 0.045 0.053 0.242 0.062 0.016 Complex 0.001 0.002
0.003 0.317 0.021 0.028 RotatE 0.022 0.009 0.007 0.017 0.005 0.009 TuckER
0.008 0.006 0.002 0.293 0.022 0.101 ConvKB 0.000 0.043 0.043 0.659 0.453 0.569

Table 4. Early stopping using $\mathcal{KP}$. The values depict the absolute
relative error between the metrics of the best models selected using
$\mathcal{KP}$ and ranking metrics.  Figure 4. Figure shows a study on the
carbon footprint on WN18RR when using $\mathcal{KP}$ vs Hits@10. The x-axis
shows the the carbon footprint in g eq $CO_{2}$.

###  6.2. Timing analysis and carbon footprint

We now study the time taken for running the evaluation (including evaluation
at intervals) of the same methods as in section 6.1 on the standard datasets.
Table 5 shows the evaluation times (validation+test) and speedup for each
method on the respective datasets. The training time is constant for ranking
metric and $\mathcal{KP}$. In some cases (ConvKB), we observe $\mathcal{KP}$
achieves a speedup of up to 2576 times on model evaluation time drastically
reducing evaluation time from 18 hours to 27 seconds; the latter is even
roughly equal to the carbon footprint of making a cup of
coffee222https://tinyurl.com/4w2xmwry. Furthermore, Figure 4 illustrates the
carbon footprints (Wu et al., 2022; Patterson et al., 2022) of the overall
process (training + evaluation) for the methods when using $\mathcal{KP}$ vs
ranking metrics. Due to evaluation time drastically reduced by $\mathcal{KP}$,
it also reduces overall carbon footprints. The promising results validate our
attempt to develop alternative method for faster prototyping of KGE methods,
thus saving carbon footprint (answering RQ3).

###  6.3. Ablation Studies

We systematically provide several studies to support our evaluation and
characterize different properties of $\mathcal{KP}$.

Robustness to noise induced by sampling: An important property that makes
persistent homology worthwhile is its stability concerning perturbations of
the filtration function. This means that persistent homology is robust to
noise and encodes the intrinsic topological properties of the data (Hensel et
al., 2021). However, in our application of predicting the performance of KG
embedding methods, one source of noise is because of sampling the negative and
positive triples. It could cause perturbations in the graph topology due to
the addition and deletion of edges (cf., Figure 2). Therefore, we would like
the proposed metric to be stable concerning perturbations. To understand the
behavior of $\mathcal{KP}$ against this noise, we conduct a study by
incrementally adding samples to the graph and observing the mean and standard
deviation of the correlation at each stage. In an ideal case, assuming the KG
topology remains similar, the mean correlations should be in a narrow range
with slight standard deviations. We observe a similar effect in Figure 5 where
we report the mean correlation at various fractions of triples sampled, with
the standard deviation(error bands). Here, the mean correlation coefficients
are within the range of 0.06(0.04), and the average standard deviations are
about 0.02(0.02) for the FB15K237(WN18RR) dataset. This shows that
$\mathcal{KP}$ inherits the robustness of the topological data analysis
techniques, enabling linear time by sampling from the graph for dense KGs
while keeping it robust.

Metrics Hits@10 $\mathcal{KP}$ Speedup $\uparrow$ Dataset FB15K237 WN18RR
FB15K237 WN18RR FB15K237 WN18RR split val + test val + test val + test val +
test Avg Avg TransE 103.6 86.1 0.337 0.120 x 322.8 x 754.1 TransH 37.1 21.2
0.333 0.099 x 117.0 x 224.4 TransR 192.0 137.1 0.352 0.135 x 572.0 x 1066.4
Complex 136.1 151.4 0.340 0.142 x 420.1 x 1121.7 RotatE 174.2 155.2 0.359
0.142 x 509.5 x 1145.6 TuckER 94.8 22.1 0.332 0.098 x 300.0 x 241.9 ConvKB
1106.0 138.1 0.451 0.139 x 2576.6 x 1044.3

Table 5. Evaluation Metric Comparison wrt Computing Time (in minutes, for 100
epochs). Column 1 denotes popular KGE methods. Depicted values denote
evaluation(validation+test) time for computing a metric and corresponding
speedup using $\mathcal{KP}$. $\mathcal{KP}$ significantly reduces the
evaluation time (green).

Figure 5. Effect of sample size on the correlation coefficient between
$\mathcal{KP}$ and the ranking metrics on FB15K237 (left diagram) and WN18RR
datasets. The correlations for the different sampling fractions are
comparable. Also, the standard deviation is less, indicating the method’s
robustness due to changes in local topology while doing sampling.

Generalizability Study- Correlation with Stratified Ranking Metric: Mohamed et
al. (2020) proposed a new stratified metric (strat-metric) that can be tuned
to focus on the unpopular entities, unlike the standard ranking metrics, using
certain hyperparameters ($\beta_{e}\in(-1,1)$, $\beta_{r}\in(-1,1)$). Special
cases of these hyperparameters give the micro and macro ranking metrics. Goal
here is to study whether our method can predict strat-metric for the special
case of $\beta_{e}=1,\beta_{r}=0$, which estimates the performance for
unpopular(sparse) entities. Also, we aim to observe if $\mathcal{KP}$ holds a
correlation with variants of the ranking metric concerning its generalization
ability. The results (cf., Table 6) shows that $\mathcal{KP}$ has a good
correlation with each of the stratified ranking metrics which indicate
$\mathcal{KP}$ also takes into account the local geometry/topology (Adams and
Moy, 2021) of the sparse entities and relations.

Datasets FB15K237 WN18RR Metrics r $\rho$ $\tau$ r $\rho$ $\tau$ Strat-Hits@1
($\uparrow$) 0.965 0.857 0.714 0.513 0.482 0.411 Strat-Hits@3 ($\uparrow$)
0.898 0.821 0.619 0.691 0.714 0.524 Strat-Hits@10 ($\uparrow$) 0.871 0.821
0.619 0.870 0.750 0.619 Strat-MR ($\downarrow$) -0.813 -0.679 -0.524 -0.701
-0.821 -0.619 Strat-MRR ($\uparrow$) 0.806 0.679 0.524 0.658 0.714 0.524

Table 6. $\mathcal{KP}$ correlation with stratified ranking metrics as
proposed in (Mohamed et al., 2020).

###  6.4. Summary of Results and Open Directions

To sum up, following are key observations gleaning from empirical studies: 1)
$\mathcal{KP}$ shows high correlation with ranking metrics (Table 2) and its
stratified version (Table 6). It paves the way for the use of $\mathcal{KP}$
for faster prototyping of KGE methods. 2) $\mathcal{KP}$ holds a high
correlation at every interval during the training process (Table 3) with
marginal relative error; hence, it could be used for early stopping of a KGE
method. 3) $\mathcal{KP}$ inherits key properties of persistent homology,
i.e., it is robust to noise induced by sampling. 4) The overall carbon
footprints of the evaluation cycle is drastically reduced if $\mathcal{KP}$ is
preferred over ranking metrics.

What’s Next? We show that topological data analysis based on persistent
homology can act as a proxy for ranking metrics with conclusive empirical
evidence and supporting theoretical foundations. However, it is the first step
toward a more extensive research agenda. We believe substantial work is needed
collectively in the research community to develop strong foundations, solving
scaling issues (across embedding methods, datasets, KGs, etc.) until
persistent homology-based methods are widely adopted.

For example, there could be methods/datasets where the correlation turns out
to be a small positive value or even negative, in which case we may not be
able to use $\mathcal{KP}$ in the existing form to simulate the ranking
metrics for these methods/datasets. In those cases, some alteration may exist
for the same and seek further exploration similar to what stratified ranking
metric (Mohamed et al., 2020) does by fixing issues encountered in the ranking
metric. Furthermore, theorem 4.5 would be a key to understand error bounds
when interpreting limited performance (e.g., when the correlation is a small
positive). However, this does not limit the use of $\mathcal{KP}$ for KGE
methods as it captures and contrasts the topology of the positive and negative
sampled graphs learned from these methods, which could be a useful metric by
itself. In this paper, the emphasis is on the need for evaluation and
benchmarking methods that are computationally efficient rather than providing
an exhaustive one method fits all metric. We believe that there is much scope
for future research in this direction. Some promising directions include 1)
better sampling techniques(instead of the random sampling used in this paper),
2) rigorous theoretical analysis drawing the boundaries on the
abilities/limitations across settings (zero-shot, few-shot, etc.), 3) using KP
(and related metrics) in continuous spaces, that could be differentiable and
approximate the ranking metrics, in the optimization process of KGE methods.

##  7\. Conclusion

We propose Knowledge Persistence ($\mathcal{KP}$), first work that uses
techniques from topological data analysis, as a predictor of the ranking
metrics to efficiently evaluate the performance of KG embedding approaches.
With theoretical and empirical evidences, our work brings efficiency at center
stage in the evaluation of KG embedding methods along with traditional way of
reporting their performance. Finally, with efficiency as crucial criteria for
evaluation, we hope KGE research becomes more inclusive and accessible to the
broader research community with limited computing resources.

Acknowledgment This work was partly supported by JSPS KAKENHI Grant Number
JP21K21280.

## References

  * (1)
  * Adams and Moy (2021) Henry Adams and Michael Moy. 2021.  Topology Applied to Machine Learning: From Global to Local.  _Frontiers in Artificial Intelligence_ 4 (2021), 54.
  * Ali et al. (2021) Mehdi Ali, Max Berrendorf, Charles Tapley Hoyt, Laurent Vermue, Mikhail Galkin, Sahand Sharifzadeh, Asja Fischer, Volker Tresp, and Jens Lehmann. 2021.  Bringing light into the dark: A large-scale evaluation of knowledge graph embedding models under a unified framework.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ (2021).
  * Balažević et al. (2019) Ivana Balažević, Carl Allen, and Timothy Hospedales. 2019\.  TuckER: Tensor Factorization for Knowledge Graph Completion. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_. 5185–5194.
  * Bansal et al. (2020) Iti Bansal, Sudhanshu Tiwari, and Carlos R Rivero. 2020\.  The impact of negative triple generation strategies and anomalies on knowledge graph completion. In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_. 45–54.
  * Bastos et al. (2021) Anson Bastos, Kuldeep Singh, Abhishek Nadgeri, Saeedeh Shekarpour, Isaiah Onando Mulang, and Johannes Hoffart. 2021.  Hopfe: Knowledge graph representation learning using inverse hopf fibrations. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_. 89–99.
  * Berrendorf et al. (2020) Max Berrendorf, Evgeniy Faerman, Laurent Vermue, and Volker Tresp. 2020.  Interpretable and Fair Comparison of Link Prediction or Entity Alignment Methods. In _2020 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT)_. IEEE, 371–374.
  * Bollacker et al. (2007) Kurt D. Bollacker, Robert P. Cook, and Patrick Tufts. 2007\.  Freebase: A Shared Database of Structured General Human Knowledge. In _AAAI_.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013\.  Translating embeddings for modeling multi-relational data. In _NeurlPS_. 1–9.
  * Bordes et al. (2011) Antoine Bordes, Jason Weston, Ronan Collobert, and Yoshua Bengio. 2011.  Learning structured embeddings of knowledge bases. In _Twenty-fifth AAAI conference on artificial intelligence_.
  * Borgwardt and Kriegel (2005) Karsten M Borgwardt and Hans-Peter Kriegel. 2005.  Shortest-path kernels on graphs. In _Fifth IEEE international conference on data mining (ICDM’05)_. IEEE, 8–pp.
  * Borgwardt et al. (2007) Karsten M. Borgwardt, Tobias Petri, S. V. N. Vishwanathan, and Hans-Peter Kriegel. 2007\.  An Efficient Sampling Scheme For Comparison of Large Graphs. In _Mining and Learning with Graphs, MLG_.
  * Broder et al. (2003) Andrei Z Broder, Marc Najork, and Janet L Wiener. 2003\.  Efficient URL caching for world wide web crawling. In _Proceedings of the 12th international conference on World Wide Web_. 679–689.
  * Carrière et al. (2017) Mathieu Carrière, Marco Cuturi, and Steve Oudot. 2017\.  Sliced Wasserstein Kernel for Persistence Diagrams. In _Proceedings of the 34th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research)_ , Vol. 70. PMLR, 664–673.
  * Chok (2010) Nian Shong Chok. 2010\.  _Pearson’s versus Spearman’s and Kendall’s correlation coefficients for continuous data_.  Ph.D. Dissertation. University of Pittsburgh.
  * Edelsbrunner et al. (2000) Herbert Edelsbrunner, David Letscher, and Afra Zomorodian. 2000\.  Topological persistence and simplification. In _Proceedings 41st annual symposium on foundations of computer science_. IEEE, 454–463.
  * Fasy et al. (2020) Brittany Fasy, Yu Qin, Brian Summa, and Carola Wenk. 2020\.  Comparing Distance Metrics on Vectorized Persistence Summaries. In _NeurIPS 2020 Workshop on Topological Data Analysis and Beyond_.
  * Galárraga et al. (2014) Luis Galárraga, Katja Hose, and Ralf Schenkel. 2014\.  Partout: a distributed engine for efficient RDF processing. In _Proceedings of the 23rd International Conference on World Wide Web_. 267–268.
  * Gesese et al. (2019) Genet Asefa Gesese, Russa Biswas, Mehwish Alam, and Harald Sack. 2019.  A survey on knowledge graph embeddings with literals: Which model links better literal-ly?  _Semantic Web_ Preprint (2019), 1–31.
  * Hensel et al. (2021) Felix Hensel, Michael Moor, and Bastian Rieck. 2021\.  A survey of topological machine learning methods.  _Frontiers in Artificial Intelligence_ 4 (2021), 52.
  * Jain et al. (2021) Nitisha Jain, Jan-Christoph Kalo, Wolf-Tilo Balke, and Ralf Krestel. 2021.  Do Embeddings Actually Capture Knowledge Graph Semantics?. In _European Semantic Web Conference_. Springer, 143–159.
  * Jain et al. (2020) Prachi Jain, Sushant Rathi, Soumen Chakrabarti, et al. 2020\.  Knowledge base completion: Baseline strikes back (again).  _arXiv preprint arXiv:2005.00804_ (2020).
  * Ji et al. (2021) Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and Philip S Yu. 2021.  A survey on knowledge graphs: Representation, acquisition and applications.  _EEE Transactions on Neural Networks and Learning Systems_ (2021).
  * Kadlec et al. (2017) Rudolf Kadlec, Ondřej Bajgar, and Jan Kleindienst. 2017.  Knowledge Base Completion: Baselines Strike Back. In _Proceedings of the 2nd Workshop on Representation Learning for NLP_. 69–74.
  * Li et al. (2021) Zelong Li, Jianchao Ji, Zuohui Fu, Yingqiang Ge, Shuyuan Xu, Chong Chen, and Yongfeng Zhang. 2021.  Efficient non-sampling knowledge graph embedding. In _Proceedings of the Web Conference 2021_. 1727–1736.
  * Lim et al. (2003) Lipyeow Lim, Min Wang, Sriram Padmanabhan, Jeffrey Scott Vitter, and Ramesh Agarwal. 2003.  Dynamic maintenance of web indexes using landmarks. In _Proceedings of the 12th international conference on World Wide Web_. 102–111.
  * Lin et al. (2015) Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. 2015.  Learning entity and relation embeddings for knowledge graph completion. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 29.
  * Miller (1995) George A Miller. 1995\.  WordNet: a lexical database for English.  _Commun. ACM_ 38, 11 (1995), 39–41.
  * Mohamed et al. (2020) Aisha Mohamed, Shameem Parambath, Zoi Kaoudi, and Ashraf Aboulnaga. 2020.  Popularity agnostic evaluation of knowledge graph embeddings. In _Conference on Uncertainty in Artificial Intelligence_. PMLR, 1059–1068.
  * Moor et al. (2020) Michael Moor, Max Horn, Bastian Rieck, and Karsten Borgwardt. 2020\.  Topological autoencoders. In _International conference on machine learning_. PMLR, 7045–7054.
  * Nadjahi et al. (2021) Kimia Nadjahi, Alain Durmus, Pierre E Jacob, Roland Badeau, and Umut Simsekli. 2021.  Fast Approximation of the Sliced-Wasserstein Distance Using Concentration of Random Projections.  _Advances in Neural Information Processing Systems_ 34 (2021).
  * Nayyeri et al. (2019) Mojtaba Nayyeri, Chengjin Xu, Yadollah Yaghoobzadeh, Hamed Shariat Yazdi, and Jens Lehmann. 2019\.  Toward Understanding The Effect Of Loss function On Then Performance Of Knowledge Graph Embedding.  _arXiv preprint arXiv:1909.00519_ (2019).
  * Nguyen et al. (2018) Tu Dinh Nguyen, Dat Quoc Nguyen, Dinh Phung, et al. 2018\.  A Novel Embedding Model for Knowledge Base Completion Based on Convolutional Neural Network. In _NAACL_. 327–333.
  * Patterson et al. (2022) David Patterson, Joseph Gonzalez, Urs Hölzle, Quoc Le, Chen Liang, Lluis-Miquel Munguia, Daniel Rothchild, David So, Maud Texier, and Jeff Dean. 2022\.  The Carbon Footprint of Machine Learning Training Will Plateau, Then Shrink.  _arXiv preprint arXiv:2204.05149_ (2022).
  * Peng et al. (2021) Xutan Peng, Guanyi Chen, Chenghua Lin, and Mark Stevenson. 2021\.  Highly Efficient Knowledge Graph Embedding Learning with Orthogonal Procrustes Analysis. In _NAACL_. 2364–2375.
  * Pezeshkpour et al. (2020) Pouya Pezeshkpour, Yifan Tian, and Sameer Singh. 2020\.  Revisiting evaluation of knowledge base completion models. In _Automated Knowledge Base Construction_.
  * Rieck et al. (2018) Bastian Rieck, Matteo Togninalli, Christian Bock, Michael Moor, Max Horn, Thomas Gumbsch, and Karsten Borgwardt. 2018.  Neural Persistence: A Complexity Measure for Deep Neural Networks Using Algebraic Topology. In _International Conference on Learning Representations_.
  * Rim et al. (2021) Wiem Ben Rim, Carolin Lawrence, Kiril Gashteovski, Mathias Niepert, and Naoaki Okazaki. 2021\.  Behavioral Testing of Knowledge Graph Embedding Models for Link Prediction. In _3rd Conference on Automated Knowledge Base Construction_.
  * Safavi and Koutra (2020) Tara Safavi and Danai Koutra. 2020.  CoDEx: A Comprehensive Knowledge Graph Completion Benchmark. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. 8328–8350.
  * Sakia (1992) Remi M Sakia. 1992\.  The Box-Cox transformation technique: a review.  _Journal of the Royal Statistical Society: Series D (The Statistician)_ 41, 2 (1992), 169–178.
  * Sharma et al. (2018) Aditya Sharma, Partha Talukdar, et al. 2018\.  Towards understanding the geometry of knowledge graph embeddings. In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. 122–131.
  * Singh et al. (2018) Kuldeep Singh, Arun Sethupat Radhakrishna, Andreas Both, Saeedeh Shekarpour, Ioanna Lytra, Ricardo Usbeck, Akhilesh Vyas, Akmal Khikmatullaev, Dharmen Punjani, Christoph Lange, et al. 2018\.  Why reinvent the wheel: Let’s build question answering systems together. In _Proceedings of the 2018 world wide web conference_. 1247–1256.
  * Spearman (1907) C. Spearman. 1907\.  Demonstration of Formulæ for True Measurement of Correlation.  _The American Journal of Psychology_ 18, 2 (1907), 161–169.  http://www.jstor.org/stable/1412408
  * Speranskaya et al. (2020) Marina Speranskaya, Martin Schmitt, and Benjamin Roth. 2020\.  Ranking vs. Classifying: Measuring Knowledge Base Completion Quality. In _Automated Knowledge Base Construction_.
  * Sun et al. (2018) Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2018\.  RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space. In _International Conference on Learning Representations_.
  * Sun et al. (2020) Zhiqing Sun, Shikhar Vashishth, Soumya Sanyal, Partha Talukdar, and Yiming Yang. 2020\.  A Re-evaluation of Knowledge Graph Completion Methods. In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. 5516–5522.
  * Tabacof and Costabello (2019) Pedro Tabacof and Luca Costabello. 2019.  Probability Calibration for Knowledge Graph Embedding Models. In _International Conference on Learning Representations_.
  * Tiwari et al. (2021) Sudhanshu Tiwari, Iti Bansal, and Carlos R Rivero. 2021\.  Revisiting the evaluation protocol of knowledge graph completion methods for link prediction. In _Proceedings of the Web Conference 2021_. 809–820.
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016.  Complex embeddings for simple link prediction. In _International Conference on Machine Learning_. PMLR, 2071–2080.
  * Tu et al. (2019) Ke Tu, Jianxin Ma, Peng Cui, Jian Pei, and Wenwu Zhu. 2019.  Autone: Hyperparameter optimization for massive network embedding. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 216–225.
  * Turkeš et al. (2022) Renata Turkeš, Guido Montúfar, and Nina Otter. 2022\.  On the effectiveness of persistent homology.  https://doi.org/10.48550/ARXIV.2206.10551
  * Villani (2009) C. Villani. 2009\.  Optimal transport.  _Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]_ 338 (2009).
  * Wang et al. (2021d) Haoyu Wang, Yaqing Wang, Defu Lian, and Jing Gao. 2021d.  A lightweight knowledge graph embedding framework for efficient inference and storage. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_. 1909–1918.
  * Wang et al. (2021c) Kai Wang, Yu Liu, Qian Ma, and Quan Z Sheng. 2021c.  Mulde: Multi-teacher knowledge distillation for low-dimensional knowledge graph embeddings. In _Proceedings of the Web Conference 2021_. 1716–1726.
  * Wang et al. (2022) Kai Wang, Yu Liu, and Quan Z Sheng. 2022.  Swift and Sure: Hardness-aware Contrastive Learning for Low-dimensional Knowledge Graph Embeddings. In _Proceedings of the ACM Web Conference 2022_. 838–849.
  * Wang et al. (2017) Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. 2017\.  Knowledge graph embedding: A survey of approaches and applications.  _IEEE Transactions on Knowledge and Data Engineering_ 29, 12 (2017), 2724–2743.
  * Wang et al. (2021a) Xin Wang, Shuyi Fan, Kun Kuang, and Wenwu Zhu. 2021a.  Explainable automated graph representation learning with hyperparameter importance. In _International Conference on Machine Learning_. PMLR, 10727–10737.
  * Wang et al. (2021b) Xiaozhi Wang, Tianyu Gao, Zhaocheng Zhu, Zhengyan Zhang, Zhiyuan Liu, Juanzi Li, and Jian Tang. 2021b.  KEPLER: A unified model for knowledge embedding and pre-trained language representation.  _Transactions of the Association for Computational Linguistics_ 9 (2021), 176–194.
  * Wang et al. (2014) Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. 2014\.  Knowledge graph embedding by translating on hyperplanes. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 28.
  * Wasserman (2018) Larry Wasserman. 2018\.  Topological data analysis.  _Annual Review of Statistics and Its Application_ 5 (2018), 501–532.
  * Wu et al. (2022) Carole-Jean Wu, Ramya Raghavendra, Udit Gupta, Bilge Acun, Newsha Ardalani, Kiwan Maeng, Gloria Chang, Fiona Aga, Jinshi Huang, Charles Bai, et al. 2022\.  Sustainable ai: Environmental implications, challenges and opportunities.  _Proceedings of Machine Learning and Systems_ 4 (2022), 795–813.
  * Yang et al. (2015) Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2015.  Embedding Entities and Relations for Learning and Inference in Knowledge Bases. In _3rd International Conference on Learning Representations, ICLR_.
  * Yu et al. (2021) Shih-Yuan Yu, Sujit Rokka Chhetri, Arquimedes Canedo, Palash Goyal, and Mohammad Abdullah Al Faruque. 2021\.  Pykg2vec: A Python Library for Knowledge Graph Embedding.  _J. Mach. Learn. Res._ 22 (2021), 16–1.
  * Zhang et al. (2021) Yufeng Zhang, Weiqing Wang, Wei Chen, Jiajie Xu, An Liu, and Lei Zhao. 2021\.  Meta-Learning Based Hyper-Relation Feature Modeling for Out-of-Knowledge-Base Embedding. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_. 2637–2646.
  * Zhang et al. (2022) Yongqi Zhang, Zhanke Zhou, Quanming Yao, and Yong Li. 2022\.  KGTuner: Efficient Hyper-parameter Search for Knowledge Graph Learning.  _CoRR_ abs/2205.02460 (2022).
  * Zomorodian and Carlsson (2005) Afra Zomorodian and Gunnar Carlsson. 2005.  Computing persistent homology.  _Discrete & Computational Geometry_ 33, 2 (2005), 249–274.

##  8\. appendix

Metrics FB15K FB15K237 WN18 WN18RR Hits1($\uparrow$) Hits3($\uparrow$)
Hits10($\uparrow$) MR($\downarrow$) MRR($\uparrow$) Hits1($\uparrow$)
Hits3($\uparrow$) Hits10($\uparrow$) MR($\downarrow$) MRR($\uparrow$)
Hits1($\uparrow$) Hits3($\uparrow$) Hits10($\uparrow$) MR($\downarrow$)
MRR($\uparrow$) Hits1($\uparrow$) Hits3($\uparrow$) Hits10($\uparrow$)
MR($\downarrow$) MRR($\uparrow$) Conicity 0.071 -0.071 0.000 -0.036 -0.214
0.393 0.250 -0.071 0.036 0.250 0.600 0.600 0.600 -0.143 0.600 -0.393 -0.607
-0.607 0.357 -0.607 AVL 0.607 0.214 0.250 -0.679 0.179 -0.107 -0.321 -0.429
0.393 -0.250 0.886 0.886 0.886 -0.771 0.886 0.321 -0.143 -0.464 0.607 -0.143
Graph Kernel (Train) -0.536 -0.321 -0.357 0.964 -0.393 -0.929 -0.714 -0.607
0.643 -0.821 -0.943 -0.943 -0.943 0.714 -0.943 -0.357 -0.786 -0.607 0.571
-0.786 Graph Kernel (Test) -0.107 0.107 0.000 0.893 0.036 -0.429 -0.607 -0.679
0.464 -0.607 -0.657 -0.657 -0.657 0.086 -0.657 -0.393 -0.714 -0.821 0.786
-0.714 $\mathcal{KP}$ (Train) 0.214 0.536 0.750 0.000 0.607 0.893 0.750 0.643
-0.679 0.786 0.829 0.829 0.829 -0.600 0.829 0.286 0.714 0.643 -0.750 0.714
$\mathcal{KP}$ (Test) 0.964 0.750 0.750 -0.536 0.714 0.714 0.821 0.857 -0.750
0.857 0.943 0.943 0.943 -0.829 0.943 0.286 0.714 0.643 -0.643 0.714

Table 7. Spearman’s ranked correlation ($\rho$) scores computed from the
metric scores with respect to the ranking metrics on the standard KG embedding
datasets. The KG methods are evaluated after training.

Metrics FB15K FB15K237 WN18 WN18RR Hits1($\uparrow$) Hits3($\uparrow$)
Hits10($\uparrow$) MR($\downarrow$) MRR($\uparrow$) Hits1($\uparrow$)
Hits3($\uparrow$) Hits10($\uparrow$) MR($\downarrow$) MRR($\uparrow$)
Hits1($\uparrow$) Hits3($\uparrow$) Hits10($\uparrow$) MR($\downarrow$)
MRR($\uparrow$) Hits1($\uparrow$) Hits3($\uparrow$) Hits10($\uparrow$)
MR($\downarrow$) MRR($\uparrow$) Conicity 0.048 -0.048 -0.048 0.048 -0.143
0.238 0.143 -0.048 -0.048 0.143 0.467 0.467 0.467 -0.333 0.467 -0.238 -0.333
-0.429 0.238 -0.333 AVL 0.429 0.143 0.143 -0.524 0.048 -0.143 -0.238 -0.429
0.333 -0.238 0.733 0.733 0.733 -0.600 0.733 0.238 -0.048 -0.333 0.524 -0.048
Graph Kernel (Train) -0.429 -0.143 -0.143 0.905 -0.238 -0.810 -0.524 -0.333
0.429 -0.714 -0.867 -0.867 -0.867 0.467 -0.867 -0.333 -0.619 -0.333 0.333
-0.619 Graph Kernel (Test) -0.143 0.143 -0.048 0.810 0.048 -0.429 -0.524
-0.524 0.429 -0.524 -0.600 -0.600 -0.600 0.200 -0.600 -0.238 -0.524 -0.619
0.619 -0.524 $\mathcal{KP}$ (Train) 0.143 0.429 0.619 -0.048 0.524 0.714 0.619
0.429 -0.524 0.619 0.600 0.600 0.600 -0.467 0.600 0.238 0.524 0.429 -0.619
0.524 $\mathcal{KP}$ (Test) 0.905 0.619 0.619 -0.429 0.524 0.619 0.714 0.714
-0.619 0.714 0.867 0.867 0.867 -0.733 0.867 0.238 0.524 0.429 -0.429 0.524

Table 8. Kendall’s tau ($\tau$) scores computed from the metric scores with
respect to the ranking metrics on the standard KG embedding datasets. The KG
methods are evaluated after training.

Figure 6. Study on the carbon footprint of the evaluation phase of the KGE
methods on YAGO3-10 when using $\mathcal{KP}$ vs Hits@10. The x-axis shows the
the carbon footprint in g eq $CO_{2}$ in log scale. Figure 7. Study on the
carbon footprint of the evaluation phase of the KGE methods on Wikidata when
using $\mathcal{KP}$ vs Hits@10. The x-axis shows the the carbon footprint in
g eq $CO_{2}$ in log scale.

###  8.1. Extended Evaluation

Effect of $\mathcal{KP}$ on Efficient KGE Methods Evaluation: The research
community has recently proposed several KGE methods to improve training
efficiency (Wang et al., 2021d, 2022; Peng et al., 2021). Our idea in this
experiment is to perceive if efficient KGE methods improve their overall
carbon footprint using $\mathcal{KP}$. For the same, we selected state-of-the-
art efficient KGE methods: Procrustes (Peng et al., 2021) and HalE (Wang et
al., 2022). Figure 8 illustrates that using $\mathcal{KP}$ for evaluation
drastically reduces the carbon footprints of already efficient KGE methods.
For instance, the carbon footprint of HalE is reduced from 110g (using
hits@10) to 20g of CO2 (using $\mathcal{KP}$).

Figure 8. Study on efficient KGE methods and their the carbon footprint on
WN18RR when using $\mathcal{KP}$ vs Hits@10. The x-axis shows the the carbon
footprint in g eq $CO_{2}$.

Robustness and Efficiency on large KGs: This ablation study aims to gauge the
correlation behavior of $\mathcal{KP}$ and ranking metric on a large-scale KG.
For the experiment, we use Yago3-10 dataset. A key reason to select the Yago-
based dataset is that besides being large-scale, it has rich semantics.
Results in Table 9 illustrate $\mathcal{KP}$ shows a stable and high
correlation with the ranking metric, confirming the robustness of
$\mathcal{KP}$. We show carbon footprint results in Figure 6 for the yago
dataset. Further we also study the efficiency of $\mathcal{KP}$ on the
wikidata dataset (Wang et al., 2021b) in Figure 7 which reaffirms that
$\mathcal{KP}$ maintains its efficiency on large scale datasets.

Efficiency comparison of Sliced Wasserstein vs Wasserstein as distance metric
in $\mathcal{KP}$: In this study we empirically provide a rationale for using
sliced wasserstein as a distance metric over the wasserstein distance in
$\mathcal{KP}$. The results are in table 10. We see that $\mathcal{KP}$ using
sliced wasserstein distance provides a significant computational advantage
over wasserstein distance, while having a good performance as seen in the
previous experiments. Thus we need an efficient approximation such as the
sliced wasserstein distance as the distance metric in place of wasserstein
distance in $\mathcal{KP}$.

Metrics Hits@1($\uparrow$) Hits@3($\uparrow$) Hits@10($\uparrow$)
MR($\downarrow$) MRR($\uparrow$) r 0.657 0.594 0.414 -0.920 0.572 $\rho$ 0.679
0.679 0.5 -0.714 0.643 $\tau$ 0.524 0.524 0.333 -0.524 0.429

Table 9. $\mathcal{KP}$ correlations on the YAGO dataset.

Metrics $\mathcal{KP}$(W) $\mathcal{KP}$(SW) Speedup $\uparrow$ Dataset
FB15K237 WN18RR FB15K237 WN18RR FB15K237 WN18RR split val + test val + test
val + test val + test Avg Avg TransE 1136.766 9.655 0.321 0.114 x 3540.3 x
84.6 TransH 2943.869 7.549 0.317 0.095 x 9278.5 x 79.8 TransR 1734.576 4.423
0.336 0.129 x 5168.3 x 34.4 Complex 1054.721 13.089 0.324 0.135 x 3255.3 x
97.0 RotatE 865.417 12.783 0.342 0.136 x 2531.1 x 94.3 TuckER 1021.649 3.840
0.316 0.098 x 3230.0 x 39.1 ConvKB 719.310 5.154 0.429 0.132 x 1675.7 x 39.0

Table 10. Evaluation Metric Comparison wrt Computing Time (in minutes, for 100
epochs). Column 1 denotes popular KGE methods. Depicted values denote
evaluation(validation+test) time for computing a metric and corresponding
speedup using $\mathcal{KP}(SW)$. $\mathcal{KP}(SW)$ with sliced wasserstein
as the distance metric significantly reduces the evaluation time (green) in
comparison with $\mathcal{KP}(W)$ which uses the wasserstein distance.

###  8.2. Theoretical Proof Sketches

We work under the following considerations: As the KGE method converges the
mean statistic($m_{\nu}$) of the scores of the positive triples consistently
lies on one side of the half plane formed by the mean statistic($m_{\mu}$) of
the negative triples, irrespective of the data distribution. The detail proofs
are here.

###### Lemma 8.0.

$\mathcal{KP}$ has a monotone increasing correspondence with the Proxy of the
Expected Ranking Metrics(PERM) under the above stated considerations as
$m_{\nu}$ deviates from $m_{\mu}$

###### Proof Sketch.

Considering the 0-dimensional PD as used by $\mathcal{KP}$ and a normal
distribution for the edge weights (can be extended to other distributions
using techniques like (Sakia, 1992)) of the graph(scores of the triples), we
have univariate gaussian measures (Sharma et al., 2018) $\mu$ and $\nu$ for
the positive and negative distributions respectively. Denote by $m_{\mu}$ and
$m_{\nu}$ the means of the distributions $\mu$ and $\nu$ respectively and by
$\Sigma_{\mu}$, $\Sigma_{\nu}$ the respective covariance matrices.

(2) $W_{2}^{2}(\mu,\nu)=\norm{\mu-\nu}^{2}+B(\Sigma_{\mu},\Sigma_{\nu})^{2}$

where
$B(\Sigma_{\mu},\Sigma_{\nu})^{2}=tr(\Sigma_{\mu}+\Sigma_{\nu}-2(\Sigma_{\mu}^{\frac{1}{2}}\Sigma_{\nu}\Sigma_{\mu}^{\frac{1}{2}})^{\frac{1}{2}})$.

Next we see how that changing the means of the distribution(and also variance)
changes PERM and $\mathcal{KP}$. We can show that,

$\displaystyle P$
$\displaystyle=\int_{x=-\infty}^{x=\infty}D^{+}(x)\left(\int_{y=x}^{y=\infty}D^{-}(x)dy\right)dx$
$\displaystyle\frac{\partial P}{\partial m_{\nu}}$
$\displaystyle=\int_{x=-\infty}^{x=\infty}D^{+}(x)\left(\int_{y=x}^{y=\infty}\frac{\partial
D^{-}(x)}{\partial m_{\nu}}dy\right)dx$ $\displaystyle\geq 0$
$\displaystyle\frac{\partial P}{\partial\Sigma_{\nu}}$
$\displaystyle=\int_{x=-\infty}^{x=\infty}D^{+}(x)\left(\int_{y=x}^{y=\infty}\frac{\partial
D^{-}(y)}{\partial\Sigma_{\nu}}dy\right)dx$ $\displaystyle\leq 0$
$\displaystyle\frac{\partial P}{\partial\Sigma_{\mu}}$
$\displaystyle=\int_{x=-\infty}^{x=\infty}\frac{\partial
D^{+}(x)}{\partial\Sigma_{\nu}}\left(\int_{y=x}^{y=\infty}D^{-}(y)dy\right)dx$

Since $\mathcal{KP}$ is the (sliced) wasserstein distance between PDs we can
show the respective gradients are as below,

$\displaystyle\frac{\partial W_{2}^{2}(\mu,\nu)}{\partial m_{\nu}}$
$\displaystyle=2|m_{\mu}-m_{\nu}|$ $\displaystyle\geq 0$
$\displaystyle\frac{\partial W_{2}^{2}(\mu,\nu)}{\partial\Sigma_{\nu}}$
$\displaystyle=I-\Sigma_{\mu}^{\frac{1}{2}}(\Sigma_{\mu}^{\frac{1}{2}}\Sigma_{\nu}\Sigma_{\mu}^{\frac{1}{2}})^{\frac{-1}{2}}\Sigma_{\mu}^{\frac{1}{2}}$

As the generating process of the scores changes the gradient of PERM along the
direction $(dm_{\nu},d\sigma_{\mu},d\sigma_{\nu})$ can be shown to be the
following

$\displaystyle\left<\left(dm_{\nu},d\sigma,d\sigma\right),\left(\frac{\partial
PERM}{\partial m_{\nu}},\frac{\partial
PERM}{\partial\Sigma_{\mu}},\frac{\partial
PERM}{\partial\Sigma_{\nu}}\right)\right>$ $\displaystyle\geq 0$

Similarly the gradient of $\mathcal{KP}$ along the direction
$(dm_{\mu},d\sigma_{\mu},d\sigma_{\nu})$ is

$\displaystyle\left<(dm_{\nu},d\sigma,d\sigma),(\frac{\partial
W_{2}^{2}(\mu,\nu)}{\partial m_{\nu}},\frac{\partial
W_{2}^{2}(\mu,\nu)}{\partial\Sigma_{\mu}},\frac{\partial
W_{2}^{2}(\mu,\nu)}{\partial\Sigma_{\nu}})\right>$ $\displaystyle\geq 0$

Since both PERM and and $\mathcal{KP}$ vary in the same manner as the
distribution changes, the two have a one-one correspondence (Spearman, 1907).

∎

The above lemma shows that there is a one-one correspondence between
$\mathcal{KP}$ and PERM and by definition PERM has a one-one correspondence
with the ranking metrics. Therefore, the next theorem follows as a natural
consequence

###### Theorem 8.2.

$\mathcal{KP}$ has a one-one correspondence with the Ranking Metrics under the
above stated considerations

###### Theorem 8.3.

Under the considerations of theorem 8.2, the relative change in $\mathcal{KP}$
on addition of random noise to the scores is bounded by a function of the
original and noise-induced covariance matrix as
$\frac{\Delta\mathcal{KP}}{\mathcal{KP}}\leq
max((1-|\Sigma_{\mu_{1}}^{+1}\Sigma_{\mu_{2}}^{-1}|^{\frac{3}{2}}),(1-|\Sigma_{\nu_{1}}^{+1}\Sigma_{\nu_{2}}^{-1}|^{\frac{3}{2}}))$,
where $\Sigma_{\mu_{1}}$ and $\Sigma_{\nu_{1}}$ are the covariance matrices of
the positive and negative triples’ scores respectively and $\Sigma_{\mu_{2}}$
and $\Sigma_{\nu_{2}}$ are that of the corrupted scores.

###### Proof Sketch.

Consider a zero mean random noise to simulate the process of varying the
distribution of the scores of the KGE method. Let $m_{\mu_{1}}$ and
$m_{\nu_{1}}$ be the means of the positive and negative triples’ scores of the
original method and $\Sigma_{\mu_{1}}$, $\Sigma_{\nu_{1}}$ be the respective
covariance matrices. Let $m_{\mu_{2}}$ and $m_{\nu_{2}}$ be the means of the
positive and negative triples’ scores of the corrupted method and
$\Sigma_{\mu_{2}}$, $\Sigma_{\nu_{2}}$ be the respective covariance matrices.
Considering the kantorovich duality (Villani, 2009) and taking the difference
between the two measures we have

$\displaystyle\mathcal{KP}_{1}-\mathcal{KP}_{2}$
$\displaystyle=\underset{\gamma_{1}\in\Pi(x,y)}{inf}\int_{\gamma_{1}}Distance(x,y)d\gamma_{1}(x,y)$
$\displaystyle-\underset{\gamma_{2}\in\Pi(x,y)}{inf}\int_{\gamma_{2}}Distance(x,y)d\gamma_{2}(x,y)$
$\displaystyle\leq\underset{\Phi,\Psi}{sup}\int_{x}\Phi(x)d\mu_{1}(x)+\int_{y}\Psi(y)d\nu_{1}(y)$
$\displaystyle-\int_{x}\Phi(x)d\mu_{2}(x)-\int_{y}\Psi(y)d\nu_{2}(y)$
$\displaystyle\leq\underset{\Phi,\Psi}{sup}\int_{x}\Phi(x)(d\mu_{1}(x)-d\mu_{2}(x))+\int_{y}\Psi(y)(d\nu_{1}(y)-d\nu_{2}(y))$

Now by definition of the measure $\mu_{1}$ we have

$\displaystyle\frac{\partial\mu_{1}}{\partial x}$
$\displaystyle=-\mu_{1}\Sigma_{\mu_{1}}^{-1}(x-m_{\mu_{1}})$ $\displaystyle
d\mu_{1}(x_{i})$
$\displaystyle=-(\mu_{1}\Sigma_{\mu_{1}}^{-1}(x-m_{\mu_{1}}))[i]dx_{i}$
$\displaystyle\therefore d\mu_{1}(x)$
$\displaystyle=det(diag(-\mu_{1}\Sigma_{\mu_{1}}^{-1}(x-m_{\mu_{1}})))dx$

From the above results we can show the following

$\displaystyle\mathcal{KP}_{1}-\mathcal{KP}_{2}$ $\displaystyle\leq
max((1-det(\Sigma_{\mu_{1}}\Sigma_{\mu_{2}}^{-1})^{\frac{n}{2}+1}),(1-det(\Sigma_{\nu_{1}}\Sigma_{\nu_{2}}^{-1})^{\frac{n}{2}+1}))\mathcal{KP}_{1}$
$\displaystyle\therefore\frac{\Delta\mathcal{KP}}{\mathcal{KP}}\leq
max\left(\left(1-det(\Sigma_{\mu_{1}}\Sigma_{\mu_{2}}^{-1})^{\frac{n}{2}+1}\right),\left(1-det(\Sigma_{\nu_{1}}\Sigma_{\nu_{2}}^{-1})^{\frac{n}{2}+1}\right)\right)$

In our case as we work in the univariate setting $n=1$ and thus we have
$\frac{\Delta\mathcal{KP}}{\mathcal{KP}}\leq
max\left(\left(1-det(\Sigma_{\mu_{1}}\Sigma_{\mu_{2}}^{-1})^{\frac{3}{2}}\right),\left(1-det(\Sigma_{\nu_{1}}\Sigma_{\nu_{2}}^{-1})^{\frac{3}{2}}\right)\right)$,
as required.

∎

Theorem 8.3 shows that as noise is induced gradually, the $\mathcal{KP}$ value
changes in a bounded manner as desired.