Beyond Shapley: Efficient Computation of Asymmetric Shapley Values
06:00 · June 25, 2026 · arXiv cs.AI RSS
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.
Summary
The paper addresses the computational challenges of feature attribution in explainable AI by focusing on Asymmetric Shapley Values, a variant of standard Shapley values that incorporates a causal graph to restrict permutations to those consistent with the underlying causal structure. This restriction allows ASV to assign attributions that respect causal precedence, giving priority to features whose information is not already captured by others, rather than treating all features symmetrically as in conventional SHAP.
The authors establish that exact ASV computation can be performed in polynomial time in settings where SHAP is known to be #P-hard. They introduce equivalence classes over the topological orderings of the causal graph as a means to group permutations that produce identical marginal contributions, thereby reducing the effective search space. For the special case of rooted directed trees, they present a polynomial-time algorithm whose complexity depends on the number of such equivalence classes rather than the full set of permutations.
For general causal DAGs, where exact computation remains intractable, the work provides an approximation method that samples topological orderings uniformly at random and combines this with conditional sampling from the data distribution. The sampling step can be realized through established algorithms or simpler alternatives. Experimental evaluation on realistic causal structures confirms that the proposed exact and approximate procedures are practically viable for models and graphs where standard SHAP remains infeasible.
Why it matters
The research directly supports the development of Explainable AI (XAI), which is crucial for Dutch and EU enterprises to comply with the transparency requirements of the EU AI Act. The algorithmic improvements offer researchers practical tools to implement causal knowledge into model-agnostic explanations efficiently.
