We investigate the relationship between semantics for formal argumentation and measures from social networking theory. In particular, we consider using matrix exponentials, which are measures used for link prediction and recommendation in social networks, as a way to measure acceptability of arguments in abstract argumentation frameworks. We reformulate the approach of matrix exponentials to adhere for the fact that, compared to the social network setting, edges in argumentation frameworks have a negative connotation, arguments linked by edges should not be accepted together, and empirically evaluate this approach on benchmark graphs from ICCMA'15. Moreover, matrix exponentials can also be used for prediction in so-called signed social networks, which have both positive and negative edges denoting friend and foe relationships. As these networks bear a close resemblance to bipolar argumentation frameworks, we extend our framework and investigate the applicability of matrix exponentials from signed networks to be used in bipolar argumentation frameworks as well. Finally, we evaluate postulates for ranking-based argumentation semantics for our approach.
1. Introduction
In the field of formal argumentation [
Mathematically speaking, studies in abstract argumentation semantics are concerned
with graph-theoretic measures on (directed) graphs. Another discipline that studies the
very same mathematical object is (social) network theory [
We believe that because of the close methodological similarities of the research
disciplines of formal argumentation and social networking theory, a thorough investigation
of the applicability of the methods from one field to the other may be beneficial. Similar
observations have already been made by some other researchers in the field of formal
argumentation, see e. g. [
Let AttA(X ) for a set X of arguments be the set of its attackers, i. e., AttA(X ) = {y 2
Arg | 9 x 2 X , y ! x}. Semantics are given to an argumentation framework A = (Arg, RAtt)
through extensions [
The function F : 2Arg ! 2Arg is defined as F(B) = {A | B defends A} and is also called the characteristic function of A.
• S ✓ Arg is admissible iff S is conflict-free and S defends all of its elements. • S ✓ Arg is preferred iff S is a maximal set, with respect to set inclusion, among the admissible sets of A. • S ✓ Arg is stable iff S is conflict-free and for all B 2 / S there exist an argument A 2 S such that A ! B. • S ✓ Arg is complete iff it is an admissible set and all acceptable arguments, in respect to S, also belong to S.
• S ✓ Arg is grounded iff S is the least fixed point of F.
The set of admissible/preferred/stable/complete/grounded extensions establish the
semantics of an argumentation framework, cf. [
Bipolar argumentation frameworks [
• Given arguments A, B 2 Arg, a supported defeat is a sequence AR1 ... Rn 1B (for n 3), such that for all i=1...n-2, Ri 2 RSupp and Rn 1 2 RAtt . • Given arguments A, B 2 Arg, an indirect defeat is a sequence AR1 ... Rn 1B (for n 3), such that for all i=2...n-1, Ri 2 RSupp and R1 2 RAtt .
We say that S set-defeats A, iff there exists an argument B 2 S, such that there is some directed path from B to A that is a (supported or indirect) defeat. Similarly, we say that S set-supports A, iff there exists a sequence of the form A1R1 ... Rn 1A (for n 2), such that all Ri 2 RSupp and A1 2 S.
In bipolar argumentation frameworks, the concept of conflict-freeness has to be extended by defining internal and external conflict-freeness.
• S ✓ Arg is internally conflict-free iff S does not set-defeat any of its elements. • S ✓ Arg is externally conflict-free iff S does not set-defeat and set-support the same argument.
The above notions allow us to define the two important properties of conflict-freeness and safeness in bipolar frameworks. • S ✓ Arg is conflict-free iff @ A, B 2 S, such that {A} set-defeats B. • S ✓ Arg is safe iff @ B 2 S, such that S set-defeats and set-supports B.
However, following Cayrol et al. [
• D-admissibility (D in the sense of Dung): Let S ✓
S is conflict-free and S defends all its elements. • S-admissibility (S in the sense of safe): Let S ✓ is safe and S defends all its elements.
Example 1. Consider the bipolar argumentation framework in Figure 1. There, A,B,D is
the d-preferred extension, where A,B and D are the s-preferred extensions respectively.
3. Network Theory and Matrix Exponentials
Much attention in the field of network theory has been directed towards investigating
social network structures [
In the abovementioned social network example, edges have a positive connotation
as they indicate friendship relations. However, real social structures are also subject to
negative effects, e. g. not only friendly but also antagonistic relationships between
entities. To model these different relationships, signed networks [
Definition 1. Let A be some matrix. The matrix exponential exp(A) of A is defined as exp(A) = Â i=0 i! •
Ai (2) (3)
In other words, exp(A) sums paths of any length between users, but weights these by the inverse factorial path length. The result is a |V|⇥ |V| matrix that contains a so-called predication or recommendation score (simply called exponential score in the following) for connecting to new users. The higher this score, the more likely it is that a new edge will be established in the future.
Example 2. Figure 2 shows the adjacency matrix of the depicted friendship-graph, as well as the exponential scores computed with the matrix exponential. So we can see for example, that the system recommends A to befriend user C with a score of 0.5, as C is also a friend of B. Since Figure 2 shows a directed graph and C has no outgoing edges yet, there can be no recommendation made.
We will discuss the exponential score more closely and investigate its relationship to acceptability of arguments in the next section. 4. Matrix Exponentials for Abstract Argumentation When comparing the graph representation of argumentation frameworks to the introduced friendship networks, a fundamental difference that can be observed is the different connotations of edges. In friendship networks, edges symbolize a positive friendship relation, whereas the directed edges of argumentation frameworks represent attack relations. A further difference can be identified regarding edges. Where in friendship networks, the path length does not change the semantics of this path, the path length does have to be considered in argumentation frameworks, due to the concept of defense relations. So for example, in an argumentation framework, a path of length 1 has a negative connotation, i. e. attack, but continuing on this path via a further edge changes this to a positive connotation, i. e. a defense. Given that we have defined the semantics of a recommendation score in such a way, that a higher score value is superior to a lower value, when trying to compute a matrix exponential for a graph representing an argumentation framework, we have to integrate the different connotations of path length in order to adhere to the semantics of the recommendation score. As a result of this, paths of odd length should contribute negatively to the exponential score and paths of even length should contribute positively to the exponential score. We therefore represent attacks as negative entries in the adjacency matrix, in order to account for these mentioned factors regarding the semantics of paths in the graph.
Definition 2. Let A = (Arg, RAtt) be an abstract argumentation framework with Arg = {a1, . . . , an}. The matrix AˆA 2 {-1,0} | Arg | ⇥ | Arg | with Definition 3. Let A = (Arg, RAtt) be an abstract argumentation framework with Arg = {a1, . . . , an}. The matrix exponential exp(A) is the | Arg | ⇥ | Arg | real-valued matrix defined via exp(A) = exp(AˆA). For ai, a j 2 Arg the entry exp(A)i j 2 R is called acceptability assessment of a j wrt. ai.
An entry exp(A)i j is thus the accumulated and weighted sum of paths between ai and a j where paths of odd length contribute negatively and paths of even length contribute positively. Thus, the interpretation of a positive acceptability assessment of a j wrt. ai is that ai supports a j or “if ai is accepted then so should a j”. On the other hand, a negative acceptability assessment of a j wrt. ai indicates some contradiction between the arguments and “if ai is accepted then a j should not be accepted”. Furthermore, the ith column in exp(A) gives an overview on how argument ai is assessed by all arguments in the framework.
Example 3. Figure 3 shows (i) an argumentation framework, (ii) its adjusted adjacency
matrix, and (iii) its matrix exponential. The acceptability assessment of B wrt. A is -1,
the acceptability assessment of C wrt. A is 0.5 and so on. We can observe a correlation
between the acceptability assessment and acceptability as proposed by traditional
argumentation semantics. An admissible set in this framework is {A,C,E}, and as we can
see, the assessments for all pairs of arguments within this set are non-negative. Take the
1 0
constellation A! B! C. From the viewpoint of A, the explicit attack to B is weighted
more significantly than the defense relation from A to C, resulting in the acceptability
assessments -1 and 0.5 respectively. In our opinion, this resembles characteristics similar
to the results observed in the experiments by Rahwan et al. [
In order to make use of the assessments in the matrix exp(A) we now introduce a simple way to aggregate them and obtain a single value for each argument. In a first step, we consider a relative assessment wrt. some given set of arguments.
Definition 4. Let E ✓ Arg = {a1, . . . , an} be a set of arguments and a j 2 Arg. The relative acceptance score scoreE (ai) of ai wrt. E is defined via scoreE (a j) = Â ai2 E exp(A)i j
The value scoreE (a j) aggregates the acceptability assessments of arguments in E for argument a j. A positive value scoreE (a j) indicates that a j is assessed as acceptable. In particular, if E is any classical extension (such as a preferred extension), we would expect that scoreE (a j) for every a j 2 E is positive, indicating joint acceptability of arguments within an extension. We will come back to this issue in Section 5.
A more general acceptance score can be defined by considering the accumulated acceptability assessments wrt. to all arguments.
score(ai) = scoreArg(ai)
The value score(ai) indicates the general acceptance of ai within the argumentation framework. As for the relative acceptance score from above, we will have a closer look at the relationship of this score with classical argumentation semantics in Section 5. Note that the above method for aggregating an acceptance score for an argument is simple summation. Other aggregation methods are imaginable as well but left for future work.
Formally, our approach of acceptance scores resembles ranking semantics for
argumentation frameworks, which recently have gained some attention in the community, see
e. g. the work by Amgoud et al. [
Definition 6. Let A = (Arg, RAtt) be an abstract argumentation framework. Define the relation SeAxp ✓ Arg ⇥ Arg through (a, b) 2 SeAxp iff score(a) score(b).
is a x 2 X with (x, y) 2 SeAxp. Define also X <SeAxp Y if for all y 2 Y there is a x 2 X with (x, y) 2 SeAxp and (y, x) 2 / SeAxp.
In [
Theorem 1. The ranking Sexp satisfies the following postulates: fa(nad)RA’f0(abr)e, tihseonm(oar,pbh)i c2, iS.eAex.p, twhhereeneisvear b(ifje(act)i,ofn(bf):) A2 !SeAxA0p.0 with 8 a,b 2 A, aRb iff Independence For all simply-connected components B = (A0, R0) of A = (A, R), 8 a,b 2
A0, (a, b) 2 SeBxp whenever (a, b) 2 SeAxp.
Counter-Transitivity If AttA(b) SeAxp AttA(a) then (a, b) 2 SeAxp.
Strict Counter-Transitivity If AttA(b) <SeAxp AttA(a) then (a, b) 2 SeAxp. Quality Precedence If 9 c 2 AttA(b) such that 8 d 2 AttA(a), (d, c) 2 / SeAxp, then (b, a) 2 /
The proof of the above theorem is omitted due to space limitations but
straightforward. For a detailed discussion of these postulates see [
Before discussing some experiments in Section 5 we will have a look at the case of bipolar argumentation frameworks first. In particular, the matrix exponential can be 46666 001 010 0 0
Definition 7. Let B =(Arg, RAtt , RSupp) be a bipolar argumentation framework with Arg = {a1, . . . , an}. The matrix BˆB 2 {-1,0,1} | Arg | ⇥ | Arg | with
Definition 8. Let B =(Arg, RAtt , RSupp) be a bipolar argumentation framework with Arg = {a1, . . . , an}. The matrix exponential exp(B) is the | Arg | ⇥ | Arg | real-valued matrix defined via exp(B) = exp(BˆB). For ai, a j 2 Arg the entry exp(B)i j 2 R is called acceptability assessment of a j wrt. ai.
Relative and absolute acceptance scores can be defined for bipolar frameworks in the same way as for classical argumentation frameworks.
Example 5. Figure 5 shows (i) a bipolar argumentation framework, (ii) its adjacency
matrix, and (iii) the corresponding acceptance scores. From the point of view of argument
A, both B and C have an acceptability assessment of roughly -2, indicating a strong case
that these two arguments are not to be accepted by A. This low score can be attributed
to the explicit attack relations. Furthermore, we see that argument C supports D, which
itself supports E. Again from the view of A, the acceptability assessments are negative
for both D and E. Yet, the assessment for E is slightly higher than for D. In our opinion,
this showcases the successful implementation of our underlying motivation.
5. Experimental Evaluation
In this section, we report on some experiments we conducted in order to test the
applicability of the relative and absolute acceptance scores introduced above. The
experiments have been conducted on graphs from the First International Competition on
Computational Models of Argumentation5 (ICCMA’15) [
Regarding relative acceptance scores, i. e. the assessment of an argument from the viewpoint of the respective extension, we can distinguish between the relative acceptance score of extension members and non-extension members. As a result, we aggregated the individual relative acceptance scores into the three subgroups of positive (> 0), neutral (= 0) and negative scores (< 0) for these two types of arguments. Furthermore, we computed the average values for the relative- and absolute acceptance scores. Subsequently, the aim of our experiment was to validate these values against the following hypotheses. Hypothesis 1. If E is a complete, grounded, stable or preferred extension, the relative acceptance scores of all members of E are strictly positive.
Hypothesis 2. If E is a complete, grounded, stable or preferred extension, the relative acceptance scores of all non-members of E are strictly negative.
Hypothesis 3. If E is a complete, grounded, stable or preferred extension, the absolute acceptance scores of all members of E are on average higher than the absolute acceptance score of all non-members of E. 5.3. Results As a first result, we found that the relative acceptance scores of extension members are strictly positive. This conforms with the definition of admissible extensions as there may be no attacks within extensions. In our opinion, this shows that our approach manifests a ranking-based semantics that does not contradict extension-based argumentation semantics. Figure 6 shows the distribution of the average relative acceptance score of extension members under the grounded semantics for all considered graphs. The distributions for the complete, stable and preferred extension are very similar and were therefore omitted. As all relative acceptance scores of extension members are strictly positive, we accept hypothesis 1.
Figure 6 also shows the average distribution of relative acceptance scores for nonextension elements. As can be observed, there are some graphs where the relative accep
Extension members Non-Extension members
Extension members
Non-Extension members s t n e m u g r a f o . r N Relative acceptance score 0 0.5
1 Absolute acceptance score tance score of non-extension elements is greater than 0. We therefore reject hypothesis 2. However, it is noticeable that the scores of non-extension members are on average much lower than the scores of extension members. To put this into perspective, the average relative score for the extension members was 1.029, clearly distinguishable from the average relative acceptance score of non-extension members, which was -0.103.
When considering absolute acceptance scores, we incorporate assessments of arguments from the viewpoint of non-extension members. Here, the average absolute acceptance score of extension members was 0.733. So even when incorporating all nonextension members, i. e. attacks that should lower the individual acceptance scores, the average acceptance score of extension members did not decrease significantly. Regarding non-extension members, the average absolute acceptance score was 0.065. Nonextension members can form components that conform to each other. These components might not be admissible, still they can promote each other internally. This support will therefore increase the absolute acceptance score. Yet, we can accept hypothesis 3, as we find that admissible arguments wrt. the complete, grounded, preferred or stable extension of all graphs are ranked as more acceptable on average based on our approach. 6. Summary We have proposed an approach that computes acceptance scores of arguments using matrix exponentials from network theory. We applied this approach to both classical and bipolar argumentation frameworks and investigated its properties. Moreover, we conducted experiments to evaluate the applicability of our approach and its relationships to classical semantics. The empirical evaluation yielded two results. First, the relative acceptance score of extension members is positive in 100% of the cases. This conforms with classical semantics and shows that our approach is able to compute scores that adhere to these semantics. Secondly, for absolute acceptance scores the relative scores from before did not change significantly. In our opinion, this is a further point indicating that the semantics we assigned to the score, namely a higher score relating to a higher acceptability of an argument, is plausible. Figure 6 clearly shows, that the relative- and absolute acceptance scores of extension arguments are on average higher than the respective scores of non-extension arguments.
Our work contributes both from the conceptual as well as the computational point of view to research in computational argumentation. First, our ranking-based semantics gives a new perspective on fine-grained assessments of acceptability due to the use of matrix exponentials and its links to network theory. Second, as the (approximations of) the matrix exponentials are feasible to compute and due to the strong relationships between our semantics and classical semantics one could exploit this for computational purposes and develop a new solver for abstract argumentation based on our approach. We leave this topic for future work.
Further future work could be directed towards investigating comparable scores based on other recommendation measures from network theory. It is also worth noting that it might prove as beneficial to apply abstract argumentation theory to network theory, e. g. to consider whether certain argumentation semantics might be utilized to promote an understanding of groups in social networks.