--- title: "Xeggora: Exploiting Immune-to-Evidence Symmetries with Full Aggregation in Statistical Relational Models (Extended Abstract)" authors: - "Mohammad Mahdi Amirian" - "Saeed Shiry Ghidary" doi: "10.24963/ijcai.2020/697" url: "https://ijcai.org/proceedings/2020/697" pdf: "https://ijcai.org/proceedings/2020/0697.pdf" venue: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence" year: 2020 pages: "5010-5014" track: "Journal track" keywords: - "Constraints and SAT: SAT: : Solvers and Applications" - "Knowledge Representation and Reasoning: Logics for Knowledge Representation" - "Machine Learning: Probabilistic Machine Learning" - "Knowledge Representation and Reasoning: Reasoning about Knowledge and Belief" --- # Xeggora: Exploiting Immune-to-Evidence Symmetries with Full Aggregation in Statistical Relational Models (Extended Abstract) Mohammad Mahdi Amirian, Saeed Shiry Ghidary *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence*, pages 5010-5014. DOI: [10.24963/ijcai.2020/697](https://doi.org/10.24963/ijcai.2020/697) ## Abstract We present improvements in maximum a-posteriori inference for Markov Logic, a widely used SRL formalism. Several approaches, including Cutting Plane Aggregation (CPA), perform inference through translation to Integer Linear Programs. Aggregation exploits context-specific symmetries independently of evidence and reduces the size of the program. We illustrate much more symmetries occurring in long ground clauses that are ignored by CPA and can be exploited by higher-order aggregations. We propose Full-Constraint-Aggregation, a superior algorithm to CPA which exploits the ignored symmetries via a lifted translation method and some constraint relaxations. RDBMS and heuristic techniques are involved to improve the overall performance. We introduce Xeggora as an evolutionary extension of RockIt, the query engine that uses CPA. Xeggora evaluation on real-world benchmarks shows progress in efficiency compared to RockIt especially for models with long formulas. ## Full text ## 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: - I. 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. ## References 1. [Amirian and Shiry Ghidary, 2019] Mohammad Mahdi Amirian and Saeed Shiry Ghidary. Xeggora: Exploiting Immune-to-Evidence Symmetries with Full Aggregation in Statistical Relational Models, Journal of Artificial Intelligence Research, 66: 33-56, 2019. 2. [Huynh and Mooney, 2009] Tuyen N. Huynh and Raymond J. Mooney. Max-margin weight learning for Markov logic networks. In Proceedings of ECML PKDD 2009, Part I, volume 5781 of Lecture Notes in Computer Science, pages 564-579, Springer, 2009. 3. [Kimmig et al., 2015] Angelika Kimmig, Lilyana Mihalkova, and Lisa Getoor. Lifted graphical models: a survey. Machine Learning, 99: 1-45, 2015. 4. [Niu et al., 2011] Feng Niu, Christopher Ré, AnHai Doan, and Jude Shavlik. Tuffy: Scaling up statistical inference in Markov logic networks using an RDBMS. In Proceedings of the VLDB Endowment, 4(6): 373-384, 2011. 5. [Noessner et al., 2013] Jan Noessner, Mathias Niepert, and Heiner Stuckenschmidt. RockIt: Exploiting Parallelism and Symmetry for MAP Inference in Statistical Relational Models. In Proceedings of AAAI, pages 739- 745, 2013. 6. [Richardson and Domingos, 2006] Matthew Richardson and Pedro Domingos. Markov logic networks. Machine Learning, 62: 107-136, 2006. 7. [Riedel, 2008] Sebastian Riedel. Improving the accuracy and efficiency of MAP inference for Markov Logic. In Proceedings of the 24 th Conference on Uncertainty in Artificial Intelligence, pages 468-475, 2008. 8. [Sarkhel et al., 2014] Somdeb Sarkhel, Deepak Venugopal, Parag Singla, and Vibhav Gogate. An Integer Polynomial Programming Based Framework for Lifted MAP Inference. Advances in Neural Information Processing Systems, pages 3302-3310, 2014. 9. [Watters, 1967] Lawrence J. Watters. Reduction of Integer Polynomial Programming Problems to Zero-One Linear Programming Problems. Operations Research, 15(6): 1171-1174, 1967. 10. [Wolsey, 1998] Laurence A. Wolsey. Integer Programming. Wiley-Interscience, New York, 1998.