# Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Source: [Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification]() Collection index: [llms.txt]() Data updated: 2026-05-22T05:00:12.726Z Authors: Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis Published: 2026-05-20T11:10:15.000Z ## Abstract Data valuation, the task of quantifying the contribution of individual data points to model performance, has emerged as a fundamental challenge in machine learning. Game-theoretic approaches, such as the Banzhaf value, offer principled frameworks for fair data valuation; however, they suffer from exponential computational complexity. We address this challenge by developing efficient algorithms specifically tailored for computing Banzhaf values in $k$-nearest neighbor ($k$NN) classifiers. We first establish the theoretical hardness of the problem by proving that it is \\#P-hard. Despite this intractability, we exploit the locality properties of $k$NN classifiers to develop practical exact algorithms. Our main contribution is a dynamic programming framework that achieves significant computational improvements: we present a pseudo-polynomial algorithm with $O(Wkn^2)$ time complexity for weighted $k$NN classifiers, where $W$ is the maximum sum of top-$k$ weights, and a specialized algorithm for unweighted $k$NN that achieves $O(nk^2)$ time complexity, that is, linear in the number of data points. We also offer efficient Monte Carlo estimation methods. Extensive experiments on real-world datasets demonstrate the practical efficiency of our approach and its effectiveness in data valuation applications. ## Recorded benchmark results A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage. - [Identifying mislabeled points on click](): Identifying mislabeled points; Click; Recall: 14. - [Identifying mislabeled points on click (Precision)](): Identifying mislabeled points; Click; Precision: 7. - [Identifying mislabeled points on click (F1 score)](): Identifying mislabeled points; Click; F1 Score: 9. - [Identifying mislabeled points on creditcard (Recall)](): Identifying mislabeled points; creditcard; Recall: 14. - [Identifying mislabeled points on creditcard (Precision)](): Identifying mislabeled points; creditcard; Precision: 7. - [Identifying mislabeled points on creditcard (F1 score)](): Identifying mislabeled points; creditcard; F1 Score: 9. - [Identifying mislabeled points on apsfail (F1 score)](): Identifying mislabeled points; apsfail; F1 Score: 21. - [Identifying mislabeled points on apsfail](): Identifying mislabeled points; apsfail; Recall: 27. - [Identifying mislabeled points on apsfail (Precision)](): Identifying mislabeled points; apsfail; Precision (apsfail): 14. - [Identifying mislabeled points on phoneme (F1 score)](): Identifying mislabeled points; phoneme; F1 Score: 27. - [Identifying mislabeled points on cpu](): Identifying mislabeled points; CPU; Recall: 32. - [Identifying mislabeled points on MNIST](): Identifying mislabeled points; MNIST; Recall: 45. - [Identifying mislabeled points on cpu (Precision)](): Identifying mislabeled points; CPU; Precision: 16. - [Identifying mislabeled points on MNIST (Precision)](): Identifying mislabeled points; MNIST; Precision: 23. - [F1 score on Identifying mislabeled points on cpu](): Identifying mislabeled points; CPU; F1 Score: 21. - [F1 score on Identifying mislabeled points on MNIST](): Identifying mislabeled points; MNIST; F1 Score: 30. - [Identifying mislabeled points on wind (Recall)](): Identifying mislabeled points; Wind; Recall: 36. - [Identifying mislabeled points on wind (Precision)](): Identifying mislabeled points; Wind; Precision (wind): 18. - [Identifying mislabeled points on MNIST (AUC-ROC)](): Identifying mislabeled points; MNIST; AUC-ROC: 11. - [Identifying mislabeled points on phoneme (AUC-ROC)](): Identifying mislabeled points; phoneme; AUC-ROC: 15. - [Identifying mislabeled points on vehicle (F1 score)](): Identifying mislabeled points; vehicle; F1 Score: 15. - [Identifying mislabeled points on wind (F1 score)](): Identifying mislabeled points; Wind; F1 Score: 24. - [Identifying mislabeled points on 2dplanes](): Identifying mislabeled points; 2Dplanes; Recall: 41. - [Identifying mislabeled points on cifar10](): Identifying mislabeled points; CIFAR10; Recall: 14. - [Identifying mislabeled points on fraud](): Identifying mislabeled points; Fraud; Recall: 27. - [Identifying mislabeled points on vehicle](): Identifying mislabeled points; vehicle; Recall: 23. - [Identifying mislabeled points (Precision) on 2dplanes](): Identifying mislabeled points; 2Dplanes; Precision: 20. - [Identifying mislabeled points on fraud (Precision)](): Identifying mislabeled points; Fraud; Precision: 14. - [Identifying mislabeled points on vehicle (Precision)](): Identifying mislabeled points; vehicle; Precision: 11. - [Identifying mislabeled points on 2dplanes (F1 score)](): Identifying mislabeled points; 2Dplanes; F1 Score: 27. - [Identifying mislabeled points on fraud (F1 score)](): Identifying mislabeled points; Fraud; F1 Score: 18. - [Mislabel Detection on apsfail](): Mislabel Detection; apsfail; AUROC: 0.22. - [Identifying mislabeled points on phoneme (Recall)](): Identifying mislabeled points; phoneme; Recall: 27. - [Identifying mislabeled points on pol (Recall)](): Identifying mislabeled points; POL; Recall (pol): 14. - [Identifying mislabeled points on phoneme (Precision)](): Identifying mislabeled points; phoneme; Precision: 14. - [Identifying mislabeled points on pol (Precision)](): Identifying mislabeled points; POL; Precision: 7. - [Identifying mislabeled points on click (AUC-ROC)](): Identifying mislabeled points; Click; AUC-ROC: 4. - [Identifying mislabeled points on pol (F1 score)](): Identifying mislabeled points; POL; F1 Score (pol): 9. - [Misclassification Detection on CIFAR10](): Misclassification Detection; CIFAR10; AUROC: 9. - [Mislabel Detection on fraud](): Mislabel Detection; Fraud; AUROC: 11. - [Identifying mislabeled points on creditcard (AUC-ROC)](): Identifying mislabeled points; creditcard; AUC-ROC: 2. - [Mislabel Detection on pol](): Mislabel Detection; POL; AUROC: 0.06. - [Mislabel Detection on wind](): Mislabel Detection; Wind; AUROC: 12. - [Mislabel Detection on 2dplanes](): Mislabel Detection; 2Dplanes; AUROC: 0.21. - [Mislabel Detection on vehicle](): Mislabel Detection; vehicle; AUROC: 0.08. - [Mislabel Detection on cpu](): Mislabel Detection; CPU; AUROC: 5. ## Original sources and implementation [Original paper]() [PDF]()