# Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation

arXiv: https://arxiv.org/abs/2603.03672 · HTML: https://mlsanity.com/paper/2603.03672/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 72 references that are in the map.
- First posted on arXiv 4 Mar 2026.

## Builds on (most cited first, 30 of 33)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Unsupervised Feature Learning via Non-Parametric Instance-level Discrimination](https://mlsanity.com/paper/1805.01978/) (2018)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Revisiting Unreasonable Effectiveness of Data in Deep Learning Era](https://mlsanity.com/paper/1707.02968/) (2017)
- [Prevalence of Neural Collapse during the terminal phase of deep learning training](https://mlsanity.com/paper/2008.08186/) (2020)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Estimating Training Data Influence by Tracing Gradient Descent](https://mlsanity.com/paper/2002.08484/) (2020)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Influence Functions in Deep Learning Are Fragile](https://mlsanity.com/paper/2006.14651/) (2020)
- [Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms](https://mlsanity.com/paper/1908.08619/) (2019)
- [Training Data Influence Analysis and Estimation: A Survey](https://mlsanity.com/paper/2212.04612/) (2022)
- [Data Valuation using Reinforcement Learning](https://mlsanity.com/paper/1909.11671/) (2019)
- [Algorithms to estimate Shapley value feature attributions](https://mlsanity.com/paper/2207.07605/) (2022)
- [Data Shapley in One Training Run](https://mlsanity.com/paper/2406.11011/) (2024)
- [Bounding the Estimation Error of Sampling-based Shapley Value Approximation](https://mlsanity.com/paper/1306.4265/) (2013)
- [OpenDataVal: a Unified Benchmark for Data Valuation](https://mlsanity.com/paper/2306.10577/) (2023)
- [Measuring the Effect of Training Data on Deep Learning Predictions via Randomized Experiments](https://mlsanity.com/paper/2206.10013/) (2022)
- [A Survey on Data Pricing: from Economics to Data Science](https://mlsanity.com/paper/2009.04462/) (2020)
- [Model-based Pricing for Machine Learning in a Data Marketplace](https://mlsanity.com/paper/1805.11450/) (2018)
- [Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation](https://mlsanity.com/paper/2308.15709/) (2023)
- [Efficient Data Shapley for Weighted Nearest Neighbor Algorithms](https://mlsanity.com/paper/2401.11103/) (2024)
- [Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality](https://mlsanity.com/paper/1402.0567/) (2014)
- [Data Market Platforms: Trading Data Assets to Solve Data Problems](https://mlsanity.com/paper/2002.01047/) (2020)
- [On Shapley Value in Data Assemblage Under Independent Utility](https://mlsanity.com/paper/2208.01163/) (2022)
- [Shapley Value-driven Data Pruning for Recommender Systems](https://mlsanity.com/paper/2505.22057/) (2025)

## Built on by (most cited first, 1 of 1)

- [Dynamic Shapley Computation](https://mlsanity.com/paper/2605.20620/) (2026)

## Abstract (arXiv)

The Shapley value provides a principled foundation for data valuation, but exact computation is #P-hard due to the exponential coalition space. Existing accelerations remain global and ignore a structural property of modern predictors: for a given test instance, only a small subset of training points influences the prediction. We formalize this model-induced locality through support sets defined by the model's computational pathway (e.g., neighbors in KNN, leaves in trees, receptive fields in GNNs), showing that Shapley computation can be projected onto these supports without loss when locality is exact. This reframes Shapley evaluation as a structured data processing problem over overlapping support-induced subset families rather than exhaustive coalition enumeration. We prove that the intrinsic complexity of Local Shapley is governed by the number of distinct influential subsets, establishing an information-theoretic lower bound on retraining operations. Guided by this result, we propose LSMR (Local Shapley via Model Reuse), an optimal subset-centric algorithm that trains each influential subset exactly once via support mapping and pivot scheduling. For larger supports, we develop LSMR-A, a reuse-aware Monte Carlo estimator that remains unbiased with exponential concentration, with runtime determined by the number of distinct sampled subsets rather than total draws. Experiments across multiple model families demonstrate substantial retraining reductions and speedups while preserving high valuation fidelity.