Learning argumentation frameworks from labelings

1.Introduction

An abstract argumentation framework due to Dung [15] is defined as a graph, where the nodes are arguments and the edges represent attacks between these arguments. An attack from an argument A to another argument B means that, if we consider the argument A to be acceptable, then we have to reject B, since A contradicts B. The goal of this approach is to model human argumentation in a formal manner and to use this model for reasoning. Abstract argumentation frameworks are interpreted using the notion of an (argumentation) semantics. A semantics characterizes acceptable sets of arguments (called extensions), which are supposed to model a valid outcome of the argumentation represented by an argumentation framework. In particular, they usually require that extensions are conflict-free, i.e., that there is no conflict between arguments of the extension, and that it defends itself, i.e., it counterattacks all its attackers (the latter property is called admissibility). While Dung proposed several different semantics in his seminal paper, like complete, grounded, preferred, and stable semantics, there have since been many proposals for new semantics [4], all with different goals in mind.

Extension-based semantics focus on the accepted arguments only, so, any extension with respect to some semantics only consists of the arguments that are considered acceptable. That means we also get the implicit knowledge that all other arguments are not accepted. However, we do not know for what reason these arguments are not accepted. They could be directly attacked by some acceptable argument, meaning the extension actively contradicts them. In contrast to that they could also be not accepted because they are part of some conflict, unrelated to the acceptable arguments, which means these arguments could potentially also be compatible with the acceptable arguments. This additional information can be encoded in labelings [17]. In a labeling each argument of the argumentation framework receives a label, if it is considered acceptable the argument is labeled in, if the argument is attacked by some acceptable argument it gets the label out and otherwise it receives the label undec.

In Inductive Logic Programming [21] we derive from a given set of examples and background knowledge a hypothesized logic program that entails these examples. In a similar manner, algorithms for Bayesian Network Learning [13,18] are concerned with inducing a bayesian network from given data. Overall, both of these approaches are concerned with generalizing from observations or examples to a program or network which entails this knowledge and therefore also allows for inferring new knowledge in line with the input knowledge.

This approach is also interesting for the field of argumentation. In general, argumentation semantics allows us to perform inference with an abstract argumentation framework, by determining semantical information (extensions or labelings) from given syntactical information (in the form of an argumentation framework). In this work, we are, as already hinted at above, interested in the reverse direction, i.e., the process of learning a syntactic structure from semantical information. So, given a set of labelings we wish to infer a suitable attack relation that explains this input. That means, we want to find an argumentation framework that has at least those labelings.

This is interesting, if we look for example at the area of argument mining [20] which is concerned with extracting arguments and their relations from text. There, extracting the relations between arguments is especially hard [18]. This is one area where inductive learning approaches are useful, since they can aid us in constructing the attack relation for a set of arguments. Additionally, learning the attack relation for a set of arguments can also be helpful in terms of explainability [1,12] since this allows us to construct better argumentative explanations based on the underlying argumentation framework itself, see e.g., [16,27]. It will also allow us to better understand how the labelings originated and how we could challenge them, as the following example will highlight.

Assume a situation where we are able to meet up with a person A that has an anti-vax stance. We are able to discuss with them about the topic of the COVID-19 vaccine and our goal is to understand their personal reasoning process. Doing so may allow us to find better counterarguments in future discussions on the topic and it will also aid us in identifying false conclusions that A might have made, so that we can potentially clear them up. The internal reasoning process of A is represented as an argumentation framework, which is hidden to us. During the discussion, we may ask A for his opinion on different statements on the topic. From A’s answers we can then infer a labeling, which essentially assigns to each argument their stance, i.e., either they agree (in), disagree (out) or their stance is unclear/unknown (undec). Given such a labeling, our goal is to reconstruct the hidden argumentation framework of A.

For example, lets consider the following four arguments:

From our first discussion with A we may conclude that they agree with the arguments a and d while disagreeing with b and c. This would then translate to the complete labeling ℓ1={in:{a,d},out:{b,c},undec:∅}. A complete labeling is defined such that arguments not attacked by an out-labeled argument must be labeled in, all arguments attacked by an in-labeled arguments are labeled out and otherwise the argument is labeled undec. If we now try to reconstruct their internal argumentation framework, for example by simply brute-forcing every possible combination of attacks, we will find that multiple argumentation frameworks are consistent with this labeling. See for example the three argumentation frameworks in Fig. 1. At this point, it is impossible for us to decide which argumentation framework correctly represents the reasoning of A. If we were to choose one, we would have to make some additional assumptions and discard all other argumentation frameworks. This may lead to unintentionally discarding the actual framework that we are looking for. For that reason, it is sensible to maintain a representation of all of these argumentation frameworks. This allows us to easily incorporate additional information in the future.

For example, if we want to refine our understanding of A’s reasoning, we could initiate another discussion with them so that we can obtain another complete labeling. After our second discussion, we may get the labeling ℓ2={in:{c},out:{a},undec:{b,d}}. With this additional labeling, we can again reconstruct argumentation frameworks that are consistent with both ℓ1 and ℓ2. In our example, we will find that only F2 and F3 from Fig. 1 are consistent with both labelings, while F1 is only consistent with ℓ1. This again highlights the advantage of maintaining a representation of all consistent argumentation frameworks after each step.

Fig. 1.

Some argumentation frameworks that were reconstructed from the labelings ℓ1 and ℓ2 of the arguments {a,b,c,d} as defined above. Note that these frameworks are not supposed to model factual information but rather the reasoning process of someone with potentially flawed logic or limited understanding of the topic at hand.

With the argumentation framework(s) that we have learned from the labelings, we can then for example try to identify missing or nonsensical attacks (e.g. there should probably be an attack from b on c). Another thing we can do, is identify key arguments that we can disprove to sway the opinion of the person A. For example, if we present some evidence that the vaccine development has in fact not been rushed, A might change their opinion on the argument a and subsequently this could influence their stance on arguments b and c.

In this work, we will answer the following research question:

We explicitly allow the labelings to have different semantics in order to be more general, especially since different semantics have different advantages depending on the application [4]. In other words, for a given set of labelings L with respect to different semantics, we want to define a method to construct the set of all argumentation frameworks F, such that at least all labelings in L are labelings of F. In that case, we will also say that the argumentation framework F is consistent with L.

The general problem of learning argumentation frameworks has only received limited attention so far [23,25] and none of these works are able to address the exact scenario we outlined above. In their paper, Niskanen et al. [23] investigate the synthesis of argumentation frameworks from positive and negative examples. These examples are extensions with respect to conflict-free, admissible, complete or stable semantics. A positive example E is then encoded in some logical formula, representing the information in E. All positive examples are encoded with a corresponding formula for their semantics and the negative examples are encoded as the negation of those formulae. Their approach also allows for the attachment of weights to each example. The encoded examples, together with their weights, are given to a MaxSAT solver, which returns the optimal solution, i.e., an argumentation framework, which is consistent with all or most of the positive examples and the least of the negative examples.

On the other hand, Riveret et al. [25] propose an approach for learning attacks from labelings. Their algorithm is built around the grounded semantics and takes a stream of labelings as input. Since it is not possible to reconstruct the argumentation framework by only knowing the (uniquely determined) grounded extension, Riveret et al. decided to extend their scenario as follows. Their algorithm works with knowledge about the sub-frameworks of the argumentation framework, i.e., restrictions of the graph on different subsets of arguments. The input of their algorithm therefore consists of grounded labelings of different sub-frameworks. For the process of learning the hidden argumentation framework we start with a weighted argumentation framework, where every attack has an initial weight of 0. Then, for each input labeling we iterate over all combinations of two arguments and check whether they satisfy one of four rules, which essentially encode the different conditions a grounded labelings has to fulfill. If a rule is satisfied, the weight of the attacks between these two arguments are updated accordingly. After examining all input labelings we remove all attacks whose weight is below a certain threshold from the argumentation framework. The resulting argumentation framework is then the approximation of the original hidden argumentation framework.

While the above mentioned approaches can be used to construct argumentation frameworks from labelings or extensions, they only return a single argumentation framework as a result. This might not always be desirable, as we illustrated in the above example. In the case of the approach by Riveret et al. [25], their algorithm also relies on additional information about sub-frameworks.

Therefore, in this work, we propose an algorithm that better addresses this scenario by maintaining a representation of all consistent argumentation frameworks at all times. In general, our algorithm works according to the following procedure: We are given a set of arguments Arg as well as a set of input labelings L. For each input labeling ℓ∈L we compute a set of attack constraints Cℓ={Ca,σ}a∈Arg, depending on its semantics. Afterwards we combine these constraints, so that we have one constraint Ca for each argument a∈Arg. Finally, they can then be used to construct a set of argumentation frameworks F which satisfy all constraints. That means every argumentation framework F∈F is consistent with the set of input labelings L.

To summarise, the contributions of this paper are as follows:

In Section 2 we introduce the necessary background knowledge on abstract argumentation and labeling-based semantics and Section 6 concludes the paper. Proofs of technical results can be found in the Appendix.

2.Background

We consider abstract argumentation frameworks [15] defined as follows.

We say that an argument a∈Arg attacks an argument b∈Arg if (a,b)∈R. Given a set S⊆Arg we say S attacks a if for some b∈S we have (b,a)∈R, and likewise a attacks S if for some b∈S we have (a,b)∈R.

A labeling-based semantics maps each argumentation framework to a set of labelings [8,17]. These are functions that assign to each argument a label indicating the acceptance status of the argument. The labeling-based semantics that we focus on in this paper use three labels: in indicates that the argument is accepted, out that the argument is rejected, and undec that the acceptance of the argument is undecided. In this paper we use the labeling-based approach since it allows us to distinguish not only accepted and non-accepted arguments, but also rejected arguments and undecided arguments. We will refer to a labeling-based semantics simply as a semantics.

A semantics σ is represented by a condition that determines whether a labeling ℓ of F is a σ-labeling. We now define the semantics that we focus on in this paper, namely the complete, grounded, preferred and stable semantics. While not typically considered to be a semantics, we also define the notion of a conflict-free and admissible labeling and treat these conditions as semantics. For that, we will use the definitions from [8] or definitions that are equivalent to those.

A labeling is conflict-free whenever no two arguments a and b exist such that a attacks b and both are labeled in.

A labeling is admissible whenever it is conflict-free and, in addition, every argument a that is accepted is attacked only by arguments that are rejected. This amounts to requiring accepted arguments to be defended: in an admissible labeling, if a is accepted then all attackers of a are rejected and thus (as a consequence of Condition 2 in Definition 2.3) a is defended from these attackers by other arguments that are accepted.

A labeling is complete whenever it is admissible and, in addition, (1) every argument attacked by an accepted argument is rejected, and (2) every argument whose attackers are rejected is accepted. This condition amounts to requiring defended arguments to be accepted: if all attackers of an argument a are attacked by some argument that is accepted, then all attackers of a are rejected and hence a is accepted.

The remaining semantics are all defined in terms of complete labelings. Firstly, a labeling is grounded if it is complete and if it is minimal with respect to accepted arguments. The grounded labeling of an argumentation framework is unique and represents the most skeptical point of view on which arguments to accept [8,15]. A preferred labeling is a complete labeling that is maximal with respect to accepted arguments. Preferred labelings represent maximally credulous points of view on which arguments to accept. Finally, a stable labeling is a complete labeling in which no argument is undecided.

In the following, we will denote with σ(F) the set of all σ-labelings of F. The definitions in this section immediately imply the following relationships between the different semantics [8,15].

3.Learning from labelings

In this section, we introduce a novel algorithm for learning argumentation frameworks from labelings with the goal of constructing (or representing) all argumentation frameworks that are relevant to the input labelings. We start with formally defining the AF learning problem that we want to address. Afterwards, we define the concept of attack constraints and finally describe in detail our algorithm to solve this problem.

For the remainder of this work, we will consider the set of arguments Arg to be fixed. We also denote with S the set of all semantics. First, we define the notion of an input, which is a pair of the form (ℓ,σ) with a labeling ℓ and some semantics σ∈S.

We will also sometimes refer to ℓ as an input labeling. So, given a set of inputs L={(ℓ1,σ1),…,(ℓn,σn)}, our intention is to construct a set of argumentation frameworks F, such that for all F∈F and each i=1,…,n, we have that ℓi is a σi-labeling of F. More formally, we are concerned with the following problem:

The general idea behind our approach to solve the AF learning problem is as follows. We use propositional atoms of the form rba to express the existence of attacks (b,a)∈R in some argumentation framework F=(Arg,R). Then, given an input (ℓ,σ), we construct a set of attack constraints Cℓ={Ca | a∈Arg}. For a labeling ℓ we will therefore have one attack constraint Ca for each argument a∈Arg. These attack constraints depend on the semantics σ of the input as well as the labeling ℓ itself. Together, they express what an argumentation framework F has to satisfy such that ℓ is a σ-labeling of F. We will then use the fact that the models of these formulas directly correspond to argumentation frameworks by using the mapping functions described in Definition 3.3.

This approach can then also be extended to a set of input labelings L={(ℓ1,σ1),…,(ℓn,σn)}. So, for a given set of input labelings L we compute the constraints Cℓi for each labeling ℓi, depending on its semantics σi. Then, each interpretation that satisfies all attack constraints of all input labelings represents an argumentation framework F where all labelings ℓi are σi-labelings of F. It follows, that the set of models that satisfy all attack constraints exactly corresponds to the set of argumentation frameworks F as specified in the above scenario description. In other words, we construct the set of all argumentation frameworks that have at least the given input as their labelings, but they can also have additional labelings.

3.3.Algorithm

In the following we will introduce an algorithm for learning argumentation frameworks from labelings. The input of this algorithm is a set of arguments Arg and a set of inputs L={(ℓ1,σ1),…}. Our algorithm works in an iterative way. That means, each input labeling is processed independently one by one. So, the algorithm is able to consider a stream of input labelings and provide intermediate results after each processed labeling. The procedure for the algorithm is shown in Algorithm 1. In each iteration, the input parameters of the algorithm include a mapping C of the arguments to their current attack constraint. Before processing the first input labeling we assign to each argument a the initial attack constraint Ca=⊤. So, by default no attacks are necessary to satisfy the constraint, which means all argumentation frameworks F=(Arg,R) are consistent with the empty set of conditions, as would be expected.

The main procedure of the algorithm can essentially be split into three parts:

• (1) Computing the labeling constraint Cℓ for the input labeling.

• (2) Combining the labeling constraint Cℓ with the input constraints C.

• (3) Constructing the set of argumentation frameworks F from the constraints in C.

Algorithm 1

Iterative algorithm for learning argumentation frameworks from labelings

In each iteration of the algorithm we take a mapping of constraints C, the set of arguments Arg and some input (ℓ,σ)∈L as input. When we reference the mapping as Ca we mean the constraint for argument a as stored in the mapping C.

For the input we compute the attack constraint Ca,ℓ of each argument a∈Arg via the semantic constraint function AttConσ.

In the second step, we combine the labeling constraint Ca,ℓ for each argument a with the existing attack constraint Ca. We want to compute argumentation frameworks that satisfy all input labelings, therefore the combined constraint for an argument a is just the logical conjunction of the constraints of the argument for each labeling. The updated constraint overwrites the constraint for the argument in the mapping C.

The third and final step is to construct the set of argumentation frameworks F for the updated attack constraint mapping C. For this, we use the mapping modelToAttacks(A) described in Definition 3.3. In particular, we compute the set of models Ma for each argument a∈Arg. It should be noted that the model computation for these constraints are independent of each other and thus can be done in parallel. If we then pick one model Ai∈Mai for each argument, we obtain a consistent argumentation framework F=(Arg,modelToAttacks(A1∪⋯∪An)). If we consider all different combinations of models we obtain the set of all consistent argumentation frameworks F.

This step is optional, since we only need the mapping of attack constraints C with the updated constraints for each argument for further learning. So, after each learning iteration the algorithm returns the updated set of attack constraints C and (if wanted) the set of constructed argumentation frameworks F.

Regarding the complexity of constructing argumentation frameworks for a set of attack constraints. We can consider the constraints in clausal form, which follows easily from the definition of the semantic constraint functions. A very helpful property of the attack constraints in clausal form is, that all clauses contain at most one negated literal, i.e., each clause is a dual-horn clause. That means, the process of constructing an argumentation framework for a given set of attack constraints can be considered as a Dual-Horn SAT problem, which is P-complete [14]. Thus, the construction argumentation frameworks can be done in polynomial time, more precisely in linear time with respect to the size of the attack constraints which is in O(n2|L|), where n is the number of arguments and L is the set of learned labelings. This can be further improved by using parallel computations, as shown by our experiments in Section 4.

3.3.1.Properties

In the following we will look at some useful properties that the previously defined algorithm satisfies, namely soundness, completeness and monotonicity.

Theorem 3.5.

Let L be a set of inputs and F is the set of argumentation frameworks constructed by the procedure described in Algorithm 1 by iteratively processing L. For every σi in the set of inputs there exists a sound and complete semantic constraint function, i.e., σi∈{cf,ad,co,st}.

The algorithm is sound for all input labelings, i.e.,

∀F∈F:∀(ℓi,σi)∈L:ℓ is a σi-labeling of F

The algorithm is complete for all input labelings, i.e.,

∀G=(Arg,R):(∀(ℓi,σi)∈L:ℓ is a σi-labeling of G)⟹G∈F

As shown in Theorem 3.5 the algorithm based on the above defined attack constraints is sound and complete for any combination of inputs with respect to all four semantics. That means, the algorithm computes exactly the set of argumentation frameworks that are consistent with the input labelings. From the proof of Theorem 3.5 it also follows that the order in which the labelings are processed by the algorithm does not matter.

Proposition 3.4.

Let Arg be a set of arguments and ℓ1, ℓ2 are labelings. With F we denote the set of argumentation frameworks constructed by Algorithm 1 for the input labelings ℓ1 and ℓ2.

Then, the order in which the labelings are learned has no influence on the constructed set of argumentation frameworks F.

Another property of the algorithm is monotonicity (see Theorem 3.6), or more precisely the algorithm is monotonically refining. That means, if we have a set of labelings L2 with L2⊇L1 then the set of argumentation frameworks F2 constructed for L2 will be a subset of the frameworks constructed for L1. In other words, if we learn an additional labeling the number of argumentation frameworks that satisfy all attack constraints can only stay the same or become smaller.

Theorem 3.6.

Let Arg be a set of arguments and L1, L2 are sets of inputs. F1, F2 denote the sets of argumentation frameworks constructed by Algorithm 1 for the input labelings in L1 and L2 respectively.

The algorithm for constructing argumentation frameworks from labelings is monotonically refining, i.e.,

∀L1,L2∈L(Arg):L1⊇L2⟹F1⊆F2

3.4.Example

This section will showcase the application of Algorithm 1. Assume the following situation. Unknown to us, there is the hidden argumentation framework as shown in Fig. 2. Given are only the set of arguments Arg={a,b,c,d,e} and the set of inputs L={(ℓ1,ad),(ℓ2,co),(ℓ3,cf)}. The three input labelings are shown in Fig. 3. Our goal is to construct all argumentation frameworks that are consistent with these three labelings.

Fig. 2.

The hidden argumentation framework from which the input labelings are generated.

Fig. 3.

The three input labelings: ℓ1 is admissible, ℓ2 is complete and ℓ3 is conflict-free.

We start the process of learning with the admissible labeling ℓ1={in={a},out={b,c},undec={d,e}}. The first step is computing the labeling-specific attack constraint for each argument. The labeling ℓ1 is admissible, so we will use the semantic constraint function AttConad from Definition 3.8. The argument a is labeled in, that means it cannot be attacked by any in- or undec-labeled argument. b and c are labeled out, thus they have to be attacked by the only in-labeled argument a. The arguments d and e are undec which means they cannot be attacked by the in-labeled argument a. That leaves us with the following attack constraints after the first labeling:

Ca=¬raa∧¬rda∧¬reaCb=rabCc=racCd=¬radCe=¬rae

After processing the first labeling we know that the argument a must attack b and c. We also know that some attacks cannot exist, but there are still many possibilities for attacks. For example, the argument a can still be attacked by b or c and the resulting frameworks would still be consistent with ℓ1. There can also be many different combinations of attacks between the arguments b, c, d and e. This iteration of the algorithm would then return the set of attack constraints C={Ca,Cb,Cc,Cd,Ce}.

Lets consider the next labeling ℓ2={in={b,c},out={a,d},undec={e}}, which is complete. For this labeling we will use the semantic constraint function AttConco (see Definition 3.9). This labeling tells us, for example, that the out-labeled arguments a and d must be attacked by either b or c. The in-labeled arguments b and c cannot be attacked by any in- or undec-labeled arguments. The argument e is the only undec-labeled argument and since ℓ2 is complete it follows that e has to attack itself. This gives us the following set of attack constraints Cℓ2 for the labeling ℓ2:

Ca,ℓ2=rba∨rcaCb,ℓ2=¬rbb∧¬rcb∧¬rebCc,ℓ2=¬rbc∧¬rcc∧¬recCd,ℓ2=rbd∨rcdCe,ℓ2=¬rbe∧¬rce∧ree

We now have to combine the constraints C from the last step with the contraints Cℓ2 from this step. Since the argumentation frameworks we are looking for should be consistent with all input labelings we use a conjunction to combine the attack constraints. So, for each argument we set Ca=Ca∧Ca,ℓ2. If we do this for all arguments, we obtain the following attack constraints:

Ca=¬raa∧¬rda∧¬rea∧(rba∨rca)Cb=rab∧¬rbb∧¬rcb∧¬rebCc=rac∧¬rbc∧¬rcc∧¬recCd=¬rad∧(rbd∨rcd)Ce=¬rae∧¬rbe∧¬rce∧ree

We have now reduced the number of possibilities even further. The argument a has to be attacked by either b or c and cannot be attacked by any other argument. The arguments b and c have to be attacked by a. They could also be attacked by d, but this attack is optional. d has to be attacked by b or c and optionally can also be attacked by itself or e. Finally, e has to attack itself and can also optionally be attacked by d. One observation we can make is that most of the uncertainty in the attack constraints is related to the argument d as it can still optionally attack b, c, e and itself. The algorithm then returns the updated set of attack constraints C.

The third and last input labeling ℓ3={in={d},out={e},undec={a,b,c}} is conflict-free. In our current situation it is very helpful to learn this labeling, because the fact that d is labeled in allows us to clear the uncertainty regarding its outgoing attacks. The labeling tells us that d cannot attack a, b, c and itself. In addition to that, we now know that d has to attack the out-labeled argument e since d is the only argument with the label in. For the labeling ℓ3 we obtain the following attack constraints:

Ca,ℓ3=¬rdaCb,ℓ3=¬rdbCc,ℓ3=¬rdcCd,ℓ3=¬rddCe,ℓ3=rde

Again, we combine the attack constraints Cℓ with the constraints C from the previous step via a conjunction. When combining the constraints we can also apply simplifications, however this is not necessary in this example. So, the attack constraints after learning all three labelings look like this:

Ca=¬raa∧¬rda∧¬rea∧(rba∨rca)Cb=rab∧¬rbb∧¬rcb∧¬rdb∧¬rebCc=rac∧¬rbc∧¬rcc∧¬rdc∧¬recCd=¬rad∧¬rdd∧(rbd∨rcd)Ce=¬rae∧¬rbe∧¬rce∧rde∧ree

These attack constraints now represent exactly the set of argumentation frameworks that are consistent with all three input labelings. The final step of the algorithm is now to construct these argumentation frameworks. Here, we use the fact that the atoms used in the attack constraints directly correspond to attacks in an argumentation framework, as described in Definition 3.3. First, we compute the models of the attack constraints of each argument:

Ma={[rba→true],[rca→true],[rba,rca→true]}Mb={[rab→true]}Mc={[rac→true]}Md={[rbd→true],[rcd→true],[rbd,rcd→true],[rbd,red→true],[rcd,red→true],[rbd,rcd,red→true]}Me={[rde,ree→true]}

The next step is constructing the corresponding partial attack relations for each model with the method modelToAttacks(A). This is quite simple, since every atom directly represents an attack. For example, the model Aa,1=[rba→true] would have the corresponding partial attack relation Ra,1={(b,a)}, since rba is the only atom which is valuated as true in Aa,1. Overall, we construct the following partial attack relations for each argument:

Ra={{(b,a)},{(c,a)},{(b,a),(c,a)}}Rb={{(a,b)}}Rc={{(a,c)}}Rd={{(b,d)},{(c,d)},{(b,d),(c,d)},{(b,d),(e,d)},{(c,d),(e,d)},{(b,d),(c,d),(e,d)}}Re={{(d,e),(e,e)}}

Here, we can see that b, c and e only have one partial attack relation while a has 3 and the argument d has 6 corresponding partial attack relations. That means, overall we will have 3∗6=18 different argumentation frameworks. These frameworks are constructed by taking all possible combinations while taking one partial attack relation from each argument, i.e., we obtain the set of all attack relations RL=Ra×Rb×Rc×Rd×Re. We then take these attack relations Ri∈RL and assemble the corresponding argumentation framework Fi=(Arg,Ri). The set F of all argumentation frameworks that are consistent with L then consists of exactly these argumentation frameworks.

All constructed argumentation frameworks are shown in Fig. 4. In the figure, each framework Fi represents two actual argumentation frameworks: Fi which is the depicted framework without the attack (e,d) and Fi′ which does include the optional attack (e,d). All of these argumentation frameworks are consistent with the three input labelings.

Fig. 4.

All 18 constructed argumentation frameworks which are consistent with the labelings ℓ1, ℓ2 and ℓ3. Each framework Fi represents two actual argumentation frameworks: Fi does not have the attack (e,d) and Fi′ includes the optional attack (e,d).

4.Experiments

In this section we will conduct an experimental feasibility study of the approach introduced in Section 3. For that, we will consider both a naive implementation of the algorithm, as well as an optimized implementation with parallelized learning and construction steps. For the evaluation we will measure the performance of the algorithm, i.e., the time the algorithm takes to learn the input labelings and the time for constructing an argumentation framework that satisfies the learned constraints.

We will look at two different scenarios for our experiments. In the first scenario, we will use argumentation frameworks generated with the AFBenchGen2 generators [10] in order to measure how the algorithm’s performance scales with the number of arguments. In the second scenario, we will use the benchmark argumentation frameworks from the ICCMA’19 competition [6] to measure the performance of the algorithm in a more realistic application scenario.

In the following, we briefly describe the system, both implementations and the two main metrics used for the evaluation.

System setup. The experiments were run on a machine with the Ubuntu 20.04 operating system. The machine has a 3.4 GHz Intel Xeon E5-2643v3 CPU with 12 cores and 24 threads and a total of 192 GB DDR4 memory.

Implementation. The implementation11 has been done in Java as part of the TweetyProject library [26]. For the computation of the models of the attack constraints, needed for the construction of argumentation frameworks in the final step of the algorithm, the Java-based SAT-solver Sat4j22 is used. In the naive version, all computations are done sequentially. On the other hand, in the optimized implementation, the learning of a labeling is done in parallel, i.e., the computation of the attack constraints for each argument. In addition to that, the computation of models of the constraints in the construction step is also done in parallel.

Metrics. In the following we define some questions that we want to answer with the experiments. Each question has a corresponding metric that will be investigated in order to answer it:

4.1.Experiment 1: AFBenchGen2

The main goal of our first experiment is to investigate how our algorithm scales with the number of arguments. In particular, we are interested in how the parallelization affects the performance.

For this experiment, we generated a total of 1200 argumentation frameworks F=(Arg,R) with n=|Arg|=20,40,…,200 arguments with the three AFBenchGen2 generators [10]. So, for each n we have 120 argumentation frameworks, one third generated by each of the generators: WattsStrogatz, ErdösRenyi and BarabasiAlbert. For each argumentation framework we compute all inputs (ℓ,σ) with σ∈{ad,co,st}. Then, we iteratively learn up to 1000 of these input labelings and measure the time the algorithm takes to learn them and to construct a consistent argumentation framework.

4.1.1.Results

Fig. 5.

Learning time per labeling and construction time in relation to the number of arguments for the AFs generated via AFBenchGen2.

Let us first consider the median learning time per labeling tTPL. For the naive implementation, the median time per labeling scales from 2 ms for the instances with 20 arguments up to 361 ms for the instances with 200 arguments. While the number of arguments has increased tenfold, the time per labeling has increased by a factor of 172. Fig. 5(a) shows the learning time per labeling in relation to the number of arguments. Note the logarithmic scale of the vertical axis. We can quite clearly see that the time per labeling scales polynomially with the number of arguments for the naive implementation. This is also supported by the fact that the complexity of computing the labeling constraint is in O(n2), as we have to compute n attack constraints, one for each argument a, and for each computation we have to consider all n arguments once to determine their relation to a.

On the other hand, in the optimized implementation the median time per labeling ranges from 477 μs at 20 arguments to only 35 ms at 200 arguments, which is an increase by a factor of 73. That also means, for the smaller instances the parallelization reduces the computing time by approx. 77% and for the largest instances with 200 arguments by over 90%.

For the instances with 120 or more arguments we can observe outliers with significantly lower learning times per labeling. In these cases the argumentation frameworks had only very few labelings and thus less than the intended 1000 labelings were learned. This suggest that there is a positive correlation between the number of learned labelings and the time per labeling tTPL.

Fig. 6.

The total learning time tlearn per instance in relation to the number of arguments |Arg| of the optimized version for larger AFs generated via AFBenchGen2.

To ensure the observed scaling of the algorithm is accurate and not due to hardware, we consider larger and thus harder instances with up to 2000 arguments, generated in a similar fashion. The results for the total learning time tlearn for the optimized version of the algorithm are shown in Fig. 6. While the instances with 200 arguments have a total learning time of 13.4 s on average, the largest instances with 2000 arguments have an average total learning time of 1524 s. As before, we can observe a polynomial scaling of the learning time with the number of arguments, even for the harder instances.

We now look at the time it takes to construct an argumentation framework that is consistent with the attack constraints of the learned labelings. This includes computing a model for the attack constraint of each argument as well as converting these models to an attack relation. The time tconstr it takes to do this has been measured, depending on the number of arguments, and the results are shown in Fig. 5(b). For the naive implementation, the time for constructing ranges from a median of 62 ms for n=20 to 9.7 s for the instances with 200 arguments. Similar to the time per labeling tTPL, the construction time tconstr scales polynomially with the number of arguments as already discussed in Section 3.3. The optimized implementation scales a lot better with the number of arguments. The smaller instances with 20 arguments only require about 23 ms on average while the instances with 200 arguments take up to an average of 250 ms for the construction step. This is a near linear increase (factor of 11) of construction time from 20 to 200 arguments, while the naive implementation increased by a factor of 158 over the same span. Furthermore, at 200 arguments the optimized version reduces the computing time by over 97%.

Regarding the difference between original and learned argumentation framework we can observe the following. On average, less than 2% of the possible attacks were different for the instances in this experiment with a standard deviation of 0.01. The biggest difference was only 5.67%. In general, we can observe that the learned argumentation frameworks contained about 55% less attacks than the original one. This is to be expected, since in our scenario we are interested in the argumentation frameworks that produce at least the input labelings. That means, we explicitly allow other labelings to exist in the learned framework. This allows for a less restrictive attack relation, leading to fewer attacks being necessary to represent the labelings.

Overall, we can say that the paralellization is very effective in reducing the computation time for both processing a labeling as well as constructing a consistent argumentation framework in this artificial scenario. It is however more effective in the construction step than in the learning step.

4.2.Experiment 2: ICCMA’19

In the second experiment we will learn argumentation frameworks on the basis of some more realistic data in order to get an idea of the general performance of our algorithm. For that, we will use the argumentation frameworks from the ICCMA’19 competition [6]. In this experiment we consider only admissible, complete and stable labelings. It would not be feasible to construct all argumentation frameworks since there may be millions of frameworks that may be consistent with the input labelings, thus we only construct one argumentation framework that satisfies the attack constraints.

From the benchmark set, we consider all argumentation frameworks that have less than 1,000 arguments. Thus, we have 276 argumentation frameworks with the number of arguments ranging from 4 to 1,000. For each argumentation framework, we compute the inputs (ℓ,σ) with σ∈{ad,co,st} and randomly learn from up to 1000 input labelings. After learning, we construct one argumentation framework F∈F that satisfies all learned attack constraints, i.e., we simply take the first model computed by the SAT solver.

4.2.1.Results

In the following, the results of the first experiment are summarized and we look at each of the above defined questions and metrics.

Fig. 7.

Learning time per labeling and construction time in relation to the number of arguments in the experiment with the ICCMA’19 instances.

We consider again the time per labeling tTPL=tlearn|L|. Fig. 7(a) shows the time per labeling in relation to the number of arguments of the corresponding ICCMA instance.

For the naive version, the time per labeling ranges from 10 μs to 10.6 s with a median of 42.25 ms per labeling. On the other hand the time per labeling ranges from 28 μs to 733 ms with a median of 3.82 ms per labeling for the optimized implementation.

On average, the optimization brings a decrease in computation time by a factor of about 10. The higher the number of arguments the higher the performance improvement. For the smallest instances with less than 10 arguments the naive implementation actually performs better. This is likely due to some computational overhead of the parallelization, but already for instances with 10 or more arguments the optimized implementation consistently and significantly outperforms the naive version.

One observation we can make for both implementations is that there are some instances for which the time per labeling is significantly lower compared to other instances of similar size. Like in the previous experiment, these are instances where less than the intended 1000 labelings have been processed (simply due to the fact that there where not enough labelings for those instances). This is likely due to the fact, that with a growing number of input labelings the attack constraints get more complex and thus it takes longer to check satisfiability.

We now consider the construction times tconstr for the ICCMA’19 dataset which are shown in Fig. 7(b). The time for constructing a consistent argumentation framework ranges from 94.37 ms to 5527 s with a median of 6 s for the naive implementation. For the optimized version the times range from 51.75 ms to 16.6 s with a median of 996.8 ms. As we have already observed in the previous experiment the effect of the parallelization is even greater for the construction step where the optimized implementation is on average about 22 times faster than the naive version. Even for the smallest instances the optimized implementation is between 1.5 and 2 times faster while for the worst instances it reduces the construction time by a factor of over 200. It should be noted that we can again see the instances with less labelings learned, also being faster than comparable instances in the construction step. However, this seems to only effect the naive algorithm and the optimized algorithm has a lot less variance in its construction times.

Fig. 8.

The frequency distribution of the normalized number of different attacks datt for the ICCMA’19 instances.

Finally, Fig. 8 shows the distribution of the normalized number of different attacks datt for the ICCMA’19 instances. On average We can see that for the majority of instances the constructed argumentation framework is quite close to the original framework. This suggests that after learning 1000 labelings for these instances, there is not much uncertainty left and only a few argumentation frameworks are consistent with these labelings. However, only very few instances yield the exact same argumentation framework. If we would want to reconstruct the exact argumentation framework, we would either need additional labelings or some other information, e.g., negative examples. Interestingly, there are also a number of instances with a proportion datt of over 90%. They all have in common that the attack relation is very dense, i.e., over 90% of all possible attacks are present in the original argumentation framework. That also means these frameworks have only few labelings. Learning these labelings then means we only need very few attacks to ensure consistency with them, since we do not require there to be no further labelings for the constructed argumentation framework. In general, we can observe that the constructed argumentation frameworks contain on average 70% less attacks than the original framework. This is again related to the fact that we allow further labelings to exist in the learned argumentation frameworks.

Overall, this experiment on the ICCMA’19 dataset has confirmed the observation from the first experiment. Our findings suggest a time complexity within O(n2|L|) for learning argumentation frameworks from labelings. The parallelization of both the learning and construction step is very effective and significantly improves performance, especially for larger argumentation frameworks.

5.Discussion

In the previous sections we have introduced and discussed an algorithm for learning a set of argumentation frameworks from a given set of labelings. This algorithm computes a set of attack constraints for each labeling. These constraints represent the acceptability of each argument with regards to the labeling. Afterwards they are combined into a single attack constraint per argument. This set of attack constraints then represents all input labelings and can then be used to construct the argumentation frameworks that are consistent with the input labelings.

In this section we will take a closer look at our algorithm and discuss its strengths and weaknesses. Furthermore, we will discuss some existing algorithms from Riveret et al. [25] and Niskanen et al. [23] and the recent work of Mumford et al. [22] on the computational complexity of the AF learning problem.

We will first discuss some key advantages that distinguish our algorithm proposed in this work from the existing algorithms. One key point is the structure of the algorithms. Our algorithm works in an iterative way and can be applied on a stream of input labelings similarly to the algorithm of Riveret et al. [25]. This is an important difference to the algorithm of Niskanen et al. [23] which only works with a set of input extensions. An iterative approach means we are able to get intermediate results after each processed input labeling. It also means that we are able to refine our result at any point by learning more labelings. This would not be possible in the algorithm of Niskanen et al. [23] where we would have to start over and learn all labelings again. The iterative approach also allows us to choose the order in which the labelings are processed. This means we can add an additional layer to the algorithm by deciding which labeling to learn next based on the current status (i.e., the last intermediate result).

Another important difference is related to the conditions that are used to encode the labelings. The algorithm of Niskanen et al. [23] also uses conditions based on the input, however there is an important difference: these conditions model one extension as a whole. So, using the terminology introduced in Section 3, these conditions are formulae over the set attackAtoms(Arg), i.e., the set of atoms representing all possible attacks over Arg. On the other hand, in our algorithm we have one condition per argument which are formulae over the set of atoms inAttacks(a), i.e., all attacks onto the argument. In other words, the algorithm of Niskanen et al. [23] uses global conditions while our algorithm uses local conditions from the perspective of arguments. These local conditions are important because they enable us to define the iterative approach mentioned above, since we can easily combine formulae for the same argument. This is considerably harder in the algorithm of Niskanen et al. [23]. The fact that the conditions are local and from the perspective of the individual arguments also makes them easier to understand and modify. Furthermore, as we have seen in Section 4, the local conditions also lead to a significantly better performance both while learning a labeling as well as during the construction of an argumentation framework that satisfies the constraints.

The most important advantage of our algorithm compared to those of Riveret et al. and Niskanen et al. is the following: Our algorithm maintains a representation of all argumentation frameworks that are consistent with the input labelings while both other algorithms simply return one fitting argumentation framework. The algorithm of Riveret et al. [25] only maintains one representation of a weighted argumentation framework internally and returns this at the end. On the other hand, the algorithm of Niskanen et al. [23] computes one condition per labeling and as a result returns just one model that represent an argumentation framework. Our algorithm preserves all of the information that is given to it via the input labelings. This is done by translating the input labelings into a set of attack constraints and then combining and simplifying them. So, internally the algorithm only stores one set of mutually independent attack constraints that represent the set of argumentation frameworks. This approach enables us to incorporate additional input labelings at any point and refine the set of argumentation frameworks further. It also ensures that we do not discard any correct argumentation framework during the learning process, something that can happen in both the algorithms of Riveret et al. [25] and Niskanen et al. [23]. It should be mentioned however, that the algorithm of Niskanen et al. [23] can be modified to also return all consistent argumentation frameworks.

We will now look at some other minor differences between all three algorithms. The input of our algorithm is a set of arguments and a set of input labelings. That means, we assume that all arguments of the hidden framework are known. The same assumption is also made by both other algorithms. The second part of the input is the set of input labelings. In the iterative version this can also be a stream of input labelings, similarly to the algorithm of Riveret et al. [25]. This is a different approach compared to the algorithm of Niskanen et al. [23], which uses positive and negative examples in the form of extensions.

Furthermore, all approaches differ in the semantics that are accepted for the input. The algorithm of Riveret et al. [25] only allows grounded labelings as input, while the algorithm of Niskanen et al. [23] accepts conflict-free, admissible, complete, stable, grounded and preferred extensions. Our algorithm accepts conflict-free, admissible, complete and stable labelings. While the algorithm covers many semantics, it does not support grounded and preferred semantics. The reason for that is related to the definition of these semantics. The grounded labeling is defined as the minimal complete labeling and the preferred labelings are maximally complete. These constraints cannot be encoded in the attack constraints and thus it is not possible to learn these labelings with our algorithm, as already discussed in Section 3.2.5. The same applies to some other semantics proposed in the literature, such as semi-stable [7] which maximizes the attacked arguments of an extension. Similarly, the naive semantics and the semantics based on it, like CF2 [5], work with maximal conflict-free sets and thus cannot be modeled by the algorithm in its current form. However, it might be possible to address these issues by extending the algorithm with some form of global conditions. One possibility would be to use conditions similar to those used by Niskanen et al. [23] for modeling the grounded and preferred extensions and adjust them for the respective labelings. It should be mentioned, that this would of course weaken the advantages of our local constraints.

The algorithm of Riveret et al. [25] uses grounded sub-framework labelings as input. This considerably eases the task of learning from labelings since we can just consider all sub-frameworks with just two arguments and take the grounded labeling of these as input. Our algorithm does not rely on such labelings and is able to reconstruct argumentation frameworks from standard labelings.

Argumentation frameworks may contain self-attacking arguments. The algorithm of Riveret et al. [25] does have problems with such argumentation frameworks and there are cases where this algorithm is not able to reconstruct the hidden argumentation framework if there are self-attacking arguments. Our algorithm does not have any problems in that case and is able to work with self-attacking arguments.

Finally, we will also discuss some weaknesses of our algorithm compared to the existing work. The fact that our algorithm requires labelings instead of extensions as input can be considered a weakness. Labelings are more specific than extensions and hold more information about the argumentation framework that produced them. They make a distinction between directly rejected (out) and indirectly rejected (undecided) arguments. Without this distinction it would not be possible to compute the attack constraints in their current form. This is something that can potentially be worked on in the future.

Another observation regarding the input of the algorithm can be made. Our algorithm cannot handle input noise, i.e., some ‘wrong’ labelings that are not actually produced by the hidden argumentation framework. This is something that the algorithms of Riveret et al. [25] and Niskanen et al. [23] are able to handle. The algorithm of Riveret et al. [25] does this by using an internal weighted argumentation framework. This leaves more room to handle inconsistent input but might also lead to returning an argumentation framework which is not consistent with all of the correct input labelings. The algorithm of Niskanen et al. [23] uses weighted MaxSAT encodings for the input extensions. This allows them so find the argumentation framework which is consistent with the highest number of input extensions even if there are some noisy inputs. It might be possible to apply a similar concept to our attack constraints which is also something that can be tackled in the future. Alternatively, we could consider some paraconsistent logic [24] to interpret the attack constraints instead of the classical propositional logic.

The recent work of Mumford et al. [22] investigates the computational complexity of learning argumentation framework both from labelings and extensions. They focus on the complete semantics, but also consider grounded, preferred and stable semantics. Their results show that learning argumentation frameworks from extensions is NP-complete while learning from labelings is solvable in polynomial time. More specifically, they present an algorithm for constructing one consistent argumentation framework from labelings with a time complexity in O(n2|L|). This nicely complements our experimental findings, which suggest the same time complexity dimension for our algorithm. However, our algorithm can be parallelized, which significantly improves its performance. In addition to that, our approach is also capable of producing all consistent solutions instead of just one. This has one disadvantage however, as the algorithm by Mumford et al. has a space complexity within O(n2), while our algorithm needs more space to maintain a representation of multiple argumentation frameworks. In the worst case, our algorithm has a space complexity in O(n2|L|), which easily follows from the fact that we have one attack constraint Ca with at most n atoms for each of the n arguments and labelings. However, in practice we will often need less space than that since the attack constraints may be simplified due to overlap or contradictions in the learned labelings.

A final related work worthwhile to mention is [2], where an approach is presented that incrementally computes extensions when changes on the initial argumentation framework are observed, such as adding an attack. The problem faced in this work is somewhat orthogonal to ours, since we consider the argumentation framework to be unknown but fixed, and we process extensions (or more precisely labelings) incrementally.

6.Conclusion

We investigated the AF learning scenario, where we want to reconstruct argumentation frameworks from given labelings. The goal in this scenario is to find all argumentation frameworks that are consistent with at least all input labelings. To address this problem, we introduced a novel algorithm that iteratively processes labelings and translated them to attack constraints for each argument. These attack constraints are mutually independent and together they represent the set of all consistent argumentation frameworks. The independence of these constraints allows us to parallelize both the learning and construction part of the algorithm. Our experiments showed that this leads to a significant increase in performance. In particular, for the ICCMA’19 dataset the learning time has been improved by a factor of 10 while the construction time showed an even greater improvement with it being over 22 times faster. We also highlighted some of the key advantages of our approach compared to other similar existing approaches. These advantages are, among others, the ability to fully parallelize all computations and the fact that the attack constraints maintain a representation of all consistent argumentation frameworks at all times.

For future work, there are several possibilities. One such possibility is extending our algorithm to other AF-based formalisms, such as bipolar argumentation frameworks [9] or attack-support argumentation frameworks [11]. For these frameworks, there also exist acceptability semantics from whose labelings we can learn the respective frameworks. In particular, instances of these formalisms can be transformed into semantically equivalent meta argumentation frameworks [3]. That means, one only needs to deal with the meta arguments that are created by this transformation.

Another direction is to extend the capabilities of our algorithm. This could be done by defining semantic constraint functions for other semantics, e.g., for the strong admissible semantics [4]. We are however not limited to specific semantics. Alternatively, we can define semantic constraint functions for other concepts from the literature such as credulous or skeptical acceptance with respect to some semantics σ or properties like unattackedness. Another possibility would be to adapt the algorithm to be able to process negative examples, like the algorithm of Niskanen et al. [23]. It would also be interesting to convert the algorithm to a extension-based approach, if possible. One weakness of our approach is the inability to deal with noisy input. As already mentioned in Section 5, this could for example be addressed by using some paraconsistent logic [24].

Furthermore, it would also be interesting to consider a scenario where we can only obtain incomplete information in the form of a partial labeling wrt. some semantics where some of the arguments have no specified label. For a scenario like that, we would have to explore under which circumstances it is possible to recover information about the framework from the partial labeling and adapt the semantic constraint functions accordingly.

Another interesting thing to explore would be the relationship of the number of learned labelings and the difference between attacks in the hidden and the constructed argumentation framework. Meaning, we look at how many labelings we would need to learn in order to obtain construct exactly the hidden argumentation framework or some framework with at most k different attacks.

Finally, another interesting direction would be to make the scenario of learning argumentation frameworks from labelings more interactive, similar to the scenario of eliciting argumentation frameworks [19]. In that scenario the goal is to elicit a hidden argumentation framework from an entity by asking questions about the extensions of this framework. In our scenario, we could also include user input to control which labeling to learn next. This can then be used to steer the learning process to learn more “effectively”, i.e., by choosing labelings that shrink the set of consistent argumentation frameworks the most.