Bruno Yun

Madalina Croitoru

Srdjan Vesic

Pierre Bisquert

Graph theoretical properties of logic based argumentation frameworks: proofs and general results

In this paper we extend our first results concerning the characterisation of the graph structure of logic based argumentation graphs with two main classes of findings. First we provide full proofs for the structural results of argumentation graphs built over Datalog+/-knowledge base composed of facts and negative constraints solely. Second, we also provide some structural properties for the general case of knowledge bases composed of facts, rules and negative constraints.

Introduction

We consider existential rules [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF] as the underlying logical language for the argumentation framework. Starting from an inconsistent existential rule knowledge base (composed of a set of factual knowledge and an ontology stating positive and negative rules about the factual knowledge), using the instantiation of [START_REF] Croitoru | What Can Argumentation Do for Inconsistent Ontology Query Answering?[END_REF] we generate the arguments and the attacks corresponding to the knowledge base. The instantiation has been proven to respect rationality desiderata [START_REF] Amgoud | Postulates for logic-based argumentation systems[END_REF][START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF] from the argumentation literature and outputs a set of extensions equivalent to the repairs [START_REF] Lembo | Inconsistency-Tolerant Semantics for Description Logics[END_REF][START_REF] Bienvenu | On the Complexity of Consistent Query Answering in the Presence of Simple Ontologies[END_REF] of the knowledge base (i.e. the maximum w.r.t. inclusion consistent set of factual knowledge).

In [START_REF] Yun | A structural benchmark for logical argumentation frameworks[END_REF] we have given on overview of structural results for simple knowledge bases composed over facts and negative rules only (without any positive rules). In this paper we extend this first study by detailing the results on simple knowledge bases and providing some results that also hold in the general case. More precisely:

-We first consider the case of the knowledge base solely consisting of factual knowledge and negative constraints (expressing fact incompatibility). We fully prove the following structural properties of the argumentation graphs constructed from such knowledge bases: the existence of several duplicates of the same sub-graph, graphautomorphism induced graph symmetries and specific strongly connected component behaviour. We demonstrate how this serves as a complete characterisation of argumentation frameworks obtained from such knowledge bases. We also show that the cf2 semantics [START_REF] Baroni | SCC-recursiveness: a general schema for argumentation semantics[END_REF][START_REF] Sarah | The cf2 argumentation semantics revisited[END_REF] coincides with the preferred and naive semantics in the case of argumentation frameworks generated from such knowledge bases (without positive rules) that only contain binary negative constraints. Furthermore, we give an example showing that if ternary negative constraints are added, this equivalence no longer holds.

-Second, for the general case of knowledge bases with any number of facts, rules or negative constraints we unveil the following structural properties: the presence of a complete directed sub-graph, the presence of at least one cycle in the graph and, intriguingly, the fact that the cf2 semantics [START_REF] Baroni | SCC-recursiveness: a general schema for argumentation semantics[END_REF][START_REF] Sarah | The cf2 argumentation semantics revisited[END_REF] is yielding, in this instantiation, potentially inconsistent bases of arguments.

The significance of our results lies in the graph theoretical structural analysis of a whole family of potentially real world argumentation graphs. Such results are important to know for software engineers when designing argumentation solvers. For example, when designing SAT inspired solvers [START_REF] Cerutti | Computing Preferred Extensions in Abstract Argumentation: A SAT-Based Approach[END_REF], graph symmetries induce as choice the solvers that better perform in the presence of symmetries [START_REF] Lagniez | Coquiaas: A constraintbased quick abstract argumentation solver[END_REF]. Another practical interest lies in benchmark generation [Yun et al., 2017a]. Recently argumentation competitions [START_REF] Thimm | Summary Report of The First International Competition on Computational Models of Argumentation[END_REF] have been held where the benchmarks are generated based on graph theoretical structures known to be difficult for solvers but not confirmed to appear in practice. Revealing real world behaviour could fill this gap and complete the benchmark spectra of instances. Last, it is important to be aware of logic based argumentation graph behaviour in order to keep a realistic expectation of the added value of argumentation in such domains. It is known [Yun et al., 2017b] that even for a modest knowledge base of 7 facts, 2 rules and 1 binary negative constraints, the generated argumentation graph can take gargantuan proportions reaching 383 arguments and 32768 attacks. This paper will help explain, at least partially, these results. For example, the sub-graph duplicate result directly shows the exponential growth of the argumentation graph when facts are added to the knowledge base. Please note that even if the paper of Yun et al. [2017b] deals with benchmark generation of existential rule knowledge bases it is fundamentally different from this work in at least two ways. First, no graph theoretical properties are demonstrated in Yun et al. [2017b]. Second, regarding practical added value of Yun et al. [2017b], the authors provide a benchmark generation tool but given the size of the generated graphs it would be difficult to generate the graphs in order to test for their structure. This paper fills this gap and directly provides a variety of graph theoretical properties such graphs enjoy.

In Section 2, we recall the basic notions of existential rules and argumentation. In Section 3, we show a complete set of structural properties for argumentation frameworks generated from knowledge bases without rules w.r.t. symmetry, strongly connected components and k-copy graphs. Then, the rest of the section deals with structural results for argumentation frameworks generated from general knowledge bases. We show general structural properties such as the absence of self-attacking arguments but also the presence of complete directed sub-graphs. We conclude with a concrete example showing that the cf2 semantics is not suitable for existentially rule instantiated logical argumentation frameworks as it can output sets with inconsistent bases.

The existential rules language [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF] has attracted much interest recently in the Semantic Web and Knowledge Representation community for its suitability for representing knowledge in a distributed context (such as Ontology Based Data Access (OBDA) applications) [START_REF] Thomazo | Mixing Materialization and Query Rewriting for Existential Rules[END_REF][START_REF] Zhang | Expressive Completeness of Existential Rule Languages for Ontology-Based Query Answering[END_REF]. It is composed of formulae built with the usual quantifiers (∃, ∀) and only two connectors: implication (→) and conjunction (∧) and is composed of the following elements:

-A fact is a ground atom of the form p(t 1 , . . . , t k ) where p is a predicate of arity k and

t i , i ∈ [1, . . . , k] constants. -An existential rule is of the form ∀ - → X , - → Y H[ - → X , - → Y ] → ∃ - → Z C[ - → Z , - → X ]
where H (called the hypothesis) and C (called the conclusion) are existentially closed atoms or conjunctions of existentially closed atoms and

- → X , - → Y , - →
Z their respective vectors of variables. A rule is applicable on a set of facts F iff there exists a homomorphism from the hypothesis of the rule to F. Applying a rule to a set of facts (also called chase) consists of adding the set of atoms of the conclusion of the rule to the facts according to the application homomorphism. Different chase mechanisms use different simplifications that prevent infinite redundancies [START_REF] Baget | On rules with existential variables: Walking the decidability line[END_REF]. We use recognisable classes of existential rules where the chase is guaranteed to stop [START_REF] Baget | On rules with existential variables: Walking the decidability line[END_REF].

-A negative constraint is a particular kind of rule where C is ⊥ (absurdum). Negative constraints can be of any arity (i.e. the number of atoms in C is not bounded). Negative constraints implement weak negation. Please note that negative constraints generalise simple binary conflicts that can easily be translated between the two representations: ¬p(X) is transformed into np(X) and the negative constraint p(X) ∧ np(X) → ⊥ is added to the rules set. -A knowledge base K = (F, R, N ) is composed of a finite set of facts F, a set of rules R and a set of negative constraints N . We denote by C * R (F) the closure of F by R (computed by all possible rule R applications over F until a fixed point). C * R (F) is said to be R-consistent if no negative constraint hypothesis can be deduced. Otherwise,

C * R (F) is R-inconsistent. -Given a knowledge base K = (F, R, N ), a set of facts C ⊆ F is called a minimal conflict iff C is R-inconsistent and any strict subset C ⊂ C of it is R-consistent.
The set of all minimal conflict of K is denoted conf licts(K). If there are no minimal conflicts there are no attacks.

In the OBDA setting rules and constraints act as an ontology used to "access" different data sources. These sources are prone to inconsistencies. As per literature principles, we suppose that the set of rules is compatible with the set of negative constraints, i.e. the union of those two sets is satisfiable [START_REF] Lembo | Inconsistency-Tolerant Semantics for Description Logics[END_REF]. This assumption is made because in OBDA we assume that the ontology is believed to be reliable as it is the result of a robust construction by domain experts. However, as data can be large and heterogeneous due to merging and fusion, in the OBDA setting the data is assumed to be the source of inconsistency. This means that by applying the rules on the set of facts, we might violate a constraint. To handle inconsistency, in this paper we use the existential rule instantiation of argumentation frameworks of [START_REF] Croitoru | What Can Argumentation Do for Inconsistent Ontology Query Answering?[END_REF]:

-An argument [START_REF] Croitoru | What Can Argumentation Do for Inconsistent Ontology Query Answering?[END_REF] in Datalog ± is composed of a minimal (w.r.t. set inclusion) set of facts called support and a conclusion entailed from the support. The Skolem chase coupled with the use of decidable classes of Datalog ± ensures the finiteness of the argumentation framework proposed (following from [START_REF] Baget | On rules with existential variables: Walking the decidability line[END_REF]). Formally, an argument a is a tuple (H, C) with H a non-empty R-consistent subset of F and C a set of facts:

• H ⊆ F and C * R (H) |= ⊥ (consistency) • C ⊆ C * R (H) (entailment) • H ⊂ H s.t. C ⊆ C * R (H ) (minimality)
The support H of an argument a is denoted by Supp(a) and the conclusion C by Conc(a).

-The attack considered is the undermine [START_REF] Croitoru | What Can Argumentation Do for Inconsistent Ontology Query Answering?[END_REF] Example 1. Let us consider the knowledge base K = (F, R, N ) with:

F = {a(m), b(m), c(m), d(m)}, R = ∅ and N = {∀x(a(x) ∧ b(x) ∧ c(x) → ⊥)}.
The corresponding argumentation framework AS K is composed of 36 attacks and the following 13 arguments:

-a0 0 : ({a(m)}, {a(m)}) -a1 0 : ({b(m)}, {b(m)}) -a2 2 : ({a(m), b(m)}, {a(m), b(m)}) -a3 0 : ({c(m)}, {c(m)}) -a4 2 : ({a(m), c(m)}, {a(m), c(m)}) -a5 2 : ({b(m), c(m)}, {b(m), c(m)}) -a6 0 : ({d(m)}, {d(m)}) -a7 2 : ({a(m), d(m)}, {a(m), d(m)}) -a8 2 : ({b(m), d(m)}, {b(m), d(m)}) -a9 6 : ({a(m), b(m), d(m)}, {a(m), b(m), d(m)}) -a10 2 : ({c(m), d(m)}, {c(m), d(m)}) -a11 6 : ({a(m), c(m), d(m)}, {a(m), c(m), d(m)}) -a12 6 : ({b(m), c(m), d(m)}, {b(m), c(m), d(m)})
Please note that the attack is not symmetric, for instance, the argument a5 2 attacks the argument a0 0 but not conversely.

Let us now recall basic argumentation notions [START_REF] Minh | On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games[END_REF]. Let AS be an argumentation framework, S ⊆ A and a ∈ A. We say that:

-S is conflict-free iff there exists no arguments a, b ∈ S such that (a, b) ∈ C.

-S defends a iff for every argument b ∈ A, if we have (b, a) ∈ C then there exists c ∈ S such that (c, b) ∈ C. -S is admissible iff it is conflict-free and defends all its arguments.

-S is a preferred extension iff it is a maximal (with respect to set inclusion) admissible set. -S is a stable extension iff it is conflict-free and for all a ∈ A \ S, there exists an argument b ∈ S such that (b, a) ∈ C.

Example 2 (cont.). There are 3 stable (resp. preferred) extensions in AS K :

-

ε 1 = {a0 0, a1 0, a2 2, a6 0, a7 2, a8 2, a9 6} -ε 2 = {a1 0, a3 0, a5 2, a6 0, a8 2, a10 2, a12 6} -ε 3 = {a0 0, a3 0, a4 2, a6 0, a7 2, a10 2, a11 6}
It was shown in [START_REF] Croitoru | What Can Argumentation Do for Inconsistent Ontology Query Answering?[END_REF] that, for existential rules argumentation frameworks, the set of preferred and stable extensions coincide and correspond to the set of maximally consistent sets of facts (repairs).

Example 3 (cont.). The preferred extension ε 1 corresponds to the repair:

r 1 = {a(m), b(m), d(m)}.
Indeed, we have that Base(ε 1 ) = r 1 .

Structural Results

This section is organised as follows. In Section 3.1 we first investigate the graph theoretical results of knowledge bases composed solely of facts and negative constraints. Then, in Section 3.2 we investigate the general case where rules are also considered in the argumentation framework.

Results for simple knowledge bases

The graph theoretical results of this subsection are solely looking at the case where the knowledge base is composed of a set of facts and a set of negative constraints defined on these facts. Therefore, at the basis of the results lies the notion of knowledge base minimal conflict. We exhibit three main results:

-The first result deals with conflict induced structural properties. Namely, we characterise dummy arguments, arguments that are un-attacked and that do not attack other arguments, and show the repetitious nature of the argumentation graph by introducing the notion of k-copy graph. -The second result deepens these results and looks into the symmetries of the argumentation graph based on graph auto-morphisms. -Last, we look into the connectivity of the graph and demonstrate strongly connected components related results.

Please note that these three points will enable us to completely characterise the structural properties of argumentation graphs generated from knowledge bases without positive rules. We begin by introducing the scope of a negative constraint which is the set of all sets of facts on which the negative constraint is applicable.

Definition 1. Let K = (F, R, N ) be a knowledge base with R = ∅ and N ∈ N be a negative constraint. We define the scope of the negative constraint N as the set F N = {X ⊆ F | X is minimal with respect to set inclusion such that there is an homomorphism from the body of N to X}.

Example 4 (cont.). The scope of the negative constraint

N = ∀x(a(x) ∧ b(x) ∧ c(x) → ⊥ is F N = {{a(m), b(m), c(m)}}.
We show that the number of un-attacked arguments that do not attack other arguments, called "dummy arguments", depends on the number of facts and the scope of all negative constraints.

Proposition 1. Let K = (F, R, N ) be an inconsistent knowledge base such that R = ∅ and |F| = n. If AS K = (A, C) is the corresponding argumentation framework, there are exactly 2 n-k -1 dummy arguments a in AS K such k = | N ∈N X∈F N X|. Proof. Denote J = N ∈N X∈F N X. Denote U nn = {a ∈ A | Att -(a) = Att + (a) = ∅}. 1. Let us prove that |U nn| ≥ 2 n-k -1 with |J| = k and |F| = n. The set J = N ∈N
X∈F N X corresponds to the set of facts that trigger at least one negative constraint. Thus, every fact that belongs to E = F \ J is not in any conflict. Since |E| = n -k and R = ∅, we conclude that there are at least 2 n-k -1 arguments that have a non empty subset of E as support. These arguments are not attacked and do not attack other arguments as the elements of their supports and conclusions are not in any conflict. 2. Let us prove that |U nn| ≤ 2 n-k -1 with |J| = k and |F| = n. By means of contradiction, suppose that there is an argument a that do not attack other arguments and that is not attacked but Supp(a) ⊆ E. It means there exists a negative constraint N such that ( X∈F N X) ∩ Supp(a) = ∅ and there is X ∈ F N such that X ∩ Supp(a) = ∅. Now, let us consider Y = X \ Supp(a). We know that Y is not empty otherwise there is a contradiction with the consistency of the support of a. Furthermore, Y is R-consistent since |Y | is strictly inferior to the arity of the negative constraint N . Thus, there is an argument b = (Y, Y ) such that (b, a) ∈ C, contradiction.

Example 5 (cont.). We have that n = 4 and since we know that N ∈N X∈F N X = {a(m), b(m), c(m)}, we conclude that there is 2 4-3 -1 = 1 dummy argument. This argument corresponds to a6 0 = ({d(m)}, {d(m)}).

We now analyse the related behaviour of atoms in the scope of a negative constraint. To do so we introduce the notion of k-copy graph.

A k-copy graph of a graph is another graph that has k times more arguments and each copy a of a attacks the same arguments as a and possesses the same attackers. Formally:

Definition 2. Let AS = (A, C) be an argumentation framework. We say that the graph of AS is a k-copy graph of AS = (A , C ) iff:

-|A| = k * |A | and there is a surjective function f from A to A such that for every argument a ∈ A , we have |W a | = k, where W a = {a ∈ A | f (a) = a }. -For all a, b ∈ A, (a, b) ∈ C iff (f (a), f (b)) ∈ C .
Example 6. In Figure 1, the graph G (on the right) is a 2-copy graph of the graph G (on the left). We have that If two arguments are the copies of the same argument, then they attack the same arguments and are attacked by the same arguments.

W a = {a 1 , a 2 }, W b = {b 1 , b 2 }, W c = {c 1 , c 2 }.
The following proposition shows that if there is a knowledge base K with no rule and containing k facts that are not in the scope of any negative constraints, then there exists a subgraph of AS K that is a 2 k -copy graph of AS K where K is the knowledge base with no rules, the same negative constraints as K and that contains only the facts that are in the scope of at least one negative constraint of K.

This property is important as it shows the behaviour of the instantiation in the case of addition of facts not appearing in any conflict. It shows the structure of the graph and exhibits the exponential growth of the number of arguments w.r.t. these facts.

Proposition 2. Let K = (F, R, N ) be a knowledge base with R = ∅.

If J = N ∈N X∈F N X = ∅ and |F \ J| = k then there is a subgraph of AS K = (A, C) that is a (2 k )-copy graph of AS K = (A , C ) where K = (J, R, N ) and |A| = (|A | + 1) * 2 k -1.
Proof. If |F \ J| = 0, then it is obvious that AS K is a 1-copy graph of itself. Suppose now that |F \ J| > 0. We denote by AS K = (A , C ) the argumentation framework from the knowledge base K = (J, R, N ). Moreover, since R = ∅, the arguments can only be of the form (X, X) where X is an R-consistent subset of J.

Hence, |A | = |{X | X is an R-consistent subset of J}|.
Now, let us consider AS K = (A, C), the argumentation framework corresponding to the knowledge base K = (F, R, N ). We show that the subgraph

AS K = (A , C ) of AS K where A = {a ∈ A | Supp(a) ∩ J = ∅} and C = C |A is a (2 |F \J| )-copy graph of AS K : -We know that for any set X that is an R-consistent subset of J, X ∪ X , where X is a subset of F \ J, is an R-consistent set. Thus |A | = |{X ∪ X | X ⊆ F \ J and X is an R-consistent subset of J}|. Since the number of subsets of F \ J is 2 |F \J| , then |A | = |A | * 2 |F \J| . -We denote by f the function from A to A such that f (a ) = a iff Supp(a ) =
Supp(a ) ∩ J. We now show that this function is surjective. Let a be an argument of A and c an arbitrary element of F \J (it exists since |F \J| > 0). As mentioned before, we know that E = Supp(a

) ∪ {c} is R-consistent. Therefore a = (E, E) is an argument of A and f (a ) = a . -Let a ∈ A and W a = {a ∈ A | f (a ) = a }. For every subset X of F \ J, L = X ∪ Supp(a ), (L, L) ∈ W a . Since the number of different subsets of F \ J is 2 |F \J| , we have |W a | ≥ 2 |F \J| . Since for every a 1 , a 2 ∈ A , W a 1 ∩ W a 2 = ∅, then for every a ∈ A , |W a | = 2 |F \J| because |A | = |A | * 2 |F \J| . -Let (a 1 , a 2 ) ∈ C
, by definition, we have that there exists φ ∈ Supp(a 2 ) s.t.

Conc(a 1 )∪{φ} is R-inconsistent. Since there are no rules, it is true that Supp(a 1 )∪ {φ} is also R-inconsistent. However, it is clear that this inconsistency cannot come from elements of F \J. Thus, there exists φ ∈ Supp(a 2 )∩J such that (Supp(a

1 )∩ J) ∪ {φ} is R-inconsistent. Therefore (f (a 1 ), f (a 2 )) ∈ C since Supp(f (a 1 )) = Supp(a 1 ) ∩ J and Supp(f (a 2 )) = Supp(a 2 ) ∩ J. -Let a 1 , a 2 ∈ A such that (f (a 1 ), f (a 2 )) ∈ C . It means that there exists φ ∈ Supp(f (a 2 )) s.t. Conc(f (a 1 )) ∪ {φ} is R-inconsistent. By definition, we have that Supp(f (a 2 )) = Supp(a 2 ) ∩ J, thus φ ∈ Supp(a 2 ). Likewise, we have that Conc(f (a 1 )) = Supp(f (a 1 )) = Supp(a 1 ) ∩ J = Conc(a 1 ) ∩ J. We conclude that (Conc(a 1 ) ∩ J) ∪ {φ} is R-inconsistent. Therefore Conc(a 1 ) ∪ {φ} is R- inconsistent and (a 1 , a 2 ) ∈ C . Finally, we have that |A| = |{X | X is an R-consistent subset of F}| = |{X | X ∩ J = ∅ and X is an R-consistent subset of F} ∪ {X | X ⊆ F \ J and X is an R-consistent subset of F}| -1 = |A | * 2 |F \J| + 2 |F \J| -1 = (|A | + 1) * 2 |F \J| -1.
This concludes the proof.

We want to emphasise the result of Proposition 2 as it shows that the addition of "superfluous" facts will increase the size of the argumentation graph by an exponential factor.

Example 7 (cont.). The argumentation framework AS K has a subgraph that is a 2-copy graph of AS K , where K = ({a(m), b(m), c(m)}, ∅, N ). Indeed, the argumentation framework AS K is composed of the following arguments:

-

a 1 : ({a(m)}, {a(m)}) -a 2 : ({b(m)}, {b(m)}) -a 3 : ({a(m), b(m)}, {a(m), b(m)}) -a 4 : ({c(m)}, {c(m)}) -a 5 : ({a(m), c(m)}, {a(m), c(m)}) -a 6 : ({b(m), c(m)}, {b(m), c(m)})
We have that W a1 = {a0 0, a7 2}.

We now focus on detecting symmetries in the graph. Please first note that we have the presence of symmetric arcs in the argumentation framework without rules. It obviously holds that if all negative constraints are binary, then the graph has only symmetric arcs (since the undermining will rely on binary sets). However, if the set of rules is not empty the symmetry no longer holds.

We now explore the link between the instantiation and symmetries in graphs. The next definitions introduce the notions needed to comprehend symmetries, namely, permutations of arguments, orbit of an argument and the cycle notation of a permutation. Definition 3. A permutation on a set of elements X is a bijection σ from X to X. Given a permutation σ, the orbit of element x ∈ X is the set O x = {x, σ(x), σ 2 (x), . . . , σ n (x)}, with n ∈ {0, 1, . . . } the minimal integer s.t. σ n+1 (x) = x. Definition 4. Given a permutation σ on X, an orbit O and an element x ∈ O, a cycle is a sequence (x, σ(x), σ 2 (x) . . . , σ n (x)), where n ∈ {0, 1, . . . } is the minimal integer such that σ n+1 (x) = x.

A permutation can be compactly expressed as a product of cycles corresponding to the orbits of the permutation1 .

Definition 5. Let G = (V, E) be a graph. A permutation σ on set V is an auto- morphism of G iff for every two nodes v 1 , v 2 ∈ V , we have that (v 1 , v 2 ) ∈ E iff (σ(v 1 ), σ(v 2 )) ∈ E.
The set of automorphisms of a graph, together with the function composition operator, form a group called the automorphism group. The automorphism groups of a graph characterise its symmetries, and are therefore very useful in determining certain of its properties. A subset of a group is called a generating set of a group iff every group's element can be expressed as the combination (under group operation) of finitely many elements of the subset and their inverses.

Proposition 3. Let AS = (A, C) be a k-copy graph of AS = (A , C ). For every a ∈ A , for every a 1 , a 2 in W a , we have that (a 1 , a 2 ) is an automorphism of AS.

The next proposition shows that if we add nodes (and no arc) to a graph with automorphisms, then the obtained graph also has automorphisms. It is used for showing, in Proposition 5, that a graph constructed on a KB with no rules possesses non trivial automorphisms derived from its subgraph.

Proposition 4. Let G = (V, E) be a graph such that σ is an automorphism of G. The graph G = (V ∪ X, E), where X ∩ V = ∅, has the automorphism σ from V ∪ X to V ∪ X: ∀v ∈ V ∪ X, σ (v) = σ(v) if v ∈ V v if v ∈ X Proposition 5. Let K = (F, R, N ) with R = ∅, J = N ∈N X∈F N X = ∅, |F \ J| = k, K = (J, R, N )
and AS be a (2 k )-copy graph of AS K = (A , C ). If AS has k automorphisms, then AS K has at least k automorphisms.

Proof. From Proposition 2, we know that AS K has a subgraph AS K = (A , C ) that is a 2 k -copy graph of AS K . We first show that every argument a that is in

A \ A is such that Att -(a) = Att + (a) = ∅.
Then we use Proposition 4.

1. We showed in the proof of Proposition 2 that A = {a ∈ A | Supp(a) ∩ J = ∅}. Thus, A \ A = {a ∈ A | Supp(a) ⊆ F \ J}. Since we have no rules, the arguments in A \ A cannot attack other arguments. 2. From Proposition 4, we conclude that there is an automorphism of AS K for every automorphism of AS K .

Proposition 5 is important as it shows that the graph inherit all of the automorphisms of its subgraph. This will be useful when designing new solvers relying on symmetries.

Example 8 (cont.). Using Proposition 4 and Proposition 5, we have that (a0 0, a7 2) is an automorphism of AS K .

We now characterise the connectivity of the graph by showing the structure of the strongly connected components. We first define the impossible set associated to a minimal conflict C as the set containing all the possible subsets of F that are supersets of at least one subset of C of size |C -1|. Definition 6. Let K be a knowledge base and C a minimal conflict of conf licts(K).

The impossible set of C denoted by

Imp(C) is {X ⊆ F | X ⊆ X and X ⊆ C with |X | = |C -1|}.
An argumentation framework is strongly connected if and only if there is a path from any argument a to any argument a . Definition 7. Let AS = (A, C) be an AF. We say that AS is strongly connected iff for every a, a ∈ A such that a = a , there is a path from argument a to argument a .

Please note that the set of nodes of any arbitrary directed graph can be partitioned such that the subgraphs, induced by each set of nodes, is strongly connected that are called the strongly connected components of this graph. In the rest of this paper, we will denote by SCC(AS), this particular partition of the set of arguments of AS.

In the following proposition, we characterise the structure of the strongly connected components of an argumentation framework obtained from a knowledge base without rules.

Proposition 6. Let KB be a knowledge base such that R = ∅ and AS K = (A, C) the corresponding AF. We have that:

1. {(X i , X i )} ∈ SCC(AS K ) where X i ∈ 2 F \ C∈conf licts(K) Imp(C) 2. (A \ i s i ) ∈ SCC(AS K )
Proof. We split the proof in two parts: 1. Suppose that s i is not a strongly connected component by itself, it means that there is another argument a such that there is a path from x i = {X i , X i } to a and inversely. Let us denote by a 1 , the first argument attacked by x i on a path from x i to a. By definition, it means that there exists φ ∈ Supp(a 1 ) such that

X i ∪ {φ} is R-inconsistent. Since X i is R-consistent, it means that X i ∪ {φ} is a minimal conflict and that X i ∈ Imp(X i ∪{φ}). Then, Xi / ∈ 2 F \ C∈conf licts(K) Imp(C), contradiction.
2. Let a, b be two arguments in (A \ i s i ), we show here that there is a path from a to b. From the definitions, we know that a (resp. b) is of the form (X, X) (resp.(X , X )) such that there exists a minimal conflict C (resp. C ) and

W ⊆ C (resp. W ⊆ C ) with |W | = |C -1| (resp. |W | = |C -1|) and W ⊆ X (resp. W ⊆ X ). Let H = C \ X, X = X \ H, W ⊆ X with |W | = |X -1| and J = H ∪ W ∪ (C \ X ).
-If J is R-consistent, we denote by u, the argument (J, J). We have that u belongs to (A \ i s i ) because J = |C -1| and J ⊆ C . We have that a attacks u and u attacks b. We now summarise all the structural properties of the AFs generated from simple knowledge bases using Figure 2

-If J is R-inconsistent, it means that there is a minimal conflict C ⊆ J such that C ⊆ C and C ⊆ C. Let us consider K, L ⊆ J such that |K| = |L| = |J -1|, H ⊆ K

as an example:

-There is one k-copy graph (encircled in the dashed-line zone).

-The arguments that are not inside the k-copy graph are "dummy arguments" (arguments that are outside the dashed-line zone) and their number can be computed using Proposition 1. -There is one dense strongly connected component composed of the majority of the arguments (encircled in the grey circle). -The other strongly connected components are composed of only one argument each (arguments that are outside of the grey circle). The number of strongly connected components can be computed using Corollary 1.

Fig. 2: Structural properties of AFs from simple KBs

Since we deal with strongly connected components, one of the research questions that naturally arise from this is whether or not the cf2 semantics [START_REF] Baroni | An introduction to argumentation semantics[END_REF][START_REF] Sarah | The cf2 argumentation semantics revisited[END_REF] is equivalent to the preferred semantics in argumentation graphs generated from knowledge bases without positive rules.

On one hand, it appears that if the set of negative constraints is only composed of binary negative constraints, then the graph only has symmetric arcs. We conclude that since all SCCs are isolated, the cf2 semantics coincides with the naive and preferred semantics.

Proposition 7. Let KB be a knowledge base such that R = ∅, then the cf2 semantics coincides with the preferred and the naive semantics in AS K .

On the other hand, if we add ternary negative constraints, the cf2 semantics will no longer coincide with the preferred semantics as shown in Example 10.

Example 10. Let K = (F, R, N ) be a knowledge base such that F = {a(m), b(m), c(m), d(m), e(m)}, R = ∅ and N = {∀x(a(x) ∧ b(x) ∧ c(x) → ⊥), ∀x(e(x) ∧ d(x) → ⊥)}.
The corresponding argumentation framework is composed of 161 attacks and the 20 following arguments: The preferred extensions will be composed of the following sets:

-a0 0 : ({a(m)}, {a(m)}) -a1 0 : ({b(m)}, {b(m)}) -a2 2 : ({a(m), b(m)}, {a(m), b(m)}) -a3 0 : ({c(m)}, {c(m)}) -a4 2 : ({a(m), c(m)}, {a(m), c(m)}) -a5 2 : ({b(m), c(m)}, {b(m), c(m)}) -a6 0 : ({d(m)}, {d(m)}) -a7 2 : ({a(m), d(m)}, {a(m), d(m)}) -a8 2 : ({b(m), d(m)}, {b(m), d(m)})), d(m)}) -a9 6 : ({a(m), b(m), d(m)}, {a(m), b(m), d(m)}) -a10 2 : ({c(m), d(m)}, {c(m), d(m)}) -a11 6 : ({a(m), c(m), d(m)}, {a(m), c(m), d(m)}) -a12 6 : ({b(m), c(m), d(m)}, {b(m), c(m), d(m)}) -a13 0 : ({e(m)}, {e(m)}) - a14
ε 1 = {a0 0, a1 0, a2 2, a6 0, a7 2, a8 2, a9 6} ε 2 = {a0 0, a3 0, a4 2, a6 0, a7 2, a10 2, a11 6} ε 3 = {a1 0, a3 0, a5 2, a6 0, a8 2, a10 2, a12 6} ε 4 = {a0 0, a1 0, a2 2, a13 0, a14 2, a15 2, a16 6} ε 5 = {a0 0, a3 0, a4 2, a13 0, a14 2, a17 2, a18 6} ε 6 = {a1 0, a3 0, a5 2, a13 0, a15 2, a17 2, a19 6}

The set of cf2 extensions is the set {ε 1 , ε 2 , ε 3 , ε 4 , ε 5 , ε 6 , ε 7 , ε 8 } with:

ε 7 = {a0 0, a1 0, a3 0, a6 0, a7 2, a8 2, a10 2} ε 8 = {a0 0, a1 0, a3 0, a13 0, a14 2, a15 2, a17 2}

Results for general knowledge bases

In this subsection we consider the general case of knowledge bases composed of a set of facts, a set of rules and a set of negative constraints. Unfortunately, as the set of rules can completely change the argumentation framework, general results are much harder to obtain. It is easy to show that the link between the conflict graph (the hyper-graph generated by the negative constraints on the facts, potentially enriched with rules) bares no obvious link to the argumentation graph generated by the corresponding knowledge base. In the Appendix we show that there can be several argumentation frameworks associated with the same minimal conflict graph.

Despite the generality of the problem, we however present three graph theoretical structural results of argumentation graphs:

-First we show general structural properties of the graph: no self-attacking arguments, every argument is defended, having at least one cycle, etc. -Second we demonstrate the presence of a complete directed sub-graph.

-Third, we show that preferred extensions are included into cf2 extensions but not the other way. Contrary to expectations, we show that the cf2 semantics (originally designed to better handle cycles in graphs) is producing a set of arguments with an inconsistent base.

Let us start by making a few observations on the structure of the argumentation graph. Indeed, it is clear that not any graph can be obtained when constructing arguments from an existential rule knowledge base. First, we remark that an AF generated from a knowledge base K is always finite. Second, given the definition of an argument, we can also note that there are no self-attacking arguments in our framework: Proposition 8. Let AS = (A, C) be an argumentation framework s.t. there is an argument a ∈ A with (a, a) ∈ C. There is no Datalog ± knowledge base K s.t. AS K = AS.

For every argument in the instantiated argumentation framework, there is a stable (resp. preferred and semi-stable) extension that contains it. Please note that the fact that there are no rejected arguments does not mean that the framework is not expressive as ranking-based semantics may be used to attach more fine-graded acceptability degrees to arguments.

Proposition 9. Let AS K = (A, C) be the corresponding AF of K. Then, for every argument a ∈ A, there exists a preferred extension ε ∈ Ext p (AS K ) (resp. semi-stable extension ε ∈ Ext ss (AS K ) and stable extension ε ∈ Ext s (AS K )) s.t. a ∈ ε.

We now focus on basic observations regarding attacks. First, no knowledge base can generate a framework where an argument a is attacked by an unattacked argument b: Proof. By definition, we have that E and E are R-consistent. Suppose that the argument (E, E) / ∈ A, it means that there is

H ⊂ E and E ⊆ C * R (H) (minimality). It means that (C \ E) ∪ H is R-inconsistent and ((C \ E) ∪ H) ⊂ C, contradiction.
If there is at least one minimal conflict C of size at least 2, then there is a cycle2 in the graph of the instantiated AF: Proposition 12. If K is a Datalog ± knowledge base and AS K = (A, C) the corresponding instantiated AF with C a minimal conflict of K of size at least 2 then AS K has a cycle.

Proof. Since there is a minimal conflict of at least size 2 then we know from Proposition 11 that there are two arguments (E, E) and

(E , E ) in A such that E, E ⊂ C, E = E and |E| = |E | = |C -1|.
We have that (E, E) attacks (E , E ) and conversely.

Minimal conflicts create a particular structure in the graph of the AF. For every minimal conflict of size n, there is a complete directed subgraph on n nodes (i.e. a subgraph containing n arguments where every argument attacks every argument except itself). Let us now investigate the behaviour of the cf2 semantics on general Datalog ± argumentation graphs. First, we show that the set of preferred extensions is included in the set of cf2 extensions. We know that in the general case, we have that a stable extension is also a cf2 extension [START_REF] Sarah | The cf2 argumentation semantics revisited[END_REF][START_REF] Baroni | SCC-recursiveness: a general schema for argumentation semantics[END_REF]. Proposition 14. Let AS be a random AF, we have that Ext st (AS) ⊆ Ext cf 2 (AS).

Furthermore, since we are working in the setting of Datalog ± argumentation frameworks described in [START_REF] Croitoru | What Can Argumentation Do for Inconsistent Ontology Query Answering?[END_REF], a basics result is that the set of preferred extension is equal to the set of stable semantics.

Proposition 15. Let AS be a Datalog ± AF, we have that Ext st (AS) = Ext pr (AS).

We thus conclude that the set of preferred extensions is included the set of cf2 extensions for the case of Datalog ± AFs.

In this paper we investigated the formal structural properties of argumentation graphs generated from Datalog ± knowledge bases.

We showed that for the case of argumentation frameworks originated from knowledge bases without rules, the dummy arguments are the result of facts that are not in the scope of any negative constraints and that their numbers are exponential w.r.t. these facts. Then, we proved that these frameworks possess a particular subgraph called kcopy graph which have symmetries in the form of automorphisms. Moreover, these symmetries can be transferred to the full argumentation framework without loss of generality. Next, we characterised the strong connectivity of the argumentation framework by explaining their structure. Lastly, we showed that the cf2 semantics coincides with the preferred and naive semantics in the case of argumentation frameworks generated from knowledge bases without rules and containing only binary negative constraints.

We then dealt with the case of argumentation frameworks generated from general knowledge bases with rules. We first showed general structural properties of the graph such as the absence of self-attacking arguments, the fact that every argument is defended and the presence of at least one cycle. Second we proved the presence of a complete directed sub-graph associated to each minimal conflict of the knowledge base. Third, we showed that preferred extensions are included into cf2 extensions in this particular instantiation. Last, contrary to expectations, we proved by providing a counter-example that the cf2 semantics (originally designed to better handle cycles in graphs) is producing a set of arguments with an inconsistent base.

The significance of our results lies in the fact that this is the first paper highlighting the graph theoretical structural analysis of real world argumentation graphs. We believe that our thorough analysis will enable modellers to understand why and how the changes in the knowledge base can impact the structure of the argumentation framework. What's more, we feel that this paper could be useful for designing faster and better suited solvers for realistic argumentation graphs relying on their inherent structure.

Let us also make a note about the logical language used for instantiating the knowledge bases. Existential rules have been recently intensively investigated for their generalisation with respect to Description Logic fragments. Please note that certain structural results have also been shown to hold in the work of Arioua et al. [2017b]. However, their definition of argument is different from the one used in this paper (as our definition prevents unnecessary repeated arguments). We also note that using argumentation over existential rules has been shown to be of practical interest over existing approaches ([Hecham et al., 2017a]). Argumentation for handling inconsistency tolerant semantics enhance the human interaction ( [Arioua and Croitoru, 2016]), can be used for practical applications in food science ( [Arioua et al., 2016[Arioua et al., , 2017a]]) or allow for alternative computation methods [START_REF] Yun | An argumentation workflow for reasoning in ontology based data access[END_REF]). Such techniques have been shown to have further implications with respect to human reasoning and bias detection [START_REF] Bisquert | Substantive irrationality in cognitive systems[END_REF]). While the OBDA inspired restriction of inconsistency only coming from the facts could be too strong for certain applications, recently, argumentation inspired approaches that consider defeasible reasoning have been proposed ( [Hecham et al., 2017b]). Future work will investigate the case of symmetries and strongly connectivity for argumentation graphs from general knowledge bases. Our goal is to obtain a complete characterisation of the argumentation graphs generated from a Datalog ± knowledge base.

Appendices

We first give the definition of a minimal conflict graph and show that there can be several argumentation frameworks associated with the same minimal conflict graph. This observation is highlighted with an example. We then characterise the arguments and attacks shared by every argumentation frameworks associated with the same minimal conflict graph.

Definition 8. The minimal conflict graph of an inconsistent knowledge K = (F, R, N ) is a tuple (F, J ), where J = conf licts(K). It can be represented with by an hypergraph where elements of F and elements of J represent nodes and hyper-edges respectively.

Please note that it is possible that two distinct argumentation frameworks have the same minimal conflict graph. There are two attacks (a 1 , a 2 ) and (a 2 , a 1 ). However, the argumentation framework AS K = (A ∪ {a 3 , a 4 }, C ) is composed of two more arguments:

a 3 : ({b(m)}, c(m)) a 4 : ({b(m)}, c(m) ∧ b(m))

We have that C = C ∪ {(a 1 , a 3 ), (a 1 , a 4 ), (a 4 , a 1 )}. We remind the reader that these two KBs have the same conflict graph.

Since different argumentation frameworks can have the same conflict graph, it gives us the intuition that there are similarities shared by all these argumentation frameworks. Definition 9. The set of consistent subsets of a knowledge base K is defined as consistent(K) = {X ⊆ F | ∃E ∈ conf licts(K) and E ⊆ X}.

Proposition 17. For every X, X ∈ consistent(K) such that there exists C ∈ conf licts(K) with C ⊆ X ∪ X , we have that (a 1 , a 2 ) ∈ C and (a 2 , a 1 ) ∈ C, where:

a 1 : (X, X) a 2 : (X , X )

These arguments and attacks are shared by all the argumentation frameworks sharing the same minimal conflict graph.

  : a attacks b iff the union of the conclusion of a and an element of the support of b are Rinconsistent. Formally, an argument a attacks an argument b denoted by (a, b) ∈ C (or aCb) iff ∃φ ∈ Supp(b) s.t. Conc(a)∪{φ} is R-inconsistent. The set of attackers of an argument a is denoted Att -(a) = {a | a Ca} and the set of arguments attacked by a, Att + (a) = {a | aCa }. -An argumentation framework AS K = (A, C) is the corresponding AF of K where A is the set of arguments and C is the corresponding attack relation defined above. -If X is a set of arguments, Base(X) is the union of the supports of the arguments of X: Base(X) = x∈X Supp(x).

Fig. 1 :

 1 Fig. 1: Representation of a 2-copy graph.

  and H ⊆ L. By definition, K and L are R-consistent, thus the arguments c = (K, K) and d = (L, L) exist. We have that a attacks c, c attacks d and d attacks b. Corollary 1. Let KB be a knowledge base such that R = ∅. There are |2 F \ C∈conf licts(K) Imp(C)| + 1 strongly connected components in AS K . Example 9 (cont.). The only minimal conflicts is C 1 = {a(m), b(m), c(m)}. We conclude that 2 F \ C∈conf licts(K) Imp(C) = {{a(m)}, {b(m)}, {c(m)}, {d(m)}, {a(m), d(m)}, {b(m), d(m)}, {c(m), d(m)}} and that there are 7 + 1 = 8 strongly connected components in AS K .

  2 : ({a(m), e(m)}, {a(m), e(m)}) -a15 2 : ({b(m), e(m)}, {b(m), e(m)}) -a16 6 : ({a(m), b(m), e(m)}, {a(m), b(m), e(m)}) -a17 2 : ({c(m), e(m)}, {c(m), e(m)}) -a18 6 : ({a(m), c(m), e(m)}, {a(m), c(m), e(m)}) -a19 6 : ({b(m), c(m), e(m)}, {b(m), c(m), e(m)})

Proposition 10 .

 10 Let AS = (A, C) be an argumentation framework. If there are two arguments a, b s.t. (b, a) ∈ C and there does not exist c ∈ A s.t. (c, b) ∈ C then there is no Datalog ± knowledge base K s.t. AS K = AS. In the next proposition, we prove the existence of particular arguments associated with a minimal conflict. Proposition 11. Let K be a Datalog ± knowledge base and AS K = (A, C) the corresponding instantiated AF with C a minimal conflict of K of size at least 2. If E, E ⊂ C such that |E| = |E | = |C -1| and E = E then the arguments (E, E) and (E , E ) are in A.

Proposition 13 .

 13 Let K be a knowledge base and AS K = (A, C) the corresponding instantiated AF. For every minimal conflict C of K s.t. C ⊆ F, there exists a complete directed subgraph of AS K with |C| arguments. Proof. We consider the case where |C| > 1, otherwise it is obvious. Let us consider the set of arguments A C = {a ∈ A|a = (S, S), S ⊂ C, |S| = |C| -1}. We know that |A C | = |C| and for all a, b ∈ A C s.t. a = b, we have that (a, b) ∈ C.

Example 12 .

 12 Let K = (F, R, N ) and K = (F, R , N ) be two knowledge bases with F = {a(m), b(m)}, R = ∅, R = {∀x(b(x) → c(x)} and N = {∀x(a(x) ∧ b(x) → ⊥)}.The argumentation framework AS K = (A, C) is composed of two arguments:a 1 : ({a(m)}, a(m)) a 2 : ({b(m)}, b(m))

In the rest of the paper, and in order to simplify the notation, we omit cycles corresponding to singleton orbits.

We say that a tuple of arguments (a1, . . . , an) is a cycle if and only if a1Ca2, . . ., an-1Can and anCa1.

Proposition 16. Let AS be a Datalog ± AF, we have that Ext pr (AS) ⊆ Ext cf 2 (AS).

Note that this result is not true in general (for graphs not generated from Datalog ± KBs). Moreover, we highlight here that Ext cf 2 (AS) ⊆ Ext pr (AS) in the Datalog ± setting by providing the following counter-example.

Example 11. Let us consider the knowledge base K = (F, R, N ):

The argumentation graph corresponding to this knowledge base is We have 3 preferred extensions Ext pr = {ε 1 , ε 2 , ε 3 } and 4 cf2 extensions Ext cf 2 = Ext pr ∪ {ε 4 } with:

We showed with Example 11 that the set of cf2 extensions are not included in the set of preferred extensions and thus not equal. Furthermore, contrary to expectations, the cf2 semantics (originally designed to better handle cycles in graphs) is producing a set of arguments with an inconsistent base. Indeed, the set ε 4 contains the arguments a 0 0 and a 5 5 which together form an inconsistent base.


Bruno Yun

Madalina Croitoru

Srdjan Vesic

How to generate a benchmark of logical argumentation graphs?

Keywords: Logic Based Argumentation, Argumentation Graphs, Benchmarks

In this demonstration extended abstract we present a workflow of how to generate a benchmark for logical argumentation graphs issued from knowledge bases expressed using existential rules.

Significance and demonstration workflow

The lack of large, practically inspired benchmarks in the argumentation field was acknowledged by the community long time ago, but became obvious with the appearance of the International Competition on Computational Models of Argumentation (ICCMA) 1 . Currently the competition uses randomly generated graphs with certain graph theoretical properties intuitively considered desirable (e.g Nofal et al. [START_REF] Nofal | Algorithms for decision problems in argument systems under preferred semantics[END_REF] and Cerutti et al. [START_REF] Cerutti | Computing Preferred Extensions in Abstract Argumentation: A SAT-Based Approach[END_REF]). Reasoning methods in argumentation are based on graph theoretical operations, the graph properties of the underlying graph can "make or break" tool performance.

In this demonstration extended abstract we focus on argumentation graphs issued from inconsistent logical knowledge bases. We use the existential rule instantiation of argumentation frameworks from [START_REF] Croitoru | What Can Argumentation Do for Inconsistent Ontology Query Answering?[END_REF] where nodes of these graphs represent all possible arguments one can construct over the knowledge base while the directed edges represent the attacks that model the inconsistency between two arguments. The reason for using existential rules stems from their versatility: they supsume certain subsets of Description Logics and are widely used as an ontological layer over relational databases. Therefore using existential rules knowledge bases as backbones for the argumentation graphs offers the possibility of using any inconsistent existential rule knowledge base developed part of a project or available online. Moreover, the argumentation graphs issued from this instantiation are known to respect certain graph theoretical properties: presence of isolated nodes, the existence of at least one strongly connected component with more than one nodes, presence of repetitive patterns of subgraphs and, last but definetely not least an impressive size. In [START_REF] Yun | A Structural Benchmark for Logical Argumentation Frameworks[END_REF] we show that even for a modest knowledge base composed of 7 facts, 3 rules and 1 binary negative constraint one gets an argumentation graph of 383 arguments and 32768 attacks. Let us stress that in [START_REF] Yun | Graph theoretical properties of logic based argumentation frameworks: Proofs and general results[END_REF] we also provide a complete graph structural characterisation of argumentation graphs constructed as above from knowl- bases solely composed of factual knowledge and negative constraints. Using such structural knowledge one can, for instance, design argumentation solvers that, despite the huge size, perform better in the presence of symmetries [START_REF] Lagniez | CoQuiAAS: A Constraint-Based Quick Abstract Argumentation Solver[END_REF]. This demonstration will show how one can generate a benchmark of argumentation graphs issued from logical knowledge bases expressed using existential rules. The demonstration workflow is visualised in 1. According to the workflow, the following steps need to be followed: first the existential rules knowledge base are generated or loaded. [START_REF] Yun | A Structural Benchmark for Logical Argumentation Frameworks[END_REF] provides a benchmark set of knowledge bases increasing in size with respect to number of facts, rules and negative constraints, as well as variations in how the negative constraints cover the facts. In the next step, for each generated or loaded knowledge base, the argumentation graph is constructed. This is done using the DAGGER (Datalog+/-Argumentation Graph GEneRator) tool demonstrated in [START_REF] Yun | Dagger: Datalog+/-argumentation graph generator[END_REF]. The DAGGER tool takes as input an inconsistent knowledge base expressed using existential rules (in .dglp format) and outputs the corresponding argumentation graph (in aspartix format). If needed the user can also visualise the graph or compute the extensions.

Figure 1 .

 1 Figure 1. The workflow for generating a benchmark of argumentation graphs issued from existential rules knowledge bases.

http://argumentationcompetition.org/


Ja-Myeong Koo

Seung-Boo Jung

Seung-Boo Jung Effect

EFFECT OF SURFACE FINISH OF SUBSTRATE ON MECHANICAL RELIABILITY OF IN-48SN SOLDER JOINTS IN MOEMS PACKAGE

HAL is

INTRODUCTION

The growth of fiber optic networks is driving the development of novel miniaturized and high performance optical components based on micro electro mechanical system (MEMS) technology [START_REF] Wang | MOEMS: Packaging and Testing[END_REF]. These needs for the micro optical electro mechanical systems (MOEMS) have pushed the development of area-array packages, such as ball grid array (BGA), wafer level package (WLP) and flip-chip, due to their smaller package size, more input/output (I/O) pins and higher electrical performance. For the MOEM package, the area array package using solder materials is simpler to process than the thermosonic bonding process using gold or aluminum metal bumps, and has better electrical performance and mechanical properties than the bonding process using conductive adhesives. In the area-array package, the solder joints provide a path for the dissipation of the heat generated by the device as well as furnish the electrical and mechanical connection between the device and substrate [START_REF] Koo | Mechanical and Electrical Properties of Sn-3.5Ag Solder/Cu BGA Packages during Multiple Reflows[END_REF]. Therefore, the reliability of solder joints has been a crucial issue in the MEMS and MOEMS packaging industries.

Essential solder materials for the MOEM package can be categorized as tin-lead (Pb-Sn), gold-tin (Au-Sn), indium (In) and indium-tin (In-Sn) [START_REF] Mickelson | Optoelectronic Packaging[END_REF]. The solder assembly using Sn-Pb solder has been the most popular approach. However, electrical and electronic equipment (EEE) manufacturers are showing more and more interest in the development of Pb-free solders and their soldering processes, due to the increasing environmental awareness of society, upcoming legislation on the use of Pb such as the waste of electrical and electronic equipment (WEEE) and restriction of hazardous substances (RoHS) directives and the tremendous market potential for 'green' products [START_REF] Koo | Reliability of In-48Sn solder/Au/Ni/Cu BGA Packages during Reflow Process[END_REF]. The Au-Sn solder shows low-creep behavior, but induces the residual stress at the joint interface during bonding and system use due to its high stiffness and bonding temperature. Pure In solder exhibits excellent heat and electrical conductivity, but has poor creep resistance [START_REF] Mickelson | Optoelectronic Packaging[END_REF]. In this respect, eutectic In-Sn (In-48 wt.% Sn) solder alloy has been considered as a Pb-free solder material with good potential in the MOEMS package, due to its very low melting point, great ductility and long fatigue life [START_REF] Mickelson | Optoelectronic Packaging[END_REF][START_REF] Koo | Reliability of In-48Sn solder/Au/Ni/Cu BGA Packages during Reflow Process[END_REF][START_REF] Morris | Microstructure and Mechanical Properties of Sn-In and Sn-Bi Solders[END_REF]. While industrial interest in the In-Sn solder is increasing, there has been relatively little fundamental research on its bonding characteristics and mechanical reliability [START_REF] Morris | Microstructure and Mechanical Properties of Sn-In and Sn-Bi Solders[END_REF].

During the bonding process, it is inevitable that the intermetallic compounds (IMCs) form and grow at the solder/substrate interface [START_REF] Koo | Effect of Substrate Metallization on Mechanical Properties of Sn-3.5Ag BGA Solder Joints with Multiple Reflows[END_REF]. The formation of a thin IMC layer between the molten solder and substrate during bonding is essential to the bondability of these two materials, while the excessive IMC formation at the interface weakens the solder joints. The metallurgical and mechanical properties of the solder joints formed during bonding significantly depend on the surface finish of the substrate as well as the solder material. With the adoption of Pb-free solders in the packaging technology, the selection of an appropriate metallization on a substrate plays an increasingly important role in the development of reliable solder joints [START_REF] He | Solid State Interfacial Reaction of Sn-37Pb and Sn-3.5Ag Solders with Ni-P Under Bump Metallization[END_REF]. Because the In-48Sn (in wt.%) alloy has the low solubility and dissolution rate of Au in the molten solder at a bonding temperature, the Au layer, which is a typical surface finish on the substrate in [START_REF] Koo | Reliability of In-48Sn solder/Au/Ni/Cu BGA Packages during Reflow Process[END_REF]. Therefore, the application of the In-48Sn solder joint has been limited in MEMS and MOEMS systems. The OSP surface finish has several advantages, such as its good wetting property, low cost and simple processing steps, while the In-Sn/Cu system exhibited fast IMC growth to consume the Cu layer rapidly [START_REF] Chuang | Phase Identification and Growth Kinetics of the Intermetallic Compounds Formed during In-49Sn/Cu Soldering Reactions[END_REF]. The In-Sn/ENIG solder joint may provide the key to successful application of In-48Sn solder, due to its thin Au layer, while the Ni 3 P formed at the interface between Ni 3 (Sn,In) 4 IMC and Ni-P substrate can weaken the solder joint [START_REF] Ho | Reaction Kinetics of Solder-Balls with Pads in BGA Packages during Reflow Soldering[END_REF]. The I-Ag surface finish provides excellent solderability and electrical properties, but neither the interfacial reaction nor mechanical property of In-Sn/I-Ag solder joint has been reported yet.

The purpose of this work is to investigate the interfacial reactions and shear properties of the In-48Sn solder joints with the surface finish on the BGA substrate during bonding, for the application of the In-48Sn solder in MOEM packages. Four commercial surface finishes over an underlying Cu pad were examined in this work: E-NG, ENIG, I-Ag and OSP.

EXPERIMENTAL PROCEDURE

Sample Preparation

The solder balls used in this study were In-48Sn (in wt.%) solder spheres having a diameter of 500 µm (Indium Corporation, U.S.A.). The substrate was a FR-4 BGA substrate. The solder bonding pad was designed as a solder mask defined (SMD) type with a pad opening of 460 ㎛ in diameter, a pad pitch of 2 mm in length and a solder mask (or side wall) of 10 ㎛ in thickness. Four surface finishes of the substrate over an underlying Cu (30 µm) pad were examined in this study: electroplated Ni (7 µm)/Au (0.7 µm), electroless Ni-P (5 µm)/immersion Au (0.15 µm), immersion Ag and organic solderability preservative (OSP). The electroless plated Ni layer contained about 15 at.% P and had an amorphous structure. The BGA substrates were cleaned using an ultra-sonic cleaner, and then dried with hot air. The solder balls were dipped into an RMA (Rosin Mildly Activated) flux and placed on the pads of the BGA substrates. All of the samples were bonded in a reflow machine (SAT-5100 + profile temperature raise heater, Rhesca Co., Japan). The heating rate, bonding temperature and time were 1.5 °C /s, 150 ± 3 °C and 100 s, respectively. After the bonding process, all samples were air-cooled to room temperature. The soldering process was carried out in a nitrogen atmosphere to prevent oxidation of the samples. The oxygen concentration in the bonding furnace was measured using an oxygen analyzer (MAXO2, Maxtec TM , U.S.A.) and kept below 1000 ppm during the bonding process. The samples were cleaned using an ultrasonic cleaner with a flux remover after the bonding process.

Observation of Microstructure

Upon completion of the bonding process, the specimens were mounted in cold epoxy, ground using 100, 400, 1200, 1500 and 2,000-grit SiC papers through a row of solder balls and polished with 0.3 ㎛ Al 2 O 3 powder. The microstructures of the samples were observed using scanning electron microscopy (SEM) in back-scattered electron imaging mode (BEI). For more accurate observation of the microstructures, solder was selectively etched with an etching solution consisting of 80 vol.% H 2 O, 10 vol.% HF and 10 vol.% H 2 O 2 . Elemental analysis was also carried out using an energy dispersive X-ray spectroscopy (EDS). For each sample, the IMC area formed at the interface was measured using an image analyzer (UTHCSA Image tool). The measured area was then divided by the width of the image, in order to estimate the average IMC layer thickness.

Ball Shear Test

The ball shear tests were conducted using a bonding tester (PTR-1000, Rhesca Co., Japan) at 3600±300 s after bonding, due to the influence of room temperature aging on the solder alloys. The experimental procedure for the BGA ball shear tests followed the JEDEC standard (JESD22-B117). Before testing, the 5 kgf load cell used in this study was calibrated using a 1 kgf standard weight. The displacement rate and probe height were 200 µm/s and 50 µm, respectively. The displacement at break was measured when the shear force had decreased by 67% (2/3) of its maximum value. The work of break was obtained from measuring the area of the F-x (shear forcedisplacement) curve using the image analyzer software. The cross-sections of the fractured specimens were observed using SEM.

RESULTS AND DISCUSSION

Microstructure

In-48Sn solders and four different surface-finished BGA substrates were bonded successfully in a nitrogen atmosphere. Figure 1 shows the SEM micrographs of the In-48Sn BGA solder joints with different surface finishes after bonding. Based on the EDS analysis results, the bulk solder exhibited a lamellar structure consisting of β (In 3 Sn) and γ (InSn 4 ) phases.

After bonding, there was a continuous facetted IMC layer, having a thickness of approximate 1.3 µm, between the solder and the topmost Au layer of the E-NG substrate, as shown in Fig. 1(a). The chemical composition of the IMC layer was In 66. [START_REF] Koo | Reliability of In-48Sn solder/Au/Ni/Cu BGA Packages during Reflow Process[END_REF] Au 33.6 (in at.%), corresponding to AuIn 2 . Generally, the Au layer of the E-NG substrate dissolved into the molten Sn-based solder to form AuSn 4 IMC particles at a bonding temperature of 225 °C within 30 s [START_REF] Ho | Reaction Kinetics of Solder-Balls with Pads in BGA Packages during Reflow Soldering[END_REF]. However, the topmost Au layer remained even after bonding at 150 °C for 100 s, because of very low solubility and dissolution rate of Au in the molten In-48Sn solder at 150 °C [START_REF] Lee | Getting Ready for Lead-Free Solders[END_REF].

All Au atoms of the ENIG substrate reacted with the molten solder and spalled off to the solder during bonding, due to the layer thinness. Therefore, neither Au nor Aubased IMC layer could be observed at the solder/substrate interface after bonding. The reaction between the molten solder and the exposed Ni layer resulted in the formation of a very thin IMC layer, having a thickness of approximate 0.21 µm, as shown Fig. 1 Generally, the diffusivity of atoms at the grain boundary was much faster than that of the same atoms in the lattice [START_REF] Shewmon | Diffusion in Solids[END_REF], suggesting that the cubes were formed by the Ni atoms diffusing through the grain boundaries of the IMC layer rapidly and subsequently reacted with the molten solder. A very thin reaction layer could be observed at the interface between the Ni 3 (Sn,In) 4 and Ni-P layers. The reaction layer was too thin to determine its chemical composition exactly using EDS and EPMA analyses. It was reported in the previous study using transmission electron microscope (TEM) analysis that the reaction layer formed between the Ni 3 (Sn,In) 4 and Ni-P layer during the liquid/solid reaction was Ni 3 P [START_REF] Koo | Interfacial Reactions between In-48Sn Solder and Electroless Nickel/Immersion Gold Substrate during Reflow Process[END_REF].

The topmost Ag layer of the I-Ag substrate was completely depleted and disappeared at the solder/substrate interface after bonding. It is suggested that the consumption of the Ag layer was faster than that of the Au layer during bonding. There were two different IMCs at the interface between the solder and the exposed Cu layer after bonding. Based on the EDS analysis results, the chemical compositions of the lower and upper IMC layers, marked as IMC-1 and IMC-2 in Fig. 1(c

Ja-Myeong Koo and Seung-Boo Jung EFFECT OF SURFACE FINISH OF SUBSTRATE ON MECHANICAL RELIABILITY OF IN-48SN SOLDER...

the IMC-1 and IMC-2 layers were approximate 1.7 µm and 1.2 µm, respectively, it is suggested that IMC-1 was the dominant phase in the In-48Sn/I-Ag interfacial reactions. These results were consistent with those in the previous studies. Kim et al. found that the solid-state reactions between the In-48Sn and Cu substrate resulted in the formation of Cu(In,Sn) 2 and Cu 6 (Sn,In) 5 IMC layers, containing In 52 Cu 32 Sn 16 (in at.%) and Cu 56 Sn 24 In 20 (in at.%), respectively [START_REF] Kim | Interfacial Reactions and Growth kinetics for Intermetallic Compound Layer between In-48Sn Solder and Bare Cu Substrate[END_REF]. The chemical compositions of IMC-1 and IMC-2 in this work were similar to those of Cu 6 (Sn,In) 5 and Cu(In,Sn) 2 , respectively. This suggests that the IMC-1 and IMC-2 corresponded to Cu 6 (Sn,In) [START_REF] Morris | Microstructure and Mechanical Properties of Sn-In and Sn-Bi Solders[END_REF] and Cu(In,Sn) 2 , with a minor Ag element, respectively. Moreover, it was observed that the intermetallics, marked as B in Fig. 1(c (in at.%), respectively. The IMCs which spalled off to the solder during bonding had higher Ag content than the IMCs that existed at the solder/substrate interface.

The interfacial reaction of the In-48Sn solder with the OSP substrate resulted in the formation of two differently shaped IMCs, consisting of needle and planar types, as shown in Fig. 1(d). The chemical composition of the IMCs was Cu 57.4 Sn 25. [START_REF] Koo | Effect of Substrate Metallization on Mechanical Properties of Sn-3.5Ag BGA Solder Joints with Multiple Reflows[END_REF] In 17.0 (in at.%), corresponding to Cu 6 (Sn,In) 5 . Sommadossi et al. reported that only Cu 6 (Sn,In) 5 IMC, having two different morphologies, was formed at the interface after bonding below 200 °C [START_REF] Sommadossi | Characterization of the Reaction Process in Diffusion-Soldered Cu/In-48 at.% Sn/Cu Joints[END_REF]. Laurila et al. suggested that the needle-shaped IMC was formed by the rapid dissolution of Cu in the molten solder followed by the local constitutional supercooling of the molten solder [START_REF] Laurila | Interfacial Reactions between Lead-Free Solders and Common Base Materials[END_REF]. These results were consistent with our results. The needle-shaped Cu 6 (Sn,In) 5 intermetallics, marked as C in Fig. 1(d), were also found in the bulk solder. It is suggested that these intermetallics spalled off to the molten solder during bonding.

Ball Shear Properties

The ball shear tests were carried out with four different surface finishes of the substrate, to investigate the effect of the surface finishes on the shear properties, such as shear force, displacement at break, work of break and fracture mode, of the In-48Sn BGA solder joints after bonding. The complex shape of the solder joint made it difficult to define the shear area and gage length. In this work, therefore, the shear force, displacement at break and work of break were used to evaluate the mechanical Figure 2 shows the relationship between the shear force of the In-48Sn solder joint and the surface finish of the BGA substrate after bonding. The In-48Sn/E-NG and In-48Sn/ENIG solder joints showed the highest and lowest shear forces among the four different solder joints, respectively. The shear force of the In-48Sn/I-Ag solder joint was higher than that of the In-48Sn/OSP solder joint.

Figure 3 shows the relationship between the displacement at break of the In-48Sn solder joint and the surface finish of the BGA substrate after bonding. The values for the I-Ag and OSP surface finishes, forming the Cu-based IMC at the interface, were higher than those for the E-NG and ENIG surface finishes. In particular, the In-48Sn/I-Ag solder joint showed the highest displacement at break among the four different solder joints.

Figure 4 shows the relationship between the work of break of the In-48Sn solder joint and the surface finish of the BGA substrate after bonding. The work of break strongly depended on the displacement at break, rather than the shear force. The In-48Sn/I-Ag and In-48Sn/ENIG solder joints exhibited the highest and lowest work of break among the four different solder joints.

The crack propagated along the weakest layer or interface, which determined the mechanical integrity of the solder joint. Therefore, failure mode has been an important acceptance criterion of the ball shear test. Figure 5 shows the fracture surface of the fractured samples after the shear tests for the In-48Sn solder joints in terms of the surface finish.

There were many AuIn 2 intermetallics and dimples induced by the AuIn 2 IMC on the fracture surface in the In-48Sn/E-NG solder joint. The AuIn 2 IMC improved the shear force of the In-48Sn solder joint, but degraded the displacement at break and work of break. Therefore, it was suggested that the AuIn 2 IMC significantly strengthened the solder joint, while the cracks easily propagated along the IMC, because of its brittleness.

The fracture surfaces of the In-48Sn/ENIG solder joints showed a mixed mode containing both ductile and brittle fractures. Many Ni 3 (Sn,In) 4 intermetallics were observed on the fracture surface in the In-48Sn/ENIG solder joint. Therefore, it is normal that the formation of the continuous Ni 3 (Sn,In) 4 IMC layer degraded the mechanical integrity of the solder joint, because of its brittleness. These results showed that the ENIG surface finish was unsuitable for the In-48Sn solder.

The fracture of the In-48Sn/OSP solder joints propagated along the bulk solder. The fracture surface showed typical ductile fracture characteristics. Therefore, the mechanical properties of the solder joints were determined by those of the bulk solder. During bonding, Cu was dissolved in the molten solder and the Cu 6 (Sn,In) 5 IMC spalled off to the solder, as stated above. Therefore, the solder/OSP solder joints showed high shear properties, due to the solid-solution hardening and dispersion hardening.

The fracture characteristics of the In-Sn/I-Ag solder joints were similar to those of the In-Sn/OSP solder joints. Moreover, the shear properties of the In-Sn/I-Ag solder joints were higher than those of the In-Sn/OSP solder joints. Ag in the substrate reacted with the molten solder rapidly, and many intermetallics, spalling off to the solder, were observed in the bulk solder, as stated above. Ag and its reaction products strengthened the bulk solder better than Cu and its reaction products. Therefore, it is normal that the solder joint showed excellent mechanical properties, due to the solid-solution hardening and dispersion hardening. The I-Ag surface finish was the

CONCLUSIONS

Interfacial reactions and shear properties of the In-48Sn solder joints were investigated with four different surface finishes of the BGA substrate after bonding, to determine the optimum surface finish of the substrate for the application of the In-48Sn solder in the MOEMS package. The results are summarized as follows.

The interfacial reaction between the solder and E-NG substrate formed a continuous facetted AuIn 2 IMC layer during bonding. The solder/E-NG solder joint exhibited the highest shear force, while the displacement at break and work of break was low, due to the brittleness of AuIn 2 IMC.

During bonding, continuous Ni 3 (Sn,In) 4 and Ni 3 P IMC layers were formed at the interface between the solder and ENIG substrate. The brittleness of the Ni 3 (Sn,In) 4 IMC layer weakened the mechanical integrity of the solder joints.

Cu 6 (Sn,In) 5 IMC, having two different morphologies, was observed after bonding. The dissolution of Cu in the molten solder and the spallation of the Cu 6 (Sn,In) 5 IMC improved the shear properties of the solder joints.

Cu 6 (Sn,In) 5 and Cu(In,Sn) 2 IMCs, with a minor Ag element, were formed at the solder/I-Ag interface during bonding. The In-48Sn/I-Ag solder joint showed the best shear properties among the four solder joints after bonding, because of the dissolution of Ag and Cu and the IMCs dispersed in the bulk solder.

  (b). The chemical composition of the IMC layer consisted of Sn 45.8 Ni 37.9 In 16.3 (in at.%), corresponding to Ni 3 (Sn,In) 4 . Cubes of Ni 3 (Sn,In) 4 , marked as A in Fig. 1(b), existed over the thin Ni 3 (Sn,In) 4 IMC layer.

  Figure 1 SEM micrographs of the interface between the In-48Sn (in wt.%) solder and BGA substrate with four different surface finishes over an underlying Cu pad after reflow: (a) E-NG, (b) ENIG, (c) I-Ag and (d) OSP.

Figure 3

 3 Figure 3 Displacement at break of the In-48Sn (in wt.%) solder joints with the surface finishes of the BGA substrate after bonding.

Figure 2 Figure 4

 24 Figure 2 Shear force of the In-48Sn (in wt.%) solder joints with the surface finishes of the BGA substrate after bonding.

Figure 5

 5 Figure 5 SEM micrographs of fracture surfaces of the shear-tested Sn-48Sn (in wt.%) BGA solder joints with four different surface finishes over an underlying Cu pad after bonding: (a) E-NG, (b) ENIG, (c) I-Ag and (d) OSP. Figures (b), (d), (f) and (h) show the magnified images of region A in Figs. (a), (c), (e) and (g), respectively.

  ), spalled off to the solder after bonding. The chemical compositions of the intermetallics were Cu 65.2 Sn 13.3 In 13.3 Ag 8.2 (in at.%) and In 44.5 Ag 24.7 Cu 16.2 Sn 14.6

ACKNOWLEDGEMENTS

This work was supported by grant No. RTI04-03-04 from the Regional Technology Innovation Program of the Ministry of Commerce, Industry and Energy (MOCIE).