Computational Argumentation: Reasoning, Dynamics, and Supporting Explainability

1 Introduction

Computational argumentation provides foundational approaches how to represent and reason with arguments within the broader field of Artificial Intelligence (AI) [Baroni et al., 2018; Gabbay et al., 2021]. Nowadays, computational argumentation finds heterogeneous application areas such as in legal reasoning and medical reasoning [Atkinson et al., 2017], e.g., in the form of supporting fraud detection at the Dutch National Police [Odekerken et al., 2020].

Among the aims of computational argumentation are supporting decision-making, explainability, and automated reasoning. Central to these are formal approaches to argumentative reasoning, which are oftentimes classified into structured [Besnard et al., 2014] and abstract argumentation [Dung, 1995]. The former prescribes formalized workflows [Caminada and Amgoud, 2007], or processes, that specify how to carry out argumentation (Figure 1). Conceptually, from a conflicting and possibly incomplete knowledge base arguments are constructed, which can, e.g., be derivations based on defeasible rules and assumptions. Relations connect arguments together, with an attacking relation being the most prominent one, yet several other notions, e.g., support relations, have been considered as well [Brewka et al., 2014]. Abstracting the content of arguments and looking only at the abstracted arguments and their relations is the topic of abstract argumentation. In this field several argumentation semantics exist [Baroni et al., 2011], which are criteria specifying which (sets of) arguments can be deemed acceptable together. As an example, a basic ingredient of checking whether an argument can be accepted is that of being defended by an admissible set of arguments, which is a conflict-free set of arguments that defends itself against all counter-arguments.

Reflecting the heterogeneity of argumentation, many argumentation formalisms are studied in the field, including general-purpose structured argumentation formalisms such as assumption-based argumentation (ABA) [Bondarenko et al., 1997], ASPIC+ [Modgil and Prakken, 2013], defeasible logic programming (DeLP) [Garc´ıa and Simari, 2004], deductive argumentation [Besnard and Hunter, 2008], Gorgias [Kakas et al., 2019], and Carneades [Gordon et al., 2007]. For abstract argumentation, argumentation frameworks (AFs) [Dung, 1995] are the most prominent formal approach, which were extended in various ways, e.g., allowing general forms of specifying acceptance conditions of arguments in abstract dialectical frameworks (ADFs) [Brewka and Woltran, 2010; Brewka et al., 2018].

All of these approaches, structured and abstract, share a high computational complexity of argumentative reasoning: even checking whether there is an admissible set defending a queried argument is NP-hard, and many other reasoning tasks have higher complexity, e.g., are hard for a class in the polynomial hierarchy [Dvoˇr´ak and Dunne, 2018].

In this paper I give an overview of our research on the topic of computational argumentation, focusing in particular on the research agenda of furthering various forms of argumentative reasoning both from foundational aspects as well as regarding algorithms and system tools. Naturally, the research outlined in this paper involves several researchers and research groups.

2 Reasoning in Argumentation Formalisms

Towards algorithmic solutions for reasoning in computational argumentation, in particular for more advanced forms of argumentative reasoning, a thorough understanding of the complexity of the tasks to solve is essential. Since even basic reasoning tasks in formal argumentation are NP-hard and several forms of reasoning in this field are hard or complete for a class in the polynomial hierarchy, algorithm design can significantly benefit from understanding the underlying complexity. Based on state-of-the-art search algorithms for NP-complete problems, such as SAT(isfiability) solving [Biere et al., 2021] and answer set programming (ASP) [Gelfond and Lifschitz, 1988; Niemel¨a, 1999], algorithm design can be tailored to usage of, e.g., SAT solvers, as required from the complexity of the task to solve. For instance, problems complete for ΣP2 are, presumably, not poly-time reducable to one SAT call, yet can be solved, e.g., via interaction of several SAT sub procedures.

We contributed to understanding the complexity of various reasoning tasks in computational argumentation. For ADFs that allow for flexible specification of acceptance conditions for arguments, with applications in legal reasoning [AlAbdulkarim et al., 2019], we showed fundamental complexity results for general ADFs [Strass and Wallner, 2015] and for restricted ADFs [Linsbichler et al., 2022]. Complexity of reasoning in general ADFs goes up to the third level of the polynomial hierarchy, and remains NP (or coNP) hard even for computationally simple argumentation semantics, such as the grounded semantics. In brief, these results imply that the complexity of reasoning in ADFs is "one level higher" in the polynomial hierarchy than reasoning in AFs, for corresponding reasoning tasks. AFs feature the fundamental notion of directed attacks, while the additional expressivity of general ADFs comes at a higher computational cost.

To overcome the complexity barrier, we investigated several restrictions to ADFs. In so-called bipolar ADFs [Brewka and Woltran, 2010], acceptance conditions of each argument in an ADF are restricted, intuitively representing only certain forms of attacks or supports between arguments. If it is known which arguments are attacking or supporting, the complexity of bipolar ADFs drops to the level of AFs, thus leading to a fragment of ADFs with additional representational expressivity [Strass, 2015], yet without higher complexity.

Going into other directions, we considered restrictions to the underlying graph structure of ADFs, by considering acyclic, bipartite, and symmetric graph structures, as well as certain distance notions to these graph structures (e.g., removal of some arguments suffices to have an acyclic ADF). While bipartiteness and symmetry does not appear to support milder forms of reasoning, acyclicity does indeed lead to milder complexity: many reasoning tasks are decidable in polynomial time. Yet even with low distances to acyclicity reasoning is not poly-time decidable.

Algorithm design for ADFs can in particular be utilized by bipolarity and further semantical restrictions that allow only a bounded number of interpretations satisfying criteria of a chosen semantics. Using state-of-the-art SAT solving, algorithms for general ADFs can make use of these complexity results to restrict usage of SAT solvers, if possible.

In the area of structured argumentation investigations of algorithmic solutions and complexity analysis face an intrinsic barrier: arguments are not explicitly given, but need to be constructed. For instance, in Figure 2 the atoms a, b, and c may be assumed and use derivations by rules x1, . . . , xn → h, denoted by edges in the figure, e.g., x can be derived from b in this example. Solid edges and nodes denote "strict components" that cannot be attacked, while dashed components denote defeasible reasoning that may be invalidated by conflicts. Each derivation is then an argument, e.g., arguments A1 to A7 in the figure.

In general structured argumentation, the number of arguments is not bounded and can be infinite [Lehtonen et al., 2023]. While in many forms of structured argumentation it is direct to restrict construction to a finite set of arguments, an exponential number of arguments can still be generated [Strass et al., 2019]. Many instantiation procedures give rise to exponentially many arguments. We showed that, under certain complexity assumptions from compilation theory, an exponential number appears unavoidable in ABA [Lehtonen et al., 2024]. When imposing certain restrictions, e.g., allowing no assumptions to be derivable for ABA frameworks, a polynomially sized "core" can be constructed which suffices to perform reasoning [Lehtonen et al., 2023].

Going into a different direction, we also investigated complexity and algorithms when working on a compact representation of arguments, without explication (construction) of arguments. For the case of ABA such a compact representation was developed earlier [Cyras et al., 2018], while for ASPIC+ a novel characterization or representation was required to be developed. These representations involve, in brief terms, specifying which part of a given knowledge base corresponds to, e.g., an admissible set of arguments. Then computation can focus on "selecting" parts of the knowledge base and checking whether a correspondence holds.

Together with earlier results, compact representations allowed to analyze complexity of argumentative reasoning in ABA and ASPIC+, without requiring construction of (potentially exponentially many) arguments. The results indicate that complexity in many cases is the same as for AFs, i.e., complexity results give here a clear indication that exponentially many arguments are not needed to be constructed for reasoning, although at the potential disadvantage of not having explicit arguments to show to a user. For the case of preferential argumentative reasoning, which is seen as key to computational argumentation, complexity rises again under certain chosen types of preferences [Lehtonen et al., 2021; Lehtonen et al., 2022].

Algorithms we developed for both ABA and ASPIC+ rely on SAT and ASP solving [Lehtonen et al., 2021; Lehtonen et al., 2020; Lehtonen et al., 2023]. In experiments, algorithms operating on compact representations of arguments were shown to be the current state of the art in terms of runtime performance. However, having explicit arguments turned out to be beneficial in cases, in particular those with certain language features that lead to more involved checks in compact representations, while on explicated arguments are more direct to compute [Lehtonen et al., 2024].

For the area of solving reasoning tasks on different argumentation formalisms, we think more research is needed. We believe that in particular (i) preferential reasoning, (ii) optimized argument construction procedures, and (iii) extending language features that can be solved are promising directions for future research.

3 Dynamics in Argumentative Reasoning

Argumentative reasoning is, naturally, not always static, in the sense that all arguments (or their contents) are known before-hand. What is sometimes called dynamics in computational argumentation refers to situations of dynamically evolving argumentation scenarios. Many such forms are studied in the literature [Doutre and Mailly, 2018].

We contributed to the field of dynamics in computational argumentation by advancing understanding of various forms of dynamic reasoning. One fundamental dynamic operation is called enforcement [Baumann et al., 2021], which aims to find arguments to expand (or remove) in a current situation such that a desired argument can be found acceptable. That is, enforcement aims to "enforce" acceptance of a queried argument, even though the current situation does not warrant acceptance. For instance, in Figure 3, the AF on the left does not include argument d in the grounded extension, which is among the most cautious semantics of AFs. Here unattacked arguments are acceptable, as well as all arguments iteratively defended by the unattacked arguments. By expanding with argument e (right in the figure), an unattacked argument defends a, and, in turn, d is defended. The enforcement problem can be phrased as an optimization problem: the changes (e.g., additions of arguments) may be required to be minimal. An application is then which arguments to pose in a dialogue in order to advance acceptance of certain arguments.

We showed complexity in several settings of enforcement of arguments in abstract and structured argumentation [Wallner et al., 2017] and developed algorithms for finding enforcements. The optimization nature of enforcement in particular suggests to use solvers for NP hard problems including optimization, such as Maximum SAT (MaxSAT) solvers [Bacchus et al., 2021] and ASP solvers. Complexity of enforcement on AFs (usually) inherits complexity of static reasoning, as one has to first check whether an argument is already accepted without modifications. Nevertheless, this form of dynamic reasoning oftentimes leads to higher complexity, e.g., the poly-time grounded semantics leads to NPcomplete problems in the enforcement setting.

Approaches that include learning in computational argumentation recently gained more and more traction in the research community [Proietti and Toni, 2023]. We considered the AF Synthesis problem [Niskanen et al., 2019] that provides an automated way of constructing attacks between arguments. The AF Synthesis problem can be seen as an inverse task than "normal" reasoning: based on semantical examples what are, e.g., admissible sets, which attacks have to be present? In the AF Synthesis problem, the task is to synthesize, learn, or generate an AF based on such semantical examples. We allow for noisy and incomplete examples, in the sense that relative trust of examples can be specified and the resulting AF should be of optimal cost (violation of an example incurs its weight as a cost). The AF Synthesis problem is connected to so-called realizability in formal argumentation [Dunne et al., 2015] which studies existence questions like "does an AF exist having certain semantical properties?" Similar to enforcement, MaxSAT solvers can be utilized to solve the AF Synthesis problem.

In the application by the Dutch National Police [Odekerken et al., 2020] a different kind of dynamic scenario is important: stability of an argumentative decision. For instance, if the current state of argumentation draws a certain conclusion, can the conclusion change if further arguments are added? That is, can one expand with further arguments and enforce another outcome? In case the answer is negative, the current outcome is seen as stable. We supported the research on the computational problem of stability, which is phrased in the ASPIC+ framework [Odekerken et al., 2023]. Here, as well, as for static forms of reasoning, compact representations were key to both complexity analysis and algorithms, with the current state of the art relying on ASP solving.

In case a current setting is not stable, i.e., a different outcome is still possible, the computational problem of relevance aims to find open issues that can lead to a stable conclusion. That is, which propositions are relevant in changing an outcome in the sense that after their addition the result is stable. For the grounded semantics, stability and relevance raise the computational complexity by one and two steps, respectively, compared to static forms of reasoning.

Summarizing, computational approaches to dynamic forms of argumentation oftentimes are more involved than more static forms of reasoning. Tasks like enforcement can be seen as basic operations that are part of more complex settings, such as in incomplete scenarios. More advanced language features, e.g., using preferential information, requires more research in the dynamic setting, as well, in our opinion.

4 Supporting Argumentative Explainability

Computational argumentation lends itself naturally to forms supporting explainability, e.g., an admissible set of arguments contains (in the structure of arguments) a clear indication why a certain conclusion can be (argumentatively) defended. More generally, argumentation in AI is seen as a promising approach to explainability in AI (XAI) [Cyras et al., 2021; Vassiliades et al., 2021].

Nevertheless, arguments, while individually direct to interpret, may face barriers, nevertheless. For instance, as briefly hinted above, the number of arguments may be high (e.g., exponential-sized w.r.t. a given rule-base), the arguments themselves might be complex derivations, and argumentation semantics might not always give clear indications of a result. For instance, checking whether an admissible set (in an AF) exists containing a queried argument is NPcomplete. Thus, checking if no such set exists is coNPcomplete, a complexity class whose witnesses for being a positive result evades polynomial-size, under certain complexity assumptions. Thus, a witness for an argument being in no admissible set is not expected to be small in general.

We investigated how to cope with high number of arguments, approaches to support "no" answers, and supporting explainability in general.

Strongly accepting or rejecting sub frameworks F ′ , of a given AF F, are parts of the AF such that any AF "inbetween" F and F ′ has the same outcome [Saribatur et al., 2020; Ulbricht and Wallner, 2021]. Say, there is no admissible set containing a queried argument in AF F, then a sub framework F ′ of F is strongly rejecting the same argument (under the same semantics) if each F ′′ which contains all parts of F ′ and may expand up to F finds the same answer. In this way, strongly accepting or rejecting sub frameworks can find small parts of the given framework that suffice to draw a certain conclusion. This behavior is connected to both stability (see above) and incomplete AFs [Baumeister et al., 2018], with a main difference is that with strongly accepting or rejecting sub frameworks an aim is to find small (minimal, optimal) sub frameworks. Complexity of reasoning under these strongly accepting or rejecting sub frameworks, both in abstract and structured argumentation [Ulbricht and Wallner, 2022], is more involved than static forms of reasoning.

While strongly accepting or rejecting sub frameworks may focus reasoning on a part of a given AF (or structured rule base), they are restricted to parts of the given input. In contrast, forms of abstraction, as investigated, e.g., in model checking [Clarke et al., 2003], allow for abstracting parts of the input, while aiming to being faithful to original argumentative outcomes. We considered forms of existential abstraction both on AFs [Saribatur and Wallner, 2021] and in ABA [Apostolakis et al., 2024], by clustering parts of the input. For instance, in Figure 4, in a given AF (a) the left-most three arguments are clustered into one "clustered argument" (Figure 4(b)). By adapting classical argumentation semantics to the clustered setting, in the AF in the middle, the same argumentative conclusions can be drawn, i.e., this clustering is faithful, while the clustering on the right leads to an incorrect conclusion. The latter is deemed spurious, due to faulty reasoning introduced in the abstraction. Abstraction is here "existential" in the sense that attacks in the clustering are present if there exists an attack in the AF from or to the clusters.

An advantage of such clusterings is that they can significantly reduce the set of arguments, but instead of removal, arguments are abstracted into clusters. For instance, in the faithful clustering (Figure 4(b)) argument e can be defended against the attack originating form d, by using the cluster. But which argument is responsible for defense was abstracted away. Abstraction via clustering can also be used interactively: a user may choose more or less abstraction (i.e., "zooming" in or out).

While many research works are strengthening the potential, we believe that more research is needed to fully realize the explainability potential of computational argumentation. In addition to the aforementioned form of abstraction, general simplification procedures are, we believe, useful for users. For instance, users may interactively gain insights into why certain (argumentative) conclusions hold. For this, users might need simplifications in order to digest main components of argumentative reasoning.

5 Conclusions

We gave an overview of the author's contributions to computational argumentation, going from foundational complexity questions to algorithmic solutions. Static forms, in which the current state does not change, and dynamic forms, ranging from finding usable arguments to learning arguments, were studied.

As summarized in the above sections, future research is, in our opinion, needed to further potential of computation argumentation. Among the promising directions are support for more advanced language features in the formal languages, both conceptually and from an algorithmic perspective. Moreover, support for explainability, in its many forms, is a useful research direction. We think in particular interactions with users is a direction with potential for advancing applications.

Acknowledgments

The author is supported by the Austrian Science Fund (FWF) P35632. The author thanks all co-authors for their insightful and continuous cooperations.