An experimental analysis on the similarity of argumentation semantics

Abstract

In this paper we ask whether approximation for abstract argumentation is useful in practice, and in particular whether reasoning with grounded semantics – which has polynomial runtime – is already an approximation approach sufficient for several practical purposes. While it is clear from theoretical results that reasoning with grounded semantics is different from, for example, skeptical reasoning with preferred semantics, we investigate how significant this difference is in actual argumentation frameworks. As it turns out, in many graphs models, reasoning with grounded semantics actually approximates reasoning with other semantics almost perfectly. An algorithm for grounded reasoning is thus a conceptually simple approximation algorithm that not only does not need a learning phase – like recent approaches – but also approximates well – in practice – several decision problems associated to other semantics.

1. Introduction

Dung’s theory of abstract argumentation [17] unifies a large variety of formalisms in nonmonotonic reasoning, logic programming and computational argumentation. It is based on the notion of an argumentation framework ( $\mathit{AF}$ ) that consists of a set of arguments and of an attack relation between them. Different argumentation semantics introduce the criteria to determine which arguments emerge as justified from the conflicts, by identifying a number of extensions, i.e. sets of arguments that can survive the conflicts together. In [17] four traditional semantics are introduced, namely grounded, complete, stable, and preferred semantics. Other literature proposals include semi-stable [5,36] and ideal semantics [18]. For an introduction on the various semantics, see [2]. Several problems are associated to each semantics, notably credulous and skeptical acceptance of an argument with respect to a given argumentation framework – i.e. determining whether an argument belongs to at least one (resp. every) extension – and enumeration of all or some extensions given an argumentation framework. Among those semantics, grounded semantics prescribes a unique extension which can be computed in polynomial time, thus all the problems related to grounded semantics are easy to solve. Instead, decision problems associated to the other semantics are much more complex, with some at the second level of the polynomial hierarchy (see also Section 2).

To our knowledge, only a few work addressed the problem of approximating the solution of some decision or enumeration problems associated to an argumentation semantics, despite its paramount importance for existing argumentation-based decision support systems. For instance, CISpaces [32] is an argumentation-based research-grade prototype for supporting intelligence analysts in their sense-making process, under consideration for transitioning into a commercial product by the U.S. Army Research Laboratory. It makes extensive use of preferred extensions – seen as coherent views of the pieces of information collected by the analyst – hence being in the position to exploit fast, reliable, approximators would clearly be an important feature to improve the user experience.

In [35] predictive models have been positively exploited in abstract argumentation for predicting significant aspects, such as the number, of the solution to the preferred extensions enumeration problem, where the complete knowledge of such structure would require a computationally hard problem to be solved. In [26], an approximation algorithm for credulous reasoning with preferred/complete semantics is presented. That algorithm is based on learning a graph convolutional neural network [25] from a set of correctly solved benchmark instances and then using the learned network as an approximation algorithm. The advantage is that runtime drastically decreases (basically to linear runtime, given the learned network) while classification accuracy is still at a reasonable 80% or more in certain cases, i.e. 80% of all arguments of a certain input argumentation framework were correctly classified as credulously accepted or not. The work [26] thus showed that it is generally feasible to employ this methodology for developing approximation algorithms for hard problems in abstract argumentation. Using more recent approaches from the deep learning community and increasing efforts in streamlining this methodology will probably increase classification accuracy further, see [13,28] for approaches in this direction.

It has to be noted that the methodologies used in works such as [13,26,28] are conceptually complex, requiring sophisticated learning algorithms and complex deep learning models, and need additional time for the learning phase. In the present paper, we ask the question whether such a complexity is necessary in practice. More concretely, we ask the question whether reasoning with grounded semantics, which has polynomial runtime, is not already a sufficient approximation approach. While it is clear from theoretical results (Section 2) that reasoning with grounded semantics is different from, for example, skeptical reasoning with preferred semantics, we wish to investigate how significant this difference is in actual argumentation frameworks (Section 3). As it turns out, in many graphs models (Section 4) reasoning with grounded semantics actually approximates reasoning with other semantics almost perfectly (Section 5). An algorithm for grounded reasoning is thus a conceptually simple approximation algorithm that does not need an expensive learning phase but turns out to have high classification accuracy as well. Our results provide even more general insights. We can observe that many semantics coincide with some others on almost all of our benchmarks. For example, credulous reasoning with preferred semantics coincides with credulous reasoning with semi-stable semantics almost perfectly. This allows for reasoning systems tailored for preferred semantics to be used for semi-stable semantics as well in practice, even if the latter problem is computationally more difficult than the former.

2. Background

An argumentation framework [17] consists of a set of arguments1

¹

In this paper we consider only finite sets of arguments: see [3] for a discussion on infinite sets of arguments.

and a binary attack relation between them.

Definition 1.

An argumentation framework ( $\mathit{AF}$ ) is a pair $\mathrm{\Gamma }=⟨{\mathcal{A}}_{}\mathrm{,}{\mathcal{R}}_{}⟩$ where $\mathcal{A}$ is a set of arguments and $\mathcal{R}\subseteq \mathcal{A}\times \mathcal{A}$ . We say that $\mathbf{\text{b}}$ attacks $\mathbf{\text{a}}$ iff $\mathrm{(}\mathbf{\text{b}}\mathrm{,}\mathbf{\text{a}}\mathrm{)}\in \mathcal{R}$ , also denoted as $\mathbf{\text{b}}\to \mathbf{\text{a}}$ . The set of attackers of an argument $\mathbf{\text{a}}$ is denoted as ${\mathbf{\text{a}}}^{-}\triangleq \{\mathbf{\text{b}}:\mathbf{\text{b}}\to \mathbf{\text{a}}\}$ , the set of arguments attacked by $\mathbf{\text{a}}$ is denoted as ${\mathbf{\text{a}}}^{+}\triangleq \{\mathbf{\text{b}}:\mathbf{\text{a}}\to \mathbf{\text{b}}\}$ . An argument $\mathbf{\text{a}}$ without attackers, i.e. such that ${\mathbf{\text{a}}}^{-}=\varnothing$ , is said initial. We also extend attack notations to sets of arguments, i.e. given $\mathit{E}\mathrm{,}\mathit{S}\subseteq \mathcal{A}$ , $\mathit{E}\to \mathbf{\text{a}}$ iff $\exists \mathbf{\text{b}}\in \mathit{E}$ s.t. $\mathbf{\text{b}}\to \mathbf{\text{a}}$ ; $\mathbf{\text{a}}\to \mathit{E}$ iff $\exists \mathbf{\text{b}}\in \mathit{E}$ s.t. $\mathbf{\text{a}}\to \mathbf{\text{b}}$ ; $\mathit{E}\to \mathit{S}$ iff $\exists \mathbf{\text{b}}\in \mathit{E}$ , $\mathbf{\text{a}}\in \mathit{S}$ s.t. $\mathbf{\text{b}}\to \mathbf{\text{a}}$ ; ${\mathit{E}}^{-}\triangleq \{\mathbf{\text{b}}\mid \exists \mathbf{\text{a}}\in \mathit{E}\mathrm{,}\mathbf{\text{b}}\to \mathbf{\text{a}}\}$ and ${\mathit{E}}^{+}\triangleq \{\mathbf{\text{b}}\mid \exists \mathbf{\text{a}}\in \mathit{E}\mathrm{,}\mathbf{\text{a}}\to \mathbf{\text{b}}\}$ .

Each argumentation framework has an associated directed graph where the vertices are the arguments, and the edges are the attacks.

The basic properties of conflict–freeness, acceptability, and admissibility of a set of arguments are fundamental for the definition of argumentation semantics.

Definition 2.

Given an $\mathit{AF}$ $\mathrm{\Gamma }=⟨{\mathcal{A}}_{}\mathrm{,}{\mathcal{R}}_{}⟩$ :

a set $\mathit{S}\subseteq \mathcal{A}$ is a conflict–free set of Γ if $\nexists \mathbf{\text{a}}\mathrm{,}\mathbf{\text{b}}\in \mathit{S}$ s.t. $\mathbf{\text{a}}\to \mathbf{\text{b}}$ ;

an argument $\mathbf{\text{a}}\in \mathcal{A}$ is acceptable in Γ with respect to a set $\mathit{S}\subseteq \mathcal{A}$ if $\forall \mathbf{\text{b}}\in \mathcal{A}$ s.t. $\mathbf{\text{b}}\to \mathbf{\text{a}}$ , $\exists \mathbf{\text{c}}\in \mathit{S}$ s.t. $\mathbf{\text{c}}\to \mathbf{\text{b}}$ ;

the function ${\mathcal{F}}_{\mathrm{\Gamma }}:2^{\mathcal{A}}\to 2^{\mathcal{A}}$ such that ${\mathcal{F}}_{\mathrm{\Gamma }}\mathrm{(}\mathit{S}\mathrm{)}=\{\mathbf{\text{a}}\mid \mathbf{\text{a}}\text{ is }\text{acceptable}\text{ in }\mathrm{\Gamma }\text{ w.r.t. }\mathit{S}\}$ is called the characteristic function of Γ;

a set $\mathit{S}\subseteq \mathcal{A}$ is an admissible set of Γ if S is a conflict–free set of Γ and every element of S is acceptable in Γ with respect to S, i.e. $\mathit{S}\subseteq {\mathcal{F}}_{\mathrm{\Gamma }}\mathrm{(}\mathit{S}\mathrm{)}$ .

An argumentation semantics σ prescribes for any $\mathit{AF}$ Γ a set of extensions, denoted as ${\mathcal{E}}_{\mathit{\sigma }}\mathrm{(}\mathrm{\Gamma }\mathrm{)}$ , namely a set of sets of arguments satisfying the conditions dictated by σ. The paper is focused on grounded (denoted as $\mathsf{GR}$ ), stable ( $\mathsf{ST}$ ), preferred ( $\mathsf{PR}$ ) semantics, introduced in [17]; as well as on semi–stable ( $\mathsf{SST}$ ), originally introduced with the name of admissible argumentation stage extension in [36] and then re-named in [5,6]; and on ideal ( $\mathsf{ID}$ ), originally introduced in [18].2

²

Note that we do not consider complete semantics [17] explicitly, as skeptical reasoning with complete semantics is identical to reasoning with grounded semantics and credulous reasoning with complete semantics is identical to credulous reasoning with preferred semantics, see below.

Definition 3.

Given an $\mathit{AF}$ $\mathrm{\Gamma }=⟨{\mathcal{A}}_{}\mathrm{,}{\mathcal{R}}_{}⟩$ :

a set $\mathit{S}\subseteq \mathcal{A}$ is the grounded extension of Γ i.e. $\{\mathit{S}\}={\mathcal{E}}_{\mathsf{GR}}\mathrm{(}\mathrm{\Gamma }\mathrm{)}$ , iff S is the minimal (w.r.t. set inclusion) fixed point of ${\mathcal{F}}_{\mathrm{\Gamma }}$ ;

a set $\mathit{S}\subseteq \mathcal{A}$ is a stable extension of Γ, i.e. $\mathit{S}\in {\mathcal{E}}_{\mathsf{ST}}\mathrm{(}\mathrm{\Gamma }\mathrm{)}$ , iff S is a conflict-free set of Γ and $\mathit{S}\cup {\mathit{S}}^{+}=\mathcal{A}$ ;

a set $\mathit{S}\subseteq \mathcal{A}$ is a preferred extension of Γ, i.e. $\mathit{S}\in {\mathcal{E}}_{\mathsf{PR}}\mathrm{(}\mathrm{\Gamma }\mathrm{)}$ , iff S is a maximal (w.r.t. set inclusion) admissible set of Γ;

a set $\mathit{S}\subseteq \mathcal{A}$ is a semi–stable extension of Γ, i.e. $\mathit{S}\in {\mathcal{E}}_{\mathsf{SST}}\mathrm{(}\mathrm{\Gamma }\mathrm{)}$ , iff S is a preferred extension where $\mathit{S}\cup {\mathit{S}}^{+}$ is maximal (w.r.t. set inclusion) among all preferred extensions;

a set $\mathit{S}\subseteq \mathcal{A}$ is the ideal extension of Γ, i.e. $\{\mathit{S}\}={\mathcal{E}}_{\mathsf{ID}}\mathrm{(}\mathrm{\Gamma }\mathrm{)}$ , iff S is the maximal (w.r.t. set inclusion) admissible set of Γ that is also subset of each preferred extension.

An argument $\mathbf{\text{a}}$ is credulously (resp. skeptically) accepted with regard to a given semantics σ and a given $\mathit{AF}$ Γ iff $\mathbf{\text{a}}$ belongs to at least one (resp. each) extension of Γ under σ. Let denote with ${\mathit{\sigma }}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}$ (resp. ${\mathit{\sigma }}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}$ ) the set of all the credulously (resp. skeptically) accepted arguments of Γ according to σ, i.e., if $\exists \mathit{S}\in {\mathcal{E}}_{\mathit{\sigma }}\mathrm{(}\mathrm{\Gamma }\mathrm{)}$ , $\mathbf{\text{a}}\in \mathit{S}$ , then $\mathbf{\text{a}}\in {\mathit{\sigma }}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}$ ; and if $\forall \mathit{S}\in {\mathcal{E}}_{\mathit{\sigma }}\mathrm{(}\mathrm{\Gamma }\mathrm{)}$ $\mathbf{\text{a}}\in \mathit{S}$ , then $\mathbf{\text{a}}\in {\mathit{\sigma }}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}$ . Note that in the case no stable extension exists, ${\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}=\mathcal{A}$ .

With a slight abuse of notation, and begging the reader for forgiveness, we will write ${\mathsf{GR}}_{\mathrm{\Gamma }}={\mathsf{GR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}={\mathsf{GR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}$ and ${\mathsf{ID}}_{\mathrm{\Gamma }}={\mathsf{ID}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}={\mathsf{ID}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}$ as both grounded and ideal are unique. Also, when it applies to generic Dung’s argumentation framework, or when it is clear from the context, we will also drop the reference to a given $\mathit{AF}$ , hence for instance we will write ${\mathsf{PR}}_{}\mathsf{\text{-}}\mathsf{C}$ to refer to ${\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}$ where Γ is a generic, unspecified Dung’s argumentation framework, or the specific Dung’s argumentation framework we are discussing in a specific portion of text.

In [4] the notion of skepticism has been formally investigated. As the author themselves discuss in their paper, “skepticism is related with making more or less committed evaluations about the justification state of arguments in a given situation: a more skeptical attitude corresponds to less committed (i.e. more cautious) evaluations.” An extension ${\mathit{E}}_1$ is at least as skeptical as an extension ${\mathit{E}}_2$ if ${\mathit{E}}_1\subseteq {\mathit{E}}_2$ , since then ${\mathit{E}}_1$ supports the acceptance of no more arguments than ${\mathit{E}}_2$ .

Definition 4.

Given two extensions ${\mathit{E}}_1$ and ${\mathit{E}}_2$ of an argumentation framework Γ, ${\mathit{E}}_1$ is at least as skeptical as ${\mathit{E}}_2$ , denoted as ${\mathit{E}}_1⪯{\mathit{E}}_2$ if and only if ${\mathit{E}}_1\subseteq {\mathit{E}}_2$ .

This notion suffices in the case of grounded and ideal semantics as they are unique. In [4] the authors introduced also the following two relations between non-empty sets of extensions3

³

An interested reader is referred to [4] to appreciate the differences with possibly empty sets of extensions.

based to skeptical and credulous acceptance.

Definition 5.

Given two non-empty sets of extensions ${\mathcal{E}}_1$ and ${\mathcal{E}}_2$ of an argumentation framework Γ, ${\mathcal{E}}_1{⪯}_{\cap }{\mathcal{E}}_2$ if and only if ${\bigcap }_{{\mathit{E}}_1\in {\mathcal{E}}_1}{\mathit{E}}_1\subseteq {\bigcap }_{{\mathit{E}}_2\in {\mathcal{E}}_2}{\mathit{E}}_2$ .

Definition 6.

Given two non-empty sets of extensions ${\mathcal{E}}_1$ and ${\mathcal{E}}_2$ of an argumentation framework Γ, ${\mathcal{E}}_1{⪯}_{\cup }{\mathcal{E}}_2$ if and only if ${\bigcup }_{{\mathit{E}}_1\in {\mathcal{E}}_1}{\mathit{E}}_1\subseteq {\bigcup }_{{\mathit{E}}_2\in {\mathcal{E}}_2}{\mathit{E}}_2$ .

Figure 1 summarises the skeptical relationships that exists between different semantics extensions [4] when at least one stable extension exists.4

⁴

As discussed at length in [4], without such an assumption, no conclusion can be drawn regarding the skeptical relationships between stable and other semantics.

In it, for instance, we can see that $\mathsf{GR}{⪯}_{\cap }\mathsf{ID}{⪯}_{\cap }\mathsf{PR}{⪯}_{\cap }\mathsf{ST}\equiv \mathsf{SST}$ .

Fig. 1.

${⪯}_{\cap }$ (left) and ${⪯}_{\cup }$ (right) relation for frameworks where the stable extensions exist.

Table 1

Complexity of traditional decision problem on Dung’s abstract argumentation

σ	$\mathbf{\text{a}}\stackrel{?}{\in }{\mathit{\sigma }}_{}\mathsf{\text{-}}\mathsf{C}$	$\mathbf{\text{a}}\stackrel{?}{\in }{\mathit{\sigma }}_{}\mathsf{\text{-}}\mathsf{S}$
$\mathsf{GR}$	P-complete	P-complete
$\mathsf{ST}$	NP-complete	coNP-complete
$\mathsf{PR}$	NP-complete	${\mathrm{\Pi }}_2^{\mathsf{P}}$ -complete
$\mathsf{SST}$	${\mathrm{\Sigma }}_2^{\mathsf{P}}$ -complete	${\mathrm{\Pi }}_2^{\mathsf{P}}$ -complete
$\mathsf{ID}$	${\mathrm{\Theta }}_2^{\mathsf{P}}$ -complete	${\mathrm{\Theta }}_2^{\mathsf{P}}$ -complete

3. Measuring relative skepticism

If we have a look at the computational complexity of decision problems associated to Dung’s argumentation framework – see [19] for an extensive analysis – we can see (cf. Table 1) that many decision problems cannot be solved in deterministic polynomial time, except for the case of grounded semantics.

Building on top of Fig. 1 – that assumes the existence of at least one stable extension – we can easily derive a ⊆ ordering between sets of credulously and skeptically accepted arguments according to the semantics we consider in this paper.

Proposition 1.

Given an argumentation framework Γ for which ${\mathcal{E}}_{\mathsf{ST}}\mathrm{(}\mathrm{\Gamma }\mathrm{)}\ne \varnothing$ $$\begin{array}{c}{\mathsf{GR}}_{\mathrm{\Gamma }}\subseteq {\mathsf{ID}}_{\mathrm{\Gamma }}\subseteq {\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\subseteq {\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\equiv {\mathsf{SST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\subseteq {\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\equiv {\mathsf{SST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\subseteq {\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\end{array}$$

Figure 2 illustrates the result of Proposition 1. We now need to be able to quantify the distance between such sets, so to have an indication of how much the grounded extension covers the other sets. In another line of work, Doutre and Mailly [16] already investigated a similar problem from an analytical perspective. More specifically, they developed difference measures between semantics that take aspects such as computational complexity, formal properties, and other features into account. However, we want to investigate the difference between the sets of accepted arguments empirically in order to assess the practical relevance of such results. For this reason we rely on the statistic provided by the Jaccard’s index [24] that quantifies the similarities between sets.5

⁵

Jaccard’s distance is but one of many options for measuring the dissimilarities between finite sets [15]; it appears to us that it is a natural one in virtue of its simplicity and its straightforward connection with the notion of skepticism [4]. Moreover, Jaccard’s distance is also the first non-correlation-based distance proposed in literature [12] and it has been proven to be analogous, a special case or connected concepts of much more elaborated ones, such as the Marczewski–Steinhaus distance [29], the Tanimoto distance [31], and the Horadam–Nyblon distance [23].

It is defined as the size of the intersection divided by the size of the union of the sample sets.

Fig. 2.

Hasse diagram of the relationship between sets of credulously and skeptically accepted arguments w.r.t. $\mathsf{GR}$ , $\mathsf{ST}$ , $\mathsf{PR}$ , $\mathsf{SST}$ , and $\mathsf{ID}$ for argumentation frameworks admitting at least one stable extension.

Definition 7 (Jaccard’s Index and Distance, derived from [24]).

Given two sets A and B, their Jaccard’s Similarity Coefficient is: $$\begin{array}{c}\mathit{J}\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}={\displaystyle \frac{|\mathit{A}\cap \mathit{B}|}{|\mathit{A}\cup \mathit{B}|}}\end{array}$$

Their Jaccard’s distance is then: $$\begin{array}{c}{\mathit{J}}_{\mathit{\delta }}\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}=1-\mathit{J}\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\end{array}$$

Therefore, the set of all the sets of credulously and skeptically accepted arguments for an $\mathit{AF}$ form a metric space, independently of the existence of stable extensions.

Proposition 2.

Given an $\mathit{AF}$ Γ, $⟨\{{\mathsf{GR}}_{\mathrm{\Gamma }}\mathrm{,}{\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{SST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{SST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{ID}}_{\mathrm{\Gamma }}\}\mathrm{,}{\mathit{J}}_{\mathit{\delta }}⟩$ is a metric space. Proof.

It follows from results in [ 27 ]. □

From Figs 1 and 2 one can say that grounded is the most skeptical semantics possible (among those considered). We can then define the measure of relative (to $\mathsf{GR}$ ) skepticism of a set of credulously or skeptically accepted arguments according to a semantics as the Jaccard’s distance from the grounded extension.6

⁶

This definition does not require the existence of at least one stable extension: for each $\mathit{AF}$ $\mathrm{\Gamma }=⟨{\mathcal{A}}_{}\mathrm{,}{\mathcal{R}}_{}⟩$ with ${\mathcal{E}}_{\mathsf{ST}}\mathrm{(}\mathrm{\Gamma }\mathrm{)}=\varnothing$ , ${\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}=\varnothing$ and ${\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}=\mathcal{A}$ .

Definition 8 (Measure of relative skepticism).

Given an $\mathit{AF}$ Γ and given ${\tilde{\mathit{\sigma }}}_{\mathrm{\Gamma }}\in \{{\mathsf{GR}}_{\mathrm{\Gamma }}\mathrm{,}{\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{SST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{SST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{ID}}_{\mathrm{\Gamma }}\}$ , its measure of relative (to $\mathsf{GR}$ ) skepticism ${\mathit{\mu }}_{\mathit{S}}$ is defined as: $$\begin{array}{c}{\mathit{\mu }}_{\mathit{S}}\mathrm{(}{\tilde{\mathit{\sigma }}}_{\mathrm{\Gamma }}\mathrm{)}={\mathit{J}}_{\mathit{\delta }}\mathrm{(}{\tilde{\mathit{\sigma }}}_{\mathrm{\Gamma }}\mathrm{,}{\mathsf{GR}}_{\mathrm{\Gamma }}\mathrm{)}\end{array}$$

The following propositions show properties of this measure: proofs are omitted as straightforward. In particular, this measure is a function whose range is the set of real numbers between 0 and 1 (both included).

Proposition 3.

Given an $\mathit{AF}$ Γ and given ${\tilde{\mathit{\sigma }}}_{\mathrm{\Gamma }}\in \{{\mathsf{GR}}_{\mathrm{\Gamma }}\mathrm{,}{\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{SST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{SST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{ID}}_{\mathrm{\Gamma }}\}$ , ${\mathit{\mu }}_{\mathit{S}}\mathrm{(}{\tilde{\mathit{\sigma }}}_{\mathrm{\Gamma }}\mathrm{)}=[0\mathrm{,}1]$ .

Also, the measure of relative skepticism has a global minimum point in correspondence of the grounded semantics.

Proposition 4.

Given an $\mathit{AF}$ Γ, ${\mathit{\mu }}_{\mathit{S}}\mathrm{(}\mathsf{GR}\mathrm{)}⩽{\mathit{\mu }}_{\mathit{S}}\mathrm{(}{\tilde{\mathit{\sigma }}}_{\mathrm{\Gamma }}\mathrm{)}$ , $\forall {\tilde{\mathit{\sigma }}}_{\mathrm{\Gamma }}\in \{{\mathsf{GR}}_{\mathrm{\Gamma }}\mathrm{,}{\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{SST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{SST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{ID}}_{\mathrm{\Gamma }}\}$ .

However, such a global minimum point, in general, is not unique as the grounded extension might coincide with some other set of credulously or skeptically accepted arguments ${\tilde{\mathit{\sigma }}}_{\mathrm{\Gamma }}$ .

Proposition 5.

Given an $\mathit{AF}$ Γ, $\forall {\tilde{\mathit{\sigma }}}_{\mathrm{\Gamma }}\in \{{\mathsf{GR}}_{\mathrm{\Gamma }}\mathrm{,}{\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{SST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{SST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{ID}}_{\mathrm{\Gamma }}\}$ , if ${\mathit{\mu }}_{\mathit{S}}\mathrm{(}{\tilde{\mathit{\sigma }}}_{\mathrm{\Gamma }}\mathrm{)}=0$ then ${\tilde{\mathit{\sigma }}}_{\mathrm{\Gamma }}={\mathsf{GR}}_{\mathrm{\Gamma }}$ .

Finally, it follows that in the case of acyclic free $\mathit{AF}$ s, each set of credulously or skeptically accepted arguments has zero as measure of relative skepticism, consistently with the results provided in [19].

Proposition 6.

Given an acyclic $\mathit{AF}$ Γ, $\forall {\tilde{\mathit{\sigma }}}_{\mathrm{\Gamma }}\in \{{\mathsf{GR}}_{\mathrm{\Gamma }}\mathrm{,}{\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{ST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{PR}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{SST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{SST}}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{ID}}_{\mathrm{\Gamma }}\}$ ${\mathit{\mu }}_{\mathit{S}}\mathrm{(}{\tilde{\mathit{\sigma }}}_{\mathrm{\Gamma }}\mathrm{)}=0$ .

4. Benchmarks

To experimentally analyse the measure of relative skepticism (Definition 8), we considered a significantly large experimental setting with a great variety of benchmarks, so to cover the vast majority of benchmarks currently used in abstract argumentation.7

⁷

An archive of all benchmarks can be downloaded from http://mthimm.de/misc/exparg_instances.tar.gz.

4.1. A million $\mathit{AF}$ s

We exhaustively generated the first million of $\mathit{AF}$ s with increasing size using the EnumeratingDungTheoryGenerator from TweetyProject.8

⁸

http://tweetyproject.org/api/1.17/net/sf/tweety/arg/dung/util/EnumeratingDungTheoryGenerator.html

This generator enumerates all possible combinations of attacks with an increasing number of arguments. In the following, we collectively refer to this group of $\mathit{AF}$ s as $\mathsf{aMillion}$ . Figure 3 illustrates the first six of them. Note that the $\mathit{AF}$ s in this group are rather small (the largest contains only five arguments), but there is no underlying model in the generation process, making this group unbiased on any assumption about the generation process.

Fig. 3.

The first six argumentation frameworks with increment size generated using the Tweety Generator.

4.2. Structured $\mathit{AF}$ s

Fig. 4.

One of the smallest examples of ABA-derived Dung’s $\mathit{AF}$ s in the ICCMA 2017 benchmarks.

We also considered the 426 Assumption-Based argumentation frameworks translated to Dung’s argumentation framework that have been submitted to the ICCMA 2017.9

⁹

http://argumentationcompetition.org/2017/ABA2AF.pdf

This benchmark restricted the ABA benchmark provided in [14]10

¹⁰

Details and the full set of benchmarks can be found at http://robertcraven.org/proarg/experiments.html (on 18 Aug 2020).

to those with at most 1,500 arguments. In the following, we collectively refer to this group of $\mathit{AF}$ s as $\mathsf{sABA}$ . Figure 4 depicts one of the smallest.

Fig. 5.

Example of a Dung’s $\mathit{AF}$ generated from an ASPIC-like theory.

We considered 300 ASPIC-like instances generated using TweetyProject.11

¹¹

http://tweetyproject.org/api/1.17/net/sf/tweety/arg/aspic/util/RandomAspicArgumentationTheoryGenerator.html

In the following, we collectively refer to this group of $\mathit{AF}$ s as $\mathsf{sASPIC}$ . Listing (1) in Appendix A lists an example of ASPIC-like theories used for generating the Dung’s $\mathit{AF}$ depicted in Fig. 5; Appendix A also contains the necessary background on ASPIC [30] and the generation process.

4.3. Random $\mathit{AF}$ s with palatable argumentative characteristics

Fig. 6.

One of the smallest example of Dung’s $\mathit{AF}$ s generated controlling parameters related to strongly connected components.

We randomly generated, using the probo [9] SccGenerator 2,400 $\mathit{AF}$ s with a controllable number structure in terms of strongly connected components. In a first step, a specified number of arguments are partitioned (with a uniform distribution) into components ${\mathit{C}}_1\mathrm{,}\dots \mathrm{,}{\mathit{C}}_{\mathit{n}}$ . Within each component attacks are added randomly with a high probability given as a parameter (and thus likely forming a strongly connected component). In-between components attacks are randomly added with less probability (also given as parameter), but only from a component ${\mathit{C}}_{\mathit{i}}$ to ${\mathit{C}}_{\mathit{j}}$ with $\mathit{i}\mathrm{>}\mathit{j}$ (in order to avoid having few large strongly connected components).12

¹²

Parameters used here: arguments=20,40,…,200, numSccs=#arg/5,#arg/10,#arg/20, innerprob=0.6,0.8, outerprob=0.05,0.1.

In the following, we collectively refer to this group of $\mathit{AF}$ s as $\mathsf{rSCC}$ . Figure 6 depicts one of the smallest.

We also randomly generated 200 $\mathit{AF}$ s featuring a large number of stable extensions – and clearly of preferred extensions as well – using probo’s StableGenerator. This generator first identifies a set of arguments grounded (of size uniformly distributed between a given interval) to form an acyclic subgraph which will contain the grounded extension. Afterwards another subset M (a candidate for a stable extension) of arguments (of size uniformly distributed between a given interval) is randomly selected and attacks are randomly added from some arguments within M to all arguments neither in M nor grounded. This process is repeated until a number of desired stable extensions is reached.13

¹³

Parameters used: arguments=20,40,…,200, minNum=#arg/20, maxNum=#arg/2, minSize=#arg/10, maxSize=#arg/2, minGround=0, maxGround=#arg/10.

In the following, we collectively refer to this group of $\mathit{AF}$ s as $\mathsf{rStable}$ . Figure 7 depicts an example of such $\mathit{AF}$ s.

Fig. 7.

An example of $\mathit{AF}$ s featuring a large number of stable extensions.

4.4. Random graphs as $\mathit{AF}$ s

Finally, we consider random graphs generators proposed in literature as a way to generate random $\mathit{AF}$ s as well.

We generated 599 $\mathit{AF}$ s according to the Erdös-Rényi [20] model – with edges between arguments randomly selected according to a uniform distribution – varying the number of arguments between 20 and 200, with an increment of 20, and with probability of attacks fixed as $\{0.01\mathrm{,}0.05\mathrm{,}0.1\}$ .14

¹⁴

AFBenchGen2 [8] parameters numargs=20,40,…,200, and ER_probAttacks=0.01,0.05,0.1.

In the following, we collectively refer to this group of $\mathit{AF}$ s as $\mathsf{rER}$ . Figure 8 depicts an example of Erdös-Rényi-like $\mathit{AF}$ s.

Fig. 8.

An example of Erdös–Rényi-like $\mathit{AF}$ s.

We also generated 360 $\mathit{AF}$ s according to the Barabasi–Albert [1] model, varying the number of arguments between 20 and 200 with an increment of 20; and enforcing the probability to have at least one argument belonging to a cycle in the range $\{0.1\mathrm{,}0.2\mathrm{,}0.3\}$ .15

¹⁵

AFBenchGen2 [8] parameters numargs=20,40,…,200, and BA_WS_probCycles=0.1,0.2,0.3.

The Barabasi–Albert model enforces the common property of many large networks that the node connectivities follow a scale-free power-law distribution. This is generally the case when: (i) networks expand continuously by the addition of new nodes, and (ii) new nodes attach preferentially to sites that are already well connected. In the following, we collectively refer to this group of $\mathit{AF}$ s as $\mathsf{rBA}$ . Figure 9 depicts an example Barabasi–Albert-like $\mathit{AF}$ s.

Fig. 9.

An example of Barabasi–Albert-like $\mathit{AF}$ s.

Finally, we considered the Watts–Strogatz [37] model, where a ring of n arguments where each argument is connected to its k nearest neighbors in the ring. k must satisfy $\mathit{n}\mathrm{>}\mathit{k}\mathrm{>}log\mathrm{(}\mathit{n}\mathrm{)}\mathrm{>}1$ to ensure a connected graph. Also, each edge is randomly rewired with a probability β. Indeed, Watts and Strogatz [37] show that many biological, technological and social networks are neither completely regular nor completely random, but something in the between. They thus explore simple models of networks that can be tuned through this middle ground: regular networks rewired to introduce increasing amounts of disorder. These systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs, and they are named small-world networks by analogy with the small-world phenomenon. We generated 1,800 $\mathit{AF}$ s according to the Watts–Strogatz model varying the number of arguments between 20 and 200 with an increment of 20; enforcing the probability to have at least one argument belonging to a cycle in the range $\{0.1\mathrm{,}0.2\mathrm{,}0.3\}$ ; setting k equal to half of the number of arguments; and varying β in $\{0.2\mathrm{,}0.4\mathrm{,}0.6\}$ .16

¹⁶

AFBenchGen2 [8] parameters numargs=20,40,…,200, BA_WS_probCycles=0.1,0.2,0.3, WS_baseDegree=(#arg/2), and WS_beta=0.2,0.4,0.6.

In the following, we collectively refer to this group of $\mathit{AF}$ s as $\mathsf{rWS}$ . Figure 10 depicts an example of Watts–Strogatz-like $\mathit{AF}$ s.

Fig. 10.

An example of Watts–Strogatz-like $\mathit{AF}$ s.

5. Empirical analysis

To inform useful considerations, let us introduce the averaged measure of relative skepticism over a set $\mathcal{B}$ of $\mathit{AF}$ s.

Definition 9.

Let $\mathcal{B}$ be a set of $\mathit{AF}$ s, given a semantic $\mathit{\sigma }\in \{\mathsf{GR}\mathrm{,}\mathsf{ST}\mathrm{,}\mathsf{PR}\mathrm{,}\mathsf{SST}\mathrm{,}\mathsf{ID}\}$ , ${\mathit{\mu }}_{\mathit{S}}^{\mathcal{B}}$ is the averaged measure of relative skepticism w.r.t. $\mathcal{B}$ defined as follows: $$\begin{array}{c}{\mathit{\mu }}_{\mathit{S}}^{\mathcal{B}}\mathrm{(}{\mathit{\sigma }}_{}\mathsf{\text{-}}\mathsf{C}\mathrm{)}={\displaystyle \frac{{\sum }_{\mathrm{\Gamma }\in \mathcal{B}}{\mathit{\mu }}_{\mathit{S}}\mathrm{(}{\mathit{\sigma }}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{C}\mathrm{)}}{|\mathcal{B}|}}\end{array}$$ and $$\begin{array}{c}{\mathit{\mu }}_{\mathit{S}}^{\mathcal{B}}\mathrm{(}{\mathit{\sigma }}_{}\mathsf{\text{-}}\mathsf{S}\mathrm{)}={\displaystyle \frac{{\sum }_{\mathrm{\Gamma }\in \mathcal{B}}{\mathit{\mu }}_{\mathit{S}}\mathrm{(}{\mathit{\sigma }}_{\mathrm{\Gamma }}\mathsf{\text{-}}\mathsf{S}\mathrm{)}}{|\mathcal{B}|}}\end{array}$$

5.1. Empirical evaluation of the averaged measure of relative skepticism

Figure 11 graphically summarises the averages of the measure of relative skepticism ${\mathit{\mu }}_{\mathit{S}}$ over the benchmarks we introduced in Section 4: full results for each of the benchmark groups are provided in Appendix B. First of all, it is worth mentioning that – except for the case of ${\mathsf{ST}}_{}\mathsf{\text{-}}\mathsf{S}$  – the ⊆ ordering discussed in Proposition 1 is naturally maintained. Also, the measure of relative skepticism is bounded between 0 and 1 (cf. Proposition 3): since ${\mathit{\mu }}_{\mathit{S}}\mathrm{(}{\mathsf{GR}}_{\mathrm{\Gamma }}\mathrm{)}=0$ for any $\mathit{AF}$ Γ (cf. Proposition 4), we omit it from Fig. 11.

Fig. 11.

Measure of relative skepticism ${\mathit{\mu }}_{\mathit{S}}$ of sets of credulously or skeptically accepted arguments according to the semantics discussed in Definition 3 and over the benchmarks described in Section 4. $\mathsf{GR}$ is omitted as ${\mathit{\mu }}_{\mathit{S}}\mathrm{(}{\mathsf{GR}}_{\mathrm{\Gamma }}\mathrm{)}=0$ for any $\mathit{AF}$  Γ.

Fig. 12.

0.05-clusters of averaged measures of relative skepticism ${\mathit{\mu }}_{\mathit{S}}$ of sets of credulously or skeptically accepted arguments according to the semantics discussed in Definition 3 and over the benchmarks described in Section 4.

As we can see in Fig. 11, there are case where the averaged measures of relative skepticism appear to cluster closely together. To investigate this further, let us introduce the concept of a ε-cluster, as the set of credulously or skeptically accepted arguments with averaged measure of skepticism all within a chosen ε.

Definition 10.

Let $\mathcal{B}$ be a set of $\mathit{AF}$ s, and ${\tilde{\mathit{\sigma }}}_1^{\mathcal{B}}\mathrm{,}{\tilde{\mathit{\sigma }}}_2^{\mathcal{B}}\in \{{\mathsf{GR}}_{}\mathrm{,}{\mathsf{ST}}_{}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{ST}}_{}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{PR}}_{}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{PR}}_{}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{SST}}_{}\mathsf{\text{-}}\mathsf{C}\mathrm{,}{\mathsf{SST}}_{}\mathsf{\text{-}}\mathsf{S}\mathrm{,}{\mathsf{ID}}_{}\}$ , we say that ${\tilde{\mathit{\sigma }}}_1^{\mathcal{B}}$ and ${\tilde{\mathit{\sigma }}}_2^{\mathcal{B}}$ belong to the same ε-cluster ${\mathcal{C}}^{\mathit{\epsilon }}$ with $\mathit{\epsilon }⩾0$ if $|{\mathit{\mu }}_{\mathit{S}}^{\mathcal{B}}\mathrm{(}{\tilde{\mathit{\sigma }}}_1^{\mathcal{B}}\mathrm{)}-{\mathit{\mu }}_{\mathit{S}}^{\mathcal{B}}\mathrm{(}{\tilde{\mathit{\sigma }}}_2^{\mathcal{B}}\mathrm{)}|⩽\mathit{\epsilon }$ .

Figure 12 provides a qualitative interpretation of Fig. 11 in terms of 0.05-clusters of sets of credulously or skeptically accepted arguments.

From Figs 11 and 12, we can observe the following:

1. $\mathsf{GR}$ on average coincides with the skeptically accepted arguments of any semantics for $\mathsf{sASPIC}$ , and $\mathsf{rBA}$ . In the same sets it appears that all the credulously accepted set of arguments have the same averaged measure of relative skepticism;

2. $\mathsf{GR}$ on average is a good estimator17

   ¹⁷

   By good estimator we consider 0.05-clusters.

   of ${\mathsf{PR}}_{}\mathsf{\text{-}}\mathsf{S}$ , ${\mathsf{SST}}_{}\mathsf{\text{-}}\mathsf{S}$ , and $\mathsf{ID}$ for $\mathsf{sABA}$ , as they all belong to the same 0.05-cluster;

3. $\mathsf{GR}$ might serve as an estimator of all the sets of credulously and skeptically accepted arguments w.r.t. any semantics except for ${\mathsf{ST}}_{}\mathsf{\text{-}}\mathsf{S}$ for $\mathsf{rWS}$ : despite not being in the same 0.05-cluster, they would be part of the same 0.1-cluster;

4. ${\mathsf{ST}}_{}\mathsf{\text{-}}\mathsf{S}$ is furthest apart from $\mathsf{GR}$ when considering $\mathsf{rSCC}$ and $\mathsf{rWS}$ ;

5. ${\mathsf{PR}}_{}\mathsf{\text{-}}\mathsf{C}$ seems consistently to have the same measure of skepticism of ${\mathsf{SST}}_{}\mathsf{\text{-}}\mathsf{C}$ , except in $\mathsf{rER}$ ;

6. $\mathsf{GR}$ on average does not seem to be a reasonable choice to predict any set of credulously or skeptically arguments for any semantics in the case of $\mathsf{rSCC}$ , $\mathsf{rStable}$ , and $\mathsf{rER}$ .

Figure 13 depicts the distribution of the averages of Jaccard’s distances across all the dataset comparing all the combinations of sets of credulously or skeptically accepted arguments. We can thus see:

1. ${\mathsf{PR}}_{}\mathsf{\text{-}}\mathsf{S}$ almost always coincide with $\mathsf{ID}$ and ${\mathsf{SST}}_{}\mathsf{\text{-}}\mathsf{S}$ in our dataset;

2. ${\mathsf{PR}}_{}\mathsf{\text{-}}\mathsf{C}$ almost always coincide with ${\mathsf{SST}}_{}\mathsf{\text{-}}\mathsf{C}$ in our dataset.

Fig. 13.

Distributions of Jaccard’s distance – aggregating the averages for each dataset – between the various sets of credulously or skeptically accepted arguments for the various semantics identified in Definition 3 and: $\mathsf{GR}$ (a) (equivalent to ${\mathit{\mu }}_{\mathit{S}}$ ); $\mathsf{ID}$ (b); ${\mathsf{ST}}_{}\mathsf{\text{-}}\mathsf{C}$ (c); ${\mathsf{ST}}_{}\mathsf{\text{-}}\mathsf{S}$ (d); ${\mathsf{PR}}_{}\mathsf{\text{-}}\mathsf{C}$ (e); ${\mathsf{PR}}_{}\mathsf{\text{-}}\mathsf{S}$ (f); ${\mathsf{SST}}_{}\mathsf{\text{-}}\mathsf{C}$ (g); ${\mathsf{SST}}_{}\mathsf{\text{-}}\mathsf{S}$ (h).

5.2. Empirical analysis of features impacting the measure of relative skepticism

We then question whether there are some specific characteristics that substantially impact the measure of relative skepticism. To this end, following traditional machine learning approaches, we note that information about the structure of an $\mathit{AF}$ can be extracted under the form of features. Each feature summarises a potentially important property of the considered framework, and the whole set of features can be seen as the fingerprint of the $\mathit{AF}$ at hand.

Consistently with other approaches exploiting predictive models [7,10,11,33–35], we decided a large set of features from each of the $\mathit{AF}$ s. In total, the feature set includes 147 values, which exploit the representation of $\mathit{AF}$ s as a graph or as a matrix.18

¹⁸

The interested reader is referred to [35] for a detailed description of the features.

Fig. 14 provides an example $\mathit{AF}$ and its corresponding matrix encoding, from which additional features can be decided. Examples of the considered features include the number of arguments, number of Strongly Connected Components, presence of auto-loops, etc.

Fig. 14.

An example $\mathit{AF}$ , and its matrix encoding on the right.

In order to identify a subset of relevant features, out of the 147 considered, we implemented a three-step approach based on linear regression and feature selection techniques. Linear regression aims at modeling the relationships between the considered features and the value to predict by fitting a linear equation to the available data [21]. Feature selection has been performed using CorrelationAttribute in Weka [22]. The Correlation Attribute technique evaluates the worth of a feature by measuring the correlation (Pearson’s) between it and the value to predict.

The implemented three-step approach consisted of: (i) performing linear regression on the whole set of features; (ii) feature selection, and (iii) linear regression again on the subset of selected features. The idea being of generating a predictive model based on all the possible features in the first step, as a reference model. A subset of features deemed to be informative is then selected (ii), and its usefulness is assessed by generating a second predictive model, that exploits only the subset of features selected, and compare its performance against the model generated at step (i). If the models generated at steps (i) and (iii) show similar performance, we can conclude that the selected subset of features include the informative ones. Further, the use of linear regression can also help in gaining an understanding of the relevance of features, on the basis of the assigned weight.

From the performed analysis, it appears that the most important aspects are: (1) flow hierarchy;19

¹⁹

The fraction of edges not participating in cycles in a directed graph.

(2) the aperiodicity of the graph;20

²⁰

A graph is aperiodic if there is no $\mathit{k}\mathrm{>}1$ that is a integer divisor of the length of each cycle in the graph.

and (3) the number of SCCs. There are also some informative matrix-related features, but those are much harder to relate to characteristics of the AFs. Appendix C provides additional details broken down per benchmark set.

6. Conclusion

In this paper we provide a first answer to the question whether reasoning with grounded semantics, which has polynomial runtime, is not already a sufficient approximation approach. As it turns out, in many graphs models reasoning with grounded semantics actually approximates reasoning with other semantics almost perfectly. Indeed, our extensive experimental analysis (Section 5) shows that the grounded extension is a very good – sometimes a perfect – estimator of skeptical acceptance of arguments in $\mathit{AF}$ s derived from the two approaches to structured argumentation we considered in this paper, as well as from graphs obeying to the Barabasi–Albert and Watts–Strogatz models, according to all the semantics except for stable. The main reason for this is that stable semantics is the only semantics for which existence is not guaranteed, and this has clearly a substantial effect on skeptical acceptance. Instead, it appears to be not a good predictor in the case of argumentation frameworks with a substantial number of SSCs, with a large number of stable extensions, and derived from graphs obeying to the Erdös-Renyi model. The $\mathit{AF}$ s derived from graphs obeying to the Erdös-Renyi model also seem to be the ones for which the set of arguments credulously accepted according to preferred semantics is different from the set of arguments credulously accepted according to semi-stable semantics, albeit they both belong to the same 0.05-cluster. We also performed an analysis of graph features that could be mostly informative for predicting the correlation results. Unsurprisingly it appears that the most informative ones are connected to the presence of cycles in the graph.

The extensive experimental section of this paper supports the claim that an algorithm for grounded reasoning is thus a conceptually simple approximation algorithm that does not need an expensive learning phase while having a good performance on several instances of $\mathit{AF}$ s, including some of those closely linked to structured argumentation. On the one hand, this can thus help the development of real-world tools using abstract argumentation, where results, albeit approximate, might need to be provided in a near-real-time setting. On the other hand, it helps shed some light about the benchmarks currently used in the community, and provides effective guidance on the hardness of $\mathit{AF}$ s instances. Indeed, one could argue that benchmarks for which the 0.05-clusters of averaged measures of relative skepticism (i.e. Fig. 12) should resemble as much as possible the theoretical results associated to skeptical relationships between semantics, i.e. Fig. 2. From visual inspection, the set of $\mathit{AF}$ s exhibiting a large number of stable extensions, as well as those derived from graphs obeying to the Erdös-Renyi model appear to have the 0.05-clusters distributed in a way similar to the theoretical results we know from the analysis of skepticisms of the various semantics.