mlsanityData to 7 Oct 2026

Efficient Data Shapley for Weighted Nearest Neighbor Algorithms

arXiv 2401.11103 ↗First posted 20 Jan 2024cs.DS cs.LG stat.MLcited by 18

Not on the map. Why?

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.

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

Builds on

27 of 52 references.

References · 27

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2019Sentence-BERT: Sentence Embeddings using Siamese BERT-Networkscited by 9,049
  4. 2018GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understandingcited by 4,854
  5. 2019Generalization through Memorization: Nearest Neighbor Language Modelscited by 788
  6. 2019Data Shapley: Equitable Valuation of Data for Machine Learningcited by 617
  7. 2021Pervasive Label Errors in Test Sets Destabilize Machine Learning Benchmarkscited by 388
  8. 2019Towards Efficient Data Valuation Based on the Shapley Valuecited by 279
  9. 2021Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learningcited by 162
  10. 2019Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithmscited by 147
  11. 2020A Principled Approach to Data Valuation for Federated Learningcited by 127
  12. 2022Data Banzhaf: A Robust Data Valuation Framework for Machine Learningcited by 126
15 more
  1. 2020A Distributional Framework for Data Valuationcited by 79
  2. 2023LAVA: Data Valuation without Pre-Specified Learning Algorithmscited by 69
  3. 2022Measuring the Effect of Training Data on Deep Learning Predictions via Randomized Experimentscited by 50
  4. 2021N24News: A New Dataset for Multimodal News Classificationcited by 40
  5. 2023Data-OOB: Out-of-bag Estimate as a Simple and Efficient Data Valuecited by 38
  6. 2021Data Shapley Valuation for Efficient Batch Active Learningcited by 27
  7. 2020Beyond User Self-Reported Likert Scale Ratings: A Comparison Model for Automatic Dialog Evaluationcited by 22
  8. 2023Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuationcited by 19
  9. 2022Data Debugging with Shapley Importance over End-to-End Machine Learning Pipelinescited by 16
  10. 2023A Note on "Towards Efficient Data Valuation Based on the Shapley Value''cited by 11
  11. 2023A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms"cited by 11
  12. 2021Energy-Based Learning for Cooperative Games, with Applications to Valuation Problems in Machine Learningcited by 10
  13. 2021HERALD: An Annotation Efficient Method to Detect User Disengagement in Social Conversationscited by 9
  14. 20232D-Shapley: A Framework for Fragmented Data Valuationcited by 7
  15. 2023Optimizing Data Shapley Interaction Calculation from O(2^n) to O(t n^2) for KNN modelscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 7; 2025: 3; 2026: 8.

18 papers.

Sort:

By area:

  1. 2024Data Shapley in One Training Runcited by 76
  2. 2024Capturing the Temporal Dependence of Training Data Influencecited by 34
  3. 2024Rethinking Data Shapley for Data Selection Tasks: Misleads and Meritscited by 29
  4. 2025TokenShapley: Token Level Context Attribution with Shapley Valuecited by 14
  5. 2026An Odd Estimator for Shapley Valuescited by 5
  6. 2024On the Inflation of KNN-Shapley Valuecited by 4
  7. 20242D-OOB: Attributing Data Contribution Through Joint Valuation Frameworkcited by 4
  8. 2024CHG Shapley: Efficient Data Valuation and Selection towards Trustworthy Machine Learningcited by 3
  9. 2026Exactly Computing do-Shapley Valuescited by 3
  10. 2024SAVA: Scalable Learning-Agnostic Data Valuationcited by 1
  11. 2025On the Impact of the Utility in Semivalue-based Data Valuationcited by 1
  12. 2026Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuationcited by 1
6 more
  1. 2025Adaptive Data Selection for Multi-Layer Perceptron Training: A Sub-linear Value-Driven Methodcited by 0
  2. 2026SCARV: Structure-Constrained Aggregation for Stable Sample Ranking in Redundant NLP Datasetscited by 0
  3. 2026ConfoundingSHAP: Quantifying confounding strength in causal inferencecited by 0
  4. 2026Efficient Banzhaf-Based Data Valuation for k-Nearest Neighbors Classificationcited by 0
  5. 2026OperatorSHAP: Fast and Accurate Shapley Value Estimation for Neural Operatorscited by 0
  6. 2026Validation-Induced Shapley Shifts: How Validation Structure Distorts Data Valuationcited by 0