An experimental analysis on the similarity of argumentation 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 (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 arguments11 and a binary attack relation between them.

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.

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

An argument a is credulously (resp. skeptically) accepted with regard to a given semantics σ and a given AF Γ iff a belongs to at least one (resp. each) extension of Γ under σ. Let denote with σΓ-C (resp. σΓ-S) the set of all the credulously (resp. skeptically) accepted arguments of Γ according to σ, i.e., if ∃S∈Eσ(Γ), a∈S, then a∈σΓ-C; and if ∀S∈Eσ(Γ) a∈S, then a∈σΓ-S. Note that in the case no stable extension exists, STΓ-S=A.

With a slight abuse of notation, and begging the reader for forgiveness, we will write GRΓ=GRΓ-C=GRΓ-S and IDΓ=IDΓ-C=IDΓ-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 AF, hence for instance we will write PR-C to refer to PRΓ-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 E1 is at least as skeptical as an extension E2 if E1⊆E2, since then E1 supports the acceptance of no more arguments than E2.

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 extensions33 based to skeptical and credulous acceptance.

Figure 1 summarises the skeptical relationships that exists between different semantics extensions [4] when at least one stable extension exists.44 In it, for instance, we can see that GR⪯∩ID⪯∩PR⪯∩ST≡SST.

Fig. 1.

⪯∩ (left) and ⪯∪ (right) relation for frameworks where the stable extensions exist.

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.

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.55 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. GR, ST, PR, SST, and ID for argumentation frameworks admitting at least one stable extension.

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

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 GR) skepticism of a set of credulously or skeptically accepted arguments according to a semantics as the Jaccard’s distance from the grounded extension.66

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

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

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 σ˜Γ.

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

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

4.1.A million AFs

We exhaustively generated the first million of AFs with increasing size using the EnumeratingDungTheoryGenerator from TweetyProject.88 This generator enumerates all possible combinations of attacks with an increasing number of arguments. In the following, we collectively refer to this group of AFs as aMillion. Figure 3 illustrates the first six of them. Note that the AFs 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 AFs

Fig. 4.

One of the smallest examples of ABA-derived Dung’s AFs 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.99 This benchmark restricted the ABA benchmark provided in [14]1010 to those with at most 1,500 arguments. In the following, we collectively refer to this group of AFs as sABA. Figure 4 depicts one of the smallest.

Fig. 5.

Example of a Dung’s AF generated from an ASPIC-like theory.

We considered 300 ASPIC-like instances generated using TweetyProject.1111 In the following, we collectively refer to this group of AFs as sASPIC. Listing (1) in Appendix A lists an example of ASPIC-like theories used for generating the Dung’s AF depicted in Fig. 5; Appendix A also contains the necessary background on ASPIC [30] and the generation process.

4.3.Random AFs with palatable argumentative characteristics

Fig. 6.

One of the smallest example of Dung’s AFs generated controlling parameters related to strongly connected components.

We randomly generated, using the probo [9] SccGenerator 2,400 AFs 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 C1,…,Cn. 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 Ci to Cj with i>j (in order to avoid having few large strongly connected components).1212 In the following, we collectively refer to this group of AFs as rSCC. Figure 6 depicts one of the smallest.

We also randomly generated 200 AFs 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.1313 In the following, we collectively refer to this group of AFs as rStable. Figure 7 depicts an example of such AFs.

Fig. 7.

An example of AFs featuring a large number of stable extensions.

4.4.Random graphs as AFs

Finally, we consider random graphs generators proposed in literature as a way to generate random AFs as well.

We generated 599 AFs 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,0.05,0.1}.1414 In the following, we collectively refer to this group of AFs as rER. Figure 8 depicts an example of Erdös-Rényi-like AFs.

Fig. 8.

An example of Erdös–Rényi-like AFs.

We also generated 360 AFs 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,0.2,0.3}.1515 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 AFs as rBA. Figure 9 depicts an example Barabasi–Albert-like AFs.

Fig. 9.

An example of Barabasi–Albert-like AFs.

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 n>k>log(n)>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 AFs 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,0.2,0.3}; setting k equal to half of the number of arguments; and varying β in {0.2,0.4,0.6}.1616 In the following, we collectively refer to this group of AFs as rWS. Figure 10 depicts an example of Watts–Strogatz-like AFs.

Fig. 10.

An example of Watts–Strogatz-like AFs.

5.Empirical analysis

To inform useful considerations, let us introduce the averaged measure of relative skepticism over a set B of AFs.

5.1.Empirical evaluation of the averaged measure of relative skepticism

Figure 11 graphically summarises the averages of the measure of relative skepticism μ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 ST-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 μS(GRΓ)=0 for any AF Γ (cf. Proposition 4), we omit it from Fig. 11.

Fig. 11.

Measure of relative skepticism μ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. GR is omitted as μS(GRΓ)=0 for any AF Γ.

Fig. 12.

0.05-clusters of averaged measures of relative skepticism μ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 B be a set of AFs, and σ˜1B,σ˜2B∈{GR,ST-C,ST-S,PR-C,PR-S,SST-C,SST-S,ID}, we say that σ˜1B and σ˜2B belong to the same ε-cluster Cε with ε⩾0 if |μSB(σ˜1B)−μSB(σ˜2B)|⩽ε.

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) GR on average coincides with the skeptically accepted arguments of any semantics for sASPIC, and rBA. In the same sets it appears that all the credulously accepted set of arguments have the same averaged measure of relative skepticism;

• (2) GR on average is a good estimator1717 of PR-S, SST-S, and ID for sABA, as they all belong to the same 0.05-cluster;

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

• (4) ST-S is furthest apart from GR when considering rSCC and rWS;

• (5) PR-C seems consistently to have the same measure of skepticism of SST-C, except in rER;

• (6) 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 rSCC, rStable, and 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) PR-S almost always coincide with ID and SST-S in our dataset;

• (2) PR-C almost always coincide with SST-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: GR (a) (equivalent to μS); ID (b); ST-C (c); ST-S (d); PR-C (e); PR-S (f); SST-C (g); SST-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 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 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 AFs. In total, the feature set includes 147 values, which exploit the representation of AFs as a graph or as a matrix.1818 Fig. 14 provides an example AFand 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 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;1919 (2) the aperiodicity of the graph;2020 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 AFs 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 AFs 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 AFs, 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 AFs 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 AFs 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.