Quantitative Reasoning and Structural Complexity for Claim-Centric Argumentation

Johannes Klaus Fichte, Markus Hecher, Yasir Mahmood, Arne MeierIJCAI 2023 · DOI

TL;DR

This paper introduces a quantitative approach to reasoning in claim-centric argumentation frameworks (CAFs), moving beyond simple "accepted" or "rejected" claims to a nuanced "level of justification." They achieve this by developing novel graph representations and decomposition-guided reductions to Quantified Boolean Formulas (QBFs), leading to tight complexity bounds for reasoning problems parameterized by treewidth.

What Problem Does This Paper Address?

Traditional argumentation frameworks in AI deal with conflicting information by determining which arguments (and by extension, their claims) can be simultaneously accepted. However, these frameworks often present a binary outcome: a claim is either accepted or not. This can be too coarse for real-world scenarios where we might want to understand how strongly a claim is supported or how likely it is to be accepted. Existing work on Claim-Augmented Argumentation Frameworks (CAFs) addresses this by linking arguments to specific claims, but the reasoning still largely remains qualitative. The authors aim to bridge this gap by introducing quantitative reasoning for claims, allowing for a more granular understanding of justification, and to analyze the computational complexity of these new reasoning modes, particularly concerning the structural property of treewidth.

Methods

The core of the paper lies in introducing quantitative reasoning for claims within CAFs. This is achieved by:

  • Justification Status: Defining a quantitative measure for how many extensions support a particular claim. This allows for reasoning that falls between the extremes of credulous (at least one extension) and skeptical (all extensions) reasoning.
  • Graph Representations: Proposing new graph structures, specifically the extended primal graph (GCF), which explicitly models the relationship between arguments and their claims. This is crucial for capturing claim-centric information in a way that is amenable to structural analysis.
  • Decomposition-Guided (DG) Reductions: Leveraging DG reductions, a technique that maps reasoning problems on graphs with bounded treewidth to equivalent problems on Quantified Boolean Formulas (QBFs). This allows them to analyze the complexity of CAF reasoning problems by relating them to the well-studied complexity of QBFs.
  • Parameterization by Treewidth: Focusing on treewidth as a structural parameter. Treewidth is a measure of how "tree-like" a graph is, and it's known to be a powerful parameter for achieving fixed-parameter tractable (FPT) algorithms for many computational problems. They show that reasoning problems on CAFs can be solved efficiently when the treewidth of their extended primal graph is small.

Datasets

Not discussed in the paper. The paper focuses on theoretical contributions and complexity analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Beyond Binary Reasoning: The most significant insight is the move from binary acceptance/rejection of claims to a quantitative "level of justification." This offers a much richer understanding of argumentation, akin to probabilistic reasoning but grounded in the structure of argument extensions.
  • The Power of Extended Primal Graphs: The introduction of the extended primal graph is key. It effectively captures the claim-argument relationships, allowing for structural analysis (like treewidth) that was not possible with simpler graph representations of AFs.
  • Treewidth as a Tractability Lever: The paper reinforces the utility of treewidth as a parameter for achieving computational tractability in complex AI reasoning tasks. By reducing CAF reasoning problems to QBFs parameterized by treewidth, they can establish tight complexity bounds.
  • Quantitative Reasoning as a Generalization: The authors demonstrate that traditional credulous and skeptical reasoning can be seen as specific thresholds (e.g., probability ≥ 1 for credulous, probability = 1 for skeptical) within their proposed quantitative framework.

Key Results

  • Quantitative Reasoning Framework: The paper formally defines quantitative reasoning for claims in CAFs, enabling nuanced justification levels.
  • Tight Complexity Bounds: They establish tight fixed-parameter tractable (FPT) upper and lower bounds for quantitative reasoning problems in CAFs, parameterized by the treewidth of the extended primal graph. These bounds are expressed in terms of exponential functions of treewidth and polynomial functions of the input size.
  • DG Reductions to QBFs: Novel DG reductions are presented for various semantics (stable, admissible, complete, preferred) that map CAF reasoning problems to QBF validity problems, preserving treewidth.
  • Runtime Bounds: Specific runtime bounds are provided for counting extensions that fulfill claim assertions, showing that for constant-sized claim sets, the complexity matches that of skeptical reasoning. For arbitrary claim sets, the treewidth of the extended primal graph is shown to be necessary.

Limitations and Future Work

  • Focus on Specific Semantics: The paper primarily focuses on inherited semantics for CAFs and specific AF semantics (stable, admissible, complete, preferred). Future work could explore other semantics like semi-stable and stage semantics.
  • Practical Implementation: While theoretical bounds are established, the paper suggests that practical implementation of these DG reductions and treewidth-based algorithms would be an interesting avenue for future research.
  • Broader Parameter Space: The authors mention exploring stricter parameters for which results on QBFs have been obtained, suggesting potential for further theoretical advancements.
  • Applications of Quantitative Measures: They propose using the developed quantitative measures for navigating search spaces and providing capacities within extensions of CAFs, hinting at potential applications in areas like decision support or explanation generation.

Summary updated

BibTeX
@inproceedings{fichte2023quantitative,
  author = {Johannes Klaus Fichte and Markus Hecher and Yasir Mahmood and Arne Meier},
  title = {{Quantitative Reasoning and Structural Complexity for Claim-Centric Argumentation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/358},
}
Figure