# causasv — Causal Feature Attribution via Asymmetric Shapley Values
[](https://github.com/kent-tokyo/causasv/actions/workflows/ci.yml)
[](https://crates.io/crates/causasv)
[](https://docs.rs/causasv)
[](LICENSE-MIT)
<br>
[](https://blog.rust-lang.org/2025/02/20/Rust-1.85.0/)
[](https://www.python.org/)
[](https://doc.rust-lang.org/nomicon/meet-safe-and-unsafe.html)
`causasv` computes **Asymmetric Shapley Values (ASV)** for causal feature attribution over user-supplied DAGs. It is a Rust-first engine with Python bindings, designed for XAI workflows where feature importance should respect known causal structure.
## What is ASV?
Asymmetric Shapley Values (ASV) generalize Shapley values by averaging only over **topologically valid orderings** of features, rather than all permutations. Given a causal DAG G and a value function v:
```
φ_i = (1 / |Π(G)|) Σ_{π ∈ Π(G)} [v(pre(i,π) ∪ {i}) − v(pre(i,π))]
```
where Π(G) is the set of all linear extensions (topological orderings) of G, and pre(i,π) is the set of features appearing before feature i in ordering π.
## How ASV differs from SHAP
Standard SHAP averages over all n! feature permutations, ignoring causal structure. ASV restricts the average to permutations consistent with the causal DAG — causes always appear before their effects. This produces attributions that respect the direction of causality.
## Why causal DAGs matter
When features have causal relationships, SHAP can assign attribution to a variable for effects that are actually mediated by its descendants. ASV prevents this by constraining which orderings are considered valid.
## Rust example
```rust
use causasv::{AsvExplainer, Dag, SamplingConfig};
fn main() -> Result<(), causasv::CausasvError> {
let mut dag = Dag::new();
let education = dag.add_node("education");
let income = dag.add_node("income");
let risk = dag.add_node("risk_score");
dag.add_edge(education, income)?;
dag.add_edge(income, risk)?;
dag.validate()?;
let explainer = AsvExplainer::new(dag);
// Approximate ASV via importance-weighted topological order sampling.
let values = explainer.approximate(
|coalition| {
// User-supplied value function: score given a coalition of features.
Ok(coalition.len() as f64)
},
SamplingConfig::new(10_000).with_seed(42),
)?;
for (node, value) in &values.values {
println!("Node {:?}: ASV = {:.4}", node, value);
}
Ok(())
}
```
## Python example
```python
from causasv import CausalDAG, ASVExplainer
# From a list of edges
dag = CausalDAG.from_edges([("education", "income"), ("income", "risk_score")])
# Or from a networkx DiGraph
# import networkx as nx; G = nx.DiGraph(); G.add_edge(...)
# dag = CausalDAG.from_networkx(G)
explainer = ASVExplainer(dag)
values = explainer.explain(
value_fn=lambda feature_names: my_model_score(feature_names),
method="auto", # exact for n≤8, exact_tree for rooted trees, approx otherwise
n_samples=10_000,
seed=42,
)
# values: dict[str, float] mapping feature name → ASV value
```
The Python `value_fn` receives a sorted list of feature names present in the coalition and must return a float.
Use `explain_with_diagnostics()` to get ESS, seed, and method alongside values:
```python
info = explainer.explain_with_diagnostics(
value_fn=lambda feature_names: my_model_score(feature_names),
method="approx",
n_samples=10_000,
seed=42,
)
print(info["values"]) # dict[str, float]
print(info["ess"]) # float — ESS ≈ n_samples means reliable; ESS ≪ n_samples means high variance
print(info["ess_ratio"]) # float — ESS / n_samples ∈ (0, 1]; close to 1 is good
print(info["n_samples"]) # int
print(info["method"]) # str — the method name passed in (e.g. "approx")
```
Use `explain_adaptive()` for automatic convergence detection and per-feature confidence intervals:
```python
info = explainer.explain_adaptive(
value_fn=lambda feature_names: my_model_score(feature_names),
min_samples=1_000,
max_samples=100_000,
batch_size=1_000,
seed=42,
ci=0.95, # optional: add ci_low / ci_high to result
)
print(info["values"]) # dict[str, float]
print(info["stderr"]) # dict[str, float] — IS standard error per feature
print(info["ci_low"]) # dict[str, float] — lower bound of 95% confidence interval
print(info["ci_high"]) # dict[str, float] — upper bound of 95% confidence interval
print(info["converged"]) # bool — True if rel_tol was reached before max_samples
print(info["ess_ratio"]) # float — ESS / n_samples; close to 1 is good
```
For batched coalitions (reduced Python GIL overhead for large models), pass `value_fn_batch` or call `explain_adaptive_batch()`:
```python
# value_fn_batch receives list[list[str]] and must return list[float]
info = explainer.explain_with_diagnostics(
value_fn_batch=lambda coalitions: [my_model_score(c) for c in coalitions],
method="approx",
n_samples=50_000,
batch_size=512,
seed=42,
)
# Adaptive variant with batched evaluation
info = explainer.explain_adaptive_batch(
value_fn_batch=lambda coalitions: [my_model_score(c) for c in coalitions],
min_samples=1_000,
max_samples=100_000,
batch_size=1_000,
seed=42,
)
```
For deterministic parallel approximation, pass `parallel=True` with a `seed`:
```python
info = explainer.explain_with_diagnostics(
value_fn=lambda feature_names: my_model_score(feature_names),
method="approx",
n_samples=100_000,
seed=42,
parallel=True,
num_threads=4, # None = rayon default
)
print(info["deterministic"]) # True when seed + parallel
```
Use `explain_stability()` to verify that approximate rankings are consistent across seeds:
```python
from causasv import explain_stability
result = explain_stability(
explainer,
value_fn=lambda feature_names: my_model_score(feature_names),
seeds=[1, 2, 3, 4, 5],
method="approx",
n_samples=10_000,
)
print(result["rank_stability"]) # mean pairwise Kendall tau; 1.0 = perfectly stable
print(result["std_values"]) # dict[str, float] — small means stable estimates
print(result["mean_values"]) # dict[str, float] — mean ASV across seeds
```
Use `ASVEnsembleExplainer` to measure sensitivity across multiple candidate DAGs:
```python
from causasv import CausalDAG, ASVEnsembleExplainer
dag1 = CausalDAG.from_edges([("A", "B"), ("B", "C")])
dag2 = CausalDAG.from_edges([("A", "B"), ("A", "C")])
ensemble = ASVEnsembleExplainer([dag1, dag2])
result = ensemble.explain_with_sensitivity(
value_fn=lambda feature_names: my_model_score(feature_names),
method="auto",
)
print(result["mean_values"]) # dict[str, float] — mean ASV across DAGs
print(result["std_values"]) # dict[str, float] — std across DAGs; 0 = DAG-invariant
print(result["rank_stability"]) # float — mean pairwise Kendall tau across DAG pairs
print(result["per_dag_values"]) # list[dict[str, float]] — one dict per DAG
```
Inspect and export the DAG:
```python
dag.nodes() # ["education", "income", "risk_score"]
dag.edges() # [("education", "income"), ("income", "risk_score")]
dag.to_dot() # 'digraph {\n education -> income;\n ...\n}'
dag.to_json() # '{"nodes":[...],"edges":[...]}'
dag.ancestors("risk_score") # ["education", "income"]
dag.descendants("education") # ["income", "risk_score"]
dag.topological_layers() # [["education"], ["income"], ["risk_score"]]
# Restore a DAG from JSON
dag2 = CausalDAG.from_json(dag.to_json())
# Convert to networkx (networkx must be installed separately)
import networkx as nx
G = nx.DiGraph(dag.edges())
```
Use `TabularExplainer` for a higher-level API with sklearn-compatible models (requires numpy):
```python
from causasv import CausalDAG, TabularExplainer
dag = CausalDAG.from_edges([("education", "income"), ("income", "risk_score")])
explainer = TabularExplainer.from_model(
model=my_classifier, # any sklearn-compatible model
dag=dag,
background=X_train, # reference dataset; column means = absent-feature baseline
feature_names=["education", "income", "risk_score"],
)
values = explainer.explain_instance(X_test[0], method="auto")
# values: dict[str, float] mapping feature name → ASV value
```
Or build the value function directly with `make_tabular_value_fn` for full control:
```python
from causasv import make_tabular_value_fn
value_fn = make_tabular_value_fn(model=my_classifier, x=X_test[0],
background=X_train, feature_names=[...])
values = ASVExplainer(dag).explain(value_fn, method="auto")
```
## Exact vs Approximate
| `exact` | Small DAGs (n ≤ ~8); enumerates all linear extensions | `explainer.exact(value_fn)` |
| `exact_tree` | Rooted directed trees; order-ideal DP | `explainer.exact_tree(value_fn)` |
| `exact_dag` | General DAGs, n ≤ 20; dense order-ideal DP | `explainer.exact_dag(value_fn)` |
| `exact_dag_sparse` | Sparse DAGs, n ≤ 28; BFS over valid order ideals only | `explainer.exact_dag_sparse(value_fn)` |
| `approx` | Any DAG (n > 28 or memory limit exceeded); IS sampling | `explainer.approximate(value_fn, SamplingConfig::new(n))` |
`auto` dispatch: n ≤ 8 → `exact`; rooted tree → `exact_tree`; n ≤ 20 → `exact_dag`; 20 < n ≤ 28 → `exact_dag_sparse`; else → `approx`.
`exact_dag_sparse` visits only valid order ideals (sets where every node's parents are also present). For sparse DAGs (chains, trees, few branching points), this can be orders of magnitude fewer states than 2^n. Returns `n_order_ideals`, `state_ratio`, and `memory_mb` diagnostics.
The approximate estimator uses self-normalized importance sampling to correct for the bias introduced by the frontier sampler, so the efficiency axiom (Σφ_i = v(V) − v(∅)) holds exactly even for approximate results.
The result includes `effective_sample_size` (ESS = (Σw)² / Σw²): ESS ≈ n_samples means IS weights are uniform and the estimate is reliable; ESS ≪ n_samples indicates high weight variance.
## Status
Experimental — v0.8.1. Public API may change before v1.0.
## Algorithm status
| `exact` | Enumerates all linear extensions | Reference oracle; practical for n ≤ ~8 |
| `exact_tree` | Rooted tree validation + order-ideal DP | Efficient for trees; hook-length formula |
| `exact_dag` | Order-ideal DP over 2^n states | General DAGs, n ≤ 20; O(2^n × n) |
| `exact_dag_sparse` | BFS over valid order ideals + lazy dp_ind | Sparse DAGs, n ≤ 28; memory-bounded |
| `approx` | Self-normalized IS over topological orderings | Any DAG; corrects frontier-sampler bias |
The brute-force `exact` implementation is used as the reference oracle in tests for all other methods.
The `exact_tree` DP enumerates valid pre-sets via order ideals and weights each by the hook-length formula, avoiding explicit enumeration of all linear extensions. Caterpillar trees of depth 30 see orders-of-magnitude speedups over brute-force.
The `exact_dag` DP computes two tables over all 2^n bitmasks: `dp_fwd[S]` (orderings of valid order ideals S) and `dp_ind[T]` (linear extensions of any induced subgraph G[T]). The ASV for each node i accumulates `dp_fwd[S] × dp_ind[V\(S∪{i})] × (v(S∪{i}) − v(S))` over all valid transitions. This is the order-ideal DP generalized from trees to arbitrary DAGs.
## Feature matrix
| Exact ASV (brute-force) | ✓ | ✓ | Stable |
| Rooted-tree exact DP | ✓ | ✓ | Experimental |
| General DAG exact DP (n ≤ 20) | ✓ | ✓ | Experimental |
| Sparse exact DAG DP (n ≤ 28) | ✓ | ✓ | Experimental |
| Approximate ASV with ESS | ✓ | ✓ | Experimental |
| Adaptive approximation + CI | ✓ | ✓ | Experimental |
| Seeded deterministic parallel approx | ✓ | ✓ | Experimental |
| Batched coalition evaluation | ✓ | ✓ | Experimental |
| sklearn / NumPy helper (TabularExplainer) | — | ✓ | Experimental |
| DAG ensemble / sensitivity ASV | — | ✓ | Experimental |
| DAG structural inspection | — | ✓ | Experimental |
| Graph export (DOT / JSON / networkx) | — | ✓ | Experimental |
## Paper correspondence
*Beyond Shapley: Efficient Computation of Asymmetric Shapley Values*
| ASV definition | ✓ `exact` (brute-force oracle) |
| Rooted tree exact algorithm | ✓ `exact_tree` (order-ideal DP + hook-length formula) |
| General DAG exact DP | ✓ `exact_dag` (order-ideal DP, n ≤ 20) |
| Importance-sampling approximation for general DAGs | ✓ `approx` |
| Sparse exact DAG DP | ✓ `exact_dag_sparse` (BFS over order ideals, n ≤ 28) |
| Causal discovery | — out of scope |
- `exact_tree` implements the order-ideal enumeration + hook-length weighting for rooted directed trees.
- `exact_dag` implements the two-table order-ideal DP for general DAGs (n ≤ 20).
- `approx` implements importance-weighted topological ordering sampling for any DAG.
- `exact` is a brute-force baseline oracle used as a correctness reference in tests.
## Performance
Selected results on Apple M-series (arm64, release build), `v(S) = |S|`. See [docs/benchmarks.md](docs/benchmarks.md) for full tables.
| Chain | 7 | `exact` (brute-force) | 2.7 µs |
| Balanced tree | 15 | `exact_tree` (DP) | 2.8 ms |
| Caterpillar | 10 | `exact_tree` (DP) | 170 µs |
| Chain | 16 | `exact_dag` (dense DP) | 5.3 ms |
| Chain | 24 | `exact_dag_sparse` | 15 µs |
| Two parallel chains | 20 | `exact_dag` (dense, 1M states) | **87.9 ms** |
| Two parallel chains | 20 | `exact_dag_sparse` (121 states) | **91 µs** (~1000×) |
| Chain | 10 | `approx` (1k samples) | 916 µs |
| Chain | 20 | `approx` serial seeded (10k) | 18.2 ms |
| Chain | 20 | `approx` parallel 4t seeded (10k) | 7.4 ms |
Run `cargo bench` to reproduce. HTML reports saved to `target/criterion/`.
## Current limitations
- Brute-force exact ASV is exponential in the number of linear extensions; only practical for n ≤ ~8 nodes.
- `exact_tree` requires a rooted directed tree (single root, all other nodes have in-degree 1). For general DAGs with n ≤ 20, use `exact_dag`. For sparse DAGs with n ≤ 28, use `exact_dag_sparse`. For larger DAGs, use `approx`.
- Python bindings provide `nodes()`, `edges()`, `to_dot()`, and `make_tabular_value_fn`; graph-level DOT export works but Rust-side export is not yet implemented.
- No built-in causal discovery, model training, or automatic graph construction.
## Compared to other tools
`causasv` is not a SHAP replacement or a general-purpose explainability framework.
It solves one narrow problem:
> Computing Asymmetric Shapley Values over a user-supplied causal DAG.
| [SHAP](https://github.com/shap/shap) | General-purpose Shapley / SHAP | No — standard Shapley only |
| [Captum](https://captum.ai/) | PyTorch model interpretability | No |
| [shapr](https://github.com/NorskRegnesentral/shapr) | Conditional / causal Shapley (R + Python) | Yes — broader scope, R-first |
| [shapflex](https://pypi.org/project/shapflex/) | ASV with causal knowledge (Python alpha) | Yes — similar concept |
| **causasv** | ASV over user-supplied causal DAGs | **Core focus** |
The main differences from `shapr` and `shapflex`: `causasv` is a Rust-first engine
that requires the user to supply an explicit causal DAG and a value function.
It does not perform causal discovery and does not depend on the data distribution.
## Scope
- **Does** compute ASV (causal feature attribution) given a DAG and a value function
- **Does not** do causal discovery, model training, or feature selection
- **Not** a SHAP replacement — ASV and SHAP answer different questions
## Building Python bindings
```bash
cd py
python -m venv .venv && source .venv/bin/activate
pip install maturin
maturin develop --features python
python -m pytest tests/
```
## Citation
> Fryer, D., Strümke, I., & Nguyen, H. (2021). *Shapley values for feature selection: The good, the bad, and the axioms.* IEEE Access.
For the asymmetric formulation and efficient tree computation, see the paper that inspired this library:
> Beyond Shapley: Efficient Computation of Asymmetric Shapley Values
## License
Licensed under either of
- Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE))
- MIT License ([LICENSE-MIT](LICENSE-MIT))
at your option.