---
_id: '59910'
abstract:
- lang: eng
  text: <jats:p>The connection between inconsistent databases and Dung’s abstract
    argumentation framework has recently drawn growing interest. Specifically, an
    inconsistent database, involving certain types of integrity constraints such as
    functional and inclusion dependencies, can be viewed as an argumentation framework
    in Dung’s setting. Nevertheless, no prior work has explored the exact expressive
    power of Dung’s theory of argumentation when compared to inconsistent databases
    and integrity constraints. In this paper, we close this gap by arguing that an
    argumentation framework can also be viewed as an inconsistent database. We first
    establish a connection between subset-repairs for databases and extensions for
    AFs considering conflict-free, naive, admissible, and preferred semantics. Further,
    we define a new family of attribute-based repairs based on the principle of maximal
    content preservation. The effectiveness of these repairs is then highlighted by
    connecting them to stable, semi-stable, and stage semantics. Our main contributions
    include translating an argumentation framework into a database together with integrity
    constraints. Moreover, this translation can be achieved in polynomial time, which
    is essential in transferring complexity results between the two formalisms.</jats:p>
author:
- first_name: Yasir
  full_name: Mahmood, Yasir
  id: '99353'
  last_name: Mahmood
- first_name: Markus
  full_name: Hecher, Markus
  last_name: Hecher
- first_name: Axel-Cyrille
  full_name: Ngonga Ngomo, Axel-Cyrille
  id: '65716'
  last_name: Ngonga Ngomo
citation:
  ama: 'Mahmood Y, Hecher M, Ngonga Ngomo A-C. Dung’s Argumentation Framework: Unveiling
    the Expressive Power with Inconsistent Databases. In: <i>Proceedings of the AAAI
    Conference on Artificial Intelligence</i>. Vol 39. Association for the Advancement
    of Artificial Intelligence (AAAI); 2025:15058-15066. doi:<a href="https://doi.org/10.1609/aaai.v39i14.33651">10.1609/aaai.v39i14.33651</a>'
  apa: 'Mahmood, Y., Hecher, M., &#38; Ngonga Ngomo, A.-C. (2025). Dung’s Argumentation
    Framework: Unveiling the Expressive Power with Inconsistent Databases. <i>Proceedings
    of the AAAI Conference on Artificial Intelligence</i>, <i>39</i>(14), 15058–15066.
    <a href="https://doi.org/10.1609/aaai.v39i14.33651">https://doi.org/10.1609/aaai.v39i14.33651</a>'
  bibtex: '@inproceedings{Mahmood_Hecher_Ngonga Ngomo_2025, title={Dung’s Argumentation
    Framework: Unveiling the Expressive Power with Inconsistent Databases}, volume={39},
    DOI={<a href="https://doi.org/10.1609/aaai.v39i14.33651">10.1609/aaai.v39i14.33651</a>},
    number={14}, booktitle={Proceedings of the AAAI Conference on Artificial Intelligence},
    publisher={Association for the Advancement of Artificial Intelligence (AAAI)},
    author={Mahmood, Yasir and Hecher, Markus and Ngonga Ngomo, Axel-Cyrille}, year={2025},
    pages={15058–15066} }'
  chicago: 'Mahmood, Yasir, Markus Hecher, and Axel-Cyrille Ngonga Ngomo. “Dung’s
    Argumentation Framework: Unveiling the Expressive Power with Inconsistent Databases.”
    In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, 39:15058–66.
    Association for the Advancement of Artificial Intelligence (AAAI), 2025. <a href="https://doi.org/10.1609/aaai.v39i14.33651">https://doi.org/10.1609/aaai.v39i14.33651</a>.'
  ieee: 'Y. Mahmood, M. Hecher, and A.-C. Ngonga Ngomo, “Dung’s Argumentation Framework:
    Unveiling the Expressive Power with Inconsistent Databases,” in <i>Proceedings
    of the AAAI Conference on Artificial Intelligence</i>, 2025, vol. 39, no. 14,
    pp. 15058–15066, doi: <a href="https://doi.org/10.1609/aaai.v39i14.33651">10.1609/aaai.v39i14.33651</a>.'
  mla: 'Mahmood, Yasir, et al. “Dung’s Argumentation Framework: Unveiling the Expressive
    Power with Inconsistent Databases.” <i>Proceedings of the AAAI Conference on Artificial
    Intelligence</i>, vol. 39, no. 14, Association for the Advancement of Artificial
    Intelligence (AAAI), 2025, pp. 15058–66, doi:<a href="https://doi.org/10.1609/aaai.v39i14.33651">10.1609/aaai.v39i14.33651</a>.'
  short: 'Y. Mahmood, M. Hecher, A.-C. Ngonga Ngomo, in: Proceedings of the AAAI Conference
    on Artificial Intelligence, Association for the Advancement of Artificial Intelligence
    (AAAI), 2025, pp. 15058–15066.'
date_created: 2025-05-15T11:05:36Z
date_updated: 2026-02-20T10:07:00Z
department:
- _id: '574'
doi: 10.1609/aaai.v39i14.33651
intvolume: '        39'
issue: '14'
language:
- iso: eng
page: 15058-15066
project:
- _id: '121'
  name: 'TRR 318; TP B01: Ein dialogbasierter Ansatz zur Erklärung von Modellen des
    maschinellen Lernens'
publication: Proceedings of the AAAI Conference on Artificial Intelligence
publication_identifier:
  issn:
  - 2374-3468
  - 2159-5399
publication_status: published
publisher: Association for the Advancement of Artificial Intelligence (AAAI)
status: public
title: 'Dung’s Argumentation Framework: Unveiling the Expressive Power with Inconsistent
  Databases'
type: conference
user_id: '99353'
volume: 39
year: '2025'
...
---
_id: '53073'
abstract:
- lang: eng
  text: While shallow decision trees may be interpretable, larger ensemble models
    like gradient-boosted trees, which often set the state of the art in machine learning
    problems involving tabular data, still remain black box models. As a remedy, the
    Shapley value (SV) is a well-known concept in explainable artificial intelligence
    (XAI) research for quantifying additive feature attributions of predictions. The
    model-specific TreeSHAP methodology solves the exponential complexity for retrieving
    exact SVs from tree-based models. Expanding beyond individual feature attribution,
    Shapley interactions reveal the impact of intricate feature interactions of any
    order. In this work, we present TreeSHAP-IQ, an efficient method to compute any-order
    additive Shapley interactions for predictions of tree-based models. TreeSHAP-IQ
    is supported by a mathematical framework that exploits polynomial arithmetic to
    compute the interaction scores in a single recursive traversal of the tree, akin
    to Linear TreeSHAP. We apply TreeSHAP-IQ on state-of-the-art tree ensembles and
    explore interactions on well-established benchmark datasets.
author:
- first_name: Maximilian
  full_name: Muschalik, Maximilian
  last_name: Muschalik
- first_name: Fabian
  full_name: Fumagalli, Fabian
  id: '93420'
  last_name: Fumagalli
- first_name: Barbara
  full_name: Hammer, Barbara
  last_name: Hammer
- first_name: Eyke
  full_name: Huellermeier, Eyke
  id: '48129'
  last_name: Huellermeier
citation:
  ama: 'Muschalik M, Fumagalli F, Hammer B, Huellermeier E. Beyond TreeSHAP: Efficient
    Computation of Any-Order Shapley Interactions for Tree Ensembles. In: <i>Proceedings
    of the AAAI Conference on Artificial Intelligence (AAAI)</i>. Vol 38. ; 2024:14388-14396.
    doi:<a href="https://doi.org/10.1609/aaai.v38i13.29352">10.1609/aaai.v38i13.29352</a>'
  apa: 'Muschalik, M., Fumagalli, F., Hammer, B., &#38; Huellermeier, E. (2024). Beyond
    TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles.
    <i>Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)</i>, <i>38</i>(13),
    14388–14396. <a href="https://doi.org/10.1609/aaai.v38i13.29352">https://doi.org/10.1609/aaai.v38i13.29352</a>'
  bibtex: '@inproceedings{Muschalik_Fumagalli_Hammer_Huellermeier_2024, title={Beyond
    TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles},
    volume={38}, DOI={<a href="https://doi.org/10.1609/aaai.v38i13.29352">10.1609/aaai.v38i13.29352</a>},
    number={13}, booktitle={Proceedings of the AAAI Conference on Artificial Intelligence
    (AAAI)}, author={Muschalik, Maximilian and Fumagalli, Fabian and Hammer, Barbara
    and Huellermeier, Eyke}, year={2024}, pages={14388–14396} }'
  chicago: 'Muschalik, Maximilian, Fabian Fumagalli, Barbara Hammer, and Eyke Huellermeier.
    “Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for
    Tree Ensembles.” In <i>Proceedings of the AAAI Conference on Artificial Intelligence
    (AAAI)</i>, 38:14388–96, 2024. <a href="https://doi.org/10.1609/aaai.v38i13.29352">https://doi.org/10.1609/aaai.v38i13.29352</a>.'
  ieee: 'M. Muschalik, F. Fumagalli, B. Hammer, and E. Huellermeier, “Beyond TreeSHAP:
    Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles,” in
    <i>Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)</i>, 2024,
    vol. 38, no. 13, pp. 14388–14396, doi: <a href="https://doi.org/10.1609/aaai.v38i13.29352">10.1609/aaai.v38i13.29352</a>.'
  mla: 'Muschalik, Maximilian, et al. “Beyond TreeSHAP: Efficient Computation of Any-Order
    Shapley Interactions for Tree Ensembles.” <i>Proceedings of the AAAI Conference
    on Artificial Intelligence (AAAI)</i>, vol. 38, no. 13, 2024, pp. 14388–96, doi:<a
    href="https://doi.org/10.1609/aaai.v38i13.29352">10.1609/aaai.v38i13.29352</a>.'
  short: 'M. Muschalik, F. Fumagalli, B. Hammer, E. Huellermeier, in: Proceedings
    of the AAAI Conference on Artificial Intelligence (AAAI), 2024, pp. 14388–14396.'
date_created: 2024-03-27T14:50:04Z
date_updated: 2025-09-11T16:20:11Z
department:
- _id: '660'
doi: 10.1609/aaai.v38i13.29352
intvolume: '        38'
issue: '13'
keyword:
- Explainable Artificial Intelligence
language:
- iso: eng
page: 14388-14396
project:
- _id: '126'
  name: 'TRR 318 - C3: TRR 318 - Subproject C3'
- _id: '109'
  name: 'TRR 318: TRR 318 - Erklärbarkeit konstruieren'
- _id: '117'
  name: 'TRR 318 - C: TRR 318 - Project Area C'
publication: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)
publication_identifier:
  issn:
  - 2374-3468
  - 2159-5399
publication_status: published
status: public
title: 'Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for
  Tree Ensembles'
type: conference
user_id: '93420'
volume: 38
year: '2024'
...
---
_id: '45841'
abstract:
- lang: eng
  text: "<jats:p>Logic-based argumentation is a well-established formalism modeling
    nonmonotonic reasoning. It has been playing a major role in AI for decades, now.
    \ Informally, a set of formulas is the support for a given claim if it is consistent,
    subset-minimal, and implies the claim. In such a case, the pair of the support
    and the claim together is called an argument. In this paper, we study the propositional
    variants of the following three computational tasks studied in argumentation:
    ARG (exists a support for a given claim with respect to a given set of formulas),
    ARG-Check (is a given set a support for a given claim), and ARG-Rel (similarly
    as ARG plus requiring an additionally given formula to be contained in the support).
    ARG-Check is complete for the complexity class DP, and the other two problems
    are known to be complete for the second level of the polynomial hierarchy and,
    accordingly, are highly intractable. Analyzing the reason for this intractability,
    we perform a two-dimensional classification: first, we consider all possible propositional
    fragments of the problem within Schaefer's framework, and then study different
    parameterizations for each of the fragment.\r\nWe identify a list of reasonable
    structural parameters (size of the claim, support, knowledge-base) that are connected
    to the aforementioned decision problems. Eventually, we thoroughly draw a fine
    border of parameterized intractability for each of the problems showing where
    the problems are fixed-parameter tractable and when this exactly stops. Surprisingly,
    several cases are of very high intractability (paraNP and beyond).</jats:p>"
author:
- first_name: Yasir
  full_name: Mahmood, Yasir
  id: '99353'
  last_name: Mahmood
- first_name: Arne
  full_name: Meier, Arne
  last_name: Meier
- first_name: Johannes
  full_name: Schmidt, Johannes
  last_name: Schmidt
citation:
  ama: 'Mahmood Y, Meier A, Schmidt J. Parameterized Complexity of Logic-Based Argumentation
    in Schaefer’s Framework. In: <i>Proceedings of the AAAI Conference on Artificial
    Intelligence</i>. Vol 35. Association for the Advancement of Artificial Intelligence
    (AAAI); 2021:6426-6434. doi:<a href="https://doi.org/10.1609/aaai.v35i7.16797">10.1609/aaai.v35i7.16797</a>'
  apa: Mahmood, Y., Meier, A., &#38; Schmidt, J. (2021). Parameterized Complexity
    of Logic-Based Argumentation in Schaefer’s Framework. <i>Proceedings of the AAAI
    Conference on Artificial Intelligence</i>, <i>35</i>(7), 6426–6434. <a href="https://doi.org/10.1609/aaai.v35i7.16797">https://doi.org/10.1609/aaai.v35i7.16797</a>
  bibtex: '@inproceedings{Mahmood_Meier_Schmidt_2021, title={Parameterized Complexity
    of Logic-Based Argumentation in Schaefer’s Framework}, volume={35}, DOI={<a href="https://doi.org/10.1609/aaai.v35i7.16797">10.1609/aaai.v35i7.16797</a>},
    number={7}, booktitle={Proceedings of the AAAI Conference on Artificial Intelligence},
    publisher={Association for the Advancement of Artificial Intelligence (AAAI)},
    author={Mahmood, Yasir and Meier, Arne and Schmidt, Johannes}, year={2021}, pages={6426–6434}
    }'
  chicago: Mahmood, Yasir, Arne Meier, and Johannes Schmidt. “Parameterized Complexity
    of Logic-Based Argumentation in Schaefer’s Framework.” In <i>Proceedings of the
    AAAI Conference on Artificial Intelligence</i>, 35:6426–34. Association for the
    Advancement of Artificial Intelligence (AAAI), 2021. <a href="https://doi.org/10.1609/aaai.v35i7.16797">https://doi.org/10.1609/aaai.v35i7.16797</a>.
  ieee: 'Y. Mahmood, A. Meier, and J. Schmidt, “Parameterized Complexity of Logic-Based
    Argumentation in Schaefer’s Framework,” in <i>Proceedings of the AAAI Conference
    on Artificial Intelligence</i>, 2021, vol. 35, no. 7, pp. 6426–6434, doi: <a href="https://doi.org/10.1609/aaai.v35i7.16797">10.1609/aaai.v35i7.16797</a>.'
  mla: Mahmood, Yasir, et al. “Parameterized Complexity of Logic-Based Argumentation
    in Schaefer’s Framework.” <i>Proceedings of the AAAI Conference on Artificial
    Intelligence</i>, vol. 35, no. 7, Association for the Advancement of Artificial
    Intelligence (AAAI), 2021, pp. 6426–34, doi:<a href="https://doi.org/10.1609/aaai.v35i7.16797">10.1609/aaai.v35i7.16797</a>.
  short: 'Y. Mahmood, A. Meier, J. Schmidt, in: Proceedings of the AAAI Conference
    on Artificial Intelligence, Association for the Advancement of Artificial Intelligence
    (AAAI), 2021, pp. 6426–6434.'
date_created: 2023-07-03T11:34:49Z
date_updated: 2024-06-04T15:59:46Z
doi: 10.1609/aaai.v35i7.16797
intvolume: '        35'
issue: '7'
keyword:
- General Medicine
language:
- iso: eng
page: 6426-6434
publication: Proceedings of the AAAI Conference on Artificial Intelligence
publication_identifier:
  issn:
  - 2374-3468
  - 2159-5399
publication_status: published
publisher: Association for the Advancement of Artificial Intelligence (AAAI)
status: public
title: Parameterized Complexity of Logic-Based Argumentation in Schaefer's Framework
type: conference
user_id: '99353'
volume: 35
year: '2021'
...