causasv — Causal Feature Attribution via Asymmetric Shapley Values

English | 日本語 | 中文

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

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

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:

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["seed"])       # int | None
print(info["is_exact"])   # bool
print(info["method"])     # str — the method name passed in (e.g. "approx")

Inspect and export the DAG:

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):

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:

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

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.7.0. Public API may change before v1.0.

Algorithm status

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

Paper correspondence

Beyond Shapley: Efficient Computation of Asymmetric Shapley Values

• 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

Benchmarks on Apple M-series (arm64, release build). v(S) = |S| (additive value function).

Exact enumeration would require visiting ~22 million valid causal orderings for n=15; exact_tree computes the same ASV in milliseconds via order-ideal DP. exact_dag handles arbitrary DAGs of the same size via 2^n bitmask DP.

Note: for n ≤ ~8, exact is often faster than exact_tree due to lower allocator overhead. exact_tree becomes the only feasible exact method for larger trees; exact_dag covers non-tree DAGs of the same scale. Run with cargo bench to reproduce.

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.

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

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)
• MIT License (LICENSE-MIT)

at your option.