In the phase of evaluation of accepted arguments, one may nd that not all the arguments of discussion are essential when drawing conclusions. Especially when the cardinality of the set of arguments is high, the task of identifying the most relevant arguments of the whole discussion in huge Argument Systems through the analysis of its synthesis may favor better interpretability and may allow us to extract semantics that include the the strongest arguments. We propose a new matrix interpretation of argumentation graphs and exploit a matrix decomposition technique, i.e. the Singular Value Decomposition, in order to yield a synthetized argument system with only the most prominent arguments.
Dung's abstract argumentation frameworks (AFs) [
The Singular Value Decomposition (SVD) [
This paper is organized as follows. The next section addresses the problem of argument graph matrix representation and how to deal with SVD matrix factorization. A general procedure to rebuild the argument graph with the reconstructed matrix is then discussed. Section 3 shows its application to a real discussion from a Online Debating System. The last section concludes. 2
An argument graph can be represented with a slightly di erent version of its adiacency matrix. Given an Argumentation Framework F = hA; Ri, where A is a nite set of arguments and R A A, with jAj = n, we call Argumentation Matrix of F the n n matrix MF = [Mij ] such that for any two arguments i; j 2 A, the entry Mij = 1 i there is an attack from i towards j , otherwise the entry Mij = 0, meaning that there is no attack relation between arguments i and j . Under this assignment, the Argumentation Matrix can be thought as a representation of the Argumentation Framework.
This representation enables to establish links between extensions (under various semantics) of the AF and to explore new properties and techniques useful to abstract argumentation puroposes. Moreover, we can extend this representation also to generalizations of argumentation frameworks.
{ BAF: the entry Mij = 1 is added to represent the support relation; { WAF: instead of Mij = 1, the entry of the Argumentation Matrix has a value Mij = n, with n 2 R+, that corresponds to the weight of the attack relation between two arguments; { BWAF: entries of Argumentation Matrix have values Mij = w, with w 2 [ 1; 1] corresponding to the relative strength of relations between arguments.
Matrix decomposition allows us to deal with the problem of low-rank approximation. It is a minimization problem, in which the cost function measures the t between a given matrix and an approximating matrix, subject to a constraint that the approximating matrix has reduced rank. For this purpose, we exploit SVD. 2.1
Let A 2 Rm n be a matrix and p = min(m; n), the SVD of A is a factorization in the form A = U V T where U = (u1; : : : ; um) 2 Rm m and V = (v1; : : : ; vn) 2 Rn n are orthogonal, and 2 Rm n is a diagonal matrix with elements 1 2 : : : p 0. Each 1; : : : ; p is called singular value or principal component of A. They correspond to the square roots of A's eigenvalues.
The Eckart{Young theorem allows us to solve the problem of approximating a matrix A with another matrix A~, said truncated, which has a speci c rank k. If A is a matrix of rank r > 1, A = U V T is the corresponding SVD, and B = fB 2 Rm n : rank(B) kg 8k 2 f1; : : : ; r 1g, than for all A~ 2 B, where A~ = Uk kVkT = Pik=1 ai iviT , it holds that minB2B kA Bk2F = kA A~k2F = Pir=k+1 i2, i.e., the k-dimensional submatrix A~ of A represents the closest approximation of A between all the approximations of A with rank less than or equal to k, in Frobenius norm. In other words, the approximation is based on minimizing the Frobenius norm of the di erence between A and A~ under the constraint that rank(A~) = k. It turns out that the solution is given by the SVD of A, namely A~ = Uk kVkT = Pik=1 ui iviT where k is the same matrix as except that it contains only the k largest singular values (the other singular values are replaced by zero). 2.2
Given the Argumentation Matrix of the argumentation graph under consideration (i.e, AF, BAF, WAF, BWAF), its low-rank approximation with the truncated SVD, reduced with only the k largest principal components, will ensure that the reconstruction will be the best approximation, and at the same time will preserve the meaning of the discussion. The problem relies on how to select the number of principal components k to keep aboard. This is tackled with the Kaiser criterion, which de nes a rule to investigate the scree plot of matrix eigenvalues. It plots eigenvalues and looks for the \elbow": such a plot when read left-to-right across the abscissa can often show a clear separation in fraction of total variance where the 'most important' k components cease and the 'least important' components begin. The point of separation is often called the 'elbow'; the rest is \scree". Therefore, the number of components k that make up the \cli " are extracted.
Now, it is possible to reconstruct the reduced approximating matrix E 2 Rn n, where n is the number of nodes of the argumentation graph, considering only its k largest principal components. Depending on the considered argumentation graph (i.e., AF, BAF, WAF, BWAF), the approximation of the corresponding reconstructed Argumentation Matrix must satisfy speci c constraints, for which this matrix must be revised otherwise.
Let a; b be two arguments, then there is: { AF: an attack relation between them i Eab > 0:5; { BAF: an attack relation or a support relation between them i , respectively
Eab 0:5 or Eab 0:5, otherwise any relation is built; { WAF: an attack relation between them i Eab > 0 where its weight is given by approximating the value Eab to the nearest integer number; { BWAF: an attack relation or a support relation between them with weight value equal to Eab with bounds 1 or 1 i , respectively, 1 < Eab < 0 or 0 < Eab < 1.
The reconstructed argumentation graph will yield only the strongest arguments, depending on the relations survived from the operation of the SVD dimensionality reduction. In fact, we expect that this operation will delete the weakest relations from the argument graph. Then, the arguments no longer engaged in the discussion will be excluded, giving rise to a synthetized version of the Argument System. We call such a graph Principal Argument System, which can be referred to a Principal AF (P -AF), as well as to a Principal BAF (P -BAF), Principal WAF (P -WAF), and Principal BWAF (P -BWAF). 3
In order to show the validity of such an approach in real cases, we considered a Reddit discussion of an episode of popular TV series (http://bit.ly/2fQxq4I) divided into several arguments with attacks and supports. The produced BWAF is made up of 70 arguments and 69 weighted relations, of which 52 attacks and 17 supports. The corresponding graph is reported in Figure 1.
a21 -0.45 a78
a58
The synthetized version of the BWAF, i.e. the P -BWAF, is obtained using SVD. According to the Kaiser criterion, we reconstructed the new argument system with 25 principal components. The Principal BWAF has now 59 arguments involved in at least one relation and 58 weighted relations, of which 44 attacks and 14 supports. The corresponding graph is reported in Figure 2.
The rst observation about the new synthetized P -BWAF is that the global meaning of the discussion has been preserved. The strongest relations continue to exist in the revised P -BWAF while the weakest relations have been pruned. In particular, the following relations have been removed: 1. support from a49 towards a48 with strength 0:05; 2. attack from a59 towards a58 with strength 0:12; 3. attack from a60 towards a58 with strength 0:12; 4. attack from a75 towards a74 with strength 0:1; 5. attack from a78 towards a74 with strength 0:08; 6. attack from a80 towards a74 with strength 0:1.
From a qualitative analysis, it appears that the SVD has removed the lowest weight relations, in absolute terms, to 0:12. In particular, it has been removed about the 67% of relations with weight less than 0:12 for the starting graph. Interestingly, the SVD removed only the \peripheral" relations, i.e., those relations coming from nodes receiving no relation. This opens a new perspective about the evaluation of arguments in abstract argumentation: it turns out that sometimes, the unattacked/unsupported arguments may not be considered as winning (i.e., justi ed) ones, especially when the strength of their attack, or support, is extremely weak. Another interesting e ect of the SVD is that even some subgraphs may have been removed. In our case, two subgraphs have been removed: a63 a62 -0.16 -0.16 a61 0.32 a60 a75 -0.42 a76
This behaviour suggests a possible strategy to determine the ideal inconsistency budget for WAFs and BWAFs, in order to establish a level of tolerance of the inconsistency with minimal loss of information that does not change the conclusions from those of the starting argumentation framework. 4
This paper propose to exploit the SVD of an argument graph to extract its syntethized version in order to highlight only the relevant arguments involved in a discussion. This approach con rms the preservation of the meaning of the whole discussion while discarding the less relevant arguments. We showed its application to a real web-based debate and discussed its e ectiveness on the removed arguments and relations.
In terms of future work on this avenue of research, it would be of main interest to assess how the dimension reduction works with respect to the notion of extension-based semantics. Having introduced the basic framework of Principal Argument Systems, some important open issues arise, such as how extensionbased semantics are a ected by reduction, or whether arguments removed are a57 a69 -0.33 -0.44 a68 a58 a66
-0.46 a55
-0-.05.1 -0.5-0.1-70.170.17 a85 a71 a26 a64 -0.47
a43
a42 a29 -0.16
-0.14 a28 -0.32 a45 0.16 0.16 0.16 -0.48
a17 -0.49 those that can be immediately agged up as accepted/unaccepted for an extension of a given semantics. In a larger perspective, it may be useful to understand how the reduced dimension of argumentation graphs a ects solvers, and, in general, whether the minimization would be helpful for the reasoning process.
This work was partially funded by the Italian PON 2007-2013 project PON02 00563 3489339 `Puglia@Service'.