How to Turn Your Knowledge Graph Embeddings into Generative Models
Authors: Lorenzo Loconte
Nicola Di Mauro
Robert Peharz
Antonio Vergari
Venue: NeurIPS 2023 oral (2023)
Keywords: knowledge graph
knowledge graph embeddings
probabilistic circuits
probabilistic reasoning
tractable inference
TL;DR: We cast existing state-of-the-art knowledge graph embedding models into generative models that enable us to perform exact and efficient marginalisation, sampling and to integrate hard constraints with theoretical guarantees.

Abstract: Some of the most successful knowledge graph embedding (KGE) models for link prediction – CP, RESCAL, TuckER, ComplEx – can be interpreted as energy-based models. Under this perspective they are not amenable for exact maximum-likelihood estimation (MLE), sampling and struggle to integrate logical constraints. This work re-interprets the score functions of these KGEs as circuits – constrained computational graphs allowing efficient marginalisation. Then, we design two recipes to obtain efficient generative circuit models by either restricting their activations to be non-negative or squaring their outputs. Our interpretation comes with little or no loss of performance for link prediction, while the circuits framework unlocks exact learning by MLE, efficient sampling of new triples, and guarantee that logical constraints are satisfied by design. Furthermore, our models scale more gracefully than the original KGEs on graphs with millions of entities.

How to Turn Your Knowledge Graph Embeddings into Generative Models
Lorenzo Loconte
Nicola Di Mauro University of Bari, Italy nicola. dimauroluniba. it
University of Edinburgh, UK 1. loconte@sms.............s....... ed. ac
Robert Peharz
Antonio Vergari University of Edinburgh, UK avergari@ed ac uk
TU Graz, Austria
robert. peeert.peharzzturrazccoo
Abstract
Some of the most successful knowledge graph embedding (KGE) models for link prediction CP, RESCAL, TUCKER, COMPLEEX energy-based models. Under this perspective they are not amenable for exact maximum-likelihood estimation (MLE), sampling and struggle integrate logical constraints. This work re-interprets the score functions of these KGEs as circuits -constrained computational graphs allowing efficient marginalisation. Then, we design two recipes to obtain efficient generative circuit models by either restricting their activations to be non neg-ttetevve or squaring their outputs. Our interpretation comes with little or no loss of performance for link prediction, while the circuits framework unlocks exact learning by MLE, efficient sampling of new triples, and guarantee that logical constraints are satisfied by design. Furthermore, our models scale more gracefully than the original KGEs on graphs with millions of entities.
be interpreted
Introduction
Knowledge graphs (KGs) popular way represent structured domain information directed graphs encoded as collections of triples (subject, predicate, object), where subjects and objects (entities) are nodes in the graph, and predicates their edge labels. For example, the information that the drug "Ioxoprofen" interacts with the protein "COX2" is represented as a triple (loxoprofen, interacts, COX2) in the biomedical KG ogbl-biokg [32]. As real-world KGs often incomplete, are interested in performing reasoning tasks over them while dealing with missing information. The simplest reasoning task is link prediction [48], i... querying for the entities that are connected in KG by an edge labelled with certain predicate. For instance, we can retrieve all proteins that the drug "loxoprofen" interacts with by asking the query (loxoprofen, interacts,
Knowledge graph embedding (KGE) models are state-of-the-art (SOTA) models for link prediction [40, 56, 12] that map entities and predicates sub-symbolic representations, which are used assign a real-valued degree of existence to triples order to rank them. For example, the SOTA KGE model COMPLEX [65] assigns (loxoprofen, interacts, phosphoric-acid) and (loxoprofen, interacts. COX2) scores 2.3 and 1.3, hence ranking the first higher than the second in our link prediction example.
This simple example, however, also highlights some opportunities that missed by KGE models. First, triple scores cannot be directly compared across different queries and across different KGE models, they can be seen negative energies and not normalised probabilities over triples [41, 7, 6, 27, 43]. To establish a sound probabilistic interpretation and therefore have probabilities instead of scores that can be easily interpreted and compared [79], would need to compute the normalisation
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

KGE models
Circuits
GeKC's
CP RESCAL
CP
CP
Non-negative
RESCAL" TOCKER
RESCAL TULKER
PCs
restriction
COMPLEX
COMPLEY
COMPLEX
Squaring
Figure 1: Which KGE models can be used as efficient generative models of triples? The score functions of popular KGE models such as COMPLEX, CP, RESCAL and TUCKER can be easily represented as circuits (lilac). However, to retrieve a valid probabilistic circuit (PC, in orange) that encodes a probability distribution over triples (GeKCs) we need to either restrict its activations to be non-negative (in blue, see Section 4. or square it (in red, see Section 4.2).
constant (or partition function), which is impractical for real-world KGs due to their considerable size (see Section 2). Therefore. learning KGE models by maximum-ikcllhhod estimation (MLE) would be computationally infeasible, which is the canonical probabilistic way learn generative model over triples. A generative model would enable us to sample new triples efficiently, e.g., to generate a surrogate KG whose statistics are consistent with the original one or do data augmentation [9]. Furthermore, traditional KGE models do not provide a principled way to guarantee the satisfaction of hard constraints, which are crucial to ensure trustworthy predictions in safety-critica contexts such as biomedical applications. The result is that predictions of these models can blatantly violate simple constraints such as KG schema definitions. For instance, the triple that the SOTA COMPI. Ex ranks higher in our example above violates the semantics of "interacts", i.e., such predicate can only hold between drugs (c.g., loxoprofen) and proteins (c.g., COX2) but phosphoric-acid is not a protein.
Contributions. We show that KGE models that have become a de facto standard, such as COMPLEX and alternatives based on multilinear score functions [47, 40, 66]. can be represented as structured computational graphs, named circuits [13]. Under this light, i) we propose a different interpretation of these computational graphs and their parameters, to retrieve efficient and yet expressive probabilistic models over triples KG, which we name generative KGE circuits (GeKCs) (Section 4). We show that ii) not only GeKCs can be efficiently trained by exact MLE, but learning them with widely-used discriminative objectives [37, 40, 56, 12] also scales far better over large KGs with millions of entities. In addition, iii) we are able to sample new triples exactly and efficiently from GeKCs, and propose novel metric to measure their quality (Section 7.3). Furthermore, by leveraging recent theoretical advances in representing circuits [76], iv) we guarantee that predictions at test time will never violate logical constraints such as domain schema definitions by design (Section 5). Finally, our experimental results show that these advantages come with no or minimal loss in terms of link prediction accuracy.
2 From KGs and embedding models...
KGs and embedding models. A KG G is a directed multi-graph where nodes are entities and edges are labelled with predicates, i.e., elements of two sets E and R, respectively. We define g as a collection of triples (s, o) C & x R x E, where s, o denote the subject, predicate and object, respectively. A KG embedding (KGE) model maps a triple (s, (s,r,)) o) to real scalar via a score function Φ: & x R x E - IR. A common recipe to construct differentiable score functions for many the KGE models [56] to (i) map entities and predicates to embeddings of rank d, i.e., elements of normed vector spaces (e.g., Rd), and (ii) combine the embeddings of subject, predicate and object via multilinear maps. This is the case for KGE models such as CP [40], RESCAL [47], TUCKER [3], and COMPLEX [65] (see Fig. 2). For instance, the score function of COMPLEX [65] is defined as (XCOMMIFX((,, r, o) = Re( (e., Wy, e,)) where ex, W,, e, E Cd are the complex embeddings of subject, predicate and object, (-. ', .) denotes a trilinear product, denotes the complex conjugate operator and Re(-) the real part of complex numbers.
Probabilistic loss-derived interpretation. KGE models have been traditionally interpreted as based models (EBMs) [41, 7, 6, 27, 43]: their score function is assumed to compute the negative energy of a triple. This interpretation induces a distribution over possible KGs by associating Bernoulli variable, whose parameter is determined by the score function, to every triple [48]. Learning EBMs under this perspective requires using contrastive objectives [7, 48, 56), but several recent works observed that to achieve SOTA link prediction results one needs only to predict

---

subjects, objects [37, 40, 56] or more recently also predicates of triples [12], i.e., to treat KGEs as discriminative classifiers. Specificallyy they are learned by minimising categorical cross-entropy. e.g.. by maximising log 8, r) &f 8, 0) log Lo (x,, r, r,,") for object prediction. From
this perspective, we observe that we can recover an energy-bane -bargd interpretation if we assume there exist joint probability distribution p over three variables S R, O, denoting respectively subjects, predicates and objects. Written as a Boltzmann distribution, we have that p(S = 8, R = T. O = 0) = (exp ó(s, r, o))/2, where Z Egree St ErER Loree exp o(s', r', o') denotes the partition function. This interpretation is apparently in contrast with the traditional one over possible KGs [48]. We reconcile it with ours in Appendix E. Under this view, can reinterpret and generalise the recently introduced discriminative objectives [12] as a weighted pseudo- bog-likelihood (PLL) [70]
f1l (emooee Wa log (1,0) + wo log 8, + wr log p(r 5,
(I)
where ws; Way way E 1 can differently weigh each term, which is conditional log-probability that can be computed by summing out either 8, r or o, e.g., to compute log | s,r) above. Optimisation is usually carried out by mini-batch gradient ascent [56] and, given batch of triples B C G, we have
that exactly computing the PL.L objective requires time O(EE) |B] cost(()) and space O(EE) [B])
to exploit GPU parallelism [36],' where cost(ő) denotes the complexity of evaluating the e once.
Note that the PLL objective (Eq. (1)) is a traditional proxy for learning generative models for which it is infeasible to evaluate the -ikeenihodd estimation (MLE) objective*
LIEE := Σ E Eeerooee logp(s, o) = - log Z + Σ (amoeeg Hs,r,,).
(2)
In theory, evaluating log p(s. exactly can be done in polynomial time under our three- variable interpretation, as computing Z requires [(E) [ - cost(6)) time, but in practice this cost still prohibitive for real-world KGs. In fact, it would require summing over | x R x El evaluations of the score function é, which for FB15k-23 237 [62], the small fragment of Freebase [48], translates to -10 evaluations of Φ. This practical bottleneck hinders the generative capabilities of these models and their ability to yield normalised and interpretable probabilities. Next, we show how we can reinterpret KGE score functions as to retrieve a generative model over triples for which computing Z exactly can be done in time (((E)| + [R])- cos), making renormalisation feasible.
3 to Circuits...
In this section, we show that popular and successful KGE models such as CP, RESCAL, TUCKER
and COMPLEX (see Fig. 2 and Section 2), can be viewed as structured computational graphs that can, in principle, enable summing over all possible triples efficiently. Later, to exploit this efficient summation for marginalisation over triple probabilities, we reinterpret the semantics of these computational graphs as yield circuits that output valid probabilities. We start with the needed background about circuits and show that some score functions can be readily represented as circuits.
Definition (Cireuit [13, 76)). A circuit & is parametrized computational graph over variables X encoding function o () and comprising three kinds of computational units: input, product, and sum. Each product or sum unit n receives as inputs the outputs of other units, denoted with the set in(n). Each unit n encodes function ón defined as: (i) ln (sc(n) if n is an input unit, where 4n is function over variables sc(n) S X, called its scope, (ii) II IIgin()) di (sc(o))) if n is a product unit, and (iii)
Eisin(n) (sc()) if n is a sum unit, with 0: e IR denoting the weighted sum parameters. The scope of a product sum unit is the union of the scopes of its inputs, i.e., sc(nz) Usein(n) sc(i).
Fig. 2 and Fig. A.1 show examples of circuits. Next, we introduce the two structural properties that enable efficient summation and Prop. certifies that the aforementioned KGEs have these properties.
Definition (Smoothness and Decomposability). A circuit is smooth if for every sum unit n, its input units depend all on the same variables, i.e, Vi,j E in(n): sc(i) = sc(j). A circuit is decomposable if the inputs of every product unit n depend on disjoint sets of variables, i.e, vi,j E in(n)= + j: sc(i) O sc(j)= Ø0
I For large real- world KGs is reasonable to assume that |||
>
|
'I general, the PLL is recognised as proxy for MLE because, under certain assumptions, it is possible to show it can retrieve the MLE solution asymptotically with enough data [35].
3

---

(ox) W,, Gol
W.Co oe
T x1 X2
Re((e, w., w.,
COMPLEX
RESCAL
TUCKER
vec'7
vec W
Refe,) im(e.) Re(w.) Im( Re(e.) Imle.))
Figure 2: Interpreting the score functions of CP, RESCAL, TUCKER, COMPL.E as circuits over 2-dimensional embeddings. Input, product and sum units are coloured in purple, orange and blue, respectively. Output sum units are labelled with the score functions, and their parameters are assumed to be I, if not specified. The detailed construction is presented in Appendix A.I. Given a triple (s, r, o), the input units map subject s, predicate r and object o to their embedding entries. Then, the products are evaluated before the weighted sum, which oulputs the score of the input triple.
Proposition 1 (Score functions of KGE models as circuits). The computational graphs of the score functions & of CP, RESCAL, TUCKER and COMPLEX smooth and decomposable circuits over X = {S, R. O}. whose evaluation cost is (ō) E @(())), where [ø) denotes the number of edges in the circuit, also called its size. For example, the size of the circuit for CP is (écr| (d)).
Appendix A. reports the complete proof by construction for the score functions of these models and the circuit sizes, while Fig. illustrates them. Intuitively, since the score functions of the cited KGE models are based on products and sums operators, they can be represented as circuits where input units map entities and predicates into the corresponding embedding components (similarly to look-up tables). As the inputs of each sum unit product units that share the same scope {S, R, O} and fully decompose in their input units, they satisfy smoothness and decomposability (Def. 2).
Smooth and decomposable circuits enable summing over all possible (partial) assignments to X by (i) performing summations at input units over values in their domains, and (ii) evaluating the circuit once in feed-forward way [13, 76]. This re-interpretation of score functions allows to "push" summations to the input units of a circuit, greatly reducing complexity, as detailed in the following proposition.
Proposition (Efficient summations). Let ø be a smooth and decomposable circuit over X = {S, R. O} that encodes the score function of KGE model. The sum Eees ΣxeR Loes Φ(s, o) or any other summation over subjects, predicates objects can be computed in time ((((E) + [R)) (o)).
However, these sums are in logarithm space, as we have that p(s, r, o) xx exp o(s, (see Section 2). As a consequence, summation in this context does not correspond probability space. This drives us to reinterpret the semantics of these circuit structures as to operate directly in probability space, rather than in logarithm space, i.e., by encoding non-negative functions.
marginalising variables in
4 to Probabilistic Circuits
We now present how to reinterpret the semantics of the computational graphs of KGE score functions to directly output non-negative values for any input. That is, we cast them as probabilistic circuits (PCs) [13, 76, 19]. First, we define our subclass of PCs that encodes possibly unnormalised probability distribution over triples a KG, but allows for efficient marginalisation.
Definition 3 (Generative KGE circuit). A generative KGE circuit (GeKC) is a smooth and decom- posable PC &pe over variables X = {S, R, O} that encodes a probability distribution over triples, i.e., (pc(s, r, o) x p(s,r, r, o) for any (s, r. o) E E x
Since our GeKCs are smooth and decomposable (Def. 2) they guarantee the efficient computation of Z in time [[[[E] + [R]) -ppcl) (Prop. 2). This is in contrast with existing KGE models, for which it would require the evaluation of the whole score function on each possible triple (Section 2). For example, assume non-negative CP score function ( r, o)
(e,, wr, eo) E R, for some embeddings Cs, Wy. C. ddd Then, we can compute Z by pushing the outer summations inside the trilinear product, i.e., Z = (E.es Cs, ErER Wr. Eoes Co), which can be done in time ((E)) + (RI)- - d). the following sections, we propose two ways to turn the computational graphs of CP, RESCAL, TUCKER and COMPLEX into GeKCs without additional space requirements.

---

GPU Memory (GiB)
15
Time per batch (5)
0.6
COMPLEX COMPLEX COMPLEX
20
0.4
25
0.2
30
0.0
10a
10a
Batch size
10 Num. of entities
Figure 3: GeKCs scale better. Time (in seconds) and peak GPU memory (in GiB as bubble sizes) required for computing the PLL objective and back-propagatinn through it for single batch on ogbl-wikikg2, by increasing the batch size and number of entities. See Appendix C.4.3 for details.
4.1 Non-negative restriction of a score function
The most natural way of casting existing KGE models to GeKCs is by constraining the computational units of their circuit structures (Section 3) output non-negative values only. We will refer to this conversion method as the non-negative restriction of model. To achieve the non- non-negative restriction of CP, RESCAL and TUCKER we can simply restrict the embedding values and additional parameters in their score functions to be non-negative, as products and sums are operators closed R. Thus, each input unit over variables or O (resp. R) in a non-negen non-negative GeKC encodes function in (Def. 1) modelling an unnormalised categorical distribution over entities (resp. predicates). For example, each i-th entry Est the embedding e, E T associated to an entity parameter of the i-th unnormalised categorical distribution over S. See Fig. C.1 for an example. We denote the non non-negative restriction of these KGEs as CP*, RESCAL* and TUCKER* respectively.
& becomes a
However, deriving COMPLEX* [65] by restricting the embedding values of COMPLEX to be non- negative is not sufficient, because its score function includes subtraction as operates on complex numbers. To overcome this, we re- re-parameterise the imaginary part of each complex embedding to be always greater than or equal to its real part. Appendix C.2 details this procedure. Even if this reparametrisation allows for more flexibility, imposing non- non-negativity on GeKCs can restrict their ability to capture intricate interactions over subjects, predicates and objects given fixed number of learnable parameters [67]. We empirically confirm this in our experiments in Section 7. Therefore, we propose an alternative way of representing KGEs as PCs via squaring.
4.2 Squaring the score function
Squaring works by taking the score function of KGE model Φ, and multiplying it with itself to obtain 8² = Φ Φb. Note that ø² would guaranteed to be a PC, as always outputs non-negative values. The challenge is to represent the product of two circuits to guarantee efficient marginalisation (Prop. 2).² In general, this task is known to be #P-hard [76].
smooth and decomposable PC as
However, it can be done efficiently if the two circuits are compatible [76], as we further detail in Appendix B. Intuitively, the circuit representations of the score functions of CP, RESCAL, TUCKER and COMPLEX (see Fig. 2) are simple enough that every product unit is defined over the same scope {S, R. O} and fully decomposes on its input units. As such, these circuits can be easily multiplied with any other smooth and decomposable circuit, property also known as cmniicompatibility [76]. This property enables us to build the squared version of these KGE models, which we denote as CP² RESCAL.2, TUCKER2 and COMPL.EX3 as PCs that are still smooth and decomposable. Note that these squared GeKCs do allow for negative parameters, and hence can be more expressive. The next theorem, instead, guarantees that we can normalize them efficiently.
Theorem 1 (Efficient summations on squared GeKCs). Performing summations as stated in Prop. 2 on CP², RESCAL TUCKER² and COMPLEX² can be done in time (((E) [R]) (6]2).
For instance, the partition function Z of CP2 with embedding size d would require ((((E) + |R] ) )d)))
operations be computed, while a simple ferd-forward pass for a batch of B] triples still O B .d). While in this case marginalisation requires increase in complexity that is quadratic in d, it is still faster than the brute force approach to compute (see Section and Appendix C.4.1).
In fact, even though d² can be easily built by introducing a product unit over two copies of 6 as sub- circuits, the resulting circuit would be not decomposable (Def. 2). the sub-circuits are defined on the same scope.
5

---

Quickly distilling KGEs to squared GeKCs. Consider a squared GeKC obtained by initialising its parameters with those of its energy-based KGE counterpart. If the score function of the original KGE model always assigns non-negative scores to triples, then the "distilled"" squared GeKC will output the same exact ranking of the original model for the answers to any link prediction queries. Although the premise of the non-negativity of the scores might not be guaranteed, we observe that, in practice, learned KGE models do assign positive scores to all or most of the triples of common KGs (see Appendix D). Therefore, we can use this observation to either instantly distil a GeKC or provide good heuristic to initialise its parameters and fine-tune them (by MLE or PLL maximisation). In both cases, the result is that we can convert the original KGE model into GeKC that provides comparable probabilities, enable efficient marginalisaaton, sampling, and the integration of logical constraints with little or no loss of performance for link prediction (Section 7.1).
4.3 On the Training Efficiency of GeKCs
GeKCs also offer an unexpected opportunity to better scale the computation of the PLL objective (Eq. (1)) on very large knowledge graphs. This is because computing the PLL for batch of [B] triples with GeKCs obtained via non-negative restriction and by squaring (Sections 4.1 and 4.2) does not require storing a matrix of size O[[E] [B]) to fully exploit GPU parallelism [36]. For instance,
in Appendix C.4.2 we show that computing the PLL for CP [40] with embedding size d requires time O(EE) [B] d) and additional space O(E [B]). On the other hand, for CP² (resp. CP*) it requires
time (({ + BI) d') (resp. O([EE + BI) d)) and space O[ d). Table C.1 summarises similar reduced complexities for other instances of GeKCs, such COMPLEX* and COMPLEX? The reduced time and memory requirements with GeKCs allow us to use larger batch sizes and better scale to large knowledge graphs. Fig. 3 clearly highlights this when measuring the time and GPU memory required to train these models on a KG with millions of entities such as ogbl-wikikg2 [32].
4.4 Sampling new triples with GeKCs
GeKCs only allowing non- negative parameters, such as CP RESCAL* and TUCKER*, support ancestral sampling as sum units can be interpreted as marginalised discrete latent variables, similarly to the latent variable interpretation in mixture models [55, 53] (see Appendix C.3 for details). This is however not possible in general for COMPLEX* and GeKCs obtained by squaring, as negative parameters break this interpretation. Luckily, as these circuits still support efficient marginalisation (Prop. 2 and Thm. 1) and hence also conditioning, we can perform inverse transform sampling. That is, to generate triple (s, r, o). we can sample in autoregressive fashion, e.g., first s ~ p(S), then r p(R 8) and o ~ p(O 8, r), hence requiring only three marginalization steps.
5 Injection of Logical Constraints
Converting KGE models to PCs provides the opportunity "embed" logical constraints in the neural link predictor such that (i) predictions are always guaranteed to satisfy the constraints at test time, and (ii) training can still be done by efficient MLE (or PLL). This is in stark contrast with previous approaches for KGEs, which relax the constraints or enforce them only at training time (see Section 6). Consider, as an example, the problem of integrating the logical constraints induced by a schema of KG, i.e., enforcing that triples not satisfying a domain constraint have probability zero.
Definition 4 (Domain constraint). Given a predicate r E R and (r) ko(r) S E &the sets of all subjects and objects that are semantically coherent with respect to r,, domain constraint is propositional logic formula defined as
K, S E ks(r) AR= A ko(r) (Vuers())S u) ^ AR-
(Vuemo(r) v). (3)
Given R (ri...., [Tm] a set of predicates, the disjunction K = Kr v v... Krn, encodes all the domain constraints that are defined in a KG. An input triple (s, r,) o) satisfies K, written as (s, r. }= K, if E (r) and o E (r).. ). To design GeKCs such as their predictions always satisfy logical constraints (which might not be necessarily domain constraints), we follow Ahmed et al. [i] and define score function to represent a probability distribution px that assigns probability mass only to triples that satisfy the constraint K, i.e., Φpe(s, o)- cx(ss, o) x pk (x,,,T,,) o). Here, &pe is a GeKC and cx (s, r, o) = 11 [(s r, F= K) is an indicator function that ensures that zero mass assigned to triples violating K. In words, we are "cutting" the support of &pc. as illustrated in Fig. 4.

---

L((S, interacts, 0) 1 K)
cx(S, R, 0)
(0pe cx)(S, R,
$ Ds R = int O Ps
(S, interacts,
( R. 0)
Copa
Wist
int
S = M1
0
РK
loxoprofen, interacts, phosp-acid) = 0
Figure 4: Injection of domain constraints. Given a circuit encoding domain constraints and GeKC Ope. the probability assigned by the product circuit &pe - сg to the inconsistent triple showed in Section 1 is O, and positive probability is assigned to consistent triples only, e.g., for the interacts predicate those involving drugs (Ds) as subjects and proteins (Ps) as objects. Best viewed in colours.
Computing pk (K(8, vr,) exactly but naively would require computing new partition function Zx Eves LneR Eo'ge (Øpe r', o') ")- (s(ss'r' "'ss,,'," o'),, which is impractical as previously discussed smooth and decomposable eircuit, sometimes called (Section 2). Instead, we compile Cg
constraint or logical circuit [19, 1]. by leveraging compilers from the knowledge compilation literature [18, 52]. In a nutshell, ск another circuit over variables S, R, O that outputs if an input triple satisfies the encoded logical constraint K and 0 otherwise. See Def. A.2 for a formal definition of such circuits. Then, similarly to what we have showed for computing squared circuits that enable efficient marginalisation (Section 4.2), the satisfaction of compatibility between GeKC Φpe and a constraint circuit сg enable us to compute Zx efficiently. as certified by the following theorem.
Theorem 2 (Tractable integration of constraints in GeKCs). Let ск be a constraint eircuit encoding a logical constraint K over variables {S, R, O}. Then exactly computing the partition function Zx of the product (pc(s, r. o) Cx (s, r. 0) Xx pK (8, r, o) for any GeKC &be derived from CP, RESCAL, TUCKER or COMPL.EX (Section 4) can be done in time (((E) + [R]) |0pel |cx|).
In Prop. A. we show that the compilation of domain constraints K (Def. 4) is straightforward and results in constraint circuit eœ having compact size. For example, the size of the constraint circuit encoding the domain constraints of ogbl-biokg is approximately |cx| = 307 103 in perspective, the size of the circuit for COMPLEX with embedding size 1000 is the much larger 375 - 10 Since |cx| is much smaller, by the same argument on the efficiency of GeKCs obtained via squaring (Section 4.3) results that the integration of logical constraints adds negligible overhead.
To put this number
Related Work
SOTA KGEs and current limitations. A plethora of ways to represent and learn KGEs has been proposed, see [31] for a review. KGFs such as CP and COMPL.E are still the de facto go-to choices in many applications [5, 56, 12]. Works performing density estimation in embedding space [78, 11] can sample embeddings, but to sample triples one would need to train decoder. Several works try to modify training for KGEs as to introduce a penalty for triples that do not satisfy given logical constraints [8, 39, 34, 42, 23, 30], or casting it as a min-max game [44]. Unlike our GeKCs (Section 5), none of these approaches guarantee that test-time predictions satisfy the constraints. Moreover, several heuristics have been proposed to calibrate the probabilistic predictions of KGE models ex-poxt [61, 79]. As showed in [64], the triple distribution can be modelled autoregressively as p(S, R, 0) = p(S) p(O 5) p(R S, O) where each conditional distribution is encoded by neural network. However, differently from our GeKCs, integrating constraints exactly or computing any marginal (thus conditional) probability is inefficient. KGE models based on non-negative tensor decompositions [63] are equivalent to GeKCs obtained by non-negative restriction (Section 4)1,, but are generally trained by minimizing different con-pobaaiilistic losses.
Circuits. Circuits provide a unifying framework for several tractable probabilistic models such sum- num-product networks (SPNs) and hidden Markov models, which are smooth and decomposable
7

---

FB15k-237
WN18RR
ogbl-biokg
Table I: GeKCs are competitive with their energy-based counterparts. Best average test MRRs of CP. COMPLEX and GeKCs trained with the PLL and MLE objectives (Eqs. (1) and (2)). For standard deviations and training times see Table F.2.
Model
PLI
MLE
PLI
MLB
PLI
MLE
CP
0.310
0.105
0.831
CP'
0.237
0.230
0.027
0.026
0.496
0.501
Cp²
0.315
0.282
0.104
0.091
0.848
0.829
COMPLEX
0.342
0.471
0.829
COMPLEX*
0.214
0.205
0.030
0.029
0.503
0,516
COMPLEX2
0.334
0.300
0.420
0.391
0.858
0.840
PCs [13], well compact logical representations [19, 1J. See [75, 13, 17] for overview. PCs with negative parameters are also called non-monoto [58], but are surprisingly not as well investigated as their monotonic counterparts. i.c., PCs with only non-negative parameters. least from the learning perspective, Similarly to our construction for COMPLEX* (Appendix C.2), Dennis [20] constrains the output of the non-monotonic sub-cireuits of larger PC to be less than their monotonic counterparts. Squaring a circuit has been investigating for tractably computing several divergences [76] and is related to the Born-rule of quantum mechanics [51].
Circuits for relational data. Logical circuits to compile formulas in first-order logic (FOL) [25] have been used to reason over relational data, e.g. via exchangeability [68, 49]. Other formalisms such as tractable Markov Logic [77], probabilistic logic bases [50], relational SPNs [46, 45] and generative clausal networks [71] use underlying circuit-like structures to represent probabilistic models over tractable fragment of FOL formulas. These works assume that every atom in a grounded formula is associated to random variable, also called the possible world semantics in probabilistic logic programs [57] and databases (PDBs) [14]. In this semantics, TractOR [26] casts answering complex queries over KGEs to performing inference in PDBs. Differently from these works, our GeKCs are models defined over only three variables (Section 2). In Appendix E we reconcile these two semantics by interpreting the probability of a triple to be proportional that of all KGs containing
Empirical Evaluation
We aim to answer the following research questions: RQ1) are GeKCs competitive with commonly used KGEs for link prediction? RQ2) Does integrating domain constraints in GeKCs benefit training and prediction?; RQ3) how good are the triples sampled from GeKCs?
7.1 Link Prediction (RQ1)
Experimental setting. We evaluate GeKCs on standard KG benchmarks for link prediction :
FB15k-237 [62], WN18RR [21] and ogbl-biokg [32], whose statistics can be found in Appendix F.1. As usual [48, 56, 54], we assess the models for predicting objects (queries (s, r. ?)) and subjects (queries (?, o)), and report their mean reciprocal rank (MRR) and fraction of hits at k (Hits @ k) (see Appendix F.2). We remark that our aim in this Section is not to score the new state-of-the-on link prediction performance on these benchmarks. Instead, we aim to rigorously assess how close GeKCs can be to commonly used and reasonably tuned KGE models. We focus on CP and COMPLEX as they currently are the go-to models of choice for link prediction [40, 56, 12]. We compare them against our GeKCs CP*, COMPLEX* CP2 and COMPLEX² (Section 4). Appendix F.4 collects all the details about the model hyperparameters and training for reproducibility.
Link prediction results. Table 1 reports the MRR and times for all benchmarks and models when trained by PLL or MLE. First, CP2 and COMPLEX² achieve competitive scores when compared to CP and COMPLEX. Moreover, CP2 (resp. COMPLEX2) always outperforms CP* (resp. COMPLEX*), thus providing empirical evidence that negative embedding values are crucial for model expressiveness. Concerning times, Table F.2 shows that squared GeKCs can train much faster on large KGs (see Section 4.3): CP2 and COMPLEX² require less than half the training time of CP and COMPLEX on ogbl-biokg, while also unexpectedly scoring the current SOTA MRR on it. 5 We experiment also on the much larger ogbl-wikikg2 KG [32], comprising millions of entities. Even more remarkably, we are
1 'Code available at https: / //tpt/gttttt.t////// com/ apr il towlooollaaoooo /ggk//...c.... AAcross non-ensemble methods and according to the OGB leaderboard, updated at the time of this writing.
8

---

Embedding size
Model
A:
10
50
200
1000
99.68
99.90
99.93
99.94
Test MRR
COMPLEX
20
99.81
99.79
99.85
99.91
0.7
100
99.60
99.44
99.60
99.77
82.50
94.22
99.30
99.50
COMPLEX
COMPLEX²
20
86. 50
96. 70
99.42
99.64
COMPLEX
100
90.66
97.71
99.23
98.78
D-COMPLEX
100,00
100.00
100,00
100,00
D-COMPLEX
20
100.00
100.00
100,00
100,00
10a
10a
10
100
100.00
100.00
100.00
100.00
Embedding size
Figure 5: GeKCs with domain constraints guarantee domain-consisten predictions. Semantic consistency scores (Sem @ k) [33] on ogbl-biokg achieved by COMPLEX, COMPLEX² and its inte- gration with domain constraints (D-COMPLEX: (left), and MRRs computed on test queries (right). COMPLEX infers 200+ triples violating constraints as the highest scoring completions
1).
able to score an MRR of 0.572 after just -3 hours with COMPLEX² trained by PLL with a batch size of 10t and embedding size d 100. To put this in context, we were able to score 0.562 with the best configuration of COMPLEX but after- -3 days, as we could not fit in memory more than a batch size 500. The same trends are shown for the Hits @k (Table F.3) and likelihood (Table F.4) metrics.
Distilling GeKCs.
Table F.5 reports the results achieved by CP² and COMPLEX² initialised with the parameters of learned CP and COMPLEX (see Section 4.2) and confirms we can quickly turn an EBM into GeKC, thus inheriting all the perks of being a tractable generative model.
Calibration study. We also measure how well calibrated the predictions of the models in Table 1 are, which is essential to ensure trustworthiness in critical tasks. For example, given a perfectly calibrated model, for all the triples predicted with probability of 80%, exactly 80% of them would actually exist [79]. On all KGs but WN18RR, GeKCs achieve lower empirical calibration errors [29] and better calibrated curves than their counterparts, as we report in Appendix F.5.3. The worse performance of all models on WN18RR can be explained by the distribution shift that exists between its training and test split, which we better confirm in Section 7.3.
7.2 Integrating Domain Constraints (RQ2)
We focus on ogbl-biokg [32], as it contains the domain metadata for each entity (i.e., disease, drug, function, protein, or side effect). Given the entity domains allowed for each predicate, we formulate domain constraints in Def. 4. First, want estimate how likely the models to predict triples that do not satisfy the domain constraints. We focus on COMPLEX and COMPLEX², as they have been shown to achieve the best results in Section 7.1 and introduce D- D-COMPLEX
the constraints- aware version of COMPL.Ex (Section 5). For each test query (s, ?) (resp. (?,r, o)). we compute the Sem @ k score [33] the average percentage of triples in the first k positions of the rankings of potential object (resp. subject) completions that satisfy the domain constraints (see Appendix F.2).
Fig. 5 highlights how both COMPLEX and COMPLEX² systematically predict object (or subject) completions that violate domain constraints even for large embedding sizes. For instance, a Sem score of 99% (resp. 99.9%) means that ~3200 (resp. -320) predicted test triples violate domain constraints. While for COMPLEX and COMPLEx² there is no theoretical guarantee of consistent predictions with respect to the domain constraints, D- D-COMPLEX* always guarantee consistent predictions by design. Furthermore, we observe a significant improvement in terms of MRR when integrating constraints for smaller embedding sizes, as reported in Fig. 5.
7.3 Quality of sampled triples (RQ3)
Inspired by the literature on evaluating deep generative models for images, we propose metric akin to the kernel Inception distance [4] to evaluate the quality of the triples we can sample with GeKCs.
Definition 5 (Kernel triple distance (KTD)). Given IP, Q two probability distributions over triples, and positive definite kernel k: A& x h + IR we define the kernel triple distance KTD(P, Q) as
A smaller (d = 50) and highly tuned version of COMPLEX achieves 0.639 MRR but still after days [12].

---

Model
FB15k-237
WN18RR
ogbl-biokg
Table 2: GeKCs trained by MLE generate new likely triples. Empir- ical KTD scores between test triples and triples generated by baselines and GeKCs trained with the PLL ob- jective or by MLE (Eqs. (1) and (2)). Lower is better. For standard devia- tions see Table F.6.
Training
0.055
0.260
0.029
Uniform
0.589
0.766
1.822
NNMFAug
0.414
0.607
0.518
PLL
MLE
PLL
MLE
PLL
MLE
CP
0.404
0,433
0.633
0.578
0.966
0.738
CP
0.253
0.070
0.768
0.768
0.039
0,017
COMPLEX*
0.336
0.323
0.456
0.478
0.175
0.097
COMPLEX²
0.326
0.102
0.338
0.278
0.104
0.034
the squared maximum mean discrepancy [28] between triple latent representations obtained via map 3 + RR that projects triples to an h-dimensiioal embedding, i.e.
wh: & x R
x
KTD P. = Ee (bb(()) (/(x'))))))))) + F (v)),, (v/1)) - P. (k((()))))))))))))))))))())))( (v)))
An empirical estimate of the KTD score close to zero indicates that there little difference between the two triple distributions P and Q (see Appendix F.3). For images, v is typically chosen as the last embedding a SOTA neural classifier. We choose & to be the Le-normed outputs the product units of circuit [73, 74], specifically the SOTA COMPLEX learned by Chen et al. [12] with / 4000. We choose & as the polynomial kernel k(x, y) = (x y + 1)², following Binkowski et al. [4].
Table 2 shows the empirical KTD scores computed between the test triples and the generated ones, and Fig. F.1 visualises triple embeddings. We employ two baselines: uniform probability distribution over all possible triples and NNMFAug [9], the only work to address triple sampling to the best of our knowledge. We also report the KTD scores for training triples as an empirical lower bound. Squared GeKCs achieve lower KTD scores with respect to the ones obtained by non-negative restriction, confirming again better estimation of the joint distribution. In addition, they achieve lower KTD scores than all competitors when learning by MLE (Eq. (2)), which justifies its usage an objective. Lastly, we confirm the distribution shift on WN18RR: training set KTD scores are far from zero, but even in this challenging scenario, COMPLEX² scores KTD values that are closer to the training ones.
8 Conclusions and Future Work
We proposed to re-interpret the representation and learning of widely used KGE models such as CP, RESCAL, TUCKER and COMPLEX, as generative models, overcoming some of the classical limitation of their usual EBM interpretation (see Sections I and 2). GeKC-variants for other KGE models whose scores are multilinear maps can be readily devised in the same way. Moreover, we conjecture that other KGE models defining score functions having distance-basee based semantics such as TransE [7] and RotatE [60] can be reinterpreted to be GeKCs as well. Our GeKCs open up a number of interesting future directions. First, plan to investigate how the enhanced efficiency and calibration of GeKCs can help in complex reasoning tasks beyond link prediction [2]. Second, we can leverage the rich literature learning the structure of circuits [72, 75] to devise smaller and sparser KGE circuit architectures that better capture the triple distribution or sporting structural properties that can make reasoning tasks other than marginalisation efficient [22, 16, 71].
Acknowledgments and Disclosure of Funding
We would like acknowledge lain Murray for his thoughtful feedback and suggestions draft of this work. In addition, we thank Xiong Bo and Ricky Zhu for pointing out related works in the knowledge graphs literature. AV was supported by the "UNREAL: Unified Reasoning Layer for Trustworthy ML" project (EP/Y023838/I) selected by the ERC and funded by UKRI EPSRC. RP was supported by the Graz Center for Machine Learning (GraML).
References
[1] Kareem Ahmed, Stefano Teso, Kai- Kei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic probabilistic layers for neuro-symbolic learning. In Advances in Neural Information
10

---

Processing Systems 35 (NeurIPS), volume 35, pages 29944-29959, Curran Associates, Inc., 2022.
[2] Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. Complex query answering with neural link predictors. In ICLR. OpenReview.net, 2021.
[3] Ivana Balazevic, Carl Allen, and Timothy M. Hospedales. Tucker: Tensor factorization for knowledge graph completion. In EMNLP-IJCNLP, pages 5184-5193, Association for Computational Linguistics, 2019.
[4] Mikolaj Binkowski, Danica J. Sutherland, Michael Arbel, and Arthur Gretton. Demystifying MMD gans. In ICLR (Poster). OpenReview.net, 2018.
[5] Stephen Bonner, Ian P Barrett, Cheng Ye, Rowan Swiers, Ola Engkvist, Charles Tapley Hoyt, and William L Hamilton. Understanding the performance of knowledge graph embeddings in drug discovery. Artificial Intelligence in the Life Sciences, 2: 2:100036, 2022.
[6] Antoine Bordes, Jason Weston, Ronan Collobert, and Yoshua Bengio. Learning structured embeddings of knowledge bases. Proceedings of the AAAI Conference on Artificial Intelligence, 2011.
[7] Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Neural Information Processing Systems (NIPS), pages 2787-2795, 2013.
[8] Kai- Kai-Wei Chang, Wen-tau Yih, Bishan Yang. and Christopher Meek. Typed tensor decomposition of knowledge bases for relation extraction. In EMNLP, pages 1568-1579, ACL, 2014.
[9] Jatin Chauhan, Priyanshu Gupta, and Pasquale Minervini. A probabilistic framework for knowledge graph data augmentation. arXiv preprint arXiv:2110.13205. 2021.
[10] Mark Chavira and Adnan Darwiche. On probabilistic inference by weighted model counting. Artificial Intelligence. 172(6-7):772-799, 2008
[11] Xuelu Chen, Michael Boratko, Muhao Chen, Shib Sankar Dasgupta, Xiang Lorraine Li, and Andrew McCallum. Probabilistic box embeddings for uncertain knowledge graph reasoning. arXiv preprint arXiv:2104.04597 2021.
[12] Yihong Chen, Pasquale Minervini, Sebastian Riedel, and Pontus Stenetorp. Relation prediction as an auxiliary training objective for improving multi-relational graph representations. CoRR, abs/2 10.02834, 2021.
[13] YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic modeling. 2020.
[14] Nilesh Dalvi and Dan Suciu, Efficient query evaluation on probabilistic databases. The VLDB Journal, 16(4):523-544, 2007.
[15] Nilesh N. Dalvi and Dan Suciu. The dichotomy of probabilistic inference for unions of conjunctive queries. ACM, 596))3301-330.87 2012.
[16] Mcihua Dang, Antonio Vergari, and Guy Broeck. Strudel: Learning cuuntured-decomppon probabilistic circuits. In International Conference on Probabilistic Graphical Models, pages 137-148. PMLR, 2020.
[17] Adnan Darwiche. Modeling and Reasoning with Bayesian Networks. Cambridge University Press, 2009.
[18] Adnan Darwiche. SDD:
new canonical representation of propositional knowledge bases. In Twenty-Second International Joint Conference Artificial Intelligence, 2011.
[19] Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research (JAIR), 17:229-264, 2002.

---

[20] Aaron W. Dennis. Algorithms for Learning the Structure of Monotone and Nonmonotone Sum-Product Networks. PhD thesis, Brigham Young University, 2016
[21] Tim Dettmers, Pasquale Minervini. Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In AAAI, pages 1811-1811 AAAI Press, 2018.
[22] Nicola Di Mauro. Antonio Vergari, Teresa M. A. Basile, and Floriana Esposito. Fast and accurate density estimation with extremely randomized cutset networks. Machine Learning and Knowledge Discovery in Databases: ECML PKDD, pages 203-219. Springer, 2017.
[23] Boyang Ding, Quan Wang, Bin Wang. and Li Guo. Improving knowledge graph embedding using simple constraints. In Annual Meeting of the Association for Computational Linguistics, 2018.
[24] Leslie H. Fenton. The sum of log-normal probability distributions in scatter transmission systems. IEEE Transactions on Communications, 8:57-67, 1960.
[25] Daan Fierens, Guy Van den Broeck, Joris Renkens, Dimitar Shterionov, Bernd Gutmann, Ingo Thon, Gerda Janssens, and Luc De Raedt. Inference and learning in probabilistic logic programs using weighted boolean formulas. Theory and Practice of Logic Programming, 15(3):35--401, 2015.
[26] Tal Friedman and Guy Van den Broeck. Symbolic querying of vector spaces: Probabilistic databases meets relational embeddings. In UAI, volume 124, pages 1268-1277 AUAI Press, 2020.
[27] Xavier Glorot, Antoine Bordes, Jason Weston, and Yoshua Bengio. A semantic matching energy function for learning with multi-relational data. Machine Learning, 94:233-259, 2013.
[28] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander J. Smola. A kernel two-sample test. J. Mach. Learn. Res., 13:723-773, 2012.
[29] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pages 1321-1330. PMLR, 2017.
[30] Shu Guo, Lin Li, Zhen Hui, Lingshuai Meng, Bingnan Ma, Wei Liu, Lihong Wang. Haibin Zhai, and Hong Zhang. Knowledge graph embedding preserving soft logical regularity. Proceedings of the 29th ACM International Conference on Information & Knowledge Management, 2020.
[31] Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d' A'mtoo Gerard de Melo, Claudio Gutierrez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, et al. Knowledge graphs. ACM Computing Surveys (CSUR), 54(4):1-37, 2021.
[32] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs arXiv preprint urXiv:2005.00667 2020.
[33] Nicolas Hubert, Pierre Monnin, Armelle Brun, and Davy Monticolo. New strategies for learning knowledge graph embeddings: The recommendation case. In EKAW, volume 13514 of Lecture Notes in Computer Science, pages 66-80. Springer, 2022.
[34] Nicolas Hubert, Pierre Monnin, Armelle Brun, and Davy Monticolo. Enhancing knowledge graph embedding models with semantic-driven loss functions, 2023.
[35] Aapo Hyvärinen. Consistency of pseudolikelihood estimation of fully visible boltzmann machines. Neural Computation, 18:2283-222 2006.
[36] Prachi Jain, Sushant Rathi, Mausam, and Soumen Chakrabarti. Knowledge base completion: Baseline strikes back (again). ArXiv, abs/2005.00804, 2020.
[37] Armand Joulin, Edouard Grave, Piotr Bojanowski, Maximilian Nickel, and Tomas Mikolov. Fast linear model for knowledge graph embeddings. ArXiv, abs/17100 2017.
[38] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. 3rd International Conference Learning Representations (ICLR), 2015.
12

---

[39] Denis KrompaB, Stephan Baier, and Volker Tresp. sype-constrained representation learning in knowledge graphs. In ISWC (1), volume 9366 of Lecture Notes in Computer Science, pages 640-655. Springer, 2015.
[40] Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In ICML, volume 80 of Proceedings of Machine Learning Research, pages 2869-2878 PMLR. 2018.
[41] Yann LeCun, Sumit Chopra, Raia Hadsell, Mare' Aurelio Ranzato, and Fujie Huang. A tutorial on energy-based learning. Predicting Structured Data, 2006.
[42] Pasquale Minervini, Claudia d' A'Amtoo, Nicola Fanizzi, and Floriana Esposito. Leveraging the schema in latent factor models for knowledge graph completion. In SAC, pages 327-332. ACM, 2016.
[43] Pasquale Minervini, Claudia d' Amato, and Nicola Fanizzi. Efficient energy- embedding models for link prediction in knowledge graphs Journal of Intelligent Information Systems, 47:
91-109, 2016.
[44] Pasquale Minervini, Thomas Demeester, Tim Rocktäschel, and Sebastian Riedel. Adversarial sets for regularising neural link predictors. arXiv preprint arXiv: 1707.07966 2017.
[45] Aniruddh Nath and Pedro Domingos. Learning relational
networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
[46] Aniruddh Nath and Pedro M. Domingos. Learning relational sum- cum-product networks. In AAAI, pages -286.. AAAI Press, 2015.
[47] Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. A three-way model for collective learning multi-relational data. In ICML, pages 809-816. Omnipress, 2011.
[48] Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. JEEE, 104(1):11-33)) 2016.
[49] Mathias Niepert and Guy Van den Broeck. Tractability through exchangcability: A new perspective on efficient probabilistic inference. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 2467-2475. AAAI Press, 2014.
[50] Mathias Niepert and Pedro M Domingos. Learning and inference in tractable probabilistic knowledge bases. In UAI, pages 632-641,22 2015.
[51] Georgii S. Novikov, Maxim E. Panov, and Ivan V. Oseledets. Tensor-train density estimation. In 37th Conference on Uncertainty in Artificial Intelligence (UAI), volume 161 of Proceedings of Machine Learning Research, pages 1321-1331. PMLR, 2021.
[52] Umut Oztok and Adnan Darwiche. A top-down compiler for sentential decision diagrams. In IJCAI, pages 3141-3148. AAAI Press, 2015.
[53] Robert Peharz, Robert Gens, Franz Pernkopf, and Pedro M. Domingos. On the latent variable interpretation in sum-product networks. IEEE Transactions on Pattern Analalysis and Machine Intelligence, 39(10): 39(10):200--2044 2017.
[54] Pouya Pezeshkpour, Yifan Tian, and Sameer Singh. Revisiting evaluation of knowledge base completion models. In AKBC, 2020.
[55] Hoifung Poon and Pedro Domingos. Sum-produce networks: new deep architecture. IEEE International Conference Computer Vision Workshops (ICCV Workshops), pages 689-690. IEEE, 2011.
[56] Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla. You CAN teach an old dog new tricks! on training knowledge graph embeddings. In ICLR. OpenReview.net, 2020.
[57] Taisuke Sato and Yoshitaka Kameya. Prism: a language for symbolic-statistiaal modeling. In IJCAI, volume 97, pages 1330-1339. Citeseer, 1997.
13

---

[58] Amir Shpilka, Amir Ychudayoff, et al. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends@ in Theoretical Computer Science, 5(:-4):207-388 2010.
[59] Richard Socher, Danqi Chen, Christopher Manning, and Andrew Ng. Reasoning with neural tensor networks for knowledge base completion. In Advances in Neural Information Processing Systems 26, 2013.
[60] Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. RotatE: Knowledge graph embed- ding by relational rotation in complex space. In ICLR (Poster). OpenReview.net, 2019.
[61] Pedro Tabacof and Luca Costabello. Probability calibration for knowledge graph embedding models. ArXiv, abs/1912. 10000, 2019.
[62] Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In 3rd Workshop on Continuous Vector Space Models and Their Compositionalityy ACL, 2015.
[63] Volker Tresp, Cristóbal Esteban, Yinchong Yang. Stephan Baier, and Denis Krompass. Learning with memory embeddings. ArXiv, abs/ abs/1551..7977.. 2015.
[64] Volker Tresp, Sahand Sharifzadeh, Hang Li, Dario Konopatzki, and Yunpu Ma. The tensor brain: A unified theory of perception, memory, and semantic decoding. Neural Computation. 35:156-227, 2021.
[65] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In ICML, volume 48 of JMLR Workshop and Conference Proceedings, pages 2071-2080. JMLR.org, 2016.
[66] L. Tucker. The extension of factor analysis to dimensiimniional matrices. Contributions to mathematical psychology., pages 1 110-127. Holt, Rinehart and Winston, 1964.
[67] Leslie G. Valiant. Negation can be exponentially powerful. In 11th Annual ACM Symposium on Theory of Computing, pages 189-196, 1979.
[68] Guy Van den Broeck, Nima Taghipour, Wannes Meert, Jesse Davis, and Luc De Raedt. Lifted probabilistic inference by first-order knowledge compilation. In IJCAI, pages 2178-2185. JCCAI/AAII, 2011.
[69] Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 988))2557-2265, 2008.
[70] Cristiano Varin, Nancy Reid, and David Firth. An overview of composite likelihood methods. Statistica Sinica, 21, 01 2011.
[71] Fabrizio Ventola, Devendra Singh Dhami, and Kristian Kersting. Generative clausal networks: Relational decision trees as probabilistic circuits. In Inductive Logic Programming: 30th International Conference, ILP 2021, Virtual Event, October 25-27, 2021, Proceedings, pages 251-265. Springer, 2022.
[72] Antonio Vergari, Nicola Di Mauro, and Floriana Esposito. Simplifying, regularizing and strengthening sum- cum-product network structure learning. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2015, Porto, Portugal, September 7-11, 2015, Proceedings, Part II 15, pages 343-358. Springer, 2015.
[73] Antonio Vergari, Robert Peharz, Nicola Di Mauro, Alejandro Molina, Kristian Kersting, and Floriana Esposito. Sum-product autoencoding: Encoding and decoding representations using num-product networks. In Proceedings of the AAAI Conference Artificial Intelligence. volume 32, 2018
[74] Antonio Vergari, Nicola Di Mauro, and Floriana Esposito. Visualizing and understanding sum-product networks. Machine Learning, 108(4):551-57, 2019.
[75] Antonio Vergari, Nicola Di Mauro, and Guy Van den Broeck. Tractable probabilistic models: Representations, algorithms, learning, and applications. Tutorial at the 35th Conference on Uncertainty in Artificial Intelligence (UAI), 2019.
14

---

[76] Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A composi- tional atlas of tractable eircuit operations for probabilistic inference. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 13189-13201. Curran Associates, Inc., 2021.
[77] W Austin Webb and Pedro Domingos. Tractable probabilistic knowledge bases with existence uncertainty. In Workshops at the Twenty-Seventh AAAI Conference Artificial Intelligence. 2013.
[78] Han Xiao, Minlie Huang, and Xiaoyan Zhu. Transg: A generative model for knowledge graph embedding. In Annual Meeting of the Association for Computational Linguistics, 2016.
[79] Ruiqi Zhu, Fangrong Wang, Alan Bundy, Xue Li, Kwabena Nuamah, Lei Xu, Stefano Mauceri, and Jeff Z. Pan. A closer look at probability calibration of knowledge graph embedding. In I 11th International Joint Conference on Knowledge Graphs, page 104-109, 2023.
15

---

X e X Wr X3 Co T
E embbediings
dTUCKER (loxprofen, interacts, COX2)
Ploveproten
[0.5 0.3]
vec
oçox2
00.1 -0.4]
(
@phce-acid
-0.9 0.4]
R embeediings
Wonnit
[0.9
0.6]
[0.8
0.2
e
Wr
e
elucoprotion
W
(a)
(h)
Figure A.1: Evaluation of circuit representations of score functions as in neural networks. ferd-forwardd evaluation of the TUCKER score function as circuit over 2-dimensional embed- dings and parameterised by the core tensor T (see proof of Prop. 1 below) (a). Given a triple (loxoprofen, interacts, COX2), the input units (Def. 1) map subject, predicate and object to their embedding entries (in violet boxes). Then, the circuit is evaluated similarly to neural networks: the products (in orange) are evaluated before the weighted sum (in blue), which is parameterised by the core tensor values (in green) (b). The output of the circuit is the score of the input triple.
A Proofs
A.1 KGE Models as Circuits
Proposition 1 (Score functions of KGE models as circuits). The computational graphs of the score functions & of CP. RESCAL, TUCKER and COMPLEX are smooth and decomposable circuits over X {S, R, O}, whose evaluation cost is cØs E ((ø)), where (ø) denotes the number of edges in the circuit, also called its size. For example, the size of the circuit for CP is |Øcpl E (()..
Proof. We present the proof by construction for TUCKER [3], as CP [40], RESCAL [47] and COMPLEX [65] define score functions that are a specialisation of it [3] (see below). Given a triple (s,T.0) E & x R E, the TUCKER score function computes
ŌTUCKER (s, r. = T x1 e2 X2 W X3 C. = Σ
(4)
Rmm
where T E Rdd denotes the core tensor, x,, denotes the tensor product along the n-th mode, and de, dl denote respectively the embedding sizes of entities and predicates (which might not be equal). To see how this parametrization generalises that of CP. RESCAL and COMPLEX, consider for example the score function of CP on d-dimensional embeddings. It can be obtained by (i) setting the core tensor T to be a diagonal tensor having ones on the superdiagonal, and (ii) having two distinct embedding instances for each entity that are used depending on their role (either subject or object) in a triple. The embeddings C2 C, E Rd (resp. W, Rd.) are rows of the matrix ). which associates an embedding to each entity (resp. predicate). E E R Exxd, (resp. W E R gR]]x,.)
Constructing the circuit. For the construction of the equivalent circuit it suffices to (i) create an input unit for each i-th entry of an embedding for subjects, predicates and objects, as implement a look-up table that computes the corresponding embedding value for an entity or predicate, and (ii) transform the tensor multiplications into corresponding sum and product units. We start by introducing the input units ( 12t and 10 for 1 S i, S de and 1 < j < dp as parametric mappers over variables S, R and O, respectively. The input units is and to (resp. 1,9) are parameterised by the matrix (resp. W) such that 1, (s; E) Cai and 1 (o E) Coi for some s, E (resp. 1f(r; W) wri for some R). To encode the tensor products in Eq. (4) we introduce d² d, product units Oijk, each of them computing the product of a combination of the outputs of input units.
(ija(s, r,) o) = 15 (s) (r( (0)
Finally, a sum unit Gut parameterised by the core tensor T Rdd computes weighted summation of the outputs given by the product units, i.c..
dout ())
Σ Task (i))(8,),0)
(LIAEE
[d.xx(d[[((a)]
16

---

Table A.I: Score functions as compact circuits. Asymptotic size of circuits encoding the score functions of CP, RESCAL, COMPLEX and TuCKER, with respect to the embedding size. For TUCKER, de and d, denote the embedding sizes for entities and predicates, respectively.
KGE Model
Circuit Size
KGE Model
Circuit Size
CP
((d) O(d)
RESCAL TUCKER
((d)) Olde .dr)
COMPLEX
where [d] denotes the set {l....,d} d} and Tijk is the (i,i,) k) entry of T. We now observe that the constructed circuit Pout encodes the TUCKER score function (Eq. (4)), as OTUCKER (8,T,)) = (s, o) for any input triple (s.r.o) E
Circuit evaluation and properties. Evaluating the score function of TUCKER corresponds to performing a feed-forward pass of its circuit representation, where each computational unit is evaluated once, as we illustrate in Fig. A.I. As such, the cost of evaluating the score function is proportional to the size of its circuit representation. i.e., cost(c) E ((())) where |o| E O(d² - d,)) is the number of edges. In Table A. we show how the sizes of the circuit representation of the other score functions increases with respect to the embedding size. Finally, since each product unit Φisk defined on the same scope (see Def. 1) {S, R. O} and fully decompose into inputs (i.e., into {S), {R), {O]), and the inputs of the sum unit @out are all defined over the same scope, we have that the circuit satisfies smoothness and decomposability (Def. 2).
Furthermore, in Lem. A.I we show that the circuit representations of CP. RESCAL, TUCKER and COMPLEX and the proposed GeKCs (Section 4) satisfy a structural property known as omni- computibility (see Def. B.2). In nutshell, the score functions of the aforementioned KGE models and GeKCs are circuits that fully decompose their scope {S, R. O} into ({5); {R), (0)). The satisfaction of this property will be useful to prove both Thm. I and Thm. 2 later in this appendix.
Lemma A.1 (KGE models and derived GeKCs are omni-compatible) The circuit representation of the score functions of CP, RESCAL, TUCKER, COMPLEX and their GeKCs counterparts obtained by nen-negative restriction (Section 4.1) or squaring (Section 4.2) are omni-compatible (see Def. B.2).
Proof. To begin, we note that to comply with Def. B.2 every omni-compatibl circuit shall contain product units that fully factorise over their scope. In other words, for every product unit n with scope sc(n) = X, its scope shall decompose as ({X)), [X2)..... (X|s((1))))) To see why, consider circuit Φ with a product unit whose scope is decomposed as sc(n) = (X, Y). It is easy to construct another circuit øf that not compatible with é by having a product unit m with scope sc(m) sc(n) decomposed in way that it cannot be rearranged by introducing additional decomposabl product units (Def. 2), e-g., SC sc(m) = (Z, W) with Zn X # and W 0 + Ø. such, every omni- compatible circuit over X must be representable in the form Σ ===1 0, increase in its size.
X (xx) without any
Now, it is easy to verify that the circuit representations of CP, RESCAL, TUCKER and COMPLEX follow the above form, with different number N of product units feeding the single sum unit, but each one decomposing its scope {S, R, 0} into ({S), {R), (O}) (see Fig. 2). From this it follows that CP* RESCAL* TUCKER and COMPLEX* are omni-compatible as well, as they share the same structure of their based counterpart, while just enforcing non -egativee activations via reparametrisation (see Section 4.1).
Finally, we note that CP2, RESCAL TUCKER² and COMPLEX² are still omni- compatible because the square operation yields the following fully-factorised representation: (EM1 6, [X Lu (Xx))² = EN Ey 0,0, [ (X,) IT (Xx) which can be easily rewritten as ΣN wh X (Xx) where now h ranges over the Cartesian product of i E [N] and j E [N], w/ is the product of 0,0, and lak new input unit that encodes Lu (Xx) 1xx (Xx) for certain variable index k.
17

---

A.2 Efficient Summations over Circuits
Proposition (Efficient Summations), Let @ be a smooth and decomposable circuit over X {S, R, O} that encodes the score function of a KGE model. The sum EEeg Erer Lase Φ(8, or any other summation over subjects, predicates or objects can be computed in time ((((E)
+ + (0))
Proof. A proof for the computation of marginal probabilities in smooth and decomposable probabilis- tic circuits (PCs) defined over discrete variables in linear time with respect to their size can be found in [13]. This proof also applies for computing summations in smooth and decomposable circuits that do not necessarily corresponds to marginal probabilities [76]. The satisfaction of smoothness and decomposability (Def. 2) in a circuit & permits to push outer summations inside the computational graph until input units are reached, where summations are actually performed independently and on smaller sets of variables (i.e.. {5). ).{ {R), {O} our case), and then to evaluate the circuit only once.
Here we take into account the computational cost of summing over each input unit (see proof of Prop. 1), which is ((E)) (resp. R()) for those defined on variables S, O (resp. R). Since the size of the circuit |6] must be at least the number of input units, we retrieve that the overall complexity for computing summations as stated in the proposition is (((8)+|RR) (ol).
As an example, consider the CP score function computing dcr(s, r. = (C..Wr, Co) for some triple (s,r, o) and embeddings es, Wr; e, E Rd. We can compute Exce EreR Exee ΦCP(s, r, by pushing the outer summations inside the trilinear product, L.e,, by computing it as E.EE es EPER W,,, Eoee eo). which requires time (((EE) [R]) d).
A.3 Efficient Summations over Squared Circuits
Theorem (Efficient summations of squared GeKCs). Performing summations as stated in Prop. on CP², RESCAL", TUCKER* and COMPLEX² can be done in time (((E) + |R]) lol3).
Proof. In Lem. A.I we showed that the circuit representations @ of CP, RESCAL, TUCKER and COMPLEX are omni-compatible (see Def. B.2). As a consequence, o is compatible (see Def. B) with itself. Therefore, Prop. B.1 ensures that we can construct the product eircuit ø á (i.e., d²) as smooth and decomposable circuit having size ( () in time O())l²). Since &² is still smooth and decomposable, Prop. 2 guarantees that we can perform summations in time ((EE) + (R])-107 O
A.4 Circuits encoding Domain Constraints
In Def. A.1 introduce the concepts of support and determinism, whose definition is useful to describe constraint circuits in Def. A.2.
Definition A.1 (Support and Determinism [13, 76]). In a circuit the support of a computational unit over variables X computing Φ, (X) is defined as the set of value assignments
variables in X such that the output n non-zero, i.e., supp(n) = fx E val(X) (X) + 0}. A sum unit n is deterministic if its inputs have disjoint supports, i.e., Vi,j E in(n), fj: supp(i) O supp(j) = Ø.
Definition A.2 (Constraint Cireuit [1].. Given a propositional logie formula K, constraint circuit CK is a smooth and decomposable PC over variables X with deterministic sum units (Def. A. and indicator functions input units, such that rx(x) 1 (x F K} for any val(X).
In general, we can compile any propositional logic formula into a constraint circuit (Def. A.2) by leveraging knowledge compilation techniques [19, 18, 52]. For domain constraints (Def. 4) this compilation process is straightforward, as we detail in the following proposition and proof.
Proposition A.1 (Circuit encoding domain constraints). Let K = Kr V...V r. be disjunction of domain constraints defined over set of predicates = (ri,.... I'm] and a set of entities (Def. 4). We can compile K into constraint circuit ск (Def. A.2) defined over variables X {S, R, 0}
having size O(E [R() in the worst case and O(E) + [R] in the best case.
Proof. Let K = K,, V... V Kr. be disjunction of domain constraints (Def. 4) where
Kr = SE SEKK(() A R = R no(r) (Vu = u) A R= (Vueno(r) =
18

---

Note that the disjunctions in K are deterministic, i.e., only one of their argument can be true the same time. This enables us construct the constraint circuit ск such that cx (s, [(8, 0) F K} for any triple by simply replacing conjunctions and disjunctions with product and sum units, respectively. Note that ск is indeed smooth and decomposable (Def. 2), as the inputs of the sum units are product units having scope {S, R, O) that are fully factorised into ((S), { (R), (O]). Moreover, K is a disjunction of [R] conjunctive formulae having O(E)) terms, and therefore |ex| O [R]) in the worst case. In the best case of every predicate sharing the same subject and object domains Kis, Ko C &, we can simplify K into a conjunction of three disjunctive expressions, i.e.,
K (Vuens = A (VEERR=: = (VeEmO 0
that can be easily compiled into a constraint circuit ск having size O(E + [R]). by again noticing that disjunctions are deterministic. In real-world KGs like ogbl-biokg [32] several predicates share
the same subject and object domains, and this permits to have much smaller constraint circuits. C
A.5 Efficient Integration of Domain Knowledge in GeKCs
Theorem 2 (Tractable integration of constraints in GeKCs). Let cx be a constraint circuit encoding logical constraint K over variables {SS, R, Q)- Then exactly computing the partition function Z of the product (pe(8, r, o) Cx( (8, o) x Px (s, r; o) for any GeKC Ópc derived from CP, RESCAL, TUCKER or COMPLEX (Section 4) can be done time (((E) + [R]) |dpel [cK[).
Proof: In Lem. A.1 we showed that the GeKCs Ope derived from CP, RESCAL, TUCKER and COMPLEX via non-negative restriction (Section 4.1) or squaring (Section 4.2) are omni-compatible (see Def. B.2). As consequence, Ope is always compatible with cк regardless of the encoded logical constraint K, since constraint circuits are by definition smooth and decomposable (Def. A.2). By applying Prop. B.I, retrieve that we can construct Φpc CK as smooth and decomposable circuit of size O1[ppel |cx() and in time O(Opel |cx]). As the resulting product circuit is smooth and decomposable, Prop. 2 guarantees that
compute its partition function Zx
EVEE ETER Eoee (ppc(s, r, o) ox (s, r, 0)) in time (((E) + [R() lépel Ickk)).
B Circuits
B.1 Tractable Product of Circuits
In this section, we provide the formal definition of compatibility (Def. B. and onni-compatibility (Def. B.2), stated by Vergari et al. [76]. Given compatible circuits, Prop. B.1 guarantees that we can represent their product as a smooth and decomposable circuit efficiently.
Definition B.1 (Compatibillity). Two circuits é, o' over variables X are compatible if (1) they smooth and decomposable, and (2) any pair of product units n E Φ m E ø' having the same scope can be rearranged into binary products that mutually compatible and decompose their scope in the same way, i.e., (sc(n) = sc(m)) = (sc(n,) = sc(m;), n, and m; are compatible) for some rearrangements of the inputs of (resp. m) into n m2 (resp. mi, m2))
Definition B.2 (Omni-coopptiinn
A circuit & over variables X is omni-compatible if it is compatible with any smooth and decomposable circuit over X.
Proposition B.1 (Tractable product of circuits). Let Φ. ø' be two compatible (Def. B.1) circuits. We represent the product circuit d' computing the product of the outputs of and ø' smooth and decomposable circuit having size O[Øo) lØ'l) in time ((Ø)) (d'l). Moreover, if both & and d' omni-compatible (Def. B.2), then also the product circuit ø' is omni-compatible.
Prop. B.I allows us to compute the partition function and any other marginal probability in GeKCs obtained via squaring efficiently (see Section 4.2 and Thm. 1). In addition, Prop. B. is a crucial theoretical result that allows us to inject logical constraints in GeKCs in a way that enable computing the partition function exactly and efficiently (see Section 5 and Thm. 2).
19

---

C From KGE Models to PCs
C.1 Interpreting Non-negative Embedding Values
In Fig. C.I we interpret the embedding values of GeKCs obtained via non-negative restriction CP* RESCAL', TUCKER*, COMPLEX* (Section 4.1) as the parameters of unnormalised categorical distributions over entities (elements in 8) predicates (elements in R.).
0.6
0.4
0.4
0.3
0.3
Catg
Po
cual E wee
0.2
Catg
Pr wr2/ E 1/2 PER.
0.9
0.5
Cat
Pa = cus/ Σ eul wee
0.3
0.4
0.4
0.1
Cati
Σ War W/r/ neRe
Olocspraten
ecokc
Cphas woid
Winhiba Winhibia
Wi
W reauta
& embeddings
R embeddings
Figure C.I: Non-negative embeddings parameterise categorical distributions. 2-dimensional em- 4.1) can be seen as the parameters of two categorical distributions over entities (left) predicates (right) up renormalisation.
beddings of GeKCs obtained via non-negative restrictions (Section
C.2 Realising the Non-negative Restriction of COMPLEX
As anticipated in Section 4.1, for the COMPLEX [65] score function restricting the real and imaginary parts to be non-negative is not sufficient to obtain PC due to the presence of subtraction, as showed in the following equation.
ΦCOMPLEX (x r, = (Re(e,). Re(w,), Re(e,)) + (Im(e,), Re(w,R ww, Im(e.)) (Re(e,), Im Im (Im(e,), Im(,,,) Re(c.))
(5)
Here Cs. Wr, Co Cd are the embeddings associated the subject, predicate and object, respectively. Under the restriction of embedding values to be non-negative, we ensure that (CCoMpLEx((s1) 2 0 for any input triple by enforeing the additional constraint
(Re(ez), Re(R,))))))) Re(e.)) 2 (Im(e.). Im(w.),
(6)
which can be simplified into the two distinct inequalities
Vu E E Re(ems) 2 Im(ew)) and
EE Re(w,)) 2 Im(w,s).
In other words, want the real part of each embedding value to be always greater equal than the corresponding imaginary part. We implement this constraint in practice by reparametrisation of the imaginary part in function of the real part, i.e.,
Vu E E
Im(e = Re(eus) (Bus) Im(w,) Re(w,)) ((tr))
Vr R
where (Ix) 1/(1 exp(-x)) E [0 denotes the logistic function and Owi, Tri E R are additional parameters associated entities & and predicates r R. respectively. The reparametrisation of the imaginary parts using Eqs. (7) and (8) is sufficient condition for the satisfaction of the constraint showed in Eq. (6), and also maintains the same number of learnable parameters of COMPLEX.
C.3 Sampling from GeKCs with Non-negative Parameters
Parameters interpretation. Sum units with non non-negative parameters in smooth and decomposable PCs can be seen as marginalised discrete latent variables, similarly to the latent variable interpretation in mixture models [55, 53]. That is, the non-negative parameters of sum unit are the parameters of (possibly unnormalised) categorical distribution over assignments to a latent variable. For Cp+ and RESCAL* (Section 4. 1),, the non-negative parameters of the sum unit encode uniform and
20

---

unnormalised categorical distribution, as they are all fixed to 1 (see Fig. 2). By contrast, in TUCKER* these parameters are the vectorisation of the core tensor (see the proof Prop. 1), and hence they are learned. The input units of CP+, RESCAI. and TUCKER* can be interpreted as unnormalised categorical distribution over entities or predicates, as detailed Appendix C.I.
Sampling from CP*, COMPLEX*, TUCKER". Thanks to the latent variable interpretation, ances- tral sampling CP RESCAL* and TUCKER* can be performed by (1) sampling an assignment to the latent variable associated to the single sum unit, i.e., one of its input branches, (2) selecting the corresponding combination subject-reddicte-obieee predicate and object respectively from each of the indexed unnormalized categorical distributions.
input units, and (3) sampling a subject,
C.4 Learning Complexity of GeKCs
In Table C.I we summarise the complexities of computing the PI.L and MLE objectives (Fqs. (1) and (2)) for KGE models and GeKCs. Asymptotically, GeKCs manifest better time and space complexities with respect to the number of entities E), batch size B and embedding size. This makes GeKCs more efficient than traditional KGE models during training, both in time and memory (see Section 4.3 and Fig. 3).
Table C.I: Summary of complexities for exactly computing the PLL and MLE objectives. Time and space complexity of computing jogp(o s, and the partition function Z. These complexities are respectively lower bounds of the complexities of computing the PLL and MLE objectives, as we have that |E| > [R. for large real-world KGs. For CP, RESCAL and COMPLEX and GeKCs derived from them, d denotes the size of both entity and predicate embeddings. For TUCKER and GeKCs derived from it, d, and d, denote the embedding sizes for entities and predicates, respectively.
Complexity log p(o s,
Complexity of
Model
Time
Space
Time
Space
CP
O(EE) BB| d)
O [B]
O(g82
R d)
O(d)
RESCAL
O(E)
B d
B d
O(E
BD)
0(8
R d
((d))
TUCKER
O[[0)
B de
+
[B]
d d.)
O(E
[B)
0(8
R
d2
dz)
O d,)
COMPLEX
O(EE)
B -d)
O(EE
[B]
0(E?2
R -d]
O(d)
CP
O((E)
B d)
O(B) d)
O([E
[
O(d)
RESCAL
O((18
R d)
d)
O B
d))
O(EE R dd)-)
O(1))
TUCKER
O((EE
B de
d+)
de))
O d, d.)
O E] d. R dr
di d.)
O(d d.) O(d)
COMPLEX*
O((EET
B -d)
O
O(IE + [
CP2
O((E)
B
- d
O(B)
O(IE [R]
O(d)
RESCAL2
O((E)
R d2)
O (
OQIE + |R d]
O d2)
TUCKER2
(((
B de d
d)
O
dr)
O(IE d9) de)
0(E) de [
O dr)
COMPLEX²
(((()
B
d
O
(
C.4.1 Computing the Partition Function
In this section derive the computational complexity of computing the partition function for GeKCs obtained via squaring (Section 4.2). For a summary of these complexities, see Table C.I.
CP2 and COMPLEX2, Here derive the partition function of CP². For COMPLEX² the derivation similar, as the score function of COMPLEX can be written in terms of trilinear products just like CP (see Eq. (5)). The score function Φcr² encoded by CP² can be written
d
(s, (e., w,, eo)2
ΣΣ
Est WoWeeeoooooo
(resp. w, E (Rd) are rows of the matrices U, V E RlEled (resp. W [ xd), where es, 6, E d which associate each entity (resp. predicate) vector. By leveraging the einsum notation for
21

---

brevity, the partition function of Ocp2 can be written
z= ΣΣΣ +E PER 3EE
Pcp (8,
Σ BEE
CxrSaj
Σ PER
WreWly
Σ aoE
CoiCaj
i=1 j=1
U W
where - U. W = w W and V' = V are d x d matrices. With the simplest algorithm
for matrix multiplication, we recover that computing Z requires time ( d² + [R] d²) and additional space (d.))
RESCAL?. The score function RRESAA encoded by RESCAL. can be written
(RESCAL = (e, W.W.
Σ
WrishhWriWWhheee
where [d] denotes the set {I....,d} d]. e, e, Rd are rows the matrix E E gle)xd and W, E Rdxd are slices along the first mode of the tensor W E R which consists of stacked matrix embeddings associated to predicates. The partition function of PRESCAL? can be written as
z --ΣΣΣ
PRESCAL (s,T,, = E
Σ (...A.EEd)) BEE
CaiCsh
Σ PER
Wrij Wrkt
Σ LOES
CoyCol
SEE FER OEE
E. Wryg Er
where E' E Rdxd The complexity of computing Z depends the order of tensor contractions in the einsum operation showed in Eq. (9). By optimising the order of tensor contractions (e.g., by using software libraries like opt__iin_ttt et__insum), O(EE) - and additional space ([ Notice that the time complexity here is slightly lower than the theoretical upper bound given in Thm. 1, which would be O(EE) d² |R| dd)..
retrieve that computing % requires time
TUCKER² Lastly, we present the derivation of the partition function for TUCKER?, The score function TUCCKER* encoded by TUCKER? can be written as
PTUCKER=(S,12) (8, (T X1 C, W, X3 c.)² Σ
Σ
(Lm.a)e [.]x(d])x [d.] [d.]x(d))x(aa)
where Cs, Co E R.de are rows of the matrix E E RlEixd, w, is row of the matrix W E R R xd. and T E Rd X.x xd, denotes the core tensor. The partition function of TTUCKER* can be written as
Z
ΣΣΣ
PTUCKER- (s,
SEE oER
Σ (.
Σ (L,,nnE
Σ 3E
Cartesl
Wry Wren Σ PER
Σ aoEE
Tisk Tban
Cok Con
[d.]x(d (de [d.]x(d.] (d.]x(d
Tisk Timn E,J W jm E kn
(10)
where E' = E EEEEE the order of tensor contractions in the einsum operation showed in Eq. (10), we retrieve that computing requires time (1E) the time complexity is lower than the theoretical upper bound given in Thm. 1, which would be O(E)) - di R de + d de).
E Rd.xd, and W W W Rd.xdd, Similarly to RESCAL2, by optimising
dR dd.) and additional space (d d,.). Similarly to RESCAL
C.4.2 Complexity of Computing the PLL Objective
In this section, show that GeKCs enable to better scale the computation of the PLL objective (Eq. (1) with respect to energy-based KGE models (see Section 2). We present this concept for CP and GeKCs derived from it (Section 4), as for the other score functions it is similar.
22

---

Complexity of the PLL objective on CP. Let (cr(s, r, o) = (e,, eo) - the score function of CP [40], where ex E Rd (resp. w, E Rd)) are rows of the matrices U, V E RlEixd xd (resp. W E R which associate to each entity (resp. predicate) vector. Given a training triple (s, o), the computation of the term logp(o s, = @(5,r, o) log Eores exp ((s, r, o') requires evaluating (cp(s, r, o') for all objects o' E E. In order fully exploit GPU parallelism [36], this is usually done with the matrix-vector multiplication V(e, w,) E RIE!, where @ denotes the Hadamard product [40, 12]. Therefore, computing logp(o 8, r) for each triple (s. in a mini-batch B & R. x & such that [&] >> [B] requires time O[EE) [B] d) and space - For the other terms of the PLL objective (i.e., logp(s r, o) and log p(r o)) the derivation is similar. Moreover, for real-world large KGs it reasonable assume that [ R] and therefore
= CitWri be
the cost of computing logp(r 8, o) is negligible.
Complexity of the PLL objective on GeKCs. GeKCss obtained from CP either by non-negative
restriction (Section 4.1) or by squaring (Section 4.2) encode (8, r, o) xx p(s, r, o) for any input triple. As such, the component p(o 8,r) of the PLL objective can be written
log 8, log (8) log Σ Spess,rr, d'EE
(11)
The absence the exponential function the summed terms in Eq. (11) allows us to push the outer summation inside the circuit computing @pc(s, o), and to sum over the input units relative objects. For instance, for CP* we can write
d
Σ Pcp (s,r,o')== O'EE
-E>
Wit = Σ 1=1
Σ Eco's co'i = (e, (wr) (V AEE
Wri
d'E 1=1
where Cs Wr, Co E R4, V V p denotes the matrix whose rows are object embeddings, and
1g = [I... 1] is a vector of ones. Note that V 1g E _4 does not depend on the input triple. Therefore, given a mini-batch of triples B, computing log p(o s,r) requires time O([EE + [B)) d) and space O] d), which is much lower than the complexity on CP showed above, and we can still leverage GPU parallelism. For CP², the complexity similar to the derivation of the partition function complexity showed in Appendix C.4.1. That is, for CP² we can write
d
Σ (err(s,
Σ
Σ estWyiooi
Σ ediieo's 3O'EE
ex
d'E
O'EE
i=1j=1
= (e, O w.) (V V) 3 w,)
where Cs, Wr, C. E Rd, V E Bleldd Note that the matrix V V E Radd does not depend on the input triple. Therefore, given mini-batch of triples B, computing log p(o s,r) requires time ((([)) + [B) d²) and space O[ d). While the time complexity is quadratic in the embedding size d, is still much lower than the time complexity on CP. A similar discussion can also be carried out for the other KGE models and the corresponding GeKCs, which retrieves the complexities showed in Table C.I.
C.4.3 Training Speed-up Benchmark Details
In this section we report the details about the training benchmark on COMPLEX, COMPLEX* and COMPLEX2, whose results are showed in Fig. 3. We measure time and peak GPU memory usage required for computing the PLL objective (Eq. (1)) and to do an optimisation step for single batch on ogbl-wikikg2 [32]. large knowledge graph with millions of entities (see Table F.1). We fix the embedding size to d = 100 for the three models. For the benchmark with increasing batch size, we keep all the entities and increase the batch size from 100 to 5000. For the benchmark with increasing number of entities, we keep the batch size fixed to 500 (the maximum allowed for COMPLEX by our GPUs) and progressively increase the number of entities, from about 3 10 to 2.5 10 We report the average time over 25 independent runs single Nvidia RTX A6000 with 48 GiB of memory.
23

---

D Distribution of Scores
10a
FB15K-257
WN18RR
oghl-hiokg
10
10
-5
10
15
-5
0
10
15
( r, o)
Figure D.I: Scores are mostly non-negative. Histograms of the scores assigned by COMPLEX to existing validation triples (left) and their perturbation (right) on three data sets. The vast majority of triple scores are non-negative, suggesting that squaring them has minimal effect the rankings.
In Fig. D.1 we show the histograms of the scores assigned the validation triples and their per- turbations of three data sets (see Appendix F.1). Following Socher et al. [59], we generate triple perturbations that are challenging for link prediction. That is, for each validation triple (s, r, o), the corresponding perturbation (s, r, 0) is obtained by replacing the object with a random entity that has appeared least once object in training triple with predicate The bottom line is that scores are mostly non-negative, and hence can be used as a heuristic to effectively initialise GeKCs quickly distil them (e.g., FB15K-237), we further discuss in Appendix F.5.1.
E
Reconciling Knowledge Graph Embeddings Interpretations
Triples as boolean variables. KGE models such as CP, RESCAL, TUCKER and COMPLEX have been historically introduced as factorizations of tensor-represennation of KG, which we discuss next. In fact, KG G can be represented as a 3-way binary tensor Y E {0, 13 [[]x in which every entry YsTo is if (s, r, o) and otherwise [48]. Under this light, a KGE model like RESCAL factorises every slice Y, {0, 1 |[E)x|E), corresponding to the predicate r as EW, where E is an |8] x d matrix comprising the entity embeddings and W, is an d x d matrix containing the embeddings for the predicate r. To deal with uncertainty and incomplete KGs, Y can be interpreted as Bernoulli random variable. As such, its distribution becomes p(Y aro which is usually modelled as a (Ø((, r, o)), where a denotes the logistic function and 6 is the score function of KGE model. Note that this distribution of triple introduces E R El random variables, one for each possible triple.
s, o)
KGE models estimators of distribution KGs. At the same time, the interpretation of triples as boolean variables induces a distribution over possible KGs, g(9), which is the distribution over all possible binary tensors p(Y). The probability
KG G can therefore be computed as the product of the likelihoods of all variables Y.ro. i.e., (G) = I[(e.ro) P(Y.ro = 1 s, o):
s. o). Note that (re- )ormmalising this distribution is intractable in general, as it would require summing over all possible 2 R binary tensors. This is why historically KGE models have been interpreted as energy-base based models. by directly optimising for ó(s, o). interpreted as the negated energy associated to every triple, and not p(Y has been done via negative sampling or other contrastive learning objectives [6. 7]. We point out that this very same interpretation can be found in the literature of probabilistic logic programming [25], probabilistic databases (PDBs) [14] and statistical relational learning (see Section 6) where the distribution over possible "worlds" is over sets of boolean assignments to ground atoms or facts, or tuples in a PDB, each interpreted as Bernoulli random variables.
[( P(Y.oo
s, o) (see Section 2). This
Estimating distribution over triples. In this work, instead, we interpret existing KGE models and our GeKCs as models that encode a possibly unnormalised probability distribution over three random variables, R, O, which induces distribution over triples that is tractable renormalise."
The polynomial cost of renormalising an based KGE is unfortunately infeasible for real-world KGs. Section 2.
24

---

To reconcile these two perspectives, we interpret the probability of a triple p(s, 0) to be proportional the probability of all KGs G where (s. r) holds, ie.. those G such that (s, r) E G. Intuitively, triple will be more probable to exist if it does exist in highly probable KGs. More formally, given
q probability distribution over KGs, we define p as an unnormalised probability distribution over triples, i.e., p(),r,o) xx p(s, r, 0), where
((S,T,0) = Σ ( Σ (9) -,((,,,()) E 9} = Bg [1 E E GEH
(12)
SEH (aTr,))G
and 7 2xXRXX denotes the set of all possible KGs. Computing the expectation in Eq. (12) exactly is equivalent to solving a weighted model counting (WMC) problem [10], where we sum the probabilities of all possible KGs containing (s, r, 0). Alternatively, it is equívalent computing the probability of the simplest possible query in a PDB (i.e., asking for a single tuple), where each stored tuple is interpreted as an independent Bernoulii random variable Yrro- Therefore, we have that u(s o) is simply the likelihood that Yaro is true, i.c., p(Yero- = s, o). Furthermore, the normalisation constant of μ (Eq. (12)) can be written
Z = Σ u(S,T,0)= Σ (9))) Σ 1((s,r,0) ((s,,,o)EE))-- GEH
Σ (G) |6| 1g GER
(a.N.))E ÉXRXE
(S.T.))
EXRXE
which is the expected size of KG according to the probability distribution g. Written in this way, however, computing Z through (()) intractable. For this reason, we directly encode μ with GeKCs and compute Z by summing over all triples, and therefore without modelling g(G).
Further interpretations in related works. Under the interpretation of KG as PDB, Friedman and Van den Broeck [26] further decompose the likelihood that Ysro is true as
PYY.ro 1 s, s.r,o) = p(E, = p(T, 1 p(E, = 1)
where Eg, Eg, T, new Bernoulli variables that assumed to be conditionally independent given the parameters of the PDB. That is, instead of introducing one random variable per triple, they introduce one random variable per entity and predicate. In this framework, they reinterpret the score function of DISTMULT, a simplified variant of CP, as an implicit circuit that models an unnormalized distribution over the collection of variables Z {EuJues (Tr)reR. trained by negative sampling. This decomposition permits to compute the probability of any database query efficiently, which otherwise is known be either PTIME
#a-hard problem, depending on the query type [15]. If we were to interpret our distribution μ(S = R = r, 0 o) as the unnormalized marginal distribution p(
T, 1, F., 1) Ex pl E, 1, T, 1, F., 1, z'). where Z' \ (E,, Tr, E.}, we could equivalently compute any probabilistic query efficiently. Note that under this interpretation, training our GeKCs by MLE over S, R, O would be equivalent to maximise composite marginal log- likelihood [70] over Z.
F Empirical Evaluation
F.1
Datasets Statistics
Table F.1 shows statistics of commonly-used datasets to benchmark KGE models for link prediction. We employ standard benchmark datasets [62, 21, 32] whose number of entities (resp. predicates) ranges from R 114 to 222.5M (resp. from 11 to 2x50)).
Table F.1: Dataset statistics. Statistics of multi-relational knowledge graphs: number of entities (EE)), number of predicates ([R)), number of training/validatioonnes triples.
Dataset
[3]
[
# Train
# Valid
# Test
FB15k-237
[62]
14,541
237
252.
17,535 3,034
20,466
WN18RR
[2]
40,943
11
86,835
3,134
ogbl-biokg
[2]
93,773
51
4,763 -10a
163 -10
163 -10a
ogbl-wikikg2
[32]
2.5 -106
535
16,
-103
429 -103
598 -103
25

---

F.2 Metrics
Mean reciprocal rank and hits k. Given a test triple (s. r.,o). we rank the possible object o' (resp. subject s') completions to link prediction queries rs, (resp. (?, r. o)) based on their scores in descending order. The position of the test triple (s, o) in the ranking of object (resp. subject) completed queries (s,r, o') (resp. (8', (,,,)))) is then used to compute the mean reciprocal rank (MRR)
MRR
Σ
rank(o s,r) + rank(s r.o)
2/9uss
(s
where Grest denotes the set of test triples, and rank(o) r), rank(s r, denote respectively the positions of the true completion (s,r, o) in the rankings of object and subject completed queries. The fraction of hits (Hits k) for l is computed as
Hits& K
Σ
(I(rank(o) s,r) s k) + 11 [rank(s (r,0) S k))-
2 2
(s,1,0)E9es
Consistently with existing works on link prediction [56, 12], the MRRs and Hits l metrics are computed under the filtered setting, i.e., we rank true completed triples against potential ones that do not appear in the union of training, validation and test splits.
Semantic consistency score. Let be a logical constraint encoding some background knowledge variables S, R and O. Given test triple (s, o), we first rank the possible completions link prediction queries in the same way as for computing the MRR. Then, the semantic consistency score (Sem@k) [33] for some integer k 0 is computed as
Sem@k
Σ
Σ [((s),d)kK]+
Σ
K}
(s. (dEA)((E))))
where Gue denotes the set of test triples, (s, r, o) (resp. A (s, denotes the list of the top-k candidate object (resp. subject) completions to the link prediction query (s, ?) (resp. (?, o)), and (s, 0) -= K if and only if (s, o) satisfies K.
F.3 Empirical KTD Score
Let F f {リy}リ= two sets of triples that are drawn i.i.d. from two distributions P, Q over triples. We compute the empirical KTD score with an unbiased estimator [28] (TTD(FF.9) as
mm(m- Σ (((()))
2 mn
m
k(v(a,),
ninn
iデj
For each data set, we compute the empirical KTD score between n = 25, 000 triples sampled from GeKCs and m test triples. case m n, we sample n triples randomly, uniformly and without replacement from the set of test triples. The time complexity of computing the KTD score is (nmhh). where h denotes the size of triple latent representations (h = 4000 our case, see Section 7.3). For efficiency reasons, we therefore follow Binkowski et al. [4] and randomly extract two batches of 1000 triples each from both the generated and the test triples sets and compute the empirical KTD score on them. We repeat this process 100 times and report the average and standard deviation in Table F.6.
F44 Experimental Setting
Hyperparameters. All models are trained by gradient descent with either the PLL the MLE objective (Eqs. (1) and (2)). We set the weights wa, Wr; w, of the PLL objective all to one, as to retrieve classical pseudo-log-likellhod [70]. Note that Chen et al. [12] set Way 42, one and treat wr as an additional hyperparameter instead that is opportunely tuned. The models are trained until the MRR computed on the validation set does not improve after three consecutive epochs. We fix the embedding size d = 1000 for both CP and COMPLEX and use Adam [38] as optimiser with 10 10-3 as learning rate. An exception is made for GeKCs obtained via non-negative restriction (Section 4.1), for which learning rate of 10 is needed, we observed very slow convergence rates. We search for the batch size in (5- 102, 10 2- 103 100) based the validation MRR. Finally, we perform repetitions with different seeds and report the average MRR and two standard deviations in Table F.2.
26

---

Parameters initialisation. Following [40, 12], the parameters of CP and COMPLEX are initialised by sampling from normal distribution (0, with o 10 -3 Since the embedding values in CP+ and COMPL.E** can be interpreted as parameters of categorical distributions over entities and predicates (see Appendix C.I), we initialise them by sampling from a Dirichlet distribution with concentration factors set to 10 To allow unconstrained optimisation for CP* and COMPLEX* we represent the embedding values by their logarithm and perform computations directly in log-space, iee. summations and log-sum-exp operations instead of multiplications and summations, respectively. Moreover, the parameters that ensure the non-negativity of COMPLEX* (see Appendix C.2) are initialised by sampling from normal distribution NO0 o²) with = 10 We initialise the parameters CP" and COMPLEX" such that the logarithm of the scores are approximately normally distributed and centred in zero during the initial optimisation steps, since this applies for the scores given by CP and COMPI.Ex Such initialisation therefore permits a fairer comparison. To do so, initialise the embedding values by sampling from log-normal distribution LW d²), where log (d) /3 o²/ /2 for CP and μ = log (2d)/3 d²/2 /2 for COMPLEX, both with o = 10-3 The mentioned values for j can be derived via Fenton-Wilkinsee Wilkinson approximation [24]. Even though the parameters of GeKCs obtained via non-monotonic squaring are initialised to be non-negative, they are free of becoming negative during training (as we also confirm in practice).
Hardware. Experiments on the smaller knowledge graphs FB15K-237 and WN18RR were run on a single Nvidia GTX 1060 with GiB of memory, while those on the larger ogbl-biokg and ogbl-wikikg2 were run on single Nvidia RTX A6000 with 48 GiB of memory.
F.5
Additional Experimental Results
F.5.1
Link Prediction Results
In this section, we present the additional results regarding the link prediction experiments showed in Section 7.1 and analyse different metries and learning settings.
Statistical tests and hits at k. Table F.2 shows the best test average MRRs (see Appendix F.2) with two standard deviation and average training time across 5 independent runs with different seeds. We highlight the best results in bold according to one-sided Mann-Whitney U test with confidence level of 99%. The showed results terms of MRRs are also confirmed in Table E3,, which shows the best average Hits @ (see Appendix F.2) with & E (1,3, 10).
Average log-likelihood. For the best GeKCs for link prediction showed in Table F.2, we report the average log- ligeliieo of test triples and two standard deviations (across 5 independent runs) in Table F.4. We again highlight the best results in bold, according to a one-sided Mann-Wai Whinney U test.
Quickly distilling parameters. As discussed in Section 4.2, since learned KGE models mostly assign non-negative scores to triples (see Appendix D) we can initialise the parameters of GeKCs obtained by squaring with the parameters of already-learned KGE models, without losing much in terms of link prediction performances. Here, we test this hypothesis and fine-tune GeKCs initialised in this way by using either the PLL MLE objectives (Eqs. (1) and (2)). To do so, we first collect the parameters of the best CP and COMPLEX found for link prediction (see Section 7. Then, we initialise GeKCs derived by squaring with these parameters and fine-tune them until the MRR computed on validation triples does not improve after three consecutive epochs. We employ Adam [38] as optimiser, and we search for the batch size in (5 102 10 2 10 5 10 } and learning rate in (10-3 10-4], as fine-tuning may require lower learning rate than the one used in previous experiments (see Appendix F.4). Table F.5 shows the MRRs achieved by CP, COMPLEX and the corresponding GeKCs obtained via squaring that are initialised by distilling the parameters from the Atready-trained CP and COMPLEX. On FB15K-237 and WN18RR, distilling parameters induces a substantial improvement in terms of MRR with respect to CP² and COMPLEXX whose parameters have been initialised randomly (see Appendix F.4). Furthermore, for COMPL.Ex* and on WN18RR and ogbl-biokg we achieved similar MRRs with respect to COMPLEX without the need of fine-tuning.
27

---

Table F.2: GeKCs are competitive with their energy-based counterparts. Best test MRRs (and two standard deviations) of CP, COMPLEX and GeKCs trained with the PLL and MLE objectives (Eqs. (1) and (2)). In parentheses we show the average training time (in minutes).
FB15k-237
WN18RR
ogbl-biokg
Model
PLI
MLE
PL.
MLE
PL.
MIE
CP
0.310 #0.001 (8)
0.105 #0.007 (II)
0.831
#0.001 (136)
CP
0.237 +0.003
(1) 0.230 +0.003
(1)
0.027
#0.002 ()) 0.026
#0.001
(1)
0.496 #0.013 (172) 0.501
+0.010 (142)
CP2
0.315 20.003
(8) 0.282
#0.004
0.104
#0,001 (23) 0.091 =0.004
(23) 0.848 =0.001
(66) 0.829
+0.001
(61)
COMPLEX
0.342 #0.005 (36)
0.471 =0,002 (16)
0.829 =0.001 (180)
COMPLEX*
0.214 40.003
0.205
#0.006
0.030
#0.001 0.029
=0.001
(3) 0.503 =0.014 (245) 0.516 +0.009 (212)
COMPLEX² 0.334 #0.001 (10) 0.300 #0.003 (16) 0.420 #0.011 0.391 =0.004 (19) 0.858 #0.001 (71) 0.840 #0.001
Table F.:: H results. Average test Hits@ for E (1,3, 10) of CP, COMPI.Ex and CP2 and COMPLEX? trained with the PLL or MLE objectives.
FB15k-237
WN18RR
ogbi-bbokk
PLL
MLE
PLL
MLE
PLL
MLE
Model
10
10
3
10
3
10
10
3
10
CP
22.4
34.1
48.2
7.5
16.8
76.4
88.1
95.0
CP
17.0
25.8
36.7
16.7
24.9
35.4
1.7
2.7
4.5
1.6
2.5
4.4
38.0
54.4
73.4
38.4
55.0
74.4
CP²
23.1
34.8
48.2
20.5
30.8
43.5
6.7
12.1
17.6
5.9
10.7
15.3
78.6
89.5
95.7
76.1
83.1
95.0
COMPLEX
25.2
37.5
52.5
43.3
48.6
54.6
76.1
87.9
COMPLEX*
15.7
23.1
31.7
15.0
22.1
30.4
1.5
2.7
4.5
1.6
2.5
4.4
38.8
55.1
74.1
40.0
56.7
75.9
C
24.5
36.9
51.1
21.6
33.0
46.7
36.0
45.6
52.4
34.5
42.3
46.9
80.0
90.1
95.8
77.5
88.8
95.4
Table F.4: Better distribution estimation with GeKCs obtained via squaring. Average log- likelihood of test triples achieved by baselines and GeKCs trained with the PLL or MLE objectives.
Model
FB15k-237
WN18RR
ogbl-biokg
Uniform NNMFAug
-24 638
-23.638
-26 829
-19.270
-22.938
-17.562
PLL
MLE
PLL
MLE
PLL
MLE
CP+
-16.773 +0.040
-6.599 +0.059
-21.987 30,006
-22.103
+0.010
-17.900 +0.048
-17.416 =0.049
Cp2
-17.105 +0.031
-15.982
+0.028
224.91
#0.241
-26.352
+0.077
-17.231
+0.059
-16.533 20.013
COMPLEX*
-17.507 +0.035
-17.592
+0.039
-21.233 #0.058
-21.432 +0.008
-18.716
+0.088
-17.749 #0.019
COMPLEX²
-17.100 +0.026
-15.744 +0.041
-19.522
#0.530
-19,739
+0.214
-17.340
+0.022
-16.518 #0.003
#0.003
Table F.5: Distilling parameters can improve performances. Test MRRs achieved by CP, COM- PLEX and GeKC' obtained by squaring (Section 4.2). For CP² and COMPLEX² we report the best MRRs achieved by distilling the parameters from the already-learned CP and COMPLEX (denoted with +), and with we denote those results for which further fine-tuning with the PLL or MLE objectives did not bring better results. We underline results for which distilling parameters increased the MRR.
FB15k-237
WN18RR
ogbl-biokg
Model
PLI.
MLE
PLL
MLE
PL.
MLE
CP
0.311
0.108
0.831
COMPLEX
0.344
0.470
0.829
CP2
0.317
0.285
0.103
0.089
0.849
0.830
CP2
0.327
0.315
0.102
0.115
0.851
0.828 f
C
0.333
0.301
0.416
0.390
0.859
0.839
2
0.342
0.340
0.462 t
0.463
0.859
0.828 f
28

---

F.5.2 Quality of Sampled Triples Results
In this section, we provide additional results regarding the evaluation of the quality of triples sampled by GeKCs (see Section 7.3). For these experiments, we search for the same hyperparameters as for the experiments on link prediction (see Appendix F.4,, and train GeKCs until the average log-likelihood computed on validation triples does not improve after three consecutive epochs.
Table F.6 shows the mean empirical KTD score and one standard deviation (see Appendix F.3). In addition. we visualise triple embeddings of sampled and test triples in Fig. F.1 by leveraging t-SNE [69] as method for visualising high-dimensional data. In particular, we apply the t-SNE method implemented in scikit-learn with perplexity 50 and number of iterations 5- 10s, while other parameters are fixed to their default value. As showed in Fig. F. an empirical KTD score close to zero translates to an high clusters similarity between embeddings of sampled and test triples.
Table F.;: GeKCss trained by MLE generate new likely triples. Empirical KTD scores between test triples and triples generated by basclines and GeKCs trained with the PLL objective by MLE (Eqs. (1) and (2)). Lower is better.
Model
FB15k-237
WN18RR
ogbl-biokg
Training set
0.055 +0.007
0.260 #0.013
0.029 #0.010
Uniforn
0.589 +0.012
0.766 +0.036
1.822 #0.044
NNMFAug
0.414 #0.014
0.607 +0.028
0,518 #0.035
PLL
MLE
PLL
MLE
PLL
MLE
CP
0.404 20.016
0,433 20.015
0.633 20.033
0.578 #0.029
0.966 #0.040
0.738 20.030
CP2
0,253 +0.014
0.070 +0.007
0.768 20.036
0.768 #0.036
0.039 =0.009
0.017 #0.013
COMPLEX*
0,336 20.016
0.323 20.015
0.456 20.018
0.478 20.019
0.175 20.019
0.097 20.013
COMPLEX
0.326 20.016
0.102 20.010
0.338 a0.020
0.278 20.017
0.104 zb.010
0.034 20.007
(a) FB15k-237 KTD- 0.102 + 0.010
(b) WN18RR
(c) ogbl-biokg KTD 0.034 + 0.007
KTD 0.278 + 0.017
Figure F.1: Sampled triples are close to test triples. t-SNE [69] visualisations of the embeddings of test triples (in blue) and triples sampled by COMPLEX² (in orange). The distribution shift between training and test triples on WN18RR mentioned in Section 7.3 is further confirmed in Fig. F.Ib, as it shows a region of test triples (at the bottom and in blue) that is not covered by many generated triples.
F,5.3 Calibration Diagrams
Existing works on studying the calibration of KGE models are based on interpreting each possible triple (s, r. o) as an independent Bernoulli random variable Y.ro whose likelihood is determined by the score function d. i.e., Pr(Y.ro
s, r. o) (d(s,r, [61, 54, 79], where denotes the logistic function. While GeKCs encode a probability distribution over all possible triples, this does not impede us to reinterpret them to model the likelihood of each Y by still considering scores in log-space as negated energies (see Section 2). Therefore, to evaluate the calibration of GeKCs encoding a non-negative score function &pe (see Section 4) we compute the probability of a triple 1 s, T, 0) a olog @pc (s, o)). However, the usage of the logistic
(s, r, o) being true as p(Y
29

---

function might give misleading results in case of scores not being centred around zero on average. Therefore, we also report calibration diagrams (see paragraph below) where the p is obtained via min-max normalisation of the scores given by KGE models (the logarithm of the scores given for GeKCs), where the minimum and maximum are computed on the training triples. Note that several ex- ex-post (re- rre))calibration techniques are available [61, 79], but they should benefit GeKCs as they do with existing KGE models.
s, r, o)
Setting and metries. To plot calibration diagrams. we follow Socher challenging negative triples, i.e. for each test triple (s, o) we sample an unobserved perturbed one (s, r, 0) by replacing the object with an entity that has appeared least once with the predicate
[59] and sample
r in the training data. We then compute the empirical calibration error (ECH) [79] as ECE ==
E. Ip, f, where b is the number of sefformll-chosser bins for the interval [0, 1] of triple probabilities, and Pj. are respectively the average probability and relative frequency of actually existing triples in the j-th bin. The lower the ECE score, the better calibrated are the predictions, as they are closer to the empirical frequency of triples that do exist in each bin. The calibration curves plotted by considering the relative frequency of existing triples in each bin, and curves closer to the main diagonal indicate better calibrated predictions.
GeKC Cs are more calibrated out-of-the-box. Fig. F.2 (resp. Fig. F.3) show calibration diagrams for GeKCs derived from CP and COMPLEX trained with the MLE objective (Eq. (2)) (resp. PLL objective (Eq. (1))). In 19 cases over 24, GeKCs obtained via squaring (Section 4.2) achieve lower ECE scores and better calibrated curves than CP and COMPL.EX. While GeKCs obtained via non-negative restriction (Section 4) )) are not well calibrated when using the logistic function, on ogbl-biokg [32] they still better calibrated than CP and COMPLEX when probabilities via min-max normalisation. Furthermore, on WN18RR GeKCs achieved the highest ECE scores (corresponding to poorly-calibrated predictions), which could be explained by the distribution shift between training and test triples that was observed for this KG in Section 7.3 and further confirmed in Appendix F.5.2.
obtained
30

---

FB15K-237
WN18RR
ogbi biokg
Ralio
0.0
0.4
0.0
0.8
1.0
1.0
CP BCE 0.307
CP ECE: 0.272
CP ICE 0421
CP BOB
CP+ 01900
DCI:0.000
(a)
1.0
of of
0.8
0.6
0.1
0.2
0.0
CP- PCTS 01151
CP 0.500 0.500
CP- ROR 0464
CP 0.00
CP BCB 0:351
CP BCCS 0.161
FB15K-237
WN18RR
ogbl-biokg
1.0
of Poxities
0.5
0.6
0.4
0.2
0.0
CP ECE: 0.307
CP 0.B.0222
CP ECE 0422
-.C:00.00
(
CP -.CE
ECE. 0.655
CP BCE 0.64
1.0
Ratio Positves
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
BCE:
CP
0.300
CP ECE
0.401
CP ECEE 0.199
CP
CP' ECE: 0.357
CP CCE.CEE 0.167
Figure F.2: Better calibrated predictions with CP2, Calibration diagrams of CP. CP* and CP2 trained with either the PLL (Fig. F.2)) or MLE (Fig. F.2b) objectives. The probability of triples are obtained via the application of the logistic function (rows above) and min-max normalisation (rows below). See Appendix F.5.3 for details. The calibration curves for CP+ where triple probabilities are obtained with the logistic function do not provide any meaningful information, the logarithm of their scores are generally distributed over large negative values.
31

---

FB15K-237
WN18RR
agbi-blokg
1.0
Ratio of
0.0
0.2
0.4
0.88
0.6
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.8
0.8
10
COMPLEX" BCE: IL306
COMPLEx* ECE 0,500
COMPLEX" BCE: 0.500
(a)
COMPLEX 0,17:0.77
COMPLES Ex BU3:
COMPLIXX 1C1e
1.0
Ratio Positner
0.0
0.2
0.4
0.0
0.8
1.0
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
COMPLEX"
BCE 0.237
COMPLEx* ECE
0.312
COMPLEX"
0.E:00.50
COMPLEX
0.0000000
COMPLEX"
COMPLEXX
FB15K-237
WN18RR
ogbi-bbokg
1.0
Ratio-of of Posiives
088
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
10
COMPLEX-
COMPLEN: ECB:0.230
CoMPi iit" -RCH 0.949
COMB Rx+ -KC 0,500
COMPLEXX -RCR-D.500
(b)
COMPLEX" -BCEEX
COMPLEX"
1.0
Ratio of Posstives
088
0.6
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.5
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
COMPLEX-
COMPLEN: ECB:00584
COMPLEX-
COMPLEN" -BCCE-U2 0.251
COMPLRC* IKC 0.10
COMPLEXX"
-BCB-U.MM
COMPLEX -BCR-0.22
Figure F.3: Better calibrated predictions with COMPLEX2 Calibration diagrams of COMPLEX, COMPL.Ex* and COMPLEX² trained with either the PL. (Fig. F.3a) or MLE (Fig. F.3b) objectives. The probability of triples are obtained via the application of the logistic function (rows above) and min-max normalisation (rows below). See Appendix F.5.3 for details. The calibration curves for COMPLEX* where triple probabilities are obtained with the logistic function do not provide any meaningful information, as the logarithm of their scores are generally distributed over large negative values.
32


Reviews:
[{"review_id": "KfrFD8NfTf", "reviewer": "Reviewer_v5Gr", "summary": "This paper provides a reduction from several well-known knowledge graph embedding (KGE) methods (e.g., TuckER, CP, etc.) to *decomposable* circuits $\\phi$ which can be efficiently computed in $O( (|E| + |R|) |\\phi|)$ (note that this is mostly due to the decomposable nature of TuckER and its derivatives). The authors then address the problem that $\\phi$ can be negative and hence suitable to directly represent a probability distribution by applying one of two operations---non-negativity or squaring---which allows the circuit to be efficiently learnt and sampled from. Finally, they show how the circuit formalism allows one to easily apply domain constraints as the product of the two circuits.\n\nThe authors then evaluate their proposed variants of the KGE methods on four knowledge graphs, where they show (1) their squared variant produces comparable or better results to the original variants with significant computational speedups, (2) their method guarantees domain constraints, and (3) their squared method generates higher quality samples than state-of-the-art. They authors present several additional results in their appendices including: showing that it is feasible to distilling parameters from already trained circuits to the proposed variants (which allows them to be sampled from) and showing that the proposed variants are better calibrated than the original ones.", "questions": "The paper is extremely well-written and clear, and I don't have any questions.", "limitations": "* While the paper reduces several existing KGE methods to circuits, the reduction is quite straightforward and only practical for this family of circuits.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* This is a meticulously executed paper with thorough empirical evaluation. While its key results are in the paper, there are many more interesting and insightful experiments in the appendix.\n* The paper presents a useful and elegant theoretical framework for computing knowledge graph embeddings that *extends* existing methods like TuckER or ComplEx allowing them to be learned and sampled from efficiently (it's not just conceptual).\n* The paper is extremely well-written and clear.", "weaknesses": "* While the paper reduces several existing KGE methods to circuits, the reduction is quite straightforward and only practical for this family of circuits. There are other KGE methods (e.g. graph neural networks) that are not covered by this paper or its related work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating the rigor, novelty and direction of our research! Such a simple idea can open up many valuable perspectives.\n\n> There are other KGE methods (e.g. graph neural networks) that are not covered by this paper.\n\nIndeed, connecting circuits with more general KGEs such as GNNs is a promising idea.  Unfortunately, these models are generally more difficult to deal with, given the presence of some non-linearities that cannot be modeled within the language of tractable circuits. However, recently a connection between GNNs and tensor factorization-based KGE models has been established [A], thus our analysis might well be useful  for connecting GNN-based models and circuits in future work.\n\nAdditionally, in our response 1 to reviewer S5Mx we sketch how to turn other KGE models such as TransE and RotatE into GeKCs. However, this is not straightforward and is left to future  work.\n\n[A] Y. Chen et al. ReFactor GNNs: Revisiting Factorisation-based Models from a Message-Passing Perspective (2022).\n\n"}, {"review_id": "nbdp9m5dZX", "reviewer": "Reviewer_P87h", "summary": "This paper converts score functions of knowledge graph embeddings into generative KGE circuits (GeKCs) by restricting activations to be non-negative or squaring their outputs. \nThe changes come with little or no loss of link prediction performance, \nwhile enabling probabilistic interpretations, exact maximum-likelihood estimation, better scaling when trained with discriminative objectives, efficient sampling of new triples, and logical constraints such as domain schema definitions. \nThe paper additionally proposes a metric for measuring the quality of sampled subject-predicate-object triples.", "questions": "1. To confirm understanding: the model difference between GeKCs and other KGEs is constraining scores to be non-negative or squaring them, and nothing else, right? \n2. About scaling.\n(a) Why does the GeKCs scale better, given the additional squaring operations or non-negative restrictions?\n(b) Is MLE intractable for the models in the paper that can be but are not yet converted to GeKCs? Can you elaborate on why?\n3. About loss. When is PLL training recommended and when is MLE training recommended? Why?\n4. About probabilities. (a) L29 says the scores cannot be compared across different queries, but L27 gives an example of scores being compared. Why? At least within the same model, negative energies can be compared, right? (b) L29: What are the cases where we want to compare scores across KGE models? (c) What's the benefit of having a probabilistic model instead of an energy based model?\n5. About sampling. Why would people want to generate a surrogate KG or do data augmentation? The aim for knowledge graph embeddings is to answer queries over incomplete knowledge graphs. Does having a generative model help this purpose?\n6. About logical constraints. Can we set energies to infinity if a query violates logical constraints? It seems that without the probabilistic framework presented in this paper, one may still be able to enforce logical constraints.\n7. About generality of the method. This paper turns the score functions of KGEs into probabilistic circuits. Can the same be applied to turn score functions in all sorts of models into PCs?\n8. L231: What does consistent mean?\n9. Eq. (3): There are two levels of \"=\". Please differentiate them to avoid difficulty in parsing the formula.\n10. L307: Initializing by CP and ComplEx should not be called distillation.\n11. L361: How can KGEs be smaller, now that the presented circuits are already with only 2 layers?\n\nUpdate: The authors addressed my major concerns in the rebuttal.", "limitations": "The paper mentions future work which may be considered limitations. It does not seem to discuss negative societal impact, which it may not directly have.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Novel combination of probabilistic circuits and knowledge graph embeddings.\n- Clear presentation. Solid theory.", "weaknesses": "1. Multiple questions regarding the motivation (i.e. why the introduced properties are useful) need to be clarified. See Questions.\n2. Empirical results are not motivating enough. \n(a) Sec. 7.1 doesn't show evidence that GeKCs are always preferred for link prediction in terms of accuracy or provide actionable knowledge about on what datasets GeKCs may perform better. \n(b) In Sec. 7.2 Integrating Domain Constraints, d-ComplEx2 results are 100 by design, but the baseline ComplEx also achieves very high numbers (99+) while ComplEx2 has worse-than-baseline results. Can you provide d-ComplEx2's general link prediction performance as compared to methods in Sec. 7.1's experiments, so that people can decide whether it is worth using in practice? Do you have results on more than one dataset and more than one model?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for all the comments. We believe we addressed all the concerns and are happy to follow up in the discussion phase.\n>The difference between GeKCs and other KGEs is constraining scores or squaring?\n\nYes, although apparently simple, this modeling difference enables the semantic of normalized probabilities which unlocks a new set of capabilities for KGE models: (i) scaling training to very large KGs (ii) guaranteeing satisfaction of constraints by design which is crucial in high-stake scenarios, and (iii) generative capabilities. This is possible only thanks to recent theoretical advancements in circuits [72].\n>Empirical results are not motivating enough\n\nWe remark that the goal of our paper is *not* doing SOTA results for link prediction (L289-290) but to show that a new class of KGEs can excel in other important directions, namely (i-iii) highlighted above. Furthermore, in terms of link prediction only, GeKCs score comparable or better than KGE baselines. Therefore making a strong alternative if one is interested in (i-iii).\n>d-ComplEx2 results are 100 by design, but ComplEx also achieves high numbers\n\nNote that while ComplEx can achieve 99+% semantic consistency, it still predicts more than 360 of semantically invalid triples (see L327-328). Even if it achieved 100% on the test set, it would not guarantee that predictions will be valid for future queries. Our method instead guarantees predictions that will **always be valid**, which is crucial in high-stake applications as pointed out by reviewer t9NK.\n>Can you provide d-ComplEx2's link prediction performance\n\nWe did not run D-ComplEx^2 on FB15K-237 and WN18RR because they do not come with constraints, differently from ogbl-biokg. In the attached pdf, we show that GeKCs with domain constraints perform similarly or better than GeKCs alone (and better than other KGEs). We are happy to experiment on additional KGs with domain constraints suggested by the reviewer.\n>Why does the GeKCs scale better?\n\nBecause summations in PLL and MLE can be pushed down to the inputs of circuits, thus requiring only linear time w.r.t. the number of entities and predicates (L148-155). This further simplifies the complexity w.r.t. the batch size, as we formalize in Appendix C.4.1-2.\n\nSquared GeKCs adds a minor overhead (see answer 3 to reviewer S5Mx), which is absorbed by the aspects above.\n>When is PLL/MLE recommended?\n\nMLE is recommended to learn better generative models, to improve sample quality (see Table 2). By contrast, as expected by training with a discriminative objective, training via PLL favors link prediction scores, but falls short in other inference tasks. We detail the PLL-MLE relationship in answer 2 to reviewer t9NK.\n>Can Negative energies be compared?\n\nWe can only compare the scores of triples that answer the same query to get an ordering for ranking (L27). Scores associated to different queries (eg, different predicates) can differ a lot and are not informative without renormalizing. This can negatively affect a concrete scenario such as complex query reasoning, where scores associated to triples with different predicates are compared. Recently this particular aspect has been investigated in [B].\n>Why comparing scores across KGE models?\n\nComparing scores is useful to perform model selection or model integration. For model selection, the log-likelihood is the canonical way to compare probabilistic models but requires normalized probabilities. For integration, consider this real-world application: consolidate several existing KGEs from Wikipedia in different languages or integrate them with a probabilistic LLM: we need scores that are normalized in the same range.\n>Why sampling?\n\nSampling enables us to approximate complex probabilistic inference scenarios, eg, via Monte Carlo estimates. Particularly for KGs, this was useful to approximate the proposed Kernel Triple Distance (Appendix F.3) or to answer complex queries [10,15]. Also, [9] has shown that performing data augmentation via sampling during training can be beneficial for link prediction.\n>Can we set energies to infinity if a query violates constraints?\n\nFiltering EBMs predictions ex-post can be done, but with an external reasoner and this can be very expensive in practice.  Eg, to answer a query $(s,p,?)$ we need first to find all objects $o’$ for which $(s,p,o’)$ violates the constraint. This requires calling a reasoner for possibly millions of objects. For more complex reasoning scenarios, involving predicting multiple links, the number of calls quickly grows (eg, finding all objects $o’$ such that $\\exists V.(s,p,V)\\land (V,p’,o’)$ is satisfied). The missed opportunity here is to amortize all the intermediate reasoning computations done for the same $(s,p)$, or $(p,o)$ when later we want to answer $(?,p,o)$.\nThe knowledge compilation step in our models (L242-244) does exactly this, converting these reasoner calls into a compact circuit structure [18,51].\n>Can we turn all sorts of models into PCs?\n\nInvestigating how to turn other KGE models into GeKCs is surely interesting and worth a follow up, please see our responses to reviewers v5Gr, S5Mx.\n>What does consistent mean?\n\nWe will specify in the camera-ready that consistency means that entities satisfy the logical constraint.\n>There are two levels of \"=\".\n\nThanks, we will fix it in the camera-ready.\n>Initializing by CP and ComplEx should not be called distillation.\n\nThanks, we will fix that line by mentioning we are indeed performing fine-tuning as reported in Table F.5.\n>How can KGEs be smaller, now that the presented circuits are already with only 2 layers?\n\nWe can leverage the data to learn __sparser__ structures of KGE models. For example, by clustering triples (or entities/predicates) we can smartly construct connections encoding particular dependencies and avoid “fully connected” layers as they are now. \n\n[B] E. Arakelyan et al. Adapting Neural Link Predictors for Data-Efficient Complex Query Answering 2023\n"}, {"review_id": "NxL3R5fgmv", "reviewer": "Reviewer_t9NK", "summary": "The authors show that standard KGE models, such as COMPLEX, can be represented as structured computational graphs called circuits. They propose a new interpretation of these graphs and their parameters to create efficient and expressive probabilistic models over triples in a KG, called generative KGE circuits (GeKCs). These can be efficiently trained by exact MLE and scale well on large KGs with millions of entities. GeKCs can also sample new triples exactly and efficiently, and predictions at test time never violate logical constraints such as domain schema definitions. Experiments show that these advantages come with little or no loss in link prediction accuracy.", "questions": "Q1: It is not clear from line 89 why (2) is considered a proxy for (1). Can you provide more details on the reasoning behind this?\n\nQ2: In Table 2, it is not stated why the results from [12] were not included as a baseline. Is there a specific reason for this?", "limitations": "Limitations are discussed in sec 7.1 and sec 8.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- This paper is well-written, with clear language and a well-structured presentation. I enjoy reading it.\n- The idea of making KGEs generative is brilliant! There have been so many new KGEs in the past years, we constantly rely on real world datasets. Now with the proposed method, we can actually generate KG datasets conveniently.\n- The re-interpretation of existing training objectives as MLE is very clever. \n- Additionally, the proposed method makes it easier to add constraints to KGEs. \n- The experiments are clearly designed and well-executed, further demonstrating the value of this work. \n\nOverall, this paper is a valuable contribution to the field and deserves a wide audience for its insights and rigorous analysis.", "weaknesses": "Maybe not a weakness but some extension?\n\n- The constraint adding part can be extended into another work. I can imagine, in high-stake decision-making applications like finance etc, adding constraints can play a vital role.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for valuing the significance of our contribution as well as its execution.\n\n\n> “The constraint adding part can be extended into another work”\n\nThanks for recognizing the significance of our work for reliable decision making in safety-critical scenarios. We have some applications of KGE models in biomedical domains in mind, where indeed making trustworthy predictions is crucial if we want to deploy these models and use them. We are very open to additional suggestions.\n\n\n> It is not clear from line 89 why (2) is considered a proxy for (1). \n\nWe say the PLL is a proxy of the actual log-likelihood because, under certain assumptions, it is possible to show that the PLL objective can retrieve the MLE solution asymptotically with enough data [C].\n\nTo give more context, computing the partition function is infeasible for traditional KGE models when dealing with large knowledge graphs. This generally holds for arbitrary energy-based models (EBMs). In the EBM literature, the pseudo-log-likelihood (PLL) circumvents the problem of computing the log-likelihood exactly as it is easier to compute (it requires summing over only one variable at a time).\n\nAn additional difference is that the PLL is a classical discriminative objective while the MLE is a generative one. As such, it permits to obtain a better estimate of the joint probability distribution, and not just (one or many) conditionals, thus being more suitable for generative tasks such as sampling or imputation.\n\n\n> In Table 2, it is not stated why the results from [12] were not included as a baseline. \n\nOur PLL objective is a generalization of the loss used in [12]. In fact, the loss used in [12] can be retrieved from the PLL by setting $\\omega_s = \\omega_o = 1$ and leaving $\\omega_r$ as an hyperparameter. We highlight this in L920-921 in the appendix.\n\nTherefore, our experimental setting with CP and ComplEx when using the PLL encompasses the one in [12] under the column labeled with PLL in Table 1 (here we are assuming the reviewer is referring to Table 1 and not 2, please let us know if that is not the case). The difference in terms of MRR w.r.t. [12] is due to a simplified experimental protocol: a smaller grid search and fixing $\\omega_r = 1$. This is because of our limited computational resources, but searching more hyperparameters (and for longer) would likely bring better results for all models.\n\n[C] A. Hyvärinen, Consistency of Pseudolikelihood Estimation of Fully Visible Boltzmann Machines (2006)\n"}, {"review_id": "4comGMCX4h", "reviewer": "Reviewer_S5Mx", "summary": "This paper provides an new perspective for looking at the popular knowledge graph embedding (KGE) method for knowledge graph completion. Specifically, KGEs models are re-interpreted as circuits. The paper first prove the circuits-based equivalence of score functions of several KGE models, and, in order to regulate KGE further as probabilisitic circuits (GeKC), two restrictions (i.e., non-negative, squaring) are introduced to modify the score functions. Additionally, two techniques are proposed to improve GeKCs: firstly, utilizing trained KGEs as initialization for efficient training of GeKCs, and secondly, introducing constraints to modify the support of GeKCs.\n\nThe empirical experiments demonstrate that GeKCs exhibit competitive performance compared to PLL objective applied in KGE. Moreover, the proposed constraint method is justified to avoid constraint violations during inference. Finally, the paper compares GeKCs' ability to the uniform and NNMFAug baseline, showing GeKCs' strong capability to generate new likely triples.", "questions": "1. Could other KGE models such as TransE, RotatE be viewed as circuits?\n2. In line251, how is |c_k| be calculated? Does that mean constrained GeKCs generally have higher computational cost compared to the one without constraints?\n3. Why does training time for squared-COMPLEX in ogbl-biokg decrease compared to COMPLEX/COMPLEX+? Theorem 1 suggests that squared-GeKCs have a higher level of complexity than that indicated in proposition 2.", "limitations": "I do not find out any potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Generally the paper presents a novel perspective for the knowledge graph embedding model. This perspective enables researchers to learn KGE models through MLE and therefore build a generative model based on those models. Additionally, logical constraints can be incorporated to this framework to ensure that projected triples are valid during inference.", "weaknesses": "The perspective of probabilistic circuits seems to be limited. As in the paper, the score functions of KGE models interpreted as circuits are mainly basd on tensor factorization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and pointing out how GeKCs are indeed competitive with existing KGE models.\n\n> Could other KGE models such as TransE, RotatE be viewed as circuits?\n\nThis is a super interesting question. Here are some ideas.\n\nTo our knowledge, distance-based KGE models like TransE and RotatE have not been trained as energy-based models using the pseudo-log-likelihood (PLL). In fact, they are not shown in Figure 2 in [55], which compares several KGE models on different experimental settings.\n\nThis is likely because they have different semantics than tensor factorization-based models.  Indeed, the scores computed by TransE and RotatE are “distances”, while scores given by tensor factorization-based models are “similarities”. The first have been interpreted as energies while the latter as negative energies (see L68-70).\n\nOne possible way to represent TransE as a probabilistic circuit (PC) is by using a squared norm-2 as distance measure. By doing so, the scores (distances) would be a sum over squares, which can be written as a sum of decomposable squared circuits as done in our work. Representing RotatE as a PC is more challenging. This is because to our knowledge, RotatE is based on a norm-1 on complex embeddings and therefore it would require computing square roots. However, if we slightly modify the original RotatE formulation to use a squared norm-2 instead, we should recover a circuit akin to the one for TransE.\n\nOnce we turn TransE/RotatE into a PC, then it would encode a probability distribution $q(S, R, O)$ assigning low probability to likely triples and high probability to unlikely triples, since scores are energies (see above). To solve this issue, it might be possible to model the distribution $p(S,R,O) \\propto 1 - q(S, R, O)$ with a circuit and then re-normalizing it (which can be done efficiently). By doing so, we should possibly be able to train them using the PLL objective, akin to the proposed GeKCs. This is certainly an interesting perspective that deserves to be investigated rigorously in a follow up work.\n\n\n> In line251, how is |c_k| be calculated?\n\n$|c_K|$ is calculated by counting the number of edges in the compiled logic circuit, which depends on how complicated the logical formula $K$ is.\n\nFor domain constraints, we have shown in Proposition A.1 that in the best case it is linear in the sum of the number of entities $|E|$ and the number of predicates $|R|$. In the worst case is instead linear in the product $|E| \\cdot |R|$. In practice, we noticed that on ogbl-biokg the domain constraints are much closer to the best case scenario. In fact, the size of the logic circuit is $306,841$ while $|E|=93,773$ and $|R|=55$.\n\n\n> Does that mean constrained GeKCs generally have higher computational cost compared to the one without constraints?\n\nThe computational cost of constrained GeKCs is similar to the cost of multiplying two circuits. In the **worst** case is the product of the sizes of the two circuits, but this is a loose bound and in practice the complexity is much lower as already noted in [D] [72].\n\nFigure 3 supports this claim in practice, since ComplEx^2 brings only a small overhead with respect to ComplEx+ and can be much faster than ComplEx.\n\nTo put this in context of the constrained circuits, multiplying by a $c_K$ is going to add a similar overhead, worst case proportional to $|c_K|$. Luckily, the size of $c_K$ for ogbl-biokg is $306,841$. Now consider that the size of the circuit for ComplEx(+) with embedding size 1000 is already much larger, about $375 \\cdot 10^6$ and by the same argument in Figure 3 their product should not add more overhead. \n\n\n> Why does training time for squared-COMPLEX in ogbl-biokg decrease compared to COMPLEX/COMPLEX+? \n\nThe times shown in Table 1 are relative to the best models found based on validation data, which might have different hyper-parameters and therefore converge at different rates. The results of a more accurate benchmark on the much larger knowledge graph ogbl-wikikg2 are shown in Figure 3.\n\n[D] Y. Shen et al., Tractable Operations for Arithmetic Circuits of Probabilistic Models (2016)\n"}]

Author rebuttal:
We thank all reviewers for the time spent reviewing the paper and recognizing the **significance** (“useful and elegant theoretical framework” – v5Gr, “solid theory” – P87h, “deserves a wide audience for its insights and rigorous analysis” – t9NK) and **novelty** (“Novel combination” – P87h, “making KGEs generative is brilliant!” – t9NK, “novel perspective” – S5Mx) of our research direction, as well as the **quality of the presentation** (“meticulously executed paper” – v5Gr, “clear presentation” – P87h, “well-written, with clear language and a well-structured presentation” – t9NK).

We provided below individual answers to your reviews, and we are happy to follow up on any aspect in the discussion phase.


Meta-review: The paper introduces an innovative perspective on knowledge graph embedding (KGE) models, allowing for generative model construction through maximum likelihood estimation (MLE). The incorporation of logical constraints enhances inference validity. The paper's clarity, well-structured presentation, and reimagining of training objectives as MLE have been mentioned as its strengths. The well-designed experiments further support the proposed methods. All reviewers are positive to very positive about his submission. I strongly recommend accepting this paper, as it significantly contributes a fresh perspective to the evolving landscape of KGE research.
Decision: Accept (oral)