On Independence and SCC-Recursiveness in Assumption-Based Argumentation

Lydia Blümel, Anna Rapberger, Matthias Thimm, Francesca ToniIJCAI 2025 · DOI

Abstract

Assumption-Based Argumentation (ABA) is a prominent framework for structured AI reasoning. This paper formalizes the concept of conditional independence for ABA, providing a theoretical foundation for modular reasoning. Although exact determination of independence is computationally hard (ranging from $\Pi^P_2$-complete to $\Pi^P_3$-complete), the authors introduce polynomial-time methods leveraging Strongly Connected Components (SCCs) and a novel SCC-recursiveness property for ABA frameworks.

Introduction

In artificial intelligence, "independence" is a critical property that enables the decomposition of large knowledge bases into smaller, manageable components. While well-established in probabilistic models like Bayesian networks and abstract argumentation, independence has remained largely unaddressed in structured argumentation frameworks like Assumption-Based Argumentation (ABA). ABA builds arguments from basic assumptions and inference rules, making its internal structure more complex than purely abstract models. This paper bridges that gap by defining conditional independence in ABA and addressing the associated computational challenges.

Formalizing Independence in ABA

The authors define independence based on "labellings" — the assignment of assumptions as in, out, or undecided (und). Two sets of assumptions are considered independent if the possible labellings for one set do not restrict the possible labellings for the other, given some observed evidence.

Table 1: Labellings for various assumptions under different argumentation semantics (complete, grounded, preferred, stable).

As shown in the table above, different semantics (e.g., grounded vs. preferred) result in different sets of valid labellings. The paper proves that ABA independence satisfies the semi-graphoid axioms, aligning it logically with independence concepts in probability and database theory.

Complexity and SCC-Recursiveness

Determining independence exactly is computationally expensive. The authors map the complexity to the second and third levels of the polynomial hierarchy: $\Pi^P_2$-complete for complete and stable semantics, and $\Pi^P_3$-complete for preferred semantics. This high cost necessitates more efficient, albeit approximate, methods.

To address this, the paper introduces SCC-recursiveness to ABA. By decomposing an argumentation framework into its Strongly Connected Components (SCCs) — clusters of mutually dependent elements — reasoning can be performed locally. The authors demonstrate that standard ABA semantics are SCC-recursive, allowing for modular processing without losing global consistency.

Efficient Independence Checking: The d-Graph Approach

The authors propose two "sound but incomplete" polynomial-time algorithms to check independence:

  1. AF-based: Translating the ABA framework into an Abstract Framework (AF) and applying existing graph-based "d-separation" techniques.
  2. Native ABA: A more efficient method that operates directly on the ABA's dependency graph.
Figure 1: A complex dependency graph representing the internal structure of an ABA framework.

The "Native" approach is particularly powerful because it avoids the exponential blow-up often associated with converting structured ABA into abstract AFs. By handling "contraries" (negations of assumptions) separately, the native method can sometimes identify independencies that abstract translations overlook.

Conclusion and Future Work

This research provides the first formal treatment of independence in ABA, offering both theoretical proofs and practical algorithms. While the proposed d-graph methods are incomplete — meaning they might miss some independencies — they offer a massive speedup for large-scale systems. Future work includes extending these concepts to "non-flat" ABA frameworks and applying independence checks to tasks like information repair and forgetting in AI systems.

Summary updated

BibTeX
@inproceedings{blumel2025independence,
  author = {Lydia Blümel and Anna Rapberger and Matthias Thimm and Francesca Toni},
  title = {{On Independence and SCC-Recursiveness in Assumption-Based Argumentation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/488},
}
Figure