Year: 2019

Abstract:
We study theoretical properties of embedding methods for knowledge graph completion under the “missing completely at random” assumption. We prove generalization error bounds for this setting. Even though the missing completely at random setting may seem naive, it is actually how knowledge graph embedding methods are typically benchmarked in the literature. Our results provide, to a certain extent, an explanation for why knowledge graph embedding methods work (as much as classical learning theory results provide explanations for classical learning from i.i.d. data).

text: We study theoretical properties of embedding methods for knowledge graph completion under the “missing completely at random” assumption. We prove generalization error bounds for this setting. Even though the missing completely at random setting may seem naive, it is actually how knowledge graph embedding methods are typically benchmarked in the literature. Our results provide, to a certain extent, an explanation for why knowledge graph embedding methods work (as much as classical learning theory results provide explanations for classical learning from i.i.d. data).

heading: 1 INTRODUCTION
text: Many large knowledge bases such as YAGO (Mahdisoltani et al., 2015) and NELL (Carlson et al., 2010) are represented as knowledge graphs. A knowledge graph is a set of triples (head, predicate, tail) where head and tail are objects (also frequently called entities) and predicate is a binary relation. Each such triple represents a fact about the world, e.g. (NewYork, IsLocatedIn,US). The objects can be seen as vertices of a graph and the relations as labeled directed edges (pointing from head to tail), hence the name knowledge graph. Most knowledge bases are incomplete, i.e. there are facts that should be included in them but are not. A popular task is to automatically complete such knowledge bases. This is often done by embedding the objects and relations contained in them into some vector spaces and then using the embedding to predict the missing tuples.
There has been a number of knowledge graph completion methods presented in the literature (we give an overview of existing methods in Section 2.3). However, to our best knowledge, there has not been any theoretical analysis of the generalization abilities of these methods in the spirit of classical learning theory. We make the first steps in this direction in the present paper. We derive expected error bounds for a class of knowledge graph embedding methods. A key challenge in deriving generalization bounds in this setting is that the training and test data do not satisfy assumptions typically used in learning theory. The knowledge bases that we receive contain only positive examples, that is, the facts already in the knowledge base. We do not know which of the facts not contained in the knowledge base are just missing and which are not contained in the knowledge base because they are actually false. This is known as learning from positive and unlabeled data (PU-learning); we refer to (Bekker & Davis, 2018) for a recent survey. Only a few results have been obtained for generalization bounds for PU-learning so far, e.g. (Niu et al., 2016), but they are not directly applicable to our setting (we discuss the details in Section 10).
The bounds that we derive in this paper rely on an assumption on how the triples are missing from the knowledge graph. In particular, we assume that the triples are missing “completely at random”, i.e. that each tuple may be missing with probability δ > 0 independently of the others. Even though this setting may appear naive, it is actually exactly how some famous datasets’ training and test sets are created, e.g. (Bordes et al., 2013). Thus, the theoretical results actually do relate to what one observes in “practice” (i.e. in the respective papers that use these datasets). The bounds that we derive here apply to knowledge graph embedding methods that use log-loss for learning the embeddings such as ComplEx (Trouillon & Nickel, 2017), SimplE (Kazemi & Poole, 2018) or ConvE (Dettmers et al., 2018).
Main Technical Contributions Our main technical results are expected error bounds on the number of triples (h, r, t) that are predicted incorrectly when using knowledge graph embedding for knowledge graph completion (stated in Theorems 4 and 5), i.e. either to be in the knowledge graph when they are not supposed to be (false positives) or not to be in the knowledge graph when they are supposed to be (false negatives). The bound assumes that the knowledge graph embedding is learned by maximizing the log-likelihood of a certain exponential-family distribution (introduced in Section 5), which turns out to be equivalent to how several prominent knowledge graph embedding methods (Trouillon & Nickel, 2017; Kazemi & Poole, 2018; Dettmers et al., 2018) are learned using log-loss (this is discussed in detail in Section 10). Our results therefore provide a statistical learning theory style justification for these knowledge graph embedding methods. In order to obtain the main results we also derive several auxiliary technical results which might be of independent interest (in particular, Theorems 2 and 3).

heading: 2 PRELIMINARIES

heading: 2.1 KNOWLEDGE GRAPHS
text: Let O be a set of objects and R a set of relations. A knowledge graph is a set of triples (h, r, t) where h and t are objects and r is a relation. Here h is called the head of the triple and t is called the tail of the triple. In the formalism of first-order logic, a triple (h, r, t) represents a first-order logic atom r(h, t). For instance the triple (Alice,Knows,Bob) corresponds to the first-order logic atom Knows(Alice,Bob), which represents the fact that Alice knows Bob. Here, Alice and Bob are objects and Knows is a relation.
Example 1. Let us have the following objects and relations: O = {France,Germany,Berlin,Paris}, R = {CapitalOf,Borders}. Then the knowledge graph, representing our geographical knowledge about these countries and cities, can look as G = {(France, Borders,Germany), (Germany,Borders, France), (Berlin,CapitalOf,Germany), (Paris,CapitalOf, France)}. Whereas, in this case, the knowledge graph is complete and accurate, in reality most knowledge graphs will lack some of the true tuples. The task of knowledge base completion is to add such missing facts.

heading: 2.2 KNOWLEDGE GRAPH EMBEDDING
text: Knowledge graph embedding methods represent knowledge graphs geometrically. They do so by representing objects and relations as vectors (or matrices). Given a knowledge graph G on some sets of objects O and relations R, most knowledge graph embedding methods need three components: vector representations of objects, vector representations of relations and a function ψ(xh,xr,xt) which takes the representations of h, r and t and produces a score that is used to assess how likely it is that the relation (h, r, t) is contained in the knowledge graph. One can then compare the output of the function with a threshold to decide which triples are (predicted to be) in the knowledge graph.
Note on notation. For a set of objects O and a set of relations R we will normally denote their vector representations by X. We will usually treat X as a look-up table. For an object o we will typically use xo to denote its vector representation from X and analogically for a relation r we will use xr, unless explicitly stated otherwise. With a slight abuse of notation, we will also sometimes treat X as a set of vectors and, for instance, write x ∈ X. Relations can be mapped to matrices (denoted Mr) or tensors instead of only vectors, and even if relations are mapped to vectors the dimension may be different from the dimension of entity embeddings. However, for the sake of simplicity, we will not introduce more notations, and X and ψ will also be used in these cases.

heading: 2.3 EXISTING METHODS
text: One can roughly categorize knowledge graph (KG) embedding approaches into several groups based on different scoring functions such as distance-based scoring functions and similarity-based scoring functions.
The most well-known class of embedding methods using distance-based scoring functions is TransE (Bordes et al., 2013) and its variants. The scoring function of TransE is defined as the negative distance between xh + xr and xt, i.e., ψ(xh,xr,xt) = −||xh + xr − xt||2. In order to effectively model more general relations rather than only one-to-one relations, TransH has been proposed (Wang et al., 2014). Given a triple (h, r, t), the scoring function is defined as −||x⊥h + xr − x⊥t ||2 where x⊥h and x⊥t are the projections of entity embeddings xh and xt onto some hyperplane, respectively. TransR (Lin et al., 2015), TransD (Ji et al., 2015) and TranSparse (Ji et al., 2016) are similar to TransH, allowing relation-specific embeddings in different ways. TransM (Fan et al., 2014; Xiao et al., 2015), ManifoldE (Xiao et al., 2016) and TransF (Feng et al., 2016) relax the requirement xh + xr ≈ xt. SE (Bordes et al., 2011) uses two matrices to project head and tail entities for each relation r, and the score is −||M1rxh −M2rxt||1. RotatE (Sun et al., 2019) defines each relation as a rotation from the source entity to the target entity in the complex vector space, and its scoring function is −||xh ◦xr −xt||2 where ◦ is the entry-wise product.
In the class of similarity-based methods, RESCAL (Nickel et al., 2011) and its variants are among the most well-known ones. RESCAL also assigns every entity a vector but every relation r a matrix Mr
1. The scoring function is defined as x>hMrxt. Jenatton et al. (2012) further assumes that every Mr has the same set of eigenvectors. Garcı́a-Durán et al. (2014) adds other terms into the scoring function x>hMrxt+x > h xr+x > r xt+x > t Dxh whereD is a diagonal matrix independent of relations. DistMult (Yang et al., 2015) is a simplified version of RESCAL by restricting Mr being diagonal, and hence improves the efficiency of RESCAL. To combine the advantages of both methods, i.e., the expressive power of RESCAL and the simplicity of DistMult, HolE (Nickel et al., 2016) has been proposed. ComplEx (Yang et al., 2015) extends DistMult by allowing complex-valued embeddings, which is more powerful in modeling asymmetric relations. Hayashi & Shimbo (2017) show that ComplEx is in fact equivalent to HolE. To capture analogical structures, ANALOGY (Liu et al., 2017) further requires Mr in RESCAL to be normal and mutually commutative.
A class of KG embeddings is based on tensor factorization approaches such as the Canonical Polyadic (CP) decomposition (Hitchcock, 1927) whose scoring function is similar to DistMult, but every entity has two independent embeddings. SimplE (Kazemi & Poole, 2018) is a recent extension of CP decomposition, which ensures the two embeddings of every entity dependent.
There are also a group of algorithms using neural networks for embedding, e.g., SME (Bordes et al., 2014), NTN and SLM (Bordes et al., 2014), MLP (Dong et al., 2014), NAM (Liu et al., 2016) and ConvE (Dettmers et al., 2018).
All the aforementioned embedding methods map entities and relations in a deterministic way. In KG2E (He et al., 2015), representations of entities and relations are random vectors sampled from multivariate normal distributions,
xh ∼ N (µh,Σh) xr ∼ N (µr,Σr) xt ∼ N (µt,Σt).
A possible scoring function is KL(xt−xh||xr) and another is the probability inner product (Jebara et al., 2004) of xt − xh and xr. TransG (Han et al., 2016) further models relations using mixtures of Gaussians.

heading: 3 LEARNING SETTING
text: We work within the following learning setting. We assume that there exists some “ground truth” knowledge graph G∗ and that we observe only a subset of the triples contained in it. We will denote the observed knowledge graph consisting of a subset of G∗’s triples by Ĝ. Furthermore, we assume that Ĝ is obtained from G∗ by the following sampling process, called data-generating distribution. Definition 1 (Data-generating distribution). Let G∗ be a ground-truth knowledge graph and δ > 0 be a real number. The data-generating distribution is given by the following process. Iterate over
1One can also treat the embedding of every relation as a vector xr , and the corresponding scoring function becomes xr · vec(xhx>t ) where vec is the vectorization operator.
all triples τ ∈ G∗ and add each of them to Ĝ with probability 1− δ independently of the others. We call δ the missingness parameter.
The task that we want to solve is then to reconstruct the ground-truth knowledge graph G∗ as well as possible from a single sample from the data-generating distribution. Remark 1. Some knowledge graph embedding methods use different representations for the same object depending on whether it is used as a head or tail of a particular triple. It is easy to see that our general setting also allows such representations;it is enough to double the dimension of the vectors and assume that the function ψ(xh,xr,xt) depends only on the first half of dimensions of xh and the second half of the dimensions of xt. It is easy to see that we can also handle the case when the vector representations of relations have different dimensions than those of objects similarly.

heading: 4 INTUITION AND SKETCH OF THE ARGUMENT
text: Our main results are bounds for the expected number of incorrectly predicted triples for knowledge graph completion. In particular, we show that, assuming certain technical assumption on the knowledge graph embedding method and the way it is trained, there exists a constant C such that the expected error rate in the realizable setting is bounded byC( √ |G∗|/(|R||O|2)· √ ln |O|/|O|+1/|O|), where G∗ is the ground truth knowledge graph and O is the set of objects and R is the set of relations. The first term in the product measures sparsity of the graph and the second term has the familiar form of classical error bounds for learning from i.i.d. data. We also provide similar bounds for the agnostic setting.
The strategy taken in this paper is based on viewing the problem as learning a distribution on knowledge graphs. Suppose that we have not only one sample Ĝ (one knowledge graph) from the datagenerating distribution, but actually many such samples Ĝ1, Ĝ2, . . . , Ĝn (a collection of knowledge graphs instead of just one). We could try to use the knowledge graphs Ĝ1, Ĝ2, . . . , Ĝn to estimate a distribution over knowledge graphs. Then we would predict the triples with frequency higher than some threshold t as true. In reality, we do not have a collection of knowledge graphs but only one. However, to estimate the data-generating distribution, we can exploit the fact that we know its form and the independencies it satisfies. In the next section, we define a distribution to approximate the data-generating distribution, parameterized by the vector representations X of objects and relations.
For the approach sketched above to work, we need (i) the distribution to be expressive enough and (ii) we need to show that the learned distribution will be close enough to the data-generating distribution if we estimate it from a sufficiently large knowledge graph. The question of expressiveness has been tackled in the literature (e.g. Kazemi & Poole (2018)) and we do not deal with it much in this paper. We deal with the second question. Using a concentration inequality for log-likelihood (Theorem 1), we prove a generalization bound for log-likelihood (Theorem 2) from which a bound on KullbackLeibler divergence follows. What then remains to be done is to show how to bound the number of incorrectly predicted triples as a function of the Kullback-Leibler divergence, which we do with the help of Pinsker’s inequality (Theorem 3). Combining these two latter results together then yields a bound on the expected number of triples that are predicted incorrectly (both false positives and false negatives) by the learning method sketched here (Theorem 4).

heading: 5 A PROBABILISTIC PERSPECTIVE
text: Following the intuition described in the previous section, we cast the knowledge graph embedding problem as the problem of estimating the distribution induced by the data-generating process. We seek an approximation of this distribution as an exponential-family model of the form given below in Definition 2. The parameters of this exponential family model are the vector embeddings of the objects and relations. Definition 2 (KG-distribution). LetO be a set of objects,R be a set of relations and Ω = 2O×R×O be the set of all possible knowledge graphs on these objects and relations. Let G ∈ Ω be a knowledge graph and X be the vector representation of the objects and relations. Then we define
PX(G) = 1
Z ∏ (h,r,t)∈G exp (ψ(xh,xr,xt)),
where xh, xr and xt are the vector representations of h, r and t given by X, ψ : Rd × Rd × Rd is a function, d is the dimension of the vector representations, and finally Z =∑ G′∈Ω ∏ (h,r,t)∈G′ exp (ψ(xh,xr,xt)) is a normalization constant, ensuring that PX(G) is a probability distribution.
Unless we allow |ψ| to be infinite, KG-distributions cannot model the data-generating distribution exactly. However, as we will show it is enough if the KG-distributions are close enough in KullbackLeibler divergence.
Remark 2. The KG-distribution from Definition 2 can equivalently be written as
PX(G) = ∏
(h,r,t)∈G
exp (ψ(xh,xr,xt))
1 + exp (ψ(xh,xr,xt)) ∏ (h,r,t)∈(O×R×O)\G
1
1 + exp (ψ(xh,xr,xt)) .

heading: 6 GENERALIZATION BOUNDS FOR LOG-LIKELIHOOD
text: In this section, we derive generalization bounds for log-likelihood of KG-distributions learned from one sample (i.e. knowledge graph) from the data-generating distribution described in Section 3.
First, we define log-likelihood and normalized log-likelihood of the KG-distribution model.
Definition 3 (Normalized log-likelihood). Let G be a knowledge graph on a set of objects O and a set of relationsR and X be vector representations of the objects and relations. The log-likelihood of this model is L(X|G) = lnPX(G) and its normalized log-likelihood is then defined as NL(X|G) =
1 |O|2|R| · L(X|G).
We start by proving a concentration inequality for the log-likelihood of KG-distributions, which is a rather straightforward consequence of McDiarmid’s inequality.
Theorem 1. Let G∗ be the ground-truth knowledge graph. Let G be sampled from the datagenerating distribution induced by G∗ and X be fixed vector representations. Then
P [|L(X|G)− E[L(X|.)]| ≥ ε] ≤ 2 exp ( − 2ε 2
M2|G∗| ) where M ≥ suph,t,r∈X |ψ(xh,xr,xt)| (we assume suph,t,r∈X |ψ(xh,xr,xt)| to be finite) and the probability P [. . . ] and the expectation E[. . . ] are w.r.t. the sampling of knowledge graphs from the data-generating distribution.
The next theorem is the main result of this section. It bounds the expectation of the maximum deviation of the log-likelihood of KG distributions from their mean, where the KG-distributions are selected from a hypothesis classH (which has to satisfy certain assumptions listed in the theorem). Theorem 2. Let G∗ be a ground-truth knowledge graph on a set of objects O and a set of relations R and let G be sampled by the data-generating distribution. Let X ⊆ Rd. Finally, let HX (“hypothesis class”) denote the set of vector representations X, X ⊆ X |O|+|R|, of the objects from O and relations fromR. Let D, M and K be real numbers satisfying:
1. ∀x,x′ ∈ X : ‖x− x′‖ ≤ D,
2. ∀xh,xr,xt ∈ X : |ψ(xh,xr,xt)| ≤M ,
3. ∀xh,xr,xt,x′h,x′r,x′t ∈ X : ‖ψ(xh,xr,xt) − ψ(x′h,x′r,x′t)‖ ≤ K(‖xh − x′h‖ + ‖xr − x′r‖+ ‖xt − x′t‖).
Then the following holds:
E [
sup X∈HX |NL(X|G)− E[NL(X|.)]| ] ≤ 4 |O| +M √ |G∗| |R||O|2 · √ d ln (4eDK|O| √ d) |O|
where both expectations on the l.h.s. are w.r.t. sampling of knowledge graphs from the datagenerating distribution.

heading: 7 PINSKER’S INEQUALITY COMES INTO PLAY
text: In this section, we use Pinsker’s inequality to show how the Kullback-Leibler divergence between the data-generating distribution, which generates the observed knowledge graph, and the learned distribution can be used to bound the number of incorrectly predicted triples. In particular, we assume that all triples with probability given by the learned distribution greater than a fixed threshold t are predicted as positive (i.e. predicted to belong in the knowledge graph) and the rest as negative (i.e. predicted not to belong in the knowledge graph). An incorrectly predicted triple is then either a triple which is included in the ground-truth knowledge graph but we predict it as false (false negative) or a triple which is not included in the ground-truth knowledge graph but we predict it as true (false positive). In combination with the results from the previous section, this will allow us to bound the expected number of incorrectly predicted triples (this is explained in detail in the next section).
Theorem 3, which is the main result of this section, bounds the number of incorrectly predicted triples as a function of the Kullback-Leibler divergence of the data-generating and the learned distributions, of the threshold t (used to decide which triple is predicted as positive) and the missingness parameter δ (the fraction of the triples missing from the ground-truth knowledge graph). The main idea of the proof of this theorem (which is given in the appendix) is as follows. Whenever there is an incorrectly predicted triple τ , the difference between its probability w.r.t. the data-generating distribution and w.r.t. the learned distribution must be greater than some fixed ∆ (the value of ∆ depends on the threshold t and the missingness parameter δ), otherwise τ could not be incorrectly predicted. Pinsker’s inequality (Pinsker, 1964), which relates total variation distance and KullbackLeibler divergence, then allows us to obtain a lower bound on the Kullback-Leibler divergence of the data-generating and the learned marginal distributions corresponding to the incorrectly predicted triple τ . Since triples are sampled independently of each other in both the data-generating and the learned distributions, the sum of the Kullback-Leibler divergences of the marginal distributions corresponding to all possible individual triples will equal the Kullback-Leibler divergence of the datagenerating distribution and the learned distribution. This all together is what allows us to derive the bound stated in the next theorem. Theorem 3. Let G∗ be the ground-truth graph on a set of objects O and relations R. Let P denote the data-generating distribution induced by G∗ with the missingness parameter δ and let Q denote the learned distribution. Let t ∈ (0; 1− δ) be a threshold for predicting which triples belong to the knowledge graph. Finally, let F be the set of incorrectly predicted triples, i.e. the set of all triples τ ∈ O×R×O such that either τ ∈ G∗ and the probability of τ given by the learned distributionQ is smaller than t (false negatives) or τ 6∈ G∗ and the probability of τ given by the learned distribution Q is greater or equal to t (false positives). Then the following holds for the cardinality of the set of incorrectly predicted triples F:
|F| ≤ max { ln 2
2t2 ,
ln 2
2(1− δ − t)2
} ·KL(P ||Q).
Note that the bound from this theorem is minimized for the threshold t := (1− δ)/2. This suggests how to set the threshold if we knew the missingness parameter δ.

heading: 8 PUTTING EVERYTHING SO FAR TOGETHER
text: Next we combine the results from the previous sections to obtain a bound on the expected number of incorrectly predicted triples for vector representations X learned by maximizing the likelihood of the respective KG-distribution parametrized by X. Here we assume that the domain X of the vector representations is a subset of Rd of finite diameter and that there is some pre-fixed scoring function ψ. Theorem 4. Let G∗ be a ground-truth knowledge graph on a set of objectsO and a set of relationsR and let G be sampled by the data-generating distribution. LetX ⊆ Rd. LetHX (“hypothesis class”) denote the set of vector representations X, X ⊆ X |O|+|R|, of the objects from O and relations from R. Let K, M , D be as in Theorem 2 and t and δ be as in Theorem 3. Let X ∈ HX be a representation of objects and relations learned by maximizing the log-likelihood L(X|G), i.e. X = arg maxX′∈HX L(X′|G). Finally, let X∗ = arg maxX∈HX E[L(X|.)]. Then the following holds for
the sets of incorrectly predicted triples FX, obtained using the KG-distribution with X: E [ |FX| |O|2|R| ] ≤ max { ln 2 t2 , ln 2 (1− δ − t)2 } · ( 4 |O|
+M √ |G∗| |R||O|2 · √ d ln (4eDK|O| √ d) |O| + KL(P ||PX∗) |O|2|R|  where KL(P ||PX∗) is the Kullback-Leibler divergence of the data-generating distribution P and the best possible representable distribution PX∗ .

heading: 9 THE “REALIZABLE” CASE
text: In learning theory, one usually speaks of the “realizable case” when the hypothesis class contains the target concept. In general, the data generating distribution cannot be represented exactly using the KG-distribution with vector representations from a given set X unless we allow |ψ| to be infinite (which would be needed to model the triples that have zero probability of being sampled from the data generating distribution because they are not contained in the ground-truth knowledge graph G∗). Therefore we cannot really speak of the “realizable case” in the usual sense. In particular it may be the case that the given scoring function ψ and the given domain of vector representations X are enough to represent the knowledge graph in the sense that there exists a threshold t such that (ψ(xh,xr,xt) ≥ t) ⇔ (h, r, t) ∈ G∗), and yet the data-generating distribution could not be represented by the corresponding KG-distribution exactly. Hence, it makes sense to define the realizable case slightly differently for our setting. Definition 4 (γ-Realizable case). For a given data-generating distribution P induced by a groundtruth knowledge graph G∗ with the missingness parameter δ and a given scoring function ψ and a domain of vector representations X , we say that a KG-distribution PX given by a scoring function ψ and vector representations X is γ-admissible if the following is satisfied: exp(ψ(xh,xr,xt))/(1 + exp(ψ(xh,xr,xt))) ≥ 1 − γ for all (h, r, t) ∈ G∗ and 1/(1 + exp(ψ(xh,xr,xt))) ≤ γ for all (h, r, t) 6∈ G∗, where xh,xr,xt are vector representations given by X. We say that a learning problem is γ-realizable if all vector representations X ∈ X |O|+|R| that maximize the expected log-likelihood (i.e. the best vector representations) give rise to γ-admissible KG-distributions.
Next we present a version of Theorem 3 suitable for γ-realizable settings. Theorem 5. Let G∗ be the ground-truth graph on a set of objects O and relations R. Let P denote the data-generating distribution induced by G∗ and let Pγ be a γ-admissible distribution. Let Q denote the learned distribution and let t ∈ (γ; 1 − γ) be a threshold. Then the following holds for the cardinality of the set of incorrectly predicted triples F:
|F| ≤ max { ln 2
2(t− γ)2 ,
ln 2
2(1− γ − t)2
} ·KL(Pγ ||Q).
In the next theorem we present a tighter version of Theorem 4 for γ-realizable settings. Theorem 6. Let everything be as in Theorem 4 but assume a γ-realizable setting. Then the following holds for the sets of incorrectly predicted triples FX, obtained using the KG-distribution with X:
E [ |FX| |O|2|R| ] ≤ max { ln 2 (t− γ)2 ,
ln 2
(1− t− γ)2
} · ( 4
|O| +M √ |G∗| |R||O|2 √ d ln (4eDK|O| √ d) |O|  The next example illustrates that the results from Theorem 6 are asymptotically non-trivial (which is non-obvious as we show below). Example 2. Let us assume that we have some fixed HX , K, D and d and that the X∗ ∈ HX . For simplicity, let us assume that this is a γ-realizable setting with γ = 0.1. Let the ground knowledge graphs G be sparse and satisfy |G| = α(|O|) · |O| where α is an integer-valued function and O is the set of objects in the knowledge graph. We suppose that the threshold t satisfies t ∈ (γ, 1 − γ). Then the expected fraction of triples incorrectly predicted by the learned model from our hypothesis
class can be bounded by: C1 · √ α(|O|) √ ln |O|/|O| where C1 is a positive constant. Now consider another “alternative prediction method” which always predicts all triples as false. The fraction of triples incorrectly predicted by this method will be: E [ |F|/(|O|2|R|) ] ≤ C2 · α(|O|)/|O| where C2 is a positive constant. It follows that whenever α(|O|) grows faster than ln |O|, the bounds of the maximum likelihood method, derived in this paper, become tighter than the error bound of this trivial method. Here, we note that α(|O|) growing only as a logarithm corresponds to very sparse knowledge graphs (in which prediction of positive examples is likely hard).

heading: 10 EXISTING KGE METHODS IN THE LIGHT OF OUR ANALYSIS
text: In this section, we discuss how existing knowledge graph embedding methods in general fit into our analysis.

heading: 10.1 SCORING FUNCTIONS
text: We assumed that predictions are made by comparing exp (ψ(xh,xr,xt)) with a threshold. In existing works, one directly compares the output of the scoring function ψ(xh,xr,xt) with a threshold. This differs only by taking a logarithm and, hence, obviously does not harm applicability of our analysis.

heading: 10.2 LOSS FUNCTIONS
text: Throughout this paper we assumed learning vector representations of objects and relations using maximum likelihood. Here we show that this setting corresponds to learning knowledge graph embeddings using a sigmoidal transformation of the scoring function ψ together with log-loss. This combination is often used in the knowledge graph embedding literature (Trouillon et al., 2016; Dettmers et al., 2018; Kazemi & Poole, 2018).2 In particular the loss used in the literature is (using our notation):
l(X,G) = ∑
(h,r,t)∈G
ln (1 + exp(−ψ(xh,xr,xt)))+ ∑
(h,r,t)∈(O×R×O)\G
ln (1 + exp(ψ(xh,xr,xt)))
= ∑
(h,r,t)∈G
− ln (
1
1 + exp(−ψ(xh,xr,xt))
) + ∑ (h,r,t)∈(O×R×O)\G − ln (
1
1 + exp(ψ(xh,xr,xt))
)
= −  ∑ (h,r,t)∈G ln ( exp(ψ(xh,xr,xt)) 1 + exp(ψ(xh,xr,xt)) ) + ∑ (h,r,t)∈(O×R×O)\G ln ( 1 1 + exp(ψ(xh,xr,xt)) ) .
It is not difficult to see that this is the same as the negative log-likelihood of the KG-distribution with scoring function ψ. Thus, our analysis directly applies to methods that use this loss, such as ComplEx (Trouillon et al., 2016), ConvE (Dettmers et al., 2018) and SimplE (Kazemi & Poole, 2018). For other methods, log-loss can in principle be also used and it was observed by Trouillon & Nickel (2017) that the margin-based loss functions, used by many knowledge graph embedding methods, are more prone to overfitting compared to log-likelihood. Our results may shed further light on this latter observation, however, to verify it theoretically would require to perform a similar type of analysis as we did in this paper for the margin-based loss functions (which might require completely different techniques). Therefore we leave this comparison for future work.

heading: 10.3 LIPSCHITZ CONTINUITY AND BOUNDED DOMAIN ASSUMPTIONS
text: Our result requires Lipschitz continuity. Most of the scoring functions ψ used by existing knowledge graph methods are not globally Lipschitz continuous. However, they are Lipschitz continuous if we
2These works use regularized log-loss. Here we ignore the regularization term but note that bounding the domain of the vector representations has to some extent a similar effect.
restrict the domain of the embeddings to a bounded subset of Rd (this is among others true for the approaches based on matrix or tensor factorization).
For obtaining the generalization bounds, we needed to assume that the learned vector representations come from a set with a bounded diameter. Existing methods usually do not have such a constraint explicitly but use a regularization term which has a similar effect in practice.

heading: 10.4 NUMERICAL EXAMPLES
text: TransE Here we show how our results apply to TransE (Bordes et al., 2013), arguably the simplest embedding method. In TransE, ψ(xh,xr,xt) = −‖xh + xr − xt‖. It is not difficult to show that the Lipschitz constant K = 1 as follows (using the triangle inequality repeatedly):
|‖xh + xr − xt‖ − ‖x′h + x′r − x′t‖| = |‖xh − x′h + xr − x′r − xt + x′t + x′h + x′r − x′t‖ −‖x′h + x′r − x′t‖| ≤ ‖xh−x′h + xr −x′r −xt + x′t‖ ≤ ‖xh−x′h‖+ ‖xr −x′r‖+ ‖xt−x′t‖.
Let the dimension of the vector embeddings be d = 3. Let us suppose that X = {x|‖x‖ ≤ ln 10}. Then the remaining parameters from Theorem 4 areD = ln 102 andM = ln 103. For simplicity, let us assume a γ-realizable setting with γ = 0.01. Let t = 0.5. Finally suppose that |G∗| = |O| ln2 |O| and |R| = 1. Now we have all parameters needed to apply Theorem 6. We plot the resulting bound for a varying number of objects in Figure 1 in red. Note that, even though the number of dimensions of the vector embeddings is low, the total number of parameters of the model is very high because each object and each relation has its own parameters.
SimplE Next we illustrate how our analysis applies to SimpleE (Kazemi & Poole, 2018), which is a fully-expressive knowledge graph embedding method. In SimplE, each object o ∈ O and each relation r ∈ R are represented by two vectors x′o and x′′o , respectively, x′r and x′′r . In our formalism, we represent both as single vectors: xo = [x′o,x ′′ o ] and xr = [x ′ r,x ′′ r ]. The scoring function of SimpleE is ψ(xh,xr,xt) = 12 (〈x ′ h,x ′ r,x ′′ t 〉+ 〈x′t,x′′r ,x′′h〉) where 〈x,y, z〉 := ∑d i=1 xiyizi. Clearly the Lipschitz constant of ψ(xo,xr,xt) is not bounded for unbounded xh, xr and xt. We therefore need to restrict the domain of the vector representations X , which our theorems assume anyways and which is done implicitly through the L2-regularization term in the original work (Kazemi & Poole, 2018). We show in the appendix that the Lipschitz constant K for SimplE can be bounded by √
6 2 supx∈X ‖x‖ 2. For the illustration, we will assume the same dimension d = 3 and the same domain X as we did for TransE, i.e. X = {x|‖x‖ ≤ ln 10}. Then the other parameters needed to compute the generalization bound for SimplE are D = ln 102, M = (ln 10)3, K = √ 6
2 (ln 10) 2.
Finally, we assume the same γ, |R| and |G∗| as we did for TransE. The resulting generalization bound for SimplE following from Theorem 5 is shown in Figure 1 in red together with the bound for TransE (in blue). Not surprisingly, the generalization error bound is looser for SimplE as it is
a more flexible model (in fact, a fully-expressive model with a sufficiently large dimension of the vector representations).

heading: 11 RELATED WORK
text: Our work is very close in spirit to the theoretical analyses of learning from positive and unlabeled examples, known as PU-learning (Niu et al., 2016). However, there are several distinctions that do not allow direct application of the existing results to the problem that we analyze in this paper. First, existing works on PU-learning assume the inductive setting whereas our setting is transductive. Second, the work (Niu et al., 2016), which is one of the few papers analyzing generalization bounds for PU-learning, only applies to losses that satisfy l(t,+1) + l(t,−1) = 1 which is not the case for log-loss. Moreover the losses considered by Niu et al. (2016) are usually not used for knowledge graph embedding in practice. Third, even if the previous two differences were not a problem (although they are), it would still not be obvious how to apply the existing results to the knowledge graph embedding setting in which we deal with interconnected examples; i.e. it is not clear what the attributes of the examples and the hypothesis class should be so that we could fit knowledge graph embedding setting into the standard PU learning setting. Lastly, an advantage of our analysis is that it uses a simple probabilistic model which provides a possible, hopefully intuitive, explanation of why knowledge graph embedding methods work (at least in the standard testing scenarios that use test data generated completely at random).
Another line of works that are related to ours are works on generalization bounds for link prediction, such as (London et al., 2013; Wang et al., 2018). The main differences w.r.t. these works is that (i) they assume availability of both positive and negative examples (whereas we only have positive examples), (ii) the links are predicted based on attributes of nodes and not on the structure of the relations. Finally, our work is also related to works for tensor completion using tensor decomposition, such as (Nickel & Tresp, 2013). However, first, not all knowledge graph embedding methods can be seen as some low-rank tensor decompositions and, second, as far as we know no analysis of generalization bounds of tensor decomposition applies to the PU-learning setting, in which one observes only positive examples (which is the setting studied in our work).

heading: 12 CONCLUSIONS
text: In this paper we have derived generalization bounds for the expected number of triples predicted incorrectly by knowledge graph embedding methods. The main assumptions that we used were: (i) facts are missing from the knowledge graph “completely at random” and (ii) the vector representations of objects and relations are learned by maximizing log-likelihood of the model (equivalently by minimizing log-loss). While the “missing completely at random” assumption may seem simplistic, it is actually how training and test sets are usually constructed, e.g. in (Bordes et al., 2013), and only recently there have been works systematically looking beyond datasets constructed in this way, e.g. (Trouillon et al., 2019). As for the second assumption, it would be interesting to see if one could derive similar bounds for other loss functions that have been used for knowledge graph embedding in the literature, which would then provide a more solid theoretical justification for their use.

heading: A USEFUL INEQUALITIES
text: We will need the following well-known inequalities. Lemma 7 (Pinsker’s inequality (Pinsker, 1964)). Let P and Q be distributions. Then
KL(P ||Q) ≥ 1 2 ln 2 ‖P −Q‖21.
Lemma 8 (McDiarmid’s Inequality (McDiarmid, 1989)). Let X1, . . . , Xn be independent random variables with values from a set X and let f : Xn → R. If, for all i ∈ {1, . . . , n}, and for all x1, , xn, x ′ i ∈ X , the function f satisfies |f(x1, . . . , xi, . . . , xn)−f(x1, . . . , x′i, . . . , xn)| ≤ ci then:
P [|f(X1, . . . , Xn)− E[f ]| ≥ ε] ≤ 2 exp ( − 2ε
2∑n i=1 c 2 i
) .

heading: B PROOF OF THEOREM 1
text: In this section, we prove Theorem 1.
Theorem 1. Let G∗ be the ground-truth knowledge graph. Let G be sampled from the datagenerating distribution induced by G∗ and X be fixed vector representations. Then
P [|L(X|G)− E[L(X|.)]| ≥ ε] ≤ 2 exp ( − 2ε 2
M2|G∗|
) ,
where M ≥ suph,t∈Xo,r∈Xr |ψ(xh,xr,xt)|.
Proof. Let F := |G∗|. Let U1, . . . , UF be Bernoulli random variables such that P [Ui = 1] = 1− δ. Let us denote by τi the i-th tuple in G∗. Let g : {0, 1}F → 2G ∗ be defined as g(u1, . . . , uF ) = {τi ∈ G∗|ui = 1}, i.e. g(u1, . . . , uF ) contains all τi’s for which ui = 1. It is not difficult to see that G and g(U1, . . . , UF ) have the same distribution. Hence we can bound the probability P [|L (X|g(U1, . . . , UF ))− E[L(X|.)]| ≥ ε] instead of directly P [|L(X|G)− E[L(X|.)]| ≥ ε]. It follows from the assumptions of the theorem that for any (u1, . . . , uF ) ∈ {0, 1}F the following must hold:
|L (X|g(u1, . . . , ui, . . . , uF ))− L (X|g(u1, . . . , u′i, . . . , uF )) |
= ∣∣∣∣∣∣ ∑
(h,r,t)∈g(u1,...,ui,...,uF )
ψ(xh,xr,xt)− lnZ − ∑
(h,r,t)∈g(u1,...,u′i,...,uF )
ψ(xh,xr,xt) + lnZ ∣∣∣∣∣∣ ≤ |ψ(xhi ,xri ,xti)| ≤M,
where xh, xr and xt denote vector representations of h, r and t, respectively.
Hence, we can use McDiarmid’s inequality to obtain P [|L (X|g(U1, . . . , UF ))− E[L(X|.)]| ≥ ε] ≤ 2 exp ( − 2ε 2
M2F
) from which the statement of the theorem follows directly.

heading: C PROOF OF THEOREM 2
text: In this section, we give a proof of Theorem 2. First, we prove several lemmas that we need to prove this theorem. Lemma 9. Let M̃ > 0 be such that for every object or relation o it holds ‖xo−x′o‖ ≤ M̃ where xo and x′o are the vector representations of o in X and X′, respectively. If ψ satisfies the assumptions of Theorem 2 then the following holds: |L(Xo,Xr|G)− L(X′o,X′r|G)| ≤ 2K|O|2|R|M̃.
Proof. Let us first introduce some notation. Let V := |O| and R = |R|. Whenever we write xh, xr and xt, it denotes the vector representations of h, r and t from X, whereas when we write x′h, x′r and x′t, it denotes the representations from X′. We have
|L(Xo,Xr|G)− L(X′o,X′r|G)| = ∣∣∣∣∣∣ ∑
(h,r,t)∈G
(ψ(xh,xr,xt)− ψ(x′h,x′r,x′t))− ln Z
Z ′ ∣∣∣∣∣∣ ≤ ∣∣∣∣∣∣ ∑
(h,r,t)∈G
(ψ(xh,xr,xt)− ψ(x′h,x′r,x′t)) ∣∣∣∣∣∣+ ∣∣∣∣ln ZZ ′ ∣∣∣∣ . Next we bound the terms on the r.h.s. of the above inequality separately. We start by obtaining the bound for the first term:∣∣∣∣∣∣ ∑ (h,r,t)∈G ( ψ(xh,xr,xt)− ψ(x′h,x′r,x′t)
)∣∣∣∣∣∣ ≤ KV 2R ·
(∥∥xh − x′h∥∥+ ∥∥xr − x′r∥∥+ ∥∥xt − x′t∥∥) ≤ KV 2RM̃. (1) It remains to bound the second term. We have:
Z Z ′ =
∑ G∈Ω ∏ (h,r,t)∈G e
ψ(xh,xr,xt)∑ G∈Ω ∏ (h,r,t)∈G e ψ(x′h,x ′ r,x ′ t) =
∑ G∈Ω ∏ (h,r,t)∈G e (ψ(xh,xr,xt)−ψ(x′h,x ′ r,x ′ t)+ψ(x
′ h,x ′ r,x ′ t))∑ G∈Ω ∏ (h,r,t)∈G e ψ(x′h,x ′ r,x ′ t)
≤ eK·V 2R·M̃
∑ G∈Ω ∏ (h,r,t)∈G e
ψ(x′h,x ′ r,x ′ t)∑ G∈Ω ∏ (h,r,t)∈G e ψ(x′h,x ′ r,x ′ t) = eKV 2RM̃ (2)
where the last inequality follows from the inequality K (‖xh − x′h‖+ ‖xr − x′r‖+ |xt − x′t‖) ≤ KM̃ . Combining (1) and (2) we obtain the inequality that we needed to prove.
Lemma 10. Let G∗ be a ground-truth knowledge graph on a set of objectsO and a set of relationsR and let G be sampled by the data-generating distribution. Let H (“hypothesis class”) be a finite set of vector representations of the objects fromO and relations fromR. Then the following inequality holds
E [
sup X∈H |L(X|G)− E[L(X|.)|
] ≤M √ |G∗| ln (2e|H|)
2
where M ≥ suph,t∈Xo,r∈Xr |ψ(xh,xr,xt)|.
Proof. We denote W := supX∈H |L(X|G)− E[L(X|.)| and B := 2/(|G∗| ·M2). Then, using the union bound and Theorem 1, we have: P [W ≥ ε] ≤ 2|H| · exp ( −ε2 ·B ) . Next, we have
E[W ] ≤ √ E[W 2] = √∫ ∞ 0 P [W 2 ≥ t]dt = √∫ ∞ 0 P [W ≥ √ t]dt ≤ √ u+ ∫ ∞ u P [W ≥ √ t]dt
≤ √ u+ ∫ ∞ u 2|H| · exp (−t ·B)dt = √ u+ 2|H| B · exp (−u ·B)
The above expression is minimized for u := ln (2|H|)/B (note that u may be arbitrary), yielding the bound: √
ln (2e|H|) B = M
√ |G∗| ln (2e|H|)
2 .
Lemma 11 (Covering number, e.g., (Shalev-Shwartz & Ben-David, 2014)). Let S be a subset of Rd of diameter at most k (i.e. for any x1,x2 ∈ S, ‖x1 − x2‖ ≤ k). Then S can be covered by(
(2k √ d)/ρ )d balls of radius ρ.
Now we are ready to prove Theorem 2.
Theorem 2. Let G∗ be a ground-truth knowledge graph on a set of objects O and a set of relations R and let G be sampled by the data-generating distribution . Let X ⊆ Rd. Finally, let HX (“hypothesis class”) denote the set of vector representations X, X ⊆ X |O|+|R|, of the objects from O and relations fromR. Let D, M and K be real numbers satisfying:
1. ∀x,x′ ∈ X : ‖x− x′‖ ≤ D,
2. ∀xh,xr,xt ∈ X : |ψ(xh,xr,xt)| ≤M ,
3. ∀xh,xr,xt,x′h,x′r,x′t ∈ X : ‖ψ(xh,xr,xt) − ψ(x′h,x′r,x′t)‖ ≤ K(‖xh − x′h‖ + ‖xr − x′r‖+ ‖xt − x′t‖),
Then the following holds:
E [
sup X∈HX |NL(X|G)− E[NL(X|.)]| ] ≤ 4 |O| +M √ |G∗| |R||O|2 · √ d ln (4eDK|O| √ d) |O| .
Proof. Let B be a finite set of vectors of dimension d such that if we place centers of balls of radius ρ in all these points then these balls will cover the set X . Using Lemma 11, we know that it is possible to find such a set B satisfying
|B| ≤ ( (2D √ d)/ρ )d (3)
because the diameter of the set X is at most D (due to the assumptions of the theorem) and the dimension of the vectors in X is d. Next we assume that we are only searching for a maximumlikelihood solution X consisting of vectors from B so that we could use Lemma 10 which expects a finite hypothesis set H. Even though we have so far been thinking of the vector representations X as lookup tables, it will be more convenient here to think of them as lists of vectors. Specifically, we assume that the objects and relations are ordered arbitrarily. The hypothesis set will then be
represented asHB = B|O|+|R|. Hence, using (3), we obtain |HB| ≤ ( (2D √ d)/ρ )d(|O|+|R|) . Then
from Lemma 10 we have:
E [
sup X∈B |L(X|G)− E[L(X|.)|
] ≤M √ |G∗| ln (2e|HB|)
2 . (4)
Using the bound on |HB|, we can bound the r.h.s. by:
M √√√√ |G∗|d(|O|+ |R|) ln( 4eD√dρ ) 2
(5)
For fixed vector representations X′ of the objects and relations, let H(X′) denote the set of vector representations X which satisfy that for every object or relation o: ‖xo − x′o‖ ≤ ρ where xo and x′o are vector representations of o from X and X′, respectively. Now, optimizing over the hypothesis set HX of all possible vector representations from X instead of just the vectors from the setHB, would
yield the next bound: E [
sup X∈HX
|L(X|G)− E[L(X|.)]| ]
= E [ sup
X′∈HB sup X∈H(X′) |L(X|G)− E[L(X′|.)] + E[L(X′|.)]− E[L(X|.)]|
]
≤ E [ sup
X′∈HB sup X∈H(X′) |L(X|G)− L(X′|G) + L(X′|G)− E[L(X′|.)]| ] + sup
X′∈HB sup X∈H(X′) |E[L(X′|.)]− E[L(X|.)]|
≤ E [ sup
X′∈HB sup X∈H(X′) |L(X|G)− L(X′|G)|
] + E [ sup
X′∈HB |L(X′|G)− E[L(X′|.)]| ] + sup
X′∈HB sup X∈H(X′) |E[L(X′|.)]− E[L(X|.)]|
Next, to bound the first and third term, we use Lemma 9 and, to bound the second term, we use Equations (4) and (5). After setting ρ := 1K|O| and after simplifying, this gives us the following bound:
E [
sup X∈HX
|L(X|G)− E[L(X|.)]| ] ≤ 4|O||R|+M √ |G∗|d(|O|+ |R|) ln (4eDK|O| √ d)
2 ≤ 4|O||R|+M √ |G∗||O||R|d ln (4eDK|O| √ d).
For the expected error of normalized log-likelihood we then obtain
E [
sup X∈HX |NL(X|G)− E[NL(X|.)]| ] ≤ 4 |O| +M √ |G∗| |R||O|2 · √ d ln (4eDK|O| √ d) |O|
which finishes the proof of the theorem.

heading: D PROOF OF THEOREM 3
text: In this section, we prove Theorem 3.
Theorem 3. Let G∗ be the ground-truth graph on a set of objects O and relations R. Let P denote the data-generating distribution induced by G∗ with the missingness parameter δ and let Q denote the learned distribution. Let t ∈ (0; 1− δ) be a threshold for predicting which triples belong to the knowledge graph. Finally, let F be the set of incorrectly predicted triples, i.e. the set of all triples τ ∈ O×R×O such that either τ ∈ G∗ and the probability of τ given by the learned distributionQ is smaller than t (false negatives) or τ 6∈ G∗ and the probability of τ given by the learned distribution Q is greater or equal to t (false positives). Then the following holds for the cardinality of the set of incorrectly predicted triples F:
|F| ≤ max { ln 2
2t2 ,
ln 2
2(1− δ − t)2
} ·KL(P ||Q).
In the proof of the theorem, we will use the following simple lemma (which can be verified by computing the discriminant of the respective quadratic equation). Lemma 12. The following inequality holds for all x, y ∈ [0; 1]2 and α ∈ (0;∞):
α(x− y)2 + 1 4α ≥ |x− y|.
Proof of Theorem 3. We assume that all possible triples (h, r, t) ∈ O × R × O are ordered (arbitrarily) and that τi denotes the i-th triple from this set and I = {1, 2, . . . , |O|2 · |R|}. Let G be sampled from the data-generating distribution and G′ be sampled from the learned model (i.e. the KG-distribution). We define binary random variables Bi := 1(τi ∈ G) and B′i := 1(τi ∈ G′). Hence the complete vectors B = (B1, . . . , Bn) and B′ = (B′1, . . . , B ′ n) represent the knowledge graphs sampled from the data-generating and modelled distributions, respectively. We denote by PB and P ′B the distributions of B and B
′. Due to the independence properties of the two distributions, the following holds: KL(PB||PB′) = ∑ i∈I KL(PBi ||PB′i) where PBi and P ′ Bi
are the distributions of Bi and B′i, respectively.
Next we bound the error that is made when we classify all triples τi with P [B′i = 1] > t as true (i.e. belonging to the knowledge graph) and the rest as false. We may notice that when misclassifying a triple τi, we must either have
P [Bi = 1] = 0 and P [B′i = 1] > t
(“false positive”) or P [Bi = 1] = 1− δ and P [B′i = 1] < t
(“false negative”). Hence, if we denote by FP the set of triples τi for which we have false positive errors, we must have for all α > 0
t|FP| ≤ ∑ τi∈FP P [B′i = 1] ≤ ∑ τi∈FP (|P [Bi = 1]− P [B′i = 1]|)
≤ ∑ τi∈FP ( 1 4α + α|P [Bi = 1]− P [B′i = 1]|2 ) where the last inequality follows from Lemma 12. It follows that
|FP| · ( t− 1
4α ) ≤ ∑ τi∈FP α|P [Bi = 1]− P [B′i = 1]|2.
Letting α = 1/(2t) yields the bound
|FP| ≤ 1 t2 · ∑ τi∈FP |P [Bi = 1]− P [B′i = 1]|2. (6)
Similarly for false negatives, if we denote by FN the set of triples for which we have false negative errors, we must have for all α′ > 0:
|FN | · (1− δ − t) ≤ ∑
τi∈FN |P [Bi = 1]− P [B′i = 1]|
≤ ∑
τi∈FN
( 1
4α′ + α′|P [Bi = 1]− P [B′i = 1]|2
) .
Hence, we also have: |FN | · (
4α′ − 1 4α′
− δ − t ) ≤ α′ ∑ τi∈FN |P [Bi = 1]− P [B′i = 1]|2
Letting α′ = 1/(2− 2δ − 2t) gives us
|FN | ≤ 1 (1− δ − t)2
· ∑
τi∈FN |P [Bi = 1]− P [B′i = 1]|2. (7)
Next we combine (6) and (7) and apply Pinsker’s inequality:
|FP|+ |FN | ≤ 1 t2 · ∑ τi∈FP |P [Bi = 1]− P [B′i = 1]|2
+ 1 (1− δ − t)2 · ∑
τi∈FN |P [Bi = 1]− P [B′i = 1]|2
= 1 t2 · ∑ τi∈FP 1 4 ‖PBi − PB′i‖ 2 1 +
1 (1− δ − t)2 · ∑
τi∈FN
1 4 ‖PBi − PB′i‖ 2 1
≤ 1 4 max
{ 1
t2 ,
1
(1− δ − t)2 } · ∑ i∈I ‖PBi − PB′i‖ 2 1
≤ max { ln 2
2t2 ,
ln 2
2(1− δ − t)2
} ·KL(PB||PB′). (8)
This finishes the proof of this theorem.

heading: E PROOF OF THEOREM 4
text: Theorem 4 Let G∗ be a ground-truth knowledge graph on a set of objectsO and a set of relationsR and let G be sampled by the data-generating distribution. LetX ⊆ Rd. LetHX (“hypothesis class”) denote the set of vector representations X, X ⊆ X |O|+|R|, of the objects from O and relations from R. Let K, M , D be as in Theorem 2 and t and δ be as in Theorem 3. Let X ∈ HX be a representation of objects and relations learned by maximizing the log-likelihood L(X|G), i.e. X = arg maxX′∈HX L(X′|G). Finally, let X∗ = arg maxX∈HX E[L(X|.)]. Then the following holds for the sets of incorrectly predicted triples FX, obtained using the KG-distribution with X:
E [ |FX| |O|2|R| ] ≤ max { ln 2 t2 ,
ln 2
(1− δ − t)2
} · ( 4
|O|
+M √ |G∗| |R||O|2 · √ d ln (4eDK|O| √ d) |O| + KL(P ||PX∗) |O|2|R|  where KL(P ||PX∗) is the Kullback-Leibler divergence of the data-generating distribution P and the best possible representable distribution PX∗ .
Proof. Let G denote the knowledge graph sampled from the data-generating distribution and PX the learned distribution. For a fixed Xfixed, the following equality holds: KL(P ||PXfixed) = H(P ) + EP [L(Xfixed|G)]. Then we also have KL(P ||PXfixed)−KL(P ||PX∗) = EP [L(Xfixed|G)] − EP [L(X∗|G)]. Next we can define g(G′) := arg maxX∈HX L(X|G′), substitute g(G′) for Xfixed and take the expectation over graphs G′, which are assumed to be sampled from the data-generating distribution. This yields:
EG′∼P [KL(P ||Pg(G′))−KL(P ||PX∗)] = EG′∼P [EG∼P [L(g(G′)|G)]− EG∼P [L(X∗|G)]]. Next we can use Lemma 8.2 from (Devroye et al., 2013) to bound the r.h.s.:
EG′∼P [EG∼P [L(g(G′)|G)]− EG∼P [L(X∗|G)]] ≤ 2EG′∼P [
sup X∈HX
|L(X|G′)− E[L(X, .)]| ] .
Finally, we use the bound from Theorem 2 to bound the r.h.s. of this inequality. Combining this with Theorem 3 finishes the proof.

heading: F PROOF OF THEOREM 5
text: Theorem 5. Let G∗ be the ground-truth graph on a set of objects O and relations R. Let P denote the data-generating distribution induced by G∗ and let Pγ be a γ-admissible distribution. Let Q
denote the learned distribution and let t ∈ (γ; 1 − γ) be a threshold. Then the following holds for the cardinality of the set of incorrectly predicted triples F:
|F| ≤ max { ln 2
2(t− γ)2 ,
ln 2
2(1− γ − t)2
} ·KL(Pγ ||Q).
Proof. The proof of this theorem is very similar to the proof of Theorem 3. We highlight the most important differences in bold.
We assume that all possible triples (h, r, t) ∈ O × R × O are ordered (arbitrarily) and that τi denotes the i-th triple from this set and I = {1, 2, . . . , |O|2 · |R|}. Let G be sampled from the distribution Pγ and G′ be sampled from the learned model (i.e. the KG-distribution). We define binary random variables Bi := 1(τi ∈ G) and B′i := 1(τi ∈ G′). Hence the complete vectors B = (B1, . . . , Bn) and B′ = (B′1, . . . , B ′ n) represent the knowledge graphs sampled from the distribution Pγ and the modelled distribution, respectively. We denote by PB and P ′B the distributions of B and B′. Due to the independence properties of the two distributions (after all, Pγ is still a KG-distribution and therefore inherits its independence structure), the following holds: KL(PB||PB′) = ∑ i∈I KL(PBi ||PB′i) where PBi and P ′ Bi
are the distributions of Bi and B′i, respectively.
Next we bound the error that is made when we classify all triples τi with P [B′i = 1] > t as true (i.e. belonging to the knowledge graph) and the rest as false. We may notice that when misclassifying a triple τi, we must either have
P [Bi = 1] ≤ γ and P [B′i = 1] > t
(“false positive”) or P [Bi = 1] ≥ 1 − γ and P [B′i = 1] < t
(“false negative”).
The rest of differences w.r.t. the proof of Theorem 3 follows from the differences highlighted so far in a straightforward way (details follow below).
Hence, if we denote by FP the set of triples τi for which we have false positive errors, we must have for all α > 0
t|FP| ≤ ∑ τi∈FP P [B′i = 1] ≤ ∑ τi∈FP (γ + |P [Bi = 1]− P [B′i = 1]|)
≤ ∑ τi∈FP ( γ + 1 4α + α|P [Bi = 1]− P [B′i = 1]|2 ) where the last inequality follows from Lemma 12. It follows that
|FP| · ( t− γ − 1
4α ) ≤ ∑ τi∈FP α|P [Bi = 1]− P [B′i = 1]|2.
Letting 1/(2t− 2γ) yields the bound
|FP| ≤ 1 (t− γ)2 · ∑ τi∈FP |P [Bi = 1]− P [B′i = 1]|2. (9)
Similarly for false negatives, if we denote by FN the set of triples for which we have false negative errors, we must have for all α′ > 0:
|FN | · (1− γ − t) ≤ ∑
τi∈FN |P [Bi = 1]− P [B′i = 1]|
≤ ∑
τi∈FN
( 1
4α′ + α′|P [Bi = 1]− P [B′i = 1]|2
) .
Hence, we also have: |FN | · (
4α′ − 1 4α′
− γ − t ) ≤ α′ ∑ τi∈FN |P [Bi = 1]− P [B′i = 1]|2
Letting α′ = 1/(2− 2γ − 2t) gives us
|FN | ≤ 1 (1− γ − t)2
· ∑
τi∈FN |P [Bi = 1]− P [B′i = 1]|2. (10)
Next, we combine (9) and (10) and apply Pinsker’s inequality:
|FP|+ |FN | ≤ 1 (t− γ)2 · ∑ τi∈FP |P [Bi = 1]− P [B′i = 1]|2
+ 1 (1− γ − t)2 · ∑
τi∈FN |P [Bi = 1]− P [B′i = 1]|2
= 1 (t− γ)2 · ∑ τi∈FP 1 4 ‖PBi − PB′i‖ 2 1 +
1 (1− γ − t)2 · ∑
τi∈FN
1 4 ‖PBi − PB′i‖ 2 1
≤ 1 4 max
{ 1
(t− γ)2 ,
1
(1− γ − t)2 } · ∑ i∈I ‖PBi − PB′i‖ 2 1
≤ max { ln 2
2(t− γ)2 ,
ln 2
2(1− γ − t)2
} ·KL(PB||PB′). (11)
This finishes the proof of this theorem.

heading: G PROOF OF THEOREM 6
text: Theorem 6 Let everything be as in Theorem 4 but assume a γ-realizable setting. Then the following holds for the sets of incorrectly predicted triples FX, obtained using the KG-distribution with X: E [ |FX| |O|2|R| ] ≤ max { ln 2 (t− γ)2 , ln 2 (1− t− γ)2 } · ( 4 |O| +M √ |G∗| |R||O|2 √ d ln (4eDK|O| √ d) |O| 
Proof. The proof of this theorem is practically identical to the proof of Theorem 4. The only difference is that in this proof we invoke Theorem 5 instead of Theorem 3.

heading: H THE LIPSCHITZ CONSTANT OF SIMPLE’S SCORING FUNCTION
text: In this section we derive a bound on the Lipschitz constant K of the scoring function of SimplE (Kazemi & Poole, 2018) on a bounded domain X ⊆ R2d.3 The scoring function of SimplE is ψ(xo,xr,xt) = 1 2 (〈x ′ h,x ′ r,x ′′ t 〉+ 〈x′t,x′′r ,x′′h〉) where 〈x,y, z〉 := ∑d i=1 xiyizi. Let us denote xh = [x ′ h,x ′′ h], xr = [x ′ r,x ′′ r ], xt = [x ′ t,x ′′ t ] and r = [xh,xr,xt]. Since the function ψ(r) is differentiable everywhere, any K satisfying K ≥ ‖∇ψ(r)‖ for all r ∈ X 3 will be a Lipschitz constant for ψ on the bounded domain X . Next we compute the gradient of ψ(r). To simplify the notation, we use x[i] to denote the i-th element of the vector x. We then have
3Here we use d to denote the dimension of the vector representations as used by Kazemi & Poole (2018). Since SimplE defines two vectors for every object or relation, the dimension in our formalism is 2d, hence X ⊆ R2d.
∂ψ(r) ∂x′h[i] = 1 2 · x′r[i] · x′′t [i],
∂ψ(r) ∂x′r[i] = 1 2 · x′h[i] · x′′t [i],
∂ψ(r) ∂x′′t [i] = 1 2 · x′h[i] · x′r[i],
∂ψ(r) ∂x′t[i] = 1 2 · x′′r [i] · x′′h[i],
∂ψ(r) ∂x′′r [i] = 1 2 · x′t[i] · x′′h[i],
∂ψ(r) ∂x′′h[i] = 1 2 · x′t[i] · x′′r [i].
From this we get
‖∇ψ(r)‖2 = 1 4 d∑ i=1 ( x′r[i] 2 · x′′t [i]2 + x′h[i]2 · x′′t [i]2 + x′h[i]2 · x′r[i]2 + x′′r [i]2 · x′′h[i]2
+x′t[i] 2 · x′′h[i]2 + x′t[i]2 · x′′r [i]2 ) ≤ 1
4
( 〈x′r,x′′t 〉2 + 〈x′h,x′′t 〉2 + 〈x′h,x′r〉2 + 〈x′′r ,x′′h〉2 + 〈x′t,x′′h〉2 + 〈x′t,x′′r 〉2 ) ≤ 6
4 sup x∈X ‖x‖4.
Thus, we get
‖∇ψ(r)‖ ≤ √ 6
2 sup x∈X ‖x‖2 := K,
Let us now denote yh = [y′h,y ′′ h], yr = [y ′ r,y ′′ r ], yt = [y ′ t,y ′′ t ], and s = [yh,yr,yt]. Then we have
‖ψ(r)− ψ(s)‖ ≤ K‖r− s‖ ≤ K · (‖xh − yh‖+ ‖xr − yr‖+ ‖xt − yt‖) .
So K = √
6 2 supx∈X ‖x‖ 2 is indeed the Lipschitz constant that we need in order to be able to obtain generalization bounds using Theorems 4 and 5.

Review summaries:
This work conducts a theoretical study of the generalization bounds for the number of wrongly predicted triples of KG embedding methods. Under a "``missing completely at random'' assumption, the authors model the distributions of sampled KG and ground-truth KG, and derivate the bounds as a function of the KL-divergence by leveraging Pinsker's inequality. Preliminary discussions on how existing KG embedding methods fit into this theoretical study have been conducted.