Xeggora: Exploiting Immune-to-Evidence Symmetries with Full Aggregation in Statistical Relational Models (Extended Abstract)

1 Introduction

MAP inference is a concerning need in Markov Logic [Richardson and Domingos, 2006] because of its high complexity. Several lifting approaches [Kimmig et al., 2015] including Cutting Plane Aggregation (CPA) [Noessner et al., 2013] are introduced to speed up inference by detecting symmetries and avoiding repetitive computations. CPA improves compilation from a ground network to an Integer Linear Program (ILP) by decreasing the size of the program and better exposing its symmetries. The ILP is further passed to traditional solvers and the solution is mapped to a MAP state of the original MLN.

There still exist further symmetries that CPA is unable to handle. In this work [Amirian and Shiry Ghidary, 2019], we first illustrate some types of these symmetries by introducing order of aggregation and showing that CPA is able to perform only aggregations of order one, whereas higher-order aggregations are required to exploit the ignored symmetries. Secondly, a superior algorithm, namely Full Constraint Aggregation (FCA) is introduced, empowered with any possible order of aggregation with respect to the model. FCA performs a novel translation to efficient ILPs by relaxing some constraints. We then propose complementary techniques, including heuristics and RDBMS leverage to choose efficiently among multiple candidates the one in which FCA fits the best. The proposed methods are implemented within an evolutionary extension of RockIt, namely Xeggora. Finally, we show that Xeggora's time-preserving techniques outperform RockIt while applied to models with long formulas.

* This paper is an extended abstract of an article in the Journal of Artificial Intelligence Research [Amirian and Shiry Ghidary, 2019]

1.1 MAP Inference in Markov Logic

Markov Logic allows softening a first-order formula f, by attaching a real-valued weight w to it. A positive (negative) weight makes the formula support (penalize) worlds in which it is satisfied. Hard formulas are regular first-order formulas which are expressed with infinite weights and have to be fulfilled by every possible world. The probability of a possible world x in the presence of evidence e is defined as:

and e, to respect with constant normalization a is ௘ܼ where satisfy that x in 𝑖݂ of groundings true of number the is ሻ݁ ,ݔሺ𝑖݊ e. MAP inference corresponds to inferring the most likely possible world, and reduces to finding the interpretation that maximizes the sum of the weights of the satisfied clauses.:

This can be left as an ILP formulation [Wolsey, 1998] for efficient optimizers to be solved. Huynh and Mooney [2009]

proposed a translation of MAP queries to ILPs and Noessner et al. [2013] extended the approach by applying constraint aggregation. We improve the result by applying higher-order aggregations and introduce Full Constraint Aggregation. The method is powered with RDBMS and heuristic techniques to choose efficiently among candidate clauses to be aggregated.

1.2 Preface

In the next section we describe the ILP formulation and constraint aggregation methods. Section 3 is composed of the FCA algorithm description. Section 4 describes add-on techniques that leverage RDBMS and related heuristics to improve the overall performance. The reader is referred to the original paper for details, examples, soundness proofs, ILP solving analytics, and the empirical evaluation of FCA on six benchmark MLNs.

2 MAP ILP Formulation Techniques

In all parts of the process, formulas are supposed to be composed of disjunctive clauses. The traditional ILP formulation, and the enhancements of constraint aggregation are introduced here. We then continue by introducing symmetries that CPA fails to exploit.

2.1 Traditional ILP Formulation

Given a set of ground clauses 𝒢 as input, one binary ILP varin occurring ℓ atom ground each with associated is ℓݔ iable the set, assigning it a value 1 provided ℓ is true and 0 otherwise. Each evidence atom can be represented as a linear conclause ground each For ͳ. ൒ ℓݔ or Ͳ ൑ ℓݔ straint of the form coeffi- with ௚ݖ variable binary a ℝ, ∈ ௚ݓ weight with 𝒢 ∈ ݃ be- totally objective The objective. the to added is ௚ݓ cient comes:

to ௚ݖ It is straightforward to design constraints considering be assigned 1 provided its corresponding ground clause is satisfied in the MAP solution and 0 otherwise. For a clause with ILP: the to added is constraint following the Ͳ, > ௚ݓ

atoms ground all of sets the to refer ሻ݃ሺ 𝐿- and ሻ݃𝐿+ሺ where truth A respectively. ,݃ occurring unnegated and negated in value assignment to any ground atom that fulfills the disjuncposi- constraint the of side left-hand the makes ,݃ tive clause 1. value possible maximum its take can ௚ݖ tive, thus,

objective the to added is term no =∞), ௚ݓ( For hard clauses 1: with replaced simply is constraint the in ௚ݖ and

to ௚ݖ lower to tries optimizer the Ͳ, < ௚ݓ For a clause with its minimum possible value 0. The following constraint is added to permit this only if none of its constituting ground :݃ atoms satisfy

Finally, for clauses with zero weights, no constraint is added to the ILP.

2.2 Cutting Plane Aggregation

Grounding formulas in MLN often results in symmetries in multiple ground clauses, and consequently, in the ILP constraints. Constraint aggregation proposes aggregating ground clauses that include symmetries, resulting in smaller constraint matrices and aiding symmetry detection algorithms of the ILP solver. The candidate sets of ground clauses to which aggregation can be applied are defined as follows:

Definition 1 Let 𝐺 ⊆ 𝒢 be a set of n weighted ground clauses and let c be a ground clause. We say that 𝐺 can be aggregated with respect to c if (a) all ground clauses in 𝐺 have the have we ,݊ ൑ 𝑖 ൑ ͳ 𝐺, ∈ 𝑖݃ same weight and (b) for every literal. negative a or positive a is ℓ𝑖 where ܿ ש ℓ𝑖 = 𝑖݃ that

For such a set, all corresponding ILP constraints can be replaced by fewer constraints with the following rules:

Definition 2 (First-Order Aggregation Rules) Let 𝐺 ⊆ 𝒢 be a aggre- be can that ீݓ set of n ground clauses with weight gated with respect to a ground clause c.

• corre- the replace ≠∞), ீݓ( I. In case of a finite weight sponding terms in the ILP objective with a new integer :ீݓ coefficient with }݊ , . . {Ͳ, ∈ ீݖ variable

objective. the of rest + ீݖீݓ maximize

constraints ILP corresponding the replace Ͳ, > ீݓ If with: ∑

with: Ͳ, < ீݓ and if

• the replace only =∞), ீݓ( II. In case of an infinite weight corresponding ILP constraints with:

be to considered is ீݖ According to the aggregation rules, assigned the number of satisfied ground clauses in 𝐺; it gains the maximum value n provided a solution satisfies the ground clause c, otherwise it is equal to the number of the literals (of the form p or ¬q) satisfied by the solution. The CPA algorithm chooses greedily among sets that can be aggregated to a more compact ILP and applies constraint aggregation.

2.3 CPA Failure

There still exist similarities between clauses in the following example, but in addition, diversity in more than one literal.

Example 1 Consider an MLN with a single formula of weight 2.3 stating that each kid may be happy of having a kind parent who has fun with him (her):

Happy(k). ⇒ k) HasFun(p, ר Kind(p) ר 2.3 Child(k, p)

By grounding and applying the evidence: Child(Mary, Jack), Child(Mary, Rose) the essential ground clauses in normal form would be: Happy(Mary) ש Mary) ¬HasFun(Jack, ש 2.3 ¬Kind(Jack) Happy(Mary) ש Mary) ¬HasFun(Rose, ש 2.3 ¬Kind(Rose)

These symmetries are ignored by the CPA algorithm; it allows only one literal to be distinct while all others must be identical. This is the justification of naming the method firstorder aggregation. This failure often happens in models containing long formulas. We introduce Full-Constraint-Aggregation that can exploit this type of symmetry.

3 Full Constraint Aggregation

We start by illustrating symmetry types that appear in ground clauses as in Example 1, based on a parameter we name order of aggregation. Then we describe our superior algorithm which performs higher-order aggregations.

Definition 3 Let 𝐺 ⊆ 𝒢 be a set of n weighted ground clauses and let c be a ground clause with non-zero length. We say that 𝐺 can be aggregated of order k with respect to c, if (a) all ground clauses in 𝐺 have the same weight and (b) for 𝐿𝑖 where ܿ ש 𝐿𝑖 = 𝑖݃ that have we ,݊ ൑ 𝑖 ൑ ͳ 𝐺, ∈ 𝑖݃ every is a ground clause of maximum length k. We call k the aggregation order of 𝐺, if k is the minimum order of which 𝐺 can be aggregated (with respect to any ground clause c).

Due to Definition 3, the constraint aggregation method is only applicable to the sets of ground clauses with aggregation order of 1, performing first-order aggregation. For a set of a higher aggregation order, we need to associate disjunctions of literals with binary terms in the optimization program, e.g. Polyno- Integer an in results This .௕ݔ௔ݔ- ௕ݔ+ ௔ݔ ≡ ܾ ש ܽ mial Program. To be more precise, a k th order trivial aggregation may be performed to formulate the MAP inference problem as an integer k th order mathematical program. The program can be further linearized to an equivalent ILP using the classic linearization method outlined by Watters [1967], as previously done in a different MAP inference method by Sarkhel et al. [2014]. However, the resulting ILP would carry much more variables and constraints and last longer to be solved than the one from the traditional ILP formulation.

To overcome this issue, we propose a novel relaxed translation of MLNs to ILPs by associating auxiliary variables with disjunctive clauses. This is done through higher-order aggregation rules.

Definition 4 (Higher-Order Aggregation Rules) Let 𝐺 ⊆ 𝒢 be aggregation the with ீݓ a set of n ground clauses with weight re- with ݇ order of aggregated be can i.e., ͳ, > ݇ order of spect to a ground clause c. Each ground clause 𝐿𝑖 such that negated or unnegated k most at of disjunction a is 𝐺 ∈ ܿ ש 𝐿𝑖 ground atoms. For each 𝐿𝑖 with length 1, apply the First-Order Aggregation Rules. For the remainder:

1. Corresponding to each 𝐿𝑖, define a new binary ILP varConstraints Bound following the of one Choose . 𝑖௦ݔ iable ILP: the to it add and ீݓ (BCs) after the sign of

• corre- the replace ≠∞), ீݓ( II. In case of a finite weight sponding terms in the ILP objective with a new integer :ீݓ coefficient with }݊ , . . {Ͳ, ∈ ீݖ variable

objective. the of rest + ீݖீݓ maximize

constraints ILP corresponding the replace Ͳ, > ீݓ If 𝑖௦ݔ with: ∑ ℓݔ݊ ௡𝑖=1 +∑ ሻ ℓݔ-ͳሺ݊ ℓ∈𝐿+ሺ௖ሻ +∑ ℓ∈𝐿-ሺ௖ሻ ,ீݖ ൒ with: Ͳ, < ீݓ and if 𝑖௦ݔ ∑ ,ீݖ ௡𝑖=1 ൑ ீݖ ൑ ℓݔ݊ ,ሻܿ𝐿+ሺ ∈ ℓ ݕݎ݁ݒ݁ ݎ݋݂ .ሻܿሺ 𝐿- ∈ ℓ ݕݎ݁ݒ݁ ݎ݋݂ ீݖ ൑ ሻ ℓݔ-ͳሺ݊

the replace only =∞), ீݓ( III. In case of an infinite weight corresponding ILP constraints with:

The Upper-BC and Lower-BC pair if used altogether, represent the disjunction operator(s) of 𝐿𝑖 in the ILP. Intuitively, to correspond a logical OR operator for two Boolean variaine- two add may one space, integer the in ܾ ש ܽ ≡ ܿ bles: would inequalities Similar .௖ݔʹ ൑ ௕ݔ+ ௔ݔ ൑ ௖ݔ qualities: is ௖ݔ represent the disjunction of k Boolean variables. Now if involved in either maximization or minimization, one can drop the corresponding inessential constraint. The reader is referred to the original paper [Amirian and Shiry Ghidary, 2019] for the soundness proof.

4 Leveraging RDBMS and Heuristics

In the original paper, we showed analytically a major difference between the first-order and higher-order aggregations. First-order aggregation, if applicable, reduces the ILP size on the order of the number of aggregated clauses, which results in much faster program solving. This is also verified through experiments on the artificial data. Desired metrics may be obtained to compare the efficiency of possible clustering schemes. However, this is not trivial because efficiency is an abstract measure that relates to the cost of the aggregation procedure in terms of size and runtime, along with the cost of solving the ILP. Moreover, involving a metric in the algorithm would acquire time-consuming computations. Instead, we propose a heuristic approach to choose an appropriate clustering scheme for aggregation as described in the following algorithm. In order to benefit from query optimization technologies, this algorithm leverages RDBMS to compute the compactness of possible aggregations. The idea of RDBMS leverage for MAP inference in Markov Logic was inspired by Riedel [2008] and evolved by Niu et al. [2011] and Noessner et al. [2013]. They used RDBMS in the grounding phase and also in finding the violated constraints, but the computation of counting features was not implemented with RDBMS because it requires storing or regeneration of the ground table which is often inefficient for first-order aggregation. In the case of higher-order aggregations however, counting the number of rows is required several times which is done by the COUNT DISTINCT query. It is a standard SQL query used for counting the number of distinguishable rows on the specified columns in a table. Extensionally, MySQL permits using it multiple times in a single query.

Algorithm CHOOSEFORAGGREGATION

Input ℱ: a first-order disjunctive clause Input 𝒢: a SQL table, containing all essential ground clauses of ℱ Output appropriate clustering scheme as the target for aggregation ሺℱሻ ݂݋_ݏ݈ܽݎ݁ݐ𝐿𝑖 1: L  ሺLሻ ݂݋_ݏ݈ܾ݁ܽ𝑖ݎܽ𝑉 2: 𝒱  3: if |L| = 1 4: candidate_sets  {∅} 5: else 6: candidate_sets  {} 7: foreach non-empty 𝑉 ⊆ 𝒱 8: ⊆ ሻ ሺℓ𝑖 ௙௢ݏ݈ܾ݁ܽ𝑖ݎܽ𝑉 identical_literals  {ℓ𝑖 ∈ 𝐿| 𝑉} 9: if identical_literals  candidate_sets and identical_literals ≠ L 10: add identical_literals to candidate_sets 11: if candidate_sets contains any sets of literals with the size of |L| - 1 12: return best of them greedily to be further first-order aggregated 13: else 14: query  'SELECT ' 15: foreach identical_part ∈ candidate_sets 16: query  query + 'COUNT (DISTINCT ' ' as ') + ሺidentical_partሻ ݁ݖ𝑖݈ܽ𝑖ݎ݁ܵ + ሺidentical_partሻ ݊݋𝑖ݐ݌ܽܥ + [+ ','] // except for the last loop 17: query  query + 'FROM ' + 𝒢 18: execute query into #clusters 19: best_candidate_sets  {argmin#௖𝑙௨௦௧௘௥௦ candidate_sets} 20: return argmaxcardinality best_candidate_sets

The algorithm is provided with a disjunctive clause and a table containing all of its essential groundings in the rows and its constituting variables in the columns. Inessential groundEx- in }݁ݏ݋ܴ ↦ ݌ ,ܾ݋ܤ ↦ ݇{ ings (e.g. by the substitution of ample 1) should have been previously ignored in order to produce an effective output. The algorithm first acquires the set of all literals that constitute the clause and also all variables that participate in grounding (lines 1, 2). In lines 3-6, a set is initialized for storing all feasible partitioning schemes of the literals. Each candidate set is a representative for the set of identical literals (i.e., clause c in Definition 3), so the complementary literals are considered distinct. The cardinality of a candidate set represents the clause length minus its proposing order of aggregation. ∅ is by default a feasible candidate set. However, it is added only for first-order aggregation as it would not be efficient for higher orders, as considered in Definition 3. Lines 7-10 collect candidate sets for aggregation. One may trivially collect the sets based on ground literals; however, we build the collection method upon nonempty sets of variables, in order to avoid producing infeasible candidate sets. It starts with partitioning the variables. Each partitioning scheme of variables specifies a feasible partitioning scheme of literals which in turn corresponds to a clustering scheme of the essential ground clauses. Line 11 discovers if any candidates are present for first-order aggregation, to be in case the arguments of a call to the procedure (line 12). If there exist more than one candidate, one would be chosen greedily as done in CPA. Lines 14-18 contain the code for generating and executing the SQL query that counts the number of clusters aggregated according to each partitioning scheme. Each single clause that is not aggregated is considered in a singleton cluster. We involve the query output #clusters as a lookup table which returns the number of clusters given a candidate set. Finally, the candidate partitioning scheme that offers the minimum number of clusters is selected. If there exist multiple solutions, the one with the lowest aggregation order is returned (lines 19-20). This is motivated from the analysis on the artificial data; keeping other parameters fixed, lower-order aggregations often produce slightly more efficient ILPs.

5 Empirical Evaluation

We implemented the proposed methods within an evolutionary extension of RockIt, namely Xeggora, besides fixing minor bugs of the previous system. Finally, we proved enhancements with comprehensive experiments upon two benchmark sets. The first set of artificial benchmarks explores the effect of higher-order aggregation as compared to the first-order aggregation with respect to the length of clauses. The results confirm the intuition developed through the theoretic side. On practical benchmarks for the entire system, we showed that FCA retains the enhancements of previous works on instances where higher-order aggregation is not applicable, but provides a large benefit in instances where it is.