# Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 77 references that are in the map.
- First posted on arXiv 30 Aug 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Membership Inference Attacks From First Principles](https://mlsanity.com/paper/2112.03570/) (2021)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Differential Privacy Has Disparate Impact on Model Accuracy](https://mlsanity.com/paper/1905.12101/) (2019)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Numerical Composition of Differential Privacy](https://mlsanity.com/paper/2106.02848/) (2021)
- [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)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [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)
- [Sampling Permutations for Shapley Value Estimation](https://mlsanity.com/paper/2104.12199/) (2021)
- [A Distributional Framework for Data Valuation](https://mlsanity.com/paper/2002.12334/) (2020)
- [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)
- [A Multilinear Sampling Algorithm to Estimate Shapley Values](https://mlsanity.com/paper/2010.12082/) (2020)
- [Understanding the Sparse Vector Technique for Differential Privacy](https://mlsanity.com/paper/1603.01699/) (2016)
- [Data Shapley Valuation for Efficient Batch Active Learning](https://mlsanity.com/paper/2104.08312/) (2021)
- [Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms](https://mlsanity.com/paper/2201.03968/) (2022)
- [Beyond User Self-Reported Likert Scale Ratings: A Comparison Model for Automatic Dialog Evaluation](https://mlsanity.com/paper/2005.10716/) (2020)
- [Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFT](https://mlsanity.com/paper/2102.12412/) (2021)
- [Data Debugging with Shapley Importance over End-to-End Machine Learning Pipelines](https://mlsanity.com/paper/2204.11131/) (2022)
- [Estimation of the Shapley value by ergodic sampling](https://mlsanity.com/paper/1906.05224/) (2019)
- [Private Data Valuation and Fair Payment in Data Marketplaces](https://mlsanity.com/paper/2210.08723/) (2022)

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

- [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)
- [Efficient Data Shapley for Weighted Nearest Neighbor Algorithms](https://mlsanity.com/paper/2401.11103/) (2024)
- [On the Inflation of KNN-Shapley Value](https://mlsanity.com/paper/2405.17489/) (2024)
- [Targeted synthetic data generation for tabular data via hardness characterization](https://mlsanity.com/paper/2410.00759/) (2024)
- [Concept-TRAK: Understanding how diffusion models learn concepts through concept-level attribution](https://mlsanity.com/paper/2507.06547/) (2025)
- [A Comprehensive Study of Shapley Value in Data Analytics](https://mlsanity.com/paper/2412.01460/) (2024)
- [Thresholding Data Shapley for Data Cleansing Using Multi-Armed Bandits](https://mlsanity.com/paper/2402.08209/) (2024)
- [SAVA: Scalable Learning-Agnostic Data Valuation](https://mlsanity.com/paper/2406.01130/) (2024)
- [Towards Data Valuation via Asymmetric Data Shapley](https://mlsanity.com/paper/2411.00388/) (2024)
- [On the Fragility of Contribution Score Computation in Federated Learning](https://mlsanity.com/paper/2509.19921/) (2025)
- [Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation](https://mlsanity.com/paper/2603.03672/) (2026)
- [A case for data valuation transparency via DValCards](https://mlsanity.com/paper/2506.23349/) (2025)
- [Adaptive Data Selection for Multi-Layer Perceptron Training: A Sub-linear Value-Driven Method](https://mlsanity.com/paper/2510.21286/) (2025)
- [Reliable and Private Utility Signaling for Data Markets](https://mlsanity.com/paper/2511.07975/) (2025)
- [SCARV: Structure-Constrained Aggregation for Stable Sample Ranking in Redundant NLP Datasets](https://mlsanity.com/paper/2605.00944/) (2026)
- [Is Data Shapley Not Better than Random in Data Selection? Ask NASH](https://mlsanity.com/paper/2605.10684/) (2026)
- [Validation-Induced Shapley Shifts: How Validation Structure Distorts Data Valuation](https://mlsanity.com/paper/2607.03675/) (2026)

## Abstract (arXiv)

Data valuation aims to quantify the usefulness of individual data sources in training machine learning (ML) models, and is a critical aspect of data-centric ML research. However, data valuation faces significant yet frequently overlooked privacy challenges despite its importance. This paper studies these challenges with a focus on KNN-Shapley, one of the most practical data valuation methods nowadays. We first emphasize the inherent privacy risks of KNN-Shapley, and demonstrate the significant technical difficulties in adapting KNN-Shapley to accommodate differential privacy (DP). To overcome these challenges, we introduce TKNN-Shapley, a refined variant of KNN-Shapley that is privacy-friendly, allowing for straightforward modifications to incorporate DP guarantee (DP-TKNN-Shapley). We show that DP-TKNN-Shapley has several advantages and offers a superior privacy-utility tradeoff compared to naively privatized KNN-Shapley in discerning data quality. Moreover, even non-private TKNN-Shapley achieves comparable performance as KNN-Shapley. Overall, our findings suggest that TKNN-Shapley is a promising alternative to KNN-Shapley, particularly for real-world applications involving sensitive data.