🤖 AI

Beyond Shapley: Efficient Computation of Asymmetric Shapley Values

This paper introduces efficient algorithms for computing Asymmetric Shapley Values by leveraging causal graphs, demonstrating that exact computation is possible in polynomial time for rooted directed trees and proposing a uniform sampling-based approximation method for arbitrary causal DAGs to overcome the #P-hardness of standard Shapley value calculations.

Original authors: Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola

Published 2026-06-25

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a team of players (features) working together to win a game (make a prediction). You want to know exactly how much credit each player deserves for the win. In the world of AI, this is called Explainability.

The most famous way to do this is called Shapley Values. Think of it like a fair referee who looks at every possible order in which the players could have entered the game. If Player A enters first, second, or last, the referee calculates how much the team's score changed because of them. The final score for Player A is the average of all these changes.

The Problem with the Old Way
The problem is that calculating this for every single possible order is a nightmare. If you have 20 players, there are billions of orders to check. For complex AI models, this calculation is so hard it's practically impossible to do exactly.

Also, the old method treats all players as equals. If Player B is a copy of Player A, they get the same score. But in real life, sometimes one player causes the other to act. If Player A causes Player B to move, Player A is the real boss. The old method misses this "cause-and-effect" relationship.

The New Solution: Asymmetric Shapley Values (ASV)
This paper introduces a smarter referee called Asymmetric Shapley Values (ASV). Instead of looking at every possible order, this referee only looks at orders that make sense according to a Causal Map (a diagram showing who causes whom).

The Analogy: Imagine a factory assembly line. You can't paint the car before you build the frame. The Causal Map says, "Frame first, then paint." The ASV referee ignores any order where someone tries to paint before building. They only count the logical, cause-and-effect orders.
The Benefit: This gives a more honest explanation of who really caused the result. It also, surprisingly, makes the math easier in some cases where the old method was impossible.

How They Made It Fast (The Magic Tricks)
Even with the Causal Map, checking every valid order can still be too slow. The authors came up with two clever tricks to speed this up:

The "Grouping" Trick (Equivalence Classes):
Imagine you are counting how many ways people can line up. You realize that for the purpose of the calculation, it doesn't matter if two people swap places if they are both standing after the main boss. They are in the same "group."
The authors found a way to group thousands of similar orders into single "buckets" (called equivalence classes). Instead of checking 1,000,000 orders, they might only need to check 500 groups. This turns a impossible task into a quick one, especially if the Causal Map looks like a simple tree (like a family tree).
The "Sampling" Trick (Guessing with a Sample):
If the map is too messy to group neatly, they use a sampling method. Instead of checking every valid order, they randomly pick a few hundred orders that follow the rules and calculate the average.
- The Analogy: Instead of tasting every single grain of rice in a giant pot to see if it's salty, you take a spoonful from different spots. If the spoonfuls taste salty, you know the whole pot is salty. The paper shows this "spoonful" method is fast and gives a very good guess.

What They Tested
The authors tested these ideas on real-world data structures (like networks used to predict cancer or child development) and made-up tree structures.

They found that for tree-like structures, their "Grouping" method was incredibly fast, reducing the work by millions of times compared to the old way.
For messier structures, their "Sampling" method was fast and accurate enough to be useful.

The Bottom Line
This paper proves that by respecting the "cause-and-effect" rules of the data, we can explain AI models more accurately and faster. They showed that for certain types of data, a method that was previously impossible to calculate exactly can now be done quickly, and for others, a fast, accurate guess is easy to make.

Technical Summary: Beyond Shapley: Efficient Computation of Asymmetric Shapley Values

Problem Statement

The paper addresses the computational and interpretability challenges associated with feature attribution in Explainable AI (XAI). While Shapley values (and their machine learning instantiation, SHAP) provide a theoretically grounded method for distributing a model's prediction among input features, they suffer from two primary limitations:

Computational Intractability: Calculating exact Shapley values is often #P-hard, particularly for expressive models (e.g., neural networks) or when the underlying data distribution is complex (e.g., Naive Bayes distributions).
Interpretability Deficits: Standard Shapley values treat all features symmetrically. This fails to capture causal relationships, potentially assigning equal importance to a cause and its deterministic effect, thereby obscuring the true data-generating process.

To address the second issue, Asymmetric Shapley Values (ASV) were proposed, which restrict the calculation to permutations of features that respect a given causal graph (a Directed Acyclic Graph or DAG). However, the computational complexity of ASV had not been thoroughly explored. This paper investigates whether incorporating causal constraints can actually render the computation of attribution scores more tractable than standard Shapley values in specific contexts.

Methodology

The authors propose a suite of algorithms to compute ASV exactly and approximately, leveraging the structure of the causal graph and the underlying probability distribution (modeled as a Bayesian Network).

1. Theoretical Tractability Analysis

The authors establish a theoretical result regarding the complexity of ASV under Naive Bayes distributions. They prove that while computing standard Shapley values is intractable for certain model families under Naive Bayes distributions, computing ASV is polynomial-time tractable for the same families if the causal graph used for ASV is identical to the Naive Bayes network structure. This suggests that the causal constraints imposed by the distribution can break symmetries that otherwise make the problem hard.

2. Exact Computation via Equivalence Classes

To extend tractability to more general causal structures, specifically rooted directed trees, the authors introduce a method to reduce the search space of permutations:

Equivalence Classes: They define an equivalence relation over the set of topological orderings of the causal graph. Two orderings are equivalent with respect to a feature $x$ if the set of features preceding $x$ is identical in both orderings.
Algorithm: Instead of iterating through all topological orderings (which can be exponential), the algorithm computes the set of equivalence classes ( $\Lambda_x^C$ ) and the size of each class. The ASV is then computed by summing the marginal contributions weighted by the size of each equivalence class.
Complexity: For rooted directed trees, the number of equivalence classes is bounded by $h \cdot l + 1$ (where $h$ is depth and $l$ is the number of leaves). The authors provide a polynomial-time algorithm (in terms of the number of equivalence classes) to compute these classes and their sizes.

3. Approximate Computation via Sampling

For arbitrary causal DAGs where exact computation may be infeasible, the authors propose a sampling-based approximation scheme.

Sampling Topological Orderings: The method relies on sampling topological orderings uniformly at random. The authors implement two approaches:
1. A recursive counting algorithm for polytrees (graphs with at most one path between any two nodes) that counts topological orderings to weight source nodes correctly.
2. A random walk-based algorithm (based on Bubley & Dyer, 1999) for general DAGs.
Error Bounds: They formalize that if the topological ordering sampler is $\epsilon_{samp}$ -close to uniform and the characteristic function (expected model value) is approximated with error $\epsilon_{\nu}$ , the resulting ASV estimate has an additive error of $O(\epsilon_{samp} + \epsilon_{\nu})$ .

Key Results

The authors evaluated their methods on real-world Bayesian networks (Cancer, Child) and artificial structures (balanced trees, Naive Bayes, multiple paths).

Reduction in Search Space: The equivalence class approach significantly reduces the computational burden compared to enumerating all topological orders. In the "Child" network, the number of topological orders was $\approx 7.41 \times 10^{11}$ , whereas the number of equivalence classes was only $\approx 2003$ on average.
Runtime Efficiency:
- Computing equivalence classes for practical graph sizes took less than one second.
- The runtime of the exact algorithm was strongly correlated with the number of equivalence classes, allowing the pre-computation of class counts to serve as a predictor for computational cost.
- Enumerating all topological orders became infeasible for larger graphs, while the equivalence class method remained tractable.
Sampling Performance:
- The custom recursive sampling algorithm for polytrees was efficient, with non-linear scaling relative to the number of samples due to parallel candidate generation.
- Using 1,000 samples yielded an average relative error of approximately 8% for ASV values. The error was lower for larger ASV values and higher for very small true values.

Significance and Claims

The paper claims that ASV is a viable and potentially superior framework for explainability when causal structure is relevant, as it captures dependencies that standard SHAP misses. The primary contribution is demonstrating that causal constraints can transform an intractable problem into a tractable one for specific model-distribution pairs (e.g., decision trees under Naive Bayes).

The authors emphasize that while ASV offers these theoretical and practical benefits, its scalability is heavily dependent on the topology of the causal graph:

For rooted directed trees and polytrees, exact computation is feasible via equivalence classes.
For dense or large DAGs, the number of equivalence classes may still grow too large, necessitating the use of sampling-based approximations.

The work concludes that ASV is a promising direction for XAI, provided that the causal graph is known and the graph structure allows for efficient enumeration or sampling of topological orderings. Future work is suggested to generalize the exact algorithms to broader classes of graphs (e.g., general polytrees) and to optimize sampling mechanisms.