Synthesis of Argumentation Graphs
by Matrix Factorization
Andrea Pazienza, Stefano Ferilli, and Floriana Esposito
Dipartimento di Informatica – Università di Bari
name.surname @uniba.it
Abstract. In the phase of evaluation of accepted arguments, one may
find 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 dis-
cussion in huge Argument Systems through the analysis of its synthesis
may favor better interpretability and may allow us to extract seman-
tics that include the the strongest arguments. We propose a new matrix
interpretation of argumentation graphs and exploit a matrix decomposi-
tion technique, i.e. the Singular Value Decomposition, in order to yield a
synthetized argument system with only the most prominent arguments.
1 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 ar-
gumentation 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 representa-
tions 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 ap-
proach can be addressed also for generalized versions of argument graphs, such as
Bipolar Argumentation Framework (BAF) [1], Weighted Argumentation Frame-
works (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 re-
constructed matrix is then discussed. Section 3 shows its application to a real
discussion from a Online Debating System. The last section concludes.
2 Principal Argument Systems
An argument graph can be represented with a slightly different version of its
adiacency matrix. Given an Argumentation Framework F = hA, Ri, 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 MF = [Mij ] such that for any two arguments
αi , αj ∈ A, the entry Mij = −1 iff 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 var-
ious 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 ∈ R+ ∗ , that corresponds to the weight of the attack
relation between two arguments;
– BWAF: entries of Argumentation Matrix have values Mij = w, with w ∈
[−1, 1] corresponding to the relative strength of relations between arguments.
Matrix decomposition allows us to deal with the problem of low-rank approx-
imation. 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.
2.1 Singular Value Decomposition in a Nutshell
Let A ∈ 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 ) ∈ Rm×m and V = (v1 , . . . , vn ) ∈
Rn×n are orthogonal, and Σ ∈ 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 Ã, 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 ∈ Rm×n : rank(B) ≤ k} ∀k ∈ {1, . . . , r − 1}, than for all à ∈ B,
Pk
where à = Uk Σk VkT = i=1 ai σi viT , it holds that minB∈B kA − Bk2F = kA −
Pr
Ãk2F = 2
i=k+1 σ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
Pk
by the SVD of A, namely à = Uk Σk VkT = i=1 ui σi viT 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 Argument System Reconstrunction
Given the Argumentation Matrix of the argumentation graph under considera-
tion (i.e, AF, BAF, WAF, BWAF), its low-rank approximation with the trun-
cated 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 se-
lect 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 frac-
tion 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 ∈
Rn×n , where n is the number of nodes of the argumentation graph, considering
only its k largest principal components. Depending on the considered argumen-
tation graph (i.e., AF, BAF, WAF, BWAF), the approximation of the corre-
sponding 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 Eab > 0.5;
– BAF: an attack relation or a support relation between them iff, respectively
Eab ≤ −0.5 or Eab ≥ 0.5, otherwise any relation is built;
– WAF: an attack relation between them iff 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 iff, respectively, −1 < Eab < 0 or
0 < Eab < 1.
The reconstructed argumentation graph will yield only the strongest argu-
ments, depending on the relations survived from the operation of the SVD di-
mensionality reduction. In fact, we expect that this operation will delete the
weakest relations from the argument graph. Then, the arguments no longer en-
gaged 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 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.
a20 -0.19 a19
-0.45 -0.48
a18
a21
a76
-0.48
a23
-0.42 a17
0.32
a62 a14
a63
a24 a16
a75 -0.49
-0.16 a22
-0.16 a80 -0.48
a8 -0.44
a10
a61 0.16
-0.1 0.16 -0.47
-0.1
a78 a11
0.32 a45 0.16
-0.08 -0.48
a60 a53 a12
a74 a9
-0.47
-0.17 a85
-0.46
-0.12
a59 a84 -0.17
-0.12 a15 a44 a13
a58 -0.1 -0.5 0.17
-0.25 a72
-0.5 0.43
-0.13 -0.25
a66 a43
-0.5 a33
a0 -0.4 a71
-0.5 0.24
0.25
a69 -0.44 a68 a42
a57 -0.5 0.5 a27 -0.48
-0.5 -0.5 -0.13
-0.33 -0.5 0. 5 a26 -0.16
a65 0.06 0.22
0.08
a31 -0.45 a32
a56 -0.14
-0.48 a28
a54 a73 a64
a4 -0.15 -0.45 -0.48
a47 -0.16
a48 a29
-0.46 a50 -0.16 -0.16
a36
a37 a34
0.45
a55 0.05 a41 -0.34
0.08 a39
-0.24
a5
-0.32 a38
a51 a49
a40 a35
Fig. 1. BWAF representation for the considered Reddit Thread.
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 sys-
tem 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 re-
lations 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:
a63
-0.16 a75
a61 0.32 a60
-0.42
-0.16 a76
a62
This behaviour suggests a possible strategy to determine the ideal inconsis-
tency 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 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 inter-
est 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 extension-
based semantics are affected by reduction, or whether arguments removed are
a19
-0.48
a18
-0.19
a23
a20 -0.48 a14
a16
-0.45 0.32
a17
a24
a21 a22 -0.48
a8 -0.44
-0.49
a74 0.16
0.16
a53 a45
-0.47 a11 -0.48 a12
a10
a69 a84 0.16
a9
-0.17 -0.46
a58 -0.1 -0.47
-0.5 -0.17 a85
-0.5 a13
-0.44 0.17
-0.13 a44
-0.25 a72 a15 0.43
a66
a43
a57 -0.5 -0.25 a33
-0.5 a0 -0.4 a71
a68 0.24 a42
0.25
-0.33 -0.5 0.5
-0.48
-0.5 a27
a65 0 .5 -0.13
a26 -0.16
-0.5 -0.5 a31
a56 0.06 0.22 -0.45
-0.48 0.08 -0.14 a32
a54
a4 a64 a28 -0.45
-0.46 -0.48
a73 -0.15 -0.16
a55 a47 a36
a29 -0.16 -0.16
a48 a37
0.45 a34
a50
a41
a39 -0.34 -0.24
a5
-0.32
a38 a35
a40
Fig. 2. P -BWAF representation of the resulting synthetized BWAF.
those that can be immediately flagged up as accepted/unaccepted for an exten-
sion 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 gen-
eral, whether the minimization would be helpful for the reasoning process.
Acknowledgments
This work was partially funded by the Italian PON 2007-2013 project
PON02 00563 3489339 ‘Puglia@Service’.
References
[1] L. Amgoud, C. Cayrol, and M. Lagasquie-Schiex. On the bipolarity in argumenta-
tion frameworks. In NMR, pages 1–9, 2004.
[2] P. M. Dung. On the acceptability of arguments and its fundamental role in non-
monotonic reasoning, logic programming and n-person games. Artificial intelli-
gence, 77(2):321–357, 1995.
[3] P. E. Dunne et al. Weighted argument systems: Basic definitions, algorithms, and
complexity results. Artificial Intelligence, 175(2):457 – 486, 2011.
[4] G. H. Golub and C. Reinsch. Singular value decomposition and least squares solu-
tions. Numerische mathematik, 14(5):403–420, 1970.
[5] A. Pazienza, S. Ferilli, and F. Esposito. On the gradual acceptability of arguments
in bipolar weighted argumentation frameworks with degrees of trust. In ISMIS
2017, pages 195–204, 2017.