Formulating semantics of probabilistic argumentation by characterizing subgraphs: theory and empirical results

Beishui Liao, Kang Xu, Huaxin Huang

Introduction

In the field of artificial intelligence, Abstract Argumentation Frameworks (AFs) provide a robust structure for modeling conflicting information and reasoning through disputes. However, classical AFs are deterministic, assuming that arguments and their relationships are either present or absent. Real-world reasoning is rarely so binary; it is often characterized by uncertainty. This has led to the development of Probabilistic Argumentation Graphs (PrAGs), where arguments exist with a specific probability.

While PrAGs offer a more nuanced representation of reality, they introduce a significant computational challenge known as the "curse of dimensionality." This paper explores a novel approach to calculating the probability of extensions—sets of acceptable arguments—by moving away from exhaustive "possible worlds" simulations toward a more efficient method based on characterizing subgraphs (C-Sub).

The Computational Challenge: Possible Worlds

In classical argumentation, we seek to identify "extensions"—sets of arguments that are internally consistent and can defend themselves against external attacks according to specific rules, or semantics ($\sigma$). In a probabilistic setting, the goal is to determine the probability $p(E^\sigma)$ that a specific set $E$ constitutes an extension.

The traditional method for this calculation is the Possible Worlds (PW) approach. Given a graph with $n$ arguments, there are $2^n$ potential subgraphs (worlds). To find the probability of $E$, one must:

  1. Construct every possible subgraph.
  2. Verify if $E$ is an extension within that specific subgraph.
  3. Sum the probabilities of all subgraphs where $E$ is valid.

This approach is computationally expensive. For a graph with only 25 arguments, a system must evaluate over 33 million subgraphs. As the number of nodes increases, exact computation becomes functionally impossible for real-time AI applications.

The C-Sub Approach: Smart Partitioning

The core contribution of this research is the Characterized Subgraph (C-Sub) approach. Rather than evaluating every possible world, the authors identify the specific properties a subgraph must possess for a set $E$ to be an extension. They achieve this by partitioning the graph into four distinct components relative to the target extension $E$:

  • The Extension ($E$): The set of arguments we wish to validate.
  • Direct Attackers: Arguments that attack $E$ but are not attacked back by $E$.
  • Defeated Arguments: Arguments that are attacked by $E$.
  • Remaining Arguments ($I$): The "uncertain" set of arguments that do not directly interact with $E$ but may indirectly influence its validity.

By characterizing the necessary behavior of these components—for instance, requiring that all arguments in $E$ appear while ensuring that attackers of $E$ are excluded unless defended—the authors derived formulas to compute $p(E^\sigma)$ directly. For complex semantics like Preferred or Grounded, the researchers utilized labeling-based algorithms (assigning arguments as IN, OUT, or UNDECIDED) to navigate the search space of the "Remaining Arguments" ($I$) more efficiently.

Theoretical and Empirical Results

The shift from the total number of nodes ($n$) to the size of the remaining set ($I$) fundamentally changes the complexity of the problem. The authors demonstrated that for Admissible and Stable semantics, the probability can be calculated in polynomial time. For Complete and Preferred semantics, the problem becomes Fixed-Parameter Tractable (FPT), meaning the complexity is tied to the size of $I$ rather than the entire graph.

Empirical Performance

The researchers tested their C-Sub approach against the PW approach using randomly generated graphs with 10 to 25 nodes and varying edge densities. The results revealed several key insights:

  • Dramatic Speedup: In a graph with 25 nodes and a 3:1 edge-to-node ratio, the PW approach exceeded the 180-second timeout. In contrast, the C-Sub approach completed the task in approximately 15 seconds.
  • The Inverse Efficiency Property: Interestingly, denser graphs—which usually slow down graph algorithms—actually improved the performance of the C-Sub approach. In dense graphs, $E$ attacks more arguments, which shrinks the set $I$ and reduces the search space.
  • Scalability: While the PW approach's execution time grew exponentially with the number of nodes, the C-Sub approach remained relatively stable, particularly when the target extension $E$ was larger and covered more of the graph.

Conclusion and Future Work

By focusing only on the "worlds that matter," the C-Sub approach provides a significant performance boost for probabilistic reasoning. This framework moves probabilistic argumentation closer to practical application in complex decision-support systems.

However, the authors acknowledge several limitations that pave the way for future research. Currently, the model assumes that the appearance of one argument is independent of others, which may not hold in logical chains of reasoning. Furthermore, the current study focuses on argument-based probability; future iterations could expand to include uncertain attacks (edges). Finally, proving whether Grounded semantics is Fixed-Parameter Tractable under this approach remains an open challenge for the field.

Summary updated

Abstract

In existing literature, while approximate approaches based on Monte-Carlo simulation technique have been proposed to compute the semantics of probabilistic argumentation, how to improve the efficiency of computation without using simulation technique is still an open problem. In this paper, we address this problem from the following two perspectives. First, conceptually, we define specific properties to characterize the subgraphs of a PrAG with respect to a given extension, such that the probability of a set of arguments E being an extension can be defined in terms of these properties, without (or with less) construction of subgraphs. Second, computationally, we take preferred semantics as an example, and develop algorithms to evaluate the efficiency of our approach. The results show that our approach not only dramatically decreases the time for computing p(E^σ), but also has an attractive property, which is contrary to that of existing approaches: the denser the edges of a PrAG are or the bigger the size of a given extension E is, the more efficient our approach computes p(E^σ). Meanwhile, it is shown that under complete and preferred semantics, the problems of determining p(E^σ) are fixed-parameter tractable.
BibTeX
@article{liao2018formulating,
  author = {Beishui Liao and Kang Xu and Huaxin Huang},
  title = {{Formulating semantics of probabilistic argumentation by characterizing subgraphs: theory and empirical results}},
  journal = {J. Log. Comput.},
  year = {2018},
  doi = {10.1093/logcom/exx035},
}
Figure