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.
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.
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_DAGprocessed 99.84% of arguments in under one second. - Exactness vs. Approximation: When compared to Monte-Carlo approximations under the same time budget,
Fast_DAGprovided 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_DAGis 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