Computing Grounded Semantics of Uncontroversial
Acyclic Constellation Probabilistic Argumentation
in Linear Time
Stefano Bistarelli1 , Victor David1,* , Francesco Santini1 and Carlo Taticchi1
1
    Department of Mathematics and Computer Science University of Perugia, Italy


                                         Abstract
                                         We propose a new and faster (linear instead of exponential) way to compute the acceptability probability of
                                         an argument (in uncontroversial acyclic graph) with the grounded semantics in the constellations approach
                                         of probabilistic argumentation frameworks. Instead of computing all the worlds of the constellation (which
                                         is exponential) we show that it is possible to compute the probability of an argument only according to the
                                         acceptability probability of its direct attackers and the probability of its attacks by using a function.

                                         Keywords
                                         Probabilistic Argumentation Framework, Constellation, Grounded Semantics




1. Introduction
In recent years, argumentation has been increasingly recognised as a promising new research
direction in artificial intelligence. As a consequence of this growing interest, many authors have
studied different argumentation frameworks with different features and for various applications,
like decision making (e.g. [1]), negotiation (e.g. [2]), explainability (e.g. [3]). The pioneering
article in the field of abstract argumentation comes from Dung [4], where the notion of an abstract
argumentation framework is defined. These frameworks can be seen as directed graphs where the
nodes are arguments and the edges represent conflict relations (called attacks) between two argu-
ments. A fundamental issue in these argumentation frameworks is to determine the acceptability
of arguments and for this purpose so-called semantic methods are used. As mentioned earlier,
since Dung many extensions to this framework have been proposed, e.g. the addition of a support
relation (e.g. [5]), the addition of a similarity relation (e.g. [6, 7, 8, 9]), or the addition of weights
on arguments (e.g. [10]), on attack (e.g. [11]) and support relations (e.g. [12]). Note that the
meaning of the weights on arguments and relations can have different interpretations involving
different semantics for computing the collective acceptability of arguments.
   In this paper we place ourselves in the framework of probabilistic argumentation [13] where
our graphs only have arguments connected by probabilistic attacks, i.e. the weights on these
attacks indicate the probability that this attack exists. Recall that the two main approaches to
(abstract) probabilistic argumentation are constellations and epistemic approaches [14]. The
former considers probability functions on subgraphs of abstract argumentation frameworks, the
AI3 2022: 6th Workshop on Advances In Argumentation In Artificial Intelligence (AI³ 2022)
**
 Corresponding author.
                                       © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073
                                       CEUR Workshop Proceedings (CEUR-WS.org)
latter uses probability theory to represent degrees of belief in arguments, given a fixed framework.
Hence, our work is about the constellation approach. In this case, when we want to study the
acceptability of an argument, we need to look at all the possible worlds (i.e. the whole set of
possible subgraphs depending on the presence or absence of attacks). However, the creation
of a constellation (the set of subgraphs) is in general exponential [13] and for this reason the
attractiveness of research in this field is reduced for practical reasons. This paper is a first step
to show that it is possible to optimize the computation of the acceptability probability of an
argument without having to build the constellation.


2. Background
2.1. Dung Argumentation Frameworks
Following [4], an argumentation frameworks (AF) is a pair ⟨𝒜, ℛ⟩, where 𝒜 is a set of elements
called arguments and ℛ is a binary relation on 𝒜, called the attack relation. For 𝑎, 𝑏 ∈ 𝒜, if
(𝑎, 𝑏) ∈ ℛ, then we say that 𝑎 attacks 𝑏 and that 𝑎 is an attacker of 𝑏. If for 𝑎 ∈ 𝒜 there is no 𝑏 ∈ 𝒜
with (𝑏, 𝑎) ∈ ℛ, then 𝑎 is unattacked. For a set of arguments 𝐸 ⊆ 𝒜 and an argument 𝑎 ∈ 𝒜, 𝐸
defends 𝑎 if ∀(𝑏, 𝑎) ∈ ℛ, ∃𝑐 ∈ 𝐸 such that (𝑐, 𝑏) ∈ ℛ. We say that 𝑎 is defended if for each last
argument (unattacked) 𝑏𝑛 for each path to 𝑎 (i.e. {(𝑏𝑛 , 𝑏𝑛−1 ), . . . , (𝑏1 , 𝑎)}), all the 𝑏𝑛 arguments
defend 𝑎, i.e. 𝑛 is even. Let the set of attackers of 𝑎 denoted by Att(𝑎) = {𝑏 ∈ 𝒜 | (𝑏, 𝑎) ∈ ℛ}.
We say that an AF is uncontroversial ([4]) if ∀𝑎 ∈ 𝒜, 𝑎 is uncontroversial, i.e. ∄𝑏 ∈ 𝒜 s.t. 𝑎
attacks and defends 𝑏 (e.g. let AF be an odd cycle, then AF and each argument are controversial).
   An AF provides means to represent conflicting information. Reasoning with that information is
done by means of argumentation semantics. A semantics provides a characterisation of acceptable
arguments in an AF. A set of acceptable arguments according to a semantics is called an extension
and is taken as a reasoning outcome. Many semantics have been proposed, see e.g. [15] for
overviews. In this work, we will consider the very well established
                                                                 ⋃︀            grounded semantics: the
grounded extension of ⟨𝒜, ℛ⟩ can be constructed as gr = 𝑖≥0 𝐺𝑖 , where 𝐺0 is the set of all
unattacked arguments, and ∀𝑖 ≥ 0, 𝐺𝑖+1 is the set of all arguments that 𝐺𝑖 defends. For any
⟨𝒜, ℛ⟩, the grounded extension gr always exists and is unique.

2.2. Constellation Probabilistic Argumentation Frameworks
There exist different ways to extend the classic AF with probability into probabilistic argumenta-
tion framework (PrAF). For example, we can label arguments and/or attacks with a probability.
In [16] the authors proposed a way to transform any PrAF having probability on arguments and
attacks to PrAF with probability only on attacks (or only on arguments) thanks to the probabilistic
attack normal forms (or probabilistic argument normal form). They showed that all these forms
are equivalent, i.e. same probabilistic distribution on their extensions.

Definition 1 (PrAF). A probabilistic argumentation frameworks (PrAF) is a tuple 𝐴𝐹 =
⟨𝒜, ℛ, 𝑃𝑅 ⟩ ∈ 𝒰 1 such that: 𝒜 ⊆𝑓 Arg 2 , ℛ ⊆𝑓 𝒜 × 𝒜, 𝑃𝑅 : ℛ →]0, 1].
1
    We denote by 𝒰 the universe of all probabilistic argumentation frameworks.
2
    The notation 𝒜 ⊆𝑓 Arg stands for: 𝒜 is a finite subset of the universe of all arguments.
  The constellation of a graph is composed by all its possible subgraphs (worlds), and we
compute the probability of one subgraph as follows.
Definition 2 (Probability of a world). Let 𝐴𝐹 = ⟨𝒜, ℛ, 𝑃𝑅 ⟩ ∈ 𝒰 and 𝜔 = ⟨𝒜′ , ℛ′ , 𝑃𝑅 ⟩ be
                                                       3
probabilistic                   (︁ ∏︀such that 𝜔(︀ ⊑ 𝐴𝐹 . The)︀)︁probability of subgraph 𝜔, denoted
        (︁ ∏︀ argumentation)︁graph
𝑝(𝜔) =       𝑎𝑡𝑡∈ℛ′ 𝑃𝑅 (𝑎𝑡𝑡) ×        𝑎𝑡𝑡∈ℛ∖ℛ′ 1 − 𝑃𝑅 (𝑎𝑡𝑡)

Example 1. Let see the controversial acyclic graph 𝐴𝐹 = ⟨{𝑎, 𝑏, 𝑐}, {(𝑎, 𝑏), (𝑎, 𝑐), (𝑐, 𝑏)}, 𝑃𝑅 ⟩
such that 𝑃𝑅 ((𝑎, 𝑏)) = 0.4, 𝑃𝑅 ((𝑎, 𝑐)) = 0.7, 𝑃𝑅 ((𝑐, 𝑏)) = 0.2 and 𝑎 is controversial .
  Let see the constellation of 𝐴𝐹 with the probability of each world:

      𝑎             𝑎             𝑎            𝑎             𝑎             𝑎             𝑎            𝑎
            𝑏            𝑏             𝑏             𝑏             𝑏             𝑏            𝑏             𝑏
      𝑐             𝑐             𝑐            𝑐             𝑐             𝑐             𝑐             𝑐
      𝑝(𝜔1 ) =      𝑝(𝜔2 ) =      𝑝(𝜔3 ) =      𝑝(𝜔4 ) =      𝑝(𝜔5 ) =     𝑝(𝜔6 ) =      𝑝(𝜔7 ) =      𝑝(𝜔8 ) =
       0.056         0.224         0.084         0.024         0.336        0.096         0.036         0.144

  Recall that it was shown in [14]∑︀that the sum of the probability of any subgraph is equal to 1.
Let 𝐴𝐹 = ⟨𝒜, ℛ, 𝑃𝑅 ⟩ ∈ 𝒰, then 𝜔⊑𝐴𝐹 𝑝(𝜔) = 1.
  Let us recall now how to compute the probability of an argument or a set of arguments
belonging to the extensions of an extension-based semantics.
Definition 3 (Acceptability Probability). Let 𝐴𝐹 = ⟨𝒜,     ∑︀ℛ, 𝑃𝑅 ⟩ ∈ 𝒰, 𝑋𝒮 ⊆ 𝒜 and 𝒮
                                                 𝒮
an extension-based semantics, we denote by 𝑃 (𝑋) =             𝜔⊑𝐴𝐹 𝑝(𝜔) × In (𝜔, 𝑋), where
In𝒮 (𝜔, 𝑋) = 1 if 𝑋 is a subset of each extension of 𝒮 in 𝜔, otherwise it is equal to 0.
   Note that in [17], instead of giving a probability of acceptability for each argument (or set of
arguments) for the grounded semantics, they return a single set of acceptable arguments for the
initial graph. We consider that returning the probabilities is more generic and can be used in a
second step to provide an acceptable set of arguments.
Example 1 (Continued). The acceptability probabilities of the arguments with the grounded
semantics are: 𝑃 gr (𝑎) = 1, 𝑃 gr (𝑏) = 0.084 + 0.336 + 0.144 = 0.564, 𝑃 gr (𝑐) = 0.024 +
0.096 + 0.036 + 0.144 = 0.3.


3. Linear Computation in Uncontroversial Acyclic PrAF
Let us introduce the new function Fastgr , which is able to compute the probability of an argument
to be accepted in the grounded extension.
Definition 4 (Fastgr ). Let Fastgr the function from any PrAF ⟨𝒜, ℛ, 𝑃𝑅 ⟩ ∈ 𝒰 which compute
the acceptability probability of any argument to be in the grounded extension (𝒜 → [0, 1]), s.t.
                          ⎧
                                                                  )︀ if Att(𝑎) = ∅
                          ⎨ 1
            Fastgr (𝑎) =
                                 ∏︀       (︀     gr (𝑏) × 𝑃 (𝑏, 𝑎)
                          ⎩ 𝑏∈Att(𝑎)  1 −    Fast          𝑅         otherwise

3
    The notation 𝜔 ⊑ 𝐴𝐹 stands for: 𝒜′ ⊆ 𝒜 and ℛ′ = {(𝑎, 𝑏) ∈ ℛ | 𝑎 ∈ 𝒜′ and 𝑏 ∈ 𝒜′ }: 𝜔 is a subgraph of an AF.
   Let start by discuss the intuition of this function to understand why it characterises the
acceptability probability of the grounded semantics in some graph.
   Recall that an argument is in the grounded extension if it is defended, i.e. if all its incoming
attacks fail. Trivially, an unattacked argument will be acceptable in all worlds so its probability of
acceptability is 1. Let us now look at the case where an argument is attacked. The Fastgr (𝑏) ×
𝑃𝑅 (𝑏, 𝑎) makes the conjunction (computes the probability) of the events argument 𝑏 is acceptable
AND the attack (𝑏, 𝑎) exists. Thus 1 − Fastgr (𝑏) × 𝑃𝑅 (𝑏, 𝑎) gives the probability that argument
𝑏 is not acceptable OR attack (𝑏, 𝑎) does not exist, i.e. this attack fails. Finally, the product of this
computation for each attack ensures that all the attacks on 𝑎 fail, i.e. 𝑎 is defended.
   Remark: the coherence constraint results from the fact that Fastgr considers the acceptability
of arguments independently, i.e. it is possible for an controversial argument to be acceptable in
its defence path and rejected in its attack path. Therefore, for an acyclic PrAF AF, Fastgr returns
the probabilities of the arguments for the equivalent version of AF such that it is uncontroversial ,
i.e. each controversial argument is duplicated for its attacks and defences.
   Note that if controversial arguments are always rejected or accepted in worlds, as in Example 1
(𝑃 gr (𝑎) = 1), then Fastgr can return the same values as the constellation method (Fastgr (𝑎) =
𝑃 gr (𝑎) = 1, Fastgr (𝑏) = 𝑃 gr (𝑏) = 0.564 and Fastgr (𝑐) = 𝑃 gr (𝑐) = 0.3). We show next that
Fastgr characterises 𝑃 gr for any uncontroversial acyclic PrAF.

Theorem 1. If 𝐴𝐹 ∈ 𝒰 is uncontroversial and acyclic then ∀𝑎 ∈ 𝒜, 𝑃 gr (𝑎) = Fastgr (𝑎).

  We also study complexity of Fastgr : in the worst case (when an argument have as attackers
and defenders all other arguments) the complexity is linear O(n) (n is the number of all attacks)
and in the best case (unattacked argument) the complexity is constant O(1).

Theorem 2. Let 𝐴𝐹 ∈ 𝒰 is uncontroversial and acyclic. For any argument 𝑎 ∈ 𝒜, the
complexity of Fastgr (𝑎) depends on the number 𝑛 of attacks (direct and indirect) to 𝑎, i.e. 𝑂(𝑛).


4. Related Work and Conclusion
In [18], the complexity of computing the acceptability probability of an argument has been done
for different semantics and the result for the grounded is FP #𝑃 -complete. Having such a high
complexity, the work in [19] proposed some restriction on the value of the probability to improve
the complexity. If the probability is binary 0 or 1, then the probability of acceptance is polynomial
in time in the case of grounded semantics. If the probability is ternary 0, 0.5 or 1, then the
acceptability probability with the grounded is P-hard. Finally, in [20] a new fast algorithm to
compute the ground extension has been proposed for classic AF. It could be interesting to study
how this algorithm can be extended to PrAF.
   The constellations approach [13] suffers of a high complexity due to the exponential number
of generated worlds. In order to tackle this, we propose to compute the acceptance probability of
an argument with a new function, which is able to give the same score in linear time when we
curb to uncontroversial acyclic PrAFs. As future work, we will investigate how to extend this
function to controversial and cyclic PrAFs, then how to compute the probability of acceptance of
a set of arguments, and finally how to extend it to other semantics.
References
 [1] Q. Zhong, X. Fan, X. Luo, F. Toni, An explainable multi-attribute decision model based on
     argumentation, Expert Systems Applications 117 (2019) 42–61.
 [2] N. Hadidi, Y. Dimopoulos, P. Moraitis, Argumentative alternating offers, in: Proceed-
     ings of the international conference on Autonomous Agents and Multi-Agent Systems
     (AAMAS’10), 2010, pp. 441–448.
 [3] K. Čyras, A. Rago, E. Albini, P. Baroni, F. Toni, Argumentative xai: a survey, arXiv preprint
     arXiv:2105.11266 (2021).
 [4] P. M. Dung, On the Acceptability of Arguments and its Fundamental Role in Non-Monotonic
     Reasoning, Logic Programming and n-Person Games, Artificial Intelligence 77 (1995).
 [5] A. Cohen, S. Gottifredi, A. J. García, G. R. Simari, A survey of different approaches to
     support in argumentation systems, The Knowledge Engineering Review 29 (2014) 513–550.
 [6] V. David, Dealing with Similarity in Argumentation, Ph.D. thesis, Université Paul Sabatier-
     Toulouse III, 2021.
 [7] L. Amgoud, V. David, Measuring similarity between logical arguments, in: 16th Interna-
     tional Conference on Principles of Knowledge Representation and Reasoning, 2018.
 [8] L. Amgoud, V. David, D. Doder, Similarity measures between arguments revisited, in:
     G. Kern-Isberner, Z. Ognjanovic (Eds.), Symbolic and Quantitative Approaches to Reason-
     ing with Uncertainty, 15th European Conference, ECSQARU, 2019, pp. 3–13.
 [9] L. Amgoud, V. David, A General Setting for Gradual Semantics Dealing with Similarity,
     in: 35th AAAI Conference en Artificial Intelligence (AAAI 2021), 2021.
[10] J. Leite, J. Martins, Social abstract argumentation, in: T. Walsh (Ed.), Proc. of the 22nd
     International Joint Conference on Artificial Intelligence (IJCAI’11), 2011, pp. 2287–2292.
[11] P. E. Dunne, A. Hunter, P. McBurney, S. Parsons, M. J. Wooldridge, Weighted argument
     systems: Basic definitions, algorithms, and complexity results, Artif. Intell. (2011) 457–486.
[12] L. Amgoud, J. Ben-Naim, Evaluation of arguments in weighted bipolar graphs, International
     Journal of Approximate Reasoning 99 (2018) 39–55.
[13] H. Li, N. Oren, T. J. Norman, Probabilistic argumentation frameworks, in: International
     Workshop on Theorie and Applications of Formal Argumentation, Springer, 2011, pp. 1–16.
[14] A. Hunter, A probabilistic approach to modelling uncertain logical arguments, International
     Journal of Approximate Reasoning 54 (2013) 47–81.
[15] G. Charwat, W. Dvořák, S. A. Gaggl, J. P. Wallner, S. Woltran, Methods for solving
     reasoning problems in abstract argumentation–a survey, Artificial intelligence 220 (2015) 2.
[16] T. Mantadelis, S. Bistarelli, Probabilistic abstract argumentation frameworks, a possible
     world view, International Journal of Approximate Reasoning 119 (2020) 204–219.
[17] S. Bistarelli, F. Santini, A definition of sceptical semantics in the constellations approach,
     in: International Conference on Logic Programming and Nonmonotonic Reasoning, 2022.
[18] B. Fazzinga, S. Flesca, F. Parisi, On the complexity of probabilistic abstract argumentation
     frameworks, ACM Transactions on Computational Logic (TOCL) 16 (2015) 1–39.
[19] X. Sun, B. Liao, Probabilistic argumentation, a small step for uncertainty, a giant step for
     complexity, in: Multi-Agent Systems and Agreement Technologies, Springer, 2015.
[20] S. Nofal, K. Atkinson, P. E. Dunne, Computing grounded extensions of abstract argumenta-
     tion frameworks, The Computer Journal 64 (2021) 54–63.