Probabilistic Entity Representation Model for Reasoning over Knowledge Graphs
Authors: Nurendra Choudhary
Nikhil Rao
Sumeet Katariya
Karthik Subbian
Chandan K. Reddy
Venue: NeurIPS 2021 Poster (2021)
Keywords: gaussian space
probabilistic embeddings
knowledge graphs
query reasoning

Abstract: Logical reasoning over Knowledge Graphs (KGs) is a fundamental technique that can provide an efficient querying mechanism over large and incomplete databases. Current approaches employ spatial geometries such as boxes to learn query representations that encompass the answer entities and model the logical operations of projection and intersection. However, their geometry is restrictive and leads to non-smooth strict boundaries, which further results in ambiguous answer entities. Furthermore, previous works propose transformation tricks to handle unions which results in non-closure and, thus, cannot be chained in a stream. In this paper, we propose a Probabilistic Entity Representation Model (PERM) to encode entities as a Multivariate Gaussian density with mean and covariance parameters to capture its semantic position and smooth decision boundary, respectively. Additionally, we also define the closed logical operations of projection, intersection, and union that can be aggregated using an end-to-end objective function. On the logical query reasoning problem, we demonstrate that the proposed PERM significantly outperforms the state-of-the-art methods on various public benchmark KG datasets on standard evaluation metrics. We also evaluate PERM’s competence on a COVID-19 drug-repurposing case study and show that our proposed work is able to recommend drugs with substantially better F1 than current methods. Finally, we demonstrate the working of our PERM’s query answering process through a low-dimensional visualization of the Gaussian representations.

Probabilistic Entity Representation Model for Reasoning over Knowledge Graphs
Nurendra Choudhary', Nikhil Rao', Sumeet Katariya², Karthik Subbian', Chandan K. Reddy Department of Computer Science, Virginia Tech, Arlington, VA
2 Amazon, Palo Alto, CA
nurendrašvt edu, fnikhilsr, katsumee, ksubbian) com, reddyåcs.vt.c. vt.
Abstract
Logical reasoning over Knowledge Graphs (KGs) is fundamental technique that can provide efficient querying mechanism over large and incomplete databases. Current approaches employ spatial geometries such as boxes to learn query rep- resentations that encompass the answer entities and model the logical operations projection and intersection. However, their geometry is restrictive and leads non-smooth strict boundaries, which further results in ambiguous answer entities. Furthermore, previous works propose transformation tricks handle unions which results in non-closure and, thus, cannot be chained in a stream. In this paper, we propose Probabilistic Entity Representation Model (PERM) to encode entities as Multivariate Gaussian density with mean and covariance parameters to capture its semantic position and smooth decision boundary, respectively. Additionally, we also define the closed logical operations of projection, intersection, and union that can be aggregated using an end-to-end objective function. On the logical query rea- soning problem, we demonstrate that the proposed PERM significantly outperforms the ttate-of-the-ane methods on various public benchmark KG datasets on standard evaluation metrics. We also evaluate PERM's competence repurposing case study and show that our proposed work able to recommend drugs with substantially better Fl than current methods. Finally, we demonstrate the working of our PERM's query answering process through low-dimensional visualization of the Gaussian representations.
COVID-19 drug-
Introduction
Knowledge Graphs (KGs) are structured heterogeneous graphs where information is organized as triplets of entity pair and the relation between them. This organization provides a fluid schema with applications in several domains including e-commerce [[]. web ontologies P B and medical research 4 [ Chain reasoning is fundamental problem in KGs, which involves answering a chain of first-order existential (FOE) queries (translation, intersection, and union) using the KGs" relation paths. A myriad of queries can be answered using such logical formulation (some examples are given in Figure D. Current approaches 6 & in the field rely mapping the entities and relations onto representational latent space such that the FOE queries can be reduced to mathematical operations in order further retrieve the relevant answer entities.
Euclidean vectors ? provide a nice mechanism to encode the semantic position the entities by leveraging their neighborhood relations. They utilize a fixed threshold over the vector query for answer entities (such as k-nearest neighbor search). However, queries differ their breadth. Certain queries would lead greater set of answers than others, c.g., query Canadians will result in higher number of answers than query Canadian Turing Award winners. To capture this query behavior, spatial embeddings
learn border parameter that accounts for broadness of
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Q: Who (1) are the Canadian (C) and European (t) Turing (T)
Award (A) viinners (WY?
namess [Wijnnererss gategoryyT
nleibizen(W, Europe) cibizen Canada
Q: Which treatment drugs (T) interact with all proteins (P)
associated with SARS diseases (D)?
category
: 2
associate D.)l
Award
Turing Award
Winners
associate
Treatment
GRIGNTTN
SARS-COVE
Protein
Interacts
Europe
Europeans
Intersection
aesociate
union
BARS-COV2N
Protein 2
(a) Drug Repurposing (DRKG).
(b) Open-domain (FB15K).
Figure Sample FOE queries from different datasets that utilize existential quantification (7), intersection (N), and union (U) operations. The simple operations need to be chained together in an end-to-end objective function retrieve relevant results for complex queries.
queries by controlling the volume of space enclosed by the query representations. However, these spatial embeddings rely form solution to the union operation, e.g., the union of two boxes is not a box. Thus, further FOE operations cannot be applied to the union operation. Additionally, their strict borders lead some ambiguity in the border case scenarios and non-smooth distance function, e.g., a point on the border will have much smaller distance if it is considered be inside the box than if it considered be outside. This challenge also applies to other geometric enclosures such as hyperboloids
complex geometries such boxes 7 which do not have closed
Another line of work includes the of structured geometric regions [22 15| instead vector points for representation learning. While these approaches utilize the representations for modeling individual entities and relations between them, we aim provide closed form solution to logical queries over KGs using the Gaussian density function which enables chaining the queries together. Another crucial difference in our work is handling a stream of queries. Previous approaches rely on Disjunctive Normal Form (DNF) transformation which requires the entire query input. In our model, every operation is closed in the Gaussian space and, thus, operations of large query can be handled individually and aggregated together for the final answers.
density functions
13 14
014
Europeans
Europeans
LeCunn
LeCunn
Bengio
LeCunn
Hinton
-010
Citizen
Canadinn
French
Brithh-Cnnddann
0.09
Fumpewn
0.213
1.343
0.146
1.589
1114
Union
0.146
0.211
1114
Canadians
Bengia
Hinton
Hinton
0.06
Bengio
0.05
Gaussian Misture
Canadan
0.146
1.57
1118
Canadians
0.03
(c) Distance of entitics from query space. For comparability, distances are given relative to entity Bengio's distance to European query.
0.00
(a) Union of box queries.
(b) Gaussian mixture queries.
Figure 2: Results of the query Europeans U Canadians Entities in the darker areas have higher probability of being the answers than lighter areas. We can observe from (c) that the non-smooth borders of box geometry do not encompass the answer Hinton.
To alleviate the drawbacks of operations not being closed under unions and border ambiguities, we propose Probabilistic Entity Representation Model (PERM). PERM models entities mixture of Gaussian densities. Gaussian densities have been previously used in natural language processing [14] and graphs 15 to enable more expressive parameterization of decision boundaries. In case,

---

utilize mixture of multivariate Gaussian densities due to their intuitive closed form solution for translation, intersection, and union operations. In addition, they can also enable the use of smooth distance function; Mahalanobis distance [16]. Figure 2 provides an example of such case where the non-smooth boundaries of box query embeddings are not able to capture certain answers. We utilize the mean (1) and co-variance (E) parameters of multivariate Gaussian densities to encode the semantic position and spatial query area of an entity, respectively. The closed form solution for the operations allows us to solve complex queries by chaining them in pipeline. PERM does not need to rely on DNF transformations, since all the outputs are closed in the Gaussian space and complex queries can be consolidated in end-to-end objective function, e.g., in Figure 2b Europeans U Canadi ans is a Gaussian mixture and the single objective is to minimize the distance between the mixture and entity Hinton, whereas in the case of boxes (shown in Figure 2a). we have two independent objectives to minimize the distance from each box in the union query. Summarizing, the contributions of our work is as follows:
1. We develop Probabilistic Entity Representation Model (PERM), a method to reason over KGs using (mixture of) Gaussian densities. Gaussians are able provide closed form solution to intersection and union, and also smooth distance function. This enables us to process chain of complex logical queries in an end-to-end objective function.
2. PERM is able outperform the current otate-of-the-art baselines on logical query reasoning over standard benchmark datasets. Additionally, it is also able to provide better drug recommendations for COVID-19.
3. PERM is also interpretable since the Gaussian embeddings can be visualized after each query process to understand the complete query representation.
The rest of the paper is organized as follows: Section 2 presents the current work in the field. In section 5 we present PERM and define its various operations. Section 4 provides the formulation for building the reasoning chains for complex queries. We provide the experimental setup and results in section 5
We conclude our paper in section C and present its broader impact in section 7
2 Related Work
The topic of multi-hop chain reasoning over KGs has gained a lot of attention in recent years [
[8 19 M. These approaches utilize vector spaces to model query representation and retrieve results using& a fixed threshold. While such representations are efficient at encoding semantic information, the fixed thresholds that are typically used in these models do not allow for an expressive (adjustable) boundary and, thus, are not best suited for representing queries. Spatial embeddings
g 20 enhance the simple vector representations by adding a learnable border parameter that controls the spatial area around a query representation. These methods have strict borders that rely on non-smooth distance function that creates ambiguity between border cases. On the other hand, in our model, the variance parameter of the query's Gaussian densities creates soft smoothly increasing borders in terms of the Mahalanobis distance. Additionally, the previous methods do not provide closed form solution for unions which we solve using Gaussian mixture models.
Density-based embeddings have seen recent surge of interest in various domains. Word2Gauss [4] provides a method of learning Gaussian densities for words from their distributional semantic information. In addition, the authors further apply this work to knowledge graphs [33. Another approach [1] aims to learn Gaussian graph representations from their network connections. These methods are, however, focused learning semantic information and do not easily extend to logical queries over knowledge graphs. PERM primarily focuses on learning spatial Gaussian densities for queries, while also capturing the semantic information. To achieve this, we derive closed form solutions to FOE queries.
3 Probabilistic Entity Representation Model for Logical Operators
Knowledge Graphs (KG) G
R are heterogeneous graphs that store entities (E) and relations
(R). Each relation E R is a Boolean function r E x E + (True, False) that indicates if the relation r exists between a pair of entities. Without loss of generality, KGs can also be organized as set of triples (e1, r, e2) C G. defined by the Boolean relation function r(e1, eg). In this work,
3

---

part of query and another an entity e; E E as a multivariate Gaussian density function; e; = [N,, Ej), where the learnable parameters je; (mean) and Σ, (covariance) indicate the semantic position and the surrounding query focus on the following three FOE operations: translation (t), intersection (Π), and union (U), The operations are defined as below:
qe (Qa) A (11, 22, ... [k C E 3 01
(1)
gn 2n {ui, U2 ... 3 S E 3 01 Aag n.. Na;
(2)
q. VV : f0), U2, ..., Rx [ 3 Uaz Ua.
(3)
where Q+ (e1, Qu {(11, r1); (2).
and a; a= ra va)
where Qt- In. and qu the translation, intersection, and union queries, respectively; and Vi, Vn, and
Vu are the corresponding results [0]]_ As we notice above, each entity has dual nature; one as being candidate answer to a query. In PERM,
model the query space of
density of the entity, respectively. As a candidate, we only consider the and ignore the Σ, of the entity. We define the distance of candidate entity e2 (N 2,) from a query Gaussian ej (u,, Eg) using the Mahalanobis distance [[ given by:
(us e,) = (1g - n4) n4) _ (M, p4)
Additionally, need define the FOE operations for the proposed Probabilistic Entity Representa- tion Model. visual interpretation of the operations; translation, intersection, and union is shown in Figure The operations are defined follows:
Translation (t), Each entity e E and r E R are encoded as Niees E.) and ModN((rr: E,), respectively, We define the translation query representation of an entity with relation as ge and the distance of resultant entity " E Ve from the query as dy given by:
q: = [[ + Mr, (r, + of == 9t)
(5)
Intersection (7). Intuitively, the intersection of two Gaussian densities implies random variable that belongs both the densities. Given that the entity densities are independent of each other, we define the intersection of two entity density functions e1, as On and distance of resultant entity en E Vn from the query as d given by:
Φn = =N Ee, (M Eez) = NNus: Ez): da = dy((r, 9-)
where, Σg Ej + Σう¹
and μ13 = Ex 1 + Σ 1 12)
E3 33- 1I E
We provide a brief sketch the proof that the intersection of Gaussian density functions is closed operation. A complete proof is provided in Appendix A Let us consider two Gaussian PDFs P(O1) ( Σ1) and P(02) N(2,,, Σ2). Their intersection implies a random variable that distributed as the product, P(0)) The intersection P(0) NNu,, Σz) is derived as follows:
P(0) P(O.).P(02)
log( P(0)) (x: - TT (x m1) + (x 122) TT (x 12) (x - 133) Egg (x Ms) = (a- ((r-M)) m1) T (I m1) + (x - (22) "55 (r v2) Comparing coefficients; 25 = MT + 1 Ms = (5, #1 + E u2)
Union (U). We model the union of multiple entities using Gaussian mixtures. The union of entity density functions given by 61, C22 es...., Cn is defined as gu and the distance of resultant entity au E Vu from the query as dº given by:
au Σ (NN Legl; d3 =
Gidx(ou. Eeg)
where, di exp (Mey: Eecs)
Σ/= eap (N (N(Mess Ee
Φ; E ① are the weights for each Gaussian density in the Gaussian mixture, calculated using the self-attention mechanism over the parameters of the Gaussians the mixture, i.e., Meç E,,, Vi -> n.

---

(a) Translation (g+)
(b) Intersection (gn)
(c) Union (qu)
(d) Chain Translation (c+)
(e) Chain Intersection (cn)
(1) Chain Union (cu)
Figure 3: The logical single (top row) and chain operations (bottom row) of translation, intersection, and union in the Gaussian space. The operations are closed and will result in either Gaussian density or a Gaussian mixture. The input operands are given blue and red and the resultant Gaussian density/mixture is depicted in purple. For simplicity, the example is given for univariate Gaussian model, but in our work, we use multivariate Gaussian densities.
Chain Reasoning over Knowledge Graphs
We consider the Gaussian density function (embedding of a single entity) as a special case of Gaussian mixture with single component. This ensures that all the operations defined in Section B are closed under the Gaussian space with an output that is either a single (for translations and intersections) or multi-component Gaussian mixture (for unions). Hence, for chaining the queries, need define the logical operators with a Gaussian density and a Gaussian mixture input. In this section, we define the different operators (depicted in Figure in the case of Gaussian mixture input.
Chain Translation. Let us assume that the input query embedding is an n-component mixture p >i= (u, Mx) and we need to translate it with relation N N(,r, 2,). Intuitively, we would like to translate all the Gaussians in the mixture with the relation. Hence, we model this translation as c and the distance from entities 2 Vi df given by:
C
Φ:N(u + pr. (DT+ + Σマ
(8)
d; o + Mry (Ep エーリ)ー
Chain Intersection. A Gaussian mixture union over individual densities. Based on the dis- n tributive law of sets, an intersection over a Gaussian mixture > Ej) and entity e [pee Σ.) implies the union of the intersection between the entity and each Gaussian density in the mixture. Hence, we derive this intersection
and the distance from entities un E Vn as df;
en UL (M,
Σ
E.)W,, E.)
cn = Σ
N. (Merii Doni)
(10)
1=1
where, Σ-1 ---1 Ex and Meri Eoni(E Me E-1(u) 14)
di = Σ
ondy(un Deni))
(11)
Chain Union. The union of an entity = NNuee Ed) with Gaussian mixture Σn_ d:W(u Σ,) the addition of the entity to the mixture. Hence, the union cu and the distance from entities au Vu
5

---

d can be defined as follows:
J (n Σ,) + (eN(Hee Ec)
(12)
d Bod ((,, (ed Ec))
(13)
Implementation Details. To calculate the weights (d, 4) of the Gaussian mixtures, the popular self-attention mechanism [21] The gradient descent over Mahalanobis distance (Eq. 4 and derivation for the product of Gaussians (Eq. 6 are given by [22) and Appendix A respectively. Another important note is that we do not need to compute E for the operations, but rather we only need compute the E-1 Also, storing the complete Σ requires quadratic memory, i.e., Gaussian density of d variables requires d X d parameters for Σ. So, we only store a decomposed matrix LL Thus, for Gaussian density of d variables our memory requirement is d (r+1) parameters (d for μu and x r for Σー²). For computing the μ4 for intersection, in Eq. we use a linear solver (torch. solve) for faster computation. All our models are implemented and run on four Quadro RTX 8000.
L of :-1:--1
in Pytorch 2
5
Experiments
This section describes the experimental setup used to analyze the performance of PERM on various tasks with focus the following research questions:
1. Does PERM's ' query representations perform better than the state-of-the-ard baselines on the task of logical reasoning
standard benchmark knowledge graphs?
2. What is the role of individual components in PERM's ' overall performance gain?
3. Is PERM able recommend better therapeutic drugs for COVID-19 from drug re-purposing graph data compared the current baselines?
Are we able to visualize the operations on PERM's query representations in the latent space?
5.1 Datasets and Baselines
We utilize the following standard benchmark datasets to compare PERM's performance on the task of reasoning over KGs:
FB15K-237 24 is comprised of the 149,689 relation triples and textual mentions of Freebase
entity pairs. All the simply invertible relations are removed.
NELL.995 consists of 107,98? triples obtained from the 995th iteration of the Never-Ending Language Learning (NELL) system.
DBPedia is subset of the Wikipedia snapshot that consists of multi-level hierarchical taxonomy over 240,942 articles.
DRKG 20 (Drug Re-purposing Knowledge Graph) is used to evaluate the performance of our model on both the logical reasoning and drug recommendation tasks.
Table 1: Dataset statistics including the number unique entities, relations, and edges, along with the splits of dataset triples used in the experiments.
Dataset Entities
Relations
Edges
Training
Validation
Test
FB15k-237
14,505
237
310,079
272,115
17,526
20,438
NELL995
63,361
200
142,804
114,213
14,324
14,267
DBPedia
34,575
3
240,942
168,659
24,095
48,188
DRKG
97,238
107
5,874,271
4,111,989
587,428
1,174,854
Implementation code: cade/h/atpes//ghhhhh.c.oo/ttttie GaABR---GuuiinnKGGG
https://ww/ http://wwe...oo/ooono//ettaaaaaa

---

More detailed statistics of these datasets are provided in Table ! For our experiments, we select the following baselines based on (i) their performance the logical reasoning task and (ii) their ability to extend to all FOE query combinations.
Graph Query Embedding (GQE) embeds entities and relations as vector and utilizes TransE [17 to learn the query embeddings. The distance of the answer entities is calculated using Ll-norm.
Query2Box (Q2B) embeds entities and relations axis aligned hyper-rectangles boxes and utilize FOE queries to learn query representations, The distance of answer entities is given by weighted combination of the answer's distance from the center and the border of the query box.
Beta Query Embedding (BQE) [1 utilizes beta distribution learn query representations from FOE queries with a novel addition of negation queries. The distance is calculated as the dimension-wise KL. divergence between the answer entity and the query beta embedding.
Complex Query Decomposition (CQD) 10 answers complex queries by reducing them to simpler sub-queries and aggregating the resultant scores with t-norms.
Some of the other baselines intuitively extended to handle all FOE queries, and hence, we did not include them in our study.
2 focus solely the multi-hop problem. They could not be
Table 2: Performance comparison PERM against the baselines to study the efficacy of the query representations. The columns present the different query structures and the overall average performance. The last row presents the Average Relative Improvement (%) of PERM compared to CQD over all datasets across different query types. Best results for each dataset are shown in bold. The MRR results for experiments are given in Appendix C
HITS@1
@3
Dataset
Model
3t
20
3n
2U
nt
tn
Ut
Avg
FB15K-237
GQE
.404
.214
.147
266
.390
.164
.087
.162
.155
.221
BQE
.455
.122
.102
.32
.459
.141
.244
.124
.101
.218
Q2B
.467
.440
.186
.324
.453
.239
.050
.108
.193
.251
CQD
.512
.288
.221
.322
.457
.284
.129
.249
.121
.290
PERM
.520
286
.216
.361
.490
.305
.128
.212
.239
.306
NELL995
GQE
.417
.231
.203
.388
.454
.200
.081
.188
.139
.248
BQE
.711
.156
.132
.438
.540
.153
.250
.160
.091
.292
Q2B
.555
266
2333
343
.480
.369
.132
.212
.163
.306
CQD
.667
.350
.288
.410
.529
.531
.171
.277
.156
.375
PERM
.581
.266
.243
.352
.508
.460
.143
.195
.200
.328
DBPedia
GQE
.673
.006
N.A.
.833
.879
.402
.160
.668
0.00
.458
BQE
881
.007
N.A.
1.00
1.00
.384
.435
.590
0.00
.655
Q2B
.832
.0073
N.A.
1.00
1.00
.649
.224
.856
0.00
.571
CQD
.870
.0073
N.A.
1.00
1.00
.673
.218
.787
0.00
.569
PERM
.950
.0073
N.A.
1.00
1.00
.782
.232
.952
0.00
.615
DRKG
GQE
.200
.188
.153
270
.409
.181
101
.186
.174
.235
BQE
.554
.141
.123
347
-512
.185
.281
.173
.124
.271
Q2B
.499
.263
.199
.37
.489
.284
.068
.134
.235
.279
CQD
.554
.323
.238
369
.495
.341
.184
.310
.150
.329
PERM
.565
.322
.236
.387
.540
.376
.190
.273
.297
.354
PERM Q2B (%)
10.9
12.3
13.0
7.20
6.10
26.3
84.2
50.8
24.3
15.9
PERM vs CQD (%)
3.80
-0.9
-2.4
2.00
5.80
9.50
1.80
-5.5
93.0
6.2
5.2 (RQ1) Reasoning over KGs
To evaluate the efficacy of PERM's query representations, we compare against the baselines on different FOE query types; (i) Single Operator: 1t, 2t, 3t, 2n, 3n, 2U and (ii) Compound Queries:
nt, tn, Ut. We follow the standard evaluation protocol 7 1 and utilize the three splits a KG
DDBPedia has an extremely large number of resultant grand-childeed leaves (z= 10 per grand-parent for the 2t task and, thus, notice poor performance 2t task across all the evaluation models.
7

---

for training Gtrain, validation Ivalid, and evaluation Gtest (details in Table I. The models are trained on Girain with validation on Inald- The final evaluation metrics for comparison are calculated on Grest- For the baselines, we calculate the relevance of the answer entities to the queries based on the distance measures proposed in their respective papers. PHRM, the distance of the answer entity from the query Gaussian density is computed according to the measures discussed in Sections $ and
We use the evaluation metrics HITS@K K and MRR to compare the ranked set results obtained from different models. Given the ground truth E and model outputs {ei, ...,... Cn E E, the metrics calculated follows:
[1 E E
HITS@K E
f(ex);
f(ex)
K
10 else
k=1
MRR 1
Σ ==1
f(e)) = i, i E
00, else
From the results provided in Table 2 we observe that PERM, is able to outperform all the current state-of-the-ard approaches, on an average across all FOE queries by 6.2%. Specifically, we see consistent improvement for union queries; 9.5% and 93% in the case of 2U and Ut., respectively. Comparing the models based on only geometries, we notice the clear efficacy PERM query representations with average improvement of 37.9%, 15.9%, and 37.3% over vectors (GQE), boxes (Q2B), and beta distribution (BQE), respectively. Given these improvements and the ability to handle compound queries in an end-to-end manner, we conclude that Gaussian distributions are better at learning query representations for FOE reasoning over KGs. Additionally, we provide PERM's results sample queries from different datasets in Table
Table 3: Qualitative results of PERM on samples from different datasets. Results given in green and red indicate correct and incorrect prediction, respectively.
Query
Results
Who are European and Canadian Turing awards winners?
Jeffrey Hinton, Yoshua Bengio, Andrew Yao
Which Actors and Football Players also became
Amold Schwarzenegger, Heath Shuler, Frank White
Governors?
Which treatment drugs interact with all proteins associated with SARS diseases?
Ribavirin, Dexamethasone, Hydroxychloro- quine
5.3 (RQ2) Ablation Study
In this section, we evaluate the need for different components and their effects on the overall performance of our model. First, we look at the contribution of utilizing different types of queries to the performance (i) only It queries, (ii) only translation (It,2t,3t) queries and (iii) only single operator queries (1t,2,,33,2n,3) 3,2, Furthermore, we look the need for attentive aggregation the case of union of Gaussian mixtures. We test other methods of aggregation; (i) vanilla averaging and (ii) MLP [28
our model. For this, we train our model on different subsets of queries;
Table Ablation study results. Performance comparison of PERM (final) against different variants of our model. 1t, translation and single utilize the 1-hop queries, all translation queries and all single operator queries, respectively. The average and MLP variants utilize vanilla averaging and MLP for aggregation in union queries. The metrics reported here are average over all the datasets. Finer evaluation with results for each dataset is given in Appendix D Best results are given in bold.
HITS@3
Model Variants
1t
3t
2n
3n
20
ntt
Ut
Avg
PERM-1t
.649
.141
.128
.400
.466
.477
.095
.257
.102
.303
PERM-translatin translation
.649
.182
.179
.463
.555
.479
.128
.308
.143
.341
PERM-sings -single
.652
.225
.228
524
.632
.475
.167
.398
.181
.387
FFRM-avvragee
.628
.222
.224
.524
.624
.444
.158
.387
.180
.377
PERM-MIP
.642
.225
.228
.26
.631
.462
.166
.400
183
.385
PERM (final)
.654
.225
.232
.255
.635
.481
.170
.408
.184
.390

---

From Table 4 we notice that utilizing only It queries significantly reduces the performance of our model by 22.3% and even increasing the scope all translation queries still lower in performance by 12.5% for this case. However, we notice that training on all single operator queries results in comparable performance to the final PERM model. But, given the better overall performance, we utilize all the queries in our final model. For union aggregation, we observe that attention has clear advantage and both vanilla averaging and MLP lead to lower performance by 3.33% and 1.28%, respectively, Thus, we adopt self-attention in our final model.
5.4 (RQ3) Case Study: Drug Recommendation
In this experiment, we utilize the expressive power of PERM's 's query representations to recommend therapeutic drugs for COVID-19 from the DRKG dataset. Drugs in the dataset are already approved for other discases and the aim is to utilize the trug-protein-diseas networks and employ them towards treating COVID-19. This can potentially reduce both the drug development time and cost [29]. For this experiment,
utilize the treatment relation in DRKG and retrieve drugs D D treats, X, where is a set of SARS diseases related to the COVID-19 virus. Given that we only need these limited set of entity types (only SARS diseases and drugs) and relation types (only treatments), only consider the DRKG subgraph that contains this necessary set of entities and relations for learning the representations. We compare the recommendations of different models against set of actual candidates currently in trials for COVID-19. We use the top- lop10 recommendations with the evaluation metries of precision, recall, and Fl-score for comparison.
Table 5: Performance comparison of various models on the COVID-19 drug recommendation problem using precision (P), recall (R), and Fl-score (F1) metrics. The top three drugs recommended by the models are given in the last column. The recommendations given in green and red indicate correct and incorrect predictions, respectively. The last two rows provide the average relative improvement of PERM compared to the state-of the art baselines Q2B and COD.
Model
P@ 10
R 10
F1
Top Recommended Drugs Piclidenoson, Ibuprofen, Chloroquine Ossetamii,,slttmiiiii Ruxolitinib
GQE
.119
.174
.141
BQE
.159
200
.177
Q2B
.194
.255
.221
Ribavirin, Dexamethasone, Deferoxamine Ribavirin, Dexamethasone, Tofacitinib Ribavirin, Dexamethasone, Hydroxychloroquine
CQD
.209
.260
.232
PERM
.217
.269
.251
PERM Q2B (%)
11.9
5.5
13.6
PERM vs CQD (%)
3,8
3.5
8.2
We can observe from Table that that PERM is able to provide the best drug recommendations, across all evaluation metrics. Our model is able to outperform the current methods by atleast 3.8%, 3.5%, and 8.2% in precision, recall, and F1, respectively. Also, the top recommended drugs by our PERM are more inline with the current drug development candidates, thus, showing the better performance of model's query representations.
5.5 (RQ4) Visualization of the Gaussian Representations
To visualize the entity and query in the latent space, extract representative entity samples from the FB15K-237 dataset and present them a 2-dimensional space for better comprehension.
Figure depicts the different entities and the mechanism through which PERM narrows down to the particular answer set. Notice that, we are able to perform an intersection after union operation due to the closed form nature of our operations. This is currently not possible in state-of-the ff-the-art art baseline methods. Additionally, it should be noted that, unions widen the query space and intersections narrow them down (as expected). Furthermore, the variance parameter acts as control over the spatial area that an entity should cover and more general entities such as Turing Award and Europe occupy a larger area than their respective sub-categories, namely, winners and Europeans.

---

Europeans
Turing Award Winners
Canadian (C) European Turing (A) (W)?
Awards
Turing
winners
Europe
Europeans
Intersection
Final Query Representation
Union
Canadiane
Canada
Canadians
(a) Query processing in PERM. This figure depicts univariate version of the entity Gaussian embeddings for better visualization of the process. The same property, however, generalizes over an increased number of dimensions, i.c., multivariate case.
(b) Bivariate version of the final query space, given in grayscale with darker colors representing a higher probability of answers.
Figure 4: An illustration of the flow for sample complex query in the representational space. We note that intersection after union is possible in our PERM model because the operations are closed in Gaussian distributions and this is not possible in current methods including BQE, Q2B, and CQD.
Conclusion
In this paper, we present Probabilistic Entity Representation Model (PERM), a model learn query representations for chain reasoning over knowledge graphs. We show the representational power of PERM by defining closed form solutions to FOE queries and their chains. Additionally, we also demonstrate its superior performance compared to its state-of-the-ard counterparts on the problems reasoning over KGs and drug recommendation for COVID- 19 from the DRKG dataset. Furthermore, we exhibit its interpretability by depicting the representational space through sample query processing pipeline.
Broader Impact
PERM is the first method that models an individual entity in knowledge graphs using Gaussian density function, making it possible to solve FOE queries using a closed form solution. This enables its application in domains that require chain reasoning. The main idea of the proposed solution can also be extended to any domain that can encode its basic units as Gaussians and extend the units through FOE queries, e.g., in topic modeling, topies can be encoded Gaussians and documents as union of topics.
However, PERM depends the integrity of the knowledge graph used for training. Any malicious attacks/errors NO 3II that lead to incorrect relations could, further, lead to incorrect results and affect the confidence of our model. Furthermore, due the connected nature of complex queries, this attack could propagate and affect a larger set of queries. Such incorrect results would be problematic in sensitive areas of research such drug recommendations and cybersecurity and, thus, it is necessary to maintain the integrity of training data before learning representations and querying with PERM.
Acknowledgments
Funding: This work was supported in part by the US National Science Foundation grant IIS- 1838730 and Amazon AWS cloud computing credits for research.
Competing Interests: All the authors had some form of affiliation with Amazon in the past 36 months.
10

---

References
[1] Xin Luna Dong, Xiang He, Andrey Kan, Xian Li, Yan Liang. Jun Ma, Yifan Ethan Xu, Chenwei Zhang, Tong Zhao, Gabriel Blanco Saldana, et al. Autoknow: Self-driving knowledge collection for products of thousands of types. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 2724 2734, 2020.
[2] Christian Bizer, Jens Lehmann, Georgi Kobilarov, Sören Auer, Christian Becker, Richard Cyganiak, and Sebastian Hellmann. Dhpedia-a crystallization point for the web of data. Journal of web semanties, 7(3): 1011541114 165, 2009.
[3] Piero Andrea Bonatti, Stefan Decker, Axel Polleres, and Valentina Presutti. Knowledge Graphs: New Directions for Knowledge Representation on the Semantic Web (Dagstuhl Seminar 18371). Dagstuhl Reports, 8(9):29-111, 2019.
[4] Linfeng Li, Peng Wang, Jun Yan, Yao Wang. Simin Li, Jinpeng Jiang, Zhe Sun, Buzhou Tang. Tsung- Hui Chang, Shenghui Wang, and Yuting Liu. Real-world data medical knowledge graph: construction and applications. Artificial Intelligence Medicine, 103:101817, 2020.
[5] Longxiang Shi, Shijian Li, Xiaoran Yang. Jiaheng Qi, Gang Pan, and Binbin Zhou. Semantic health knowledge graph: semantic integration of heterogeneous medical knowledge and services. BioMed research international, 2017.
[6] William L. Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries on knowledge graphs. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 2030-2041, Red Hook, NY, USA, 2018. Curran Associates Inc.
[7] Hongyu Ren", Weihua Hu and Jure Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In International Conference on Learning Representations, 2020.
[8] Nurendra Choudhary, Nikhil Rao, Sumeet Katariya, Karthik Subbian, and Chandan K. Reddy. Self-supervised hyperboloid representations from logical queries over knowledge graphs. In Proceedings of the Web Conference 2021. WWW '21, page 1333-1386 New York, NY, USA. 2021. Association for Computing Machinery.
[9] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, ICML' 16, page JMLR.org, 2016.
[10] Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. Complex query answering with neural link predictors. In International Conference on Learning Representations, 2021.
[11) Hongyu Ren and Jure Leskovec. Beta embeddings for multi-hop logical reasoning in knowledge graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balean, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 19716-19722 19726. Curran Associates, Inc., 2020.
[12] Katrin Erk. Representing words as regions in vector space. In Proceedings of the Thirteenth Conference on Computational Natural Language Learning (CoNLL-2009), pages 57-65, 2009.
[13] Luke Vilnis, Xiang Li, Shikhar Murty, and Andrew McCallum. Probabilistic embedding of knowledge graphs with box lattice measures. In Proceedings of the 56th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 263-272, Melbourne, Australia, July 2018. Association for Computational Linguistics.
[14] Luke Vilnis and Andrew McCallum. Word representations via gaussian embedding. In ICLR, 2015.
[15] Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsuper- vised inductive learning via ranking. In International Conference on Learning Representations, 2018.
[16] Yadolah Dodge. Mahalanobis Distance, pages 325-326. Springer New York, New York, NY, 2008.

---

[17] Antoine Bordes, Nicolas Usunier, Alberto Garcia- Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Neural Information Processing Systems (NIPS), pages 1-9, 2013.
[18)
Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. A three-way model for collective learning on multi-relational data. In leml, 2011.
[19] Rajarshi Das, Arvind Neclakantan, David Belanger, and Andrew McCallum. Chains of reasoning over entities, relations, and text using recurrent neural networks. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume
1, Long Papers, pages 132-141, Valencia, Spain, April 2017. Association for Computational Linguistics.
[20] Haitian Sun, Andrew O Arnold, Tania Bedrax- Weiss, Fernando Pereira, and William W Cohen. Faithful embeddings for knowledge base queries. Advances in Neural Information Processing Systems, 33, 2020.
[21] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez,
E. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[22] Marc T Law, Yaoliang Yu, Matthieu Cord, and Eric P Xing. Closed-form training of mahalanobis distance for supervised clustering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3909-3917, 2016.
[23] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'lché-Buu BBch E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035 Curran Associates, Inc., 2019.
[24] Kristina Toutanova, Danqi Chen, Patrick Pantel, Hoifung Poon, Pallavi Choudhury, and Michael Gamon. Representing text for joint embedding of text and knowledge bases. In Proceedings of the 2015 conference on empirical methods in natural language processing, pages 1499-1509, 2015.
[25] Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam Hruschka, and Tom Mitchell. Toward an architecture for never-ending language learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 24, 2010.
[26] Vassilis N. loannidis, Xiang Song, Saurav Manchanda, Mufei Li, Xiaoqin Pan, Da Zheng, Xia Ning, Xiangxiang Zeng, and George Karypis. Drkg drug repurposing knowledge graph for covid-19. https://gitth:i www.hh...oo......ae/m..........a gpngdr/DRGGrr///// 2020.
[27] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXhv:1412.6575. 2014.
[28] Fionn Murtagh. Multilayer perceptrons for classification and regression. Neurocomputing. 2(5):183-197, 1991.
[29] Sudeep Pushpakom, Francesco Iorio, Patrick A Eyers, K Jane Escott, Shirley Hopper, Andrew Wells, Andrew Doig, Tim Guilliams, Joanna Latimer, Christine McNamee, et al. Drug repurpos- ing: progress, challenges and recommendations. Nature reviews Drug discovery, 18 (8)1158, 2019.
[30] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2847-2856, 2018.
[31] Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International conference on machine learning, pages 1115-1124. PMLR, 2018
12


Reviews:
[{"review_id": "yVvAIhRdGNZ", "reviewer": "Reviewer_HW1P", "summary": "The paper proposes a new multi-hop reasoning algorithm on incomplete knowledge graphs. The method aims to embed complex logical queries and the chain reasoning steps as Gaussian mixtures. The benefit is that the model can provide extra flexibility in modeling union operations compared with previous embedding-based methods. The paper did extensive experiments, showed the proposed model outperforms prior models on the empirical performance and also demonstrated some visualizations and case studies. Overall the paper is well written and easy to follow. But the math/notations are somewhat messy (see below) and the paper is not that much well-motivated, especially for the specific design choices of the logical operators. The paper listed what they do but it would be better if the authors can justify why they want to have such design choices.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Please find my detailed comments and questions below.\n1. Is the figure 2 a real example or is it a synthetic illustration? Why is the distance(hinton, union) smaller than distance(hinton, european) and also distance(hinton, canadian) in the Gaussian mixture model? \n2. The description of the prior methods in the introduction has some errors. For example, line 38-41, “strict borders lead to ambiguity in the border case scenarios and a discontinuous distance function, e.g., a point on the border will have a much smaller distance if it is considered to be inside the box than if it is considered to be outside.” In fact, the according to Eq. 3 in [1], $\\text{dist}_\\text{box}(v;q)=\\text{dist}_\\text{outside}(v;q)+\\alpha \\cdot \\text{dist}_\\text{inside}(v;q)$. No matter the node on the border is considered insider or outside the box, the $\\text{dist}_\\text{outside}$ is always 0 and the $\\text{dist}_\\text{inside}$ is always the offset of the query box $q$. In other words, the distance function is continuous (piecewise linear function). Please justify your argument since I do not think border ambiguity is an issue for prior methods.\n3. Regarding the other motivation “closed under union operations”, I think the beta query embedding [2] can also achieve closed union operation using the negation and intersection operations. Can you also clarify this point?\n4. Do you also consider queries with both intersection and union operations? According to Eq. 1/2/3, it seems you do not. Since the paper emphasized chainable operations, it would be nice if the authors can discuss how to chain union and intersection in the same query.\n5. The papers introduce how they design the translation, intersection, union operators in section 3. But they are not well motivated. Can you explain (1) why you ignore the covariance in the entity embedding when you calculate the distance between query and entity? (2) modeling the mean embedding as summation in the translation operator makes perfect sense to me, but why would you want to model the covariance as $\\Sigma_e^{-1}+\\Sigma_r^{-1}$?, what is the geometric intuition behind it? Does it shrink or expand the covariance matrix in general? More discussion can be super helpful. (3) you mention the weights for each Gaussian density is calculated using the self-attention mechanism, then are there any neural network modules with learnable parameters except for the embeddings to calculate the self-attention? I do not see any additional parameters in Eq. 7, and also the math is messy and has errors (see below). (4) Also why would you want to model the intersection of two \\textbf{entity} density functions (line 118-120)? How would you define the intersection of two entities? If you mean the intersection of the two sets $\\{e1\\}\\wedge \\{e2\\}$, then the results will be an empty set as long as $e1 \\neq e2$. This is really confusing.\n6. The math in Eq 7 is sketchy. Based on my understanding $\\phi_i$ is a scalar or a vector (please clarify), and $\\mathcal{N}(\\mu_{e_i}, \\Sigma_{e_i})$ is the pdf of the Gaussian distribution. Then why does $exp$ of a function returns a scalar ($\\phi_i$)?\n7. Also for the inline equation in line 138, it should be $p=\\sum_{i=0}^n \\mathbf{\\phi_i} \\mathcal{N}(\\mu_i, \\Sigma_i)$ instead of $p=\\sum_{i=0}^n \\mathcal{N}(\\mu_i, \\Sigma_i)$\n8. How would you calculate $\\phi_i$ in Eq. 8 (and also in Eq. 9-12)? Is it the same as Eq. 7? And does the $\\phi_i$ is a self-attention over the \\textbf{input} union query embedding or is it over the \\textbf{output} union query embedding?\n9. I have the same question in the Chain Intersection paragraph in Section 4. According to line 141-144, you are modeling the intersection between an entity and a query (a set of entities). But this intersection operation is trivial in the sense that the result will either be an empty set or a set of a single entity.\n10. How would you model the intersection/union of two Gaussian mixtures?\n11. Line 153-155, the paper mentions that “$d$ for $\\Sigma^{-1}$”, so the $\\Sigma^{-1}$ is factorized as the multiplication of a $L\\times 1$ matrix and its transpose? Does it cause performance decrease since this has a large approximation error.\n12. What is $\\cap t, t\\cap, \\cup t$ queries? An illustration/example would be very helpful.\n13. For the results in Table1, do you train PERM on all query types?\n14. I still have questions on how PERM handles intersection operator and the self-attention mechanism, especially for ablation studies in Table 2. I wonder how PERM can answer queries with intersection if they are only trained on 1t queries. But this concern should be addressed if the authors can give me a detailed formulation of the self-attention mechanism and correct the math errors in Eq. 7.\n15. Have you tried to measure the “uncertainty” of a query as in [2]? The idea is to calculate the entropy of the Gaussian mixtures and to find whether it shows any signal e.g., correlation with the number of answers of the query.\n\nminor: you do not need to mention the distance function every time from Eq. 8 to Eq.12, since it is the same as in Eq. 5 to Eq. 7.\n\n[1] Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings\n\n[2] Beta Embeddings for Multi-Hop Logical Reasoning in Knowledge Graphs", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please check the main review section. I do not think it has any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "mCBYlXUlhik", "reviewer": "Reviewer_TYBk", "summary": "The proposed approach PERM is a knowledge graph embedding method that enables chain reasoning with first-order existential queries. In particular, it represents the query with a mixture of Gaussian distributions, constructed from intersection, union, and translation operations. Then, the result entities to the Gaussian mixture query are ranked using Mahalanobis distance. The evaluation shows that the proposed approach mostly outperform or comparable to the 4 baselines on 4 datasets.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this can be an excellent paper for a few reasons, and the simple but new way to compute the first-order existential queries is empirically shown to outperform the baselines, and the analysis on how this approach works, and the ablation study are solid. Using a Gaussian distribution to represent a first-order logic looks sound in most cases, and it can have future research implications beyond this paper, considering typicality, etc. Although the paper is in general well-written, there is some information missing that can potentially make this paper very hard to understand for some out-of-field readers. The details are below.\n\nStrengths\n- S1: Solid experimental results showing the improvement on diverse datasets.\n- S2: Additional experiments to show ablation study and visualization of a query and entities are helpful to understand the strength.\n\nWeaknesses\n- W1: The OR logic might not be best represented using the mixture of Gaussians because an entity can satisfy two predicates at once. For example, a person can be fully European and Canadian, if dual citizenship is allowed, and embedding an entity between two distributions might not be the best representation.\n- W2: Only limited to first-order existential queries.\n- W3: I understand the space is tight, but some key information about the training and some detail are missing. For example, the entire process is a bit vague, how to produce training data (not KGs, but queries), what is the dimensionality of the entities and so on because these are not mentioned or shown. For the overall process, an overview figure can be really helpful here. The overview becomes only slightly clearer in the algorithm in the appendix. The algorithm pseudo code might not be necessary, but some description should be there in the main text.\n\nI like the paper in general, but I find the problem of missing some key information needs to be fixed before publication and make the paper self-contained as much as possible, if not citing an existing work. I'm willing to change the decision if it can be addressed even with the tight space.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The impact is discussed in the paper. I agree with the authors, and I would consider the potential negative impact beyond scope of this work and it is where we also need to put more effort to prevent malicious knowledge graphs.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Yb37WM0TjJA", "reviewer": "Reviewer_dgsE", "summary": "The authors propose a Probabilistic Entity Representation Model (PERM) for learning query representations for chain reasoning over knowledge graphs. The model encodes knowledge graph entities as a Multivariate Gaussian density with mean and covariance parameters for encoding the semantic position and spatial query area of the entities. In particular, they utilize a mixture of multivariate Gaussian densities due to their intuitive closed-form solution for translation, intersection, and union operations. They claim that the closed-form solution for the operations allows them to solve complex queries by chaining them in a pipeline.\n\nAs contributions of the work, the authors provide Gaussian densities that can produce a closed-form solution to intersection and union and also a continuous distance function, which enables processing a chain of complex logical queries in an end-to-end objective function. \nFurthermore, they indicate state-of-the-art results on logical query reasoning over multiple standard benchmarks and better drug recommendations for COVID-19 from the DRKG dataset. Finally, they declare that PERM is also interpretable as Gaussian embeddings can be visualized.\n", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The approach for utilizing a mixture of multivariate Gaussian densities to represent KG entities for learning query representations for chain reasoning is new in the field. The paper is well written and easy to follow. The methodology and claims are also supported. It is also nice that the code is provided. \n\nHowever, I have concerns regarding the experiments part. \nIn the first experiment, the authors indicate SotA results compared to other approaches, and they also emphasize a comparison between Q2B and CQD models. Even though they visualize in Figure 2 why their model can be superior compared to union box queries, the authors do not explain why their model performs better for particular query types and worse for others (Table 1). \n\nThe ablation experiment looks solid. I only miss a mention of the benchmark for which results are reported in Table 2. Currently, it is not indicated in the table and also in the caption. \n\nThe case study for COVID-19 drug recommendation only indicates that the proposed model performs better than previous baselines and not why. It is similar to the first experiment. An error analysis here would be much more helpful. For instance, showing a particular set of queries or entities that the model fails to produce valid results would be much more useful.\n\nThe visualization experiment is also not convincing. Being able to visualize the entity and query in the latent space is interesting, but is only dedicated to one particular example. The visualization ability of Gaussian representations would match better with a solid error analysis or a case study with multiple examples covering different types of queries. \n\nOverall, I find the work solid and interesting, but the experiments part weak. I believe it requires a revision to prove the superiority of the proposed model. For example, the authors need to provide why their approach works better for some query types and why not for others. Moreover, an error analysis and a case study for different query types, alongside the visualization ability, would provide more in-depth insights into the performance. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have appropriately addressed the limitations and potential negative social impact of their work in Section 7 of the paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5"}, "extra_text": {}}, {"review_id": "EKKiJdLvmkB", "reviewer": "Reviewer_6UFN", "summary": "This paper provides a novel approach to using embeddings to directly encode chains of reasoning over KBs with a particular focus on choosing a representation capable of handling unions. The proposed approach represents:\n\n- Entities via Gaussian densities\n- Relations (referred to as \"translations\") as an *action on mixtures of Gaussians*\n- Intersection operations as a product of Gaussian densities\n- Union operations as a self-attention weighted combination of Gaussian densities\n\nThe authors demonstrate an improvement over a variety of baselines for standard logic embedding evaluations as well as a COVID-19 drug repurposing dataset.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Overview\n\n**Originality:** Are the tasks or methods new? Is the work a novel combination of well-known techniques? (This can be valuable!) Is it clear how this work differs from previous contributions? Is related work adequately cited?\n\n**Quality:** The proposed model seems technically sound, there are a few issues with the mathematical formalisms which need to be clarified. The authors seems to have some misconceptions about previous work, however, which leads them to make stronger criticisms or claims about than are appropriate. (See below.)\n\n**Clarity:** The submission is clearly written, however general editing and refactoring for clarity would improve it further.\n\n**Significance:** The authors evaluate on a number of standard tasks which are of interest to the community, and provide convincing evidence that their model outperforms baselines.\n\n---\n\n### Specific Questions / Suggestions:\n\n**L38:** The distance is typically not discontinuous. While for some methods the *gradient* may be discontinuous (eg. [0]), this typically isn't a problem for training. Even so, there are various ways to solve this, as have been developed in additional box embedding work (eg. convolution [1] or random latent variables [2]). This issue is also mentioned in the caption of Figure 2, and on line 62, but in each case the discontinuity is not really the problem. Query2Box, for example, uses a loss function with different weights inside the box or out. Similar to Gaussians, this will always assign some positive score to an entity, even outside the \"box\" which represents the query.\n\n**L114-L116:** (Minor) It would be better to simply say that the translations are *actions* on Gaussian mixtures - they take in a Gaussian mixture and return a new one. There's not really a sense in which their parameters are, themselves, representative of the mean and std deviation of a Gaussian. (This criticism also applies to Query2Box, which characterizes projections as boxes when in fact they are actions.)\n\n**L117-L124:** The product of two Gaussian PDFs is not Gaussian, rather it is *proportional* to a Gaussian. It is unclear to me whether you perform this rescaling or not - the definition of the intersection operation suggests that the result is always a normalized Gaussian, but the left-hand-side of equation (6) looks as though you are just multiplying PDFs, as does Figure 3(b). Depending on which you are performing, there may be an error in the derivation (which is fairly standard and may be moved to the appendix).\n\n**L127-128:** In the self-attention mechanism, are you using the mean and covariance parameters or the PDFs of the Gaussians?\n\n**L153:** Is the decomposed matrix $L$ diagonal? If so, I would suggest simply characterizing this fact as $\\Sigma^{-1} = \\text{diag}(\\lambda)$, rather than the decomposition. If not, how does it only require $d$ parameters?\n\n**Table 1:** FB15k-237, BQE actually performs best. In general, it seems BQE performs best for intersection queries. Do the authors have any intuition as to why this would be? (I would suggest that the reason has to do with the distinction of representing queries via random variables vs. densities - i.e. the BetaE paper represents queries as random variables, and the product of two Beta random variables is also a Beta random variable, whereas this paper proposes using the densities as the representation, and while the product of two Gaussian densities is also Gaussian the product of two Gaussian random variables is decidedly not Gaussian.)\n\n[0] Ren, Hongyu, Weihua Hu, and Jure Leskovec. \"Query2box: Reasoning over knowledge graphs in vector space using box embeddings.\" arXiv preprint arXiv:2002.05969 (2020).\n\n[1] Li, Xiang, Luke Vilnis, Dongxu Zhang, Michael Boratko, and Andrew McCallum. \"Smoothing the geometry of probabilistic box embeddings.\" In International Conference on Learning Representations. 2018.\n\n[2] Dasgupta, Shib Sankar, Michael Boratko, Dongxu Zhang, Luke Vilnis, Xiang Lorraine Li, and Andrew McCallum. \"Improving Local Identifiability in Probabilistic Box Embeddings.\" arXiv preprint arXiv:2010.04831 (2020).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Throughout, the authors imply that their method of using Gaussians enables handling the union in a more principled way, however this claim is a bit dubious (aside from empirical evidence) and previous methods may also be extended in a similar manner. For example, Query2Box could have equally well interpreted their outputs (via min pooling as a result of DNF transformation) as representative of a multimodal score function. Perhaps the argument in favor of this approach is simply that the mixture of Gaussians is smoother, and thus trains better, but in fact a min (or max, in the PDF case) does seem more in-line with a union query, an observation which the authors ignore. One can simply view this as a difference in pooling functions (self-attention or min/max) and the loss by which a vector is compared to a query (i.e. Mahalanobis distance vs. weighted $\\ell^1$).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper attempts to improve logical reasoning over knowledge graphs. In this regards, the authors propose a novel technique of  embedding complex logical queries and the chain reasoning steps as Gaussian mixtures. It is claimed that this allows for increased model expressibility and especially fits well for intersection. From empirical results, it seems the proposed method works well for certain types of queries. The reviewers found this work to be novel and interesting, but reached to a consensus that the reasoning provided do not corroborate with experimental results.  Also the reviewers found the presentation of some of the results hard to comprehend (e.g. the visualizations). Also it would be useful to understand and provide examples where the proposed model still fails. Thus, unfortunately I cannot recommend an acceptance of the paper in its current form, however the authors are strongly encouraged to make the fixes and resubmit to the next venue.
Decision: Accept (Poster)