Incremental Computation of Grounded Semantics for Dynamic Abstract Argumentation Frameworks

Abstract

Abstract argumentation has emerged as a central field in Artificial Intelligence. Although the underlying idea is very simple and intuitive, most of the semantics proposed so far suffer from a high computational complexity. For this reason, in recent years, an increasing amount of work has been done to define efficient algorithms. However, so far, the research has concentrated on the definition of algorithms for static frameworks, whereas argumentation frameworks (AFs) are highly dynamic in practice. Surprisingly, the definition of evaluation algorithms taking into account such dynamic aspects has been mostly neglected. In this paper, we address the problem of efficiently recomputing the extensions of AFs which are updated by adding/deleting arguments or attacks. In particular, after identifying some properties that hold for updates of AFs under several well-known semantics, we focus on the most popular unique-status semantics (namely, the grounded semantics) and present an algorithm for its incremental computation, well-suited to dynamic applications where updates to an initial AF are frequently performed to take into account new available knowledge.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Abstract argumentation has emerged as a central field in Artificial Intelligence [3, 10, 26, 42, 44, 45]. Although the underlying idea is very simple and intuitive, most of the semantics proposed so far suffer from a high computational complexity [22,23,24,25, 28,29,30,31,32]. Complexity bounds and evaluation algorithms for argumentation frameworks (AFs) have been deeply studied in the literature, but this research focused on ‘static’ frameworks, whereas, in practice, AFs are not static systems [4, 5, 19, 27, 39]. Typically an AF represents a temporary situation as new arguments and attacks continuously can be added/removed to take into account new available knowledge. This may change significantly the conclusions that can be derived. For instance, when a new attack is added to an AF, existing attacks may cease to apply and new attacks become applicable.

Surprisingly, the definition of evaluation algorithms and the analysis of the computational complexity taking into account such dynamic aspects have been mostly neglected, whereas in these situations incremental computation techniques can greatly improve performance. Sometimes changes to the AF can make small changes to the set of conclusions, and recomputing the whole semantics from scratch can be avoided. For instance, consider the situation shown in Fig. 1: the initial AF ${\mathcal {A}}_0$, where h is not attacked by any other argument, is updated to AF ${\mathcal {A}}$ by adding attack (g, h). According to the most popular argumentation semantics, i.e. grounded, complete, ideal, preferred, stable, and semi-stable [15, 20, 21], the initial AF ${\mathcal {A}}_0$ admits the extension $E_0=\{a,h,g,e,l,m,o\}$, whereas the extension for the updated framework ${\mathcal {A}}$ becomes $E=\{a,c,g,e,l,m,o\}$. As it will be shown later, for the grounded semantics the extension E can be efficiently computed incrementally by looking only at a small part of the AF, which is “influenced by” the update operation. This part is just $\{h,c\}$ in our example, and we will show that the membership of the other arguments to E does not depend on the update operation, and thus we do not need to compute them again after performing update $+(g,h)$.

Fig. 1.

AFs ${\mathcal {A}}_0$ and ${\mathcal {A}}=+(g,h)({\mathcal {A}}_0)$

Contributions. The main contributions are as follows:

• We introduce the concept of influenced set consisting of the arguments whose status could change after an update. The influenced set refines the previously proposed set of affected arguments [4, 39] and makes the computation more efficient.

• We present an incremental algorithm for recomputing the grounded extension. It is very efficient as it (iteratively) computes the status of influenced arguments only and when it finds that the status of arguments derived at some step cannot be changed by subsequent steps then it stops.

• We present experimental results showing the effectiveness of our approach.

Plan of the paper. We start by discussing related works in Sect. 2, and reviewing Dung’s abstract argumentation framework in Sect. 3, where updates are introduced. Next, we identify some sufficient conditions on the updates that guarantee that the semantics of an AF does not change, and introduce the concept of influenced set in Sect. 4. Then we provide our algorithm for incrementally computing the grounded semantics in Sect. 5. In Sect. 6 we present experimental results on two datasets showing that our incremental approach outperforms the computation from scratch of the grounded semantics. Finally, we draw conclusions and discuss future work in Sect. 7, where we also discuss how the results presented in the paper carry over to the case of sets of updates to be performed simultaneously.

2 Related Work

There have been several efforts coping with dynamics aspects of abstract argumentation. In [12, 13] the principles according to which the extension does not change when the set of arguments/attacks are changed have been studied. However, this work does not consider how the extensions of an AF evolve when new arguments are added or some of the old ones are removed. [17, 18] addressed the problem of revising the set of extensions of an AF, and studied how the extensions can evolve when a new argument is considered. However, they focus on adding only one argument interacting with one initial argument (i.e. an argument which is not attacked by any other argument). The work in [17, 18] has been extended in [11], where the evolution of the set of extensions after performing a change operation (addition/removal of arguments/interaction) is studied. Dynamic argumentation has been applied to decision-making of an autonomous agent in [1], where it is studied how the acceptability of arguments evolves when a new argument is added to the decision system. However, they do not compute the whole extensions and also focused on the case where only one argument is added to the system.

The division-based method, proposed in [39] and refined in [4], divides the updated framework into two parts: affected and unaffected, where only the status of affected arguments is recomputed after updates. However, the set of affected arguments consists of those that are reachable from the updated arguments, which is often larger than the set that actually needs to be considered when recomputing the extension. For the AF of Fig. 1, all the arguments in the chains originated by h turn out to be ‘affected’. But we only need to recompute the status of h and c after the update. Recently, [48] introduced a matrix representation of AFs and proposed a matrix reduction that, when applied to dynamic AFs, resembles the division-based method in [39]. In [5, 9] an approach exploiting the concept of splitting of logic programs [40] was adopted to deal with dynamic argumentation. However, the technique considers weak expansions of the initial AF, where added arguments never attack previous ones. Recently, [16] studied the relationship between argumentation and logic programming [14, 35, 36].

[8] investigated whether and how it is possible to modify a given AF in such a way that a desired set of arguments becomes an extension, whereas [43] studied equivalence between two AFs when further information (another AF) is added to both simultaneously. [6] focused on specific expansions where new arguments and attacks may be added but the attacks among the old arguments remain unchanged, while [7] characterized update and deletion equivalence, where adding as well as deleting arguments and attacks is allowed (deletions were not considered in [6, 43]).

To the best of our knowledge, this is the first paper that exploits the initial extension $E_0$ of an AF ${\mathcal {A}}_0$ not only for computing the set ${\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ of arguments influenced by an update u but also for recomputing the status of the arguments in ${\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ by applying early termination conditions. A short version of this paper appeared in [37].

3 Preliminaries

We assume the existence of a set Arg whose elements are called arguments. An (abstract) argumentation framework [20] (AF) is a pair $\langle {A}, \varSigma \rangle$, where ${A}\subseteq Arg$ is a finite set whose elements are referred to as arguments, and $\varSigma \subseteq {A}\times {A}$ is a binary relation over ${A}$ whose elements are referred to as attacks. Essentially, an AF is a directed graph in which the arguments are represented by the nodes and the attack relation is represented by the set of directed edges. An argument is an abstract entity whose role is entirely determined by its relationships with other arguments.

Given arguments $a,b\in {A}$, we say that a attacks b iff $(a,b)\in \varSigma$. An argument a attacks a set $S \subseteq {A}$ iff $\exists \, b\in S$ such that a attacks b.

We use $S^+=\{b\ |\ \exists a\in S : (a,b)\in \varSigma \}$ and $S^-=\{b\ |\ \exists a\in S : (b,a)\in \varSigma \}$ to denote the sets of all arguments that are attacked by S and attack S, respectively.

A set $S\subseteq A$ defends a iff $\forall b\in A$ such that b attacks a, there is $c\in S$ such that c attacks b.

A set $S\subseteq A$ of arguments, is said to be

• (i) conflict-free, if there are no $a, b \in S$ such that a attacks b;

• (ii) admissible, if it is conflict-free and it defends all its arguments.

An argumentation semantics specifies the criteria for identifying a set of arguments considered to be “reasonable” together, called extension. A complete extension (co) is an admissible set that contains all the arguments that it defends. A complete extension S is said to be:

• preferred ( pr ) iff it is maximal (w.r.t. $\subseteq$);

• semi-stable ( ss ) iff $S\cup S^+$ is maximal (w.r.t. $\subseteq$);

• stable ( st ) iff it attacks each argument in $A\setminus S$;

• grounded ( gr ) iff it is minimal (w.r.t. $\subseteq$);

• ideal ( id ) iff it is contained in every preferred extension and it is maximal (w.r.t. $\subseteq$).

Given an AF ${\mathcal {A}}$ and a semantics ${\mathcal {S}}\in \!\!\{$ co, pr, ss, st, gr, id $\}$, we use ${\mathcal {E}}_{\mathcal {S}}({\mathcal {A}})$ to denote the set of ${\mathcal {S}}$-extensions of ${\mathcal {A}}$.

All the above-mentioned semantics except the stable admit at least one extension, and the grounded and ideal admit exactly one extension [15, 20, 21]. That is, for ${\mathcal {S}}\in \!\{$ co, pr, ss, gr, id $\}$ it is the case that ${\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}) \ne \emptyset$, while ${\mathcal {E}}_{\texttt {st}}({\mathcal {A}})$ may be empty. Semantics ${\texttt {gr}}$ and ${\texttt {id}}$ are called unique status semantics as $|{\mathcal {E}}_{\texttt {gr}}({\mathcal {A}})|=|{\mathcal {E}}_{\texttt {id}}({\mathcal {A}})|=1$, whereas the others are called multiple status semantics. It is well-known that, for any AF ${\mathcal {A}}$, ${\mathcal {E}}_{\texttt {gr}}({\mathcal {A}}) \subseteq {\mathcal {E}}_{\texttt {co}}({\mathcal {A}})$ and ${\mathcal {E}}_{\texttt {id}}({\mathcal {A}}) \subseteq {\mathcal {E}}_{\texttt {co}}({\mathcal {A}})$, and ${\mathcal {E}}_{\texttt {st}}({\mathcal {A}}) \subseteq {\mathcal {E}}_{\texttt {ss}}({\mathcal {A}}) \subseteq {\mathcal {E}}_{\texttt {pr}}({\mathcal {A}}) \subseteq {\mathcal {E}}_{\texttt {co}}({\mathcal {A}})$.

Example 1

Consider the AF ${\mathcal {A}}_0$ shown in Fig. 2. Then, the set of admissible sets is $\{\ \emptyset ,\ \{a\},\ \{d\},\ \{a,d\},\ \{b,d\}\ \}$, and ${\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}_0)$ with ${\mathcal {S}}\in \!\{$ co, pr, ss, st, gr, id $\}$ is as reported in the second column of Fig. 3.    $\square$

Fig. 2.

AF ${\mathcal {A}}_0$ Example 1.

Fig. 3.

Sets of extensions for the AF of Example 1, and changes in the sets after performing updates $+(b,d)$ and $-(c,b)$.

The argumentation semantics can be also defined in terms of labelling. A labelling for an AF ${\mathcal {A}}= \langle {A}, \varSigma \rangle$ is a total function $L :{A}\rightarrow \{ {\textsc {in}}, {\textsc {out}}, {\textsc {un}}\}$ assigning to each argument a label. $L(a)={\textsc {in}}$ means that argument a is accepted, $L(a)={\textsc {out}}$ means that a is rejected, while $L(a)={\textsc {un}}$ means that a is undecided.

Let $in(L)=\{a\ |\ a\in {A}\wedge L(a)={\textsc {in}}\}$, $out(L)=\{a\ |\ a\in {A}\wedge L(a)={\textsc {out}}\}$, and $un(L)=\{a\ |\ a\in {A}\wedge L(a)={\textsc {un}}\}$. In the following, we also use the triple $\langle in(L), out(L), un(L)\rangle$ to represent L.

A labelling L is said to be admissible (or legal) if $\forall a \in in(L) \cup out(L)$ (i) if $L(a)={\textsc {out}}$ then $\exists \, b\in {A}$ such that $(b,a)\in \varSigma$ and $L(b)={\textsc {in}}$; and (ii) if $L(a)={\textsc {in}}$ then $L(b)={\textsc {out}}$ for all $b\in {A}$ such that $(b,a)\in \varSigma$. L is a complete labelling iff conditions (i) and (ii) hold for all $a \in {A}$.

Between complete extensions and complete labellings there is a bijective mapping defined as follows: for each extension E there is a unique labelling $L = \langle E, E^+, {A}\setminus (E \cup E^+)\rangle$ and for each labelling L there is a unique extension in(L). We say that L is the labelling corresponding to E.

In the following, we say that the status of an argument a w.r.t. a labelling L (or its corresponding extension in(L)) is ${\textsc {in}}$ (resp., ${\textsc {out}}$, ${\textsc {un}}$) iff $L(a)={\textsc {in}}$ (resp., $L(a)={\textsc {out}}$, $L(a)={\textsc {un}}$). We will avoid to mention explicitly the labelling (or the extension) whenever it is understood.

Updates. An update u for an AF ${\mathcal {A}}_0$ consists in modifying ${\mathcal {A}}_0$ into an AF ${\mathcal {A}}$ by adding or removing arguments or attacks.

In the following, we focus on updates consisting of adding/deleting one attack between arguments belonging to ${\mathcal {A}}_0$. As we discuss in Sect. 7, focusing on single attack updates is not a limitation as multiple (attack) updates to be performed simultaneously can be simulated by means of a single attack update.

Concerning the addition (resp. deletion) of a set of isolated arguments, it is easy to see that if ${\mathcal {A}}$ is obtained from ${\mathcal {A}}_0$ through the addition (resp. deletion) of a set S of isolated arguments, then, let $E_0$ be an extension for ${\mathcal {A}}_0$, $E = E_0 \cup S$ (resp. $E = E_0 \setminus S$) is an extension for ${\mathcal {A}}$ that can be trivially computed. Of course, if arguments in S are not isolated, we can first delete all attacks involving arguments in S; adding an attack between an argument in ${\mathcal {A}}_0$ and a new argument can be simulated as well.

We use $+(a,b)$ (resp. $-(a,b)$) to denote the addition (resp. deletion) of an attack (a, b), and $u({\mathcal {A}}_0)$ to denote the application of update $u=\pm (a,b)$ to ${\mathcal {A}}_0$.

Updating an AF implies that its semantics (sets of extensions or labellings) changes, as shown in the following example.

Example 2

Consider the AF ${\mathcal {A}}_0$ of Example 1. For each semantics ${\mathcal {S}}$, the set ${\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}_1)$ of extensions for ${\mathcal {A}}_1=+(b,d)({\mathcal {A}}_0)$ is reported in the third column of Fig. 3. If update $-(c,b)$ is performed on ${\mathcal {A}}_1$, then ${\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}_2)$ with ${\mathcal {A}}_2=-(c,b)({\mathcal {A}}_1)$ is as shown on the last column of Fig. 3.    $\square$

4 Influenced Arguments

In this section, we first identify conditions ensuring that a given ${\mathcal {S}}$-extension continues to be an ${\mathcal {S}}$-extension after an update, and then introduce the influenced set that will be used to limit the set of arguments that needs to be recomputed after an update. In addition, arguments not in the influenced set can be used to derive extensions for the updated AF.

The following two propositions introduce sufficient conditions guaranteeing that a given ${\mathcal {S}}$-extension is still an ${\mathcal {S}}$-extension after performing an update.

Proposition 1

Let ${\mathcal {A}}_0$ be an AF, $u = +(a,b)$ an update, ${\mathcal {S}}$ a semantics, $E_0 \in {\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}_0)$ an extension of ${\mathcal {A}}_0$ under semantics ${\mathcal {S}}$, and $L_0$ the labelling corresponding to $E_0$. Then $E_0 \in {\mathcal {E}}_{\mathcal {S}}(u({\mathcal {A}}_0))$ if

• ${\mathcal {S}}\in \!\{$ co, st, gr $\}$ and one of the following conditions holds:

  • $L_0(a)\ne {\textsc {in}}$ and $L_0(b)\ne {\textsc {in}}$,

  • $L_0(a)={\textsc {in}}$ and $L_0(b)={\textsc {out}}$;

• ${\mathcal {S}}\in \!\{$ pr, ss, id $\}$ and $L_0(b)={\textsc {out}}$.

Proposition 2

Let ${\mathcal {A}}_0$ be an AF, $u = -(a,b)$, ${\mathcal {S}}\in \!\{{\texttt {co}}, {\texttt {pr}}, {\texttt {ss}}, {\texttt {st}}, {\texttt {gr}}\}$, and $E_0 \in {\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}_0)$ an extension of ${\mathcal {A}}_0$ under ${\mathcal {S}}$. Then $E_0 \in {\mathcal {E}}_{\mathcal {S}}(u({\mathcal {A}}_0))$ if one of the following conditions holds:

• (1) $L_0(a)\!=\!{\textsc {out}}$;

• (2) $L_0(a)\!=\!{\textsc {un}}$ and $L_0(b)\!=\!{\textsc {out}}$.

Example 3

Consider the AFs ${\mathcal {A}}_1\!=\!+(b,d)({\mathcal {A}}_0)$ and ${\mathcal {A}}_2\!=\!-(c,b)({\mathcal {A}}_1)$, where ${\mathcal {A}}_0$ is the AF of Example 2. For ${\mathcal {S}}\in \!\{{\texttt {co}}, {\texttt {pr}}, {\texttt {ss}}, {\texttt {st}}\}$, extension $\{a,d\}$ of ${\mathcal {A}}_1$ is still an extension of ${\mathcal {A}}_2$ as $L_0(c)\!=\!{\textsc {out}}$ (see Fig. 3). The grounded extension $\emptyset$ of ${\mathcal {A}}_1$ is still a grounded extension of ${\mathcal {A}}_2$, whereas the ideal extension $\{a,d\}$ of ${\mathcal {A}}_1$ is not the ideal extension of ${\mathcal {A}}_2$.    $\square$

Given an AF ${\mathcal {A}}= \langle {A}, \varSigma \rangle$ and an argument $b \in {A}$, we denote as ${ Reach}\!\!_{_{\mathcal {A}}}\!(b)$ the set of arguments that are reachable from b in ${\mathcal {A}}$. We now introduce the influenced set.

Definition 1

(Influenced set). Let ${\mathcal {A}}= \langle {A}, \varSigma \rangle$ be an AF, $u = \pm (a,b)$ an update, E an extension of ${\mathcal {A}}$ under a given semantics ${\mathcal {S}}$, and let

• $$\begin{aligned} {\mathcal {I}}_0(u,{\mathcal {A}},E) ={\left\{ \begin{array}{ll} \emptyset \ \ {if}\ E \in {\mathcal {E}}_{\mathcal {S}}(u({\mathcal {A}}))\ \ \hbox {[i.e., the conditions of Prop. 1/2 hold] } or\\ \, \, \, \exists (z,b)\in \varSigma \ s.t.\ z\in E \wedge z\not \in { Reach}\!\!_{_{\mathcal {A}}}\!(b); \\ \\ \{ b \}\ otherwise; \end{array}\right. } \end{aligned}$$

• ${\mathcal {I}}_{i+1}(u,{\mathcal {A}},E) = {\mathcal {I}}_i(u,{\mathcal {A}},E) \cup \{y \ | \ \exists (x,y)\in \varSigma \ s.t.\ x\in {\mathcal {I}}_i(u,{\mathcal {A}},E )\ \wedge \not \exists (z,y)\in \varSigma \ s.t.\ z\in E \wedge z\not \in { Reach}\!\!_{_{\mathcal {A}}}\!(b) \}$.

The influenced set of update u w.r.t. AF ${\mathcal {A}}$ and the extension E is ${\mathcal {I}}(u,{\mathcal {A}},E) = {\mathcal {I}}_{n}(u,{\mathcal {A}},E)$ such that ${\mathcal {I}}_n(u,{\mathcal {A}},E) = {\mathcal {I}}_{n+1}(u,{\mathcal {A}},E)$.    $\square$

Thus, the set of arguments that are influenced by an update of the status of b are those that can be reached from b without using any intermediate argument y whose status is known to be out because it is determined by an argument $z\in E$ which is not reachable from (and thus not influenced by) b.

Example 4

For the AF ${\mathcal {A}}_0=\langle {A}_0, \varSigma _0 \rangle$ of Fig. 1, whose grounded extension is $E_0=\{a,h,g,e,l,m,o\}$, we have that ${ Reach}\!\!_{{_{\mathcal {A}}}_0}\!(h)\! =\! {A}_0 \setminus \{ a,b\}$, and the influenced set of $u = +(g,h)$ is ${\mathcal {I}}(u,{\mathcal {A}}_0,E_0) = \{h,c\}$. Note that $d\not \in {\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ since it is attacked by $a\in E_0$. Thus the arguments that can be reached only using d cannot belong to ${\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ either.

For ${\mathcal {A}}=u({\mathcal {A}}_0)$, whose the grounded extension is $E=\{a,c,g,e,l,m,o\}$, we have that $S = {\mathcal {I}}(u,{\mathcal {A}},E)$ is still $\{h,c\}$. Therefore, only the status of arguments in S could change and their status can be determined by considering a restricted AF containing only arguments in $S \cup S^-$.    $\square$

Proposition 3

Given an AF ${\mathcal {A}}= \langle {A}, \varSigma \rangle$, an update $u = \pm (a,b)$, and an extension E, the complexity of computing the influenced set of u w.r.t. ${\mathcal {A}}$ and E is $O(|\varSigma |)$.

All the arguments not belonging to the influenced set of an update will still belong to an extension of the updated AF.

Theorem 1

Let ${\mathcal {A}}_0$ be an AF, and ${\mathcal {A}}=u({\mathcal {A}}_0)$ be the AF resulting from performing update $u=\pm (a,b)$ on ${\mathcal {A}}_0$. Let $E_0 \in {\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}_0)$ be an extension for ${\mathcal {A}}_0$ under any semantics ${\mathcal {S}}\in \!\!\{{\texttt {co}}, {\texttt {pr}}, {\texttt {ss}}, {\texttt {st}}, {\texttt {gr}}, {\texttt {id}}\}$. Let ${{\overline{\mathcal {I}}}}=Arg\setminus {\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ be the set of the arguments that are not influenced by u in ${\mathcal {A}}_0$ w.r.t. $E_0$. Then, either ${\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}) = \emptyset$ or there is an extension $E \in {\mathcal {E}}_{\mathcal {S}}({\mathcal {A}})$ for ${\mathcal {A}}$ such that $(E\cap {\overline{\mathcal {I}}})=(E_0\cap {\overline{\mathcal {I}}})$.

Observe that the set of extensions may be empty only for the stable semantics. For all of the other semantics, the theorem suggests the following strategy for computing an extension of the updated AF: derive it by first projecting out the set of arguments not influenced by the update and then extend the so-obtained set by using the information provided by it.

We conclude this section by introducing a refinement of Proposition 1 that makes use of the influenced set. This result will be used in the next section to restrict the input AF.

Proposition 4

Let ${\mathcal {A}}_0$ be an AF, $u = +(a,b)$, ${\mathcal {S}}\in \!\{$ co, pr, ss, st, gr $\}$, and $E_0 \in {\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}_0)$ an extension of ${\mathcal {A}}_0$ under ${\mathcal {S}}$. Then $E_0 \in {\mathcal {E}}_{\mathcal {S}}(u({\mathcal {A}}_0))$ if

• one of the conditions of Proposition 1 holds or

• the next three conditions hold:

  • (1) $L_0(a)={\textsc {out}}$,

  • (2) $L_0(b) = {\textsc {in}}$, and

  • (3) either (i) ${\mathcal {S}}\in \{ {\texttt {co}}, {\texttt {st}}, {\texttt {ss}},$ ${\texttt {pr}} \}$ or (ii) $a \not \in {\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ and ${\mathcal {S}}={\texttt {gr}}$.

Example 5

Consider AFs ${\mathcal {A}}_0$ and ${\mathcal {A}}_1=+(b,d)({\mathcal {A}}_0)$ of Examples 1 and 3. For ${\mathcal {S}}\in \!\{$ co, pr, ss, st $\}$, extension $E_0=\{a,d\}$ for ${\mathcal {A}}_0$ is still an extension of the AF ${\mathcal {A}}_1$ as $L_0(b)={\textsc {out}}$ and $L_0(d)={\textsc {in}}$ (see Fig. 3). However, the grounded extension $E'_0=\{d\}$ for ${\mathcal {A}}_0$ is not guarantee to be a grounded extension for ${\mathcal {A}}_1$ as neither Proposition 1 nor conditions 1) and 3.ii) of Proposition 4 hold (b is un and $b \in {\mathcal {I}}(+(b,d),{\mathcal {A}}_0,E'_0)$).    $\square$

5 Recomputing the Grounded Semantics

Given an AF ${\mathcal {A}}_0$, the grounded extension $E_0$ for ${\mathcal {A}}_0$, an update u for ${\mathcal {A}}_0$ yielding ${\mathcal {A}}= u({\mathcal {A}}_0)$, we address the problem of efficiently computing the grounded extension E of the updated AF ${\mathcal {A}}$ starting from $E_0$.

For any AF ${\mathcal {A}}= \langle {A},\varSigma \rangle$ and set $S \subseteq {A}$ of arguments, we denote with $\varPi (S,{\mathcal {A}}) = \langle S, \varSigma \cap S \times S \rangle$ the subgraph of ${\mathcal {A}}$ induced by the nodes in S. Moreover, given two AFs ${\mathcal {A}}_1 = \langle {A}_1,\varSigma _1\rangle$ and ${\mathcal {A}}_2 = \langle {A}_2,\varSigma _2\rangle$, we denote as ${\mathcal {A}}_1 \sqcup {\mathcal {A}}_2 = \langle {A}_1 \cup {A}_1,\varSigma _1 \cup \varSigma _2\rangle$ the union of the two AFs.

Our algorithm first identifies the restricted subgraph of the given AF containing the arguments influenced by the update.

Definition 2

(Restricted AF for grounded semantics). Given an AF ${\mathcal {A}}= \langle {A},\varSigma \rangle$, a grounded extension E for ${\mathcal {A}}$, and an update $u = \pm (a,b)$, the restricted AF of ${\mathcal {A}}$ w.r.t. E and u (denoted as ${\mathcal {R}}\!_{{\texttt {gr}}}(u,{\mathcal {A}},E)$) is as follows.

• ${\mathcal {R}}\!_{{\texttt {gr}}}(u,{\mathcal {A}},E)$ is empty if ${\mathcal {I}}(u,{\mathcal {A}},E)$ is empty or one of the conditions of Proposition 4 holds.

• ${\mathcal {R}}\!_{{\texttt {gr}}}\!(u,{\mathcal {A}},E)=\varPi ({\mathcal {I}}(u,{\mathcal {A}},E),u({\mathcal {A}}))\sqcup T_1 \sqcup T_2$ where:

  • $T_1$ is the union of the AFs $\langle \{a,b\}, \{ (a,b) \}\rangle$ s.t. (a, b) is an attack of $u({\mathcal {A}})$ and $a \not \in {\mathcal {I}}(u,{\mathcal {A}},E)$, $a \in E$, and $b \in {\mathcal {I}}(u,{\mathcal {A}},E)$;

  • $T_2 = \langle \{ c\, |\, Check(c) \}, \{ (c,c)\, |\, Check(c) \} \rangle$, where Check(c) is true if $\exists (e,c) \in \varSigma$ such that $c \in {\mathcal {I}}(u,{\mathcal {A}},E)$ and $e \not \in {\mathcal {I}}(u,{\mathcal {A}},E)$ and $e \not \in E \cup E^+$.     $\square$

Hence, AF ${\mathcal {R}}\!_{{\texttt {gr}}}(u,{\mathcal {A}},E)$ contains, in addition to the subgraph of $u({\mathcal {A}})$ induced by ${\mathcal {I}}(u,{\mathcal {A}},E)$, additional nodes and edges containing needed information on the “external context”, i.e. information about the status of arguments which are attacking some argument in ${\mathcal {I}}(u,{\mathcal {A}},E)$. Specifically, if there is in $u({\mathcal {A}})$ an edge from node $a\not \in {\mathcal {I}}(u,{\mathcal {A}},E)$ whose status is ${\textsc {in}}$ to node $b\in {\mathcal {I}}(u,{\mathcal {A}},E)$, then we add the edge (a, b) so that, as a does not have incoming edges in ${\mathcal {R}}\!_{{\texttt {gr}}}(u,{\mathcal {A}},E)$, its status is confirmed to be ${\textsc {in}}$. Moreover, if there is in $u({\mathcal {A}})$ an edge from a node $e\not \in {\mathcal {I}}(u,{\mathcal {A}},E)$ to a node $c\in {\mathcal {I}}(u,{\mathcal {A}},E)$ such that e is ${\textsc {un}}$, we add edge (c, c) to ${\mathcal {R}}\!_{{\texttt {gr}}}(u,{\mathcal {A}},E)$ so that the status of c cannot be ${\textsc {in}}$. Using fake arguments/attacks to represent external contexts has been exploited in a similar way in [2], where decomposability properties of argumentation semantics are studied.

Example 6

Continuing Example 4, ${\mathcal {R}}\!_{{\texttt {gr}}}(+(g,h),{\mathcal {A}}_0,E_0)$ consists of the subgraph induced by ${\mathcal {I}}(u,{\mathcal {A}}_0,E_0) = \{h,c\}$ as well as the edge (g, h) which is an attack towards argument $h\in {\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ coming from argument g outside ${\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ labelled as ${\textsc {in}}$. Hence, ${\mathcal {R}}\!_{{\texttt {gr}}}(+(g,h),{\mathcal {A}}_0,E_0) = \langle {A}_d, \varSigma _d\rangle$ with ${A}_d=\{g,h,c\}$ and $\varSigma _d=\{(g,h),(h,c)\}$.    $\square$

Example 7

Consider the AF ${\mathcal {A}}_0 = \langle \{a,b,c,d,e,f,g\},$ $\{ (a,b), (b,a), (c,d), (d,c), (a,c),$ $(b,c), (f,c), (g,f) \} \rangle$ and the update $u = +(e,d)$. We have that

• (i) the grounded extension of ${\mathcal {A}}_0$ is $E_0 = \{ g, e \}$ (i.e. arguments a, b, c, d are all labeled as ${\textsc {un}}$);

• (ii) the influenced set is ${\mathcal {I}}(u,{\mathcal {A}}_0, E_0) = \{ c, d \}$; and

• (iii) the restricted AF is ${\mathcal {R}}_{\texttt {gr}}(u,{\mathcal {A}}_0, E_0) = \langle \{c,d\},\{(c,d),$ $(d,c)\}\rangle \sqcup T_1\sqcup T_2$ where $T_1=\langle \{e,d\},$ $\{(e,d)\}\rangle$ and $T_2=\langle \{c\},\{(c,c)\}\rangle$.

That is, ${\mathcal {R}}_{\texttt {gr}}(u,{\mathcal {A}}_0, E_0)\!\!=\!\!\langle \{ c, d, e \},\ \{ (c,d),$ (d, c),  $(e,d), (c,c) \} \rangle$.    $\square$

Algorithm 1 first checks if the restricted AF (computed w.r.t. update $u=\pm (a,b)$) is empty (Line 3). If this is the case, then $E=E_0$. Otherwise, the status of arguments in $S={\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ needs to be recomputed and the extension E of $u({\mathcal {A}}_0)$ is constructed at Line 6 by combining the arguments in $E_0$ not belonging to the influenced part and the arguments returned by Function IFP (incremental fixpoint), which is invoked with AF ${\mathcal {A}}_d=\langle {A}_d,\varSigma _d\rangle$ (the restricted graph of ${\mathcal {A}}$) and starting extension $E_0 \cap {A}_d$ (the restriction of $E_0$ to ${A}_d$).

Function IFP first computes the set of nodes which are labelled ${\textsc {in}}$ and an initial set of nodes which are labelled ${\textsc {out}}$. If no argument can be labelled ${\textsc {in}}$, it returns the empty set. Otherwise, it iteratively applies function G that takes as input the set of arguments $S_{\textsc {out}}$ which have been labeled ${\textsc {out}}$ so far and the subset $\varDelta _{\textsc {out}}\subseteq S_{\textsc {out}}$ of arguments which have been labelled out in the last step, and returns the arguments $b \in \varDelta _{\textsc {out}}^+$ such that for every attack $(a,b)\in \varSigma$, argument $a \in S_{\textsc {out}}$ (i.e. a is labelled ${\textsc {out}}$).¹ Function G returns the set $\varDelta _{\textsc {in}}$ of arguments which are labeled ${\textsc {in}}$ at Line 6. Arguments labeled ${\textsc {out}}$ are immediately derived by taking $\varDelta _{\textsc {in}}^+$, that is the arguments which are attacked by some argument which has been labelled as ${\textsc {in}}$ (Line 7). Function G is iteratively applied until, in the last step of the repeat loop, all arguments derived are confirmed to be in the extension $E_0$ of the AF ${\mathcal {A}}_0$ being updated (i.e., $\varDelta _{\textsc {in}}\subseteq E_0$). Finally, if $\varDelta _{\textsc {in}}$ is empty, then it just returns the set of arguments labeled as ${\textsc {in}}$ (in this case, the status of all the arguments in the restricted AF has been recomputed by function G), otherwise it returns $S_{\textsc {in}}$ union the arguments in $E_0$ whose status has not been recomputed by function G.

Example 8

Consider the AF ${\mathcal {A}}_0$ of Fig. 1 where $E_0=\{a,h,g,e,l,m,o\}$ and ${\mathcal {I}}(u,{\mathcal {A}}_0,E_0) = \{h,c\}$. Algorithm 1 computes the grounded extension E of the AF ${\mathcal {A}}=+(g,h)({\mathcal {A}}_0)$ as follows. The restricted AF ${\mathcal {A}}_d$ = $\langle {A}_d, \varSigma _d\rangle = {\mathcal {R}}\!_{{\texttt {gr}}}(u,{\mathcal {A}}_0,E_0)$ is computed (at Line 2) obtaining ${A}_d=\{g,h,c\}$ and $\varSigma _d=\{(g,h),(h,c)\}$. As ${A}_d$ is not empty, Function IFP with actual parameters ${\mathcal {A}}_d$ and $E_0 \cap {A}_d = \{g,h\}$ is called at Line 6. Function IFP first computes $S_{\textsc {in}}=\varDelta _{\textsc {in}}=\{ g \}$ and $S_{\textsc {out}}=\varDelta _{\textsc {out}}=\{ h\}$. Next, at the first iteration of the repeat loop, it is computed $\varDelta _{\textsc {in}}= G(\{ h\},\{ h\})=\{c\}$ (Line 6) and $\varDelta _{\textsc {out}}=\emptyset$ (Line 7) as there is no argument attacked by c in ${\mathcal {A}}_d$. Then the function terminates returning the set $\{ g,c \}$ and E turns out to be the set $\{a,g,e,l,m,o\} \cup \{g,c\}$.    $\square$

Theorem 2

For any AF ${\mathcal {A}}= \langle {A},\varSigma \rangle$, the complexity of computing IFP(${\mathcal {A}}, E_0$), with $E_0\subset {A}$, is $O(|{A}| \times {\bar{d}}\,^2 )$, where ${\bar{d}}$ is the maximum input degree of a node (i.e., the maximum number of attacks towards an argument in ${A}$).

Theorem 3

For any AF ${{{\mathcal {A}}}_0 = \langle {{A}}_0,{\varSigma }_0\rangle }$ with grounded extension $E_0$, and $u=\pm (a,b)$, the complexity of Algorithm Incr-Grounded-Sem(${\mathcal {A}}_0, u, E_0$) is $O(|\varSigma _0| + |{\mathcal {I}}(u,{\mathcal {A}}_0,E_0)| \times {\bar{d}}\,^2 )$, where ${\bar{d}}$ is the maximum input degree of a node.

Theorem 4

Given an AF ${\mathcal {A}}_0$, an update u=$\pm (a,b)$ for ${\mathcal {A}}_0$ yielding ${\mathcal {A}}=u({\mathcal {A}}_0)$, and the grounded extension $E_0$ of ${\mathcal {A}}_0$, Algorithm 1 computes the grounded extension E of ${\mathcal {A}}$.

6 Experimental Results

We implemented a prototype for incremental computation of argumentation semantics using the Java argumentation libraries provided by the Tweety project [47].

Datasets. We used two datasets taken from the International Competition on Computational Models of Argumentation (ICCMA)²:

• (i) REAL consists of 19 AFs $\langle {A}_0, \varSigma _0\rangle$ with $|{A}_0|\in [5K,100K]$ and $|\varSigma _0|\in [7K,143K]$;

• (ii) SYN consists of 24 AFs $\langle {A}_0, \varSigma _0\rangle$ with $|{A}_0|\in [1K,4K]$ and $|\varSigma _0|\in [14K,172K]$.

The AFs in the two datasets have a different structure: on average, $|{{ Reach}}_{{\mathcal {A}}_0}(a)|$ is around 2200 for arguments a in SYN, while it is about 10 for REAL; moreover, the average number of attacks per argument for REAL is 1.5 while it is 26 for SYN.

Algorithms. For each AF ${\mathcal {A}}_0=\langle {A}_0, \varSigma _0\rangle$ in each dataset, we first computed the grounded extension $E_0$. Then, we randomly selected an update u of the form $+(a,b)$ (with $a,b\in {A}_0$ and $(a,b) \not \in \varSigma _0$) or $-(a,b)$ (with $(a,b)\in \varSigma _0$). Next, we executed the following algorithms:

• (i) BaseG which computes the grounded semantics E of the updated AF $u({\mathcal {A}}_0)$ from scratch. It finds the fixpoint of the characteristic function of an AF as implemented in the libraries of Tweety [47]. This algorithm was also used to compute the initial extension $E_0$ which is taken as input by the incremental algorithms;

• (ii) Incr-Grounded-Sem (IncrG for short) which incrementally computes the grounded extension E by implementing Algorithm 1 (note that it also includes the computation of the influenced set and the restricted AF).

All experiments have been carried out on an Intel Core i7-4790 CPU 3.60 GHz with 16 GB RAM running Ubuntu 14.04 64bit. All data points reported on the figures are averages over 20 trials (except those for BaseG which are averages of 5 trials, as it can take hours in some cases due to the huge size of the datasets considered).

Fig. 4.

Run times (ms) of BaseG and IncrG over REAL.

Fig. 5.

Run times (ms) of BaseG and IncrG over SYN.

Results. Figures 4 and 5 report the run times (log scale) of BaseG and IncrG for computing the grounded extensions of the updated AFs versus the number of arguments over REAL and SYN, respectively.³ The experiments also showed that, on average, the size of the influenced set w.r.t. that of the input AF for REAL (resp. SYN) is about $0.01\%$ (resp. $1\%$).

From these results, we can draw the following conclusions:

• The overall time needed by our algorithm for incrementally computing the grounded extension is orders of magnitude better than the time needed to recompute the whole extension from scratch.

• The definition of influenced set substantially restricts the portion of the AF to be analysed for recomputing the semantics of an AF after performing an update. It is worth noting that this means that even using any non-incremental algorithm taking as input the restricted AF would result in a performance improvement, since the size of the input data to be processed would be significantly smaller.

7 Conclutions and Future Work

We presented an incremental approach for computing the grounded extension of updated AFs. Our algorithm exploits the initial extension of an AF for computing the set of arguments influenced by an update, and for detecting early termination conditions during the recomputation of the status of the arguments. The experiments showed that the incremental computation outperforms the base (non-incremental) computation. In fact, the time needed by our algorithm for incrementally computing the grounded extension is orders of magnitude better than the time needed to recompute the whole extension from scratch.

Although in this paper we focused on updates consisting of adding/removing only one attack, our technique can be extended to deal with the case of multiple updates. Indeed, in [38] a construction is provided for reducing the application of a set of updates $\{+(a_1,b_1),\dots ,+(a_n,b_n),$ $-(a_1',b_1'),$ $\dots ,-(a_m',b_m')\}$ on AF ${\mathcal {A}}_0$ to the application of a single attack update $+(v,w)$ on an AF obtained from ${\mathcal {A}}_0$ by adding some new arguments/attacks and replacing some existing ones. Thus, this construction can be used to simulate the simultaneous application of a set of updates by a single attack update of the type considered in this paper.

Moreover, our approach can be extended to work in the case of the incremental computation of the ideal extension of an AF. In fact, the definition of influenced set can be used as it is to compute the part of the AF consisting of the arguments whose status can change after performing an update, and an appropriate definition of restricted AF ${\mathcal {R}}_{id}(u,{\mathcal {A}},E)$ for the ideal semantics can be provided [38]. Once the restricted AF is identified, even a non-incremental algorithm taking as input the restricted AF could be used to recompute the status of influenced arguments.

We plan to continue our work along two directions. First, we will investigate the application of the techniques developed in this paper to other (multiple status) semantics. Indeed, the influenced set is defined already for non-deterministic semantics, and the identification of restricted AFs for these semantics would enable the use of existing (non-incremental) algorithms taking as input a smaller AF for computing extensions. We envisage the definition of incremental algorithms that make use of initial extensions for computing extensions after updates for multiple status semantics where we need to deal with the additional issue that extensions can be split/merged after an update.

Our second direction of research for future work is related to the recent investigations of the integration of argumentation and database repairing techniques [46]. In fact, database reparation is often modelled as interactive reasoning process [41], and the user can profitably exploit argumentation techniques to identify and resolve the conflicts between tuples, possibly specifying preferences among repairs suggested by the system [33, 34]. Given the interactive nature of this process, we believe it would benefit from the use of incremental algorithms for the computation of the arguments justifying repairs, and thus plan to explore this issue in the future.