pith. sign in

arxiv: 2606.25103 · v1 · pith:MIG43M5Jnew · submitted 2026-06-23 · 💻 cs.AI

Beyond Shapley: Efficient Computation of Asymmetric Shapley Values

Ezequiel Companeetz , Santiago Cifuentes , Sergio Abriola This is my paper

Pith reviewed 2026-06-25 22:54 UTC · model grok-4.3

classification 💻 cs.AI
keywords asymmetric shapley valuescausal graphsfeature attributiontopological orderingspolynomial time algorithmsexplainable AIdirected treesapproximation algorithms
0
0 comments X

The pith

Asymmetric Shapley values can be computed exactly in polynomial time when the causal graph is a rooted directed tree.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that asymmetric Shapley values incorporate causal knowledge through a given graph to produce model explanations. It demonstrates that exact ASV computation runs in polynomial time in settings where standard Shapley values are #P-hard. The key step is defining equivalence classes over topological orderings to avoid enumerating all orderings. A dedicated algorithm achieves this polynomial bound precisely when the causal graph is a rooted directed tree. An approximation procedure extends the approach to general causal DAGs via uniform sampling of orderings.

Core claim

The paper claims that in certain contexts in which the computation of SHAP is #P-hard, the exact computation of ASV can be done in polynomial time. Equivalence classes over the topological orderings of the underlying causal graph reduce the time needed. A polynomial-time algorithm in the number of equivalence classes computes ASV whenever the causal graph is a rooted directed tree. A separate sampling-based algorithm approximates ASV on arbitrary causal DAGs.

What carries the argument

Equivalence classes over topological orderings of the causal graph, which group permitted orderings to allow summation over representatives instead of all permutations.

If this is right

  • Exact ASV computation becomes feasible without exponential enumeration when the causal graph is a rooted directed tree.
  • Computation time scales with the number of equivalence classes rather than the full set of topological orderings.
  • Approximation of ASV remains available for general DAGs through uniform random sampling of topological orderings.
  • Causal feature attributions avoid the hardness barrier of standard Shapley values in tree-structured cases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The equivalence-class reduction may extend to other acyclic graph families if similar partitions can be identified efficiently.
  • Practitioners could adopt ASV over SHAP when a tree causal graph is available and exact values are required.
  • Improved sampling routines for topological orderings would directly tighten the approximation guarantees for non-tree DAGs.

Load-bearing premise

The causal graph is supplied as input and correctly encodes the permitted feature orderings with equivalence classes computable at low additional cost.

What would settle it

A rooted directed tree causal graph on n features where the algorithm requires time super-polynomial in n would falsify the polynomial-time claim.

Figures

Figures reproduced from arXiv: 2606.25103 by Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola.

Figure 1
Figure 1. Figure 1: Examples of Bayesian network structures. [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Graph partition into ancestors, descendants and unrelated nodes with respect to [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of the first step of the sampling algorithm. The candidate source [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
read the original abstract

We address the problem of explainability in machine learning models through feature attribution methods. In particular, we consider a variant of Shapley values known as Asymmetric Shapley Values (ASV), which enables the incorporation of causal knowledge into model-agnostic explanations through the use of a causal graph. We show that in certain contexts in which the computation of SHAP is $\#P$-hard, the exact computation of ASV can be done in polynomial time. To extend this algorithmic result, we introduce a notion of equivalence classes over the topological orderings of the underlying causal graph, which is useful to reduce the time to compute ASV. In particular, we present a polynomial-time algorithm (in the number of equivalence classes) to compute it whenever the causal graph is a rooted directed tree. Finally, we develop an algorithm for approximating ASV in arbitrary causal DAGs which relies on a procedure to sample topological orderings uniformly at random. To implement this sampling mechanism we leverage known algorithms as well as simpler alternatives. Our experimental results demonstrate the practical viability of the proposed approach in realistic causal structures.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper addresses efficient computation of Asymmetric Shapley Values (ASV) that incorporate causal knowledge via a given DAG. It claims that ASV admits exact polynomial-time computation in certain settings where standard SHAP is #P-hard; introduces equivalence classes over topological orderings to reduce computation; gives a polynomial-time algorithm (in the number of equivalence classes) for rooted directed trees; and presents a sampling-based approximation algorithm for general DAGs that relies on uniform sampling of topological orderings. Experimental results are asserted to demonstrate practicality.

Significance. If the complexity claims and sampling procedure hold, the work would offer a concrete algorithmic route to causality-aware explanations that remains tractable precisely where Shapley-value computation is intractable, together with a reusable sampling primitive for topological orderings. The equivalence-class reduction and the tree-specific algorithm constitute the primary technical contributions.

major comments (2)
  1. [Abstract] Abstract: the opening claim that 'in certain contexts in which the computation of SHAP is #P-hard, the exact computation of ASV can be done in polynomial time' is not accompanied by an explicit statement of the graph families or parameter regimes under which the polynomial bound holds. The subsequent sentence qualifies the rooted-tree result as polynomial 'in the number of equivalence classes,' yet no argument is supplied that this number is itself polynomial in |V| for arbitrary rooted trees (e.g., high-branching trees or disjoint subtrees).
  2. [rooted directed tree algorithm section] Section introducing the rooted-tree algorithm (presumably §4 or §5): the reduction to equivalence classes is presented as yielding a polynomial-time procedure, but the manuscript does not exhibit a direct poly-time enumeration or dynamic-programming procedure that avoids explicit enumeration of the classes. Without such a bound or algorithm, the claimed contrast with #P-hardness of SHAP does not transfer unconditionally to all rooted directed trees.
minor comments (2)
  1. [experiments] The experimental section asserts 'practical viability' but provides no quantitative comparison of running times against exact SHAP or against the number of equivalence classes; a table or plot relating runtime to |V| and number of classes would strengthen the claim.
  2. [equivalence classes definition] Notation for the equivalence relation on topological orderings is introduced without an explicit definition of the equivalence predicate; a short formal definition would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful review and for highlighting the need to clarify the precise conditions under which our polynomial-time claims hold. We will revise the abstract and the relevant section to make the dependence on the number of equivalence classes explicit. Our responses to the major comments follow.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the opening claim that 'in certain contexts in which the computation of SHAP is #P-hard, the exact computation of ASV can be done in polynomial time' is not accompanied by an explicit statement of the graph families or parameter regimes under which the polynomial bound holds. The subsequent sentence qualifies the rooted-tree result as polynomial 'in the number of equivalence classes,' yet no argument is supplied that this number is itself polynomial in |V| for arbitrary rooted trees (e.g., high-branching trees or disjoint subtrees).

    Authors: We agree that the abstract should state the regimes more explicitly. The phrase 'certain contexts' is meant to cover rooted directed trees in which the number of topological equivalence classes is polynomial in |V|. This does not hold for every possible rooted tree (for instance, a star with many leaves can induce a superpolynomial number of classes). We will revise the abstract to read that the polynomial-time result applies to rooted directed trees whenever the number of equivalence classes is polynomial in the number of nodes. This qualification aligns with the body of the paper and does not change the technical contribution. revision: yes

  2. Referee: [rooted directed tree algorithm section] Section introducing the rooted-tree algorithm (presumably §4 or §5): the reduction to equivalence classes is presented as yielding a polynomial-time procedure, but the manuscript does not exhibit a direct poly-time enumeration or dynamic-programming procedure that avoids explicit enumeration of the classes. Without such a bound or algorithm, the claimed contrast with #P-hardness of SHAP does not transfer unconditionally to all rooted directed trees.

    Authors: The manuscript states that the algorithm runs in time polynomial in the number of equivalence classes; we do not claim an unconditional polynomial bound in |V| for arbitrary rooted trees. Because the number of classes can be exponential, no such unconditional claim is made or supported. The contrast with SHAP therefore applies precisely in the regimes where the number of classes remains small. We will add a short paragraph in the tree-algorithm section noting that the running time is parameterized by the number of classes and briefly discussing when this number is expected to be polynomial (e.g., trees with limited branching or strong causal ordering). We do not currently provide a DP that bypasses class enumeration, as our focus is the equivalence-class reduction itself. revision: partial

Circularity Check

0 steps flagged

No circularity in derivation; claims rest on independent graph algorithms

full rationale

The paper's core results are algorithmic constructions for ASV computation on causal graphs, specifically a poly-time procedure (in equivalence classes) for rooted directed trees and a sampling method for general DAGs. No quoted steps reduce by definition to fitted parameters, self-citations, or ansatzes; the equivalence-class reduction and topological-order sampling are presented as explicit graph-theoretic procedures rather than tautological renamings or self-referential fits. The poly-time claim is qualified by the number of classes, but this does not constitute circularity under the enumerated patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the assumption that a correct causal DAG is supplied and that topological orderings can be enumerated or sampled efficiently; no free parameters, invented entities, or additional axioms beyond standard graph theory are introduced in the abstract.

axioms (2)
  • domain assumption A causal graph is provided that correctly restricts the allowed feature orderings for ASV.
    Invoked when stating that ASV incorporates causal knowledge through the graph.
  • domain assumption Topological orderings of the graph exist and can be grouped into equivalence classes whose number is polynomial for trees.
    Required for the polynomial-time claim on rooted directed trees.

pith-pipeline@v0.9.1-grok · 5719 in / 1402 out tokens · 19224 ms · 2026-06-25T22:54:33.103736+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 4 canonical work pages

  1. [1]

    Classics in game theory , year=

    A value for n-person games , author=. Classics in game theory , year=

  2. [2]

    Ieee Access , volume=

    Fryer, Daniel and Str. Ieee Access , volume=. 2021 , publisher=

    2021

  3. [3]

    The inadequacy of

    Huang, Xuanxiang and Marques-Silva, Joao , journal=. The inadequacy of

  4. [4]

    Reasoning Web

    Logic-based explainability in machine learning , author=. Reasoning Web. Causality, Explanations and Declarative Knowledge: 18th International Summer School 2022, Berlin, Germany, September 27--30, 2022, Tutorial Lectures , pages=. 2023 , publisher=

    2022

  5. [5]

    From local explanations to global understanding with explainable

    Lundberg, Scott M and Erion, Gabriel and Chen, Hugh and DeGrave, Alex and Prutkin, Jordan M and Nair, Bala and Katz, Ronit and Himmelfarb, Jonathan and Bansal, Nisha and Lee, Su-In , journal=. From local explanations to global understanding with explainable. 2020 , publisher=

    2020

  6. [6]

    The tractability of

    Arenas, Marcelo and Barcel. The tractability of. Proceedings of the AAAI Conference on

  7. [7]

    On the tractability of

    Van den Broeck, Guy and Lykov, Anton and Schleich, Maximilian and Suciu, Dan , journal=. On the tractability of

  8. [8]

    On the complexity of

    Arenas, Marcelo and Barcel. On the complexity of. Journal of Machine Learning Research , volume=

  9. [9]

    Asymmetric

    Frye, Christopher and Rowat, Colin and Feige, Ilya , journal=. Asymmetric

  10. [10]

    Artificial Intelligence , volume=

    Fusion, Propagation, and Structuring in Belief Networks , author=. Artificial Intelligence , volume=. 1986 , publisher=

    1986

  11. [11]

    Cooper , title =

    Gregory F. Cooper , title =. Artificial Intelligence , volume =. 1990 , doi =

    1990

  12. [12]

    arXiv preprint arXiv:2411.04872 , year=

    Frontiermath: A benchmark for evaluating advanced mathematical reasoning in ai , author=. arXiv preprint arXiv:2411.04872 , year=

    Pith/arXiv arXiv

  13. [13]

    2024 , eprint=

    Emergent World Representations: Exploring a Sequence Model Trained on a Synthetic Task , author=. 2024 , eprint=

    2024

  14. [14]

    2022 , subtitle=

    Interpretable Machine Learning , author =. 2022 , subtitle=

    2022

  15. [15]

    2009 , publisher =

    Probabilistic Graphical Models : Principles and Techniques , author =. 2009 , publisher =

    2009

  16. [16]

    2017 , eprint=

    A Unified Approach to Interpreting Model Predictions , author=. 2017 , eprint=

    2017

  17. [17]

    Brightwell and Peter Winkler , title=

    Graham R. Brightwell and Peter Winkler , title=. Order , volume =. 1991 , doi =

    1991

  18. [18]

    Adnda Darwiche , title=

  19. [19]

    Poole , year=

    Nevin Lianwen Zhang and David L. Poole , year=. A simple approach to

  20. [20]

    1990 , url=

    Triangulation of Graphs : Algorithms Giving Small Total State Space Triangulation of Graphs Algorithms Giving Small Total State Space , author=. 1990 , url=

    1990

  21. [21]

    2018 , eprint=

    Exact and approximate inference in graphical models: variable elimination and beyond , author=. 2018 , eprint=

    2018

  22. [22]

    Kahn, A. B. , title=. 1962 , issue_date =. doi:10.1145/368996.369025 , journal =

    work page doi:10.1145/368996.369025 1962

  23. [23]

    Knuth and Jayme L

    Donald E. Knuth and Jayme L. Szwarcfiter , keywords =. A structured program to generate all topological sorting arrangements , journal =. 1974 , issn =. doi:https://doi.org/10.1016/0020-0190(74)90001-5 , url =

    work page doi:10.1016/0020-0190(74)90001-5 1974

  24. [24]

    and Nicholson, Ann E

    Korb, Kevin B. and Nicholson, Ann E. , year=

  25. [25]

    and Dawid, A

    Spiegelhalter, David J. and Dawid, A. Philip and Lauritzen, Steffen L. and Cowell, Robert G. , journal=. 1993 , publisher=

    1993

  26. [26]

    An Efficient Method for Indexing All Topological Orders of a Directed Graph

    Inoue, Yuma and Minato, Shin-ichi. An Efficient Method for Indexing All Topological Orders of a Directed Graph. Algorithms and Computation. 2014

    2014

  27. [27]

    2024 , month =

    Data on Large-Scale. 2024 , month =

    2024

  28. [28]

    Explanation in Artificial Intelligence:

    Tim Miller , keywords =. Explanation in. Artificial Intelligence , volume =. 2019 , issn =. doi:https://doi.org/10.1016/j.artint.2018.07.007 , url =

    work page doi:10.1016/j.artint.2018.07.007 2019

  29. [29]

    2017 , eprint=

    The Mythos of Model Interpretability , author=. 2017 , eprint=

    2017

  30. [30]

    On the Computational Tractability of the (Many)

    Reda Marzouk and Shahaf Bassan and Guy Katz and Colin de la Higuera , year=. On the Computational Tractability of the (Many). 2502.12295 , archivePrefix=

    arXiv

  31. [31]

    2017 , institution =

    Dua, Dheeru and Graff, Casey , title=. 2017 , institution =

    2017

  32. [32]

    On the Tractability of

    Reda Marzouk and Colin de La Higuera , year=. On the Tractability of. 2405.02936 , archivePrefix=

    arXiv

  33. [33]

    2021 , eprint=

    On the Explanatory Power of Decision Trees , author=. 2021 , eprint=

    2021

  34. [34]

    Fast perfect sampling from linear extensions , journal =

    Mark Huber , keywords =. Fast perfect sampling from linear extensions , journal =. 2006 , issn =. doi:https://doi.org/10.1016/j.disc.2006.01.003 , url =

    work page doi:10.1016/j.disc.2006.01.003 2006

  35. [35]

    Counting linear extensions of sparse posets , year =

    Kangas, Kustaa and Hankala, Teemu and Niinim\". Counting linear extensions of sparse posets , year =. Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence , pages =

  36. [36]

    Journal of the American statistical association , volume=

    Probability inequalities for sums of bounded random variables , author=. Journal of the American statistical association , volume=. 1963 , publisher=

    1963

  37. [37]

    Discrete mathematics , volume=

    Faster random generation of linear extensions , author=. Discrete mathematics , volume=. 1999 , publisher=

    1999

  38. [38]

    Neurocomputing , volume=

    Explainable artificial intelligence: A survey of needs, techniques, applications, and future direction , author=. Neurocomputing , volume=. 2024 , publisher=

    2024