# Efficient Data Shapley for Weighted Nearest Neighbor Algorithms

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 52 references that are in the map.
- First posted on arXiv 20 Jan 2024.

## Builds on (most cited first, 27 of 27)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Pervasive Label Errors in Test Sets Destabilize Machine Learning Benchmarks](https://mlsanity.com/paper/2103.14749/) (2021)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2110.14049/) (2021)
- [Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms](https://mlsanity.com/paper/1908.08619/) (2019)
- [Data Banzhaf: A Robust Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2205.15466/) (2022)
- [A Principled Approach to Data Valuation for Federated Learning](https://mlsanity.com/paper/2009.06192/) (2020)
- [A Distributional Framework for Data Valuation](https://mlsanity.com/paper/2002.12334/) (2020)
- [LAVA: Data Valuation without Pre-Specified Learning Algorithms](https://mlsanity.com/paper/2305.00054/) (2023)
- [Measuring the Effect of Training Data on Deep Learning Predictions via Randomized Experiments](https://mlsanity.com/paper/2206.10013/) (2022)
- [N24News: A New Dataset for Multimodal News Classification](https://mlsanity.com/paper/2108.13327/) (2021)
- [Data-OOB: Out-of-bag Estimate as a Simple and Efficient Data Value](https://mlsanity.com/paper/2304.07718/) (2023)
- [Data Shapley Valuation for Efficient Batch Active Learning](https://mlsanity.com/paper/2104.08312/) (2021)
- [Beyond User Self-Reported Likert Scale Ratings: A Comparison Model for Automatic Dialog Evaluation](https://mlsanity.com/paper/2005.10716/) (2020)
- [Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation](https://mlsanity.com/paper/2308.15709/) (2023)
- [Data Debugging with Shapley Importance over End-to-End Machine Learning Pipelines](https://mlsanity.com/paper/2204.11131/) (2022)
- [A Note on "Towards Efficient Data Valuation Based on the Shapley Value''](https://mlsanity.com/paper/2302.11431/) (2023)
- [A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms"](https://mlsanity.com/paper/2304.04258/) (2023)
- [Energy-Based Learning for Cooperative Games, with Applications to Valuation Problems in Machine Learning](https://mlsanity.com/paper/2106.02938/) (2021)
- [HERALD: An Annotation Efficient Method to Detect User Disengagement in Social Conversations](https://mlsanity.com/paper/2106.00162/) (2021)
- [2D-Shapley: A Framework for Fragmented Data Valuation](https://mlsanity.com/paper/2306.10473/) (2023)
- [Optimizing Data Shapley Interaction Calculation from O(2^n) to O(t n^2) for KNN models](https://mlsanity.com/paper/2304.01224/) (2023)

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

- [Data Shapley in One Training Run](https://mlsanity.com/paper/2406.11011/) (2024)
- [Capturing the Temporal Dependence of Training Data Influence](https://mlsanity.com/paper/2412.09538/) (2024)
- [Rethinking Data Shapley for Data Selection Tasks: Misleads and Merits](https://mlsanity.com/paper/2405.03875/) (2024)
- [TokenShapley: Token Level Context Attribution with Shapley Value](https://mlsanity.com/paper/2507.05261/) (2025)
- [An Odd Estimator for Shapley Values](https://mlsanity.com/paper/2602.01399/) (2026)
- [On the Inflation of KNN-Shapley Value](https://mlsanity.com/paper/2405.17489/) (2024)
- [CHG Shapley: Efficient Data Valuation and Selection towards Trustworthy Machine Learning](https://mlsanity.com/paper/2406.11730/) (2024)
- [2D-OOB: Attributing Data Contribution Through Joint Valuation Framework](https://mlsanity.com/paper/2408.03572/) (2024)
- [Exactly Computing do-Shapley Values](https://mlsanity.com/paper/2602.07203/) (2026)
- [SAVA: Scalable Learning-Agnostic Data Valuation](https://mlsanity.com/paper/2406.01130/) (2024)
- [On the Impact of the Utility in Semivalue-based Data Valuation](https://mlsanity.com/paper/2502.06574/) (2025)
- [Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation](https://mlsanity.com/paper/2603.03672/) (2026)
- [Adaptive Data Selection for Multi-Layer Perceptron Training: A Sub-linear Value-Driven Method](https://mlsanity.com/paper/2510.21286/) (2025)
- [SCARV: Structure-Constrained Aggregation for Stable Sample Ranking in Redundant NLP Datasets](https://mlsanity.com/paper/2605.00944/) (2026)
- [ConfoundingSHAP: Quantifying confounding strength in causal inference](https://mlsanity.com/paper/2605.10533/) (2026)
- [Efficient Banzhaf-Based Data Valuation for k-Nearest Neighbors Classification](https://mlsanity.com/paper/2605.21033/) (2026)
- [OperatorSHAP: Fast and Accurate Shapley Value Estimation for Neural Operators](https://mlsanity.com/paper/2606.28065/) (2026)
- [Validation-Induced Shapley Shifts: How Validation Structure Distorts Data Valuation](https://mlsanity.com/paper/2607.03675/) (2026)

## Abstract (arXiv)

This work aims to address an open problem in data valuation literature concerning the efficient computation of Data Shapley for weighted K nearest neighbor algorithm (WKNN-Shapley). By considering the accuracy of hard-label KNN with discretized weights as the utility function, we reframe the computation of WKNN-Shapley into a counting problem and introduce a quadratic-time algorithm, presenting a notable improvement from O(NK), the best result from existing literature. We develop a deterministic approximation algorithm that further improves computational efficiency while maintaining the key fairness properties of the Shapley value. Through extensive experiments, we demonstrate WKNN-Shapley's computational efficiency and its superior performance in discerning data quality compared to its unweighted counterpart.