LogicMP: A Neuro-symbolic Approach for Encoding First-order Logic Constraints
Authors: Weidi Xu
Jingwei Wang
Lele Xie
Jianshan He
Hongting Zhou
Taifeng Wang
Xiaopei Wan
Jingdong Chen
Chao Qu
Wei Chu
Venue: ICLR 2024 poster (2024)
Keywords: Variational Inference
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We present a novel and modular neural layer LogicMP, capable of encoding first-order logic constraints using fully parallel computation.

Abstract: Integrating first-order logic constraints (FOLCs) with neural networks is a crucial but challenging problem since it involves modeling intricate correlations to satisfy the constraints. This paper proposes a novel neural layer, LogicMP, which performs mean-field variational inference over a Markov Logic Network (MLN). It can be plugged into any off-the-shelf neural network to encode FOLCs while retaining modularity and efficiency. By exploiting the structure and symmetries in MLNs, we theoretically demonstrate that our well-designed, efficient mean-field iterations greatly mitigate the difficulty of MLN inference, reducing the inference from sequential calculation to a series of parallel tensor operations. Empirical results in three kinds of tasks over images, graphs, and text show that LogicMP outperforms advanced competitors in both performance and efficiency.

Published as a conference paper at ICLR 2024
LOGICMP: A NEURO-SYMBOLIN APPROACH FOR EN- CODING FIRST-ORDER LOGIC CONSTRAINTS
Weidi Xu Jiinwei Wang". Lele Xie", Jianshan He?, Hongting Zhou,, Taifeng Wang', Xiaopei Wan Jingdong Chen', Chao Qu', Wei Chu 2,1 INFLY TECH (Shanghai) Co., Ltd Ant Group BBoMap Research wdxuê udxu@inftech.at
ABSTRACT
Integrating first-order logic constraints (FOLCs) with neural networks is crucial but challenging problem since it involves modeling intricate correlations to satisfy the constraints. This paper proposes novel neural layer, LogicMP, which performs mean-field variational inference over Markov Logic Network (MLN). It can be plugged into any off-the-shelf neural network to encode FOLCs while retaining modularity and efficiency. By exploiting the structure and symmetries in MLNs, we theoretically demonstrate that our well-designed, efficient mean-field iterations greatly mitigate the difficulty of MLN inference, reducing the inference from sequential calculation to series parallel tensor operations. Empirical results three kinds of tasks over images, graphs, and text show that LogicMP outperforms advanced competitors in both performance and efficiency.
INTRODUCTION
The deep learning field has made remarkable progress in the last decade, owing to the creation of neural networks (NNs) (Goodfellow al., 2016) Vaswani et al. (017). They typically use feed-forward architecture, where interactions occur implicitly in the middle layers with the help of various neural mechanisms. However, these interactions do not explicitly impose logical constraints among prediction variables, resulting in predictions that often do not meet the structural requirements.
(a) Input Image
(b) Ground Truth
(c) LayoutLM
(d) SLrelax
(e) LogicMP
The document understanding task predicts whether every two tokens coexist in the same block in input document image (a). The FOLC regarding the transitivity of coexistence can be used to obtain the structured output. The ground truth (b) typically forms several squares for the segments. Both NN Xu al. 2020) (c) and advanced method (Xu et 2018) (d) struggle to meet the FOLC where many coexist variables are incorrectly predicted. In contrast, LogicMP (e) is effective while maintaining modularity and efficiency. See Sec. for complete experimental details.
Figure 1:
This paper investigates the problem of incorporating first-order logic constraints (FOLCs) into neural networks. An example of FOLCs can be found in the document understanding task (Jaume et al. 2019), which aims to segment the given tokens into blocks for document image (Fig. a)). We formalize the task into the binary coexistence prediction of token pairs C(a, b) E (0.T) where denotes the co-existence of tokens a, (Fig. (b)) There FOLC about the transitivity of coexistence predictions: when tokens and b coexist in the same block, and tokens b and cocxist in
"Corresponding author. Code is available https: stcpa://github...

---

Published as a conference paper at ICLR 2024
Σ
Raltas I 1e
Varinosnal APOPORETAEON of
JAMMUN
Pala Maan-Foold Ianalon
varistionl approsiration olyek
Figure 2: A high-level view of LogicMP. NNs typically use the softmax layer for independent prediction (left), which can be replaced by LogicMP encoding FOLCs (middle). LogicMP is implemented (right) by efficient mean-field iterations which leverage the structure of MLN (Sec.
the same block, then and must coexist, i.e., Va, b, c: C(a, A c(b, = C(a, c). to which
refer as "transitivity rule". NNs generally predict C(:,)) independently. failing to meet this FOLC (Fig. [e),, and the same applies to the advanced regularization method (Xu et al.) (2018) (Fig. [d)
We aim to incorporate the transitivity rule into NNs so that the predicted result satisfies the logical
constraint (Fig. e)). FOLCs are also critical in many other real-world tasks, ranging from collective
classification tasks over graphs (Richardson & Domingos 20066; Singla & Domingos 2005) to
structured prediction over text (Sang & Meulder 2003).
Incorporating such FOLCss into neural networks is long- challenge. The main difficulty lies in modeling intricate variable dependencies among massive propositional groundings. For instance, for the transitivity rule with 512 tokens, 262K coexistence variables are mutually dependent in 134M groundings. Essentially, modeling FOLCs involves the weighted first-order model counting (WFOMC) problem, which has been extensively studied in the previous literature (den Broeck & Davis 2012 Dalvi & Suciu 2013 Grikkoff et al. 2014).. However, is proved #P-complete for even moderately complicated FOLCs (Dalvi & Suciu 2013), such the transitivity rule mentioned above.
Markov Logic Networks (MLNs) (Richardson & Domingos/ 2006) are a common approach to modeling FOLCs, which use joint potentials to measure the satisfaction of the first-order logic rules, ML. is inherited from WFOMC, and is difficult to achieve exact inference (Gribkoff et al., 2014). Although MLN formalization allows for approximate inference, MLNS have long suffered from the absence of efficient inference algorithms. Existing methods typically treat the groundings individually and fail utilize the structure and symmetries of MLNs accelerate computation (Yedidia et al.
2000 Richardson & Domingos 2006; Poon & Domingos 2006). ExpressGNN (Qu & Tang] [2019] Zhang et al.] (020) attempts combine MLNs and NNs using variational EM, but they remain inherently independent due to the inference method's s inefficiency. Some lifted algorithms exploit the structure of MINs to improve efficiency but are infeasible for neural integration due to their requirements of symmetric input (de Salvo Braz et al. 2005 Singla & Domingos 2008 Niepert 2012) or specific rules (den Broeck & Davis 2012; Gribkoff et al. 2014).
This paper proposes novel approach called Logical Message Passing (LogicMP) for general- purpose FOLCs. It is an efficient MLN inference algorithm and can be seamlessly integrated with any off-the-sher NNs, positioning it as neuro-symbolic approach. Notably, it capitalizes the benefits of parallel tensor computation for efficiency and the Blug-and-pu -play principle for modularity. Fig g illustrates the computational graph of LogicMP. Bare NNs (Fig. 21) predict each output variable independently. LogicMP can be stacked on top of any encoding network as an efficient modular neural layer that enforces FOLCs in prediction (Fig. (p). Specifically, LogicMP introduces an efficient mean-field (MF) iteration algorithm for MLN inference (Fig. bb). This MF algorithm enables LogicMP's ' outputs to approximate the variational approximation of MLNs, ensuring that FOLCs can be encoded into LogicMP's inputs. In contrast to vanilla MF algorithms that rely on inefficient sequential operations (Wainwright & Jordan 2008 Koller & Friedman, 2009)), our well-designed MF iterations can be formalized as Hinstein summation, thereby supporting parallel tensor computation. This formalization benefits from our exploitation of the structure and symmetries of MINs (Sec. 3.2 which is supported by theoretical guarantees (Sec.
In Sec. [. we demonstrate the versatility of LogicMP by evaluating its performance on various real- world tasks from three domains: visual document understanding over images, collective classification over graphs, and sequential labeling over text. First, we evaluate LogicMP on a real-world document understanding benchmark dataset (FUNSD) (Jaume al. 2019) with up 262K variables and show that outperforms previous state-of the methods (Sec. S.T.. Notably, the results demonstrate that LogicMP can lead evident improvements even when imposing a single
2

---

Published as a conference paper at ICLR 2024
FOLC prediction variables, which is beyond the capacity of existing methods using arithmetic circuits (ACs). For the second task (Sec. (52)) we conduct experiments on relatively large datasets in the MLN literature, including UW-CSE (Richardson & Domingos, 2006 and Cora (Singla &
Domingos 2005). Our results show that LogicMP significantly speeds up by about 10x compared competitive MINN inference methods, which enables larger-scale training for better performance. Finally, we evaluate LogicMP on a sequence labeling task (CoNLL-2003) (Sang & Meulder 2003) and show that it can leverage task-specific rules to improve performance over competitors (Sec.
Contributions. We: (i) Present a novel, modular, and efficient neural layer LogicMP, the first fully differentiable neuro-symbolic approach capable of encoding FOLCs for arbitrary neural networks. (ii) Design an accelerated mean-field algorithm for MLN inference that leverages the structure and symmetries MINS,, formalizing it to parallel computation with reduced complexity from O(N (. to ((N L (M' I M) (Sec. 3). For instance, LogicMP can incorporate FOLCs with up to 262K variables within 0.03 seconds, where AC-based methods fail during compilation. (iti) Demonstrate its effectiveness and versatility in challenging tasks over images, graphs, and text, where LogicMP outperforms state-of-the-ar neuro-symbolic approaches, often by noticeable margin.
2 MARKOV LOGIC NETWORKS
An MLN is built upon knowledge base (KB) {E, R, consisting of set E he of entities, a set R = {ri h of predicates, and a set of observation. Entities are also called constants (c.g.. tokens). Each predicate represents a property assigned to a predicate, we obtain a ground atom, e.g., C(e1, 62) where 61 and 02 are two tokens. For ground atom we use random variable oy in the MLN to denote its status, e.g., Vo(e1.ea) {0, 1} denoting whether 61 and 62 coexist. The MLN is defined over all variables {ur); and a set of first-order logic formulas F. Each formula f' E F represents the correlation among the variables, e.g., Va, b, C(a, b) A C(b, c) = C(a, e) which equals Va, c. -C(a, b) V -C(b, c) V C(a,c) by De Morgan's 's law. With particular entities assigned to the formula, we obtain a ground formula, aka grounding, e.g., -C(e,, e2) V -C(e2, ea) C(e1, e3). For grounding g. we use Vg denote the variables in e.g., (Uo(es.e2)) [e(e).e)) (c((er,e))& }. In MLN, each f is associated with a weight wy and a potential function ())+) Vg + {0, 13 that checks whether the formula is satisfied in For each formula S, we can obtain set of groundings Gy by enumerating all assignments. We adopt the open- open-world assumption (OWA) and jointly infer all unobserved facts.
relation, e.g.. coexist (C). With particular entities
Based on the KB and formulas, we express the MLN as follows:
p(v|O) exp( Σ (oa(
+
Σ W Ed)(Ts)) JEF
BEG;
neural semanties
syymbolic FOLCs
where V is the set of unobserved variables. The second term is for symbolic FOLCs, where Egec, (V,) measures the number of satisfied groundings of We explicitly express the first term to model the evidence of single ground atom in status v; using the unary potential pa(-)= Us H R. By parameterizing ou with NN, this formulation enables semantic representation, allowing exter- nal features, such as pixel values of an image, to be incorporated in addition to the KB. Note that Φu. varies with different i, but for the sake of simplicity, we omit i in the notation.
2.1 MEAN-FIELD ITERATION FOR MLN INFERENCE
The MIN inference is persistent and challenging problem, as emphasized in (Domingos & I Lowd 2019). In an effort to address this issue, we draw inspiration from CRFasRNN (Zheng et al. (015) and employ the MF algorithm (Wainwright & Jordan 2008 Koller & Friedman, 2009) to mitigate the inference difficulty, which breaks down the Markov network inference into multiple iterations. Unlike the variational EM approach (Zhang et al.] 2020). which requires additional parameters, MF does not introduce any extra parameters to the model.
We focus the MLN inference problem with a fixed structure (i.e., rules). The MF algorithm is used for MLN inference by estimating the marginal distribution of each unobserved variable. computes variational distribution Q(v) that best approaches p( p(v(O), where Q(v) = II. Q+(1.) is a product
3

---

Published as a conference paper at ICLR 2024
of independent marginal distributions over all unobserved variables. Specifically, it uses multiple mean-field iterations to update all Q; until convergence. Each mean-field iteration updates the Q; in closed-form to minimize Dx (Q(v))lp(v(O)) as follows (see derivation in App.
Qi(u;) t explo (1)) +
1 Zi
Σ Σ Qrg((i)), SEF
wy
(2)
gEG,(1)
()) is the groundings of f that involve the ground atom i, and where Z, is the partition function, (i)
Qi.g(t)) + Edlu Vg
II Q5(1s)
(3)
jEg
is the grounding message that conveys information from the variables g-i to the variable i w.r.t the grounding g. 9-; denotes the ground atoms in g except i, e.g., 9 )-((e)es) = {C(el, 62), ea)).
2.2 COMPUTATIONAL COMPLEXITY ANALYSIS
Complexity Notation. Although MF simplifies MLN inference, vanilla iteration remains compu- tationally expensive, with its exponential complexity in the arity and length of formulas. Let us examine the time complexity of single iteration using Eq 2 Denote N the number of constants in E, M = max, | as the maximum arity of formulas, L max, Ifl as the maximum length (number of atoms) of formulas, and D the maximum number of labels of predicates (for typical binary predicates, D = 2; while for multi-class predicates in many tasks, D may be large).
Expectation calculation of grounding message. The computation of grounding message Qi, (v:) Eq. involves multiplying [g (,(1,) (which (L)) for all possible values of Vg (which is ((D resulting in complexity of (LDD--)). When D is large, DL is essential.
Aggregation of massive groundings. Since the number of groundings |Gyl is O(N"), and grounding generates grounding messages for all involved variables, we have O L) grounding messages. With the complexity of computing a grounding message being O(LD the total time complexity of an MF iteration in Eq. is 1,2 which is exponential in M and T..
EFFICIENT MEAN-FIELD ITERATION VIA LOGICMP
We make two non-trivial improvements the vanilla MF iteration, enabling LogicMP to perform efficient MLN inference.
(1) We find that the calculation of a single grounding message in Eq. contains considerable unnecessary computations and its time complexity (Sec. B.I.. b. (2) We further exploit the structure and symmetries in MLN to show that the grounding message aggregation in Eq. 2 can be formalized with Einstein summation notation. As a result, MF iterations can be efficiently implemented via parallel tensor operations, which fundamentally accelerates vanilla sequential calculations (Sec. 3.2). In the following, we will introduce several concepts of mathematical logic, such as clauses and implications (see more details in App. B
be greatly reduced
3.1 LESS COMPUTATION PER GROUNDING MESSAGE
Clauses are the basic formulas that can be expressed as the disjunction of literals, e.g., f == Va, b, c -C(a, b) V CCC, e) V C(a, c). For convenience, we explicitly write the clause as [(:: where n. is
the preceding negation of atom in the clause f, e.g., (i((a))) = 1 due to the - ahead of C(a, b). A
clause corresponds several equivalent implications where the premise implies the hypothesis, e.g..
C(a, b)ACC)CCC c) = C(a, c). C(a, 6CA-C(a, c)
-c(b, c). and C(b, c)A-c(a, c) = -C(a, b).
Intuitively, the grounding message Qi.g in Eq. w.r.t. g-i - corresponds to an implication (e.g.. C(e1,e2) E2) C(e2,e3
C(er,ea)) ea)). Since the grounding affects only when the premise q=
true. most assignments of Vg-, that result in false premises can be ruled out in Σv.., in Eq.
Theorem 3.1. (Message of clause considers true premise only.) For a clause formula f(in),, the
MF iteration of Eq. is equivalent for Qi.((1) + 1,, I Qū(1; = nz))
The proof can be found in App. C Table I
briefly illustrates the idea of the proof: for assignments of g-i resulting in false premises, the potential can be ruled out since it makes no difference for
4

---

Published as a conference paper at ICLR 2024
Table 1: For the ground- ing message of w.rt C()1, A C(e2, 6z) = C()), only one assignment of ea) makes difference to C(e1, eg). i.., useful.
Gioundin Message
MasporQ
dy (vg)
Voler ea)
An Moon fold Konatinn LogicMP wxt sansiiity nuc
Po.be: -o. -Q Qu.,
9-80g [g)
(0.0) 0) 1= X
(0,1) 1= 1 X
Figure 3: Instead of sequentially generating groundings (left), we ex- ploit the structure of rules and formalize the MF iteration into Einstein summation notation, which enables parallel computation (right).
(1,0)
=
X
(1,1) 0
various assignments of the hypothesis Therefore, only the true premise (u, n2) jeg- needs be considered. Compared Eq, 3 the complexity is reduced from OLDD--1) (L). The formulas in conjunctive normal form (CNF) are the conjunction of clauses. The simplification can also be generalized to CNF for (L) complexity. The following theorem demonstrates this claim: Theorem 3.2. (Message of CNF = Σ message of clause.) For a CNF formula with distinct clauses (=).))). the MF iteration of Eq. is equivalent for Qi.g(ve) + E/e 1v.=-n, IL Q5(0, = n2))
See App. D for proof. This theorem indicates that the message of CNF can be decomposed into several messages of its clauses. Therefore, we only need consider the clause formulas. We also generalize the theorem for the formulas with multi-class predicates to benefit general tasks (App. E]
3.2 PARALLEL AGGREGATION USING EINSTEIN SUMMATION
This subsection presents efficient method for parallel message aggregation, i.e., Egec, Qig (c:) in Eq. In general, we can sequentially generate all propositional groundings of various formats in G to perform the aggregation. However, the number of possible groundings can be enormous, on the order of ((NM), MM, ), and explicitly generating all groundings is infeasible in space and time. By exploiting the structure of MLN and treating the grounding messages of the same first-order logic rule symmetrically, LogicMP automatically formalizes the message aggregation of first-order logic rules into Einstein summation (Finsum) notation. The Finsum notation indicates that aggregation can be achieved in parallel through tensor operations, resulting in acceleration at orders of magnitude.
The virtue lies in the summation of the product, i.e., Egec, IJ Q,(0, = n2) by Theo- rem which indicates that the grounding message corresponds to the implication from the premise g-4 the hypothesis i. Due to the structure of MLN, many grounding messages belong to the same implication and have the calculation symmetries, so we group them by their corresponding implications. The aggregation of grounding messages w.r.t. implication amounts integrat- ing some rule arguments, and we can formalize the aggregation into Einsum. For instance, the aggregation w.r.t. the implication Va, b, c C(a, b) A C(b, c) = C(a, c) can be expressed as einsum(" consumm"a,aa be + ac", Qa(1), Qc(1)) where Q,(v,) denotes the collection of marginals w.r.t. AA
predicate r, i.e., Qv(v,) (Qr(A.) (Er(A)))))) A. (A, is the arguments of r). Fig. 3 fillustrates this process, where we initially group the variables by predicates and then use them to perform aggregation using parallel tensor operations (see App. F We formalize the parallel aggregation as follows:
Proposition. Let [f, h] denote the implication of clause I with atom h being the hypothesis and &,, (Vr) denote the collection of (v.) w.r.t. predicate T. For the grounding messages w.r.t. [f, h) of a clause [(A, to its atom h with arguments Af, their aggregation is equivalent to:
QI..M( t Iv., Iv.,=-mx my einsum(". "..., Al..A. Afyan.... + Al. Qryen (n.4t))...),
Q
(4)
where Th, is the predicate of h, Af, is the arguments of Th. The MF iteration of Eq. equivalent to:
Q~(v,) k Z,
exp($
Σ
wi @.
(5)
5

---

Published as a conference paper at ICLR 2024
An additional benefit of using Einsum notation is indicates a way to simplity complex- ity in practical scenarios. Let us consider a chain rule Va, b, c, (a b) A r2(b, e) A Ia(c, d) + Fa d). The complexity of einsum("at bc, ed + ad" Qr (1), Qr, (1), Qr (1)) is O(N4). By Einsum optimization, we can reduce it to O(N9). Note that the Einsum op- timization almost free, as it can be done within milliseconds. This optimization method not limited to chain rules and can be applied to other rules, which demonstrate in App. G For any rule, the optimized overall complexity is O L²) where M' is the maxi- mum number of arguments in the granular operations (App. H). in contrast to the original one O(NML'DI-1) In the worst case, M equals M, but in practice, M' may be much smaller.
Algorithm 1 LogicMP.
3.3 MULTIPLE MF ITERATIONS AS LOGICMP
Require: Grouped unary potential (v..(vv.)) ).. the formulas (J(A; y and rule weights {wy]s. the number of iterations T.
Algorithm presents LogieMP, which requires the grouped unary potentials (V.)v,)), formu- las {S(A; n)}r, s. and rule weights { {wyrr y. and out- puts updated marginals {Qr (v~)), |r for all predi- cates. LogicMP performs T iteeationn and firstly computes an initial distribution for every variable using unary potentials and softmax normalization at each iteration. Then, it enumerates all impli- cations to perform Einsum via Eq. $ The unary potentials and outputs of Einsum are combined to obtain a new estimate of the marginals (Eq. 5) Finally, it returns the output from the last iteration. An execution example is shown in App. |
(v,), + ž, exp(ex (v.))) for all predicates for E [T do
Iterations
for f F do
> formulas
for h E do
Implications
Obtain " (vrz) by Eq. Parallel
end for end for Update Qv((v.) by Eq. for all predicates end for return (Q,
RELATED WORK
MIN inference. MLNs are suitable for FOLCs, but have been absent in the neuro-symbolic field for a long time due to inference inefficiency. The most relevant work is the ExpressGNN (Qu & Tang 2019; Zhang et al. 2020), which has preliminary attempted combine MLNs with NNs via variational EM. Although both ExpressGNN and LogicMP are based on variational inference, they have clear differences: (1) LogieMP uses the MF algorithm, which permits closed-form iterations (Sec. 2. (2) LogicMP obtains essential acceleration by exploiting the structure and symmetries in MLNs (Sec. D. (3) These enable LogicMP be applied in general tasks, including computer vision (CV) and natural language processing (NLP) (Sec. 5) Conventional MLN inference methods perform inference either at the level of propositional logic or in a lifted way without performing grounding. The former is inefficient due to the complicated handling of the propositional graph, e.g., Gibbs sampling (Richardson & Domingos] 2006). MC-SAT (Poon & Domingos 2006). BP (Yedidia et al., 2000). The latter consists of symmetric lifted algorithms which become inefficient with distinctive evidence, such as lifted BP (Singla & Domingos (0008), and asymmetric lifted algorithms which often requires specific formulas (den Broeck & Davis 2012, Gribkoff et al., 2014)) evidence (Bui ct al. 2012). LogicMP situates itself within the MLN community by contributing a novel and efficient MLN inference method. [Daaaratha al. (2023): Marra et al. (2020) attempted to combine neural networks with first-order logic but the training remains separate.
Neuro-symbolic reasoning, A branch of neuro-symbolic methods aims to represent the logic into neural networks (Dasaratha et al., 2023). Besides, some neuro-symbolic methods (Hoernle et al.
2022 Giunchiglia & Lukasiewicz 2021 & Srikumar 2019 Hoernle et al. 2022 Giunchiglia
Lukasiewicz 2021 Li & Srikumar 2019; Fischer et al. 2019 Yang et al. 2002)) integrate logical constraints by handling propositional groundings individually. Other methods, e.g., semantic loss (SL) (Xu et al. 2018) and semantic probabilistic layer (SPL) (Ahmed et al. (022). are rooted in probabilis- tie logic programming (PLP) that utilizes ACs. However, ACs are often limited to propositional logic and may be insufficient to handle FOLCs unless specific formulas employed (den Broeck & Davis
2012). Research applying ACs for FOLCs is currently ongoing in both the MLN and PLP fields,
including probabilistic database (Tha & Suciu 2012) and asymmetric lifted inference (den Broeck &

---

Published as a conference paper at ICLR 2024
Niepert 2015), but it remains a challenging problem. LogicMP exploits the calculation symmetries in MLN for efficient computation by parallel tensor operations. Consequently, LogicMP contributes to developing neuro-symbolic methods for FOLCs using MLNs. Notably, popular neuro-symbolic methods such as DeepProbl.og (Manhaeve et al., 2018) and Scallop (Huang et al. 2021) also use ACs and are typically used under closed world assumption rather than OWA.
5
EXPERIMENTS
5.1 ENCODING FOLC OVER DOCUMENT IMAGES
Benchmark Dataset. We apply LogicMP a CV task, i.e., the information extraction task on the widely used FUNSD form understanding dataset (Jaume et al. 2019). The task involves extracting information from a visual document image, as shown in Fig. tokens into several blocks. The maximum number of tokens is larger than 512. The evaluation metric is the F1 score. The dataset details and general settings are provided in App.
where the model needs to segment
Our Method. We formalize this task matrix prediction in (Xu et al. 2022). Each element in the matrix is a binary variable representing whether the corresponding two tokens coexist in the same block. A matrix with ground truth is shown in Fig. Tb We adopt the LayoutLM (Xu eet al. 2020). robust pre-trained Transformer, as the backbone to derive the vector representation of each token. The matrix 2 is predicted by dot-multiplying each pair of token vectors. We call this model LayoutLM-Pair Independent classifiers often yield unstructured predictions (Fig. Ic]. but we can constrain the output via the transitivity of the coexistence, i.e., tokens a, must coexist when tokens a, b coexist, and b, coexist. Formally, we denote the predicate as C and the FOLC as Va, b, c C(a. b) A c(b, c) = C(a,c) c). LogicMP applies this FOLC to LayoutLM-Paii Each experiment is performed 8 times, and the average score is reported. See App. for more details.
Compared Methods. We compare LogicMP to several robust information extraction methods, including BIOES (Xu et al. 2020), SPADE (Hwang et al. (02I), and SpanNER (Fu et al. (021). We also compare LogicMP to other neuro-symbolic techniques. SL (Xu et al. 2018) is the abbreviation of Semantic Loss, which enforces constraints on predictions by compiling an AC and using it to compute a loss that penalizes joint predictions violating constraints. However, compiling the AC for all variables (up to 262K) is infeasible. Therefore, we penalizing every triplet and summing them via the parallel method proposed in Sec. 3.2 SPL (Ahmed) et al. (022) models joint distribution using ACs, but the same relaxation as SL cannot be applied since all variables must be jointly modeled in SPL.
unrigorous relaxation (SLrelax), i...
Main Results. Table shows the results the FUNSD dataset, where "full" incorporates all blocks, and "long" excludes blocks with fewer than 20 tokens. Upon integrating FOLC using LogicMP, observe consistent improvements in two metrics, particularly 7.3% relative increase in "long" matches. This is because FOLC leverages other predictions to revise low-confidence predictions for distant pairs, as shown in Fig. However, SL and SPL both fail in this task. While attempting to ground the FOLC and compiling AC using PySDD (Darwiche) 2011), we found that it fails when the sequence length exceeds 8 (App- L.3 contrast, LogicMP can perform joint inference within 0.03 seconds using just 3 tensor operations (App. [.4] with single additional parameter. SLrelax is beneficial but outperformed by LogicMP. Additionally, LogicMP is compatible with SLrelax since LogicMP is a neural layer and SLrelax is a learning method with logical regularization. Combining them further improves performance. More visualizations are attached in App. J.5
5.2 ENCODING FOLCS OVER RELATIONAL. GRAPHS
Benchmark Datasets. We evaluate LogicMP on four collective classification benchmark datasets, each with specific FOLCs. Smoke (Badreddine et al. 2022) serves sanity check (see results in App. K.Sp. 5p. Kinship (Zhang et al. (020)) involves determining relationships between people. UW-CSE RRichardson & Domingos 2006) contains information about students and professors in the CSE department of UW. Cora (Singla Domingos, 2005) involves de-duplicating entities using the citations between academic papers. It is noteworthy that Cora has 140+K mutually dependent variables and 300+B groundings, with only around 10K known facts. The dataset details and general settings are given in App. K We conduct each experiment 5 times and report the average results.
7

---

Published as a conference paper at ICLR 2024
Table 2: Comparison F1 on FUNSD. Better results are in bold. "full" denotes the full set while "long" only considers the blocks with more than 20 tokens. "_" means failure.
Table 3: Comparison Fl on CoNLL2003. Better results are in bold. adj (list) denotes the adjacent (list) rules. "_" means failure.
Methods
F1
Methods
full
long
BLSTMM Tu al. 2016
89.98
LayouiL. BIOES Xu et al 2020
80.1
33.7
BLSTTM (ee) Cai & Nichols
2016
90.77
Layoud M. S--Spon NER di
2021
22.0
BLSTM
Lample al
Layourt MASPADE (Wane ai 2022
80.1
43.5
BLSTTM w/ CRF (mean helld Wang at al 2020
91.07
LayourLM-Pail (Xu ot
2022
82.0
46.7
BLSTM w/ X al.
Xu
2018
LayouiLM Pair w/ SL. (Xu et
2018
BI STM w/ SPI Ahhmes of 2022
Layout Pair SPL. Nhimed al
BLSTM SLrelax
90.38
Layour M-Pair w/ SLreelx
82.0
47.8
BL STM w/ LigicDist (adj) (Hu el al.
2016
p: 89,80, 91.11
M- LogicMP
83.3
50.1
BLSTM w/ LisieDist (adj-list) (Hu of 2016
p: 89.99, q: 91,18 91.25
BLSTM w/ LogicMP (adj)
LayoutL Pair w/ SLrelax-LogicMl
83.4
50.3
BLSIM w/ LogicMP (adj+liss)
91.42
Agroundings per second
UW Cww.ce
Uuy Cate targuuaee
Legesee wit Opttinnum Pariddol BudeDuu wet
2500
2003
Log casf Optiinsum
0.3
1900
0.0
352
265
gripphis
369
26h aysterns 150
0.2
500
Krohp
USI cse
Cora
300
Figure 4: Efficiency comparison of accelera- tion techniques.
Figure 5: AUC-PR w.r.t minutes during the training in UW-CSE.
Compared Methods. We compare with several strong MLN inference methods. MCMC (Gikss
ctt al. 1995 Richardson & Domingos 2006) performs samplings over the ground Markov network.
BP Yedidia al. 2000) uses belief propagation instead. Lifted BP (Singla & Domingos 2008
groups the ground atoms in the Markov network. MC-SAT (Poon & Jomingos][2000 performs
sampling using boolean satisfiability techniques. HL-MRF (Bach et 2017
al. 2019)
is hinge-loss Markov random field. ExpressGNN denotes the graph neural network proposed in (Zhang al., 2020), which is trained to fit the data. ExpressGNN w/ GS denotes that ExpressGNN trained to maximize the grounding scores, i.c., the satisfaction of formulas for the groundings using sequential summation (i.c., ExpressGNN-E (Zhang et al., (020)). Following ExpressGNN w/ GS, we adopt the OWA setting where all unobserved facts are latent variables to infer and use the area under the precision-recall curve (AUC-PR) as the performance evaluation metric.
Our Method. For fair comparison with ExpressGNN w/ GS, we set the rule weights to 1 and use ExpressGNN as the encoding network to obtain unary potentials Φu. We stack LogicMP with 5 iterations over it. The encoding network is trained to approach the output of LogicMP, which regularizes the output of the encoding network with FOLCs. This learning approach is similar to ExpressGNN w/ GS, as discussed App. computational efficiency, which enables larger-scale training for better performance.
The main advantage of using LogicMP is its
Main Results. Fig. 4 shows the training efficiency of LogicMP, which is about 10 times better than ExpressGNN w/ GS, reducing the computational time per grounding to just millisecond. Thus, we can scale the training from the original 16K (Zhang et al. 2020) to 20M groundings a reasonable time. Surprisingly, we found that the performance of LogicMP steadily improved with more training This observation suggests that the performance of ExpressGNN w/ GS reported in the original work may be hindered by its inefficiency in performing sufficient training.
(Fig. 5
Table shows the AUC-PR results for the three datasets with a mean standard deviation of 0.03 for UW-CSE and 0.01 for Cora. A hyphen in the entry indicates that it is either out of memory exceeds the time limit (24 hours). Note that since the lifted BP is guaranteed to get identical results as BP, the results of these two methods are merged into one row. LogicMP obtains almost perfect results on a small dataset (i.e., Kinship), exhibiting its excellent ability in precise inference. In addition, performs much better than advanced methods on two relatively large datasets (i.e., UW-CSE and
8

---

Published as a conference paper at ICLR 2024
Table 4: AUC-PR Kinship, UW-CSE, and Cora. The best results are in bold. "." means failure.
Kinship
UW UW-CSE
Cora
Method
S1
S2
S3
S4
S5
avg.
A.
G.
S.
T.
S2
S3
S4
S5
MCMC
Richardson Domingos 2006
.33
MLN
BP/Liif HP Singla & Domingus
2008
.33
.58
.55
.55
.56
-56
.01
.01
.01
.01
01
.01
MC-SAT
Poon & Domingos 2016
55
.55
.03
02
00
HL-MRF Bach ot
2017
1.0
1,0
1.0
1,0
.06
.09
002
.04
.03
.05
EXprossGNN
.66
49
53
54
01
01
01
01
.37
66
.4
55
.4
ExpressGNNN w/ GS Zhung et al
2020
97
99
.99
99
.99
98
099
.1
.14
06
09
.1
66
79
.6
.57
.75
.64
EXpressGNN w/ LogieMP
.26
88
Cora), improving relatively by 173%/28% over ExpressGNN w/ GS. The improvement is due to its high efficiency, which permits more training within shorter time (less than 2 hours). Without LogicMP, ExpressGNN GS would take over 24 hours to consume 20M groundings.
Ablation Study. Fig. also illustrates the efficiency ablation of the techniques discussed in Sec.
As compared to LogicMP, the parallel Einsum technique (Sec. 3.2) achieves significant acceleration, while other improvements, i.e., Einsum optimization and RuleOut (Sec. 3.1) also enhance efficiency. More comparison results are shown App.
5.3 ENCODING FOLCs OVER TEXT
Benchmark Dataset & Compared Methods. We further verify LogicMP in an NLP task, i.c., the sequence labeling task. We conduct experiments on the well-established CoNLL-2003 bench- mark (Sang & Meulder 2003). The task assigns a named entity tag each word, such as B-LOC, where B is Beginning out of BIOES and LOC stands for "location" out of 4 entity categories. This experiment aims not to achieve state-of-the-e
performance but to show that specific FOLCs can also be applied. The compared methods use the bi-directional LSTM (BLSTM) as the backbone and employ different techniques, including SLrelax and logic distillation (LogicDist) (Hu et al. 2016).
Our Method. For a fair comparison, also use BLSTM the backbone and stack LogicMP on BLSTM to integrate the following FOLCs used in LogicDist. (I) adjacent rule: The BIOES schema contains constraints for adjacent labels, e.g., the successive label of B-PER cannot be O- PER. We explicitly declare the constraints as several adjacent logic rules, such as Ví: label(i) E [B/I-PER) + label(i 1) E (I/E-PER). where label(i) (1) is the multi-class predicate of i-th token label (see the extension for multi-class predicate in App. D (2) list rule: we exploit a task-specific rule inject prior knowledge from experts. Specifically, named entities in list are likely be in the same categories, c.g., "Barcelona" and "Juventus" in "1. Juventus, 2. Barcelona, 3. The corresponding iOLC ji : label(i) (B/I/E-LOC) A samelist(i.j) + label(j) E (B/I/E-LOC,, where samelist(i.j) indicates the coexistence of two tokens in list.
Main Results. Table presents our experimental results, with the rule-based methods listed the bottom. Along with the BLSTM baselines, LogicMP outperforms SLrelax and LogicDist, where "p" denotes BLSTMM and "q" post-regularizes the output of BLSTM. These methods implicitly impose constraints during training, which push the decision boundary away from logically invalid prediction regions. In contrast, LogicMP always explicitly integrates the FOLCc Cs into the BL.TTM output. For samples with list structure, LogicMP improves Fl from 94.68 to 97.41.
CONCLUSION
We presented a novel neuro-symbolic model LogicMP, an efficient method for MLN inference, principally derived from the MF algorithm. LogicMP can act as a neural layer since the computation fully paralleled through feed-forward tensor operations. By virtue of MLN, LogicMP is able to integrate FOLCs into any encoding network. The output of LogicMP is the (nearly) optimal combination of the FOLCss from MLN and the evidence from the encoding network. The experimental results over various fields prove the efficiency and effectiveness of LogicMP.

---

Published as a conference paper at ICLR 2024
REFERENCES
Kareem Ahmed, Stefano Teso, Kai- Chang, Guy Van den Broeck, and Antonio Ver- gari. Semantic probabilistic layers for neuro-symbolic learning. In Advances Neural Information Processing Systems 35: Annual Conference on Neural Information Process- ing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 December 2022, 2022. URL /ttp::/paapprss cc/paper http://pppppeeleeeeeeeeeeeeeeeee fwwes/ h2shh/ahhhhhh/h///// (152e663118822226666626222222232 ort.a//9555.atteeoaaaeea------rr htmm
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. / wtt.orrggg.ooo wttppaapps///aaaooooog////////sp w1//1111111111
1001155633 631. html
Samy Badreddine, Artur d' Avila Garcez, Luciano Serafini, and Michael Spranger. Logic tensor networks, Artificial Intelligence, 303:103649, 2022. doi: 10. 1006//..rtimt.222111
URL
2021. https:://oi.com www.oooo.oggg.... 1016 2033.. 103649.
Hung Hai Bui, Tuyen N. Huynh, and Rodrigo de Salvo Braz. Exact lifted inference with distinct soft evidence on every object. In Proceedings of the Twenty-Sixile AAAI Conference on Artificial
Intelligence, July 22-26, 2012, Toronto, Ontario. Canada. AAAI Press, 2012. URL http
7/ /www. aaai org/ /ttp//////////////////////////// index. //tp///////////////////////////a
Jason P. C. Chiu and Eric Nichols. Named entity recognition with bidirectional LSTM-CNNs. Transactions of the Association for Computational Linguistics, 4:357-370, 2016. doi: 10.1162/
tacl|_at 001044 /tt.:tttppe//o....r///0.... htt..//orrrr...11/ttacaccccc _01004
Nilesh Dalvi and Dan Suciu. The dichotomy of probabilistic inference for unions of conjunctive queries. Journal of the ACM (JACM), 59(6):1-87, 2013.
Adnan Darwiche. SDD: A new canonical representation of propositional knowledge bases. In Proceedings of the 22nd International Joint Conference on Artificial Intelli- gence, Barcelona, Catalonia, Spain, July 16-22, 2011, pp. 819-826. IICAI/AAI,, 2011. URI.
doi: 51177735-16-8111660 111----8-1JAAA1111011 978 100--1157735-5
Sridhar Dasaratha, Sai Akhil Puranam, Karmvir Singh Phogat, Sunil Reddy Tiyyagura, and Nigel P. Duffy. Deeppsl: End-to-end perception and reasoning. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pp. 3606-3614 ijeai.org. 2023. doi: (.224663/JCAA.22224440 URL
/ttp::
/ww./////aa....... wtt.caa....2220000 2023/401
Rodrigo de Salvo Braz, Eyal Amir, and Dan Roth. Lifted first-order probabilistic inference. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh. Scotland, UK, July 30 August 5, 2005, pp. 1319-1325. Professional Book Center, 2005. URL http::// caai. org/ roceedi http:///app/e////////e///./
.pd.]
Guy Van den Broeck and Jesse Davis. Conditioning in first-order knowledge compilation and lifted probabilistic inference. In Proceedings of the Twenty-Sixth AAAI Conference Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada. AAAI Press, 2012. URL http: 7/ www..aaai...m org/ ocs / index. wwwp//A./........... AAAAIAAAAAT1.. wwt.aii/pppperreee wwwppaapppaiiiae
Guy Van den Broeck and Mathias Niepert. Lifted probabilistic inference for asymmetric graphical models. In Proceedings of the Twenty-iinth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA, pp. 1599-3605, AAAI Press, 2015. URL http:/ /tt:://wwww /www aaai org/ /cs//oc//ett index.n..... http://wpppaaaaaaaaaaaaaap//eeea
AAAI / AAA
Pedro Domingos and Daniel Lowd. Unifying logical and statistical Al with Markov logic. Communi- cations of the ACM, 62(7))74-83, 2019.
Marc Fischer, Mislav Balunovic, Dana BrcchslerCCohen Timon Gehr, Ce Zhang, and Martin Vechev. DL2: training and querying neural networks with logic. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings
10

---

Published as a conference paper at ICLR 2024
of Machine Learning Research, pp. 1931-1941. PMLR, 2019. URL http://procedings mlr. Seteess/97//iscceee html
Jinlan Fu, Xuanjing Huang, and Pengfei Liu. SpanNER: Named entity re-Itecognition span prediction. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference Natural Language Processing, ACI/I
JCNLP 2021, (Volume I: Long Papers), Virtual Event, August 1-6, 2021, pp. 7183-7195. As- sociation for Computational Linguistics, 2021. doi:
acc.ooog.... URL 558
http:://OO...rr//..1B6665
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:001120499 2010.
http:/oottraa..........moea org. citation. cmm? Stmmidd=185911
Walter R Gilks, Sylvia Richardson, and David Spiegelhalter. Markov chain Monte Carlo in practice. CRC press, 1995.
Eleonora Giunchiglia and Thomas Lukasiewicz. Multi-label classification neural networks with hard logical constraints. J. Artif. Intell. Res.. 72:759-818, 2021. doi: 10.1613/JAIR 1.18500 URL
https::/doi. /////1111111111111 11111//aar....... 12850
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
Eric Gribkoff, Guy Van den Broeck, and Dan Suciu. Understanding the complexity of lifted inference
and asymmetric weighted model counting. In Statistical Relational Artificial Intelligence, Papers from the 2014 AAAI Workshop, Québec City, Québec, Canada, July 27, 2014, volume WS-14-13 of AAAI Technical Report. AAAI, 2014. URL http:://wwwwwt.. a aaai.aaaaa........... org/ ocs/ wndex.idxx.. i
MS/ AAAIWI /AATW11/papprr/veew 8782
Nick Hoernle, Rafael-Michael Karampatsis, Vaishak Belle, and Kobi Gal. Multiplexnet: Towards fully satisfied logical constraints in neural networks. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelli- gence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 March 1, 2022, pp. 5709. AAAI Press, 2022. doi: 10.1609/AAAL V3615 20511.. URL httpt::tp//tt.......t. /oi. org/ 10. 609/ aaai. v3615. 20511
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, Association for Computer Linguistics, 2016. doi: 10. 10.18653/v1/p16-1222 URL https
www.1//1/11eeee55 1228
Jiani Huang, Ziyang Li, Binghong Chen, Karan Samel, Mayur Naik, Le Song, and Xujie Si. Scallop: From probabilistic deductive databases to scalable differentiable reasoning. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 25134-25145, 2021. d367eef13f900 3Dd www.:/9e111111111111 3
(eaaper/222/haae0 www.iiiinnnn....ssnooeoe.e wwwrips......e wwtppppppppppppppppttp / 2221//2221/2 h/ahh/ wbst.act........................ html
Wonseok Hwang, Jinyeong Yim, Seunghyun Park, Sohee Yang, and Minjoon Sco. Spatial dependency parsing for cemi--ttructurd document information extraction. In Findings of the Association for Computational Linguistics: ACL/IJCNPP 2021, Online Event, August 1-6, 2021, I, volume ACL/JCNLP 2021 of Findings of ACL. pp. 330-30 343. Association for Computational Linguistics. 2021. doi: 10. 10.18653/v1/201..ff http:///2222...nns-aaaaee findings-acl.28.
httphttt:://ee
2021 findings ac1.28
Guillaume Jaume, Hazim Kemal Ekenel, and Jean-Philippe Thiran. FUNSD: A dataset for form understanding in noisy scanned documents. In 2nd International Workshop on Open Services and Tools for Document Analysis. OST@ ICDAR 2019, Sydney, Australia, September 22-25, 2019, pp. pp.
1-6. IEEE, 2019. doi: 10.1 10.1199//DRR..21..0000
URL httttt:: 1ttp://....//.110//9911999
TCDARW. 2019 9. 10029
11

---

Published as a conference paper at ICLR 2024
Abhay Kumar Jha and Dan Suciu. Probabilistic databases with markoviews. Proceedings of the
VLDB Endowment, 5(11):1160-1174 2012. doi: 10. 10.447822502992350336 URL h
wtw.bb..rgg/vlllllp... http:///lllvv11111111111
abhay jha laaea_aa____aaaaa v1db2012.pcc.
Daphne Koller and Nir Friedman. Probabilistic Graphical Models Principles and Techniques. MIT
Press, 2009. ISBN 978-0-262-01311-2. URL http::/mitpreestt wttp://rrrss....tei...e wwtps//aaateeeeteaaaaaoaooooooo.
item/ default wtt..appppttyyyteeeeeea111
Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. Neural architectures for named entity recognition. In NAACL HLT 2016, The 2016 Conference of the North American Chapter of the Association for Computational Linguis- tics: Human Language Technologies, San Diego California, USA, June 12-17, 2016, pp. 260- 270. Association for Computational Linguistics, 2016. doi: 10. 10.18653/v1/n1-- 1030. URL
Tao Li and Vivek Srikumar. Augmenting neural networks with first-order logic. In Proceedings of the 57th Conference of the Association for Computational Linguistics, ACI. 2019, Florence, Italy, July 28- August 2, 2019, Volume I: Long Papers, pp. 292-302. Association for Computational Linguistics, 2019. doi: 10. 10.18653/11/p1910000 URL wRL.tttst http::://....cr/110..888 119-1028
Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Decpproblog: Neural probabilistic logic programming. In Advances in Neu- ral Information Processing Systems 31: Anmual Conference Neural Information Pro- cessing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp.
3753-3763, 2018. URL petttps:/prroceediine .ew.eeinnnnnn...u.ss........... neurips hcc/aaper/208/haahl dc5a637edbb62c36ec 3b htt./eeee//bbbbbbbbbbbba222. Awstractbttttt..a.e html
Giuseppe Marra, Michelangelo Diligenti, Francesco Giannini, Marco Gori, and Marco Maggini. Relational neural machines. In Giuseppe De Giacomo, Alejandro Catalá, Bistra Dilkina, Michela Milano, Senén Barro, Alberto Bugarín, and Jérôme Lang (eds.), ECAI 2020 24th European Conference Artificial Intelligence, 29 August-8 September 2020, Santiago de Compostela, Spain, August 29 September 8, 2020 Including 10th Conference on Prestigious Applications of Artificial Intelligence (PAIS 2020), volume 325 of Frontiers in Artificial Intelligence and Applications, pp. 1340-1347. IOS Press, 2020. doi: (0.3233/FALA200223. URL httph:://///d org/10. 30333331333322233333
Mathias Niepert. Lifted probabilistic inference: An MCMC perspective. In 2nd International Workshop on Statistical Relational Al (StaRAI-12), held at the Uncertainty in Artificial Intelligence Conference (UAI 2012), Catalina Island, CA, USA, August 18, 2012, 2012. URL https:/7
starai. cs..i.cc.... ku www.uven..ee.... htaeraa.ccc.ueleeeeeeee///Z//// http:///e/2.///cccppee//ea/aoaee wwwpeeddiiieeett...
Hoifung Poon and Pedro M. Domingos. Sound and efficient inference with probabilistic and deterministic dependencies. In Proceedings, The Twenty- First National Conference Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16-20, 2006, Boston, Massachusetts, USA, pp. 4638463..11 AAAI Press, 2006. httht 77 //www.aad
aat.://aai055 073.php
Meng Qu and Jian Tang. Probabilistic logic neural networks for reasoning. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8- 8-14, 2019, Vancouver, BC, Canada, pp. 7710-7720, 2019. URL httttps::/procceeddniee htwp://wwweeeednoeeeneeeeeeeeeee wwt.ccppppppp////eeccoo Laceabbb
htmll
Matthew Richardson and Pedro M. Domingos. Markov logic networks. Machine Learning, 62(1- 1007/ 13: 2006. doi: 10.10077/s119944400--58833 URL http::://doi.rroo.
110994-006-8833
Brik F. Tjong Kim Sang and Fien De Meulder. Introduction to the CoNLL-2003 shared task: named entity recognition. In Proceedings of the Seventh Conference on Natural Language Learning, CoNLL 2003, Held in cooperation with HLT-NAACL 2003, Edmonton. Canada, May 31 June 1, 2003, pp. 142-147. Association for Computational Linguistics, 2003.
URL https: /
http://aaaaaaaaaao antho ogy ogy. wwwpttooooooooo//000000000000000
12

---

Published as a conference paper at ICLR 2024
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rat Collective classification in network data. Al Mag., 29(3):93- 106, 2008, doi: 10. 20.160//imag.v22 v29i3. 2157. URL htttt:: /tgp://///o..../////////
org. 10. 1 a aimag. v2913.2151
Parag Singla and Pedro M. Domingos. Discriminative training of Markov logic networks. In The
20th National Conference Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittsburgh, Pennsylvania, USA, pp. 868- 873. AAAI Press / The MIT Press, 2005. URL URL http:hhtp:////tt /tbp:://wwwww aaai wtw.aii.or///.bbb///aaaaa
137. php
Parag Singla and Pedro M. Domingos. Lifted first-order belief propagation. In The Twent--ThindAMMM Conference on Artificial Intelligence, Chicago, Illinois, USA, July 13-17, 2008, pp. 1094-1099. aaai AAAI Press, 2008. URL wttp://wwa..rgg.bbaaaaao.oo /AAT
php
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, Jamuary 27- February 1, 2019, pp. 7975 7983. AAAI Press, 2019. doi: 10. 10.1609/aaai.v3333 33017975. URL https:
otg. 10. 1609 /0/09//aaal.. http:/aaaa.v333003 03111111110 33017975
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 5998-6008, 2017.
Deepak Venugopal, Somdeb Sarkhel, and Vibhav Gogate. Just count the satisfied groundings: Scalable local-search and sampling based inference in mlns. In Proceedings of the Twenty- Ninth AAAI Conference on Artificial Intelligence, Jumuary 25-30, 2015, Austin, Texas, USA, pp. AAAI Press, 2015. URL http: www. aaai www//rg/...ooooooooooooooooooooo winix.idxx..//ii php/ARIIpp/AR SeATi//papee/view////
Martin J.
Wainwright and Michael I. Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 1(1-2):1-305, 2008. doi: 10.1561/ 2200000001.
//to: .rgg 10. 11w.1..111211100001101
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 Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pp. 6019 6026. Association for Computational Linguistics, 2020. doi: 11116665//1/2220.1m111mmm.
485. URL httph:t/t//ooo. http/oiioooogg///// 1tttg/10.18633/1/2000
emn 1p- ma in. 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 information for structured predictor. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, (Volume I: Long Papers), Virtual Event, August 1-6, 2021, pp. 550-564. Association for Computational Linguistics, 2021. doi: 10.18853/v1/2221.1 1.w0022..clllaa acl--loog--.... URL https::/ //op:://dol.
org/ 10. 186518663///0 2020222111200 ac aclaaclllllo 1on...
Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck. A semantic loss function for deep learning with symbolic knowledge. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 5498-5507. PMLR, 2018. URL http://proceedings mlr. http://s.w...p....sseeeessseeeee wwwpp//8///eppppttpppppppp xu www8h.hhh.. htmi
Jun Xu, Weidi Xu, Mengshu Sun, Taifeng Wang, and Wei Chu. Extracting trigger-sharing events via an event matrix. In Findings of the Association for Computational Linguistics: EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11. 2022, pp. 1189-1201. Association for Computa- tional Linguistics, 2022. ptttps://aclanttolooge org. findings-emmn
85
13

---

Published as a conference paper at ICLR 2024
Yiheng Xu, Minghao Li, Lei Cui, Shaohan Huang, Furu Wei, and Ming Zhou. Layoutlm: Pre- training of text and layout for document image understanding. In KDD 20: The 26th ACM Knowledge Discovery and Data Mining, Virtual Event, CA. USA, August 23-27, 2020, pp. 1192-1200. ACM, 2020. doi: 10.1145/394486.4403117 URL https
SIGKDD Conference
77doi oog. 011.....111131111111 340334417434443
Zhun Yang, Joohyung Lee, and Chiyoun Park. Injecting logical constraints into neural networks via straight-through estimators. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICMI. 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 25096-25122. PMLR, 2022. URL v v162 1162/yang22h.hor html
mlr press/
Jonathan S. Yedidia, William T. Freeman, and Yair Weiss. Generalized belief propagation. In Advances in Neural Information Processing Systems 13, Denver, CO, USA, pp. 689-695. MIT Press, 2000, URL httpss://proeeeddng neurips cc/papper/200/hashh 62211555992226615555557702132223
Abstrace att html
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
6kSttH
Shuai Zheng, Sadeep Jayasumana, Bernardino Romera-Paredes, Vibhav Vineet, Zhizhong Su, Dalong Du, Chang Huang, and Philip H. S. Torr. Conditional random fields recurrent neural networks. In 2015 IEEE International Conference on Computer Vision, Santiago, Chile, December 7-13, 2015, pp. 1529-1537, IEEE Computer Society, 2015. doi: 10.1109/CCC22015..77.. URL
14

---

Published as a conference paper at ICLR 2024
Table 5: The used symbols and the corresponding denotations.
Symbol
Definition
the predicate
f
the formula
If A 1
the number of atoms in the formula f the arguments of formula f the arity formula f the ground formula (grounding) the set of observed facts the single ground atom the single variable denote the status of ground atom the set variables w.r.t ground atoms the grounding g the set groundings formula f the set of groundings of formula f that contains the independent umary potential of i with status the collection of unary potentials w.r.t. the potential of formula for Vy the weight formula f the collection of formula weights the set of negations of ground atoms in the grounding g w.r.t f the marginal distribution of variable the grounding message of grounding g the variable the of ground atoms in the grounding 9 except the set variables the collection of marginals of predicate r
g
o
i
V
G5
Gy(1)
(vs)
(v(v+)
(s(r,)
wy
(wy),
nf
Q
Qu.
g-1
V--1
grounding g except
Q
[]
the implication of formula with the atom being the hypothesis the summation of grounding messages w.r.t. the implication [f,
A MEAN-FIELD ITERATION EQUATION OF MLN INFERENCE
Proof. The conditional probability distribution of MLN in the inference problem is defined as:
O(v exp( Σ (u:))) +
Σ JEF
wy Σ (vg)))
(6)
gEG,
p(v(O) is generally intractable since there is an exponential summation propose to proxy variational distribution Q(v) to approximate the p(v[O) by minimizing the KL divergence DKL (Xx)((Q))ll(vv)))) (Iv(())) The proposed Q(v) is an independent distribution over each
denominator. Therefore,
variable, i.c., Q(v) = II, (.(c.) where Eme{o,1 Q.(v:) = Qv,v,) 2 0 is proper probability.
Note that minimizing the KL divergence w.r.t. Q(v) is equivalent maximizing the evidence lower bound of P(O):
(Rr(((v))ll(v(O) EQ(v) log Q(v)
p(v[O)
(Q(v)) log Q(v) [orv)logp(v(0)
Eq(v) log Q(v) logv (aplloggvv..r 0) log (OO)
-[([Q(() log p(v, O) EQ(v) log Q(v)) + p(O).
which is the negative evidence lower bound (ELBO) plus the log marginal probability of which is independent of Q.
15

---

Published as a conference paper at ICLR 2024
Since Q(v) Qr(s), have
Eq(v) log Q(v) ΣΣ Qi(u;) log Qi(w:).
(8)
and
(Qv)) logp(v|()
Σ (u(1)))((1)))) + E
wy Σ (v II log Z,
(9)
fEF gEG,
where Z is independent of Q.
We can therefore rewrite DKL ((L()))lll((v)) with these two equations
L Σ Qi(w)) log Qu( Σ (1)))) -
Σ wy Σ Σ
0s(rg)
I1s) log Z. (10)
N,
JEF BEG, Yo
iEg
Considering it as function of Q:(e;) and remove the irrelevant terms, we have
L, = Σ Qiv..) log Qu(1s)
14
(11)
- ((v))o + ΣNI wy E II (,(0,),
JEF
SEG,(i) Fo
jég-i
where g-z is the ground variables except i in the grounding Gy(i) is the groundings of formula that involve ground atom
By the Lagrange multiplication theorem with the constraint that En, Q2(es) = 1, the problem becomes
arg min C = Σ Qu(ss) log Qi(vs) Q.(e.)
(itt:)lon(s)) + Σ wy Σ Σ
Or Vo-. II 2,(r:) (12)
fEF gEG, Yx-:
jEg-
+ X Σ (1(1:))1 1).
Taking the derivative with respect to Qi(U:), we have de
dQ.(w: = + log Qi(vz) - (on(1:) +
Σ wy ΣΣ Bell Vo II ()(m))+ +A. (13)
SEF (EG Vo-2
jEg-1
Let the gradient be equal to 0, we then have
Q1(v.) (xp().(v:) +
Σ wy Σ Eds(o) II ()(1)))) - A). (14)
fer gEG,())
JE8-1
Taking À out from the equation, we have
Qi(e:) 1 exp(dn(v)) Z
Σ wy Σ
Eo(u vg.) II Q)()))
(15)
FEF (EG
jEg
where Z, is the partition function.
For clarity of presentation, define the message of single grounding (grounding message)
Qi(v;) = 7 exp((n((s) +
Σ ws Σ (v:)))))
JEF
gEG,())
(16)
(v. Σ
(1 vg..) II 2,(1,),
V&
jEg-
Then have the conclusion.
16

---

Published as a conference paper at ICLR 2024
B TERMINOLOGY
Literal. In mathematical logic, literal is atomic formula (also known atom prime formula) or its negation. Literals can be divided into two types: a positive literal is just an atom (e.g.. and negative literal is the negation of atom (e.g.. -l).
Clause. A clause a formula formed from a finite disjunction of literals. clause is true whenever least one of the literals that form is true. Clauses are usually written as (41 (2..... where the symbols 4 are literals, c.g., S(a) A F(a, b) + S(b).
Implication. Every nonempty clause is logically equivalent an implication of head from body, where the head is an arbitrary literal of the clause and the body is the conjunction of the negations the other literals. The equivalent implications of S(a) A F(a, b) = S(b) are (1)
S(a) A F(a, b) = S(b), (2) ((a) A -S(b) = -F(a, b) and (3) F(a, b) A -S(b) = -S(a)
Conjunctive Normal Form (CNF). A formula is in conjunctive normal form is conjunction of one or more clauses, where a clause is disjunction of literals. The CNF is usually written as (4,, 11.2... A (12,1 V 2222...) ..., where the symbols L..j are literals, e.g., (S(a) = C(a))
(C(a) = S(a)).
First-order Logic (FOL). FOL uses quantified variables over a set of constants, and allows the use of sentences that contain variables, so that rather than propositions such as "Tom is father, hence Tom is a man", one can have expressions in the form "for all person æ, if x father then æ is a man", where "for all" is quantifier, while z is argument. In general, the clause and CNF are used for propositional logic which does not use quantifiers. In this work, we denote the first-order clause and first-order CNF with universal quantifiers, respectively.
Ground Expression. A ground term a formal system a term that does not contain any variables. Similarly, ground formula is formula that does not contain any variables. A ground expression is a ground term or ground formula. In this paper, the grounding of formula means assigning values to the variables in the formula with universal quantifiers.
C PROOF OF THEOREM: MESSAGE OF CLAUSE CONSIDERS TRUE PREMISE ONLY
Lemma C.1. (No message of clause for the false premise.) ) When each formula f(;:) is clause, for a particular state v² of a grounding g E Gy( that 3j E g-is VJ Mi the MF iteration of Eq. is equivalent for (vg(vz) Ev Φ5(U Vo 3 Ilie Qz(T;).
Proof. Let us consider a grounding 9" in (i) and grounding message from .², to i and there is a particular state Vy that 3j E g²,,, u3 Mnj. We explicitly extract the grounding message of state Yoz, from the overall potential as below,
Q((v.) = exp(E,(u:)) Σn, exp( (E,):)))
Ea(rs) = -0y(1 voi,in) n)
II 2,(1z) + Ar(ss),
jEg-.
(17)
(,(1)) (o(l)) + Σ
65(n, Vo II 21(r,)
VoL, 22
/Eg
+ Σ wy Σ
Σ
(y V n II Q)(1,))
(1)
Vo-e
jEg-
Since 3j E 0- (1(1, v²=,)= )=
-ne. the clause will always be true regardless of i.e Ve, E (0,1}.
17

---

Published as a conference paper at ICLR 2024
Therefore, grounding message of state Voz, (i.e., O5 Voz, :n) ILsto 2)(1g)) is independent of 04, then
E((r)) = C C C= wy II O)(1ÿ).
(18)
jEgZ:
The potential of C' is eliminated in the normalization step for e = 0 and vi = 1. We can apply the same logic to all the grounding messages and obtain the conclusion: Qi(vi) 7. exp(ou((:) Σ, w (g (wi)), where (v))(e) Evanityg V jeg Q5(1))
0
The proof of the theorem simple by using this lemma.
Proof. By the lemma C.I only one remaining state needs to be considered, i.e., {U; n, heo The potential 15(()) is iff v3 = -n,, otherwise Qi.g(u:) + O. Then we derive the conclusion: Qm())) t
2; exp(< (u;) + E, wy (E)
where Qig(v)) + 1 m===n! II 2,(0, ).
D PROOF OF THEOREM: MESSAGE CNF Σ MESSAGE CLAUSE
Proof. For convenience, let consider grounding g" in G)(i) where in CNF is the conjunction of several distinct clauses fx(:;n5*):
(xp(Fx(1;))
Q.(0e) Σn, exp(Er(v:)))
E((0;) Eds( Voi,)
II Q5(0,) + A(v)),
(19)
Vot
jEg"
A.(v:) = ou(v)) +
Σ wy Σ gEGy(0)3
Σ Es
II 2y(1,)) jEg
f
Vous
Let vk sh. be {nnt) best, i.e., the corresponding true premises of clauses. We have
Er(1:) = Edp(un (i) II
Σ
05(ti, Voz,) II
(,(+)))(())) (20)
jEV 02,
E(v 9"
JEg2,
where the second term can be directly eliminated as the proof of Lemma cases that v is unique not for various k. 9_.
C.I We consider two
Case 1: vk gi
is unique: Since vk is unique, then Φ (15, v = v==nn/u and we can
get the message by the same logic in Theorem 3.1 i.e., w Iliea, Q,(0, = n
Case 2: vk 9"; is not unique: Let v 92, and be the same where h and kn are two fe
g_.
clauses in Since the clauses are unique, ni must be different with n, The two potentials are eliminated, which is equivalent to the summation of distinct messages, i.e., Σk, mo:= N Q5(ız = n
We can apply this logic for all possible groundings and obtain:
Qi(1a) < Z, exp()u((vs) + Σ wy Σ @ng(v;)),
1
/ gEG,(1)
where Qig(t:) < Σt mn== I 25(13 = ne), i.e., E,, 1 mn Ilee. 22(t; = ny).
17
18

---

Published as a conference paper at ICLR 2024
This theorem directly leads the following corollary. Corollary D.1. For the MLN, the mean-field update w.r.t. CNF formula is equivalent to the mean-field update w.E.. multiple clause formulas with the same rule weight.
E EXTENSION OF MULTI-CLASS PREDICATES
typical MLN is defined over binary variables where the corresponding fact can be either true or 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 binary predicates to describe the category of paper by checking whether the paper is of a certain category. However, the categories are typically exclusive, and combining them can ease model learning. Therefore, we extend LogicMP to model multi-class predicates.
Formally, let the predicates be multi-class classifications r(-) C.... x CC- + {0, [.... with 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, a multi-class formula about "RL paper cites RL paper" be expressed as
(21) where (a)el(x) RL means is RL paper. Sometimes the predicates in the formula appear more than one time, e.g., label(x)) E { [ML] V (a)el( E {RL)... We should aggregate them into single literal label(x)) E 2, 2 = {RL, MLJ. A clause with multi-class predicates is then formulated as ... V (e. E 2,) V where 2 is the variable associated with the atom è the clause and Z, denotes the possible values the predicate can take. With such notation, we rewrite the clauses with multi-class predicates as {;; 2 where 2 = (2 . We show that the message of the multi-class clause be derived by the following theorem.
label( E {RL} V cite(z, y) = label(y) E {RL),
Theorem F.1. When each formula with multi-class predicates (1) a clause, the MF iteration of Eq. 2 is equivalent for (:(r;) = 1,,z,, Il E2,Ez, Q,(u,)
As the derivation similar that of binary predicates, we omit the detailed proof here. By setting 2 = { } in the binary case, we can see that the message with multi-class predicates becomes the one with binary predicates. Similarly, when the formula is the CNF, the message can calculated by aggregating the messages of clauses.
F PARALLEL AGGREGATION USING EINSTEIN SUMMATION
The virtue of parallel computation lies in the summation of the product, i.e., Egeay()) Il (5(y n2)) by Theorem 3.1, which indicates that the grounding mes- sage corresponds to the implication from the premise g-i the hypothesis i. By the structure of MLN, many grounding messages belong to the same implication and have the calculation symmetries, group them by their corresponding implications. The aggregation of grounding messages w.r.t. an implication amounts to integrating some rule arguments and we can therefore formalize the aggregation into Einsum. For instance, the aggregation w.r.t. the implication S(a) F(a, b) = S(b) can be expressed as einsum ("a, ab + b", (1), Qx(1)) where Qr denotes the collection of marginals w.r.t. predicate r, i... Qv,
(CF(A))) (A, is the arguments of r). Fig. illustrates this process, where we initially group the variables by predicates and then use them to perform aggregation using parallel tensor operations. The LogicMP layer on the right of Fig. G detailed depiction of the mechanism, where 3 clauses generate 7 implications and each first-order implication statement is transformed into an Einsum operation for parallel message computation. Einsum also allows the computation for other complex formulae whose predicates have many arguments.
G EINSUM EXAMPLES
Einstein summation is the notation for the summation of the product of elements in list of high-dimensional tensors. We found the aggregation of grounding messages w.r.t. an implication
19

---

Published as a conference paper at ICLR 2024
Grounding Message
LogicMP
Mesagge w ppentre- -SAL R.
Jweein JJ -w--v--- N/V
Sewcal liggt te Re
Skat
Zibi
Lefti Sequential Grounding 0-
JUy
RR
For
duc
Righht: Paraaln Parallel
-ww.tii D011
QC-
Q-1
Pu
Figure 6: We illustrate the LogicMP for a Markov logic network (MLN) with two entities {A, B). predicates F (Friend) and S (Smoke) and (Cancer), and formulae fi (a, == -S(a)v-F(a, bSbb)) f2(a) = (-S(a) V C(a)) A (S(a) V -C(a)). Left: Vanilla mean-field implementation performs sequential grounding. Right: We expand the MLN inference into several mean-field iterations and each iteration is implemented by layer of LogicMP. The red "Grounding Message" block illustrates the message w.r.t single grounding: the message from S(A) and F(A, B) w.r.t. (A, B) can be simplified as the product of their marginals Q5(4) FF) (1) (see Sec. 3.1 We then formulate message aggregation via the parallel Einstein summation (Einsum)(see Sec. 5.2p Specifically, the ground atoms are grouped by the predicates the basic units of computation (the gray border denotes the values of -). The initial marginals are obtained from distinct evidence. each iteration, the layer of LogicMP takes them as input and performs Einsum for each logic rule (shown in the "LogicMP Layer" block). For each implication statement of the logic rules, Einsum calculates the expected number of the groundings that derive the hypothesis. The outputs of Einsum then used to update the grouped marginals. Such procedure loops for steps until convergence. Note that f2 is in CNF and its two clauses be treated separately. The Einsum also applicable for predicates with more than two arguments. The update takes several updates to converge.
20

---

Published as a conference paper at ICLR 2024
can be exactly represented by an Einstein summation expression. Notably, Einstein summation be efficiently implemented in parallel via NumPy and nowadays deep learning frameworks, e.g., PyTorch and TensorFlow. The corresponding function is called einsum which can be effectively optimized via a library opt_et nm We list several cases of message aggregation in the Einstein summation format and their optimal simplifications via dynamic argument contraction. Deriving the optimal solution is an NP-hard problem, but for the practical formulas whose argument size (i.c., arity) less than 6, the solution can be obtained within milliscconds. For all the formulas in the tested datasets, the number of arguments is less than 6.
Formula: R. (h, (2(,, A Ra(s, 8) (o(
Original: K einsum ("kk, kj.ji - Qu (1), Que (1); Qua (1))
. Optimized:
-K einsum (Kkj.jj ki", Que (1), Qs)
K einsum (hh,, ki Qs. (1), K)
Formula: Ra (), k) A Be A Rs(j A Ba(h) + Ri(i)
Original: K
siinsum""hl kj. ji, (1), (1).
Optimized:
K einsum eiissum"kj.jjr ("jjjj ki", (1), (x)
K + cinsum cinsumm"hk, h, ki Qa, (1), Qu (1)
Formula: R. (p, i) Rr Ba R. (r. A (s, (o(p.grr.))
Original: K eineum("Pp pr, , qj sjkl, rk, al - pqrs", Qu (1), (1), (1), Qa. (1), Qa(1)
Optimized:
K < einsum ("pi, ijkl + pjkl", Qu, (1), Qa (1))
K einsum "Qi. + pqkl", Qa, (1),
K einsum ("rk, pykl pqrl", Qn, K)
K einsum einsum("sl, pqrl pqra", Qa, ())
We also show several cases that cannot be optimized, as follows.
Formula: (a) A (2 b) (b)
K einaum ("a, ab 8" Qs. (1), (1))
Formula: R. (a, b, c, d) Ra A Ra(c, d) A (a d) + Ro(a,e)
K + einsum("abell be, ed, ad ac", Qa. (1), Qn (1), Qa. (1), Qu,
Formula: R, (a, b, e) (2 (a b) (a d) Ro (a, c)
* K + einsum("abe, bod, cb, ad + ac", Qa (1), Q (1), Qu Q.)
One may notice that the current implementations of the Einsum function are not available when the target matrix has external arguments that are not in the input matrices, e.g., "a - ab", We tackle this by a post-processing function for the output of Einsum.
H COMPLEXITY OF OPTIMIZED EINSTEIN SUMMATION
The optimized Einsum is of complexity O(N'') where M' the maximum number of arguments in the sequence of argument contraction operations. The optimization of Einsum, i.e., the summation of the product of list of tensors, is equivalent to a classical problem in probabilistic graph modeling, i.c., the variable climination in the summation of the product of the potentials. Each step of Einsum after the optimization contracts the rule arguments in the expression, which amounts to step of the variable
21

---

Published as a conference paper at ICLR 2024
Table 6: possible world (assignment of variables) of MLN.
Pa(a)
(r(4.4)
Mo(4)
hinary value
Table 7: An example of variable marginals.
(1)
Qrca,a)(1)
Qria,
(x
Qaaa)(1)
continuous value
0.92
0.97
0.13
0.95
0.03
0.99
elimination in the message passing. Even though, the goal of Einsum in LogicMP, which functions on the level of logical groundings, differs greatly from the original message-passing passing algorithms, which function on the standard (directed undirected) probabilistic graphs. By formulating the optimization of Einsum as variable elimination algorithm, we can see M' also equals the maximum cluster size of the junction tree constructed the variable elimination. We define the junction tree for Einsum of LogicMP as:
Definition H.1. Given the Einsum expression in LogicMP, a junction tree of LogicMP is tree T(V E) in which each vertex v E (also called a cluster) and edge e E are labeled with a subset of formula arguments, denoted by L(v) and L(e) such that: (i) for every atom defined in Einsum, there exists a vertex L(v) such that A, L(v) and (ii) for every argument æ in the Einsum expression, the set of vertexes and edges in T that mention form connected sub-tree in T (called the running intersection property).
previous study (Venugopal et al. 2015) proposed to count the true groundings in MLN by formulat- ing constraint satisfaction problem (CSP). In contrast to counting the true groundings, the Einsum calculates the expected number of groundings that derives the hypothesis (i.e., true premise) over the marginal distributions of the ground atoms. It is in principle different from previous methods since our approach is theoretically derived from the mean-field algorithm. More importantly, Einsum is a parallel tensor operation that brings computational efficiency and enables LogicMP to be an effective neural module. By using Einsum, MLN inference can be expressed as an efficient parallel NN.
I AN EXAMPLE TO ILLUSTRATE THE LOGICMP ALGORITHM
Let's take the Smoke dataset example. The predicates smoke(x) (S(z)). friend(x, y) (F(x, v)) and cancer(x) (C(z)). The observations O are two facts, i.c., F(B, A) = true and C(B) true. The unobserved variables are (s(A), (B( UF(A.A): UP(A.B) UF(B, Vc(A4). Each variable U, e.g., Us(4)) {0, 1). is binary discrete variable. An assignment to these variables corresponds to world. possible world in MIN shown in Table
In variational algorithm, LogicMP mitigates the problem of counting exponential worlds by updating in the single world of approximate marginal probabilities of ground atoms where einsum is used calculate the expected number of all possible true premises. Each variable v; represented by a marginal probability Q+(v:) E [o, 1]. e.g., @s(A) (1) = 0.92 (Qs(a)(O) 0.08) denotes that the marginal of probability of S( (A) being true is 0.92 (0.08 for false). The marginals may be as shown in Table 7
The mean-field update is computed by these 6 marginals via Proposition 3.2 which updates new marginals of variables conditioned on the current marginals of variables. We illustrate how our algorithm updates the marginals of S(A) and S(B), i.e., Qs. as follows. They receive messages from 4 implications statements and we calculate them via einsum as illustrated in Table The updated marginals are:
wie + (1()) = we wyes) (0) exp (0) + + wye)) ZZs /ZZ
where Zg = (ssp(2s(1 + wte + W263) - exp + w) + W2ea), w; the rule weight, all computations based on the marginal probabilities of ground atoms, i.e, Qis.
22

---

Published as a conference paper at ICLR 2024
Table Illustration of the Message Calculation. EN indicates the expected number.
implication
einsum
variational appruximation
S(e) A (ar, v)
8(y)
=ensumm xx, ay y². Qs(1). Q+(1))
EN of the true ground premises ((x) A F(x,
BB()) A ((2. = (8(x)
-cinsum( y, 23 - dt, 1- Qa(I), Q+(1))
EN of the true ground premises (3()) A F(a, M)
((2) 8(x)
=cinsum(" "x Qc(1))
EN
ground premises C(x)
0()) = -5(x)
-einsum(" "x - xx.1 Qn(1))
EN of the true ground premises -C(x)
J MORE RESULTS ON VISUAL. DOCUMENT UNDERSTANDING
J.1 GENERAL SETTINGS
The experiments conducted on basic machine with 132GB V100 GPU and Intel E5-2682 v4 CPU at 2.50GHz with 32GB RAM. The dataset consists of 149 training samples and 50 test samples. A sample consists of an input image and sequence of tokens with their corresponding 2-D positions. The number of tokens may be larger than 512. The tokens are segmented into several blocks and each block belongs to a category out of "other", "question", "answer", "header". The goal of this task is to segment the tokens into blocks and label each block correctly. Specifically, given the image document with image pixels and tokens from OCR (e.g., an image document with text "Date: February 25, 1998 ... CLIENT TO: L8557. 5555.002.... ..."), the goal is to segment the tokens into blocks (e.g.. "Fehruary 25, 1998" should be segmented into one "answer" block). The maximum token count is 512, and each token has an ID ranging from 0 to 511 (e.g., the ID of "February" is 2, and "25" is 3).
J.2 DETAILS OF OUR METHON
We formalize this task as matrix prediction task with reference to previous work (Xu et al. 2022). The model framework is shown in Fig. / takes image pixels and tokens as input, and outputs the predictions about whether pairs of tokens coexist within a block. Let denote the coexistence predicate and C(a, b) denote whether tokens a and cocxist. The model needs to predict all (C(a,b)) (a.b) which forms matrix. A matrix with ground truth is shown in Fig. 8b
Specifically, data sample consists of n input visual token entities {ei,..., eN.. We adopt the LayoutLM (Xu et al., 2020), which is powerful pre-trained Transformer with visual and text inputs, as the backbone to derive the vector representation of cach token, i.c., V E Nxd where N is the number of token entities and d is the dimension of vector (768). Then we apply two linear transformation layers map V to V and V as rows and columns. The similarity of V and V captured by their dot multiplication, is used as the unary potential, i.e., p. (V)(a.8))- A data sample also manually annotated with blocks containing tokens. We convert the blocks into target matrix of coexistence Y. E {0, N
Independent classifier takes 4,, input and outputs the prediction via a Sigmoid layer over + (v)t..))) The independent classifier often yields conflict predictions (Fig. Sch but we can constrain the output via the transitivity of the coexistence. Intuitively, when tokens a and b coexist and tokens b and e coexist, tokens and must coexist. Formally, we denote the predicate of the matrix as C and the FOLC is Va, b, C(a, b) A c(b.c) c) = C(a,c). c). LogicMP applies this FOLC to this matrix prediction to constrain the output. This rule should be effective considering that the distant tokens are not easily predicated but can be inferred by the coexistence other closer and easier pairs. The entire model is trained to minimize the cross-entropy between the prediction and the labels, using the Adam optimizer with learning rate of 5e-4.
J.3 AC COMPILATION
Both SL and SPL rely on the AC but AC compilation will fail in this task. Although specific first-order logic (FOL) rules can be effectively compiled into ACs, such as those liftable queries under the Big Dichotomy theorem (Dalvi Suciul 2013). the transitivity rule falls into the category where the compilation is intractable. Specifically, the AC compilation time consumption is shown in Table The table shows that the compilation time is exponential in the sequence length. Once the sequence length reaches 8, the compilation time becomes unreasonably long. In contrast, LogicMP is capable
23

---

Published as a conference paper at ICLR 2024
Syout
LogicMPP
@
Figure We adopt the LayoutLM (Xu al., 2020 as the backbone which derives the vector representation of each token V and V The matrix 4, is predicted by dot-multiplying every pair of V and V LogicMP applies the FOLC this matrix prediction 2, to constrain the output.
Table 9: The compilation time AC for transitivity rule w.r.t. sequence length.
sequence length
#variables
#clauses
compilation time (s)
5
25
125
0.38
6
36
216
11.1
7
49
343
135.7
8
64
512
6419.2 (1.78h)
9
81
729
>24h
512
262K
134M
of performing joint inference to update all 262K variables for a sequence length of 512 in just 0.03
seconds.
J.4 PSEUDO CODE OF LOGICMP FOR TRANSITIVITY RULE
The implementation of LogicMP for the transitivity rule is quite simple which only consists three different tensor operations. The pseudo PyTorch-like code is shown in Algorithm We can use few lines of code to integrate the transitivity into the logits derived from the encoding neural network. The computation overhead is small as it only involves dense tensor operations. It is also worth noting that the FOLCs can be automatically transformed into the update code by parsing the rules, thus allowing general logical FOL language for integrating LogicMP easily.
Algorithm 2 PyTorch-like Code for LogicMP with Transitivity Rule
logits: terch. Tensor, niterations: int, number of iterations
[batchsize, nentities, nentities, 2]
cur cur_logits- logits.clone ()
for in range (niterations):
Q softmax (cur (cur_logits, dim=-i) cur logits = Logits.
It Message Aggregation for Implication Vo, b, C(a, b) ((b,,)) = C(a,
msg_to_ac einsum kabkkkb kbc->kac', Q[...,1,, Q Q[...,1])
11]
Message Aggregation for implication b, b) -((acc) -c(b,o)
msg_to bc einsum ( kab, kac->kbe', Q(..., Ql...,
Message Aggregation for Implication Va, b. msg_to_abs einsum (1 kac->>abb Q 2]. 01)
= -C(a,)
msg msg_to_ac + msg_to_bc msg_to_ac cur_logits += msg weight Returns cur_togits
24

---

Published as a conference paper at ICLR 2024
Input Image
(b) Ground Truth
(c) LayoutLM
(d) SLrelax
(e) LogicMP
Figure 8: The visualization of an example that LogicMP can successfully incorporate the FOLC.
(a) Input Image
(b) Ground Truth
(c) LayoutLMM
(d) SLrelax
(e) LogicMP
Figure The visualization of an example that LogicMP can successfully incorporate the FOLC.
J.5 MORE VISUALIZATION
We illustrate additional three examples in Fig. and In these figures, the output using independent softmax layer will produce incoherent predictions. i.c., the output is not series of rectangles. Note that the rectangle structure be inferred from the predictions of other pairs via the transitivity FOLC. LogicMP can successfully integrate the FOLC to regularize the output as shown in the figures. This FOLC indeed has three meanings: (1) Ya, c C(a, b) A C(b, e) = C(a, to enhance the probability of being pair iff C(a, ()b,,,, c). (2) b, c, C(a, b)Λ b))-C((, C(a,c) - C(b, decrease the probability of being pair iff C(a, b) C(,, (3) Va, b, -(aa c(b,
-C(a,b) b) to decrease the probability of being pair if -C(a, c) A C(b,c) c). LogicMP performs the logical message passing for all three implications and therefore, has the capacity both (1) remove low-confidence token pairs and (2) fill the missing token pairs.
K MORE RESULTS ON COLLECTIVE CLASSIFICATION
K. PREDICTION TASKS
There are several predicates each dataset. the Kinship dataset, the prediction task is 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, a person can be deduced as male by the fact that he is the father of someone, and the formula expressing father male. In the UW-CSE dataset, to 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 SameTi tle b). The dataset is also split into five
need
(a) Input Image
(b) Ground Truth
(c) LayoutLM
(d) SLrelax
(e) LogicMP
Figure 10: The visualization of example that LogicMP successfully incorporate the FOLC.
25

---

Published as a conference paper at ICLR 2024
subsets according to the field of research. Note this is not the Cora dataset (Sen al. 2008 typically for the graph node classification.
Statistics. The details of the benchmark datasets are illustrated in Table
Table 10: The details of the benchmark datasets.
#ohserved fact
#ground atom
Aground formala
Dataset
Hentity
#predicate
Aqueer
Kinship/S1
15
187
38
50K
550K
Kinship/S2
110
15
307
62
158K
3M
Kinship/S3
Kinship/S4
221
15
723
150
635K
25M
Kinship/S5
266
920K
39M
UW-CSE/AI
300
22
731
4K
V5K
73M
UW-CSFA angunge
82
22
182
IK
15K
9M
UW-CSE/Systms
277
5K
95K
121M
/W-CSE/Theory
174
22
465
2K
51K
54M
Cora/S2
602
10
9K
2K
156K
431B
Cora/S3
607
3K
438B
Cora/S4
600
10
12K
2K
160K
435B
Cora/S5
600
11K
2K
140K
339B
K.2 DATASET FORMULAS
We show several logic rules in the datasets in Table The blocks each of which contains rule examples correspond to 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 see from the table that all the logic formulas are CNF. Note that some formulas contain fixed constants such as "Post_ Quals" and "Level_100" and should treat them arguments.
Table 11: Several logic rules in the datasets.
First-order order Logic Formula
#Predicates
-anokefe] V -friendie, aboke(b)
-Bnoke(e] (e) cancer(e)
2
snokela) -ccancerio)
2
.frriend(a,a)
1
-friend(a,h) (riend(a,
"feeale((x) /ebbilddy..r) V mether((s.))
3
"male(ar) V -child(g Vatherr(s
-fenale(xx) me, g) daughter(s,g) -male(x)) -child(2..) son(x.y)
-male(z) -Fenaleee))))
2
staughtay((.p:.)) Saanghhti(caal---moooooooeeeeerr Lavel 800) (ttalessg)) advisedRy(s, tenpAdvisedBy(s.p)
publicatiom(p.zz) publicationipp.)) student(ir) student(g) advisedBy(r..)) wanaaarrieddddddlldaooo..
"inPhase(s, Post Post_
V -aughtByle, v -ta(s, 4, g) couresLovel(c.evee.
advisedBy(s.p)
student(r) Vavvisddyyur..p sedpAddrseddB(f.
"publication(l.a) wwwpo:/awbuapp..aa.p.aoa.aaaaaee
sazePerson(e, (a 6) advisedByla, b) advisedBy(b.a)
AAthhor (bel, ( (w2thorr((2
#bawoorduuhhrrall..o 4w)) 4askordd4tthrr(e2 +w)) SancBib(Del b(kel, (e2)
5
Abuthor(bel..d
al) (bel, -Authorr(eee x2) HaaVordkuthor (al 4w) -taeeorkkkthoooiee +ac) SaneBib(ben (el, be2)
5
-Fitte(bel, V -Tittla(be, (2) #asworddsstal(
#ankordfittee +or) ManeBib(ke)
Title(bel,A]) V Title(br2, (2) HarkordTsslel(.. (il MaskerddTitle(22 +wo) SaneBib(kel. be2)
-Venue(bell 1, -Vemuelbk2,
#hskordVamme(rl, V 4w) SameRihhleel,
K.3 GENERAL SETTINGS
The experiments conducted basic machine with 16GB P100 GPU and an Intel E5-2682 v4 CPU at 2.50GHz with 32GB RAM. The model trained with the Adam optimizer with learning rate of 5e-4.
26

---

Published as a conference paper at ICLR 2024
Joint Prediction (UAY,)),
LogioMP
Posteriox Regularizaion
Encodingg Network:: Expresatiii
Varianles:
Figure 11: 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 encoding network. Specifically,, we are given a set of variables v. The encoding network takes the variables as input and output scores & as the unary potentials of variables. Then the unary potentials are fed into the LogicMP layers to perform MF inference derive updated marginals Q. They in turn become the targets of the encoding network through the distillation loss. The dotted line means no gradients in the back propaaprpaattion.
K.4 DETAILS OF OUR METHOD
Fig. 11 ggives an illustration of our approach. In the figure, LogicMP is stacked upon an encoding network with parameters 0 to take advantage of both worlds (the symbolic ability of LogicMP and the semantic ability of the encoding network). The encoding network is responsible for estimating the unary potentials of the variables independently. Then the LogicMP layers take these unary potentials to perform MF inference which derives a more accurate prediction with the constraints of logic rules. The outputs LogicMP layers then become the targets of the encoding network through distillation loss for better estimation. In this way, logical knowledge can be distilled into the encoding network. Note that LogicMP in this process only performs inference without any learning. Intuitively, the encoding network is responsible for point estimation, while LogicMP gives the joint estimation via symbolic reasoning. LogicMP helps to adjust the distribution of the encoding network since the output of 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 (Ganchev ett al., 2010) as follows. Specifically, the posterior regularization method derives another target distribution h(v) by minimizing Dx (poov))) with the prior constraints & from the logic rules. The optimal h(v) can be obtained in the closed form: h(v) po(v(O) exp(Xx(v O)), where A is haper-parameter. When the constraint Φ(v, O) = EsEF W Egec, Φ5(V,) (Markov logic) and po(v]O) ~ exp(E, (u 0)) (encoding network), we have h(v) ~ exp(E, ou (o;; 8) A ESer Wy y (Vg)) which is equivalent to our definition in Eq. We want to distill h(v) to (o())O). Following the work (Wang et al. 2021), we calculate the marginal of target distribution for each variable (x(r,) via LogieMP and distill the knowledge by minimizing the distance between local marginals and unary predictions, i.c., L = Σ, (Qx() Pe(u,(O), where I is the loss function selected according to the specific applications. In the implementation, we use the mean-square error of their logits.
Proposition K.1. The variational E-step training and posterior regularization with LogicMP (T = 1) have the same learning objective.
Proof. Simple proof can be obtained by investigating the gradient of each ground atom. In
the VIEM method, the posterior probabilistic distributions of ground atoms (denoted as (v))))
are independent and the learning objective is to maximize the total MLN score of groundings ΣS wy EgEG, Ev, Ev,0)(v))
Σ, wy Egeg, Ev, øy (v,)) I (v,) (see Eq. 4 in (hang et al.] 2.20)). Take single grounding as an example, the gradient of Qi w.r.t. a grounding g Eo,, (v..) 2,(%))
Combining all groundings together, the gradient becomes a Er My E Enp (e)))) Ibc._, Py(o,)
0Q.(0.)
E, Wy Eyea, Ev, (r(v,) ()(r;) is exactly what each meeldfieeld update computes for each ground atom. With a single iteration, we have the conclusion.
(Q.(v.)
27

---

Published as a conference paper at ICLR 2024
fienolx.y) 6
droup"1
frien((xy) Group
Smokes
Cancer
Smokes
Cancer
Figure 12: Facts (top) and predictions (bottom) on the Smoke dataset for the true/false facts).
knop
1.45
337
8.00
3350
33
3325
nusma
335
6.00
Figure 13: The ablation results on three datasets.
Despite the theoretical equivalence, the implementation with LogicMP practice is much more scalable due its parallel computation and thereby permits more training within reasonable time, leading to significant performance improvement. Besides, LogicMP allows performing multiple iterations obtain more precise gradient which also brings performance improvements.
K.S MORE EXPERIMENTAL RESULTS
Smoke dataset. Smoke is example dataset for sanity check and Fig. shows that the correct results can predicted.
Ablation on the number of iterations. Fig. represents the ablation results w.r.t. the number of iterations on the Kinship, UW-CSE, and Cora datasets in detail. The results show that the performance improves consistently when using multiple LogicMP layers, and it keeps stable when we further stack the layers. This is reasonable as the MF algorithm typically converges to a stable state within several steps. LogicMP takes few steps converge and layers lead to more computation, we observed little computational overhead with multiple stacks of LogicMP layers due the parallel implementation.
empirically set T 5. Although more
Inference efficiency. We show the inference time of the methods on UW-CSE in Table 12 under OWA. The methods except for ExpressGNN w/ GS and ExpressGNN w/ LogicMP CPU due the inefficiency of GPU implementation. For ExpressGNN w/o LogicMP, the encoding network is GNN that can be computed in parallel while its learning from MLN is inefficient as the groundings are obtained sequentially and the computation is expensive when consuming groundings. We can see that LogieMP achieves better inference speed than the competitors. Fig. shows the learning curves of LogicMP variations and ExpressGNN w/ GS. LogicMP w/o Opt denotes the LogicMP without the optimization for Einsum. LogicMP w/o OptEinsum++Partete implemented without parallel Einsum and performs the aggregation sequentially, LogicMP w/o also omits the technique to remove the expectation calculation in Sec. 3.1 Comparing them with LogicMP, the parallel Einsum brings evident acceleration and other improvements also improve the efficiency. Note that the Einsum optimization is almost free as it can be done in advance within milliseconds for argument size (the maximum arity is 6 in the tested
denotes that the LogicMP
AppEinsum--Parallel---ee
28

---

Published as a conference paper at ICLR 2024
Table 12: Comparison of inference time on UW-CSE. Better results are in bold.
Inference Tine (minules)
A
S.
T.
avg.
MCMC
>24h
>24h
>24h
>24h
>24h
>24h
BP
408
352
37
4.57
190
289
Lifted
270
525
278
MC-SAT
172
147
14
196
86
123
HL-MRF
135
132
18
178
72
107
EXpressGNNN w/ GS (16K)
14
20
13
12
ExpressGNN w/ LogicMP (168)
<1
<1
<1
EXpressGNN w/ GS (20M)
>24h
>24h
>24h
>24h
>-4hh
>24h
EXpressUNN w/ LogicMP (20M)
64
70
datasets). On Cora, the efficiency keeps similar to UW-CSE while the other MLN methods fail to complete within 24 hours.
Laycer led wow. Parte
02
200
Figure 14: The AUC-PR learning curves w.r.t. minutes of LogicMP variations and VIEM.
29


Reviews:
[{"review_id": "ptNddcKPIS", "reviewer": "Reviewer_svJm", "summary": "The paper proposes a novel neural layer, called LogicMP, which can be plugged into any off-the-shelf neural network to encode constraints expressed in First Order Logic.", "questions": "See above.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "Relevance: \n\nThe paper deals with a very important problem that is of interest to the larger AI community. \n\nNovelty: \n\nThe paper introduces a novel layer. However, it fails to acknowledge other works that have integrated logical constraints into a neural network layer. Among the most relevant we find: \n- Nicholas Hoernle, Rafael-Michael Karampatsis, Vaishak Belle, and Kobi Gal. MultiplexNet: Towards fully satisfied logical constraints in neural networks. In Proc. of AAAI, 2022.\n- Eleonora Giunchiglia and Thomas Lukasiewicz. Multi-label classification neural networks with hard logical constraints. JAIR, 72, 2021.\n- Tao Li and Vivek Srikumar. Augmenting neural networks with first-order logic. In Proc. of ACL, 2019.", "weaknesses": "Clarity: \n\nOverall, I found the paper not very readable, and I think the authors should try to give more intuitions. \nSee below for some questions I had while reading the paper.\n\n- While the authors included an overview of Markic Logic Networks there are still some concepts that look a bit obscure. What does the weight associated with each formula represent? Is it a way of representing the importance assigned to the formula? Why do the authors need the open-world assumption? When explaining the MLNs, can you please add an example with: (i) an ML problem, (ii) what would the FOLC be in the problem, and (iii) what would be the observed and unobserved variables in the problem. \n\n- What does it mean that $Z_i$ is the partition function? Over what? \n\n- I am not sure how to read Table 1. Same applies for Figure 3.\n\n- How is it possible that the complexity does not depend on the number of formulas $|F|$? \n\n- Finally, are the constraints guaranteed to be satisfied or they are just incorporated?", "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": "", "extra_scores": {}}, {"review_id": "K1cFe2BIrJ", "reviewer": "Reviewer_XeZX", "summary": "A scalable inference method is proposed for MLNs using neural networks. The main idea is to use Mean Field iterations to perform approximate inference in MLNs. Further, since this relies on sending messages in a ground MLN which can be very large, messages are aggregated across symmetrical groundings to improve scalability. It is shown that this can be formalized using Einsum summation. The advantage with this approach is that the messages can be computed through parallel tensor operations. Experiments are performed on several different types of problems and comparisons are presented using state-of-the-art methods", "questions": "How does evidence affect Einsum computations? Does it break symmetries making it harder to parallelize?\n\nThere has been studies in databases regarding width of a FOL (Vardi)  (e.g. in a chain formula, the width is small). This has also been used to scale-up inference using CSPs (Venugopal et al. AAAI 2015, Sarkhel et al. IJCAI 2016). Would this be related to Einsum optimization?\n\nIn the experiments were the weights for the MLN formulas encoded by LogicMP learned (it is mentioned in one case that the weights was set to 1). How do these weights impact performance?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The use of Einsum to aggregate and parallelize ground MLN messages in MF seems to be a novel and interesting idea for scaling up inference through neural computations.\n- The experiments seem extensive and are performed on a variety of different problems showing generality of the approach", "weaknesses": "- In terms of significance, there has been a long history of work in lifted inference with the same underlying principle of using symmetries to scale-up inference in MLNs. One of the key takeaways from such work (e.g. Broeck & Darwiche 2013) is that evidence can destroy symmetries in which case lifted inference reduces to ground inference (if guarantees on the inference results are required). Here, while the approach is scalable, would the same problem be encountered. In the related work section, it is mentioned that for earlier methods, “The latter consists of symmetric lifted algorithms which become inefficient with distinctive evidence”. Does this mean that LogicMP does not have this issue? While the neural approximation can scale-up, I don’t know if there is a principled way to trade-off between quality of inference results (due to approximation using einsum) and scalability. The experiments though show that using LogicMP in different cases yield good results.", "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": "", "extra_scores": {}}, {"review_id": "IVHwTpvF8q", "reviewer": "Reviewer_RzRh", "summary": "The paper proposes a mean-field variational scheme for inference in Markov Logic Networks. The corresponding message passing scheme exploits some structure of the formulas and a tensor operation to speed-up a naive mean filed approximation.", "questions": "1) The paper mentions FOLC but it never defines them. All the examples, though, are definite clauses. Are non-definite clause supported? If yes, are you employing them in your experiments?  \n\n2) Is there an impact in the size of the observed / non-observed split? Usually, there is a great imbalance between the two and it is not clear to me how this may impact the message passing / the pruning of messages.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "The technique is sound and the paper is generally well-written. \nExperiments are diverse.", "weaknesses": "The novelty of the paper is limited and cannot be assessed from the current paper. This is a major weakness,\n\nThe paper fails in positioning in the wider field of neuro-symbolic AI.\n\nThe paper claims to be the first method capable of encoding FOLC (pag. 2, “Contributions”). This is not true. The authors themselves cite ExpressGNN. However, there are many other papers attempting at this. I will cite some here, but many more can be found following the corresponding citations: \nDeep Logic Models, Marra et  al, ECML 2019 \nRelational Neural Machines, Marra et al, ECAI 2020 \nNeuPSL: Neural Probabilistic Soft Logic, Pryor et al, 2023 \nDeepPSL: End-to-End Perception and Reasoning, Dasaratha et al, IJCAI 2023\nBackpropagating Through MLNs, Betz et al, IJCLR 2021  \n\nMany of these systems have CV and citation networks experiments.", "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": "", "extra_scores": {}}, {"review_id": "hQAYFGs8Mw", "reviewer": "Reviewer_9vvz", "summary": "The paper introduces LogicMP, a neuro-symbolic method designed to efficiently integrate first-order logic constraints (FOLCs) into neural networks. LogicMP performs mean-field variational inference over an MLN, and its computation is paralleled by leveraging the structure and symmetries in MLNs. The authors demonstrate the effectiveness and efficiency of LogicMP through empirical results in various domains. The results show that LogicMP outperforms the baselines in both performance and efficiency.", "questions": "- What is the expressiveness of LogicMP? Can it encode any quantifier-free first-order logic formula? Additionally, the notation in the first paragraph of Section 2 is somewhat confusing. For instance, is a specific structure required for $f$? In other words, should $f$ be represented in the form of a disjunction of logical atoms? Moreover, is the logical atom $\\mathtt{C}(e_1, e_2)$ a general form to represent any relation between $e_1$ and $e_2$?\n- Why not directly solve problem Eq.1? In problem Eq.1, we can perform the weighted counting in a parallel manner, rather than using sequential generation as required when solving problems Eq.2 and Eq.3. Moreover, quite a few techniques in fuzzy logic can efficiently handle the discrete potential function $\\phi_f(\\cdot)$, such as translating the disjunction into the product or the minimum.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-motivated and easy to follow.\n- Using Einsum notation to formalize the message aggregation of first-order logic rules is very interesting.\n- The performance of the proposed method is better than previous work.", "weaknesses": "- Although LogicMP focuses on encoding FOLs into neural networks, it cannot handle existential quantifiers, which significantly limits its applicability.\n- The evaluation appears somewhat limited. Firstly, it only compares 3 neuro-symbolic baselines (SL, its variant SLrelax, SPL). These methods compile the constraint into a probabilistic circuit and then perform exact inference. Given that LogicMP performs approximate inference, comparing it with methods using exact inference seems somewhat unfair. Indeed, some other works encode the constraints and perform efficient approximate inference [1,2]. Lastly, since most previous work encodes propositional logic into neural networks, a more comprehensive evaluation on these previous benchmarks would enhance the paper's comprehensiveness and validity.\n\n[1] DL2: Training and Querying Neural Networks with Logic\n\n[2] Injecting Logical Constraints into Neural Networks via Straight-Through Estimators", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)