mining problem introduced in [1]. Indeed, given an alpha-
bet or a set of items Σ, in both problems we consider a
sequence s as an ordered list of itemsets s<sub>0</sub>,...,s<sub>n</sub> where
s<sub>i</sub>subseteq Σ for i=0,...,n. However, the first difference resides
in the definition of a subsequence. Indeed, in the sequen-
tial patterns, we say that s'<sub>i</sub> is a subsequence of s if there
exists a one-to-one order-preserving function f that maps
(inclusion relation) itemsets in s'<sub>i</sub> with itemsets in s. In our
new setting, the notion of subsequence is defined w.r.t. to
a given location and by using empty itemsets as wildcards.
The other difference is that in the sequential pattern min-
ing we consider a database of sequences of itemsets, while
in our setting, we consider only a single sequence of item-
sets. These differences leads also to different definitions of
the notions of support, closeness and maximality. In sum-
mary, our new problem of discovering patterns in a sequence
of itemsets can be seen as a simple and natural extension of
the same problem in a sequence of items. As we can show
later, the SAT encoding can be derived from the one used
for the sequences of items with a very slight modification
demonstrating its flexibility.

The paper is organized as follows. In the next section, we give a short overview of necessary definitions and notations about Boolean Satisfiability (SAT) and Frequent Pattern mining in a Sequence of items (FPS). The extension to the Frequent Pattern mining in a Sequence of Itemsets (FPSI) is presented in Section 3, followed by a discussion of some related works. Then our new SAT-based approach for FPS is described in Section 4, while the closeness and maximal- ity constraints are discussed in Section 5. In Section 6, we show how the SAT encoding of FPSI, can be obtained by a slight modification of the SAT encoding of FPS. Finally, experimental results are conducted and discussed before con- cluding.

2. PRELIMINARIES

## 2.1 Boolean Satisfiability

In this section, we introduce the Boolean satisfiability
problem, called SAT. It corresponds to the problem of decid-
ing if a formula of propositional classical logic is consistent
or not. It is one of the most studied NP-complete decision
problem. In this work, we consider the associated problem
of Boolean model enumeration.

We consider the conjunctive normal form (CNF) repre-
sentation for the propositional formulas. A *CNF formula*
Φ is a conjunction of clauses, where a *clause* is a disjunc-
tion of literals. A *literal* is a positive (*p*) or negated (*¬p*)
propositional variable. The two literals *p* and *¬p* are called
*complementary*.

A CNF formula can also be seen as a set of clauses, and a
clause as a set of literals. Let us recall that any propositional
formula can be translated to CNF using linear Tseitin's en-
coding [22]. We denote by $Var(Φ)$ the set of propositional
variables occurring in $Φ$.

An interpretation $\mathcal{B}$ of a propositional formula $\Phi$ is a function which associates a value $\mathcal{B}(p) \in \{0, 1\}$ (0 corresponds to false and 1 to true) to the variables $p \in \text{Var}(\Phi)$. A model of a formula $\Phi$ is an interpretation $\mathcal{B}$ that satisfies the formula. SAT problem consists in deciding if a given formula admits a model or not.

We denote by $\bar{l}$ the complementary literal of $l$, i.e., if $l = p$
then $\bar{l} = \neg p$ and if $l = \neg p$ then $\bar{l} = p$. For a set of literals $L$,
$\bar{L}$ is defined as $\{\bar{l} \mid l \in L\}$. Moreover, $\overline{\mathcal{B}}$ ($\mathcal{B}$ is an interpretation over $\text{Var}(\Phi)$) corresponds to the clause $\bigvee_{p \in \text{Var}(\Phi)} f(p)$,
where if $\mathcal{B}(p) = 0$ then $f(p) = p$, otherwise $f(p) = \neg p$.

Let us informally describe the most important compo-
nents of modern SAT solvers. They are based on a rein-
carnation of the historical Davis, Putnam, Logemann and
Loveland procedure, commonly called DPLL [9]. It performs
a backtrack search; selecting at each level of the search tree,
a decision variable which is set to a Boolean value. This
assignment is followed by an inference step that deduces
and propagates some forced unit literal assignments. This is
recorded in the implication graph, a central data-structure,
which encodes the decision literals together with there im-
plications. This branching process is repeated until finding
a model or a conflict. In the first case, the formula is an-
swered satisfiable, and the model is reported, whereas in the
second case, a conflict clause (called learnt clause) is gen-
erated by resolution following a bottom-up traversal of the
implication graph [17, 24]. The learning or conflict analy-
sis process stops when a conflict clause containing only one
literal from the current decision level is generated. Such a
conflict clause asserts that the unique literal with the cur-
rent level (called asserting literal) is implied at a previous
level, called assertion level, identified as the maximum level
of the other literals of the clause. The solver backtracks to
the assertion level and assigns that asserting literal to true.
When an empty conflict clause is generated, the literal is
implied at level 0, and the original formula can be reported
unsatisfiable.

In addition to this basic scheme, modern SAT solvers
use other components such as activity based heuristics and
restart policies. An extensive overview about propositional
Satisfiability can be found in [6, 15].

## 2.2 Frequent Pattern Mining in a Sequence of Items (FPS)

In this section, we present the frequent pattern mining
problem of enumerating frequent, closed and maximal pat-
terns with wildcards in a sequence of items [18, 20, 2]. Let
us first give some preliminary definitions and notations.

Sequences of items.

Let Σ be a finite set of items, called alphabet. A sequence
of items *s* over Σ is a simple sequence of symbols *s*₀...*s*ₙ₋₁
belonging to Σ. We denote by |*s*| its length and by *P*ₛ the set
{0, ..., |*s*| - 1} of all the locations of its symbols. A wildcard
is a new symbol ◦ which is not in Σ. This symbol matches
any symbol of the alphabet.

Pattern.

A pattern over Σ is a sequence p = p₀...pₘ₋₁, where
p₀ ∈ Σ, pₘ₋₁ ∈ Σ and pᵢ ∈ Σ ∪ {◦} for i = 1, ..., m - 2.
We say that p is included in s = s₀...sₙ₋₁ at the location
l ∈ Pₛ, denoted p ≲ l s, if ∀i ∈ {0...m - 1}, pᵢ = sᵢ₊ᵢ or
pᵢ = ◦. We also say that p is included in s, denoted p ≲ s,
if ∃l ∈ Pₛ such that p ≲ l s. The cover of p in s is defined as
the set Ls(p) = {l ∈ Pₛ | p ≲ l s}. Moreover, The support of
p in s is defined as the value |Ls(p)|.
### FPS problem.

Let $s$ be a sequence, $p$ a pattern and $\lambda \ge 1$ a minimal support threshold, called also a quorum. We say that $p$ is a frequent pattern in $s$ w.r.t. $\lambda$ if $|\mathcal{L}_s(p)| \ge \lambda$. The frequent pattern mining problem in a sequence of items (FPS) consists in computing the set $\mathcal{M}_s^\lambda$ of all the frequent patterns w.r.t. $\lambda$. For instance, let us consider the sequence $s = aaccbcabcba$ and then pattern $p = a \circ c$. We have $\mathcal{L}_s(p) = \{0, 1, 6\}$, since $p \preceq_0 s$, $p \preceq_1 s$ and $p \preceq_6 s$. In this case, if we consider that the minimal support threshold is equal to the value 3, then the pattern $p$ is a frequent pattern of $s$.

### Closed and Maximal Patterns.

A frequent pattern $p$ of a sequence $s$ is said to be closed if for any frequent pattern $q$ satisfying $q \succ p$, there is no integer $d$ such that $\mathcal{L}_s(q) = \mathcal{L}_s(p) + d$, where $\mathcal{L}_s(p) + d = \{l+d|l \in \mathcal{L}_s(p)\}$. Moreover, it is said to be maximal if for any frequent pattern $q$, $q \not\succ p$. Clearly, the set of closed frequent patterns (resp. maximal frequent patterns) is a condensed representation of the set of frequent patterns. Indeed, the frequent patterns can be obtained from the closed (resp. maximal) ones by replacing items with wildcards.

Note that if $p_1$ and $p_2$ are two patterns such that $p_1 \preceq p_2$, then if $|\mathcal{L}_s(p_2)| \ge \lambda$ then $|\mathcal{L}_s(p_1)| \ge \lambda$. This property is called anti-monotonicity.

## 3. FREQUENT PATTERN MINING IN A SEQUENCE OF ITEMSETS (FPSI)

In this section, we define a new variant of the problem of discovering patterns with wildcards in a sequence, by considering a sequence of itemsets instead of a sequence of items. The role of wildcard symbol is nicely played by the empty itemset as it match any itemset. As mentioned in the introduction, this new problem admits some similarities and differences with the classical sequential pattern mining problem introduced in [1]. The main difference resides in the definition of the notion of subsequence (inclusion), where empty itemsets are used as wildcards, and in the use or not of a single or several sequences

A sequence of itemsets $s$ over an alphabet $\Sigma$ is defined as a sequence $s_0, \dots, s_{n-1}$, where $s_i \subseteq \Sigma$ for $i = 0, \dots, n-1$. Similarly to the sequences of items, we denote by $|s|$ its length ($|s| = n$) and by $\mathcal{P}_s$ the set $\{0, \dots | s_i| - 1\}$ of the locations.

A pattern $p = p_0, \dots, p_{m-1}$ over $\Sigma$ is also defined as a sequence of itemsets where the first and the last elements are different from the empty itemset. In this context, let us mention that we do not need the wildcard symbol. Indeed, one can use the empty itemset to match any itemset. Furthermore, we say that $p$ is included in $s = s_0 \dots s_{n-1}$, denoted $p \preceq_l s$, at the location $l \in \mathcal{P}_s$ if $\forall i \in \{0 \dots m-1\}, p_i \subseteq s_{l+i}$. The relation $\preceq$ and the set $\mathcal{L}_s(p)$ are defined in the same way as in the case of the sequences of items. The cover (resp. support) of $p$ in $s$ is defined as the set $\mathcal{L}_s(p)$ (resp. as the value $|\mathcal{L}_s(p)|$).

The frequent, closed and maximal patterns are also defined in the same way. For instance, a frequent pattern $p$ of

a sequence $s$ is said to be closed if for any frequent pattern $q$ satisfying $q \succ p$, there is no integer $d$ such that $\mathcal{L}_s(q) = \mathcal{L}_s(p) + d$, where $\mathcal{L}_s(p) + d = \{l+d|l \in \mathcal{L}_s(p)\}$. The frequent patterns can be obtained from the closed (resp. maximal) ones by replacing itemsets with their subsets.

For example, let us consider the sequence of itemsets $s = \{a, b\}, \{a, b\}, \{c, d\}, \{c, e\}, \{f\}, \{g\}, \{d\}, \{a, b, d\}, \{f\}, \{c\}$ and the pattern $p = \{a, b\}, \{\}, \{c\}$. If we set the minimal support threshold to 3, then $p$ is a frequent pattern in $s$, since $\mathcal{L}_s(p) = \{0, 1, 7\}$. The pattern $p$ is also a closed frequent pattern, but $p' = \{a\}, \{\}, \{c\}$ is not closed, since $p \prec p'$.

The pattern mining task that we consider in the sequences of itemsets allows to exhibit a high degree of self similarity for better understandings of large volumes of data. For instance, a sequence of itemsets can be seen as a record of the articles bought by a customer over a period of time. In such a case, a frequent pattern could be "the customer bought acetylsalicylic acid two days after buying beer and wine in 20% of the days from 2008 to 2012".

### 3.1 Related Works and Motivations

SAT-based encodings for enumerating frequent, closed and maximal patterns in the sequences of items have been proposed in [8]. They follows the constraint programing (CP) based approach proposed recently by Luc De Raedt et al. in [10] for itemset mining. The SAT and CP based approaches in data mining are proposed in order to offer declarative and flexible frameworks. Indeed, new constraints require often new implementations in specialized approaches, while they can be easily integrated in such frameworks.

In this paper, we propose a SAT-based encodings for enumerating frequent, closed and maximal patterns in the sequences of items and the sequences of itemsets. The choice of SAT comes from our desire to exploit the efficiency of modern SAT solvers [6]. In this context, our encodings can be seen as an improvement and an extension of the encodings proposed in [8]. Indeed, we show experimentally on real world data that our encodings are better than those in [8]. Furthermore, we show that encodings in the case of the sequences of itemsets are obtained by a very slight modification of that for the sequences of items.

## 4. A NEW SAT-BASED APPROACH FOR FPS

We describe here our new Boolean encoding for the problem of enumerating the frequent patterns in a sequence of items FPS. The base idea consists in using a propositional variable to represent the location of an element of the alphabet in the candidate pattern. Moreover, we use the well-known cardinality constraint to reason about the support of the candidate pattern.

Let $\Sigma = \{a_1, \dots, a_m\}$ be an alphabet, $s$ a sequence over $\Sigma$ of length $n$ and $\lambda$ a minimal support threshold. We associate to each character $a$ appearing in $s$ a set of $k_a$ propositional variables $p_{a,0}, \dots, p_{a,(k_a-1)}$ such that $k_a = \min(\max(\mathcal{L}_s(a)) + 1, n - \lambda + 1)$. The variable $p_{a,i}$ means that $a$ is in the candidate pattern at the location $i$. In fact, that explains why we associate only $\min(\max(\mathcal{L}_s(a)) + 1, n - \lambda + 1)$ variables to each character $a$, because $\{0, \dots, \min(\max(\mathcal{L}_s(a)), n - \lambda)\}$ corresponds to the set of all possible locations of $a$ in the candidate patterns.
We first need to encode that the first symbol must be a solid character (different from the wildcard symbol). This property is expressed by the following simple clause:

$$ \bigvee_{a \in \Sigma} p_{a,0} \qquad (1) $$

The following constraint composed of binary clauses allows us to capture the locations where the candidate pattern does not appear:

$$ \bigwedge_{a \in \Sigma, 0 \le l \le n-1, 0 \le i \le k_a - 1} (p_{a,i} \wedge s_{l+i} \neq a) \rightarrow b_l \qquad (2) $$

where $b_0, \dots, b_{n-1}$ are $n$ new propositional variables. In the previous formula $b_j = 1$ if the candidate pattern does not appear in $s$ at the location $j$. Let us recall that, in classical propositional logic, we have $A \to B := \neg A \lor B$, and that explains why the previous formula can be seen as a set of binary clauses (the expressions of the for $s_{l+i} \neq a$ are constants, i.e. $s_{l+i} \neq a \in \{0, 1\}$).

In the problem of enumerating all the frequent patterns in $s$ w.r.t. $\lambda$, we need to express that the candidate pattern occurs at least $\lambda$ times. This property is obtained by the following cardinality constraint:

$$ \sum_{l=0}^{n-1} b_l \le n - \lambda \qquad (3) $$

Indeed, if this constraint is not satisfied, then we know that there exist at least $n - \lambda + 1$ locations where the candidate pattern does not appear. This is equivalent to say that there exist at most $\lambda - 1$ locations where the candidate pattern appears, i.e. it is not frequent. Otherwise, there exist at least $\lambda$ locations of the candidate pattern, i.e. it is frequent. Hence this constraint allows us to reason about the support of the considered candidate pattern and to decide whether it is greater or equal to the minimal support threshold or not.

The previous constraint involves the well known cardinality constraint (0/1 linear inequality). Several polynomial encoding of this kind of constraints into a CNF formula have been proposed in the literature. The first linear encoding of general linear inequalities to CNF have been proposed by J. P. Warners [23]. Recently, efficient encodings of the cardinality constraint to CNF have been proposed, most of them try to improve the efficiency of constraint propagation (e.g. [4, 21, 3, 16]).

**PROPOSITION 1.** *The problem of enumerating all frequent patterns in a given sequence $s$ is expressed by the constraints (1), (2) and (3).*

**PROOF.** We first prove that if $p = a_0, \dots, a_{k-1}$ is a frequent pattern, then there exists an extension of its corresponding Boolean interpretation $\mathcal{B}_p$ which is a model of (1), (2) and (3). Note that $\mathcal{B}_p$ is defined as follows: for all $a \in \Sigma$ and for all $i \in \{0, \dots, k_a\}$, if $a_i = a$ then $\mathcal{B}_p(p_{a,i}) = 1$. One can easily see that the constraint (1) is satisfied by $\mathcal{B}_p$, since $\mathcal{B}_p(p_{a_0,0}) = 1$. Let us now extend the Boolean Interpretation $\mathcal{B}_p$ to the variables $b_0, \dots, b_{n-1}$. This extension is

obtained as follows: for all $0 \le i \le n-1$, if $p \nsubseteq_i s$ then $\mathcal{B}_p(b_i) = 1$. Clearly this extension corresponds to a Boolean interpretation that satisfies (2). Finally, it also satisfies (3), since $p$ is a frequent pattern, i.e. its support is greater or equal to the minimal support threshold $\lambda$.

Conversely, we have to prove that if a Boolean interpretation $\mathcal{B}$ is a model of (1), (2) and (3), then there exists a unique pattern $p_{\mathcal{B}}$ corresponding to $\mathcal{B}$ which is frequent. Note that, using the constraints (2) and (3), we have, for all $a, a' \in \Sigma$ and for all $i \in \{0, \dots, k_a - 1\}$, if $\mathcal{B}(p_{a,i}) = \mathcal{B}(p_{a',i}) = 1$, then $a = a'$. Indeed, if there exists $a \neq a'$ such that $\mathcal{B}(p_{a,i}) = \mathcal{B}(p_{a',i}) = 1$, then we get $\sum_{l=0}^{n-1} b_l = n$ and this is in contradiction with $\sum_{l=0}^{n-1} b_l \le n - \lambda (\lambda \neq 0)$. Furthermore, using the constraint (1), we know that the first symbol of $p$ is different from $\circ$. Therefore, we deduce that there exists a unique pattern associated to $\mathcal{B}$. This pattern corresponds to $p_{\mathcal{B}} = a_0 \cdots a_{k-1}$ such that, for all $i \in \{0, \dots, k-1\}$ with $a_i \neq \circ$, $\mathcal{B}(p_{a,i}) = 1$, and $\mathcal{B}(p_{a,i}) = 0$ for all $a \in \Sigma$ with $a \neq a_i$. Moreover, using the constraint (2), we know that if $\mathcal{B}(b_i) = 1$, then $p \nsubseteq_i s$. Hence, using the cardinality constraint (3), we deduce that the support of $p$ is greater or equal to the support threshold $\lambda$. $\square$

**Example.** Consider the frequent pattern mining problem in the case of the sequence $aabb$ with 2 as minimal support threshold. Our encoding corresponds to the following formulae:

$$ \begin{aligned} & p_{a,0} \lor p_{b_0} \\ & p_{a,0} \rightarrow (b_2 \land b_3) \\ & p_{a,1} \rightarrow (b_1 \land b_2 \land b_3) \\ & p_{a,2} \rightarrow (b_0 \land b_1 \land b_2 \land b_3) \\ & p_{b,0} \rightarrow (b_0 \land b_1) \\ & p_{b,1} \rightarrow (b_0 \land b_3) \\ & p_{b,2} \rightarrow (b_2 \land b_3) \\ & b_0 + b_1 + b_2 + b_3 \le 2 \end{aligned} $$

Note that, for all Boolean interpretation $\mathcal{B}$, if $\mathcal{B}(p_{a,i}) = \mathcal{B}(p_{b,i})$, then $b_0 + b_1 + b_2 + b_3 = 4$. Hence we cannot have different solid characters at the same position. Moreover, using the last constraint, for all Boolean interpretation $\mathcal{B}$ which is a model of the encoding, we must have $\mathcal{B}(p_{a,1}) = \mathcal{B}(p_{a,2}) = 0$ and $\mathcal{B}(p_{a,0}) \neq \mathcal{B}(p_{b,1})$. If we describe each Boolean model of the formula by a subset of $\{p_{a,0}, p_{a,1}, p_{a,2}, p_{b,0}, p_{b,1}, p_{b,2}\}$, then we obtain as models $\{p_{a,0}\}$, $\{p_{b,0}\}$ and $\{p_{a,0}, p_{b,2}\}$. These Boolean models correspond to the patterns $a, b$ and $a \circ b$.

Note that in order to consider the frequent patterns with at least $min$ solid characters, we just have to add the following constraint:

$$ \sum_{a \in \Sigma, 0 \le i \le k_a - 1} p_{a,i} \ge min \qquad (4) $$

Conversely, in order to only consider the frequent patterns with at most $max$ solid characters, we add:

$$ \sum_{a \in \Sigma, 0 \le i \le k_a - 1} p_{a,i} \ge max \qquad (5) $$

Moreover, the combination of the two previous constraints allows us to only consider with the number of solid characters between $min$ and $max$. Let us mention that such extensions show that our approach is flexible.
# 5. ENUMERATING CLOSED AND MAXIMAL MOTIFS

## 5.1 Enumerating Closed Motifs (CPS)

In order to provide constraints allowing to enumerate the closed frequent patterns, we associate to each symbol a set of $k_a + (n - \min(\mathcal{L}_s(a)) - 1)$ propositional variables:

$$p_{a,-k'_a}, \dots, p_{a,k_a-1}$$

where $k'_a = n - \min(\mathcal{L}_s(a)) - 1$. Similarly to our previous encoding, the propositional variables $p_{a,0}, \dots, p_{a,k_a-1}$ allow us to reason about the possible locations of a in the candidate pattern. The variables with negative indices are used to force the candidate pattern to be closed. Our encoding of the problem of enumerating the closed frequent patterns in a sequence of items CPS is obtained by extending the previous one with new constraints.

We first have to capture all the locations where the candidates pattern appears. This is obtained by the following constraint:

$$\bigwedge_{l=0}^{n-1} (b_l \rightarrow \bigvee_{a \in \Sigma, 0 \le i \le k_a - 1} (p_{a,i} \wedge s_{l+i} \neq a)) \quad (6)$$

Indeed, the previous constraint combined to the constraint (2) allows us to obtain that, if the Boolean interpretation $\mathcal{B}$ is a model of the constraints (1), (2) and (6), then the candidate pattern that corresponds to $\mathcal{B}$ appears only in the locations $\{0 \le l \le n - 1 | \mathcal{B}(b_l) = 0\}$.

Now, we introduce a necessary, but not sufficient, constraint, w.r.t. the previous constraints, for obtaining a closed frequent pattern:

$$\bigwedge_{a \in \Sigma, 0 \le i \le k_a - 1} (\bigwedge_{l=0}^{n-1} \bar{b}_l \rightarrow s_{l+i} = a) \rightarrow p_{a,i} \quad (7)$$

Intuitively, the previous constraint maximizes the number of the symbols different from wildcard on the right side of the symbol represented by the propositional variable having 0 as index.

We now define a constraint with the propositional variables having the negative indices. Conversely to the previous constraint, the following constraint allows us to maximize the number of the symbols different from wildcard on the left side:

$$\bigwedge_{a \in \Sigma, 1 \le i \le k'_a} (\bigwedge_{l=0}^{n-1} \bar{b}_l \rightarrow s_{l-i} = a) \leftrightarrow p_{a,-i} \quad (8)$$

Let us note that if the Boolean interpretation $\mathcal{B}$ is a model of (1) $\wedge$ (2) $\wedge$ (3) $\wedge$ (6) $\wedge$ (7) $\wedge$ (8) and $\mathcal{B}(p_{a,i}) = 1$, then, for all $b \in \Sigma$ such that $a \neq b$ and $p_{b,i}$ exists, $\mathcal{B}(p_{b,i}) = 0$ holds. This property is mainly obtained from the constraints (2) and (8) (see arguments used in the proof of Proposition 1). A closed motif is obtained from a model by using the propositional variables associated to the elements of $\Sigma$ and evaluated to 1 by this model. Let $p_{a_0,i_0}, p_{a_1,i_1}, \dots, p_{a_{k-1},i_{k-1}}$ be these

variables. In this case, the closed motif is:

$$a_0 \overbrace{\underbrace{a_1}_{i_1-i_0-1} \dots \underbrace{a_{k-1}}_{i_{k-1}}}^{i_1-i_0-1}$$

We now provide another encoding without using propositional variables with negative indices. The idea consists in excluding each interpretation whenever its corresponding pattern is not closed. This encoding is obtained by replacing the constraint (8) with the following constraint:

$$\bigwedge_{a \in \Sigma, 1 \le i \le k'_a} -(\bigwedge_{l=0}^{n-1} \bar{b}_l \rightarrow s_{l-i} = a) \quad (9)$$

By the previous constraint, we simply force the candidate pattern to be closed.

**PROPOSITION 2.** *The problem of enumerating all the closed frequent patterns in a given sequence s is expressed by the constraints (1), (2), (3), (6), (7) and (9).*

**PROOF.** Let $p = a_0, \dots, a_{k-1}$ be a closed frequent pattern. We define its corresponding Boolean interpretation $\mathcal{B}_p$ as follows: for all $a \in \Sigma$ and for all $i \in \{0, \dots, k_a\}$, if $a_i = a$ then $\mathcal{B}_p(p_{a,i}) = 1$. We extend $\mathcal{B}_p$ to the propositional variables $\{b_0, \dots, b_{n-1}\}$ as follows: $p \nleq_i s$ iff $\mathcal{B}_p(b_i) = 1$, for $i = 0, \dots, n-1$. By using similar arguments as in our proof of Proposition 1, we know that $\mathcal{B}_p$ satisfies the constraints (1), (2) and (3). It also satisfies (6), since if $\mathcal{B}_p(b_i) = 1$ then $p \nleq_i s$. In this context, the support of $p$ is equal to $|\{b_i | \mathcal{B}_p(b_i) = 0\}|$. This allows us to deduce that $\mathcal{B}_p$ satisfies (7) and (9), since $p$ is closed. Indeed, if (7) or (9) are not satisfied by $\mathcal{B}_p$, then there exists a pattern $p'$ such that $p \prec p'$ with a support greater or equal to that of $p$ and we get a contradiction because that means that $p$ is not a closed pattern.

Conversely, consider $\mathcal{B}$ a model of (1), (2), (3), (6), (7) and (9). Using the constraints (2) and (3), we have, for all $a, a' \in \Sigma$ and for all $i \in \{0, \dots, k_a - 1\}$, if $\mathcal{B}(p_{a,i}) = \mathcal{B}(p_{a',i}) = 1$, then $a = a'$. Hence, there exists a unique pattern associated to $\mathcal{B}$ that corresponds to $p_{\mathcal{B}} = a_0 \cdots a_{k-1}$ such that, for all $i \in \{0, \dots, k-1\}$ with $a_i \neq 0$, $\mathcal{B}(p_{a,i}) = 1$, and $\mathcal{B}(p_{a,i}) = 0$ for all $a \in \Sigma$ with $a \neq a_i$. Using Proposition 1, we know that the pattern $p_{\mathcal{B}}$ is frequent. The constraint (6) allows us to obtain that the support of $p$ is equal to $|\{b_i | \mathcal{B}(b_i) = 0\}|$. Using the constraints (7) and (9), we now that there is no frequent pattern $q$ having the same support as $p$ such that $p \prec q$. Therefore, we deduce that $p$ is a closed frequent pattern. $\square$

Note that in order to enumerate all frequent patterns without any condition on their supports, we only have to remove the constraint 3.

## 5.2 Enumerating Maximal Motifs (MPS)

In our encoding of the problem of enumerating the maximal frequent patterns in a sequence of items MPS, we only use the propositional variables associated to the elements of $\Sigma$ with positive indices, i.e. we associate to each symbol $a$ a set of $k_a$ propositional variables $p_{a,0}, \dots, p_{a,(k_a-1)}$. Our encoding of MPS is obtained by extending the one of FPS in a similar way as our encoding of CPS.

In order to enumerate the maximal frequent patterns, we
need to capture all the locations where the candidates pattern appears. To this end, similarly to our encodings of CPS, we use the constraint (6). Indeed, the combination of the constraints (2) and (6) allows us to obtain, if $\mathcal{B}$ is a Boolean model of these two constraints, then $\{0 \le l \le n-1 | \mathcal{B}(b_l) = 0\}$ corresponds to the set of the locations where the candidate pattern appears.

We now provide the constraint allowing to maximize the number of symbols different from wildcard on the right side of the symbol represented by the propositional variable having 0 as index:

$$ \bigwedge_{a \in \Sigma, 1 \le i \le k_a - 1} \left( \sum_{l=0}^{n-1} \bar{b}_l \wedge s_{l+i} = a \ge \lambda \right) \to p_{a,i} \quad (10) $$

Intuitively, the constraint means that if $p = a_0 \cdots a_{k-1}$ is the patter candidate and there exists $a \in \Sigma$ such that then pattern $a_0 \cdots a_{k-1} \circ \cdots \circ a$ have the same support as $p$, then $p$ is not a maximal frequent pattern.

Coverely to the previous constraint, we finally introduce the constraint allowing to maximize the number of symbols different from wildcard on the left side of the symbol represented by the propositional variable having 0 as index:

$$ \bigwedge_{a \in \Sigma, 1 \le i \le k'_a} \neg\left(\sum_{l=0}^{n-1} \bar{b}_l \wedge s_{l-i} = a \ge \lambda\right) \quad (11) $$

One can easily see that it is equivalent to the following constraint:

$$ \bigwedge_{a \in \Sigma, 1 \le i \le k'_a} \sum_{l=0}^{n-1} \bar{b}_l \wedge s_{l-i} = a \le \lambda - 1 \quad (12) $$

Indeed, the constraint $\neg(\sum_{l=0}^{n-1} x \ge \lambda)$ is equivalent to cardinality constraint $\sum_{l=0}^{n-1} x \le \lambda - 1$.

**PROPOSITION 3.** The problem of enumerating all the maximal frequent patterns in a given sequence $s$ is expressed by the constraints (1), (2), (3), (6), (10) and (12).

**PROOF.** Similar to our proof of Proposition 2. $\square$

Let us mention that we can also use the constraints (4) and (5) to reason about the number of the solid characters in the considered patterns in the cases of CPS and MPS. Furthermore, we can use a constraint in order to only consider the closed and maximal patterns with support between $\lambda$ and $\lambda'$. This constraint is the following:

$$ \sum_{l=0}^{n-1} b_l \ge n - \lambda' \quad (13) $$

# 6. SAT-BASED ENCODINGS AND SEQUENCE OF ITEMSETS

In this section, we extend our SAT-based approach for discovering frequent, closed and maximal patterns in a sequence of itemsets. We will show that our encodings in this case can be obtained from the previous ones with a very slight modification.

Our encoding of the problem of enumerating the frequent patterns in a sequence of itemsets FPSI can be easily obtained from the one of FPS. We only have to replace the

equalities of the form $s_{l+i} \ne a$ with $a \notin s_{l+i}$:

$$ \bigvee_{a \in \Sigma} p_{a,0} \quad (14) $$

$$ \bigwedge_{a \in \Sigma, 0 \le l \le n-1, 0 \le i \le k_a - 1} (p_{a,i} \wedge a \notin s_{l+i}) \to b_l \quad (15) $$

$$ \sum_{l=0}^{n-1} b_l \le n - \lambda \quad (16) $$

In this case, the variable $p_{a,i}$ means that the symbol $a$ is in the candidate pattern in the itemset at the location $i$. Let us recall that we use the empty itemset as wildcard.

We denote by CPSI (resp. MPSI) the problem of enumerating the closed (resp. maximal) frequent patterns in a sequence of itemsets. Similarly to FPSI, Boolean encodings of CPSI and MPSI can be directly obtained from the ones of respectively CPS and MPS by replacing the expressions of the form $s_{l+i} \ne a$ (resp. $s_{l+i} = a$) with $a \notin s_{l+i}$ (resp. $a \in s_{l+i}$).

**Constraints of closeness:**

$$ \bigwedge_{l=0}^{n-1} (b_l \to \bigvee_{a \in \Sigma, 0 \le i \le k_a - 1} (p_{a,i} \wedge a \notin s_{l+i})) \quad (17) $$

$$ \bigwedge_{a \in \Sigma, 0 \le i \le k_a - 1} \left( \bigwedge_{l=0}^{n-1} \bar{b}_l \to a \in s_{l+i} \right) \to p_{a,i} \quad (18) $$

$$ \bigwedge_{a \in \Sigma, 1 \le i \le k'_a} \neg\left(\sum_{l=0}^{n-1} \bar{b}_l \to a \in s_{l-i}\right) \quad (19) $$

**Constraints of maximality:** to express the maximality, we add the following two constraints to (17):

$$ \bigwedge_{a \in \Sigma, 1 \le i \le k_a - 1} \left( \sum_{l=0}^{n-1} \bar{b}_l \wedge a \in s_{l+i} \ge \lambda \right) \to p_{a,i} \quad (20) $$

$$ \bigwedge_{a \in \Sigma, 1 \le i \le k'_a} \sum_{l=0}^{n-1} \bar{b}_l \wedge a \in s_{l-i} \le \lambda - 1 \quad (21) $$

The slight modification of our encodings in the case of the sequences of items in order to obtain encodings for the sequences of itemsets clearly shows the high flexibility of our proposed framework.

# 7. IMPLEMENTATION AND EXPERIMENTS

In our study, we carried out a preliminary experimental evaluation of our proposed approaches using two different datasets.

1. *Bioinformatics:* proteinic data encoded as a sequence of items, where an item is an amino-acid <fnref n="1" />.

<footnote n="1">¹http://www.biomedcentral.com/1471-2105/11/175/additional/</footnote>
2. Synthetic datasets: we use the well-known IBM item-set data generator<fnref n="2" /> to derive datasets with different features. We used this generator to get sequences of itemsets, that can be seen as an ordered set of transactions.

To make fair our comparison with the approach proposed in [8], we adopted the similar choices in our implementations. First, as we deal with the problem of enumerating all the models of a given CNF formula encoding our sequence mining problem, we implemented a model enumeration solver based on the CDCL-based solver MiniSAT 2.2 <fnref n="3" />. To enumerate all the models, each time a model is found, we add only the negation of the sub-model restricted to the literals encoding the pattern to the formula and we restart the search. Secondly, as our SAT encodings include cardinality constraints, we also use the BDD encoding [5] using BoolVar/PB open source java library <fnref n="4" />.

In the first experiment, we compare our new SAT encoding (noted CPS1) against the SAT encoding proposed in [8] (noted CPS2), on bioinformatics datasets (sequences of items). This first evaluation concerns the enumeration of frequent closed patterns with wild cards in a sequence of items. We consider a sequence of fixed length and we measure the evolution of computation time with respect to the minimal support threshold (quorum) $\lambda$. The quorum evolves linearly ($\lambda_0 = 5$ and $\lambda_i = \lambda_{i-1} + 5$). Several datasets have been considered, their evaluation shows similar behavior. The results obtained on a representative dataset are depicted in Figure 1. This experiment confirms that in the case of sequences of items, our new SAT-based sequence mining approach outperforms (in terms of CPU time) the approach proposed recently in [8]. We also obtain significant improvement w.r.t. the size of the encoding. For instance, if we consider the most difficult dataset of the Figure 1 (quorum $\lambda = 5$), the obtained CNF formula using our encoding contains about 19 millions of clauses and 3 millions of variables, whereas with the encoding proposed in [8] the formula contains about 30 millions of clauses and 7.5 millions of variables.

The second experiment concerns the new extension of the problem to the case of sequence of itemsets. Our goal is to show the feasibility of our proposed extension and its associated encodings. For our evaluation, we considered synthetic datasets, generated using the approach outlined in [1] and also used by several authors (e.g. [12]). In our context, we only consider a single sequence of itemsets with different features (size of the sequence, number of items, average size of the itemsets). In Figure 2, we illustrate the results obtained on two datasets: dataset1 (size of the sequence = 100, avg. size of itemsets = 15, number of items = 40) and dataset2 obtained from dataset1 by cutting the sequence at 50th position. The quorum is also varied linearly as in the first experiment. The main observation that can be made, is that the hardness of the enumeration problem increase as the quorum decrease. Indeed, for smaller values of $\lambda$, the number of frequent closed patterns is huge, leading to even harder problems. However for higher values of $\lambda$, the enu-

meration problem becomes easy as the number of interesting patterns decreases.

<figure><img src="image_23.png" /><figcaption>Figure 1: Bioinfo: time Vs quorum (Sequence of Items - Frequent Closed Patterns)</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Figure 2: Synthetic datasets: time Vs quorum (Sequence of Itemsets - Frequent Closed Patterns)</figcaption></figure>

As a summary, in the above experiments, we have shown that our encoding significantly improve the one proposed in [8, 7]. For comparison purposes, we used the same encoding of the cardinality constraint and also the same algorithm for enumerating all models of a CNF formula. We think that several room for future improvements can be obtained by using the state-of-the-art encoding of the cardinality [3], and by using more efficient model enumeration algorithm [13, 11, 25]. Obviously, our SAT based approach is less efficient than dedicated approaches such as the state-of-the-art algorithm proposed by Arimura et al. in [2]. However, our SAT model is declarative and highly flexible. Indeed, the SAT encoding for a sequence of itemsets is obtained with a very slight modification of the SAT encoding of a sequence of items. Also, one can easily combine several kind of constraints. Finally, SAT-based data mining benefits from the continuous progress of SAT community.

<footnote n="2">²http://sourceforge.net/projects/ibmquestdatagen/</footnote>

<footnote n="3">³MiniSAT: http://minisat.se/</footnote>

<footnote n="4">⁴BoolVAR/PB : http://boolvar.sourceforge.net/</footnote>
## 8. ACKNOWLEDGMENTS

We thank the reviewers for their helpful comments. This work has been supported in part by the CNRS and the French ANR project "DAG: Declarative Approaches for Enumerating Interesting Patterns" under the Défis program 2009.

## 9. CONCLUSION AND PERSPECTIVES

The contributions of this paper are twofolds. First, we proposed an interesting improvement of the SAT-based encodings introduced in [8] for enumerating frequent, closed and maximal patterns with wildcards in a sequence of items. Secondly, we introduced a new and natural extension of the problem to deal with the sequences of itemsets. Interestingly, its encoding to SAT is obtained with a slight modification of the SAT encoding of the problem dealing with the sequences of items. This clearly shows the high flexibility of our proposed framework and opens several issues for future research. We first plan to investigate other variants of the problem such as sequences of sequences of items or itemsets. It would be interesting to extend our encoding with constraints on the form of the enumerated patterns (restriction on the number of consecutive wildcards, regular expressions, etc). Finally, on the Boolean satisfiability side, the design of efficient model generation procedures is an important issue for SAT-based data mining framework in general and to other important application domains.

## 10. REFERENCES

[1] R. Agrawal and R. Srikant. Mining sequential patterns. In A. L. P. C. Philip S. Yu, editor, *Proceedings of the Eleventh International Conference on Data Engineering (ICDE'1995)*, pages 3-14. IEEE Computer Society, 1995.

[2] H. Arimura and T. Uno. An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence. *Journal of Combinatorial Optimization*, 13, 2007.

[3] R. Asin, R. Nieuwenhuis, A. Oliveras, and E. Rodriguez-Carbonell. Cardinality networks: a theoretical and empirical study. *Constraints*, 16(2):195-221, 2011.

[4] O. Bailleux and Y. Boufkhad. Efficient CNF Encoding of Boolean Cardinality Constraints. In *9th International Conference on Principles and Practice of Constraint Programming - CP 2003*, pages 108-122, 2003.

[5] O. Bailleux, Y. Boufkhad, and O. Roussel. A translation of pseudo boolean constraints to sat. *Journal on Satisfiability, Boolean Modeling and Computation (JSAT)*, 2(1-4), 2006.

[6] A. Biere, M. J. H. Heule, H. van Maaren, and T. Walsh, editors. *Handbook of Satisfiability*, volume 185 of *Frontiers in AI and Applications*. IOS Press, 2009.

[7] E. Coquery, S. Jabbour, and L. Sais. A constraint programming approach for enumerating motifs in a sequence. In M. Spiliopoulou, H. Wang, D. J. Cook, J. Pei, W. Wang, O. R. Zaïane, and X. Wu, editors, *ICDM Workshops*, pages 1091-1097. IEEE, 2011.

[8] E. Coquery, S. Jabbour, L. Saïs, and Y. Salhi. A SAT-Based Approach for Discovering Frequent, Closed

and Maximal Patterns in a Sequence. In *20th European Conference on Artificial Intelligence ECAI*, pages 258-263, 2012.

[9] M. Davis, G. Logemann, and D. W. Loveland. A machine program for theorem-proving. *Communications of the ACM*, 5(7):394-397, 1962.

[10] L. De Raedt, T. Guns, and S. Nijssen. Constraint Programming for Itemset Mining. In *Proceedings of the 14th International Conference on Knowledge Discovery and Data Mining (ACM SIGKDD'2008)*, pages 204-212, Las Vegas, Nevada, USA, August 24-27 2008.

[11] M. Gebser, B. Kaufmann, A. Neumann, and T. Schaub. *clasp*: A conflict-driven answer set solver. In *9th International Conference Logic Programming and Nonmonotonic Reasoning (LPNMR'2007)*, volume 4483 of *Lecture Notes in Computer Science*, pages 260-265. Springer, 2007.

[12] K. Gouda, M. Hassaan, and M. J. Zaki. Prism: A primal-encoding approach for frequent sequence mining. In *Proceedings of the 7th IEEE International Conference on Data Mining (ICDM 2007)*, pages 487-492, Omaha, Nebraska, USA, October 28-31 2007. IEEE Computer Society.

[13] O. Grumberg, A. Schuster, and A. Yadgar. Memory efficient all-solutions sat solver and its application for reachability analysis. In *In Proceedings of the 5th International Conference on Formal Methods in Computer-Aided Design (FMCAD)*, pages 275-289. Springer, 2004.

[14] T. Guns, S. Nijssen, and L. D. Raedt. Itemset mining: A constraint programming perspective. *Artificial Intelligence*, 175(12-13):1951-1983, 2011.

[15] Y. Hamadi, S. Jabbour, and L. Sais. Learning from conflicts in propositional satisfiability. *4OR*, 10(1):15-32, 2012.

[16] S. Jabbour, L. Sais, and Y. Salhi. A pigeon-hole based encoding of cardinality constraints. In *In proceedings of the 29th International Conference on Logic Programming (ICLP'2013)*, August 24-29 2013.

[17] J. P. Marques-Silva and K. A. Sakallah. GRASP - A New Search Algorithm for Satisfiability. In *Proceedings of IEEE/ACM CAD*, pages 220-227, 1996.

[18] L. Parida, I. Rigoutsos, A. Floratos, D. Platt, and Y. Gao. Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and an Efficient Polynomial Time Algorithm. In *ACM-SIAM Symposium on Discrete Algorithms*, pages 297-308, 2000.

[19] L. Parida, I. Rigoutsos, and D. Platt. An output-sensitive flexible pattern discovery algorithm. In *In proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching (CPM'2001)*, volume 2089 of *Lecture Notes in Computer Science*, pages 131-142. Springer, 2001.

[20] N. Pisanti, M. Crochemore, R. Grossi, and M.-F. Sagot. Bases of motifs for generating repeated patterns with wild cards. *IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB'2005)*, 2(1):40-50, 2005.

[21] C. Sinz. Towards an Optimal CNF Encoding of Boolean Cardinality Constraints. In *11th International*
*Conference on Principles and Practice of Constraint Programming - CP 2005*, pages 827–831, 2005.

[22] G. Tseitin. On the complexity of derivations in the propositional calculus. In H. Slesenko, editor, *Structures in Constructives Mathematics and Mathematical Logic, Part II*, pages 115–125, 1968.

[23] J. P. Warners. A linear-time transformation of linear inequalities into conjunctive normal form. *Information Processing Letters*, 68(2):63–69, 1998.

[24] L. Zhang, C. F. Madigan, M. W. Moskewicz, and S. Malik. Efficient conflict driven learning in Boolean satisfiability solver. In *IEEE/ACM CAD’2001*, pages 279–285, 2001.

[25] W. Zhao and W. Wu. Asig: An all-solution sat solver for cnf formulas. In *11th International Conference on Computer-Aided Design and Computer Graphics, CAD/Graphics 2009, Huangshan, China, August 19-21 (CAD/Graphics)*, pages 508–513. IEEE, 2009.
# The Top-$k$ Frequent Closed Itemset Mining Using Top-$k$ SAT Problem

Said Jabbour, Lakhdar Sais and Yakoub Salhi

CRIL - CNRS, Université d'Artois, France
F-62307 Lens Cedex, France
{jabbour, sais, salhi}@cril.fr

**Abstract.** In this paper, we introduce a new problem, called Top-$k$ SAT, that consists in enumerating the Top-$k$ models of a propositional formula. A Top-$k$ model is defined as a model with less than $k$ models preferred to it with respect to a preference relation. We show that Top-$k$ SAT generalizes two well-known problems: the partial Max-SAT problem and the problem of computing minimal models. Moreover, we propose a general algorithm for Top-$k$ SAT. Then, we give the first application of our declarative framework in data mining, namely, the problem of enumerating the Top-$k$ frequent closed itemsets of length at least *min* ($FCIM_{min}^k$). Finally, to show the nice declarative aspects of our framework, we encode several other variants of $FCIM_{min}^k$ into the Top-$k$ SAT problem.

## 1 Introduction

The problem of mining frequent itemsets is well-known and essential in data mining, knowledge discovery and data analysis. It has applications in various fields and becomes fundamental for data analysis as datasets and datastores are becoming very large. Since the first article of Agrawal [1] on association rules and itemset mining, the huge number of works, challenges, datasets and projects show the actual interest in this problem (see [2] for a recent survey of works addressing this problem). Important progress has been achieved for data mining and knowledge discovery in terms of implementations, platforms, libraries, etc. As pointed out in [2], several works deal with designing highly scalable data mining algorithms for large scale datasets. An important problem of itemset mining and data mining problems, in general, concerns the huge size of the output, from which it is difficult for the user to retrieve relevant informations. Consequently, for practical data mining, it is important to reduce the size of the output, by exploiting the structure of the itemsets data. Computing for example, closed, maximal, condensed, discriminative itemset patterns are some of the well-known and useful techniques. Most of the works on itemset mining require the specification of a minimum support threshold $\lambda$. This constraint allows the user to control at least to some extent the size of the output by mining only itemsets covering at least $\lambda$ transactions. However, in practice, it is difficult for users to provide an appropriate threshold. As pointed out in [3], a too small threshold may lead to the generation of a huge number of itemsets, whereas a too high value of the threshold may result in no answer. In [3], based on a total ranking between patterns, the authors propose to mine the $n$ most interesting itemsets of arbitrary length. In [4], the proposed task consists in mining Top-$k$ frequent closed itemsets of
length greater than a given lower bound *min*, where *k* is the desired number of frequent closed itemsets to be mined, and *min* is the minimal length of each itemset. The authors demonstrate that setting the minimal length of the itemsets to be mined is much easier than setting the usual frequency threshold. Since the introduction of Top-*k* mining, several research works investigated its use in graph mining (e.g. [5, 6]) and other datamining tasks (e.g. [7, 8]). This new framework can be seen as a nice way to mine the *k* preferred patterns according to some specific constraints or measures. Starting from this observation, our goal in this paper is to define a general logic based framework for enumerating the Top-*k* preferred patterns according to a predefined preference relation.

The notion of preference has a central role in several disciplines such as economy, op-
erations research and decision theory in general. Preferences are relevant for the design
of intelligent systems that support decisions. Modeling and reasoning with preferences
play an increasing role in Artificial Intelligence (AI) and its related fields such as non-
monotonic reasoning, planning, diagnosis, configuration, constraint programming and
other areas in knowledge representation and reasoning. For example, in nonmonotonic
reasoning the introduction of preferential semantics by Shoham [9] gives an unifying
framework where nonmonotonic logic is reduced to a standard logic with a preference
relation (order) on the models of that standard logic. Several models for representing
and reasoning about preferences have been proposed. For example, soft constraints [10]
are one of the most general way to deal with quantitative preferences, while CP-net
(Conditional Preferences networks) [11] is most convenient for qualitative preferences.
There is a huge literature on preferences (see [12–14] for a survey at least from the AI
perspective). In this paper we focus on qualitative preferences defined by a preference
relation on the models of a propositional formula. Preferences in propositional satisfi-
ability (SAT) has not received a lot of attention. In [15], a new approach for solving
satisfiability problems in the presence of qualitative preferences on literals (defined as
partial ordered set) is proposed. The authors particularly show how DPLL procedure
can be easily adapted for computing optimal models induced by the partial order. The
issue of computing optimal models using DPLL has also been investigated in SAT [16].

The contribution of this paper is twofold. Firstly, we propose a generic framework for
dealing with qualitative preferences in propositional satisfiability. Our qualitative pref-
erences are defined using a reflexive and transitive relation (preorder) over the models
of a propositional formula. Such preference relation on models is first used to introduce
a new problem, called Top-k SAT, defined as the problem of enumerating the Top-k
models of a propositional formula. Here a Top-k model is defined as a model with no
more than k-1 models preferred to it with respect to the considered preference relation.
Then, we show that Top-k SAT generalizes the two well-known problems, the partial
Max-SAT problem and the problem of generating minimal models. We also define a
particular preference relation that allows us to introduce a general algorithm for com-
puting the Top-k models.

Secondly, we introduce the first application of our declarative framework to data min-
ing. More precisely, we consider the problem of mining Top-k frequent closed itemsets
of minimum length *min* [17]. In this problem, the minimum support threshold usually used in frequent itemset mining is not known, while the minimum length can be set to 0 if one is interested in itemsets of arbitrary length. In itemset mining, the notion of Top-*k* frequent itemsets is introduced as an alternative to finding the appropriate value for the minimum support threshold. It is also an elegant way to control the size of the output. Consequently, itemset mining is clearly a nice application of our new defined Top-*k* SAT problem. In this paper, we provide a SAT encoding and we show that computing the Top-*k* closed itemsets of length at least *min* corresponds to computing the Top-*k* models of the obtained propositional formula. Finally, to show the nice declarative aspects of our framework, we encode several other variants of this data mining problem as Top-*k* SAT problems. Finally, preliminary experiments on some datasets show the feasibility of our proposed approach.

## 2 Preliminary definitions and notations

In this section, we describe the Boolean satisfiability problem (SAT) and some necessary notations. We consider the conjunctive normal form (CNF) representation for the propositional formulas. A CNF formula $\Phi$ is a conjunction of clauses, where a *clause* is a disjunction of literals. A *literal* is a positive (*p*) or negated (*\neg p*) propositional variable. The two literals *p* and *\neg p* are called *complementary*. A CNF formula can also be seen as a set of clauses, and a clause as a set of literals. Let us recall that any propositional formula can be translated to CNF using linear Tseitin's encoding [18]. We denote by $Var(\Phi)$ the set of propositional variables occuring in $\Phi$.

An interpretation $\mathcal{M}$ of a propositional formula $\Phi$ is a function which associates a value $\mathcal{M}(p) \in \{0, 1\}$ (0 corresponds to *false* and 1 to *true*) to the variables *p* in a set *V* such that $Var(\Phi) \subseteq V$. A *model* of a formula $\Phi$ is an interpretation $\mathcal{M}$ that satisfies the formula. The *SAT problem* consists in deciding if a given CNF formula admits a model or not.

We denote by $\bar{l}$ the complementary literal of *l*. More precisely, if $l = p$ then $\bar{l}$ is $\neg p$ and if $l = \neg p$ then $\bar{l}$ is *p*. For a set of literals $L, \bar{L}$ is defined as $\{\bar{l} | l \in L\}$. Moreover, we denote by $\overline{\mathcal{M}}$ ($\mathcal{M}$ is an interpretation over $Var(\Phi)$) the clause $\bigvee_{p \in Var(\Phi)} s(p)$, where $s(p) = p$ if $\mathcal{M}(p) = 0$, $\neg p$ otherwise. Let $\Phi$ be a CNF formula and $\mathcal{M}$ an interpretation over $Var(\Phi)$. We denote by $\mathcal{M}(\Phi)$ the set of clauses satisfied by $\mathcal{M}$. Let us now consider a set $X$ of propositional variables such that $X \subseteq Var(\Phi)$. We denote by $\mathcal{M} \cap X$ the set of variables $\{p \in X | \mathcal{M}(p) = 1\}$. Moreover, we denote by $\mathcal{M}|_X$ the restriction of the model $\mathcal{M}$ to $X$.

## 3 Preferences and Top-k Models

Let $\Phi$ be a propositional formula and $\Lambda_{\Phi}$ the set of all its models. A preference relation $\succeq$ over $\Lambda_{\Phi}$ is a reflexive and transitive binary relation (a preorder). The statement $\mathcal{M} \succeq$
$\mathcal{M}'$ means that $\mathcal{M}$ is at least as preferred as $\mathcal{M}'$. We denote by $P(\Phi, \mathcal{M}, \succeq)$ the subset of $\Lambda_{\Phi}$ defined as follows:

$$P(\Phi, \mathcal{M}, \succeq) = \{\mathcal{M}' \in \Lambda_{\Phi} | \mathcal{M}' \succ \mathcal{M}\}$$

where $\mathcal{M}' \succ \mathcal{M}$ means that $\mathcal{M}' \succeq \mathcal{M}$ holds but $\mathcal{M} \succeq \mathcal{M}'$ does not. It corresponds to all models that are strictly preferred to $\mathcal{M}$.

We now introduce an equivalence relation $\approx_X$ over $P(\Phi, \mathcal{M}, \succeq)$, where $X$ is a set of propositional variables. It is defined as follows:

$$\mathcal{M}' \approx_X \mathcal{M}'' \text{ iff } \mathcal{M}' \cap X = \mathcal{M}'' \cap X$$

Thus, the set $P(\Phi, \mathcal{M}, \succeq)$ can be partitioned into a set of equivalence classes by $\approx_X$, denoted by $[P(\Phi, \mathcal{M}, \succeq)]^X$. In our context, this equivalence relation is used to take into consideration only a subset of propositional variables. For instance, we introduce new variables in Tseitin's translation [18] of propositional formula to CNF, and such variables are not important in the case of some preference relations.

**Definition 1 (Top-k Model).** Let $\Phi$ be a propositional formula, $\mathcal{M}$ a model of $\Phi$, $\succeq$ a preference relation over the models of $\Phi$ and $X$ a set of propositional variables. $\mathcal{M}$ is a Top-k model w.r.t. $\succeq$ and $X$ iff $|[P(\Phi, \mathcal{M}, \succeq)]^X| \le k-1$.

Let us note that the number of the Top-k models of a formula is not necessarily equal to $k$. Indeed, it can be strictly greater or smaller than $k$. For instance, if a formula is unsatisfiable, then it does not have a Top-k model for any $k \ge 1$. Furthermore, if the considered preference relation is a total order, then the number of Top-k models is always smaller than or equal to $k$.

It is easy to see that we have the following monotonicity property: if $\mathcal{M}$ is a Top-k model and $\mathcal{M}' \succeq \mathcal{M}$, then $\mathcal{M}'$ is also a Top-k model.

**Top-k SAT problem.** Let $\Phi$ be propositional formula, $\succeq$ a preference relation over the models of $\Phi$, $X$ a set of propositional variables and $k$ a strictly positive integer. The Top-k SAT problem consists in computing a set $\mathcal{L}$ of Top-k models of $\Phi$ with respect to $\succeq$ and $X$ satisfying the two following properties:

1. for all $\mathcal{M}$ Top-k model, there exists $\mathcal{M}' \in \mathcal{L}$ such that $\mathcal{M} \approx_X \mathcal{M}'$; and

2. for all $\mathcal{M}$ and $\mathcal{M}'$ in $\mathcal{L}$, if $\mathcal{M} \neq \mathcal{M}'$ then $\mathcal{M} \not\succeq_X \mathcal{M}'$.

The two previous properties come from the fact that we are only interested in the truth values of the variables in $X$. Indeed, the first property means that, for all Top-k model, there is a model in $\mathcal{L}$ equivalent to it with respect to $\approx_X$. Moreover, the second property means that $\mathcal{L}$ does not contain two equivalent Top-k models.

In the following definition, we introduce a particular type of preference relations, called $\delta$-preference relation, that allows us to introduce a general algorithm for computing Top-k models.
**Definition 2.** Let $\Phi$ be a formula and $\succeq$ a preference relation on the models of $\Phi$. Then $\succeq$ is a $\delta$-preference relation, if there exists a polytime function $f_{\succeq}$ from Boolean interpretations to the set of CNF formulae such that, for all $\mathcal{M}$ model of $\Phi$ and for all $\mathcal{M}'$ Boolean interpretation, $\mathcal{M}'$ is a model of $\Phi \wedge f_{\succeq}(\mathcal{M})$ iff $\mathcal{M}'$ is a model of $\Phi$ and $\mathcal{M} \not\succeq \mathcal{M}'$.

Note that, given a model $\mathcal{M}$ of a CNF formula $\Phi$, $f_{\succeq}(\mathcal{M})$ is a formula such that when added to $\Phi$ together with $\overline{\mathcal{M}}$, the models of the resulting formula are different from $\mathcal{M}$ and they are at least as preferred as $\mathcal{M}$. Intuitively, this can be seen as a way to introduce a lower bound during the enumeration process. From now, we only consider $\delta$-preference relations.

## 3.1 Top-k SAT and Partial MAX-SAT

In this section, we show that the Top-k SAT problem generalizes the Partial MAX-SAT problem (e.g. [19]). In Partial MAX-SAT each clause is either relaxable (soft) or non-relaxable (hard). The objective is to find an interpretation that satisfies all the hard clauses together with the maximum number of soft clauses. The MAX-SAT problem is a particular case of Partial MAX-SAT where all the clauses are relaxable.

Let $\Phi = \Phi_h \wedge \Phi_s$ be a partial MAX-SAT instance such that $\Phi_h$ is the hard part and $\Phi_s$ the soft part. The relation denoted by $\succeq_{\Phi_s}$ corresponds to preference relation defined as follows: for all $\mathcal{M}$ and $\mathcal{M}'$ models of $\Phi_h$ defined over $\mathrm{Var}(\Phi_h \wedge \Phi_s)$, $\mathcal{M} \succeq_{\Phi_s} \mathcal{M}'$ if and only if $|\mathcal{M}(\Phi_s)| \ge |\mathcal{M}'(\Phi_s)|$.

Note that $\succeq_{\Phi_s}$ is a $\delta$-preference relation. Indeed, we can define $f_{\succeq_{\Phi_s}}$ as follows:

$$f_{\succeq_{\Phi_s}}(\mathcal{M}) = (\bigwedge_{C \in \Phi_s} p_C \leftrightarrow C) \wedge \sum_{C \in \Phi_s} p_C \ge |\mathcal{M}(\Phi_s)|$$

where $p_C$ for $C \in \Phi_s$ are fresh propositional variables.

The Top-1 models of $\Phi_h$ with respect to $\succeq_{\Phi_s}$ and $\mathrm{Var}(\Phi)$ correspond to the set of all solutions of $\Phi$ in Partial Max-SAT. Naturally, they are the most preferred models with respect to $\succeq_{\Phi_s}$, and that means they satisfy $\Phi_h$ and satisfy the maximum number of clauses in $\Phi_s$. Thus, the Top-k SAT problem can be seen as a generalization of Partial MAX-SAT.

The formula $f_{\succeq_{\Phi_s}}(\mathcal{M})$ involves the well-known cardinality constraint (0/1 linear inequality). Several polynomial encodings of this kind of constraints into a CNF formula have been proposed in the literature. The first linear encoding of general linear inequalities to CNF has been proposed by Warners [20]. Recently, efficient encodings of the cardinality constraint to CNF have been proposed, most of them try to improve the efficiency of constraint propagation (e.g. [21, 22]).

## 3.2 Top-k SAT and X-minimal Model Generation Problem

Let $\mathcal{M}$ and $\mathcal{M}'$ be two Boolean interpretations and $X$ a set of propositional variables. Then, $\mathcal{M}$ is said to be smaller than $\mathcal{M}'$ with respect to $X$, written $\mathcal{M} \preceq_X \mathcal{M}'$, if
**Algorithm 1: Top-k**

**Input:** a CNF formula $\Phi$, a preorder relation $\succeq$, an integer $k \ge 1$, and a set $X$ of Boolean variables

**Output:** A set of Top-k models $\mathcal{L}$

1. $\Phi' \leftarrow \Phi$;

2. $\mathcal{L} \leftarrow \emptyset$;

/* Set of all Top-k models */

/* $\mathcal{M}$ is a model of $\Phi'$ */

3. **while** (solve($\Phi'$)) **do**

4. &nbsp;&nbsp;&nbsp;&nbsp;if ($\exists \mathcal{M}' \in \mathcal{L}, \mathcal{M} \approx_X \mathcal{M}' \text{ & } \mathcal{M} \succ \mathcal{M}'$) **then**

5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;replace($\mathcal{M}, \mathcal{M}', \mathcal{L}$);

6. &nbsp;&nbsp;&nbsp;&nbsp;else if ($\forall \mathcal{M}' \in \mathcal{L}, \mathcal{M} \not\approx_X \mathcal{M}' \text{ & } |\text{preferred}(\mathcal{M}, \mathcal{L})| < k$) **then**

7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;S $\leftarrow \min_{\text{top}}(k, \mathcal{L})$;

8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;add($\mathcal{M}, \mathcal{L}$);

9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;remove($k, \mathcal{L}$);

10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;S $\leftarrow \min_{\text{top}}(k, \mathcal{L}) \setminus S$;

11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\Phi' \leftarrow \Phi' \wedge \bigwedge_{\mathcal{M}' \in S} f_{\succeq}(\mathcal{M}')$;

12. &nbsp;&nbsp;&nbsp;&nbsp;else

13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\Phi' \leftarrow \Phi' \wedge f_{\succeq}(\mathcal{M})$

14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\Phi' \leftarrow \Phi' \wedge \overline{\mathcal{M}}$;

15. &nbsp;&nbsp;&nbsp;&nbsp;return $\mathcal{L}$;

$\mathcal{M} \cap X \subseteq \mathcal{M}' \cap X$. We now consider $\preceq_X$ as a preference relation, i.e., $\mathcal{M} \preceq_X \mathcal{M}'$ means that $\mathcal{M}$ is at least as preferred as $\overline{\mathcal{M}}$.

We now show that $\preceq_X$ is a $\delta$-preference relation. We can define $f_{\preceq_X}$ as follows:

$$f_{\preceq_X}(\mathcal{M}) = (\bigvee_{p \in \mathcal{M} \cap X} \bar{p}) \vee \bigwedge_{p' \in X \setminus \mathcal{M}} \bar{p}'$$

Absolutely, $\mathcal{M}'$ is a model of a formula $\Phi \wedge \overline{\mathcal{M}} \wedge f_{\preceq_X}(\mathcal{M})$ if and only if $\mathcal{M}'$ is a model of $\Phi$, $\mathcal{M}' \neq \mathcal{M}$, and either $\mathcal{M}' \cap X = \mathcal{M} \cap X$ or $(\mathcal{M} \cap X) \setminus (\mathcal{M}' \cap X) \neq \emptyset$. The two previous statements mean that $\mathcal{M} \not\preceq_X \mathcal{M}'$. In fact, if $\mathcal{M}'$ satisfies $\bigwedge_{p' \in X \setminus \mathcal{M}} \bar{p}'$, then $\mathcal{M}' \cap X \subseteq \mathcal{M} \cap X$ holds. Otherwise, $\mathcal{M}'$ satisfies $\bigvee_{p \in \mathcal{M} \cap X} \bar{p}$ and that means that $(\mathcal{M} \cap X) \setminus (\mathcal{M}' \cap X) \neq \emptyset$. This latter statement expresses that either $\mathcal{M}' \cap X \subset \mathcal{M} \cap X$ or $\mathcal{M}$ and $\mathcal{M}'$ are incomparable with respect to $\preceq_X$.

Let $\Phi$ be a propositional formula, $X$ a set of propositional variables and $\mathcal{M}$ a model of $\Phi$. Then $\mathcal{M}$ is said to be an $X$-minimal model of $\Phi$ if there is no model strictly smaller than $\mathcal{M}$ with respect to $\preceq_X$. In [23], it was shown that finding an $X$-minimal model is $P^{NP}[O(\log(n))]$-hard, where $n$ is the number of propositional variables.

The set of all $X$-minimal models corresponds to the set of all top-1 models with respect to $\preceq_X$ and $\text{Var}(\Phi)$. Indeed, if $\mathcal{M}$ is a top-1 model, then there is no model $\mathcal{M}'$ such that $\mathcal{M}' \prec_X \mathcal{M}$, and that means that $\mathcal{M}$ is an $X$-minimal model. In this context, let us note that computing the set of Top-k models for $k \ge 1$ can be seen as a generalization of $X$-minimal model generation problem.

## 3.3 An algorithm for Top-k SAT

In this section, we describe our algorithm for computing Top-k models in the case of the $\delta$-preference relations (Algorithm 1). The basic idea is simply to use the formula $f_{\preceq}(\mathcal{M})$ associated to a model $\mathcal{M}$ to obtain models that are at least as preferred as $\mathcal{M}$.
This algorithm takes as input a CNF formula $\Phi$, a preference relation $\succeq$, a strictly positive integer $k$, and a set $X$ of propositional variables allowing to define the equivalence relation $\approx_X$. It has as output a set $\mathcal{L}$ of Top-$k$ models of $\Phi$ satisfying the two properties given in the definition of the Top-$k$ SAT problem.

**Algorithm description** In the while-loop, we use lower bounds for finding optimal models. These lower bounds are obtained by using the fact that the preorder relation considered is a $\delta$-preference relation. In each step, the lower bound is integrated by using the formula:

$$ \bigwedge_{M' \in S} f_{\succeq}(M') $$

- **Lines 4-5.** Let us first mention that the procedure `replace(M, M', L)` replaces $M'$ with $M$ in $L$. We apply this replacement because there exists a model $M'$ in $L$ which is equivalent to $M'$ and $M$ allows to have a better bound.

- **Lines 6-11.** In the case where $M$ is not equivalent to any model in $L$ and the number of models in $L$ preferred to it is strictly less than $k$ ($|\text{preferred}(M, L)| < k$), we add $M$ to $L$ (`add(M, L)`). Note that $S$ contains first the models of $L$ before adding $M$ that have exactly $k-1$ models preferred to them in this set. After adding $M$ to $L$, we remove from $L$ the models that are not Top-$k$, i.e., they have more than $k-1$ models in $L$ that are strictly preferred to them (`remove(k, L)`). Next, we modify the content of $S$. Note that the elements of $S$ before adding $M$ are used as bounds in the previous step. Hence, in order to avoid adding the same bound several times, the new content of $S$ corresponds to the models in $L$ that have exactly $k-1$ models preferred to them in $L$ (`min_top(k, L)`)) deprived of the elements of the previous content of $S$. In line 11, we integrate lower bounds in $\Phi'$ by using the elements of $S$. Indeed, for all model $M$ of a formula $\Phi' \wedge \bigwedge_{M' \in S} f_{\succeq}(M')$, $M' \not\supseteq M$ holds, for any $M' \in S$.

- **Lines 12-13.** In the case where $M$ is not a Top-$k$ model, we integrate its associated lower bound.

- **Line 14.** This instruction enables us to avoid finding the same model in two different steps of the while-loop.

**Proposition 1.** *Algorithm 1 (Top-k) is correct.*

*Proof.* The proof of the partial correctness is based on the definition of the $\delta$-preference relation. Indeed, the function $f_{\succeq}$ allows us to exploit bounds to systematically improve the preference level of the models. As the number of models is bounded, adding the negation of the found model at each iteration leads to an unsatisfiable formula. Consequently the algorithm terminates.

As explained in the algorithm description, we use lower bounds for finding optimal models. These bounds are obtained by using the function $f_{\succeq}$.

# 4 Total Preference Relation

We here provide a second algorithm for computing Top-$k$ models in the case of the total $\delta$-preference relations (Algorithm 2). Let us recall that a $\delta$-preference relation $\succeq$ is total
if, for all models $\mathcal{M}$ and $\mathcal{M}'$, we have $\mathcal{M} \supseteq \mathcal{M}'$ or $\mathcal{M}' \supseteq \mathcal{M}$.

Our algorithm in this case is given in Algorithm 2:

- **Lines 3-8.** In this part, we compute a set $\mathcal{L}$ of $k$ different models of $\Phi$ such that, for all $\mathcal{M}, \mathcal{M}' \in \mathcal{L}$ with $\mathcal{M} \neq \mathcal{M}'$, we have $\mathcal{M} \not\subset_X \mathcal{M}'$. Indeed, if $\mathcal{M}$ is a model of $\Phi$ and $\mathcal{M}'$ is a model of $\Phi \wedge \mathcal{M}_{|X}^1 \wedge \dots \wedge \mathcal{M}_{|X}^n \wedge \mathcal{M}_{|X}$, then it is trivial that $\mathcal{M} \not\subset_X \mathcal{M}'$.

- **Line 9.** Note that the set $\min(\mathcal{L})$ corresponds to the greatest subset of $\mathcal{L}$ satisfying the following property: for all $\mathcal{M} \in \min(\mathcal{L})$, there is no model in $\mathcal{L}$ which is strictly less preferred than $\mathcal{M}$. The assignment in this line allows us to have only models that are at least as preferred as an element of $\min(\mathcal{L})$. Indeed, we do not need to consider the models that are less preferred than the elements of $\min(\mathcal{L})$ because it is clear that they are not Top-$k$ models. Note that all the elements of $\min(\mathcal{L})$ are equivalent with respect to the equivalence relation $\approx$ induced by $\supseteq$, since this preorder relation is total.

- **Line 10-21.** This while-loop is similar to that in Algorithm 1 (Top-$k$). We only remove the condition $|\text{preferred}(\mathcal{M}, \mathcal{L})| < k$ and replace $\min_{\text{top}}(k, \mathcal{L})$ with $\min(\mathcal{L})$. In fact, since the preference relation $\supseteq$ is a total preorder, it is obvious that we have $|\text{preferred}(\mathcal{M}, \mathcal{L})| < k$ because of the lower bounds added previously. Moreover, as $\supseteq$ is total, the set of removed models by $\text{remove}(k, \mathcal{L})$ (Line 16) is either the empty set or $\min(\mathcal{L})$.

**Proposition 2.** *Algorithm 2 (Top-$k^T$) is correct.*

Correctness of this algorithm is obtained from that of the algorithm Top-$k$ and the fact that the considered $\delta$-preference relation is total.

# 5 An application of Top-k SAT in data mining

The problem of mining frequent itemsets is well-known and essential in data mining [1], knowledge discovery and data analysis. Note that several data mining tasks are closely related to the itemset mining problem such as the ones of association rule mining, frequent pattern mining in sequence data, data clustering, etc. Recently, De Raedt et al. in [24, 25] proposed the first constraint programming (CP) based data mining framework for itemset mining. This new framework offers a declarative and flexible representation model. It allows data mining problems to benefit from several generic and efficient CP solving techniques. This first study leads to the first CP approach for itemset mining displaying nice declarative opportunities.

In itemset mining problem, the notion of Top-k frequent itemsets is introduced as an alternative to finding the appropriate value for the minimum support threshold. In this section, we propose a SAT-based encoding for enumerating all closed itemsets. Then we use this encoding in the Top-k SAT problem for computing all Top-k frequent closed itemsets.
In this database, we have $S(\{a, b, c\}, \mathcal{D}) = |\{1, 3\}| = 2$ and $\mathcal{F}(\{a, b\}, \mathcal{D}) = \frac{3}{7}$.

Let $\mathcal{D}$ be a transaction database over $\mathcal{I}$ and $\lambda$ a minimum support threshold. The frequent itemset mining problem consists in computing the following set:

$$ \mathcal{FIM}(\mathcal{D}, \lambda) = \{I \subseteq \mathcal{I} | S(I, \mathcal{D}) \geq \lambda\} $$

**Definition 3 (Closed Itemset).** Let $\mathcal{D}$ be a transaction database (over $\mathcal{I}$) and $I$ an itemset ($I \subseteq \mathcal{I}$) such that $S(I, \mathcal{D}) \geq 1$. $I$ is closed if for all itemset $J$ such that $I \subset J$, $S(J, \mathcal{D}) < S(I, \mathcal{D})$.

One can easily see that all frequent itemsets can be obtained from the closed frequent itemsets by computing their subsets. Since the number of closed frequent itemsets is smaller than or equal to the number of frequent itemsets, enumerating all closed itemsets allows us to reduce the size of the output.

In this work, we mainly consider the problem of mining Top-k frequent closed itemsets of minimum length $min$. In this problem, we consider that the minimum support threshold $\lambda$ is not known.

**Definition 4 (FCIM<sub>min</sub><sup>k</sup>)**. Let $k$ and $min$ be strictly positive integers. The problem of mining Top-k frequent closed itemsets consists in computing all closed itemsets of length at least $min$ such that, for each one, there exist no more than $k-1$ closed itemsets of length at least $min$ with supports greater than its support.

## 5.2 SAT-based encoding for FCIM<sub>min</sub><sup>k</sup>

We now propose a Boolean encoding of $FCIM_{min}^k$. Let $\mathcal{I}$ be a set of items, $\mathcal{D} = \{(0, t_i), \dots, (n-1, t_{n-1})\}$ a transaction database over $\mathcal{I}$, and $k$ and $min$ are strictly positive integers. We associate to each item $a$ appearing in $\mathcal{D}$ a Boolean variable $p_a$. Such Boolean variables encode the candidate itemset $I \subseteq \mathcal{I}$, i.e., $p_a = true$ iff $a \in \mathcal{I}$. Moreover, for all $i \in \{0, \dots, n-1\}$, we associate to the $i$-th transaction a Boolean variable $b_i$.

We first propose a constraint allowing to consider only the itemsets of length at least $min$. It corresponds to a cardinality constraint:

$$ \sum_{a \in \mathcal{I}} p_a \geq min \qquad (1) $$

We now introduce a constraint allowing to capture all the transactions where the candidate itemset does not appear:

$$ \bigwedge_{i=0}^{n-1} (b_i \leftrightarrow \bigvee_{a \in \mathcal{I} \setminus t_i} p_a) \qquad (2) $$
This constraint means that $b_i$ is true if and only if the candidate itemset is not in $t_i$.

By the following constraint, we force the candidate itemset to be closed:

$$ \bigwedge_{a \in \mathcal{I}} \left( \bigwedge_{i=0}^{n-1} \bar{b_i} \to a \in t_i \right) \to p_a \qquad (3) $$

Intuitively, this formula means that if $S(I) = S(I \cup \{a\})$ then $a \in I$ holds. Thus, it allows us to obtain models that correspond to closed itemsets.

In this context, computing the Top-k closed itemsets of length at least min corresponds to computing the Top-k models of (1), (2) and (3) with respect to $\succeq_B$ and $X = \{p_a|a \in \mathcal{I}\}$, where $B = \{b_0, \dots, b_{n-1}\}$ and $\succeq_B$ is defined as follows: $M \succeq_B M'$ if and only if $|M(B)| \le |M'(B)|$. This preorder relation is a $\delta$-preference relation. Indeed, one can define $f_{\succeq_B}$ as follows:

$$ f_{\succeq_B}(M) = \left( \sum_{i=0}^{n-1} b_i \le |M(B)| \right) $$

Naturally, this formula allows us to have models corresponding to closed itemsets with supports greater or equal to the support of the closed itemset obtained from $M$.

## 5.3 Some Variants of $\mathcal{FCIM}_{min}^k$

In this section, our goal is to illustrate the nice declarative aspects of our proposed framework. To this end, we simply consider slight variations of the problem, and show that their encodings can be obtained by simple modifications.

**Variant 1 ($\mathcal{FCIM}_{max}^k$)** In this variant, we consider the problem of mining Top-k closed itemsets of length at most $max$. Our encoding in this case is obtained by adding to (2) and (3) the following constraint:

$$ \sum_{a \in \mathcal{I}} p_a \le max \qquad (4) $$

In this case, we use the $\delta$-preference relation $\succeq_B$ defined previously.

**Variant 2 ($\mathcal{FCIM}_\lambda^k$)** Let us now propose an encoding of the problem of mining Top-k closed itemsets of supports at least $\lambda$ (minimal support threshold). In this context, a Top-k closed itemset is a closed itemset such that, for each one, there exist no more than $k-1$ closed itemsets of length greater than its length. Our encoding in this case is obtained by adding to (2) and (3) the following constraint:

$$ \sum_{i=0}^{n} \bar{b_i} \ge \lambda \qquad (5) $$
The preference relation used in this case is $\succeq_I$ defined as follows: $\mathcal{M} \succeq_I \mathcal{M}'$ if and only if $|\mathcal{M}(I)| \geq |\mathcal{M}'(I)|$. It is a $\delta$-preference relation because $f_{\succeq_I}$ can be defined as follows:

$$f_{\succeq_I}(\mathcal{M}) = \sum_{a \in I} p_a \geq |\mathcal{M}(I)|$$

**Variant 3 (FMIM$^k_\lambda$)** We consider here a variant of the problem of mining maximal frequent itemsets. It consists in enumerating Top-k maximal itemsets of supports at least $\lambda$ and for each one, there exist no more than k - 1 maximal itemsets of length greater than its length. Our encoding of this problem consists of (2) and (5). We use in this case the $\delta$-preference relation $\succeq_I$.

# 6 Experiments

This section evaluates the performance of our Algorithm for Top-k SAT empirically. The primary goal is to assess the declarativity and the effectiveness of our proposed framework. For this purpose, we consider the problem $FCIM_{min}^k$ of computing the Top-k frequent closed itemsets of minimum length $min$ described above. For our experiments, we implemented the Algorithm 1 (Top-k) on the top of the state-of-the-art SAT solver MiniSAT 2.2¹. In our SAT encoding of $FCIM_{min}^k$, we used the sorting networks, one of the state-of-the-art encoding of the cardinality constraint (0/1 linear inequality) to CNF proposed in [26].

We considered a variety of datasets taken from the FIMI repository<fnref n="2" /> and CP4IM<fnref n="3" />. All the experiments were done on Intel Xeon quad-core machines with 32GB of RAM running at 2.66 Ghz. For each instance, we used a timeout of 4 hours of CPU time. The table 1 details the characteristics of the different transaction databases ($D$). The first column mentions the name of the considered instance. In the second and third column, we give the size of $D$ in terms of number of transactions (#trans) and number of items (#items) respectively. The fourth column shows the density (dens) of the transaction database, defined as the percentage of 1's in $D$. The panel of datasets ranges from sparse (e.g. mushroom) to dense ones (e.g. Hepatitis). Finally, in the two last columns, we give the size of the CNF encoding (#vars, #clauses) of $FCIM_{min}^k$. As we can see, our proposed encoding leads to CNF formula of reasonable size. The maximum size is obtained for the instance connect (67 815 variables and 5 877 720 clauses).

In order to analyze the behavior of our Top-k algorithm on $FCIM_{min}^k$, we conducted two kind of experiments. In the first one, we set the minimum length $min$ of the itemsets to 1, while the value of $k$ is varied from 1 to 10000. In the second experiment, we fix the parameter $k$ to 10, and we vary the minimal length $min$ from 1 to the maximum size of the transactions.

Results for a representative set of datasets are shown in Figure 1 (log scale). The other instances present similar behavior. As expected, the CPU time needed for computing the Top-k models increase with $k$. For the connect dataset, our algorithm fails to

<footnote n="1">¹ MiniSAT: http://minisat.se/</footnote>

<footnote n="2">² FIMI: http://fimi.ua.ac.be/data/</footnote>

<footnote n="3">³ CP4IM: http://dtai.cs.kuleuven.be/CP4IM/datasets/</footnote>
<table><caption>**Table 1.** Characteristics of the datasets</caption><thead><tr><th>instance</th><th>#trans</th><th>#items</th><th>dens(%)</th><th>#vars</th><th>#clauses</th></tr></thead><tbody><tr><td>zoo-1</td><td>101</td><td>36</td><td>44</td><td>173</td><td>2196</td></tr><tr><td>Hepatitis</td><td>137</td><td>68</td><td>50</td><td>273</td><td>4934</td></tr><tr><td>Lymph</td><td>148</td><td>68</td><td>40</td><td>284</td><td>6355</td></tr><tr><td>audiology</td><td>216</td><td>148</td><td>45</td><td>508</td><td>17575</td></tr><tr><td>Heart-cleveland</td><td>296</td><td>95</td><td>47</td><td>486</td><td>15289</td></tr><tr><td>Primary-tumor</td><td>336</td><td>31</td><td>48</td><td>398</td><td>5777</td></tr><tr><td>Vote</td><td>435</td><td>48</td><td>33</td><td>531</td><td>14454</td></tr><tr><td>Soybean</td><td>650</td><td>50</td><td>32</td><td>730</td><td>22153</td></tr><tr><td>Australian-credit</td><td>653</td><td>125</td><td>41</td><td>901</td><td>48573</td></tr><tr><td>Anneal</td><td>812</td><td>93</td><td>45</td><td>990</td><td>39157</td></tr><tr><td>Tic-tac-toe</td><td>958</td><td>27</td><td>33</td><td>1012</td><td>18259</td></tr><tr><td>german-credit</td><td>1000</td><td>112</td><td>34</td><td>1220</td><td>73223</td></tr><tr><td>Kr-vs-kp</td><td>3196</td><td>73</td><td>49</td><td>3342</td><td>121597</td></tr><tr><td>Hypothyroid</td><td>3247</td><td>88</td><td>49</td><td>3419</td><td>143043</td></tr><tr><td>chess</td><td>3196</td><td>75</td><td>49</td><td>3346</td><td>124797</td></tr><tr><td>splice-1</td><td>3190</td><td>287</td><td>21</td><td>3764</td><td>727897</td></tr><tr><td>mushroom</td><td>8124</td><td>119</td><td>18</td><td>8348</td><td>747635</td></tr><tr><td>connect</td><td>67558</td><td>129</td><td>33</td><td>67815</td><td>5877720</td></tr></tbody></table>

compute the Top-k models for higher value of k > 1000 in the time limit of 4 hours. This figure clearly shows that finding the Top-k models (the most interesting ones) can be computed efficiently for small values of k. For example, on all datasets the top-10 models are computed in less than 100 seconds of CPU time. When a given instance contains a huge number of frequent closed itemsets, the Top-k problem offers an alternative to the user to control the size of the output and to get the most preferred models. In Figure 2, we show the results obtained on the hardest instance from Table 1. On splice-1, the algorithm fails to solve the problem under the time limit for k > 20.

<figure><img src="image_25.png" /><figcaption>**Fig. 1.** FCIM<sub>1</sub><sup>k</sup> results for different values of k</figcaption></figure>
<figure><img src="image_26.png" /><figcaption>Fig. 2. Hardest FCIM<sub>1</sub><sup>k</sup> instance</figcaption></figure>

In our second experiment, our goal is to show the behavior of our algorithm when varying the minimum length. In Figure 3, we give the results obtained on the three representative datasets (mushroom, connect and chess) when *k* is fixed to 10 and *min* is varied from 1 to the maximum size of the transactions. The problem is easy at both the under-constrained (small values of *min* - many Top-*k* models) and the over-constrained (high values of *min* - small number of Top-*k* models) regions. For the connect dataset, the algorithm fails to solve the problem for *min* > 15 under the time limit. For all the other datasets, the different curves present a pick of difficulty for medium values of the minimal length of the itemsets.

<figure><img src="image_27.png" /><figcaption>Fig. 3. FCIM<sub>min</sub><sup>10</sup> results for different values of *min*</figcaption></figure>
# 7 Acknowledgments

This work was supported by the French Research Agency (ANR) under the project DAG "Declarative Approaches for Enumerating Interesting Patterns" - Défis program 2009.

# 8 Conclusion and Perspectives

In this paper, we introduce a new problem, called Top-$k$ SAT, defined as the problem of enumerating the Top-$k$ models of a propositional formula. A Top-$k$ model is a model having no more than $k-1$ models preferred to it with respect to the considered preference relation. We also show that Top-$k$ SAT generalizes the two well-known problems: the partial Max-SAT problem and the problem of computing minimal models. A general algorithm for this problem is proposed and evaluated on the problem of enumerating top-$k$ frequent closed itemsets of length at least $min$.

While our new problem of computing the Top-$k$ preferred models in Boolean satisfiability is flexible and declarative, there are a number of questions that deserve further research efforts. One direction is the study of (preferred/Top-$k$) model enumeration algorithm so as to achieve a further speedup of the runtime. This fundamental problem has not received a lot of attention in the SAT community, except some interesting works on enumerating minimal/preferred models.

# References

1. Agrawal, R., Imielinski, T., Swami, A.N.: Mining association rules between sets of items in large databases. In: ACM SIGMOD International Conference on Management of Data, Baltimore, ACM Press (1993) 207–216

2. Tiwari, A., Gupta, R., Agrawal, D.: A survey on frequent pattern mining: Current status and challenging issues. Inform. Technol. J 9 (2010) 1278–1293

3. Fu, A.W.C., w. Kwong, R.W., Tang, J.: Mining *n*-most interesting itemsets. In: Proceedings of the 12th International Symposium on Mthodologies for Intelligent Systems (ISMIS 2000). Lecture Notes in Computer Science, Springer (2000) 59–67

4. Han, J., Wang, J., Lu, Y., Tzvetkov, P.: Mining top-k frequent closed patterns without minimum support. In: Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM 2002), IEEE Computer Society (2002) 211–218

5. Ke, Y., Cheng, J., Yu, J.X.: Top-k correlative graph mining. In: Proceedings of the SIAM International Conference on Data Mining (SDM 2009). (2009) 1038–1049

6. Valari, E., Kontaki, M., Papadopoulos, A.N.: Discovery of top-k dense subgraphs in dynamic graph collections. In: Proceedings of the 24th International Conference on Scientific and Statistical Database Management (SSDBM 2012). (2012) 213–230

7. Lam, H.T., Calders, T.: Mining top-k frequent items in a data stream with flexible sliding windows. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2010). (2010) 283–292

8. Lam, H.T., Calders, T., Pham, N.: Online discovery of top-k similar motifs in time series data. In: Proceedings of the Eleventh SIAM International Conference on Data Mining, SDM 2011 (SDM 2011). (2011) 1004–1015
9. Shoham, Y.: Reasoning about change: time and causation from the standpoint of artificial intelligence. MIT Press, Cambridge, MA, USA (1988)

10. Meseguer, P., Rossi, F., Schiex, T.: 9. In: Soft Constraints. Elsevier (2006)

11. Boutilier, C., Brafman, R.I., Domshlak, C., Poole, D.L., Hoos, H.H.: CP-nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements. Journal of Artificial Intelligence Research (JAIR) 21 (2004) 135–191

12. Walsh, T.: Representing and reasoning with preferences. AI Magazine 28(4) (2007) 59–70

13. Brafman, R.I., Domshlak, C.: Preference Handling - An Introductory Tutorial. AI Magazine 30(1) (2009) 58–86

14. Domshlak, C., Hüllermeier, E., Kaci, S., Prade, H.: Preferences in AI: An overview. Artificial Intelligence 175(7-8) (2011) 1037–1052

15. Rosa, E.D., Giunchiglia, E., Maratea, M.: Solving satisfiability problems with preferences. Constraints 15(4) (2010) 485–515

16. Castell, T., Cayrol, C., Cayrol, M., Berre, D.L.: Using the davis and putnam procedure for an efficient computation of preferred models. In: ECAI. (1996) 350–354

17. Wang, J., Han, J., Lu, Y., Tzvetkov, P.: TFP: An efficient algorithm for mining top-k frequent closed itemsets. IEEE Transactions on Knowledge Data Engineering 17(5) (2005) 652–664

18. Tseitin, G.: On the complexity of derivations in the propositional calculus. In: Structures in Constructives Mathematics and Mathematical Logic, Part II. (1968) 115–125

19. Fu, Z., Malik, S.: On Solving the Partial MAX-SAT Problem. In: Proceedings of the Ninth International Conference on Theory and Applications of Satisfiability Testing (SAT’06). (2006) 252–265

20. Warners, J.P.: A linear-time transformation of linear inequalities into conjunctive normal form. Information Processing Letters (1996)

21. Bailleux, O., Boufkhad, Y.: Efficient CNF Encoding of Boolean Cardinality Constraints. In: 9th International Conference on Principles and Practice of Constraint Programming - CP 2003. (2003) 108–122

22. Sinz, C.: Towards an optimal cnf encoding of boolean cardinality constraints. In: 11th International Conference on Principles and Practice of Constraint Programming - CP 2005. (2005) 827–831

23. Cadoli, M.: On the complexity of model finding for nonmonotonic propositional logics. In: 4th Italian conference on theoretical computer science. (1992) 125–139

24. Raedt, L.D., Guns, T., Nijssen, S.: Constraint programming for itemset mining. In: ACM SIGKDD. (2008) 204–212

25. Guns, T., Nijssen, S., De Raedt, L.: Itemset mining: A constraint programming perspective. Artificial Intelligence 175(12-13) (August 2011) 1951–1983

26. Eén, N., Sörensson, N.: Translating pseudo-boolean constraints into SAT. JSAT 2(1-4) (2006) 1–26
# Inconsistency Measurement Thanks to MUS Decomposition

Said Jabbour
CRIL-CNRS, Univ. Artois
Lens, France
jabbour@cril.fr

Yue Ma
Institute of TCS
TU Dresden, Germany
mayue@tu-dresden.de

Badran Raddaoui
CRIL-CNRS, Univ. Artois
Lens, France
raddaoui@cril.fr

## ABSTRACT

Bearing contradictory knowledge is often unavoidable among multi-agents. Measuring inconsistency degrees of knowledge bases of different agents facilitates the understanding of an agent to her environment. Several semantics or syntax-based approaches have been proposed to quantify inconsistencies. In this paper, we propose a new inconsistency measuring framework based on both minimal unsatisfiable sets and maximal consistent sets. Firstly, we define a graph representation of knowledge bases, based on which we furthermore explore the logical property of the *Additivity* condition. Then, we show how the structure of the proposed graph representation can be used to discriminate, in a fine-grained way, the responsibility of each formula or a set of formulae for the inconsistency of a knowledge base. Finally, we extend our framework to provide an inconsistency measure for a whole knowledge base. All the proposed measures are shown satisfying the desired properties.

## Categories and Subject Descriptors

H.3 [Agent Reasoning]: Knowledge representation

## General Terms

Theory

## Keywords

Measuring Inconsistency, Classical Logic

## 1. INTRODUCTION

Measuring inconsistency has proven useful and attractive in diverse scenarios including software specifications [21], e-commerce protocols [5], belief merging [28], news reports [13], integrity constraints [8], requirements engineering [21], databases [22, 11], ontologies [33], semantic web [33], and network intrusion detection [23].

Indeed, we cannot expect large-sized knowledge bases free of inconsistency in real applications, such as multi-agents communicating with each other to build a common knowledge base or to perform certain actions in a complex environment. For illustration purpose, we consider an example

**Appears in:** Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AA-MAS 2014), Lomuscio, Scerri, Bazzan, Huhns (eds.), May, 5-9, 2014, Paris, France.

Copyright © 2014, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.

simplified from the Multi-agent System ARTOR (ARTificial ORganizations [30]) which simulates the partnership of organizations – each organization owns agents responsible for purchasing and selling products. We consider a scenario where each product has *N* grades of price and *M* grades of quantity (higher grade, larger value, e.g. $10 for the price grade 1 and $20 for the grade 2). Selling agents wish to sell products at a price as expensive as possible and with a quantity as large as possible, but buying agents wish as cheap as possible and have quantity upper bounds. By $p_i(1 \le i \le N)$ and $q_j(1 \le j \le M)$, we denote a trade of price grade *i* and of quantity grade *j*, respectively. Consider the following two agents:

Buying agent : Selling agent :

$$p_{i+1} \rightarrow p_i \quad | \quad p_i \rightarrow p_{i+1} \quad (1)$$

$$q_{j+1} \rightarrow q_j \quad | \quad q_j \rightarrow p_{j+1} \quad (2)$$

$$p_1 \wedge p_2 \wedge p_3 \wedge \neg p_4 \quad | \quad \neg p_5 \wedge p_6 \wedge \cdots \wedge p_N \quad (3)$$

$$q_1 \wedge q_2 \wedge \neg q_3 \quad | \quad \neg q_6 \wedge q_7 \wedge \cdots \wedge q_M \quad (4)$$

Item 1 (resp. 2) says that if the buying agent accepts the price (resp. quantity) at grade *i* + 1 (resp. *j* + 1), then he accepts lower prices (resp. less quantities); Whilst the selling agent accepts the price (resp. quantity) at grade *i* (resp. *j*), then he accepts higher prices (resp. larger quantities). Together with Item 3 (resp. 4), we can read that the buying agent agrees to pay at most at price grade 3 and with the maximal quantity grade 2, but the selling agent accepts minimal price grade 6 and quantity grade 7. It is easy to see that there are contradictions between these two agents (e.g. {$p_3, \neg q_7$} for the buying agent but {$\neg p_3, q_7$} for the selling agent). To make the trade successful, agents should be equipped with the ability of reasoning with inconsistency. Moreover, if an agent knows the different inconsistency degrees between him and others, a better trade plan could be arranged when multiple sellers and buyers are available.

Analyzing conflicting information has gained a considerable attention and become an important issue in computer science recently [2]. Indeed, measuring inconsistency is helpful to compare different knowledge bases and to evaluate their quality [7]. Consider again the above example, giving the opportunity for a buyer agent to choose among different selling agents, naturally he may try to choose the one that is less inconsistent.

To understand the nature of inconsistency and to quantify it in turn, a number of logic-based inconsistency measures have been studied, including the maximal *η*-consistency [18], measures based on variables or via multi-valued models [7,
12, 27, 13, 9, 20, 31, 19], n-consistency and n-probability [6], minimal inconsistent subsets based inconsistency measures [15, 24, 25, 32], the Shapley inconsistency value [14, 16], and the inconsistency measurement based on minimal proofs [17]. Although it is hardly possible to have a complete comparison of the proposed measures. One way to categorize the existing measures can be based on the dependence of syntax or semantics: Semantics based ones aim to compute the proportion of the language affected by inconsistency. The inconsistency values belonging to this class are often based on some paraconsistent semantics and syntax independent. Whilst, syntax based ones are concerned with the minimal number of formulae that cause inconsistencies. Viewing Minimal Unsatisfiable Subsets (MUSes) as the cornerstones of inconsistency, it is natural to derive inconsistency measures from MUSes of a knowledge base. Another possible classification of different measures originates in the measuring objective: formula oriented or knowledge base oriented. For example, the inconsistency measures in [14, 16] are to measure the contribution of a formula to the inconsistency of a whole knowledge base that it belongs to, while the rest measures mentioned above are to measure the inconsistency degree of a whole base. Some basic properties [16], such as *Consistency*, *Monotony*, *Free Formula Independence*, and *MinInc*, are also proposed to qualify inconsistency measures.

In this paper, we propose a new approach for measuring inconsistency, both formula oriented and knowledge base oriented. It is inspired, on the one hand, by the observation that existing measures fail to distinguish certain knowledge bases which should have different inconsistency degrees. On the other hand, a specific property is explored, namely *Additivity* that is rarely discussed in the literature due to its modeling difficulty [16]. Our study is based on a novel analysis of connections among MUSes, which is shown useful and general to quantify more finely the inconsistency responsibility of a formula and the inconsistency degree of a whole base. Note that this is unlike the oriented links between MUSes explored in [1] which says that the resolution of one MUS allows for the resolution of the other. By looking inside MUSes and taking into account the correlations between them, the proposed analysis of MUSes structure lead to several interesting measures different from the existing ones. Moreover, we propose an *enhanced additivity* property and show that our measures satisfy such a property as well as several basic properties.

The paper is organized as follows: Section 2 reviews approaches to measuring inconsistencies based on minimal inconsistent subsets and maximal consistent subsets. In Section 3, we revisit the additivity property and propose the graph representation of a knowledge base by which we introduce the notion of MUS-decomposition. This notion is then used in Section 4 to evaluate the degree of inconsistency of each formula in the knowledge base. In Section 5, we generalize our framework to quantify inconsistency of a whole base. Section 6 concludes the paper and discusses some perspectives.

## 2. PRELIMINARIES

Through this paper, we consider the propositional language $\mathcal{L}$ built from a finite set of propositional symbols $\mathcal{P}$ under connectives $\{\neg, \wedge, \vee, \rightarrow\}$. We will use $a, b, c, \dots$ to denote propositional variables, and Greek letters $\alpha, \beta, \gamma, \dots$ for

formulae. The symbol $\perp$ denotes contradiction. For a set $S$, we denote $|S|$ its cardinality.

A knowledge base $K$ consists of a finite set of propositional formulae. $K$ is inconsistent if there is a formula $\alpha$ such that $K \vdash \alpha$, and $K \vdash \neg\alpha$, where $\vdash$ is the deduction in classical propositional logic. If $K$ is inconsistent, then one can define the notion of *Minimal Unsatisfiable Subset* (MUS) as an unsatisfiable set of formulae $\mathcal{M}$ in $K$ such that any of its subsets is satisfiable. Formally,

**DEFINITION 1 (MUS).** Let $K$ be a knowledge base and $\mathcal{M} \subseteq K$. $\mathcal{M}$ is a minimal unsatisfiable (inconsistent) subset of $K$ iff $\mathcal{M} \vdash \perp$ and $\forall M' \in \mathcal{M}, M' \not\vdash \perp$.

Clearly, an inconsistent knowledge base $K$ can have multiple minimal inconsistent subsets. The set of minimal inconsistent subsets of $K$ is denoted as $MUSes(K) = \{\mathcal{M} \subseteq K \mid \mathcal{M}$ is a $\mathcal{M}$US\}$. When a $\mathcal{M}$US is singleton, the single formula in it is called a *self-contradictory formula*. A formula $\alpha$ not involved in any $\mathcal{M}$US of $K$ is called a *free formula*, meaning that $\alpha$ does not have any relationship with the inconsistency of $K$. Formally, $SelfC(K) = \{\alpha \in K \mid \{\alpha\} \vdash \perp\}$, and $free(K) = \{\alpha \mid \text{for all } \mathcal{M} \in MUSes(K), \alpha \notin \mathcal{M}\}$.

At the same time, we can define the *Maximal Satisfiable Subset* (MSS), and Hitting set as follows:

**DEFINITION 2 (MSS).** Let $K$ be a knowledge base and $\mathcal{M}$ a subset of $K$. $\mathcal{M}$ is a maximal satisfiable (consistent) subset of $K$ iff $\mathcal{M} \not\vdash \perp$ and $\forall \alpha \in K \setminus \mathcal{M}, \mathcal{M} \cup \{\alpha\} \vdash \perp$.

We denote by $MSSes(K)$ the set of all maximal consistent subsets of $K$.

**DEFINITION 3 (HITTING SET).** Given a universe $U$ of elements and a collection $S$ of subsets of $U$, $H \subseteq U$ is a hitting set of $S$ if $\forall E \in S, H \cap E \neq \emptyset$. We say that $H$ is a minimal hitting set of $S$ if $H$ is a hitting set of $S$ and each $H' \subset H$ is not a hitting set of $S$.

We denote by $LB_{HS}(K)$ the smallest size of a hitting set of $K$, i.e., $LB_{HS}(K) = \min\{|H| \mid H \text{ is a hitting set of } K\}$.

### 2.1 Inconsistency Measures

In this section, we review some inconsistency measures important and related to the rest of this paper.

There have been several contributions for measuring inconsistency in knowledge bases defined through minimal inconsistent subsets theories. In [16], Hunter and Konieczny introduce a scoring function allowing to measure the degree of inconsistency of a subset of a knowledge base. In details, for a subset $K' \subseteq K$, the scoring function is defined as the diminution of the number of minimal inconsistent subsets while $K'$ is removed, i.e., $|MUSes(K')| - |MUSes(K \setminus K')|$. By extending the scoring function, the authors introduce an inconsistency measure of a whole base, defined as the number of minimal inconsistent subsets of $K$. Formally, $I_{MI}(K) = |MUSes(K)|$. In the same paper, a family of “MinInc inconsistency values” $MIV$ based on minimal inconsistent subsets is also presented:

* $MIV_D(K, \alpha)$ is a simple measure that values 1 if $\alpha$ belongs to a minimal inconsistent subset and 0 otherwise.

* $MIV_\#$ is defined by the scoring function: $MIV_\#(K, \alpha) = |\{\mathcal{M} \in MUSes(K) \mid \alpha \in \mathcal{M}\}|$.
• $MIV_C$ takes into account the size of each minimal inconsistent subset in addition to the number of $MUSes$ of $K$, formally $MIV_C(K, \alpha) = \sum_{\alpha \in M | M \in MUSes(K)} \frac{1}{|M|}$.

Combining both minimal inconsistent subsets and maximal consistent subsets, Mu et al. present in [26] an approach to quantify the degree of inconsistency of a knowledge base. Another inconsistency value, called $I_M$ measure, that deals with that combination, has been introduced in [10]. The $I_M$ measure counts for a given knowledge base, the number of its $MSSes$ and its Self-contradictory formulae (subtraction of 1 is required to make $I_M(K) = 0$ when $K$ is consistent):

$$I_M(K) = |MSSes(K)| + |SelfC(K)| - 1.$$

Recently, in [17] a new framework based on the notion of minimal proof is proposed to measure inconsistency degrees. This framework uses conflicting minimal proofs to characterize the inconsistency of any subset of formulae in a base.

### 3. MUS PARTITIONING IN KNOWLEDGE BASES

There are a set of well accepted basic properties that inconsistency measures should satisfy (see Definition 4), while leaving one property *Additivity* debatable [15]. In this section, we propose an enhancement of the additivity property to make it more intuitive and give a way to modify the $I_M$ measure introduced above to satisfy the enhance additivity.

**Definition 4** ([16]). Let $K$ and $K'$ be two knowledge bases, $\alpha$ and $\beta$ two formulae. A set of properties of an inconsistency measure $I$ is defined as follows:

(1) Consistency: $I(K) = 0$ iff $K$ is consistent,

(2) Monotony: $I(K) \le I(K \cup K')$,

(3) Free Formula Independence: if $\alpha$ is a free formula in $K \cup \{\alpha\}$, then $I(K \cup \{\alpha\}) = I(K)$,

(4) MinInc: If $M \in MUSes(K)$, then $I(M) = 1$.

The monotony property shows that the inconsistency value of a knowledge base has to be non-decreasing while adding new formulae. The free formula independence property states that the set of formulae not involved in any minimal inconsistent subset should have no contribution to inconsistency. And MinInc means that a single MUS as a whole has inconsistency value 1. Besides, another property called *Additivity*<fnref n="1" /> has been proposed in [16].

**Definition 5** (*Additivity*). Let $K_1, \dots, K_n$ be knowledge bases and $I$ an inconsistency measure. $I$ is additive if it satisfies the following condition: If $MUSes(K_1 \cup \dots \cup K_n) = MUSes(K_1) \oplus \dots \oplus MUSes(K_n)^2$, then $I(K_1 \cup \dots \cup K_n) = I(K_1) + \dots + I(K_n)$.

The additivity was proposed to ensure that the amount of conflict of a knowledge base $K$ can be obtained by summing up the degrees of its sub-bases $K_i$ under the condition that $\{MUSes(K_i)\}$ is a partition of $MUSes(K)$. However, Luce

and Raiffa have pointed out that the interaction of sub-bases (sub-games in [29]) is not taken into account by Additivity, which is one of the criticisms about this condition [29, 16]. Although the partitionability of $MUSes$ is used to describe a sort of interaction in Definition 5, we argue that it is not enough. Consider the following example:

**Example 1.** Let $K_1 = \{a, \neg a\}$, $K_2 = \{\neg a, a \wedge b\}$, and $K_3 = \{c, \neg c\}$, each of which has only one single MUS. Consider two bases $K = K_1 \cup K_2$, and $K' = K_1 \cup K_3$. Clearly, $MUSes(K) = MUSes(K_1) \oplus MUSes(K_2)$, and $MUSes(K') = MUSes(K_1) \oplus MUSes(K_3)$. For any measure $I$, if $I$ satisfies *Additivity* by Definition 5, we should have $I(K) = I(K_1)+I(K_2)$, and $I(K') = I(K_1)+I(K_3)$. If $I$ furthermore satisfies MinInc (see Definition 4), single MUS leads to the same inconsistency value. Then $I(K) = I(K')$, which is counterintuitive because the components of $MUSes(K')$ are less interactive, thus more spreading, than that of $MUSes(K)$. And in turn $K'$ should, intuitively, contain more inconsistencies than $K$.

To enhance the consideration of interaction among sub-bases, we propose the following Enhanced Additivity:

**Definition 6** (*Enhanced Additivity*). Let $K_1, \dots, K_n$ be knowledge bases and $I$ an inconsistency measure. If $MUSes(K_1 \cup \dots \cup K_n) = MUSes(K_1) \oplus \dots \oplus MUSes(K_n)$ and $\{\alpha \in M | M \in MUSes(K_i)\} \cap \{\beta \in M | M \in MUSes(K_j)\} = \emptyset$ for all $1 \le i \ne j \le n$, $I(K_1 \cup \dots \cup K_n) = I(K_1) + \dots + I(K_n)$. $I$ is then called an independent-additive measure.

Note that the enhanced additivity requires an extra pre-condition, which is to encode a stronger independence among sub-bases to perform additivity. The enhanced additivity can exclude the counterintuitive conclusion as given in Example 1: suppose $I$ satisfies the enhanced additivity, then we have $I(K') = I(K_1)+I(K_3)$, but not necessarily $I(K') = I(K_1)+I(K_2)$. Hence $I(K)$ is not necessarily equal to $I(K')$.

Alternatively, the enhanced-additivity, given below, can be defined through multi-set partition instead of set partition as used in Definition 6.

**Definition 7.** $I$ is called *multi-set additive if it satisfies*: $I(K_1 \cup \dots \cup K_n) = \sum_{i=1}^k I(K_i)$ when $MUSes(\cup_{i=1}^n K_i) = \bigcup_{i=1}^n MUSes(K_i)$, where $\bigcup$ is the multi-set union over sets.

For Example 1, whilst $MUSes(K) = \{\{a, \neg a\}, \{\neg a, a \wedge b\}\}$, we have $MUSes(K_1) \bigcup MUSes(K_2) = \{\{a, \neg a\}, \{\neg a, a \wedge b\}, \{a, \neg a\}\}$. This leads to the conclusion that it is unnecessarily to have $I(K) = I(K_1) + I(K_2)$, the same as using Definition 6. In fact, it is easy to see that $I$ is multi-set additive if and only if it is enhanced additive.

Clearly, additivity implies enhanced additivity. While we can see that the $MIV$ measure family satisfies the additivity and the enhanced additivity, it is not the case for the $I_M$ measure as shown below.

**Proposition 1.** $I_M$ is neither additive nor enhanced additive.

**Proof.** Consider the counter-example: $K_1 = \{a, \neg a\}$, $K_2 = \{b, \neg b\}$, and $K = K_1 \cup K_2$. It is easy to check that $K$ and $K_i$ ($i = 1, 2$) satisfy the conditions of additivity and enhanced additivity. But we have $I_M(K_1 \cup K_2) = 3$ while $I_M(K_1) = I_M(K_2) = 1$. □

<footnote n="1">¹The Additivity condition is named Decomposability in [15].</footnote>

<footnote n="2">²We denote a partition $\{A, B\}$ of a set $C$ by $C = A \oplus B$, i.e., $C = A \cup B$ and $A \cap B = \emptyset$.</footnote>
Indeed, the following theorem states that under certain constraints, MSSes is multiplicative instead of additive.

**PROPOSITION 2.** Let $K_1$ and $K_2$ be two knowledge bases such that $\{\alpha \in MUSes(K_i)\} \cap \{\beta \in MUSes(K_j)\} = \emptyset$. Then, $|MSSes(K_1 \cup K_2)| = |MSSes(K_1)| \times |MSSes(K_2)|$.

As the enhanced additivity gives a more intuitive characterization of interaction among sub-sets to be added up, in the following, we are interested in restoring the enhanced additivity of the $I_M$ measure. To simplify terminology, in the rest of the paper, we call the enhanced additivity simply Additivity by default unless other claims are made.

To reach this goal, let us first define three fundamental concepts: MUS-graph, MUS-decomposition, and elementary MSS.

**DEFINITION 8 (MUS-GRAPH).** Given an inconsistent knowledge base K, the MUS-graph of K, denoted $G_{MUS}(K)$, is an undirected graph where:

(1) $MUSes(K)$ is the set of vertices, and

(2) $\forall \mathcal{M}, \mathcal{M}' \in MUSes(K), \{\mathcal{M}, \mathcal{M}'\}$ is an edge iff $\mathcal{M} \cap \mathcal{M}' \neq \emptyset$.

A MUS-graph of a knowledge base K gives us a structural representation of its interconnected minimal unsatisfiable subsets.

Moreover, $G_{MUS}(K)$ leads to a partition of a knowledge base K, named MUS-decomposition, as defined below.

**DEFINITION 9 (MUS-DECOMPOSITION).** Let K be a knowledge base, and $\{C_1, \dots, C_p\}$ with $C_i \subseteq K$ for $1 \le i \le p$. $\{C_1, \dots, C_p\}$ is the MUS-decomposition of K iff $\{C_1, \dots, C_p\}$ is the set of the connected components of $G_{MUS}(K)$.

A MUS-decomposition $\{C_1, \dots, C_p\}$ of a knowledge base K represents a partition of the minimal unsatisfiable subsets of K into connected components.

By the fact that $MUSes(K) \neq \emptyset$ and the uniqueness of connected components of a graph, we can easily see:

**PROPOSITION 3.** MUS-decomposition exists and is unique for an inconsistency knowledge base.

Definition 9 allows us to associate to a given knowledge base K a set of sub-bases $K_1, \dots, K_p$ such that the elements of each sub-base $K_i$ are the formulae of the connected component $C_i$.

In the following, we present an alternative to the inconsistency measure $I_M$ so as to make it additive. To this end, we introduce the concept of elementary MSS by using the MUS-decomposition.

**DEFINITION 10.** Let K be a knowledge base, $K' \subseteq K$, and $\{C_1, \dots, C_p\}$ the MUS-decomposition of K. $K'$ is an elementary MSS of K iff there exists a connected component $C_i$ of K such that $K' \in MSSes(K_i)$. We denote by EMSS(K) the set of all elementary MSS of K, i.e., EMSS(K) = $\bigcup_{i=1}^p MSSes(K_i)$.

That is, an elementary maximal consistent subset should be locally restricted by a connected component of $MUSes(K)$.

**EXAMPLE 2.**$^3$ Let $K = \{a \wedge d, \neg a, \neg b, b \vee \neg c, \neg c \wedge d, \neg c \vee e, c, \neg e, e \wedge d\}$. The MUS-decomposition of K contains two subsets, $C_1 = \{M_1\}$, and $C_2 = \{M_2, M_3, M_4, M_5\}$ where $M_1 = \{\neg a, a \wedge d\}$, $M_2 = \{c, \neg b, b \vee \neg c\}$, $M_3 = \{c, \neg c \wedge d\}$, $M_4 = \{\neg c \vee e, c, \neg e\}$, and $M_5 = \{\neg e, e \wedge d\}$ (see figure 1). Then, EMSS(K) = $\{\{a \wedge d\}, \{\neg a\}, \{\neg b, b \vee \neg c, \neg c \wedge d, \neg c \vee e, e \wedge d\}, \{\neg b, b \vee \neg c, \neg c \wedge d, \neg c \vee e, \neg e\}, \{b \vee \neg c, \neg c \vee e, c, e \wedge d\}, \{\neg b, \neg c \vee e, c, e \wedge d\}, \{b \vee \neg c, c, \neg e\}, \{\neg b, c, \neg e\}\}$.

Now, we use the notion of EMSS to define an alternative of the $I_M$ measure, named $I'_M$:

$$I'_M(K) = \begin{cases} |EMSS(K)| + |SelfC(K)| & \text{if } K \vdash \perp; \\ 0 & \text{otherwise.} \end{cases}$$

**PROPOSITION 4.** the $I'_M$ measure is additive.

**PROOF.** The conclusion follows immediately from the fact that both $|EMSS(K)|$ and $|SelfC(K)|$ are additive. $\square$

That is, by taking into account the connections between minimal inconsistent subsets, MUS-decomposition gives us a way to define an inconsistency measure which still satisfies the additivity.

# 4. MUS-DECOMPOSITION BASED INCONSISTENCY MEASURE

In this section, we use the MUS-decomposition of a knowledge base, defined in the previous section, to estimate the responsibility of each formula to the inconsistency of its base.

Given a MUS-graph of a knowledge base K, a distance, as defined next, is an assignment of a real number to each MUS pair of K.

**DEFINITION 11.** Let K be a knowledge base. We denote $d_{MUS}(\mathcal{M}, \mathcal{M}')$ the shortest path between $\mathcal{M}$ and $\mathcal{M}'$ in the MUS-graph $G_{MUS}(K)$.

As easily seen, $d_{MUS}(\mathcal{M}, \mathcal{M}')$ is a distance, that is, it satisfies: (1) $d_{MUS}(\mathcal{M}, \mathcal{M}') \ge 0$; (2) $d_{MUS}(\mathcal{M}, \mathcal{M}') = d_{MUS}(\mathcal{M}', \mathcal{M})$; and (3) $d_{MUS}(\mathcal{M}_1, \mathcal{M}_2) \le d_{MUS}(\mathcal{M}_1, \mathcal{M}_3) + d_{MUS}(\mathcal{M}_3, \mathcal{M}_2)$. So, we call it the distance between $\mathcal{M}$ and $\mathcal{M}'$.

Next, we will extend Definition 11 to compute the distance between a formula and a MUS.

**DEFINITION 12.** Let K be a knowledge base, $\alpha \in K \setminus free(K)$, and $\mathcal{M} \in MUSes(K)$. The distance between $\alpha$ and $\mathcal{M}$ is defined as $d_{MUS}(\alpha, \mathcal{M}) = \min\{d_{MUS}(\mathcal{M}, \mathcal{M}') | \alpha \in \mathcal{M}'\}$.

In fact, the distance between a given formula $\alpha \in K$ and a MUS $\mathcal{M}$ corresponds to the shortest path from $\alpha$ to $\mathcal{M}$ along a sequence of intersecting MUSes. Note that if $\alpha$ and $\mathcal{M}$ do not belong to the same connected component of $G_{MUS}(K)$, this means that $\mathcal{M}$ is not reachable from $\alpha$ and in this case, the distance is assigned an infinite value, i.e., $d_{MUS}(\alpha, \mathcal{M}) = +\infty$.

**EXAMPLE 3.** (Example 2 Contd.) Let $\alpha = \neg b$, we have

$$\frac{d_{MUS}(\alpha, M_2) = 0 \qquad d_{MUS}(\alpha, M_3) = 1 \\ d_{MUS}(\alpha, M_4) = 1 \qquad d_{MUS}(\alpha, M_5) = 2}{\alpha \in M}$$

<footnote>$^3$For a better display of the new notions introduced in this paper, we use a different example from the illustrative one given in Section 1.</footnote>
We note that the distance $d_{MUS}$ allows for an ordering over the minimal inconsistent subsets of K according to their distances from $\alpha$.

In the following, we quantify the inconsistency value of $\alpha$ in the light of the distances from $\alpha$ to reachable MUSes of K. Indeed, for each formula belonging to some MUSes, there exists at least one such a finite distance. To compare different formulae by their inconsistency values, only finite distances are meaningful. For free formulae, all the distances will be $+\infty$. But by *Free Formula Independence principle*, they should not be contributors to inconsistency anyway. Let us note $d_{MUS}^{max}(\alpha) = \max\{d_{MUS}(\alpha, \mathcal{M}) | \mathcal{M} \in \text{MUSes}(K), d_{MUS}(\alpha, \mathcal{M}) \neq +\infty\}$. Note that the maximum distance is not more than the cardinality of the connected component that $\alpha$ belongs to, that is, $d_{MUS}^{max}(\alpha) < |\mathcal{C}|$.

**DEFINITION 13.** Let K be a knowledge base, and $\alpha \in K$. Write $S_{MUS}(\alpha, k) = \{\mathcal{M} \in \text{MUSes}(K) | d_{MUS}(\alpha, \mathcal{M}) = k\}$. $SQ_{MUS}(\alpha)$ is defined as follows: $SQ_{MUS}(\alpha) = \{S_{MUS}(\alpha, 0), S_{MUS}(\alpha, 1), \dots, S_{MUS}(\alpha, d_{MUS}^{max}(\alpha))\}$.

Note that $S_{MUS}(\alpha, k)$ represents the set of MUSes with a distance $k$ from $\alpha$, and $SQ_{MUS}(\alpha)$ gives the sequence of MUSes distributed in terms of the distance $d_{MUS}$.

**EXAMPLE 4.** (Example 2 Contd.) For $\alpha = \neg b$, we have $S_{MUS}(\alpha, 0) = \{M_2\}$, $S_{MUS}(\alpha, 1) = \{M_3, M_4\}$, $S_{MUS}(\alpha, 2) = \{M_5\}$. Then, $SQ_{MUS}(\alpha) = \{\{M_2\}, \{M_3, M_4\}, \{M_5\}\}$. Figure 1 depicts a graphical representation of the connected components of K. Also, Figure 2 represents the distribution of MUSes according to their distances to $\alpha$. We remark that the MUSes are arranged into different levels.

<figure><img src="image_28.png" /><figcaption>Figure 1: MUS-graph of K</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>Figure 2: Distribution of MUSes according to $\alpha$</figcaption></figure>

It is easy to check that the $MIV_{\#}$ measure is just a characterization of the set $S_{MUS}$ when applying uniquely the minimum distance from the formulae. More formally,

**PROPOSITION 5.** Let K be a knowledge base, and $\alpha \in K$. Then, $MIV_{\#}(K, \alpha) = |S_{MUS}(\alpha, 0)|$.

Proposition 5 shows that the $MIV_{\#}$ value considers only the nearest neighbors of $\alpha$. However, this measure is not sufficiently discriminating for our purposes, since it takes into account only the first level of MUSes. Indeed, let us consider the formulae $d \wedge e$, and $\neg c \vee e$ of Example 2. According to $MIV_{\#}$ or $MIV_C$ measure, these two formulae have the same inconsistency value. However, according to Figure 1 $d \wedge e$ and $\neg c \vee e$ do not have the same structural properties. Indeed, the MUS containing $\neg c \vee e$ is more connected than the one of $d \wedge e$. Hence, one has to go beyond the nearest neighbors to obtain a finer-grained measure.

A first inconsistency measure can be defined as follows:

**DEFINITION 14.** Let K be a knowledge base, and $\alpha \in K$. The inconsistency value of $\alpha$ is defined as:

$$DIM_C(\alpha, K) = \frac{|S_{MUS}(\alpha, 0)|}{d_{MUS}^{max}(\alpha) + 1}$$

Unlike $MIV_{\#}$, the $DIM_C$ value takes into account the structure of connected components by considering the nearest and the farthest MUSes. More precisely, the $DIM_C$ measure aims to assign a higher value to a formula that has numerous nearest neighbors with the remaining MUSes concentrated around it. Put differently, while two formulae have the same number of neighbors of distance 0, the distance from the farthest MUSes allows us to find out the most inconsistent one. Note that if $\alpha$ is a self-contradictory formula, the $DIM_C$ measure takes value one, i.e., $DIM_C(\alpha, K) = 1$.

Let us now illustrate the behavior of the $DIM_C$ measure in the next example.

**EXAMPLE 5.** (Example 2 Contd.) It is not hard to see:

$$ 
\begin{align*}
DIM_C(a \wedge d, K) &= 1 & DIM_C(\neg a, K) &= 1 \\
DIM_C(\neg b, K) &= \frac{1}{3} & DIM_C(\neg c \wedge d, K) &= \frac{1}{3} \\
DIM_C(\neg e, K) &= 1 & DIM_C(b \vee \neg c, K) &= \frac{1}{3} \\
DIM_C(d \wedge e, K) &= \frac{1}{3} & DIM_C(c, K) &= \frac{3}{2} \\
DIM_C(\neg c \vee e, K) &= \frac{1}{2} & &
\end{align*}
$$

Notice that now we can make a distinction between $d \wedge e$, and $\neg c \vee e$, since $DIM_C(d \wedge e, K) < DIM_C(\neg c \vee e, K)$.

However, the problem remains between the formulae $d \wedge e$, and $\neg b$. In order to make the measure more accurate, we propose to extend our framework by not only considering the farthest MUSes, but the whole structure of the connected components, which leads to a more useful inconsistency measure defined as follows:

**DEFINITION 15.** Let K be a knowledge base, and $\alpha \in K$. The inconsistency value of $\alpha$ is defined as:

$$DIM_H(\alpha, K) = \sum_{\mathcal{M} \in \text{MUSes}(K) \atop d_{\text{MUS}(\alpha, \mathcal{M})} \neq +\infty} \frac{1}{d_{\text{MUS}}(\alpha, \mathcal{M}) + 1}$$

We can see more clearly by the following example that $DIM_H$ gives a more precise view of the conflict brought by each formula.

**EXAMPLE 6.** (Example 2 Contd.) We have:

$$ 
\begin{align*}
DIM_H(a \wedge d, K) &= 1 & DIM_H(\neg a, K) &= 1 \\
DIM_H(\neg b, K) &= \frac{7}{3} & DIM_H(\neg c \wedge d, K) &= \frac{7}{3} \\
DIM_H(\neg e, K) &= 3 & DIM_H(b \vee \neg c, K) &= \frac{7}{3} \\
DIM_H(d \wedge e, K) &= \frac{13}{6} & DIM_H(c, K) &= \frac{7}{2} \\
DIM_H(\neg c \vee e, K) &= \frac{7}{3} & &
\end{align*}
$$
Using the DIM<sub>H</sub> measure, the formula $d \wedge e$ has now an inconsistency value $\frac{13}{6}$ less than that of $\neg b$ which is $\frac{7}{3}$.

The DIM<sub>H</sub> measure could be refined by using the following notion of a weighting function that assigns a weight to each MUS in the MUS-graph. The idea is that a weight represents the significance of a MUS with respect to their distance from a given formula, thus leading to a better assignment of inconsistency responsibility to formulae. These weights can take into consideration other criteria like the degree of each MUS in the MUS-graph. A general definition is stated as follows.

**DEFINITION 16.** Let K be a knowledge base, and $w(M) \in \mathbb{R}$ a given weight function. The inconsistency value of $\alpha$ is defined as:

$$DIM_W(\alpha, K) = \sum_{\substack{M \in MUSes(K) \\ d_{MUS}(\alpha, M) \neq \infty}} \frac{w(M)}{d_{MUS}(\alpha, M) + 1}$$

The following result shows that the DIM<sub>W</sub> measure can be expressed by using the sequence $SQ_{MUS}(\alpha)$. The idea is that $w(M)$ only depends on the distance between $M$, and $\alpha$.

**PROPOSITION 6.** Let K be a knowledge base, and $\alpha \in K$. Then, the following equation holds:

$$DIM_W(\alpha, K) = \sum_{S_{MUS} \in SQ_{MUS}} w(i) \times \frac{|S_{MUS}(\alpha, i)|}{(i + 1)}$$

Note that $w(i)$ represents the weight associated to each MUS at distance $i$ from $\alpha$.

## 4.1 Measuring Inconsistency of Sub-bases

Instances of a DIM (such as those given in Definitions 14, 15, and 16) can be obviously extended to a set of formulae. For this purpose it will be convenient to define the distance between a subset $K' \subseteq K$, and a MUS $M \in MUSes(K)$.

**DEFINITION 17.** Let K be a knowledge base, $K'$ a subset of K, and $M \in MUSes(K)$. The distance between $K'$, and $M$ is defined as:

$$d_{MUS}(K', M) = \min\{d_{MUS}(\alpha, M) \mid \alpha \in K'\}$$

Clearly, the set of MUSes can be partitioned into different subsets according to their distances to the subset $K'$. Here, we denote by $d_{MUS}^{max}(K')$ the maximum distance of MUSes from $K'$.

Now, the inconsistency measure of $K'$ through DIM<sub>C</sub> value is defined as follows:

**DEFINITION 18.** Let K be a knowledge base, and $K' \subseteq K$. The inconsistency degree of $K'$ is defined as:

$$DIM_C(K', K) = \frac{|S_{MUS}(K', 0)|}{d_{MUS}^{max}(K') + 1}$$

Interestingly, we note that while considering more than one formula, different connected components should be taken into account. In the light of the property of additivity, DIM<sub>C</sub>(K', K) can be rewritten as stated in Proposition 7.

**PROPOSITION 7.** Let K be a knowledge base, $K' \subseteq K$, and $\{C_1, \dots, C_p\}$ the MUS-decomposition of K. Then,

$$DIM_C(K', K) = \sum_{i=1}^{i=p} DIM_C(K' \cap K_i, K)$$

**EXAMPLE 7.** Let us consider again the knowledge base $K = \{a \wedge d, \neg a, \neg b, b \vee \neg c, \neg c \wedge d, \neg c \vee e, c, \neg e, e \wedge d\}$. Then, $DIM_C(\{a \wedge d, c\}, K) = 1 + \frac{3}{2} = \frac{5}{2}$.

Similarly, DIM<sub>C</sub>, DIM<sub>H</sub>, and DIM<sub>W</sub> inconsistency values can be naturally extended to a set of formulae. In particular, if we consider the case $K' = K$, then $DIM_C(K) = \frac{|S_{MUS}(K, 0)|}{d_{MUS}^{max}(K') + 1} = |MUSes(K)|$, which corresponds to the $I_{MI}$ measure. The same result is obtained when using DIM<sub>H</sub>, i.e., $DIM_H(K) = |MUSes(K)|$.

## 4.2 Monotonicity

As seen earlier, the DIM<sub>C</sub> value combines the distances to the nearest MUSes, and the inverse of that to the farthest in order to quantify the participation of each formula in the inconsistencies. Note that adding new formulae to a knowledge base may grow the distance to the farthest MUS, and consequently the DIM<sub>C</sub> value decreases. This means that DIM<sub>C</sub> is not monotonic. For illustration, consider the knowledge base $K = \{a, \neg a \wedge b, \neg b \wedge c, \neg c \wedge d, \neg d \wedge e\}$. Then, we have $DIM_C(a) = \frac{1}{4}$. Now if we add to K the formula $\neg e$, then the value of $a$ in $K \cup \{\neg e\}$ becomes $\frac{1}{5}$.

In contrast, DIM<sub>H</sub> counts the inverse of all distances from a formula to each MUS. Moreover, adding new formulae cannot decrease the number of MUSes, and cannot increase the distance of existing MUSes from the formula, thus the inverse of the distances will be non-decreasing. Consequently, the DIM<sub>H</sub> measure is monotonic.

# 5. MEASURING INCONSISTENCIES OF A WHOLE BASE

This section is devoted to the definition of an inconsistency measurement for a whole knowledge base.

To address this question, let us firstly give a general characterization of our measure with respect to the additivity property. Then, we discuss different measures obtained by different instantiations of the general case.

**DEFINITION 19.** Let K be a knowledge base, and CC = $\{C_1, \dots, C_n\}$ the connected components of K. The inconsistency measure of K, denoted $I_{CC}(K)$, is defined as $I_{CC}(K) = \sum_{i=1}^{n} \delta(C_i)$ where $\delta$ is a function valuing in $\mathbb{R}$.

The general definition given above allows for a range of possible measures. Next we first instantiate some $I_{CC}$ measures by varying the $\delta$ function. The simplest one is obtained when $\delta(C_i) = 1$. In this case, we get a measure that assigns to K the number of its connected components, i.e., $I_{CC}(K) = |CC|$. Note that this measure is not monotonic. Indeed, adding new formulae to the knowledge base can decrease the number of connected components of the base. For instance, let us consider the knowledge base $K = \{a, \neg a, b, \neg b\}$ that contains two connected components $C_1 = \{a, \neg a\}$, and $C_2 = \{b, \neg b\}$; now adding the formula $a \vee b$ to K leads to a new knowledge base containing a unique connected component $C = \{a, \neg a, b, \neg b, a \vee b\}$. Note that this simple measure considers each connected component as an inseparable entity.
Moreover, when we consider $\delta(C_i) = |C_i|$, the $I_{CC}$ measure leads to an existing inconsistency measure. More precisely, as $|C_i|$ corresponds exactly to the number of MUSes involved in the connected component $C_i$, it is obvious to see that $I_{CC}(K)$ is equal to $I_{MI}$ measure, i.e., $I_{CC}(K) = |MUSes(K)|$. This second value is of little interest, since it states exactly the fact that the inconsistency value only takes into account the number of the minimal inconsistent subsets of a base.

In the following, we propose to deeply explore the properties of additivity, and monotonicity to define a new interesting inconsistency measure.

**DEFINITION 20.** Let $K$ be a knowledge base, and $K_1, \dots, K_n$ subsets of $K$. The set $\{K_1, \dots, K_n\}$ is called a conditional independent MUS partition of $K$ if the following conditions are satisfied:

$$ (1) \quad K_i \vdash \perp, \text{ for } 1 \le i \le n, $$

$$ (2) \quad MUSes(K_1 \cup \dots \cup K_n) = \bigoplus_{1 \le i \le n} MUSes(K_i), $$

$$ (3) \quad K_i \cap K_j = \emptyset, \forall i \neq j. $$

According to Definition 20, $K$ can be written as $K = K_1 \cup \dots \cup K_n \cup R$ where $R$ is a subset of $K$, and $\{K_1, \dots, K_n\}$ is a conditional independent MUS partition of $K$. That is, when removing the set of formulae $R$ from $K$ the remaining base can be partitioned into sub-bases $K_1, \dots, K_n$ satisfying conditions (1), (2), and (3) (Definition 20).

In general, for a given knowledge base $K$, there exist different subsets $R \subseteq K$ such that Definition 20 holds. Moreover, if $K = K_1 \cup \dots \cup K_n \cup R$, then there exists $\{M_1, \dots, M_n\} \subseteq MUSes(K)$ being a conditional independent MUS partition of $K$. In other words, $K = M_1 \cup \dots \cup M_n \cup R'$ where $M_i \cap M_j = \emptyset, \forall 1 \le i \neq j \le n$, and $MUSes(M_1 \cup \dots \cup M_n) = \bigoplus_{1 \le i \le n} M_i$. Indeed, it is sufficient to pick a MUS $M_i$ from each $K_i$ since $K_i \vdash \perp$, and consider $R' = R \cup \{K_1 \setminus M_1\} \cup \dots \cup \{K_n \setminus M_n\}$.

Let us now characterize our inconsistency measure $I$ in the light of both additivity, and monotony properties. Using Definition 20, $I(K) = I(K_1 \cup \dots \cup K_n \cup R)$. Using monotony property, we have $I(K) \ge I(K_1 \cup \dots \cup K_n)$. Finally by additivity, we conclude that $I(K) \ge I(K_1) + \dots + I(K_n)$.

Now, let us denote by $\mu_{max}(K)$ the maximal cardinality of sets $\{K_1, \dots, K_n\}$ satisfying the conditions (1), (2), and (3) of Definition 20. That is, $\mu_{max}(K)$ corresponds to the number of maximal connected components that can be obtained while removing some formulae from $K$, i.e., the maximum value taken by $n$. By considering the maximal conditional independent partition value $\mu_{max}$, one can deduce that if the measure $I$ is additive then, $I(K) \ge I(K_1) + \dots + I(K_{\mu_{max}(K)})$. Now, by using this bound one can define a new inconsistency measure as stated in Definition 21.

**DEFINITION 21.** Let $K$ be a knowledge base. We define the inconsistency measure of $K$ as:

$$ I_{CC}(K) = \mu_{max}(K) $$

So now we can show that:

**PROPOSITION 8.** The inconsistency measure $I_{CC}$ is additive, and monotonic.

**PROOF.** Let $K$, and $K'$ be two knowledge bases such that $K = K_1 \cup \dots \cup K_{\mu_{max}(K)} \cup R$. Then, $K \cup K' = K_1 \cup \dots \cup K_{\mu_{max}(K)} \cup R \cup K'$. Hence, $K \cup K' = K_1 \cup \dots \cup K'_{\mu_{max}(K)} \cup R'$. Thus, $\mu_{max}(K \cup K') \ge \mu_{max}(K)$ which proves that $I_{CC}$ is monotonic. Suppose now that $(K \setminus free(K)) \cap (K' \setminus free(K')) = \emptyset$, and $MUSes(K) \cap MUSes(K') = \emptyset$, it is easy to conclude that $\mu_{max}(K \cup K') = \mu_{max}(K) + \mu_{max}(K')$. As consequently, $I_{CC}$ is additive. $\square$

**EXAMPLE 8.** Let us consider $K = \{a, \neg a, a \lor b, \neg b, c, \neg c \land d, \neg d \land e \land f, \neg e, \neg f\}$. The figure 3 depicts its connected components. $K$ contains two connected components $C_1$ and $C_2$ such that $C_1 = \{a, \neg a, a \lor b, \neg b, b\}$, and $C_2 = \{c, \neg c \land d, \neg d \land e \land f, \neg e, \neg f\}$. The conditional independent MUS partition of $C_1$ of maximum size is equal to 2, and can be obtained from $C_1$ by removing $a \lor b$. For $C_2$, for all removed subsets of $C_2$, the number of resulting connected components can not exceed 1. Then, we have $I_{CC}(K) = I_{CC}(C_1) + I_{CC}(C_2) = 3$.

<figure><img src="image_30.png" /><figcaption>**Figure 3: Connected components of the knowledge base K**</figcaption></figure>

Let us note that among measures that are additive, monotonic, and MinInc, $I_{CC}$ is the smallest one, as shown below.

**PROPOSITION 9.** For any $I$ that is additive, monotonic, and MinInc, $I_{CC}(K) \le I(K)$.

**PROOF.** Indeed, an additive, and monotonic measure must attribute to a knowledge base a value greater than $I(K_1) + \dots + I(K_{\mu_{max}(K)})$. When a measure satisfies MinInc, and monotonicity, $I(K_i) \ge 1$. Hence, $I(K) \ge \mu_{max}(K)$. $\square$

Moreover, Proposition 10 shows the relationship between the maximal conditional independent MUS partition, and the smallest minimal hitting set.

**PROPOSITION 10.** Let $K$ be a knowledge base. Then,

$$ I_{CC}(K) \le LB_{HS}(K) $$

**PROOF.** As $K$ can be partitioned into $\mu_{max}(K)$ independent components by removing some formulae, then a minimal hitting set of $K$ must contain at least one formula from each independent component of the maximal partition. Hence, $\mu_{max}(K) \le LB_{HS}(K)$. $\square$

**EXAMPLE 9.** Let us consider again Example 8, and its second connected component $C_2$. We have $LB_{HS}(K) = 2$ while the conditional independent MUS partition of $K$ can not exceed 1.

# 6. CONCLUSION

We proposed in this paper a new framework for defining inconsistency values that allow to associate each formula with its degree of responsibility for the inconsistency of a
whole knowledge base. This approach is based on the corre-
lation between minimal inconsistent subsets which is shown
a useful way to quantify the amount of inconsistencies in
a finer way. We showed that such a framework can be ex-
tended to quantify the inconsistency of a whole knowledge
base. We also proposed an enhanced additivity property to
better capture its intuition according to the debat existing
in the literature.

In the future, we plan to investigate deeply the architec-
ture of the connected components. For instance, we plan
to use logical argumentation theory [4] to deepen the analy-
sis of the graph representation of a knowledge base [3]. We
are also going to investigate results coming from graph the-
ory in order to offer a finer grained evaluation of the incon-
sistencies. The theoretical complexity of our inconsistency
measures, and practical algorithms are under investigation.

7. ACKNOWLEDGMENTS

The first author benefits from the support of both CNRS
and OSEO within the ISI project Pajero.

8. REFERENCES

[1] S. Benferhat and L. Garcia. A local handling of inconsistent knowledge and default bases. In *Applications of Uncertainty Formalisms*, pages 325–353, 1998.

[2] L. E. Bertossi, A. Hunter, and T. Schaub. Introduction to inconsistency tolerance. In *Inconsistency Tolerance*, pages 1–14, 2005.

[3] P. Besnard, É. Grégoire, C. Piette, and B. Raddaoui. Mus-based generation of arguments and counter-arguments. In *IRI*, pages 239–244, 2010.

[4] P. Besnard and A. Hunter. A logic-based theory of deductive arguments. *Artif. Intell.*, 128(1-2):203–235, 2001.

[5] Q. Chen, C. Zhang, and S. Zhang. A verification model for electronic transaction protocols. In *APWeb*, pages 824–833, 2004.

[6] D. Doder, M. Raskovic, Z. Markovic, and Z. Ognjanovic. Measures of inconsistency and defaults. In *Int. J. Approx. Reasoning*, 51(7):832–845, 2010.

[7] J. Grant. Classifications for inconsistent theories. *Notre Dame Journal of Formal Logic*, 19(3):435–444, 1978.

[8] J. Grant and A. Hunter. Measuring inconsistency in knowledgebases. *J. Intell. Inf. Syst.*, 27(2):159–184, 2006.

[9] J. Grant and A. Hunter. Analysing inconsistent first-order knowledgebases. *Artif. Intell.*, 172(8-9):1064–1093, 2008.

[10] J. Grant and A. Hunter. Measuring consistency gain and information loss in stepwise inconsistency resolution. In *ECSQARU*, pages 362–373, 2011.

[11] J. Grant and A. Hunter. Distance-based measures of inconsistency. In *ECSQARU*, pages 230–241, 2013.

[12] A. Hunter. Measuring inconsistency in knowledge via quasi-classical models. In *AAAI/IAAI*, pages 68–73, 2002.

[13] A. Hunter. How to act on inconsistent news: Ignore, resolve, or reject. *Data Knowl. Eng.*, 57(3):221–239, 2006.

[14] A. Hunter and S. Konieczny. Shapley inconsistency values. In *KR*, pages 249–259, 2006.

[15] A. Hunter and S. Konieczny. Measuring inconsistency through minimal inconsistent sets. In *KR*, pages 358–366, 2008.

[16] A. Hunter and S. Konieczny. On the measure of conflicts: Shapley inconsistency values. *Artif. Intell.*, 174(14):1007–1026, 2010.

[17] S. Jabbour and B. Raddaoui. Measuring inconsistency through minimal proofs. In *ECSQARU*, pages 290–301, 2013.

[18] K. Knight. Measuring inconsistency. *J. Philosophical Logic*, 31(1):77–98, 2002.

[19] Y. Ma, G. Qi, and P. Hitzler. Computing inconsistency measure based on paraconsistent semantics. *J. Log. Comput.*, 21(6):1257–1281, 2011.

[20] Y. Ma, G. Qi, G. Xiao, P. Hitzler, and Z. Lin. Computational complexity and anytime algorithm for inconsistency measurement. *Int. J. Software and Informatics*, 4(1):3–21, 2010.

[21] A. B. B. Martinez, J. J. P. Arias, and A. F. V. and. On measuring levels of inconsistency in multi-perspective requirements specifications. In *PRISE’04*, pages 21–30, 2004.

[22] M. V. Martinez, A. Pugliese, G. I. Simari, V. S. Subrahmanian, and H. Prade. How dirty is your relational database? an axiomatic approach. In *ECSQARU*, pages 103–114, 2007.

[23] K. McAreavey, W. Liu, P. Miller, and K. Mu. Measuring inconsistency in a network intrusion detection rule set based on snort. *Int. J. Semantic Computing*, 5(3), 2011.

[24] K. Mu, W. Liu, and Z. Jin. A general framework for measuring inconsistency through minimal inconsistent sets. *Knowl. Inf. Syst.*, 27(1):85–114, 2011.

[25] K. Mu, W. Liu, and Z. Jin. Measuring the blame of each formula for inconsistent prioritized knowledge bases. *J. Log. Comput.*, 22(3):481–516, 2012.

[26] K. Mu, W. Liu, Z. Jin, and D. A. Bell. A syntax-based approach to measuring the degree of inconsistency for belief bases. *Int. J. Approx. Reasoning*, 52(7):978–999, 2011.

[27] C. A. Oller. Measuring coherence using lp-models. *J. Applied Logic*, 2(4):451–455, 2004.

[28] G. Qi, W. Liu, and D. A. Bell. Measuring conflict and agreement between two prioritized belief bases. In *IJCAI*, pages 552–557, 2005.

[29] H. R. Robert Duncan Luce. *Games and Decision*. Wiley, 1957.

[30] M. A. H. Shmeil and E. Oliveira. Detecting the opportunities of learning from the interactions in a society of organizations. In *SBIA*, pages 242–252, 1995.

[31] G. Xiao, Z. Lin, Y. Ma, and G. Qi. Computing inconsistency measurements under multi-valued semantics by partial max-sat solvers. In *KR*, 2010.

[32] G. Xiao and Y. Ma. Inconsistency measurement based on variables in minimal unsatisfiable subsets. In *ECAI*, pages 864–869, 2012.

[33] L. Zhou, H. Huang, G. Qi, Y. Ma, Z. Huang, and Y. Qu. Measuring inconsistency in dl-lite ontologies. In *Web Intelligence*, pages 349–356, 2009.
# Summarizing Large Graphs by Means of Pseudo-Boolean Constraints

Said Jabbour¹ and Nizar Mhadhbi¹ and Abdesattar Mhadhbi² and Badran Radaoui³ and Lakhdar Sais¹

¹ CRIL - CNRS UMR 8188, University of Artois, France
{jabbour,mhadahbi,sais}@cril.fr

² Faculty of Sciences of Gafsa, Tunisia
mhadhbiabdesattar@gmail.com

³ LIAS - ENSMA, University of Poitiers, France
badran.raddaoui@ensma.fr

**Abstract**—Many real-world problems are effectively modeled as graphs. However, the resulting graph-based representation are usually of very large size leading to an increasing computational complexity in processing such graphs. Starting from the fact that any arbitrary graph contains hidden structures corresponding to particular classes of graphs, our goal in this paper is to discover such specific structures and to exploit them to summarize the main components of the graph using a more compact representation. More precisely, we first show that some special graph classes such as cliques and bi-cliques can be represented efficiently as *Pseudo-Boolean constraints*. Then, we propose three new interesting graph classes, called *nested*, *sequence* and *clique-nested bi-partite* graphs. All these classes are bi-partite graphs satisfying some specific properties. We also show that such graph classes can be expressed in a more succinct manner using Pseudo-Boolean constraints. We then present a more general approach for a partial or a complete summarization of an arbitrary graph as a disjunction of Pseudo-Boolean constraints. This new representation can be seen as an original way to represent the edges of the graph, as they correspond to particular solutions of the Pseudo-Boolean constraints. Experimental results on real-world datasets, show that our approach allows us to efficiently summarize large graphs in a compact way and enable further analysis.

**Keywords**-Graph Mining, Graph Summarization, Pseudo Boolean Constraints.

## I. INTRODUCTION

Graphs present a general tool for modeling structural relationships between data objects. They have been widely used in several application domains, including interactions in bioinformatics, link analysis in social networks, XML documents, etc. Unfortunately, correlation mining in graph databases is expensive due to the complexity of graph data. In fact, in most of these applications, graphs are very large, with thousands or even millions of nodes and edges. Subsequently, it is difficult to understand the information/structure encoded in these graphs by simple visualization.

Taking as an example protein-protein interaction (PPI) networks [1]. These representations are depicted by graphs where nodes and edges represent proteins and interactions,

respectively. Such dependencies provide relevant insights into the underlying mechanisms of biological processes within a cell. Indeed, interacting proteins are likely to have related cellular roles. As pointed out in [2], identifying the sets of proteins that are involved in the same biological processes is an important computational task. A common approach to this issue, is to partition the interaction graph into modules (subsets of proteins) based on the connectivity of the nodes. Proceeding from the related processes common proteins tend to be situated near one another within the network [3]. In fact, identifying such modules can help to understand the structure of the cell.

Revealing the topological structure of the graph is at the basis of many approaches in social networks, such as community detection, and clustering (e.g. [4]). Generally, real networks involve high concentrations of edges within special groups of vertices, and low concentrations between these groups. As an example, in the graph of the World Wide Web, high concentrations may correspond to groups of pages dealing with the same or related topics. Due to their degree of connectedness, these communities, clusters or modules might sometimes match some graph classes such as (almost) cliques, bicliques, bipartite graphs, etc. In this paper, we aim at discovering such specific structures, which enables efficient summarization. Moreover, we exploit the discovered structures to summarize the main components of the graph using a more compact representation while maintaining the possibility to uncover the original graph. Indeed, effective graph summarization approaches are crucial since they can assist in uncovering useful insights about the patterns hidden in the underlying data. Therefore, graph summarization and compression have been a subject of intense research activities (see the related work section).

To the best of our knowledge, it is the first time where a graph is represented using Pseudo-Boolean constraints (from now on “PB-constraints”) (PB constraints for short), i.e., 0-1 linear inequalities. The main originality is that each PB constraint allows us to implicitly represent large parts
of the graph. We particularly show that any graph can be represented as a disjunction of PB constraints. Since a PB constraint can be encoded as a Boolean formula in conjunctive normal form, our results suggest that any graph can be represented as a Boolean formula. Consequently, we believe that our new compact representation opens a new research avenue for reasoning on large graphs and their underlying structures. Without loss of generality, in this paper we focus on undirected graphs and on the discovery of its most connected components corresponding to special graphs classes.

We first show that some special graph classes such as cliques and bicliques can be represented efficiently as PB constraints. Then, we propose three new interesting graph classes, called *nested*, *sequence* and *nested-sequence* bipartite graphs. All these classes are bipartite graphs satisfying some specific properties. We also show that such graph classes can be represented using PB constraints. We then present a more general approach for a partial or a complete summarization of an arbitrary graph as a disjunction of PB constraints. This new representation can be seen as an original way to represent the edges of the graph, as they correspond to particular solutions of the PB constraints.

The roadmap of this paper is organized as follows: We start by introducing some necessary definitions about PB constraints and graphs. Then, in Section III we present our proposed approach that uses PB constraints to identify and encode particular subgraphs. In addition to existing types of graphs that can be encoded, we propose a number of additional structures that can be represented efficiently as PB constraints. Section IV reports our experimental results on different real-world datasets. In Section V, we briefly overview related work. Finally, we conclude in Section VI.

## II. PRELIMINARIES

Let us introduce some necessary definitions about PB constraints and graphs. First, we assume a countable set $V$ of propositional variables. The set of propositional formulas $\mathcal{F}_V$ is defined inductively from $V$ under the logical connectives ($\lor$, $\land$, $\neg$, $\rightarrow$), and the Boolean constants $\top$ (true) and $\bot$ (false). We will use $\phi, \psi, \dots$ to denote propositional formulas. The set of propositional variables occurring in a formula $\phi$ is denoted $V_\phi$. A propositional formula is said to be in CNF, *conjunctive normal formula*, if it is a set (interpreted as a conjunction) of *clauses*, where a clause is a set (interpreted as a disjunction) of *literals*. A literal is either $x$, or its negation $\neg x$, for a propositional variable $x$. Using linear Tseitin encoding [5], any formula $\phi$ can be translated to a CNF formula equivalent w.r.t. satisfiability.

An interpretation $\mathcal{B}$ of a formula $\phi$ is a function that assigns a truth value $\mathcal{B}(x) \in \{0, 1\}$ (0 corresponds to false and 1 to true) to some of the variables $x \in V_\phi$. It can be inductively extended to a set of formulas using the usual semantic. $\mathcal{B}$ is said to be *complete* if it assigns a value to

every $x \in V_\phi$, and *partial* otherwise. An interpretation is alternatively represented by a set of literals. A model (or implicant) of a formula $\phi$ is an interpretation $\mathcal{B}$ that satisfies the formula, denoted $\mathcal{B} \models \phi$. An implicant $\mathcal{B}$ of $\phi$ is called a *prime implicant*, iff for all literals $l \in \mathcal{B}$, $\mathcal{B} \setminus \{l\} \not\models \phi$. A satisfiability problem consists in deciding whether a given CNF formula $\Phi$ admits a model or not.

Let us now introduce PB constraints (or 0-1 linear inequalities). A PB constraint $C_{pb}$ is defined as follows:

$$ \sum_{i=1}^{n} a_i x_i \ op \ b \qquad (1) $$

where $a_i$ and $b$ are integer coefficients, $x_i$ ($1 \le i \le n$) are propositional variables, and the relation operator op belongs to $\{=, \le, <, >, \ge\}$. it can be noticed that one can assume that op is $\le$ and the $a_i$ and $b$ are positive since all the other cases can be easily reduced to this normalized form [6]. Additionally, when it is more convenient we will consider the following two-sided PB constraint $C_{pb}$ by introducing a lower and upper bounds:

$$ b_{min} \le \sum_{i=1}^{n} a_i x_i \le b_{max} \qquad (2) $$

An important special case of PB constraints is the one of *cardinality constraints*, in which all coefficients $a_i$ ($1 \le i \le n$) are equal to 1. Obviously, any clause $x_1 \lor \dots \lor x_n$ can be written as a cardinality constraint as follows:

$$ \sum_{i=1}^{n} x_i \ge 1 \qquad (3) $$

Let us note that a negative literal $\neg x$ can also be written as $(1-x)$.

Next, we extend the notion of interpretation to apply to PB constraints. Let $C_{pb}$ be a PB constraint as defined in equation (1) and $\mathcal{B}$ an interpretation of the variables of $C_{pb}$, we define the interpretation $\mathcal{B}(C_{pb})$ as follows:

$$ \sum_{i=1}^{n} a_i \mathcal{B}(x_i) \ op \ b \qquad (4) $$

We say that $\mathcal{B}$ is a model of $C_{pb}$ iff $\mathcal{B}(C_{pb}) = 1$. In the similar way we can extend $\mathcal{B}$ to two-sided PB constraint. For a PB constraint $C_{pb}$, $\mathcal{M}(C_{pb})$ denotes the set of models of $C_{pb}$. We note $\mathcal{M}_\mathcal{B}^t(C_{pb}) = \{x \in V_{C_{pb}} | \mathcal{B}(x) = 1\}$ the set of variables of $V_{C_{pb}}$ that are true in the model $\mathcal{B}$. A model $\mathcal{B} \in \mathcal{M}(C_{pb})$ is called a $k$-model of the PB constraint $C_{pb}$ iff $|\mathcal{M}_\mathcal{B}^t(C_{pb})| = k$. The set of $k$-models of $C_{pb}$ is denoted $\mathcal{k-models}(C_{pb})$. Note that the concept of prime implicant can be extended to PB constraint in a straightforward way.

PB constraints are at the heart of integer linear programming and propositional satisfiability. They are essential for modeling a wide variety of applications. Indeed, several polynomial encodings of this kind of constraints into a CNF
formula have been introduced in the literature. The first
linear encoding of general 0-1 linear inequalities to CNF has
been proposed by Warners [7]. Recently, efficient encodings
of the cardinality constraint to CNF have been proposed (see
[8], [9]). Similarly, various CNF polynomial encodings have
been studied for general PB constraints of the form (2) (see
[9]).

Now, we present some terminology about graphs that will
be used throughout the paper. A graph is a pair of sets
$G = (X, E)$. $X$ is the set of vertices where the number
of vertices $|X| = n$ is the order of the graph. The set
$E \subseteq X \times X$ contains the edges of the graph with $|E| = m$.
In an undirected graph each edge is an unordered pair $\{u, v\}$.
We note $\langle X \rangle$ a sequence of nodes. We say that $v$ is a
neighbor of $u$, if $\{u, v\} \in E$. The set of neighbors of a given
vertex $v$ is called the neighborhood of $v$, denoted $\Gamma(v, G)$.
When there is no ambiguity, we note $\Gamma(v, G)$ simply as
$\Gamma(v)$. We will use $|\Gamma(v)|$ to refer to the degree of $v$. A
graph $G^s = (S, E^s)$ is a subgraph of a graph $G = (X, E)$
iff $S \subseteq X$ and $E^s = \{\{v, u\} \in E \mid u, v \in S\}$. A graph is
called complete if every pair of distinct vertices is connected
by a unique edge. A clique of an undirected graph is a complete subgraph. A maximal clique is a clique that cannot
be extended by including one more adjacent vertex. Note
that enumerating all maximal cliques of a graph requires
$3^{|X|/3}$ time in the worst case [10]. The problem of testing
whether a graph contains a clique of size $k$ is NP-Complete.
Moreover, a bipartite graph is a graph $G = (X, Y, E)$ such
that $E \subseteq X \times Y$. Alternatively, a bipartite graph is a graph
that does not contain any odd-length cycles. A biclique is
a complete bipartite graph, i.e., $E = X \times Y$. Similarly,
the problem of identifying bicliques under certain size con-
ditions is NP-Complete. Bipartite graphs are ubiquitous in
many applications where the vertices represent two distinct
classes of objects, such as customers and products.

III. PSEUDO-BOOLEAN BASED GRAPH SUMMARIZATION

In this section, we present our graph summarization
approach. Our aim is to discover hidden structures cor-
responding to some graph classes and to exploit them to
represent more succinctly the main components of the graph
using a more compact representation, namely PB constraints.

A. Illustrative Examples and Motivations

Before introducing our framework, we first present some
simple motivating examples. Let us consider a clique, a well-
known graph class, $G = (X, E)$ s.t. $X = \{x_1, \dots, x_n\}$
as depicted in Figure 1.a (left hand side). Then, $G$ can
be encoded by the following PB constraint $C_{pb}(G) =$
$\sum_{1 \le i \le n} x_i = 2$.

Clearly, the 2-models of $C_{pb}(G)$ correspond exactly to the
edges of $G$. More precisely, the edge $\{x_i, x_j\}$ corresponds to
the 2-model $\mathcal{B}$ where $\mathcal{B}(x_i) = 1, \mathcal{B}(x_j) = 1$ and $\mathcal{B}(x_k) = 0$

for all $1 \le k \le n$ s.t. $k \ne i$ and $k \ne j$. So any clique can
be encoded as a cardinality constraint. This allows us to
summarize a graph with $n$ nodes and $n^2$ edges by only one
cardinality constraint with $n$ variables, 1 positive integer and
a sum operator.

Note that even if an arbitrary graph might contain several
cliques that can be encoded as a *disjunction* of PB con-
straints, it would be better to represent also other less restric-
tive graph classes. Let us consider for example a *near clique*,
a complete graph with one missing edge {$x_1, x_2$} (see Figure
1 - right hand side). This graph remains expressible through
the following equation: $2(x_n + \dots + x_3) + x_2 + x_1 \ge 3$. In-
deed, the 2-*models* of the PB constraint, with two variables
assigned to 1, corresponds exactly to the edges of the near
clique. It is important to note that the 2-*models* of the two
previous PB constraints are prime implicants.

These two examples show the potential benefits behind
using PB constraints to summarize in a compact way some
graph classes. In the sequel, we generalize our approach to
other well-known graph classes including three novel ones.

B. Pseudo Boolean Formulas

As an arbitrary graph can not be represented as a single
PB constraint, its summarization can be achieved through a
disjunction of PB constraints, where each constraint encode
a subgraph of the original graph. Obviously, to encode an
arbitrary graph $G$, one need to partition the set of edges in
$G$. In fact, each element of the partition corresponds to a
subgraph expressible as a PB constraint.

*Definition 1 (Edges Partition)*: Let $G = (X, E)$ be an
undirected graph. We define an *edges partition* of $G$ as a
set of graphs $P_e(G) = \{G_1, \dots, G_k\}$ where $\forall 1 \le i \le k$,
$G_i = (X_i, E_i)$ s.t. $\{E_1, \dots, E_k\}$ is a partition of $E$ and
$X_i = \{x \in X \mid \exists \{x, y\} \in E_i\}$.

Next, we define a *pseudo boolean formula* as a disjunction
of PB constraints s.t. each constraint is a two sided PB
constraint of the form (1) or (2).

*Definition 2:* Let $G = (X, E)$ be an undirected graph s.t. $P_e(G) = \{G_1, \dots, G_k\}$ is an *edges partition* of *G*. Then, the *PB constraints based summarization* of *G*, denoted $F_{pb}(G)$, is defined as $F_{pb}(G) = C_{pb}(G_1) \lor \dots \lor C_{pb}(G_k)$.

To ensure correctness, our PB constraints based sum-
marization must satisfy some principles as shown by the
following definition.

*Definition 3:* Let $G = (X, E)$ be an undirected graph. A PB formula $F_{pb}(G)$ is a correct PB constraints based summarization of $G$ if it satisfies the following properties:

• $\mathcal{B} \models F_{pb}(G)$ can be answered in linear time,

* there is a one to one mapping between 2-
models($F_{pb}(G)$) and $E$,

• 1-models($F_{pb}(G)$) = $\emptyset$.

Let us note that a straightforward representation of the
whole graph as a PB formula consists in encoding each sin-
<figure><img src="image_31.png" /></figure>

<figure><img src="image_32.png" /></figure>

<figure><img src="image_33.png" /><figcaption>Figure 1: (Almost) Clique and Biclique</figcaption></figure>

gle edge {$x_i, x_j$} as a PB constraint of the form $x_i+x_j = 2$. Clearly, such summarization is not compact.

### C. From Clique-Bipartite Graphs to New and Hybrid Classes

In this subsection, we present new classes of graphs that can be expressed using PB constraints. These structures are obtained by relaxing the definition of well-known graph classes (e.g. bipartite, cliques) or by building hybrid classes from them.

1) **Nested-Bipartite Graph:** Before defining our first new graph class, we consider the case where a bipartite graph is complete (biclique). Let us recall that traditional approaches for compressing bipartite graphs use an additional node, called virtual node, connecting one side of the bipartite graph to that virtual node and the virtual node to the other side of the bipartite graph (e.g. [11], [12]). Such approaches allow to reduce the number of edges from a quadratic number to a linear number. To highlight the expressive power of PB constraints, we now consider biclique graphs class (see Figure 1.b) as stated in the following proposition.

**Proposition 1:** Let $G = (X, Y, E)$ be a biclique where $|X| = n$ and $|Y| = m$. Then, $G$ can be expressed as:

$$2 \times \sum_{i=1}^{n} x_i + 3 \times \sum_{j=1}^{m} y_j = 5 \quad (5)$$

Clearly, equation (5) is a two sided PB constraint of the form (2) where $b_{min} = b_{max} = 5$.

In the following, we extend the class of bipartite graphs (see Definition 5). For that we need some further notation.

Definition 4: Let $G = (X, E)$ be a graph and $u, v \in X$. The nodes $u$ and $v$ are called *nested nodes*, denoted $u \subseteq \Gamma v$, iff $\Gamma(u) \subseteq \Gamma(v)$. Then, $\langle X \rangle = \langle x_1 \dots x_n \rangle$ is a *nested sequence of nodes* if $X$ is totally ordered under the binary relation $\subseteq_{\Gamma}$, i.e., $x_n \subseteq_{\Gamma} x_{n-1} \subseteq_{\Gamma} \dots \subseteq_{\Gamma} x_1$.

Definition 5: Let $G = (X, Y, E)$ be a bipartite graph. Then, $G$ is called a *Nested-Bipartite graph* w.r.t $X$ (NB graph for short) if $\langle X \rangle$ is a nested sequence of nodes.

That is, a biclique is specific case of the NB graph where $\Gamma(x_1) = \Gamma(x_2) = \dots = \Gamma(x_n)$.

The following Definition is useful in order to derive the PB constraint for NB graphs.

**Definition 6:** Let $G = (X, Y, E)$ be a bipartite graph. Then, $G$ is a *Nested-Ordered Bipartite graph* (NOB graph for short) if there exists a sequence of nested nodes $\langle X \rangle = \langle x_1 \dots x_n \rangle$ and a sequence $\langle Y \rangle = \langle y_1 \dots y_m \rangle$ s.t. $\forall i \in \{1 \dots n\}, \langle \Gamma(x_i) \rangle = \langle y_1 \dots y_{m_i} \rangle$ where $m_i = |\Gamma(x_i)|$.

**Definition 6** states that a NOB graph $G = (X, Y, E)$ is a NB graph where $Y$ can be reordered as a sequence $\langle Y \rangle$ s.t. each $\Gamma(x_i)$ is represented as a sub-sequence of $\langle Y \rangle$ starting with $y_1$ (All the neighborhood sequences of $x_i$ start on the same node $y_1$). Let us note that $m = m_1 \ge m_2 \ge \dots \ge m_n$, since $\langle x_1 \dots x_n \rangle$ is a sequence of nested nodes.

Next, we show that a NB graph w.r.t $X$ is a NOB graph.

**Proposition 2:** If $G = (X, Y, E)$ is a NB graph w.r.t. $X$ then $G$ is a NOB graph.

By Proposition 2, if a graph is a NB graph w.r.t. $X$, then it is also a NB graph w.r.t. $Y$.

In the sequel, we denote the NOB representation associated to a NB graph $G$ by $G_{nob}$.

**Example 1:** Figure 2 shows how a NB graph can be reordered as a NOB graph. As we can see, the graph on left side of the Figure is a NB graph w.r.t. to $X$, i.e., $x_3 \subseteq_{\Gamma} x_2 \subseteq_{\Gamma} x_1$. The graph on the right side shows the obtained NOB structure, where $y_4 \subseteq_{\Gamma} y_3 \subseteq_{\Gamma} y_2 \subseteq_{\Gamma} y_1 \subseteq_{\Gamma} y_5$ and $\langle \Gamma(x_3) \rangle = \langle y_4, y_3 \rangle$, $\langle \Gamma(x_2) \rangle = \langle y_4, y_3, y_2 \rangle$, $\langle \Gamma(x_3) \rangle = \langle y_4, y_3, y_2, y_1, y_5 \rangle$. Then, all the neighborhood sequences of nodes of the variables from $X$ admit the same starting node $y_2$.

<figure><img src="image_34.png" /><figcaption>Figure 2: From NB Graph to NOB Graph</figcaption></figure>

In Proposition 2, we have shown that a NB graph can be represented as a NOB graph. Such representation allows us to obtain the PB constraint expressing the NB graph.

**Proposition 3:** Let $G = (X, Y, E)$ be a NB graph w.r.t. $X$. Let $G_{nob} = (\langle X \rangle, \langle Y \rangle, E)$ be a NOB representation of $G$ where $\langle X \rangle = \langle x_1 \dots x_n \rangle$ and $\langle Y \rangle = \langle y_1 \dots y_m \rangle$. Then, $G = (X, Y, E)$ is expressible with the following two sided
PB constraint:

$$-m \leq \sum_{i=1}^{m} (m+j) \times y_j - \sum_{j=1}^{n} (m+m_i) \times x_i \leq 0 \quad (6)$$

As for NB graphs, the PB constraint expressed bicliques is as follows.

$$-m \leq \sum_{i=1}^{m} (m + j) \times y_j - 2m \sum_{j=1}^{n} x_i \leq 0 \quad (7)$$

**Example 2:** Let us consider the graph depicted in Figure 2. This graph can be expressed as: $-5 \leq 6y_4 + 7y_3 + 8y_2 + 9y_1 + 10y_5 - 10x_1 - 8x_2 - 7x_3 \leq 0$.

Let us now state an interesting property of NB graphs.

**Definition 7:** We define the complement of a bipartite graph $G = (X, Y, E)$ as the bipartite graph $G^c = (X, Y, E^c)$, where $E^c = \{(x, y) \in X \times Y | \{x, y\} \notin E\}$.

**Proposition 4:** If $G = (X, Y, E)$ is a NB graph, then $G^c = (X, Y, E^c)$ is a NB graph.

**2) Sequence-Bipartite Graphs:** Let us now present our second graph class, called Sequence-Bipartite graph.

**Definition 8:** A bipartite graph $G = (X, Y, E)$ is a Sequence-Bipartite graph (SB graph for short) if $X$ and $Y$ can be written as sequences $\langle X \rangle = \langle x_1 \dots x_n \rangle$ and $\langle Y \rangle = \langle y_1 \dots y_m \rangle$ s.t. there exists an integer $k > 0$ where $\forall i \in \{1 \dots n\}, \exists k_i \in \{1 \dots m\}$ s.t. $\langle \Gamma(x_i) \rangle = \langle y_{1+k_i} \dots y_{k+k_i} \rangle$.

That is, a SB graph is a new class of the bipartite graph that consists of a set of nodes $X$ where their neighbors are sub-sequences of size $k$ successively translated with $k_i$ over $\langle Y \rangle$.

In the following, let $G_{sb} = (\langle X \rangle, \langle Y \rangle, E)$ represents the SB graph associated to $G = (X, Y, E)$ where $\langle X \rangle$ and $\langle Y \rangle$ are two sequences of the nodes of $X$ and $Y$, respectively, satisfying the conditions of Definition 8.

**Proposition 5:** If $G = (X, Y, E)$ is a SB graph, then $G^c = (X, Y, E^c)$ is a SB graph.

**Proposition 6:** A SB graph is expressible through the following two sided PB constraint:

$$1 \leq \sum_{j=1}^{m} (k+j) \times y_j - \sum_{i=1}^{n} (k+k_i) \times x_i \leq k \quad (8)$$

**Example 3:** Figure 3 depicts an SB graph. We have $\forall x \in X, |\Gamma(x)| = 5$. The neighborhood sets of $x_1, \dots, x_5$ are obtained by translation with $k_1 = 0, k_2 = 0, k_3 = 1, k_4 = 2, k_5 = 2$, respectively. This graph can be expressed by the following two-sided PB constraint: $0 \leq 8(y_1 - x_3) + 9(y_2 - x_4 - x_5) + 10y_3 + 11y_4 + 12(y_5 + y_7) + 13y_6 - 7(x_1 + x_2) \leq 5$.

We note that a biclique is specific case of SB graphs where $k_i = 0, \forall i \in \{1 \dots n\}$ and $k = m$. Hence, a biclique can

<figure><img src="image_35.png" /><figcaption>Figure 3: A Sequence-Bipartite Graph</figcaption></figure>

be expressed differently using the two-sided PB constraint:

$$1 \leq \sum_{j=1}^{m} (m + j) \times y_j - m \sum_{i=1}^{n} x_i \leq m \quad (9)$$

**3) Clique-Nested-Bipartite graph:** Here, we define a third hybrid structure combining both cliques and NB graphs.

**Definition 9:** A graph $G_{cnb} = (X, Y, E)$ is called Clique-Nested-Bipartite graph (CNB graph for short) if it satisfies the following conditions:

1) The graph $G_c = (X, E')$ with $E' = \{\{u, v\} \in E | u, v \in X\}$ is a clique, and

2) The graph $G_{nb} = (X, Y, E'')$ with $E'' = \{\{u, v\} \in E | u \in X, v \in Y\}$ is a NB graph w.r.t. $X$.

**Proposition 7:** A CNB graph can be expressed using the following two sided PB constraint.

$$\sum_{j=1}^{m} (-m - 1 + j) \times y_j - \sum_{i=1}^{n} (m - 1 + m_i) \times x_i \leq -2m \quad (10)$$

Note that for the particular case of clique-biclique graphs (see Figure 4 right side), the PB constraint can be expressed as follows:

$$\sum_{i=1}^{m} (-m - 1 + j) \times y_j - (2m - 1) \sum_{j=1}^{n} x_i \leq -2m \quad (11)$$

**Example 4:** Let us consider the CNB graph depicted in Figure 4 (left side). This graph contains two sets of nodes $X = \{x_1, x_2, x_3\}$ and $Y = \{y_1, \dots, y_5\}$. As we can see, the graph consists of two subgraphs, a clique involving $X$ and a NB graph on $X$ and $Y$ w.r.t. $\{x_1, x_2, x_3\}$, i.e, $x_3 \subseteq \Gamma, x_2 \subseteq \Gamma, x_1$. This graph can be expressed as: $5y_1 + 4y_2 + 3y_3 + 2y_4 + y_5 + 9x_1 + 8x_2 + 6x_3 \geq 10$.

**4) Graph classes: a Summary:** Let us now summarize the different graph classes discussed above. In Figure 5, we describe the relations between them. Let $A$ and $B$ be two graph classes, an arc $A \to B$ means that $A$ is a subclass of $B$. In other words, there are graphs in the class $B$ that do not belong to $A$. For clarity, we depict the new graph classes by grey color.

**5) Summarization by Subgraph Discovery: an Heuristic Approach:** Let us now address the problem of summarizing arbitrary graphs as PB formulas. Our approach is based on subgraph classes discovery. We are interested to detect the
<figure><img src="image_36.png" /></figure>

<figure><img src="image_37.png" /><figcaption>Figure 4: Clique-Nested-Bipartite Graphs</figcaption></figure>

<figure><img src="image_38.png" /><figcaption>Figure 5: Graph Hierarchy</figcaption></figure>

subgraphs that can be represented through PB constraints and then iterate such process until no "interesting" part of the graph can be represented compactly. As discussed in Section II, discovering some structures is NP-Complete. So, an exact discovery technique, which considers all the possible ordered combinations of the candidate subgraph classes and chooses the best summarization is intractable and not usable in practice. Thus, we need a heuristic-based approach that will give an efficient but approximate summarization of the whole graph. To show the feasibility of our proposed framework, we adopt a greedy approach limited to the discovery of NB graphs. Our first graph summarization approach using the NB graphs class as a PB formula is described in Algorithms 1 and 2. More precisely, the first algorithm is called to search for the next NB graph, while the second one encodes these NB subgraphs as a PB formula.

Let us start our explanation with Algorithm 1. It takes as input the current graph, and output the NB subgraph and the remaining graph (or graph residue). The graph residue is obtained by deleting the edges of the NB subgraph from the current graph, and then by deleting the single nodes (nodes with degree 0). The second Algorithm 1 proceeds

as follows. It starts by initializing the graph residue to the current graph and the NB graph to an empty graph (line 3). In line 4, we look for the node *x* with the maximum degree in the current graph (*maxDegreeNode*). The set *Y* is set to the neighbors of *x* (line 5). In the repeat loop (lines 6-13), we search for the next node with a maximum overlap (*maxOverlapNeighbors*) with *Y* in the graph residue (line 13). It is important to note that this function return *nil* if there is no node *x* sharing neighbors with *Y*. At each iteration, we update the current set of neighbors *Y* (line 7), the NB graph *G*<sub>nb</sub> (line 8) and the residue graph *G*<sub>r</sub> (line 9-11) accordingly. As we can see, in line 10 and 11, we also delete the single nodes from the graph residue.

In Algorithm 2, we present our NB Graph Summarization approach based on PB constraints (called PBnbGS). We take an arbitrary graph *G* and return a PB formula encoding all the NB subgraphs discovered by successive calls to Algorithm 1. Our algorithm also outputs the waste subgraph *G*<sub>w</sub> that can not be encoded compactly using our approach. More precisely, we search for the next NB subgraph (line 5). The PB constraint encoding the returned NB subgraph is added disjunctively to the PB formula only if its number of nodes is at least two (lines 6-7). Otherwise, there is no benefit to encode a NB subgraph with only one node and its neighbors. Obviously, this particular NB subgraph (a biclique) can be encoded using the PB constraint (5), but not in a compact way. In this case the returned NB subgraph is added to the waste graph (line 8). The algorithm ends when the set of edges of the graph residue is empty.

Finally, our approach is also able to encode an arbitrary graph with a PB formula without waste subgraph. Indeed, the NB subgraphs that we decided to not encode are bicliques of the form ({*x*}, *Y*, *E*). Indeed, using the PB constraint (5), we obtain 2 × *x* + 3 × Σ<sub>y∈*Y*</sub> *y* = 5.

## IV. EXPERIMENTAL EVALUATION

In this section, we consider NB graphs as described previously in Section III-C and we present some empirical results regarding the coverage that we can achieve using them. We also report the maximum, the minimum, and the average size among the NB graphs extracted from an input graph.

The experiments are carried out on a PC with an Intel Core 2 Quad Q9400 processor, with 8 GB RAM, and the Precise Pangolin x86_64 OS. Our implementation of Algorithm 2 was written in Python and run with PyPy 2.4.0 (http://pypy.org/). Only one CPU core was used.

In these preliminary experiments, we emphasize on the summarization aspect. We are particularly interested in the structure identification that will help the user to better understand the main graph characteristics.

We implemented and tested our proposed approach on a wide variety of large scale graphs: biological networks,
**Algorithm 1: nextNB_Graph**

**Input:** a graph $G = (X, E)$

**Output:** (a NB subgraph $G_{nb} = (X^{nb}, E^{nb})$, a graph residue $G_r = (X^r, E^r)$)

1. $(X^r, E^r) \leftarrow (X, E)$; $(X^{nb}, E^{nb}) \leftarrow (\emptyset, \emptyset)$;

2. $x \leftarrow \maxDegreeNode(G_r)$;

3. $Y \leftarrow \Gamma(x, G_r)$;

4. **repeat**

5. $Y \leftarrow Y \cap \Gamma(x, G_r)$;

6. $(X^{nb}, E^{nb}) \leftarrow (X^{nb} \cup \{x\}, E^{nb} \cup \{{\{x, v\}}|v \in Y\})$;

7. $(X^r, E^r) \leftarrow (X^r, E^r \setminus E^{nb})$;

8. **if** $(|\Gamma(x, G_r)| = 0)$ **then**

9. $X^r \leftarrow X^r \setminus \{x\}$;

10. **end**

11. $x \leftarrow \maxOverlapNeighbors(G_r, Y)$;

12. **until** $(x = \text{nil})$;

13. **return** $(G_{nb}, G_r)$;

14. **common**

**Algorithm 2: Summarization using Linear Inequalities (SuLI)**

**Input:** a graph $G = (X, E)$

**Output:** (a PB Formula $F_{pb}$, a Waste Graph $G_w = (X^w, E^w)$)

1. $F_{pb} = \top$;

2. **repeat**

3. $(G^{nb}, G_r) \leftarrow \text{nextNB\_Graph}(G)$;

4. **if** $(|X^{nb}| > 1)$ **then**

5. $F_{pb} \leftarrow F_{pb} \lor C_{pb}(G_{nb})$;

6. **end**

7. **else**

8. $(X^w, E^w) \leftarrow (X^w \cup X^{nb}, E^w \cup E^{nb})$;

9. **end**

10. **until** $(E^r = \emptyset)$;

11. **return** $(F_{pb}, G_w)$;

citation networks, web networks, qualitative constraint networks, peer-to-peer networks, collaboration networks, networks with ground-truth communities (see Table I).

Global-hgnc is a global human protein interactome dataset that was complied from public databases (HPRD, BIND, DIP, IntAct, MINT, BioGRID). Facebook is a social network that describes circles (or friends lists) from Facebook where nodes are humans. Ca-AstroPh (Astro Physics), GR-QC (General Relativity and Quantum Cosmology), and COND-MAT (Condense Matter Physics) are three collaboration networks that cover scientific collaborations between authors of papers submitted to Astro Physics category, General Relativity and Quantum Cosmology category, and Condense Matter category respectively. These data are

collected from e-print arXiv and cover papers in the period from January 1993 to April 2003 (124 months). Adml, Gadml and Gag are three qualitative constraint networks that represent the administrative geography of Great Britain, the German administrative units and the Greek administrative geography, respectively. Flickr is a social dataset built by forming links between images sharing common metadata from Flickr. The original images are collected from PASCAL, ImageCLEF, MIR, and NUS-wide. The DBLP graph is a co-authorship network where two authors are connected if they publish at least one paper together. This data of computer science bibliography provides a comprehensive list of research papers in computer science. com-LiveJournal is a social network that describes free on-line blogging community where users declare friendship each other. LiveJournal also allows users to form a group which other members can then join. web-google is an undirected (originally directed) web graph extremely large which comes from different web pages and the links between them on the internet. cnr-2000 is a web graph from a crawl of the Italian CNR domain. epinions is a who-trust-whom online social network of a general consumer review site Epinions.com. Members of the site can decide whether to "trust" each other. This network was originally directed. gnutella-31 is a peer-to-peer network where a sequence of snapshots of the Gnutella peer-to-peer file sharing network from August 2002. This graph was originally directed. The Cit-hep-th and CoAuth-hep-ph high-energy physics theory citation graphs are from the e-print arXiv and covers all the citations within a data that covers papers in the period from January 1993 to April 2003 (124 months). These networks were originally directed. The aforementioned graphs vary in category, size, and type, and are therefore very good candidates for examining the effectiveness of our proposed method.

How does our algorithm PBnbGS summarize real graphs? Is a NB graph a frequently encountered pattern in the structure of a given graph, and if so, what is its size approximately?

Table I shows the results of our algorithm for different real-datasets. Interestingly, our experimental results show that NB graphs occur frequently in real datasets. This fact alone allows us to describe a given graph more succinctly, and then help to understand the main graph characteristics in a simple manner. In Table I, we also observe that in many networks, like Global-hgnc, Facebook, Ca-AstroPh, Flickr, com-LiveJournal, Cit-hep-th, CoAuth-hep-ph, and Amazon_2003_all, our method attained an impressive coverage of the original graphs with NB graphs. As it can be seen in Table I, there is a significant number of NB graphs in Flickr, DBLP, Cit-hep-th, and Amazon_2003_all, among other networks. Moreover, as our experimental results show, for web graphs, especially
web-google network, our algorithm does not allow a high coverage of the original graph. This is because these graphs are very sparse.

From Table I, the CPU time needed to compute all NB graphs is less than 30 minutes; for most graphs whose number of edges is below one million, the computing time is less than one minute.

As a summary, we noticed that NB graphs appear very often in fourteen of real-world graphs (e.g., in citation network, social networks, qualitative networks and collaboration networks). These preliminary results by considering only one graph class (NB graphs) among those described in Section III-C are very promising. As a next step, we plan to consider all the graph classes both individually and in combination. The most important issue is then to design efficient algorithms for their identification.

## V. RELATED WORK

During past decades, many algorithms were proposed for graph compression, graph summarization and graph clustering. In this section, we only provide a very brief survey on some of the most related research work. We particularly focus on graph compression and summarization.

Graph compression and graph summarization (e.g. [21], [22]) are active research issues. The goal is twofolds, simplify the graph for better understanding and extract relevant structural knowledge. Several approaches are based on Subdue [23], one of the classical graph compression algorithm. They exploit the Minimum Description Length (MDL) principle to evaluate the interestingness of the mined substructures in term of compression. Among them, one can cite the compression model proposed by Navlakha et al. [22] that provide a highly compact two-part representation of a given graph consisting of a graph summary and a set of corrections. In [21], the authors propose a novel algorithm, called SCMiner, integrating graph summarization, graph clustering, link prediction and the discovery of the hidden structure on the basis of data compression. It proceeds by reduction of a bipartite input graph to a compact representation useful for several data mining tasks. Many other approaches try to discover interesting substructures using clustering and mining, community detection particularly in web graphs and social networks to achieve compression or summarization. In [11], a frequent pattern mining approach to extract meaningful connectivity formations. The authors propose a virtual node miner to achieve graph compression by generating virtual nodes from frequent itemsets in vertex adjacency lists. Motivated by the complexity of social, biological networks and other relations, several contributions have been proposed to deal with more complex graphs (e.g. [24]). Finally, an interesting graph summarization system, called VoG, is proposed by Danai Koutra et al. in [25]. The main ideas behind the proposed system is first to identify a set of subgraph-types that often occur in real graphs (e.g.,

stars, cliques, chains), find the most succinct description of a graph in terms of this graph classes. This last step is achieved by means of the MDL principle: a subgraph is included in the summary if it decreases the total description length of the graph. This last mentioned approach clearly share the idea of discovering subgraphs classes to achieve better summarization. Our proposed approach have significant difference, in both the considered graph classes, on how they are detected and on the way the graph is summarized (using constraints instead of MDL principle). From this brief description of the related works, our approach can benefit from the use of preprocessing techniques based for example on clustering or community detection to circumscribe our target subgraphs. These kind of approaches might be helpful to overcome the intractability of the subgraph detection problem.

In the second experiment, we compare our PBnbGS compression algorithm to the state of the art VOG tool [25]. Let us recall that VOG is a standard tool for graph summarization. It uses connectivity structures (stars, cliques, etc) represented as special vocabulary of graph primitives to summarize graphs. In Table II we report for each graph (column 1) its original size (column 2), the ratio compression using VOG (column 3) and the ratio compression using PBnbGS approach (column 4). We also consider other graphs. As we can remark, on many graphs, our PBnbGS outperforms VOG (e.g., Youtube, Twitter, epinion, etc.). On the other side, there exists graphs where VOG performs well. More especially KARATE, Com - Google, etc. Let us recall that the obtained results are very interesting since our compression approach is limited to nested bipartite graphs.

Let us remark that our new approach even if limited to nested bipartite graph is able to outperform VOG on many graphs e.g., Youtube, Twitter, epinion, etc.

## VI. CONCLUSION

In this paper, we proposed a novel approach for summarizing large graphs. Starting from the observation, that arbitrary graphs might contain hidden connected graph structures that can be represented by some graph classes, our method aims to discover such structures and summarize them using a more compact representation. Our contributions cover several aspects of the summarization process, including (i) the definition of new graph classes that can also be of interest for graph community, (ii) a first encoding of these new and some other well known graph classes as PB constraints, (iii) a new PB constraints based graph summarization algorithm and (iv) an experimental evaluation on real world graphs. In addition to the ability of our approach to summarize large graphs as shown by the experimental evaluation, the results obtained in this paper opens new research opportunities for cross-fertilization between data mining, graph theory and artificial intelligence.
<table><caption>Table I: Summarization results on real-world dataset</caption><thead><tr><th>Network</th><th>nodes/edges</th><th># NB graphs</th><th>coverage</th><th>min/max size</th><th>avg size</th><th>CPU time (s)</th></tr></thead><tbody><tr><td>Global-hgnc [13]</td><td>11 120/84 766</td><td>1 562</td><td>76.04%</td><td>2/2 402</td><td>40</td><td>112.26</td></tr><tr><td>Facebook [14]</td><td>4 039/88 234</td><td>731</td><td>81.23%</td><td>2/2 876</td><td>98</td><td>25.31</td></tr><tr><td>Ca-AstroPh [15]</td><td>18 772/198 110</td><td>3 119</td><td>81.60%</td><td>2/2 180</td><td>51</td><td>340.93</td></tr><tr><td>GR-QC [15]</td><td>5 242/14 496</td><td>360</td><td>51.63%</td><td>2/272</td><td>20</td><td>3.74</td></tr><tr><td>COND-MAT [15]</td><td>23 133/93 497</td><td>2 838</td><td>66.27%</td><td>2/501</td><td>21</td><td>225.20</td></tr><tr><td>Adm1 [16]</td><td>11 761/44 832</td><td>1 525</td><td>54.66%</td><td>2/137</td><td>16</td><td>42.40</td></tr><tr><td>Gadml [17]</td><td>42 749/159 600</td><td>1 459</td><td>41.57%</td><td>12/4 612</td><td>595</td><td>166.17</td></tr><tr><td>Gag [17]</td><td>1 732 999/5 236 270</td><td>2 635</td><td>65.12%</td><td>24/5 200</td><td>1 294</td><td>303.46</td></tr><tr><td>Flickr [18]</td><td>105 938/2 316 948</td><td>8 084</td><td>75.65%</td><td>2/52 071</td><td>216</td><td>4 837.76</td></tr><tr><td>DBLP [18]</td><td>317 080/1 049 866</td><td>8 281</td><td>30.88%</td><td>2/690</td><td>39</td><td>5 785.81</td></tr><tr><td>com-LiveJournal [18]</td><td>3 997 962/34 681 189</td><td>4 365</td><td>73.15%</td><td>43/7 948</td><td>1476</td><td>3 643.52</td></tr><tr><td>web.google [19]</td><td>855 802/4 291 352</td><td>2 582</td><td>15.12%</td><td>2/6 831</td><td>251</td><td>3 166.22</td></tr><tr><td>cnr-2000 [20]</td><td>325 557/3 216 152</td><td>487</td><td>37.81%</td><td>8/194 103</td><td>2 126</td><td>417.23</td></tr><tr><td>epinions [19]</td><td>75 877/405 739</td><td>924</td><td>26.20%</td><td>2/2 334</td><td>115</td><td>1 387.08</td></tr><tr><td>gnutella-31 [19]</td><td>62 561/147 878</td><td>3 400</td><td>30%</td><td>2/65</td><td>13</td><td>804.28</td></tr><tr><td>Cit-hep-th [19]</td><td>27 400/352 021</td><td>9 388</td><td>91.52%</td><td>2/4 203</td><td>34</td><td>1 765.15</td></tr><tr><td>CoAuth-hep-ph [19]</td><td>11 204/117 619</td><td>774</td><td>72.37%</td><td>2/3 213</td><td>109</td><td>43.97</td></tr><tr><td>Amazon_2003_all [19]</td><td>473 315/3 505 519</td><td>141 148</td><td>82.28%</td><td>2/1 521</td><td>20</td><td>9 856.43</td></tr></tbody></table>

<table><caption>Table II: VOG vs PBnbGS</caption><thead><tr><th>instance</th><th>Original Size</th><th>VOG (%)<br>Comp. Rate</th><th>PBnbGS (%)<br>Comp. Rate</th></tr></thead><tbody><tr><td>OSM</td><td>454.8KB</td><td>44.04</td><td>28.03</td></tr><tr><td>Amazon</td><td>12.1MB</td><td>4.95</td><td>0.83</td></tr><tr><td>Cnr-com</td><td>41.5MB</td><td>39.03</td><td><b>40.24</b></td></tr><tr><td>Com-DBLP</td><td>13.4MB</td><td>19.40</td><td>14.92</td></tr><tr><td>KARATE</td><td>420B</td><td>39.28</td><td>0.24</td></tr><tr><td>Youtube</td><td>38.2MB</td><td>13.08</td><td><b>30.36</b></td></tr><tr><td>Com-email</td><td>3.7MB</td><td>54.05</td><td>51.35</td></tr><tr><td>Facebook</td><td>47MB</td><td>68.08</td><td>62.97</td></tr><tr><td>Com-Gadm</td><td>1.8MB</td><td>68.01</td><td>11.11</td></tr><tr><td>Com-Gag</td><td>76.8MB</td><td>86.97</td><td>84.24</td></tr><tr><td>Com-Google</td><td>770.3KB</td><td>69.14</td><td>35.77</td></tr><tr><td>Roadnet-ttx</td><td>82.2MB</td><td>59.24</td><td>50.24</td></tr><tr><td>Twitter</td><td>4MB</td><td>65</td><td><b>75.14</b></td></tr><tr><td>Yahoo</td><td>24.9MB</td><td>48.99</td><td><b>54.61</b></td></tr><tr><td>Flickr</td><td>48.7MB</td><td>59.54</td><td>39.01</td></tr><tr><td>epinion</td><td>380.4KB</td><td>47.42</td><td><b>73.71</b></td></tr><tr><td>Ca-ostrop</td><td>207.7KB</td><td>25</td><td><b>27.78</b></td></tr><tr><td>Ca-thepth</td><td>658.6KB</td><td>33</td><td><b>45.41</b></td></tr><tr><td>Com-lj-com</td><td>50.4MB</td><td>80</td><td>67.46</td></tr><tr><td>Toto</td><td>3.7MB</td><td>32.43</td><td><b>56.75</b></td></tr><tr><td>As-skitter</td><td>129.1MB</td><td>69.01</td><td>51.89</td></tr><tr><td>Epinion</td><td>380.4KB</td><td>60.63</td><td>47</td></tr><tr><td>www.Barbassi</td><td>2.4MB</td><td>41.66</td><td>25</td></tr><tr><td>Enron</td><td>4MB</td><td>32.5</td><td><b>47.5</b></td></tr><tr><td>Chocolate</td><td>940.3KB</td><td>39.14</td><td><b>64.14</b></td></tr></tbody></table>

There are several directions in which this work can be developed further. New graph classes that can be expressed as PB constraints can be characterized. Design of new techniques for discovering subgraphs by exploiting for clustering or community detection approaches. Reasoning on graphs represented as PB formulas is also an important research

issue. For example, how to mine graphs, how to reason on graphs and how to solve graph problems using this new representation?

REFERENCES

[1] Y. Cho and A. Zhang, “Predicting protein function by frequent functional association pattern mining in protein interaction networks,” *IEEE Trans. on Info. Techno. in Biomed.*, vol. 14, no. 1, pp. 30–36, 2010.

[2] S. Navlakha, M. C. Schatz, and C. Kingsford, “Revealing biological modules via graph summarization,” *J. Comput. Biol.*, vol. 16, no. 2, pp. 253–264, 2009.

[3] D. Bu, Y. Zhao, L. Cai, H. Xue, X. Zhu, H. Lu, J. Zhang, S. Sun, L. Ling, N. Zhang, G. Li, and R. Chen, “Topological structure analysis of the protein-protein interaction network in budding yeast,” *Nucleic Acids Research*, vol. 31, pp. 2443–2450, 2003.

[4] A. K. Jain, M. N. Murty, and P. J. Flynn, “Data clustering: A review,” *ACM Comput. Surv.*, vol. 31, no. 3, pp. 264–323, Sep. 1999.

[5] G. Tseitin, “On the complexity of derivations in the propositional calculus,” in *Structures in Constructives Mathematics and Mathematical Logic, Part II*, 1968, pp. 115–125.

[6] N. Eén and N. Sörensson, “Translating pseudo-boolean constraints into SAT,” *JSAT*, vol. 2, no. 1-4, pp. 1–26, 2006.

[7] J. P. Warners, “A linear-time transformation of linear inequalities into conjunctive normal form,” *Info. Process. Lett.*, 1996.

[8] R. Asin, R. Nieuwenhuis, A. Oliveras, and E. Rodriguez-Carbonell, “Cardinality networks: a theoretical and empirical study,” *Constraints*, vol. 16, no. 2, pp. 195–221, 2011.
[9] I. Abio, R. Nieuwenhuis, A. Oliveras, E. Rodriguez-Carbonell, and V. Mayer-Eichberger, "A new look at bdds for pseudo-boolean constraints." *J. Artif. Intell. Res.*, vol. 45, pp. 443–480, 2012.

[10] "The worst-case time complexity for generating all maximal cliques and computational experiments," *Theoretical Computer Science*, vol. 363, no. 1, pp. 28–42, 2006.

[11] G. Buehrer and K. Chellapilla, "A scalable pattern mining approach to web graph compression with communities," in *WSDM*, 2008, pp. 95–106.

[12] C. Karande, K. Chellapilla, and R. Andersen, "Speeding up algorithms on compressed web graphs," *Internet Math.*, vol. 6, no. 3, pp. 373–398, 2009.

[13] G. Scardoni, M. Petterlini, and C. Laudanna, "Analyzing biological network parameters with CentiScaPe," *Bioinformatics*, vol. 25, no. 21, pp. 2857–2859, 2009.

[14] J. J. McAuley and J. Leskovec, "Discovering social circles in ego networks," *TKDD*, vol. 8, no. 1, 2014.

[15] J. Leskovec, J. M. Kleinberg, and C. Faloutsos, "Graph evolution: Densification and shrinking diameters," *TKDD*, vol. 1, no. 1, 2007.

[16] J. Goodwin, C. Dolbear, and G. Hart, "Geographical Linked Data: The Administrative Geography of Great Britain on the Semantic Web," *Transactions in GIS*, vol. 12, pp. 19–30, 2008.

[17] C. Nikolaou and M. Koubarakis, "Fast Consistency Checking of Very Large Real-World RCC-8 Constraint Networks Using Graph Partitioning," in *AAAI*, 2014, pp. 2724–2730.

[18] J. Leskovec and A. Krevl, "SNAP Datasets," http://snap.stanford.edu/data.

[19] http://www.cs.yale.edu/homes/mmahoney/NetworkData/.

[20] P. Boldi and S. Vigna, "Law," http://law.di.unimi.it/.

[21] J. Feng, X. He, B. Konte, C. Böhm, and C. Plant, "Summarization-based mining bipartite graphs," in *KDD*, 2012, pp. 1249–1257.

[22] S. Navlakha, R. Rastogi, and N. Shrivastava, "Graph summarization with bounded error," in *SIGMOD*. ACM, 2008, pp. 419–432.

[23] D. J. Cook and L. B. Holder, "Substructure discovery using minimum description length and background knowledge," *J. Artif. Intell. Res.*, vol. 1, no. 1, pp. 231–255, Feb. 1994.

[24] H. Toivonen, F. Zhou, A. Hartikainen, and A. Hinkka, "Compression of weighted graphs," in *SIGKDD*, 2011, pp. 965–973.

[25] D. Koutra, U. Kang, J. Vreeken, and C. Faloutsos, "VoG: summarizing and understanding large graphs," in *SDM*, 2014, pp. 91–99.
Clustering Complex Data Represented as
propositional formulas

Abdelhamid Boudane, Said Jabbour, Lakhdar Sais, and Yakoub Salhi

CRIL-CNRS, Université d'Artois, F-62307 Lens Cedex, France

{boudane,jabbour,sais,salhi}@cril.fr

**Abstract.** Clustering has been extensively studied to deal with different kinds of data. Usually, datasets are represented as a n-dimensional vector of attributes described by numerical or nominal categorical values. Symbolic data is another concept where the objects are more complex such as intervals, multi-categorical or modal. However, new applications might give rise to even more complex data describing for example customer desires, constraints, and preferences. Such data can be expressed more compactly using logic-based representations. In this paper, we introduce a new clustering framework, where complex objects are described by propositional formulas. First, we extend the two well-known k-means and hierarchical agglomerative clustering techniques. Second, we introduce a new divisive algorithm for clustering objects represented explicitly by sets of models. Finally, we propose a propositional satisfiability based encoding of the problem of clustering propositional formulas without the need for an explicit representation of their models. Preliminary experimental results validating our proposed framework are provided.

# 1 Introduction

Clustering is a technique used to recover hidden structure in a dataset obtained by grouping data into clusters of similar objects. It is derived by several important applications ranging from scientific data exploration, to information retrieval, and computational biology (e.g. [1]). Such diversity in terms of application domains induces a variety of data types and clustering techniques (see. [2] for a survey). Indeed, data can be transactional, sequential, trees, graphs, texts, or even of a symbolic nature [6, 7, 10]. This last kind of data is particularly suitable for modeling complex and heterogeneous objects usually described by a set of multivalued variables of different types (e.g. intervals, multi-categorical or modal) (e.g. [3, 4, 8]). We can also mention conceptual clustering proposed more than thirty years ago by Michalski [14] and defined as a machine learning task. It accepts a set of object descriptions (events, facts, observations, ...) and produces a classification scheme over them. Conceptual clustering not only partitions the data, but generates clusters that can be summarized by a conceptual description. As a summary, conceptual and symbolic clustering are twoparadigm proposed to deal with kinds of data other than those usually described by numerical values.

In today's data-driven digital era, data might be even more complex and heterogeneous. Such complex data might represent customers desires or preferences
collected in different possible ways using surveys and quizzes. As an example, one can cite configuration systems usually designed to provide customized products satisfying the different requirements of the customer, usually modeled by constraints or logic-formulas (e.g. [11]). These customers requirements-data or the data-models provided by the configuration systems are some kind of complex data that we are interested in. These data can be represented by logic-formulas (requirements) or by models (the products satisfying the requirements). Data can also represent more complex entities such as transaction databases. Indeed, suppose that we collected several transaction databases from stores chain selling the same products, one can be interested in determining similar stores (clusters) or stores with the same behavior. This could help the manager of the stores chain to better define its trade policy. In the two previous examples, data can be better represented as a set of propositional formulas or as sets of models.

In this paper, we introduce a new clustering framework, where complex objects are described by propositional formulas. We first extend the two well known k-means and hierarchical agglomerative clustering techniques. Then, we introduce a new divisive algorithm for clustering objects represented explicitly by sets of models. Finally, we propose a propositional satisfiability based encoding of clustering propositional formulas without the need for an explicit representation of their models. Preliminary experimental results validating our proposed framework are provided before concluding.

## 1.1 Propositional Satisfiability

Let $\mathcal{P}$ be a countably infinite set of propositional variables. The set of propositional formulas, denoted $F_{\mathcal{P}}$, is defined inductively starting from $\mathcal{P}$, the constant $\perp$ denoting absurdity, the constant $\top$ denoting true, We use the greek letters $\phi$, $\psi$ to represent formulas. A Boolean interpretation $\mathcal{I}$ of a formula $\phi$ is defined as a function from $\mathcal{P}(\phi)$ to $\{0, 1\}$ (0 for false and 1 for true). A model of a formula $\phi$ is a Boolean interpretation $\mathcal{I}$ that satisfies $\phi$ (written $\mathcal{I} \models \phi$), i.e. $\mathcal{I}(\phi) = 1$. We denote the set of models of $\phi$ by $\mathcal{M}(\phi)$. A formula $\phi$ is satisfiable (or consistent) if there exists a model of $\phi$; otherwise it is called unsatisfiable (or inconsistent).

Let $\phi$ and $\psi$ be two propositional formulas, we say that $\psi$ is a logical consequence of $\phi$, written $\phi \models \psi$, iff $\mathcal{M}(\phi) \subseteq \mathcal{M}(\psi)$. The two formulas $\phi$ and $\psi$ are called equivalent iff $\phi \models \psi$ and $\psi \models \phi$, i.e $\mathcal{M}(\phi) = \mathcal{M}(\psi)$.

A CNF formula is a conjunction ($\wedge$) of clauses, where a *clause* is a disjunction ($\vee$) of literals. A *literal* is a propositional variable ($p$), called positive literal, or ($\neg p$), called negative literal. The *SAT problem* consists in deciding whether a given CNF formula admits a model or not. Another problem related to SAT is the SAT model enumeration problem. Enumeration requires generating all models of a problem instance without duplicates. Models enumeration is related to #SAT, the problem of computing the number of models for a given propositional formula. Model counting is the canonical #P-complete problem. On the practical side, for model counting, *SampleCount* a sampling based approach proposed by Gomes et al in [9], provides very good lower bounds with high confidence. Similarly, an efficient model enumeration algorithm has been proposed in [12, 5].
## 2 Motivating Example

To motivate our proposed framework, let us consider a simple example of a car dealer selling different cars bands with several possible options. For each car brand, several colors and types of fuels are available. The car dealer collected the preferences of four customers through a survey questionnaire. The first customer does not want red cars. The second wants a car with a diesel fuel, while the third wants a red car with gasoline fuel. Finally, the fourth customer prefers brand Peugeot cars. In addition to these customer desires, we also consider mutual exclusion constraints (mutex), allowing to express that each car must have only one color, one type of fuel and one car brand.

To express the different customer desires in propositional logic, we consider the following propositional variables: *r* (resp. *b*) represents red (resp. black) colors, *p* (resp. *c*) represents the Peugeot (resp. Citroen) car brand and *d* (resp. *g*) represents cars with diesel (resp. gasoline) fuel.

The mutex constraints are expressed by the following formula: $\mu = [(r \land \neg b) \lor (b \land \neg r)] \land [(g \land \neg d) \lor (d \land \neg g)] \land [(p \land \neg c) \lor (c \land \neg p)]$.

In Figure 1 (left hand side), for each customer $c_i$, we associate a propositional formula $\phi_{c_i}$ expressing its desires. We also provide the set of models satisfying both the desires of the customer and the mutex constraints ($M(\phi_{c_i} \land \mu)$). The presentation of the models follows the variables ordering: $r \prec b \prec d \prec g \prec c \prec p$. In Figure 1 (right hand side), we give a graphical representation of the preferences of the four customers. This illustrative example highlights the expressiveness of

<table><thead><tr><th>Customers</th><th>c<sub>1</sub></th><th>c<sub>2</sub></th><th>c<sub>3</sub></th><th>c<sub>4</sub></th></tr></thead><tbody><tr><td>φ<sub>c<sub>i</sub></sub></td><td>¬r</td><td>d</td><td>g ∧ r</td><td>p</td></tr><tr><td>M(φ<sub>c<sub>i</sub></sub> ∧ μ)</td><td>010101<br>010110<br>011001<br>011010</td><td>011001<br>011010<br>101001<br>101010</td><td>010101<br>011001<br>100101<br>100110</td><td>010101<br>011001<br>100101<br>101001</td></tr></tbody></table>

<figure><img src="image_39.png" /><figcaption>**Fig. 1.** Logical and Graphical Representation of Customers Preferences</figcaption></figure>

logic-based data representation while allowing the possibility to define both user and background constraints.

## 3 Adapting Standard Clustering Algorithms

In this section, we present our extension of the well-known *k*-means and agglomerative hierarchical clustering algorithms to handle objects expressed as propositional formulas. Let us first fix some necessary notations and definitions.
We use $\mathcal{P}(k, \Phi)$ to denote the problem of clustering the set of propositional formulas $\Phi = \{\phi_1, \dots, \phi_n\}$ into a set of $k$ clusters with $k \le n$. Let $\mathcal{C}$ be a family of sets over $\Phi$. $\mathcal{C}$ is a solution of $\mathcal{P}(k, \Phi)$ if and only if $|\mathcal{C}| = k$, $\bigcup_{C_i \in \mathcal{C}} C_i = \Phi$ with $C_i \cap C_j = \emptyset$ for $1 \le i < j \le k$, and $\mathcal{M}(\bigwedge_{\phi \in C_i} \phi) \ne \emptyset$ for every $C_i \in \mathcal{C}$. We say that a clustering problem $\mathcal{P}(k, \Phi)$ is *consistent* if it admits a solution.

## 3.1 k-Means Algorithm for propositional formulas Clustering

Given a set of $n$ data points in $d$-dimensional space $\mathbb{R}^d$ and a positive integer $k$, the $k$-means algorithm determines a set of $k$ points in $\mathbb{R}^d$, called centers, so as to minimize an objective function such as the mean squared distance from each data point to its nearest center. To extend the $k$-means algorithm to clustering of objects described by propositional formulas, we need to define,

1. a distance between two formulas;

2. a centroid representing a given cluster;

3. an objective function to optimize.

Let us recall that a propositional formula $\phi$ can be equivalently expressed by its set of models $\mathcal{M}(\phi)$. With this representation in mind, one can consider that two formulae $\phi_1$ and $\phi_2$ are similar if their set of common models $\mathcal{M}(\phi_1) \cap \mathcal{M}(\phi_2)$ is higher with respect to the remaining (distinctive) models $\mathcal{M}(\phi_1) \setminus \mathcal{M}(\phi_2) \cup \mathcal{M}(\phi_2) \setminus \mathcal{M}(\phi_1)$. This kind of similarity is related to the well-known contrast model of similarity proposed in a seminal paper by Tversky [15].

**Definition 1 (Tversky [15]).** Let $a$ and $b$ be two objects described by two sets of features A and B respectively. Similarity between $a$ and $b$, denoted $s(a, b)$, is defined as:

$$s(a, b) = \frac{f(A \cap B)}{f(A \cap B) + \alpha f(A - B) + \beta f(B - A)} \quad \alpha, \beta \ge 0$$

The positive coefficients $\alpha$ and $\beta$ reflects the weights given to the distinctive features of the two objects $a$ and $b$. We usually assume that $f$ is a matching function satisfying the additivity property $f(A \cup B) = f(A) + f(B)$, whenever $A$ and $B$ are disjoint. The ratio model defines a normalized value of similarity such that $0 \le s(a, b) \le 1$.

Contrast similarity model is particularly suitable in our context. To extend Definition 1, we consider the relationship between set operations and logical connectives. Indeed, the set union (resp. intersection) corresponds to disjunction (resp. conjunction). The difference between sets can be expressed using both conjunction and negation connectives, while the symmetric difference between sets can be expressed using the xor (⊕) logical connective. Indeed, we have $\mathcal{M}(\phi_1) \setminus \mathcal{M}(\phi_2) \cup \mathcal{M}(\phi_2) \setminus \mathcal{M}(\phi_1) = \mathcal{M}((\phi_1 \wedge \neg \phi_2) \vee (\phi_2 \wedge \neg \phi_1)) = \mathcal{M}(\phi_1 \oplus \phi_2)$.

Using these relationships, we derive the following extension of the ratio model[16].