Introduction
Shapley Additive Explanations (SHAP) are widely considered the "gold standard" for feature attribution in machine learning due to their unique game-theoretic guarantees. However, there is a significant computational bottleneck: computing them exactly is #P-hard. To calculate the exact SHAP value for a single feature in a model with $n$ features, one must theoretically evaluate the model on every possible subset (or coalition) of the other features, resulting in $2^n$ evaluations.
Because of this exponential explosion, researchers and practitioners typically rely on statistical estimators like KernelSHAP. While these estimators are fast, they provide no formal guarantees on accuracy. Furthermore, because exact values were previously impossible to compute for large networks, the community lacked a "ground truth" to measure how inaccurate these estimators might be on realistic models.
Verified SHAP (VERISHAP) is a novel framework that bridges this gap. By repurposing neural network verification techniques, VERISHAP computes provably exact bounds on Shapley values, successfully scaling exact SHAP computation to search spaces orders of magnitude larger than previous state-of-the-art methods—moving the frontier from $2^{20}$ to $2^{60}$ coalitions.
How VERISHAP Works
VERISHAP treats the exponential search space of feature coalitions as a formal verification problem. The methodology relies on four core pillars:
- Continuous Relaxation: SHAP coalitions are inherently discrete (a feature is either "in" or "out"). VERISHAP uses a masking trick to represent coalitions as binary vectors and relaxes them into a continuous $[0, 1]$ space. This allows standard neural network verifiers to bound the model's behavior across thousands of coalitions simultaneously.
- Bound Propagation: The core innovation leverages bound propagation algorithms—specifically CROWN-IBP—to compute the lower and upper bounds of a neural network's output over these relaxed input ranges.
- Branch-and-Bound for Coalitions: Instead of enumerating every subset, VERISHAP partitions the set of all coalitions into "branches" (subsets of subsets), systematically exploring the space.
- Iterative Refinement: If the bounds on a SHAP value are too loose, the algorithm splits a branch by fixing a specific feature as "in" or "out" and recalculates. This process continues until the bounds meet a desired precision threshold or recover the exact value.
Key Insights
- Verification for Formal Explainability: Traditionally, neural network verification is used to prove safety properties (e.g., ensuring a self-driving car won't crash). This research demonstrates that verification is also a powerful tool for Formal Explainability, providing trustworthy, mathematically guaranteed insights that statistical methods cannot.
- Exploiting Piecewise Linearity: Most modern neural networks use ReLU activations, making them piecewise linear. VERISHAP recognizes when a branch of coalitions falls entirely within a single linear region of the network. When this happens, it can compute the exact SHAP contribution for that entire branch in a single, highly efficient step.
- Establishing a "Ground Truth" Baseline: For the first time, researchers can provide a definitive ranking of SHAP estimators on large search spaces. Testing revealed that LeverageSHAP generally outperforms the classic KernelSHAP—a nuance that was obscured when evaluations were limited to toy models.
Experimental Results
The authors evaluated VERISHAP across a diverse range of benchmarks, including tabular datasets (e.g., Obesity, German Credit, Mushroom) and vision datasets (e.g., MNIST, CIFAR10, GTSRB), using "superpixels" to manage feature counts in images.
- Unprecedented Scalability: VERISHAP computed exact SHAP values for search spaces of $2^{25}$ (approx. 33 million) coalitions and provided tight bounds for spaces as massive as $2^{60}$ (approx. $10^{18}$) coalitions. Previous exact methods typically failed after $2^{20}$.
- High Efficiency: On the Mushroom dataset ($2^{22}$ coalitions), VERISHAP found the exact SHAP values in just 25 seconds. In contrast, the standard "ExactSHAP" baseline ran out of memory.
- Arbitrary Precision: The algorithm can produce "arbitrarily tight" bounds. For many datasets, it reached a 1% Half-Range (HR) error—meaning the true SHAP value is guaranteed to be within a tiny, known window—long before the algorithm finished computing the absolute "exact" value.
Limitations and Future Directions
Despite its massive leap in scalability, VERISHAP is still bound by the fundamental limits of #P-hard problems.
- The Curse of Dimensionality: While $2^{60}$ is a massive search space, raw high-resolution images with thousands of individual pixels still result in search spaces far beyond the reach of this method, necessitating the use of superpixels.
- Worst-Case Complexity: There will always be "pathological" neural networks where the bounds refuse to tighten quickly. The authors noted that the algorithm struggled to converge efficiently on certain datasets, such as HepatitisC.
Looking forward, the authors suggest extending this verification framework to compute Shapley Taylor interactions (which measure how multiple features interact with one another) and exploring alternative value functions beyond the standard marginal expectation. Ultimately, VERISHAP establishes a principled cornerstone for both exact SHAP computation and the rigorous evaluation of future statistical approximation methods.
Summary updated