Fast Algorithms for Relational Marginal Polytopes

1 Introduction

We study the construction of relational marginal polytopes [Kuzelka et al., 2018], which are objects that naturally arise in the study of Markov logic networks [Richardson and Domingos, 2006] and other statistical relational learning models. Informally, given first-order logic formulas α1, α2, . . . , αk, which may contain free variables, and a set of constants tc1, c2, . . . , cnu, called a domain, the respective relational marginal polytope is the convex hull of the set of points obtained by taking a possible world ω on the given domain, counting the groundings of the formulas α1, α2, . . . , αk that are true in ω, and repeating this for all possible ω's. For instance, for the formulas α1 � smpxq and α2 � smpxq ^ friendspx, yq ^ smpyq, the points defining the polytope would be given by the numbers of smokers in the population (the formula α1) and the number of pairs of people who are friends and, at the same time, both smoke (the formula α2). Relational marginal polytopes can also be seen as "lifted" counterparts of standard marginal polytopes studied in the probabilistic graphical models literature (see, e.g., [Roughgarden and Kearns, 2013; Sontag and Jaakkola, 2008]). Relational marginal polytopes have already found applications, among others, in polynomial-time algorithms for maximum-likelihood learning [Kuzelka and Kungurtsev, 2019; Kuzelka et al., 2020].

�Corresponding author

Kuzelka and Wang [2020] recently showed that, roughly speaking, if computing the partition function of a Markov logic network given by formulas α1, . . . , αk can be done in time polynomial in the domain size, then the relational marginal polytope for the same formulas can be constructed in polynomial time. On the one hand, this is an important result, because it allows one to exploit existing lifted inference algorithms for weighted first-order model counting (WFOMC) (such as that of [Van den Broeck et al., 2011]) for the construction of relational marginal polytopes. On the other hand, despite being polynomial in the domain size, the algorithm proposed in [Kuzelka andWang, 2020] is not practical. In this paper we propose an approach that uses significantly fewer calls to a WFOMC oracle than the aforementioned algorithm. This new algorithm also outperforms a subsequent algorithm based on discrete Fourier transforms proposed in [Kuzelka, 2020]. Moreover, as a secondary contribution, we show how an efficient algorithm for relational marginal polytope construction such as the one proposed here can be applied to speed up ApproxWFOMC [van Bremen and Kuzelka, 2020], a recent approach for approximate weighted first-order model counting.

2 Preliminaries

This section briefly reviews the syntax and semantics of Markov logic networks and weighted first-order model counting.

2.1 Markov Logic Networks

We consider a function-free first-order logic defined by a set of constants ∆, called a domain, a set of variables V and a set Rk of k-ary predicates for each k P N. An atom takes the form rpa1, . . . , akq with a1, . . . , ak P ∆Y V and r P Rk. A literal is an atom or its negation. A logical variable in a formula is said to be free if it is not bound by any quantifier. A formula with no free variables is called a sentence. A formula in which none of its literals contains any variables is called ground. The set of grounding substitutions Θpα, ∆q � tθ1, . . . , θmu of a formula α w.r.t. a domain ∆ is the set of substitutions on all free variables occurring in α using constants from ∆. A possible world ω is represented as a set of ground atoms that are true in ω. The satisfaction relation |ø is defined in the usual way: ω |ø α means that the formula α is true in ω, as per the standard semantics of first-order logic.

A Markov logic network (MLN) [Richardson and Domin-

gos, 2006] is a set of weighted first-order logic formulas pα,wq, where w P R and α is a first-order formula. An MLN Φ induces a probability distribution over possible worlds ω P Ω : pΦpωq � 1Z exp ��pα,wqPΦ w � Npα, ωq�, where Npα, ωq :� �θPΘpα,∆q 1pω |ø αθq is the number of groundings of α satisfied in ω, and Z, called the partition function, is a normalization constant to ensure that pΦ is a probability distribution. We also allow infinite weights. A formula α with infinite weight 8 is understood as a hard constraint imposing that all worlds ω in which Npα, ωq is not maximal have zero probability. A literal with infinite weight is called an evidence literal. We denote by varspαq the number of free variables in the formula α.

2.2 Inference UsingWFOMC

The marginal inference task in MLNs can be reduced to weighted first-order model counting (WFOMC).

Definition 1 (WFOMC, [Van den Broeck et al., 2011]). Let wprq and ¯wprq be functions mapping predicates to complex numbers, Γ a sentence, and ∆ a set of constants. Then

where Ω∆ is the set of all possible worlds on the domain ∆ (using the predicates in Γ), Ppωq and Npωq denote the positive literals that are true and false in ω, respectively, and Predpaq denotes the predicate of a (e.g., Pred(friends(Alice, Bob)) = friends).

We may proceed as in [Van den Broeck et al., 2011] to compute the partition function Z of a given MLN using WFOMC. Given an MLN Φ, for every weighted formula pαi, wiq P Φ, where the free variables in αi are exactly x � tx1, . . . , xku and w � 8, we create a new formula @x : ξipxq � αipxq where ξi is a new predicate. When αi has w � 8, we instead create a new formula @x : αipxq. We denote the conjunction of the resulting set of sentences by Γ and set the weight function to be wpξiq � exppwiq and ¯wpξiq � 1, and for all other predicates we set both w and ¯w to be 1. It is easy to check that WFOMCpΓ,w, ¯w,∆q � Z.

Importantly, there are classes of first-order logic theories for which weighted first-order model counting can be performed in time polynomial in the domain size |∆|. In particular, as shown in [Van den Broeck et al., 2014], this is the case when the theory in question consists only of first-order sentences each containing at most two logical variables. In statistical relational learning, the term used for classes of problems that allow such a polynomial-time algorithm is domain liftability.

3 Relational Marginal Polytopes

Here we define relational marginal polytopes (RMP), which are the main focus of this paper. Intuitively, an RMP represents the possible expected values for the vectors of grounding counts of a given set of formulas. 1

Definition 2 (Relational Marginal Polytope, [Kuzelka et al., 2018]). Let ∆ be a set of constants and Ψ � pα1, . . . , αmq be a set of formulas. The relational marginal polytope of Ψ on ∆ is defined as RMPpΨ,∆q :� tpx1, . . . , xmq P Rm | Ddist. on Ω∆ s.t. ErNpα1, ωqs � x1^� � �^ErNpαm, ωqs � xmu, where Ω∆ is the set of all possible worlds on the domain ∆ using the predicates in Ψ.

3.1 RMPs as Convex Polytopes

The definition of RMPpΨ,∆q is equivalent to the convex hull of the set of integral points tpNpα1, ωq, . . . ,Npαm, ωqq | ω P Ω∆u. For simplicity, we denote NpΨ, ωq � pNpα1, ωq, . . . , Npαm, ωqq.

Example 1. Consider "friends-smokers" formulas α1 :� smpxq, α2 :� frpx, yq ^ smpxq æ smpyq and α3 :� friendspx, yq and denote Ψ1 � tα1, α2u and Ψ2 � tα1, α2, α3u. Let ∆ be a domain of size 7. The two relational marginal polytopes RMPpΨ1,∆q and RMPpΨ2,∆q are shown in Figure 1.

A convex polytope P can be specified by a set of non-redundant bounding half-spaces txa1, xy / b1, . . . , xaM, xy / bMu, called the H-representation [Fukuda,

1 Kuzelka et al. [2018] define a rescaled version of the polytope presented here.

2004]. Here we review some important terminologies of polytopes used in this paper.

Definition 3 (Bounding half-space). A half-space xa, xy / b is called valid for P if xa, xy / b holds for all x P P. A half-space xa, xy / b is a bounding half-space of the convex polytope P, if it is valid for P and the intersection of its hyperplane xa, xy � b with P is non-empty.

Definition 4 (Supporting hyperplane). A supporting hyperplane of a polytope is the hyperplane of any of its bounding half-spaces.

Definition 5 (Vertex). A vertex of a polytope P is a 0dimensional intersection of P with any of its supporting hyperplanes.

3.2 A Lifted Reduction toWFOMC

Though constructing relational marginal polytopes in practice can be quite difficult, Kuzelka and Wang [2020] provide a lifted 2 reduction from this problem to WFOMC. They first enumerate the normal vectors of all possible bounding halfspaces of RMPpΨ, ∆q. Since NpΨ, ωq can only take values in �αPΨt1, 2, . . . , varspαqu, the number of normal vectors to be checked is at most |∆|m �αPΨ varspαq . For each candidate normal vector a, they use a version 3 of Lemma 1 below to find the integer b for the bounding half-space xa, xy / b by computing the partition function of an MLN.

Lemma 1 (Based on Theorem 3 in [Kuzelka and Wang, 2020]). Given a normal vector a P Rm and a set of formulas Ψ � tα1, . . . , αmu over a domain ∆, let Z be the partition function of the MLN tpαi, 2ai ln |Ω∆|q | 1 / i / mu. Then the halfspace xa, xy / r lnZ{ ln |Ω∆|�1 2 s is a bounding half-space of RMPpΨ, ∆q.

When all bounding half-spaces of RMPpΨ, ∆q are available, constructing its H-representation is not a difficult problem. The problem is equivalent to removing redundant inequalities from a system of linear inequalities. A simple solution, which is employed by Kuzelka and Wang [2020], is to iteratively check whether a bounding half-space is redundant using linear programming (LP) (c.f. Lemma 2 therein). Since the number of enumerated bounding half-spaces is polynomial w.r.t. the domain size, they claim that if the MLNs used in Lemma 1 are domain-liftable, computing RMPpΨ,∆q can be done in time polynomial in |∆|.

However, as we discussed above, the method that they proposed requires |∆|m �αPΨ varspαq WFOMC oracle calls, which is usually infeasible in practice. Although the complexity was later improved to p|∆| � 1q�αPΨ varspαq � 1 calls using a technique based on computing the discrete Fourier transform (DFT) of the count distribution of an MLN [Kuzelka, 2020], invoking such a large number of WFOMC oracle calls still quickly becomes intractable as the domain size increases.

2 The term "lifted" here means that the reduction can be performed in time polynomial in the domain size.

3 Since Kuzelka and Wang use slightly different definitions and notation, we slightly adapted their Theorem 3 to the setting used in this paper.

4 A Faster Algorithm

In this section, we propose Fast-RMP, a faster algorithm for the RMP construction problem.

4.1 Intuition

Instead of traversing all candidate bounding half-spaces of RMPpΨ, ∆q, we consider only a portion forming a convex polytope candidate P, and iteratively check whether the vertices of P are vertices of RMPpΨ,∆q. It is clear that RMPpΨ,∆q � P, and if we reach a point where all vertices of P are vertices of RMPpΨ, ∆q, we know that P must be the desired polytope.

For each vertex v of P, we know it must be the intersection of a set of m linearly independent bounding hyperplanes of RMPpΨ,∆q. Let txa1, xy / b1, . . . , xam, xy / bmu be the corresponding bounding half-spaces. To check if v is a true vertex of RMPpΨ, ∆q, we construct a new normal vector a1 � �mi�1 ai and call the WFOMC oracle to obtain a new bounding half-space xa1 , vy / b1 of RMPpΨ,∆q. By Lemma 2, if b1 � �mi�1 bi, the candidate v is a true vertex of RMPpΨ,∆q.

Lemma 2. Let P be a convex polytope in k-dimensional space, and let H :� txa1, xy / b1, . . . , xak, xy / bku be k non-redundant half-spaces that are valid for P. Denote H the corresponding hyperplanes of H. Then the intersection of the hyperplanes in H is a vertex of P, if and only if the half-space H :� x�ki�1 ai, xy / �ki�1 bi is a bounding half-space of P.

Proof. Since H is non-redundant, it is clear that H is linearly independent and its intersection is a singleton containing a point. Let v be this point and h be the hyperplane of H. According to the definition of a vertex, it is sufficient to prove that hXP � tvu. Since H is a bounding half-space of P, we have hXP � H. Assume there exists a point v1 P hXP and v1 � v. By the condition v1 P h, we have

As v1 P P and every half-space in H is valid for P, we also have

Since all hyperplanes in H are linearly independent, their intersection v is the unique solution of the system of linear equations xai, xy � bi, i � 1, . . . , k. For the point v1 , there must exist j P t1, . . . , ku such that xaj, v1 y � bj, which combined with (2) leads to a contradiction on (1). Thus the point v is the unique point in h XP. The reverse direction is straightforward according to the definition of bounding halfspaces.

4.2 Fast-RMP

The proposed approach, named Fast-RMP, is described in Algorithm 1. We denote by boundingHalfSpace the function that takes a set of formulas Ψ, a set of possible worlds Ω and a normal vector a as inputs, and calculates the intercept of the bounding half-space of RMPpΨ, ∆q with the norm a according to Lemma 1. convexHull calls an oracle that produces a convex hull from a set of points. notVisitedpP, visitedq returns vertices of P that are not contained in the set visited.

Algorithm 1 Fast-RMP

Input: A list of formulas Ψ � tα1, . . . , αmu and a set of

• possible worlds Ω Output: Relational marginal polytope RMPpΨ,∆q 1: for i - t1, . . . ,mu do 2: // ei is the ith basis vector 3: bi - boundingHalfSpacepΨ, Ω, eiq 4: I - tx � px1, . . . , xmq | x P Zm, 0 / x1 / b1, . . . , 0 / xm / bmu 5: P - convexHullpIq 6: visited - pq 7: while notVisitedpP, visitedq is not empty do 8: v - notVisitedpP, visitedqr0s 9: txa1, xy / b1, . . . , xam, xy / bmu - HRepresentationpP, vq 10: visited.addpvq 11: a1 - �mi�1 am 12: b1 - boundingHalfSpacepΨ, Ω, a1 q 13: if b1 � �mi�1 bi then 14: // Found a vertex of RMPpΨ, ∆q 15: continue 16: I - tx | x P I, xa1 , xy / b1 u 17: P - convexHullpIq 18: return P

We use HRepresentationpP, vq to obtain a set of m nonredundant (linearly independent) bounding half-spaces of P related to the vertex v.

We initialize the convex polytope P as the bounding box specified by bounding half-spaces of RMPpΨ, ∆q with normal vectors parallel to axes. We also keep a set of integral points I contained in P. At each step, to inspect the vertex of P, we first construct the normal vector according to Lemma 2, and then find the bounding half-space with this normal vector using boundingHalfSpace based on Lemma 1. If the bounding half-space satisfies the condition in Lemma 2, we confirm that the vertex candidate is a true vertex of RMPpΨ,∆q. If the vertex candidate fails to pass the check, we purge it along with points in I not in the new half-space H, and then compute a new convex polytope from the remaining points in I using an oracle for convex hulls. It is easy to check that all bounding half-spaces of the new polytope are valid for RMPpΨ,∆q. The set of points I serves as a filter to make sure all vertices of the processed convex polytope are integral, since only an integral point can be a vertex of RMPpΨ, ∆q. When all vertices of P are verified, the current convex polytope is exactly RMPpΨ,∆q.

In the worst case, we would need to check all integral points in the original bounding box. Since in this case we need only one WFOMC call per integral point in the initial bounding box, the number of WFOMC calls in Algorithm 1 is never more than the p|∆| � 1q�αPΨ |varspαq| � 1 calls needed in [Kuzelka, 2020].

Remark 1. We choose QuickHull [Barber et al., 1996] as the oracle for convexHull, which is polynomial-time w.r.t. the number of integral points |I|. It follows that the guarantee that if MLNs given by Ψ are domain-liftable, constructing its RMP is also domain-liftable still holds for Alg. 1.

5 An Application of Fast-RMP

In this section, we present an application of Fast-RMP to improve an existing approximation algorithm for WFOMC [van Bremen and Kuzelka, 2020]. To simplify the exposition, we describe the method only for WFOMC problems obtained fromMLNs. Still, the proposed method can also be applied to general WFOMC problems (with a generalized Fast-RMP). Given an MLN Φ, denote by Ψ8 the set of formulas with infinite weight in Φ. Let Φ6 be the tuples with finite weight in Φ and Ω∆,Ψ be the set of all possible worlds on the domain ∆ that satisfy all formulas in some set Ψ. Using the reduction in Section 2.2, we can overload the definition of WFOMC to allow MLNs as input, yielding the partition function of Φ on a domain ∆:

,

"

"

5.1 ApproxWFOMC

In general, computing WFOMCpΦ,∆q exactly is a #P1-hard problem if Φ contains a formula with more than two logical variables [Beame et al., 2015]. Therefore, to deal effectively with non-liftable formulas, van Bremen and Kuzelka [2020] proposed an approximation algorithm for WFOMC. Given an MLN Φ and a domain ∆, they define the first-order model counting function as

where Z is a set of integer vectors and Ψ6 is the list of formulas in Φ6 . The WFOMC WFOMCpΦ, ∆q then can be decomposed into:

where k � pk1, . . . , kmq, K � �mi�1 t0, 1 . . . , |∆|varspαiq u. The first-order model counts are estimated using a hashingbased approximation algorithm [Chakraborty et al., 2016; Soos and Meel, 2019], which allows for PAC-guarantees on the WFOMC returned; we refer the reader to [van Bremen and Kuzelka, 2020] for more details.

In their algorithmApproxWFOMC, they approximate (3) using a divide and conquer strategy that splits the space specified by K into disjoint small rectangular boxes. For each box and a set of integer points in it C � tkp1q , . . . , kptq u, they compute MCΦ,∆pCq and the minimum and maximum of the product of weights lo � mintj�1 -mi�1 exppkpjq i wiq and hi � maxtj�1 -mi�1 exppkpjq i wiq respectively. The value of the weighted first-order model count constrained by this box can be bounded by MCΦ,∆pCq � lo and MCΦ,∆pCq � hi.

5.2 Improvement on ApproxWFOMC

We present an improved ApproxWFOMC, named FastApproxWFOMC, in Algorithm 2. The main idea is that if RMPpΨ,∆q is already known, for the decomposition given in (3),

1. we can consider only the summation on k's contained in RMPpΨ,∆q rather than in all of K; and,

Algorithm 2 Fast-ApproxWFOMC

Input: an MLN Φ of size m with a surrogate RMP P, a domain ∆ and tolerance τ Output: pb1, b2q s.t. b1 / WFOMCpΦ,∆q / b2, and b2 b1 � 1 � τ 1: queue - new priority queue 2: for i P t1, . . . ,mu do 3: // Improvement 1 4: constraintsris - pminxi x P P, maxxi x P Pq 5: C - integerPointspconstraintsq 6: mc - MCΦ,∆pCq 7: // Improvement 2 8: lb, ub - getBoundspP, constraints,Φq 9: LB,UB -mc � lb,mc � ub 10: Store pconstraints,LB,UBq in queue 11: while UB LB ¥ 1 � τ and queue is not empty do 12: Pop pconstraints, lb, ubq from queue 13: if constraints cannot be split further then 14: continue 15: i - the index of optimal formula by heuristic 16: l, u - constraintsris 17: lef tConstr - constraints 18: rightConstr - constrains 19: lef tConstrris - pl, t l�u 2 uq 20: rightConstrris - pt 1�u 2 u �1, uq 21: LB -LB � lb 22: UB -UB �ub 23: for refinedConstr in tleftConstr, rightConstru do 24: // Improvement 1 25: if ref inedConstr X P is H then 26: continue 27: // Improvement 2 28: lo, hi - getBoundspP, ref inedConstr, Φq 29: C - integerPointspref inedConstrq 30: mc - MCΦ,∆pCq 31: LB - LB � lo � mc 32: UB - UB � hi � mc 33: Push prefinedConstr, lo �mc, hi �mcq to queue 34: return pLB,UBq 35: 36: function getBounds(P, constraints,Φ) 37: Get H-representation txa1, xy / b1, . . . , xaM, xy / bMu of P 38: w- pw1, . . . ,wmq 39: Solve the following LPs and obtain the optimal objec-

tives ol and ou respectively minxw, xy or min�xw, xy s.t. xai, xy / bi, i � 1, . . . ,M xj ¥ constraintsrjsr0s, j � 1, . . . ,m xj / constraintsrjsr1s, j � 1, . . . ,m 40: return pexppolq, expp�ouqq

1. in each split box generated by ApproxWFOMC, we can further constrain k to lie in RMPpΨ,∆q to obtain better

lower and upper bounds of the product of weights.

In improvement 2, to avoid intractable integer programming, we constrain k to lie in the intersection of RMPpΨ, ∆q with the continuous area specified by the box.

Example 2. Consider the convex polytope of the MLN Φ � tpα1 : 1q, pα2 : 2qu for domain size 3, where α1 and α2 are given in Example 1. Figure 2 shows a possible split produced by ApproxWFOMC. In this split, the original lower and upper bounds for each box are pe10 , e19 q, pe12 , e21 q, pe0 , e9 q, pe2 , e11 q respectively, while in our algorithm, boxes 3 and 4 would be ignored since they do not intersect with the polytope, and the bounds for boxes 1 and 2 are improved to pe15 , e19 q, pe16 , e21 q.

Note our enhancements do not require an exact RMPpΨ,∆q. If only the RMP of a subset of formulas with indices ti1, . . . , itu is available, e.g., the RMP problem for the whole formulas is not domain-liftable, we can construct a surrogate convex polytope RMP1 pΨ, ∆q :� RMPptαi1 , . . . , αit u, ∆q XJ , where J � tx | 0 / xi / |∆|varspαiq , i � 1, . . . ,mu is the continuous area of K. Since RMP1 pΨ,∆q � J , the algorithm with RMP1 pΨ, ∆q can still benefit from the improvements proposed above.

5.3 AlgorithmDetails

In Algorithm 2, we use constraints to represent a rectangular box with its ith component specifying the boundary of the box along the ith dimension. The function integerPointspconstraintsq returns a set of the integer points within the box specified by constraints: tk P Zm | constraintsrisr0s / ki / constraintsrisr1s, i � 1, . . . ,mu.

Using the divide and conquer strategy, we progressively split K into several disjoint boxes and compute the lower and upper bounds of WFOMC constrained by these boxes. The whole WFOMC then can be estimated by adding up the lower and upper bounds over all these boxes as shown in (3). We store these boxes as well as their bounds in a queue that is sorted according to a heuristic function on these bounds. At each step of the while loop, we process one of the boxes, evenly partitioning it into two boxes along a heuristic-optimal dimension (lines 14-19) resulting in a new split of K, and refine the lower and upper bounds of the WFOMC on the new split (lines 20-30). We refer to Algorithm 1 in [van Bremen and Kuzelka, 2020] for more details.

Our improvements on the original ApproxWFOMC are highlighted by comments. In particular, the function getBoundspP, constraints,Φq realizes improvement 2, returning refined lower and upper bounds of the WFOMC within the intersection of P with the continuous area of constraints.

6 Experiments

We conduct several experiments on different benchmark problems to show the efficiency of our proposed algorithms FastRMP and Fast-ApproxWFOMC.

6.1 Implementation and Setup

We use Forclift 4 as the WFOMC oracle, QuickHull 5 as the backend for the convex hull problem, and an interior point method [Boyd and Vandenberghe, 2004] to solve LPs. We follow van Bremen and Kuzelka [2020] and utilize ApproxMC4 [Soos and Meel, 2019] as an approximate MC oracle. The hyperparameters in our WFOMC approximation experiments are set to ϵ � 0.8, δ � 0.2 and τ � 0.5, just as in the original paper.

For Fast-RMP, we further adopt a pre-compilation technique [Van Haaren et al., 2016] that only compiles Ψ into a first-order d-DNNF circuit in the first oracle call, and evaluates the circuit on the given set of weights to compute the partition function in later WFOMC calls. This further speeds up the RMP computation.

All experiments are performed on a computer with an eightcore Intel i7 3.60GHz processor and 32 GB of RAM.

6.2 RMP Construction

We use the DFT-based algorithm proposed by Kuzelka [2020] as a baseline method, since it is, to the best of our knowledge, the state-of-art for the RMP construction problem. We test Fast-RMP on four problems:

• Friends and smokers: two variants corresponding to Ψ1 and Ψ2 from Example 1.
• Friends, smokers and drinkers: Ψ3 � tstrpxq æ smpxq, smpxq ^ frpx, yq æ smpyq, strpxq æ drpxq, drpxq ^ f rpx, yq æ drpyqu
• Infection: Ψ4 � tdiseasepxq æ coughpxq, diseasepxq ^ contactpx, yq æ diseasepyq, diseasepxq æ contactpx, yqu in which the third formula simulates a quarantine on infected people.

In Figure 4a, we show the performance gain of Fast-RMP over the baseline, by quantifying the ratio between our algorithm and the baseline for both runtime and the number of WFOMC oracle calls. The baseline already times out (10 hours) for Ψ3 with a domain of size 10, so the domain size we test for Ψ3 is up to 10. Fast-RMP is more than a hundred Domain size Domain size times faster. On all tested problems, the ratio of WFOMC calls steadily decrease with domain size. Overall, Fast-RMP is approximately 10-100 times faster than the baseline.

4 https://github.com/UCLA-StarAI/Forclift

5 http://www.qhull.org/

Figure 3: Number of vertices and facets of convex polytopes of Ψ1, Ψ2, Ψ3 and Ψ4 on different domain sizes.

We also analyze the statistics of convex polytopes of the four examples on different domain sizes as shown in Figure 3. The performance of our method obviously depends on the number of vertices of the convex polytope, but it seems that the complexity of convex polytopes does not hurt the efficiency of our approach. For example, the polytope of Ψ3 is much more complicated than others, while the improvement of FastRMP on it is more significant.

6.3 WFOMCApproximation

To evaluate our new approximate WFOMC algorithm FastApproxWFOMC, we conduct inference experiments in two different WFOMC settings: (i) with MLNs that are not domainliftable and (ii) with MLNs that are domain-liftable, but have been augmented with binary evidence literals. We then compare our algorithm with the original one ApproxWFOMC and, for the experiments with domain-liftable MLNs, also with Forclift [Van den Broeck et al., 2011]. Forclift computes the exact WFOMC, but works only on domain-liftable problems. ApproxWFOMC and Fast-ApproxWFOMC provide PACguarantees on the approximation [van Bremen and Kuzelka, 2020]. We do not compare with algorithms that do not give any guarantees (such as Gibbs sampling); even though they can scale to large domains, estimates obtained using such methods can be arbitrarily bad. Such a comparison would therefore not make sense here.

Inference in Non-liftable MLNs

We perform experiments with the following two MLNs:

• Transitive smokers and drinkers: Φ1 � tpstrpxq æ smpxq, 1.22q, psmpxq ^ frpx, yq æ smpyq, 2.08q,

pfrpx, yq ^ frpy, zq æ frpx, zq, 0.69q, pstrpxq æ drpxq, 2q, pdrpxq ^ frpx, yq æ drpyq, 1.5qu, with the same weights as in [van Bremen and Kuzelka, 2020].

• Transitive infection: Φ2 � tpdiseasepxq æ coughpxq,�0.69q, pdiseasepxq ^ contactpx, yq æ diseasepyq, 0.69q, pcontactpx, yq ^ contactpy, zq æ contactpx, zq, 0.83q, pdiseasepxq æ contactpx, yq, �0.11qu

Note that the third formula in the MLNs is a transitive rule, meaning neither problem is domain-liftable. To compute their polytopes, we consider the liftable part of each of these two MLNs and feed their convex polytopes as surrogate polytopes to our algorithm as described in Section 5.2.

Figure 4b presents the runtime of our algorithm compared to the baseline. On the "transitive smokers and drinkers" problem, Fast-ApproxWFOMC performs on par with the baseline, but does better on the transitive infection problem.

To better understand why Fast-ApproxWFOMC does not improve over ApproxWFOMC on the "transitive smokers and drinkers" MLN, we further visualized the convergence rate of the bounds in Figure 5. As can be seen, though our new algorithm requires a similar number of oracle calls as the baseline to achieve an approximation within the prescribed accuracy, it converges much faster at early iterations. This suggests that, in some cases where Fast-ApproxWFOMC is not faster, overall it may still be more efficient for computing rough bounds, i.e., when the value of the tolerance τ is large.

Inference in Liftable MLNs with Binary Evidence

A "smokers and drinkers with evidence" MLN is used here: Φ3 � tpsmpxq, 1.22q, psmpxq ^ frpx, yq æ smpyq, 2.08q, pf rpx, yq, 0.69q, pdrpxq ^ f rpx, yq æ drpyq, 1.5q, pl1, �8q, . . . , pln,�8qu, where l1, . . . , ln are randomly generated literals using the binary predicate frp�, �q. The domain size is fixed to 5. Note that approximating the WFOMC of this MLN makes sense, as the exact WFOMC problem is usually hard for MLNs with binary evidence literals, even if the MLN is otherwise domain-liftable [Van Den Broeck and Davis, 2012]. However, computing the RMP used in Fast-ApproxWFOMC is tractable since it does not involve any evidence.

Figure 4c compares the runtime of Forclift, ApproxWFOMC and Fast-ApproxWFOMC for computing the partition function of the MLN above with a varying number of evidence literals. Forclift performs better than the approximation algorithms with a small number of evidence literals, while ApproxWFOMC and Fast-ApproxWFOMC surpass Forclift after 7 and 11 evidence literals respectively. The runtime of approximation algorithms decreases gradually as the size of evidence increases. The evidence literal sufficiently simplifies the theory fed to the model counting oracle, thus reducing the time needed for the propositional model counter calls. Importantly, for all evidence sizes, Fast-ApproxWFOMC is consistently faster than ApproxWFOMC.

7 Conclusions

We considered the problem of constructing relational marginal polytopes, and proposed an algorithm that is successful in reducing both the number of WFOMC oracle calls as well as overall runtime by orders of magnitude as compared to the current state of the art. We further applied our approach to an improved algorithm for approximate weighted first-order model counting. In the future, we would like to further investigate applications of RMPs in other statistical-relational models beyond MLNs.

Acknowledgments

The authors would like to thank the anonymous reviewers for their helpful comments. Yuanhong Wang and Juhua Pu are supported in part by the National Key R&D Program of China (2018YFB2100800), Science Technology and Innovation Commission of Shenzhen Municipality (JCYJ20180307123659504) , and the State Key Laboratory of Software Development Environment in Beihang University (SKLSDE-2020ZX-22). TvB is supported by the Research Foundation - Flanders [G095917N]. OK is supported by the Czech Science Foundation project "Generative Relational Models" (20-19104Y) and partially also by the OP VVV project CZ.02.1.01/0.0/0.0/16 019/0000765 "Research Center for Informatics".

A Further Analysis of the Performance of Fast-ApproxWFOMC

In this section, we try to explain the actual reason why Fast-ApproxWFOMC does not help much on the "transitive smokers and drinkers" example. One possible reason is that the "mass" of the weighted first-order model count of this example is concentrated in some rectangular boxes in the convex polytope. For instance, a possible split made by Fast-ApproxWFOMC for the subset of "transitive smokers and drinkers" MLN: tpstrpxq æ smpxq, 1.22q, psmpxq ^ frpx, yq æ smpyq, 2.08qu for domain size 3 is presented in Figure 6a. The distribution of the value of MCΨ,∆pkq � -mi�1 exppkiwiq in (3) of this example is shown in Figure 6b. It is easy to see that the large part of WFOMC of this example is mainly concentrated at the top right corner of the polytope, which is approximated by box 2. However, box 2 is contained in the polytope, and thus for this box Fast-ApproxWFOMC cannot provide better lower and upper bounds than ApproxWFOMC. The consequence is that the overall bounds cannot be improved much by FastApproxWFOMC in this specific case.