approach for determining whether a set of arguments is an extension. This di ers
in the fact that it does not use matrix sub-blocks but it creates sets of arguments
in a matrix representation to de ne tests for the di erent argumentation
semantics as they do not try to nd all arguments passing a given criteria. In [
While, in [
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 e cient techniques for computing extensions. Moreover, well-established techniques for the incremental computation of matrix-product could be pro tably used to address the incremental computation of extensions in dynamic AFs. Starting with tools coming from Linear Algebra, we show that it is possible to give a uniform (matrix-based) representation 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 de nes the problem of developing a nal matrix which is able to represent all the defeats and defenses between arguments, Section 4 describes the ability to nd 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 eld of Linear Algebra, that gives insights on some interesting properties. Finally, Section 8 concludes the paper. 2
Let us start by providing the basics of Abstract Argumentation.
De nition 1 An AF is a pair F = hA; Ri, where A is a nite set of arguments
and R A A. Given ; 2 A, the relation R means that attacks .
An argumentation semantics is the formal de nition of a method ruling the
argument evaluation process. The most basic concepts shared by all argumentation
semantics in the literature are con ict-freeness and defense. Then, standard
acceptability semantics, introduced by Dung [
De nition 2 Let F = hA; Ri be an AF, and S A: { S is con ict-free ( cf for short) if @ ; 2 S s.t. R ; { 2 A is defended by S if 8 2 A : R ) 9 2 S s.t. R ; { fF : 2A 7! 2A s.t. fF (S) = f j is defended by Sg is called the characteristic function of F ; { S is admissible if S is cf and S is defended by itself, i.e. 8 2 S; 8 2
A : R ) 9 2 S s.t. R .
{ S is a grounded extension if S is the admissible least xed point of fF ;
{ S is a stable extension if S is cf and 8 2 A; 2= S; 9 2 S s.t. R .
Regarding the generalizations of Dung's AF, we recall the following frameworks.
A Bipolar AF (BAF ) [
An argumentation graph can be represented with a slightly di erent version of its adjacency matrix.
De nition 3 Let F = hA; Ri be an AF. Let jAj = n, then the Argumentation Matrix of F is a n n matrix MF = [Mij ] such that for any two arguments i; j 2 A it holds that
Mij = ( 0 1 if h i; j i 2 R
otherwise
The substantial di erence from [
0 0 0 0 1 In the Argumentation Matrix, each row i represents the attacks launched towards the jth 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 concept 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 computing 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 de nition 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. De nition 4 Let F = hA; Ri be an acyclic AF, k 2 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 M Fi , with i = 1; : : : ; k, called Summation Matrix, and contains entries [Sij ] of three types: { Sij 2 Z < 0, indicating that there is an overall (indirect) attack from argument of row i towards argument of column j; { Sij 2 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 argument of column j.
{ Sij = 1 if there exists only one path between the two nodes (i.e., an attack); { otherwise, Sij quanti es negatively how many attacks there are more than the defenses, if there exists more than one path between the two nodes.
{ Sij = 1 if there exists only one path between the two nodes (i.e., a defense); { otherwise, Sij quanti es 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 justi ed 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 subblocks 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 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 con guration 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 Argumentation Matrix, will lead to unreliable results, since the path walk transition would declare a self-attacking argument as justi ed when the power of the Argumentation 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. De nition 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 2 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 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 \justi ed" by default in the process of evaluation of a semantics and play a key role in the arguments' evaluation process. Then, we de ne 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 Justi cation Matrix. De nition 6 Let F = hA; Ri be an acyclic AF, MF be the Argumentation Matrix 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 2 N > 0 such that WFk+1 = 0, then the Summation Matrix SF = WF + WF2 + : : : + WFk . The Justi cation Matrix is the resulting matrix
JF = SF + diags(MF ) + diagu(MF ):
Once the Justi cation 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 jth column in JF gives an overview on how argument j is assessed by all arguments in the framework. With the Justi cation Matrix we can now extract di erent sub-blocks of it in the same way in which the extensionbased semantics are extracted. 3.1
It is worth to clarify how the power series summation procedure stops. We envision this procedure as an iterative process that converges to a xed 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 Argumentation 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 xed point that stops our algorithm. It is indeed a necessary (but not su cient) condition that, in order for P WFk to converge, the i; j entry of the matrix power WFk must converge to zero as k ! 1. In the matter of converging matrices, it is signi cantly easier to consider a submultiplicative matrix norm. A particularly nice norm of this type is the Frobenius norm. What we can say then is that a necessary condition for the convergence of P WFk is that jjWFk jj ! 0 as k ! 1. A more impressive result is that a su cient condition for the convergence of P WFk is that jjWFk jj < 1.
The problem comes with cyclic graphs. Considering an argumentation graph that contains cycles, one has to determine a stop criterion to correctly evaluate arguments, otherwise the power series computation would not terminate. Moreover, 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 NPhard, meaning that it cannot be solved in polynomial time for arbitrary cyclic graphs. One has therefore to determine a cut-o point for the computation of the Justi cation 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 nd the diameter of a graph, rst nd 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 2 N > 0, it is enough to show that MF0 ; MF ; MF2 ; : : : ; MFk are linearly independent. Therefore, in cyclic argumentation graphs, it su ces to compute the diameter of the AF to ensure that the Justi cation 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 su ces to raise the matrix WF1 to the power of 2. We can now calculate the Justi cation 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 Justi cation Matrix.
20 1 0 0 0 3 20 1 0 0 0 3 60 0 0 0 0 7 60 0 0 0 0 7 WF1 = 660 1 0 1 0 77 SF1 = 660 1 1 1 1 77 640 0 1 0 157 640 1 1 1 157 0 0 0 0 0 0 0 0 0 0 20 0 0 0 03 60 0 0 0 07 WF21 = 660 0 1 0 177 640 1 0 1 057 0 0 0 0 0 By De nition 6, the matrix JF contains all the information of the AF F . In this section, we mainly focus on nding 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 rst to de ne the sub-block of a matrix.
De nition 7 Let A 2 Rn n be a square matrix. A sub-block matrix (or partitioned matrix) is a matrix B 2 Rk k, with k n whose arrays of elements are belonging to (not necessarily consecutive) rows i1; i2; : : : ; ik and columns j1; j2; : : : ; jk of A. 4.1
Since the jth column in JF gives an overview on how argument j is assessed by all arguments in the framework, it is su cient 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 justi ed in the framework, and thus would be a member of the Grounded Extension. For the Grounded Semantics, we consider as sub-block of the Justi cation 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 jAj = n, and JF be the n n Justi 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 satis es this requirement, then the Grounded Extension of F = f;g.
Example 3. In Example 2 the Justi cation Matrix of F1 is the following: Let's consider the sum of the entries for each column: The only justi ed argument, with the corresponding column sum which indeed is the Grounded Extension gr(F1). 1 is ff gg, 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
The rst basic requirement for any extension is the con ict-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 con ict-free.
Axiom 2 Let F = hA; Ri be an AF, with jAj = n, and JF be the n n Justi cation Matrix of F . The k k matrix CF , with k n, is a sub-block con ict-free matrix of F i each entry [CF ij ] 0.
To determine the admissibility of a given subset of arguments, we start by collecting all the con ict-free sub-blocks of the Justi cation Matrix and check for those sub-blocks whose entries hold non-negative values.
Axiom 3 Let F = hA; Ri be an AF, with jAj = n, and JF be the n n Justication Matrix of F . The k k sub-block con ict-free matrix DF , with k n, is a sub-block admissible matrix of F i 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 Justi cation Matrix JF1 in Example 2, we report all the con ict-free sub-blocks of JF1 : The admissible sets are the following: ffg; f g; f g; f g; f ; g; f ; gg. As we can see, the corresponding sub-blocks of each subset have rows sum and columns sum > 0. Every stable extension S A, if it exists, separates the set of arguments A into two disjoint parts: S and A n S. So, except for the con ict-freeness of S, we only need to concentrate on whether the arguments in AnS are attacked by S. Hence, for each con ict-free sub-block matrix, we need to consider the remaining outer sub-block of the Justi cation 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 con ict-free sub-block matrix is a stable sub-block. Axiom 4 Let F = hA; Ri be an AF, with jAj = n, and JF be the n n Justi cation Matrix of F . The k k sub-block con ict-free matrix EF , with k n and l = n k is a sub-block stable matrix of F i 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 Justi cation Matrix JF1 in Example 2, we report all the con ict-free sub-blocks of JF1 together with its outer sub-blocks divided by a line, obtaining a k n sub-block: con ict-free subset f g sub-block [ ] 1 f g 1 0 0 0
The only stable extension is ff ; gg. As we can see, the corresponding outer sub-blocks of the sub-block for f ; g holds at least one negative entry for each column. 5
In the following, we show that also a BAF can be mapped to a particular matrix representation. The intuition of representing attacks as a negative relation remains of actual interest, and nds its counterpart in supports, which can be represented as a \positive" relation.
De nition 8 Let B = hA; Ratt; Rsupi be a BAF. Let jAj = n, then the Signed Argumentation Matrix of B is a n n matrix MB = [Mij ] such that for any two arguments i; j 2 A it holds that
Mij = 8 > <
1 >:0 1 if h i; j i 2 Ratt if h i; j i 2 Rsup otherwise It is straightforward to note that the Justi cation Matrix of MB (with the power series stop criterion) is still a valid representation to compute sub-blocks which ensure BAF con ict-freeness, admissibility, and stable semantics requirements. Anyway, it is worth mentioning that there are di erent interpretation of the support in BAFs that can lead to alternative semantics for which the approach proposed may not work. 6
Taking into account WAFs, we rede ne the Argumentation Matrix to have the positive weights as its entries.
De nition 9 Let W = hA; R; wi be a WAF, with jAj = n. Then, the Weighted Argumentation Matrix of W is a n n matrix MW = [Mij ] such that for any two arguments i; j 2 A it holds that
Mij = ( w(h i; j i) if h i; j i 2 R 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 Justi cation 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 2 R+ [
k=1 Mkj < 0 otherwise
The -consistent Argumentation Matrix is a matrix representation of the WAF in which all the attacks exceeding the inconsistency threshold are neglected. This resulting matrix is now in the standard form such that its Justi cation Matrix representation can now be computed. Admissibility is de ned 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 de ned 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 representation Let = 3, then MW1; is the corresponding -consistent Argumentation Matrix.
MW1 = 666600 00 50 02 10 05 00 007777 20 0 0 0 0 0 0 03 60 0 0 0 0 0 0 07 665 5 0 0 0 0 0 077 660 0 0 0 0 0 5 577 6 7 40 0 0 0 0 0 0 05 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 3 6 0 0 0 0 0 0 0 0 7 66 1 1 0 0 0 0 0 0 77 MW1; = 6666 00 00 0 0 0 1 0 0 77
1 0 0 0 0 0 77
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 [
0:6 0:7
0:5 0:3 De nition 11 A BWAF is a triplet G = hA; R^ ; wR^ i, where A is a nite set of arguments, R^ A A and wR^ : R^ 7! [ 1; 0[ [ ]0; 1] is a function assigning a weight to each relation. Attack relations are de ned as R^ att = fh ; i 2 R^ j wR^ (h ; i) 2 [ 1; 0[ g and support relations as R^ sup = fh ; i 2 R^ j wR^ (h ; i) 2 ]0; 1] g.
Given two arguments ; 2 A and a path h ; x1; x2; : : : ; xn; i from towards , then: { {
bw-defends if the product of weights wR^ (h ; x1i) wR^ (hx1; x2i) : : : wR^ (hxn; i) is positive.
bw-attacks if the product of weights wR^ (h ; x1i) wR^ (hx1; x2i) : : : 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 rede ne the Argumentation Matrix to have the negative and positive weights as its entries.
De nition 12 Let G = hA; R^ ; wR^ i be a BWAF with weights in the interval [ 1; 0[[]0; 1], and jAj = n. Then, the Signed Weighted Argumentation Matrix of G is a n n matrix MG = [Mij ] such that for any two arguments i; j 2 A it holds that
Mij = (
^ wR^ (h i; j i) if h i; j i 2 R 0 otherwise We de ne 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 Justi cation Matrix JG2 with the power series summation of MG2 . Below, M G22 is the he 2nd power of G2. Since there is no path of length 3 in G2, M G32 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 Justi cation Matrix. 20 0 0:24 0 03 60 0 0 0 07 M G22 = 660 0 0 0 077 640 0 0 0 057 0 0 0 0 0 21 0:4 0:24 0 0:73 60 0 0:6 0 0 7 JG2 = 660 0 0 0 0 77 640 0 0:5 1 0:3 57 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.
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
benets of adopting spectral linear algebra methods as a tool for analyzing
argumentation structures, as [
? 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 di erence DG J G?.
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 Justi cation 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 ; 2 A: deg G i deg( ) deg( ):
It is worth to clarify why we do not consider the weight of initializer arguments in this setting. Generally, arguments that not receive any attack or 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 satis ed. Furthermore, it will be of particular interest to verify which ranking semantics properties such new semantics will hold, considering also the particular case of weighted attacks and weighted supports.
In [
Axiom 5 The Laplacian ranking semantics satis es Independence, Void Precedence, 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 satis ed.
The proof of the above theorem is omitted due to space limitations but
straightforward. For a detailed discussion of these postulates see [
The matrix-approach may have some potential in e ciently processing abstract AFs since nding extensions can be a computationally hard procedure especially when we are dealing with several arguments and (complex) relations. Therefore, further developments on this eld will be devoted to the characterization of other extension-based semantics and on the new perspectives that Linear Algebra opens on ranking semantics, with a deeper understanding of the properties that the Laplacian matrix representation of an Argument Graph holds.