🤖 machine learning

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

This paper addresses the computational intractability of Banzhaf-based data valuation for $k$ -nearest neighbor classifiers by proving the problem is \#P-hard and subsequently developing efficient exact algorithms with pseudo-polynomial and linear time complexities, alongside Monte Carlo estimation methods, to enable practical and fair data contribution assessment.

Original authors: Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis

Published 2026-05-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant pot of soup (your machine learning model) made from thousands of different ingredients (your data points). You want to know: Which specific ingredient made the soup taste the best? Did the pinch of salt matter? Was the carrot essential? Or was that weird spice just taking up space?

In the world of machine learning, this is called Data Valuation. The paper you provided tackles a specific, tricky version of this problem: figuring out the value of ingredients when using a specific cooking method called k-Nearest Neighbors (kNN).

Here is the breakdown of their work in simple terms:

1. The Problem: Counting is Impossible

To figure out exactly how much a single ingredient (data point) contributes, the "fair" way to do it is to imagine every possible combination of ingredients you could put in the pot, see how the soup tastes with that ingredient, and then see how it tastes without it.

The Analogy: Imagine you have 1,000 ingredients. To be perfectly fair, you'd have to taste the soup with every single possible mix of those ingredients (with and without your target ingredient).
The Reality: There are more combinations of ingredients than there are atoms in the universe. Doing this math is so hard that computer scientists call it #P-hard. It's like trying to count every grain of sand on a beach by picking them up one by one. It would take longer than the age of the universe.

2. The Solution: A Smart Shortcut

The authors realized that k-Nearest Neighbors (kNN) is a special kind of "soup." In kNN, the taste of the soup depends only on the closest few ingredients (the "nearest neighbors"), not the whole pot.

The Metaphor: If you are deciding what to wear based on the weather, you only care about the temperature and wind right now. You don't need to know the weather from three days ago or three miles away. The "far away" ingredients don't matter.
The Breakthrough: Because kNN only cares about the "closest" neighbors, the authors built a Dynamic Programming algorithm. Think of this as a smart calculator that doesn't taste every single soup combination. Instead, it builds a "recipe map" that lets it calculate the value of every ingredient instantly by looking at how the "closest neighbors" change.

They created three versions of this smart calculator:

For Weighted kNN: A fast method that handles ingredients with different "strengths" (weights).
For Unweighted kNN: An even faster method that treats all ingredients as equal. This one is so efficient it scales almost linearly, meaning it can handle massive datasets (millions of ingredients) that would crash other methods.
Monte Carlo Estimation: If the dataset is too huge even for their smart calculator, they offer a "sampling" method. Instead of tasting every soup, you taste a few random batches and guess the average. It's not perfect, but it's very fast.

3. Why Banzhaf? (The "Voting Power" Analogy)

The paper focuses on a specific mathematical formula called the Banzhaf value.

The Analogy: Imagine a committee voting on a decision. The Shapley value (another popular method) is like counting how often a person is the "swing vote" in every possible lineup of the committee, giving extra weight to tiny groups and huge groups.
The Banzhaf Difference: The Banzhaf value is simpler. It just asks: "In how many scenarios does this person's vote actually change the outcome?"
Why it matters here: The authors found that Banzhaf is often sparser and more robust.
- Sparsity: It gives a value of zero to ingredients that don't really matter, making it easier to spot the "stars" of the show.
- Robustness: If someone sneaks in a bunch of bad, random ingredients (noise), the Banzhaf method ignores them completely. The Shapley method might get confused and give those bad ingredients a tiny bit of credit, which messes up the whole calculation.

4. What They Tested (Real-World Proof)

The authors didn't just do math on paper; they tested their "smart calculators" on real data (like recognizing handwritten numbers or detecting credit card fraud).

Speed: Their new algorithms were thousands of times faster than the old "brute force" methods. They could handle datasets with hundreds of thousands of points in hours, whereas others would take days or fail completely.
Cleaning Data: They showed that their method is great at finding "bad apples." If you remove the data points their method says are "least valuable," the model's performance drops sharply. This proves they correctly identified the important data.
Finding Mistakes: They tested if the method could find data with wrong labels (e.g., a picture of a cat labeled "dog").
- Soft vs. Hard: They found that "Soft" methods (which look at probabilities) are better at finding random mistakes. However, their "Hard" Banzhaf method is better at finding the critical mistakes—those specific bad data points that are actually dragging the model's performance down the most.

Summary

This paper solves a massive speed problem. It takes a mathematically impossible task (fairly valuing every data point in a kNN model) and turns it into a practical, fast tool.

The Old Way: Try to count every grain of sand (too slow, impossible).
The New Way: Use a map to only count the grains that actually touch the path (fast, accurate).

They proved that for kNN models, you don't need to taste the whole universe of soup combinations to know which ingredient is the most important. You just need to look at the neighbors.

Technical Summary: Efficient Banzhaf-Based Data Valuation for $k$ -Nearest Neighbors Classification

Problem Statement

Data valuation, the task of quantifying the contribution of individual data points to model performance, is a fundamental challenge in machine learning. While game-theoretic approaches like the Banzhaf value offer principled frameworks for fair valuation, they suffer from exponential computational complexity. Specifically, computing exact Banzhaf values requires evaluating the value function over all possible subsets of the dataset, a task proven to be #P-hard in general. This computational burden renders exact computation infeasible for real-world datasets containing thousands or millions of samples, forcing most existing work to rely on approximation methods that trade accuracy for efficiency.

This paper addresses the specific challenge of computing exact Banzhaf values for $k$ -nearest neighbor ( $k$ NN) classifiers. The authors aim to bridge the gap between the theoretical foundations of cooperative game theory and the practical demands of real-world machine learning by developing algorithms that exploit the unique locality properties of $k$ NN to achieve significant computational improvements without resorting to approximation.

Methodology

The paper proposes a suite of dynamic programming (DP) algorithms tailored to the $k$ NN classification setting, alongside efficient Monte Carlo estimation methods.

1. Theoretical Hardness

The authors first establish the theoretical difficulty of the problem. They prove that computing Banzhaf values for the $k$ NN classification model is #P-hard. This is demonstrated via a reduction from the Weighted-Majority-Game (WMG) problem, a classical #P-hard problem in cooperative game theory. This result implies that, under standard complexity assumptions, no strongly polynomial-time algorithm exists for the general case.

2. Dynamic Programming Frameworks

Despite the hardness result, the authors leverage the locality property of $k$ NN (where only the $k$ nearest neighbors influence the prediction) to develop exact algorithms with improved time complexities.

Standard DP for Weighted $k$ NN:
The authors initially present a DP algorithm with a time complexity of $O(W n^4)$ , where $n$ is the number of data points and $W$ is the maximum sum of the top- $k$ weights. This approach defines a state function $f_i(w, s, m)$ representing the number of subsets of size $s$ with a specific weight sum $w$ and a specific $m$ -th closest point.
Improved DP for Weighted $k$ NN:
To reduce the complexity, the authors introduce novel techniques:
- Partial Sum Pre-computation: For the case where subset size $s \le k$ , they pre-compute partial sums to accelerate the recurrence relation, reducing the complexity contribution of this term.
- Binomial Coefficient Recurrence: For $s > k$ , they exploit recurrence relations of binomial coefficients to compute the sum of states efficiently.
- Result: These optimizations yield an algorithm with $O(W k n^2)$ time complexity.
Specialized DP for Unweighted $k$ NN:
For the unweighted case (where all weights are 1), the authors propose a specialized algorithm that achieves $O(n k^2)$ time complexity.
- State Space Redesign: They reduce the state space by eliminating the need to track the specific identity of the $m$ -th closest point.
- Forward and Backward Aggregation: They utilize forward ( $f_i$ ) and backward ( $b_i$ ) functions, along with signed backward functions ( $b^+_i, b^-_i$ ) to handle label signs.
- Result: Since $k$ is typically a small constant, this algorithm runs in near-linear time with respect to the number of data points.

3. Monte Carlo Estimation

Recognizing that even quadratic complexity may be prohibitive for massive datasets, the paper offers two efficient sampling-based methods:

Coalition-based Sampling: Optimized by maintaining only the top $k+1$ players in a sorted list, reducing complexity to $O(m n \log k)$ for $m$ samples.
Permutation-based Sampling: Adapts the permutation formulation of Banzhaf values via a re-weighting scheme, also achieving $O(m n \log k)$ complexity.

Key Contributions

Hardness Proof: The paper proves that computing Banzhaf values for $k$ NN classifiers is #P-hard.
First Exact DP for Weighted $k$ NN: It presents the first dynamic programming algorithm for computing exact Banzhaf values in weighted $k$ NN classifiers with pseudo-polynomial time complexity.
Optimized Weighted Algorithm: It significantly improves the time complexity of the weighted algorithm to $O(W k n^2)$ through novel algorithmic techniques involving partial sums and binomial recurrences.
Near-Linear Unweighted Algorithm: It introduces a specialized algorithm for unweighted $k$ NN with $O(n k^2)$ time complexity, representing the first near-linear time algorithm for computing hard-label $k$ NN-based game-theoretic values.
Efficient Sampling: It provides optimized coalition-based and permutation-based Monte Carlo methods that exploit $k$ NN locality for faster approximate estimation.

Experimental Results

The authors conducted extensive experiments on 12 real-world datasets (ranging from 5,404 to 1,000,000 data points) and synthetic data.

Computational Efficiency:
- The brute-force algorithm failed to complete within 10 hours for datasets as small as 30 points.
- The unweighted DP algorithm (bv-uw) demonstrated almost linear scaling, handling datasets up to $10^6$ points within the time budget.
- The improved weighted DP (bv-fast) scaled up to $10^4$ points, outperforming existing hard-label Shapley baselines (sv, sv-uw) which could not complete runs for $n \ge 10^4$ .
- Monte Carlo methods offered speed-ups of up to 25 $\times$ over the weighted DP when accepting a deviation of approximately 0.02.
Practical Applications:
- Point Removal: Removing data points with the highest Banzhaf values caused a sharper drop in model accuracy compared to other methods (like LOO or Influence Functions), indicating these points were critical to performance.
- Data Selection: Selecting points with the highest values incrementally improved model accuracy faster than random selection or other baselines.
- Mislabel Detection: The study highlighted a trade-off between valuation types. Soft-label Shapley values were better at detecting randomly flipped labels (high $F_1$ score). However, hard-label Banzhaf values were superior at identifying decisive low-quality points whose correction significantly improved model performance. Hard-label values were more robust to noise and better suited for data cleaning where the goal is to fix points that actually change predictions.

Significance and Claims

The paper claims to provide the fastest algorithms for hard-label Banzhaf valuation in $k$ NN, even surpassing the efficiency of their hard-label Shapley counterparts. The significance lies in making exact game-theoretic data valuation computationally feasible for large-scale datasets, a task previously limited to approximations.

The authors emphasize that while the Banzhaf value does not satisfy the efficiency axiom (the sum of values equals the total value) without normalization, it offers distinct practical advantages:

Sparsity: It produces sparser values, highlighting a concentrated set of influential points, which is beneficial for exemplar-based interpretability.
Robustness: It is more robust to noise and duplicate data points compared to Shapley values, which can be overly sensitive to extreme subsets.
Practicality: The developed algorithms enable the application of rigorous data valuation in scenarios like data acquisition, cleaning, and collaborative learning, where understanding the relative order of data point importance is crucial.

The paper concludes that while the framework does not directly extend to $k$ NN regression due to non-decomposable normalization terms, it successfully bridges the gap between cooperative game theory and practical machine learning applications for classification tasks.