NEURAL VARIATIONAL INFERENCE FOR EMBEDDING KNOWLEDGE GRAPHS
Year: 2018

Abstract:
Recent advances in Neural Variational Inference allowed for a renaissance in latent variable models in a variety of domains involving high-dimensional data. In this paper, we introduce two generic Variational Inference frameworks for generative models of Knowledge Graphs; Latent Fact Model and Latent Information Model. While traditional variational methods derive an analytical approximation for the intractable distribution over the latent variables, here we construct an inference network conditioned on the symbolic representation of entities and relation types in the Knowledge Graph, to provide the variational distributions. The new framework can create models able to discover underlying probabilistic semantics for the symbolic representation by utilising distributions which permit training by back-propagation in the context of neural variational inference, resulting in a highly-scalable method. Under a Bernoulli sampling framework, we provide an alternative justification for commonly used techniques in large-scale stochastic variational inference, which drastically reduces training time at a cost of an additional approximation to the variational lower bound. The generative frameworks are flexible enough to allow training under any prior distribution that permits application of the re-parametrisation trick, as well as under any scoring function that permits maximum likelihood estimation of the parameters. Experimental results display the potential and efficiency of this framework by improving upon multiple benchmarks with Gaussian prior representations. Code publicly available on Github.

heading: 1 INTRODUCTION
text: In many fields, including physics and biology, being able to represent uncertainty is of crucial importance (Ghahramani, 2015). For instance, when link prediction in Knowledge Graphs is used for driving expensive pharmaceutical experiments (Bean et al., 2017), it would be beneficial to know what is the confidence of a model in its predictions. However, a significant shortcoming of current neural link prediction models (Dettmers et al., 2017; Trouillon et al., 2016a) – and for the vast majority of neural representation learning approaches – is their inability to express a notion of uncertainty.
Furthermore, Knowledge Graphs can be very large and web-scale (Dong et al., 2014) and often suffer from incompleteness and sparsity (Dong et al., 2014). In a generative probabilistic model, we could leverage the variance in model parameters and predictions for finding which facts to sample during training, in an Active Learning setting (Kapoor et al., 2007; Gal et al., 2017).(Gal & Ghahramani, 2016) use dropout for modelling uncertainty, however, this is only applied at test time.
However, current neural link prediction models typically only return point estimates of parameters and predictions (Nickel et al., 2016), and are trained discriminatively rather than generatively: they aim at predicting one variable of interest conditioned on all the others, rather than accurately representing the relationships between different variables (Ng & Jordan, 2001), however, (Gal & Ghahramani, 2016) could still be applied to get uncertainty estimates for these models. The main argument of this article is that there is a lack of methods for quantifying predictive uncertainty in a knowledge graph embedding representation, which can only be utilised using probabilistic modelling, as well as a lack of expressiveness under fixed-point representations. This constitutes a significant contribution to the existing literature because we introduce a framework for creating a family of highly scalable probabilistic models for knowledge graph representation, in a field where there has been a lack of this. We do this in the context of recent advances in variational inference, allowing the use of any prior
distribution that permits a re-parametrisation trick, as well as any scoring function which permits maximum likelihood estimation of the parameters.

heading: 2 BACKGROUND
text: In this work, we focus on models for predicting missing links in large, multi-relational networks such as FREEBASE. In the literature, this problem is referred to as link prediction. We specifically focus on knowledge graphs, i.e., graph-structured knowledge bases where factual information is stored in the form of relationships between entities. Link prediction in knowledge graphs is also known as knowledge base population. We refer to Nickel et al. (2016) for a recent survey on approaches to this problem.
A knowledge graph G , {(r, a1, a2)} ⊆ R × E × E can be formalised as a set of triples (facts) consisting of a relation type r ∈ R and two entities a1, a2 ∈ E , respectively referred to as the subject and the object of the triple. Each triple (r, a1, a2) encodes a relationship of type r between a1 and a2, represented by the fact r(a1, a2).
Link prediction in knowledge graphs is often simplified to a learning to rank problem, where the objective is to find a score or ranking function φΘr : E × E 7→ R for a relation r that can be used for ranking triples according to the likelihood that the corresponding facts hold true.

heading: 2.1 NEURAL LINK PREDICTION
text: Recently, a specific class of link predictors received a growing interest (Nickel et al., 2016). These predictors can be understood as multi-layer neural networks. Given a triple x = (s, r, o), the associated score φΘr (s, o) is given by a neural network architecture encompassing an encoding layer and a scoring layer.
In the encoding layer, the subject and object entities s and o are mapped to low-dimensional vector representations (embeddings) hs , h(s) ∈ Rk and ho , h(o) ∈ Rk, produced by an encoder hΓ : E → Rk with parameters Γ. Similarly, relations r are mapped to hr , h(r) ∈ Rk. This layer can be pre-trained (Vylomova et al., 2016) or, more commonly, learnt from data by back-propagating the link prediction error to the encoding layer (Bordes et al., 2013a; Nickel et al., 2016; Trouillon et al., 2016a).
The scoring layer captures the interaction between the entity and relation representations hs, ho and hr are scored by a function φΘ(hs,ho,hr), parametrised by Θ. Other work encodes the entity-pair in one vector (Riedel et al., 2013).
Summarising, the high-level architecture is defined as:
hs,ho,hr , h Γ(s),hΓ(o),hΓ(r)
φ(s, o, r) , φΘ(hs,ho,hr)
Ideally, more likely triples should be associated with higher scores, while less likely triples should be associated with lower scores.
While the literature has produced a multitude of encoding and scoring strategies, for brevity we overview only a small subset of these. However, we point out that our method makes no further assumptions about the network architecture other than the existence of an argument encoding layer.

heading: 2.2 ENCODING LAYER
text: Given an entity e ∈ E , the entity encoder hΓ is usually implemented as a simple embedding layer hΓ(e) , [Γ]e, where Γ is an embedding matrix (Nickel et al., 2016). For pre-trained embeddings, the embedding matrix is fixed. Note that other encoding mechanisms are conceivable, such as; recurrent, graph convolution (Kipf & Welling, 2016a;b) or convolutional neural networks (Dettmers et al., 2017).

heading: 2.3 DECODING LAYER: SCORING FUNCTIONS
text: DistMult DISTMULT (Yang et al., 2015) represents each relation r using a parameter vector Θ ∈ Rk, and scores a link of type r between (hs,ho,hr) using the following scoring function:
φΘ(hs,ho,hr) , 〈hs,ho,hr〉 , k∑ i=1 hs,iho,ihr,i,
where 〈·, ·, ·〉 denotes the tri-linear dot product.
ComplEx COMPLEX (Trouillon et al., 2016a) is an extension of DISTMULT using complex-valued embeddings while retaining the mathematical definition of the dot product. In this model, the scoring function is defined as follows:
φΘ(hr,hs,ho) , Re ( 〈hr,hs,ho〉 ) ,
,< Re (es) ,Re (er) ,Re (eo) > + < Im (es) ,Re (er) , Im (eo) > + < Re (es) , Im (er) , Im (eo) > − < Im (es) , Im (er) ,Re (eo) >
where hs,ho,hr ∈ Ck are complex vectors, x denotes the complex conjugate of x, Re (x) ∈ Rk denotes the real part of x and Im (x) ∈ Ck denotes the imaginary part of x.

heading: 3 GENERATIVE MODELS
text: Let D , {(τ1, y1), . . . , (τn, yn)} denote a set of labelled triples, where τi , 〈si, pi, oi〉, and yi ∈ {0, 1} denotes the corresponding label, denoting that the fact encoded by the triple is either true or false. We can assume D is generated by a corresponding generative model. In the following, we propose two alternative generative models.

heading: 3.1 LATENT FACT MODEL
text: In Figure 1’s graphical model, we assume that the Knowledge Graph was generated according to the following generative model. Let V , E ×R× E the space of possible triples. where τ , 〈s, p, o〉, and hτ , [hs,hp,ho] denotes the sampled embedding representations of s, o ∈ E and p ∈ R. Note that, in this model, the embeddings are sampled for each triple. As a consequence, the set of latent variables in this model isH , {hτ | τ ∈ E ×R× E}. The joint probability of the variables pθ(H,D) is defined as follows:
pθ(H,D) , ∏
(τ,yτ )∈D
pθ(hτ )p θ(yτ | hτ ) (1)
The marginal distribution over D is then bounded as follows, with respect to our variational distribution q: pθ(D) ≥ Eqφ [ log pθ(yτ | hτ ) ] −KL[qφ(hτ ) || pθ(hτ )] (2)
Proposition 1 As a consequence, the log-marginal likelihood of the data, under the Latent Fact Model, is bounded by:
log pθ(D) ≤ ∑
(τ,yτ )∈D
Eqφ [ log pθ(yτ | hτ ) ] −KL[qφ(hτ ) || pθ(hτ )] , ELBO (3)
Proof. We refer the reader to the Appendix 6 for a detailed proof LFM’s ELBO.
Assumptions: LFM model assumes each fact of is a randomly generated variable, as well as a mean field variational distribution and that each training example is independently distributed.

heading: 3.1.1 OPTIMISING THE ELBO
text: Note that this is an enormous sum over |D| elements. However, this can be approximated via Importance Sampling, or Bernoulli Sampling (Botev et al., 2017).
ELBO = ∑
(τ,yτ )∈D
Eqφ [ log pθ(yτ | hτ ) ] −KL[qφ(hτ ) || pθ(hτ )]
= ( ∑
(τ,yτ )∈D+ Eqφ
[ log pθ(yτ | hτ ) ] −KL[qφ(hτ ) || pθ(hτ )])
+ ( ∑
(τ,yτ )∈D− Eqφ
[ log pθ(yτ | hτ ) ] −KL[qφ(hτ ) || pθ(hτ )])
(4)
By using Bernoulli Sampling, ELBO can be approximated by: ELBO ≈ ∑
(τ,yτ )∈D
sτ bτ
( Eqφ [ log pθ(yτ | hτ ) ] −KL[qφ(hτ ) || pθ(hτ )] ). (5)
where pθ(sτ = 1) = bτ can be defined as the probability that for the coefficient sτ each positive or negative fact τ is equal to one (i.e is included in the ELBO summation). The exact ELBO can be recovered from setting bτ = 1.0 for all τ . We can define a probability distribution of sampling from D+ and D− – similarly to Bayesian Personalised Ranking (Rendle et al., 2009), we sample one negative triple for each positive one — we use a constant probability for each element depending on whether it is in the positive or negative set.
Proposition 2 The Latent Fact models ELBO can be estimated similarly using a constant probability for positive or negative samples, we end up with the following estimate:
ELBO ≈ ( ∑
(τ,yτ )∈D+
sτ b+
( Eqφ [ log pθ(yτ | hτ ) ] −KL[qφ(hτ ) || pθ(hτ )] ))
+ ( ∑
(τ,yτ )∈D−
sτ b−
( Eqφ [ log pθ(yτ | hτ ) ] −KL[qφ(hτ ) || pθ(hτ )] ))
(6)
where b+ = |D+|/|D+| and b− = |D+|/|D−|.

heading: 3.2 LATENT INFORMATION MODEL
text: In Figure 2’s graphical model, we assume that the Knowledge Graph was generated according to the following generative model. Let V , E ×R× E the space of possible triples.
Similarly, τ , 〈s, p, o〉, and hτ , [hs,hp,ho] denotes the sampled embedding representations of s, o ∈ E and p ∈ R. The set of latent entity variables in this model isHe , {he | e ∈ E} and the set
of latent predicate variablesHp , {hp | p ∈ R}. WithH = He ∪Hp. The joint probability of the variables pθ(H,D) is defined as follows:
pθ(H,D) , ∏ e∈E pθ(he) ∏ p∈R pθ(hp) ∏
(τ,yτ )∈D
pθ(yτ | hτ ) (7)
The marginal distribution over D is then defined as follows: pθ(D) , ∫ ∏
e∈E pθ(he) ∏ p∈R pθ(hp) ∏
(τ,yτ )∈D
pθ(yτ | hτ )dH (8)
Proposition 3 The log-marginal likelihood of the data, under the Latent Information Model, is the following:
log pθ(D) ≥ Eqφ [ log pθ(D | He,Hp) ] −KL[qφ(He) || pθ(He)]−KL[qφ(Hp) || pθ(Hp)] (9)
Proof. We refer the reader to the Appendix 6 for a detailed proof LIM’s ELBO.
Assumptions: LIM assumes each variable of information is randomly generated, as well as a mean field variational distribution and that each training example is independently distributed. This leads to a factorisation of the ELBO that seperates the KL term from the observed triples, making the approximation to the ELBO through Bernoulli sampling simpler, as the KL term is no longer approximated and instead fully computed.

heading: 3.2.1 OPTIMISING THE ELBO
text: Similarly to Section 3.1.1, by using Bernoulli Sampling the ELBO can be approximated by: ELBO ≈ ( ∑
(τ,yτ )∈D
sτ bτ
Eqφ [ log pθ(yτ | hτ ) ] )− ( ∑ e∈E KL[qφ(he) || pθ(he)] )
− ( ∑ p∈R KL[qφ(hp) || pθ(hp)] ). (10)
Which can be estimated similarly using a constant probability for positive or negative samples, we end up with the following estimate:
Proposition 4 The Latent Information Models ELBO can be estimated similarly using a constant probability for positive or negative samples, we end up with the following estimate:
ELBO ≈ ( ∑
(τ,yτ )∈D+
sτ b+
Eqφ [ log pθ(yτ | hτ ) ] ) + ( ∑ (τ,yτ )∈D− sτ b− Eqφ [ log pθ(yτ | hτ ) ] )
− ( ∑ e∈E KL[qφ(he) || pθ(he)] )− ( ∑ p∈R KL[qφ(hp) || pθ(hp)] ) (11)
where b+ = |D+|/|D+| and b− = |D+|/|D−|.

heading: 4 RELATED WORK
text: Variational Deep Learning has seen great success in areas such as parametric/non-parametric document modelling (Miao et al., 2017; Miao et al., 2016) and image generation (Kingma & Welling, 2013b). Stochastic variational inference has been used to learn probability distributions over model weights (Blundell et al., 2015), which the authors named "Bayes By Backprop". These models have proven powerful enough to train deep belief networks (Vilnis & McCallum, 2014), by improving upon the stochastic variational bayes estimator (Kingma & Welling, 2013b), using general variance reduction techniques.
Previous work has also researched word embeddings within a Bayesian framework (Zhang et al., 2014; Vilnis & McCallum, 2014), as well as researched graph embeddings in a Bayesian framework
(He et al., 2015). However, these methods are expensive to train due to the evaluation of complex tensor inversions. Recent work by (Barkan, 2016; Bražinskas et al., 2017) show that it is possible to train word embeddings through a variational Bayes (Bishop, 2006) framework.
KG2E (He et al., 2015) proposed a probabilistic embedding method for modelling the uncertainties in KGs. However, this was not a generative model. (Xiao et al., 2016) argued theirs was the first generative model for knowledge graph embeddings. However, their work is empirically worse than a few of the generative models built under our proposed framework, and their method is restricted to a Gaussian distribution prior. In contrast, we can use any prior that permits a re-parameterisation trick — such as a Normal (Kingma & Welling, 2013a) or von-Mises distribution (Davidson et al., 2018).
Later, (Kipf & Welling, 2016b) proposed a generative model for graph embeddings. However, their method lacks scalability as it requires the use of the full adjacency tensor of the graph as input. Moreover, our work differs in that we create a framework for many variational generative models over multi-relational data, rather than just a single generative model over uni-relational data (Kipf & Welling, 2016b; Grover et al., 2018). In a different task of graph generation, similar models have been used on graph inputs, such as variational auto-encoders, to generate full graph structures, such as molecules (Simonovsky & Komodakis, 2018; Liu et al., 2018; De Cao & Kipf, 2018).
Recent work by (Chen et al., 2018) constructed a variational path ranking algorithm, a graph feature model. This work differs from ours for two reasons. Firstly, it does not produce a generative model for knowledge graph embeddings. Secondly, their work is a graph feature model, with the constraint of at most one relation per entity pair, whereas our model is a latent feature model with a theoretical unconstrained limit on the number of existing relationships between a given pair of entities.

heading: 5 EXPERIMENTS
text: EXPERIMENTAL SETUP
We run each experiment over 500 epochs and validate every 50 epochs. Each KB dataset is separated into 80 % training facts, 10% development facts, and 10% test facts. During the evaluation, for each fact, we include every possible corrupted version of the fact under the local closed world assumption, such that the corrupted facts do not exist in the KB. Subsequently, we make a ranking prediction of every fact and its corruptions, summarised by mean rank and filtered hits@m.
During training Bernoulli sampling to estimate the ELBO was used, with linear warm-up (Bowman et al., 2016; Davidson et al., 2018), compression cost (Blundell et al., 2015), ADAM (Kingma & Ba, 2014) Glorot’s initialiser for mean vectors (Glorot & Bengio, 2010) and variance values initialised uniformly to embedding size−1. We experimented both with a N (0, 1) and a N (0, embedding size−1) prior on the latent variables.
Table 1 shows definite improvements on WN18 for Variational ComplEx compared with the initially published ComplEX. We believe this is due to the well-balanced model regularisation induced by the zero mean unit variance Gaussian prior. Table 1 also shows that the variational framework is outperformed by existing non-generative models, highlighting that the generative model may be better suited at identifying and predicting symmetric relationships. WordNet18 (Bordes et al., 2013b) (WN18) is a large lexical database of English. WN18RR is a subset with only asymmetric relations. FB15K is a large collaboratively made dataset which covers a vast range of relationships and entities, with FB15K-257 (Toutanova & Chen, 2015), with 257 relations — a significantly reduced number from FB15K due to being a similarly refined asymmetric dataset. We now compare our model to the previous state-of-the-art multi-relational generative model TransG (Xiao et al., 2016), as well as to a previously published probabilistic embedding method KG2E (similarly represents each embedding with a multivariate Gaussian distribution) (He et al., 2015) on the WN18 dataset. Table 2 makes clear the improvements in the performance of the previous state-of-the-art generative multi-relational knowledge graph model. LFM has marginally worse performance than the state-of-the-art model on raw Hits@10. We conjecture two reasons may cause this discrepancy. Firstly, the fact the authors of TransG use negative samples provided only (True negative examples), whereas we generated our negative samples using the local closed world assumption (LCWA) . Secondly, we only use one negative sample per positive to estimate the Evidence Lower Bound using Bernoulli sampling, whereas it is likely they used significantly more negative samples.
5.0.1 LINK PREDICTION ANALYSIS
Section 5.1 and Section 5.2 explores the predictions made by Latent Information Model with ComplEx scoring function, trained with Bernoulli sampling to estimate the ELBO on the WN18RR dataset, then Section 5.3 will analyse the values of embeddings learnt for this task. Lastly, Section 5.3.1 will perform an extrinsic evaluation on learnt embedding representations for the more accessible to interpret Nations dataset.
We split the analysis into the predictions of subject ((?, r, o)) or object ((s, r, ?)) for each test fact. Note all results are filtered predictions, i.e., ignoring the predictions made on negative examples generated under LCWA — using a randomly corrupted fact (subject or object corruption) as a negative example.

heading: 5.1 SUBJECT PREDICTION
text: Table 3 shows that the relation "_derivationally_related_form", comprising 34% of test subject predictions, was the most accurate relation to predict for Hits@1 when removing the subject from the tested fact. Contrarily, "_member_of_domain_region" with zero Hits@1 subject prediction, making up less than 1% of subject test predictions. However, "_member_meronym " was the least accurate and prominent (8% of the test subject predictions) for subject Hits@1. We learn from this that even for a near state-of-the-art model there is a great deal of improvement to be gained among asymmetric modelling.

heading: 5.2 OBJECT PREDICTION
text: Table 4 displays similar results to Table 3, as before the relation "_derivationally_related_form" was the most accurate relation to predict Hits@1. Table 4 differs from Table 3 as it highlights the Latent Information Model’s inability to achieve a high Hits@1 performance predicting objects for
the "_hypernym" relation, which is significantly hindering model performance as it is the most seen relation in the test set— its involvement in 40% of object test predictions.

heading: 5.3 EMBEDDING ANALYSIS
text: These results hint at the possibility that the slightly stronger results of WN18 are due to covariances in our variational framework able to capture information about symbol frequencies. We verify this by plotting the mean value of covariance matrices, as a function of the entity or predicate frequencies (Figure 3). The plots confirm our hypothesis: covariances for the variational Latent Information Model grows with the frequency, and hence the LIM would put a preference on predicting relationships between less frequent symbols in the knowledge graph. This also suggests that covariances from the generative framework can capture genuine information about the generality of symbolic representations.

heading: 5.3.1 EXTRINSIC EVALUATION: VISUAL EMBEDDING ANALYSIS
text: We project the high dimensional mean embedding vectors to two dimensions using Probabilistic Principal Component Analysis (PPCA) (Tipping & Bishop, 1999) to project the variance embedding vectors down to two dimensions using Non-negative Matrix Factorisation (NNMF) (Févotte & Idier, 2011). Once we have the parameters for a bivariate normal distribution, we then sample from the bivariate normal distribution 1,000 times and then plot a bi-variate kernel density estimate of these samples. By visualising these two-dimensional samples, we can conceive the space in which the entity or relation occupies. We complete this process for the subject, object, relation, and a randomly sampled corrupted entity (under LCWA) to produce a visualisation of a fact, as shown in Figure 4.
Figure 4 displays three true positives from test time predictions. The plots show that the variational framework can learn high dimensional representations which when projected onto lower (more interpretable) dimensions, the distribution over embeddings are shaped to occupy areas at which true facts lie.
Figure 4 displays a clustering of the subject, object, and predicate that create a positive (true) fact. We also observe a separation between the items which generate a fact and a randomly sampled (corrupted) entity which is likely to create a negative (false) fact. The first test fact "(USA, Commonbloc0,
Netherlands)" shows clear irrationality similarity between all objects in the tested fact, i.e. the vectors are pointing towards a south-east direction. We can also see that the corrupted entity Jordan is quite a distance away from the items in the tested fact, which is good as Jordan does not share a common bloc either USA or Netherlands. We used scoring functions which measure the similarity between two vectors, however, for more sophisticated scoring functions which distance/ similarity is not important to the end result we would unlikely see such interpretable images. This analysis of the learnt distributions is evidence to support the notion of learnt probabilistic semantics through using this framework.

heading: 5.4 CONCLUSION
text: We have successfully created a framework allowing a model to learn embeddings of any prior distribution that permits a re-parametrisation trick via any score function that permits maximum likelihood estimation of the scoring parameters. The framework reduces the parameter by one hyperparameter — as we typically would need to tune a regularisation term for an l1/ l2 loss term, however as the Gaussian distribution is self-regularising this is deemed unnecessary for matching state-ofthe-art performance. We have shown, from preliminary experiments, that these display competitive results with current models. Overall, we believe this work will enable knowledge graph researchers to work towards the goal of creating models better able to express their predictive uncertainty.

heading: 6 FURTHER WORK
text: The score we acquire at test time even through forward sampling does not seem to differ much compared with the mean embeddings, thus using the learnt uncertainty to impact the results positively is a fruitful path. We would also like to see additional exploration into various encoding functions, as we used only the most basic for these experiments. We would also like to see more research into measuring how good the uncertainty estimate is.

heading: ACKNOWLEDGMENTS
text: We would like to thank all members of the Machine Reading lab for useful discussions.

Review summaries:
This work proposed two variational embedding methods for knowledge graph inference tasks. The experiments show slight improvements compared to other variational embedding methods, e.g., KG2E, TransG, and slight improvement on the WN18 dataset compared with the non-variational method. On the other hand, both the embedding method and the training of variational models used in this work are already well developed. Thus, this work doesn’t show too much novel contribution. However, the reviewer really appreciate the visualization provided in Fig. 4.