Research map / Learning theory and algorithms / Combinatorial and search optimization
Fast Computing of Dung Semantics in Acyclic Probabilistic Argumentation Frameworks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Fast SCG and Fast DAG algorithms that compute exact argument acceptance probabilities under Dung semantics in probabilistic (Constellation) argumentation frameworks on singly-connected graphs and DAGs, far faster than exact Constellation and Monte-Carlo.
Problem
Computing the probability that an argument is accepted in probabilistic abstract argumentation under the Constellation paradigm is exponential in the number of attacks, which limits scalability; prior exact methods are exponential and approximate Monte-Carlo methods are inexact.
Approach
Local probability propagation from roots to the target argument over the attack graph: for trees/SCGs a linearithmic order-based propagation, and for DAGs a symbolic expansion of dependent arguments with an idempotent multiplicative operator that removes repeated powers, yielding exact values with complexity linearithmic in the product of out-degrees of dependent arguments.
Key results
- Fast DAG computes 99.84% of arguments in under 1 second on 50-argument DAGs, versus Constellation doubling runtime per added edge (about 8,000 s at 30 edges).
- Monte-Carlo given the same time budget as Fast DAG has an average error of 38% (average absolute difference 0.15).
- Fast SCG runs in O(n log n) and Fast DAG matches Constellation exactly (Theorem 5).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Fast DAG instead of enumerating possible worlds with Constellation | Exact acceptance-probability computation on DAGs · Random DAGs (4,000 graphs, 50 arguments and 75 attacks) | runtime | Helped |
| Use Fast DAG instead of Monte-Carlo with an equal time budget | Acceptance-probability computation on DAGs · Random DAGs (1,000 graphs, 50 arguments each) | approximation error percentage: around 38% | Helped |
Surprising findings
- About 25% of Monte-Carlo approximations (12,300) could not run at all because Fast DAG finished too quickly.
Limitations
- Results are for acyclic PrAFs only; cyclic frameworks are not handled.
- Fast DAG uses SageMath symbolic computation, whose worst case can still be costly (up to ~10,000 s for some arguments).
- Focuses on grounded semantics, with equivalence to other Dung semantics only holding on DAGs/SCGs.
Experimental setup
Datasets: 4,000 random Erdős–Rényi DAGs (50 arguments, 75 attacks) random singly-connected graphs with 500-2000 attacks
Benchmarks: random DAG testbed (4,000 graphs) random SCG testbed (1,600 graphs)
Metrics: runtime absolute error of Monte-Carlo approximation time complexity growth
Baselines: Constellation method Monte-Carlo approximation Fast SCG on DAGs
Builds on: Constellation Dung argumentation frameworks Monte-Carlo probabilistic argumentation (Li, Oren, Norman 2011) Bistarelli et al. 2022 linear-time grounded computation
Closest papers by meaning
- Redefining ABA+ Semantics via Abstract Set-to-Set Attacks (AAAI 2024 · similarity 0.86)
- Bilateral Gradual Semantics for Weighted Argumentation (AAAI 2024 · similarity 0.85)
- DAG-Math: Graph-Guided Mathematical Reasoning in LLMs (ICLR 2026 · similarity 0.84)
- Complexity of Credulous and Skeptical Acceptance in Epistemic Argumentation Framework (AAAI 2024 · similarity 0.84)
- Argumentative Large Language Models for Explainable and Contestable Claim Verification (AAAI 2025 · similarity 0.84)
- Non-flat ABA Is an Instance of Bipolar Argumentation (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.