The Linear Algebra of Abstract Argumentation Andrea Pazienza and Stefano Ferilli Dipartimento di Informatica – Università di Bari Aldo Moro, Bari, Italy {andrea.pazienza,stefano.ferilli}@uniba.it Abstract. In Abstract Argumentation, the task of modeling and ana- lyzing semantics is a hot problem. An alternative representation of com- putational models of argument, based on the matrix theory, is proposed, in order to obtain a deeper understanding of extension-based semantics and of ranking semantics too. In this paper, we start from the concept of matrix representation of an argumentation graph and develop a gen- eral strategy to model both extension-based semantics and ranking-based ones, and both classical and new ones, in terms of matrix operations. This line of research is strongly based on linear algebra to evaluate arguments. Such procedures confirm the ability to evaluate arguments and open to new perspectives in the field of ranking semantics. Keywords: Abstract Argumentation · Semantics · Matrix Theory. 1 Introduction and Related Work Abstract Argumentation Frameworks (AFs) are usually represented as directed graphs not only because of the feature of visualization, but also because they play a significant role in modeling and analyzing the semantics of AFs. Mathe- matically speaking, studies in Abstract Argumentation semantics are concerned with graph-theoretic measures on directed graphs. Matrix theory is an important field of Linear Algebra used in particular for representing and handling graphs. Adjacency matrices, representing adjacent nodes, are capable of representing undirected and directed graphs. So, matrix representations provide a bridge to linear algebra-based algorithms for graph computation. Therefore, the potential application to AFs is worth to expect, since efficient and versatile methods for Abstract Argumentation are important for further advances in the field. To the best of our knowledge, there are only few works in the literature of matrix representation and computation of argument graphs. An initial work in defining a matrix representation of argumentation graphs is made in [12], in which the matrices and some operations on them are introduced into the study of Dung’s theory of argumentation, showing that every AF can be represented by a matrix, and the basic extensions of an AF can be determined by sub-blocks of its matrix. Similarly to this approach, we exploit the matrix representation of an argumentation graph, but we rely on a more intuitive strategy which is directly compatible with the theory of Abstract Argumentation. Another similar approach is defined in [8], in which it is introduced a matrix-based mathematical 2 A. Pazienza et al. approach for determining whether a set of arguments is an extension. This differs in the fact that it does not use matrix sub-blocks but it creates sets of arguments in a matrix representation to define tests for the different argumentation seman- tics as they do not try to find all arguments passing a given criteria. In [11], it is proposed a Boolean matrix approach to encode Dung’s acceptability seman- tics. Each semantics is encoded into one or more Boolean constraint models, which can be solved by Boolean constraint solvers. Recently, in [2], authors rep- resent a Weighted Argumentation Framework (WAF) by a non-binary matrix, and characterize the basic extensions by analysing sub-blocks of this matrix. While, in [5], it is investigated the relationship between semantics for for- mal argumentation and measures from social networking theory. This is done by considering matrix exponentials in which measures used for link prediction in social networks are exploited in the same way to measure acceptability of ar- guments for AFs. The intuition behind authors’ matrix representation is similar to the idea presented in the present work, but it is only used to devise a new ranking-based semantics. Moreover, it does not take into account problems like self-attacking or unattacked arguments, and there is no discussion about how the exponential evaluation behaves with cyclic graphs. The contributions of this paper are to use algebraic methods to obtain a deeper understanding of extension-based semantics, and to apply these ideas to bipolar and weighted AFs and to ranking semantics too. The matrix-based approach is related to the development of efficient techniques for computing ex- tensions. Moreover, well-established techniques for the incremental computation of matrix-product could be profitably used to address the incremental compu- tation of extensions in dynamic AFs. Starting with tools coming from Linear Algebra, we show that it is possible to give a uniform (matrix-based) represen- tation method of an argumentation graph, and a continuity in modeling both extension-based semantics and ranking-based ones, and both classical and new ones, by developing of a single general matrix-based strategy. The paper is organized as follows. After quickly discussing background and the basic concept of Argumentation Matrix in the next section, Section 3 defines the problem of developing a final matrix which is able to represent all the defeats and defenses between arguments, Section 4 describes the ability to find classical extension-based semantics in terms of matrices, and sections 5, 6 and 7 show its applicability also to generalizations of the standard AF. With the matrix operations in place, we then provide a new ranking-based semantics, coming from the field of Linear Algebra, that gives insights on some interesting properties. Finally, Section 8 concludes the paper. 2 Background Let us start by providing the basics of Abstract Argumentation. Definition 1 An AF is a pair F = hA, Ri, where A is a finite set of arguments and R ⊆ A × A. Given α, β ∈ A, the relation αRβ means that α attacks β. The Linear Algebra of Abstract Argumentation 3 An argumentation semantics is the formal definition of a method ruling the argu- ment evaluation process. The most basic concepts shared by all argumentation semantics in the literature are conflict-freeness and defense. Then, standard acceptability semantics, introduced by Dung [6], characterize conflict-free and defended sets of arguments. Definition 2 Let F = hA, Ri be an AF, and S ⊆ A: – S is conflict-free ( cf for short) if @α, β ∈ S s.t. αRβ; – α ∈ A is defended by S if ∀β ∈ A : βRα ⇒ ∃γ ∈ S s.t. γRβ; – fF : 2A 7→ 2A s.t. fF (S) = {α | α is defended by S} is called the character- istic function of F ; – S is admissible if S is cf and S is defended by itself, i.e. ∀α ∈ S, ∀β ∈ A : βRα ⇒ ∃γ ∈ S s.t. γRβ. – S is a grounded extension if S is the admissible least fixed point of fF ; – S is a stable extension if S is cf and ∀α ∈ A, α ∈ / S, ∃β ∈ S s.t. βRα. Regarding the generalizations of Dung’s AF, we recall the following frameworks. A Bipolar AF (BAF ) [4] is an extension of Dung’s AF in which two kinds of interactions between arguments are possible: the attack relation and the support relation. A Weighted AF (WAF ) [7] is another extension of Dung’s AF in which attacks between arguments are associated with a weight, indicating the relative strength of the attack. A Bipolar Weighted AF (BWAF ) [10] incorporates both above generalizations of Dung-style AFs. The idea behind it is to allow not only weighted attack relations between abstract arguments, but also weighted support relations. This is achieved by assigning to each relation a weight which can be positive or negative. Finally, ranking-based semantics [1] methods determine, for any framework, a ranking of the available arguments in the form of a pre-order (reflexive and transitive relation). These semantics focus on the evaluation of individual arguments rather than sets of arguments. 2.1 The Argumentation Matrix An argumentation graph can be represented with a slightly different version of its adjacency matrix. Definition 3 Let F = hA, Ri be an AF. Let |A| = n, then the Argumentation Matrix of F is a n × n matrix MF = [Mij ] such that for any two arguments αi , αj ∈ A it holds that ( −1 if hαi , αj i ∈ R Mij = 0 otherwise The substantial difference from [12, 8, 11, 2] is that we have the entry Mij = −1 iff there is an attack from the argument in ith row to the argument in j th column. This representation choice fits more the concept of attack in the argumentation graph, to such an extent of representing a “negative” relation, which has a basic role in our novel study. 4 A. Pazienza et al. α β γ δ  Fig. 1. F1 : Example of an AF representation Example 1. The AF in Figure 1 has the following Argumentation Matrix: α β γ δ    α 0 −1 0 0 0 β 0 0 0 0 0    MF1 = γ   0 −1 0 −1 0   δ  0 0 −1 0 −1   0 0 0 0 −1 In the Argumentation Matrix, each row i represents the attacks launched towards the j th argument. While, each column j represents the attacks received from the ith argument. In this setting, our purpose is to exploit the Argumentation Matrix in order to devise a strategy to represent the defenses for each argument. We notice that the notion of defense for an argument is based on the con- cept of transitivity which stipulates that relations between any two nodes in the graph can be described by even-length paths between the two nodes. With matrix theory, we can explore the argumentation graph uniformly with comput- ing subsequent powers of the Argumentation Matrix. Interesting things happen when we multiply the adjacency matrix by itself. By multiplying the adjacency matrix by itself, we retrieve the number of walks of length 2 such that there is an edge from i to j. And this is exactly the Aij entry in A2 , by the definition of matrix multiplication. Generally, the powers of the adjacency matrix counts the number of walks such that the entry Aij in Ak gives the number of walks from i to j of length k. Similarly, with increasing exponent, the powers of the Argumentation Matrix retrieve the indirect attack (respectively, defense) for an existing odd-length (respectively, even-length) path between two nodes. Definition 4 Let F = hA, Ri be an acyclic AF, k ∈ N > 0, and let MF be the Argumentation Matrix of F such that MFk+1 = 0 (i.e., F is connected with paths of max-length k), then the matrix SF = MF + MF2 + . . . + MFk is the resulting sum of power series MFi , with i = 1, . . . , k, called Summation Matrix, and contains entries [Sij ] of three types: – Sij ∈ Z < 0, indicating that there is an overall (indirect) attack from argu- ment of row i towards argument of column j; – Sij ∈ Z > 0, indicating that there is an overall defense from argument of row i towards argument of column j; – Sij = 0 if does not exist any path between argument of row i towards argu- ment of column j. Specifically, Sij ∈ Z < 0 means that: The Linear Algebra of Abstract Argumentation 5 – Sij = −1 if there exists only one path between the two nodes (i.e., an attack); – otherwise, Sij quantifies negatively how many attacks there are more than the defenses, if there exists more than one path between the two nodes. While, Sij ∈ Z > 0 indicates that: – Sij = 1 if there exists only one path between the two nodes (i.e., a defense); – otherwise, Sij quantifies positively how many defenses there are more than the attacks, if there exists more than one path between the two nodes. Roughly, the matrix SF represents a matrix version of justified and defeated arguments. We show that, under appropriate constraints, this matrix has many properties, which can be exploited to provide a way to select reasonable sub- blocks of this form (i.e., sets of arguments) among all the possible ones in order to determine not only the classical extension-based semantics, but also other new ranking-based semantics. 3 The Justification Matrix The strategy to handle the evaluation process with the matrix SF is subject to a constraint: we have to ensure that before the computation of the power series of the Argumentation Matrix, there must not exist non-zero entries on the main diagonal. We may have this configuration in two cases: 1. there exist self-loops (i.e., self-attacking arguments); 2. there exist initializers, i.e., arguments that do not receive any attack. The purpose is to correctly evaluate arguments in a matrix standard form. Taking into account also self-loops in the power series computation of the Argu- mentation Matrix, will lead to unreliable results, since the path walk transition would declare a self-attacking argument as justified when the power of the Ar- gumentation Matrix has an even exponent. Then, we choose to momentarily subtract from the starting Argumentation Matrix MF the main diagonal, which we call diags (MF ). In this way, we avoid the problem of self-loops. Definition 5 Let F = hA, Ri be an acyclic AF, MF be the Argumentation Matrix of F and diags (MF ) the main diagonal of MF . The Argumentation Walk Matrix is the resulting matrix WF = MF − diags (MF ) without non-zero entries on the main diagonal. With WF we avoid self-loops in the Argumentation Matrix. Then, the process of power series computation and summation to determine the matrix SF always converge to stationary point in which, for a n ∈ N > 0, the Argumentation Walk Matrix raised to the power of n will result 0. Once the Summation Matrix SF is achieved, we hold an argumentation matrix representation in which each node is compared with each other. If there were self-loops in the starting Argumentation Matrix, they are then re-added to the Summation Matrix in order to assess the 6 A. Pazienza et al. acceptability of arguments, then we need to add the previously omitted main diagonal diags (MF ) with self-loops. The last thing that we have to take on aboard, is that initializer arguments are “justified” by default in the process of evaluation of a semantics and play a key role in the arguments’ evaluation process. Then, we define another diagonal matrix with a positive value of 1 for each initializer argument, which we call diagu (MF ). The resulting matrix collects all the information useful to evaluate the acceptability of arguments, and it is called Justification Matrix. Definition 6 Let F = hA, Ri be an acyclic AF, MF be the Argumentation Ma- trix of F , diags (MF ) the main diagonal of MF with self-loops, and diagu (MF ) a diagonal matrix of MF with the entry MF ii = 1 for initializer arguments. Given the Argumentation Walk Matrix WF = MF − diags (MF ), and k ∈ N > 0 such that WFk+1 = 0, then the Summation Matrix SF = WF + WF2 + . . . + WFk . The Justification Matrix is the resulting matrix JF = SF + diags (MF ) + diagu (MF ). Once the Justification Matrix JF is obtained, we can exploit its algebraic properties in order to evaluate the acceptability of arguments. We have now a particular representation of the argumentation graph in which all the evaluations of attacks and defenses are made explicit. An entry Jij is thus the accumulated sum of paths between argument i and argument j where paths of odd length contribute negatively and paths of even length contribute positively. In this representation, the j th column in JF gives an overview on how argument j is assessed by all arguments in the framework. With the Justification Matrix we can now extract different sub-blocks of it in the same way in which the extension- based semantics are extracted. 3.1 Power Series Stop Criterion: How to Handle Cycles It is worth to clarify how the power series summation procedure stops. We en- vision this procedure as an iterative process that converges to a fixed point. It comes out that for acyclic AFs the problem of power series stop criterion is trivial, since it is pretty easy to check for that k > 0 such that its Argumen- tation Matrix representation WFk+1 = 0. In this respect, k indicates the length of longest directed path, which it has a linear time solution for directed acyclic graphs. Hence, we get a fixed point that stops our algorithm. It is indeed a nec- essary (but not sufficient) condition that, in order for WFk to converge, the i, j P entry of the matrix power WFk must converge to zero as k → ∞. In the matter of converging matrices, it is significantly easier to consider a submultiplicative ma- trix norm. A particularly nice norm of this type is the Frobenius norm. P What we can say then is that a necessary condition for the convergence of WFk is that ||WFk || → 0 as k → ∞.PA more impressive result is that a sufficient condition for the convergence of WFk is that ||WFk || < 1. The problem comes with cyclic graphs. Considering an argumentation graph that contains cycles, one has to determine a stop criterion to correctly evaluate The Linear Algebra of Abstract Argumentation 7 arguments, otherwise the power series computation would not terminate. More- over, in contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP- hard, meaning that it cannot be solved in polynomial time for arbitrary cyclic graphs. One has therefore to determine a cut-off point for the computation of the Justification Matrix, which in our case we set to be the diameter of a graph, which formally is the greatest distance between any pair of nodes, i.e., the length of the longest shortest path between any two nodes in the graph. To find the di- ameter of a graph, first find the shortest path between each pair of nodes. The greatest length of any of these paths is the diameter of the graph. In this context, if the diameter is k ∈ N > 0, it is enough to show that MF0 , MF , MF2 , . . . , MFk are linearly independent. Therefore, in cyclic argumentation graphs, it suffices to compute the diameter of the AF to ensure that the Justification Matrix would compare each node to any other. Example 2. In Example 1 there exist a self-loop for node  and there is an initializer argument α. Hence, it is necessary to subtract the diagonal matrix diags (MF1 ) from MF1 . Since there is also a cycle in F (γ attacks δ and vice versa), we set as exponent of the last Argumentation Walk Matrix to raise the diameter of F , which is 2. Then, it suffices to raise the matrix WF1 to the power of 2. We can now calculate the Justification matrix by re-adding the diagonal matrix diags (MF1 ) for self-loops and by adding the diagonal matrix diagu (MF1 ) for initializer argument. Below, WF1 is the resulting Argumentation Walk Matrix, WF21 is its 2nd power, SF1 is the related Summation Matrix, and JF1 is the resulting Justification Matrix.    0 −1 0 0 0  0 −1 0 0 0 0 0 0 0 0  0 0 0 0 0    0 −1 1 −1 1  SF1 =    0 −1 0 −1 0  WF1 =    0 0 −1 0 −1 0 1 −1 1 −1 0 0 0 0 0 0 0 0 0 0     00000 1 −1 0 0 0 0 0 0 0 0  0 0 0 0 0  WF21 =      0 0 1 0 1  0 −1 1 −1 1  JF1 =    0 1 0 1 0  0 1 −1 1 −1 00000 0 0 0 0 −1 4 Characterizing Extension-based Semantics By Definition 6, the matrix JF contains all the information of the AF F . In this section, we mainly focus on finding the characterization of various extensions in the matrix JF of F . The idea is to establish the relation between the extensions of F and the sub-blocks of JF . Formally, we have first to define the sub-block of a matrix. Definition 7 Let A ∈ Rn×n be a square matrix. A sub-block matrix (or parti- tioned matrix) is a matrix B ∈ Rk×k , with k ≤ n whose arrays of elements 8 A. Pazienza et al. are belonging to (not necessarily consecutive) rows i1 , i2 , . . . , ik and columns j1 , j2 , . . . , jk of A. 4.1 Characterizing the Grounded Extension Since the j th column in JF gives an overview on how argument j is assessed by all arguments in the framework, it is sufficient to sum the entries in each column and check whether the resulting value is ≥ 1. In fact, having a column sum strictly positive would mean that the argument in column j is fully justified in the framework, and thus would be a member of the Grounded Extension. For the Grounded Semantics, we consider as sub-block of the Justification Matrix the whole matrix itself, since the Grounded Extension is a single-status semantics, and would at least be the empty set. Axiom 1 Let F = hA, Ri be an AF, with |A| = n, and JF be the n × n Justifi- cation Matrix of F . If cs(JF )1×n is the resulting array of JF column-wise sum, then the Grounded Extension of F consists of the ith elements of cs(JF ) with cs(JF )i ≥ 1, unless there is a negative entry in the corresponding columns of JF . If none of the array elements satisfies this requirement, then the Grounded Extension of F = {∅}. Example 3. In Example 2 the Justification Matrix of F1 is the following:   1 −1 0 0 0 0 0 0 0 0    0 −1 1 −1 1  JF1 =   0 1 −1 1 −1 0 0 0 0 −1 Let’s consider the sum of the entries for each column:   cs(JF1 ) = 1 −1 0 0 −1 The only justified argument, with the corresponding column sum ≥ 1 is {{α}}, which indeed is the Grounded Extension gr(F1 ). Another interesting interpretation of the array cs(JF ) is that for each argument it is possible to evaluate how much it is defended or defeated. In this sense, we go beyond the classical accepted/rejected evaluations, and we can therefore exhibit a ranking-based evaluation of arguments. 4.2 Characterizing Conflict-free Subsets The first basic requirement for any extension is the conflict-free principle, i.e., if an argument i attacks another argument j then they can not be included together in an extension. So, we present the matrix condition which ensures that a subset of an AF is conflict-free. Axiom 2 Let F = hA, Ri be an AF, with |A| = n, and JF be the n × n Justifi- cation Matrix of F . The k ×k matrix CF , with k ≤ n, is a sub-block conflict-free matrix of F iff each entry [CF ij ] ≥ 0. The Linear Algebra of Abstract Argumentation 9 4.3 Characterizing the Admissible Subsets To determine the admissibility of a given subset of arguments, we start by col- lecting all the conflict-free sub-blocks of the Justification Matrix and check for those sub-blocks whose entries hold non-negative values. Axiom 3 Let F = hA, Ri be an AF, with |A| = n, and JF be the n × n Justi- fication Matrix of F . The k × k sub-block conflict-free matrix DF , with k ≤ n, is a sub-block admissible matrix of F iff the sum of each row [DF i ] > 0 and the sum of each column [DF j ] > 0. Example 4. Given the AF F1 in Example 1 and the Justification Matrix JF1 in Example 2, we report all the conflict-free sub-blocks of JF1 : conflict-free subset { } {α} {β} {γ} {δ} {α,  γ} {α,  δ} {β,  δ}         10 10 00 sub-block [] 1 0 1 1 01 01 11 The admissible sets are the following: {{}, {α}, {γ}, {δ}, {α, γ}, {α, δ}}. As we can see, the corresponding sub-blocks of each subset have rows sum and columns sum > 0. 4.4 Characterizing the Stable Extensions Every stable extension S ⊆ A, if it exists, separates the set of arguments A into two disjoint parts: S and A \ S. So, except for the conflict-freeness of S, we only need to concentrate on whether the arguments in A\S are attacked by S. Hence, for each conflict-free sub-block matrix, we need to consider the remaining outer sub-block of the Justification Matrix, containing information about the external arguments. If there exists at least a negative entry in each column of the outer sub-block, then the conflict-free sub-block matrix is a stable sub-block. Axiom 4 Let F = hA, Ri be an AF, with |A| = n, and JF be the n × n Jus- tification Matrix of F . The k × k sub-block conflict-free matrix EF , with k ≤ n and l = n − k is a sub-block stable matrix of F iff its corresponding outer k × l sub-block matrix contains at least one negative entry in each column. Example 5. Given the AF F1 in Example 1 and the Justification Matrix JF1 in Example 2, we report all the conflict-free sub-blocks of JF1 together with its outer sub-blocks divided by a line, obtaining a k × n sub-block: conflict-free subset { }  {α}   {β}   {γ}  {δ}  sub-block [ ] 1 −1 0 0 0 00000 1 0 −1 −1 1 1 0 1 −1 −1 conflict-free subset  {α, γ}  {α, δ}  {β, δ}  1 0 −1 0 0 1 0 −1 0 0 000 0 0 sub-block 0 1 −1 −1 1 0 1 1 −1 −1 1 1 0 −1 −1 10 A. Pazienza et al. The only stable extension is {{α, δ}}. As we can see, the corresponding outer sub-blocks of the sub-block for {α, δ} holds at least one negative entry for each column. 5 Characterizing BAFs In the following, we show that also a BAF can be mapped to a particular ma- trix representation. The intuition of representing attacks as a negative relation remains of actual interest, and finds its counterpart in supports, which can be represented as a “positive” relation. Definition 8 Let B = hA, Ratt , Rsup i be a BAF. Let |A| = n, then the Signed Argumentation Matrix of B is a n × n matrix MB = [Mij ] such that for any two arguments αi , αj ∈ A it holds that  −1 if hαi , αj i ∈ Ratt  Mij = 1 if hαi , αj i ∈ Rsup  0 otherwise  It is straightforward to note that the Justification Matrix of MB (with the power series stop criterion) is still a valid representation to compute sub-blocks which ensure BAF conflict-freeness, admissibility, and stable semantics requirements. Anyway, it is worth mentioning that there are different interpretation of the support in BAFs that can lead to alternative semantics for which the approach proposed may not work. 6 Characterizing WAFs Taking into account WAFs, we redefine the Argumentation Matrix to have the positive weights as its entries. Definition 9 Let W = hA, R, wi be a WAF, with |A| = n. Then, the Weighted Argumentation Matrix of W is a n × n matrix MW = [Mij ] such that for any two arguments αi , αj ∈ A it holds that ( w(hαi , αj i) if hαi , αj i ∈ R Mij = 0 otherwise In this representation, we choose to set positive weights as entries of the Weighted Argumentation Matrix instead of negative ones. In WAFs weights are not propagated to determine a level of acceptability for arguments, but they are only used for deciding which attacks can be ignored when computing the extensions. This means that we don’t need a Justification Matrix of MW . Some inconsistencies are tolerated in subsets of arguments, provided that the sum of the weights of attacks between arguments does not exceed a given inconsistency threshold β ∈ R+ [7]. Therefore, depending on the inconsistency threshold, we can delete all the column entries in which their column sum exceeds β. The Linear Algebra of Abstract Argumentation 11 α1 α7 5 5 1 5 5 α3 α4 α5 α6 5 5 2 α2 α8 Fig. 2. W1 : WAF example Definition 10 Let W = hA, R, wi be a WAF, with |A| = n, MW = [Mij ] be the Weighted Argumentation Matrix of W , and β ∈ R+ be an inconsistency threshold. Then, the β-consistent Argumentation Matrix of MW is a n × n matrix MW,β = [Mij,β ] such that for any entry Mij of MW it holds that ( Pn −1 if k=1 Mkj < β Mij,β = 0 otherwise The β-consistent Argumentation Matrix is a matrix representation of the WAF in which all the attacks exceeding the inconsistency threshold are ne- glected. This resulting matrix is now in the standard form such that its Jus- tification Matrix representation can now be computed. Admissibility is defined in the standard way, and standard semantics are considered leading to various notions of β-extensions which echo Dung’s ones. Then, it will be still possible to compute sub-blocks of such matrix according to semantics defined above, that will correspond to β-admissible, β-grounded, β-stable subsets of arguments. Example 6. Consider the WAF W1 in Figure 2. Below, MW1 is its matrix rep- resentation Let β = 3, then MW1 ,β is the corresponding β-consistent Argumen- tation Matrix.     00000000 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0     5 5 0 0 0 0 0 0 −1 −1 0 0 0 0 0 0      0 0 5 0 1 0 0 0  0 0 −1 0 0 0 0 0  M W1 =    MW1 ,β =    0 0 0 2 0 5 0 0  0 0 0 0 0 −1 0 0    0 0 0 0 0 0 5 5  0 0 0 0 0 0 −1 −1     0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 00000000 0 0 0 00 0 0 0 7 Characterizing BWAFs Let’s now consider the Argumentation Matrix representation for the BWAF. A BWAF is a further generalization of the Dung’s AF, in which new features are introduced to deal with bipolar weighted relations [9]: negative attacks and positive supports, bounded in a specific interval. 12 A. Pazienza et al. 0.4 0.6 α β γ −0.7 −0.5 0.3  δ Fig. 3. G2 : Example to illustrate BWAF Definition 11 A BWAF is a triplet G = hA, R̂, wR̂ i, where A is a finite set of arguments, R̂ ⊆ A × A and wR̂ : R̂ 7→ [−1, 0[ ∪ ]0, 1] is a function assign- ing a weight to each relation. Attack relations are defined as R̂att = {hα, βi ∈ R̂ | wR̂ (hα, βi) ∈ [−1, 0[ } and support relations as R̂sup = {hα, βi ∈ R̂ | wR̂ (hα, βi) ∈ ]0, 1] }. Given two arguments α, β ∈ A and a path hα, x1 , x2 , . . . , xn , βi from α to- wards β, then: – α bw-defends β if the product of weights wR̂ (hα, x1 i) · wR̂ (hx1 , x2 i) · . . . · wR̂ (hxn , βi) is positive. – α bw-attacks β if the product of weights wR̂ (hα, x1 i) · wR̂ (hx1 , x2 i) · . . . · wR̂ (hxn , βi) is negative. If we have positive and negative weights on the edges, then the assumptions made for representing AFs, BAFs and WAFs as adjacency matrices are still valid. Taking into account BWAFs, we redefine the Argumentation Matrix to have the negative and positive weights as its entries. Definition 12 Let G = hA, R̂, wR̂ i be a BWAF with weights in the interval [−1, 0[∪]0, 1], and |A| = n. Then, the Signed Weighted Argumentation Matrix of G is a n × n matrix MG = [Mij ] such that for any two arguments αi , αj ∈ A it holds that ( wR̂ (hαi , αj i) if hαi , αj i ∈ R̂ Mij = 0 otherwise We define the weight of a walk as the product of the weights of the arcs. Then if we want to know the total sum of weights of i, j paths of given length, that is the entry in the appropriate power. Example 7. Consider the BWAF G2 depicted in Figure 3. Below, MG2 is its matrix representation. We can compute its Justification Matrix JG2 with the 2 power series summation of MG2 . Below, MG 2 is the he 2nd power of G2 . Since 3 there is no path of length 3 in G2 , MG 2 is the zero matrix. Arguments α and δ are initializers, so the diagonal matrix diagu (MG2 ) will have positive values of 1 in the corresponding entries. Then, JG2 is its resulting Justification Matrix. The Linear Algebra of Abstract Argumentation 13       0 0.4 0 0 −0.7 0 0 0.24 0 0 1 0.4 0.24 0 −0.7 0 0 0.6 0 0  0 0 0 0 0 0 0 0.6 0 0  2       0 0 MG2 =  0 0 0  MG 0 0 0 0 0 = 0 0 JG2 =  0 0 0    2  0 0 −0.5 0 0.3  0 0 0 0 0 0 0 −0.5 1 0.3  0 0 0 0 0 00 0 00 0 0 0 0 0 We can now exploit this resulting matrix to compute semantics. For instance, the set of arguments with the corresponding column sum of entries ≥ 1 of JG2 is the (bw-)grounded extension. 7.1 Laplacian Ranking Semantics for BWAFs The spectral graph theory studies the properties of graphs via the eigenvalues and eigenvectors of their associated graph matrices: the adjacency matrix and the graph Laplacian and its variants. In the following we consider the possible bene- fits of adopting spectral linear algebra methods as a tool for analyzing argumen- tation structures, as [3] first started to study, and present a new ranking-based semantics, called Laplacian ranking semantics. With the justification matrix in place, we can provide the main definition: ? Definition 13 Let G = hA, R̂, wR̂ i be a BWAF, with |A| = n, and let JG be the Justification Matrix of G without positive values for initializers in the main di- agonal. The degree matrix of G is the matrix DG = diag(deg(α1 ), . . . , deg(an )), where α1 , . . . , αn ∈ A, and ∀j = 1, . . . , n : n X ? deg(αj ) = JGij i=1 Intuitively, the degree matrix of a BWAF is a diagonal matrix which contains information about the sum of weights of the edges connected to a node. The name ‘Laplacian Ranking Semantics’ derives from the fact that, in graph theory, the ? Laplacian matrix LG of a graph G is given by the difference DG − JG . In yet other words, the degree matrix DG collects in the main diagonal the column-wise sum of its entries. Hence, we argue, it captures natural information to compare the relative ‘strength’ of arguments in a BWAF, since its Justification Matrix collects all the attacks and defenses for each node in the graph. So we assign an ‘acceptability’ degree to each argument in a BWAF G, which equals its degree in DG . It follows that the degree of an argument always lies in the interval [−1, 1], so that the ranking of 0 will now tip the scales, meaning that rejected arguments will have a negative ranking, while accepted ones will have a positive ranking. Naturally, such degrees induce a total preorder, for each BWAF G and α, β ∈ A: α deg G β iff deg(α) ≥ deg(β). It is worth to clarify why we do not consider the weight of initializer ar- guments in this setting. Generally, arguments that not receive any attack or 14 A. Pazienza et al. support play a key role in the (classical) acceptability. Dealing with Laplacian matrix, we want to ensure that the algebraic properties about its eigenvalues, eigenvectors and connectivity are always satisfied. Furthermore, it will be of par- ticular interest to verify which ranking semantics properties such new semantics will hold, considering also the particular case of weighted attacks and weighted supports. In [1] several rationality postulates have been proposed which should be satisfied by any argumentation semantics based on ranking. We are now in a position to check which of the rationality postulates are satisfied, assuming that those postulates, suitably designed for AFs, are extended in the BWAF case, by considering simple attacks as bw-attacks (which include weighted notions of supported attack and indirect attack), and defenses as bw-defenses (which include a weighted notion of support and defense as a whole). Axiom 5 The Laplacian ranking semantics satisfies Independence, Void Pre- cedence, Self Contradiction, Cardinality Precedence, Quality Precedence, Defense Precedence, Distributed-Defense Precedence, Strict Addition of Defense Branch, Addition of Defense Branch, Addition of Attack Branch, Total, Non-attacked Equivalence, and Attack vs Full Defense. Other properties are not satisfied. The proof of the above theorem is omitted due to space limitations but straightforward. For a detailed discussion of these postulates see [1]. Briefly, we state that Abstraction, Counter-transitivity, Strict Counter-transitivity, Increase of Attack Branch, and Increase of Defense Branch are not satisfied by our se- mantics: Abstraction is not satisfied because it relies only on attacks between argument, while in our semantics we have to deal with supports too; Counter- transitivity, and its strict form, are not satisfied because it does not matter how many bw-attacks a node can receive, Laplacian-ranking semantics accounts for the strength of bw-attackers, not for the quantity, and it may happen that an argument α, receiving more bw-attackers than the ones received by β, would be at least acceptable as β ; Increase of Attack Branch is not satisfied because in- creasing the length of a bw-attacker of an argument does not improve its ranking. The same observation holds for Increase of Defense Branch property. Example 8. Let us consider the BWAF G2 depicted in Figure 3. The Laplacian matrix of G2 is LG2 . In particular, the degree matrix of G2 is DG2 .     0 −0.4 −0.24 0 0.7 0 0 0 0 0 0 0.4 −0.6 0 0  0 0.4 0 0 0      0 0 L G2 =  0.34 0 0  0 0 0.34 0 0  DG2 =    0 0 0.5 0 −0.3 0 0 0 0 0  0 0 0 0 −0.4 0 0 0 0 −0.4 where deg(α) = 0, deg(β) = 0.4, deg(γ) = 0.34, deg(δ) = 0, deg() = −0.4. Therefore, the Laplacian Ranking Semantics of G2 is: β deg deg deg deg G2 γ G2 α G2 δ G2 . The Linear Algebra of Abstract Argumentation 15 8 Conclusion An alternative representation of computational models of argument, based on the Matrix Theory, has been proposed. This line of research have demonstrated that it is possible to represent and evaluate arguments by devising a general strategy which led to the definition of the Justification Matrix. In this way, the computation of semantics relies no more on rules, but only on matrices products. The potential of the algebraic approach has been demonstrated to devise a new ranking-based semantics, i.e. the Laplacian semantics, which naturally satisfies a lot of well-known postulates of ranking semantics literature. The matrix-approach may have some potential in efficiently processing ab- stract AFs since finding extensions can be a computationally hard procedure especially when we are dealing with several arguments and (complex) relations. Therefore, further developments on this field will be devoted to the characteriza- tion of other extension-based semantics and on the new perspectives that Linear Algebra opens on ranking semantics, with a deeper understanding of the prop- erties that the Laplacian matrix representation of an Argument Graph holds. References 1. Amgoud, L., Ben-Naim, J.: Ranking-based semantics for argumentation frame- works. In: SUM. pp. 134–147. Springer (2013) 2. Bistarelli, S., Tappini, A., Taticchi, C.: A matrix approach for weighted argumen- tation frameworks. In: Proceedings of FLAIRS 2018. pp. 507–512 (2018) 3. Butterworth, J., Dunne, P.E.: Spectral techniques in argumentation framework analysis. In: COMMA. pp. 167–178 (2016) 4. Cayrol, C., Lagasquie-Schiex, M.: On the acceptability of arguments in bipolar argumentation frameworks. In: ECSQARU. vol. 3571, pp. 378–389 (2005) 5. Corea, C., Thimm, M.: Using matrix exponentials for abstract argumentation. In: SAFA @ COMMA. pp. 10–21 (2016) 6. Dung, P.M.: On the acceptability of arguments and its fundamental role in non- monotonic reasoning, logic programming and n-person games. Artificial intelligence 77(2), 321–357 (1995) 7. Dunne, P.E., Hunter, A., McBurney, P., Parsons, S., Wooldridge, M.: Weighted argument systems: Basic definitions, algorithms, and complexity results. Artificial Intelligence 175(2), 457 – 486 (2011) 8. Hadjisoteriou, E.: Computing argumentation with matrices. In: ICCSW 2015. vol. 49, pp. 29–36. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015) 9. Pazienza, A., Ferilli, S., Esposito, F.: Constructing and evaluating bipolar weighted argumentation frameworks for online debating systems. In: Proceedings of the 1st Workshop on Advances In Argumentation In Artificial Intelligence, AIˆ3 2017 @ AI*IA 2017. pp. 111–125 (2017) 10. Pazienza, A., Ferilli, S., Esposito, F.: On the gradual acceptability of arguments in bipolar weighted argumentation frameworks with degrees of trust. In: Foundations of Intelligent Systems - 23rd International Symposium, ISMIS. pp. 195–204 (2017) 11. Pu, F., Luo, G., Chen, Y.: Boolean matrix approach for abstract argumentation. In: Multi-Agent Systems and Agreement Technologies, pp. 470–480. Springer (2016) 12. Xu, Y., Cayrol, C.: The matrix approach for abstract argumentation frameworks. In: TAFA @ IJCAI. pp. 243–259. Springer (2015)