Fast Computing of Dung Semantics in Acyclic Probabilistic Argumentation Frameworks

Stefano Bistarelli, Victor David, Pierre Monnin, Francesco Santini, Carlo TaticchiAAAI 2025 · DOI

Abstract

This paper introduces Fast_SCG and Fast_DAG, two novel algorithms designed to efficiently compute argument acceptance in Probabilistic Argumentation Frameworks (PrAFs). By shifting from exponential "possible worlds" calculations to local probability propagation and symbolic computation for acyclic graphs, these algorithms achieve exact results in linearithmic time for tree-like structures and significantly outperform existing methods for general acyclic graphs.

Introduction

Abstract Argumentation models debates as directed graphs where nodes represent arguments and edges represent "attacks." In many real-world scenarios, such as structured debate platforms or machine learning interpretability, these attack relations are uncertain. Probabilistic Argumentation Frameworks (PrAFs) address this by assigning probabilities to arguments and attacks.

Example of a Probabilistic Argumentation Framework (PrAF) where edges represent attacks with associated probabilities.

The traditional method for evaluating argument acceptance is the "Constellation" paradigm. This approach treats a PrAF as a collection of every possible graph configuration, or "possible worlds," and sums the probabilities of all worlds where a specific argument is accepted. However, the number of possible worlds grows exponentially ($2^{|R|}$, where $R$ is the number of attacks), making the computation #P-complete. This computational bottleneck renders standard methods unusable for large-scale frameworks.

The Constellation paradigm: for a simple 3-attack graph, there are $2^3=8$ possible worlds to evaluate, illustrating the exponential complexity.

Methodology

The authors propose a "local propagation" approach that calculates the probability of an argument's acceptance based on its direct attackers, specifically targeting acyclic graphs.

Fast_SCG (Singly-Connected Graphs)

For "polytrees"—graphs with only one path between any two nodes—the Fast_SCG algorithm orders arguments from unattacked "roots" to the target. It propagates probabilities in $O(n \log n)$ time, providing a highly efficient solution for tree-like structures.

Fast_DAG (Directed Acyclic Graphs)

General DAGs present a challenge due to dependent arguments—arguments reachable through multiple paths. To avoid "double-counting" probabilities, Fast_DAG employs symbolic computation. It treats dependent arguments as variables during propagation and applies an idempotent operator ($\otimes$). In probability logic, $P(A \cap A) = P(A)$; symbolically, this means $k \otimes k = k$. By expanding these expressions and removing higher powers, the algorithm maintains exactness without visiting every possible world.

Experimental Evaluation

The algorithms were benchmarked using two primary datasets:

  • Randomly Generated DAGs: 4,000 graphs (50 arguments, 75 attacks each) created via the Erdős–Rényi model to test performance on diverse structures.
  • SCG Benchmarks: 1,600 Singly-Connected Graphs with up to 2,000 attacks to verify the linearithmic scaling of Fast_SCG.

Results and Key Insights

The experimental results demonstrate a massive shift in computational feasibility:

  • Performance Leap: While the traditional Constellation method is estimated to take billions of years for a graph with 75 edges, Fast_DAG processed 99.84% of arguments in under one second.
  • Exactness vs. Approximation: When compared to Monte-Carlo approximations under the same time budget, Fast_DAG provided exact results while the approximation still suffered from a 38% average error.
  • Structural Efficiency: The paper proves that for acyclic graphs, local topology is sufficient for exact computation. The complexity of Fast_DAG is tied to the out-degree of dependent arguments rather than the total number of attacks, which is typically small in real-world debates.

Conclusion

This work provides a significant advancement in probabilistic argumentation by enabling exact, real-time evaluation of acyclic frameworks. While currently limited to graphs without cycles, the symbolic propagation method offers a promising foundation for future extensions to cyclic PrAFs and simultaneous computation of entire argument extensions.

Summary updated

BibTeX
@inproceedings{bistarelli2025fast,
  author = {Stefano Bistarelli and Victor David and Pierre Monnin and Francesco Santini and Carlo Taticchi},
  title = {{Fast Computing of Dung Semantics in Acyclic Probabilistic Argumentation Frameworks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i14.33622},
}
Figure