Adnene Belfodil

Sylvie Cazalens

Philippe Lamarre

Marc Plantevit

Identifying exceptional (dis)agreement between groups Technical Report

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 depicts parliamentarians who express their votes w.r.t. 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 mutual 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 direct sampling paradigm which is 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.

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 outcomes of European parliament members (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 basics queries on data. 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 })". For, For , Against, Against , Against, For , For, For , For , Against , Against, Against .

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. Indeed, 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] Klosgen | Explora: A multipattern and multistrategy discovery assistant[END_REF][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] Lavrač | 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[END_REF] extends SD by offering the possibility to handle complex targets [START_REF] Downar | Exceptionally monotone models-the rank correlation model class for exceptional model mining[END_REF][START_REF] Duivesteijn | Exceptional model mining[END_REF][START_REF] Kaytoue | Exceptional contextual subgraph mining[END_REF][START_REF] De Sá | Exceptional preferences mining[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 in [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF] requires the specification of many non-intuitive parameters that may be source of misleading interpretation. 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 by intents [START_REF] Hasan | Output space sampling for graph patterns[END_REF] . Then, their usual agreement on all their expressed outcomes is computed in step [START_REF] Amelio | Analyzing voting behavior in italian parliament: Group cohesion and evolution[END_REF]. All characterizable subsets of entities (contexts (c)) are then enumerated (3) and for each selected subset, the agreement between the two groups is measured (4) and compared to their usual agreement [START_REF] Atzmueller | Vikamine-open-source subgroup discovery, pattern mining, and analytics[END_REF] to evaluate to what extent the mutual agreement changes conveyed by 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, 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. Much effort has been done to ensure a generic framework for behavioral data analysis. Algorithms. We propose two algorithms to tackle the problem of discovering exceptional (dis)agreement patterns. DEBuNk 4 is a branch-and-bound algorithm that efficiently returns the complete set of patterns. It takes benefit from 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 both synthetic and real-world datasets. Synthetic datasets with controlled ground truth allows to make some qualitative comparisons with some existing methods. It gives evidence that existing methods fail to discover inter-agreement patterns. The four real-world datasets are then used to demonstrate the efficiency and the effectiveness of our algorithms as well as the interest of the discovered patterns. Especially, 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 [START_REF] De Lacombe | Analyse de comportements relatifs exceptionnels expliquée par des textes : les votes du parlement européen[END_REF].

Entities 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. DEBuNk algorithm 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. Eventually, we conclude and discuss future directions of research in Section 8.

Problem Definition

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

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

Elements from G I (resp. G E ) have descriptive attributes, which set is denoted as A I (resp. A E ). Attributes a ∈ A I (resp. A E ) may be numerical or categorical. Furthermore, individuals or entities may be associated with a set of tags which are organized within a taxonomy. Such attributes are said to be Hierarchical Multi-Tag (HMT). For instance, in Table 1, deputies (i.e., individuals), described by their country (categorical), their political group (categorical) and their age (numerical), decide on some voting sessions outlined by a date (seen as a numerical attribute) and themes (an HMT attribute).

To describe sets of individuals and sets of entities, we define group descriptions and contexts respectively. Both are descriptions formalized by conjunctions of conditions on the values of the attributes, but we use these two different terms for ease of interpretation. For example, in Table 1, the context c = themes ⊇ '7.30 Judicial Coop' imposes the presence of '7.30 Judicial Coop' in the attribute 'themes' and identifies the set of entities G c E = {e 3 , e 5 , e 6 }. Similarly, the group description u = group='S&D' selects the set of individuals G u I = {i 1 , i 3 }. The set of all possible contexts (resp. group descriptions) is the description space denoted D E (resp. D I ).

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: I ⊆ G u2 I ). A quality measure ϕ is required to assess the interestingness of a pattern. It assigns to each pattern p a positive real number. This value is computed considering exclusively the extent of the pattern. Therefore, two equivalent patterns have the same quality. Different quality measures are proposed in Sec. 3.

Our objective is to provide the user with a collection of patterns that captures exceptional (dis)agreement 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 σ ϕ . This is of major importance, but considering the quality is not enough. Indeed, many different patterns may reach the same quality level just because they share the same extent. In such a case, we assume that the user would expect the system not to bother her with huge collections of patterns describing the same parts of the data. More interestingly, the system should provide her with the good generalizations, i.e., the patterns that are not a specialization of already found ones w.r.t. their extents. 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 valid that is p satisfies C and ϕ(p) ≥ σ ϕ . 2. (Maximality) ∀p ∈ P ∀q ∈ P : p = q and q ≡ G E ,G I p ⇒ p q 3. (Completeness) ∀q ∈ P \ P : q valid ⇒ ∃p ∈ P s.t. ext(q) ⊆ ext(p) 4. (Generality) ∀(p, q) ∈ P 2 : p = q ⇒ ext(p) ext(q). Condition (1) assures that the patterns in P are of high quality and satisfy the cardinality constraints. Condition (2) discard equivalent patterns by retaining only a unique representative which is the maximal one. Condition (3) ensures completeness and 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 and that each valid pattern in P has a representative in P covering it. Considering the generic definition of the quality measure discussed here, this problem extends the former 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 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 ϕ whose generic definition is given. Here we show how such measure captures the deviation between the contextual intergroup 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 all the entities. IAS (p * ) (resp. IAS (p)) 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 that rely on 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) .
ϕ dissent assesses the weakening of inter-group agreement in a context c:

ϕ dissent (p) = max (IAS (p * ) -IAS (p) , 0) .
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 following. 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 our study, 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 5 (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 ).
The IAS of a pattern (c, u 1 , u 2 ) (IAS : P → R + ) is the weighted average of the similarities of the aggregated outcomes for each entity e supporting the context c.

IAS(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 )

Examples of IAS Measures

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

Behavioral Data With Numerical Outcomes

Collaborative 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) (1)
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. If no weights are given, θ wavg computes a simple average over ratings, denoted θ avg . To measure agreement between two aggregated ratings over a single entity, we define sim rating :

[min, max] × [min, max] → [0, 1]. sim rating (x, y) = 1 -( |x -y| max -min ) (2)

Behavioral Data with Categorical Outcomes

A typical example of such datasets are Roll Call Votes (RCVs) 7 datasets where voting members cast categorical votes. The outcome domain O is the set of all possible votes (e.g., O = {For, Against, Abstain}). To aggregate categorical outcomes we use the majority vote8 θ majority . We adapt its definition to handle potential ties (i.e., non unique majority vote). Hence, θ majority : 2 G I ×G E → 2 O returns all the outcomes that received the majority of votes.

θ majority (G u I , e) = {v ∈ O : v = argmax z∈O #votes(z, G u I , e)} with #votes(z, G u I , e) = |{(i, e) : i ∈ G u I ∧ o(i, e) = z}| (3)
We use a Jacquard 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| . (4)

Discussion

We introduced above two simple similarity measures that can be used as part of the 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 into account the empirical distribution of votes 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 | Symmetrizing the kullback-leibler distance[END_REF]). Such measures can also be used on behavioral datasets which involves numerical outcomes, for instance Earth Mover Distance measure was investigated in similarly structured dataset (rating dataset) in [START_REF] Amer-Yahia | Exploring rated datasets with rating maps[END_REF].

Several other measures can be relevant to analyze behavioral data with numerical outcomes depending on the aim of the study. In the empirical study, we investigate another similarity measure which relies on a ratio to highlight discrepancies between the medicine consumption rates of two subpopulations.

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

We address the design of an efficient algorithm for enumerating candidate patterns. First, we present how candidates are enumerated without redundancy by relying on a closure operator. Second, we detail the enumeration process, paying particular attention to the attributes domains depicted by a hierarchy. Next, we propose optimistic estimates for the quality measures. Eventually, these elements are used to define an efficient branch-and-bound algorithm which computes the complete set of relevant (dis)agreement patterns.

Enumerating Closed Patterns

Exploring the space of patterns (dis)agreement patterns p = (c, u 1 , u 2 ) ∈ D E × D I × D I is equivalent to explore D E and D I concurrently. Despite their differences, these two universes are formalized in a similar way, such that the exploration method presented below can be applied indifferently to any of them.

Let G be a collection of records (corresponding to entities G E , or individuals G I ). We assume A = (a 1 , a 2 , ..., a m ) (corresponding to A E or A I ) to be the ordered list of attributes depicting its schema. Each attribute a j has a domain of interpretation, noted dom(a j ), which corresponds to all its possible values. In this section, we focus on attributes of two types: categorical attributes and numerical ones that cover a large number of practical cases. Nevertheless, our approach enables to introduce additional types without any modification of the general algorithm as illustrated in the section 4.2.

Description Language and Description Space Structure

A description d = r 1 , r 2 , ..., r m is an ordered list of conditions on attributes' values. G d denotes the support of d, i.e. the subset of G satisfying the conditions r j of d. When a description d 1 is less specific than a description d 2 , we note d 1 d 2 . From a logical point of view d 2 ⇒ d 1 . From this it follows that if d 1 d 2 then G d2 ⊆ G d1 . The form of a condition r j depends on the type of its related attribute. A condition on a categorical (resp. numerical) attribute is an equality test (resp. a membership test) of the form a j = v (resp. a j ∈ [v..w]) where v (and w) is (are) value(s) of the corresponding domain dom(a j ).

Characterizing a given subset S of a collection G with a specific description, denoted δ(S), plays an important role in our process. δ(S) is built in a bottomup fashion. Considering an element s of S, we obtain its characterization δ(s) by a composition of the characterizations of its values (one δ j (s) for each considered attribute a j of s). The description of S, δ(S), is then obtained by composing the characterizations of all of its elements. In the same spirit as in [START_REF] Ganter | Pattern structures and their projections[END_REF], we introduce some mapping functions δ j (s) which provide 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])) when a j is a categorical (resp. numerical) attribute. Applying such mappings to all the attributes leads to a complete description of s: δ(s) = δ 1 (s), δ 2 (s), ..., δ m (s)

Once the description δ(s) of a single record s is defined, the support G d of description d can be expressed as

G d = {g ∈ G | d δ(g)}.
It is then possible to obtain a description of S combining the descriptions of its elements. Each condition domain D j related to an attribute a j can be conceptualized as a semi-lattice with an infimum operator denoted . . Intuitively, such operator provides the tightest condition subsuming two conditions. The definition of the infimum operator depends on the type of the attribute. The infimum operator for a categorical (resp. numerical) attribute is denoted c (resp. n ). The infimum n between interval conditions is defined following [START_REF] Kaytoue | Mining gene expression data with pattern structures in formal concept analysis[END_REF].

(a j = v 1 ) c (a j = v 2 ) = a j = v 1 if v 1 = v 2 true aj else (a j ∈ [v 1 ..w 1 ]) n (a j ∈ [v 2 ..w 2 ]) = a j ∈ [min(v 1 , v 2 )..max(w 1 , w 2 )]
The Cartesian product of the m lattices related to attributes also forms a lattice [START_REF] Roman | Lattices and ordered sets[END_REF] that we can also equip with an infimum operator which provides the maximum common description of two descriptions d, d :

d d = r 1 , ..., r m r 1 , ..., r m = r 1 t 1 r 1 , ..., r m t m r m ( 5
)
with t j is n for numerical attributes and c for categorical ones.

The maximum common description covering a subset S of a collection (S ⊆ G) is then obtained by: (where is commutative, associative and idempotent)

δ(S) = g∈S (δ(g)) (6)
For example, in the dataset given in Table 1, individuals are described by both categorical and numerical attributes. The description d = true country , true group , age ∈ [START_REF] Downar | Exceptionally monotone models-the rank correlation model class for exceptional model mining[END_REF][START_REF] Kaytoue | Mining gene expression data with pattern structures in formal concept analysis[END_REF] identifies the deputies whose age is between 20 and 40. Its support G d I is {i 1 , i 2 }. Interestingly, these two individuals share more elements in common w.r.t. their descriptors. Indeed, d = δ({i 1 , i 2 }) = country='France', true group , age∈ [START_REF] Ganter | Pattern structures and their projections[END_REF][START_REF] Grosskreutz | Subgroup discovery for election analysis: a case study in descriptive data mining[END_REF] . Notice that (i) the two descriptions share the same support (G d I =G d I ) and (ii) d δ(G d I ), as d is less specific than δ({i 1 , i 2 }) = δ(G d I ). Since we expect a support to be described only once in the result, the enumeration process has to prevent the enumeration of descriptions sharing the same support. More precisely, we expect to obtain the closed description, clo(d), which is a description sharing its support with d (G d = G clo(d) ), and which is also the most specific one (if

G d =G d , then d clo(d))
. This is not a constructive definition, but interestingly clo(d) = δ(G d ).This provides a method to obtain the desired description. This equality results from the fact that d and δ( ) are a pair of Galois derivation operators between 2 G and (D, ) providing as a consequence a closure operator: namely the composite operator δ(G d ). Proof and details of this equality is omitted as it is a wellknown notion in pattern mining and formal concept analysis [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF][START_REF] Ganter | Pattern structures and their projections[END_REF].

Description Enumeration

Our exploration algorithm is based on a depth-first enumeration method starting from the most general description true a1 , . . . , true am , shortly noted * . 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. Furthermore, such refinement is minimal (d d ∧ e ∈ D : d e d ). Again, the atomic refinement of condition r j takes different forms depending on the type of a j . Since a condition over a numerical attribute is of the form a j ∈ [inf..sup] 9 , an atomic refinement corresponds to a left-minimal change with respect to existing values of the attribute

a j in G d (a j ∈ [next G d (inf )..sup]) or a right-minimal change (a j ∈ [inf..pred G d (sup)]
) on the interval bounds of the condition. An empty resulting interval means 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, v being a value in dom(a j ). Otherwise, a condition of the form a j = v does not admit any refinement. Whatever the type of the attribute is, d ≺ d denotes the fact that d results from an atomic refinement of condition d. This notion enables to easily progress from one description d to the next ones by relying on the following refining operator η.

η j (d) = {d = r 1 , . . . , r m ∈ D : r j ≺ r j and ∀k ∈ [1..j[∪]j..m], r k = r k } (7) η(d) = j∈[1..m] η j (d) (8)
Algorithm 1 called EnumCC (Closed Description ENumerator ), first introduced in [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF], describes the exploration of the search space over a collection of records G defined by the attributes A = {a 1 , . . . , a m }. Remind that such a collection may refer to either the collection of entities G E or the collection of individuals G I . Closed Description ENumerator enumerates once and only once all the closed descriptions that verify the support constraint |G c | ≥ σ G with σ G a user defined threshold. EnumCC follows the same spirit as Close-byOne algorithm [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF]. Note that EnumCC goes along the same lines of the enumeration algorithm EnumCC in our previous paper [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF]. The main differences between the two algorithms reside on their implementation and the optimizations on which EnumCC relies. The implementation is available and maintained online 10 .

Starting from a description d, EnumCC first computes its corresponding support G d (line 1). If the size exceeds the threshold (line 2), the closure of d is computed (line 3). Subsequently, a canonicity test between closure d and d is assessed (line 4). It allows to determine if a description after closure was already generated and to discard it, if appropriate, without addressing the list of already generated closed descriptions requiring hence no additional storage. 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, attribute conditions are refined following this arbitrary order. Let d = r 1 , ..., r f , ..., r m 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 between attributes, we expect for d , if it is the first tim e 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 need thus to be discarded. The intuition behind the canonicity test being explained, a canonicity test rests essentially on a lectic order (cf. [27, 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 4), closure d is returned as a valid closed candidate (line 6). The algorithm then generates the neighbors by refining the attributes {a f , ..., a n } continuing from d on the condition that cnt c is not switched to False (lines 7-9). Flag f determines the index of the last attribute that was refined in the description d (operator η). Boolean cnt c can be modified externally by some caller algorithm to prune the search space, for instance, when using optimistic estimates on the quality measures. Eventually, a recursive call is done to explore the sub search space related to d (lines [START_REF] Bendimerad | Unsupervised exceptional attributed sub-graph mining in urban data[END_REF][START_REF] Boley | Formal concept sampling for counting and threshold-free local pattern mining[END_REF]. Hence, to enable the full exploration of search space D associated to a collection of records G, the algorithm is called with this initial parameters EnumCC(G, * , σ, 1, true). Recall that * is the description true a1 , true a2 , . . . true am having the complete collection G as its support. For the sake of simplicity, we consider G a set of tagged records where each record g is described by a unique attribute tags which is a set of tags. Tags form a tree noted T . Fig. 2 depicts a dataset of tagged records. We can define the partial order ≤ between tags as the same usual partial order in a tree structure where the tree root is the minimum (e.g. * < 1 < 1.20). This enables us to define the ascendants (resp. descendants) operator ↑ (resp. ↓) of a tag t ∈ T . We have ↑ t = {u ∈ T |u ≤ t} and ↓ t = {u ∈ T |u ≥ t}. Let t and u be two tags, t is a lower neighbor of u denoted t ≺ u if t < u and e ∈ T | t < e < u. Thus t is a parent of u denoted as t = p(u).

] = {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
A condition over an HMT attribute is assimilated as a membership in a set of tags {t 1 , ..., t n }. We denote the condition domain by D which is a subset of 2 T . Each object g ∈ G is mapped by δ(g) to its corresponding condition in D. Clearly, if δ(g) = {t 1 , t 2 }, the object g is tagged explicitly by the tags t 1 and t 2 but also implicitly by all their generalizations ↑ t 1 and ↑ t 2 as shown in the flat representation in Fig. 2. Hence, an HMT restriction can be depicted by a rooted sub-tree of T and a record supports such restriction 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 more specific than r) is valid if the sub-tree r covers the sub-tree r . More formally, r r means ∀t ∈ r ∃u ∈ r | u ∈ ↓ t.

Two ways are possible to handle this attribute among the other attributes in the complex search space defined previously. One straightforward solution is to consider HMT attribute values as itemsets as depicted in the vector representation in Fig. 2. 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 viewpoints of itemsets solution. As a consequence, a larger search space is explored while determining the same closed descriptions. The same observation has been made for nu-

g 1 × × × × × g 2 × × × g 3 × × × × × g 4 × × × g 5 × × ×
Fig. 2: A tree of tags (left), a set of tagged items (middle) and its flat representation (right)

merical attributes [START_REF] Kaytoue | Mining gene expression data with pattern structures in formal concept analysis[END_REF]. To tackle such issue, we define an HMT description language. Similarly to the aforementioned attributes, we define the infimum operator between two conditions which computes the maximum common subtree covering a set of conditions. Let r = {t 1 , ..., t n } and r = {u 1 , ..., u m } be two conditions of D, we define h as : r h r = max(∪ t∈r ↑ t ∩ ∪ u∈r ↑ u) with max : 2 T → 2 T a function that maps a subset of tags s ⊆ T to the leafs of the sub-tree compound of the tags of s: max(s

) = {t ∈ s | (↓ t \ {t}) ∩ s = ∅}.
Intuitively, r h r depicts the set of the maximum explicit or implicit tags shared by the two descriptions. For instance, if c = {1.10, 2} and d = {1.20, 2.10}, c h d = {1, 2}. Fig. 3 illustrates the HMT infimum operator, where green and yellow tags represent respectively the explicit and the implicit tags of some given conditions in D.

Similarly, a restriction r is an upper neighbor of r , that is r ≺ 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. Formally:

∃! (t, u) ∈ c × d : t ≺ u ∧ ∀t ∈ (c \ t) ∃u ∈ d : t = u if |d| = |c| ∀t ∈ c ∃u ∈ d : t = u ∧ ∃!(t, u) ∈ c×d ∃t ∈ ↑ t : p(u) = p(t ) |d| = |c|+1
Finally, we need to define the lectic order between two conjunctions of tags r = {t 1 , ..., t n } and its closure r = {u 1 , ..., u n , ..., u m } to assess the canonicity test. Given that r is generated after a refinement of the f th , the lectic order is defined as:

r f r ⇔ ∀i ∈ [1..f -1] : t i = u i ∧t f u f .
The linear order between tags can be provided by the depth first search order on T . These concepts being defined, the mapping function δ and G d can be extended easily to handle HMT among other attributes. Note that the HMT attributes support itemset attributes. This can be done simply by considering a flat tree T compound of all the items. Hence, HMT attributes can be seen as generalizations of itemset attributes, 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 without pruning based on the quality measure. We present some pruning properties based on bounds on ϕ consent and ϕ dissent .

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. Below, we give the definitions of an optimistic estimate [START_REF] Grosskreutz | Tight optimistic estimates for fast subgroup discovery[END_REF].

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

∀ contexts c, d ∈ D E . c d ⇒ ϕ(d, u 1 , u 2 ) ≤ oe(c, u 1 , u 2 )
Tight optimistic estimates, defined in [START_REF] Grosskreutz | Tight optimistic estimates for fast subgroup discovery[END_REF], offer more pruning abilities than simple optimistic estimate. Without loss of generality, we assume that the input domains of oe and ϕ are defined over both the pattern space P and over 2 E ×2 I ×2 I . This is possible, since the quality measure only depends on extents.

Definition 7 (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 ).
Note that this does not require S to have a corresponding description in D E .

Lower Bound and Upper Bound for the IAS Measure

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 : .

IAS(G c E , G u1 I , G u2 I ) = e∈G c E w e × α(e)
We can now define a lower bound LB and an upper bound U B 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) | 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) | 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 | 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 | 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
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
For any context c (corresponding to a subgroup G c E ), 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) 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)
The two defined optimistic estimates tight if the IAS measure is a simple average. i.e. all weights are equal to 1.

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 (resp. oe dissent ) is a tight optimistic estimate for ϕ consent (resp. ϕ 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). To this end, it takes benefit from 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 σ ϕ then 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 new generated pattern is added to pattern set P while removing all previous generated patterns that are more specific than p w.r.t. extents (lines 11-14). Since the current pattern quality exceeds the threshold and all the remaining patterns in the current context sub search space are more specific than the current one, the sub search space is pruned (line 15). Eventually, if 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. As a consequence, it is possible to prune the sub search space of the couple descriptions (u 1 , u 2 ) whenever u 1 = u 2 (lines [START_REF] Charalabidis | A taxonomy of open government data research areas and topics[END_REF][START_REF] Csisz | Information-type measures of difference of probability distributions and indirect observations[END_REF].

Algorithm 2: DEBuNk( 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. DEBuNk and DSC algorithm [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF] differs on several levels. First, DEBuNk overcomes the limitations of lack of diversity of results provided by DSC which was designed to discover the top-k solutions. The present algorithm discards all patterns for which a generalization is already a solution. Second, DEBuNk handles a wider range of bounded quality measures (i.e. weighted mean IAS), in contrast to DSC algorithm which handles only a subset of these measures. 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 check 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 resulting patterns.

1 P ← {} 2 foreach (u 1 , G u 1 I , contu 1 ) ∈ EnumCC(G I , * , σ I , 0, True) do 3 foreach (u 2 , G u 2 I , contu 2 ) ∈EnumCC(G I , * , σ I , 0, True) do 4 IAS ref ← IAS( * , u 1 , u 2 ) 5 foreach (c, G E , contc) ∈ EnumCC(G c E , * , σ E , 0, True) do 6 if oeϕ(c, u 1 , u 2 ) < σϕ then

Sampling (Dis)Agreement Patterns

DEBuNk returns the exact solutions according to the problem definition. Although relying 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 relies on the two major steps to sample patterns, depicted in Fig. 4:

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 more 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 advantage of the devised quality measures and the optimistic estimates , this being done to reward high quality patterns by giving them more chance to be sampled by the algorithm.

Frequency-Based Sampling (Step 1)

To sample patterns of the form p = (c, u 1 , u 2 ), we aim to draw description c, respectively u 1 and u 2 , from description space D E , respectively D I , with a probability proportional to their respective support size. To this end, we devise the algorithm FBS (Frequency-Based Sampling).

In the following, for any d ∈ D, ↓ d denotes the set of all descriptions subsuming d, i.e:

↓ d = {d ∈ D : 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 .

FBS generates a description d with a probability proportional to its frequency

P(d) = |G d |) d ∈D |G d | (
formally defined in proposition 5). To this end, FBS performs two steps as depicted in Algorithm 3.

FBS starts by drawing a record g from G (line 1) with a probability proportional to the number of descriptions d ∈ D covering g (i.e: | ↓ δ(g)|). To enable this, each record g ∈ G is weighted by w g = | ↓ δ(g)|. For now, we use d g to refer to δ(g). Knowing d g = (r g 1 , ..., r g m ), the weight

w g = | ↓ d g | = j∈[1,m] | ↓ r g j |
is the product of the numbers of restrictions subsuming each r g j . The size of | ↓ r g j | depends on the type of the related attribute a j : -categorical attribute: given that r g j corresponds to a value v ∈ dom(a j ), we have ↓ r g j = { * , v} thus | ↓ r g j | = 2. -numerical attribute: given that r g j corresponds to an interval [v, w] with v, w ∈ dom(a j ), we have ↓ r g j is equal to the number of intervals having a left-bound v ≤ v and a right-bound w ≥ w. More formally, ↓ r g j =

Algorithm 3: FBS(G)

Input: G a collection of records which may be 11 Cartesian product of the m lattices related to attributes conditions spaces forms a lattice [START_REF] Roman | Lattices and ordered sets[END_REF] {

G E or G I Output: a description d from D with P(d) = |G d | d ∈D |G d | 1 draw g wg from G with wg = | ↓ δ(g)| 2 draw d uniform(↓ δ(g)) 3 return d
[v, w] | v ≤ v ∧ w ≥ w}. Hence, the cardinal of this set is | ↓ r g j | = |{v ∈ dom(a j ) : v ≤ v}| × |{w ∈ dom(a j ) : w ≥ w}|.
-HMT attribute: given that r g j corresponds to a set of tags {t 1 , t 2 , ...t l } ∈ dom(a j ), with t k ∈ T and T a tree, the condition r g j can be conceptualized as a rooted subtree of T where the leaves are {t 1 , t 2 , ...t l }. Thus, ↓ r g j represents the set of all possible rooted subtrees of r g j . The latter cardinality can be computed recursively by starting from the root * using nbs(tree, root) = k 1 (nbs(tree i , neighbor i ) + 1) where neighbor i returns the child tags of a given root and tree i the subtree rooted on neighbor i .

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

P(d|g) = j∈[1,m] P(r j ) = 1 j∈[1,m] | ↓ r g j | = 1 | j∈[1,m] ↓ r g j | = 1 | ↓ d g | .
We now define the method used to uniformly draw a condition corresponding to an attribute a j , according to its type:

categorical attribute: given that ↓ r g j = { * , v} with v ∈ dom(a j ), it is sufficient to uniformly draw an element r j from { * , v}.

numerical attribute:

given that ↓ r g j = {[v, w] | v ≤ v ∧ w ≥ w},
to generate an interval [sv, sw] from ↓ r g j uniformly, one needs to uniformly draw a left-bound sv from the set {v ∈ dom(a j ) : v ≤ v} and a right-bound sw from the set {w ∈ dom(a j ) : w ≥ w}.

-HMT attribute: given that ↓ r g j represents the set of rooted subtrees of r g j , we have to uniformly draw such rooted subtrees. A first way is to generate all the possible rooted subtrees and then uniformly draw an element from the resulting set. This does not scale. Hence we devised another method, relying on a stochastic process using the aforementioned function nbs (which counts the number of subtrees rooted on some given node). The algorithm takes the root * as a starting tree. Next, the resulting subtree is augmented by a child c of * with a chance equal to the number subtrees of ↓ r g j containing c. That is nbs(r g j , * )-nbs(r g j -{c}, * ) nbs(r g j , * )

. Recursively, the algorithm continues from a drawn candidate child c. Proposition 6 Given the cardinality constraints C, every valid pattern p is reachable by the first step of Quick-DEBuNk. i.e. ∀p ∈ P : p satistifies C ⇒ P(p) > 0 (see Appendix A for proofs)

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.

Random Walk on Contexts (RWC)

RWC ( Algorithm 4) enumerates contexts of the search space corresponding to D E while considering closure and optimistic estimates. RW C takes as input two confronted groups of individuals described by u 1 ,u 2 for which it looks for relevant contexts (i.e., to form an (dis)agreement pattern) 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 appropriate, the closed description d is computed (line 4). The algorithm proceeds by evaluating the quality of pattern (line 5). If the quality exceeds the threshold σ ϕ , the pattern is valid and is hence yielded (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 in selecting a neighbor from N tE 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 = ∅). (u 1 , u 2 ) couple of confronted group descriptions of individuals; σ E threshold on support; ϕ the quality measure; σϕ quality threshold.

Output: yield valid patterns (c, u 1 , u 2 ) 1 NtE ← {} 2 foreach d ∈ η(c) do 3 if |G d E | ≥ σ E and oeϕ(d, u 1 , u 2 ) ≥ σϕ then 4 closure d ← δ(G d E ) 5 if ϕ(d, u 1 , u 2 ) ≥ σϕ then 6 yield closure d 7 else 8 NtE ← NtE ∪ {d} 9 if NtE = ∅ then 10 draw next ϕ(next, u 1 , u 2 ) from NtE 11 foreach cnext ∈ RWC( G I , G E , O, o , next, σ E , ϕ, σϕ, u 1 , u 2 ) do
(p) ≥ σ ϕ ⇒ ∃e ∈ G c E : ϕ({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 appended to the resulting pattern set if and only if it is not more specific of an already found pattern w.r.t. extents (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 by each pattern yielded by RWC, as long as there is no more general pattern in the current pattern set P (lines 14 -16). Otherwise, RWC is interrupted (line 18). The process is repeated as long as the time budget allows.

Algorithm 5: 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 local relevant (dis)agreement patterns 1 P ← {} 2 while executionTime < timebudget do

3 u 1 ← clo(FBS(G I )) 4 u 2 ← clo(FBS(G I )) 5 if |G u 1 I | ≥ σ I ∧ |G u 2 I | ≥ σ I then 6 c ← clo(FBS(G ≥σϕ E )) G ≥σϕ E = {e ∈ G E | ϕ({e}, Iu 1 , Iu 2 ) ≥ σϕ} 7 if |G c E | ≥ σ E ∧ oeϕ(c, u 1 , u 2 ) ≥ σϕ then 8 if ϕ(c, u 1 , u 2 ) ≥ σϕ 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 in our companion page12 .

Aims and Datasets

The experiments aim to answer the following questions: Yelp 15 is a social network dataset featuring individuals who rate (scores ranging from 1 to 5) places (stores, restaurants, clinics) characterized by their categories (H) and their 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 whether users are elites or not (C). This preprocessing has been done to allow the discovery of interpretable patterns. The same IAS ratings measure is used to analyze this dataset.

-
Openmedic 16 is a drug consumption monitoring dataset that has been recently made available by Ameli 17 . This dataset inventories the number of drug boxes (described by their ATC classification (H) ) yearly administered to individuals (2014, 2015 and 2016). Individuals are described with demographic information such as age group (C), gender (C) and region (C). In the qualitative results, we 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 attributes are very different, as well as the range of the numerical ones. To enable a fair comparison, we operate a (kind of) conceptual scaling [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF]. The attributes are "projected" to 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 with an interordinal scaling [START_REF] Kaytoue | Mining gene expression data with pattern structures in formal concept analysis[END_REF]. To a given set of values 4 shows the obtained comparable characteristics. Some questions we aim to answer require data for which the ground truth is known. Since it is notoriously difficult to obtain such data, we designed an artificial behavior data generator. The generator works as follows. It first generates nb hidden patterns (dis)agreement patterns. Each pattern is represented by two group descriptions (u 1 , u 2 ) and a context (c) where u 1 , u 2 and c are defined over random categorical descriptions and are of random size. For each pattern, the extent is generated (i.e., context support size entities for the context and the two groups involving group support size individuals). The extents are generated as follows: first, a random description ds is uniformly drawn from D E (resp. D I ). Next, support size records are generated, which have a description equal to or subsumed by ds. This process is repeated for each component of the pattern so as to built nb hidden patterns (dis)agreement patterns. Note that the pattern generation process avoids overlapping between groups and contexts between differents patterns. These patterns describe conflictual situations, i.e., the individuals of one group in the pattern context express a voting outcome which is different from the other group' voting outcome. Conversely, the two groups are in agreement in the usual case, i.e., their votes over the entities outside the pattern context are similar. To achieve this, for each planted pattern (c, u 1 , u 2 ) and for each entity e ∈ G E , a random outcome os is drawn from the pool of possible outcomes (in here we consider O = {Yes, No}). Subsequently, each member comprising G u1 I votes os for the entity e. Accordingly, individuals from G u2 I cast a different outcome, if e is described by the context c. Otherwise, they cast the same outcome os. Once these patterns are generated, the rest of the dataset is generated by adding entities and individuals randomly while preserving the exceptionality of the patterns (i.e., the patterns must remain the most general exceptional patterns) till the desired size of the dataset is reached (i.e. |G E | = nb entities and |G I | = nb individuals). As described, the hidden patterns are pure. A last step enables to add noise within the patterns. For each pattern, the expressed outcome of individuals are randomly replaced with a noise rate probability. Similarly, noise is added outside the patterns. Eventually, to get as close as possible to real-world behavioral dataset, we add sparsity in the data. To perform this task, each outcome of each pair (e, i) ∈ G E × G have a probability of data sparisty to be removed from the generated artificial behavioral dataset.. The parameters used are summarized in Table 5.

[v 1 , v 2 , ...v n ], we associate 2n items {≤ v 1 , ≤ v 2 , ... ≤ v n , ≥ v 1 , ≥ v 2 , ... ≥ v n }.
The rest of this section is organized as follows. We qualitatively compare DEBuNk and Quick-DEBuNk with state-of-the-art methods on artificial data (subsect. 6.2). We then study their ability in noisy data (subsect. 6.3). A full performance study of our two algorithms is reported in subsect. 6.4. Qualitative results on the four real-world datasets are provided in subsect. 6.5. A discussion on the limitations of our algorithms closes this section.

Comparison to state-of-the-art techniques

To put DEBuNk and its sampling alternative Quick-DEBuNk to the test, we investigates the ability of classical SD/EMM techniques to tackle the problem of discovering exceptional disagreement among groups of individuals in Section 6.2.1 and we compare their efficiency and effectiveness against our first attempt [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF] implemented by DSC Algorithm in Section 6.2.2.

Comparison to SD/EMM methods

We aim to study how the SD/EMM methods are able to discover relevant (dis)agreement patterns. SD algorithms available in public implementations (e.g., Vikamine [START_REF] Atzmueller | Vikamine-open-source subgroup discovery, pattern mining, and analytics[END_REF], Cortana [START_REF] Meeng | Flexible enrichment with cortana -software demo[END_REF], PySubgroup [START_REF] Lemmerich | pysubgroup: Easy-to-use subgroup discovery in python[END_REF]) only consider one flat table with a target attribute. However, behavioral datasets involve three relations (Entities, Individuals, Outcomes) which are all processed by DEBuNk and its sampling alternative Quick-DEBuNk to discover the interesting (dis)agreement patterns. To handle the problem we defined with a classical SD algorithm, we need to preprocess the data. We discuss and compare several problem adaptations. SD-Majority: SD to discover contextual disagreements with the majority. The most direct way to apply SD on behavioral data is to consider the discovery of groups of individuals who express disagreement with the majority vote. This enables to discover patterns (c, g 1 ) where c is a context describing a set of entities and g 1 is a description of a group of individuals. To this end, we preprocess the behavioral data to obtain a Flat Behavioral Dataset (FBD) with a single table and a singe target class SAME AS MAJORITY as following: (1) we combine the entities and individuals tables using a join operation with the outcomes collection. [START_REF] Amelio | Analyzing voting behavior in italian parliament: Group cohesion and evolution[END_REF] We compute the majority vote by aggregating the votes expressed on each entity. [START_REF] Amer-Yahia | Exploring rated datasets with rating maps[END_REF] We use this information to extend each record in the newly generated FBD with the attribute SAME AS MAJORITY which is equal to +, indicating that the individual voted in agreement with the majority in the considered entity. Otherwise SAME AS MAJORITY is equal to -. Example of FBD after such preprocessing is given in Table 6. Having this FBD augmented with the target class SAME AS MAJORITY offers the possibility to run common SD techniques to identify subgroups with a high prevalence of disagreement with the majority (Target label = -). The most adapted interestingness measure in this case is the precision gain [START_REF] Fürnkranz | Foundations of rule learning[END_REF], i.e. P recision(subgroup)α -, which is high when there is a high disagreement in a subgroup compared to the disagreement observed in the full dataset. Note that this model does not fit perfectly our problem setting. It enables only the discovery of bi-set patterns (c, g 1 ) rather than the desired three-set patterns (c, g 1 , u 2 ). Nevertheless, highlighting this type of pattern may help to partially identify interesting (dis)agreement patterns in a behavioral dataset. Furthermore, this adaptation does not takes into account the usual behavior of the group against the majority. This might clearly lead to the discovery of obvious patterns highlighting the individuals that are known to be a systematic opposition. Exceptional Contextual Subgraph Mining to discover contextual disagreement between two groups. Applying SD in the two aforementioned modelings does not allow to take into account the usual inter-group agreement in the model. A way to overcome this issue is to model the behavioral dataset as an attributed graph and looking for exceptional contextual subgraphs [START_REF] Kaytoue | Exceptional contextual subgraph mining[END_REF].

Entities

The so-called COSMIC algorithm is rooted in SD/EMM and aims at discovering contextual subgraphs whose edges have weights larger than expected.

To this end, we transform the behavioral dataset to the Cartesian product G E × G I × G I extended with SAME VOTE attribute like in SD-Cartesian formalization. This table is then used to build a bipartite graph where each side represents the collection of individuals G I and an edge is instantiated between two vertices (individuals) for each entity on which the two individuals expressed conflicting outcomes. The set of transactions from G E × G I × G I where two individuals are disagree are associated to the edge between the two corresponding vertices (see Fig. 5). Once this transactions set obtained, COSMIC algorithm can be used to obtain exceptional contextual subgraphs. Note that, in this problem setting, an exceptional contextual subgraph corresponds to two groups of individuals which exhibit a higher disagreement rate in the considered context compared to the disagreement expected in a similar sized subgraph. Several interestingness measures have been proposed in the COSMIC framework [START_REF] Bendimerad | Contextual subgraph discovery with mobility models[END_REF][START_REF] Kaytoue | Exceptional contextual subgraph mining[END_REF]. For the aim of this study, the lift measure is the most adapted: ϕ(S) = P(S|C) P(S) with S is the connected contextual subgraph induced by the selection performed by the description C. Note that: P(S|C) is the probability that a random drawn edge from all the edges in the full graph supporting the selection C falls in the induced contextual subgraph, P(S) is the relative weights in terms of the number of edges of the full subgraph S (the subgraph with the most general context). Note that a post-processing is necessary to transform exceptional contextual subgraphs into (dis)agreement patterns (c, u 1 , u 2 ). Applying contextual subgraph mining given this modeling has some limitations: [START_REF] Hasan | Output space sampling for graph patterns[END_REF] the expected disagreement between two groups is computed from all the individuals instead of the individuals of the two groups. This can lead to the discovery of obvious patterns. (2) it considers as an input a transaction dataset computed from the Cartesian product G E × G I × G I which limits its usage, even for relatively small behavioral dataset.

We aim to compare how state-of-the-art methods perform in this three modelings and compare them to DEBuNk and Quick-DEBuNk. To this end, we generated 81 artificial dataset with 3 hidden patterns by varying several parameters (see Fig. 6). Note that the behavioral datasets are relatively small to be sure to obtain results for each modeling, especially ones that requires to build a Cartesian product. For SD-Majority and SD-Cartesian modelings, we used PySubgroup [START_REF] Lemmerich | pysubgroup: Easy-to-use subgroup discovery in python[END_REF] to discover subgroups for the following reasons: the implementation is available online 18 as well as the easiness of its use. We ran the exhaustive search algorithm BSD [START_REF] Lemmerich | Fast discovery of relevant subgroup patterns[END_REF] which is tailored to find relevant subgroups [START_REF] Garriga | Closed sets for labeled data[END_REF], this choice is also motivated by the fact that the selected interestingness measure is the Precision gain. For the attributed graph modeling, we used an implementation of COSMIC algorithm provided by the authors [START_REF] Kaytoue | Exceptional contextual subgraph mining[END_REF]. 1 to an augmented graph and its corresponding transactions set according to the observed discords.

To evaluate the ability of the different approaches of uncovering planted patterns, we 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 provide similar insights about changes of inter-group agreement.

sim P (p, p ) = J(G c E , G c E ) × 1 2 . J(G u 1 I , G u 1 I ) + J(G u 2 I , G u 2 I ) with J(G, G ) = |G ∩ G | |G ∪ G | .
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 )) .
For comparing two pattern sets P , P returned by respectively DEBuNk and Quick-DEBuNk, we use an F 1 score defined as follows.

F 1 (P, P ) = 2 • precision(P, P ) • recall(P, P ) precision(P, P ) + recall(P, P ) , A similar measure to the recall has been proposed by the authors in [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 the ground-truth patterns. We extend this measure with the precision to evaluate not only that all the hidden patterns have been discovered by an algorithm (i.e. recall=1.) but also the conciseness of the returned set (i.e. precision=1 if and only if all returned patterns are actually present in the behavioral dataset).

We report in Figure 6a the comparative experiments between DEBuNk, Quick-DEBuNk, SD-Cartesian, SD-Majority and COSMIC in terms of their ability to retrieve each planted pattern in synthetic behavioral datasets. We report for each method the average similarity (over the 81 artificial data) between one of the three hidden patterns and its nearest representative in the result set. As expected, DEBuNk and Quick-DEBuNk outperforms other approaches. Moreover, the order between the approaches/modelings is sound. Majority-SD has the worst results due to the fact that this method, in the best case scenario, is only able to identify two of the three restrictions of a (dis)agreement pattern which impact on its performance. COSMIC performs slightly better than its alternative SD technique over the Cartesian product G E × G I × G I thanks to a more sophisticated model to capture the usual behavior.

Figure 6b summarizes the results obtained after running the five approaches. For a fair comparison (i.e., the problem of setting the good thresholds), we report the average F-Score of the only top-10 results for each approach. We observe that DEBuNk and Quick-DEBuNk achieves to return high-quality results compared to the other approaches. Interestingly, COSMIC adaptation is of less quality than SD-Cartesian adaptation when analyzing both their conciseness and exactitude in terms of hidden pattern identification. Finally SD-Majority performs the worst due to its fundamental difference with the other approaches when comparing the provided patterns format.

Comparison to DSC

In this subsection, we report the results of experiments conducted to compare DEBuNk against first attempt [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF] implemented by algorithm DSC.

We recall that DSC solves the problem of discovering top-k patterns that elucidate exceptional (dis)agreement between groups of individuals. In addition, as aforementioned in Section 2, for a sufficiently large k, DSC solves the core problem tackled in this paper limited to the two first conditions. To compare between DEBuNk and DSC, we designed experiments to answer to the two following questions. Note that, we disable the aggregation dimension parameter for DSC to obtain comparable pattern sets. Q1. How concise is the patterns set provided by DEBuNk compared to the one provided by DSC? Q2. How diversified is the patterns set, limited to k patterns, provided by DEBuNk compared to the one provided by DSC?

In order to answer to (Q1), we evaluate the number of patterns returned by DEBuNk and DSC when looking for the complete pattern set P (i.e. k sufficiently large for DSC). For this, we run both methods on EPD8 with various19 quality thresholds σ ϕ and descriptive attributes A E , A I . Figure 7 reports the results of these experiments. Results demonstrate that DEBuNk compresses considerably 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). In average, DSC returns ×38 more patterns than DE-BuNk. Moreover, DEBuNk achieves better performance than DSC in terms of run time . Thanks to (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 discussed above clearly demonstrated the fact that in such setting DSC returns an overwhelmingly large results set. To tackle such problem, DSC implemented a top-k algorithm to control the size of the provided 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.

In order to fairly evaluate the diversity of patterns returned by both DSC and DEBuNk (Q2). We run both algorithms for several parameters20 and compare the size of the datasets regions covered by both returned patterns set. This quantity can be captured by the number of outcomes covered by a results set, that is 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 resolved 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.

|o[P k ]| = |{(i, e) ∈ G I × G E s.t. o(i,
Figure 8 sums up the results of the experiments. Clearly, DEBuNk' k-sized pattern set covers larger (and different) parts of the dataset compared to DSC' 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.

Robustness to noise and ability to discover hidden patterns

We now study the ability of DEBuNk and Quick-DEBuNk to discover hidden patterns for larger behavioral datasets as well as their robustness to noise. To this end, we carried out DEBuNk and Quick-DEBuNk over several artificial datasets varying the noise rate from 0 to 0.8. The results illustrated in Figure 9 demonstrates that the exhaustive search approach DEBuNk is able to discover almost exclusively all the hidden patterns (F 1 Score > 0.8) even jf the noise rate is rather high (≤ 0.6). Indeed when the noise rate is substantially high, DEBuN k does not retrieve the noisy hidden patterns. This clearly results from the evidence that several planted patterns disappear in the underlying artificially generated data after adding too much noise. This is an advantage for DEBuNk since the quality threshold is able to remove nonsensical patterns from the final set. In contrast, from these experiments, we observe that Quick-DEBuNk less robust to noise than DEBuNk. The performance of Quick-DEBuNk in terms of finding hidden patterns decreases faster with regard to the noise rate compared to DEBuNk. This is mainly due to the random walk procedure (RWC) which considers other sub search space than the one actually containing a hidden context as the noise reduces the quality of its subsuming parents. Still, it is worth mentioning that Quick-DEBuNk is able to retrieve partially planted patterns even when the noise is rather high. Interestingly, the sampling approach achieves a comparable precision to the exhaustive approach, this demonstrates that most of returned patterns are valid.

6.4 Performance study

Efficiency of closure operators and optimistic estimates

To evaluate the efficiency of closure operators and optimistic estimates, we resolve to 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, Basline only pushes the anti-monotonic constraints. The second baseline, dubbed Base-line+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 this experiments, we interrupt a method if its execution time exceeds ten hours. Figures 10,[START_REF] Boley | Formal concept sampling for counting and threshold-free local pattern mining[END_REF] Experiments show evidence that the closure operator and the canonicity tests performed by EnumCC are effective as they substantially reduce the number of evaluated patterns. Additionally, DEBuNk is about one order of magnitude faster than 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. Additional performance experiments on Openmedic are reported in Appendix B.

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 which entities are characterized respectively by a hierarchy of 347 tags and 1175 tags. 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 13 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 explicit 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 conduct the study 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) to 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 13 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. Figures 14,15 and 16 report the behavior of DEBuNk when run on EPD8, Movielens and Yelp. Clearly, the number of evaluated patterns and the execution time increase with regards to the size of description spaces D I and D E . The reported experiments confirm that pushing monotonic constraints (i.e. supports threshold σ E , σ I ) improves drastically the efficiency of DEBuNk. Finally, a greater 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 parliament, Movielens and Yelp datasets the overall observed inter-group agreement between groups of individuals is rather consensual. Similar results where observed when carrying out the experiments on Openmedic dataset. For more details, see Appendix B. Since it is impossible to provide a ground-truth over real-world behavioral dataset, we evaluate the efficiency of Quick-DEBuNk over these type of datasets by comparing its results set against the one returned by the exhaustive search algorithm DEBuNk, this according to different time budgets. quality patterns. Interestingly, some differences can be observed from one to another dataset. For instance, Quick-DEBuNk is less efficient on 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 3) which might impede random walk step RW C for finding high quality patterns.

We investigate also the empirical distribution from which the patterns are sampled from when using Quick-DEBuNk. This requires the true distribution of the qualities of valid patterns in the corresponding datasets. In this respect, we run DEBuNk by disabling the generality condition (see Problem definition). This is done to make 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. Clearly, we observe from the empirical distributions depicted in Figures 17b,18b and 19b that Quick-DEBuNk rewards high quality patterns by giving them more chance to be sampled.

Finally, to evaluate the importance of RWC (Random Walk on Contexts) step in Quick-DEBuNk, we perform the same experiments with the same time budgets with RWC step disabled. In such 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× less 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.

Qualitative Results

We now focus on reporting example patterns discovered by the algorithm DE-BuNk. We demonstrate the actionability of the provided patterns with 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 the 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) Eventually, we give some example patterns reporting substantial differences in medicine consumption behavior between groups of individuals. Such results can be leveraged by epidemiologists to study comparative prevalence of sicknesses among different groups of individuals.

Study of Collaborative Rating Data

Table 8 describes some patterns returned by DEBuNk when applied over 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 Student and Health professionals agree 74% of the time, they tend to disagree for Horror and Comedy Movies released between 1986 and 1994 (e.g. Evil Dead II, Braindead ). Figure 20 illustrates the usual and the contextual ratings distribution of each of the two groups. We observe from this rating distributions, that the students like the movies highlighted by the pattern, whereas the healthcare professionals dislike them.

In Table 9, we present some results provided by DEBuNk over the Yelp dataset. The groups of individuals are labeled by the size of their friend network and their seniority in the Yelp platform. Notice that additional demo- graphic 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, the second pattern in Table 9 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. University Urgent Care, Las Vegas Urgent Care), contrary to the usual, where these two groups roughly share the same opinions about places in general (81% of the time). Figure 21 gives the overall rating distribution corresponding to the second pattern. Note that in Table 9, the values shown in columns (|G u1 I |, |G u2 I |) designating respectively the size of the groups u 1 , u 2 correspond to the number of their composing aggregated groups. For instance, the (Senior, Medium) group is made up of two high granularity groups (elite and non-elite) which in reality is comprised of 44927 registered users.

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

Analysis of the Voting Behavior in the European Parliament Dataset

Table 10 exposes patterns obtained by DEBuNk where the aim is to find contexts (subsets of ballots) that lead groups of parlementarians (labeled by their countries and their corresponding date of accession to the European Union) to strong disagreement compared to the usual observed inter-group agreement. Such analysis can be valuable to political analysts and journalists as it ([1973, 1973] enables to uncover subjects/thematics of votes on which countries have divergent points of view. For instance, the second pattern in Table 10 illustrated in Figure 22, states that the ballots concerning theme 4.15.05 (Industrial Restructuring, job losses, EGF) lead to strong disagreements of parlementarians from the United Kingdom with their peers. In Figure 22, we choose to visualize the second pattern by a similarity matrix where each cell represents the similarity between two countries. This can be seen as post-processing step where the enduser chooses to enrich the pattern with more related information (similarities between other countries). Such augmented visualization brings more context to the pattern. While the second pattern conveys that UK parlementarians are in strong disagreement with their peers, the visualization goes beyond by reporting that all other countries formed a coalition against UK.

(c, u1, u2) |G c E | |G u 1 I | |G u 2 I | o(i, e) ϕ dissent 1
Algorithms elaborated in this work also enable the discovery of consensual subjects, thanks to the quality function ϕ consent . In Table 11 , we report patterns where groups of parliamentarians agree more than what is observed in general. For example, pattern 1 of Table 11 shows that while Socialists and Democrats (S&D -left-wing) parlementarians are usually in disagreement (IAS voting = 0.41) with European Conservatives and Reformists (ECRright-wing), they tend to have convergent opinions (IAS voting = 0.9) on ballots concerning theme 6.20.03 (bilateral agreement and relations with countries external to the union, e.g. Implementation of the Free Trade Agreement between the European Union and the Republic of Korea). In Figure 23, we illustrate the similarities between political groups for pattern 3 reported in Table 11. It is worth to note that, as part of a collaboration with political journalists, we provide an online tool 21 , dubbed ANCORE [START_REF] De Lacombe | Analyse de comportements relatifs exceptionnels expliquée par des textes : les votes du parlement européen[END_REF], which makes it possible to analyze European parliament voting sessions. 11. The left matrix depicts the agreement observed in general between political groups when considering all ballots. The right matrix corresponds to the inter-group agreement between groups for the context pointed out by pattern 3. We observe that group ENF is in disagreement with ALDE, PPE and S&D who hold 63% of the seats in the 8 th European Parliament. The context of Pattern 3, which mainly covers EGF (European Globalisation Adjustment Fund) ballots, suggests an agreement between group ENF and the majority.

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

Illnesses Prevalence on the Basis of Medicine Consumption

One interesting analysis task to be carried out on Openmedic Dataset is to look for subgroups of drugs where the ratio of consumption between two groups of individuals is substantially different than the one usually observed. For instance, we found that while Females takes 1.32× more drugs than Males in overall terms, this ratio icreases up to 5× when considering drugs prescribed for Hyperthyroidism (see Pattern 3 in Table 12). These results are similar to what reports an epidemiology study by Wang et Al. in [START_REF] Wang | The epidemiology of thyroid disease and implications for screening[END_REF]. Such task can provide insightful hypothesis regarding some sicknesses prevalence for particular groups of individuals. In the behavioral dataset Openmedic, the outcomes of individuals are depicted by numerical values reporting the count of drug boxes. As we are interested in characterizing the inter-group 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)
This ratio falls under the definition of IAS considered in Definition 5 as it can be rewritten in the form of a weighted average. 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 )
Drug boxes are labeled by tags in the ATC 22 classification system. We aim at leveraging the medical consumption differences between groups of individuals to investigate the comparative prevalence 23 of illnesses between gender groups. Table 12 gives an example of patterns returned by DEBuNk when applied on Openmedic. For instance, Pattern 4 states that, for drugs prescribed for Gout sickness 24 , 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 24, report details on the differences between the two gender groups in terms of population size and number of medicines 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,

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 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. Remind that 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 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 subset 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 | Multi-objective group discovery on the social web[END_REF]. This makes it possible the discovery of 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.

Similarly, the two past decades have witnessed an increasing emergence of Open Government Data25 (OGD) promoting transparency and accountability in public institutions. Consequently, many researchers 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 parliamentin 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. In the same spirit, [START_REF] Grosskreutz | Subgroup discovery for election analysis: a case study in descriptive data mining[END_REF] investigates the voting behavior of citizens instead of politicians relying on subgroup discovery. Our work goes further and supports the discovery of new insights in such data.

Monitoring the disease prevalence is an important task. Many researchers dedicated their effort to analyze the prevalence of diseases considering different sources of data. In [START_REF] Orueta | Monitoring the prevalence of chronic conditions: which data should we use?[END_REF], the authors 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.

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 absolutely huge and non-manageable for a human expert. To overcome this limitation, many approaches that can effectively sample the pattern space for interesting patterns have been proposed for a decade. These methods address some 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][START_REF] Boley | Formal concept sampling for counting and threshold-free local pattern mining[END_REF][START_REF] Hasan | Output space sampling for graph patterns[END_REF]. In [START_REF] Dzyuba | Flexible constrained sampling with guarantees for pattern mining[END_REF], the authors 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 [START_REF] Boley | Formal concept sampling for counting and threshold-free local pattern mining[END_REF][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 [START_REF] Boley | Formal concept sampling for counting and threshold-free local pattern mining[END_REF]. 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 step 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 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. The exceptional (dis)agreement patterns discovery 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 defined DEBuNk, a branch and bound algorithm which takes benefit from closure operators, properties of some descriptions space (as for HMT attributes) and (tight) optimistic estimates to efficiently enumerate the patterns. Alternatively, we devised Quick-DEBuNk, an algorithm that does not return the complete set of (dis)agreement patterns anymore but rather samples the space of patterns. We investigated several quality measures to assess inter-group agreement. The extensive experimental study we reported demonstrates the efficiency of our algorithms as well as their ability to provide new insights in three case-studies: (i) the investigation of contexts that impact the inter-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 sup-port the discovery of contexts that divide a political group. This requires the definition and the integration of adapted similarity measures into the IAS (Inter-group 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 analyse behavioral datasets with large collections of entities (e.g., Yelp), tackling large collections of individuals still remains challenging to assure 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. The study of this dynamics makes it possible to discover new insights in behavioral data.

A Appendix: Proofs of Theorems and Propositions

Before giving the proof of the proposition 1 we present the following lemma.

LB(G d E , G u 1 I , G u 2 I ) ≤ IAS(G d E , G u 1 I , G u 2 I ) (10)
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. we × α(e)

c d ⇒ LB(G c E , G u 1 I , G u 2 I ) ≤ LB(G d E , G u 1 I , G u 2 I ) (11)
Similarly, if we reorder entities e in descending order w.r. we Hence, given ( 14) and ( 15) 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: 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
∃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

B Appendix: Additional Performance Experiments for Openmedic

In this appendix we report additional performance experiments over OpenMedic. Figure 25 depicts a comparative performance study between the baseline approach performing an exhaustive search without using closure operators, a Baseline+Closed approach and DEBuNk. In contrast with what we observed with the comparative performance experiments over EPD8, Yelp and Movielens, the performance gain for Openmedic between the three method is negligible. This is mainly due to the structure of OpenMedic Data and the type of study we conduct on, more precisely: [START_REF] Hasan | Output space sampling for graph patterns[END_REF] the ratio between closed description/all description is rather small, (2) the used IAS is a weighted average with a very scattered distribution of weights, (3) the optimistic estimate proposed for weighted averages IAS measures is not tight. Finally, we report in figure 27 a comparative performance between DEBuNk and Quick-DEBuNk over Openmedic dataset. In the first stages, the sampling algorithm achieves to find a good portion of the patterns which are returned by the exhaustive search algorithm DEBuNk. However, the method seems to converges less slowly, compared to the its performance in the other datasets, to the full results set. This results from the fact that the quality measure ϕ ratio applied over openmedic is not symmetric, which requires to the algorithm to look twice for each couple of confronted groups of individuals, since the order matter between the two groups for the used interestingness measure.

Fig. 1 :

 1 Fig. 1: Overview of the task of discovering exceptional (dis)agreement between groups 4 DEBuNk stands for Discovering Exceptional inter-group Behavior patterNs 5 http://contentcheck.liris.cnrs.fr

Definition 2 ( 1 , and u 2 u 2 . 1 I

 2121 (Dis)Agreement Pattern) A (dis)agreement pattern is a triple p = (c, u 1 , u 2 ) where c ∈ D E is a context and (u 1 , u 2 ) ∈ D 2 I are two group descriptions. P = D E × D I × D I denotes the pattern space. The extent fulfilling 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 ). Several patterns may share the same extent. If ext(p) = ext(p ), patterns p and p are said to be equivalent w.r.t their extension, denoted as p ≡ G E ,G I p . Patterns are partially ordered in P by a specialization relationship. A description d 1 is a specialization of a description d 2 , denoted d 2 d 1 , iff d 1 ⇒ d 2 . Consequently, a pattern p is a specialization of a pattern p, denoted p p , iff c c , and u 1 u It follows that ext(p ) ⊆ ext(p) (i.e. G c E ⊆ G c E and G u ⊆ G u1 I and G u 2

  |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).

Definition 3 (

 3 Outcome Aggregation Operator θ) An aggregation operator is a function θ : 2 G I × G E → D which transforms the outcomes of a group of individuals G u I over one entity e ∈ G E (i.e. {o 6 (i, e) | i ∈ G u I }) into a value in a domain D (e.g. R, categorical values). Definition 4 (Similarity between aggregated outcomes sim) Function sim : D × D → R + assigns a real positive value sim(x, y) to any couple of aggregated outcomes (x,y).

Algorithm 1 :

 1 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. 3 :

 3 Fig. 3: Illustration of the infimum operator h

  ) = sim(θ(G u1 I , e), θ(G u2 I , e)) w e = w(e, G u1 I , G u2 I )

7 8 else 9 IAS 11 if quality ≥ σϕ then 12 pnew ← (c, u 1 , u 2 ) 13 if 14 P 15 contc ← False Prune the sub search space 16 if ϕ is symmetric and u 1 = u 2 then 17 break

 891112113141516117 contc ← False Prune the unpromising sub-search space under c ref ← IAS(c, u 1 , u 2 ) 10 quality ← ϕ(c, u 1 , u 2 ) computed using IAS ref and IAScontext p old ∈ P | ext(pnew) ⊆ ext(p old ) then ← (P ∪ pnew) \ {p old ∈ P | ext(p old ) ⊆ ext(pnew)} Prune the sub search space

Fig. 4 :

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

Proposition 5 A

 5 description d ∈ D has a probability of being generated by FBS equal to P(d) = G d d ∈D |G d | . (see Appendix A for proofs) F BS 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 5) 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).

Algorithm 4 :

 4 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;

12 yield cnext 5 . 3

 1253 Quick-DEBuNk Quick-DEBuNk (Algorithm 5) 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 support constraint (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 ϕ

  Average similarity between the planted patterns and their representatives returned by each method.DEBuNk Quick-DEBuNk COSMIC SD-Cartesian SD-Majority 0Boxplots of F-score comparing the top-10 discovered patterns set by each method on each generated artificial data and the corresponding ground truth.

Fig. 6 :

 6 Fig. 6: Comparative qualitative performance study between DEBuNk (σ E = 3, σ I = 3, σϕ = 0.5 and the quality measure ϕ dissent ), Quick-DEBuNk (same parameters as DEBuN k with timebudget = 5 seconds), SD-Majority (resultSetSize= 50, i.e. Top-50), SD-Cartesian (resultSetSize= 25, i.e. Top-25) and Cosmic (Default parameters) performed over 81 artificial behavioral data with 3 hidden patterns by varying the number of individuals in [100, 125, 150], the number of entities in [100, 150, 200], the sparsity factor in [0., 0.25, 0.5] and the noise in [0., 0.2, 0.4].

  e) is expressed}| with P k an arbitrary 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 DEBuN k . Next, we draw 100 k-sized samples drawn uniformly from the obtained P DEBuNk and then compute the average |o[P k

Fig. 7 :

 7 Fig. 7: Comparison between DEBuNk and DSC for the task of discovering the complete set of the desired patterns. Experiments consider the full EPD8 Dataset with the following default parameters: |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. 8 :

 8 Fig. 8: Comparison between DEBuNk and DSC (top-k) for the task of discovering ksized pattern set. Experiments consider the full EPD8 Dataset with the following 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. 9 :

 9 Fig. 9: Efficiency of DEBuNk (σ E = 7, σ I = 7, σϕ = 0.5 and ϕ dissent ) and Quick-DEBuNk (σ E = 7, σ I = 7, σϕ = 0.5, timebudget = 3 mn and ϕ dissent ) performed over 21 behavioral artificial data generated with the following default parameters (|G E | = 2000, |G I | = 500, |A E | = |A I | =3, size dom entities attributes = size dom individuals attributes =4, nb hidden patterns =5, context support size =10, group support size =10).

  and 12 report the execution time and the number of evaluated patterns by each of the three methods (i.e. Baseline, Base-line+Closed, DEBuNk) when carried out on respectively EPD8, Movielens and Yelp datasets.

Fig. 10 :Fig. 11 :Fig. 12 :

 101112 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. 13 :

 13 Fig. 13: 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 .

Fig. 14 :Fig. 15 :

 1415 Fig. 14: Effectiveness of DEBuNk over EPD8 according to the sizes of E, I, D E , D I , the supports and quality measures thresholds. Considering by default |G E | = 4161, |G I | = 958, |Outcomes| = 750k, |A E | = 3, |A I | = 6. σ E = 40, σ I = 10, σϕ = 0.5 and ϕ dissent .

Fig. 16 :

 16 Fig. 16: Effectiveness of DEBuNk over Yelp Dataset according to the size of E, I, D E , D I , the supports and the quality measures thresholds. Considering by default the full dataset. σ E = 50, σ I = 1, σϕ = 0.5 and the quality ϕ dissent

Fig. 17 :Fig. 18 :Fig. 19 :

 171819 Fig. 17: Efficiency of Quick-DEBuNk compared to DEBuNk over EPD8. Parameters used are σ E = 40, σ I = 10, σϕ = 0.5 and ϕ dissent . The red line in each figure correspond to the required time by DEBuNk to perform an exhaustive search.

  (dis)agreement patterns discovered over Movielens considering by default the full dataset, |A E | = 2, |A I | = 1, σ E = 5, σ I = 10 and σϕ = 0.4.

Fig. 20 :

 20 Fig. 20: 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 highlighted by pattern 1

  (dis)agreement patterns discovered over Yelp considering by default the full dataset, |A E | = 2, |A I | = 2, σ E = 10, σ I = 1 and σϕ = 0.4.

Fig. 21 :

 21 Fig. 21: Pattern 2 Illustration -distribution of ratings of individuals constituting the group of Yelp user registered in between 2010-2015 having a large friend network versus distribution of ratings of individuals constituting the group of Yelp users registered before 2010 having a medium friend network. Left figure corresponds to the usual distribution observed over all Yelp places. Right figure corresponds to the contextual distribution observed over Nevada's Internal Medicines Places.

Table 10 :

 10 Top-5 w.r.t. number of expressed outcomes (o(i, e) column) of Relevant (dis)agreement patterns discovered over EPD8 considering by default the full dataset, |A E | = 1, |A I | = 2, σ E = 25, σ I = 1 and σϕ = 0.5 using ϕ dissent . It is important to note that we choose carefully σ E ≥ 25 to reach subgroups of the third level of the themes hierarchy which on average contain 25 ballots.

Fig. 22 :

 22 Fig. 22: Illustration of Pattern 2 reported in Table 10. Left matrix depicts the inter-group agreement observed in general between countries when considering all ballots. The right matrix correspond to the itner-agreement between countries for the context pointed out by Pattern 1 = (['4.15.05 Industrial restructuring, job losses and EGF'], UK, *)

Table 11 :

 11 Top-5 w.r.t. number of expressed outcomes (o(i, e) column) of relevant (dis)agreement patterns discovered over European Parliament Dataset considering by default the full dataset, |A E | = 1, |A I | = 1, σ E = 15, σ I = 1 and σϕ = 0.4 using ϕconsent.

Fig. 23 :

 23 Fig. 23: Illustration of pattern 3 reported in Table11. The left matrix depicts the agreement observed in general between political groups when considering all ballots. The right matrix corresponds to the inter-group agreement between groups for the context pointed out by pattern 3. We observe that group ENF is in disagreement with ALDE, PPE and S&D who hold 63% of the seats in the 8 th European Parliament. The context of Pattern 3, which mainly covers EGF (European Globalisation Adjustment Fund) ballots, suggests an agreement between group ENF and the majority.

IAS ratio (c, u 1 , u 2 u 1 I , G u 2 I

 1212 ) × 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

Fig. 24 :

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

  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.

Lemma 1 Proof (Lemma 1 )b

 11 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 iUsing the same notations of the lemma, we know that: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 i ≥ (n -k) × k × a k × b n -k) × k × a k × b k b ican be easily proved following the same line of reasoning of the proof of the first part of the inequality. Proof (Proposition 1) By a straightforward application of Lemma 1 we obtain for any d s.t. |G d E | ≥ σ E the following inequality.

e c 1 .α(e c 1 ) ≤ w e c 2 .α(e c 2 )w e d 1 .α(e d 1 ) ≤ w e d 2 .α(e d 2 )

 11221122 This results from c d ⇒ G d E ⊆ G c E . Hence, if we reorder values of G c E and G d E where G c E = {e c 1 , ..., e c |G c E | } and G d E = {e d 1 , ..., e d ≤ ... ≤ w e c σ E .α(e c σ E ) ≤ ... ≤ w e c ≤ ... ≤ w e d σ E .α(e d σ E ) ≤ ... ≤ w e d d E ⊆ G c E , it is clear that: ∀i ≤ σ E | w e c i .α(e c i ) ≤ w e d i .α(e d i ). Having that m(G c E , σ E ) = {e c 1 , ..., e c σ E } and m(G d E , σ E ) = {e d 1 , ..., e d σ E }, it follows that: e∈m(G c E ,σ E ) we × α(e) ≤ e∈m(G d E ,σ E )

u 2 I ) Proof (Proposition 4 )

 4 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 .It follows from the fact that M (G c E , σ E ) ⊆ G c E :

u 2 ILemma 2 Proof (Proposition 5 )

 225 ) = ϕ 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. 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 : d δ(g)} and for d ∈ D, we have G d = {g ∈ G | 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) = g∈G d 1 | ↓ δ(g)| × | ↓ δ(g)| i∈G | ↓ δ(i)| weight wg normalized = |G d | g∈G | ↓ δ(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 | × |G u 2 I | and Z = p ∈P |ext(p )| a normalizing factor.

Fig. 25 :

 25 Fig. 25: Effectiveness of DEBuNk over Openmedic Dataset considering |G E | = 12219, |G I | = 78, |Outcomes| = 500k, |A E | = 1, |A I | = 3, σ E = 5, σ I = 1, σϕ = 5 and the quality measure ϕ ratio

Fig. 26 :Fig. 27 :

 2627 Fig. 26: Effectiveness of DEBuNk over Openmedic Dataset according to the sizes of E, I, D E , D I , the supports and quality measures thresholds. Considering by default the full dataset. σ E = 5, σ I = 1, σϕ = 5 and the quality ϕ ratio

Table 1 :

 1 Example of behavioral dataset -European Parliament Voting dataset 1 http://parltrack.euwiki.org/ 2 https://voteview.com/data 3 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:

	ide themes		date	idi	ide	outcome
	e1 1.20 Citizen's rights		20/04/16	i1	e1	For
	e2 2.10 Free Movement of goods	16/05/16	i1	e2	Against
	e3 1.20 Citizen's rights; 7.30 Judicial Coop	04/06/16	i1	e5	For
	e4 7 Security and Justice		11/06/16	i1	e6	Against
	e5 7.30 Judicial Coop		03/07/16	i2	e1	For
	e6 7.30 Judicial Coop		29/07/16	i2	e3	Against
				i2	e4	For
	(a) Entities (Voting sessions)		i2 i3	e5 e1	For For
	idi country	group	age	i3	e2	Against
				i3	e3	For
	i1 France	S&D	26	i3	e5	Against
	i2 France	PPE	30	i4	e1	For
	i3 Germany	S&D	40	i4	e4	For
	i4 Germany	ALDE	45	i4	e6	Against
	(b) Individuals (Parliamentarians)			(c) Outcomes

  value can be modified by a caller algorithm

	4.2 Hierarchical Multi-Tag Attribute (HMT)
	Several votes and reviews datasets contain multi-tagged records whose tags
	are part of a hierarchical structure. For instance, the ballots in the European
	parliament can have multiple tags (e.g., the ballot Gender mainstreaming in
	the work of the European Parliament is tagged by 4.10.04-Gender equality
	and 8.40.01-European Parliament. Tag 4.10.04 identifies a hierarchy where
	tag 4.10 depicts Social policy which is a specialization of tag 4 that covers
	the ballots related to Economic, social and territorial cohesion).
	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)

Table 2 :

 2 How effective is DEBuNk compared to State-of-the-Art algorithms? -How well can DEBuNk and Quick-DEBuNk identify exceptional intergroup agreement patterns in synthetic data? -Are the closure operators and optimistic estimate based pruning, efficient? -How effective is HMT closed description enumeration compared against closed itemset enumeration? -Does DEBuNk scale w.r.t. different parameters? -How effective is Quick-DEBuNk at sampling interesting patterns in limited time budgets? -Do the algorithms provide interpretable patterns?Most of the experiments were carried out on four real world behavioral datasets whose general characteristics are summarized in Table2. Each of the considered behavioral datasets figures out entities with an HMT (H) attribute together with categorical (C) and numerical (N ) ones, while the individuals have numerical and categorical attributes. Main characteristics of the behavioral datasets Movielens 14 is a movie review dataset[START_REF] Harper | The movielens datasets: History and context[END_REF] consisting of 100K ratings (ranging from 1 to 5) expressed by 943 users on 1681 movies. The movies are characterized by their genres (H) and release date (N), while individuals are described with demographic information such as age group (C), gender (C) and occupation (C). To investigate (dis)agreement patterns, we use the adapted measure IAS ratings . Its definition relies on θ wavg and sim ratings .

		|G E |	A E	|G I | A I	Outcomes
	EPD8	4161	1H + 1N + 1C	958	1N + 5C	2.7M
	Movielens	1681	1H + 1N	943	3C	100K
	Yelp	127K	1H + 1C	18	3C	750K
	Openmedic 12 219 1H	78	3C	500K

EPD8

13

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's voting during one of the 4161 sessions. Each session is described by its themes (H), its voting date (N) and its organizing committee (C). Individuals are described by their national party (C), political group (C), age group (C), country(C) and additional information about countries (date of accession to EU (N) and the country currency (C)). To analyze exceptional inter-group agreement in this dataset, we consider the measure IAS voting . This measure is defined using θ majority and sim voting .

Table 3 :

 3 Behavioral Datasets Characteristics After Scaling 14 https://grouplens.org/datasets/movielens/100k/ 15 https://www.yelp.com/dataset/challenge, last accessed on 25 April 2017 16 http://open-data-assurance-maladie.ameli.fr/, last accessed on 16 November 2017 17 Ameli -France National Health Insurance and Social Security Organization

	Entities (A E )	Individuals (A I )

Table 4 :

 4 Characteristics of datasets considered as plain collections of itemsets records -the plain collections correspond to G E × G I × G I while considering only pairable individuals (pairs of individuals who both expressed outcomes/actions)

  Table 3 illustrates this step, while Table

Table 5 :

 5 Default Parameters Used for Generating Artificial Behavioral Data

	Parameter	Description	Default value
	|G E | (nb entities)	Number of entities	2000
	|G I | (nb individuals)	Number of individuals	500
	|O|	Number of possible categorical outcomes	2
	|A E |	Number of categorical attributes for entities	2
	|dom(a j )| with a j ∈ A E	Domain size of a categorical attribute a j ∈ A E	4
	|A I |	Number of categorical attributes for individuals	2
	|dom(a j )| with a j ∈ A I	Domain size of a categorical attribute a j ∈ A I	4
	nb hidden patterns	Number of planted conflictual patterns	3
	context support size	Support size of a hidden pattern context	5
	group support size	Support size of a hidden pattern group	5
	noise rate	Noise rate in/out the ground truth patterns	0
	data sparsity	Probability of an individual not to cast an outcome	0.33

Table 6 :

 6 Example of input data format for SD-Majority after transforming the behavioral dataset given in

Table 1 .

 1 SD-Cartesian: SD to discover contextual disagreement between two groups. We propose a second modeling to enable the discovery of three-set patterns (c, u 1 , u 2 ) with SD techniques. To this end, the behavioral dataset is transformed into a flat table equivalent to the Cartesian product G E ×G I ×G I . This flat table is then augmented with a target class attribute SAME VOTE which captures the (dis-)agreement between each couple of individuals on each entity for which both expressed an outcome. SAME VOTE is thus equal to + if both individuals expressed the same outcome for the entity,otherwise. This modeling -illustrated in Table7-makes it possible to discover patterns (c, u 1 , u 2 ) which identify two groups of individuals and a context regrouping a set of entities over which the individuals in the first group disagrees with the ones composing the second group. This can be done using the precision gain as the interestingness measure. Even if the syntax of the patterns is similar to ours, the usual agreement between the two selected groups is not take into account. Hence, the semantics conveyed by these patterns is different from ours. Another major drawback of such modeling is the size of the table resulting from the Cartesian product. For instance, a small behavioral dataset with 200 entities and 100 individuals can contain up to 2 × 10 6 records which clearly make this setting not adapted and not scalable for real-world behavioral data.

		Entities	Individuals	Individuals		Outcomes
	ide	theme	idi 1	country 1	idi 2	country 2	outcome1	outcome2	SAME VOTE
	e5	7.30	i1	France	i2	France	F or	F or	+
	e5	7.30	i1	France	i3	France	F or	Against	-
	...	...	...	...	...	...	...	...

Table 7 :

 7 Example of input data format for SD-Cartesian after transforming the behavioral dataset given in Table1to a Cartesian product G

E × G I × G I .

  We use F-score measure, presented earlier in Equation9, to capture to what extent the two patterns set returned by DEBuNk and Quick-DEBuNk provide similar insights about the change of pairwise behavior.Figures17a, 18aand 19a 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 returning high

	0.0 0.2 0.4 0.6 0.8 1.0	5000 10000 15000 20000 25000 30000 35000 timespent(s) Precision Recall F1 Score	Prob.	0.0 0% 2% 4% 6% 8% 10% 12% 14% 16%	0.1	0.2	ϕ 0.3	0.4	0.5 DEBuNk Quick-DEBuNk 0.6
		(a) F1(P Quick-DEBuNk , P DEBuNk )			(b) Empirical Distribution

Table 8 :

 8 Top

	Student vs. Healthcare in ['11 Horror', '5 Comedy'] [1986, 1994]	6	196	16	106	0.42 = 0.74 -0.33
	2 Student vs. Healthcare in ['5 Comedy'] [1991, 1991]	5	196	16	40	0.41 = 0.74 -0.33
	3 Healthcare vs. Artist in ['5 Comedy', '8 Drama'] [1987, 1993]	5	16	28	28	0.42 = 0.73 -0.3
	4 Lawyer vs. Executive in ['4 Children'] [1997, 1997]	5	12	32	27	0.42 = 0.8 -0.38
	5 Executive vs. Artist in ['7 Documentary'] [1996, 1997]	8	32	28	24	0.41 = 0.77 -0.36

-5 w.r.t. number of expressed outcomes (o(i, e) column) of Relevant

Table 9 :

 9 Top-5 w.r.t. number of expressed outcomes (o(i, e) column) of Relevant

Table 12 :

 12 Top-4 w.r.t. the number of expressed outcomes on Openmedic considering by default the full dataset, |A E | = 1, |A I | = 1, σ E = 10, σ I = 1 and σϕ = 3.5 using ϕ ratio . It is important to note that we choose carefully σ E ≥ 10 to reach subgroups of medicines of the fifth level of ATC tree which on average contain 10 medicines.

Table 13 :

 13 Symbol table

  t the weights we we have ∀j ≤ σ E | w e d Hence, from[START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF] and[START_REF] Boley | Linear space direct pattern sampling using coupling from the past[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 provided 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 (10), 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 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 )(14)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 )	(15)
	This results from c d ⇒ G d E ⊆ G c E . Thus,
	we × α(e) ≥	we × α(e) and	we ≤
	e∈M (G c E ,σ E )	e∈M (G d E ,σ E )		e∈mw(G c E ,σ E )	e∈mw(G d E ,σ E )
	j	≤ w e c j . Resulting in:
			we ≥	we	(13)
		e∈M w(G c E ,σ E )	e∈M w(G d E ,σ E )

o(i, e) returns the outcome expressed by an individual i to an entity e, if given.

Roll-Call vote is a voting system where the vote of each member is recorded, such as http: //www.europarl.europa.eu (EU parliament) or https://voteview.com (US Congresses).

The same measure is used by votewatch to observe the voting behaviors of groups of parliamentarianshttp://www.votewatch.eu/blog/guide-to-votewatcheu/

Note that truea i is equivalent to a j ∈ [M INa j ..M AXa j ], M INa j , (resp. M AXa j ) being the minimal (resp. maximal) value of the domain of the attribute a j .

https://github.com/Adnene93/DEBuNk

http://parltrack.euwiki.org/, last accessed on 17 November 2017

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, 2, 3] , [1, 2, 3] , [0.2, 0.4, 0.6]]

http://contentcheck.liris.cnrs.fr

ATC: the Anatomical Therapeutic Chemical classification system classifies therapeutic drugs according to the organ or system on which they act and their chemical, pharmacological and therapeutic properties -http://www.who.int/classifications/atcddd/en/

[START_REF] Dzyuba | Flexible constrained sampling with guarantees for pattern mining[END_REF] http://www.med.uottawa.ca/sim/data/epidemiology rates e.

htm 24 https://www.medicinenet.com/gout gouty arthritis/article.htm

http://www.oecd.org/gov/digital-government/open-government-data.htm

Acknowledgements This work has been partially supported by the project ContentCheck ANR-15-CE23-0025 funded by the French National Research Agency.

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

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] Klosgen | 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] Lavrač | 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[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 mining[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/SD (i.e., EMM/SD with a non-fixed model) has been recently investigated for different aims. Bosc et al. [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 prevent 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]. This work, 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 SD/EMM. [START_REF] Belfodil | Flash points: Discovering exceptional pairwise behaviors in vote or rating data[END_REF] is extended on many levels: [START_REF] Hasan | Output space sampling for graph patterns[END_REF] we provide an easier to use framework to discover exceptional (dis)agreement between groups which requires less parameter setting and interpretation efforts 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 algorithm 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.