CoShap: A Scalable Coalition Growth Approach to Shapley Value Approximation

The Shapley value provides a theoretically grounded framework for model interpretability by quantifying feature importance, with critical applications in data analytics and data valuation. However, its exact computation is often intractable due to an exponential complexity that scales with the number of features. This poses a significant scalability challenge for high-dimensional datasets common in modern data systems. Prevailing approximation methods, typically based on Monte Carlo sampling, suffer from severe inefficiencies rooted in their unstructured and redundant exploration of the coalition space. These limitations lead to unreliable estimates and hinder practical adoption in data-intensive applications. This paper presents CoShap, a novel framework that delivers fast and reliable Shapley value approximation through systematic coalition growth. CoShap consists of a two-phase evaluation: (1) A layer-wise coalition growth phase that incrementally builds larger feature coalitions from smaller ones. Inspired by Pattern Growth, this structured approach drastically reduces redundant model evaluations by reusing previously computed coalition utilities. (2) A subsequent feature-wise evaluation phase that adaptively allocates more computational budget to high-variance features, specifically those with the most uncertain contributions, to enhance approximation reliability. To guarantee an (ε, δ)-approximation of the true Shapley values, CoShap introduces a dynamic budget allocation method that balances the evaluation budget across both phases. Experiments on diverse datasets show that CoShap significantly outperforms state-of-the-art methods, achieving up to 7.15× speedup in runtime and a 76.84% reduction in approximation error.