Introduction

Dung's abstract argumentation frameworks (AFs) [2] are a central concept in many argumentation formalisms and systems. Efficient and versatile methods for abstract argumentation are therefore important for further advances in the field. It is well known that AFs are usually represented as directed graphs, which play a significant role in modeling and analyzing the extension-based semantics of argumentation frameworks. Matrix representations of graphs are still in some areas the only way to represent graphs. Adjacency matrices represent adjacent vertices are capable of representing undirected and directed graphs. Matrix representations provide a bridge to linear algebra-based algorithms for graph computation. So, the potential application to argumentation frameworks is worth to expect.

The Singular Value Decomposition (SVD) [4] is the main linear technique for dimensionality reduction, aiming at producing a low-rank approximation of the original matrix with a less number of components. Our aim is therefore to exploit the matrix representation of argumentation frameworks and its low-rank approximation so as to produce a synthetized AF in order to decompose huge AFs and build a simplified ones, focusing only on arguments that are extremely useful for the evaluation process and discarding the less relevant ones, while preserving the interpretation of the whole discussion. We show that this new approach can be addressed also for generalized versions of argument graphs, such as Bipolar Argumentation Framework (BAF) [1], Weighted Argumentation Frameworks (WAFs) [3] and the recently proposed Bipolar Weighted Argumentation Frameworks (BWAFs) [5]. 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.

Principal Argument Systems

An argument graph can be represented with a slightly different version of its adiacency matrix. Given an Argumentation Framework F = A, R , where A is a finite set of arguments and R ⊆ A × A, with |A| = n, we call Argumentation Matrix of F the n × n matrix M F = [M ij ] such that for any two arguments α i , α j ∈ A, the entry M ij = −1 iff there is an attack from α i towards α j , otherwise the entry M ij = 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. 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 fit 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.

Singular Value Decomposition in a Nutshell

Let A ∈ R m×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 = (u 1 , . . . , u m ) ∈ R m×m and V = (v 1 , . . . , v n ) ∈ R n×n are orthogonal, and Σ ∈ R m×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 Ã, said truncated, which has a specific rank k. If A is a matrix of rank r > 1, A = U ΣV T is the corresponding SVD, and

B = {B ∈ R m×n : rank(B) ≤ k} ∀k ∈ {1, . . . , r − 1}, than for all à ∈ B, where à = U k Σ k V T k = k i=1 a i σ i v T i , it holds that min B∈B A − B 2 F = A − à 2 F = r i=k+1 σ 2 i , i.e.

, the k-dimensional submatrix à 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 difference between A and à under the constraint that rank( Ã) = k. It turns out that the solution is given by the SVD of

A, namely à = U k Σ k V T k = k i=1 u i σ i v T i

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).

Argument System Reconstrunction

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 defines 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 "cliff" are extracted. Now, it is possible to reconstruct the reduced approximating matrix E ∈ R n×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 specific constraints, for which this matrix must be revised otherwise.

Let a, b be two arguments, then there is:

-AF: an attack relation between them iff E ab > 0.5; -BAF: an attack relation or a support relation between them iff, respectively E ab ≤ −0.5 or E ab ≥ 0.5, otherwise any relation is built; -WAF: an attack relation between them iff E ab > 0 where its weight is given by approximating the value E ab to the nearest integer number; -BWAF: an attack relation or a support relation between them with weight value equal to E ab with bounds −1 or 1 iff, respectively, −1 < E ab < 0 or 0 < E ab < 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).

Application on a Reddit Thread

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. 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 first 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., justified) ones, especially when the strength of their attack, or support, is extremely weak. Another interesting effect of the SVD is that even some subgraphs may have been removed. In our case, two subgraphs have been removed: 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.

Conclusion

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 confirms 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 effectiveness 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 affected by reduction, or whether arguments removed are those that can be immediately flagged 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 affects solvers, and, in general, whether the minimization would be helpful for the reasoning process.