Efficient Banzhaf-Based Data Valuation for k k -Nearest Neighbors Classification

Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis · 2026

Read Efficient Banzhaf-Based Data Valuation for k k -Nearest Neighbors Classification by Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21033.txt.

Introduction

Guangyi Zhang and three colleagues develop efficient Banzhaf-based data valuation for k-nearest neighbours classification. Data valuation measures the share of single data points to model performance, a basic challenge in machine learning. Game-theoretic methods like the Banzhaf value give principled frameworks for fair pricing but suffer exponential computational complexity. The authors address that challenge with fast routines tuned to finding Banzhaf values in k-nearest neighbour classifiers, first proving the problem is sharp-P-hard, then using local structure.

Catalog record

CREATORGuangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE89221
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.21033

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Banzhaf-Based Data Valuation for k k -Nearest Neighbors Classification Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis 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 k -nearest neighbor ( k ​ NN k\textsc{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 k\textsc{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 𝒪 ⁡ ( W ​ k ​ n 2 ) \mathcal{O}(Wkn^{2}) time complexity for weighted k ​ NN k\textsc{NN} classifiers, where W W is the maximum sum of top- k k weights, and a specialized algorithm for unweighted k ​ NN k\textsc{NN} that achieves 𝒪 ⁡ ( n ​ k 2 ) \mathcal{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. † † authors: . PVLDB Reference Format: PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/Guangyi-Zhang/knn-banzhaf-code . 1. Introduction Data valuation has emerged as a fundamental problem in machine learning, addressing the critical question of how to quantify the contribution of individual data points to model performance ( 10 ; 34 ; 17 ) . As machine learning systems increasingly rely on large datasets assembled from diverse sources, understanding the relative importance of different data points becomes essential for various applications, such as enabling practitioners to make informed decisions regarding data acquisition, identifying low-quality or redundant data, and ensuring fair compensation for data providers in collaborative-learning scenarios. Cooperative game theory ( 7 ) provides a principled framework for addressing data-valuation tasks. By modeling the data valuation problem as a cooperative game where data points are players and the model performance represents the value function, we can leverage established solution concepts from cooperative game theory to assign fair and meaningful values to individual data points. Among the various solution concepts, the Shapley value ( 33 ) and the Banzhaf value ( 2 ) have gained particular attention due to their desirable axiomatic properties. In particular, the Banzhaf value has been adopted as a measure of voting power in the analysis of voting in the Council of the European Union ( 38 ) . Both values are based on the idea of quantifying the marginal contribution of a particular data point to the performance of the model. Arguably, the simplest way that leverages the same idea to quantify the value of a data point z in a dataset D is the leave-one-out (LOO) value, which measures the difference in the model performance before and after the data point is removed from the dataset, that is, \text{LOO}(z)=v(D)-v(D\setminus\{z\}), where v:2^{N}\to\mathbb{R} is the value function that represents the model performance, for example, the accuracy of a model. However, the LOO value is not informative in the presence of data redundancy ( 23 ) . Besides, the impact of a single data point given the remaining large amount of data is often negligible ( 3 ; 13 ) . The Shapley and Banzhaf values further develop the idea by aggregating the marginal contributions of a data point to all possible subsets of the dataset. For example, the Banzhaf value of a data point z is defined precisely as the average marginal contribution of z to all possible subsets S\subseteq D\setminus\{z\} of the dataset, that is, \beta(z)=\frac{1}{2^{n-1}}\sum_{S\subseteq D\setminus\{z\}}[v(S\cup\{z\})-v(S)]. The Shapley value is also defined similarly, but with a different weighting scheme over those subsets. Therefore, these two values give a more comprehensive view of the contribution of a data point to the model performance. Critically, the Shapley value has been mathematically proved to be the unique solution that satisfies the axioms of efficiency , symmetry , null player , and additivity ( 33 ) , while the Banzhaf value satisfies the same axioms except efficiency. These axioms are valuable properties that make both Shapley and Banzhaf values natural choices for fair and reliable data valuation. Among the axioms, efficiency requires that the value of the entire dataset is equal to the sum of the values of all data points, i.e., v(D)-v(\emptyset)=\sum_{z\in D}\phi(z), where \phi(z) is the Shapley value of data point z . The raw Banzhaf values do not satisfy the efficiency axiom, but this can be remedied by normalizing the raw Banzhaf values, a common post-processing step used in practice ( 36 ) . It is worth mentioning that though intuitively appealing, efficiency is not essential in many ranking-based applications, including dataset curation and data cleaning, where the focus is on the relative order of data-point values rather than their exact magnitudes. For these applications, Banzhaf can be a practical choice: it often yields sparser values and can be less affected by duplicate or noisy points. More broadly, the Banzhaf values can be more robust in certain scenarios ( 2 ; 41 ; 24 ; 19 ) . (a) Two selected test points (triangle and square) in a 2D dataset. (b) The values of the data points with respect to a boundary test point. (c) The values of the data points with respect to a test point that is far from the boundary. (d) Injected random noise (upper-left corner) to the 2D dataset, with test points in square. Figure 1 . The difference between the Shapley and Banzhaf values. The model performance is measured by the accuracy of a k\textsc{NN} classifier with k=5 . We illustrate the major differences between different values in Fig. 1 . The values of all data points in a 2D dataset ( Fig. 1(a) ) are computed with respect to a boundary test point (square) and a test point that is far from the boundary (triangle). Only three training data points have non-zero LOO values. After duplicating the dataset by creating a copy of each original data instance, all LOO values become zero. In contrast, most non-zero game-theoretic values remain non-zero and informative after duplication. This simple observation suggests that LOO values are less informative, especially in the presence of data redundancy ( 23 ; 3 ; 13 ) . Next, we compare the Shapley and Banzhaf values to illustrate why they can behave differently and be preferable in different applications. There are three key observations in Fig. 1 .

Read the complete text