An Efficient Mean-field Approach to High-Order Markov Logic
Authors: Weidi Xu
Jianshan He
Jingwei Wang
Hongting Zhou
Xiaopei Wan
Taifeng Wang
Ruopeng Li
Wei Chu
Venue: Submitted to ICLR 2023 (2023)
Keywords: Logic Rules
Mean-field Algorithm
Markov Logic Network
Symbolic Reasoning

Abstract: Markov logic networks (MLNs) are powerful models for symbolic reasoning, which combine probabilistic modeling with relational logic. Inference algorithms for MLNs often perform at the level of propositional logic or require building a first-order probabilistic graph, and the computational efficiency remains a challenge. The mean-field algorithm generalizes message passing for approximate inference in many intractable probabilistic graphical models, but in MLNs it still suffers from the high-order dependencies among the massive groundings, resulting in time complexity exponential in both the length and the arity of logic rules. We propose a novel method, LogicMP, to simplify the logic message passing especially. In most practical cases, it can reduce the complexity significantly to polynomial for the formulae in conjunctive normal form (CNF). We exploit the property of CNF logic rules to sidestep the expectation computation of high-order dependency, and then formulate the logic message passing by Einstein summation to facilitate parallel computation, which can be optimized by sequentially contracting the rule arguments. With LogicMP, we achieve evident improvements on several reasoning benchmark datasets in both performance and efficiency over competitor methods. Specifically, the AUC-PR of the UW-CSE and Cora datasets is improved by more than 11\% absolutely and the speed is about ten times faster.


Under review as a conference paper at ICLR 2023
AN EFFICIENT MEAN-FIELD APPROACH TO HIGH- ORDER MARKOV LOGIC
Anonymous authors Paper under double-blind review
ABSTRACT
Markov logic networks (MLNs) powerful models for symbolic reasoning. which combine probabilistic modeling with relational logic. Inference algorithms for MLNs often perform the level of propositional logic require building first-order probabilistic graph, and the computational efficiency remains a chal- lenge. The mean-field algorithm generalizes message passing for approximate inference in many intractable probabilistic graphical models, but in MLNs it still suffers from the high-order dependencies among the massive groundings, result- ing in time complexity exponential in both the length and the arity of logic rules. We propose a novel method, LogicMP, to simplify the logic message passing es- pecially. In most practical cases, it can reduce the complexity significantly polynomial for the formulae conjunctive normal form (CNF). We exploit the property of CNF logic rules to sidestep the expectation computation of high-order dependency, and then formulate the logic message passing by Einstein summation to facilitate parallel computation, which be optimized by sequentially con- tracting the rule arguments. With LogicMP, we achieve evident improvements several reasoning benchmark datasets in both performance and efficiency over competitor methods. Specifically, the AUC-PR of the UW-CSE and Cora datasets is improved by more than 1 % absolutely and the speed is about ten times faster.
INTRODUCTION
Despite the remarkable improvement in deep learning, the ability of symbolic learning believed to be indispensable for the development of modern AI (Besold et al. 2021). The entities in the real world are interconnected with each other through various relationships, forming massive rela- tional data, which leads to many logic-based models (Koller et al.) 2007). Markov logic networks (MLNs) (Richardson and Domingos 2006) are among the most well-known methods for symbolic reasoning in relational data, which take advantage of the relational logic and probabilistic graphical models. They use the logic rules to define the potential function of Markov random field (MRF) and thus soundly handle the uncertainty for the reasoning on various real-world tasks (Zhang al.
2014 Poon and Domingos 2007 Singla and Domingos 2006b Qu and Tang 2019).
Typical methods perform inference in MLNs the level of propositional logic via standard prob- abilistic inference methods, such as Gibbs sampling (MCMC) (Gilks et al. 1995 Richardson and Domingos) (0066, slice sampling (MC-SAT) (Poon and Domingos 2006). belief propaga- tion (Yedidia et 2000). However, the propositional probabilistic graph is extremely complicated as it typically generates all ground formulae as factors and the number is exponential in the arity of formulae. The methods need to manipulate these factors during the inference stage, leading to an exponential complexity. Besides, several lifted algorithms that treat the whole sets of indistin- guishable objects identically were proposed, such as first-order variable elimination (de Salvo Braz) ctt al., 2005), lifted BP (Singla and Domingos) 2008), lifted MCMC (Nieperi) 2012)). However, these lifted methods typically become infeasible when the symmetric structure breaks down, e.g., unique evidence is integrated for each variable. ExpressGNN (Zhang et al., 2020) uses a particular graph neural network as the posterior model in the variational EM training to amortize the problem of joint inference. However, its training complexity is still exponential in the length and arity of formulae. Overall, algorithm design for efficient MI.N inference remains challenge.

---

Under review as a conference paper at ICLR 2023
Grounding Message
LogcMP
Bud we M
AVA
Mi Meggose U
Milzcn Frali Updkttt of MEN
Hil Al
Man nov Lagie Networ
B
Ost
RA
Duans Oel
(00)
AMPO
Figure 1: Left: A Markov logic network (MLN) with two entities (A, B), predicates F (Friend) and S (Smoke) and с (Cancer), and formulae fi (a. b) == -(()) V -F(a, V S(b), fz(a) := (-S(a) V C(a)) (a()) V -C(a)). The circles are the ground atoms where the shaded ones are latent and the blocks like fr (A, B) denote the ground formulae. Right: We expand the MLN inference into several mean-field iterations and each iteration is implemented by a LogicMP layer. The calculation of the message w.r.t. a single grounding is illustrated in the "grounding message" block with dashed lines: the message from S(A) and F(A, B) w.r.t. fi B) can be simplified as Q (1)QF(A. (A. (1), We then formulate parallel aggregation on the right via the Einstein summation (Einsum). Specifically, the marginals of ground atoms are grouped by the predicates as the basic units of computation (the gray border denotes the marginals with -). In each iteration, LogicMP takes them as input and performs Einsum for each logic rule (shown in the middle block). Intuitively, Einsum counts the groundings that derive the hypothesis for each implication statement of the logic rules (cf. Sec. 4 The outputs of Einsum are then used to update the grouped marginals. Such procedure loops for T steps until convergence. Note that f2 is in conjunctive normal form and its two clauses can be treated separately. The Einsum is also applicable for the predicates with more than two arguments.
To mitigate the inference problem of MLNs, we adopt the mean-field (MF) algorithm (Wainwright and Jordan 2008 Koller and Friedman 2009) to reason over the relational data approximately. The MF algorithm updates the marginals of variables by calculating the expected potential over other related variables. Although the iteration of the MF algorithm can be formulated as modern neu- ral networks for several special conditional random fields (CRFs) (Zheng et al.] 2015 Vemulapalli et al. 2016). its standard implementation of MLN is still inefficient due to expectation calculation over high-order related variables and massive groundings, resulting in a computational complexity exponential in the length and the arity of formulae, respectively. We show that the MF iteration in MLN can be efficiently formulated as a special neural network LogieMP, which propagates the mes- sages for the logic rules especially. In most practical cases, for the logic rules in conjunctive normal form (CNF), can remove both exponents to effectively reduce the complexity to polynomial.
Fig. T ggives an overview of our approach with an example. For given MI. (left), the MF algorithm unfolds the MLN inference into several iterations of the forward computation (right). Specifically, LogicMP tackles the two essential problems of the standard update from two perspectives. First, we show that in the MF update the expectation calculation over the high-order related variables of the logic rules can be removed owing to the property of CNF logic rules, and only one remaining state needs to consider which forms an implication path from the related variables (as the premise) to the updated variable (as the hypothesis). The block with the dashed line across both sides in Fig. illustrates how to compute a message w.r.t. single ground formula. Second, based on this finding, we further show that the computation and aggregation of massive groundings can be efficiently im- plemented by the Einstein summation (Einsum). It can not only aggregate the grounding messages in parallel but also indicate a way for complexity reduction. The Einsum operation can be optimized in general when the arguments are contracted sequentially. For instance, the MF iteration of chain rules can be implemented in cubic polynomial complexity regardless of the exponential amount of groundings in the arity of formulae. The experimental results on the benchmark datasets prove the effectiveness and efficiency of LogicMP, boosting the average AUC-PR by 1 11% absolutely against many competitive methods with much faster training speed (about 10x) on the UW-CSE (Richard- son and Domingos] (006) and Cora (Singla and Domingos 2005) datasets. Our reproducible source code is attached in the supplementary file and will be released publicly.
2

---

Under review as a conference paper at ICLR 2023
In summary, our main contributions include: (1) We propose that the MF inference for MLNs can be practically conducted at polynomial complexity for the CNF formulae in most cases, regardless of exponential propositional groundings in the formula arity. (2) We unify the formation of logic mes- sage passing for CNF via Einsum to enable parallel computation, and design a neural network layer, LogicMP, for MF iterations. (3) We verify LogicMP on four benchmark datasets of symbolic rea- soning with considerable improvements in accuracy and efficiency. (4) Our released code supports multi-class scenarios that may benefit broad range of applications with logical knowledge.
2 RELATED WORK
Markoy logic networks. The research community in statistical relation learning (SRL) (Klller
al., )2007) combined the logic rules with the probabilistic models, giving rise several meth-
ods (Neville and Jensen 2007 Kersting and Raedt 2008). MLNs (Richardson and Domingos,
2006) are among the most well-known methods proposed for SRL and have achieved remarkable results in various reasoning tasks (Poon and Domingos] 2007] Singla and Domingos 2006b Qu and Tang 2019). They use logic rules to model the distribution of relational data as an MRF to absorb the noise. Despite the effort in improving the efficiency (de Salvo Braz et al., 2005 (Singla and Domingos 2006a Poon and Domingos (0066] Khot et al.] 20Th] et al. 201 SSiinvasaan ict al.) 2019; Jha et al. 22010; Singla and Domingos 2008; Zhang et al. 2020 Venugopal et al. 2013 Sarkhel et al. 2016), the MLNs still struggle in efficient inference. Our method formulates
the approximate MLN inference into the MF iterations that the logical structured prediction can be directly achieved by multiple stacks of LogicMP layers.
Mean-field algorithm. The MF algorithm (Wainwright and Jordan 2008 Koller and Friedman 2009) is an approximate inference algorithm typically for the graphical models whose exact infer- ence intractable. It can be efficiently implemented for a fully connected pairwise CRF (Zheng) iet al. 2015; Krähenbühl and Koltun 2013). Gaussian CRF (Vemulapalli et al., 2016) and linear- chain CRF (Wang et al. 2020). However, the MF algorithm still requires calculating the expected potential over the remaining related variables, which limits its application in MLNs where the graph structure is complicated due the massive high-order connections constructed by the logic rules. The idea of unfolding the inference procedure goes beyond the MF algorithm such as Transformer for Hopfield network (Ramsauer et al. (02T) and ReduNet (Chan et al. (02T), which also motivate us to transform the process of symbolic reasoning into multiple steps of forward computations.
3 MARKOV LOGIC NETWORKS
An MLN is built upon the knowledge base (C, R, O}, consisting of three components, i.e., a set C of constants, set R of predicates, and a set O of observed facts. Each predicate r is an indicator function r()) : C'... XC + {0, 1} to indicate whether the relation exists among the given constants.
With particular constants assigned to the predicate, we obtain the ground atom that is associated with a binary variable in probabilistic modeling. The MLN is defined over all such variables and a set of logic formulae F. Each formula f ís in the form of f(A) C x C + {0, 1] where A is its arguments. For instance, a formula in Fig. [ with A = {a. b) is ff b) == S(a) A b) - S(b)", which is equivalent to the disjunctive form SS((() V -F b) V S(b)" by De Morgan's 's law.
For each formula f. we can obtain a set of groundings Gy by assigning AA with various constants in C. With the specific assignments to the arguments, the formula becomes the ground formula, aka grounding. For a grounding g. we use Vy to denote the variables associated with the ground atoms in g. For instance, a grounding f(A, B) -S(A) V -F(A, B) V S(B) can be obtained by substituting the arguments (a, b) with constants (A, B). V = (Es(A), ()(A,B): US(B)) collects three involved variables. The ground formula can be seen as a function of v, parameterized by f.
With the knowledge base and formulae, MLN can be generalized as follows:
p(v O) x exp( Σ (v:)) + Σ W Σ (v(r)))
(1)
FEF gEG,
where v is the collection of latent variables, (.(+) is the independent unary potential of each ground atom which can be parameterized by other models, Wy E R denotes a weight for the formula f. d (-) is the potential function defined by f which simply takes the value of ground formula.
3

---

Under review as a conference paper at ICLR 2023
3.1 MEAN-FIELD UPDATE FOR MLNs
This paper focuses on the inference problem of MLN with the fixed MLN structure. Note that we consider all unobserved facts as the latent variables infer under the open-word assumption. Since p(v is generally intractable, we use the MF algorithm for approximate posterior marginal infer- ence. Specifically, the MF algorithm computes variational distribution Q(v) that best approaches p(v () where Q(v) II; Q+(1)) is a product of independent marginal distributions over each latent variables. The algorithm minimizes the KI. divergence DEL (Q(v))lll
Ed(())) log Qi(e;) - Σ Su (v.)))
E wy E5 [Q()) log Z.
FEF gEG, Vo
sEg
Note that minimizing DRL (Q(V) is equivalent to maximizing the evidence lower bound of log p(O). By considering PKL (Qv))ly)l)()))) as a function of (1:),, Wainwright and Jordan 2008 shows that the optimal Qi can be derived in closed-form as follows and the MF inference performs this update on each marginal Q until convergence (ef. Appendix Ap:
(v(+;) = 7; exp(du(vs) +
Σ wy Σ Qu:((:)); FEF
(2)
gEG,(1)
where Z, is the partition function, G)( the groundings of formula / that involve ground atom i,
(in((:))= = Σ O5(u, Vg .) II Q5(1,)
(3)
jEg
is the grounding message of a single grounding g, and g-i denotes the ground atoms in the grounding g except i. For instance, 9 (BS(B) = (((A),F(A, (A,B) B)) removes SBB) from the variables in [AA, B).
3.2 TIME COMPLEXITY ANALYSIS
To analyze the time complexity of an iteration by Eq. 2 we denote N as the number of constants in C, M maxy |A'| as the maximum arity of formulae, and L max, [fl as the maximum length (number of atoms) of formulae. For a single formula -S(a) V -F b) S(b). M 2 and L
Expectation calculation of grounding message. The grounding message Qi.g represents the influence to the variable generated by the variables g-i w.r.t. the grounding The computation of grounding message Eq. 3 needs to multiply Ilie. Q,(,;) (which (()) for all possible values of Vg-. (which is O )), resulting in complexity of (112--1).
Aggregation of massive groundings. Since the number of groundings |Gyl is ((N*) and grounding generates grounding messages for all the involved latent variables, we have ONN L) grounding messages. As the complexity of computing a grounding message is (LL2--1), the total time complexity of an MF iteration in Eq. 2 O(N 2 1224-1), 1), which is exponential in M and L.
4 EFFICIENT MEAN-FIELD ITERATION VIA LOGICMP
In the following, show that the exponent L in the complexity be removed by considering the property of the formulae in conjunctive normal form (CNF), and the exponent M can also be reduced in general by optimizing the message aggregation via Einstein summation. In particular, the overall complexity can be reduced to O
3 1,2) for arbitrary chain rules.
4.1 LESS COMPUTATION PER GROUNDING MESSAGE
We first show the complexity of computing grounding message (i.g())) in Eq. can be reduced from O(L2--1) (LL) by simplifying the message calculation for the clauses, and then generalize it to the formuluee... The clauses are the basic formulae that can be expressed as the disjunction of literals (cf. Appendix B for more details). For convenience, we explicitly write the clause as f-; n') where nh is the preceding negation of atom in the clause f (f will be removed when the context is clean). For instance, -S(a) V -((a, b) VS(b) is clause and its n is (1, 1, 0) for (S(a), (S(a),F(a,))) S(b))
4

---

Under review as a conference paper at ICLR 2023
The following lemma states that in caleulating Qig((:) of Eq. 3 with the clauses, some particular values Vg., in Σv,., can be neglected. Conceptually, a clause has several equivalent implication statements and grounding message can be seen implication from the premise of g- to the hypothesis of i. When the particular value g-. makes the premise false, it can be neglected.
Lemma 4.1. (No message of clause for the false premise.) When each formula f(;:)) is clause, for a particular state V of grounding 9 E Gy(i) that 3j E g-i, 1z = mi the MF iteration of Eq. is equivalent for Qi.g(v)) = Ev $5(15, Vg (ijes.-9((9)
See proof in the Appendix C This lemma leads to the following theorem (cf. proof in Appendix Di:
Theorem 4.2. (Message of clause considers true premise only.) When each formula f(:
clause, the MF iteration of Eq. 2 is equivalent for Qu.((v)) = 10,=0n, I Qz(c n2)).
Consequently, the grounding message can be simplified, e.g. Q (1) = QS(A) (1)Q
Compared to F the exponential summation of Vg-; is removed and the complexity of grounding message is reduced from O(L2-11) O(L) for the clauses. The theorem has simple but important meaning: only when the premise is true, does the logic rule matter for the hypothesis. In fact, Φ can be more sophisticated long as the potentials make difference for 2/ only for the true premise. The CNF formulae are the conjunction of clauses, such /2 in Fig. 1 We show that the simplification can be generalized to CNF formulae as well for the (T.) complexity as follows.
Theorem 4.3. (Message of CNF = =Σ message of clause.) When each formula f is the conjunc- tion of several distinct clauses fe(:;n), the MF iteration of Eq. 2 equivalent for (v:)( =
En, 10 11,eg (2 = n,z).
See Appendix for proof. From the theorem, we can see that the messages of several clauses can be computed separately and the message of CNF is equivalent to the summation of messages of its clauses with the same weight. Therefore, in Fig. I we can compute the message of CNF formula f2 as two separate messages of its clauses. In the following, we only consider the clause formulae because the generalization to CNF straightforward. In addition, we generalize the theorem for the formulae with multi-class predicates to benefit other tasks with logical knowledge (cf. Appendix
4.2 PARALLEL AGGREGATION USING EINSTEIN SUMMATION
This subsection provides an efficient formulation for the parallel message aggregation, i.e., summa- tion of Gy in Eq. 2 reduce the exponent M. Naturally, we can generate all the propositional groundings in Gy to perform the aggregation. However, the possible groundings can be massive, i.., M(N When M is large, the graph may be very dense and such aggregation is infeasible in both space and time. Therefore, we propose method to compute the messages via the Einstein summation (Einsum) which can not only aggregate grounding messages in parallel but also reduce complexity significantly for most practical formulae.
The virtue lies in the summation of the product, i.e., EgEa, I Qsly, = nz) by Theo-
The theorem shows that the grounding message to a variable i w.r.t. clause is the probability of the premise of g-; being true. Note that a clause corresponds to several different implication statements and implication statement corresponds to a kind of premise format in Theorem 4.2 The groundings in (i) w.r.t variable may belong to different implication state- ments and therefore have different kinds of premise formats. Therefore, we group the grounding messages by the implications they belong to. The middle block of Fig. [givess a detailed depiction of the mechanism, where 3 clauses generate implication statements and each first-order implica- tion statement is transformed into an Einsum operation for parallel message computation. Let us consider the implication statement S(a) A F(a, b) + S(b). When b is assigned as B, the groundings of the implication statement is (S(a) A F(a, B) + S(B))a We can aggregate the grounding mes- Note that the computation is also the same for various assignments of b and Σ. Qs(a) (1)QF(a)))() can be expressed via Einsum as einsum(" a, ab 6", (1),,, Qr()), where (v,), denote the collection of marginals of predi- cate r, i.c., (v,,) = (Qr(A.)(r (Cr(A))) where A, is the argument of r. Einsum also allows the computation for other complex formulae whose predicates have many arguments.
rem 4.2
sages of these groundings for S(B) by Σ. Qs(a) (1)QP(a.B)
5

---

Under review as a conference paper at ICLR 2023
Formally, now explicitly use [f, to denote the implication statement of clause with i-th atom being the hypothesis for the convenience of aggregating the grounding messages in the same premise format, and then give the update equation via Einsum.
Proposition. For the grounding messages w.r.t the implication statement [f. il of first-order clause {AA;; : to its i-th atom, their aggregation is equivalent to the Einstein expression:
(v.:)) Iv, einsum Al. Aese Af, "."","." ... Oryer (1i44))..))
(4)
where vi is the i-th predicate, Af, is the arguments of The MF iteration of Eq. 2 is equivalent
Qr Z
exp(#a(V.)) +
Σ
wy (V:
(5)
where (vv))) is the collection of unary potentials of predicate r.
Einsum can dramatically reduce the time complexity in some difficult situations. Let us consider a complicated chain rule with 4 arguments, I(a, A F(b, c) A G(c, d) + S(a, d) where F, are the predicates. The number of grounding messages is O(N*). By Einsum, we can reduce O(N))
to ((N3). Specifically, Q
einsum("ad) bc, ed - ad", Qr(1), (+(1), Q1(1)) in the ma- trix notation, which can be optimized into two matrix multiplications
((N3). First, Einsum computes Qr (1) Q=(1)) which is ( to integrate the paths through b. Then it performs multipli- cation with Qa (1) which is also O(N*)) to sum over c. Actually, the complexity is (NN) for any longer chain rules. In the practice,
opt_eint_e opt-einsum (Smith and Gray 2018 to automatically optimize Einsum for arbitrary formulae. Notice that such implementation gives a unified formation
of logic reasoning which covers the chain rules (Yang al. 2017 Sadeghian al. 2019) and the compositional rules (Yang and Song 2020).
The optimization of Einsum is achieved by search algorithm and the final complexity depends the format of the formula and the order of arguments in the contraction. We show several Einsum cases and their optimal simplifications in Appendix G In most cases, the complexity after the opti- mization is independent of M and more improvement can be achieved for a more complex formula.
4.3 COMPLETING THE ITERATION
Algorithm MF update for MLN via LogicMP.
We complete our MF update algorithm in Al- gorithm [ The algorithm implements the MF update by T LogicMP layers. takes the set of grouped unary potentials (P.(v,))rr formu- lae (f( and their rule weights {w } input and outputs the updated marginals (v,)), for all the predicates. First, an ini- tial distribution of each latent variable com- puted using the unary potentials via a normal- ization operation, i.e., the softmax layer. Sec- ond, we enumerate all the formulae and their implication statements to perform Einsum via Eq. ([fl is the length of f). Third, we com- bine the unary potentials and the outputs of Einsum to obtain new estimation of marginals.
Input: Grouped unary potential (Pa(vr)): formulae (f(A: and their rulc weights (wy J the number LogicMP layers T.
of
Q-(v.) + z,- (xp((x.(vv))) for all predicates r. for f1, for f f do for i E (1, Ifl) do
b Layers
> Formulac Implications
Obtain Q (v,)) by Eq.
b Finsum
end for end for Update (v.) by Eq. for all predicates r. end for return ( (v,)),.
5 EXPERIMENTS
5.1 EXPERIMENTAL SETTINGS
Benchmark datasets. We verify LogicMP on the Smoke dataset (Badreddine et al. 2022) and three symbolic reasoning benchmark datasets. The Kinship (Zhang et al. | 20200 dataset asks the questions in a relationship graph among the people. The social network dataset UW-CSE (Richardson and Domingos 2006) contains information about students and professors in the CSE department of UW.

---

Under review as a conference paper at ICLR 2023
The entity resolution dataset Cora (Siglla and Domingos 2005
consists of collection of citations between academic papers. All datasets contain the specific formulae and all the formulae are in CNF. The details of datasets and general experimental settings are given in Appendix H
Evaluation metrics. Following previous works (Richardson and Domingos 2006 Singla and
Domingos 2005), use the area under the precision-recal curve (AUC-PR) to evaluate the model performance. To evaluate the efficiency, we use the wall-clock time in minutes.
Compared algorithms. Our model is compared with several strong methods in the MLN litera- ture, including MCMC (Gilks et al. 1995; Richardson and Domingos (2006), belief propagation (BP) (Yedidia et al., 2000). lifted belief propagation (Lifted BP) (Singla la and Domingos 2008), MC- SAT (Poon and Domingos 2006). hinge-loss Markov random field (HL-MRF) (Bach et al. 2017
Srinivasan et al. 2019) and variational EM (ExpressGNN) (Zhang et al. 2020
Method details. In general, LogicMP performs MLN inference and can incorporate logic rules in various learning settings. Ideally, can serve as a logic CRF for arbitrary neural networks and be trained end-to-end via maximum likelihood estimation (MLE) as in CRFasRNN (Zheng et al.) 2013). However, as the labeled data is rare in our datasets, MLE is prone to overfitting and we turn to semi-supervised learning where rules act priors to infer the latent variables.
To leverage the power of representation learning, LogicMP integrates with a light-weigh neural predictor via the posterior regularization (Ganchev et al. 2010; Hu et al.) 2016 Guo et al. 2018 to distill the inference results from LogicMP into the neural predictor in an iterative way. Specifically, the neural predictor is built upon the constants which are represented by a list of embedding vectors. Each predicate is modeled by a unique bi-linear layer which takes the concatenated constant vectors as input. LogieMP takes the output of the neural predictor ou and performs symbolic reasoning to obtain estimated marginals. They in turn become the prediction targets in training the neural predictor. The detail of the method is attached in Appendix ||
We fix the formula weights W of and set the number of LogicMP layers T to 5 (cf. Sec. 5.3) for Sec.5.3)
all the experiments. Each experiment is performed times and the average score is reported. As in ExpressGNN, we sample batches of groundings for the stochastic training (cf. Appendix D]. Thanks to our acceleration techniques, we can perform large-scale training efficiently with a sampling size of 1024, i.c., batch size = 1024. Note that LogicMP can perform full graph computation efficiently, but the practical results indicate that training with sampling is more stable for the learning of logical knowledge for the neural predictor. We leave full graph training to future work. Note that Express- GNN also uses a special graph neural network to learn the logical knowledge, which approximately corresponds to the neural predictor in our approach. Different from their claim, show the use of complex GNN is unnecessary in the large-scale training (cf. the model capacity in Appendix K)
5.2
MAIN RESULTS
Smoke & Kinship. The Smoke dataset is an example dataset to validate the usefulness of the proposed method and Fig. shows that the correct results can be predicted. Table I demonstrates the AUC-PR results on the Kinship dataset, which synthetic and noise-free with an increasing number of entities from S1 to S5. The compared methods are performed under the open-world setup, where unobserved facts are seen as latent variables (cf. Append L.. denotes that the method fails to complete the training as it is either out of memory only manages to obtain the result on the smallest split. HL-MRF can achieve perfect accuracy in S1-S4 but it is invalid in the largest split. Our method can obtain nearly perfect results in all the splits, consistently outperforming all other competitors. These results demonstrate that our method is effective in precise reasoning.
exceeds 24 hours. MCMC
UW-CSE & Cora. Table Table@]shows the results of the UW-CSE dataset which is collected in a real- world scenario with considerable noise. In UW-CSE, the closed-world setup is used for the com- pared methods except for ExpressGNN as they are invalid under the open-world setup. Due to the noise in the dataset and the scarcity of observed facts, the results are much lower than those in Kin- ship and the competitor methods can hardly achieve an average AUC-PR of 20%. Even though. our method further improves the performance by an absolute margin of 11% 1% against HI-MRR. Table ? also shows the results of the Cora dataset, which is larger than the UW-CSE dataset. We can see
TTis is not the Cora dataset Sen et al. 2008 typically for the graph node classification.
7

---

Under review as a conference paper at ICLR 2023
Table 1: AUC-PR on Kinship. Best results are in bold. The bracket denotes the standard deviation.
Kinship
Method
Viensla.5 in umioo'
riendee Group
S2
MCMC
.53
BP/Lifted
.33
.58
MC-SAT
.54
.60
.55
.55
1.0
ExpressGNN
.97
.97
.99
.99
.99
Cancer
(001)
(.00)
(.01)
(001)
(.00)
Figure 2: Facts (top) and predictions (bottom) Smoke for true/false facts).
LogicMP
.99
.98
1,0
1,0
1.0
(.00)
(.00)
(.00)
(.00)
(000
Table The AUC-PR on the UW-CSE and Cora datasets. The best results in bold. The bracket denotes the standard deviation for which we rerun ExpressGNN 5 times. "A., G., L., S., T." are abbreviations for "AI, Graphies, Language, Systems, Theory".
UW-CSE
Cora
Method
A.
G.
L.
S.
T.
81
S2
S3
$4
S5
MCMC
.19
.04
.03
.15
.10
.43
.63
.24
.46
.56
.46
BP/Lifted BP
.21
.04
.01
.14
.05
.09
.44
.62
.24
.45
.57
.46
IIL-MRF
.26
.18
.06
.27
.19
.19
.60
.78
.52
.70
.81
.88
ExpressGNN
(02)
(.02)
(.03)
(.02)
(.02)
(02)
(.02)
(01)
(,02)
(.03)
(002)
(0.2)
LogicMP
.25
.30
.42
.25
.80
.88
.82
(.02)
(.04)
(.03)
(002)
(.05)
(003
(001)
(01)
(.01)
(.01)
(00)
(.01)
batchsize=16
-26
.28
.58
.64
(03)
(04))
(.06)
(.02)
(.06)
(004)
(01)
(01)
(.0))
(01)
(01)
(.01)
mlayers=1
.30
.38
.23
.80
.88
.71
.82
(.04)
(.03)
(.02)
(.04)
(.01)
(.01)
(.01)
(.01)
(.01)
that in the Cora dataset our method can also achieve better results against all the competitors and the improvements in the 5 splits are consistent. The performance in UW-CSE and Cora demonstrates the effectiveness of LogicMP in incorporating logic formulae in real-world tasks. We also visualize the test curves w.r.t. the training steps in Fig. 3 to demonstrate the robustness of our approach.
Ingi-e A2C
Figure 3: Test curves w.r.t. the training steps.
5.3 EFFECT OF MULTIPLE LOGICMP LAYERS
We show detailed ablation results with one LogicMP layer for the UW-CSE and Cora datasets in Table 2 and the ablation with various layers for all the splits of three datasets Fig. The ex- perimental results show that the performance improves consistently when using multiple LogicMP layers. And the performance keeps stable when we further stack the layers. This is reasonable as MF algorithm typically converges to stable state within several steps. With more adequate inter- action, the variables can gather more information from the logic formulae to make better reasoning, which also leads to better performance. Fortunately, LogicMP takes few steps (typically within 5) to achieve good performance and we can empirically set T to 5.
5.4 TRAINING EFFICIENCY
Table 2 shows the scalability capacity. From the ablation experiment against a small grounding batch size of 16, we can that the performance improves considerably. The efficient implementa-
8

---

rather short time Under review as a conference paper at ICLR 2023
1825
399
3.20
(375
(350
0.00
022
6.70
0.20
#Layard
#Layar22
4
-4
54
25
p00fccs
argage
Exterm
06
53
30
54
Figure 4: AUC-PR w.r.t the number of LogicMP layers.
Orfonel ne Undere Legonp
130
0.20
Logbne--on 24124
Lnck wew.-a--aatteeee. m3
2002
3.5
140
709
250
151
100
199
200
76
130
254
1826
Figure 5: Left two: AUC-PR in minutes. Right: #Groundings/scconn w.r.t. batch size in Kinship.
tion of LogicMP is essential for large-scale training. We show the test AUC-PR curves of LogicMP and ExpressGNN w.r.t. training time on the left two of Fig. on Al and Language cases of the UW-CSE dataset respectively. The learning method of EXpressGNN is computationally inefficient since it calculates ELBO with the expectation computation over posterior probabilities (which can be accelerated by the simplification in Sec. 4.1 and the groundings are computed separately. From figure, we can see that the scores of ExpressGNN increase slowly and using more groundings in batches is ineffective, because the training speed consistently decreases for larger batch sizes without parallel implementation. In contrast, LogicMP can complete training with quickly increasing scores. When doubling the groundings, we obtain better results at faster speed. These results reveal the efficiency of LogicMP. For a detailed comparison of training efficiency, ablate the grounding velocity of various implementations in the Kinship dataset the right of Fig. [5] The original MF update denotes that the implementation without the technique in Sec. [4.1 or Einsum. For LogicMP w/o Einsum, we perform scattering and gathering to aggre- gate the propositional groundings (cf. Appendix MM. We also used LogicMP to perform full graph computation which demonstrated in the "nosampling" group. From the figure, we can see the MF update can outperform ExpressGNN remarkably and the two proposed techniques effectively accelerate the training speed, achieving 10x training velocity than ExpressGNN (cf. Appendix N). When the sampling strategy is disabled, Finsum can calculate all the grounding messages in parallel and achieve superior efficiency.
CONCLUSION
We presented novel neural network layer, LogicMP, to implement efficient MF update for MLNs. The efficiency improvement mainly comes from two non-trivial discoveries. We first showed that the grounding message of CNF is the summation of grounding messages of clauses that only need to consider the true premises, thus eliminating the exponent of the formulae length from computational complexity. Then, we showed that the aggregation of grounding messages can be transformed into Einstein summation for parallel computation, and Finsum itself can be optimized to reduce the exponent of the formulae arity in the complexity for most formulae in practice. Both contribute to the LogicMP layer that can perform MLN inference with polynomial complexity in general.
Note that LogicMP neglects the existential quantifier in the first-order logic. A plausible solution is to transform the formula into the Skolem norm form to eliminate the existential variables. is also necessary to investigate the property of LogicMP both empirically and theoretically when serving as a logic CRF in the end-to-end training of some data-rich tasks. In the large knowledge bases, further reduction of cubic polynomial complexity is also worth exploring. We leave them to future work.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Stephen H. Bach, Matthias Broecheler, Bert Huang, and Lise Getoor. Hinge-loss Markov random fields and probabilistic soft logic. The Journal of Machine Learning Research, 18:109:1-109:67, 2017. URL/tttp://3ml www.:/.rggppppppp...ee v1//111/1111 8/15--11111 631 html
Samy Badreddine, Artur d' Avila Garcez, Luciano Serafini, and Michael Spranger. Logic tensor networks. Artificial Intelligence, 303:103649, 2022. doi:
URL
wtt.......1...1 wtw.:iiin..n........ 103649.
Tarek R. Besold, Artur d' Avila Garcez, Sebastian Bader, Howard Bowman, Pedro Domingos, Pas- cal Hitzler, Kai-Uwe Kühnberger, Luís C. Lamb, Priscila Machado Vieira Lima, Leo de Penning, Gadi Pinkas, Hoifung Poon, and Gerson Zaverucha. Neural-symbolic learning and reasoning: A survey and interpretation. In Pascal Hitzler and Md. Kamruzzaman Sarker, editors, Neuro- Symbolic Artificial Intelligence: The State of the Art, volume 342 of Frontiers Artificial In- telligence and Applications, pages 1-51. IOS Press, 2021. doi: 10.3233/FA1A210348 URI. https: / wogg/rrgg..... /233/FAAA2103330
Kwan Ho Ryan Chan, Yaodong Yu, Chong You. Haozhi Qi, John Wright, and Yi Ma. Redunet: A white-box deep network from the principle of maximizing rate reduction. CoRR, abs/2105.
2021. URL htt.ttttt://aaxttt org abs / 20000 10446
Rodrigo de Salvo Braz, Eyal Amir, and Dan Roth. Lifted first-order probabilistic inference. In Leslie Pack Kaelbling and Alessandro Saffiotti, editors, IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30 Au- gust 5, 2005, pages 1319 1325, Professional Book Center, 2005. URL http::ttpp/eeeeee orrg/ Proceedings 05 Pwwers
pdf
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In 7th International Conference Learning Represeniations, ICLR 2019, New Or- leans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. Eorum? id BIxy hRctX
Kuzman Ganchev, João Graça, Jennifer Gillenwater, and Ben Taskar. Posterior regularization for structured latent variable models. The Journal of Machine Learning Research, 11 11:2001-2049, 2010. UtLppttp://porttaa www.aacm...ro...o //c/caaaiiioooooooooo act.oor//ccaatiinnonn cfm? wwf.ffid=188999
Walter R Gilks, Sylvia Richardson, and David Spiegelhalter. Markov chain Monte Carlo in practice. CRC press, 1995.
Shu Guo, Quan Wang. Lihong Wang, Bin Wang, and Li Guo. Knowledge graph embedding with iterative guidance from soft rules. In Sheila A. Mcllraith and Kilian Q. Weinberger, editors, Pro- ceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium Ed- ucational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, Febru- ary 2-7, 2018, pages 4816 (826-48833440 AAAI Press, 2018. URL https: www aaai www.aai...........aaeeeeeaeeeeee index. phpp whtpphppp//aaaaaappp http:///taaaa/////////aaaaaaaaet http//vee/////// /ww.w//6669999
Zhiting Hu, Xuezhe Ma, Zhengzhong Liu, Eduard H. Hovy, and Eric P. Xing. Harnessing deep neural networks with logic rules. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume 1: Long Papers. The Association for Computer Linguistics, 2016. doi: 10.18653/v1/p1-111 1228. URL https://dot wttp://....1./////1//
Abhay Kumar Jha, Vibhav Gogate, Alexandra Meliou, and Dan Suciu. Lifted inference seen from the other side The tractable features. John D. Lafferty, Christopher K. I. Williams, John Shawe-Taylor, Richard S. Zemel, and Aron Culotta, editors, Advances in Neural Information Pro- cessing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of meeting held 6-9 December 2010, Vancouver, British Columbia, Canada, pages 973-981. Curran Associates, Inc., 2010. URL
mew.eeeededdnngn..n.e.s.e cc/ co/
.tmll
10

---

Under review as a conference paper at ICLR 2023
Hang Jiang, Sairam Gurajada, Qiuhao Lu, Sumit Neelam, Lucian Popa, Prithviraj Sen, Yunyao Li, and Alexander G. Gray. LNN-EL: A neuro- syuuo-yymbolic approach to short-text entity linking. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli, editors, Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the Ith International Joint Conference on Natural Language Processing, ACI/IJCNLP 2021, (Volume I: Long Pa- pers), Virtual Event, August 1-6, 2021, pages 775-787, Association for Computational Linguis- http://///oooo///..////..1
tics, 2021, doi: 10.18653/v 102/33//1/222111 acl-long.64, 64. URL 2021 acl- 1all-long long........ 64
Zhengyao Jiang and Shan Luo. Neural logic reinforcement learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Ma- chine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 3110-3119. PMLR, 2019. URL http: //proceedings mll press //////////n//// 9a. html
Kristian Kersting and Lue De Raedt. Basic principles of learning Bayesian logic programs. In Probabilistic Inductive Logic Programming Theory and Applications, volume 4911 of Lecture Notes in Computer Science, pages 189-221. Springer, 2008. doi: 10.10077978- 0-1-778---54--7855522-
_7. URL https: / //o:://dooi..o org/ 10-000797----50 786522-8872777
Tushar Khot, Sriraam Natarajan, Kristian Kersting, and Jude W. Shavlik. Learning Markov logic networks via functional gradient boosting. In / 1th IEEE International Conference on Data Min- ing, Vancouver, BC, Canada, December 11-14, 2011, pages 320-329. IEEE Computer Society, 2011. doi: 10.1 10911100 L.87. URL /ttp:///////..oo000101111/////// ICDOM ICD.. 2011.8 87
Daphne Koller and Nir Friedman. Probabilisticc Graphical Models Principles and Techniques. MIT Press, 2009. ISBN 978-0-262-01319-2. URL http: httt:://mitpppi http:://mmitpressssee mmi.tedd//ataloo /teemddffalt... wtt.::/ttty---22i.--1111...
Daphne Koller, Nir Friedman, Saão Džeroski, Charles Sutton, Andrew McCallum, Avi Pfeffer, Pieter Abbeel, Ming-Fai Wong, Chris Meek, Jennifer Neville, et al. Introduction Statistical Relational Learning. MIT press, 2007.
Philipp Krähenbühl and Vladlen Koltun. Parameter learning and convergent inference for dense random fields. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, volume 28 of JMLR Workshop and Conference Pro- ceedings, pages 513-521. JMLR.org, 2013. URL http:://proceediggs... .rr.s.sss/
w28/kraehembuehh .tml
Tao Li and Vivek Srikumar. Augmenting neural networks with first-order logic. In Anna Korho- nen, David R. Traum, and Lluís Mårquez, editors, Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Papers, pages 292-302, Association for Computational Linguisties, 2019. doi: 10.18653/v1/p19-1000 1028.
Giuseppe Marra and Ondrej Kuzelka. Neural Markov logic networks. In Cassio P. de Campos, Marloes H. Maathuis, and Erik Quaeghebeur, editors, Proceedings of the Seiitt-Seventh Confer- ence on Uncertainty in Artificial Intelligence, UAI 2021, Virtual Event, 27-30 July 2021, volume 161 of Proceedings of Machine Learning Research, pages 908-917. AUAI Press, 2021. URL www...pres///oe http:/vv11mmmaaa w1t.em1mmmaaaaii html
Jennifer Neville and David D. Jensen. Relational dependency networks. The Journal of Machine Learming Research, 8:653-692 2007. URL http:://tlllt.//// attp:///a...acc.o.o...c.ccaaataa www.iionnnc.....ommmmm.m........ ff
1314522
Mathias Niepert. Lifted probabilistic inference: An MCMC perspective. In Henry A. Kautz, Kris- tian Kersting, Sriraam Natarajan, and David Poole, editors, 2nd International Workshop Sta- fistical Relational Al (StaRAi-12), held at the Uncertainty in Artificial Intelligence Conference (UAI 2012), Catalina Island, CA, USA, August 18, 2012, 2012. URL htthttts: ptttsp::/sstrai... kuleuven. Seannnbe/2ie wwtpb////t//etttpttpptttpptttttt /tt/b/////ccppteeeeeeee actppttd/ccpecccccccccccccccc niepert. pdf
Ali Payani and Faramarz Fekri. Inductive logic programming via differentiable deep neural logic networks. CORR, abs/1906. 19630035663,, 2019. URL http: wrg. hbsh//bs//199 03523

---

Under review as a conference paper at ICLR 2023
Hoifung Poon and Pedro M. Domingos. Sound and efficient inference with probabilistic and deterministic dependencies. In Proceedings, The Twenty-Fits First National Conference on Arti- ficial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Confer- ence, July 16-20, 2006, Boston, Massachusetts, USA, pages 458 0638-463.400 AAAI Press, 2006. URL http:/ www. aaai wttgg//ibbarr//aa////OOOO
0 063073. php
Hoifung Poon and Pedro M. Domingos. Joint inference in information extraction. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22-26, 2007, Vancouver, British Columbia, Canada, pages 913-918. AAAI Press, 2007. URL. http://tp/// www.waai. org/ Ligbary AAAI/2007 http:/2000aaaaa00000 aa1.//111.11111111
Meng Qu and Jian Tang. Probabilistic logic neural networks for reasoning. In Advances in Neu- ral Information Processing Systems 32, December 8-14, 2019, Vancouver, BC, Canada, pages 7710-7720, 2019, URL http:tts///oocceeiiinneee/////e newripss.. wwtppa/ee//119//aa.....
.htll
Hubert Ramsauer, Bernhard Schäfl, Johannes Lehner, Philipp Seidl, Michael Widrich, Lukas Gru- ber, Markus Holzleitner, Thomas Adler, David P. Kreil, Michael K. Kopp. Günter Klambauer, Jo- hannes Brandstetter, and Sepp Hochreiter. Hopfield networks is all you need. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. d= Sen.eaaannnniiit
OpenReview.net, 2021. URL.btts::/ U hwtp://ee//fooreeoeeeo
Jan Niclas Reimann, Andreas Schwung, and Steven X. Ding. Neural logic rule layers. Information Sciences, 596: 1996:185-0001 2022. doi: 10. (0.1016)..ns.2222.03..8
1016/3. ins. 2022. 03. 021
Matthew Richardson and Pedro M. Domingos. Markov logic networks. Machine Learning, 62(1-
2):107-136, 2006. doi: 10.1007/5109994406---88333 URL https:://cc...... aeeeiioogg/ll 1ttp//1..1000...00 s 610994-006-5833-
Ryan Riegel, Alexander G. Gray, Francois P. S. Luus, Naweed Khan, Ndivhuwo Makondo, Is- mail Yunus Akhalwaya, Haifeng Qian, Ronald Fagin, Francisco Barahona, Udit Sharma, Shajith Ikbal, Hima Karanam, Sumit Neclam, Ankita Likhyani. and Santosh K. Srivastava. Logical neural networks. CoRR, abs/2006. 13155, 2020. URL htttt: www.:/iii.rrrrooooooo wwwp/rrg////aeeeeeeeee.eeeeeeeee abt.a////2..... 13155
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. DRUM: end-to- end differentiable rule mining on knowledge graphs In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' 'Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Ad- vances in Neural Information Processing Systems 32: Annual Conference on Neural Informa- tion Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 15321-15331, 2019. URL pttppsss///oooodiigg www.innggnneeiiii neurips. watpecccppppppe cctpappr/2019/ hash/Oc wttph///ccccbbbeeeeeeeee 51 2el55112000a. wwt.000aee27222222 792d03 Abstract (tttraactttmll]
Somdeb Sarkhel, Deepak Venugopal, Tuan Anh Pham, Parag Singla, and Vibhay Gogate. Scal- able training of markov logic networks using approximate counting. In Dale Schuurmans and Michael P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelli- gence, February 12-17, 2016, Phoenix, Arizona, USA, pages 1067-1073. AAAI Press, 2016. URL ltttp://ww. aaai. org/ ocs/ wnwex.nddxx/////m
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. Al Mug., 29(3):93-106, 2008 doi: 10. 1609/amma. v2913.2157. URL httlh:tp////// //ds::///ooic org/oo..///oo.o..... 1ww.1669///00 wtw.:////ammm..2113..... 2157
Parag Singla and Pedro M. Domingos. Discriminatiee training of Markov logic networks. In The 20th National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9- 13, 2005, Pittsburrh. Pennsylvania, USA, pages 868- 873. AAAI Press/ / The MIT Press, 2005. URL http:/ www. aaai weraii.org/aae Laagg//iibarr/// /AAI/
2005/aaa 05 1255-131 17..37ppm. .php]
Parag Singla and Pedro M. Domingos. Memory-efficien inference in relational domains. In The Sreenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Ap- plications of Artificial Intelligence Conference, July 16-20, 2006, Boston, Massachusetls, USA,
12

---

Under review as a conference paper at ICLR 2023
pages 488 493, AAAI Press, 2006a. URL
2006/ /a/6//aaan aataaaaaii----7-00 078. php
Parag Singla and Pedro M. Domingos. Entity resolution with Markov logic. In Proceedings of the 6th IEEE International Conference on Data Mining 18-22 December 2006, Hong Kong, China, pages 572-582 IEEE Computer Society, 2006b. doi: 10.1109/CCM.22006655 URL
hittps://do. .rgg 10..109/TCMM..200
Parag Singla and Pedro M. Domingos. Lifted first-order belief propagation. In The Twenty-Thit AAA/ Conference Artificial Intelligence. Chicago, Illinois, USA, July 13-17, 2008, pages 1094-1099. AAAI Press, 2008. URL http:::/ww..aaa...rr//bbbbrre www.:aaa...rg/.bbbbaaa//////0/00
aaai 1eai08-17:3 10.1.p--73.php
Daniel G. Smith and Johnnie Gray. opt opt_einsum- A python package for optimizing contraction order for einsum-like expressions. J. Open Source Softw., 3(26):753, 2018. doi: 10.21 105/joss.
00753. URL httpthtts////do org/10 21000/211111111 21105/joss 00753
Sriram Srinivasan, Behrouz Babaki, Golnoosh Farnadi, and Lise Getoor. Lifted hinge-loss Markov random fields. In The Thirty-Third AAAI Conference on Artificial Intelligence, Honolulu, Hawaii, USA, January 27- February I, 2019, pages 7975-7983. AAAI Press, 2019. doi: 10. 10.1609/aaai. 133101.33017975. URLhttpss
doi org /10 1609/ aaai v33101.
Raviteja Vemulapalli, Oncel Tuzel, Ming-Yo Yu Liu, and Rama Chellappa. Gaussian conditional ran- dom field network for semantic segmentation. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, Las Vegas, NV, USA. June 27-30, 2016, pages 2223-3233. IEEE Computer Society, 2016. doi: 10. 10.1109/CVPR.2016.355 URL https: /to. 10 wttp://.0/0/...11/11100 1109/CVPR. 201 3.1
Deepak Venugopal, Somdeb Sarkhel, and Vibhav Gogate. Just count the satisfied groundings: Scal- able local-search and sampling based inference in mlns. In Blai Bonet and Sven Koenig, edi- tors, Proceedings of the Twenty-Ninhh AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA, pages 3606-361 -612. AAAI Press, 2015. URL wtw.hhttp:/// wwwww aaai. wwwp/indexx.ooo
AAAI /ttp////A/AAAAA/////////////////
Martin J. Wainwright and Michael I. Jordan. Graphical models, exponential families, and variational inference. Found. Trends Mach. Learn., 1(1-2):1-305, 2008.
doi: 10.1561/2200000001. URL
https://doot org.lorgglll 11....16112200 wtt..11111/22000000000000
Xinyu Wang, Yong Jiang, Nguyen Bach, Tao Wang, Zhongqiang Huang, Fei Huang, and Kewei Tu. AIN: fast and accurate sequence labeling with approximate inference network. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pages 2019-6026. Association for Computational Linguistics, 2020. doi: 18.13/3//v1/ 1220.emllp-main445 URL
emn emnlp-main..
485
Xinyu Wang, Yong Jiang, Zhaohui Yan, Zixia Jia, Nguyen Bach, Tao Wang. Zhongqiang Huang, Fei Huang, and Kewei Tu. Structural knowledge distillation: Tractably distilling informa- tion for structured predictor. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Lan- guage Processing, (Volume 1: Long Pupers), Virtual Event, August 1-6, 2021, 1, pages 550-564. Association for Computational Linguistics, 2021. doi: 10.18653/v1/002 acl-long.46. URL
https://doi: org/1000.g/00... 1......16533111100 acl- accp://iooo.......ooooooo.o..o 46
Patrick Henry Winston. Artificial intelligence. Addison- -Wesley Longman Publishing Co., Inc., 1984.
Yaqi Xie, Ziwei Xu, Kuldeep S. Meel, Mohan S. Kankanhalli, and Harold Soh. Embedding symbolic knowledge into deep networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buu,, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Pro- cessing Systems 2019, NeurIPS 2019, December 8- 8-14, 2019, Vancouver, BC, Canada, pages
13

---

Under review as a conference paper at ICLR 2023
4235-4245, 2019. httptt////rrrceedngs..uuu//// http:///eeeeoooooooooo....rrrrar 76661td0012771a177200001111----3
Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck. A semantic loss function for deep learning with symbolie knowledge. Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference Stockholmsmüsssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 5498-5507, PMLR, 2018. URL http://proceedings mml..
Machine Learning, ICMI. 2018,
press/v80 xul 8h. htmll
Fan Yang, Zhilin Yang, and William W. Cohen. Differentiable learning of logical rules for knowledge base reasoning. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Ad- vances in Neural Information Processing Systems 30: Annual Conference Neural In- formation Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 2319 2328, 2017. URL https::/ newriie.eppppp.. wwtpp//ppep//////aa..... (e5566aaa$$220833229333333038 Abst html
Yuan Yang and Le Song. Learn to explain efficiently via neural logic inductive learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. htttps://oppereeeeeee
net forum?id-
SJ 118CEYDB
Jonathan S. Yedidia, William T. Freeman, and Yair Weiss. Generalized belief propagation. In Advances in Neural Information Processing Systems 13, Denver, CO, USA, pages 689-695. MIT Press, 2000. URL htttps::/ppooced........ ngg neurips....... cctppaaper/2200/hsst/
6bb116886e2bc1133555577bbbb -bstr html
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.
Yuyu Zhang, Xinshi Chen, Yuan Yang, Arun Ramamurthy, Bo Li, Yuan Qi, and Le Song. Efficient probabilistic logic reasoning with graph neural networks. In 8th International Conference on Learning Representations, Addis Ababa, Ethiopia, April 26-30. 2020. OpenReview.net, 2020.
URL httphhs://pppeeeee////a// http://wwwwwee//orrteemmaa
net forum? saarummid=rJg77600 6kkStw
Shuai Zheng, Sadeep Jayasumana, Bernardino Romera-Paredes, Vibhav Vineet, Zhizhong Su, Da- long Du, Chang Huang, and Philip H. S. Torr. Conditional random fields as recurrent neural networks. In 2015 IEEE International Conference on Computer Vision, Santiago, Chile, Decem- ber 7-13, 2015, pages 1529-1537. IEEE Computer Society, 2015. doi: 10.1109/1CC22015.1179. URL Utt.ttpp:://0....///0000001//// 2015.
A MEAN-FIELD UPDATE EQUATION OF MLN
Proof. The conditional probability distribution of MLN in the inference problem defined as:
O(v(O) & expl Σ (are)) +
Σ SEF
w Σ (v(g)))
(6)
gEG,
p(v(O) is generally intractable since there is an exponential summation in the denominator. There- fore, we propose use proxy variational distribution Q(v) approximate the p(v[O) by mini- mizing the KL divergence (xz)v())llp(v over each variables, i.e., Q(v) II, (e(z)) where Ev,e(o.) Q((1.) 1, 1,Qx()) 0 is proper probability.
The proposed Q(v) an independent distribution
14

---

Under review as a conference paper at ICLR 2023
Table 3: The used symbols and the corresponding denotations.
Symbol
Definition
f
the formula
If]
the number of atoms in the formula
A
the arguments of formula the arity of formula the ground formula (grounding) the set of observed facts the set of unobserved facts the single variable associated with ground atom i the of groundings of formula the set of groundings of formula that contains i independent unary potential the collection of unary potentials the potential of formula f the weight of formula the of variables w.r.t. ground predicates in the grounding the set of negations ground predicates in the grounding the marginal variable i the grounding message of grounding to the variable i the set of ground predicates in the grounding except i the of variables in the grounding except i the collection of marginals of predicate the implication statement formula f to i-th atom the summation of grounding messages w.r.t. the implication [/. i]
9
H
G2
Gy(1)
4.
61
wf
Vg
ny
Q:
Q
9-1
Vs-c
Q-
[f.i]
Q!/-1
Note that minimizing the KL divergence w.rt. Q(v) is equivalent to maximizing the evidence lower bound of log pOO):
DRu(Q(v)ip(vIO) Eq(v) log Q(v)
p(v[O)
Eq(v) log Q(v) (Q(v)p(v(O)
(7)
Eq(v) log Q(v) EQ(v)p(v, 0) l()
-FFq(v)P(V, O) -EQ(v) log Q(v)) logr(O),
which is the negative ELBO plus the log marginal probability of O which is independent of Q.
Since @(v) = II; Qi(v;), we have:
Eq(v) log Q(v)= = ΣΣ
(i(1s) Qi(v:)
(8)
and
Eq(v) log ((v)(
Σ (v))
+Σ
Σw,, wy Σ E
II Q.(..) - log Z, (9)
6,0%
feF gEG, Vx
iEg
where independent of Q.
We can therefore rewrite D ( with these two equations as:
L = Σ (i(1z))og (v( Σ (x()))
Σ wi
Σ Σ gEG,
(5 Il
log Z. (10)
3,0%
fer
sEg
15

---

Under review as a conference paper at ICLR 2023
Considering it as function of Qi(e)) and remove the irrelevant terms, we have:
L, = logss Qi(4))
(1I)
+ (u(
Σ wf JEF
Σ
Σ
Solu Vo-.) II e,(1)),
gEG, (1) Fa_.
jEg-i
where g-j is the ground variables except i in the grounding g. Gy(i) is the groundings of formula that involve ground atom i,
By the Lagrange multiplication theorem with the constraint that Ev, Qi(us) 1, the problem becomes:
arg min
C = (i(ss) Qi(us)
(((+))
Σ (d)
+
Σ wy Σ
E0l(ei II (,(w;)
(12)
2x
SEF
gEGr Vo-s
jEg
+ A Σ (i(v:)
Take the derivative with respect to Qi(e:):
dCt 1 log Qi(u:) (o,(;) + Σ wy Σ
Osler vo..) II (,(0,) +X. (13)
dQ.(m;)
fEF 9EG, Va
JEg-2
Let the gradient be equal to O, we then have:
Q1(v;) = cxp( +
Σ wy
dol(tts (5(1)) -1 1-1), (14)
JEF
gEG,( Yo-s
jEg-c
Take out from the equation, we have:
Qi(vs) = 1 Z
1 exp((n(v))
Σ Wy Σ Er va-.) II (,(6))
(15)
FEF (EG,(()
jEg
where Z₁ is the partition function.
For clarity of presentation, we define the message of single grounding (grounding message) as:
Qi(ws) = Z exp(du(u:) + Σ ws Σ (v:()))))
SEF
9EG,())
(16)
Qig(v:) Σ
(1 Vg-.) II Q7(1;).
Va-s
1E9-1
Then we have the conclusion.
B TERMINOLOGY
Clause. In logic, a clause a formula formed from a finite disjunction of literals (atomic formulac their negations). A clause is true whenever at least one of the literals that form it is true. Clauses are usually written as (4 V l2...,, where the symbols I; are literals.
Conjunctive Normal Form (CNF). A formula is in conjunctive normal form if the formula is the conjunction of several clauses. The form usually in (4,1 V 4.2...) A (12,1 V V222... A... where the symbols 4 literals..
16

---

Under review as a conference paper at ICLR 2023
First-order Logic. First-order logic uses quantified variables over set of constants and allows the use of sentences that contain variables, so that rather than propositions such as "Tom a father, hence Tom is man", can have expressions in the form "for all person I, if x: is father then & is a man", where "for all" is a quantifier, while x is a variable. In general, the clause and CNF used for propositional logic. In this work, they denote the first-order clause and first-order CNR with universal quantifiers respectively.
Ground Expression. In mathematical logic, ground term of formal system is term that does contain any variables. Similarly, a ground formula is a formula that does not contain any variables. In this paper, we consider universal quantifiers, and grounding formula denotes an assignment of constants to the arguments in the formula with universal quantifiers.
C PROOF OF LEMMA: No MESSAGE OF CLAUSE FOR FALSE PREMISE
Proof. Let consider grounding g" in (i) and grounding message from أا, to i and there is a particular state v that 3j E 9-1; D3 = -Ry:
exp(E,(U;)) Q((x)) En, (x;()
(v(1)) 006 vo n) II 2)(2g) + Ar()),
JEGL.
(17)
A.(e)) oo(()) + Σ
V II 25(1))
VoL AV
jEaL.
+ Σ uf Σ
Σ
Cr iin) II Q,(g)))
(a vo
jEa-
Since 3j E g- m the clause will always be true regardless of e. i.e., Vo: {0. (,,,, (v. vg "=- Therefore, dy ;nn) ;n)) IIEes, Qy(0)) is independent of U;:
=1.
E(((,) C. + AA()), C= wy II 21(1)) jEn
(18)
The two potentials of C can be eliminated in the normalization step. We can apply the same logic to all the grounding messages and obtain the conclusion: Qi(v:) 2, (xp( + Σ, w Ege Qig(1:)), where Qi: Evantty Hg(Ui, Vg_, II jeg_. 22(1))
D PROOF OF THEOREM: MESSAGE OF CLAUSE CONSIDERS TRUE PREMISE ONLY
Proof. By the lemma 4.1 only one remaining state needs be considered, i.e., Uy = nj. g-i- And the potential ④y(-) is iff vs = -M otherwise Qig(1:) & O. Then we de- rive the conclusion: Qi(+:) = z, (xp( + E, wy Egec, (v:), where @ig(v:) =
bn Ibeg., Q = m!)
17

---

Under review as a conference paper at ICLR 2023
E PROOF OF THEOREM: MESSAGE OF CNF = Σ MESSAGE OF CLAUSE
Proof. For convenience, let us consider grounding g" in Gy(1) where f CNF is the conjunction of several distinct clauses f+);
(xp(F.(1;;))
Qi(0e) Σn, exp(E,(u:) (E(())))
E((0;) = E Collus.Va II Q,(1))+
(19)
VaL
jEg2.
A.(0;) du(u)) +
ΣEer w
Σ
Σ 1o v-)) II Qy(1,))
DEC,(0))" Vo-i
jen'.
Let v be (nf") bess i.e., the corresponding true premises of clauses. We have:
E,(U,) = Eds(es vk
II (,(0))+
S V II ()(1))+((m)) (20) E
JEV 9"
5E92,
where the second term can be directly eliminated as in the proof of Lemma cases that g is unique or not for various k.
4.1 We consider two
Case
v 9-;
is unique: Since v 9_; unique, then (5(4), v
u. and we can
get the message by the same logic in Theorem 4.2 i.c. mf Ilse Q,(0, n
Case 2 g is not unique: Let vk: 92. and g.. be the same where k and hi are two clauses in f. Since the clauses are unique, n, [h must be different with n The two potentials will eliminated, which is equivalent the summation of distinct messages, i.e. Ex mf= Iljgr, Q5(Uş = n n
.
We can apply this logic for every possible groundings and obtain: Qi(1:) 2. exp((a((=)) + E, wy E E9E Qu) where Qia((:) Σx 1 1 Ili Q5(u; nft), i.c.
Σn 1,, mn 1T. (5(2g n2))
This theorem directly leads the following corollary:
Corollary E.1. For the MIN, the mean-field update w.r.f. CNF formula equivalent the mean- field update w.t.. multiple clause formulae with the same rule weight.
F EXTENSION OF MULTI-CLASS PREDICATES
A typical Markov logic network is defined over binary variables where the corresponding fact can be either true false. This is unusual in the modeling of common tasks, where the exclusive categories form single multi-class classification. For instance, a typical MLN will use several distinct binary predicates describe the category of paper. However, the categories are typically exclusive, and combining them can ease model learning. Therefore, we extend the LogicMP model to the multi- class predicates.
Formally, let the predicates be multi-class classifications r(.) C..... x C 1,. with 2 2 categories, which is different with standard MLN. The atom in the formula is then equipped with another configuration Z for the valid value of predicates. For instance, multi-class formula about "RL paper cites RL paper" can be expressed as "P(x) E {1} V C(x.y) E (1} - P(y) E {1]" (P(x) = means æ is RL paper, C(æ, y) 1 means z cites y). Sometimes the predicates in the formula appears more than one time, e.g.. P(x) e (2) P(x) E (1)... We should aggregate them into single literal P(x) E 2, 2 (1,2) A clause with multi-class predicates is then formulated
18

---

Under review as a conference paper at ICLR 2023
(e, V ... where e is the variable associated with the atom in the clause and 2, denotes the possible values the predicate can take. In such notation, we rewrite the clauses with multi-class predicates f(: 2 where 2 = {Z,);- We show that the message of the multi-class clause can be derived by the following theorem.
Theorem F.1. When each formula with multi-class predicates f(: Zf) a clause, the MF iteration of Eq. is equivalent for Qi(e;) = lv,ez, Ileeg ((- (1--2.,e Mn,ez, Qı(y)))
As the derivation is similar that of binary predicates, omit the detailed proof here. By setting 2 = {-na}} } in the binary case, we can see that the message with multi-class predicates hecomes the one with binary predicates. Similarly, when the formula is the CNF, the message be calculated by aggregating the messages of clauses as in Theorem 4.3
G THE EINSTEIN SUMMATION
The Einstein summation is the notation for the summation of the product of elements in a list of high-dimensional tensors. We found the aggregation of grounding messages w.r.t. an implication statement can be exactly represented by Einstein summation expression. And the Einstein sum- mation can be efficiently implemented in parallel via NumPy and nowadays deep learning frame- works, c.g., Py PyTorch and TensorFlow. The corresponding function is called einsum which can be We list several cases of message aggregation in
effectively optimized via a library opt e nnsumm f Einstein summation format and their optimal simplifications via dynamic argument contraction.
Formula: R. (h, k) (a(k.)) () A () Rx(x)
Original: K < einsum kj. x" Qa, (1), Qa, (1), (1)(1)
Optimized:
K einsum ('kj.ji ki", Qn, Q1y(1)
K einsum(" ki Qs. (1), K)
Formula: R. (h, A (a A Rs(j. i) A (h) + Ba(i)
Original: K einsum("Iaa "lk, kj. ji, Qa. (1), Qz. (1), Q1) (1))
Optimized:
K cinsum ("nsuum""jjji ki", Qa (1), (1))
K einsum (hk, +1",, Qz. (1), Qu (1)
Formula: R. (p, 1) Re A k. Ra k) (1 1) (o(2,
Original: K einsum(" pi, y U.. ijkl, rk, al pqrs" Qn (1), Qa, (1), Qu (1), Qa, Q((1))
Optimized:
K < einsum ('pi, ijkl + pjkt", Qa (1), Qa, (1))
K <- einsum ("gj. pjkl > pgkl", Qu (1),
K einsum (aresumm"r;a""""" p"rk,pykl pgrl" Qu (1),
K einsum(" ("sl, pgrl pqrs", " Qa, K)
We also show several cases that cannot be optimized:
Formula: (a(a) A Ba(a, b) (b)
. K + einsum(" ab 6", Qa. (1), (1))
Formula: R, A
d) d) Ro
K - einsum("nheddd be, ed, ad - ac", Qa. (1), Qa. (s,, (1))
hhtpss//eennn "mttps//en..wwiipeeiiii http://www....iiiia.ooo///iiinin notatono
19

---

Under review as a conference paper at ICLR 2023
Formula: (a, A (2( AR(cc.) Ra(a, d) (a
einsumm"aaal (aabe, bed, cb, + ac", Qu (1), Qu (1), Q1) QI,))
One may notice that the current implementations of the Einsum function not available when the target matrix has external arguments that are not in the input matrices, i.e,, ab". We tackle this by a post-processing function for the output of Einsum.
H MORE EXPERIMENTAL SETTINGS
Prediction tasks. There several predicates in each dataset. In the Kinship dataset, the prediction task to answer the gender of the person in the query, e.g., male(c), which can be inferred from the relationship between the persons. For instance, person can be deduced as male by the fact that he is the father of someone and the formula expressing a father is male. In the UW-CSE dataset, we need infer AdvisedBy (a, b) when the facts about teachers and students are given. The dataset is split into five sets according to the home department of the entities. The Cora dataset contains the queries to de-duplicate entities, and one of the queries is SameTitle( b). The dataset is also split into five subsets according to the field of research.
Statistics. The details of the benchmark datasets are illustrated Table
Table 4: The details of the benchmark datasets.
#ground predicate
#ground formula
#entity
#relation
#query
Kinship/S1
62
15
187
38
50K
550K
Kinship/S2
110
158K
3M
Kinship/S3
160
15
482
102
333K
9M
Kinship/S4
221
15
723
150
635K
23M
Kinship/S5
266
885
183
920K
39M
UW-CSE/AT
300
UW-CSE/Graphies
195
22
449
4K
70K
64M
LnnCuug
82
182
1K
15K
9M
UW CSE//yystems
277
733
SK
95K
121M
UW CSF/hhrryyyr
174
22
465
2K
5IK
54M
Cora/S1 1
670
10
11K
2K
175K
621B
Cora/S2
431B
Cora/S3
607
18K
3K
156K
438B
Cora/54
600
12K
2K
160K
435B
ConvS5
600
11K
2K
140K
3398
Formulae of the datasets. We show several logic rules in the datasets in Table The blocks each of which contains 5 rule examples correspond the Smoke, Kinship, UW-CSE, and Cora datasets. The maximum length of Smoke and Kinship rules is 3, and 6 for the UW-CSE and Cora datasets. We can see from the table that all the logic formulae are CNF. Note that some formulae contain fixed constants such as "Post. Quals" and "Level_100 and we should not treat them as arguments.
General settings. The experiments were conducted on a basic machine with 16GB P100 GPU and an Intel E5-2688 v4 CPU at 2.50GHz with 32GB RAM. The model is trained with the Adam optimizer with a learning rate of 5e-4.
I INCORPORATING LOGIC RULES VIA SEMI-SUPERVISED LEARNING
LogicMP can be used as component to integrate logic rules in various learning settings. As the labeled data is much rare compared to the latent variables, the usage like CRFasRNN via end-to- end supervised learning is prone to overfitting for our tasks and hence we adopt a semi-supervised
technique, i.e., posterior regularization (Ganchev et al. 2010 10 Hu et al. 2016 Guo et al.) 2018), to incorporate the logical knowledge. uses the logic rules as the prior constraints to guide the model via distillation. Fig. o gives illustration of our approach. In the figure, LogicMP is stacked upon a neural predictor with parameters 9 to take advantage of both worlds (the symbolic ability of LogicMP and the semantic ability of the neural predictor). The neural predictor is responsible
20

---

Under review as a conference paper at ICLR 2023
Table 5: Several logic rules in the datasets. # denotes the number of predicates.
First Logic Formula
(anoke(a) (f (a, b) am)ke(()
-anoke(a) cancer(a)
anoke(a) V -cancer(s)
-friend(o.e)
driendjo,h) V (1
-fenale(a) V -child(y, x) (aother(s..)
-aale(x) </-hiiddgg.r V father(z.
-fenale(s) V -chidd(2,))) daughter(2.g))
-nala(2) V V--child( 20) aale(z) demalo(a)
taughtByle, -oorraaeeellleeeeeeeo..oooooo L50) -ta(c.s.g) advisedBy(s,p) temphdviaedBy(
publication(p..)) -ppbiicatiiiiii -etuddent()) student(y) V advieedByy( 3) teupAdvieedBy(a.
1o -taughtByle p. -talc, courseLavel(e, 110) (s
studant(z) V sddisedyy( tampAdvisedRR(is.))
publication(f..d hopplleeoeyyllllicciooooo.
eanePereon(a. b) advisedBy(a, b) advisedBy(0.
Muthor(bel, al] Author (622, o2) Iassordkathoridl, +w) -aadVordduthorfal, +w) Sabe3ib(bell l2))
Muthor(bel, al) -duthor (1c2, o2) Beeforddatthrrell +w) -EsaWordAuthor(c +w) Same bx))
-Title/bel,, VT-Ttiieii 12) -HaaVordTitlee(1 +w) -BBaoorrdT1c1e((2 +w) I SaneBib(bel be2)
-Title(bel, (1) (T1
tesWordTitlee(1 -w) y BBeeordfTicee12 +w) SaneBib(lel, (x2)
-Venue(bel, -Venue(bel) x2)
-HaawordVeeueeellll +w) -HaskordVenuee (e2 4-0) Some Bib(eel,b))
Joint Prediction (Q,,,),,
Inference by LogicMP
conditioned obsarvation
Distillation Loss
LogicMP Layers
Unary Prediction (1) (D, (v,)),
(EA,, B))
Neural Predictor 0
Predicate Bilinear Layer
Constant Embedding
Variables [y,),
Figure 6: The illustration of incorporating the logic rules into the models via posterior regularization. In this learning paradigm, LogicMP plays the role of logical inference layer for the neural predictor with parameters 0. Specifically, variables as input and output scores Q, as the unary potentials of variables. Then the unary potentials fed into the LogicMP layers to perform MF inference derive updated marginals Q. They in turn become the targets of unary prediction through the distillation loss. The dotted line means no gradients in the pack-propagation. The right bottom block gives the details of the neural predictor: for each variable of the ground atom, it converts the constants into a list of embedding vectors. The concatenation of the vectors fed into a bilinear layer obtain the unary potential.
are given set of variables v. The neural predictor takes the
for estimating the unary potentials of the variables independently. Then the LogicMP layers take these unary potentials to perform MF inference which derives more accurate prediction with the constraints of logic rules. The outputs of LogicMP layers then become the targets of the neural predictor through a distillation loss for better estimation. In this way, logical knowledge can be distilled into the neural predictor. Note that LogicMP in this process only performs inference without any learning. Intuitively, the neural predictor is responsible for point estimation, which LogieMP gives the joint estimation via symbolic reasoning. LogicMP helps to adjust the distribution of the neural predictor since the output LogicMP can not only match the original prediction but also fit the logic rules.
We show the derivation of such a learning paradigm from the posterior regularization as follows.
Specifically, the posterior regulariztion method derives another target distribution h(v) by minimiz- ing Dxr. r. (po with the prior constraints & from the logic rules. Ganchev et al. (2010)
shows that the optimal h(v) can be obtained in the closed form: h(v) po (v(O) exp(XΦ O)),
21

---

Under review as a conference paper at ICLR 2023
Table The comparison of AUC-PR with different Pg- The bracket denotes the standard deviation. "A., G., L.,, S., T." are abbreviations for "AI, Graphics, Language, Systems, Theory".
UW
avg.
55
avg.
0.0
.08
.13
.44
.06
.13
.17
.44
.25
.46
.57
.47
(.01)
(.04)
(.12)
(.0))
(.13)
(.06)
(.02)
(.01)
(01)
(01))
(.02)
(.01)
0.9
.25
.30
42
25
.28
.30
.80
.88
-72
83
.89
.22
(00)
(.04)
(003)
(02)
(.05)
(.03)
(001)
(.01)
(01)
(01)
(.00)
(.01)
where À is a hyper-parameter. When the constraint -)v,0)== wy Egec, ()((g) (Markov logic) and pe(v)O) exp(E; &u (1;; 0)) (neural predictor), we have h(v) ~ exp(E, ou( 0) + A EEE wy E ZgEc, (V₂)) which is equivalent to our first definition in Eq. We want to distill l(v) to (v(O..). However, since the target distribution is an MRF, direct distillation is difficult. Following the work (Wang et al. 202I). we calculate the marginal of target distribution for cach variables Qi(v;) via LogicMP and distill the knowledge by minimizing the distance between lo- cal marginals and unary predictions, i.., C = E, ((2 (v:), Po (v. (,))), where / is the loss function selected according to the specific applications. In practice, find the mean-square error of their logits works better for the tested datasets.
J SAMPLING STRATEGY
We sample mini- batches of ground formulae as in ExpressGNN Zhang al. (2020) in each optimization iteration, we sample a batch of ground formulae by randomly instantiating the arguments using entities C. To make the inference results more reliable each batch of training, the sampling is biased towards the facts with observations. Specifically, each grounding is sampled by gradually selecting the ground atoms. In selecting the ground atoms, we choose a ground atom in O with the probability Pg. Otherwise, random atom is grounded. This process is proposed in ExpressGNN and is proved to be effective in their results. This is reasonable since the estimation is very in-confident if all the ground atoms in the groundings are not observed, i.e., with rare evidence. In our approach, we also witness the effectiveness of the sampling approach and Pg is also set to 0.9. We have investigated the performance of Ps and list the results in Table 6 The results show that the sampling strategy is critical for performance. Nevertheless, the usage of the sampling strategy is rather a practical choice, considering the performance in UW-CSE/language is similar when Pg O.
Specifically,
K MODEL CAPACITY
In the compared methods, Zhang et al. (2020) also leverages a neural predictor, i.e., ExpressGNN, to learn the logical knowledge, similar to neural predictor. The original paper showed that the use of ExpressGNN can effectively improve performance in their setting. However, in our experiments, we found our lightweight model with solely list of embedding vectors is adequate and can achieve on-par results with a few parameters (embedding size = 128). Specifically, we showed the model parameter numbers Table Due to the varying number of constants, the number of parameters varies with different datasets. From the table, we can see that our model is more parameter-efficient than ExpressGNN. We have conducted experiments using ExpressGNN as the neural predictor and the results keep similar. Note that as the neural predictor can be implemented in parallel, various neural predictors make little difference the training speed. These results indicate that the use of the ExpressGNN model is unnecessary in our work and therefore we use the simple sahedding-bbsed model instead.
L COMPARISON BETWEEN CLOSED-WORLD AND OPEN-WORLD ASSUMPTION
Our work follows the open-world assumption where all the unobserved facts are seen as latent vari- ables. However, this assumption leads to severe scalability issues for many competitor methods. For
22

---

Under review as a conference paper at ICLR 2023
Table The number of parameters of our neural predictor and ExpressGNN. "A., G., L., S., T." abbreviations for "AI, Graphics, Language, Systems, Theory".
U'W-CSB
ExpressGNN
S98K 39K
591K 25K
584K 11K
596K
589K 23K
277K
223K
224K
223K
223K 77K
Ours
77K
78K
77K
FAU
POUOE
PAR
PAUS
PAUDA
SUN
SpV
FUR.A
SPU
sgg
SgR
PRLAL
SSA3
PRUS
POUM
CUN
DUN
QB
CRS
CRSI
Iteration
Iteration
Iteration
Figure 7: The illustration the mean-field update by formulating the grounding messages as a set of hyperreedgs in a graph. The computation can be achieved via scattering and gathering operations.
the UW-CSE and Cora datasets, the compared methods can hardly bear the computational complex- ity and fail derive valid results. Therefore, list the results under the closed-world assumption for these methods in the main paper, where unobserved facts (except the queries) are assumed to be false. We show that these methods typically perform better in the closed-world assumption illus- trated in Table Even though, our method outperforms these methods by a considerable margin.
Table AUC-PR of competitors under two assumptions on UW-CSE. Better results are in bold.
UW-CSE Langunge
Method
Assumption
Graphics
Systems
Theory
Open-world world
MCMC
Closed-world
0.19
0.04
0.03
0.08
Open-world
0.01
0.01
0.01
0.01
BPiLifeed BP
Closed-world
0.21
0.04
0.01
0.14
0,05
Open-world
0.03
0.05
0.06
0.02
0.02
MC-SAT
Closed-world
0.13
0.04
0.03
0.11
0.08
HL-MRF
Open-world
0.06
0.06
0.02
0.04
0.03
Closed-world
0.26
0.18
0.06
0.27
0.19
M IMPLEMENTATION WITHOUT EINSTEIN SUMMATION
Without Einsum, we generate all grounding messages to create graph with the hyper-edges. Fig. shows an example grounding messages. Since the number latent variables varies in different groundings, we manually append some dummy variables to the batch of latent variables of g-i- In the computation of the message, those dummy variables will be masked and replaced with the probabilities of 1 in the product of (1; n.j). Note that there is outer loop of formulae in Eq. and we eliminate this by assigning the rule index to each grounding message. The model can be efficiently implemented using scattering and gathering operations. The overall complexity of an iteration is (NN L2). Algorithm 2 illustrate the steps of iterations without Einsum where the messages aggregated by gathering all messages of (t).
23

---

Under review as a conference paper at ICLR 2023
Algorithm 2 The mean-field update w/o Einstein summation.
Qc(vs) z; exp(()(e:))) for i
Initialization
f {1..... T do
(v. t -u,--m Is Q,(y,= nz)
Grounding Message
(m)) + E, wy Egea,() (ia(x)
Aggregation
(e(e.) z, exp(ón(u:) + (v:))
Adding unary potential & Normalization
end for
N MORE COMPARISON OF TRAINING EFFICIENCY
Table Paaleelillttttee the training velocity of groundings in second as well as the total runtime in min- utes with a batch size of 1024. These results show that LogicMP achieves around 10x acceleration compared to ExpressGNN.
Table 9; The comparison of training efficiency and runtime.
Kinship/S1
UW CSEAI
Cora/SI
method
ExpressCiN
LogicMP
ExpressGiNN
LogicMP
ExpressUIN
LigicMP
growndings/sccond
225
2,844
1,229 276
runtime (minutes)
80
8
4,024
5,333
684
O LIMITATION OF THIS WORK
A grounding in this paper and some previous work in the literature means an assignment to the arguments in the formulae or predicates. This implies that are using the universal quantifier in the first-order logic. However, there is still an existential quantifier that is not considered.
The existential quantifier is more difficult than the universal quantifier. For a universal quantifier, any assignment leads to ground formula that needs to satisfy. In contrast, the existential quamtifier needs to consider multiple assignments jointly it only requires there exists one assignment that satisfies the formula. We leave the study of existential quantifiers to future work. Currently, we feel that there are two plausible ways to tackle the problem. The first way is to replace the existential quantifier by series of conjunctions, i.e., 3z, F(x) <> V,F(x;). However, in some difficult situa- tions, such replacement will construct an extremely complicated ground formula that is difficult to generalize. The second way is to transfer it to the Skolem norm form which eliminate the exis- tential quantifier by a map function that maps the existential variables to the universal variables. This is more promising module like special attention model. Since the tested benchmarks do not have any formulae with existential quantifiers, leave the extension and verification future work.
generalize the theorem the cxistential quantifier via another mapping
P ADDITIONAL RELATED WORK
Symbolic reasoning. The ability of symbolic reasoning is critical for intelligence (Winston 1984) and likely indispensable for nowadays Al research. popular branch of symbolic learning is
the logical specifications of neural networks (Dong et al. 2019 Reimann et al. 2022 Payani and
Fekri 2019; Marra and Kuzelka 2021 Yang and Song 2020) with constraints of logical knowl-
edge (Badreddine et al. 2022 Riegel et al. 2020). Another research focus is the logic-based learning
algorithms to enable the logical reasoning of common models (Hu et al. 2016 Xu et al. 2018 Guo et al. 2018; Xie et al., 2019). Besides. many methods were proposed to incorporate the symbolic reasoning into various tasks (Jiang and Luo 2019)) Li and Srikumar 2019 Jiang et al. 2021). Our LogicMP can be seen specification of the Markov logic network to perform logical inference.
24

---

Under review as a conference paper at ICLR 2023
friend(a, b)
value
smokc(a)
friend(a, s(a) and f(a,b)
smoke(a)
value
friend(A. A)
smoke(A)
friend(A, A)
0
smoke(A)
friend(A,
smoke(A)
friend(A, B)
smoke(B)
friend B, A)
smoke(B)
friend(B, A) 0
friend(B: (B, B)
smoke(B)
friend(B, B) 0
Figure 8: (1) The ground atoms of the predicate "smoke". (2) The ground atoms of the predicate "friend". (3) The formula of "smoke(a) and friend(a, b)".
Table 10: Comparison between the results between neural predictor with and without LogicMP.
UW-CSE
Cora
A.
G.
L.
S.
T.
avg.
S1
S2
S3
84
85
avg.
neural predictor
.01
.01
.01
01
.01
.01
.37
66
.21
.22
.55
.44
(.00)
(.00)
(.00)
(.00)
(.00)
((00)
(.03)
(.03)
(.01)
(.03)
(003
(.03)
neural predictor LogicMP
.25
-30
.42
.25
.80
.88
.72
.89
.82
(.02)
(.04)
(.03)
(002)
(.05)
(.03)
(001)
(.01)
(.01)
(001
(.00)
(.01)
Q CONNECTION BETWEEN EINSUM AND PDB
Einsum an efficient implementation of the summation of the product which can count the true groundings of conjunctive formulae. In the probabilistic database (PDB), the product can be achieved by the join operation and the summation can be seen as the aggregation operation. For example, for conjunctive formula "smoke(a) and friend(a,b)), we can create a table with two columns (æ1, Ø2) where smoke(a) (friend(a,
b)) corresponds to #1 (Z2). The value of each column is the ground atom and the goal is to find the groundings that make the formula true.
Fig. S8 (3) can be derived from (1) and (2). Note the "smoke(a) and friend(a, b)" is the premise of "smoke(a) and friend(a, b) smoke(b)". Our mean-field method "counts" the groundings of each conjunctive premise that evaluate to true so that it can be implemented efficiently via parallel Einsum operation. Note that "counts" is intuitive Q is continuous probability rather than discrete 0/1.
R ADDITIONAL RESULTS OF NEURAL PREDICTOR
We attach the results using the neural predictor only in Table 10 The experimental results show that the neural predictor only without LogicMP performs poorly in both the UW-CSE and Cora datasets. of logical knowledge, the neural predictor hardly learn useful patterns for the generalization in the tested queries. Note that since UW-CSE has no negative samples (i.e., false facts), we create negative samples for class balance by treating unobserved facts as false, and half samples in the batch are drawn from these negative samples.
As expected, without the explicit
25


Reviews:
[{"review_id": "pCSCvGsTu6", "reviewer": "Reviewer_cRow", "summary": "", "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": "", "summary_of_the_paper": "The paper proposes to improve inference in Markov Logic Networks through the use of deep models. In particular, Mean Field inference is implemented as layers which pass messages to compute summations more efficiently by exploiting logical structure in the MLN.\n\nThe time complexity analysis is performed to show that the exponential complexity of a Mean Field iteration is reduced for chain ruled formulas in the MLN. Further by parallelizing, we can achieve far salable computations of the messages in the MF iterations. Einstein summation is used to reduce complexity of enumerating all possible groundings of a first-order formula. It is shown that in some cases, even when the total number of groundings of the formula is large, the complexity of computing messages can be reduced by performing summations using Einsum. \n\nExperiments are performed with 3 datasets in the MLN literature. Comparisons are with existing MLN-based inference algorithms as well as ExpressGNN which is a GNN-based approach for MLN inference. Results indicate that the proposed approach is accurate and also scale well with increased number of groundings.\n", "summary_of_the_review": "The connection of Mean Field iterations and the deep model layers seems nice. Also, parallelizing the computations and demonstrating scalability is a nice contribution since inference in MLNs is known to be hard due to the large number of groundings. However, as I understand it, other approaches have tried to address the grounding problem in MLNs, so maybe the novelty is limited.", "strength_and_weaknesses": "Strengths\n-The use of Mean-Field inference for MLNs through deep model layers seems like a novel contribution to me.\n-The complexity analysis is performed rigorously and shows the scalability of the proposed method.\n-Experiments show that the proposed method scales well over large number of groundings while also being accurate\n\nWeakness\n-One weakness is that the problem of controlling the exponential grounding problem in MLNs has been explored in earlier work. For example, Venugopal et al. (AAAI 2015) model the same problem using a junction tree formulation and use approximate message passing to scale up the computations. In such cases, the complexity is dependent not on the number of groundings but the width of the tree-decomposition. For a chain formula, this width is small but for more densely connected formulas, this is large. Other similar approaches have also been explored. \nThus, I am not sure how the proposed method compares in terms of significance.\n\n-The experiment baselines particularly for CORA does not seem as strong. Another approach that implements MLNs through deep models (Graph Markov Neural Nets, Qu et al. ICML 2020) seems to show better performance. In general, I feel experiments on just two datasets (since smokers is more of a toy dataset) does not strongly demonstrate the significance of the proposed method.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "a0_LPhNQoE", "reviewer": "Reviewer_sKHS", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "The paper proposed using tensor operator, i.e. einsum, to perform mean field inference in MLN. Author demonstrated that each iteration of the MF message passing can be efficiently computed using a sequence of einsum operation. This not only enables one to perform approximate inference in MLN, the inference procedure can easily implemented as neural layers to perform neural-symbolic learning. In particular, author demonstrated that it achieves good results on relational prediction tasks when combining a neural predictor and a MLN regularizer. ", "summary_of_the_review": "In general, the paper delivers an interesting approach to perform inference in MLNs, and authors further demonstrated that the inference procedure can be integrated with a neural backbone to perform prediction tasks while leveraging the logical connections between the output.", "strength_and_weaknesses": "Strength:\n1. It is likely the first work that applies mean field on MLNs. The reduction of the mean field procedure using einsum makes the procedure easy to be implemented and accelerated. \n2. Author shows good result of using MLNs as a regularizer for learning a model in relational application, e.g. UW-CSE and Cora.\n\nCons:\n1. The notation introduced in the paper is a little bit dense, e.g. variables with many super scripts and lower scripts. It was challenging for the reviewer to go through the equations within few passes. One unsolicited suggestion is to remove some of the super script when the context is clear. E.g. In Theorem 4.3, the super script on the n might be known from the context and can be dropped. Alternatively, adding more examples on how each equation is computed might also help. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "OAduMIET49H", "reviewer": "Reviewer_gHdR", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "The paper proposes a new method for inference in MLNs.\n", "summary_of_the_review": "The paper is well written and the claims are supported by theoretical proofs.\n\nIt is not clear whether the structure of the MLNs are fixed or learned from scratch. In this case this should be explained in the paper.\nIn particular, while the part concerning the mean-field approach is very clear and correctly presented, there is a lack of description about the structure learning adopted in the paper. \n\nFurthermore, more datasets could be used in order to prove the validity of the approach.\n\nFinally, the paper is interesting but could be improved integrating some parts as reported above.\n", "strength_and_weaknesses": "+ Very interesting idea\n+ Well written paper\n- lack of experimental results\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8yRySJq0PAH", "reviewer": "Reviewer_qmoi", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper proposes an approximate inference algorithm for Markov Logic networks (MLNs) with disjunctive clauses.  The exponential grounding of the first-order structure is mitigated by leveraging a neural network architecture called LogicMP, which implements an efficient mean field approximation of the true posterior.\n", "summary_of_the_review": "The problem considered in this work is relevant, but I had an hard time reading the paper. I fully read the paper multiple times, but there are still important aspects of the proposed approach that I don't understand. I cannot reccomend the current version for publication.", "strength_and_weaknesses": "Pros:\n+ MLNs represent a very popular class of relational probabilistic models. \n+ Advances in MLN inference are valuable for a broad audience.\n\nCons:\n- In my opinion, the presentation of the proposed approach should be greatly improved before publication (details in the Clarity section).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject