Knowledge Graph Embedding: A Probabilistic Perspective and Generalization Bounds
Authors: Ondrej Kuzelka
Yuyi Wang
Venue:  (2020)
Keywords: knowledge graph embedding
generalization bounds

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 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).

Under review as a conference paper at ICLR 2020
KNOWLEDGE GRAPH EMBEDDING: A PROBABILISTIC PERSPECTIVE AND GENERALIZATION BOUNDS
Anonymous authors Paper under double-blind review
ABSTRACT
We study theoretical properties of embedding methods for knowledge graph com- pletion under the "missing completely at random" assumption. We prove gen- cralization 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 cer- tain extent, 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).
INTRODUCTION
Many large knowledge bases such as YAGO (Mahdisoltani et al., 2015) and NELL (Carl- et al.) 2010) are represented knowledge graphs. A knowledge graph is set of triples (head, predicate, tail) where head and tail are objects (also frequently called entities) and predicate is binary relation. Each such triple represents (NewYork, IsLocate,In, 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 knowl- edge bases are incomplete, i.e. there are facts that should be included in them but are not. A popular task is 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.
fact about the world, e.g.
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 gen- cralization bounds in this setting is that the training and test data do not satisfy assumptions typically used in learning theory. The knowledge bases that 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 (Bekker & Davis 2018) for recent survey. Only few results have been obtained for gen- eralization bounds for PU 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 I0).
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 5 > O independently of the others. Even though this setting may appear naive, 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 derive here apply to knowledge graph embedding methods that log-loss for learning the embeddings such as ComplEx (Trouillon & Nickel 2017), SimplE (Kazemi & Poole, 2018) or ConvE: (Dettmers et al. 2018).

---

Under review as a conference paper at ICLR 2020
Main Technical Contributions Our main technical results expected error bounds the num- ber of triples (h, r,t) that are predicted incorrectly when using knowledge graph embedding for knowledge graph completion (stated in Theorems 4 and i.c. 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 supposed to be (false negatives). The bound assumes that the knowledge graph embedding is learned by maximizing the log-likelihood of certain exponential-famij) distribution (introduced in be equivalent how several prominent knowledge graph embedding
Section [5), which turns methods (Trouillon & Nickel 2017 Kazemi & Poole 2018 Dettmers et al. 2018) are learned using log-loss (this is discussed in detail Section 10). Our results therefore provide statistical learning theory style justification for these knowledge graph embedding methods. In order to obtaín the main results we also derive several auxiliary technical results which might be of independent interest (in particular, Theorems and
PRELIMINARIES
2.1 KNOWLEDGE GRAPHS
Let O be a set of objects and R. a set of relations. A knowledge graph a set of triples (h, r, where l and are objects and is relation. Here h is called the head of the triple and f. is called the tail of the triple. In the formalism of first-order logic, a triple (h, represents first-order logic atom rhh, t). For instance the triple (Alice, Knows, Bob) corresponds the first-order logic atom Knows (Alice Bob), which represents the fact that Alice knows Bob. Here, Alice and Bob are objects and Knows relation.
Example 1. Lel us have the following objects and relations:
O
(France, Germany, Berlin, Paris), R. R= [CapitalOff Borders). Then the knowledge graph, repre- senting our geographical knowledge about these countries and cities, can look as G {(Frnnce, 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.
2.2 KNOWLEDGE GRAPH EMBEDDING
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: objects, vector representations of relations and a function ('(x,, X, x.) which takes the representations of h, and and produces score that is used to assess how likely that the relation (h, r, t) is contained in the knowledge graph. One can then compare the output of the function with a threshold decide which triples are (predicted to be) in the knowledge graph.
vector representations
Note on notation. For a set of objects O and a set of relations we will normally denote their vector representations by X. We will usually treat X look-up table. For an object we will typically use x, to denote its vector representation from X and analogically for a relation r we will use x,, unless explicitly stated otherwise. With a slight abuse of notation, will also sometimes treat as a set of vectors and, for instance, write x E X. Relations can be mapped to matrices (denoted M,,) 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, will not introduce more notations, and X and i will also be used in these cases.
2.3 EXISTING METHODS
One 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.
2

---

Under review as a conference paper at ICLR 2020
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 X + x, and x,, i... ( X,, x,) =||x, + -x,112-
In order to effectively model more general relations rather than only one-to-one relations, TransH has been proposed (Wang al., 2014). Given triple rh, t), the scoring function is defined as -||x; + x, x where x and x are the projections of entity embeddings XĄ2 and x, onto some hyperplane, respectively. TransR (Lin al. 2015), TransD (Ji al. 2015) and TranSparse (Ji et al., 20166) are similar to TransH, allowing relation-specific embeddings in different ways. TransM (Fan al. 2014 Xiao et al.) 2013). ManifoldE (Xiao et al. 2016) and TransF (Feng et al., 2016)
relax the requirement X + X2 2 X₃-
SE (Bordes al.
2011) uses two matrices to project head and tail entities for each relation and M X
the score is
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 - -||x, o x,, xell2 where o is the entry-wiss product.
In the class of similarity based methods, RESCAL NNicel et al., 2011 1) and its variants are among the most well-known ones. RESCAL also assigns every entity a vector but every relation r matrix M. The scoring function is defined as x, M, Jenatton et al.
2012) further assumes that every M, has the same set of eigenvectors. Gareia-Durán et al. 2014) adds other terms into the scoring function x, M, +x x, x, +x, x, +x, Dx,, where D is diagonal matrix independent of relations. DistMult Yang et al., 2015) is a simplified version of RESCAL by restricting M, 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.) (0166) 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 HolE. To capture analogical structures, ANALOGY (Liu et al., 2017 further requires M, 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 (2088) 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 deterministic way. In KG2E (He et al.) 2013), representations of entities and relations are random vectors sampled from multivariate normal distributions,
X1. (( En, Xr ~ ( Σ,) X N N( Ex).
A possible scoring function K KL(x; Xi. (xx))) and another is the probability inner product (Jebara let al. (2004) of x, X₁, and x,, TransG (Han et al., 2016) further models relations using mixtures of Gaussians.
3 LEARNING SETTING
We work within the following learning setting. We assume that there exists some "ground truth" knowledge graph G" and that we observe only subset of the triples contained in it. We will denote the observed knowledge graph consisting of a subset of G' triples by J. Furthermore, we assume that & is obtained from G* by the following sampling process, called data- datta-generating distribution. Definition (Data-generating distribution). Let G" be ground-truth knowledge graph and be real number. The data-generaiee generating distribution is given by the following process. Iterate over
'One can also treat the embedding of every relation vector x,, and the corresponding scoring function hecomes x, vee xx,, where vec the vectorization operator.
3

---

Under review as a conference paper at ICLR 2020
all triples G" and add each of them to G with probability 1 - independently of the others. We call 6 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 sata-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;i is enough to double the dimension of the vectors and assume that the function e Xh. Xy, Xt) depends only on the first half of dimensions xf, and the second half of the dimensions of xt. It is easy to see that can also handle the case when the vector representations of relations have different dimensions than those of objects similarly.
4 INTUITION AND SKETCH OF THE ARGUMENT
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 knowl- edge graph embedding method and the way it trained, there exists constant C such that the ex- pected error rate in the realizable setting is bounded by where G is the ground truth knowledge graph and O is the set of objects and R. is the set of re- lations. 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.
/In 11//0)+)/00))
The strategy taken in this paper is based on viewing the problem learning distribution on knowl- edge graphs. Suppose that we have not only one sample I (one knowledge graph) from the data- generating distribution, but actually many such samples G. ....... In (a collection of knowledge .... graphs instead of just one). We could try to use the knowledge graphs G1. G2. ......... Go to estimate a distribution over knowledge graphs. Then we would predict the triples with frequeney higher than some threshold as true. In reality, we do not have a collection of knowledge graphs but only one. However, to estimate the data-get gett-generatiig 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-generaie 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) need to show that the learned distribution will be close enough the data-generating distribution if we estimate it from a sufficiently large knowledge graph. The question of expressiveness has been tackled in the literature (c.g. Kazemi & Poole (2018) and we do not deal with it much in this paper. We deal with the second question. Using concentration inequality for log-likelihood (Theorem II) we prove a generalization bound for log-likelihood (Theorem 2 from which a bound on Kullback- Leibler 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 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)
5 A PROBABILISTIC PERSPECTIVE
Following the intuition described in the previous section, we cast the knowledge graph embedding problem the problem of estimating the distribution induced by the aata-generating process. We seek an approximation of this distribution as an exponential-fame in Definition 2 The parameters of this exponential family model are the vector embeddings of the objects and relations.
model of the form given below
Definition (KG-distributionn) Let O be a set of objects. R be a set of relations and J xxxxx be the set of all possible knowledge graphs on these objects and relations. Let G E Q be a knowledge graph and X be the vector representation of the objects and relations. Then we define
1
Px(g) = Z
II
exp (1b(X,, X,, xx));
(h.r.))G
4

---

Under review as a conference paper at ICLR 2020
where Xh, Xr and are the vector representations of h, and t given by X. vh: R x R. x Rd is function, d is the dimension of the vector representations, and finally Z = Ex'en (hr...)e exp Xx, is normalization constant, ensuring that Px(9) is prob- ability distribution.
Unless we allow |æb| to be infinite, KG-distributions cannot model the data-generating distribution exactly. However, as we will show it enough the KG-distributions are close enough Kullback- Leibler divergence.
Remark 2. The KG-distribution from Definition can equivalently be written
exp (Kh, Xy, Xx)
Px( = II
II
1 ++ exp (1b (Xh, Xr, Xx))
1 exp Xx,,,,,x,xxx)
(hir,t)eg
(
GENERALIZATION BOUNDS FOR LOG-LIKELIHOOD
In this section, we derive generalization bounds for log- rngglikklihood 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 knowledge graph on set of objects O and set of relations and X be vector representations of the objects and relations. The log-likeliin pellikllihood of this model is (XX In (g) and its normalized log- likelihood is then defined as NL(() TOP (l()
We start by proving concentration inequality for the log- liielihhood of KG-distributions, which is rather straightforward consequence of McDiarmid's inequality.
Theorem Let G be the ground-truth knowledge graph. Let G be sampled from the data- generating distribution induced by G and % be fixed vector representations. Then
25 (-MP(GH1)
(-
PIIL(X()) E[((XE]
$ 2exp
where M 2 suph.t,eex (xh,,, Xy, X,, Xx) (we assume suph,t,exx [x( Xr, x:)1 probability P(...] and the expectation B[...] are w.r.t. the sampling of knowledge graphs from the data-generating distribution.
X,,X:) to be finite) and the
The next theorem is the main result of this section. bounds the expectation of the maximum deviation of the log- ligeliiel of KG distributions from their mean, where the KG-distributions selected from a hypothesis class H (which has to satisfy certain assumptions listed in the theorem).
Theorem 2. Let G" a ground-trut -ruth knowledge graph on set of objects O and a set of relations RR and let G be sampled by the data- teta--generatnng distribution. Let X C TRd. Finally, let Hx ( ("hy- pothesis class") ) denote the set of vector representations X. X C x(0+||R) of the objects from O and relations from R. Let D, M and K be real numbers satisfying:
1. Vx E X: ||x x'1 D,
2. VXh, Xy,, X2 E X: (1 X,, x,) & M,
3. VX,, X,, x x X: [|0( x,, x, S K({xA - -x/,l ||x,
xX11 + ||xe x(Il)
Then the following holds:
4 + M
gg'h
d (4eDK
E sup [NL(X E[NL(X))
XEHx
|
|0|
where both expectations on the lhh.s are w.r.f sampling of knowledge graphs from the data- generating distribution.
5

---

Under review as a conference paper at ICLR 2020
7 PINSKER'S 'S INEQUALITY COMES INTO PLAY
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 negative (i.e. predicted not belong the knowledge graph). An incorrectly predicted triple is then either triple which is included in the ground-truth knowledge graph but we predict it as false (false negative) or triple which not included the ground-trutt 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 5] which is the main result of this section, bounds the number of incorrectly predicted triples function of the Kullback-Leible divergence of the date-genea and the learned distri- butions, of the threshold & (used to decide which triple is predicted as positive) and the missingness parameter 5 (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 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 A (the value of A depends on the threshold and the missingness parameter 5), otherwise could not be incorrectly predicted. Pinsker's 's inequality (Pinsker 1964), which relates total variation distance and Kullback- Leibler divergence, then allows us to obtain lower bound on the Bellbacck-Leible divergence of the data-generating and the learned marginal distributions corresponding to the incorrectly predicted triple т. Since triples are sampled independently of cach other in both the data Kata-generating and the learned distributions, the sum of the Kullback-Leibler divergences of the marginal distributions cor- responding to all possible individual triples will equal the Kullback- Leibllr divergence of the data- generating 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 natar-gen distribution induced by G with the missingness parameter 6 and let Q denote the learned distribution. Let E (0; 1 5) 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 T E O x Rx such that either E G and the probability of given by the learned distribution Q is smaller than t (false negatives) or T & G and the probability of given by the learned distribution Q is greater or equal to I (false positives). Then the following holds for the cardinality of the set of incorrectly predicted triples F:
In2 2
1n2
FFl S max
t)2 KL(P)IQ).
2 2(1
Note that the bound from this theorem is minimized for the threshold ( := (1 8)/2. This suggests how to set the threshold if we knew the missingness parameter ö.
8 PUTTING EVERYTHING So FAR TOGETHER
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 subset of Rd of finite diameter and that there is some fre-fixed scoring function v.
Theorem 4. 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 C Rdd Let Hx ("hypothesis class") denote the set of vector representations X. X C (R))+ of the objects from O and relations from R. Let K. M. D be as in Theorem 2 and and 8 be as in Theorem 3 Let X. E Hx be representation of objects and relations learned by maximizing the log billiikli L(X(g), i.e. = arg max [xX (G). Finally, let X arg maxxeHx [[I.(X))). Then the following holds for
6

---

Under review as a conference paper at ICLR 2020
the sets of incorrectly predicted triples Fx. obtained using the KG-distribution with X:
Fxl
1n2
In
E
I max
1
(1 8
1)2
O
9-1
dln (4eDK]0lV))
(T((PIPx-)) j013 R
+M
|R|OP
10|
where KL(PI)Pxx)) the Ballback-Leible divergence of the data- eata-generating distribution annd the best possible representable distribution Pz..
THE "REALIZABLE" CASE
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 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 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 may be the case that the given scoring function y 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 (v(x,, X,, xx) 2 t) + rh, E 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 (7-Realizable case). For given data generatnngg distribution P induced by ground- truth knowledge gruph G with the missingness parameter ó and a given scoring function vú and domain of vector representations X, we say that KG-dissributioo Pz given by a scoring function vi and vector representations X is ay-adiissible if the following is satisfied: exp(}) Xr. xx))/(1 + exp(tb(X,, Xx,X,))) 1-11 for all (h, t) G and 1/(1 exp(ub(x X,,X,,, xx))) Y for all (h, & G", where Xh. Xy, X are vector representations given by X. We say that a learning problem is "-realizable if all vector representations E [[[++|R] that maximize the expected log- lilikiiihood (i.e. the best vector representations) give rise "yadmissible KG- KG-distributtons.
Next we present a version of Theorem 3 suitable for 7-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- generatnn distribution induced by G" and let P. be y-admissible distribution. Let Q denote the learned distribution and let t E 1y;1-1) y)) be a threshold. Then the following holds for the cardinality of the set of incorrectly predicted triples F:
ln2
1n2
S max
t)2 KI(P,IIQ).
(((- 2(1
In the next theorem we present a tighter version of Theorem for 7-realizable settings. Theorem 6. Let everything be in Theorem
F but assume rr-relizzalle setting. Then the following holds for the sets of incorrectly predicted triples Fx, obtained using the KG-distribution with X.
Fx O
{
1n2 (1 7 (1
1
9-1 |
dln (4cDK)O)
E
< max
+M
7)
O
10
The next example illustrates that the results from Theorem 6 are asymptotically non-trivial (which non-obvious show below).
Let us assume that have some fixed Hx, K, D and d and that the X E Hxx For simplicity, let us assume that this is a r-realizable setting with y = 0.1. Let the ground knowledge graphs G be sparse and satisfy [9] a([O)) |O] where is integer-valued function and O is the set of objects the knowledge graph. We suppose that the threshold t satisfies E (r, 1y,1= y). Then the expected fraction triples incorrectly predicted by the learned model from our hypothesis
Example 2.
7

---

Under review as a conference paper at ICLR 2020
class can be bounded by: C1. C..vallol /0///10 where C1 is 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/(
S C2 a(OO))/|O where C2 is positive constant. It follows that whenever a{IO)) grows faster than in [O], the bounds of the maximum likelihood method, derived this paper, become tighter than the error bound of this trivial method. Here, note that a( a(O))) growing only as logarithm corresponds very sparse knowledge graphs (in which prediction of positive examples is likely hard).
10 EXISTING KGE METHODS IN THE LIGHT OF OUR ANALYSIS
In this section, we discuss how existing knowledge graph embedding methods in general fit into our analysis.
10.1 SCORING FUNCTIONS
We assumed that predictions are made by comparing exp (v'(X,, x,, xx)) with threshold. In exist- ing works, one directly compares the output of the scoring function Xr: Xe) with threshold. This differs only by taking a logarithm and, hence, obviously does not harm applicability of our analysis.
10.2 LOSS FUNCTIONS
Throughout this paper we assumed learning vector representations of objects and relations using maximum likelihood. Here show that this setting corresponds learning knowledge graph embeddings using sigmoidal transformation of the scoring function ú together with log-loss. This combination is often used the knowledge graph embedding literature (Trouillon al. 2016 Dettmers et al. 2018 Kazemi & Poole 2018 In particular the loss used in the literature is (using our notation):
((19))
Σ (Ku,,)s
In (1
Σ
In (1 exp(x(xxx Xy, x;)))
Σ In
Σ -In
+
I+ (xxxpppp(xxxxxx Xc, (xx)))((0Rx00)))
e Xy, x.))
(h,rA)EGG
exp((xxx, X,, ( exp( X,,, )
Σ In
Σ
In
I1 exp(((U(Xx
(horjee
(hint)((O<xx000G
not difficult to see that this the same as the negative log- likeliiid the KG KG-distribution with scoring function vb. Thus, analysis directly applies to methods that use this loss, such as ComplEx (Trouillon et al., (016), ConvE (Dettmers et al., 2018) and SimplE (Kazemi & Poole 2018). For other methods, log-loss in principle be also used and it observed by Trouillon & Nickel (017)) that the margin-based loss functions, used by many knowledge graph embedding methods, are more prone overtitting compared
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-basee based loss functions (which might require completely different techniques). Therefore we leave this comparison for future work.
10.3 LIPSCHITZ CONTINUITY AND BOUNDED DOMAIN ASSUMPTIONS
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
These works regularized log-loss. Here ignore the regularization term but note that bounding the domain of the vector representations has some extent similar effect.
8

---

Under review as a conference paper at ICLR 2020
Bound from Theorem 6
0.8
0.6
0.4
0.2
0
0.5
1.5
2
2.5
3
3.5
4
4.5
Number of objects in the domain
|O]
-10
Illustration the generalization bound from Theorem 6 applied on TransE (Bordes et al. 2013) and SimplE (Kazemi & Poole 2018). The bound for TransE is shown in red and the bound for SimplE in blue. The parameters of the models are described in the main text.
Figure I:
restrict the domain of the embeddings to bounded subset of IR (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 regularization term which has similar effect in practice.
10.4 NUMERICAL EXAMPLES
TransE Here we show how our results apply to TransE (Bordes et al. 2013), arguably the simplest embedding method. In TransE, (X,,, Xr; xx) -||x; ; + x, xz not difficult to show that the Lipschitz constant K = as follows (using the triangle inequality repeatedly):
X4 x, x
x x
||| Xh. x/, x, x x, + x
x/,
x,
x
- ||x +
X2 x,, x, X
x < X2 x²,11 ||x X
| X1I1
Let the dimension of the vector embeddings be d = 3. Let us suppose that X = |x|| < In 10). Then the remaining parameters from Theorem are D In 102 and M 10 For simplicity, let us assume a r-rrelizable setting with y 0.01. Let 0.5. Finally suppose that | = O In |0] and [R| 1. Now we have all parameters needed to apply Theorem 6 We plot the resulting bound for varying number of objects Figure 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.
Next we illustrate how analysis applies to SimpleE (Kazemi & Poole 2018 which a fully--xpressive knowledge graph embedding method. In SimplE, each object E O and each relation r R are represented by vectors x and x" respectively, x and x" In formalism, we represent both as single vectors: X. = [x,, x"] and x, = [x',, x"]. The scoring function of Sim- pleE is ( Xr, X.) 1 ((x). x x"" + (x,, x" x()) where (x, y, Σd - Tz Clearly the Lipschitz constant of (X,, Xy. X₂) is not bounded for unbounded X₁, X, and X,. We therefore 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 >/6 by 2 suPxEx |x] For the illustration, we will assume the same dimension domain X as did for TransE, i.c. X [x|||x|| < In 10). Then the other parameters needed to compute the generalization bound for SimplE are D = 10?, M = (In 10) K v/ (In 10) Finally, assume the same 7, |R] and G-* as did for TransE. The resulting generalization bound for SimplE following from Theorem 5 is shown in Figure | in red together with the bound for TransE (in blue). Not surprisingly, the generalization error bound is looser for SimplE as it is
SimplE
need to restrict the domain of the vector representations X. which
and the same
2

---

Under review as a conference paper at ICLR 2020
more flexible model (in fact, fxlly-expressivve model with sufficiently large dimension of the vector representations).
11 RELATED WORK
Our work is very close in spirit to the theoretical analyses of learning from positíve 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 transductive. Sec- ond, 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 I(t, +1) + [[t, -1) = 1 which is not the case for usually not used for knowledge
log-loss. Moreover the losses considered by Niu al. (20T6) graph embedding in practice. Third, even if the previous two differences were not problem (al- though 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.c. 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 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,
work is also related to works for tensor completion using tensor decomposi- tion, 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 we know analysis of generalization bounds of tensor decomposition applies to the PU-learning setting, in which one observes only positive examples (which the setting studied in our work).
12 CONCLUSIONS
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 used were: (i) facts are missing from the knowledge graph "completely at random" and (ii) the vector representa- tions of objects and relations 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. (Bordes et al. (013). and only recently there have been works systematically looking beyond datasets constructed in this way, e.g. (Troullon et al., 2019). As for the second assumption, 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.
REFERENCES
Jessa Bekker and Jesse Davis. Learning from positive and unlabeled data: A survey. arXiv preprint vrXiv:1811.0482. 2018
Antoine Bordes, Jason Weston, Ronan Collobert, and Yoshua Bengio. Learning structured embed- dings of knowledge bases. In Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011.
Antoine Bordes, Nicolas Usunier, Alberto Farcia-Duran Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in neural information processing systems, pp. 2787-2792 2013.
Antoine Bordes, Xavier Glorot, Jason Weston, and Yoshua Bengio. A semantic matching energy function for learning with multi-relational data. Machine Learning, 94(2):233-25) 2014.
10

---

Under review as a conference paper at ICLR 2020
Andrew Carlson, Justin Betteridge. Bryan Kisiel, Burr Settles, Estevam R Hruschka, and Tom M Mitchell. Toward an architecture for never-ending language learning. In Twenty-Fourty AAAI Conference Artificial Intelligence, 2010.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Proceedings of the Thirty-Second AAAI Conference on Arti- ficial Intelligence, (AAAI-18), pp. 1811-1818, 2018.
Luc Devroye, László Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition, vol- ume 31. Springer Science & Business Media, 2013.
Xin Dong. Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn. Ni Lao, Kevin Murphy. Thomas Strohmann, Shaohua Sun, and Wei Zhang. Knowledge vault: web-scale approach to proba- bilistic knowledge fusion. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 14, 2014, pp. 601 601-610, 2014.
Miao Fan, Qiang Zhou, Emily Chang, and Thomas Fang Zheng. Transition-based knowledge graph embedding with relational mapping properties. In Proceedings of the 28th Pacific Asia Conference on Language, Information and Computing, pp. 328-337, 2014.
Jun Feng. Minlie Huang, Mingdong Wang. Mantong Zhou, Yu Hao, and Xiaoyan Zhu, Knowledge graph embedding by flexible translation. In Fifteenth International Conference the Principles of Knowledge Representation and Reasoning, 2016.
Alberto Garáía,Durán, Antoine Bordes, and Nicolas Usunier. Effective blending of two and three- way interactions for modeling multi-relational data. In Join! European Conference Machine Learning and Knowledge Discovery in Databases, 2014.
Xiao Han, Minlie Huang, Hao Yu, and Xiaoyan Zhu Transg A generative mixture model for knowledge graph embedding. Computer Science, 2016.
Katsuhiko Hayashi and Masashi Shimbo. On the equivalence of holographic and complex em- beddings for link prediction. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguisties, ACL 2017, Volume 2: Short Papers, pp.
2017.
Shizhu He, Liu Kang, Guoliang Ji, and Jun Zhao. Learning to represent knowledge graphs with gaussian embedding, Acm International on Conference on Information & Knowledge Manage- ment, 2015.
Frank L Hitchcock. The expression of a tensor or a polyadic as a sum of products. Journal of Mathematics and Physics, 611-4):164-189, 1927.
Tony Jebara, Risi Kondor, and Andrew Howard. Probability product kernlss. Journal of Machine 2004.
Learning Research,
Rodolphe Jenatton, Nicolas Le Roux, Antoine Bordes, and Guillaume Obozinski. latent factor model for highly multi-relational data. Advances in Neural Information Processing Systems, 4: 3167-3175, 2012.
Guoliang Ji, Shizhu He, Liheng Xu, Kang Liu, and Jun Zhao. Knowledge graph embedding via dynamic mapping matrix. Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Pro- cessing (Volume 1: Long Papers), pp. 687-696,7 2015.
Guoliang Ji, Kang Liu, Shizhu He, and Jun Zhao. Knowledge graph completion with adaptive sparse transfer matrix. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Seyed Mehran Kazemi and David Poole. Simple embedding for link prediction in knowledge graphs. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Infor- mation Processing Systems 2018, NeurIPS., pp. 2289-4300, 2018.
Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. Learning entity and relation embeddings for knowledge graph completion. In Twenty-ninth AAAI conference on artificial intelligence, 2015.
11

---

Under review as a conference paper at ICLR 2020
Hanxiao Liu, Yuexin Wu, and Yiming Yang. Analogical inference for multi-relational embeddings. In Proceedings the 34th International Conference on Machine Learning, (CML2017, pp. 2168- 2178, 2017.
Quan Liu, Hui Jiang, Zhen-Hua Ling, Si Wei, and Yu Hu. recbaiinisticccaasnnnnn via deep learning: Neural association models. CoRR, fas//6633007044, 2016. URL URL/bttp:://axxvvoorg///
1603.07708
Ben London, Bert Huang, and Lise Getoor. Graph-based generalization bounds for learning binary relations. CoRR, abs/ 300.5334,,, 2013. UtL/http://axxivvooo wtg.//twwi.i..aaaoooooaaoaaaaaaa hbtp://bs/iii /1022 5348
Farzaneh Mahdisoltani, Joanna Biega, and Fabian M Suchanek. YAGO3: : Knowledge Base from
Multilingual Wikipedias. In Proceedings of the Conference on Innovative Data Systems Research, CIDR 15, 2015.
Colin McDiarmid. On the method bounded differences. Surveys in combinatorics, 141(1):148- 188, 1989.
Maximilian Nickel and Volker Tresp. An analysis of tensor models for learning on structured data. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp- 272-287. Springer, 2013.
Maximilian Nickel, Volker Tresp. and Hans-Peter Kriegel. A three-way model for collective learning on multi-relational data. In ICML., volume 11, pp. 809-816, 2011.
Maximilian Nickel, Lorenzo Rosasco, and Tomaso A Poggio. Holographic embeddings of knowl- edge graphs. In Thirtieth Aaai Conference on Artificial Intelligence. 2016.
Gang Niu, Marthinus Christoffel du Plessis, Tomoya Sakai, Yao Ma, and Masashi Sugiyama. Theo- retical comparisons of positive-unlabeldd learning against positive-negative learning. In Advances in neural information processing systems, pp. 1
2016.
Mark S Pinsker. Information and information stability of random variables and processes. Holden- Day, 1964.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory algo- rithms. Cambridge university press, 2014.
Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In 7th International Conference on Learning Represen- tations, ICLR 2019, 2019.
Théo Trouillon and Maximilian Nickel. Complex and holographic embeddings of knowledge graphs: comparison. arXiv preprint arXiv:1707.01440 2017.
Théo Trouillon, Johannes Welbl, Sehastian Riedel, fric Gaussier, and Guillaume Bouchard. Com- plex embeddings for simple link prediction. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, pp. 2071-2080 2016.
Théo Trouillon, Éric Gaussier, Christopher R. Dance and Guillaume Bouchard. On inductive abili- ties of latent factor models for relational learning. J. Artif. Intell. Res., 64:21-53, 2019.
Yuanhong Wang, Yuyi Wang, Xingwu Liu, and Juhua Pu. On the ERM principle with networked data. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), pp. 4244 4251, 2018
Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by trans- lating on hyperplanes. In Twenty-Eighth AAAI conference on artificial intelligence, 2014.
Han Xiao, Minlie Huang, Yu Hao, and Xiaoyan Zhu. Transa: An adaptive approach for knowledge 2015.
graph embedding. arXiv preprint 1509
Han Xiao, Minlie Huang, and Xiaoyan Zhu. From point to manifold: knowledge graph embedding for precise link prediction. In Proceedings of the Twenty-Fifhh International Joint Conference on Artificial Intelligence, pp. 1315-1321. AAAI Press, 2016.
12

---

Under review as a conference paper at ICLR 2020
Bishan Yang, Scott Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In Proceedings of the International Conference Learning Representations (ICLR) 2015, 2015.
A USEFUL INEQUALITIES
We will need the following well-known inequalities.
Lemma 7 (Pinsker's inequality (Pinsker 1964)). Let P and Q be distributions. Then
KL(PIIQ)
2ln2 Qll
Lemma 8 (McDiarmid's Inequality McDiarmid 1989) ). Let XI..... Xn be independent random variables with values from set X' and let f nn IR. If. for all i E (.....,,.. and for all
1i Znz 2' X, the function f satisfies [f I In) -f :.]] S C then:
2ea
PlIS(X X.)) E[A] 2 al S 2exp
Li=l c
B PROOF THEOREM
In this section, we prove Theorem
Theorem 1 G* be the ground-truth knowledge graph. Let G be sampled from the data- generating distribution induced by G and X be fixed vector representations. Then
PI|((X))) - E[L(XIMI 2 E] 2exp (->22) 25
where M suph,tex. (X),
X,, X:)l
Proof. Let Fet = | Let UI.... Up be Bernoulli random variables such that PIU; 1] 8. Let us denote by T; the i-th tuple G* Let g: 10. - 20 be defined as g(u1..... up)
{N E G"lu: = 1}. i.e. g(u1..... ...: up) contains all T:'s for which u; = 1. It is not difficult to see that G and g(U,, UF) have the same distribution. Hence we can bound the probability P (II (X]g(U,,,,... UF) - E[L(X|)]] 2 e] instead of directly P (XIL(X(G) - E[L(X|))] 2 e).
follows from the assumptions of the theorem that for any (U1,..., ur) E (0, 13 the following must hold:
IL (Xlg(u1, (1 u....., uF)) L (Xlg(u1..... ........ th.
up))
Σ
In X,,
Σ
(X Xr, Xx) In Z
S |0b(x), Xy, xx,) S M,
where Xn, X, and x, denote vector representations of h, r and I, respectively.
Hence, we can use McDiarmid's inequality to obtain P [ gUU...... Ur)) -[(()11
2 exp
2 M'F
from which the statement of the theorem follows directly.
C PROOF OF THEOREM 2
In this section, we give proof of Theorem First, prove several lemmas that need to prove this theorem.
Lemma 9. Let M be such that for every object or relation it holds ||x,, - -x,-,,1l s M where x, and x,, are the vector representations of in X and X', respectively. If a satisfies the assumptions of Theorem then the following holds: [T.(X,, X Tx x 9)] 2K 2
13

---

Under review as a conference paper at ICLR 2020
Proof. Let first introduce some notation. Let V := |0] and R | Whenever write X and X,, it denotes the vector representations of h, r and t from X, whereas when we write X,. X, and x,, denotes the representations from X'. We have
XX( - (x x,, - In 7
[L,,,, X,1 - (xxx,,
Σ (h.nA)eG
Z'
Σ
(1h(x) Xr, 16 x,,
+
In
Z
(H.r.))e
Next we bound the terms on the r.h.s. the above inequality separately. We start by obtaining the bound for the first term:
Σ
Xr,x,, - +xh x,, x(i)
(h.r.))
S SKV 11. (1|xA xill + ||x, - xill + ||x, xill s KV2RM. (1)
It remains bound the second term. We have:
Z Egen Ilm e (x).)))))))
Egen Mimneee (00
Z' Eeen Il(hni)e e x(x,),
Even Il x(,x,,x,.xx))
R. Esen IanrtE (x x,x())
KV2
Esea II... (x,,,x,
where the last inequality follows from the inequality K ([|xs x + ||x, - x + |x: x K.M. Combining and we obtain the inequality that we needed to prove.
Lemma 10. Let be ground-truth knowledge graph set of objects O and set of relations R and let G be sampled by the data-generating distribution. Let H ("hypothesis class") be a finite set of vector representations of the objects from O and relations from R. Then the following inequality holds
(2e
E sup [X E[L(X|>)| < M
XEH
2
where M 2 suph,tex,,rex, (xb, Xx, X:)l.
Proof. We denote W union bound and Theorem have: P P[W c] < 2/7(| exp (-E2. B). Next, we have
SuDXEM LXX - EX)() and B 2/(19-1 2)). Then, using the
P(W 2 Vidl < PIW2 2 4dll %.
E[W] < v B[W
u P(W 2 Vidl
2/H1
< uu
2|H| exp (-t- B)dt
V -
eepp (-u B)
B
The above expression is minimized for = In (2 (note that may be arbitrary), yielding the bound:
In (2e H|)
g In (2e
M
B
2
Lemma 11 (Covering number, e.g., (Shalev-Shwartz & Ben- David 2014)). Let S a subset of Rdd of diameter most is (i.e. for any X1, X2 S, x X2 k). Then S can be covered by
((2kv0)/0) balls of radius
14

---

Under review as a conference paper at ICLR 2020
Now are ready to prove Theorem
2
Theorem 2, Let G be a ground trund-truuh 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 C Rd. Finally, let Hx ("hy- pothesis class") ") denote the set of vector representations X. X _ xlOT+|Ri, of the objects from O and relations from R. Let D, M and K be real numbers satisfying:
Vx, E N: ||x - x S D.
2. Vxn, X,,, X₁ E X: (x) X,,, xx)1 S M,
3. VXn, X,,, X,, X/, x x E X: Xx, 10xx/ x(I1 & {([ - -xall + ||x,
xX|| + || x(11),
Then the following holds:
4 O
|9-|
d (4eDK)Olva
E
sup XEHx
[N E[NL(X
$
V
1
[
Proof. Let B be finite of vectors of dimension d such that if we place centers of balls radius in all these points then these balls will cover the set X. Using Lemma II we know that it is possible to find such set satisfying
B S (2DDV))/))
because the diameter of the set X' at most D) (due to the assumptions of the theorem) and the dimension of the vectors in X' is d. Next assume that we are only searching for maximum- likelihood solution consisting of vectors from so that we could use Lemma [1] which expects finite hypothesis set H. Even though have far been thinking of the vector representations X as lookup tables, will be more convenient here to think of them as lists of vectors. Specifically, assume that the objects and relations ordered arbitrarily. The hypothesis set will then be
a( d(()+1R]
represented as Hg- ||O|+ Hence, using 3). we obtain [Hgl S ((2DV))/p) from Lemma 10 we have:
Then
G In (2e) H.
E
sup
((X E[L(X < My
(4)
xeB
2
Using the bound on [Hs), bound the r.h.s. by:
G G*|d([0) + [R]) In
4nDva P
M
(5)
2
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 relation ||x, x/1 I p where x, and x,, are vector representations from X and X', respectively. Now, optimizing over the hypothesis set Hx of all possible vector representations from A' instead of just the vectors from the set Hs. would
15

---

Under review as a conference paper at ICLR 2020
yield the next bound:
E
sup L.
[L(X9) - -(
E
sup X'E XEH(X)) [T(X(9) -[
sup
+ + E (
< E
sup X'E XEH(X))
sup
[X(Xg) - -(11)) -
+ sup X XEX(X')
sup
[E[L(X - B(
supp
sup
( 1(
+
sup
9) - E|L(X
E XEH(X))
X'EHs
sup sup X'EHo XEH(X))
|BL
EI
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 = x and after simplifying, this gives us the following
bound:
( + (R]) In (4eDK]0lVa)
E sup [L(XI)) - E[Z(xI)]] ||0|| + M
2
$ 4|0|| M
For the expected error of normalized oog-iiklihood we then obtain
d (4eDK(Olvv
sup [NL(X]G) - EE [[N](())
- 0 + M
XEHx
O
10|
which finishes the proof of the theorem.
D PROOF OF THEOREM 3
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- aata-generating distribution induced by G" with the missingness parameter 5 and let Q denote the learned distribution. Let t E (0; 1 8) be a threshold for predicting which triples belong the knowledge graph. Finally, let FF be the set of incorrectly predicted triples, i.e. the set of all triples O x x O such that either G* and the probability of given by the learned distribution Q is smaller than t (false negatives) o & g" and the probability of T given by the learned distribution Q is greater equal to (false positives). Then the following holds for the cardinality of the set of incorrectly predicted triples F:
ln2
In2
F S max
- 5 1)3 KL(PIIQ).
212
2(1
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 I, y [0; 1]2 and (0)
axx y)² +
2 |x - yl.
4a
16

---

Under review as a conference paper at ICLR 2020
Proof of Theorem 3 We assume that all possible triples rh, r, E O R O ordered (arbi- trarily) and that Ta denotes the i-th triple from this set and = {1.2...., ( |R]. sampled from the data-generating distribution and G' be sampled from the learned model (i.e. the KG-distribution). We define binary random variables B, := 1 (T; E () and B == (T: E g')- Hence the complete vectors B (B1,... B,) and B' (Bi,-... B represent the knowledge graphs sampled from the data-generating and modelled distributions, respectively. We denote by PB and 1' the distributions of B and B'. Due to the independence properties the two distri- butions, the following holds: K KL [[BB PB.) Eiez (L(PB.l (L(PB.11PP) PB;) where PB, and PB; are the distributions of B, and B respectively.
Let g be
Next we bound the error that is made when classify all triples 7; with P 1] > t true (i.e. belonging to the knowledge graph) and the rest as false. We may notice that when misclassifying triple Ti, we must either have
P(B, 1] = 0 and PIB₁ = 1]
("false positive") or
P = = 1 and PIB = 1] <
("false negative"). Hence, if we denote by FP the set of triples for which we have false positive errors, must have for all
& P[B TEFP
Σ (I
=
P( = 1]])
TEFP
1 +a|P = = 1]]3 4a
TEFP
where the last inequality follows from Lemma 12
It follows that
IFPI-
t
Σ
alP[B; = P|B 1]1
4a
T.FP
Letting 1/(2t) yields the bound
|FP|
< F
Σ
PPB = - - PIB = 1|f.
(6)
T:EFP
Similarly for false negatives, if we denote by FN the set of triples for which we have false negative errors, must have for all a' 0:
Σ PP = P[B =1]
TEEFN
$ Σ ( ((
= - - -1()
BEEN 4a
Hence, we also have:
(A0'~ ( 4a' 811)
|FN].
a Σ
P[B. = 1 P
TEFN
Letting a' = 11(22 - 28 - 2t) gives us
JFA < (1-8 1)2
1
Σ
-1 1] P|B
TEFM
17

---

Under review as a conference paper at ICLR 2020
Next combine 6 and 7 and apply Pinsker's inequality:
+FPI+IFM
- 2
Σ
P[B; 1] PiB:
REFP
+
= -
Σ
(1
- t)²
TEEN
1
PPB
PB; ll +
1
Σ
1
PI - PB:
t2
(1- 5
- t)2
4
TEFP
TEEN
Σ
max
1
Σ
|PB. PR:lli
f2 (1 8 t)²
iET
In
In2
S max
K K PB Pt.).
(8)
2/ 2(1
8 1)2
This finishes the proof of this theorem.
E PROOF OF THEOREM 4
Theorem 4 Let G be ground-truth knowledge graph set of objects O and set of relations R. and let G be sampled by the data- mata-generattng distribution. Let X C Rd. Let Hx ("hypothesis class" ") denote the set of vector representations X. X C X101+TRI of the objects from O and relations from R. Let K, M, D be as in Theorem 2 and and 6 be as in Theorem 3 Let % E H.x be representation of objects and relations learned by maximizing the hog-likeldoodd L(X(g), i.e. X arg max L(X' 9). Finally, let X = arg maxge Hx [[ the sets of incorrectly predicted triples Fz, obtained using the KG-distribution with X:
(%.... .).. Then the following holds for
Fx
{
2n2 12
In
S max
1 R
(1
1)2
O
9-1
dln (4eDK)
KL 1012 R
+M
O
O
where (L(PI|(x-)) is the Bullback-Leible divergence of the data tatta-enerattng distribution P and the best possible representable distribution Pz..
Proof. Let G denote the knowledge graph sampled from the data-generating distribution and Px the learned distribution. For a fixed Xpxed: the following equality holds: K KT(P] Pxe..) H(P) + KI(P P 1 (X(* Next can define g(9") := arg ma L(Xlg'), substitute (G") for Xfaed
Er (Xe [9)] Then we also have K KT[(PI
Ey [L [X)ceel])
and take the expectation over graphs g', which are assumed to be sampled from the aata-generatinng distribution. This yields:
Bg (()))) KL Px Rg [ [
Next we can use Lemma 8.2 from Devroye et al. 2013) to bound the r.h.s.:
(L (9)] < 2Eg
sup |L(X(g') E[L(X.))
XEH.
Finally, we use the bound from Theorem to bound the r.h.s. of this inequality. Combining this with Theorem 3 finishes the proof.
F PROOF OF THEOREM 5
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-adiissibee distribution. Let Q
18

---

Under review as a conference paper at ICLR 2020
denote the learned distribution and let t (y;; - -) be threshold. Then the following holds for the cardinality of the set of incorrectly predicted triples F:
1n2
1n2
FF| S max
KL(P,
2( 2))
2(1 7 2
t)2 -
Proof. The proof of this theorem is very similar to the proof of Theorem important differences in bold.
We highlight the most
We assume that all possible triples r,, E E R O are ordered (arbitrarily) and that тı denotes the i-th triple from this set and I (1.2.... 1012 [R] Let be sampled from the distribution P and G' be sampled from the learned model (i.e. the KG-distribution), We define binary random variables B; = 1(T, 9) and B == 1( E 9)). Hence the complete vectors B = (Bi,..., Bx,) and B' (B').... (B,)) represent the knowledge graphs sampled from the distribution P, and the modelled distribution, respectively. We denote by PB and P/ the distribu- tions 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: where Pn; and Ps are the distributions of B& and B/,
KL(Pa]] P Eiez LLPPn, (P:)) respectively.
Next we bound the error that is made when classify all triples T; with P 1] > t as true (i.e. belonging to the knowledge graph) and the rest as false. We may notice that when misclassifying triple Tú we must either have
PIB; S y and P[B >
("false positive") or
PIB; = 1] 2 7 and PIB <t
("false negative").
The rest of differences w.Et. the proof of Theorem follows the differences highlighted so far in straightforward way (details follow below).
Hence, we denote by FP the set of triples T₁ for which we have false positive errors, we must have for all 0
#FPI < Σ
PIB =|
Σ (7+1P[B = =] P(B 1]])
TEPP
TEEP
Σ
-1
111?
4a
TEPP
where the last inequality follows from Lemma
12
It follows that
(1 (t-
1
|FP]
S
a P[B: 1] P[B 1]
40
TEPP
Letting 1/(2t - 27)) yields the bound
FP
Σ
P[B: 1] =1
( 71-
TEFP
Similarly for false negatives, if we denote by FW the set of triples for which have false negative enrors, must have for all a' > 0:
- (1-1111--1)
Σ P(B: 1| P[B =1]
TENN
( 1
$ Σ
+ - =1]
+
4a
TEFN
19

---

Under review as a conference paper at ICLR 2020
Hence, we also have:
FF (44' -7 -
sa' Σ
- 1]
-
4a
TENN
Letting a' = =1((2 - 27 - 2f) gives us
FF < 1
Σ
P
(10)
1)2
TEEN
Next, we combine and 10p and apply Pinsker's incquality:
1
Σ
PP = -| 1|
1]12
(t 7)²
TEFP
+ (1 7 t)2
Σ
P(B, = 1 P(B; 1]
TEENN
Σ Pl..B PB: li
1
Σ illpB. PB:ll
7)2 TEFP
71-7-th t)2
TrEN
1 max
Σ
PB. - Pay ll
(t- (1 -
IET
1n2
In2
S max
K (KL(PPl (11)
2(t - 7)2² 2(1 - t)²
This finishes the proof of this theorem.
G PROOF OF THEOREM
Theorem Let everything be as in Theorem 4 but assume a rrerealizabll setting. Then the following holds for the sets of incorrectly predicted triples Fx, obtained using the KG-distribution with X.
Fx [
S max {
1n2 (t (t- (1 (1- (1-t-a 7)2
1n2
}
9 } (10) +M |
dln (4cDK)OlVa
E
10
Proof. The proof of this theorem is practically identical to the proof of Theorem The only differ- ence is that in this proof we invoke Theorem linstead of Theorem
H THE LIPSCHITZ CONSTANT OF SIMPLE'S SCORING FUNCTION
In this section derive bound the Lipschitz constant K of the scoring function of SimplE Kazemi & Poole 2018) on bounded domain X' S 2d The scoring function of SimplE is
3
(X., Xr, xx)
x() where (x,y,z) = Σd Di=1 Tebs Let us denote X1 = X2, xx] x, X4, x X X2 X and r [h,, Xr, xt). Since the function (6(r) is
(x
differentiable everywhere, any K satisfying K [Vv(()) for all 3 will be Lipschitz constant for y on the bounded domain X.
Next compute the gradient of (r)) To simplify the notation, use x|i] to denote the i-th element of the vector x. We then have
Here we use d to denote the dimension of the vector representations used by Kazemi & Poole 2018 Since SimplE: defines two vectors for every object relation, the dimension in our formalism is 2d, hence
X C 2d
20

---

Under review as a conference paper at ICLR 2020
(v((r)
1
(1)(
(v)(r)
1
x,[0
x x
[i]
2 X x/
0x,
2
,x, [i]
0x [
(v)
1
(v)(r)
(v(r)
xXI
xX
x/1
xXII
2 x|1 x
0x|10
2
0x][1]
0x7
From this get
[[v(r)]]
Σ
(x,|)*- x| + x4, x11
M x [0] + x" x!I??
x x
1 4 (xx) (x/, x() + (x/
6
(x4, xx) +
sup ||x||
4 xex
Thus, get
[ S v6
sup ||x|| = K, xex
2
Let us now denote yı. 1y yr = y" yt = [''. and s = Yr. Yr. Then we have
- (s)] S K - +|| K (1|xa - ynll | - y- I1 |x yrll).
So K Li 2 supxex || 2 is indeed the Lipschitz constant that we need in order to be able to obtain generalization bounds using Theorems and
21


Reviews:
[{"review_id": "ryeKpGJiFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a study on bound of the number of the expected triples wrongly predicted by general graph embedding methods. The paper considers methods that follow the \"completely at random\" assumption and aim to maximize the likelihood (or minimize the log-loss).\n\nThe study considers the learning from positive and unlabelled data problem and theoretically demonstrates the correctness of the bounds on the number of triples that embedding methods can add during the completion of the knowledge graph.\n\nThe paper is well written, theorems and proofs seem to me to be mathematically sound and correct. To the best of my knowledge, I agree with the authors when they claim to be the first to inspect the problem to give bounds under the setting they have considered. However, I have to admit that I am not an expert on the problem, I am more aware of the practical part of this field and less aware of the theoretical part.\n\nHowever, I have carefully checked the validity of the analysis and I have not found any flawless or critical errors in the proofs. I would suggest removing aliases for |O|, |R|, etc. from the proofs as they do not simplify the formulas significantly.\n\nOther corrections:\n- on page 5 the word \"the\" is written twice in the sentence just before Theorem 2.\n- on page 7 C is defined as constant but C should be C_1. Also C_2 should be defined.\n- on page 7, in \"Lipschitz Continuity\" after the sentence \"Our result requires Lipschitz continuity\" there must be a full stop or the word Most must begin with a lowercase m.\n- on page 8 there is inside the Figure 1 (on the red line, near 1*10^4 number of objects in the domain |O|) a link to page 6 that should be removed.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "N/A"}, "extra_text": {}}, {"review_id": "Skgitzsg9B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nPros:\n- This work raises a novel problem, i.e., analyzing the theoretical generalization ability of existing KG embedding methods. \n- The paper is well motivated with clear writing and technically sound with rigorous formula derivation.\n\nCons:\n1) For KG construction, people usually collect/mine in a batch/incremental fashion in which each batch focuses on certain aspects. For example, one can collect some bio facts about Persons from Wikipedia, then collect some entertainment related facts from news. So in practice, \"``missing completely at random\" assumption may not hold for KG.\n\n2) The derivation is suitable for a class of KG models that maximize log-likelihood losses, while many KG embedding methods use margin-based loss functions. Although the authors mentioned \"``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'', more rigorous theoretical analysis is suggested to verify (or refine) the applicability of the proposed analysis \n\n3) It would be better to see more examples that applying the proposed analysis to different KG embedding methods, corresponding comparisons help to get a deeper understanding for existing KG embedding methods, and may shed further light on how to design a KG embedding method that achieves a good enough generalization with fewer model parameters.\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1emzi3atr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThis paper studied the knowledge completion problem from the viewpoint of statistical learning theory. More specifically, it formalized a knowledge graph completion problem as an estimation of the optimal embedding by assuming the canonical distribution derived from the embedding and derived the upper bound of misclassification rate of entities under the missing-completely-at-random assumption.\n\n\nDecision\n\nAlthough the formalization of knowledge graph completion problems is novel (to the best of my knowledge), there is much room for improvement in the organization of the paper. Therefore, I would recommend to reject the paper this time and to ask authors to revise the paper so that the paper is more accessible to researchers and engineers.\nThere are numerous existing works about the knowledge graph embedding problem and the knowledge graph completion problem using embeddings. However, few works have been done to justify these methods theoretically. This paper attempted to answer this question via statistical learning theorem perspectives. The theorems gave sufficient conditions in terms of the size of a knowledge graph and properties of embedding functions under which the misclassification rate goes to $0$. In this aspect, this paper gave insights into how we can give justifications to existing embedding methods.\nHowever,  I think it is hard for those who are not familiar with this field to follow the logic of the paper, as I write in detail in the following sections. I understand some people argue that the paper organization is not essential for how a paper contributes to science and technology. However, the accessibility to the paper is vital to promote technical communications in different fields. Also, I believe it is beneficial for the paper to maximize its value. Thus, I would ask the authors to polish the paper.\n\n\nSuggestions\n\n- Introduction \n\t- Please explain what knowledge graphs are in the introduction before explaining how knowledge graphs represent knowledge, or what problems of practically available knowledge graphs have.\n\t- I think it is a bit too casual and conversational to use wordings like \"Please bare in mind\" in papers.\n\t- I think it is helpful if the authors add a summary of theorems and its implication in the introduction to grasp the theoretical contributions the paper has made.\n- Section 6, Theorem 1\n\t- Please describe what is the probability of $P$ and with respect to which probability distribution $\\mathbb{E}$ takes the expectation.\n- Section 7\n\t- The authors claim that Pinsker's inequality plays a central role in deriving the upper bound for the ratio of wrongly predicted triples. However, we cannot know how the authors used the inequality unless we see the proof of Theorem 3, which is available in the appendix.\n\t- In Theorem 3, the definition of \"wrongly predicted triple\" is missing. I only find a description related to it in the proof of Theorem 3 in the appendix. Could you add the definition in the main part?\n- Section 8, Theorem 4\n\t- The statement of Theorem 4 says that $\\mathbb{X}$ is a learned representation. But it is not available in the main article how we obtain it. We know that the authors used the maximum-likelihood estimator if we read the proof of the theorem. The author should clarify it in the statement of the theorem.\n- Section 10\n\t- What does \"this\" mean in the title of the section?\n\t- In the initial reading, I could not understand the main point the authors want to address in the paragraph starting with Loss. I think authors can clarify the point by restructuring the paragraph.\n\n\nMinor comments\n\n- Section 2 and Section 6\n\t- The authors treated $\\mathbb{X}$, which is the set of vector representations of objects and relations, as a lookup table in Section 2.2 and reinterpreted it as the subset of $\\mathcal{X}^{|\\mathcal{O}|+|\\mathcal{R}|}$ in Section 6. I think we can simplify the description if we treat $\\mathbb{X}$ as the subset of $\\mathcal{X}^{\\mathcal{O} \\sqcup \\mathcal{R}} := \\{f: \\mathcal{O} \\sqcup \\mathcal{R} \\to \\mathcal{X} \\}$ and denote $\\mathbb{X}(o)$ as $x_o$ in short hand for a representation $\\mathbb{X}$ and an object $o\\in \\mathcal{O}$ (and similarly for $x_r$).\n- Section 4\n\t- It would be helpful to make the correspondence explicit between each sentence and theorem later in the last paragraph. For example, \"We prove a generalization bound for log-likelihood from which a bound on Kullback-Leibler divergence follows (Theorem 3)\" or something like that. - Section 6, Theorem 1\n\t- The definitions of $\\mathbb{X}_o$ and $\\mathbb{X}_r$ are missing, if I do not miss something.\n\t- It is better to add the assumption that $\\sup_{h, r, t} |\\psi(x_h, x_r, x_t)|$ is finite.\n- Section 12\n\t- \"simplistic\" means too simple by itself. So, \"too simplistic\" should be \"too simple\" or \"simplistic\".\n\n\nQuestions\n\n- Section 4\n\t- I could not fully understand the intuition of the proof in the second paragraph. The authors think that the situation is desirable if multiple knowledge graphs are available. However, in the first approach, they concatenated the graphs into one (I interpreted the union of graphs as $\\widehat{\\mathcal{G}}_1 \\cup \\widehat{\\mathcal{G}}_2 \\cup \\cdots \\widehat{\\mathcal{G}}_n$. Correct me if I am wrong). Since this operation would reduce the situation to the single-graph case, we cannot take advantage of multiple graphs.\n- Section 7, Theorem 4\n\t- The upper bound is in terms of the estimator which maximizes the expected log-likelihood. I am wondering whether this estimator can achieve the best possible misclassification rate (i.e., $|\\mathcal{F}/|\\mathcal{O}^2|/|\\mathcal{R}||$). I understand that it minimizes the discrepancy between the inferred distribution and the data generating distribution. But I am not sure it implies the least misclassification rate.\n\t- The small terms in the upper bound (i.e., first and second terms) depend on the number of objects $|\\mathcal{O}|$ and not on relations $|\\mathcal{R}|$. Since the role of $\\mathcal{O}^2$ and $\\mathcal{R}$ is symmetric mathematically (if I understand correctly), I feel it is weird that the additional terms do not necessarily go to zero when $\\mathcal{R}\\to \\infty$. I particular, I expected that the additonal small terms depend solely on $|\\mathcal{G}|=|\\mathcal{O}|^2|\\mathcal{R}|$.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a generalization error bound, which extends the results from PU learning, for the problem of knowledge graph completion. The authors assume a missing at random setting, and provide bounds on the triples (two nodes and an edge) that could be mistakes. Then the paper provides a maximum likelihood interpretation, as well as relations to existing knowledge graph completion methods. The problem setting is interesting, and the writing clear.

This discussion was extensive, with reviewers and authors following the spirit of ICLR and having a constructive discussion which resulted in improvements to the paper. However, there seems to be still some remaining improvements to be made in terms of clarity of presentation, as well as precision of the theoretical arguments.

Unfortunately, there are many strong submissions, and the paper as it currently stands does not satisfy the quality threshold of ICLR.
Decision: Reject