Deriving Dependency Graphs from Abstract Argumentation Frameworks: a Preliminary Report Stefano Bistarelli1,* , Carlo Taticchi1 1 Department of Mathematics and Computer Science, University of Perugia, Perugia, Italy Abstract Abstract Argumentation Frameworks (AFs) are used, in the field of Artificial Intelligence, to evaluate the justification state of conflicting information, thus allowing the development of automatic reasoning techniques and systems. Complex argumentative processes, such as decision-making and negotiation, which take place over time (usually marked by shifts in which two or more counterparts exchange their opinions), can be modelled through the Concurrent Language for Argumentation, a formalism for handling concurrent interactions between intelligent agents that use an AF as shared memory. In this paper, we first show how AFs can be interpreted as dependency graphs by exploiting the causal relation between arguments induced by the attacks. Then, we describe a methodology for obtaining a procedure that generates the given AF. Such a procedure allows to dynamically represent dialogues and other forms of interaction that brought to the instantiation of the specific AF. The dependency graph also provides an explanation for the acceptance/rejection of a given argument: the path from a leaf to a root of the underlying graph can be seen as a motivation for the assigned justification state. Keywords Computational Argumentation, Dependency Graphs, Explainable AI 1. Introduction Argumentation Theory [1] deals with the problem of representing and reasoning with conflicting information. In this context, Argumentation Frameworks constitute the basic tool for studying complex phenomena like the cognitive processes through which humans draw conclusions from a set of premises. The logic underlying the single arguments is neglected in Abstract Argumentation Frameworks (AFs) [2], which can be represented as directed graphs where nodes and edges are interpreted as arguments and attacks, respectively. On the one hand, abstracting the internal structure of arguments entails the possibility of automating tasks such as the selection of acceptable conclusions. On the other hand, AFs only provide information regarding the relations between arguments, and not about the arguments themselves. This limits the understanding we can have of the argumentative process which leads to the instantiation of a given AF, an understanding that is crucial for achieving real-world results [3]. The purpose of this paper is twofold. First, we use the causal relation between the arguments AI3 2022 - 6th Workshop on Advances in Argumentation in Artificial Intelligence, November 28, 2022, University of Udine, Udine, Italy * Corresponding author. $ stefano.bistarelli@unipg.it (S. Bistarelli); carlo.taticch@unipg.it (C. Taticchi)  0000-0001-7411-9678 (S. Bistarelli); 0000-0003-1260-4672 (C. Taticchi) Β© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) of an AF induced by attacks (the attacking argument must have been brought forward in the reasoning after the attacked argument) to interpret AFs as dependency graphs, namely structures that describe the dependencies between their elements. In particular, attacking arguments will depend on the attacked ones. Considering this type of dependency, we can derive the order in which the arguments are presented, thus obtaining a potential description of how the instantiation of the AF took place. Then, we show how AFs can be generated through the Concurrent Language for Argumentation (cla), a language able to model interactions between intelligent agents which communicate and reason through a shared AF. A cla program is given as a series of actions to perform for building the target AF. In this short paper, we restrict the study to acyclic graphs. 2. Preliminaries We briefly recall the fundamental notions of AFs and argumentation semantics. Definition 1 (AFs). An Abstract Argumentation Framework is a pair βŸ¨π΄π‘Ÿπ‘”, π‘…βŸ© where π΄π‘Ÿπ‘” is a finite set of arguments and 𝑅 is a binary relation on π΄π‘Ÿπ‘”. For two arguments π‘Ž, 𝑏 ∈ π΄π‘Ÿπ‘”, the notation (π‘Ž, 𝑏) ∈ 𝑅 represents an attack directed from π‘Ž against 𝑏. Moreover, we denote as π‘Ž+ and π‘Žβˆ’ the set of attacks respectively incoming into and outgoing from π‘Ž. A notion of defence can be used as a criterion for distinguishing acceptable sets of arguments (extensions) in the framework [2, 4]. Definition 2 (Defended Argument). Given an AF 𝐹 = βŸ¨π΄π‘Ÿπ‘”, π‘…βŸ©, an argument π‘Ž ∈ π΄π‘Ÿπ‘” is acceptable with respect to 𝐷 βŠ† π΄π‘Ÿπ‘” if and only if βˆ€π‘ ∈ π΄π‘Ÿπ‘” such that (𝑏, π‘Ž) ∈ 𝑅, βˆƒπ‘ ∈ 𝐷 such that (𝑐, 𝑏) ∈ 𝑅, and we say that π‘Ž is defended from 𝐷. The Concurrent Language for Argumentation (cla) [6, 7, 8] is a framework for modelling concurrent interactions between agents that reason and take decisions through argumentation processes. Agents communicating through cla constructs share a knowledge base, represented by an AF, to perform reasoning tasks. This shared store can be accessed and updated by the various agents via specifically designed operators that are also able to change the underlying AF. Please refer to [6] for a complete overview of the language. 3. AFs as Dependency Graphs In addition to modelling conflicts in AFs, attacks between arguments also establish a causal relationship between the arguments themselves. Consider an AF 𝐹 = βŸ¨π΄π‘Ÿπ‘”, π‘…βŸ© with two arguments π‘Ž, 𝑏 ∈ π΄π‘Ÿπ‘” and the attack relation (𝑏, π‘Ž) ∈ 𝑅. We interpret this attack as a conflict between the two arguments, with the further knowledge that 𝑏 is the argument from which the attack against π‘Ž starts. This means that 𝑏 is specifically introduced into the framework to contrast argument π‘Ž and undermine its validity. In the case π‘Ž was not present from the beginning, 𝑏 would have no reason to be part of the AF and this fact allows us to identify a causal relation between π‘Ž and 𝑏. In our example, the existence of π‘Ž is preliminary to that of 𝑏, so we can say that 𝑏 depends on π‘Ž. Following these considerations, an AF can be interpreted as a dependency graph, i.e. a directed graph representing the dependencies of various elements (in our case, arguments). Formally, a dependency graph is a couple 𝐷 = (𝑆, 𝑇 ) where 𝑆 is a set of elements and 𝑇 the transitive reduction of a relation 𝑅 βŠ† 𝑆 Γ— 𝑆. In a dependency graph, one can look for an evaluation order respecting the given dependencies. A correct evaluation order is a numbering that orders two elements π‘Ž and 𝑏 in such a way that if π‘Ž is evaluated before 𝑏, then π‘Ž must not depend on 𝑏. For example, the element corresponding to argument π‘Ž in Figure 1 should come before 𝑏 and 𝑐 in a correct evaluation order of the represented graph, while 𝑏 should come before 𝑑 and after both π‘Ž and 𝑐. Figure 1: Example of a directed graph that can be interpreted both as an AF and a dependency graph. Finding a correct evaluation order for a dependency graph amounts to reconstructing the reasoning process that leads to the generation of an AF superseding the same graph. Indeed, AFs represent conflicting information and they can be seen as the instantiation of an argumentative process between intelligent agents. In the real world, such kinds of processes take place over time and can be imagined as a succession of statements made by one or more counterparties, with the various statement referring to (attacking) each other. The beginning of this argumentative process is to be found, therefore, in the leaves of the AF, which, not attacking any other argument, must be the first sentences that started the process. 4. A cla Program for Generating AFs Using the constructs of cla, we can realise procedures able to generate AFs by modifying the shared store, which will take the shape of a desired AF. In this preliminary study, we only take into account acyclic AFs, (giving some hints on how to deal with cycles in the concluding section). For example an AF like the one illustrated in Figure 1 can be obtained as a result of the following cla procedure, which can also be executed through our web interface.1 checkw({},{}) -> add({a},{}) -> checkw({a,c},{}) -> add({b},{(b,a),(b,c)}) -> checkw({b},{}) -> add({d},{(d,b)}) -> success || checkw({a},{}) -> add({c},{(c,a)}) -> success 1 Link to cla web interface: https://conarg.dmi.unipg.it/cla. The operation π‘β„Žπ‘’π‘π‘˜π‘€(𝐴, 𝑅) verifies if the given subsets of arguments 𝐴 and attacks 𝑅 belong to the shared store, while π‘Žπ‘‘π‘‘(𝐴, 𝑅) inserts 𝐴 and 𝑅 into the AF; the execution, then, terminates with a 𝑠𝑒𝑐𝑐𝑒𝑠𝑠 (for a detailed discussion of cla operations, the reader is referred to [6]). We provide and algorithm for automatically generating AFs through cla procedures which use check and add operations in accordance with a correct evaluation order for the nodes. Algorithm 1: AFs generation through cla Data: AF 𝐹 = βŸ¨π΄π‘Ÿπ‘”, π‘…βŸ©, 𝐼 βŠ† π΄π‘Ÿπ‘”, string 𝑆 Result: cla program 𝑆 1 procedure AFtoProg(𝐹 ,𝐼,𝑆 ): 2 foreach π‘Ž in 𝐼 do 3 if π‘Ž is not discovered then 4 mark π‘Ž as discovered 5 if π‘Ž is the only discovered node in 𝐼 then 6 𝑆 = 𝑆+ β€œcheckw(a+ ,{}) -> add({a},{(π‘Ž, 𝑏) | 𝑏 ∈ π‘Ž+ )}) -> ” 7 else 8 𝑆 = 𝑆+ β€œ|| checkw(a+ ,{}) -> add({a},{(π‘Ž, 𝑏) | 𝑏 ∈ π‘Ž+ )}) -> ” 9 if π‘Žβˆ’ is empty then 10 𝑆 = 𝑆+ β€œsuccess” 11 else 12 AFtoProg(𝐹 ,π‘Žβˆ’ ,𝑆 ) The recursive procedure AFtoProg in Algorithm 1 takes in input an AF 𝐹 , a subset of argument 𝐼 and a string 𝑆 which at the end of the execution will contain the desired cla program. The set 𝐼 initially contains the leafs of the AF. All the elements in 𝐼 are processed (line 2) and only if they have not been visited yet, the procedure continues (line 3). Nodes are marked as discovered in line 4 and then are added into the cla program. If there are no other discovered nodes in 𝐼 apart from the one being visited (let us call it π‘Ž), we first check that all the arguments attacked by π‘Ž have already been added, and then we also add π‘Ž with all its outgoing attacks (lines 5 βˆ’ 6). If π‘Ž is not the only discovered nodes, we build the same cla process, this time adding the parallel construct at the beginning (lines 7 βˆ’ 8). In lines 9 βˆ’ 10 we have the terminal case: whenever we reach a root in the AF, we make the (branch of the) cla program terminate with success. If the visited node has incoming attacks, we recursively call AFtoProg passing the attackers of π‘Ž as a parameter (lines 11 βˆ’ 12). 5. Discussion We studied AFs from the perspective of dependency between arguments. We first showed how causality can be derived from the attack relations, allowing us to interpret an AF as a dependency graph in which arguments depend on those they attack. Second, we resorted to cla constructs for obtaining a program which generates a desired AF. The advantage of producing an AF in this way lies in the fact that, by reading the trace of the cla program, it is possible both to reconstruct the process that generated the AF and to obtain an explanation for the justification state assigned to the various arguments. In this paper, we conducted a preliminary investigation of various aspects related to the similarity between dependency graphs and AFs, and in the future, we plan to deepen this study under several aspects. First of all, we want to remove the constraints on the AF structure that we have imposed in the current work. To generalise our approach also to AFs with cycles, we want to devise a methodology for selecting a set of initial arguments for the procedure of Algorithm 1 even when there are no non-attacked arguments. In particular, we plan to use the Kosaraju-Sharir’s algorithm [9] to detect the strongly connected components in the AF and select in a non-deterministic fashion an argument in the cycle that can be reached by any other arguments in the graph. Then, we also want to understand how to obtain optimised programs (for instance, with shorter traces) representing the same argumentative process. In this sense, we could exploit the monoid structure of dependency graphs to identify minimal traces of cla programs. We also plan to investigate other models for concurrent execution (like Petri nets) in order to study how argumentative processes can be represented and interpreted with the ultimate goal of extracting meaningful information. Finally, it would be interesting to conduct a comparative study with existing approaches for the computation of argumentation semantics in order to understand the connections between the causal relationship we identify and the notion of acceptability. References [1] C. Dutilh Novaes, Argument and Argumentation, in: E. N. Zalta (Ed.), The Stanford Encyclopedia of Philosophy, Fall 2022 ed., Metaphysics Research Lab, Stanford University, 2022. [2] P. M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artif. Intell. 77 (1995) 321–358. [3] H. Prakken, M. D. Winter, Abstraction in argumentation: Necessary but dangerous, in: COMMA, volume 305 of Frontiers in Artificial Intelligence and Applications, IOS Press, 2018, pp. 85–96. [4] P. Baroni, M. Caminada, M. Giacomin, An introduction to argumentation semantics, Knowl. Eng. Rev. 26 (2011) 365–410. [5] M. Caminada, On the issue of reinstatement in argumentation, in: JELIA, volume 4160 of Lecture Notes in Computer Science, Springer, 2006, pp. 111–123. [6] S. Bistarelli, C. Taticchi, A concurrent language for argumentation, in: AI3 @AI*IA, volume 2777 of CEUR Workshop Proceedings, CEUR-WS.org, 2020, pp. 75–89. [7] S. Bistarelli, C. Taticchi, Introducing a tool for concurrent argumentation, in: JELIA, volume 12678 of Lecture Notes in Computer Science, Springer, 2021, pp. 18–24. [8] S. Bistarelli, C. Taticchi, A concurrent language for modelling arguing agents, Submitted to Argument & Computation (2022). [9] M. Sharir, A strong-connectivity algorithm and its applications in data flow analysis, Computers & Mathematics with Applications 7 (1981) 67–72.