Weighted Bipolar Argumentation Graphs: Axioms and Semantics

1 Introduction

Argumentation is a form of common-sense reasoning, which consists of justifying claims by arguments. The latter have generally basic strengths, and may be both attacked and supported by other arguments, leading to the so-called weighted bipolar argumentation graphs.

Two families of semantics were proposed in the literature for the evaluation of arguments in such graphs: extension semantics [Cayrol and Lagasquie-Schiex, 2005b; Oren and Norman, 2008; Brewka and Woltran, 2010; Boella et al., 2010; Nouioua and Risch, 2010], and gradual semantics [Cayrol and Lagasquie-Schiex, 2005a; Evripidou and Toni, 2014; Baroni et al., 2015; Rago et al., 2016; Pazienza et al., 2017]. The former evaluate mainly sets of arguments (extending Dung's 1995 semantics) while the latter focus on individual arguments.

This paper extends our previous works on axiomatic foundations of semantics for unipolar graphs (support graphs [Amgoud and Ben-Naim, 2016b] and attack graphs [Amgoud and Ben-Naim, 2016a]). It defines principles that a semantics would satisfy in a bipolar setting. Such principles are useful for defining reasonable semantics, for a better understanding of the design choices or foundations of each semantics, and for comparing pairs of semantics. As a second contribution, the paper analyzes existing semantics against the principles. The main conclusion is that extension semantics do not harness the potential of support relations. For instance, when there is no attack in a graph, the existing semantics declare all (supported, non-supported) arguments of the graph as equally strong. Gradual semantics take into account supporters in this particular case, however they violate some key principles. The third contribution of the paper is the definition of a novel gradual semantics for the sub-class of non-maximal acyclic bipolar graphs. We show that it satisfies all the proposed principles. Furthermore, it avoids a big jump problem that may impede the relevance of existing gradual semantics in some practical applications.

1 This is an abridged version of a paper titled "Evaluation of arguments on weighted bipolar graphs" which won a best-paper award at ECSQARU-17 conference.

2 Basic Concepts

Let us now introduce weighted bipolar argumentation graphs.

Definition 1 A weighted bipolar argumentation graph is a quadruple A = 〈A, w, R, S〉, where A is a finite set of arguments, w a function from A to [0, 1], R ⊆ A×A, S ⊆ A×A. Let WAG denote the set of all such graphs.

Given two arguments a and b, aRb (resp. aSb) means a attacks (resp. supports) b, and w(a) is the intrinsic strength of a. The latter may be the certainty degree of the argument's premises, trustworthiness of the argument's source, . . ..

A semantics is a function assigning an overall strength from the unit interval [0, 1] to each argument of a weighted bipolar graph. Arguments that get value 1 are extremely strong whilst those that get value 0 are worthless.

Definition 2 A semantics is a function S transforming any A = 〈A, w, R, S〉 ∈ WAG into a function DegSA from A to [0, 1]. For a ∈ A, DegSA(a) is the overall strength of a.

Let us recall the notion of isomorphism between graphs.

Definition 3 Let A = 〈A, w, R, S〉, A′ = 〈A′ , w′ , R′ , S ′ 〉 ∈ WAG. An isomorphism from A to A′ is a bijective function f from A to A′ such that: i) ∀ a ∈ A, w(a) = w′ (f(a)), ii) ∀ a, b ∈ A, aRb iff f(a)R′ f(b), iii) ∀ a, b ∈ A, aSb iff f (a)S ′ f (b).

Notations: Let A = 〈A,w,R, S〉 ∈ WAG and a ∈ A. AttA(a) = {b ∈ A | bRa} and sAttA(a) = {b ∈ AttA(a) | DegSA(b) ̸= 0}. Similarly, SuppA(a) = {b ∈ A | bSa} and sSuppA(a) = {b ∈ SuppA(a) | DegSA(b) ̸= 0}. Let A′ = 〈A′ ,w′ ,R′ , S ′ 〉 ∈ WAG such that A∩A′ = ∅. Let A ⊕ A′ be 〈A′′ ,w′′ ,R′′ , S ′′ 〉 ∈ WAG such that A′′ = A∪A′ , R′′ = R∪R′ , S ′′ = S ∪S ′ , ∀x ∈ A′′ , the following holds: w′′ (x) = w(x), if x ∈ A; w′′ (x) = w′ (x), if x ∈ A′ .

3 Principles for Semantics

In what follows, we propose principles that shed light on foundational properties behind semantics. In other words, properties that help us to better understand the underpinnings of semantics, and that facilitate their comparisons. The first nine principles are simple combinations of properties proposed for graphs with only one type of interactions (support in [Amgoud and Ben-Naim, 2016b] and attack in [Amgoud and Ben-Naim, 2016a]). The three last principles are new.

The first basic principle, Anonymity, states that the degree of an argument is independent of its identity.

Principle 1 (Anonymity) Semantics S satisfies anonymity iff, for all A = 〈A,w,R, S〉, A′ = 〈A′ ,w′ ,R′ , S ′ 〉 ∈ WAG, for any isomorphism f fromA to A′ , the following property holds: ∀ a ∈ A, DegSA(a) = DegSA′ (f (a)).

Bi-variate independence principle states the following: the overall strength of an argument a should be independent of any argument b that is not connected to it (i.e., there is no path from b to a, ignoring the direction of the edges).

Principle 2 (Bi-variate Independence) Semantics S satisfies bi-variate independence iff, for all A = 〈A,w,R, S〉, A′ = 〈A′ ,w′ ,R′ , S ′ 〉 ∈ WAG such that A∩A′ = ∅, the following property holds: ∀ a ∈ A, DegSA(a) = DegSA⊕A′ (a).

Bi-variate directionality principle states that the overall strength of an argument should depend only on its incoming arrows, and not on the arguments it itself attacks or supports.

Principle 3 (Bi-variate Directionality) Semantics S satisfies bi-variate directionality iff, for all A = 〈A,w,R, S〉, A′ = 〈A′ ,w′ ,R′ , S ′ 〉 ∈ WAG such that A = A′ , w = w′ , R ⊆ R′ , and S ⊆ S ′ , the following holds: for all a, b, x ∈ A, if R′ ∪ S ′ = R ∪ S ∪ {(a, b)} and there is no path from b to x, then DegSA(x) = DegSA′ (x). A path can mix attack and support relations, but the edges must be directed from b to x.

Bi-variate equivalence principle ensures that the overall strength of an argument depends only on its basic strength and the overall strengths of its attackers and supporters.

Principle 4 (Bi-variate Equivalence) Semantics S satisfies bi-variate equivalence iff, for any A = 〈A, w,R, S〉 ∈ WAG, for all a, b ∈ A, if:

• w(a) = w(b),
• there exists a bijective function f from AttA(a) to AttA(b) s.t ∀x ∈ AttA(a), DegSA(x) = DegSA(f(x)),
• there exists a bijective function f ′ from SuppA(a) to SuppA(b) s.t ∀x ∈ SuppA(a), DegSA(x) = DegSA(f (x)),

Stability principle states the following: if an argument is neither attacked nor supported, its overall strength should be equal to its intrinsic strength.

Principle 5 (Stability) Semantics S satisfies stability iff, for any A = 〈A, w, R, S〉 ∈ WAG, for any a ∈ A, if AttA(a) = SuppA(a) = ∅, then DegSA(a) = w(a).

Neutrality principle states that worthless attackers and worthless supporters have no effect on their targets.

Principle 6 (Neutrality) Semantics S satisfies neutrality iff for any A = 〈A, w, R, S〉 ∈ WAG, for all a, b, x ∈ A, if:

• w(a) = w(b),
• AttA(a) ⊆ AttA(b),
• SuppA(a) ⊆ SuppA(b),
• AttA(b) ∪ SuppA(b) = AttA(a) ∪ SuppA(a) ∪ {x} such that DegSA(x) = 0,

If an argument a is equally or less attacked than an argument b, and equally or more supported than b, then Bi-variate Monotony ensures that a should be at least as strong as b.

Principle 7 (Bi-variateMonotony) Semantics S satisfies bi-variate monotony iff, for any A = 〈A,w,R, S〉 ∈ WAG, for all a, b ∈ A such that:

• w(a) = w(b),
• AttA(a) ⊆ AttA(b),
• SuppA(b) ⊆ SuppA(a),

the following holds:

• DegSA(a) ≥ DegSA(b); (Monotony)
• if (DegSA(a) > 0 and sAttA(a) ⊂ sAttA(b)) or (DegSA(b) < 1 and sSuppA(b) ⊂ sSuppA(a)), then DegSA(a) > DegSA(b). (Strict Monotony)

Bi-variate Reinforcement principle concerns the quality of attackers and supporters. It states that any argument becomes stronger if the quality of its attackers is reduced and the quality of its supporters is increased.

Principle 8 (Bi-variate Reinforcement) Semantics S satisfies bi-variate reinforcement iff, for any A = 〈A, w, R, S〉 ∈ WAG, for all C, C′ ⊆ A, for all a, b ∈ A, for all x, x′ , y, y′ ∈ A \ (C ∪ C′ ) such that:

• w(a) = w(b),
• AttA(a) = C ∪ {x} AttA(b) = C ∪ {y},
• SuppA(a) = C′ ∪ {x′} SuppA(b) = C′ ∪ {y′},
• DegSA(x) ≤ DegSA(y) DegSA(x′ ) ≥ DegSA(y′ ),

the following holds:

• DegSA(a) ≥ DegSA(b); (Reinforcement)
• if (DegSA(a) > 0 and DegSA(x) < DegSA(y)) or (DegSA(b) < 1 and DegSA(x′ ) > DegSA(y′ )), then DegSA(a) > DegSA(b). (Strict Reinforcement)

Our next principle is not mandatory. Its suitability depends on the nature of arguments (opinion-based, analogical, etc.). It combines Imperfection property from [Amgoud and BenNaim, 2016b] with Resilience one from [Amgoud and BenNaim, 2016a]. Imperfection states that an argument whose basic strength is less than 1 cannot be fully rehabilitated by supports. This property prevents irrational behaviors, like fully accepting fallacious arguments that are supported. Resilience states that an argument whose basic strength is positive cannot be completely destroyed by attacks.

Principle 9 (Resilience) Semantics S satisfies resilience iff, for any A = 〈A, w, R, S〉 ∈ WAG, for all a ∈ A,

The next principles are new and answer the question: how the overall strengths of attackers should be aggregated with those of supporters? To answer this question, it is important to specify which of the two types of interactions is more important. We argue that a support is weaker than an attack since an attack is sufficient for weakening a whole argument while a support may only strengthen a part of it. Hence, in what follows we consider the case where an attack is more important than a support (Franklin principle) and the case where both relations are equally important (Strict Franklin principle). The latter ensures that an attacker and a supporter of equal strength counter-balance each other. This principle is suitable in multiple criteria decision making contexts.

Principle 10 (Franklin) A semantics S satisfies franklin iff, for any A = 〈A, w, R, S〉 ∈ WAG, for all a, b, x, y ∈ A, if

• w(a) = w(b),
• AttA(a) = AttA(b) ∪ {x},
• SuppA(a) = SuppA(b) ∪ {y},
• DegSA(x) = DegSA(y),

then the following hold:

• DegSA(a) ≤ DegSA(b), (Franklin)
• DegSA(a) = DegSA(b). (Strict Franklin)

Proposition 1 Let S be a semantics that satisfies Bi-variate Independence, Bi-variate Directionality, Stability, and Strict Franklin. For any A = 〈A, w, R, S〉 ∈ WAG, for any a ∈ A, if there exists a bijective function f from AttA(a) to SuppA(a) such that for any x ∈ AttA(a), DegSA(x) = DegSA(f(x)), then DegSA(a) = w(a).

Weakening states that if the attackers of an argument overcome its supporters, the argument looses weight. The idea is that supporters are not sufficient for counter-balancing attackers, however, they may mitigate the global loss due to attacks.

Principle 11 (Weakening) Semantics S satisfies weakening iff, for any A = 〈A, w, R, S〉 ∈ WAG, for any a ∈ A, if w(a) > 0 and there exists an injective function f from SuppA(a) to AttA(a) such that:

• ∀x ∈ SuppA(a), DegSA(x) ≤ DegSA(f(x)); and
• sAttA(a) \ {f(x) | x ∈ SuppA(a)} ̸= ∅ or ∃x ∈ SuppA(a) such that DegSA(x) < DegSA(f(x)),

Strengthening states that if the supporters of an argument overcome its attackers, the argument gains weight. Indeed, attacks are not sufficient for counter-balancing supports, however, they may mitigate the global gain due to supports.

Principle 12 (Strengthening) Semantics S satisfies strengthening iff, for any A = 〈A,w,R, S〉 ∈ WAG, for any a ∈ A, if w(a) < 1 and there exists an injective function f from AttA(a) to SuppA(a) such that:

• ∀x ∈ AttA(a), DegSA(x) ≤ DegSA(f(x)); and
• sSuppA(a) \ {f(x) | x ∈ AttA(a)} ̸= ∅ or ∃x ∈ AttA(a) such that DegSA(x) < DegSA(f(x)),

Bivariate Monotony follows from five other principles.

Proposition 2 If a semantics satisfies Bi-variate Independence, Bi-variate Directionality, Stability, Neutrality and Bi-

variate Reinforcement, then it satisfies Bivariate Monotony. Proposition 3 The principles can be satisfied all together.

4 Formal Analysis of Existing Semantics

There are two families of semantics in case of bipolar argumentation graphs: extension semantics [Cayrol and Lagasquie-Schiex, 2005b; Oren and Norman, 2008; Brewka and Woltran, 2010; Boella et al., 2010; Nouioua and Risch, 2010] and gradual semantics [Cayrol and Lagasquie-Schiex, 2005a; Baroni et al., 2015; Rago et al., 2016].

Extension semantics extend Dung's 1995 ones for accounting for supports between arguments. They take as input an argumentation graph 〈A, w, R, S〉 whose arguments have all the same intrinsic strength, and return sets of arguments, called extensions. From the extensions, a three-valued qualitative degree is assigned to every argument. Indeed, an argument is accepted if it belongs to all extensions, undecided (or credulously accepted) if it belongs to some but not all extensions, and rejected if it does not belong to any extension. When the support relation is empty, the semantics proposed in [Cayrol and Lagasquie-Schiex, 2005b; Oren and Norman, 2008; Brewka and Woltran, 2010; Boella et al., 2010; Nouioua and Risch, 2010] coincide with Dung's ones. Thus, they violate the principles that are violated by Dung's semantics (see [Amgoud and Ben-Naim, 2016a] for a detailed analysis of Dung's semantics). For instance, stable semantics violates Bi-variate Independence, Bi-variate Equivalence, Stability, Resilience, and Strict Monotony. When the attack relation is empty, the approaches from [Cayrol and Lagasquie-Schiex, 2005b; Oren and Norman, 2008; Boella et al., 2010] return a single extension, which contains all the arguments of the graph at hand. Thus, all arguments are equally accepted. This shows that the support relation does not play any role, and a supported argument is as strong as a non-supported one. Formally, these approaches violate strengthening principles, which capture the role of supports. The approaches developed in [Brewka and Woltran, 2010; Nouioua and Risch, 2010] also return a single extension when the attack relation is empty. In case of acyclic graphs, the extension is the set of all arguments. Thus, these approaches violate strengthening and the support relation may not be fully exploited in the evaluation of arguments.

Gradual semantics were introduced for the first time in [Cayrol and Lagasquie-Schiex, 2005a]. The authors presented some properties that such semantics should satisfy (like a particular case of strengthening). However, they did not define concrete semantics. To the best of our knowledge, the first gradual semantics was proposed in [Evripidou and Toni, 2014]. It was extended to QuAD in [Baroni et al., 2015] for evaluating arguments in acyclic graphs.

Definition 4 Let A = 〈A, w,R, S〉 ∈ WAG. A is acyclic iff the following holds: for any non-empty finite sequence a = 〈a1, a2, . . . , an〉 of elements of A, if ∀i ∈ {1, 2, . . . , n - 1}, 〈ai, ai+1〉 ∈ R ∪ S, then 〈an, a1〉 ̸∈ R ∪ S.

We define next restricted semantics. All principles for semantics are straightforwardly adapted to restricted semantics.

Definition 5 A restricted semantics is a function S transforming any acyclic A = 〈A, w, R, S〉 ∈ WAG into a function DegSA from A to [0, 1].

QuAD is a restricted semantics assigning a numerical value to every argument on the basis of its intrinsic strength, and the overall strengths of its attackers and supporters. It evaluates differently supporters and attackers before aggregating them.

Proposition 4 QuAD violates Strict Monotony, Strict Reinforcement, Resilience, (Strict) Franklin, Weakening, and Strengthening. It satisfies all the remaining principles.

As a consequence of violating Weakening and Strengthening, QuAD may behave irrationally. Consider a weighted bipolar graph where A = {a, b1, b2, b3}, w(b1) = w(b2) = 0.8, w(b3) = 0.9, R = {(b2, a), (b3, a)}, and S = {(b1, a)}. Thus, a has an attacker and a supporter of equal strengths (DegSA(b1) = DegSA(b2) = 0.8), and an additional attacker b3. If w(a) = 0.2, then DegSA(a) = 0.422 meaning that the single supporter is privileged to the two attackers. However, if w(a) = 0.7, DegSA(a) = 0.477 meaning that attacks are privileged to support. More generally, we can show that if w(a) ≥ 0.5, then DegSA(a) < w(a), else DegSA(a) > w(a). Hence, choosing which of support and attack should take precedence depends on the intrinsic strength of an argument.

QuAD was recently extended to the restricted semantics DF-QuAD in [Rago et al., 2016]. Unlike QuAD, it uses the same function for aggregating supporters and attackers separately. It satisfies Strict Franklin axiom, thus it treats equally attacks and supports. It violates Strengthening and Weakening in presence of attackers/supporters of degree 1. However, the semantics avoids the irrational behavior of QuAD.

Proposition 5 DF-QuAD violates Strict Monotony, Strict Reinforcement, Resilience, Weakening, and Strengthening. It satisfies all the remaining principles.

Both (QuAD, DF-QuAD) suffer from a big jump problem. Consider the graph depicted in Figure 1. For x being QuAD or DF-QuAD, DegxA(i) = 0.991. Note that the value of i makes a big jump from 0.10 to 0.991 and i becomes even stronger than its supporter j. There are two issues with such jump: First, the gain is enormous. Assume that i is a fallacious argument. The supporter may increase slightly its strength but cannot fully rehabilitate it. Second, such jump impedes the discrimination between different cases where w(i) > 0.1 since whatever the value of w(i), the overall strength is almost 1.

5 Euler-based Graded Semantics

We have seen that no existing semantics satisfies all our principles. We define a novel restricted semantics satisfying them all for the subclass of acyclic non-maximal graphs. Without loss of generality, the basic strengths of arguments are considered less than 1. Note that few arguments are intrinsically perfect. The probability of false information, exceptions, etc., is rarely 0. In contrast, the loss of cyclic graphs is important. But, we consider that the class of all acyclic non-maximal graphs is expressive enough to deserve attention.

Definition 6 A restricted semantics is a function S transforming any acyclic non-maximal A = 〈A, w, R, S〉 ∈ WAG into a function DegSA from A to [0, 1].

Before presenting our semantics, we need to introduce a relation between arguments based on the longest paths to reach them (mixing support and attack arrows).

Definition 7 (Well-founded relation) Let A = 〈A,w,R, S〉 be an acyclic BAG and a ∈ A. A path to a in A is a non-empty finite sequence a = 〈a1, a2, . . . , an〉 of elements of A such that an = a and ∀i ∈ {1, 2, . . . , n - 1}, 〈ai, ai+1〉 ∈ R ∪ S. We denote by Rel(A) the well-founded binary relation ≺ on A such that ∀x, y ∈ A, x ≺ y iff max{n | there exists a path to x of length n} < max{n | there exists a path to y of length n}. Since A is acyclic, those maximum lengths are well-defined, so is Rel(A).

We are ready to define the Euler-based restricted semantics. The general idea is to take into account supporters and attackers in an exponent E of e (the Euler's number). More precisely, the stronger or more-numerous the supporters, the greater and more-likely-positive that exponent. Obviously, the inverse is true with the attackers. Then, the overall strength of an argument a is naturally defined as w(a)eE . Finally, we need certain tweaking (including a double polarity reversal) to make our function a restricted semantics in the first place, and to have it satisfy all our axioms.

Definition 8 We denote by Ebs the restricted semantics such that for any acyclic non-maximal A = 〈A, w, R, S〉 ∈ WAG, Ebs(A) is the function f from A to [0, 1] recursively defined with Rel(A) as follows: ∀a ∈ A,

Theorem 1 Let A = 〈A,w,R, S〉 ∈ WAG be acyclic nonmaximal and a ∈ A. The following holds:

Example 1 Consider the graph depicted in Figure 1. Every circle contains [argument name]:[intrinsic strength] and below [overall strength]. The neutrality principle can be checked with g and e, stability with d, g, h, and j, bivariate monotony with a and b, bivariate reinforcement with b and c, Imperfection with i, Strict Franklin with a, weakening with e.g. b, and strengthening with i.

Note also that being supported by a very strong argument does not cause a weak argument to become extremely strong, which shows that Ebs does not suffer from the big jump problem. Indeed, Deg Ebs A (i) = 0.22 and thus the jump is not big.

Theorem 2 Ebs satisfies all the 12 principles.

6 Conclusion

The paper presented for the first time principles that serve as guidelines for defining semantics for weighted bipolar argumentation graphs. It also analyzed existing semantics with regard to the principles. The results revealed that extension semantics violate key principles, and do not fully exploit support relations. Existing gradual semantics satisfy more but not all the principles. We proposed a novel semantics which satisfies all the principles.

This work can be extended in several ways. An urgent future work consists of defining a semantics that satisfies the principles while dealing with any typology of graphs including thus cyclic ones. Another perspective consists of defining semantics that take strict precedence to attacks over supports. Finally, new principles can be defined for capturing other features of semantics like those proposed very recently in [Baroni et al., 2018; Mossakowski and Neuhaus, 2016].

Acknowledgments

This work was supported by ANR-13-BS02-0004 and ANR11-LABX-0040-CIMI.