Efficient Probabilistic Logic Reasoning with Graph Neural Networks
Authors: Yuyu Zhang
Xinshi Chen
Yuan Yang
Arun Ramamurthy
Bo Li
Yuan Qi
Le Song
Venue:  (2020)
Keywords: probabilistic logic reasoning
Markov Logic Networks
graph neural networks

Abstract: Markov Logic Networks (MLNs), which elegantly combine logic rules and probabilistic graphical models, can be used to address many knowledge graph problems. However, inference in MLN is computationally intensive, making the industrial-scale application of MLN very difficult. In recent years, graph neural networks (GNNs) have emerged as efficient and effective tools for large-scale graph problems. Nevertheless, GNNs do not explicitly incorporate prior logic rules into the models, and may require many labeled examples for a target task. In this paper, we explore the combination of MLNs and GNNs, and use graph neural networks for variational inference in MLN. We propose a GNN variant, named ExpressGNN, which strikes a nice balance between the representation power and the simplicity of the model. Our extensive experiments on several benchmark datasets demonstrate that ExpressGNN leads to effective and efficient probabilistic logic reasoning.

Published as a conference paper at ICLR 2020
EFFICIENT PROBABILISTIC LOGIC REASONING WITH GRAPH NEURAL NETWORKS
Yuyu Zhang', Xinshi Chen', Yuan Yang', Arun Ramamurthy Bo Lis, Yuan Qi' & Le Songl.1
!Georgia Institute of Technology SSiemens Corporate Technology
University of Illinois at Urbana Champaign *Ant Financial (yuyu, xinshi. chen, yyang7 54 @egatech. edu arun. wwnn..rmmurrtteieeeeeeee yuan. qi @ant fin. com, lsongêces cc. gatech. edu
com, lboβ pelfillimm allliniiii s edu
ABSTRACT
Markov Logic Networks (MLNs), which elegantly combine logic rules and proba- bilistic graphical models, can be used to address many knowledge graph problems. However, inference MLN is computationally intensive, making the industrial- scale application of MLN very difficult. In recent years, graph neural networks (GNNs) have emerged as efficient and effective tools for large-scale graph prob- lems. Nevertheless, GNNs do not explicitly incorporate prior logic rules into the models, and may require many labeled examples for target task. In this paper, we explore the combination of MINS and GNNs, and use graph neural networks for variational inference in MLN. We propose a GNN variant, named ExpressGNN, which strikes nice balance between the representation power and the simplicity of the model. Our extensive experiments on several benchmark datasets demonstrate that ExpressGNN leads to effective and efficient probabilistic logic reasoning.
INTRODUCTION
Knowledge graphs collect and organize relations and attributes about entities, which are playing an increasingly important role many applications, including question answering and information retrieval. Since knowledge graphs may contain incorrect, incomplete or duplicated records, additional processing such as link prediction, attribute classification, and record dc-duplication is typically needed improve the quality of knowledge graphs and derive new facts.
Markov Logic Networks (MLNs) were proposed to combine hard logic rules and probabilistic graphical models, which Domingos, 2006). The logic rules incorporate prior knowledge and allow MLNs to generalize in tasks with small amount of labeled data, while the graphical model formalism provides principled framework for dealing with uncertainty in data. However, inference in MLN is computationally intensive, typically exponential
be applied to various tasks knowledge graphs (Richardson &
the number of entities, limiting the real-world application of MLN. Also, logic rules can only cover a small part of the possible combinations of knowledge graph relations, hence limiting the application of models that are purely based on logic rules.
Graph neural networks (GNNs) have recently gained increasing popularity for addressing many graph related problems effectively (Dai et al., 2016; Li et al., 2016; Kipf & Welling, 2017; Schlichtkrull et al., 2018). GNN-based methods typically require sufficient labeled instances specific end tasks to achieve good performance, however, knowledge graphs have the long-tail nature (Xiong et al., 2018), i.c., large portion the relations in only are few triples. Such data scarcity problem among long-tail relations poses tough challenge for purely data-driven methods.
In this paper, we explore the combination of the best of both worlds, aiming for method which is data-driven yet can still exploit the prior knowledge encoded in logic rules. To this end, we design a simple variant of graph neural networks, named ExpressGNN, which can be efficiently trained in the variational EM framework for MLN. An overview of our method is illustrated Fig. ExpressGNN and the corresponding reasoning framework lead the following desiderata:

---

Published as a conference paper at ICLR 2020
MLN
Variational EM
GNN
TDD
<
formula potentall
predicate posterior
Knowledge Graph
Likelihood Decoding
Posterior Encoding
Figure 1: Overview of method for combining MLN and GNN using the variational EM framework.
Efficient inference and learning: ExpressGNN can be viewed as the inference network for MLN, which scales up MLN inference much larger knowledge graph problems.
Combining logic rules and data supervision: ExpressGNN can leverage the prior knowledge encoded in logic rules, as well as the supervision from graph structured data.
Compact and expressive model: ExpressGNN may have small number of parameters, yet is sufficient to represent mean-field distributions in MLN.
Capability of zero-shot learning: ExpressGNN can deal with the zero-shot learning problem where the target predicate has few or zero labeled instances.
2 RELATED WORK
Statistical relational learning. There is extensive literature relating the topic of logic reasoning. Here we only focus on the approaches that are most relevant to statistical relational learning on knowledge graphs. Logic rules can compactly encode the domain knowledge and complex depen- dencies. Thus, hard logic rules are widely used for reasoning in earlier attempts, such as expert systems (Igmizio, 1991) and inductive logie programming (Muggleton & De Raedt, 1994). However, hard logic is very brittle and has difficulty in coping with uncertainty in both the logic rules and the facts knowledge graphs. Later studies have explored to introduce probabilistic graphical model in logic reasoning, seeking to combine the advantages of relational and probabilistic approaches. Repre- sentative works including Relational Markov Networks (RMNs; Taskar et al. (2007)) and Markov Logic Networks (MLNs; Richardson & Domingos (2006) were proposed in this background.
Markov Logic Networks. MLNs have been widely studied due to the principled probabilistic model and effectiveness in a variety of reasoning tasks, including entity resolution (Singla & Domingos, 2006a), social networks (Zhang et al., 2014), information extraction (Poon & Domingos, 2007), etc. MLNS elegantly handle the noise in both logic rules and knowledge graphs. However, the inference and learning in MLNs is computationally expensive due to the exponential cost constructing the ground Markov network and the NP No-complete optimization problem. This hinders MLNs be applied to industry-scale applications. Many works appear in the literature to improve the original MLNs in both accuracy (Singla & Domingos, 2005; Mihalkova & Mooney, 2007) and efficiency (Singla & Domingos, 2006b; 2008; Poon & Domingos, 2006; Khot et al., 2011; Bach et al., 2015). Nevertheless, to date, MLNs still struggle to handle large-scale knowledge bases practice. Our framework ExpressGNN overcomes the scalability challenge of MINs by efficient stochastic training algorithm and compact posterior parameterization with graph neural networks.
Graph neural networks. Graph neural networks (GNNs; Dai et al. (2016); Kipf & Welling (2017)) can learn effective representations of nodes by encoding local graph structures and node attributes. Due to the compactness of model and the capability of inductive learning, GNNs are widely used in modeling relational data (Schlichtkrull et al., 2018; 8; Battaglia et al., 2018). Recently, Qu et al. (2019) proposed Graph Markov Neural Networks (GMNNs), which employs GNNs together with conditional random fields to learn object representations. These existing works are simply data-driven, and not able leverage the domain knowledge human prior encoded in logic rules. To the best
2

---

Published as a conference paper at ICLR 2020
of our knowledge, ExpressGNN is the first work that connects GNNs with first-order logic rules to combine the advantages of both worlds.
Knowledge graph embedding. Another line of research for knowledge graph reasoning is in the family of knowledge graph embedding methods, such as TransE (Bordes et al., 2013), NTN (Socher al., 2013), DistMult (Kadlec al., 2017), ComplEx (Trouillon al., 2016), and RotatE (Sun et al., 2019). These methods design various scoring functions to model relational patterns for knowledge graph reasoning, which are very effective in learning the transductive embeddings of both entities and relations. However, these methods are not able to leverage logic rules, which can be crucial in some relational learning tasks, and have no consistent probabilistic model. Compared these methods, ExpressGNN has consistent probabilistic model built in the framework, and can incorporate knowledge from logic rules. recent concurrent work Qu & Tang (2019) has proposed probabilistic Logic Neural Network (pl.ogicNet), which integrates knowledge graph embedding methods with MLNs with EM framework. Compared to pLogicNet which uses flattened embedding table as the entity representation, our work explicitly captures the structure knowledge encoded in the knowledge graph with GNNs and supplement the knowledge from logic formulae for the prediction task.
FCD
PRELIMINARY
MINN
Knowledge Graph. A knowledge graph is tuple K = (C, R, O) consisting of set C fci...., Cas of M entities, a set R fri..... TN } of N relations, and collection O = foi....,07 ) } of
PILRO
WAi
L observed facts. In the language of first-order logic, entities are also called constants. For instance, a constant can be a person or an object. Relations are also called predicates. Each predicate is a logic function defined over C, i..., r(-) C.... general, the arguments of predicates are asymmetric. For instance, for the predicate r(c, d') == [cc, c') (I for Like) which checks whether e likes c', the arguments c and c' are not exchangeable.
GKV
... x C + {0, 1) In
Figure 2: Bottom: A knowlcdge base as factor graph. (A, C, Dj are entities, and (Friend) and S (Smoke) are predicates. Top: Markov Logic Network (MLN) with formula f(c,c') -s(e)V -F(c, s(c'). Shaded circles correspond to latent variables.
With a particular set of entities assigned to the arguments, the pred- icate is called a ground predicate, and each ground predicate = a binary random variable, which will be used to define MIN. For a d-ary predicate, there are Md ways to ground it. We denote an assignment a,. For instance, with a, = (c, c'), we can simply write a ground predicate r(c, c') as r(a,). Each observed fact in knowledge bases is truth value (0. 1} assigned to ground predicate. For instance, a fact o can be [I(c, c)) = 1]. The number of observed facts is typically much smaller than that of unobserved facts. We adopt the open- world paradigm and treat these unobserved facts = latent variables.
As clearer representation, we express knowledge base K. by bipartite graph GK = (C, E,), where nodes on one side of the graph correspond to constants and nodes on the other side correspond to observed facts O which is called factor in this case. The set I edges. E = {ei,..., ), connect constants and the observed facts. More specifically, an edge = (c, o, i) between node e and o exists, if the ground predicate associated with uses as argument in its i-th argument position (Fig. 2).
Markoy Logic Networks. MLNs use logic formulae to define potential functions in undirected graphical models. A logic formula f()) C x ... x C. + {0, 1} is a binary function defined via the composition of a few predicates. For instance, a logic formula (c,,c') can be Smoke(c) (c) A Friend(c, c') = Smoke(c')
-Smoke(c) V -Friiend(c,e') v Sm"ke(c'), where - is negation and the equivalence is established by De Morgan's law. Similar to predicates, we denote an assignment of constants to the arguments of a formula f as a,, and the entire collection of consistent assignments of constants as A, {a).a ........ ... A formula with constants assigned to all of its arguments is called a ground formula. Given these logic representations, MLN can be defined as joint distribution over all observed facts O and unobserved facts H
Pi (O, == z(w) exp
EEEF Wy Eayes, $)(at))
(1)
where Z(w) is the partition function summing over all ground predicates and (.) is the potential function defined by formula f illustrated in Fig. 2. One form of de can simply be the truth
3

---

Published as a conference paper at ICLR 2020
value of the logic formula f. For instance. if the is f(c,'')=== := -s(e====(e---(.eeVsiie then o c') can simply take value when f(c, ") is true and 0 otherwise. Other more sophisticated øy can also be designed, which have the potential to take into account complex entities, such as images or texts, but will not be the focus of this paper. The weight w can be viewed as the confidence score of the formula f:: the higher the weight, the more accurate the formula is.
Difference between KG and MLN. We note that the graph topology of knowledge graphs and MLN can are very different, although MLN is defined on top of knowledge graphs. Knowledge graphs are typically very sparse, where the number of edges (observed relations) is typically linear in the number of entities. However, the graphs associated with MLN are much denser, where the number of nodes can be quadratic or more in the number of entities, and the number of edges (dependency between variables) also high-order polynomials in the number of entities.
4 VARIATIONAL EM FOR MARKOV LOGIC NETWORKS
In this section, we introduce the variational EM framework for MLN inference and learning, where we will use EXpressGNN key component (detailed in Sec. 5). Markov Logic Networks model the joint probabilistic distribution of all observed and latent variables, as defined in Eq. 1. This model can be trained by maximizing the log-likelihood of all the observed facts log (O). However, is intractable to directly maximize the objective, since it requires to compute the partition function Z (w) and integrate over all variables O and H. We instead optimize the variational evidence lower bound (ELBO) of the data log-likelihood, as follows
log Pw (O) 2 CELBO(Qo, Pw) == (QI(HO))) log P. (O, ()) EEQ log Qu (H10) (2)
where Qo (H () is a variational posterior distribution of the latent variables given the observed ones. The equality in Eq. 2 holds if the variational posterior Qo (H|O) equals to the true posterior Per (H((). We then use the variational EM algorithm (Ghahramani et al., 2000) to effectively optimize the ELBO. The variational EM algorithm consists of an expectation step (E-step) and maximization step (M-step), which will be called in an alternating fashion to train the model: 1) In the E-step (Sec. 4.1), we infer the posterior distribution of the latent variables, where Pa, is fixed and Qo is optimized to minimize the KL divergence between Qa (HOO) and P. O]; 2) In the M-step (Sec. 4.2), we learn the weights of the logie formulae in MLN, where Qo is fixed and Pa is optimized to maximize the data log-likelihood.
4.1 E-STEP: INFERENCE
In the E-step, which is also known as the inference step, we are minimizing the KL divergence between the variational posterior distribution Qa (H|O) and the true posterior distribution Pw (H|O). The exact inference of MI.N is computationally intractable and proven to be NP-complete (Richardson & Domingos, 2006). Therefore, choose to approximate the true posterior with mean-field distribution, since the mean-field approximation has been demonstrated to scale up large graphical models, such as latent Dirichlet allocation for modeling topics from large text corpus (Hoffman et al., 2013). In the mean-field variational distribution, each unobserved ground predicate r(a,) E H is independently inferred as follows:
Qo(H10) = Je Qo(r(ar)), Qor(a)))
(3)
where each factorized distribution (r(a))) follows the Bernoulli distribution. We parameterize the variational posterior Qo with deep learning models as our neural inference network. The design of the inference network is very important and has lot of considerations, since need compact yet expressive model to accurately approximate the true posterior distribution. We employ graph neural networks with tunable embeddings as our inference network (detailed in Sec. 5), which can trade-off between the model compactness and expressiveness.
With the mean-field approximation, LELBO(Qe, Pw)) defined in Eq. 2 can be reorganized as below:
(Ew, w Σ EQ.(HOO) [ log Z(w)) r(a,)Em
Σ Equ(r(a.)) log Qo(r(a.)))). (4)
FEF ayEA,
where Wy is fixed in the E-step and thus the partition function Z(w) can be treated as a constant. We notice that the first term (ooo P.. (O, H)) has the summation over all formulae and all
4

---

Published as a conference paper at ICLR 2020
possible assignments to each formula. Thus this double summation may involve a large number of terms. The second term (HI0)) [log Qo (H]O) is the sum of entropy of the variational posterior distributions (r(r(),)), which also involves large number of terms since the summation ranges over all possible latent variables. Typically, the number of latent facts in database is much larger than the number of observed facts. Thus, both terms in the objective function pose the challenge of intractable computational cost.
To address this challenge, we sample mani-bacches of ground formulae to break down the exponential summations by approximating it with sequence of summations with controllable number of terms, More specifically, in each optimization iteration, we first sample batch of ground formulae. For each ground formula in the sampled batch, we compute the first term in Eq. 4 by taking the expectation of the corresponding potential function with respect to the posterior of the involved latent variables. The mean-field approximation enables us to decompose the global expectation over the entire MLN into local expectations over ground formulae. Similarly, for the second term in Eq. 4, we use the posterior of the latent variables in the sampled batch to compute a local sum of entropy.
For tasks that have sufficient labeled data as supervision, we can add supervised learning objective to enhance the inference network, as follows:
Liatei (Qo) Deo log Qo(r(a,)).
(5)
This objective is complementary to the ELBO on predicates that are not well covered by logic rules but have sufficient observed facts. Therefore, the overall E-step objective function becomes:
Lo = LELBO(QO Pw) + XLuaa
(6)
where À is hyperparameter to control the weight. This overall objective essentially combines the knowledge in logic rules and the supervision from labeled data.
4.2 M-STEP: LEARNING
In the M-step, which is also known as the learning step, we are learning the weights of logic formulae in Markov Logic Networks with the variational posterior Qo (HI fixed. The partition function (ww in Eq. 4 is not a constant anymore, since we need to optimize those weights in the M-step. There are exponential number of terms in the partition function Z(w), which makes it intractable to directly optimize the ELBO. To tackle this problem, we adopt the widely used pseudo-log-ikkeiibe (Richardson & Domingos, 2006) as an alternative objective for optimization, which is defined as:
P (O, H) = (H(() Er(aneex log (r(a,) MB.((a)))
where MBr(a,) is the Markov blanket of the ground predicate r(a,)), i.c., the set of ground predicates that appear in some grounding of a formula with r(a,). For each formula i that connects r(a,) to its Markov blanket, we optimize the formula weight w; by gradient descent, with the derivative:
(8) where Yr(as) = 0 or 1 if r(a,)) is an observed fact, and Dr(a.) = (r(()))) otherwise. With the independence property of Markov Logic Networks, the gradients of the logic formulae weights can be efficiently computed on the Markov blanket of each variable.
V 10 [log Pw (r(a,) MB,(a.))] = Ur(a.) - (r(aa) MBr(a.)),
For the M-step, design a different sampling scheme to make computationally efficient. For each variable in the Markov blanket, we take the truth value if it's observed and draw a sample from the variational posterior Qe if it's latent. In the M-step, the ELBO of a fully observed ground formula depends on the formula weight, thus we need to consider all the fully observed ground formulae. It is computationally intractable use all possible ground predicates compute the gradients in Eq. To tackle this challenge, we simply consider all the ground formulae with at most one latent predicate, and pick up the ground predicate if its truth value determines the formula's a's truth value. Therefore, we keep a small subset of ground predicates, each of which can directly determine the truth value of ground formula. Intuitively, this small subset contains all representative ground predicates, and makes good estimation of the gradients with much cheaper computational cost.
5 INFERENCE NETWORK DESIGN: EXPRESSGNN
In the neural variational EM framework, the key component is the posterior model, or the inference network. We need to design the inference network that is both expressive and efficient approximate
5

---

Published as a conference paper at ICLR 2020
the true posterior distribution. A recent concurrent work Qu & Tang (2019) uses flattened embedding table as the entity representation to model the posterior. However, such simple posterior model is not able to capture the structure knowledge encoded in the knowledge graph. We employ graph neural networks with tunable embeddings to design our inference network. We also investigate the expressive power of GNN from theoretical perspective, which justifies our design.
Our inference network, named ExpressGNN, consists of three parts: the first part is a vanilla graph neural network (GNN), the second part uses tunable embeddings, and the third part uses the embeddings to define the variational posterior. For simplicity, we assume that each predicate has two arguments (i.e., consider only r rec, c')). We design each part as follows:
We build a GNN on the knowledge graph 9k, which is much smaller than the ground graph of MLN (see comparison in Fig. 2). The computational graph of the GNN is given in Algorithm 1. The GNN parameters 0 and 02 are shared across the entire graph and independent of the number of entities. Therefore, the GNN a compact model with (dd)) parameters given d dimensional embeddings, Me E R...
For each entity in the knowledge graph, we augment its GNN embedding with a tunable embedding We e R as fac = [Me, The tunable embeddings increase the expressiveness of the model. As there are M entities, the number of parameters in tunable embeddings is OKkM).
We use the augmented embeddings of 01 and C2 to define the variational posterior. Specifically, Qo(r(c1, o2)) = o (MLP Pez, r; 0z)), where a(-) I+exp(--)- The number of parameters in 0z is Od k:).
Algorithm 1: GNN()
In summary, ExpressGNN can be viewed as a two-level encoding of the entities: the compact GNN assigns similar embeddings to similar entities in the knowl- edge graph, while the expressive tunable embeddings provide additional model capacity to encode entity- specific information beyond graph structures. The over- all number of trainable parameters in ExpressGNN is Old + kM). By tuning the embedding size d and k, ExpressGNN can trade-off between the model compact- ness and expressiveness. For large-scale problems with a large number of entities (M is large), ExpressGNN can save lot of parameters by reducing k.
Initialize entity node: no, Vc E C for t 0 to T' do
> Compute message Vr(c,e') EO
(t) m d' = MLP (t) r; 01)
a Aggregate message Vc C
(++1) AGG((m ( -edeet()))))))) me
> Update embedding VC E
me ((+1) = MLP (t), ((+1), 02) me
return embeddings (1("T)
5.1 EXPRESSIVE POWER OF GNN AS INFERENCE NETWORK
The combination of GNN and tunable embeddings makes the model sufficiently expressive to approximate the true posterior distributions. Here we provide theoretical analysis on the expressive power of GNN in the mean-field inference problem, and discuss the benefit of combining GNN and tunable embeddings in ExpressGNN.
Recent studies (Shervashidze et al., 2011; Xu et al., 2018) show that the vanilla GNN embeddings can represent the results of graph coloring, but fail to represent the results of the more strict graph isomor- phism check, i.e., GNN produces the same embedding for some nodes that should be distinguished. We first demonstrate this problem by a simple example:
((AEE)
(BBE)
Example. Fig. 3 involves four entities (A, B, E, F), two predi- cates (Friend: -(.-), Like: L).,-)), and one formula (F(c, e') + L(c, c')). In this example, MLN variables have different posteri- ors, but GNN embeddings result in the same posterior represen- tation. More specifically,
MAJEI
PIBLI:
LINED
PIB -B
aa
Entity A and B have opposite relations with E, i.e., ((A, 1 versus F(B GNN on the knowledge graph will always produce the same embeddings for A and B, i.e., PA pB.
0 in the knowledge graph. but running
H
up
Figure 3: Bottom: A knowledge base with 0-1-0-1 loop. Top: MLN.

---

Published as a conference paper at ICLR 2020
L(A, and E) apparently have different posteriors. However, using GNN embeddings, (2( = a (MLPs(MA, (E, L)) always identical to Qo(L(B, E)) (MLP3(UB: Me,
We can formally prove that solving the problem in the above example requires the graph embeddings to distinguish any non-isomorphic nodes in the knowledge graph. formal statement is provided below (see Appendix E for the proof).
Definition 5.1. Two ordered sequences of nodes (c....., G.) and (c)...., ,,,), are isomorphic in a graph 9K there exists an isomorphism ग Gi + 9K such that T())) =c cI...., (c.) cn.
Theorem 5.1. Two latent variables r(cr,..., Ca) and r(c,,..., ,n) have the same posterior dis- tribution in any MLN if and only if the nodes (c1,--, Ca) and (c',' ",,,",,,,,,,, ,,,) are isomorphic in the knowledge graph 9x.
Implied by the theorem, to obtain expressive enough representation for the posterior, need more powerful GNN variant. A recent work has proposed a powerful GNN variant (Maron et al., 2019), which can handle small graphs such chemical compounds and protein structures, but it is computationally expensive due to the usage of high-dimensional tensors. As a simple yet effective solution, ExpressGNN augments the vanilla GNN with additional tunable embeddings, which is trade-off between the compactness and expressiveness of the model.
In summary, ExpressGNN has the following nice properties:
ExpressGNN directly works on the knowledge graph, instead of the huge MLN grounding graph, making it much more efficient than the existing MI. inference methods.
Efficiency:
Compactness: The compact GNN model with shared parameters can be very memory efficient, making ExpressGNN possible to handle industry-scale problems.
Expressiveness: The GNN model can capture structure knowledge encoded in the knowledge graph. encode entity-specific information, which compensates
Meanwhile, the tunable embeddings for GNN's deficiency in distinguishing non-isomorphic nodes.
Generalizubility With the GNN embeddings, ExpressGNN may generalize to new entities or even different but related knowledge graphs unseen during training time without the need for retraining.
6 EXPERIMENTS
Benchmark datasets. We evaluate ExpressGNN and other baseline methods on four benchmark
datasets: UW-CSE (Richardson & Domingos, 2006), Cora (Singla & Domingos, 2005), synthetic Kinship datasets, and FB15K 1533773 (Toutanova & Chen, 2015) constructed from Freebase (Bollacker et al., 2008). Details and full statistics of the benchmark datasets are provided in Appendix B.
General settings. We conduct all the experiments machine powered by Intel Xeon Silver 41 16 processors at 2. 10GHz with 256GB RAM. We implement ExpressGNN using PyTTrchh and train it with Adam optimizer (Kingma & Ba, 2014). To ensure fair comparison, we allocate the same computational resources (CPU, GPU and memory) for all the experiments. We use the default tuned hyperparameters for competitor methods, which can reproduce the experimental results reported in their original works.
GPU-enabled (Nvidia RTX 2080 Ti) Linux
Model hyperparameters. For ExpressGNN, we use 0.0005 the initial learning rate, and decay by half for every 10 epochs without improvement of validation loss. For Kinship, UW-CSE and Cora, we run ExpressGNN with a fixed number of iterations, and use the smallest subset from the original split for hyperparameter tuning. For FB 15K-237, we use the original validation set to tune the hyperparameters. We use a two-layer MLP with ReLU activation function as the nonlinear transformation for each embedding update step in the GNN model. We learn different MLP parameters for different steps. To increase the model capacity of ExpressGNN, we also use different MLP parameters for different edge type, and for different direction of embedding aggregation. For each dataset, we search the configuration of ExpressGNN on either the validation set or the smallest subset. The configuration embeddings and GNN embeddings, the number of embedding update steps, and the sampling batch size. For the inference experiments, the weights for all the logic formulae are fixed as 1. For the
search includes the embedding size, the split point of tunable
7

---

Published as a conference paper at ICLR 2020
Table I: Inference accuracy (AUC-PR) of different methods on three benchmark datasets.
Kinship
UW-CSB Language
Cora
Method
S1
S3
S4
S5
Al
Graphics
Systems
Theory
(avg)
MCMC
0.53
BP / Lifted BP
0.53
0.58
0.55
0.55
0.56
0.01
0.01
0.01
0.01
0.01
MC-SAT
0,54
0.60
0.55
0.55
0.03
0.05
0,06
0.02
0.02
HL-MRF
1,00
1,00
1,00
1.00
0.06
0.06
0,02
0.04
0.03
ExpressGNN-E
0.97
0.97
0.99
0.99
0.99
0.09
0.19
0.14
0.06
0.09
0.64
learning experiments, the weights are initialized as 1. For the choice of in the combined objective Le in Eq. 6, we set À = 0 for the inference experiments, since the query predicates are never seen in the training data and no supervision is available. For the learning experiments, we À
6.1 COMPARISON TO MLN INFERENCE METHODS AND ABLATION STUDY
We first evaluate the inference accuracy and efficiency of ExpressGNN. We compare our method with several strong MLN inference methods on UW-CSE, Cora and Kinship datasets. We also conduct ablation study to explore the trade-off between GNN and tunable embeddings.
Experiment settings. For the inference experiments, we fix the weights of all logic rules 1. A key advantage of MLN is that can handle open-works setting in consistent probabilistic framework. Therefore, adopt open- world setting for all the experiments, as opposed to closed-world setting where unobserved facts (except the query predicates) are assumed to be false. We also report the performance under closed-world setting in Appendix C.
Prediction tasks. The deductive logic inference task is to answer queries that typically involve single predicate. For example in UW-CSE, the task is predict the Advi sedBy(ccc) relation for all persons in the set. In Cora, the task is to de-duplicate entities, and one of the query predicates is SameAuthcr(c..)) As for Kinship, the task is predict whether person is male or female, i.c.. Male (c). For each possible substitution of the query predicate with different entities, the model is tasked to predict whether it's true or not.
Evaluation metrics. Following existing studies (Richardson & Domingos, 2006; Singla & Domingos, 2005), we use area under the precision-reed -ecaall curve (AUC-PR) to evaluate the inference accuracy. To evaluate the inference efficiency, we use wall-clock running time in minutes.
Competitor methods. We compare our method with several strong MIN inference algorithms, including MCMC (Gibbs Sampling: Gilks et al. (1995); Richardson & Domingos (2006)), Belief Propagation (BP; Yedidia et al. (2001)), Lifted Belief Propagation (Lifted BP: Singla & Domingos (2008)), MC-SAT (Poon & Domingos, 2006) and Hinge-Loss Markov Random Field (HL-MRF; Bach et al. (2015); Srinivasan et al. (2019)).
Inference accuracy. The results of inference accuracy three benchmark datasets reported in Table A hyphen in the entry indicates that it is either out of memory or exceeds the time limit (24 hours). We denote our method ExpressGNN-E since only the E-step is needed for the inference experiments. Note that since the lifted BP is guaranteed to get identical results as BP (Singla & Domingos, 2008), the results of these two methods are merged into one row. For these experiments, ExpressGNN-E uses 64-dim GNN embeddings and 64-dim tunable embeddings. On Cora, all the baseline methods fail bandle the data scale under open-world setting, and ExpressGNN-E achieves good inference accuracy. On UW-CSE, ExpressGNN-E consistently outperforms all baselines. The Kinship dataset is synthesized and noise-free, and the number of entities increases linearly on the five sets S1-S5. HL-MRF achieves perfect accuracy for $1-S4, but is infeasible on the largest set S5. ExpressGNN-E yields similar but not perfect results, which presumably caused by the stochastic nature of our sampling and optimization procedure.
Inference efficiency. The inference time corresponding to the experiments in Table is summarized in Fig. 4. On UW-CSE (left table), ExpressGNN-E uses much shorter time for inference compared to all the baseline methods, and meanwhile ExpressGNN-E achieves the best inference performance. On Kinship (right figure), as the data size grows linearly from S1 to S5, the inference time of most baseline methods grows exponentially, while ExpressGNN-E maintains a nearly constant time cost, demonstrating its nice scalability. Some baseline methods such as MCMC and MC-SAT become
8

---

Published as a conference paper at ICLR 2020
infeasible for larger sets. HL-MRF maintains comparatively short inference time, however, it has huge increase of memory cost and not able to handle the largest set S5.
Method
Inference (minutes)
HBF
A1
Graphics
Language
Systems
Theory
Lifted
MCMC
24hh
>-4hh
>-4hh
2-24h
>44h
900
352
457
300
Liñed BP
321
270
32
525
243
MC-SAT
172
147
196
86
200
HL-MRF
135
132
18
178
72
100
ExpressGNN-E
14
20
5
7
13
51
53
55
Figure Left Right: Inference time on UW-CSE/ Kinship respectively. N/A indicates the method is infeasible.
Ablation study. ExpressGNN can trade-off the compactness and expressiveness of model by tuning the dimensionality of GNN and tunable embeddings. We perform ablation study on the Cora dataset to investigate how this trade-off affects the inference accuracy. Results of different configurations of ExpressGNN-E are shown in Table 2. It is observed that GNN64+ Tune4 has comparable performance with Tune64, but is consistently better than GNN64. Note that the number of parameters in GNN64+Tune4 is (64 + CC), while that in Tune64 is (664(C). When the number of entities is large, GNN64+Tune4 has much less parameters to train. This is consistent with our theoretical analysis result: As compact model, GNN saves lot of parameters, but GNN alone is not expressive enough. similar conclusion is observed for GNN64+Tune66 and Tune Therefore, ExpressGNN seeks combination of two types of
Table 2: AUC-PR for different combi-
nations of GNN and tunable embeddings. Tune stands for d-dim tunable embed- dings and GNN d stands for d-dim GNN embeddings.
Cora
Configuration
S1
S2
S3
S4
S5
Tune64
0.57
0.74
0.34
0.55
0.70
GNN64
0.57
0.58
0.38
0.54
0.53
GNN64+Tuned
0.61
0.75
0.39
0.54
0.70
Tune128
0.62 0.76
0.42
0.60
0.73
GNN128
0.59
0.45
0.55
0.61
GNN64+Tune64
0.62
0.79 0.46 0.57 0.75
embeddings to possess the advantage of both: having a compact model and being expressive. The best configuration of their embedding sizes can be varied on different tasks, and determined by the goal: getting a portable model or better performance.
6.2 COMPARISON KNOWLEDGE BASE COMPLETION METHOSS
We evaluate ExpressGNN in the knowledge base completion task on the FB15K-231 dataset, and compare it with oatte-of-th-aaee art knowledge base completion methods.
Experiment settings. To generate logic rules, we use Neural LP (Yang et al., 2017) on the training set and pick up the candidates with top confidence scores. See Appendix D for examples of selected logic rules. We evaluate both inference-only and Sierence-anndlearmien version of ExpressGNN, denoted as ExpressGNN-E and ExpressGNN-EEM respectively.
Prediction task. For each test query r(c, d') with respect to relation r, the model is tasked to generate rank list over all possible instantiations of r and sort them according the model's confidence how likely this instantiation is true.
Evaluation metrics. Following existing studies (Bordes al., 2013: Sun et al., 2019), we use filtered ranking where the test triples are ranked against all the candidate triples not appearing in the dataset. Candidate triples are generated by corrupting the subject object of query r(c, c'). For evaluation. we compute the Mean Reciprocal Ranks (MRR), which is the average of the reciprocal rank of all the truth queries, and Hits @ 10, which the percentage of truth queries that are ranked among the top 10.
Competitor methods. Since none of the aforementioned MLN inference methods can scale up to this dataset, we compare ExpressGiNN with a number state-of-the -fe--ar-rt methods for knowledge base completion, including Neural Tensor Network (NTN; Socher et al. (2013)). Neural LP (Yang et al., 2017), DistMult (Kadlec et al., 2017), ComplEx (Trouillon et al., 2016), TransE (Bordes et al., 2013), RotatE (Sun et al., 2019) and pLogicNet (Qu & Tang, 2019). The results of MLN and pLogicNet are directly taken from the paper Qu & Tang (2019). For all the other baseline methods, we use publicly available code with the provided best hyperparameters run the experiments.

---

Published as a conference paper at ICLR 2020
Table Performance on FB15K-237 with varied training set size.
Table 4: Zero-shot learning
Model
MRR
Hits @ 10
performance on FB FB15K-20 15K-2337.
0%
5%
10%
20%
100%
0%
5%
10%
20%
100%
Model
MRR
Hits@ 10
MLN
0.10
16.0
NTN
0.09
0.10
0.10
0.11
0.13
17.9
19.3
19.1
19.6
23.9
NTN
0.001
0.0
Neural LP
0.01
0.13
0.15
0.16
0.24
1.5
23.2
24.7
26.4
36.2
Neural LP
0.010
2.7
DistMult
0.23
0.24
0.24
0.24
0.31
40.0
40.4
40.7
41.4
48.5
DistMult
0.004
0.8
ComplEx
0.24
0.24
0.24
0.25
0.32
41.1
41.3
41.9
42.5
51.1
ComplEx
0.013
2.2
TransE
0.24
0.25
0.25
0.25
0.33
42.7
43.1
43.4
43.9
52.7
TransE
0.003
0.5
RotatE
0.25
0.25
0.25
0.26
0.34
42.6
43.0
43.5
44.1
53.1
RotatE
0.006
1.5
pLogicNet
0.33
52.8
ExpressGNN-E
0.181
29.3
ExpressGNN-E 0.42 0.42
0.42
0.44
0.45
53.1
53.1
53.3
55.2
57.3
ExpressGIN-EM 0.185
29.6
EXpressGNN-EM 0.42 0.42
0.43
0.45
0.49
53.8
54.6
55.3
55.6
60.8
Performance analysis. The experimental results on the full training data are reported in Table (100% columns). Both Express(iNN-E and ExpressGNN-EN significantly outperform all the baseline methods. With learning the weights logic rules, ExpressGNN-ENN achieves the best performance. Compared to MLN, ExpressGNN achieves much better performance since MLN only relies on the logic rules while ExpressGNN can also leverage the labeled data as additional supervision. Compared knowledge graph embedding methods such TransE and RotatE, ExpressGNN can leverage the prior knowledge in logic rules and outperform these purely mata-driven methods.
Data efficiency. We investigate the data efficiency of EXpressGNN and compare it with baseline methods. Following (Yang et al., 2017). we split the knowledge base into facts / ttaining / validation / testing sets, and vary the size of the training set from 0% to 100% to feed the model with complete facts set for training. From Table 3, we see that ExpressGNN performs significantly better than the baselines on smaller training data. With more training data as supervision, data-driven baseline methods start to close the gap with ExpressGNN This clearly shows the benefit of leveraging the knowledge encoded in logic rules when there data is insufficient for supervised learning.
Zero-shot relational learning. In practical scenarios, a large portion of the relations in the knowledge base are long-tail, i.c., most relations may have only a few facts (Xiong et al., 2018). Therefore, relations with insufficient training data. We
is important investigate the model performance construct a zero-shot learning dataset based on FB 1K-2337 by forcing the training and testing data to have disjoint sets of relations. Table 4 shows the results. As expected, the performance of all the supervised relational learning methods drop to almost zero. This shows the limitation of such methods when coping with sparse long-tail relations. Neural LP designed handle new entities in the test set (Yang et al., 2017), but still struggles to perform well in zero-shot learning. In contrast, ExpressGNN leverages both the prior knowledge in logic rules and the neural relational embeddings for reasoning, which is much less affected by the scarcity of data on long-tail relations. Both variants of our framework (ExpressGNN-EE and ExpressGNN-EMM achieve significantly better performance.
CONCLUSION
This paper studies the probabilistic logic reasoning problem, and proposes ExpressGiNN to combine the advantages of Markov Logic Networks in logic reasoning and graph neural networks in graph representation learning. ExpressGNN addresses the scalability issue Markov Logic Networks with efficient stochastic training in the variational EM framework. ExpressGNN employs GNNs to capture the structure knowledge that is implicitly encoded in the knowledge graph, which serves as supplement to the knowledge from logic formulae. ExpressGNN is general framework that can trade-off the model compactness and expressiveness by tuning the dimensionality of the GNN and the embedding part.
ACKNOWLEDGEMENTS
We acknowledge grants from NSF IIS- 121-42,, NIH BIGDATA IR01031,,34), NSF CAREER IIS- 1350983, NSF US-16997792 EAGER, NSF IIS- 1841351 EA-GER, NSF CNSS-104770 ONR N00014- N00014-15-1-2340 Intel ISTC, Nvidia, Google, Amazon AWS and Siemens. We thank Hyunsu Park for his insightful discussions and help on experiments. We thank the anonymous reviewers for their helpful and thoughtful comments. Yuyu Zhang is supported by the Siemens FutureMaker Fellowship.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Stephen H Bach, Matthias Broecheler, Bert Huang, and Lise Getoor. Hinge-loss markov random fields and probabilistic soft logic. arXiv preprint arXiv: 040460 2015.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzale, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 180.00161, 2018.
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collabora- tively created graph database for structuring human knowledge. Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 1247-1250. AcM, 2008.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in neural information processing systems, pp. 2787-2795, 2013.
Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for structured 2016.
data. In International conference on machine learning, pp.
Woodrow W Denham. The detection of patterns in Alyawara nonverbal behavior. PhD thesis,
University of Washington, Seattle., 1973.
Zoubin Ghahramani, Matthew J Beal, et al. Graphical models and variational methods. Advanced mean field methods-theory and practice. MIT Press, 2000.
Walter R Gilks, Sylvia Richardson, and David Spiegelhalter. Markov chain Monte Carlo in practice. Chapman and Hall/CRC, 1995.
Matthew Hoffman, David M Blei, Chong Wang. and John Paisley. Stochastic variational inference. The Journal of Machine Learning Research, 141311303-1377 2013.
James Ignizio. Introduction to expert systems, volume 21. 1991.
Rudolf Kadlec, Ondrej Bajgar, and Jan Kleindienst. Knowledge base completion: Baselines strike back. arXiv preprint 1705
2017.
Tushar Khot, Sriraam Natarajan, Kristian Kersting, and Jude Shavlik. Learning markov logic networks via functional gradient boosting. In 201/ IEFE I1th International Conference on Data Mining, pp- 320-329. IEEE, 2011.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:
arXiv:1412.6988 /4/2.6980, 2014.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In ICLR, 2016.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. arXiv preprint arXiv: 190.. 2019.
Lilyana Mihalkova and Raymond J Mooney. Bottom-up learning of markov logic network structure. In Proceedings of the 24th international conference on Machine learning, pp. 625-632. ACM, 2007.
Stephen Muggleton and Lue De Raedt. Inductive logic programming: Theory and methods. The Journal of Logic Programming, 19:629-679, 1994.
Hoifung Poon and Pedro Domingos. Sound and efficient inference with probabilistic and deterministic dependencies. In AAAI, volume 6, pp. 458-465- 463, 2006.

---

Published as a conference paper at ICLR 2020
Hoifung Poon and Pedro Domingos. Joint inference in information extraction. In AAAI, volume pp. 913-918, 2007.
Meng Qu and Jian Tang. Probabilistic logic neural networks for reasoning. arXiv preprint orXiv:/906.000 08495, 2019.
Meng Qu, Yoshua Bengio, and Jian Tang. GMNN: Graph Markov neural networks. In Proceedings of the 36th International Conference on Machine Learning, pp. 5241-5250, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Matthew Richardson and Pedro Domingos. Markov logic networks. Machine learning, 62(1-2): 107-136, 2006.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(Sep): 2539-2561, 2011.
Parag Singla and Pedro Domingos. Discriminative training of markov logic networks. In AAAI, volume 5, pp. 868-873, 2005.
Parag Singla and Pedro Domingos. Entity resolution with markov logic. In Data Mining, 2006.
ICDM'06 06. Sixth International Conference on, pp. 572-582, IEEE, 2006a.
Parag Singla and Pedro Domingos. Memory--fficient inference in relational domains. In AAAI, volume 6, pp. 488-493, 2006b.
Parag Singla and Pedro M Domingos. Lifted first-order belief propagation. In AAAI, volume 8, pp. 1099, 2008
Richard Socher, Danqi Chen, Christopher D Manning, and Andrew Ng. Reasoning with neural tensor networks for knowledge base completion. In Advances neural information processing systems, pp. 926-9344 2013.
Sriram Srinivasan, Behrouz Babaki, Golnoosh Farnadi, and Lise Getoor, Lifted hinge-loss markov random fields. AAAI, 2019.
Zhiqing Sun, Zhi-Hong Deng, Jian Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. arXiv preprint arXiv: 1902. 10197, 2019.
Ben Taskar, Pieter Abbeel, Ming-Fai Wong, and Daphne Koller. Relational markov networks. Introduction to statistical relational learning, pp. 175-200, 2007.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality, pp- 57-66, 2015.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In International Conference on Machine Learning, pp. 2071-2080 2016.
Wenhan Xiong, Mo Yu, Shiyu Chang, Xiaoxiao Guo, and William Yang Wang. One-shot relational learning for knowledge graphs. arXiv preprint arXiv: 1808. 09040, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1810.:/8100000 2018.
Fan Yang. Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base completion. CoRR, abs/l702.08366 2017.
Jonathan S Yedidia, William T Freeman, and Yair Weiss. Generalized belief propagation. In Advances in neural information processing systems, pp. 689,695,10 2001.
Weizhe Zhang, Xiaoqiang Li, Hui He, and Xing Wang. Identifying network public opinion leaders based on markov logic networks. The scientific world journal, 2014, 2014.
12

---

Published as a conference paper at ICLR 2020
Appendix
A
COUNTER EXAMPLES
We provide more examples in this section to show that it is more than a rare case that GNN embeddings alone not expressive enough.
A.I
EXAMPLE 1
F(A,E)=1
A
E
F(B,F)=1
B
F
f(A,B)
F(B
F(A,F) =1
L(AEE) =2
F(R,E) =?
L(BEF) =?
Figure Example
Top:
Knowledge base. Bottom: MLN
Unlike the example shown in main text, where A and have OPPOSITE relation with E, Fig. shows a very simple example where A and B have exactly the same structure which makes A and indistinguishable and isomorphic. However, since (A,E) and (B,E) are not isomorphic, can be easily seen that L(A, E) has different posterior from L(B,E)
A.2 EXAMPLE 2
F(AE)=
E
F(A,F=0
FYB,E)=
F(B,F)=1
S(A,E)
F(AEE) =
L(A,E) =!
F(REE) =
L(B.E) =?
Figure 6: The same example as in Fig. 3. Top: Knowledge base. Bottom: MLN
Fig. shows an example which is the same as Fig. 3. However, in this example, it is already revealed in the knowledge base that (A, F) and (B, F) have different local structures they connected by different observations. That is, (A, [ (A, = =]] F) and (B, [F(8, F) 0] F) can be distinguished by GNN.
Now, we use another example in Fig. to show that even when the local structures are the same, the posteriors can still be different, which is caused by the formulae.
13

---

Published as a conference paper at ICLR 2020
H
FiC
F(A,Fje1
RGMie
F(BFF)
K
F(G,K)eD)
(G0g)))))((((())( TF(CgC2) A F((,))) M(C,)2))
LAC
f(AEB..))
F(C.D.DK)
FIC.H.G.M)
FCAJE) -1
FTIEF) =0
P(R,F)
F(A.F)
FCC.D
FILDD
FID.KI
P(C =
FIC.D
FIG.E
PrG.MD =l
FIC
Figure 7: Example 2. Top: Knowledge base. Bottom: MLN
In Fig. 7, E) and (C.H) have the same local structure, so that the tuple (A, (A, E) = 1], B) and NOT be distingushed by GNN. However. B, to define a formula, and then the resulting MIN gives different posterior to L(A,, E) and T.(C, H), be from the figure. Note that this construction of MIN is the same the construction steps stated in the proof in Sec.
(c, (C, = 1]
make of subgraph
14

---

Published as a conference paper at ICLR 2020
Table 5: Complete statistics of the benchmark datasets.
# ground predicate
ground
Dataset
# entity
# relation
# fact # query
formula
FB15K-237
15K
237
272K
20K
50M
679B
Kinship-SI
62
15
187
38
50K
550K
Kinship-S2
110
15
307
62
158K
3M
Kinship-S3
160
15
482
102
333K
9M
Kinship-S4
221
15
723
150
635K
23M
Kinship-S5
266
15
885
183
920K
39M
UW-CSE-AI
300
22
731
4K
95K
73M
UW-CSE-Graphine
195
22
449
4K
70K
64M
UW-CSE-Language
182
1K
15K
9M
UW-CSE-Systems
277
22
733
5K
95K
121M
UW-CSE- -h-rryy
174
22
465
2K
51K
54M
Cora-S1
670
10
11K
2K
175K
621B
Cora-S2
602
10
9K
2K
156K
431B
Cora-S3
607
10
18K
3K
156K
438B
Cora-S4
600
10
12K
2K
160K
435B
Cora-S5
600
10
11K
2K
140K
339B
B DATASET DETAILS
For our experiments, we use the following benchmark datasets:
The social network dataset UW-CSE (Richardson & Domingos, 2006) contains publicly available information of students and professors the CSE department UW. The dataset is split into five sets according to the home department of the entities.
The entity resolution dataset Cora (Singla & Domingos, 2005) consists a collection citations to computer science research papers. The dataset is also split into five subsets according to the field research.
We introduce synthetic dataset that resembles the popular Kinship dataset (Denham, 1973). The original dataset contains kinship relationships (e.g., Father, Brother) among family members in the Alyawarra tribe from Central Australia. The synthetic dataset closely resembles the original Kinship dataset but with a controllable number of entities. To generate dataset with entities, we randomly split n entities into two groups which represent the first and second generation respectively. Within each group, entities are grouped into a few sub-grouph soobgroups representing the sister- and brother-hood. Finally, entities from different sub-groups in the first generation are randomly coupled and sub-group in the second generation is assigned to them as their children. To generate the knowledge base, we traverse this family tree, and record all kinship relations for each entity. We generate five kinship datasets (Kinship $1 S1-S5) by linearly increasing the number of entities.
The knowledge base completion benchmark FB 1-3772 (Toutanova & Chen, 2015) a generic knowledge base constructed from Freebase (Bollacker et al., 2008), which is designed challenging variant of FB 15K. More specifically, FB 1K3-333 37 is constructed by removing near- duplicate and inverse relations from FB 1BK.. The dataset is split into training validation testing and we use the same split of facts from training as in prior work (Yang et al., 2017).
more
The complete statistics of these datasets shown in Table 5. Examples of logic formulae used in four benchmark datasets are listed in Table 7.
C INFERENCE WITH CLOSED-WORLD SEMANTICS FOR BASELINE METHODS
In Sec. 6.1 we compare EXpressGNN with five probabilistic inference methods under open-world semantics. This is different from the original works, where they generally adopt the closed-won world setting due to the scalability issues. More specifically, the original works assume that the predicates (except the ones in the query) observed in the knowledge base is closed, meaning for all instantiations
15

---

Published as a conference paper at ICLR 2020
Table Inference performance of competitors and our method under the closed-world semanties.
Cora
UW-CSE
Method
S1
S3
S4
S5
AI
Graphics
Language
Systems
Theory
MCMC
0.43
0.63 0.24
0.46
0.56
0.19
0.04
0.03
0.15
0.08
BP / Lifted Liftef BP
0,44
0.62
0.24
0.45
0.57
0.21
0.04
0.01
0.14
0,05
MC-SAT
0.43 0.63
0.24
0.46
0.57
0.13
0.04
0.03
0.11
0.08
HL-MRF
0.60 0.78 0.52 0.70 0.81
0.26
0.18
0.06
0.27
0.19
of these predicates that do not appear in the knowledge base are considered false. Note that only the query predicates remain open- open-world in this setting.
For sanity checking, we also conduct these experiments with a closed-workd setting. We found the close those reported in the original works. This shows that
results summarized in Table we have fair setup (including memory size, hyperparameters, etc.) for those competitor methods. Additionally, one can find that the AUC-PR scores compared those (Table 1) under open-world setting are actually better. This is due to the way the datasets were originally collected and evaluated generally complies with the monsed-world assumption. But this is very unlikely to be true for real- world and large-scale knowledge base such as Freebase and WordNet, where many true facts between entities are not observed. Therefore, in general, the open-world setting is much more reasonable, which we follow throughout this paper.
16

---

Published as a conference paper at ICLR 2020
D LOGIC FORMULAE
We list some examples of logic formulae used in four benchmark datasets Table 7. The full list of logic formulae is available in our source code repository. Note that these formulae are necessarily as clean as being always true, but are typically true.
For UW-CSE and Cora, we the logic formulae provided in the original dataset. UW-CSE provides 94 hand-coded logic formulae, and Cora provides 46 hand-coded rules. For Kinship. we hand-code 22 first-order logic formulae. For F555--337, we first use Neural LP (Yang et al., 2017) on the full data to generate candidate rules. Then we select the ones that have confidence scores higher than 90% of the highest scored formulae sharing the same target predicate. We also de-duplicate redundant rules that can be reduced to other rules by switching the logic variables. Finally, we have generated 509 logic formulae for FB 15K-237.
Table 7: Examples logic formulae used in four benchmark datasets.
Dataset
First-order Logic Formulae
Father (x, 2) Mother (2, 2) > Husband (X, Y)
Father (x, 7) A Fusband (X, = Mother (Y, 2)
Kinship
Husband (X, Y) = Wife (Y, X)
Son X) = Fat (X, Y) Mothhrr (X,
Daughter XX, X) = Father (X V Mother (X,
taught (c, P, A Aourseeevve (c, Tevel500) professor (p)
tempAdvi (p, 8) professor
UW-CSE
advisedBy (p, student
tempAdvisedBy (p, s) student (s)
professor (p) hasPosition Faculty) taughtBy P, g)
SameRib (b1 b2) A SameRib (b2, b3) = SameBl (b1, b3)
SameTille (t1, L2) SaaeTitlee (L2, L3) = SameTit (t1,
Cora
Author (bcl, al) A Author (bc2, A SameAuchor (al,a2) = SameBib (bel, bc2)
BasWordVemue (al, +w) A HasWordVennee (a2, +w) + SameVenue (al, a2)
Title (bcl,, Title (bc A (t1, 7 SameBib (bcl, bc2)
position (B, A position (C, B) position A)
ceremony (B, A ceremony (C, B) calegoryOf (C, participant C)
FB15K-237 film(B, A) fiim
storyBy (A, B) > particcipan: (A,
adjoins B) country (B, servicelocationn... (A,
17

---

Published as a conference paper at ICLR 2020
E PROOF OF THEOREM
First, re-state the definition and theorem in mathematical form:
Definition. [[somorphic Nodes] Two ordered sequences of nodes (cI,..., Cn and (c....,c,, isomorphic in a graph 9K if there exists an isomorphism from Gx (C, E) to itself, i... π CUO + CUO, such that π (c1) = 14.....7((4 = Cx Further, we use the following notation
(01, (eI,".,,,.)) - ....... (n)) (cI, (n) and (c ...
... ,c,) are isomorphic Gx.
Theorem. Consider knowledge base K = (C, R, O) and any E R. Two latent random variables X == r(c,..... Gn) and X' = r(c,..... Cn) have the same posterior distribution in any MLN and only if (c1,--- Cn) & (k....,,)))
Then we give the proof as follows.
Proof. A graph isomorphism from G to itself is called automorphism, so in this proof, will use the terminology automorphism to indicate such self-bijection.
We first prove the sufficient condition:
I automorphism π on the graph 9K such that (c;)) = c/. Vi 1, n,
then for any R, r(c,....,,.. and
<,,)) have the same posterior in any MLN.
MLN is graphical model that can also be represented by factor graph MLN = (OU H. Fy. where ground predicates (random variables) and ground formulae (potential) connected. We will show that 3 an automorphism e on MLN such that ø (r(ci,..., Gx)) = rc''....,, Cy). Then the sufficient condition is true. This automorphism & is easy construct using the automorphism on Gic. More precisely. we define é: (OU H.F.) + (OUH,F,)
)(r(a,)) = (()(),)), ((((a)) f(*(ay)),
for any predicate E R, any assignments to its arguments, any formula f E F. and any assignments a to its arguments. is easy to see & is an automorphism:
Since is a bijection, apparently also a bijection.
2. The above definition preserves the biding of the arguments. r(a,) and f(a,) are connected if and only if ((((a))) and (=(())) are connected.
3. Given the definition of π, know that r(a,) and r(T(a,)) have the same observation value. Therefore, in MLN, RodeType(r(a.)) = Node Typee
This completes the proof of the sufficient condition.
(-) To prove the necessary condition, it is equivalent to show the following assumption
(A 1): there is no automorphism π on the graph 9x such that π (c;)) = d,, = 1,..,
can imply:
there must exists a MLN and a predicate r such that r(c1,..- Ca) and r(d,.-... (,) have different posterior.
Before showing this, let us first introduce the factor graph representation of a single logic formula
f.
18

---

Published as a conference paper at ICLR 2020
A logic formula can be represented as a factor graph, Gf = (Cy. Rr), where nodes one side of the graph is the set of distinet constants C5 needed in the formula, while nodes the other side is the set of predicates R used to define the formula. The set of edges, E,, will connect constants to predicates or predicate negation. That is, an edge
stantiated from C. An illustration of logic formula factor graph can be found in Fig. 8. Similar to the factor graph for the knowledge base, we also differentiate the type of edges by the position of the argument.
= (c,r,)) between node and predicate ex- ists, if the predicate r use constant in its i-th argu- ment.
Z
We note that the set of distinctive constants used in the definition of logic formula are templates where actual constant can be in-
Figure 8: An example of the factor graph for the logic formula -Husband (X, Y) V -Mtther (Y, 2) Daughter (2,
Therefore, every single formula can be represented by factor graph. We will construct factor graph representation to define particular formula, and show that the MLN induced by this formula will result different posteriors for r(ci,..., (x)) and r(ci,.... c.)) The factor graph for the formula is constructed in the following way (see Fig. 7 as an example of the resulting formula constructed using the following steps):
(i) Given the above assumption (A 1), we claim that:
3 subgraph G (C2, O E S Gx such that all subgraphs Ge,.. (c,, S 9K satisfy:
(Condition) if there exists an isomorphism @ 9 Get satisfying ((c) 4, Vi 1,...,7 after the observation values are IGNORED (that is, (...) =] and (-. ) = 1] are treated as the SAME type of nodes), then the set fact nodes (observations) in these two graphs are different (that is, O o Og).
The proof of this claim is given at the end of this proof.
(ii) Next, we use Gi.... to define a formula f. We first initialize the definition the formula value as
fei,..., CT Ea,...,,,, ,,,) = (A (f(a;) F(a+) E 9 }) + r(ci,..., (10)
Then, we change F(aç) in this formula to the negation -F(a;) if the observed value of F(a,) is in G
We have defined formula f using the above two steps. Suppose the MLN only contains this formula f. Then
the two nodes
and r(c), (ch....,,,)) (h) in this MIN must be distinguishable.
The reason is, in MLN, r(ci,...,c, Cx) is connected ground formula [(1, ... Cn. .I..... kn). whose factor graph representation is G Ur(cI..... C.). In this formula, all variables observed in the knowledge base XC except for r(ci...., Ca) and and the observation set is O The formula value is
f(i.,... .i...., 2,) = (1 + r(c.....,
(11)
Clarification: Eq. 10 is used to define formula and c; in this equation be replaced by other con- stants, while Eq. 11 represents a ground formula whose arguments are exactly CI...., Cny čj... cn. Based (Condition), there is NO formula f(c ..i ch Cr..,,,.,, (,,) that contains r(q,..... (,) has
19

---

Published as a conference paper at ICLR 2020
observation set the same Og. Therefore, r(ci,..., Cn) and .c......, (2)) are distinguishable in this MLN.
Proof of claim:
We show the existence by constructing the subgraph g S GK in the following way:
(i) First, we initialize the subgraph as G GK. Given assumption (A 1) stated above, it is clear that
(S 1) A subgraph g' S Gx. there is no isomorphism x g - g' satisfying T())) =
dy Vi = 1, ,.. n.
(ii) Second, we need to check wether the following case occurs:
(C 1) 3 subgraph g' (C', (C',O', E') such that (1) there EXISTS an isomorphism ø 9 - G" satisfying Φ(c;) = c4, Vi = 1,..., n after the observation values are IGNORED (that is, [ry(-..) ) 0] and (ry(-.)) = are treated as the same type of nodes); and (2) the set of factor nodes (observations) in these two graphs are the same (that is, O O').
(iii) Third, need to modify the subgraph if the case (C 1) is observed. Since |9 1 | the only subgraph that will lead to the case (C1) is the maximal subgraph 9% 9 The isomorphism ø is defined by ignoring the observation values, while the isomorphism ı (S 1) is not ignoring them. Thus,
(S 1) and (C - a set of nodes S : = (a)) = 0] ,..., (r)(a))) = 0}} such that for any isomorphism satisfying the conditions in (C 1), the range d(S) contains at least one node (-) 1] which has observation value 1.
Otherwise, it is easy see contradiction to statement 1).
(M 1) Modify the subgraph by 9 9 \S. The nodes (and also their edges) in the set S = (1) 0) ,.--. [r (a) }}} are removed.
For the new subgraph 9 after the modification (M 1), the case 1C will not occur. Thus, we ve obtained subgraph that satisfies the conditions stated in the claim. Finally, we can remove the nodes that are not connected with (cI...., Cn. (that is, there is no path between this node and any one of The remaining graph is connected (cr...., Co) and still satisfies the conditions that need.
20


Reviews:
[{"review_id": "rkgx3TK2tr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper the authors propose a system, called ExpressGNN, that combines MLNs and GNNs. This system is able to perform inference and learning the weights of the logic formulas.\n\nThe proposed approach seems valid and really intriguing. Moreover the problems it tackles, i.e. inference and learning over big knowledge graphs, are of foremost importance and are interesting for a wide community of researchers.\nI have just one concern and it is about the experiments for the knowledge graph completion task. In fact, this task was performed only on one KG. I think the proposed system should be evaluated on more KGs.\n\nFor these reasons I think the paper, after an extension of the experimental results, should be accepted.\n\n[Minor]\nPage 3. “The equality holds” which equality are you talking about?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SkgLKByAtS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a framework for solving the probabilistic logic reasoning problem by integrating Markov neural networks and graph neural networks to combine their individual features into a more expressive and scalable framework. Graph neural networks are used for learning representations for Knowledge graphs and are quite scalable when it comes to probabilistic inference. But no prior rules can be incorporated and it requires significant amount of examples per target in order to converge. On the other hand, MLN are quite powerful for logical reasoning and dealing with noisy data but its inference process is computationally intensive and does not scale. Combining these two frameworks seem to result in a powerful framework which generalizes well to new knowledge graphs, does inference and is able to scale to large entities. \n\nRegarding its contribution, the paper seems to consider a training process which is done using the variational EM algorithm. The variational EM is used to optimize the ELBO term (motivation for this is the intractability of the computing the partition term). In the E-step, they infer the posterior distribution and in the M-step they learn the weights. The integration of variational EM algorithm and MLN has been explored in another work (pLogicNet: Probabilistic Logic Neural Networks for Reasoning), but this paper proposes a new pipeline of tools: MLN, GNN and variational EM which seem to outperform all the existing baseline methods.The paper looks technically sound to me and the evaluations results are delivered neatly, however the flow of the paper makes it a bit difficult to follow sometimes due to many topics covered in it.\nRegarding the significance of the paper, it tries to combine logic reasoning and probabilistic inference which is of great interest among the researchers recently. ExpressGNN proves to generalise well and perform accurate inference due to the tunable embeddings added at the GNN.\n\nOverall, the work of this paper seems technically sound but I don’t find the contributions particularly surprising or novel. Along with plogicnet, there have been many extensions and applications of Gnns, and I didn’t find that the paper expands this perspective in any surprising way. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HygnUyGAYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes to use graph neural networks (GNN) for inference in MLN. The main motivation seems to be that inference in traditional MLN is computationally inefficient. The paper is cryptic about precisely why this is the case. There is some allusion in the introduction as to grounding being exponential in the number of entities and the exponent being related to the number of variables in the clauses of the MLN but this should be more clearly stated (e.g., does inference being exponential in the number of entities hold for lifted BP?). In an effort to speed up inference, the authors propose to use GNN instead. Since GNN expressivity is limited, the authors propose to use entity specific embeddings to increase expressivity. The final ingredient is a mean-field approximation that helps break up the likelihood expression. Experiments are conducted on standard MLN benchmarks (UW-CSE, Kinship, Cora) and link prediction tasks. ExpressGNN achieves a 5-10X speedup compared to HL-MRF. On Cora HL-MRF seems to have run out of memory. On link prediction tasks, ExpressGNN seems to achieve better accuracy but this result is a bit difficult to appreciate since the ExpressGNN can't learn rules and the authors used NeuralLP to learn the rules followed by using ExpressGNN to learn parameters and inference.\n\nHere are the various reasons that prevent me from rating the paper favorably:\n\n- MLNs were proposed in 2006. Statistical relational learning is even older. This is not a paper where the related work section should be delegated to the appendix. The reader will want to know the state of inference and its computational complexity right at the very beginning. Otherwise, its very difficult to read the paper and appreciate the results.\n\n- Recently, a number of papers have been tried to quantify the expressive power of GNNs. MLN is fairly general, being able to incorporate any clause in first-order logic. Does the combination with GNN result in any loss of expressivity? This question deserves an answer. If so, then the speedup isn't free and ExpressGNN would be a special case of MLN, albeit with the advantage of fast inference.\n\n- Why doesn't the paper provide clear inference time complexities to help the reader appreciate the results? At the very least, the paper should provide clear time complexities for each of the baselines.\n\n- There are cheaper incarnations of MLN that the authors should compare against (or provide clear reasons as to why this is not needed). Please see BoostSRL (Khot, T.; Natarajan, S.; Kersting, K.; and Shavlik, J. 2011. Learning Markov logic networks via functional gradient boosting. In ICDM)", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is far more borderline than the review scores indicate. The authors certainly did themselves no favours by posting a response so close to the end of the discussion period, but there was sufficient time to consider the responses after this, and it is somewhat disappointing that the reviewers did not engage.

Reviewer 2 states that their only reason for not recommending acceptance is the lack of experiments on more than one KG. The authors point out they have experiments on more than one KG in the paper. From my reading, this is the case. I will consider R2 in favour of the paper in the absence of a response.

Reviewer 3 gives a fairly clear initial review which states the main reasons they do not recommend acceptance. While not an expert on the topic of GNNs, I have enough of a technical understanding to deem that the detailed response from the authors to each of the points does address these concerns. In the absence of a response from the reviewer, it is difficult to ascertain whether they would agree, but I will lean towards assuming they are satisfied.

Reviewer 1 gives a positive sounding review, with as main criticism "Overall, the work of this paper seems technically sound but I don’t find the contributions particularly surprising or novel. Along with plogicnet, there have been many extensions and applications of Gnns, and I didn’t find that the paper expands this perspective in any surprising way." This statement is simply re-asserted after the author response. I find this style of review entirely inappropriate and unfair: it is not a the role of a good scientific publication to "surprise". If it is technically sound, and in an area that the reviewer admits generates interest from reviewers, vague weasel words do not a reason for rejection make.

I recommend acceptance.
Decision: Accept (Poster)