An Efficient Algorithm for Skeptical Preferred Acceptance in Dynamic Argumentation Frameworks

Gianvincenzo Alfano, Sergio Greco, Francesco ParisiIJCAI 2019 · DOI

TL;DR

This paper introduces SPA, an efficient algorithm for incrementally determining if an argument is skeptically accepted in dynamic argumentation frameworks (AFs). By focusing on a "context-based" subgraph and cleverly maintaining the ideal extension, SPA significantly speeds up computations compared to re-evaluating the entire framework from scratch, making it practical for real-world scenarios where arguments and attacks change frequently.

What Problem Does This Paper Address?

Abstract argumentation frameworks (AFs) are powerful tools for modeling disputes and reasoning about arguments. However, determining whether an argument is "skeptically accepted" (i.e., accepted in all possible valid interpretations of the arguments and their attacks) is computationally expensive, even for static frameworks. This problem becomes even more challenging in dynamic AFs, where arguments and attacks are constantly added or removed, reflecting evolving knowledge or ongoing debates. Existing research has largely focused on static AFs, leaving a significant gap in efficient methods for handling these dynamic changes, especially for skeptical acceptance under preferred semantics, which is notoriously complex.

Methods

The core of this paper is the development of the SPA (Skeptical Preferred Acceptance) algorithm, designed for incremental computation in dynamic AFs. SPA leverages two key ideas:

  • Supporting Set: The algorithm first identifies a "supporting set" of arguments. This set contains only those arguments whose acceptance status might change due to an update and could potentially influence the acceptance of a target argument. This drastically prunes the search space.
  • Context-Based AF: Based on the supporting set, a smaller, "context-based" AF is constructed. This context-based AF is a subgraph of the updated framework that is sufficient to determine the skeptical acceptance of the target argument. By solving the problem on this smaller subgraph, SPA avoids re-evaluating the entire, potentially massive, dynamic AF.
  • Incremental Ideal Extension Maintenance: SPA also incrementally maintains the "ideal extension" of the AF. The ideal extension is the largest admissible set contained within every preferred extension. This information acts as a shortcut, allowing SPA to quickly determine if the target argument's status is unaffected by the update. A simpler variant, SPA-base, is also presented, which omits the ideal extension maintenance to highlight the benefits of the context-based approach alone.

Datasets

The authors evaluated their approach using benchmarks from the DS-pr track of the ICCMA'17 competition. These datasets, A2 and A3, consist of abstract argumentation frameworks with varying numbers of arguments and attacks, ranging from tens to hundreds of thousands. The experiments involved randomly selecting updates and arguments from these existing benchmarks.

Key Insights and Ideas

  • Pruning is Paramount: The most significant insight is that not all arguments in a dynamic AF need to be re-evaluated after an update. By identifying a focused "supporting set" and constructing a "context-based AF," the computational burden can be dramatically reduced.
  • Ideal Extension as a Shortcut: Maintaining the ideal extension proves to be a valuable optimization. It allows for quick checks to see if an argument's status is unchanged, further accelerating the incremental computation.
  • Context Matters: The concept of a "context-based AF" is crucial. It demonstrates that a localized view of the framework, informed by the update and the target argument, is often sufficient for accurate reasoning, rather than a global re-analysis.
  • SPA vs. SPA-base Trade-off: The experiments reveal that while SPA (with ideal extension maintenance) is generally faster, SPA-base can sometimes perform better when the initial ideal extension is empty, suggesting a potential for adaptive strategies.

Key Results

The experimental evaluation demonstrated the effectiveness of SPA and SPA-base:

  • Significant Speedup: Both SPA and SPA-base consistently and significantly outperformed computing skeptical acceptance from scratch using ArgSemSAT, often by several orders of magnitude.
  • SPA Outperforms SPA-base: On average, SPA was faster than SPA-base, highlighting the benefit of incrementally maintaining the ideal extension.
  • Scalability: The improvements were observed across datasets with varying sizes, although the speedup decreased as the number of attacks increased, particularly when the AFs became denser.
  • Handling Multiple Updates: SPA showed strong performance even when dealing with multiple updates, whether applied simultaneously or sequentially, with simultaneous updates being faster.

Limitations and Future Work

The authors acknowledge a few limitations and suggest future directions:

  • Heuristics for SPA/SPA-base: Developing heuristics to dynamically choose between SPA and SPA-base based on the initial ideal extension could further optimize performance.
  • Extending to Sets of Arguments: The current algorithm focuses on a single argument. Future work could extend SPA to handle sets of arguments, leveraging the union of supporting sets.
  • Other Semantics: While SPA is directly applicable to semi-stable semantics, further investigation is needed to adapt it for other argumentation semantics like stable semantics.
  • Performance with Empty Ideal Extensions: The paper notes that SPA can be slower than SPA-base when the initial ideal extension is empty. Future work could explore ways to mitigate this.

Summary updated

BibTeX
@inproceedings{alfano2019efficient,
  author = {Gianvincenzo Alfano and Sergio Greco and Francesco Parisi},
  title = {{An Efficient Algorithm for Skeptical Preferred Acceptance in Dynamic Argumentation Frameworks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/3},
}
Figure