Optimisation and Approximation in Abstract Argumentation: The Case of Stable Semantics

Matthias ThimmIJCAI 2024

Introduction: Softening Logic for Real-World Argumentation

Abstract Argumentation Frameworks (AAFs) are a cornerstone of AI reasoning, modeling arguments as nodes in a graph and "attacks" as directed edges. Traditionally, researchers seek "stable extensions"—sets of arguments that are internally consistent (conflict-free) and collectively defeat all external arguments.

An example of an Abstract Argumentation Framework (AAF) where nodes represent arguments and directed edges represent attacks.

However, stable extensions are often non-existent in complex, real-world graphs. This paper addresses the need for graded or "soft" semantics. Instead of an all-or-nothing approach, the authors introduce measures of how close a set of arguments is to being stable, allowing for the ranking of arguments even when perfect consistency is impossible.

Quantitative Relaxations and Heuristics

The authors propose two primary optimization problems to handle these scenarios:

  1. MAXSTABLE: Seeks a conflict-free set that attacks the maximum number of external arguments (referred to as $k$-stable).
  2. MAXSTABLE: Seeks a set that covers all arguments (full-range) while minimizing internal conflicts (referred to as $k$-stable).

To solve these, four greedy heuristic algorithms were developed: GCF (Growing Conflict-Free) and SCF (Shrinking Conflict-Free) for MAXSTABLE, and GFR and SFR for MAXSTABLE*. These heuristics aim to provide fast, near-optimal solutions where exact solvers might struggle.

Theoretical Hardness vs. Empirical Success

Theoretically, these optimization problems are highly complex ($FP^{NP[\log]}$-complete) and difficult to approximate (Poly-APX-complete). This suggests that in the worst case, finding a good approximation is as hard as solving the classic Independent Set problem.

Despite these grim theoretical bounds, empirical testing on benchmarks from the International Competition on Computational Models of Argumentation (ICCMA) tells a different story.

Performance comparison of optimal solvers (OPT) and greedy heuristics (GCF, SCF, GFR, SFR) on ICCMA benchmark datasets.

Key Results

The greedy heuristics demonstrated remarkable accuracy and efficiency across thousands of instances from the ICCMA17 and ICCMA19 competitions:

  • Accuracy: The heuristics achieved surprisingly high approximation ratios (AR). For MAXSTABLE, the GCF algorithm achieved an average AR of 0.964 on the ICCMA17-B dataset. For MAXSTABLE, the SFR algorithm reached an AR of 0.984*.
  • Efficiency: Heuristics were significantly faster than optimal MaxSAT-based solvers. As shown in the results table, optimal solvers (OPT/OPT*) suffered from over 700 timeouts (#TO) on ICCMA17-B, whereas the greedy approaches had minimal to zero timeouts.

Conclusion

This work bridges the gap between qualitative logic and quantitative optimization. While the theoretical complexity is high, the practical performance of simple greedy algorithms suggests that real-world argumentation structures are more amenable to approximation than mathematical worst cases suggest. Future research will look to extend these "soft" semantics to other frameworks like admissible and preferred semantics.

Summary updated

BibTeX
@inproceedings{thimm2024optimisation,
  author = {Matthias Thimm},
  title = {{Optimisation and Approximation in Abstract Argumentation: The Case of Stable Semantics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure