Adnene Belfodil

Sylvie Cazalens

Philippe Lamarre

Keywords: Supervised Pattern Mining, Subgroup Discovery, Exceptional Model Mining, Behavioral Data Analysis

Under the term behavioral data, we consider any type of data featuring individuals performing observable actions on entities. For instance, voting data depict parliamentarians who express their votes w.r.t. legislative procedures. In this work, we address the problem of discovering exceptional (dis)agreement patterns in such data, i.e., groups of individuals that exhibit an unexpected (dis)agreement under specific contexts compared to what is observed in overall terms. To tackle this problem, we design a generic approach, rooted in the Subgroup Discovery/Exceptional Model Mining framework, which enables the discovery of such patterns in two different ways. A branch-and-bound algorithm ensures an efficient exhaustive search of the underlying search space by leveraging closure operators and optimistic estimates on the interestingness measures. A second algorithm abandons the completeness by using a sampling paradigm which provides an alternative when an exhaustive search approach becomes unfeasible. To illustrate the usefulness of discovering exceptional (dis)agreement patterns, we report a comprehensive experimental study on four real-world datasets relevant to three different application domains: political analysis, rating data analysis and healthcare surveillance.

Identifying exceptional (dis)agreement between groups

Adnene Belfodil • Sylvie Cazalens • Philippe Lamarre • Marc Plantevit 1 Introduction
Consider data describing the organization and votes of a parliamentary institution (e.g., European Parliament 1 , US Congress 2 ). Such datasets record the activity of each member in voting sessions held in the parliament, as well as information on the parliamentarians and the sessions. Table 1 provides an example. It reports the votes of Members of the European Parliament (MEPs) on legislative procedures. These procedures are described by attributes such as themes and dates. MEPs are characterized by their country, parliamentary group and age. The general trends are well known, and easy to check on these data with basic queries. For instance, the Franco-German axis is reflected by consensual votes between parliamentarians of both countries as well as the usual opposition between right wing and left wing. An analyst (e.g., a data journalist) is aware of these political positions and expects deeper insights. To this end, it is of major interest to discover groups of individuals that exhibit an unexpected mutual agreement (or disagreement) under specific conditions (contexts). For example, from Table 1, an exceptional (dis)agreement pattern is p = (c = 〈themes = 7.30 Judicial Coop〉, u 1 = 〈country = France〉, u 2 = 〈country = Germany〉), which reads: "in overall terms, while German and French parliamentarians are in agreement (comparing majority votes leads to 66% 3 of equal votes), an unexpected strong disagreement between the two groups is observed for Judicial Cooperation related legislative procedures (the respective majorities voted the same way only 33% of the time in the corresponding voting sessions, i.e. {e 3 , e 5 , e 6 })".

In this work, we aim to discover such exceptional (dis)agreement patterns not only in voting data but also in more generic data which involves individuals, entities and outcomes. In fact, voting data are particular instances of a more general type of data that we call behavioral data. It regroups any type of data featuring individuals (e.g., parliamentarians, users in social networks, patients) performing observable actions (e.g., votes, ratings, intakes) on entities (e.g., procedures, movies, restaurants, medicines). From such datasets, we aim to discover exceptional (dis)agreement between groups of individuals on specific contexts. That is to say, an important difference between the groups' behaviors is observed compared to the usual context (i.e., the whole data). This could answer a large variety of questions. For instance, considering political data, an analyst may ask: what are the controversial subjects in the European parliament in which groups or parliamentarians have divergent points of view? In collaborative rating analysis, one may ask what are the controversial items? And which groups are opposed? In Healthcare surveillance, the analyst may want to know if some medicines are prescribed much more often for one group of individuals than another one.

The discovery of regions within the data that stand out with respect to a given target has been widely studied in data mining and machine learning communities under several names [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF] (subgroup discovery [START_REF] Wrobel | An algorithm for multi-relational discovery of subgroups[END_REF], emerging patterns [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF], contrast sets [START_REF] Bay | Detecting group differences: Mining contrast sets[END_REF]). Subgroup Discovery (SD) is known as the most generic one as it is agnostic of the data and the pattern domain. For instance, subgroups can be defined by a conjunction of conditions on symbolic [START_REF] Lavrac | Subgroup discovery with CN2-SD[END_REF] or numeric attributes [START_REF] Grosskreutz | On subgroup discovery in numerical domains[END_REF][START_REF] Atzmüller | Sd-map -A fast algorithm for exhaustive subgroup discovery[END_REF] as well as sequences [START_REF] Grosskreutz | A relevance criterion for sequential patterns[END_REF]. Furthermore, the single target can be discrete or numeric [START_REF] Lemmerich | Fast exhaustive subgroup discovery with numerical target concepts[END_REF]. Exceptional Model Mining (EMM) [START_REF] Leman | Exceptional model mining. In: Machine Learning and Knowledge Discovery in Databases[END_REF] extends SD by offering the possibility to handle complex targets [START_REF] Duivesteijn | Exceptional model miningsupervised descriptive local pattern mining with complex target concepts[END_REF]. However, no model in the EMM/SD framework makes it possible to investigate exceptional contextual (dis)agreement between groups. We made a first attempt to discover exceptional (dis)agreement patterns in [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF]. However, the model proposed required the specification of many non-intuitive parameters that may be the source of misleading interpretations. In this paper, we strive to provide a simpler and more generic framework to analyze behavioral data.

Figure 1 gives an overview of the approach we devise to discover exceptional (dis)agreement between groups. At a high level of description, five steps are necessary to discover interesting (dis)agreement patterns. First, two groups of individuals (u 1 , u 2 ) are selected (1) . Then, their usual agreement on all their expressed outcomes is computed in step [START_REF] Bosc | Anytime discovery of a diverse set of patterns with monte carlo tree search[END_REF]. All characterizable subsets of entities (contexts (c)) are then enumerated (3). For each selected subset, the agreement between the two groups is measured (4) and compared to their usual agreement [START_REF] Grosskreutz | A relevance criterion for sequential patterns[END_REF] to evaluate to what extent the mutual agreement changes conditioned at a (dis)agreement pattern (c, u 1 , u 2 ). Eventually, all pairs of groups (at least conceptually) are confronted. The discovery of exceptional (dis)agreement patterns requires to explore (simultaneously) both the search space associated to the individuals and the search space related to the entities. Moreover, behavioral datasets may contain several types of attributes (e.g., numerical and/or categorical attributes potentially organized by a hierarchy), and outcomes. This requires efficient enumeration strategies. Last but not least, different measures to capture agreement may be considered depending on the application domain. Accordingly, the proposed method must be generic.

The main contributions of this paper are threefold:

Problem formulation. We define the novel problem of discovering exceptional (dis)agreement between groups of individuals when considering a particular subset of outcomes compared to the whole set of outcomes. Particular attention is paid to ensure a generic framework for behavioral data analysis. Algorithms. We propose two algorithms to tackle the problem of discovering exceptional (dis)agreement patterns. DEBuNk4 is a branch-and-bound algorithm that efficiently returns the complete set of patterns. It exploits both closure operators and optimistic estimates. Quick-DEBuNk is an algorithm that samples the space of (dis)agreement patterns in order to support instant discovery of patterns. Evaluation. We report an extensive empirical study on four real-world datasets to demonstrate the efficiency of our algorithms as well as the interest of the discovered patterns. In particular, we report three case-studies from different application domains: political analysis, rating data analysis and healthcare surveillance to demonstrate that our approach is generic. The analysis of political votes, which is done in collaboration with journalists, is also available online 5 .

The rest of this paper is organized as follows: the problem formulation is given in Section 2. We present the agreement measure and how it is integrated into an interestingness measure to capture changes of inter-group agreement in Section 3. Algorithm DEBuNk is presented in Section 4 while a pattern space sampling version, Quick-DEBuNk, is defined in Section 5. We report an empirical study in Section 6. Section 7 reviews the literature. We conclude and discuss future directions of research in Section 8.

Problem Definition

We are interested in discovering exceptional (dis)agreements among groups in Behavioral Datasets, which are defined as follows.

Definition 1 (Behavioral Dataset) A behavioral dataset 〈G I , G E , O, o〉 consists of (i) a collection of Individuals G I , (ii) a collection of Entities G E , (iii) a domain of possible Outcomes O, and (iv) a mapping function o : G I × G E → O that gives the outcome of an individual i over an entity e.

In order to define appropriately the form of the sought patterns, we need first to characterize subgroups of data records in G I and G E . These two sets are collections of records defined over a set of descriptive attributes (Schema). We denote such collection of records by G, reintroducing the subscripts only in case of possible confusion. We assume A = (a 1 , ..., a m ) to be the ordered list of attributes constituting the schema of G. Each attribute a j has a domain of interpretation, noted dom(a j ), which corresponds to all its possible values. Attributes may be numerical or categorical potentially augmented with a taxonomy referred to by Hierarchical Multi-Tag (HMT) attributes (see section 4.2). For instance, in Table 1, parliamentarians, described by their country (categorical), their political group (categorical) and their age (numerical), decide on some voting sessions outlined by a date (numerical) and themes (HMT attribute). The attributes' domains define a description domain D which corresponds to the set of all possible descriptions characterizing subgroups in G.

Definition 2 (Description) Let G be a collection defined over the schema A = {a 1 , ..., a m }, a description d ∈ D is a conjunction of conditions of the form d = 〈r 1 , ..., r m 〉 where r j depends on the type of the attribute a j :

-If a j is a categorical attribute then condition r j is an equality test of the form a j = v with v ∈ dom(a j ) ∪ { * j }. Note that * j is a symbol representing any value in dom(a j ). (i.e. every record in G satisfies a j = * j ).

-If a j is a numerical attribute then condition r j is a membership test of the form a j ∈ [v..w] with v, w ∈ dom(a j ).

A description d characterizes a subgroup of records, also called support, in G denoted

G d = {g ∈ G s.t. g satisfies d}.
Descriptions are partially ordered in D by a specialization relationship defined as follows.

Definition 3 (Specialization between descriptions ⊑) Let d and d ′ be two descriptions from D.

d ′ is said to be a specialization of d, denoted d ⊑ d ′ , iff d ′ ⇒ d, i.e. each condition r ′ j in d ′ implies its corresponding condition r j in d.
As a consequence of the previous definition, if

d ⊑ d ′ then G d ′ ⊆ G d , since each record satisfying d ′ satisfies d.
Formally, the concept of description is used to describe both sets of individuals and sets of entities. Yet, for the ease of interpretation, we use two different terms to name them: group description and context. For example, in Table 1, the context c = 〈 date ∈ [05/06/16..30/07/16] 〉 identifies the set of entities G c E = {e 4 , e 5 , e 6 }. Similarly, the group description u = 〈 group='S&D' 〉 selects the set of individuals G u I = {i 1 , i 3 }. Since we are interested in patterns highlighting exceptional (dis)agreement between two groups of individuals described by u 1 and u 2 , in a context c compared to the overall context, the sought patterns are defined as follows:

Definition 4 ((Dis)Agreement Pattern) A (dis)agreement pattern is a triplet p = (c, u 1 , u 2 ) where c ∈ D E is a context and (u 1 , u 2 ) ∈ D 2
I is a pair of group descriptions.

The extent of a (dis)agreement pattern p is ext(p) = (G c E , G u1 I , G u2 I ) with G c
E the set of entities satisfying the conditions of context c, and G u1 I (resp. G u2 I ) the set of individuals supporting the description u 1 (resp. u 2 ). The set of all possible patterns is denoted as P = D E × D I × D I . Furthermore, as P = D E ×D I ×D I is the product of three partially ordered collections, patterns of P are also partially ordered.

Definition 5 (Specialization between patterns

⊑) Let p = (c, u 1 , u 2 ) and p ′ = (c ′ , u ′ 1 , u ′ 2 ) be two patterns from P, p ′ is a specialization of a pattern p, denoted p ⊑ p ′ , iff c ⊑ c ′ , u 1 ⊑ u ′ 1 and u 2 ⊑ u ′ 2 . Notice that, if p ⊑ p ′ then ext(p ′ ) ⊆ ext(p), that is G c ′ E ⊆ G c E and G u ′ 1 I ⊆ G u1 I and G u ′ 2 I ⊆ G u2 I . Moreover, two descriptions d 1 , d 2 ∈ D are said to be equivalent if they characterize the same subset S ⊆ G, i.e. G d1 = G d2 . Similarly, two patterns p, p ′ ∈ P are equivalent if ext(p) = ext(p ′ ).
To objectively evaluate how interesting a (dis)agreement pattern is, a quality measure ϕ is required [START_REF] Duivesteijn | Exceptional model miningsupervised descriptive local pattern mining with complex target concepts[END_REF]. Definition 6 (Quality measure) A quality measure is a function ϕ : P → R which assigns to each pattern p = (c, u 1 , u 2 ) ∈ P a real number ϕ(p) ∈ R.

A quality measure is designed to compare patterns: the quality of one will be compared to the quality of the others, most of the time to choose the best one. Consequently, it must be carefully designed with respect to what the algorithm is expected to produce. Our first objective is to identify particular parts of the data. This naturally leads to quality evaluation functions focusing only on the extent of the pattern. In particular, this means that, in this paper, syntax is not considered to assess the quality of a pattern.

Consequently, the quality measures we propose6 are of the form: ϕ(p) = ϕ ′ (ext(p)). It follows that two patterns characterizing the same data, i.e. with the same extent, share the same quality measurement: ∀p,

p ′ ∈ P, if ext(p) = ext(p ′ ) then ϕ(p) = ϕ(p ′ ).
The user will be provided with a collection of patterns that captures exceptional (dis)agreements in a given behavioral dataset. A first intuitive idea is to provide all patterns of high quality, i.e. with a quality greater than a user-defined threshold σ ϕ . However, by construction of the quality measures, different patterns sharing the same extent will reach the same quality level, leading to multiple descriptions of the same parts of the data. Assuming that the user can be quickly bothered by such duplication, we propose to expose each interesting part of the data only once. More interestingly, the system should provide the user with the best generalizations only, i.e., patterns whose extent is not included in some other found ones. Additionally, some cardinality constraints can be added to avoid patterns of too small extent. Given two minimum support thresholds σ E and σ I , these constraints ensure, for a pattern p = (c, u 1 , u 2 ), that the size of the context extent (i.e. Given a behavioral dataset 〈G I , G E , O, o〉, a quality measure ϕ, a quality threshold σ ϕ and a set of cardinality constraints C, the problem is to find the pattern set P ⊆ P such that the following conditions hold: 1. (Validity) ∀p ∈ P, p is valid ; that is p satisfies C and ϕ(p) ≥ σ ϕ . 2. (Maximality) ∀p ∈ P ∀q ∈ P, ext(q) = ext(p) ⇒ q ⊑ p.

(Completeness) ∀q

∈ P \ P, q is valid ⇒ ∃p ∈ P, ext(q) ⊆ ext(p). 4. (Generality) ∀(p, q) ∈ P 2 , p ∕ = q ⇒ ext(p) ⊈ ext(q).
Condition (1) ensures that the patterns in P are of high quality and satisfy the cardinality constraints. Condition (2) retains only one unique representative among patterns sharing the same extent: the maximal one w.r.t. ⊑. Such a pattern exists only if the specialization relation ⊑ over the pattern space induces a lattice structure [START_REF] Ganter | Pattern structures and their projections[END_REF]. It is commonly referred to as the closed pattern [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF]. We confine ourselves to such pattern spaces. Condition (3) ensures that each valid pattern in P has a representative in P covering it, while condition (4) ensures that only the most general patterns w.r.t. their extents are in P . In other words, the combination of conditions (3) and (4) guarantees that the solution P is minimal in terms of the number of patterns while having each valid pattern represented in the solution. Considering the generic definition of the quality measure discussed here, this problem extends the top-k problem addressed in [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF]) by introducing conditions (3) and (4). That is, for a sufficiently large k, the method formerly provided in [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF] solves this problem only limited to the two first conditions providing, hence, a solution with a much larger number of redundant patterns.

Quality Measures and Inter-group Agreement Measurement

The previous section has already hinted at the fact that pattern interestingness is assessed with a quality measure ϕ (cf. Definition 6). Here, we propose such measures to capture the deviation between the contextual inter-group agreement and the usual inter-group agreement.

Quality Measures

For any pattern p = (c, u 1 , u 2 ) ∈ P, we denote by p * the pattern ( * , u 1 , u 2 ) which involves the same groups but all the entities. IAS (p * ) (resp. IAS (p)), which stands for Inter-group Agreement Similarity, represents the usual (resp. contextual) inter-group agreement observed between the two groups u 1 , u 2 . In order to discover interpretable patterns, we define two quality measures using IAS (p * ) and IAS (p).

ϕ consent assesses the strengthening of inter-group agreement in a context c:

ϕ consent (p) = max (IAS (p) -IAS (p * ) , 0) . (1)
ϕ dissent assesses the weakening of inter-group agreement in a context c:

ϕ dissent (p) = max (IAS (p * ) -IAS (p) , 0) . (2)
For instance, one can use ϕ consent to answer: "What are the contexts for which we observe more consensus between groups of individuals than usual? ".

Inter-group Agreement Similarity (IAS)

Several IAS measures can be designed according to the domain in which the data was measured (e.g., votes, ratings) and the user objectives. The evaluation of an IAS measure between two groups of individuals over a context requires the definition of two main operators: the outcome aggregation operator (θ) which computes an aggregated outcome of a group of individuals for a given entity, and a similarity operator (sim) which captures the similarity between two groups based on their aggregated outcomes over a single entity. These operators are defined in a generic way as follows.

Definition 7 (Outcome Aggregation Operator θ) An aggregation operator is a function θ : 2

G I × G E → D.
θ(u, e) simply transforms the outcomes of individuals u over an entity e into a value belonging to a domain D (e.g., R, categorical values). From this, two elements of D have to be compared.

Definition 8 (Similarity between aggregated outcomes sim) A similarity betweed aggregarted outcomes is a function sim : D × D → R + . sim(x, y) assigns a real positive value to any couple of aggregated outcomes (x,y).

Based on these operators, we properly define IAS which assigns to each pattern p = (c, u 1 , u 2 ) ∈ P a value IAS(p) ∈ R + . This similarity evaluates how the two groups of individuals (u 1 , u 2 ) behave similarly given their outcomes w.r.t. the context c. In the scope of this work, we confine ourselves to IAS measures that can be expressed as weighted averages. The next definition, though limiting, is generic enough to handle a wide range of behavioral data.

Definition 9 (Inter-group Agreement Similarity Measure IAS) Let w be a function associating a weight to each triple from (G E × 2 G I × 2 G I ). IAS: P → R + associates to each pattern p the weighted average of the similarities of the aggregated outcomes for each entity e supporting the context c.

IAS (p = (c, u 1 , u 2 )) = 󰁓 e∈G c E w(e, G u1 I , G u2 I ) × sim(θ(G u1 I , e), θ(G u2 I , e)) 󰁓 e∈G c E w(e, G u1 I , G u2 I )
.

(3)

Examples of IAS Measures

By simply defining sim and θ, we present two instances of IAS measures that address two types of behavioral data with specific aims.

Behavioral Data With Numerical Outcomes: Rating datasets are a classic example of behavioral data with numerical outcomes. Such datasets describe users who express numerical ratings belonging to some interval O = [min, max] (e.g., 1 to 5 stars) over reviewees (e.g., movies, places). A simple and adapted measure for aggregating individual ratings over one entity is the weighted mean θ wavg : 2

G I × G E → [min, max]. θ wavg (G u I , e) = 1 󰁓 i∈G u I w(i) 󰁛 i∈G u I w(i) × o(i, e). (4)
Weight w(i) corresponds to the importance of ratings given by each individual i ∈ G I . Such weight may depend on the confidence of the individual or the size of the sample population if fine granularity ratings (rating of each individual ) are missing.

θ majority (G u I , e) = {v ∈ O s.t. v = argmax z∈O #votes(z, G u I , e)}. (6)
We use a Jaccard index to assess the similarity between two majority votes x and y. Hence, sim voting :

2 O × 2 O → [0, 1] is defined as follows. sim voting (x, y) = |x ∩ y| |x ∪ y| . (7)

Discussion

Above we introduced simple outcome aggregating functions and similarities that can be used to build an IAS measure to assess how similar two groups of individuals are. More sophisticated measures can be considered. For instance, in behavioral datasets with categorical outcomes, one can define an outcome aggregation measure which takes the empirical distribution of votes into account and then a similarity measure which builds up on a statistical distance (e.g., Kullback-Leibler divergence [START_REF] Csisz | Information-type measures of difference of probability distributions and indirect observations[END_REF][START_REF] Johnson | Mining gene expression data with pattern structures in formal concept analysis[END_REF]). Such measures can also be used on behavioral datasets which involves numerical outcomes, for instance the Earth Mover Distance measure was investigated in similarly structured datasets (rating datasets) in (Amer-Yahia et al, 2017). Several other measures can be relevant to analyze behavioral data with numerical outcomes depending on the aim of the study. In Section 6, "empirical study", we investigate another IAS measure which relies on a ratio to highlight discrepancies between the medicine consumption rates of two subpopulations.

4 A Branch-and-Bound Algorithm for Mining Relevant (Dis)Agreement Patterns

In this section, we present DEBuNk, a branch-and-bound algorithm that solves the problem outlined in Section 2. To this end, DEBuNk uses an exhaustive search strategy that exploits properties of closure operators to enumerate groups and contexts in a systematic manner and without redundancy. This allows the exploration of the complete search space, at least conceptually, by confronting all pair of groups (u 1 , u 2 ) ∈ D I × D I in every possible context c ∈ D E . To speed up this exploration process while ensuring completeness, it is necessary to identify areas of the search space that cannot lead to the discovery of interesting patterns (i.e. patterns whose qualities are above the minimum quality threshold σ ϕ ). This is where optimistic estimates for the used quality measures are needed, since they provide an upper bound on the maximum possible quality measurement that a pattern can observe in each sub-search space. Algorithm 1 outlines the different ingredients of DEBuNk

= D E × D I × D I is a crucial part of DEBuNk.
We give in Section 4.1 an overview of how the search space is structured and its main properties that one can leverage for an efficient enumeration of candidate patterns. We then pay particular attention to hierarchical multi-tag attributes in Section 4.2. 2. Evaluating the quality of candidate patterns (lines 4-6) : Section 3 already discussed how the quality of patterns is assessed by capturing the deviation between the usual inter-group agreement and the contextual one using IAS measures (see Definition 9). 3. Pruning unpromising areas of the search space (lines 7 -10): For a more efficient exploration, one need to safely discard, as early as possible, unpromising parts of the search space. To this end, we define optimistic estimates for the proposed quality measures in Section 4.3.

Once these ingredients are properly defined, we introduce, in Section 4.4, Algorithm DEBuNk which efficiently computes the complete set of exceptional (dis)agreement patterns.

Enumerating Candidate Subgroups

Exploring the space of (dis)agreement patterns from D E × D I × D I is equivalent to enumerating descriptions in D E and D I concurrently. Therefore, we explain how to enumerate descriptions for an arbitrary collection of records G associated to an arbitrary descriptions space D.

Recall that several descriptions are considered to be equivalent when they characterize the same subset S ⊆ G. This may cause redundancy which we want to avoid. Focusing on closed descriptions enables to only retain in the results set the unique maximal element w.r.t. ⊑ -identified by clo(d) -of each equivalence class ċ = {d ∈ D s.t. G c = G d } [START_REF] Ganter | Formal Concept Analysis -Mathematical Foundations[END_REF].

We need to introduce some basic notions to define the operator clo(d). Similarly to [START_REF] Ganter | Pattern structures and their projections[END_REF], we define a mapping function δ j (s) which provides a condition describing the value v of attribute a j . This clearly depends on the type of a j . δ j (s) is of the form (a j = v) (resp. (a j ∈ [v..v])) if a j is a categorical (resp. numerical) attribute. Applying such mappings to all attributes leads to the tightest (maximal) description of a record g ∈ G: δ(s) = 〈δ 1 (g), ..., δ m (g)〉. Given these mappings, the subgroup associated to a description d can be defined formally as such

G d = {g ∈ G s.t. d ⊑ δ(g)}.
Extending the definition of δ to subsets S ⊆ G characterizes a subset with the maximum common description of its elements:

δ(S) = 󰁡 g∈S δ(g) = 〈 ∧ 1 g∈S (δ 1 (g)), ..., ∧ m g∈S (δ m (g))〉. ( 8
)
δ(S) requires to compute a conjunction 9 󰁙 j of conditions related to each attribute a j . Using the aforementioned concepts, the closure operator can be defined as clo(d) = δ(G d ). This results from the fact that □ d and δ(□) form a pair of Galois derivation operators between 2 G and (D, ⊑) providing as a consequence a closure operator δ(□ d ) [START_REF] Ganter | Pattern structures and their projections[END_REF].

Algorithm 2, called EnumCC (Enumerate Closed Candidates), first introduced in [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF], enumerates once and only once all the closed descriptions that fulfill the support constraint |G c | ≥ σ G with σ G a user defined support threshold similarly to the ClosebyOne [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF] algorithm and the divide-and-conquer (Boley et al, 2010b) algorithm.

] = {clo(d) s.t. d ∈ D} 1 if |G d | ≥ σ then 2 closure d ← δ(G d ) 3 if d ⋖ f closure d then 4 cnt c ← copy(cnt)
⊲ cnt c value can be modified by a caller algorithm

5 yield (closure d, G closure d , cnt c)
⊲ yield the results and wait for next call

6 if cnt c then 7 foreach j ∈ [f, m] do 8 foreach d ′ ∈ η j (closure d) do 9 foreach (nc, G nc , cnt nc) ∈ EnumCC(G, d ′ , σ G , j, cnt c) do 10 yield (nc, G nc , cnt nc) 9 (a j ∈ [v 1 ..w 1 ]) ∧ j (a j ∈ [v 2 ..w 2 ]) = a j ∈ [min(v 1 , v 2 )..max(w 1 , w 2 )] for numerical attributes. For categorical attributes (a j = v 1 ) ∧ j (a j = v 2 ) = v 1 if v 1 = v 2 else true j .
EnumCC, initially called with the following inputs EnumCC(G, * , σ, 1, true), explores the search space D in a depth-first search manner starting from the most general description 〈true a1 , . . . , true am 〉, denoted * . It proceeds by atomic refinements to progress, step by step, toward more specific descriptions. Intuitively, an atomic refinement of a description d produces a more specific description d ′ by reinforcing the condition of one attribute only. Such descriptions are provided by a refinement operator denoted η :

D → 2 D which returns η(d) the collection of neighbor descriptions d ′ , i.e. η(d) = {d ′ ∈ D s.t. d ⊏ d ′ ∧ ∄e ∈ D, d ⊏ e ⊏ d ′ }.
η can be built up by defining a refinement operator η j for conditions related to each attribute a j ∈ A. For numerical attributes, an atomic refinement corresponds to a left-minimal (resp. right-minimal) change w.r.t. existing values of the attribute

a j in G d , that is a j ∈ [next G d (inf)..sup] (resp. a j ∈ [inf..pred G d (sup)]
) on the interval bounds of the condition (Kaytoue et al, 2011). An empty resulting interval means that there is no possible refinement. Considering a categorical attribute, the atomic refinement of a condition true aj gives a condition of the form a j = v ∈ dom(a j ). Otherwise, a condition of the form a j = v does not admit any refinement.

Given a description d, EnumCC first computes G d . If the support constraint is fulfilled (line 1), the closure of d is computed (line 2). Subsequently, a canonicity test between clo(d) and d is assessed (line 3). It enables to determine whether a description after closure was already generated and to discard it, if appropriate. The canonicity test relies on an arbitrary order between attributes in A G = {a 1 , a 2 , ..., a m } indicating that, in the enumeration process, attributes' conditions are refined following this arbitrary order. Let d = 〈r 1 , ..., r f , ..., r m 〉 be a description resulting from the refinement of the f th condition of some preceding description, and d ′ = 〈r ′ 1 , ..., r ′ f , ..., r ′ m 〉 = clo(d) the closure of d. Following the arbitrary order, we expect for d ′ , if it is the first time that it is encountered, that no condition before r ′ f (i.e. r ′ 1 , ..., r ′ f -1 ) is refined; otherwise, clo(d) was already generated after a refinement of preceding conditions and has thus to be discarded. This canonicity test is based on lectic order (cf. (Ganter and Wille, 1999, p.66-68)) between d and its closure

d ′ denoted d ⋖ f d ′ which is defined as follows: d ⋖ f d ′ ↔ ∀i ∈ [1..f -1], r i = r ′ i ∧ r f ⋖ r ′ f . The latter condition, r f ⋖ r ′
f , corresponds to an analogous canonicity test between conditions and makes sense for multi-valued attributes types only (e.g., HMT in Section 4.2). It does not need to be calculated for simple attributes (numerical, categorical). If the canonicity test is successful (line 3), clo(d) is returned as a valid closed candidate (line 5). The algorithm then generates the neighbors by refining the attributes {a f , ..., a n } from d on the condition that cnt c is not switched to False (lines 6-8). Flag f determines the index of the last attribute that was refined in the description d. Boolean cnt c can be modified externally by some caller algorithm to prune the search space, for instance, when using optimistic estimates. Eventually, a recursive call is done to explore the sub search space related to d (lines 9-10).

Hierarchical Multi-Tag Attribute (HMT)

Vote and review datasets often contain multi-tagged records whose tags are part of a hierarchical structure. For instance, voting sessions in the EU parliament can have multiple tags. For example, procedure Gender mainstreaming in the work of the EU Parliament is tagged by 4.10.04-Gender equality and 8.40.01-EU Parliament. Tag 4.10.04 is identified in a a hierarchy as a specialization of tag 4.10 that depicts Social policy and which is itself a specialization of tag 4 that covers all the sessions related to Economic, social and territorial cohesion. We formally define this type of attribute named HMT.

Definition 10 (HMT Attribute) Let T = {t 1 , t 2 . . . t k } ∪ { * } be a set of values (also called tags), < be a partial order over T inducing a tree structure (T, <) whose root is ' * '. t i < t j denotes the fact that t j is a descendant of t i in T . In addition, the ascendants (resp. descendants) of a tag t ∈ T is

↑ t = {t ′ ∈ T s.t. t ′ ≤ t} (resp. ↓ t = {t ′ ∈ T s.t. t ′ ≥ t}).
A HMT attribute a j takes its values in dom(a j ) = 2 T .

As an example, Fig. 2b describes G, a set of tag records defined by a unique attribute tags. Elements of tags are organized through the tree from Fig. 2a. We have * < 1 < 1.20 and ↑ 1.20 = {1.20, 1, * }.

For a HMT attribute a j , each record g ∈ G is mapped by δ j (g) to its corresponding tightest set of tags in dom(a j ). If δ j (g) = {t 1 , ..., t n }, the record g is tagged explicitly by all the tags t k for k ∈ [1, n] and also implicitly by all their generalizations ↑ t k . Figure 2c illustrates this by reporting the flat representation of the collection of tagged records depicted in Figure 2b. It follows that a condition over a HMT attribute is defined as follows:

Definition 11 (Condition on a HMT attribute) (extends Definition 2) Let G be a collection defined over the schema A = {a 1 , ..., a m }.

-If a j is a HMT attribute then condition r j is a superset test of the form a j ⊇ χ with χ ∈ dom(a j ) .

Accordingly, a HMT condition can be depicted by a rooted sub-tree of T and a record supports such a condition if it contains at least all tags of the sub-tree. It follows that, the partial order between two HMT conditions r, r ′ denoted r ⊑ r ′ (r ′ is a specialization r) is valid if the sub-tree r covers the sub-tree r Two ways are possible to take this attribute into account in the enumeration of descriptions from the complex search space aforementioned. One straightforward solution is to consider HMT attribute values as itemsets as depicted in the vector representation in Fig. 2c. However, such a solution ignores the taxonomy T implying the enumeration of chain descriptions. For instance, a chain description {1, 1.20.01} is regarded as a different description than {1.20.01}. This stems from the fact that items are unrelated from the viewpoint of itemsets solution. As a consequence, a larger search space is explored while determining the same number of closed descriptions. To tackle this issue, we define a HMT description language.

′ . i.e. , r ⊑ r ′ means ∀t ∈ r, ∃t ′ ∈ r ′ , t ′ ∈ ↓ t. * 1 2 3 1.10 1.20 2.10 (a) Tree of tags -T tags g 1 {1.20, 2.10} g 2 {1, 3} g 3 {1.10, 2.10, 3} g 4 {2.10} g 5 {1.20} (b) Tagged records * 1 1.10 1.20 2 2.10 3 g 1 × × × × × g 2 × × × g 3 × × × × × g 4 × × × g 5 × × × (c) Flat representation
Similarly to the aforementioned attributes, we define the conjunction operator ∧ between two conditions which computes the maximum common sub-tree covering a set of conditions. Let r = {t 1 , ..., t n } and r

′ = {t ′ 1 , ..., t ′ m } be two HMT conditions, r ∧ r ′ = max(∪ t∈r ↑ t ∩ ∪ t ′ ∈r ′ ↑ t ′ )
where max : 2 T → 2 T maps a subset of tags s ⊆ T to the leafs of the sub-tree induced by s:

max(s) = {t ∈ s s.t. (↓ t \ {t}) ∩ s = ∅}. Intuitively, r ∧ r ′ is
the set of the maximum explicit and implicit tags shared by the two descriptions (cf. Fig. 3).

Moreover, we define an atomic refinement operation which enables calculating neighbors of a HMT condition r. A condition r ′ is said to be a neighbor of r if: either only one tag of r is refined in r ′ or a new tag is added in r ′ that shares a parent with a tag in r or with one of its ascendants.

Finally, we define the lectic order between two conjunctions of tags r = {t 1 , ..., t n } and its closure r ′ = {t ′ 1 , ..., t ′ n , ..., t ′ m } for the canonicity test to avoid the enumeration of already visited descriptions. Let r be generated after a refinement of the f th tag, the lectic order is defined as:

r ⋖ f r ′ ⇔ ∀i ∈ [1..f -1] : t i = t ′ i ∧ t f ⋖ t ′ f .
The linear order ⋖ between tags can be provided by a depth first search order on T . These concepts being defined, the mapping function δ can be extended easily to handle HMT among other attributes. Note that HMT supports itemsets. This can be done simply by considering a flat tree T with all the items as leaves. Hence, HMT can be seen as a generalization of itemsets, where implications between items are known.

Optimistic Estimates on Quality Measures

The enumeration of closed patterns enables a non-redundant traversal of the search space. For a more efficient exploration, we follow a branch and bound scheme to discard unpromising parts of the search space. This requires the definition of safe pruning properties leveraging optimistic estimates on ϕ.

Let u 1 , u 2 be two descriptions from D I that respectively cover the two groups G u1 I , G u2 I . We consider optimistic estimates only with regards to the search space D E . We assume that u 1 and u 2 are instantiated a priori. Moreover, without loss of generality, we assume that the input domains of oe and ϕ are defined over both the pattern space P and 2 G E × 2 G I × 2 G I . This is possible, since the quality measure only depends on extents (cf. Section 2). Below, we give the definition of an optimistic estimate [START_REF] Grosskreutz | Tight optimistic estimates for fast subgroup discovery[END_REF].

Definition 12 (Optimistic Estimate) An optimistic estimate oe for a given quality measure ϕ is a function such that:

∀ contexts c, d ∈ D E . c ⊑ d ⇒ ϕ(G d E , G u1 I , G u2 I ) ≤ oe(G c E , G u1 I , G u2 I ).
Tight optimistic estimates, defined in [START_REF] Grosskreutz | Tight optimistic estimates for fast subgroup discovery[END_REF], offer more pruning abilities than simple optimistic estimates. The two quality measures ϕ consent and ϕ dissent rely on the IAS measure. Since u 1 and u 2 are considered to be instantiated for optimistic estimates, we can rewrite the IAS measure for a context c ∈ D E and its extent G c E :

Definition 13 (Tight Optimistic Estimate) An optimistic estimate oe is tight iff: ∀c ∈ D E . ∃S ⊆ G c E : oe(G c E , G u1 I , G u2 I ) = ϕ(S, G u1 I , G u2 I ).
IAS(G c E , G u1 I , G u2 I ) = 󰁓 e∈G c E w e × α(e) 󰁓 e∈G c E w e with 󰀫 α(e) = sim(θ(G u1 I , e), θ(G u2 I , e)) w e =
w(e, G u1 I , G u2 I )

.

(9) We can now define a lower bound LB and an upper bound UB for the IAS measure based on the following operators that are defined for any context c ∈ D E and for n ∈ N:

-m(G c E , n) = Lowest e∈G c E ({w e × α(e) s. t. e ∈ G c E }, n) returns the set of the n distinct records e from G c
E having the lowest values of w e × α(e).

-

M(G c E , n) = Highest e∈G c E ({w e × α(e) s. t. e ∈ G c E }, n) returns the set of the n distinct records e from G c
E having the highest values of w e × α(e).

-

mw(G c E , n) = Lowest e∈G c E ({w e s. t. e ∈ G c E }, n) returns the set of the n distinct records e from G c
E having the lowest values of w e .

-

Mw(G c E , n) = Highest e∈G c E ({w e s. t. e ∈ G c E }, n) returns the set of the n distinct records e from G c
E having the highest values of w e .

Proposition 1 (Lower bound LB for IAS) we define function LB as:

LB(G c E , G u1 I , G u2 I ) = 󰁓 e∈m(G c E ,σ E ) w e × α(e) 󰁓 e∈Mw(G c E ,σ E ) w e . ( 10
)
For any context c (corresponding to a subgroup G c E ), LB provides a lower bound for IAS w.r.t. contexts with σ E a minimum context support threshold:

∀c, d ∈ D E . c ⊑ d ⇒ LB(G c E , G u1 I , G u2 I ) ≤ IAS(G d E , G u1 I , G u2 I ).
Proposition 2 (Upper bound UB for IAS) we define function UB as:

UB(G c E , G u1 I , G u2 I ) = 󰁓 e∈M(G c E ,σ E ) w e × α(e) 󰁓 e∈mw(G c E ,σ E ) w e . ( 11
)
For any context c, UB provides an upper bound for IAS w.r.t. contexts. i.e.

∀c, d ∈ D E . c ⊑ d ⇒ IAS(G d E , G u1 I , G u2 I ) ≤ UB(G c E , G u1 I , G u2 I ).
Now that both the lower bound and the upper bound of IAS are defined w.r.t. contexts, we define the optimistic estimates corresponding to ϕ consent and ϕ dissent . The proofs of the propositions are given in Appendix A.

Optimistic Estimates for Quality Measures

Proposition 3 (Optimistic estimate for ϕ consent and ϕ dissent ) oe consent (resp. oe dissent ) is an optimistic estimate for ϕ consent (resp. ϕ dissent ) with:

oe consent (G c E , G u1 I , G u2 I ) = max(UB(G c E , G u1 I , G u2 I ) -IAS(G E , G u1 I , G u2 I ), 0). (12) oe dissent (G c E , G u1 I , G u2 I ) = max(IAS(G E , G u1 I , G u2 I ) -LB(G c E , G u1 I , G u2 I ), 0). ( 13
)
The two defined optimistic estimates are tights if IAS is a simple average.

Proposition 4 If ∀({e}, G u1 I , G u2 I ) ⊆ G E × G I × G I : w(e, G u1 I , G u2 I ) = 1, oe consent (oe dissent ) is a tight optimistic estimate for ϕ consent (ϕ dissent ).

Algorithm DEBuNk

DEBuNk is a Branch-and-Bound algorithm which returns the complete set of patterns as specified in the problem definition (Section 2). DEBuNk follows the same guidelines given in Algorithm PseudoDEBuNk (see Algorithm 1). For an efficient exploration, it exploits the defined closure operator and optimistic estimates. Relying on algorithm EnumCC, DEBuNk starts by generating the couples of confronted groups of individuals that are large enough w.r.t. σ I (lines 2-3). Then it computes the usual agreement observed between these two groups of individuals when considering all entities in G E (line 4). Next, the context search space is explored to generate valid contexts c (line 5). Subsequently, the optimistic estimate oe is evaluated and the context sub search space is pruned if oe is lower than σ ϕ (lines 7-8). Otherwise, the contextual inter-group agreement is computed and the quality measure is calculated (lines 9-10). If the pattern quality exceeds σ ϕ , two scenarios are possible. Either the current pattern set P already contains a more general pattern, or it does not. In the former case, the pattern is discarded. In the latter, the newly generated pattern is added to pattern set P while removing all previously generated patterns whose extents are included in the extent of p (lines 11-14). Since the current pattern quality exceeds the threshold and all the remaining patterns in the current context sub search space have their extents included in the extent of the current one, the sub search space is pruned (line 15). Eventually, in the case that the quality measure is symmetric w.r.t. u 1 and u 2 (i.e.

∀u 1 , u 2 ∈ D 2 I , ϕ(c, u 1 , u 2 ) = ϕ(c, u 2 , u 1 )
) there is no need to evaluate both qualities. It is therefore possible to prune the sub search space of the couple descriptions (u 1 , u 2 ) whenever u 1 = u 2 (lines [START_REF] Boley | Listing closed sets of strongly accessible set systems with applications to data mining[END_REF][17].

DEBuNk and DSC algorithm [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF] differ on several levels. First, DEBuNk overcomes the lack of diversity of results provided by DSC which was designed to discover the top-k solutions. The proposed algorithm discards all patterns for which a generalization w.r.t. extents is already a solution. Second, DEBuNk handles a wider range of bounded quality measures (i.e. weighted mean IAS) in contrast to DSC algorithm. Finally, DSC requires the prior definition of an aggregation level which makes it difficult to use and interpret. DEBuNk overcomes this issue by reducing the number of input parameters and integrating relevancy checks between patterns. Hence, it requires less effort from the end-user both in terms of setting the parameters, and in terms of interpreting the quality of the patterns. σ E (resp. σ I ) minimum support threshold of a context (resp. group); ϕ the quality measure; σϕ quality threshold on the quality. Output: P the set of exceptional (dis)agreement patterns. DEBuNk returns the exact solutions according to the problem definition. Although it relies on the enumeration of closed descriptions and pruning techniques, such an exploration may take a considerable time depending on the size and the complexity (i.e. attributes types) of the behavioral data. To address this concern, we devise a (dis)agreement pattern sampling approach called Quick-DEBuNk. It enables instant mining of (dis)agreement patterns by yielding approximate solutions that improve over time. Quick-DEBuNk follows almost the same guidelines given in Algorithm PseudoDEBuNk (see Algorithm 1), while Quick-DEBuNk adopt a sampling strategy instead of enumerating candidate patterns (Ingredient 1), it uses the same ingredients to evaluate the quality of patterns (Ingredient 2) and to prune unpromising areas of the search space (Ingredient 3). To sample the candidate patterns, Quick-DEBuNk relies on two major steps as depicted in Fig. 4:

1 P ← {} 2 foreach (u1, G u 1 I , cont u1) ∈ EnumCC(G I , * , σ I , 0, True) do 3 foreach (u2, G u 2 I , cont u2) ∈EnumCC(G I , * , σ I , 0, True) do 4 IAS ref ← IAS( * , u1, u2) 5 foreach (c, G E , cont c) ∈ EnumCC(G c E , * , σ E , 0, True) do 6 if oeϕ(c, u1, u2) < σϕ then
Frequency-Based Sampling (Step 1). A (dis)agreement pattern p ∈ P is drawn with a probability proportional to the size of its extent (i.e.

|ext(p = (c, u 1 , u 2 ))| = |G c E | × |G u1 I | × |G u2 I |).
The key insight is to provide a greater chance to patterns supported by larger groups and contexts which are less likely to be discarded by more general ones generated by future iterations. This technique is inspired by the direct frequency-based sampling algorithm proposed in [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF] which considers only Boolean attributed datasets. Here, this method is extended to handle more complex data with HMT, categorical and numerical attributes. Random Walk on Contexts (Step 2). Starting from a context obtained in step 1, a random walk traverses the search tree corresponding to the contexts description space D E . We introduce some bias to fully take ad-

↓ d = {d ′ ∈ D s.t. d ′ ⊑ d}. Since D 11 = D 1 × D 2 × ... × D m , it follows that: ↓d =↓〈r 1 , r 2 , ..., r m 〉 =↓ r 1 × ↓ r 2 × ...× ↓ r m ,
where ↓r j is the set of conditions less specific than (implied by) r j in the conditions space D j .

To achieve the property defined in Proposition 5, FBS performs two steps following the reasoning of [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF]:

Step 1.1 (line 1): FBS starts by drawing a record g from G with a probability proportional to the number of descriptions d ∈ D covering g (i.e: ↓ δ(g)).

To enable this, each record g is weighted by

w g = | ↓ δ(g)|. Knowing that δ(g) = 〈r g 1 , ..., r g m 〉, the weight w g = | ↓ δ(g)| = 󰁔 j∈[1,m] | ↓ r g j |
is the product of the numbers of conditions subsuming each r g j . The size of | ↓ r g j | depends on the type of the related attribute a j 12 .

Step 1.2 (line 2): Given g, the record returned from the first step and its corresponding description δ(g) = 〈r g 1 , ..., r g m 〉, FBS uniformly generates a description d from the set of descriptions covering g, that is ↓ δ(g). This can be done by uniformly drawing 12 conditions r j from ↓ r g j , hence returning a description d = 〈r 1 , ..., r m 〉. This comes from the fact that ∀j ∈ [1, m] :

P(r j ) = 1 |↓r g j | : Algorithm 4: FBS(G) Input: G a collection of records which may be G E or G I Output: a description d from D which may be D E or D I 1 draw g ∽ (wg = | ↓ δ(g)|) from G ⊲ Step 1.1 2 draw d ∽ uniform(↓ δ(g)) ⊲ Step 1.2 3 return d P(d|g) = 󰁜 j∈[1,m] P(r j ) = 1 󰁔 j∈[1,m] | ↓ r g j | = 1 | 󰁔 j∈[1,m] ↓ r g j | = 1 | ↓ δ(g)| . ( 14
)
FBS algorithm makes it possible to generate valid patterns p = (c, u 1 , u 2 ) from the pattern space P = D E × D I × D I . This is achieved in the first step of Quick-DEBuNk (lines 3-6 in Algorithm 6) by sampling two group descriptions u 1 , u 2 from D I and a context c from D E followed by assessing if the three descriptions satisfy the cardinalities constraints C (min. support thresholds).

Proposition 6 Given C, every valid pattern p is reachable by the first step of Quick-DEBuNk: ∀p ∈ P, p satistifies C ⇒ P(p) > 0 (Proofs in Appendix A)

Step 1 of Quick-DEBuNk does not favor the sampling of high quality patterns as it does not involve an exploitation phase. The random walk process on contexts used in Step 2 enables a smarter traversal of the search space while taking into account the devised quality measures and optimistic estimates. (u1, u2) couple of confronted group descriptions; σ E threshold on support; ϕ the quality measure; σϕ quality threshold. Output: yield valid patterns (c, u1, u2)

1 NtE ← {} 2 foreach d ∈ η(c) do 3 if |G d E | ≥ σ E and oeϕ(d, u1, u2) ≥ σϕ then 4 closure d ← δ(G d E ) 5 if ϕ(d, u1, u2) ≥ σϕ then 6 yield closure d 7 else 8 NtE ← NtE ∪ {d} 9 if NtE ∕ = ∅ then 10 draw next ∽ ϕ(next, u1, u2) from NtE 11 foreach cnext ∈ RWC(〈G I , G E , O, o〉, next, σ E , ϕ, σϕ, u1, u2) do 12 yield cnext
13 For the sake of brevity and clarity, the reader is referred to [START_REF] Belfodil | Identifying exceptional (dis)agreement between groups[END_REF] for technical details about the computation of | ↓ r g j | and the uniform sampling of conditions r j from ↓ r g j for each attribute a j .

appropriate, the closed description d is computed (line 4). The algorithm proceeds by evaluating the quality of the pattern (line 5). If the quality exceeds the threshold σ ϕ , the pattern is valid and is hence returned (line 6). Otherwise, the pattern is added to NtE (Neighbors to be Explored ) (line 8) as its related sub search space may contain interesting patterns (i.e oe ϕ (d, u 1 , u 2 ) ≥ σ ϕ ). The second step of RWC consists of selecting a neighbor from NtE to be explored with a probability proportional to its quality (lines 10 -12). This process is recursively repeated until a terminal node is reached (i.e. NtE = ∅).

5.3

(p) ≥ σ ϕ ⇒ ∃e ∈ G c E s.t. ϕ({e}, G u1 I , G u2 I ) ≥ σ ϕ (
since the quality measure is a weighted mean). If the context fulfills the cardinality constraint and its evaluated optimistic estimate is greater than the quality threshold (line 7), the algorithm then evaluates the quality of the sampled pattern (line 8). If this quality is greater than the threshold σ ϕ , the pattern is added to the resulting pattern set if and only if its extent is not included in an extent of an already found pattern (lines 9 -11). Otherwise, a random walk is launched starting from context c (line 13). This is done by relying on RWC. The algorithm continues by updating the resulting pattern set P with each pattern p new returned by RWC, as long as there is no pattern p old in P whose extent includes the extent of p new (lines 14 -16). Otherwise, RWC is interrupted (line 18). The process is repeated as long as the time budget allows.

I | ≥ σ I ∧ |G u 2 I | ≥ σ I then 6 c ← clo(FBS(G ≥σϕ E )) ⊲ G ≥σϕ E = {e ∈ G E s.t. ϕ({e}, G u 1 I , G u 2
I ) ≥ σϕ} 7 if |G c E | ≥ σ E ∧ oeϕ(c, u1, u2) ≥ σϕ then 8 if ϕ(c, u1, u2) ≥ σϕ then 9 pnew ← (c,

Empirical Study

In this section, we report on both quantitative and qualitative experiments over the implemented algorithms. For reproducibility purposes, source code (in Python) and data are made available on a companion page 13 .

Aims and Datasets

The experiments aim to answer the following questions:

-Do the algorithms provide interpretable patterns? -How effective is DEBuNk compared to state-of-the-art algorithms? -Are the closure operators and optimistic estimate based pruning, efficient? -How effective is HMT closed description enumeration? -Does DEBuNk scale w.r.t. different parameters? -How effective is Quick-DEBuNk at sampling patterns?

Most of the experiments were carried out on four real-world behavioral datasets whose main characteristics are given in Table 2. Each dataset involves entities and individuals described by an HMT (H) attribute together with categorical(C) and numerical(N) ones.

EPD8 14 features voting information of the eighth European Parliament about the 958 members who were elected in 2014 or after. The dataset records 2.7M tuples indicating the outcome (For, Against, Abstain) of a member voting during one of the 4161 sessions. Each session is described by its themes (H), a voting date (N) and the organizing committee (C). Individuals are described by a national party (C), a political group (C), an age group (C), a country(C) and additional information about countries (date of accession to the European Union (N) and currency (C)). To analyze (dis)agreement patterns in this dataset, we consider IAS voting which is defined by using θ majority and sim voting .

Movielens 15 is a movie review dataset [START_REF] Harper | The movielens datasets: History and context[END_REF] 1681 movies. A movie is characterized by its genres (H) and a release date (N), while individuals are described with demographic information such as age group (C), gender (C) and occupation (C). To handle the numerical outcomes, we use the measure IAS rating which relies on θ wavg and sim rating .

Yelp 16 is a social network dataset featuring individuals who rate (scores ranging from 1 to 5) places (stores, restaurants, clinics) characterized by some categories (H) and a state (C). The dataset originally contains 1M users. We preprocessed the dataset to constitute 18 groups of individuals based on the size of their friends network (C), their seniority (C) in the platform and their account type (e.g., elites or not) (C). We also use IAS rating measure in this dataset.

Openmedic 17 is a drug consumption monitoring dataset that has been recently made available by Ameli 18 . This dataset inventories the number of drug boxes (described by their Anatomical Therapeutic Chemical (ATC) Classification 19 (H)) yearly administered to individuals (from 2014 to 2016). Individuals are described with demographic information such as age (C), gender (C) and region (C). We further discuss an adapted IAS measure.

Comparing the size and the complexity of these datasets is difficult because of the heterogeneity of the attributes. In particular, the hierarchies of the HMT 18 Ameli -France National Health Insurance and Social Security Organization 19 The Anatomical Therapeutic Chemical classification system classifies therapeutic drugs according to the organ or system on which they act and their chemical, pharmaco-logical and therapeutic propertieshttps://www.whocc.no/atc/structure_and_principles/, last access on October 18, 2019.

attributes are very different, as well as the range of the numerical ones. To enable a fair comparison, we employ a conceptual scaling [START_REF] Ganter | Formal Concept Analysis -Mathematical Foundations[END_REF]. The attributes are "projected" on a set of items by transforming each one to a Boolean representation. Each possible value of a categorical attribute provides a single item (e.g., gender gives male, f emale and unknown). The items corresponding to an HMT attribute are all the nodes of the tag tree (T ). Each numerical attribute is transformed to an itemset via interordinal scaling (Kaytoue et al, 2011). To a given set of values

[v 1 , v 2 , ...v n ], we associate 2n items {≤ v 1 , ≤ v 2 , ... ≤ v n , ≥ v 1 , ≥ v 2 , ... ≥ v n }.

Qualitative Results

First, we focus on illustrating patterns discovered by DEBuNk. To this end, we report three real world case studies: (i) In collaborative rating platforms (Yelp, Movielens), we study the affinities between groups of users with regard to their expressed ratings. (ii) In a voting system (European Parliament Dataset), we show how the voting behavior of parlementarians can provide interesting insights about the cohesion and the polarization between groups of parliamentarians in different contexts. Such information can be valuable for journalists and political analysts. (iii) We give example patterns reporting substantial differences in medicine consumption behavior between groups. Such results can be leveraged by epidemiologists to study comparative prevalence of sicknesses among subpopulations.

Study of Collaborative Rating Data

Table 4 describes some patterns returned by DEBuNk on the Movielens dataset when looking for contexts that lead to a disagreement between groups of individuals labeled by their professional occupations. The first pattern describes that, while students and health professionals agree 74% of the time, they tend to disagree for horror and comedy-like movies released between 1986 and 1994 (e.g., Evil Dead II, Braindead ). Figure 5 illustrates the usual and the contextual rating distribution of each groups. We observe from this rating distributions, that the students like the movies highlighted by the pattern, whereas the healthcare professionals dislike them. 4.

In Table 5, we present some results provided by DEBuNk over Yelp dataset. The groups of individuals are labeled by the size of their friend network and '5 Comedy', '8 Drama'] [1987, 1993] 0.73 -0.3 their seniority in the Yelp platform. Notice that additional demographic data about users are missing. This prevents DEBuNk from obtaining concrete results similar to the ones obtained in Movielens. The resulting patterns highlight the places for which groups of individuals have divergent opinions. For example, pattern 2 states that Senior Yelp users (registered in Yelp before 2010) having a friend network of medium size (less than 100 friends) disagree with users registered in Yelp before 2015 having a large friend network (more than 100 friends) on Internal Medicines Clinics in Nevada (e.g., Las Vegas Urgent Care), contrary to the usual, where these two groups roughly share the same opinions about places (81% of the time).

(c, u1, u2) |G c E | |G u 1 I | |G u 2 I | o(i, e) ϕ dissent 1

Analysis of the Voting Behavior in the European Parliament Dataset

Table 6 reports patterns obtained by DEBuNk where the aim is to find contexts (subsets of voting sessions) that lead groups of parliamentarians (labeled by their countries and their corresponding date of accession to the European Union) to strong disagreement compared to the usual observed agreement. Note that we choose carefully σ E ≥ 25 to reach subgroups of the third level of the themes hierarchy which on average contain ∽ 25 voting sessions. Such analysis can be valuable to political analysts and journalists as it enables to uncover subjects/thematics of votes on which countries have divergent opinions. For instance, the second pattern in Table 6 illustrated in Figure 6, states that the voting sessions about theme 4.15.05 (Industrial Restructuring, job losses, EGF, e.g., Mobilization of the European Globalization Adjustment Fund: redundancies in aircraft repair and installation services in Ireland) lead to strong disagreements between parliamentarians from the United Kingdom and their peers. In Figure 6, we provide a visualization of this pattern through a similarity matrix where each cell represents the similarity between two countries. This can be seen as a post-processing step where the end-user chooses to augment the pattern with more related information (similarities between other countries). Such visualization brings more context to the pattern. While the second pattern conveys that British parliamentarians are in strong disagreement with ([1973, 1973] [1958,1958] Italy) vs. ([1981, 2013]

(c, u1, u2) |G c E | |G u 1 I | |G u 2 I | o(i, e) ϕ dissent 1
E | = 1, |A I | = 2, σ E = 25, σ I = 1 and σϕ = 0.5 using ϕ dissent ).
their peers, the visualization goes beyond by reporting that all other countries formed a coalition against the voting decision of British parlementarians. The algorithms elaborated in this work also allow to discover patterns exhibiting consensual subjects, thanks to the quality measure ϕ consent . Additional experiments are reported in the technical report [START_REF] Belfodil | Identifying exceptional (dis)agreement between groups[END_REF] illustrating such patterns. Moreover, as part of a collaboration with political journalists, we provide an online tool20 , dubbed ANCORE that makes it possible to analyze European parliament voting sessions. 6. The left matrix depicts the agreement observed in general between countries when considering all voting sessions. The right matrix corresponds to the inter country agreement for the context of pattern 2.

Illnesses Prevalence on the Basis of Medicine Consumption

One interesting analysis task to be carried out on the Openmedic dataset is to look for subgroups of drugs where the ratio of intakes between two groups of individuals is substantially different than the one usually observed. For instance, we find that while Females takes 1.32× more drugs than Males in overall terms, this ratio increases up to 5× when considering drugs prescribed for Hyperthyroidism (see Pattern 3 in Table 7). These results are similar to those reported in an epidemiology study by [START_REF] Wang | The epidemiology of thyroid disease and implications for screening[END_REF]. Such task can provide some insight regarding illness prevalence for particular groups of individuals. In the behavioral dataset Openmedic, the outcomes expressed by individuals are depicted by numerical values reporting the count of medicine boxes. As we are interested in characterizing the agreement by the consumption ratio, we instantiate IAS as follows:

IAS ratio (c, u 1 , u 2 ) = 󰁓 e∈G c E θ avg (G u1 I , e) 󰁓 e∈G c E θ avg (G u2 I , e) . ( 15
)
This ratio falls under the definition of IAS considered in Definition 9 as it can be expressed as a weighted average:

IAS ratio (c, u 1 , u 2 ) = 󰁓 e∈G c E w(e, G u 1 I , G u 2 I ) × sim ratio (θavg(G u 1 I , e), θavg(G u 2 I , e)) 󰁓 e∈G c E w(e, G u 1 I , G u 2 I ) with w(e, G u 1 I , G u 2 I ) = θavg(G u 2
I , e) and sim ratio (x, y) = x y .

(16)

In order to provide interpretable patterns according to the aim of the study, we define an adapted quality measure ϕ ratio as:

ϕ ratio (p) = IAS ratio (p) IAS ratio (p * ) with p = (c, u 1 , u 2 ) ∈ P and p * = ( * , u 1 , u 2 ). ( 17
)
Drug boxes are labeled by tags in the ATC classification system. We aim at leveraging the medical consumption differences between groups of individuals to investigate the comparative prevalence21 of illnesses between gender groups. Table 7 shows some patterns discovered by DEBuNk on Openmedic. Note that we carefully choose σ E ≥ 10 to reach subgroups of drugs of the fifth level of ATC tree which on average contains ∽ 10 drugs. Pattern 4 states that, for drugs prescribed for Gout22 , men consume 3× more drugs than women, whereas in overall terms, men consume 0.76× less drugs than women. Similar results were reported by an epidemiology study of Gout in [START_REF] Roddy | Epidemiology of gout[END_REF] giving an incidence of gout per 1,000 person-years of 1.4 in women and 4.0 in men. Patterns 3 and 4, depicted in Figure 7, report details on the differences between the two gender groups in terms of population size and number of drugs consumed both in overall and in the context highlighted by the pattern.

(c, u1, u2) |G c E | |G u 1 I | |G u 2 I | o(i,
| = 1, |A I | = 1
, σ E = 10, σ I = 1 and σϕ = 3.5 using ϕ ratio .

Comparison to state-of-the-art techniques

We have investigated the ability of classical SD/EMM techniques to tackle the problem of discovering exceptional (dis)agreement among groups of individuals. To this end, we have considered three appropriate SD/EMM adaptations 23 and tested them on synthetic datasets with ground truth. No existing quality measure (in classical SD) or model (in classical EMM) makes it possible to uncover exactly the (dis)agreement patterns, and these experiments obviously supported this observation (for more details, please refer to the technical report [START_REF] Belfodil | Identifying exceptional (dis)agreement between groups[END_REF]). This is due to the fact that SD and EMM techniques are usually tailored to tackle a specific mining task. Therefore and for the interest of brevity, we report here only comparative experiments against our first attempt [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF] implemented by DSC. DSC aims at discovering top-k patterns that elucidate exceptional (dis)agreement between groups of individuals. In addition, for a sufficiently large k, DSC solves the core problem tackled in this paper limited to the two first conditions (i.e., validity and maximality). Note that, we disable the aggregation dimension parameter for DSC to obtain comparable pattern sets. To compare between DEBuNk and DSC, we designed experiments to answer to the two following questions: Q1. How concise is the patterns set provided by DEBuNk compared to the one provided by DSC? Q2. How diverse is the pattern set, limited to k patterns, provided by DEBuNk compared to the one provided by DSC?

In order to answer (Q1), we evaluate the number of patterns returned by DEBuNk and DSC when looking for complete pattern set P (i.e., k sufficiently 23 Since common SD techniques require flat representations of the underlying dataset augmented with a target attribute, we have proposed two adaptations: SD-Majority for discovering (dis)agreement with the majority and SD-Cartesian for discovering (dis)agreement between two groups on the cartesian product G E × G I × G I . In both of the aformentioned adaptations, the target is equal to 1 if there is an agreement, 0 else. Experiments are performed using PySubgroup [START_REF] Lemmerich | pysubgroup: Easy-to-use subgroup discovery in python[END_REF] while utilizing the precision gain [START_REF] Fürnkranz | Foundations of Rule Learning[END_REF] as a quality measure. Moreover, to take into account the usual agreement between groups, we adapt Exceptional Subgraph Mining [START_REF] Kaytoue | Exceptional contextual subgraph mining[END_REF] to discover contextual (dis)agreement in subgraphs representing individuals group pairs. large for DSC). For this, we run both methods on EPD8 with various24 quality thresholds σ ϕ and descriptive attributes A E , A I . Figure 8 reports the results of these experiments. Results demonstrate that DEBuNk considerably reduces the desired pattern set while ensuring that each pattern returned by DSC is represented by a pattern returned by DEBuNk (according to the problem definition). On average, DSC returns 38 times more patterns than DEBuNk. Moreover, DEBuNk achieves better performance than DSC in terms of run time . This is explained by (i) the model simplification which reduces the complexity of computing the interestingness measure and (ii) the pruning property implemented by DEBuNk supported by condition (3) of the problem definition. So far, we compared DEBuNk against DSC when looking for the complete pattern set. Experiments (Q1) demonstrated the fact that in such a setting DSC returns an overwhelmingly large result set. To tackle this problem, DSC implements a top-k algorithm to control the size of the returned pattern set. Of course, the main drawback of using a top-k algorithm is the lack of diversity even when redundancy is avoided by closure operators. This lack of diversity is induced by the fact that, most likely, the patterns observing the highest qualities are condensed in small region of the dataset.

To fairly evaluate the diversity of patterns returned by both DSC and DE-BuNk (Q2), we run both algorithms for several parameters 25 and compare the size of the datasets regions covered by both returned pattern sets. This quantity can be captured by the number of outcomes covered by a result set, that is

|o[P k ]| = |{(i, e) ∈ G I × G E s.t. o(i, e
) is expressed}| with P k an ar- bitrary pattern set containing k patterns. For a fair comparison, we compare

|o[P k DSC ]| (top-k patterns) against |o[P k DEBuNk ]|.
To obtain the latter quantity, we run DEBuNk so as to obtain the complete pattern set P DEBuNk . Next, we draw 100 k-sized samples drawn uniformly from the obtained P DEBuNk and then compute the average |o[P k DEBuNk ]|. It is worth mentioning that comparison can be made also by taking the top-k patterns P DEBuNk rather than an arbitrary k-sized sample. We decided to study the latter scenario, since the philosophy of DEBuNk is to retrieve the complete patterns set summarizing exceptional (dis)agreement in an underlying behavioral dataset.

Results are reported in Figure 9. Clearly, DEBuNk's k-sized pattern set covers larger (and different) parts of the dataset compared to DSC's top-k pattern set. We observe that DEBuNk surpasses DSC by one order of magnitude (×12.5 in average) when comparing the portions of the dataset covered by their respective k-sized pattern set. Simply put, when the pattern set related to DEBuNk covers 10% of the dataset, DSC patterns cover less than 1% of the underlying dataset records.

6.4 Performance study

Efficiency of closure operators and optimistic estimates

To evaluate the efficiency of closure operators and optimistic estimates, we compare DEBuNk against two baseline algorithms. The first baseline, named Baseline, is obtained by disabling both closure operators and the pruning properties supported by the defined optimistic estimates. Thus, Baseline only pushes the anti-monotonic constraints (i.e., the set of cardinality constraints C). The second baseline, Baseline+Closed, is proposed to study more precisely the efficiency of the optimistic estimates. Thus, it is obtained by disabling the optimistic estimate based pruning. In these experiments, we interrupt a method if its execution time exceeds 10 hours. Figure 10 reports the execution time and the number of candidate patterns processed by each of the three methods when varying the size of the dataset w.r.t. both the number of records and the size of the descriptions space.

Experiments give evidence that the closure operator and the canonicity tests performed by EnumCC are effective as they drastically reduce the number of evaluated patterns. Additionally, DEBuNk is about one order of magnitude faster than the Baseline+Closed algorithm, thanks to the optimistic estimate-based pruning. This especially happens when the IAS measure is a simple average, which is the case of the IAS measure used for EPD8, Yelp and Movielens. This is explained by the fact that the corresponding optimistic estimate is tight. Similar observations hold for the experiments carried on Yelp and Movielens datasets, in contrast, experiments run on Openmedic exhibit slightly different performance profiles. For more details, please refer to the technical report [START_REF] Belfodil | Identifying exceptional (dis)agreement between groups[END_REF].

Efficiency of HMT closed descriptions vs. closed itemsets enumeration

In order to evaluate the performance of the closed descriptions enumeration in the presence of a taxonomy linking the tags (items), we study the behavior of DEBuNk (i.e. execution time and the number of explored patterns) both with and without leveraging the hierarchy between items. The latter can be done by scaling the HMT values (as illustrated in Fig. 2) using a vector representation for each tagged record. Experiments are carried out on EPD8 and Yelp datasets whose entities are characterized by a hierarchy of 347 tags and 1175 tags respectively. To vary the number of items/tags constituting the hierarchy, we remove tags from the tree in a bottom-up fashion until the desired number of tags/items is reached, followed by replacing the HMT values of each entity by the set of ascendants tags remaining in the obtained tree. Experiments reported in Figure 11 demonstrate that taking into account the hierarchy of tags significantly improves the performance of DEBuNk (5× faster). This results from the fact that, in contrast to itemsets enumeration, HMT descriptions enumeration exploits the structure of the hierarchy and therefore avoids considering chain descriptions (e.g., {1, 1.10.40}). Note that the bars depict the number of patterns that are visited by EnumCC used in DEBuNk to generate the closed patterns. Obviously, the HMT and Itemset closed description enumeration return the same number of closed patterns. We choose to represent the number of visited patterns rather than the number of closed patterns to illustrate the differences between the HMT and Itemset enumeration in terms of the size of the explored search space.

Performance study of DEBuNk

We now focus on the study of DEBuNk according to the size of the description spaces (D E , D I ), the support thresholds, the quality threshold and the quality measures. To study the behavior of DEBuNk according to the size of the description spaces, we choose to vary the number of items resulting from projecting the attributes values of each record (entity/individual) on their corresponding vector representation. To this end, we select values from each attribute according to the size of its corresponding domain so as to obtain the required number of items. We follow the same approach as in the experiments reported in Figure 11 to select the required number of tags for an HMT attribute. Numerical attributes domains are discretized according to the required number of items. Subsets of values of categorical attributes are regrouped under single categories in order to obtain the desired number of values. Figure 12 reports the behavior of DEBuNk on EPD8. Clearly, the number of evaluated candidates and the execution time increase with regards to the size of description spaces D I and D E . These experiments confirm that pushing monotonic constraints (i.e. supports threshold σ E , σ I ) drastically improves the efficiency of DEBuNk. Finally, a higher threshold on the quality σ ϕ leads to an important reduction of the number of visited patterns and therefore to a better execution time. This demonstrates the effectiveness of the pruning properties enabled by the use of optimistic estimates. We also notice that ϕ consent performs slightly better than ϕ dissent . This effect arises mainly from the fact that, in the EU Parliament dataset, the overall observed agreement between groups of individuals is rather consensual. The same conclusions can be drawn as well from experiments performed on Movielens, Yelp and Openmedic. For more details, see the technical report [START_REF] Belfodil | Identifying exceptional (dis)agreement between groups[END_REF]).

Quick-DEBuNk vs. DEBuNk

To evaluate the efficiency of Quick-DEBuNk, we compare it against the exhaustive search algorithm DEBuNk over different time budgets. To objectively measure how well Quick-DEBuNk results approximates DEBuNk results, let us first define a similarity measure sim P between two patterns p = (c, u 1 , u 2 ) and p ′ = (c ′ , u ′ 1 , u ′ 2 ) from P. It captures to what extent two patterns covers the same context and groups and relies on a Jaccard Index (J in what follows):

sim P (p, p ′ ) = 󰁵 J(G c E , G c ′ E ) × 1 2 . 󰀓 J(G u1 I , G u ′ 1 I ) + J(G u2 I , G u ′ 2 I ) 󰀔 with J(G, G ′ ) = |G ∩ G ′ | |G ∪ G ′ | . (18)
Note that, the quantity (J(G u1 I , G

u ′ 1 I ) + J(G u2 I , G u ′ 2 I
)) is replaced by the following measure if the quality measure ϕ is symmetric:

max(J(G u1 I , G u ′ 1 I ) + J(G u2 I , G u ′ 2 I ), J(G u1 I , G u ′ 2 I ) + J(G u2 I , G u ′ 1 I )) (19)
For comparing two pattern sets P , P ′ returned by respectively DEBuNk and Quick-DEBuNk, we use precision and recall defined as follows.

A similar measure to recall has been proposed by [START_REF] Bosc | Anytime discovery of a diverse set of patterns with monte carlo tree search[END_REF] to evaluate the ability of their algorithm to retrieve ground-truth patterns. We extend this measure with the precision to evaluate not only that all the patterns returned by DEBuNk have been retrieved by Quick-DEBuNk (i.e. recall=1) but also the conciseness of the returned set (i.e. precision=1 if and only if all returned patterns by Quick-DEBuNk are actually present in the ground-truth result set, namely the returned patterns by DEBuNk).

Figures 13a, 14a and 15a report the comparative study between DEBuNk and Quick-DEBuNk carried out on respectively EPD8, Movielens and Yelp. We notice that in all situations, Quick-DEBuNk is able to promptly return high quality patterns. Interestingly, some differences can be observed between datasets. Quick-DEBuNk is less efficient on the Yelp dataset. We argue that this is due to the fact that the corresponding context search space is much larger than the three other behavioral datasets (see Table 2) which might impede random walk step RWC for finding high quality patterns.

We also investigate the empirical distribution from which the patterns are sampled when using Quick-DEBuNk. This requires the true distribution of the qualities of valid patterns in the corresponding datasets. To this end, we run DEBuNk by disabling the generality condition (see Problem definition). This makes it possible to identify all interesting (dis)agreement patterns in the dataset. In these experiments, we choose an arbitrary threshold set to σ ϕ = 0.1. Similarly, we run Quick-DEBuNk so as to obtain a sufficiently large pattern set, and calculate the sampling distribution from the retrieved patterns' qualities. We observe from the empirical distributions depicted in Figures 13b, 14b and 15b that Quick-DEBuNk rewards high quality patterns by giving them a better chance to be sampled. Finally, to evaluate the importance of the RWC (Random Walk on Contexts) step in Quick-DEBuNk, we perform the same experiments with the same time budgets with the RWC step disabled. This configuration, Quick-DEBuNk without RWC returned only 3 472, 389 and 120 valid patterns compared to 408 610, 64 198 and 75 398 valid patterns when carried out on, respectively, EPD8, Movielens and Yelp. In average, Quick-DEBuNk without RWC retrieved 20× fewer valid patterns than the original Quick-DEBuNk. This clearly indicates that RWC improves the performance of Quick-DEBuNk. This stems from the fact that when the first step (FBS step) generates a pattern, most of the time the pattern is not of a sufficient quality. RWC tackles this issue by locally searching for interesting patterns, starting from the generated pattern.

Discussion

DEBuNk scales well w.r.t. the size of the search space corresponding to the entities collection thanks to the defined optimistic estimates which enable to prune unpromising parts of the search space. However, DEBuNk does not scale according to the size of the description spaces related to the individuals. This limits its application when behavioral datasets have a large number of individuals described with many attributes. This is due to the need of taking into account the usual inter-group agreement in the interestingness measures. As a consequence, it is notoriously difficult to define an optimistic estimate which not only works on the entities related search space, but also on the one corresponding to the confronted couples of groups of individuals. This should be the scope of future research, starting with definition of bounds on the usual agreement quantity. Algorithm Quick-DEBuNk partially addresses this scalability issue by sampling the couples of groups directly from the patterns space rather than starting from the search tree root. Interestingly, the experiments demonstrated that Quick-DEBuNk makes it possible to retrieve most of the interesting patterns in a relatively small amount of time (i.e. compared to what returns the exhaustive search algorithm DEBuNk and the ground truth in artificial data). This is particularly observed for EPD8 dataset involving the largest descriptions space D I × D I , hence empirically demonstrating its interest. Nevertheless, Quick-DEBuNk does not have theoretical guarantees on the distribution of the sampled patterns (we only proved that all valid patterns are reachable and are generated proportionally to their size). This shortcoming is due to two reasons. On the one hand, the three-set format of the patterns makes them challenging to be sampled proportionally to their interestingness measure since the value is computed only when the context is known (no information is available before the instantiation of the two groups).

On the other hand, quality measures that are expressed as average functions are complex to apprehend under direct pattern sampling framework. Dealing with this two issues is required to obtain theoretical guarantees.

To avoid misleading interpretations, it is important to be aware of the data sparsity. To this end, the proposed approaches enable to discard some patterns that involve too small subset of entities on which the two confronted groups haven't expressed enough outcomes. Moreover, the strength of the claim related to the pattern should be assessed according not only to the data sparsity but also to the representativeness of the two subpopulation of interest (e.g., the claims drawn from the EU parliament votes are usually consistent even though the data are fairly sparse).

Related Work

Subgroup Discovery and Exceptional Model Mining. Scientists have always seen Exploratory Data Analysis (EDA) as an important research area since its introduction [START_REF] Tukey | Exploratory data analysis. Addison-Wesley series in behavioral science : quantitative methods[END_REF]. Among the various EDA techniques that aim to maximize insight into datasets and uncover underlying structures, Subgroup Discovery (SD) [START_REF] Klösgen | Explora: A multipattern and multistrategy discovery assistant[END_REF][START_REF] Wrobel | An algorithm for multi-relational discovery of subgroups[END_REF][START_REF] Atzmueller | Subgroup discovery[END_REF][START_REF] Herrera | An overview on subgroup discovery: foundations and applications[END_REF] is a generic data mining task concerned with finding regions in the data that stand out with respect to a given target. Many other data mining tasks have similar goals as SD, e.g., emerging patterns [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF], significant rules [START_REF] Terada | Statistical significance of combinatorial regulations[END_REF], contrast sets [START_REF] Bay | Detecting group differences: Mining contrast sets[END_REF] or classification association rules [START_REF] Liu | Integrating classification and association rule mining[END_REF]. However, among these different tasks, SD is known as the most generic one, especially SD is agnostic of the data and the pattern domain. For instance, subgroups can be defined with a conjunction of conditions on symbolic [START_REF] Lavrac | Subgroup discovery with CN2-SD[END_REF] or numeric attributes [START_REF] Grosskreutz | On subgroup discovery in numerical domains[END_REF][START_REF] Atzmüller | Sd-map -A fast algorithm for exhaustive subgroup discovery[END_REF] as well as sequences [START_REF] Grosskreutz | A relevance criterion for sequential patterns[END_REF]. Furthermore, the single target can be discrete or numeric [START_REF] Lemmerich | Fast exhaustive subgroup discovery with numerical target concepts[END_REF]. Exceptional Model Mining (EMM) [START_REF] Leman | Exceptional model mining. In: Machine Learning and Knowledge Discovery in Databases[END_REF], while sharing exactly the same exploration space (i.e., the description space), extends SD by offering the possibility to handle complex targets, e.g., several discrete attributes [START_REF] Van Leeuwen | Diverse subgroup set discovery[END_REF][START_REF] Duivesteijn | Subgroup discovery meets bayesian networks -an exceptional model mining approach[END_REF][START_REF] Duivesteijn | Exceptional model miningsupervised descriptive local pattern mining with complex target concepts[END_REF], graphs [START_REF] Kaytoue | Exceptional contextual subgraph mining[END_REF][START_REF] Bendimerad | Unsupervised exceptional attributed sub-graph mining in urban data[END_REF][START_REF] Bendimerad | Contextual subgraph discovery with mobility models[END_REF], two numeric targets [START_REF] Downar | Exceptionally monotone models-the rank correlation model class for exceptional model mining[END_REF] and preferences [START_REF] De Sá | Exceptional preferences mining[END_REF][START_REF] De Sá | Discovering a taste for the unusual: exceptional models for preference mining[END_REF]. Our method is rooted in the SD/EMM framework. Nevertheless, the problem we tackle cannot be directly addressed with an instance of SD/EMM because a target space is provided instead of explicit targets. As a consequence, the discovery of (dis)agreement patterns with a SD/EMM instance would consist in performing a SD discovery algorithm per pair of confronted groups of individuals, which is not feasible in practice due to the exponential number of possible pairs of groups. Dynamic EMM (i.e., EMM with a non-fixed model) has been recently investigated for different aims. [START_REF] Bosc | Local subgroup discovery for eliciting and understanding new structure-odor relationships[END_REF] propose a method to handle multi-label data where the number of labels per record is much lower than the total number of labels which prevents the use of usual EMM model. Other dynamic EMM approaches aim to discover exceptional attributed sub-graphs [START_REF] Kaytoue | Exceptional contextual subgraph mining[END_REF][START_REF] Bendimerad | Unsupervised exceptional attributed sub-graph mining in urban data[END_REF][START_REF] Bendimerad | Contextual subgraph discovery with mobility models[END_REF]. The present paper, which is an extension of [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF], is the first attempt to discover (dis)agreement patterns with a method rooted in dynamic EMM. Our preliminary work [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF] is extended on many levels: (1) we provide an easier to use framework to discover exceptional (dis)agreement between groups which requires less parameter setting and interpretation effort by the end-user. ( 2) Our proposal enables to use a wider spectrum of interestingness measures that can be enriched by relying on the building blocks discussed in Section 3. (3) This work provides a more elaborate exhaustive search algorithm compared to the former one as discussed in Section 4 and (4) An alternative sampling approach Quick-DEBuNk is proposed. It enables instant mining of (dis)agreement patterns, which sets the ground for interactive pattern mining tools.

Rating Data Analysis. Behavioral data analysis has received a wide interest in the last two decades allowing the development of new services for consumers, citizens, companies and organizations. In [START_REF] Das | MRI: meaningful interpretations of collaborative ratings[END_REF], the problem of discovering meaningful ratings interpretation is introduced. It can be formalized as a SD problem, the authors' aim is to identify groups of users that substantially agree or disagree w.r.t. some given subsets of entities while using a mono-objective measure (ratings average). Extensions have been proposed to enable multi-objective groups identification thanks to more complex statistical measure (rating distribution) [START_REF] Amer-Yahia | Exploring rated datasets with rating maps[END_REF][START_REF] Omidvar-Tehrani | Multiobjective group discovery on the social web[END_REF]. This makes it possible to discover intra-group behavior patterns such as polarized and homogeneous opinions. The main differences with our work are: (i) these methods consider intra-group agreement only (no inter-group agreement) without taking into account the usual agreement observed between the individuals; (ii) the set of reviewees on which the study is performed is given in prior, in contrast to our SD/EMM based approach, which discovers relevant contexts by leveraging the reviewees dimension.

Voting Data Analysis. Similarly, the past two decades have witnessed an increasing emergence of Open Government Data 26 (OGD) promoting transparency and accountability in public institutions. Consequently, many re-searchers from different fields (e.g., information science, political and social sciences, data mining and machine learning) have studied such data [START_REF] Charalabidis | A taxonomy of open government data research areas and topics[END_REF]. For instance, [START_REF] Jakulin | Analyzing the us senate in 2003 : Similarities , networks , clusters and blocs[END_REF] uses hierarchical clustering and PCA to identify cohesion blocs and dissimilarity blocs of voters within the US Senate. Similar work was done on the Finnish [START_REF] Pajala | Parliamentary group and individual voting behavior in finnish parliament in year 2003 : A group cohesion and voting similarity analysis[END_REF], the Italian [START_REF] Amelio | Analyzing voting behavior in italian parliament: Group cohesion and evolution[END_REF] and the Swiss [START_REF] Etter | Mining democracy[END_REF] parliaments to study the polarization and cohesion between parliamentarians. Similarly, [START_REF] Grosskreutz | Subgroup discovery for election analysis: A case study in descriptive data mining[END_REF] investigate the voting behavior of citizens instead of politicians relying on SD. Our work goes further and supports the discovery of new insights in such data.

Outpatient Data Analysis. Monitoring the disease prevalence is an important task. Many researchers dedicated much effort to analyze the prevalence of diseases considering different sources of data. [START_REF] Orueta | Monitoring the prevalence of chronic conditions: which data should we use?[END_REF] highlight the importance of considering outpatient data (e.g., medical prescriptions) in such epidemiology studies. This motivates the analysis task proposed over Openmedic data. It provides an interesting additional tool in epidemiology surveillance applications by revealing substantial differences in medicine consumption between subpopulations.

Pattern Sampling Approaches. The discovery of the complete set of interesting patterns (e.g., frequent, discriminant) has two disadvantages that limit the use of such methods in practice. It is time consuming to compute the complete set of solutions. Furthermore, this set can be huge and non-manageable for a human expert. To overcome these limitations, many approaches that can effectively sample the pattern space for interesting patterns have been proposed for a decade. These methods address frequent or discriminant itemset mining tasks [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF][START_REF] Giacometti | Frequent pattern outlier detection without exhaustive mining[END_REF][START_REF] Li | Sampling frequent and minimal boolean patterns: theory and application in classification[END_REF][START_REF] Moens | Randomly sampling maximal itemsets[END_REF] offering some theoretical guarantees on the sampling quality or more generic ones [START_REF] Dzyuba | Flexible constrained sampling with guarantees for pattern mining[END_REF]Boley et al, 2010a;[START_REF] Hasan | Output space sampling for graph patterns[END_REF]. [START_REF] Dzyuba | Flexible constrained sampling with guarantees for pattern mining[END_REF] define the problem of sampling pattern sets and propose a method based on a SAT solver sampling solution. However, this approach only supports pattern languages that can be compactly represented by binary variables such as itemsets. It requires the discretization of numerical attributes. Authors in (Boley et al, 2010a;[START_REF] Hasan | Output space sampling for graph patterns[END_REF] use a MCMC (Monte-Carlo Markov-Chain) based algorithm to achieve sampling with guarantees according to a desired probability distribution. Despite the generic nature and the interesting guarantees that MCMC algorithms provide, it requires a number of steps that grows exponentially in the input size to generate a single pattern (Boley et al, 2010a). This may prevent the user to obtain instant results. The problem we are interested in has several specificities. First, the search space involves attributes of different types (i.e., numerical, symbolical, HMT attributes) which prevents us to use sampling techniques based on itemset language. Second, the quality measure is not considered in the state-of-the-art methods that mainly support frequency and discriminative measures [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF][START_REF] Boley | Linear space direct pattern sampling using coupling from the past[END_REF]. Finally, the method proposed in [START_REF] Moens | Instant exceptional model mining using weighted controlled pattern sampling[END_REF] for EMM is not suited to our problem since we have to simultaneously consider both description space and target space. Algorithm Quick-DEBuNk handles the specificity of the problem by combining an exploration step (i.e. direct sampling from the pattern space) and an exploitation step while taking profit of the quality measures properties (i.e. random walk step on contexts search space). However, we have no theoretical guarantee on the quality of the sampled (dis)agreement patterns.

Conclusion

In this paper, we have defined the problem of discovering exceptional (dis)agreement in behavioral data. The generic definition of behavioral data enables to encompass datasets featuring individuals and their outcomes on some entities whatever the application domain (e.g., ratings, votes, medicines consumption). The discovery of exceptional (dis)agreement patterns is rooted in SD/EMM with a novel pattern domain and associated quality measures. However, the targets are not specified and have to be enumerated in our framework. We have defined DEBuNk, a branch-and-bound algorithm which takes benefit from closure operators, properties of the underlying descriptions space (as for HMT attributes) and (tight) optimistic estimates to efficiently enumerate the patterns. Alternatively, we devised Quick-DEBuNk that samples the space of patterns instead of returning the complete set of (dis)agreement patterns. We have investigated several quality measures to assess inter-group agreement. The extensive experimental study demonstrates the efficiency of our algorithms as well as their ability to provide new insights in three casestudies: (i) the investigation of contexts that impact the inter-group agreement between parliamentarians, (ii) the characterization of affinities and contrasted opinions between reviewers in rating platforms and (iii) the study of prevalence of certain sicknesses that can be pointed out by high discrepancies between the medicine consumption rates of two subpopulations.

We believe that this work opens new directions for future research. This generic framework can be extended by paying a particular attention to the analysis of intra-group agreement within a group of individuals. It may support the discovery of contexts that divide a political group. This requires the definition and the integration of suited similarity measures into the IAS (Intergroup Agreement Similarity) measure. For instance, the cohesion of a political group can be assessed by the "agreement index" [START_REF] Hix | Power to the parties: cohesion and competition in the european parliament, 1979-2001[END_REF], which is an application-specific measure to the study the European parliament. More generic measures, such as Krippendorff's alpha coefficient [START_REF] Hayes | Answering the call for a standard reliability measure for coding data[END_REF], could also be investigated. While our method is able to analyze behavioral datasets with large collections of entities (e.g., Yelp), tackling large collections of individuals still remains challenging to ensure the scalability of both DEBuNk and Quick-DEBuNk. Indeed, the search space related to individuals does not have, according to our problem definition, properties that can be leveraged to prune unpromising parts of this search space. Another interesting future direction is to take into account the temporal dimension into the analysis of behavioral data. This can offer the opportunity to investigate how the relationship (e.g., inter-group agreement) between groups of individuals evolves through time. .

Symbol Definition

Proof (Lemma 1) Using the same notations of the lemma, we know that:

󰁓 n i=1 a i 󰁓 n i=1 b i - 󰁓 k i=1 a i 󰁓 k i=1 b i
is of the same sign of: Using the lemma hypotheses (orders between a i 's and b i 's), we have:

n 󰁛 i=k+1 a i ≥ (n -k) × a k , k 󰁛 i=1 b i ≥ k × b k , k 󰁛 i=1 a i ≤ k × a k , n 󰁛 i=k+1 b i ≤ (n -k) × b k .
Thus:

󰀳 󰁃 n 󰁛 i=k+1 a i 󰀴 󰁄 × 󰀣 k 󰁛 i=1 b i 󰀤 ≥ (n -k) × k × a k × b k , 󰀣 k 󰁛 i=1 a i 󰀤 × 󰀳 󰁃 n 󰁛 i=k+1 b i 󰀴 󰁄 ≤ (n -k) × k × a k × b k .
We ) .

Given that we.

G d E ⊆ G c E ,
Hence, from ( 23) and [START_REF] Harper | The movielens datasets: History and context[END_REF] we have LB(

G c E , G u 1 I , G u 2 I ) ≤ LB(G d E , G u 1 I , G u 2 I ) and pro- vided that LB(G d E , G u 1 I , G u 2 I ) ≤ IAS(G d E , G u 1 I , G u 2 I ) from (21), we have: ∀c, d ∈ D E , c ⊑ d ⇒ LB(G c E , G u 1 I , G u 2 I ) ≤ IAS(G d E , G u 1 I , G u 2 I ).

⊓ ⊔

Proof (Proposition 2) This proof is similar to the proof of Proposition 1. For the sake of brevity, we give a proof sketch. By a direct application of Lemma we.

Hence, given [START_REF] Roddy | Epidemiology of gout[END_REF] and ( 26) it follows that:

∀c, d ∈ D E . c ⊑ d ⇒ IAS(G d E , G u 1 I , G u 2 I ) ≤ UB(G c E , G u 1 I , G u 2 I ).
⊓ ⊔

Proof (Proposition 3) given c, d ∈ D E such that c ⊑ d, using proposition 1 we have:

IAS(G d E , G u 1 I , G u 2 I ) ≤ UB(G c E , G u 1 I , G u 2 I ), IAS(G d E , G u 1 I , G u 2 I ) -IAS(G E , G u 1 I , G u 2 I ) ≤ UB(G c E , G u 1 I , G u 2 I ) -IAS(G E , G u 1 I , G u 2 I ). Since ϕconsent(G d E , G u 1 I , G u 2 I ) = max(IAS(G d E , G u 1 I , G u 2 I ) -IAS(G E , G u 1 I , G u 2 I ), 0) thus ϕconsent(G d E , G u 1 I , G u 2 I ) ≤ oeconsent(G c E , G u 1 I , G u 2 I
). Similarly we have: α(e) σ E .

IAS(G d E , G u 1 I , G u 2 I ) ≥ LB(G c E , G u 1 I , G u 2 I ), IAS(G E , G u 1 I , G u 2 I ) -IAS(G d E , G u 1 I , G u 2 I ) ≤ IAS(G E , G u 1 I , G u 2 I ) -LB(G c E , G u 1 I , G u 2 I ). Since ϕ dissent (G d E , G u 1 I , G u 2 I ) = max(IAS(G E , G u 1 I , G u 2 I ) -IAS(G d E , G u 1 I , G u 2 I ), 0) we get ϕ dissent (G d E , G u 1 I , G u 2 I ) ≤ oe dissent (G c E , G u 1 I , G u 2 I ).
It follows from the fact that M (G c E , σ E ) ⊆ G c E :

∃S ⊆ G c E , UB(G c E , G u 1 I , G u 2 I ) = IAS(S, G u 1 I , G u 2 I ), UB(G c E , G u 1 I , G u 2 I ) -IAS(G E , G u 1 I , G u 2 I ) = IAS(S, G u 1 I , G u 2 I ) -IAS(G E , G u 1 I , G u 2 I ), oeconsent(G c E , G u 1 I , G u 2 I ) = ϕconsent(S, G u 1 I , G u 2 I ).
The subset S being for example the set M (G c E , σ E ) itself. The same reasoning applies when considering oe dissent . In this case we consider the lower bound LB. We have:

LB(G c E , G u 1 I , G u 2 I ) = 󰁓 e∈m(G c E ,σ E ) α(e) σ E .
Given that m(G c E , σ E ) ⊆ E, we have:

∃S ⊆ G c E , LB(G c E , G u 1 I , G u 2 I ) = IAS(S, G u 1 I , G u 2 I ), IAS(G E , G u 1 I , G u 2 I ) -LB(G c E , G u 1 I , G u 2 I ) = IAS(G E , G u 1 I , G u 2 I ) -IAS(S, G u 1 I , G u 2 I ), oe dissent (G c E , G u 1 I , G u 2 I ) = ϕ dissent (S, G u 1 I , G u 2 I ).
This proves that, if IAS is a simple mean, for any c ∈ D E s.t.

|G c E | ≥ σ E : ∃S, S ′ ⊆ G c E 󰀫 oeconsent(G c E , G u 1 I , G u 2 I ) = ϕconsent(S, G u 1 I , G u 2 I ) oe dissent (G c E , G u 1 I , G u 2 I ) = ϕ dissent (S ′ , G u 1 I , G u 2 I )
.

Hence oeconsent and oe dissent are tight optimistic estimates for respectively ϕconsent and ϕ dissent if the underlying IAS is a simple average.

⊓ ⊔

Before giving the proof of the proposition 5 we present the following lemma. ⊓ ⊔

Fig. 1 :

 1 Fig. 1: Overview of the task of discovering exceptional (dis)agreement between groups

  |G c E | ≥ σ E ) and the size of both groups (i.e. |G u1 I | ≥ σ I and |G u2 I | ≥ σ I ) are large enough. Now, we introduce formally the core problem we tackle in this paper. Problem Def. (Discovering Exceptional (Dis)Agreement between Groups).

Algorithm 2 :

 2 EnumCC(G, d, σ G , f, cnt) Inputs : G is the collection of records depicted each by m descriptor attributes d a description from D, σ G a support threshold, f ∈ [1, m] a refinement flag, cnt a boolean Output: yields all closed descriptions, i.e. clo[D

Fig. 2 :Fig. 3 :

 23 Fig. 2: A collection of records labeled each by a set of tags and its flat representation.

  10

  4.3.1 Lower Bound and Upper Bound for the IAS Measure

Algorithm 3 :

 3 DEBuNk(〈G I , G E , O, o〉, σ E , σ I , ϕ, σ ϕ ) Inputs : 〈G I , G E , O, o〉 a behavioral dataset;

7

  cont c ← False ⊲ Prune the unpromising sub-search space under c 8 else 9 IAScontext ← IAS(c, u1, u2) 10 quality ← ϕ(c, u1, u2) ⊲ computed using IAS ref and IAScontext 11 if quality ≥ σϕ then 12 pnew ← (c, u1, u2) 13 if ∄p old ∈ P | ext(pnew) ⊆ ext(p old ) then 14 P ← (P ∪ pnew) \ {p old ∈ P | ext(p old ) ⊆ ext(pnew)} 15 cont c ← False ⊲ Prune the sub search space 16 if ϕ is symmetric and u1 = u2 then 17 break ⊲ Prune the sub search space 18 return P 5 Sampling (Dis)Agreement Patterns

Fig. 4 :

 4 Fig. 4: Quick-DEBuNk approach in a nutshell

5. 2

 2 RWC -Random Walk on Contexts (Step 2) RWC (Algorithm 5) enumerates contexts of the search space D E while considering closure and optimistic estimates. RWC takes as input two confronted groups u 1 ,u 2 for which it looks for relevant contexts following a random walk process starting from a context c. Mainly, RWC has two steps that are recursively executed until a terminal node is reached. RWC starts by generating all neighbors d of the current context c (line 2). Next, RWC assesses whether the size of the corresponding support G c E and the optimistic estimates respectively exceed the support threshold σ E and the quality threshold σ ϕ (line 3). If Algorithm 5: RWC(〈G I , G E , O, o〉, c, u 1 , u 2 , σ E , ϕ, σ ϕ ) Inputs : 〈G I , G E , O, o〉 a behavioral dataset; c the current context;

Algorithm 6 :

 6 Quick-DEBuNk(〈G I , G E , O, o〉, σ E , σ I , ϕ, σ ϕ ,timebudget) Inputs : 〈G I , G E , O, o〉 a behavioral dataset; σ E (resp. σ I ) minimum support threshold of a context (resp. group); ϕ the quality measure; σϕ threshold on the quality; timebudget the maximum amount of time given to the algorithm. Output: P the set of sampled exceptional (dis)agreement patterns 1 P ← {} 2 while executionTime < timebudget do 3 u1 ← clo(FBS(G I )) 4 u2 ← clo(FBS(G I ))

Fig. 5 :

 5 Fig. 5: Pattern 1 Illustration -distribution of ratings of individuals constituting the group of students versus distribution of ratings of individuals constituting the group of health professionals. Left figure corresponds to the usual distribution observed over all movies. Right figure corresponds to the contextual distribution observed over the context of pattern 1 from Table4.

Table 5 :

 5 Top-3 w.r.t. number of expressed outcomes (o(i, e) column) of disagreement patterns discovered on the Yelp dataset (|A E | = 2, |A I | = 2, σ E = 10, σ I = 1 and σϕ = 0.4).

Fig. 6 :

 6 Fig.6: Illustration of pattern 2 reported in Table6. The left matrix depicts the agreement observed in general between countries when considering all voting sessions. The right matrix corresponds to the inter country agreement for the context of pattern 2.

Fig. 7 :

 7 Fig. 7: Drugs consumption behavior of gender groups in Patterns 3 (left) and 4 (right).

Fig. 8 :

 8 Fig. 8: Comparison between DEBuNk and DSC for the task of discovering the complete set of the desired patterns on EPD8 dataset (default parameters are: |A E | = 2, |A I | = 2, σϕ = 0.4, σ E = 40, σ I = 10 and ϕ dissent ). Lines correspond to the execution time and bars correspond to the number of returned patterns.

Fig. 9 :

 9 Fig. 9: Comparison between DEBuNk and DSC (top-k) for the task of discovering ksized pattern sets on EPD8 Dataset (default parameters: |A E | = 2, |A I | = 2, σϕ = 0.4, σ E = 40, σ I = 10 and ϕ dissent ). Box plots correspond to the size of O[P k ] when varying k in [10, 50, 100].

Fig. 10 :

 10 Fig. 10: Effectiveness of DEBuNk considering EPD8 Dataset with |G E | = 2000, |G I | = 500, |Outcomes| = 750k, |A E | = 3, |A I | = 4, σ E = 40, σ I = 10, σϕ = 0.5 and ϕ dissent . Lines correspond to the execution time and bars correspond to the number of evaluated patterns.

Fig. 11 :

 11 Fig. 11: Efficiency of HMT against itemsets closed descriptions enumeration according to the number of items/tags constituting the hierarchy for the two datasets EPD8 (left) and Yelp (right). For both datasets we only consider the HMT attribute for entities |A E | = 1. The used parameters for EPD8 are: |A I | = 6, σ E = 1, σ I = 10, σϕ = 0.5 and ϕ dissent . The used parameters for Yelp are: |A I | = 3, σ E = 5, σ I = 1, σϕ = 0.5 and ϕ dissent . Lines correspond to the execution time and bars correspond to the number of visited patterns.

Fig. 12 :

 12 Fig. 12: Effectiveness of DEBuNk on EPD8 according to the sizes of G E , G I , D E , D I , the supports and quality measures thresholds. Considering by default |G E | = 4161, |G I | = 958, |Outcomes| = 2.7M , |A E | = 3, |A I | = 6. σ E = 40, σ I = 10, σϕ = 0.5 and ϕ dissent . Lines correspond to the execution time and bars correspond to the number of evaluated patterns.

Fig. 13 :Fig. 14 :

 1314 Fig. 13: Efficiency of Quick-DEBuNk compared to DEBuNk on EPD8. Parameters used are σ E = 40, σ I = 10, σϕ = 0.5 and ϕ dissent . The red line corresponds to the required time by DEBuNk to perform an exhaustive search.

Fig. 15 :

 15 Fig. 15: Efficiency of Quick-DEBuNk compared to DEBuNk over Yelp. Parameters used are σ E = 15, σ I = 1, σϕ = 0.1 and ϕ dissent . The red line corresponds to the required time by DEBuNk to perform an exhaustive search.

  of records depicting entities G I A finite collection of records depicting individuals O the domain of possible outcomes o function returning the outcome of an individual over an entity 〈G I , G E , O, o〉 A behavioral dataset A E Descriptive attributes of entities A I Descriptive attributes of individuals θ An outcome aggregation measure sim a similarity function between two aggregated outcomes IAS Inter-group Agreement Similarity Measure ϕ An interestingness measure D E The description domain of entities containing all possible contexts D I The description domain of individuals G d E A subgroup of entities supporting a description d ∈ D E G u I A subgroup of individuals supporting a description u ∈ D I δ A mapping function that binds an entity from G to a description in D P = D E × D I × D I and denotes the pattern space p = (c, u 1 , u 2 ) ∈ P depicts a (dis)agreement pattern p * = ( * , u 1 , u 2 ) ∈ P depicts the referential (dis)agreement pattern related to some pattern p = (c, u 1 , u 2 ) P ⊆ P denotes a pattern set ⊑ read "less restrictive than" is a partial order between descriptions (resp. patterns) in some descriptions space D (resp. patterns space P) ∧ the conjunction operator between descriptions in D η the refinement operator which applies atomic refinements of a given description d ∈ D, thereby yielding neighbor descriptions of d w.r.t. ⊑

  c ⊑ d ⇒ G d E ⊆ G c E . Hence, if we reorder values of G c E and G d

  Given that ∀(e, G u 1 I , G u 2 I ) ∈ E × 2 I × 2 I : w(e, G u 1 I , G u 2 I ) = 1, we have for any c ∈ D E s.t. |G c E | ≥ σ E ,

Lemma 2 5 ).

 25 The sums of the number of all descriptions covering each record in G is equal to the sum of the supports of all descriptions in D. That is:󰁛 g∈G | ↓ δ(g)| = 󰁛 d∈D |G d |. Proof (Lemma 2) For g ∈ G, we have ↓ δ(g) = {d ∈ D s. t. d ⊑ δ(g)} and for d ∈ D, we have G d = {g ∈ G s. t. d ⊑ δ(g)}.Let us define the indicator function on D × G:1 ⊑ (d, g) = 󰀫 1 if d ⊑ δ(g) 0 else . Hence, we have | ↓ δ(g)| = 󰁓 d∈D 1 ⊑ (d, g) and |G d | = 󰁓 g∈G 1 ⊑ (d,g) thus: We denote by gs the random record drawn in line 1 and by ds the random description drawn in line 2 of F BS. P(ds = d) = 󰁛 g∈G P((gs = g)(ds = d|g))It follows that from Lemma 2 that P(ds= d) = |G d | 󰁓 d ′ ∈D |G d ′ | . ⊓ ⊔ Proof (Proposition 6) Given Proposition 5, it is clear that ∀p ∈ P : p = (c, u 1 , u 2 ) satisfies C ⇒ P(p) = |ext(p)| Z > 0. with |ext(p)| = |G c E | × |G u 1 I | × |Gu 2 I | and Z = 󰁓 p ′ ∈P |ext(p ′ )| a normalizing factor.

Table 1 :

 1 Example of behavioral dataset -European Parliament Voting dataset Since the majorities of 〈u 1 , u 2 〉 voted respectively on {e 1 , e 2 , e 3 , e 4 , e 5 , e 6 } as follows: 〈For, For〉, 〈Against, Against〉, 〈Against, For 〉, 〈For, For〉, 〈For , Against〉, 〈Against, Against〉.

	ide	themes	date	idi	ide	outcome
	e 1 e 2 e 3 e 4 e 5 e 6 idi i 1 i 2 i 3 i 4	1.20 Citizen's rights 2.10 Free Movement of goods 1.20 Citizen's rights; 7.30 Judicial Coop 7 Security and Justice 7.30 Judicial Coop 7.30 Judicial Coop (a) Entities (Voting sessions) country group France S&D France PPE Germany S&D Germany ALDE	20/04/16 16/05/16 04/06/16 11/06/16 03/07/16 29/07/16 age 26 30 40 45	i 1 i 1 i 1 i 1 i 2 i 2 i 2 i 2 i 3 i 3 i 3 i 3 i 4 i 4 i 4	e 1 e 2 e 5 e 6 e 1 e 3 e 4 e 5 e 1 e 2 e 3 e 5 e 1 e 4 e 6	For Against For Against For Against For For For Against For Against For For Against
		(b) Individuals (Parliamentarians)			(c) Outcomes

1 http://parltrack.euwiki.org/, last access on October 15, 2019. 2 https://voteview.com/data, last access on

October 25, 2019. 3

  Algorithm 1: PseudoDEBuNk(〈G I , G E , O, o〉, σ E , σ I , ϕ, σ ϕ ) Inputs : 〈G I , G E , O, o〉 a behavioral dataset; σ E (resp. σ I ) minimum support threshold of a context (resp. group); ϕ the quality measure; σϕ quality threshold on the quality. Output: P the set of exceptional (dis)agreement patterns. 1 P ← ∅ 2 foreach pair of groups (u 1 , u 2 ) ∈ D I × D I do

	3 4	foreach context c ∈ D E do Evaluate the quality of the pattern ϕ(c, u 1 , u 2 )
	5 6	if the pattern is interesting (i.e. ϕ(c, u 1 , u 2 ) ≥ σϕ) then Update P with (c, u 1 , u 2 )
	7	else
	8	Evaluate the optimistic estimate oe(c, u 1 , u 2 )
	9	if oe(c, u 1 , u 2 ) < σϕ then
	10	Prune the sub-search space (backtrack).
	11 return P
	and explains how they are combined to compute the complete set of excep-
	tional (dis)agreement patterns.
		From Algorithm 1, we see that the main ingredients of DEBuNk basically
	consists of:
	1. Enumerating candidate patterns (lines 2 -3): Efficiently enumerating candidate patterns in the whole search space P

Sampling patterns satisfying cardinality constraints (FBS) Step 2 : Random Walk on Contexts (RWC)

	Sampled groups of individuals Step 1 : Selected context to Sampled context c to expand Confronted refine in a random walk process iteration groups
			u 1
			u 2
	Minimum support					Interesting pattern p
	threshold	Individuals	Contexts Search	contexts c forming interesting	Local sub-search space	found by Quick-DEBuNk
		Search Space D I	Space D E	patterns (c,u 1 ,u 2 )	corresponding to the sampled context c

  Quick-DEBuNk Quick-DEBuNk (Algorithm 6) samples patterns from the full search space D E ×D I ×D I . It is based on FBS and RWC. It takes as input the same parameters as DEBuNk in addition to a timebudget. It starts by generating a couple of closed group descriptions of individuals u 1 , u 2 that fulfill the cardinality constraints (lines 3 -5) using FBS. Next, Quick-DEBuNk generates a context while only considering entities having a quality greater than the threshold σ ϕ (line 6). The reason behind considering only G

≥σϕ E is clear: we have ∀p ∈ P p satisfies C and ϕ

  consisting of 100K ratings (ranging from 1 to 5) expressed by 943 users on 13 https://github.com/Adnene93/DEBuNk, last access onOctober 25, 2019.

14

https://parltrack.org/, last access on October 15, 2019. 15 https://grouplens.org/datasets/movielens/100k/, last access on

April 24, 2017.

Table 2 :

 2 Behavioral datasets characteristics before and after scaling.

			Entities	Individuals	Outcomes
	EPD8	Size (Nb. records)	4161	958	2.7M
		attribute types	1H + 1N + 1C	1N + 5C
		size after scaling	347 + 26 + 40 = 413	16 + 285 = 301
		avg scaling per record	20.44	14
	Movielens	Size (Nb. records)	1681	943	100K
		attribute types	1H + 1N	3C
		size after scaling	20 + 144 = 164	4 + 2 + 21 = 27
		avg scaling per record	75.72	3
	Yelp	Size (Nb. records)	127 000	18	750K
		attribute types	1H + 1C	3C
		size after scaling	1175 + 29 = 1204	3 + 2 + 3 = 8
		avg scaling per record	5.77	3
	Openmedic	Size (Nb. records)	12 221	78	500K
		attribute types	1H	3C
		size after scaling	14 094	2 + 13 + 3 = 18
		avg scaling per record	7	3

16

https://www.yelp.com/dataset/challenge, last access on April 25, 2017. 17 http://open-data-assurance-maladie.ameli.fr/, last access on

November 16, 2017.

Table 3 :

 3 Table 2 illustrates this step, while Table3shows the obtained comparable characteristics. Characteristics of the datasets considered as plain collections of itemsets recordsthe plain collections correspond to G

	Dataset	Transactions	Items	AverageSize
	EPD8	1 727 032 585	1 015	34.48
	Movielens	16 807 109	218	79.37
	Yelp	5 860 354	1 220	9.00
	Openmedic	28 512 418	14 130	10.00

E × G I × G I while considering only pairable individuals (i.e., the cartesian product contains a record (e, i 1 , i 2 ) only if both individuals expressed an outcome on the entity e, that is o(i 1 , e) and o(i 2 , e) are given).

Table 4 :

 4 Top

		(c, u1, u2)	|G c E |	|G	u 1 I |	|G	u 2 I |	o(i, e)	ϕ dissent
		(Newcomer,*) vs. (Middler,*) in							0.4 =
	1	['03 Automotive', '14.22 Electronics Repair', '22.06 Battery Stores', '22.21 Electronics'] *	10	6		6		43	0.8 -0.4
	2	(Senior, Medium) vs. (Middler, Large) in ['10.55.21 Internal Medicine'] Nevada	15	2		2		39	0.43 = 0.81 -0.38
		(Newcomer, Medium) vs. (Middler, Large)							0.4 =
	3	['11.59.01 Apartments', '11.59.18 University Housing'] Arizona	14	2		2		30	0.78 -0.38

-3 w.r.t. number of expressed outcomes (o(i, e) column) of disagreement patterns discovered on Movielens (|A E | = 2, |A I | = 1, σ E = 5, σ I = 10 and σϕ = 0.4).

Table 6 :

 6 Top-3 w.r.t. number of expressed outcomes (o(i, e) column) of Relevant (dis)agreement patterns discovered on EPD8 (|A

Table 7 :

 7 Top-4 w.r.t. the number of expressed outcomes on Openmedic considering by default the full dataset, |A E

Table 8 :

 8 Symbol tableA Appendix: Proofs of Theorems and PropositionsBefore giving the proof of the proposition 1 we present the following lemma.Lemma 1 Let n ∈ N * , A = {a i } 1≤i≤n and B = {b i } 1≤i≤n such that: ∀i ∈ 1..n -1, 0 ≤ a i ≤ a i+1 , ∀i ∈ 1..n -1, 0 < b i+1 ≤ b i .

	We have:
	∀k ∈ 1..n,	󰁓 k i=1 a i 󰁓 k i=1 b i	≤	󰁓 n i=1 a i 󰁓 n i=1 b i	≤	󰁓 n i=n-k+1 a i 󰁓 n i=n-k+1 b i

  can be easily proved following the same line of reasoning of the proof of the first part of the inequality. By a straightforward application of Lemma 1 we obtain for any d s.t. |G d E | ≥ σ E the following inequality. This stems from the fact that LB(G d E , G u 1 I , G u 2 I ) takes the sum of the lowest σ E quantities constituting the numerator of IAS(G d E , G u 1 I , G u 2 I ) and divides them by the sum of the greatest σ E quantities forming the denominator of IAS(G d E , G u 1 I , G u 2 I ). Moreover, we have that LB is monotonic w.r.t. ⊑ of D E . i.e.

	conclude that
	󰀳 󰁃	n 󰁛 i=k+1	a i	󰀴 󰁄 ×	󰀣 k 󰁛 i=1	b i	󰀤	-	󰀣 k 󰁛 i=1	a i	󰀤	×	󰀳 󰁃	n 󰁛 i=k+1	b i	󰀴 󰁄 ≥ 0.
	Hence, we have:
					∀k ∈ 1..n,	󰁓 k i=1 a i 󰁓 k i=1 b i	≤	󰁓 n i=1 a i 󰁓 n i=1 b i	.
	Similarly the inequality	󰁓 n i=1 a i 󰁓 n i=1 b i	≤	󰁓 n i=n-k+1 a i 󰁓 n i=n-k+1 b i
																	⊓ ⊔
	Proof (Proposition 1) LB(G d E , G u 1 I , G u 2 I ) ≤ IAS(G d E , G u 1 I , G u 2 I ).	(21)

  it is clear that: ∀i ≤ σ E , w e c i .α(e c i ) ≤ w e d E ) = {e c 1 , ..., e c σ E } and m(G d E , σ E ) = {e d 1 , ..., e d σ E }, it follows that: 󰁛 Similarly, if we reorder entities e in descending order w.r.t the weights we we have ∀j ≤ σ E | w e d

	m(G c E , σ e∈m(G c E ,σ E )	we × α(e) ≤	󰁛 e∈m(G d E ,σ E )	i we × α(e).	.α(e d i ). Having that (23)
	j	≤ w e c j . Resulting in:
		󰁛		󰁛
		e∈M w(G c E ,σ E )	we ≥	e∈M w(G d E ,σ E )

  1, it is clear that for any d s.t. |G d E| ≥ σ E , IAS(G d E , G u 1 I , G u 2 I ) ≤ UB(G d E , G u 1 I , G u 2 I ). (25)We have that U B is anti-monotonic w.r.t. ⊑ of D E . i.e.

		c ⊑ d ⇒ UB(G c E , G u 1 I , G u 2 I ) ≥ UB(G d E , G u 1 I , G u 2 I ).	(26)
	This results from c ⊑ d ⇒ G d E ⊆ G c E . Thus, 󰁛 󰁛	󰁛		󰁛
	e∈M (G c E ,σ E )	we × α(e) ≥	e∈M (G d E ,σ E )	we × α(e) and	e∈mw(G c E ,σ E )	we ≤	e∈mw(G d E ,σ E )

DEBuNk stands for Discovering Exceptional inter-group Behavior patterNs

http://contentcheck.liris.cnrs.fr, last access onOctober 25, 2019.

Different quality measures are proposed in Sec. 3.

Note that this does not require S to have a corresponding description in D E .

Cartesian product of the m lattices related to the attributes' conditions spaces forms a lattice[START_REF] Roman | Lattices and ordered sets[END_REF]

http://contentcheck.liris.cnrs.fr, last accessOctober 25, 2019.

https://www.idf.org/component/attachments/attachments.html?id=811&task= download [Page=97], last access on October 18, 2019.

https://bit.ly/2zuorQK, last access on October 18, 2019.

27 runs for each method by varying (|AE |, |A I |, σϕ) ∈ [[1, 2, 3] , [1, 2, 3] , [0.2, 0.4, 0.6]]

81 runs by varying (k, |A E |, |A I |, σϕ) ∈ [[10, 50, 100] ,[1,[START_REF] Bosc | Anytime discovery of a diverse set of patterns with monte carlo tree search[END_REF] 3] ,[1, 2, 3] , [0.2, 0.4, 0.6]]

http://www.oecd.org/gov/digital-government/open-government-data.htm, last access onOctober 25, 2019.

Acknowledgements This work has been partially supported by the project ContentCheck ANR-15-CE23-0025 funded by the French National Research Agency. The authors would like to thank the reviewers for their valuable remarks. Their thoughtful and deep comments allowed us to considerably improve this paper. They also warmly thank Wouter Duivesteijn, Albrecht Zimmermann and Aimene Belfodil for interesting discussions.