Visual Explanations for the Verification Problem in Abstract Argumentation

Abstract

The verification problem in abstract argumentation consists of checking whether a set is acceptable under a given semantics in a given argumentation graph. Explaining why the answer is so is the challenge tackled by this paper. Visual explanations in the form of subgraphs of the initial argumentation framework are defined. These explanations are grouped into classes, allowing one to select the explanation that suits them best among the several offered possibilities. Results are provided on how to use the visual aspects of these explanations to support the acceptability of a set of arguments under a semantics. Computational aspects of specific explanations are also investigated.

1. Introduction

In the context of explainable artificial intelligence (XAI), abstract argumentation is receiving a growing interest as a formal tool to provide explanations. The term argumentative XAI has emerged, with a number of application domains, ranging from machine learning to decision (for instance, in medicine or security); see Vassiliades et al. (2021) and Guo et al. (2023) for an overview. Čyras et al. (2021) present the current approaches of argumentative XAI and their open challenges, and underline that explanations for the argumentative process itself are also necessary.

According to Dung (1995), the argumentation process relies on an abstract framework which takes the form of a directed graph, whose nodes are arguments and edges represent attacks between arguments. Semantics characterize the acceptability of arguments, which, in the case of Dung (1995), take the form of extensions, that is, of sets of arguments which are collectively acceptable according to the semantics. Explaining the acceptability status of an argument or of a set of arguments, that is, why, under a given semantics, they belong to at least one extension (credulous acceptance) or to every extension (skeptical acceptance), are the main explainability issues that have been addressed so far in this context.

The most common explanation approach consists of identifying set(s) of arguments which act as explanation(s), as in Fan and Toni (2015a), Borg and Bex (2021b), Borg and Bex (2021a), Ulbricht and Wallner (2021), Liao and van der Torre (2020), and Baumann and Ulbricht (2021). However, since the argumentative process of abstract argumentation already provides ways for selecting arguments, explaining this process by further selection of arguments (although different ones) may not be fully helpful. Indeed, an explanation must be viewed as an answer to a given user that could have potentially no expert knowledge in abstract argumentation; thus, the selection of more arguments for answering does not help such users, and we think that another way for defining and presenting explanations could be more significant. Moreover, this set of argument approaches does not highlight the attacks that are involved in the explanations.

Another explanation approach consists of presenting relevant subgraphs of the framework, as in Cocarascu et al. (2018), Saribatur et al. (2020), Niskanen and Järvisalo (2020), and Racharak and Tojo (2021). Such a visual approach is particularly of interest for human users, graphs having been shown to be helpful for humans to comply with argumentation reasoning principles (Vesic et al., 2022). This graph-based approach not only highlights arguments, but also attacks.

Besides the main argumentation acceptability issues, the verification problem ${\mathit{\text{Ver}}}_{\sigma }$ also deserves interest. This problem consists, given an argumentation framework (AF) $\mathcal{A}$ , a set of arguments $S$ , and an extension-based semantics $\sigma$ , in answering the following question “Is $S$ [not] a $\sigma$ extension?” The answer to this problem is “Yes” or “No.” Determining why the answer is so is of interest, in particular, for users who may not be experts in the domain, to help them understand what makes a set of arguments an extension under a given semantics. The explanation verification problem ${\mathit{\text{XVer}}}_{\sigma }$ is thus defined as the answer to the following question: “Why is $S$ [not] a $\sigma$ extension?”

One of the first approaches that addressed this problem is Cocarascu et al. (2018): an explanation for a set $S$ satisfying a semantics $\sigma$ is a (set of) subgraph(s) $\mathit{\text{Expl}}$ of $\mathcal{A}$ such that $\mathit{\text{Expl}}$ satisfies a given graph property $C$ . In line with this approach, Besnard et al. (2022a) have provided answers for some acceptability semantics of Dung (1995) in the form of relevant subgraphs, as in Saribatur et al. (2020), Niskanen and Järvisalo (2020), and Racharak and Tojo (2021). Besnard et al. (2022a) go further by considering the possibility that the answer to the verification problem is not known before an explanation is asked and given. In this case, the explanation graph and its interpretation offer at the same time the answer to the problem and a justification for this answer. Properties that these answers satisfy have been established, depending on whether the answer to the corresponding verification problem is “Yes” or “No.” Moreover, the semantics which are considered in Besnard et al. (2022a) are based on a modular definition (any semantics can be viewed as the combination of several properties), ¹ which allows the explanations to be decomposed.

A limitation of Besnard et al. (2022a) is, however, that, for each semantic principle, a single explanation subgraph is defined. It is more realistic to consider classes (sets) of explanations. Indeed, such classes would be particularly meaningful and useful when several agents, human or artificial, are involved in the explanation of the same problem: classes offer a variety of answers, which all follow the same schema, but which may differ on their exact content. Any agent can choose or can be presented with an explanation that suits them best, and any agent can understand an explanation given by another agent, different from theirs. ² The need for classes of explanations is also supported by the study of Miller (2019) in social sciences, which highlights that explanations are selected by humans among a set of possible explanations.

In the context of formal argumentation, only a few related works can be found concerning this notion of classes of explanation. Such classes have already been proposed in Baumann and Ulbricht (2021) for the problem of credulous acceptance of an argument, where the authors consider explanation schemes made of several elements, one of them being fixed, the other ones varying from one explanation to another. Another related work is Borg and Bex (2021b), in which the authors define a parametric computation of explanations. As such, it is more the computation processes that are grouped in classes, rather than the explanations (i.e., results of the processes) themselves.

This paper aims at defining classes of explanations following a generic methodology, applied to classical semantics (conflict-free, admissible, complete, and stable), by building up on the approach of Besnard et al. (2022a). Additional properties (emptiness, uniqueness, maximality, minimality, complexity, and computation) of explanations on these new classes will be defined and investigated.

Section 2 recalls background notions relative to abstract argumentation, graph theory, and presents the explanation approach defined in Besnard et al. (2022a). Classes of explanations are defined in Section 3, Section 4 studies their properties; Section 5 shows how to compute their maximal and minimal explanations. Section 6 describes some related works and Section 7 concludes and presents some potential future works. Proofs are given in Supplement A.

Note that this work originates from Duchatelle (2023), that explanations for the defense principle have been addressed in Doutre et al. (2023a), and that this contribution is an extended version of Doutre et al. (2023b). In particular, we now propose a generalized definition for some classes of explanation, while showing that our previous results are preserved. We also bring new results for all our classes of explanations, which place boundaries on the spatial complexity of minimal explanations. Moreover, unlike Doutre et al. (2023a) and Doutre et al. (2023b), the proofs of all the results are presented.

2. Background Notions

2.1. Abstract Argumentation and Graph Theory

We begin with recalling basic notions on abstract argumentation as they have been defined by Dung (1995).

Definition 1

An Argumentation Framework (AF) is an ordered pair $(\mathcal{A},\mathcal{R})$ such that $\mathcal{R}\subseteq \mathcal{A}\times \mathcal{A}$ .

Example 1

Figures 1 and 2 give two examples of AFs.

Figure 1.

A First Example of an Argumentation Framework (Arguments are Represented by Nodes and Attacks by Edges).

Figure 2.

A Second Example of an Argumentation Framework.

Vocabulary

For an AF $(\mathcal{A},\mathcal{R})$ :

The elements of $\mathcal{A}$ are called arguments. $\mathcal{R}$ is an attack relation: for $a,b\in \mathcal{A}$ , $a\mathcal{R}b$ means that $a$ attacks $b$ . This can be extended to sets of arguments: for $S\subseteq \mathcal{A}$ and $b\in \mathcal{A}$ , we say that $S$ attacks $b$ if and only if $a\mathcal{R}b$ for some $a\in S$ .

For $a,c\in \mathcal{A}$ , we say that $a$ defends $c$ if and only if $a\mathcal{R}b$ for some $b\in \mathcal{A}$ such that $b\mathcal{R}c$ . This can be extended to sets of arguments: for $S\subseteq \mathcal{A}$ and $c\in \mathcal{A}$ , we say that $S$ defends $c$ if and only if $a\mathcal{R}b$ for some $a\in S$ and some $b\in \mathcal{A}$ such that $b\mathcal{R}c$ . ³

The main asset of Dung’s approach is the definition of semantics using some basic properties in order to define sets of acceptable arguments, as follows.

Definition 2

Let $(\mathcal{A},\mathcal{R})$ be an AF. An argument $a\in \mathcal{A}$ is acceptable with respect to $S\subseteq \mathcal{A}$ if and only if for all $b\in \mathcal{A}$ , if $b\mathcal{R}a$ then $c\mathcal{R}b$ for some $c\in S$ . $F_{\mathcal{A}}(S)$ denotes the set of the acceptable arguments with respect to $S$ .

Definition 3

Let $(\mathcal{A},\mathcal{R})$ be an AF. A subset $S$ of $\mathcal{A}$ is said to be:

conflict-free iff there are no $a$ and $b$ in $S$ such that $a$ attacks $b$ ,

admissible iff $S$ is conflict-free and for all $a\in S$ , $a$ is acceptable with respect to $S$ (so $S\subseteq F_{\mathcal{A}}(S)$ ),

complete iff $S$ is admissible and for all $a\in \mathcal{A}$ , if $a$ is acceptable with respect to $S$ then $a\in S$ (so $S=F_{\mathcal{A}}(S)$ ),

stable iff $S$ is conflict-free and $S$ attacks all $a\in \mathcal{A}\setminus S$ .

The verification problem for the four semantics given in Definition 3 can be solved in polynomial time, as indicated by Dvorák and Dunne (2018).

Example 2

Considering the AF of Figure 2, an instance of the verification problem could be: “Is $\{\}$ a stable extension?”; in this case, the answer is “No.” Another instance would be: “Is $\{a,i,f\}$ a complete extension?”; in this case, the answer is “Yes.”

Since an AF can be represented using directed graphs, we also need to recall some basic notions of graph theory.

Definition 4

Let $G=(V,E)$ and $G^{\prime }=(V^{\prime },E^{\prime })$ be two graphs.

$G^{\prime }$ is a subgraph of $G$ iff $V^{\prime }\subseteq V$ and $E^{\prime }\subseteq E$ .

$G^{\prime }$ is a strict subgraph of $G$ iff it is a subgraph of $G$ and either $V^{\prime }\subset V$ or $E^{\prime }\subset E$ .

Definition 5

Let $G=(V,E)$ and $G^{\prime }=(V^{\prime },E^{\prime })$ be two graphs.

$G^{\prime }$ is an induced subgraph of $G$ by $V^{\prime }$ if $G^{\prime }$ is a subgraph of $G$ and for all $a,b\in V^{\prime },(a,b)\in E^{\prime }$ iff $(a,b)\in E$ . $G^{\prime }$ is then denoted as $G[V^{\prime }{]}_{\mathrm{Ind}}$ .

$G^{\prime }$ is a spanning subgraph of $G$ by $E^{\prime }$ if $G^{\prime }$ is a subgraph of $G$ and $V^{\prime }=V$ . $G^{\prime }$ is then denoted as $G[E^{\prime }{]}_{\mathrm{Span}}$ .

A subgraph $G^{\prime }$ of $G$ is included in $G$ . In an induced subgraph $G^{\prime }$ of $G$ by a set of vertices, some vertices of $G$ can be missing, but all the edges concerning the kept vertices are present. In a spanning subgraph $G^{\prime }$ of $G$ by a set of edges, all the vertices of $G$ are present, but some edges of $G$ can be missing.

Example 3

Figure 3 depicts the induced subgraph of Figure 2 by the set $\{a,b,c,d,g\}$ . Figure 4 depicts the spanning subgraph of Figure 2 by the set $\{(c,f),(f,b),(f,d),(f,e),(f,h),(j,f)\}$ .

Figure 3.

An Induced Subgraph of the Argumentation Framework (AF) in Figure 2.

Figure 4.

A Spanning Subgraph of the Argumentation Framework (AF) in Figure 2.

Induced and spanning subgraphs are examples of ways to compute a graph from another single graph. Another operation producing a new graph from other ones is the union which represents the aggregation of the information contained in the two graphs:

Definition 6

Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be two graphs. The union of $G_1$ and $G_2$ is $G_1\cup G_2=(V_1\cup V_2,E_1\cup E_2)$ .

Let us consider also particular kinds of graphs, bipartite graphs, whose set of vertices can be split into two disjoint sets and in which every arc connects a vertex of one part to a vertex of the other part:

Definition 7

Let $G=(V,E)$ be a graph. $G$ is bipartite (with parts $T$ and $U$ ) if and only if there exist $T,U\subseteq V$ such that $T\cup U=V$ and $T\cap U=\varnothing$ ( $T$ and $U$ represent a partition of $V$ ) and for every $(a,b)\in E$ , either $a\in T$ and $b\in U$ , or $a\in U$ and $b\in T$ .

Some important functions can be defined over graphs.

Definition 8

Let $G=(V,E)$ be a graph.

The successor function of $G$ is the function $E^{+}:V\mapsto 2^V$ such that $E^{+}(v)=\{u|(v,u)\in E\}$ and the predecessor function of $G$ is the function $E^{-}:V\mapsto 2^V$ such that $E^{-}(v)=\{u|(u,v)\in E\}$ .

Let $S$ be a set of vertices. $E^{+}(S)=\bigcup _{v\in S}{E}^{+}(v)$ and $E^{-}(S)=\bigcup _{v\in S}{E}^{-}(v)$ .

Let $n\ge 0$ . The n-step successor (respectively, predecessor) function of $G$ is $E^{+n}(v)=\stackrel{n\text{times}}{\overbrace{E^{+}\circ \cdots \circ E^{+}}}(v)$ (respectively, $E^{-n}(v)=\stackrel{n\text{times}}{\overbrace{E^{-}\circ \cdots \circ E^{-}}}(v)$ ).

Considering an AF, the successor (respectively, predecessor) function represents the arguments that are attacked by (respectively, are the attackers of) some argument(s). An AF being usually denoted by $(\mathcal{A},\mathcal{R})$ , the successor and predecessor functions are thus denoted ${\mathcal{R}}^{+}$ and ${\mathcal{R}}^{-}$ in this context.

We then recall some notions on vertices having a particular status in a graph.

Definition 9

Let $G=(V,E)$ be a graph and $v\in V$ .

$v$ is a source vertex if and only if $E^{-}(v)=\varnothing$ .

$v$ is a sink vertex if and only if $E^{+}(v)=\varnothing$ .

$v$ is an isolated vertex if and only if it is both a source vertex and a sink vertex.

Thus, sources (respectively, sinks) are vertices that may only be origins (respectively, endpoints) of arcs. Isolated vertices are those that are connected to no other vertices.

Example 4

In the graph of Figure 4, $c$ and $j$ are source vertices, $b$ , $d$ , $e$ , and $h$ are sink vertices, and $a$ , $g$ , and $i$ are isolated vertices.

2.2. Explanation for Abstract Argumentation

We recall the main definitions of what explanations are in Besnard et al. (2022a), but only for those answering the questions about semantics results in abstract argumentation. These questions are defined as follows: let $\sigma$ represent a semantics among conflict-freeness, admissibility, completeness, and stability, and given an AF $\mathcal{A}=(\mathcal{A},\mathcal{R})$ and some set $S\subseteq A$ ,

$$\begin{array}{r}{Q}_{\sigma }^{\mathit{E}\mathit{x}\mathit{t}}:\mathtt{\text{ ``Why is }}S\mathtt{\text{ [not] a }}\sigma \mathtt{\text{ extension for }}\mathcal{A}\mathtt{\text{?"}}\end{array}$$

In order to answer these questions, and hence to provide explanations, Besnard et al. (2022a) use the decomposition of semantics into principles. The idea is to identify some properties that can be used to provide a modular characterization of semantics. We refer the reader to Doutre and Mailly (2016) for further details. Given a set $S$ , the following principles are considered:

It is worth noting that the reinstatement principle can be split into two subprinciples. Indeed, to decide whether a set $S$ of arguments contains all the arguments acceptable wrt $S$ , one must consider on the one hand the arguments that are unattacked and thus acceptable by lack of attackers (subprinciple denoted by $\mathit{\text{Rein1}}$ ), and on the other hand the arguments for which $S$ defeats all the attackers (subprinciple denoted by $\mathit{\text{Rein2}}$ ).

The following has been proven in Doutre and Mailly (2016).

Figure 5.

The Explanation $G_{\mathrm{Coh}}(\mathcal{A},S)$ for $\mathcal{A}$ Being the Argumentation Framework of Figure 1 and $S=\{b,d,e,g\}$ .

Proposition 1

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, and $S\subseteq A$ . $S$ is:

With this result, a straightforward answer arises for $Q_{\sigma }^{\mathrm{Ext}}$ : a set $S$ is an extension under semantics $\sigma$ because it respects all the principles listed for $\sigma$ in Proposition 1. This moves the burden of explanation from semantics to principles. So, in order to answer $Q_{\sigma }^{\mathrm{Ext}}$ , we are going to answer intermediate questions on principles. Let $\pi \in \{\mathit{\text{Coh}},\mathit{\text{Def}},\mathit{\text{Rein1}},$ $\mathit{\text{Rein2}},$ $\mathit{\text{CA}}\}$ represent a principle. Given an AF $\mathcal{A}=(\mathcal{A},\mathcal{R})$ and some set $S\subseteq A$ , the questions we will define answers for are:

$$\begin{array}{r}{Q}_{\pi }^{\mathit{E}\mathit{x}\mathit{t}}:\mathtt{\text{ ``Why does S [not] respect the }}\pi \mathtt{\text{ principle in }}\mathcal{A}\mathtt{\text{?"}}\end{array}$$

Besnard et al. (2022a) define visual answers to these questions. These answers take the form of a graph. This allows for the answers to be drawn, as well as to study their visual (i.e., structural) properties. More precisely, as AFs are graphs themselves, the answers given are subgraphs of an AF. Moreover, the interpretation of these subgraphs can be done using a “checking procedure” in order to explicitly identify if the given subset satisfies or not the concerned principle.

Example 5

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be the AF of Figure 1, and $S=\{b,d,e,g\}$ . Suppose we wish to answer the question “Why is {b,d,e,g} [not] an admissible extension?”

Answering this question comes down to answering the following questions:

1. “Why does {b,d,e,g} [not] respect the Coherence principle?” and

2. “Why does {b,d,e,g} [not] respect the Defence principle?”

Regarding question $1$ , according to Besnard et al. (2022a), the explanation graph shows the arguments of $S$ and the attacks, if any, between elements of $S$ ; the explanation graph for the coherence principle is then the induced subgraph of $\mathcal{A}$ on $S$ ( $\mathcal{A}[S{]}_{\mathrm{Ind}}$ —see Figure 5). Checking whether the coherence principle is satisfied or not comes down to verifying whether the obtained graph contains arcs (in which case $S$ is not conflict-free) or not ( $S$ is thus conflict-free). When looking at the graph of Figure 5, one can conclude that $S$ is conflict-free.

Regarding now the defense principle of question 2, the explanation graph of Besnard et al. (2022a) shows the elements of $S$ and their attackers, along with their attacks if any (induced subgraph of $\mathcal{A}$ on $S\cup {\mathcal{R}}^{-1}(S)$ ); these attacks only should be presented (spanning subgraph of the previous subgraph—see Figure 6). In this subgraph, an attacker of $S$ that is a source vertex is an attacker against which $S$ does not defend itself: checking whether $S$ satisfies the defense principle comes down to checking whether an attacker that is also a source vertex exists in the explanation subgraph. When looking at the graph of Figure 6, we can see that $f$ and $h$ are source vertices: $S$ does not defend all its elements.

Figure 6.

The Explanation $G_{\mathrm{Def}}(\mathcal{A},S)$ for $\mathcal{A}$ Being the Argumentation Framework of Figure 1 and $S=\{b,d,e,g\}$ .

The graphs of Figures 5 and 6 together constitute an explanation for why $S$ is not an admissible extension.

The definitions of the explanation graphs for the reinstatement and the complement attack principles follow a similar procedure, which will not be detailed here, but which can be found in Besnard et al. (2022a).

The formal definition of the explanation graph for each principle in Besnard et al. (2022a) is as follows:

Definition 10

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ , $S\subseteq \mathcal{A}$ and $\pi \in \{\mathit{\text{Coh}},\mathit{\text{Def}},\mathit{\text{Rein1}},$ $\mathit{\text{Rein2}},\mathit{\text{CA}}\}$ . $G_{\pi }(\mathcal{A},S)$ is defined as:

$$\begin{array}{rl}{G}_{\mathit{C}\mathit{o}\mathit{h}}(\mathcal{A},S)& =\mathcal{A}[S{]}_{Ind},\\ G_{\mathit{D}\mathit{e}\mathit{f}}(\mathcal{A},S)& =(\mathcal{A}[S\cup {\mathcal{R}}^{-1}(S){]}_{Ind})[\\ & \{(a,b)\in \mathcal{R}|(a\in {\mathcal{R}}^{-1}(S)\text{ and }b\in S)\text{ or }(a\in S\text{ and }b\in {\mathcal{R}}^{-1}(S))\}{]}_{Span},\\ G_{\mathit{R}\mathit{e}\mathit{i}\mathit{n}\mathit{1}}(\mathcal{A},S)& =\mathcal{A}[\{a\in \mathcal{A}|{\mathcal{R}}^{-1}(a)=\varnothing \}{]}_{Ind},\\ G_{\mathit{R}\mathit{e}\mathit{i}\mathit{n}\mathit{2}}(\mathcal{A},S)& =(\mathcal{A}[S\cup {\mathcal{R}}^{+2}(S)\cup {\mathcal{R}}^{-1}({\mathcal{R}}^{+2}(S)){]}_{Ind})[\\ & \{(a,b)\in \mathcal{R}|(a\in {\mathcal{R}}^{-1}({\mathcal{R}}^{+2}(S)),b\in {\mathcal{R}}^{+2}(S))\text{ or }(a\in S,b\in {\mathcal{R}}^{-1}({\mathcal{R}}^{+2}(S)))\}{]}_{Span}\\ G_{\mathit{C}\mathit{A}}(\mathcal{A},S)& =\mathcal{A}[\{(a,b)\in \mathcal{R}|a\in S\text{ and }b\notin S\}{]}_{Span}.\end{array}$$

The checking procedures which allow one to interpret these subgraphs in order to explicitly identify if the given subset satisfies or not the concerned principle are defined as follows by Besnard et al. (2022a):

Notation

In the following, considering an AF $\mathcal{A}=(\mathcal{A},\mathcal{R})$ and a set of arguments $S\subseteq \mathcal{A}$ , we denote by:

For each principle $\pi$ , Besnard et al. (2022a) have proven that the checking procedure $C_{\pi }$ applied on the subgraph $G_{\pi }(\mathcal{A},S)$ and the set $S$ provides an explanation that answers question $Q_{\pi }^{\mathrm{Ext}}$ . ⁴ More precisely, if a set $S$ respects a principle $\pi$ , then $C_{\pi }(G_{\pi }(\mathcal{A},S),S)$ is satisfied, otherwise it does not. When the principles are combined into a semantics $\sigma$ , the answer to $Q_{\sigma }^{\mathrm{Ext}}$ is the corresponding set of subgraphs along with their corresponding checking procedures.

Legend of the colors used in the explanation graphs (wrt a given input set and a given principle):

The arguments of the set that is given as input in the question will be in blue with dotted background .

Arguments that are displayed because they take the role of attackers (of a given set, wrt the given principle), as well as problematic attacks, will be in red with horizontal lines .

Arguments that are defended or acceptable with respect to the input set, but not part of it, will be in green with vertical lines .

Other arguments and attacks of the explanation subgraph will appear in black without background.

Elements of the explanation graph that make the conformity check of the given principle fail, will be displayed as thickened

Note that Section 4.2 will show that these explanation graphs correspond to the maximal explanations of the classes which will be defined in Section 3.

3. Classes of Explanations

We are interested in refining the notion of explanation proposed in Besnard et al. (2022a) and recalled in Section 2.2. Indeed, considering the last example (see Figure 6) leads to the following remark: for explaining the respect of the Defence principle, it seems useless to consider the two defenders of $b$ , $b$ itself, and $d$ (only one is enough for proving that $b$ is defended). Likewise, it seems useless to consider the two attacks of $f$ on both $e$ and $g$ (only one is enough for $f$ to need to be taken care of). So, in order to propose a more flexible notion of explanation, another approach based on the notion of classes of explanations is presented in this section. Of course, the definition of these classes allows us to recover the explanations described in Besnard et al. (2022a), but also results in the possibility of producing several explanations for the same question.

Hence, as briefly presented in Doutre et al. (2023b), for each principle $\pi$ , we define our explanations so that they contain at least enough information to be able to decide whether or not $S$ respects $\pi$ . We then prove that our explanations can be used in conjunction with the checking procedures recalled in Section 2.2.

Convention

An explanation to a question $Q_{\pi }^{\mathrm{Ext}}$ for a set $S$ on an AF will be given in the form of a subgraph called answer, which will be interpreted according to the checking procedure (also called conformity check) relative to $\pi$ . The elements of the answer (arguments or attacks) that do not comply with the checking procedure will appear in bold. The arguments of $S$ will be in blue with dotted background in all the answers, and depending on the semantics addressed by the question, attackers will appear in red with horizontal lines and defended arguments in green with vertical lines.

Note that, in each following section, we first consider the explanations for some given principles, then the explanation for the semantics built using these principles. In the case when the semantics is composed of only one principle, we give two distinct definitions: one for the principle and one for the semantics. Indeed, we want to be the most general as possible and so conserve the distinction between the principles and the semantics.

3.1. Explanations for Coherence and Conflict-Freeness

3.1.1. Explanations for Coherence

Recall that a set of arguments respects the coherence principle if and only if there are no arcs between its elements. Hence, if we are to show why a set of arguments is coherent, we must show a part of the graph that highlights the absence of arcs within this set.

The idea here is to have a subgraph in which we make sure that if there is at least one arc between two arguments of the questioned set, then such an arc appears in it. Indeed, the presence of at least one such arc is enough to conclude that the set is not coherent. If no such arc exists, then none is displayed, and we can conclude that the set is coherent.

In this situation, we may only focus on the arguments of the questioned set and forgo all the others.

Even if only one arc between two arguments of the set is enough, there may very well be several of them. In this case, we may choose to keep only one, all of them, or even any number in between. All these choices result in valid explanations, since we can infer from them that the set is not coherent. It is, however, crucial that at least one appears so that we do not make a false conclusion.

All these considerations give rise to the following definition.

Definition 11

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ , and consider $X=\{(a,b)\in \mathcal{R}|a,b\in S\}$ . A subgraph $({\mathcal{A}}^{\prime },{\mathcal{R}}^{\prime })$ of $\mathcal{A}$ is an answer to $Q_{\mathit{\text{Coh}}}^{\mathrm{Ext}}$ for $S$ on $\mathcal{A}$ , denoted by ${\mathit{\text{Expl}}}_{\mathrm{Coh}}(\mathcal{A},S)$ , if and only if

${\mathcal{A}}^{\prime }=S$ .

${\mathcal{R}}^{\prime }\subseteq X$ .

If $X\ne \varnothing$ , then ${\mathcal{R}}^{\prime }\ne \varnothing$ .

Example 6

Consider the AF of Figure 2 and the questions:

“Why does {a,f,i} respect the Coherence principle?” and

“Why does {b,d,i} not respect the Coherence principle?”

Figures 7 and 8 show the answers for the first and second question, respectively.

Figure 7.

Explanation on Why $\{a,f,i\}$ is Coherent in Figure 2. All Arcs Between $a$ , $f$ , and $i$ are Shown, and There is None.

Figure 8.

Explanation on Why $\{b,d,i\}$ is not Coherent in Figure 2. All Arcs Between $b$ , $d$ , and $i$ are Shown, and There is One Between $i$ and $b$ , and One Between $i$ and $d$ . These Arcs Show that the Set is not Coherent, Which is Why They Appear in Bold Red.

Once an answer to $Q_{\mathit{\text{Coh}}}^{\mathrm{Ext}}$ is provided, the conformity check simply consists of verifying whether or not an arc is displayed. ⁵ In other terms, it consists of verifying whether or not the set of arcs is empty. The following theorem indicates that this conformity check is correct for every explanation of the class corresponding to the coherence principle.

Theorem 1

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ and ${\mathit{\text{Expl}}}_{\mathrm{Coh}}(\mathcal{A},S)$ be an explanation for coherence for $S$ on $\mathcal{A}$ . $S$ is conflict-free if and only if $C_{\mathrm{Coh}}({\mathit{\text{Expl}}}_{\mathrm{Coh}}(\mathcal{A},S),S)$ is satisfied.

This theorem indeed states that, in order to know whether a set $S$ of arguments is conflict-free or not (semantic property), one might just compute an explanation for coherence ${\mathit{\text{Expl}}}_{\mathrm{Coh}}(\mathcal{A},S)$ and see whether arcs are present or not (structural property). Interestingly, since this is an equivalence result, if we know beforehand that $S$ is conflict-free, we can predict the appearance of ${\mathit{\text{Expl}}}_{\mathrm{Coh}}(\mathcal{A},S)$ (i.e., being devoid of arcs).

3.1.2. Explanation for Conflict-Freeness

Let us consider now the conflict-free semantics. Recall that this semantics is only made of the coherence principle. As such, we can define an answer to $Q_{\mathit{\text{CF}}}^{\mathrm{Ext}}$ for a set $S$ as a set containing only an explanation for coherence ${\mathit{\text{Expl}}}_{\mathrm{Coh}}(\mathcal{A},S)$ .

Definition 12

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, and $S\subseteq \mathcal{A}$ . An answer to $Q_{\mathit{\text{CF}}}^{\mathrm{Ext}}$ for $S$ on $\mathcal{A}$ , denoted by ${\mathit{\text{Expl}}}_{\mathrm{CF}}(\mathcal{A},S)$ , is a set $\{{\mathit{\text{Expl}}}_{\mathrm{Coh}}(\mathcal{A},S)\}$ .

Example 7

Figures 7 and 8 both display answers to $Q_{\mathit{\text{CF}}}^{\mathrm{Ext}}$ on the AF of Figure 2, for $\{a,f,i\}$ and $\{b,d,i\}$ , respectively.

3.2. Explanations for Defense and Admissibility

3.2.1. Explanations for Defense

Recall that a set of arguments respects the defense principle if and only if all its arguments are acceptable with respect to it. In particular, this means that for every argument that attacks one in the set, there is an argument in the set that attacks this attacker. Therefore, if we are to show why a set of arguments only contains arguments that are acceptable with respect to it, we must exhibit a part of the graph highlighting that all the attackers of this set are attacked in return.

As presented in Doutre et al. (2023a) and Doutre et al. (2023b), the idea here is to have a subgraph in which we make sure that, for every attacker of the set, if there is at least one arc from an argument of the set to that attacker, then such an arc appears in the subgraph. Indeed, the presence of such an arc is enough to conclude that the attacker we consider is being taken care of. Hence, the need to do so for every attacker. If no such arc exists, then none is displayed, and we can conclude that there is a hole in the defense of the set, and so that it does not respect the defense principle. Additionally, we should make sure that, for every attacker, an arc from that attacker to an argument of the set appears in the subgraph, to show that they are indeed attackers.

In this situation, we may only focus on the arguments of the questioned set and its attackers, and so forgo all the others. Additionally, we are only interested in attacks that go from an element of $S$ to an attacker of $S$ or vice versa.

We can make a similar observation as in the case of explanations for the coherence principle, concerning the arcs from the questioned set to its attackers or the arcs from the attackers to the questioned set. For each attacker, even if only one in both directions is enough, there may very well be several of them. Just as in the case of explanations for the coherence principle, we may in this situation choose how many we keep between one and all of them, all these choices resulting in valid explanations. Yet again, it is crucial that at least one appears, so that we do not make a false conclusion.

All these considerations give rise to the following definition.

Definition 13

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ , and consider $X=\{(b,a)\in \mathcal{R}|b\in {\mathcal{R}}^{-1}(S),a\in S\}$ and $Y=\{(a,b)\in \mathcal{R}|a\in S,b\in {\mathcal{R}}^{-1}(S)\}$ . A subgraph $({\mathcal{A}}^{\prime },{\mathcal{R}}^{\prime })$ of $\mathcal{A}$ is an answer to $Q_{\mathit{\text{Def}}}^{\mathrm{Ext}}$ for $S$ on $\mathcal{A}$ , denoted by ${\mathit{\text{Expl}}}_{\mathrm{Def}}(\mathcal{A},S)$ , if and only if

${\mathcal{A}}^{\prime }=S\cup {\mathcal{R}}^{-1}(S)$ .

${\mathcal{R}}^{\prime }\subseteq X\cup Y$ .

$\mathrm{\forall }b\in {\mathcal{R}}^{-1}(S)$ , if $b\in {\mathcal{R}}^{+1}(S)$ , then $\mathrm{\exists }(a,b)\in {\mathcal{R}}^{\prime }$ with $a\in S$ .

$\mathrm{\forall }b\in {\mathcal{R}}^{-1}(S)$ , $\mathrm{\exists }(b,a)\in {\mathcal{R}}^{\prime }$ with $a\in S$ .

Example 8

Consider the AF of Figure 2 and the questions:

"Why does {a,f,i} respect the defense principle?" and

"Why does {b,h,j} not respect the Defense principle?"

Figures 9 and 10 show the answers for the first and second questions, respectively.

Figure 9.

Explanation on Why $\{a,f,i\}$ Only Contains Arguments that are Acceptable with Respect to $\{a,f,i\}$ in Figure 2. All the Attackers of $a$ , $i$ , and $f$ are Attacked in Return.

Figure 10.

Explanation on Why $\{b,h,j\}$ does not Only Contain Arguments that are Acceptable with Respect to $\{b,h,j\}$ in Figure 2. $h$ is Attacked by $d$ , and $j$ is Attacked by $e$ , While Both $d$ and $e$ are not Attacked by $b$ , $h$ , or $j$ in Return.

Once an answer to $Q_{\mathit{\text{Def}}}^{\mathrm{Ext}}$ is provided, the conformity check consists of verifying whether or not every attacker of $S$ is attacked back by $S$ . Since, by definition, in an answer to $Q_{\mathit{\text{Def}}}^{\mathrm{Ext}}$ attackers of $S$ can only be attacked by elements of $S$ , this reduces to verifying whether or not every attacker of $S$ is attacked at all. In other terms, it consists of verifying whether or not every attacker of $S$ is not a source vertex. ⁶ The following theorem indicates that this conformity check is correct for every explanation of the class corresponding to the defense principle, provided that the questioned set is conflict-free.

Theorem 2

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ be a conflict-free set of arguments, and ${\mathit{\text{Expl}}}_{\mathrm{Def}}(\mathcal{A},S)$ be an explanation for defense for $S$ on $\mathcal{A}$ . $S\subseteq F_{\mathcal{A}}(S)$ if and only if $C_{\mathrm{Def}}({\mathit{\text{Expl}}}_{\mathrm{Def}}(\mathcal{A},S),S)$ is satisfied.

This theorem states that, in order to know whether a conflict-free set $S$ of arguments contains only acceptable arguments, one might just compute an explanation for defense ${\mathit{\text{Expl}}}_{\mathrm{Def}}(\mathcal{A},S)$ and see whether there exists a source vertex among the attackers of $S$ or not. As we have an equivalence result, this also means that we can predict what the explanation will look like if computed on a set that we know to be admissible.

In addition to Theorem 2, we have an additional result concerning the visual behavior of explanations for defense. Recall that the idea is to consider a set, its attackers, and the attacks that go from one to the other and vice versa. Hence, we can feel that there is an inherent separation between the two groups of arguments in the explanation. The following proposition formalizes this intuition.

Proposition 2

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF and $S\subseteq \mathcal{A}$ . If $S$ is conflict-free, then ${\mathit{\text{Expl}}}_{\mathrm{Def}}(\mathcal{A},S)$ is a bipartite graph with part $S$ . ⁷ ${}^{,}$ ⁸

The previous proposition is illustrated in Figure 11, which is Figure 9 reorganized for highlighting the partition of arguments.

Figure 11.

Explanation on Why $\{a,f,i\}$ Satisfies the Defense Property Presented as a Bipartite Graph.

As such, if an explanation for defense is computed on a set that is conflict-free, it is possible to display it so that its vertices are separated into two groups, with the arcs always going from one group to the other group. Alternatively, if one computes an explanation for defense for a set and if it does not result in a bipartite graph with the set as one of its parts, we may conclude that the set is not conflict-free.

3.2.2. Explanation for Admissibility

Let us consider now the admissible semantics. Recall that this semantics is made of the coherence and the defense principles. As such, we can define an answer to $Q_{\mathit{\text{Adm}}}^{\mathrm{Ext}}$ for a set $S$ as being a set containing an explanation for coherence ${\mathit{\text{Expl}}}_{\mathrm{Coh}}(\mathcal{A},S)$ and an explanation for defense ${\mathit{\text{Expl}}}_{\mathrm{Def}}(\mathcal{A},S)$ .

Definition 14

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, and $S\subseteq \mathcal{A}$ . An answer to $Q_{\mathit{\text{Adm}}}^{\mathrm{Ext}}$ for $S$ on $\mathcal{A}$ , denoted by ${\mathit{\text{Expl}}}_{\mathrm{Adm}}(\mathcal{A},S)$ , is a set $\{{\mathit{\text{Expl}}}_{\mathrm{Coh}}(\mathcal{A},S),{\mathit{\text{Expl}}}_{\mathrm{Def}}(\mathcal{A},S)\}$ .

Example 9

Figures 7 and 9 constitute an answer to $Q_{\mathit{\text{Adm}}}^{\mathrm{Ext}}$ on the AF of Figure 2 for $\{a,f,i\}$ .

3.3. Explanations for Reinstatement and Completeness

Recall that a set of arguments respects the reinstatement principle if and only if all the arguments that are acceptable with respect to it belong to it. In particular, this means that all the arguments for which the set attacks all the attackers should belong to it. However, in virtue of Definition 2, this also means that all the arguments for which there exists no attacker should belong to the set as well. The latter consideration corresponds to the $\mathit{\text{Rein1}}$ subprinciple, while the former corresponds to the $\mathit{\text{Rein2}}$ subprinciple. As they make together the reinstatement principle, following our methodology, we will define an answer to $Q_{\mathit{\text{Rein}}}^{\mathrm{Ext}}$ as a set containing an answer to $Q_{\mathit{\text{Rein1}}}^{\mathrm{Ext}}$ and an answer to $Q_{\mathit{\text{Rein2}}}^{\mathrm{Ext}}$ .

3.3.1. Explanation for $\mathit{\text{Rein1}}$

In the case of $\mathit{\text{Rein1}}$ , the idea is to have a subgraph in which we make sure that, if an unattacked argument does not belong to the questioned set, then such an argument appears in the subgraph. Indeed, the presence of such an argument is enough to conclude that there exists an argument that is acceptable with respect to the set and does not belong to it.

In this situation, we may only focus on the arguments that are not attacked and forgo all the others. Additionally, since the arguments displayed are unattacked, there cannot exist any interaction between them; thus, we will always have an empty set of arcs.

We can make a similar observation as in the previous cases, concerning the unattacked arguments that are not in the set. Even if only one is enough, there may very well be several of them. Just as in the previous cases, we may in this situation choose how many we keep between one and all of them, all these choices resulting in valid explanations. Yet again, it is crucial that at least one appears, so that we do not make a false conclusion.

All these considerations give rise to the following definition.

Definition 15

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ and consider $X=\{a\in \mathcal{A}|{\mathcal{R}}^{-1}(a)=\varnothing \}$ . A subgraph $({\mathcal{A}}^{\prime },{\mathcal{R}}^{\prime })$ of $\mathcal{A}$ is an answer to $Q_{\mathit{\text{Rein1}}}^{\mathrm{Ext}}$ for $S$ on $\mathcal{A}$ , denoted by ${\mathit{\text{Expl}}}_{\mathrm{Rein}1}(\mathcal{A},S)$ , if and only if

$S\cap X\subseteq {\mathcal{A}}^{\prime }\subseteq X$ .

${\mathcal{R}}^{\prime }=\varnothing$ .

If $(\mathcal{A}\setminus S)\cap X\ne \varnothing$ , then $\mathrm{\exists }a\in (\mathcal{A}\setminus S)\cap X$ with $a\in {\mathcal{A}}^{\prime }$ .

Example 10

Consider the AF of Figure 1 and the question ‘‘Why does {b} not respect the $\mathit{\text{Rein1}}$ principle?" Figure 12 shows the answer to that question. The unattacked arguments that do not belong to $S$ appear in green.

Figure 12.

Explanation on Why $\{b\}$ does not Contain all the Unattacked Arguments in Figure 1. Only $f$ is Unattacked and it is not Part of the Set, which is Why it Appears in Bold Green.

Once an answer to $Q_{\mathit{\text{Rein1}}}^{\mathrm{Ext}}$ is provided, the conformity check simply consists of verifying whether or not every argument displayed belongs to $S$ .

3.3.2. Explanation for $\mathit{\text{Rein2}}$

In the case of $\mathit{\text{Rein2}}$ , the idea is to have a subgraph in which we make sure that, if an argument, for which the questioned set attacks all the attackers, does not belong to the set, then such an argument appears in the subgraph. Indeed, the presence of such an argument is enough to conclude that there exists an argument that is acceptable with respect to the set and does not belong to it. To get these arguments, we may consider those for which the set attacks at least one attacker, in other words, the arguments that the set defends. These are the arguments reachable in two steps of the successor function starting from the set. We should then also consider all the attackers of these arguments.

In this situation, we may focus on the arguments of the questioned set, the arguments that it defends, and the attackers of those arguments. Additionally, we are only interested in attacks from the set to the attackers (to know whether or not the defended arguments are acceptable) and from the attackers to the defended arguments (to show that they are indeed attackers).

We can make a similar observation as in the previous cases, concerning the attacks from the set to the attackers of the arguments it defends, or the arcs from the attackers of the arguments it defends to those arguments. For each attacker, even if only one in both directions is enough, there may very well be several of them. Just as in the previous cases, we may in this situation choose how many we keep between one and all of them, all these choices resulting in valid explanations. Yet again, it is crucial that at least one appears, so that we do not make a false conclusion.

All these considerations give rise to the following definition.

Definition 16

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ and consider $X=\{(b,c)\in \mathcal{R}|b\in {\mathcal{R}}^{-1}({\mathcal{R}}^{+2}(S)),c\in {\mathcal{R}}^{+2}(S)\}$ and $Y=\{(a,b)\in \mathcal{R}|a\in S,b\in {\mathcal{R}}^{-1}({\mathcal{R}}^{+2}(S))\}$ . A subgraph $({\mathcal{A}}^{\prime },{\mathcal{R}}^{\prime })$ of $\mathcal{A}$ is an answer to $Q_{\mathit{\text{Rein2}}}^{\mathrm{Ext}}$ for $S$ on $\mathcal{A}$ , denoted by ${\mathit{\text{Expl}}}_{\mathrm{Rein}2}(\mathcal{A},S)$ , if and only if

$A^{\prime }=S\cup {\mathcal{R}}^{+2}(S)\cup {\mathcal{R}}^{-1}({\mathcal{R}}^{+2}(S))$ .

${\mathcal{R}}^{\prime }\subseteq X\cup Y$ .

$\mathrm{\forall }b\in {\mathcal{R}}^{-1}({\mathcal{R}}^{+2}(S))$ , if $b\in {\mathcal{R}}^{+1}(S)$ , then $\mathrm{\exists }(a,b)\in {\mathcal{R}}^{\prime }$ with $a\in S$ .

$\mathrm{\forall }b\in {\mathcal{R}}^{-1}({\mathcal{R}}^{+2}(S))$ , $\mathrm{\exists }(b,c)\in {\mathcal{R}}^{\prime }$ with $c\in {\mathcal{R}}^{+2}(S)$ .

Example 11

Consider the AF of Figure 1 and the question ‘‘Why does {b} not respect the $\mathit{\text{Rein2}}$ principle?" Figure 13 shows the answer for that question.

Figure 13.

Explanation on why $\{b\}$ does not Contain all the Arguments for Which it Attacks all the Attackers in Figure 1. The Arguments Defended by $b$ Appear in Green. $b$ Attacks $c$ , thus Defending $e$ , but it is not Enough to Make $e$ Acceptable Since it is also Attacked by $f$ and $h$ , so $e$ should not be in the Set, Which is the Case. However, Attacking $c$ also Makes $d$ Acceptable, so $d$ should be in the Set, Which is not the Case, Reason Why it Appears in Bold.

Once an answer to $Q_{\mathit{\text{Rein2}}}^{\mathrm{Ext}}$ is provided, the conformity check consists of verifying whether or not every argument defended by $S$ that is not in $S$ has an attacker that is not attacked by $S$ . Since, by definition, in an answer to $Q_{\mathit{\text{Rein2}}}^{\mathrm{Ext}}$ these attackers can only be attacked by elements of $S$ , this reduces to verifying whether or not every argument defended by $S$ that is not in $S$ has an attacker that is not attacked at all. In other terms, it consists of verifying whether or not every argument defended by $S$ that is not in $S$ has an attacker that is a source vertex.

The following theorem formalizes the correctness of both conformity checks associated with $\mathit{\text{Rein1}}$ and $\mathit{\text{Rein2}}$ for the reinstatement principle.

Theorem 3

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ , ${\mathit{\text{Expl}}}_{\mathrm{Rein}1}(\mathcal{A},S)$ be an explanation for $\mathit{\text{Rein1}}$ for $S$ on $\mathcal{A}$ and ${\mathit{\text{Expl}}}_{\mathrm{Rein}2}(\mathcal{A},S)$ be an explanation for $\mathit{\text{Rein2}}$ for $S$ on $\mathcal{A}$ . If $C_{\mathrm{Reins}1}({\mathit{\text{Expl}}}_{\mathrm{Rein}1}(\mathcal{A},S),S)$ and $C_{\mathrm{Reins}2}({\mathit{\text{Expl}}}_{\mathrm{Rein}2}(\mathcal{A},S),S)$ are satisfied, then $F_{\mathcal{A}}(S)\subseteq S$ .

This theorem states that by computing ${\mathit{\text{Expl}}}_{\mathrm{Rein}1}(\mathcal{A},S)$ and verifying that all its vertices are in $S$ , and by computing ${\mathit{\text{Expl}}}_{\mathrm{Rein}2}(\mathcal{A},S)$ and verifying that the arguments that $S$ defends but are not in $S$ are all attacked by a source vertex, one verifies that $S$ contains all the arguments that are acceptable with respect to it.

Notice that, on the contrary of previous results, this is not an equivalence result. We also have a result that reverses the implication, but it does not rely on the same conditions.

Theorem 4

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ , ${\mathit{\text{Expl}}}_{\mathrm{Rein}1}(\mathcal{A},S)$ be an explanation for $\mathit{\text{Rein1}}$ for $S$ on $\mathcal{A}$ and ${\mathit{\text{Expl}}}_{\mathrm{Rein}2}(\mathcal{A},S)$ be an explanation for $\mathit{\text{Rein2}}$ for $S$ on $\mathcal{A}$ . If $F_{\mathcal{A}}(S)\subseteq S$ , then $C_{\mathrm{Reins}1}({\mathit{\text{Expl}}}_{\mathrm{Rein}1}(\mathcal{A},S),S)$ and $C_{\mathrm{Reins}2}^{\prime }({\mathit{\text{Expl}}}_{\mathrm{Rein}2}(\mathcal{A},S),S)$ are satisfied, with $C_{\mathrm{Reins}2}^{\prime }({\mathit{\text{Expl}}}_{\mathrm{Rein}2}(\mathcal{A},S),S)$ being the condition “all the arguments that $S$ defends but are not in $S$ are attacked by a source vertex or by an argument of ${\mathcal{R}}^{+2}(S)$ in ${\mathit{\text{Expl}}}_{\mathrm{Rein}2}(\mathcal{A},S)$ .”

This theorem states that if we compute ${\mathit{\text{Expl}}}_{\mathrm{Rein}1}(\mathcal{A},S)$ on a set $S$ of arguments which we know contains all the arguments that are acceptable with respect to it, we know that all the arguments in ${\mathit{\text{Expl}}}_{\mathrm{Rein}1}(\mathcal{A},S)$ will be contained in $S$ . Likewise, if we compute ${\mathit{\text{Expl}}}_{\mathrm{Rein}2}(\mathcal{A},S)$ on a similar set, we know that all the arguments that $S$ defends but which are not in $S$ will be attacked by a source vertex or by an argument that $S$ defends.

From Theorems 3 and 4 follows the next corollary, which shows an equivalence result for the reinstatement principle (due to the additional constraint about the conflict-freeness of ${\mathcal{R}}^{+2}(S)$ ):

Corollary 1

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ be a set of arguments such that ${\mathcal{R}}^{+2}(S)$ is conflict-free, ${\mathit{\text{Expl}}}_{\mathrm{Rein}1}(\mathcal{A},S)$ be an explanation for $\mathit{\text{Rein1}}$ for $S$ on $\mathcal{A}$ and ${\mathit{\text{Expl}}}_{\mathrm{Rein}2}(\mathcal{A},S)$ be an explanation for $\mathit{\text{Rein2}}$ for $S$ on $\mathcal{A}$ . $F_{\mathcal{A}}(S)\subseteq S$ if and only if $C_{\mathrm{Reins}1}({\mathit{\text{Expl}}}_{\mathrm{Rein}1}(\mathcal{A},S),S)$ and $C_{\mathrm{Reins}2}({\mathit{\text{Expl}}}_{\mathrm{Rein}2}(\mathcal{A},S),S)$ are satisfied.

3.3.3. Explanation for Completeness

Let us consider now the complete semantics. Recall that this semantics is made of the coherence, defense, and reinstatement principles, the last one being divided into the $\mathit{\text{Rein1}}$ and $\mathit{\text{Rein2}}$ subprinciples. As such, we can define an answer to $Q_{\mathit{\text{Co}}}^{\mathrm{Ext}}$ for a set $S$ as being a set containing an explanation for coherence ${\mathit{\text{Expl}}}_{\mathrm{Coh}}(\mathcal{A},S)$ , an explanation for defense ${\mathit{\text{Expl}}}_{\mathrm{Def}}(\mathcal{A},S)$ , an explanation for $\mathit{\text{Rein1}}$ ${\mathit{\text{Expl}}}_{\mathrm{Rein}1}(\mathcal{A},S)$ , and an explanation for $\mathit{\text{Rein2}}$ ${\mathit{\text{Expl}}}_{\mathrm{Rein}2}(\mathcal{A},S)$ .

Definition 17

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, and $S\subseteq \mathcal{A}$ . An answer to $Q_{\mathit{\text{Co}}}^{\mathrm{Ext}}$ for $S$ on $\mathcal{A}$ , denoted by ${\mathit{\text{Expl}}}_{\mathrm{Co}}(\mathcal{A},S)$ , is a set $\{{\mathit{\text{Expl}}}_{\mathrm{Coh}}(\mathcal{A},S),{\mathit{\text{Expl}}}_{\mathrm{Def}}(\mathcal{A},S),{\mathit{\text{Expl}}}_{\mathrm{Rein}1}(\mathcal{A},S),{\mathit{\text{Expl}}}_{\mathrm{Rein}2}(\mathcal{A},S)\}$ .

Example 12

Figures 12 to 15 constitute an answer to $Q_{\mathit{\text{Co}}}^{\mathrm{Ext}}$ on the AF of Figure 1, for $\{b\}$ . In particular, Figures 14 and 15 show that $\{b\}$ respects the principles of coherence and defense, respectively, but Figures 12 and 13 show that $\{b\}$ does not respect the $\mathit{\text{Rein1}}$ and $\mathit{\text{Rein2}}$ principles, respectively.

Figure 14.

Explanation on Why $\{b\}$ is Coherent in Figure 1.

Figure 15.

Explanation on Why $\{b\}$ Only Contains Arguments that are Acceptable with Respect to $\{b\}$ in Figure 1.

3.4. Explanations for Complement Attack and Stability

3.4.1. Explanations for Complement Attack

Recall that a set of arguments respects the complement attack principle if and only if all the arguments that do not belong to the set are attacked by an argument of the set. Consequently, if we are to show why a set of arguments attacks its complement, we must show a part of the graph highlighting the attacks from this set to its complement.

The idea here is to have a subgraph in which we make sure that, for every argument that is not in the considered set, if there is at least one arc from an argument of the set to that outsider, then such an arc appears in the subgraph. Indeed, the presence of such an arc is enough to conclude that the outsider we consider is being dealt with. As a consequence, it is needed to do so for every argument that is not in the set. If no such arc exists, none is displayed, and we can conclude that some outsider is being left aside, so that the set does not respect the complement attack principle.

In this situation, it seems best to focus both on arguments of the questioned set and the arguments that do not belong to it, that is to say, all the arguments. However, we are only interested in the arcs that go from the arguments of the set to those that are not in it, and so we forgo all the others.

Similarly to the previous cases, we can observe that, for each argument that is not in the set, even though only one arc from an argument of the set is enough, there may be several of them. In such a case, we may again choose how many arcs we keep, between one and all of them, all these choices resulting in valid explanations. Once again, it is crucial that at least one appears, so that we do not make a false conclusion.

All these considerations give rise to the following definition.

Definition 18

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ and $X=\{(a,b)\in \mathcal{R}|a\in S,b\notin S\}$ . A subgraph $({\mathcal{A}}^{\prime },{\mathcal{R}}^{\prime })$ of $\mathcal{A}$ is an answer to $Q_{\mathit{\text{CA}}}^{\mathrm{Ext}}$ for $S$ on $\mathcal{A}$ , denoted by ${\mathit{\text{Expl}}}_{\mathrm{CA}}(\mathcal{A},S)$ , if and only if

${\mathcal{A}}^{\prime }=\mathcal{A}$ .

${\mathcal{R}}^{\prime }\subseteq X$ .

$\mathrm{\forall }b\in \mathcal{A}\setminus S$ , if $b\in {\mathcal{R}}^{+1}(S)$ , then $\mathrm{\exists }(a,b)\in {\mathcal{R}}^{\prime }$ with $a\in S$ .

Example 13

Consider the AF of Figure 2 and the questions:

‘‘Why does {a,f,i} respect the Complement Attack principle?" and

‘‘Why does {b,h,j} not respect the Complement Attack principle?"

Figures 16 and 17 show the answers for the first and second questions, respectively.

Figure 16.

Explanation on Why $\{a,f,i\}$ Attacks Its Complement in Figure 2. All Arguments that are not $a$ , $f$ , or $i$ are Attacked by Either $a$ , $f$ , or $i$ .

Figure 17.

Explanation on Why $\{b,h,j\}$ does not Attack its Complement in Figure 2. $d$ and $e$ are not Attacked by $b$ , $h$ , or $j$ ; this is the Reason why they Appear in Bold.

Once an answer to $Q_{\mathit{\text{CA}}}^{\mathrm{Ext}}$ is provided, the conformity check consists of verifying whether or not every argument that is not in $S$ is attacked by $S$ . Since, by definition, in an answer to $Q_{\mathit{\text{CA}}}^{\mathrm{Ext}}$ , arguments not in $S$ can only be attacked by elements of $S$ , this reduces to verifying whether or not every argument not in $S$ is attacked at all. In other terms, it consists of verifying whether or not every argument not in $S$ is not a source vertex. In addition, since the attacks from $S$ to arguments not in $S$ are the only attacks in the graph, it consists, in fact, of verifying whether or not every argument not in $S$ is not an isolated vertex. ⁹ The following theorem indicates that this conformity check is correct for every explanation of the class corresponding to the complement attack principle.

Theorem 5

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ and ${\mathit{\text{Expl}}}_{\mathrm{CA}}(\mathcal{A},S)$ be an explanation for complement attack for $S$ on $\mathcal{A}$ . $\mathcal{A}\setminus S\subseteq {\mathcal{R}}^{+1}(S)$ if and only if $C_{\mathrm{CA}}({\mathit{\text{Expl}}}_{\mathrm{CA}}(\mathcal{A},S),S)$ is satisfied.

This theorem states that, in order to know if a set $S$ of arguments attacks its complement or not, one might just compute ${\mathit{\text{Expl}}}_{\mathrm{CA}}(S)$ and look at the arguments not in $S$ . If one of them is isolated, $S$ does not attack its complement; otherwise, it does. Again, since this is an equivalence result, if we compute ${\mathit{\text{Expl}}}_{\mathrm{CA}}(S)$ on a set that we know to attack its complement, we can predict what ${\mathit{\text{Expl}}}_{\mathrm{CA}}(S)$ will look like.

As for the defense principle, we have an additional result regarding the visual behavior of explanations for the complement attack. Indeed, recall that the idea is to separate the arguments between those that belong to the questioned set and those that do not, while only considering the attacks that go from the set to its complement. Again, we can sense that a clear separation between the two groups of arguments can be made. The following proposition formalizes this intuition.

Proposition 3

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF and $S\subseteq \mathcal{A}$ . ${\mathit{\text{Expl}}}_{\mathrm{CA}}(\mathcal{A},S)$ is a bipartite graph with part $S$ ¹⁰ ${}^{,}$ ¹¹ and every argument of $S$ is a source vertex in ${\mathit{\text{Expl}}}_{\mathrm{CA}}(\mathcal{A},S)$ . ¹²

Thus, it is possible to display an explanation for the complement attack principle so that its vertices are separated into two groups, with the arcs always going from one group to the other.

Notice that Proposition 3, on the contrary to Proposition 2, does not require a condition on the set of arguments. Moreover, it is more precise in that we have an additional result on the status of the arguments in the explanation, which is not the case for Proposition 2.

3.4.2. Explanation for Stability

Let us study now the stable semantics. Recall that this semantics is made of the coherence and the complement attack principles. As such, we can define an answer to $Q_{\mathit{\text{Sta}}}^{\mathrm{Ext}}$ for a set $S$ as being a set containing an explanation for coherence ${\mathit{\text{Expl}}}_{\mathrm{Coh}}(\mathcal{A},S)$ and an explanation for complement attack ${\mathit{\text{Expl}}}_{\mathrm{CA}}(\mathcal{A},S)$ .

Definition 19

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, and $S\subseteq \mathcal{A}$ . An answer to $Q_{\mathit{\text{Sta}}}^{\mathrm{Ext}}$ for $S$ on $\mathcal{A}$ , denoted by ${\mathit{\text{Expl}}}_{\mathrm{Sta}}(\mathcal{A},S)$ , is a set $\{{\mathit{\text{Expl}}}_{\mathrm{Coh}}(\mathcal{A},S),{\mathit{\text{Expl}}}_{\mathrm{CA}}(\mathcal{A},S)\}$ .

Example 14

Figures 7 and 16 constitute an answer to $Q_{\mathit{\text{Sta}}}^{\mathrm{Ext}}$ on the AF of Figure 2, for $\{a,f,i\}$ .

4. Properties of Explanations

Now that we have formalized the correctness of the conformity checks, linking structural (and so, visual) properties to semantic ones, as well as giving additional results regarding the visual behavior of some explanations, we turn to the study of other types of properties. As briefly presented in Doutre et al. (2023b), these additional properties help to identify specific explanations inside a given class, some of them that could be deemed undesirable, and help us understand how these classes of explanations are organized. Let us first define the properties that we investigate.

4.1. Definitions of Some Specific Explanations

Minimality, Maximality

A minimal (respectively, maximal) explanation is an explanation that contains the least (respectively, all the) possible amount of information. In a sense, a minimal explanation only provides what is required to explain, whereas a maximal explanation in fact provides everything that might be relevant to explain, even if it might be redundant.

Definition 20

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ and $\pi \in \{\mathit{\text{Coh}},\mathit{\text{Def}},\mathit{\text{Rein1}},\mathit{\text{Rein2}},\mathit{\text{CA}}\}$ be an abstract argumentation principle. ${\mathit{\text{Expl}}}_{\pi }(\mathcal{A},S)$ is a minimal (respectively, maximal) answer to $Q_{\pi }^{\mathrm{Ext}}$ if and only if there is no other ${\mathit{\text{Expl}}}_{\pi }^{\prime }(\mathcal{A},S)$ such that ${\mathit{\text{Expl}}}_{\pi }^{\prime }(\mathcal{A},S)$ is a strict subgraph (respectively, supergraph) of ${\mathit{\text{Expl}}}_{\pi }(\mathcal{A},S)$ .

Emptyness

The notion of an empty explanation is one that should be avoided when providing explanations, in the sense that it somewhat represents the incapacity of the system to answer the question that has been asked. So, considering that the verification problem $\mathit{\text{XVer}}$ (evoked in the introduction section) can also be applied to a given principle $\pi$ , we can defined ${\mathit{\text{XVer}}}_{\pi }$ as the problem that consists in answering the following question: "Why does $S$ [not] satisfy the $\pi$ principle?" and so the following proposition holds:

Definition 21

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ and $\pi \in \{\mathit{\text{Coh}},$ $\mathit{\text{Def}},$ $\mathit{\text{Rein1}},$ $\mathit{\text{Rein2}},$ $\mathit{\text{CA}}\}$ be an abstract argumentation principle. ${\mathit{\text{Expl}}}_{\pi }(\mathcal{A},S)$ is an empty answer to ${\mathit{\text{XVer}}}_{\pi }$ if and only if ${\mathit{\text{Expl}}}_{\pi }(\mathcal{A},S)=(\varnothing ,\varnothing )$ .

Uniqueness

We consider an explanation to be unique when there is only one of its kind. Although we defined classes of explanations that can represent all the different points of view that could emerge as to how to answer a question, in some situations, there can only be one way to answer that question.

Definition 22

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ and $\pi \in \{\mathit{\text{Coh}},$ $\mathit{\text{Def}},$ $\mathit{\text{Rein1}},$ $\mathit{\text{Rein2}},$ $\mathit{\text{CA}}\}$ be an abstract argumentation principle. ${\mathit{\text{Expl}}}_{\pi }(\mathcal{A},S)$ is a unique answer to ${\mathit{\text{XVer}}}_{\pi }$ if and only if there is no ${\mathit{\text{Expl}}}_{\pi }(\mathcal{A},S{)}^{\prime }$ such that ${\mathit{\text{Expl}}}_{\pi }(\mathcal{A},S{)}^{\prime }\ne {\mathit{\text{Expl}}}_{\pi }(\mathcal{A},S)$ .

Minimality and uniqueness are also seen as explanation principles in Liao and van der Torre (2020). However, in Liao and van der Torre (2020), explanations are defined as sets of arguments, and not subgraphs, as we do. This obviously implies that the definitions of minimality and uniqueness given in Liao and van der Torre (2020) are slightly different from ours (we also take into account attacks and not only arguments).

4.2. Properties of Specific Explanations

Here, we provide the results of our formal study on our explanations using the aforementioned properties. The first results concern empty explanations. The following theorem shows that although empty explanations can occur, they only do so in very specific situations.

Theorem 6

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF and $S\subseteq \mathcal{A}$ . $(\varnothing ,\varnothing )$ is an answer to

1. (1)

$Q_{\pi }^{\mathrm{Ext}}$ for $S$ on $\mathcal{A}$ with $\pi \in \{\mathit{\text{Coh}},\mathit{\text{Def}},\mathit{\text{Rein2}}\}$ if and only if $S=\varnothing$ .

(2)

$Q_{\mathit{\text{Rein1}}}^{\mathrm{Ext}}$ for $S$ on $\mathcal{A}$ if and only if $\{a\in \mathcal{A}|{\mathcal{R}}^{-1}(a)=\varnothing \}=\varnothing$ .

(3)

$Q_{\mathit{\text{CA}}}^{\mathrm{Ext}}$ for $S$ on $\mathcal{A}$ if and only if $\mathcal{A}=(\varnothing ,\varnothing )$ .

As such, the empty explanation is, and can only be, a valid explanation when the question $Q_{\pi }^{\mathrm{Ext}}$ is asked on an empty set for the principles $\mathit{\text{Coh}}$ , $\mathit{\text{Def}}$ and $\mathit{\text{Rein2}}$ , and when it is asked on an empty AF for the principle $\mathit{\text{CA}}$ . In the case of the principle $\mathit{\text{Rein1}}$ , this occurs when the set of unattacked arguments in the initial AF is empty, which is certainly less specific than for the other principles. In practice, we consider that it means that when an explanation is required for the complete semantics on an AF without unattacked arguments, we may skip the explanation for $\mathit{\text{Rein1}}$ and only display the three other explanations (recall Definition 17).

Not only is the empty explanation a valid explanation in specific cases, it is itself a very specific one, as shown by the following result.

Theorem 7

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ and $\pi \in \{\mathit{\text{Coh}},$ $\mathit{\text{Def}},$ $\mathit{\text{Rein1}},$ $\mathit{\text{Rein2}},$ $\mathit{\text{CA}}\}$ be an abstract argumentation principle. If $(\varnothing ,\varnothing )$ is an answer to $Q_{\pi }^{\mathrm{Ext}}$ for $S$ on $\mathcal{A}$ , then it is unique.

This theorem states that the empty explanation is in fact so specific that, when it occurs, it is the only possible explanation.

We now turn to maximal explanations. For every abstract argumentation principle that we consider, there is only one maximal explanation. This is the object of the next theorem.

Theorem 8

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ and $\pi \in \{\mathit{\text{Coh}},$ $\mathit{\text{Def}},$ $\mathit{\text{Rein1}},$ $\mathit{\text{Rein2}},$ $\mathit{\text{CA}}\}$ be an abstract argumentation principle. If ${\mathit{\text{Expl}}}_{\pi }(\mathcal{A},S)$ is a maximal explanation for $\pi$ , then it is the unique maximal explanation for $\pi$ .

Since there exists only one maximal explanation for every abstract argumentation principle that we consider, we introduce a dedicated notation for referring to them.

Notation

In the following, considering an arbitrary AF $\mathcal{A}$ and given a set $S$ of arguments and an abstract argumentation principle $\pi$ , we will denote a maximal explanation for $\pi$ for $S$ on $\mathcal{A}$ by ${\mathit{\text{MaxExpl}}}_{\pi }(\mathcal{A},S)$ .

Our notion of maximal explanations is also what allows us to bridge the present work with the work done in Besnard et al. (2022a). This is the subject of the following proposition.

Proposition 4

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ and $\pi \in \{\mathit{\text{Coh}},$ $\mathit{\text{Def}},$ $\mathit{\text{Rein1}},$ $\mathit{\text{Rein2}},$ $\mathit{\text{CA}}\}$ be an abstract argumentation principle. ${\mathit{\text{MaxExpl}}}_{\pi }(\mathcal{A},S)=G_{\pi }(\mathcal{A},S)$ .

As such, our maximal explanations precisely correspond to the explanations defined in Besnard et al. (2022a). Thus, the classes of explanations studied in the present work can be thought of as a way to reduce the complexity of the explanations of Besnard et al. (2022a), while preserving the same properties. Indeed, in the worst case, the number of explanations can be exponential in the size of some specific sets of elements, depending on the type of explanation (for instance, the set of attacks between the arguments belonging to the extension $S$ in the case of explanations for the coherence principle). Thus, considering only minimal explanations is a first step toward a computationally efficient method, and we might then wonder if they could be unique as the maximal one. Nevertheless, as it turns out, there can be multiple minimal explanations in general for each principle. So, we do not have a uniqueness result on minimal explanations.

Example 15

Figures 18 and 19 depict different minimal explanations for coherence for $\{b,d,i\}$ on the AF of Figure 2, whereas Figure 8 gives the corresponding unique maximal explanation.

Figure 18.

A Minimal Explanation on Why $\{b,d,i\}$ is not Coherent in Figure 2.

Figure 19.

Another Possible Minimal Explanation on Why $\{b,d,i\}$ is not Coherent in Figure 2.

However, minimal and maximal explanations have a particular relation, which is the object of the next theorem.

Theorem 9

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ and $\pi \in \{\mathit{\text{Coh}},$ $\mathit{\text{Def}},$ $\mathit{\text{Rein1}},$ $\mathit{\text{Rein2}},$ $\mathit{\text{CA}}\}$ be an abstract argumentation principle. Consider a maximal explanation for $\pi$ ${\mathit{\text{MaxExpl}}}_{\pi }(\mathcal{A},S)$ , and let $M$ be the set of all minimal explanations for $\pi$ . Then ${\mathit{\text{MaxExpl}}}_{\pi }(\mathcal{A},S)=\bigcup _{G\in M}G$ .

This last theorem states that, for each abstract argumentation principle that we consider in the present work, the maximal explanation of the class related to this principle is exactly the union (in the sense of the graph union operator defined in Definition 6) of all the minimal explanations. This gives us some insight as to how the class of explanations is organized regarding the inclusion (i.e., subgraph) relation.

Example 16

Concerning the explanations for coherence for $\{b,d,i\}$ on the AF of Figure 2, the graph depicted in Figure 8 is indeed the union of the graphs presented in Figures 18 and 19 .

Finally, an original contribution of the present work is an additional result on minimal explanations. It is often acknowledged that an important quality of good explanations is simplicity. Simplicity, however, is not easily characterized and might take different forms depending on the context in which this concept is used. The following results are an attempt at characterizing the simplicity of our minimal explanations.

Proposition 5

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ , $\pi \in \{\mathit{\text{Coh}},$ $\mathit{\text{Def}},$ $\mathit{\text{Rein1}},$ $\mathit{\text{Rein2}},$ $\mathit{\text{CA}}\}$ be an abstract argumentation principle, and ${\mathit{\text{Expl}}}_{\pi }(\mathcal{A},S)=({\mathcal{A}}^{\prime },{\mathcal{R}}^{\prime })$ be an explanation for $\pi$ . The following points hold:

If $\pi =\mathit{\text{Coh}}$ and $({\mathcal{A}}^{\prime },{\mathcal{R}}^{\prime })$ is a minimal explanation for $\mathit{\text{Coh}}$ , then $|{\mathcal{A}}^{\prime }|+|{\mathcal{R}}^{\prime }|\le |\mathcal{A}|+1$ .

If $\pi =\mathit{\text{Def}}$ , $({\mathcal{A}}^{\prime },{\mathcal{R}}^{\prime })$ is a minimal explanation for $\mathit{\text{Def}}$ and $S$ is conflict-free, then $|{\mathcal{A}}^{\prime }|+|{\mathcal{R}}^{\prime }|\le 3\times |\mathcal{A}|$ .

If $\pi =\mathit{\text{Rein1}}$ and $({\mathcal{A}}^{\prime },{\mathcal{R}}^{\prime })$ is a minimal explanation for $\mathit{\text{Rein1}}$ , then $|{\mathcal{A}}^{\prime }|+|{\mathcal{R}}^{\prime }|\le |\mathcal{A}|$ .

If $\pi =\mathit{\text{Rein2}}$ , $({\mathcal{A}}^{\prime },{\mathcal{R}}^{\prime })$ is a minimal explanation for $\mathit{\text{Rein2}}$ and ${\mathcal{R}}^{-1}({\mathcal{R}}^{+2}(S))\cap S={\mathcal{R}}^{-1}({\mathcal{R}}^{+2}(S))\cap {\mathcal{R}}^{+2}(S)=\varnothing$ , then $|{\mathcal{A}}^{\prime }|+|{\mathcal{R}}^{\prime }|\le 3\times |\mathcal{A}|$ .

If $\pi =\mathit{\text{CA}}$ and $({\mathcal{A}}^{\prime },{\mathcal{R}}^{\prime })$ is a minimal explanation for $\mathit{\text{CA}}$ , then $|{\mathcal{A}}^{\prime }|+|{\mathcal{R}}^{\prime }|\le 2\times |\mathcal{A}|$ .

What these results essentially say is that the spatial complexity of our minimal explanations is linear in the number of arguments in the initial AF. Consider that in the general case, the size ¹³ of a graph is quadratic in the number of its vertices. This might very well be the case of the initial AF on which to compute an explanation. However, we can guarantee that, if a minimal explanation is computed, the size of this explanation is linearly bounded by the number of arguments in the initial AF from which it is derived. We believe that this reduction in the degree of complexity is a strong argument advocating in favor of the simplicity of our minimal explanations.

Notice that in the case of the defense and $\mathit{\text{Rein2}}$ principles, we added some hypotheses on the set $S$ for which to compute the explanation. Although we proved the result only for these specific cases, we believe the results hold in the general case. The proof in the general case is, however, much more difficult. We thus leave these general results as conjectures to be fully proved (or refuted) in future works.

Conjecture

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ , $\pi \in \{\mathit{\text{Def}},$ $\mathit{\text{Rein2}}\}$ be an abstract argumentation principle, and ${\mathit{\text{Expl}}}_{\pi }(\mathcal{A},S)=({\mathcal{A}}^{\prime },{\mathcal{R}}^{\prime })$ be an explanation for $\pi$ . If ${\mathit{\text{Expl}}}_{\pi }(\mathcal{A},S)$ is a minimal explanation for $\pi$ , then $|{\mathcal{A}}^{\prime }|+|{\mathcal{R}}^{\prime }|\le 3\times |\mathcal{A}|$ .

Note that some results presented in this section open the way to algorithmic solutions since, for a given principle, a maximal explanation covers all the possible explanations (the minimal ones, but also all the intermediate explanations). This is the aim of the next section.

5. Computation of explanations

We now turn to how to obtain an answer to a question $Q_{\pi }^{\mathrm{Ext}}$ for some $\pi \in \{\mathit{\text{Coh}},$ $\mathit{\text{Def}},$ $\mathit{\text{Rein1}},$ $\mathit{\text{Rein2}},$ $\mathit{\text{CA}}\}$ . Here are the elements that we consider reasonable to use to compute our explanations:

(1)

The initial AF.

(2)

The set of arguments for which to compute the explanation.

(3)

The abstract argumentation principle for which to compute the explanation.

Now, using these elements to compute explanations, we take advantage of the inner organization of classes of explanation regarding the inclusion relation (cf. Theorem 9). The idea is to have a way to obtain maximal explanations (which are unique in virtue of Theorem 8), and a way to obtain the other explanations from the maximal ones.

Using Proposition 4, we see that we can easily and efficiently obtain maximal explanations only using the induced subgraph and spanning subgraph operators (Definition 5) on the initial AF. Some maximal explanations require both operators (using the induced subgraph first, then the spanning subgraph), while others require only the use of one of them. In particular, maximal explanations for coherence and $\mathit{\text{Rein1}}$ are only induced subgraphs, while the maximal explanation for the complement attack is only a spanning subgraph.

Next, from the maximal explanations, we give algorithms to compute minimal explanations as briefly presented in Doutre et al. (2023b). These algorithms all follow the same schema. The idea is to start from a maximal explanation and to gradually remove elements until a minimal explanation is obtained. We give one algorithm for each abstract argumentation principle that we consider, and name them ${\mathit{\text{Alg}}}_{\pi }$ for $\pi \in \{\mathit{\text{Coh}},\mathit{\text{Def}},\mathit{\text{Rein1}},\mathit{\text{Rein2}},\mathit{\text{CA}}\}$ .

To make the algorithms for defense and $\mathit{\text{Rein2}}$ clearer, we provide the following example. We illustrate the algorithm for defense, but the algorithm for $\mathit{\text{Rein2}}$ works using the same idea.

Example 17

Consider the AF of Figure 20 and $S=\{a,b,d,e,f,g\}$ . Suppose that we are to compute a minimal explanation for defense for $S$ .

Figure 20.

An Argumentation Framework.

We begin by computing ${\mathit{\text{MaxExpl}}}_{\mathrm{Def}}(\mathcal{A},S)$ , which corresponds to $G_{\mathrm{Def}}(\mathcal{A},S)$ , according to Proposition 4, and can thus be easily obtained using the induced and spanning subgraph operators. In this case, we obtain the AF of Figure 20 as the maximal explanation.

Then, the whole idea of this algorithm can be summed up in trying to remove as many arcs as possible, without breaking the third and fourth conditions of Definition 13. To remove arcs, we use the observations that one attack to $S$ is enough to need to be taken care of (i.e., multiple attacks from a single argument to $S$ is redundant) and one attack to an attacker of $S$ is enough to take care of it (i.e., multiple attacks from $S$ to one of its attackers is redundant).

Consider the argument $c$ , which is an attacker of $S$ without being in $S$ . It attacks multiple arguments of $S$ and receives multiple attacks from $S$ . We should thus remove incoming and outgoing attacks from it.

Regarding the attacks from $S$ to $c$ , if we want to preserve Definition 13, we should remember that there is a chance that the origin of the attack might also be an attacker of $S$ . As such, we should make sure that condition 4 of Definition 13 is preserved for that origin of the attack. In this case, since $c$ is not in $S$ , there is no risk, and we can simply remove incoming attacks until one remains. For the sake of the example, we could remove $(a,c)$ .

Likewise, regarding the attacks from $c$ to $S$ , if we want to preserve Definition 13, we should remember that there is a chance that the target of the attack might also be an attacker of $S$ . As such, we should make sure that condition 3 of Definition 13 is preserved for that target of the attack. In this case, since $c$ is not in $S$ , there is no risk, and we can simply remove outgoing attacks until one remains. For the sake of the example, we could remove $(c,f)$ .

Consider now the argument $d$ , which is an attacker of $S$ while being in $S$ . Like the argument $c$ , it attacks multiple arguments of $S$ and receives multiple attacks from $S$ . We should thus remove incoming and outgoing attacks from it. We can have a similar reasoning as for $c$ .

Regarding the attacks from $S$ to $d$ , since $d$ is both an attacker and a member of $S$ , it can be attacked both by attackers and members of $S$ . In particular, it can be attacked by attackers of $S$ that are not in $S$ , which we covered previously. Since these cases have already been covered, we will only consider the attackers of $d$ that are in $S$ . If we want to preserve Definition 13, we should remember that there is a chance that these attackers might also be attackers of $S$ . As such, we should make sure that condition 4 of Definition 13 is preserved for them. In this case, since $d$ is in $S$ , there is indeed a risk, which would be to remove the last attack from them to an argument of $S$ , as it would break condition 4 of Definition 13. Thus, we must verify beforehand whether the attack to be removed is not the last of this kind. If this is the case, and if it is not the last attack from $S$ to $d$ , it is indeed removed; otherwise, it is left untouched. For the sake of the example, we could remove $(b,d)$ , because it is not the last attack from $S$ to $d$ (there is also $(a,d)$ ) and because it is not the last attack from $b$ to $S$ (there is also $(b,e)$ ).

Likewise, regarding the attacks from $d$ to $S$ , since $d$ is both an attacker and a member of $S$ , it can attack attackers of $S$ that are not in $S$ , that we covered previously. So, we will only consider the targets of $d$ that are in $S$ . If we want to preserve Definition 13, we should remember that there is a chance that these targets might also be attackers of $S$ . As such, we should make sure that condition 3 of Definition 13 is preserved for them. In this case, since $d$ is in $S$ , there is indeed a risk, which would be to remove the last attack from $S$ to them, as it would break condition 3 of Definition 13. Thus, we must verify beforehand whether the attack to be removed is not the last of this kind. If this is the case, and if it is not the last attack from $d$ to $S$ , it is indeed removed; otherwise, it is left untouched. For the sake of the example, we could remove $(d,f)$ , because $f$ is not an attacker of $S$ and because it is not the last attack from $d$ to $S$ (there is also $(d,g)$ ).

In the end, applying these procedures to all the attackers of $S$ , we obtain the AF of Figure 21, which is a minimal explanation for defense for $S$ on the AF of Figure 20. Note that this is not the only possibility.

Figure 21.

A Minimal Explanation for Defense for $\{a,b,d,e,f,g\}$ on the Argumentation Framework of Figure 20. $d$ and $e$ are not Defended Against $a$ and $b$ , Respectively.

The following theorem states that our algorithms are sound and complete for the computation of minimal explanations.

Theorem 10

Let $\mathcal{A}=(\mathcal{A},\mathcal{R})$ be an AF, $S\subseteq \mathcal{A}$ and $\pi \in \{\mathit{\text{Coh}},$ $\mathit{\text{Def}},$ $\mathit{\text{Rein1}},$ $\mathit{\text{Rein2}},$ $\mathit{\text{CA}}\}$ . Algorithm ${\mathit{\text{Alg}}}_{\pi }$ using $\mathcal{A}$ and $S$ as inputs is sound and complete for the computation of a minimal explanation for $\pi$ .

The computation of minimal explanations thus relies on the computation of maximal explanations, and the removal of some arcs (or arguments) in them. The computation of maximal explanations is already known to be polynomial (see Besnard et al., 2022a). Moreover, the complexity of the removal operation in the worst case is linear in the number of removed elements and this number is either quadratic in the number of vertices in the graph when these elements are attacks (so for any principle except the one for the first part of reinstatement), or linear in the number of vertices in the graph when these elements are vertices (for the first part of reinstatement). From these considerations, our algorithms can be considered as computationally efficient.

To finish with, we would like to point out that Algorithms ${\mathit{\text{Alg}}}_{\pi }$ can easily be adapted to compute not a minimal explanation, but an intermediate one, which is neither minimal, nor maximal. To do so, it suffices to stop the removal process before its corresponding loop has ended. By arbitrarily doing so, we can obtain any intermediate explanation. As such, we have a process to obtain any explanation, given an initial AF, a set of arguments, and an abstract argumentation principle among $\{\mathit{\text{Coh}},\mathit{\text{Def}},\mathit{\text{Rein1}},\mathit{\text{Rein2}},\mathit{\text{CA}}\}$ .

6. Related Works

In this section, we compare our work with some related works existing in the literature, and the presentation of this comparison is done using the categorization from Čyras et al. (2021) with four main categories of explanations (explanations can be either subgraphs or changes or extensions, or dialogues).

Let recall briefly the three important points concerning our approach: firstly, our explanations are subgraphs of the initial AFs; secondly our explanations must be viewed as answers to precise questions; thirdly, our explanations rely on visual criteria in order to make them usable without expert knowledge.

Let us now consider the main categories used in related works.

Explanations and Subgraphs

In Saribatur et al. (2020), the authors define explanations for the credulous nonacceptance of some argument. So the first difference with our approach is that we are not interested in the same questions. Moreover, they consider some semantics we do not consider (grounded and preferred semantics). And finally, to the contrary of Saribatur et al. (2020), our subgraphs are not only induced subgraphs but also spanning subgraphs. In Niskanen and Järvisalo (2020) and Ulbricht and Wallner (2021), explanations for the credulous nonacceptance and acceptance of some argument are defined as sets of arguments (respectively, attacks). So the same first difference is that we do not address the same problem. Moreover, the explanations proposed in Niskanen and Järvisalo (2020) and Ulbricht and Wallner (2021) are based on the behavior of the induced (respectively, spanning) subgraph resulting from the considered set of arguments (respectively, attacks). Our work instead considers the subgraphs to be the explanations themselves. And finally, the subgraphs we define are computed using both the induced subgraph and the spanning subgraph operations, while Niskanen and Järvisalo (2020) consider them separately and Ulbricht and Wallner (2021) only use induced subgraphs. Some other works, Fan and Toni (2015a) and Racharak and Tojo (2021), use specific graphs (the defense trees in which nodes are arguments and each successor of a node is an attacker of that node) to explain the credulous acceptance of some argument under admissibility. And so the same main difference between the works of Fan and Toni (2015a) and Racharak and Tojo (2021) and ours is that we do not explain the same problem.

Explanations and Changes

Changes consist of identifying which elements to remove from an AF in order to modify a given result. This is the method used in Fan and Toni (2015b), in which the authors explain why an argument is not credulously accepted under admissibility. Their explanations consist of sets of arguments or attacks to remove from the AF in order to make the considered argument credulously accepted under admissibility in the resulting subgraph. These explanations are computed using defense trees. Such sets were also studied in Ulbricht and Baumann (2019) (and called here “diagnoses”) when no arguments are credulously or skeptically accepted under some semantics and when one tries to know how to “repair” this. Diagnoses are also parts of the study of Niskanen and Järvisalo (2020) for identifying underlying reasons for the nonacceptance of an argument under credulous reasoning. Another example is given in Čyras et al. (2019) in which the existence or nonexistence of attacks is seen as an explanation in the context of argumentation for explainable scheduling. Note that all these approaches are clearly different from ours, particularly because of the addressed problems and the form of the explanations.

Explanations and Extensions

The third category of approach consists of taking sets of arguments as explanations. This is probably the most widely used approach to this problem. Here, the point of view is to consider that explanation equates to justification. In Fan and Toni (2015a), an explanation semantics, called related admissibility, is defined, providing all the reasons why an argument belongs to an admissible set. Extensions of this new semantics are explanations, and they are computed using defense trees. In Borg and Bex (2020) and Borg and Bex (2021a), the authors propose a basic framework to compute explanations as sets of arguments for the credulous/skeptical acceptance or nonacceptance of an argument with several variants: skeptical and credulous explanations, parametrization for the computation, adaptation to structured argumentation (Borg & Bex, 2021b, 2021c), etc. Some other works define their explanations from the observation that in the computation of an extension, some parts are nondeterministic choices, while others, deterministic, result from the first ones. This is the case of Liao and van der Torre (2020) (based on the strongly connected component of the AF), or of Baumann and Ulbricht (2021) (based on the grounded or the strongly admissible extension). All these approaches differ from ours in the addressed problems and the form of the explanations.

Explanations and Dialogues

The fourth and last category regroups approaches considering dialogues (or dialogue-games) as an explanation. A dialogue is a formalism in which several agents are engaged in a conversation built turn by turn by the agents and regulated by a protocol. This allows us to use dialogues as proofs of certain results (typically, a proof for the acceptability or not of a given argument). Such proofs are called dialectical proofs. Modgil and Caminada (2009) study how dialogues (called argument games) can be used to prove certain results in argumentation. This is not necessarily tied to explainability, but provides good insights into the workings of dialogues and how to use them. Booth et al. (2014) take changes as explanations for argumentative results, but use dialogues to obtain them. Arioua et al. (2017) propose a dialogue with explanatory abilities using abstract argumentation in the context of inconsistent databases. In this setting, the dialogue is taken to be the explanation that answers the user’s query. In Sklar and Azhar (2018), the authors present their argumentation-based dialogue framework for explanation in a human–robot interaction setting. As such, the dialogues produced have an explanatory role. Once again, all these approaches differ from ours in the addressed problems and the form of the explanations.

7. Conclusion and Future Works

This paper has defined classes of explanations for principles and semantics for the verification problem in abstract argumentation. These classes of explanations have been studied according to general properties such as maximality, minimality, emptyness, uniqueness, and results that place boundaries on the spatial complexity of minimal explanations, advocating for their simplicity. These classes extend and generalize the single explanation approach of Besnard et al. (2022a), allowing more flexibility in the choice of explanations that could be presented to potential users. Moreover, the paper establishes that the explanations of Besnard et al. (2022a) correspond to the maximal explanations of the defined classes, thus providing a way to compute them using graph operators. A procedure to compute minimal explanations from the maximal ones has also been provided and proven sound and complete for each class of explanations.

This contribution will be of help in any application that uses computational abstract argumentation (Čyras et al., 2021; Vassiliades et al., 2021).

Conjectures have been stated, which we believe to hold. A complete proof should be sought to either validate them or to lead to counterexamples that would invalidate them: this is a first perspective for future work.

In addition, as underlined by Čyras et al. (2021), and like in any XAI approach, an empirical evaluation should be conducted to assess to what extent these visual explanations actually are helpful for human agents to understand the answer to the verification problem. This is an important future work.

Moreover, this evaluation could also provide a first study about what is a “best explanation” and how to select it. It is therefore also related to another important future work: how to take into account the issue of the “realizability” or personalization of an explanation. Indeed, one may have in mind parts of an explanation (some arguments and some attacks), but not a correct and complete explanation; determining whether there exists such an explanation, and providing it would ensure a personalized answer. This study is also encouraged by the findings in the context of social sciences, which highlight that “humans are adept at selecting one or two causes from a sometimes infinite number of causes to be the explanation” (Miller, 2019). The reconstruction of an entire formal explanation from what is selected by a user is of interest. In order to do so, a deeper investigation of the inner structure of the classes of explanation, and more specifically of the links they could have with lattices, may be a first step.

Another finding in Miller (2019) is that explanations are contrastive. Single explanations to contrastive questions have been proposed in Besnard et al. (2022a); their generalization to classes of explanations may be studied using the work presented here, since, very often, as Besnard et al. (2022a) shows, a contrastive question can be viewed as the conjunction of some specific single questions.

The approach presented in this paper may also be extended to semantics that use additional principles such as maximality/minimality for set inclusion, for instance, the preferred or grounded semantics; in this case, some new visual criteria must be identified in order to be able to explain why a given set is or is not a preferred or a grounded extension; note that the visualization difficulty is not related to the complexity of the underlying problem (since the verification problem for the grounded semantics is a polynomial problem whereas it is an exponential one for the preferred semantics).

These last two research avenues can be considered as an attempt to produce a generic approach for the computation of explanations, on the model of the approach of Besnard et al. (2022b).

Finally, more notions of graph theory may be investigated in order to provide other kinds of visual explanations. In particular, the notion of graph isomorphism seems of great interest, especially to provide ways of reasoning by association (explaining a result via a structurally identical AF that one has already accepted).

Supplemental Material

sj-pdf-1-eai-10.1177_30504554251374991 - Supplemental material for Visual Explanations for the Verification Problem in Abstract Argumentation

Supplemental material, sj-pdf-1-eai-10.1177_30504554251374991 for Visual Explanations for the Verification Problem in Abstract Argumentation by Sylvie Doutre, Théo Duchatelle and Marie-Christine Lagasquie-Schiex in The European Journal on Artificial Intelligence