Shapley-Based Data Valuation for Weighted $k$-Nearest Neighbors
Authors: Guangyi Zhang
Qiyu Liu
Aristides Gionis
Venue: NeurIPS 2025 poster ()
Keywords: Data valuation
Shapley values
Nearest Neighbors
Primary area: general_machine_learning
TL;DR: We propose a new method to compute exact Shapley values for weighted k-Nearest Neighbors in near-linear time.

Abstract: Data valuation quantifies the impact of individual data points on model performance, and 
Shapley values provide a principled approach to this important task due to their desirable axiomatic properties,
albeit with high computational complexity. 
Recent breakthroughs have enabled fast computation of exact Shapley values for unweighted $k$-nearest neighbor ($k$NN) classifiers. 
However, extending this to weighted $k$NN models has remained a significant open challenge. 
The state-of-the-art methods either require quadratic time complexity or resort to approximation via sampling.
In this paper, we show that a conceptually simple but overlooked approach --- data duplication --- can be applied to this problem, yielding a natural variant of weighted $k$NN-Shapley.
However, a straightforward application of the data-duplication idea 
leads to increased data size and prohibitive computational and memory costs.
We develop an efficient algorithm that avoids materializing the duplicated dataset by exploiting the structural properties of weighted $k$NN models,
reducing the complexity to near-linear time in the original data size.
Besides, we establish theoretical foundations for this approach through axiomatic characterization of the resulting values,
and empirically validate the effectiveness and efficiency of our method.

Shapley-Based Data Valuation for Weighted k--Nearest Neighbors
Guangyi Zhang Shenzhen Technology University zhangguangy1@sztu. edu. cn
Qiyu Liu"
Southwest University
wes.uu.ss@mmal...m com
Aristides Gionis'
KTH Royal Institute of Technology and Digital Futures argioniskth..
Abstract
Data valuation quantifies the impact of individual data points model performance, and Shapley values provide a principled approach to this important task due to their desirable axiomatic properties, albeit with high computational complexity. Recent breakthroughs have enabled fast computation of exact Shapley values for unweighted k-nearest neighbor (kNN) classifiers. However, extending this weighted kNN models has remained a significant open challenge. The state-of-the- art methods either require quadratic time complexity resort approximation via sampling. In this paper, we show that a conceptually simple but overlooked approach data duplication - can be applied this problem, yielding natural variant of weighted kNN-Shapley. However, straightforward application of the data-duphl duttaduplication idea leads increased data size and prohibitive computational and memory costs. We develop efficient algorithm that avoids materializing the duplicated dataset by exploiting the structural properties of weighted &NN models, reducing the complexity to near-linear time in the original data size. Besides, we establish theoretical foundations for this approach through axiomatic characterization of the resulting values, and empirically validate the effectiveness and efficiency of our method.
Introduction
In the of data-driven machine learning, understanding the value and contribution of individual data points has emerged as critical challenge. Data valuation-the process of quantifying the impact of each training instance on model crrformance-plas including identifying influential samples, detecting mislabeled data, and designing data markets [ As machine-learring systems continue to proliferate across domains, the development of robust and scalable Nata-valuation methods has become increasingly essential.
pivotal role in numerous applications.
Among various approaches for data valuation 33, 51, the Shapley value from cooperative game theory has attracted significant attention due to its unique desirable axiomatic properties (6]. When applied to machine learning, data Shapley values provide principled framework for distributing the model's performance among training instances, where each data point's Shapley value represents its average marginal contribution across all possible subsets the dataset [
Despite its thcoretical appeal and desirable properties, the exact computation of data Shapley values presents substantial challenges, requires enumerating and re-training over all possible subsets
"Conesponding authors
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

of data points task whose complexity grows exponentially with the dataset size. Indeed. the computation has been proven to be #P-hard in certain games [7]. Fortunately, a notable recent advancement in this domain by Jia et al. g leverages the structural properties of unweighted k- nearest neighbor (kNN) classifiers to efficiently calculate exact data Shapley values closed form, referred to as unweighted &NN-SV hereafter. The kNN approach is a classic algorithm in machine learning, and has been shown that running ANN over pre-trained embeddings can yield comparable performance with more advanced models [2].
However, a significant limitation of the approach by Jia al. [ lies in its restriction to unweighted KNN models. In practice, weighted ANN models, which assign different importance to neighbors based on their distances, offer greater flexibility and typically yield superior performance. Computing Shapley values for weighted ANN models poses unique challenges due to the lack of closed- form solution analogous to the unweighted case. To date, the only successful attempt has been a hard-label variant of weighted kNN-SV (IO), which invokes a sophisticated and time-consuming dynamic-progee programmngg approach that is similar in spirit to those for power indexes M..
In this paper, we offer a novel variant of weighted KNN-SV, dubbed as DANN-SV for duplication- based weighted kNN-SV, whose underlying classifier is equivalent the standard weighted ANN classifier. We demonstrate that this weighted variant can be effectively reduced to the unweighted case by a duplication technique. Since naïve duplication could significantly increase the dataset size and computational burden, we further develop an efficient algorithm that exploits the structural properties of the weighted ANN models, thereby eliminating the additional computational costs associated with data duplication. In other words, the data duplication has been made conceptual and does not need to be materialized. Our algorithm runs in near-linear time O(n log n), while the fate-of-theear methods either require a pseudo- polynomial time complexity of "WWk??" [I0] or settle for approximation by sampling from n! permutations (8), where n the dataset size and is the maximum weight. We analyze the theoretical properties of the proposed DkNN-SV scheme, and empirically validate its effectiveness and efficiency against other &NN-SV variants. For example, our algorithm performs better at the task of noisy label detection.
The rest of the paper is organized as follows. First, we review the preliminaries in Section and the unweighted kNN-SV V in Section 3, Next, we introduce the new weighted DANN-SV in Section 4 and develop an efficient algorithm for it in Section [ We discuss the related work in Section Finally, we empirically evaluate the proposed method in Section We conclude in Section 8 All proofs are deferred to Appendix A
2 Preliminaries
In this section, review the framework for data valuation based on Shapley values (SV) and establish our notation for applying this concept to the k-nearest neighbor (kNN) model.
2.1 Cooperative game theory and Shapley values
The concept of data valuation can be elegantly formalized through the lens of cooperative game theory [12]. In this framework, we consider collection of players who form coalitions to generate collective utility. Formally, a cooperative game consists of a pair (I, util), where / = {1,..... ; represents set of n players and util 2' - R is utility function that assigns real value each possible coalition S I.
A central question in cooperative game theory concerns fair allocation: how should the total utility be distributed among individual players based on their contributions? The Shapley value, introduced by Lloyd Shapley (6. provides a rigorous solution to this problem. The Shapley value s(i) for player i represents their expected marginal contribution when joining the coalition a random order. Let II denote the set of all permutations of players in I. For permutation E 11, let n, represent the set of players that precede player in æ. Then, the Shapley value equals
sii) 1 Σ [ U (i)) (t:)
(I)
2

---

An equivalent expression represents the Shapley value as the average marginal contribution across all possible coalition formations, that
si)
1 nE SCN
Σ
n SS] )
(s util(
(2)
is well known that the Shapley value is the unique allocation mechanism that satisfies the following desirable properties: efficiency, symmetry, null player, and additivity [6]. These properties make the Shapley values a principled approach for data valuation, relying on an axiomatic framework.
To apply the Shapley-value framework to the data-valuation setting, we interpret individual data coalition game, and performance measure of model as a utility function. The value of the utility function for a coalition of players corresponds to the performance measure of the model trained on the respective subset of data. This framework allows for quantifying the contribution of each training data point to the overall model performance.
points as players
2.2 ANN-based Shapley values
In this section we discuss how the Shapley-value framework described above can be used for data valuation with a kNN model [8]. We refer to this method as kNN-SV The idea is first presented for single test data point, and then extended to multiple test data points.
Consider a dataset D with n training data points, where each point (xr, y) E comprises x E IRd and y V, where is the label space. Consider also single test data point 2iest (Fress Mesa). We want to compute the Shapley value s(x 2test) of each training point 2 E D with respect to the test point Stest For each point we consider rational weight w(= Arest E Q+. often determined by the distance between ı and Tiest (see discussion below). For a subset S C D of the training data, the
NNN utility of S is defined
Emia (11.8) (a) (iex) (Ha,( Mex)
if S > 0
util(S) =
E w[Ra, (8) (ass)
if S = 0,
where C= [ is the number of classes, (S) the index of the i-th closest point of S to Ziests and i is the rank of (S) in S.
For defining the weight w(z mess), the case of unweighted KNN, we simply set w(s zeea) 1. More generally, by using the distance dist(z, z²) || x we can define the weight w(= zeeat as the Gaussian kernel w(2 &usa) = ((dist(2, )ess)) = exp( -ditt(z, (2, Zress) /22""), where a measures the width of the kernel. Clearly. any other distance metric be used.
Having defined the utility function for subsets S S D. the Shapley value of data point D can be computed using Eq. L Formally, the Shapley value of a training data point E D concerning single test data point Stest defined as
s(2 Ziea)
Σ SCD)(=)
n (M=]) [8]
[util(S (z}) util
In practice, when given multiple test data points, the data Shapley value of data point & can be straightforwardly extended as the average over all test points. That is, when given a test dataset D of Thes data points, we have
8(2)
Σ
8(2 Zres)-
(5)
Frees
E Dess
3 Exact computation for unweighted KNN-SV
In this section, we introduce the analytical solution to unweighted ANN-SV, introduced by Jia et al. 8 and a subsequent note [13] This solution results in a dramatic improvement in the time complexity for exact computation, from O(2") to O(dn log n) for a single test point, over the naive approach that enumerates all possible subsets S of the datasct D.
3

---

We fix a test point Sest throughout this section. Given a subset S S D, recall that (s)(S) is the index of the i-th closest element of S Ates. When the context is clear, we write (D) as 2; and (()a(()) 2tsst) as wi for simplicity. Similarly, we denote by s; the Shapley value s(z; Ørest) for data point 2/-
We restate the main result from Wang and Jia 13 for unweighted &NN-SV. For ease of exposition, we assume n 2 2 and n 2 throughout the paper.
Theorem (Wang and Jia [3). Assume n 2 and a 2 k. For the unweighted kNN classifier, the Shapley value of a data point 2, be computed as follows.
Sn [ 1n Σ
Σ
1,
C-1
(6)
n2
where 11 = 1ly-- yeest and i n,
8; = 91+1 + 1; - li+1
k Σ 1
minfk: i) 11) -k)
(7)
11 -
Following Theorem I we can compute the Shapley values by first sorting the data points by increasing distance to Stest: and then iteratively computing the Shapley values in the reverse order, as specified by Eq. (6) and Eq. (7).
However, extending the previous result to the weighted KNN is challenging. Given a subset S, we refer the quantity US U {=;}) - US as the marginal contribution (MC) of z to S. The key principle behind the result in Theorem [ is that for unweighted kNN, the MC can only take a few distinct values, which turns kNN-SV problem into combinatorial counting problem. For example,
for any |S| 2 k. we have
(S U {++)) ut) or uS util(S) = (1 = yhess] 1[Maxx(S) = Meea]
the latter of which only takes three possible distinct values. Thus, one can simply count the number of subsets S for each distinct MC value, and aggregate the results, without evaluating the MC for all possible subsets. However, for weighted ANN, as in Eq. (3). the MC may take arbitrary values due to the weights and the normalization term
4 Weighted KNN-SV via data duplication
In this section, we show how to overcome the challenge in the weighted kNN-SV problem. We do so by introducing new variant and reducing it to the unweighted case using novel data-duplication technique. We relate the new variant to the concept of Owen values [14], and prove adherence to axiomatic properties. We further compare it with other ANN-SV variants analytically in Section 4.2
Our main idea to create w(= Fies) - 1 copies of every point = E D. For ease of exposition, we assume that all weights are integers. This assumption can be easily removed by scaling the weights appropriatcly. Let the new dataset containing and its copies be D', We will then apply the unweighted ANN classifier to D' with parameter k".
To obtain an equivalent weighted KNN classifier, we adaptively k' for each test point उeest 155 Specifically, we adjust k so that it includes the top-k nearest neighbors of Zes in D and their copies. Formally, we set
k Σ w (o(Za.(D) Reea)-
k'
(8)
We show that this leads to an equivalent weighted &NN classifier.
Proposition 2. Running unweighted kNN classifier on a duplicated dataset D' with parameter k
defined Eq. K) is equivalent running weighted kNN classifier on the original dataset D for any
test point Zrest-

---

Fixing test point Leest, we define the utility of unweighted ANN on D' for any subset S' of D' as
min
1(y (89) Mux)
if if IS = 0.
S'"
min
[5] [2)
The Shapley value of a data point E D' concerning given test point Stest is then simply
Σ (n'-
[SS ("/ST)) -1
s((2 Ziest)
[util((S' u {=}) util((
(10)
n' S'CD'(=
The DANN-SV of a data point 2 E D is the sum of the Shapley values of all its copies in D', i...,
<(=
Ziest)
Σ
8'(2' (ees) = w(= (rest) (z
Ziest)
(11)
x'ED's''s
Note that duplicating data points according to their weights may result in a dataset D' much larger than D, which may cause significant scalability issues. We will address this challenge in Section by proposing an efficient algorithm that avoids materializing D'.
4.1 Duplication-basee weighted &NN-SV as group values
An alternative way to interpret the DENN-SV 6(2 Erea) is to view a data point 2 and its copies as a "group" with z being the representative of the group, and 6(= Ztest) measuring the value of the whole group. This is similar to the classic concept of Owen values [4] which characterizes the value of players in game with coalition structure.
Formally, to compute the Owen values, we are given non-overlapping groups 9 = [GI..... Gm3 such that - G2 D' and G2 G2 0 for all i # j. Owen values are caleulated by considering permutations of players that are compatible with the group structure. A permutation и of the player set D' is called group-compatible if players within the same group G; appear consecutively in the permutation. The Owen value of a player z' is its average marginal contribution over all group- compatible permutations, computed in way similar to Eq. ( The only difference is that the Owen value sums over all group-compatible permutations instead of all permutations. The Owen value of a group G; is then the sum of the Owen values of all players =' E G..
In our setting, each group is a set of copies of a single point. The main difference is that we do not require all players in group to always act as unit, and thus do not require the permutations to be group-compatible Instead, we allow each player (data point) to act independently in the game, and eventually aggregate their contributions to obtain the group value in the same manner. This relaxation allows us to design an efficient algorithm. Our approach can also be justified axiomatically. These axiomatic properties ensure that data valuation is conducted in fair, theoretically sound, and interpretable manner for downstream tasks. Moreover, additional properties about symmetry between and its copies enable us devise a fast algorithm without materializing D': see Section 5
Theorem 3. The group value o(2 Erest) defined in Eq. (11) satisfies the following axioms:
1. Efficiency: ExED 6(2 Zrea) = (i") utif(() mtil(D) - uiil((), that is, the sum of all group values equals the total utility.
2. Symmetry: If 21 and 22 are such that ut U {x1)) = (S U (2/3) for all S' C D' {24, 2/23 where of and 2/2 are copies of 21 and 22 respectively, then 0(21 2res) //w())/(( (22
Zven) = 6(22 Fwed//wl /w(22 Znew).
3. Dummy Player: If z is such that uttit(S" U utif((")) ( for all S' C where o' is a copy of 2. then Φ(2 Zrest) = 0.
4. Additivity: If utill and util, are two utility functions, and Φ1 and d2 are their corresponding values, then the value o corresponding to util' + util,, satisfies & = Φ1 + Φ2.
Theorem 3 can be easily extended to more general settings, where each group is formed by an arbitrary subset of players instead of a set of copies.
5

---

4.2 Comparison with other KNN-SV
Comparison with standard weighted ANN-SV. Although Proposition shows that the duplica- tion strategy provides an equivalent weighted KNN classifier, it may not produce the same Shapley values. This is because we need equivalent classification over all possible subsets instead merely the entire dataset D. More generally, we show that their values remain different regardless of the value of parameter K'. We give counterexample below. The intuition that the effect of increasing the weight of point and increasing its number of copies on its value is similar over most subsets, but may differ over certain subsets.
Proposition 4. In the genral case, the group Shapley values in Eq. Shapley values of weighted kNN-SV Eq.
11
may be different from the
Hence, our duplication strategy offers a new variant for computing data Shapley values for weighted kNN-SV. Due to the lack of closed-form derivation for the vanilla weighted &NN-SV, we compare the different methods empirically in the experiments, and show that they are correlated, however, the values in the proposed approach can be computed more efficiently.
Comparison with the sealed unweighted ANN-SV. One might also wonder how the group values 6(2 Seest compare to simply scaling the unweighted &NN-SV values s(2 Zee) in the original dataset D. A natural scaling approach might be s(2 &ust) w(2 Eees). However, such scaling is fundamentally different from our duplication strategy, and fails to capture the inherent weighted nature of the weighted ANN-SV, as illustrated the analysis below.
Given an arbitrary test point Sestt we first examine the scaled value &n of the farthest point An.
n
Wn
1 -
- i=1
1, n
Σ
1n t
s, = Sn Wn
+ wn
n n'
n'
where Wi, w((z, Rest) and 1; 11/ Vhes)). To simplify the analysis, we set k to be the same as k. If we compare the scaled value 8n with the group value (izn zwal, we have
Wn nd
n-1
(wn 1)1, + wil
Σ J+1
8n - -(( Zress)
1n
1,
n
weighted avg
unweighted avg
Thus, the difference driven by the choice of the reference mean used the comparison. Define unweighted and weighted reference means
1
(wn, 1)11, + E. w.1,
Panw Σ
and
Mw
n
1=1
Then the scaled value 8,, uses the deviation 1, Munw, which measures the contribution of on by the deviation of its label from this unweighted reference mean, whereas the group value considers the deviation from the weighted reference mean by using 1n -lw
Moving on the scaled value of the i-th closest point 2,, we have
n
$
s:w, n1'
1,
1 1i+1
k 1
min iJ -k)
8:41 W.
+
W
n1'
n1
n¹
j
min(k, i)(n - -k) -x) )
1; 1i+1
864 00g
W1
To
where the last approximation follows by taking
n-1 n w
R 1. Then, if we compare the scaled value
3; with the group value <b2; Piest), we have
5; o(z 2

---

Algorithm 1:
Fast algorithm for duplicate-based weighted ANN-SV
Input: Integer k; weight function w, datasets D and Diest
Initialize Øs with default value 0 for every 2 E D
for Ztest Dreet do
3
Let 21, 21,...; be the points in D sorted by increasing distance to
4
n' t Σ ==1 w(zi Reest)
5
k' Σ k
==1 w(2;
2test)
6
S'2n t +
1n
(wo 1)an wil,
(Ejzn (ti) + L-=1/C,
where
ni
n
w; = w(2; (rost) and 1, Ui Vteat
7
for n1 -,...,1 do
1' Ej=1((z)
(((2) Ztest)
8/2, + s'z.m + -i-li-1
n'-l 22 1 1 minik' d')(n''1) k')
9
for ...... do
22 0z w(zzs Ftret))ls
for D do
13
Φ= 0z/ mees
Return values {0z 22E
814-77 ((2(41)
1; 1:+11 1 n'
min(k, il(n 1) min I' - -1)
+
n
W/+1
k
First, the difference between these two values accumulates from the previous (i + 1)-th point. In addition, the contribution from the i-th point to the scaled value š; is roughly weighted by (f(n-1) 1(m'=1) while the contribution the group value <f=; Frest) is roughly weighted by #. That is, the former scales up every rank uniformly by a factor of n'-1 n-T while the latter uses the rank i' of the i-th point in the duplicated dataset D'. Therefore, the scaled value tends to amplify the contribution of nearest. neighbors with a large weight more than the group value.
5 Fast algorithm for duplication-based weighted ANN-SV
Recall that we duplicate data points in D according to their weights to form a new dataset D However, the size of D' may be much larger than that of D. This poses significant challenge to the computational cost of the recursive computation of the Shapley values. Specifically, it requires On' log n') time for each given test point, where n' is the size of D'. this section, we propose a fast algorithm for the duplication-ben based weighted ANN-SV, with time complexity as small as On log n). The algorithm successfully obtains the Shapley values while avoiding materializing the duplicated dataset D'.
The proposed algorithm is displayed in Algorithm I The key idea is to leverage the symmetry property of the Shapley values to avoid materializing the duplicated data points.
Lemma 5. Fix a test point zust- Lei be point in D. Then, every copy z' of z has the Shapley value (2') Zrest) as that of z. This continues to hold when the values are obtained by applying the recursive formula Theorem 7 with an arbitrary order among z and its copies.
Therefore, when applying the recursive formula in Theorem I once, and skip its copies by directly multiplying the Shapley value by the number of its copies. This valid as a result of Lemma imagine we are taking an order where is behind all its copies and processed first.
we only process every point & D
Note that the partial sum of the harmonic series can be accurately approximated by the Fuler- Maclaurin formula [16), or retrieved from pre-computed table. Asymptotically, the Macle--a
7

---

formula [6] F() below converges to the harmonic series H, = =EE= ! as j + 00.
1
F(j) = 10() +
2j 12j²¹
where 7 R 0.5772156649 is the Buler-Mascheron constant. In practice we adopt the following more accurate approximation scheme. When j is a small constant (e.g.. E 1000), we can afford to compute H, exactly. Otherwise, we use F(j) F(1000) + H1000 as approximation (in (1)) time where 1000 is pre-computed) to climinate the noticeable error when j is relatively small. We verify that the absolute error most 4.167 x 10- for up to I million and continues to decrease as j increases. We believe this approximation is sufficient for our purpose.
Hence, the total time complexity is dominated by the sorting step, which is O(n log n). In addition, distance computations cost (dn) time. We summarize the results in the following theorem. Theorem 6. Algorithm 7 computes duplication- based weighted kNN-SV in Odn + nlo n) time.
Related work
Data Valuation.
Data valuation aims assign importance scores to training examples 345 The
dominant approaches are based on the concept of leave-one-out (LOO), which measures the marginal contribution of a data point to the utility function (c.g., model accuracy) when it is removed from the training procedure. DataShapley (1 and its variants such as BetaShapley [7]. DataBanzhaf [18), least core [19], are all based on the LOO principle, but differ in the way the marginal contributions aggregated. We discuss several notable options beyond Shapley values below. Feldman and Zhang (20 simulate the data values by LOO retraining albeit constrained on a small sample of the training data, while DataModels [2]] sacrifice the exactness of LOO to achieve better scalability by model predictions. Another line of popular methods gradient-based. TracIn [22] estimates the importance of a training example by tracing the change in the test loss caused by the example during the training
process. Variations of influence functions 23 24 have their roots in robust statistics 25 and offer
a gradient-based approximation of the LOO values.
Shapley Values. Shapley values (6] originated in cooperative game theory as method for fairly distributing gains among players, and have been widely adopted in multiple fields such as eco- nomics [26]. Computing exact Shapley values is well-known to be expensive, i.e., #P-hart in certain games 77.. This computational challenge has motivated various approximation techniques, including mostly Monte Carlo sampling [27] 28 29 30), and specialized algorithms for specific games BI]. Our work falls into the latter category. Early work on Shapley values with exogenous coalitions distributes among players from group G the utility util(G), respecting the so-called relative efficiency axiom. Owen [4] and subsequent work (32) further consider a game between coalitions. Our duplication technique creates natural coalitions in the game.
Shapley Values (kNN-SV). The k-Nearest Neighbor (ANN) model provides a unique opportunity for efficient computation of data Shapley values. Jia et al. S are the first to discover an efficient algorithm in time O (Mteet log n) for unweighted kNN-SV. Wang and Jia [ provide refinements to the unweighted ANN utility function. The weighted ANN case turns out to be more challenging due to the normalization factor in the utility function. Wang et al. [0] propose a time- consuming
algorithm for weighted &NN-SV with hard label utility function. Our work offers a more efficient approach for weighted KNN-SV.
Experiments
We investigate the following research questions in the experiments: (1) How does Algorithm perform compared with the existing methods? We study this question with a task of noisy label
detection. See Section 7.1 (2) How does the D&NN-SV deviate from those of the unweighted and
weighted kNN-SV formulations' We visualize and compare them in Section 7.2 (3) How the
scalability of Algorithm[[P We study this in Fig. 1b and further in Appendix B.3 (4) What is the
effect of the parameters on Algorithm [T
We study this Fig. Ic and more in Appendix B..
Datasets. We evaluate the proposed methods on 11 datasets, whose statisties are listed in Table AT
The size of the datasets ranges from 5K to IM. Many of them are chosen to be of a moderate size, so
8

---

click
2dplanes
1.5
unweighted
Positive/ NNegative valuues
unweighted
Running (seconds)
10
dup
0.45
dup
dup
mc-100
0.5
mc-1000
10P
Fl sccoee
0.40
unweighted
0.0
10
0.35
-0.5
0.30
10a
10a
10
sorted by distance
(b)
Figure 1: Visualization of the Shapley values of different methods concerning a random test point (Fig. Tap. The running time on random 1-dimensional dataset of different sizes (Fig. Tb). The effect
of the parameter k on the performance of different methods (Fig. Tcl.
as to allow us to compare with more costly baselines. By default, we randomly select 1% the data up to 100 points as the testing set.
Baselines. We include the following baselines in the experiments: (1) unweighted &NN-SV (un-
weighted), (2) scaled unweighted KNN-SV (scaled) in Section 4.2 (3) weighted &NN-SV (mc) by
fast Monte Carlo sampling g with different number of samples, (4) random selection (random), and finally (5) our duplication-base bassed D&NN-SV in Algorithm (dup). (dup). The hard-label weighted kNN-SV [0O] is not included as it fails to finish within hours on small datasets (with default dis- cretization bits Rbits 3),
report comparison results with it tiny datasets in Appendix [.1 Our code can be found at a Github repository 2 By default, we run each algorithm three times and report the average results.
7.1 Noisy label detection
To evaluate the performance of different methods, we follow the setup previous works 8 13 10 and use the task of noisy label detection. For each dataset, we randomly flip the labels of 5% of the training data points, which forms a noisy subset of size n/20. We predict the noisy subset by the top-/ data points with the lowest Shapley values. We set = 500 for all methods. Intuitively, stronger data valuation methods should be able to detect noisy data points more accurately.
We tune the key parameter, kernel width a, of all algorithms that use kernel function as follows. We randomly select 5% of the training data as a validation set. We train weighted kNN classifier on the rest of the data, and evaluate its accuracy on the validation set. We select the value that gives the highest accuracy from list of candidates. Note that no information about the noisy labels is leaked to the validation process.
The results shown in Tables 1 and 2 with standard deviation. Our proposed algorithm dup consistently outperforms all the other methods on most datasets. Its running time is slightly higher than that of the unweighted kNN-SV due to the additional cost in weighting the data points, but still very efficient. The weighted kNN-SV (mc) achieves better performance as the number of samples increases; however, only reaches the performance of unweighted &NN-SV when the sample number is as large as 1000 and is nearly 1000 times slower. The scaled kNN-SV (scaled) is comparable to the unweighted kNN-SV. SV. All methods perform significantly better than random selection.
7.2 Visualization of Shapley values
We visualize the Shapley values of different methods with respect to a random test point Fiest as follows. We sort all data points by increasing distance ziest and plot their Shapley values. Besides, we plot the positive and negative values separately. We limit the number of points to the top 100 as the rest are all close to zero.

---

Table Fl scores of different methods on the noisy label detection task. in bold, and the second best is underlined. *." indicates timeout.
The best one is highlighted
unweighted
dup
scaled
random
mc-10
mc-100
mc-1000
phoneme
0.318 + 0.074
0.283 + 0.167
0.232 + 0.090
0.032
0.225
0.298
0.318 + 0.074
wind
0.286 = 0,026
0.357 +: 0.017
0.277 + 0.009
0.043
0.240
0.283
0.289 0.017
cpu
0.507 = 0.089
0.565 1.014
0.444 + 0.000
0.049
0.365
0.486
0.507 0.096
2dplanes
0.342 = 0.021
0.368 =
0.330 + 0.027
0.055
0.226
0.339
0.351 0.016
apsfail
0.746 = 0.004
0.795
0.737 + 0.020
0.055
0.520
0.732
0.749 0.003
click
0.070 + 0.021
0.072 0.033
0.059 0.011
0.055
0.054
0.067
0.069 0.017
creditcard
0.119 0.040
0.132 0.050
0.120 0.039
0.055
0.102
0.118
0.118 0.036
fraud
0.879 = 0.003
0.888 0.010
0.874 0.019
0.055
0.737
0.853
0.881 0.011
pol
0.420 + 0.003
0.447
0.021
0.425 0.024
0.055
0.390
vehicle
0.140 + 0.007
0.119 0.031
0.055
0.111
0.128
0.138 0.007
poker
0.150 = 0.002
0.305 + 0.001
0.137 0.001
0.050
0.069
Table 2: Running time (seconds) of different methods on the noisy label detection task. The best one highlighted in bold, and the second best underlined. 1-' indicates a timeout.
unweighted
dup
scaled
random
mc- 10
mc-100
100
mc-1000
phoneme
1.2 + 0.2
1.3 0.1
9.8
92.1
874.1 + 25.5
wind
1.5 + 0.0
2.4 0.2
1.9 0.1
0.0
14.9
129.2
1278.2 26.6
cpu
2.300.2
4.2
0.3
0.0
22.3
206.7
1975.4 = 12.3
2dplanes
3.5
5.8 4.8+0.0
4.2
0.0
33.5
307.5
2961.1 = 69.8
apsfail
3.4
5.7
0.5
0.0
33.7
299.0
2940. 447.7
click
0.3
5.6
4.3
33.9
302.4
2931. 39.7
creditcard
3.4
5.4
4.7
0.0
33.9
305.7
2952.4 49.5
fraud
3.4
5.3
0.3
0.0
33.9
300.0
2923.2 = 27.9
pol
3.6 0.3
5.6
4.5
0.0
33.1
297.2
2937.4 29.1
vehicle
3.5 0.0
5.6
0.3
0.0
34.6
307.2
2948.2 4.2
poker
368.7 = 41.9
637.4
496.5
36.7
3606.3
The representative visualization shown Fig. and more in Appendix B.2 similar pattern and assign larger absolute values nearer points. One common property that is shared by dup and me is that they are able to differentiate the nearest points, while the unweighted kNN-SV often assigns an equal value to, for example, the top 10 points.
All methods follow
Conclusion
In this paper, introduced novel variant of weighted ANN-SV that leverages duplication technique to reduce the weighted case to the unweighted one effectively. This variant successfully captures the weighted nature of the &NN models and maintains the desirable axiomatic properties of Shapley values, while being amenable to efficient computation.
We discuss limitations and directions for future work. Our method does not solve the original weighted kNN-SV problem but rather a new variant of it. Though the resulting data values can be justified axiomatically, they are not Shapley values. Several promising directions for future work include extending our approach to ANN regression tasks, and investigating the applicability of our duplication technique to other ANN-related scenarios.
Acknowledgments and Disclosure of Funding
This research is supported by the ERC Advanced Grant REBOUND (834862), the Swedish Research Council project ExCLUS (2024-05603), the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, Guangdong Provincial College Youth Innovative Talent Project (Grant No. 2025K Natural Science Founda- tion of Top Talent of SZTU (Grant No. GDRC202520), SZTU University Research Project (No. 202510 101100002))) and fundamental research funds for the central universities of Ministry of Educa- tion of China (SWU-KR24043)
10

---

References
[1] Amirata Ghorbani and James Y. Zou, Data shapley: Equitable valuation of data for machine learning. In Proceedings of the 36th International Conference on Machine Learning, pages 2242-2251. PMLR, 2019.
[2] Ruoxi Jia, David Dao, Boxin Wang. Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas Spanos. Towards efficient data valuation based on the shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1167-1176. PMLR, 2019.
[3] Zayd Hammoudeh and Daniel Lowd. Training data influence analysis and estimation: survey. Mach. Learn., 1 113(5):2351-244) --033 2024.
[4] Kevin Fu Jiang, Weixin Liang, James Y. Zou, and Yongchan Kwon. Opendataval: a unified benchmark for data valuation. Advances in Neural Information Processing Systems, 36:28624 28647, 2023.
[5] Rachael Hwee Ling Sim, Xinyi Xu, and Bryan Kian Hsiang Low. Data valuation in machine learning: "ingredients", strategies, and open challenges. In Proceedings of the 7 Thirty-Firr Inter- national Joint Conference on Artificial Intelligence, IJCAI-22, pages 5607-5614. International Joint Conferences on Artificial Intelligence Organization, 2022.
[6] Lloyd S. Shapley. A value for n-person games. In Contributions to the Theory of Games, Volume 11, pages 307-318. Princeton University Press, Princeton, NJ, USA, 1953.
[7] Xiaotie Deng and Christos H. Papadimitriou. On the complexity of cooperative solution concepts. Math. Oper. Res., 19(2):257-266, 1994.
[8] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gürel, Bo Li, Ce Zhang, Costas J. Spanos, and Dawn Song. Efficient task-specific data valuation for nearest neighbor algorithms. Proc. VLDB Endow., 12 16110--6161,,3,, 2019.
[9] Ruoxi Jia, Fan Wu, Xuchui Sun, Jiacen Xu, David Dao, Bhavya Kailkhura, Ce Zhang, Bo Li, and Dawn Song. Scalability vs. utility: Do we have to sacrifice one for the other in data importance quantification? In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8239-8247, 2021.
[10] Jiachen T. Wang, Prateek Mittal, and Ruoxi Jia. Efficient data Shapley for weighted near- est neighbor algorithms. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, pages 2557-2565. PMLR, 2024.
[11] Tomomi Matsui and Yasuko Matsui. A survey of algorithms for calculating power indices of weighted majority games. Journal of the Operations Research Society of Japan, 43(1):71-86, 2000.
[12] Edith Elkind and Jörg Rothe. Cooperative game theory. Economics and computation: an introduction to algorithmic game theory, computational social choice, and and fair division, pages
135-193, 2016.
[13] Jiachen T. Wang and Ruoxi Jia. A note on "efficient task-specific data valuation for nearest neighbor algorithms", 2023.
[14] Guilliermoo Owen. Values of games with a priori unions. In Mathematical economics and game theory: Essays in honor of Oskar Morgenstern, pages 76-88. Springer, 1977.
[15] Akshay Balsubramani, Sanjoy Dasgupta, Shay Moran, et al. An adaptive nearest neighbor rule for classification. Advances in Neural Information Processing Systems, 32, 2019.
[16] Ralph P Boas Jr and John W Wrench Jr. Partial sums of the harmonic series. The American 1971.
Mathematical Monthly, 78(8):664-88
[17] Yongchan Kwon and James Zou. Beta shapley: unified and noise-reduced data valuation framework for machine learning. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pages 8780-8802. PMLR, 2022.
[18] Jiachen T. Wang and Ruoxi Jia. Data banzhaf: A robust data valuation framework for machine learning. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, pages 6388-6421. PMLR, 2023.
[19] Tom Yan and Ariel D Procaccia. If you like shapley then you'll love the core. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6):5751-575) 2021.
11

---

[20] Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances Neural Information Processing Systems, 33:
2881-2891, 2020.
[21] Andrew llyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc, and Aleksander Madry. Datamodels: Understanding predictions with data and data with predictions. In Proceedings of the 39th International Conference on Machine Learning, pages 9525-9587. PMLR, 2022.
[22] Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating training data influence by tracing gradient descent. Advances in Neural Information Processing Systems, 33: 19920-19930, 2020.
[23] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference Machine Learning, pages 1885-1894.
PMLR, 2017.
[24] Andrea Schioppa, Polina Zablotskaia, David Vilar, and Artem Sokolow. Scaling up influence functions. Proceedings of the AAAI Conference on Artificial Intelligence, 36(8):8179-8188 2022.
[25] R. Dennis Cook and Sanford Weisberg. Residuals and Influence in Regression. Chapman and Hall, New York, NY, USA, 1982.
[26] Alvin E. Roth. The Shapley Value: Essays in Honor of Lloyd S. Shapley. Cambridge University Press, Cambridge, UK, 1988.
[27] Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the shapley value based on sampling. Comput. Oper. Res., 36(5):1726-1733) 2009.
[28] S. Shaheen Fatima, Michael J. Wooldridge, and Nicholas R. Jennings. A linear approximation method for the shapley value. Artif. Intell., 17((14):673--169) 2008.
[29] Sasan Maleki, Long estimation error of sampling-basee shapley value approximation, 2013.
Greg Hines, Talal Rahwan, and Alex Rogers. Bounding the
[30] Jiayao Zhang, Qiheng Sun, Jinfei Liu, Li Xiong, Jian Pei, and Kui Ren. Efficient sampling approaches to shapley value approximation. Proceedings of the ACM on Management of Data, 1(1):1-24, 2023.
[31] David Liben-Nowell, Alexa Sharp, Tom Wexler, and Kevin M. Woods. Computing shapley value in supermodular coalitional games. In Computing and Combinatories 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20-22, 2012. Proceedings, pages 568-579, Berlin, Heidelberg. 2012. Springer.
[32] Sergiu Hart and Mordecai Kurz. Endogenous formation of coalitions. Econometrica: Journal of the econometric society, pages 1047-1064, 1983.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We believe that the claims made in the abstract and introduction accurately reflect contributions and scope the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
See the discussion in the conclusion (Section 8
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
We have clearly stated every major assumption and provided complete and correct proofs for all the theorems.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have provided sufficient information in the paper and the associated source code to reproduce the main experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We have released the code with usage instructions, and all data used in the experiments are publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
Policyylyyyyyyyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ccpublle pwwppppguuuiieeeeep Sttp:///uuiiees/deeuuuubiiis
(CodeSubiisss wwtauubmmsssoonoi ssiiiissiicccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We have provided all the details necessary to understand the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We have reported standard deviation key metrics the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided sufficient information on the computer resources in Ap-
pendix B
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't I make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:////aaaapp.ccoooo/////aaaaa
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code of Ethics and we believe that the research conducted in the paper conforms to it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: We propose a new methodology for the task of data valuation to facilitate fair and interpretable distribution of the total utility generated by data, which can have a positive socictal impact. We are not aware of any potential negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
16

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do release any models or data that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have properly credited and mentioned the license and terms of use of the data and code used the paper.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We have provided sufficient documentation for the released code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
We do involve research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
18

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: We do not use LLMs as an important, original, or non-standard component of the core methods in this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy hbtpps///porrisccc////oorrrrrree for what should or should not be described.
19

---

A Missing proofs
Theorem 3. The group value 6(2 Eres)) defined in Eq. (11 satisfies the following axioms:
1. Efficiency: EEED 6(2 Zseu) utif"( D') uti util(D) -nti((), that is, the sum of all group values equals the total utility.
2. Symmetry: If 21 and 22 are such that (S {=13) uS U (2/3) for all S' C D') {01, 212) where z and 2/2 are copies of and z2 respectively, then 6(21 Fresa)/ ww( Zrent) = 6(22 //ss)/(())
Zress)
3. Dummy Player: If z is such that ut U (2(3) (S) for all S' DDM where o' is copy of z. then 6(z Zrest) = =0.
4. Additivity: If util', and util, are two utility functions, and Φr and 62 are their corresponding values, then the value & corresponding to utit' + utilz sattisfies 01 + 22-
Proof of Theorem 3)
We prove each property separately.
Efficiency: It directly follows from the efficiency of Shapley values game. The equality Dt') = (til( holds because of Proposition
s' Zeea)) in the duplicated
Σ ZED
6(= Zress) = Σ Σ
8'(2') Ziest) = Σ
8((=') (rees) util((D') util(
2ED ='D':''=
Z'ED"
Symmetry: two points 2 and 22 make identical marginal contributions through their copies, then by the symmetry of Shapley values, each copy receives the same value, i.e., s² Ziess) = s (2/2 Z Thus,
(21 2
Ziea)
w(21 Erest) (s'
Zresa)
((22 2
s'(=) Ziea) = s 5(/2 iress)
20 (021
Zuea)
w(21 Zies
w(22 Aress)
Dummy Player: If point a contributes nothing through any of its copies, then by the dummy player property of Shapley values, s'(=') Aisa) = for all copies z' z. Therefore,
ø(2 Ztest) w(2 (x Rws) w(2 zus)) =
Additivity: Let util' and util? be two utility functions with corresponding values oi and Φ2. Let s and 8/2 be the Shapley values in the duplicated games for util', and utilz. By the additivity of Shapley values, s' s'(z') = (2') + x²2))) for the combined utility util' util', + utily. Therefore:
Φ(= Zwe)) w(2 Zress) (2 2rest)
w(2 Zrest (s' (z (rea)) 5/(2 2rest))
w(2 Atest) Rsest) (z 2rest) + w(2 Zress Zress) 5/((2 Zrest)
di (z Zrost) + Ø2(2 Erest).
Proposition 4. In the genral case, the group Shapley values in Eg. Shapley values of weighted kNN-SV Eq.
11 may be different from the
Proof of PPropoitiinn 4 Consider a dataset D = ( _n where all points share Zies 's label. Note that since all points have the correct label, the marginal contribution of adding any point to a subset S is non-zero only when S is empty, regardless of the value of k. Let w(21) = 2 and w(2.) 1 for 1.
We first discuss the weighted kNN-SV on D. is easy to see that
1
)
81 n
Next, we consider the unweighted KNN-SV on D'. By symmetry, we have S' = =3/2, 8o
( = 2/ 8/4 n +
2
(1 1
(1-7)
Equality ((21) holds only when 1. For it holds
2 >
n+I
20

---

Table Al: Statistics of the datasets used in the experiments.
Dataset
d
|
phoneme
5404
5
2
wind
6574
14
2
cpu
8192
21
2
2dplanes
10000
10
2
apsfail
10000
170
2
click
10000
11
2
creditcard
10000
23
2
fraud
10000
30
2
pol
10000
48
2
vehicle
10000
100
2
poker
1000000
10
10
Lemma 5. Fix a test point Zust- Let point in Then, every copy z of z has the same Shapley value (2' Rest) that of z. This continues to hold when the values are obtained by applying the recursive formuul Theorem] 7 with an arbitrary order among z and its copies.
The first statement is direct consequence of the symmetry property of the Shapley values. The second statement follows by observing that any two copies of z share the same label, which turns the second term in Eq. 7 into zero. Thus, their values do not depend on the order of z and its copies.
Proof Lemma 5
Theorem 6. Algorithm computes dlplicatioon-asser weighted KNN-SV in O + nlog n) time.
Following Lemma 5 we take an order where each point is behind all its copies. Then we apply the recursive formula in Theorem to compute the Shapley values. After processing each point E D, we can skip its copies by multiplying s( Frest) by the number of its copies, as instructed by Lemma Thus, no copies need to be materialized, and the time complexity dominated by the sorting step, which is O(dn + n logn).
Proof of Theorem 6
B Additional experimental details
Experimental Environment. All algorithms were implemented in Python 3.11. All experiments were carried out on a Linux server equipped with 64 CPUs of Intel(R) Xeon(R) Platinum 8358P CPU @ 2.60 GHz and 1511 GB RAM.
See Table Al for the statistics of the datasets used in the experiments.
B.1
Comparison with hard-label weighted ANN-SV
Instead of resorting the approximate version, we choose compare with the exact version of this baseline [00] over small datasets. The hard-label weighted &NN-SV is denoted as dp below. We set the data size to 300 by randomly sampling from the original datasets. tune the parameter of kernel width in the same fashion in the main experiments. Very surprisingly,
reported in Table A2 the dp is only slightly better than random guessing for the task of noisy label detection, and is far behind the performance of the unweighted &NN-Shapley and our method. To make sure this is not caused by bugs in the code, we further verify that its values are indeed consistent with those by Monte-Cart sampling with hard-label utility function.
After careful inspection, we identify the key reason: a hard-label utility function may be less suitable for the task of noisy label detection, or require stronger signal from distance- based weights. Unlike soft-label utility,
unable to capture the fine- tineggrinned contribution of a data point. It requires the noisy point to be game changer for the prediction of its neighbors in order to be considered harmful, which not the case for most mislabeled points. A mislabeled point is often surrounded by well-labeled points, and its ability to change the prediction of its neighbors is often negligible. Note
21

---

Table A2: Fl scores of different methods on the noisy label detection task. The best one is highlighted in bold, and the second best is underlined.
dup
unweighted
random
dp
2dplanes
0.232 + 0.090
0.250 + 0.092
0.036
0.071 + 0.058
apsfail
0.786 0.143
0.696 = 0.090
0.036
0.071 0.058
click
0.036 + 0.041
0.036 = 0.041
0.036
0.036
opu
0.607 0.071
0.536 + 0.149
0.036
0.071 0.100
creditcard
0.107 + 0.124
0.125 + 0.036
0.036
0.054 + 0.068
fraud
0.821 0.137
0.893 + 0.071
0.036
0.036 + 0.041
phoneme
0.321 + 0.092
0.321 + 0.041
0.000
0.018 0.036
pol
0.339 0.236
0.339 + 0.147
0.036
0.071 = 0.058
vehicle
0.143 + 0.154
0.179 + 0.189
0.036
0.107 + 0.092
wind
0.250 0.092
0.214 + 0.154
0.089
0.036 + 0.041
poker
0.071 + 0.000
0.071 = 0.000
0.054
0.000 = 0.000
that resorting to a hard-label utility function is the key modification that enables the DP algorithm in Wang et al. [10] to work.
B.2
Visualization of the Shapley values
See Fig. for more visualization of the Shapley values.
B.3 Scalability
We compare the running time of unweighted and dup with different dataset sizes. We vary the size of random I-dimensional dataset from 100 to 10 The results are shown Fig. Tb As we can see, the running time of dup follows that of the unweighted &NN-SV closely, confirming its near-linear time complexity.
B.4 Effect of the parameter k
We examine the effect of the parameter ic on the performance of representative methods. See Fig. A2 for more results on the effect of the parameter Overall, the performance of all methods robust to the choice of k.
22

---

x10
phoneme
x10
wind
0.5
X10-2
qpu
Positive/ NNegative values
5.0
unweighted
Positvve /Nogative values
Posilive//Neee /Negatiieeeeeeeeeeeeeee values
dup
0.0
0.0
2.5
mc-1000
-2.5
-0.5
0.0
unweighted
-1.0
dup
dup
unweighted
-7.5
-5.0
mc-1000
mc-1000
100
100
100
Data sorted by distance
Data sorted by distance
Data sorted by distance
x10
2dplanes
x10
apsfail
x10
creditcard
Fositive/Ness /Nogative values
Positive/Neeg /'eggatveeeeeeeeeee values
unweighted
Positive/Nee /Nggalive values
unweighted
0
dup
dup
me-1000
1.0
mc 1000
0.5
unweighted
dup
-1
mc-1000
-2
50
100
100
50
Data sorted by distance
Data sorted by distance
Data sorted by distance vehicle
0.5
-
fraud
x10
pol
x10
Positive/ Saaivve/Ngativee values
Positive Negatiie values
unweighted
Posilive /Negalivee values
dup
0.0
mc-1000
2
-0.5
unweighted
-2
unweighted
dup
dup
-1.0
mc-1000
-2-
mc-1000
0
50
100
0
50
100
50
100
Data sorted by distance
Data sorted by distance
Data sorted by distance
Figure AI: Visualization of the Shapley values of different methods concerning random test point.
23

---

phoneme
wind
cpu
0.40
0.30
0.35
0.58
Fl score
Fl
0.56
dup
dup
dup
me-100
0.20
me-
0.54
me-100
0.25
unweighted
unweighted
unweighted
0.52
10
20
30
40
0
10
20
30
40
10
20
30
40
K
K
K
apsfail
click
crediteard
0.80
0.085
dup
0.12
mn--100
0.080
ubweiighted
score
FI score
0.11
0.075
0.74
dup
F1
0.10
dup me-100 unweighted
mc-100 unveighted
0.070
0.72
0.065
0.09
10
20
30
40
30
40
K
fraud
pol
vehicle
0.46
0.17
dup mc-100 unweighted
0.44
Fiscore
0.87
Fl
0.16
0.86
Fl
0.15
dup unweighted
dup
0.85
0.38
unweighted
10
20
30
10
20
30
40
30
K
Figure A2: Effect of the parameter on the performance of different methods.
24


Reviews:
[{"review_id": "salTVctRwI", "reviewer": "Reviewer_KFsJ", "summary": "This paper is building on previous work leveraging $k$-NN classifiers in order to reduce the computational burden of the Shapley value, in order to perform data valuation. Current $k$-NN based approaches consider either (1) un-weighted $k$-NN models (where neighbors are not penalised with respect to their distance to the target data sample); (2) or weighted $k$-NN models but with prohibitive quadratic computational cost.\n\nThis paper is an attempt to fill this gap by proposing a novel approach leveraging weighted $k$-NN models with almost linear (w.r.t. the full coalition size $n$) computational cost, i.e. of the order of $O(nlog(n))$. To that purpose, the authors are proposing the following contributions:\n- a novel variant of weighted $k$-NN Shapley value by duplicating the training dataset, which is shown to meet the unweighted variant (Proposition 2);\n- a thorough discussion of the aforementioned proposed framework compared to related techniques (e.g. Owen values and other $k$-NN Shapley-based data valuation techniques (Sections 4.1 & 4.2);\n-  a scalable data valuation algorithm avoiding the naive additional computational burden related to data duplication;\n- experiments showing the benefits of the proposed approach.", "questions": "See my concerns in the above section.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The paper is very well written, clear and contributions well identified compared to past work.\n- The discussion and comparison with related approaches (notably Owen and $k$-NN based) are thorough and insightful.\n- The contribution is timely and of interest for the machine learning community.\n- Support from both theoretical insights and experimental ones is adequate.\n- The proposed approach is simple (I consider this as a strength) but its benefits are clear.\n\nOverall, the paper looks solide and mature.\n\n**Weaknesses**\n\n- [Major] Could you discuss in further details the impact of the dimensionality $d$ compared to unweighted variants, on the scalability of the proposed approach?\n- [Minor] $K$ is not defined in (3), I believe it is $k$?", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for reviewing our paper and recognizing our contributions.\nWe answer your questions below.\n\n**Q1**: [Major] \nCould you discuss in further detail the impact of the dimensionality $d$ compared to unweighted variants, on the scalability of the proposed approach?\n\n**A1**: \nAs far as we know, the dimensionality $d$ plays no special role in the comparison between the weighted and unweighted kNN-Shapley.\nIt only affects the sorting stage, which is *required* for both the weighted and unweighted kNN-Shapley.\nWhen given a test point $z_{test}$, we need to compute the distance between $z_{test}$ and all the training points in $D$ before we can sort $D$ by non-decreasing distance to $z_{test}$.\nThus, the time complexity of distance computation (e.g., Euclidean distance) is $O(d)$ for each pair of points, which leads to $O(dn)$ in total.\n\n\n**Q2**: [Minor] \n$K$ is not defined in (3), I believe it is $k$?\n\n**A2**: Yes, you are correct. We will fix the typo. Thanks."}, {"review_id": "aFIVB0Ygj1", "reviewer": "Reviewer_B26m", "summary": "This paper introduces a novel approach to computing Shapley values for weighted k-nearest neighbor (kNN) classifiers through a data duplication technique. While existing methods for computing exact Shapley values in kNN models are limited to unweighted cases or require computationally expensive approximations for weighted variants, the authors propose creating multiple copies of each data point proportional to its weight, effectively reducing the weighted kNN problem to an unweighted one.", "questions": "N/A", "limitations": "I decided to set my score as 3 given (1) the limited theoretical contribution, (2) insufficient discussion on algorithm details, and (3) missing important baselines from the experiments. Happy to raise the score if all the concerns are addressed during the rebuttal.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n- Data valuation is an important problem for ML community and KNN-Shapley is a very popular approach. \n- The paper is well-written and accessible, with comprehensive background material that facilitates understanding.\n\n## Weaknesses\n- Section 3 is still the preliminaries from prior works and should be merged into Section 2. Additionally, Theorem 1 should cite Wang and Jia's technical note in its title. \n- Line 140 should use \"integer\" instead of \"integral\". \n- I feel the theoretical contribution falls on the low end. For example, Proposition 2 appears to be a straightforward observation. Theorem 3 merely restates standard Shapley axioms with minor adaptation. \n- Theorem 6's runtime analysis omits the dependency on K', with only a brief mention that \"partial sum of the harmonic series can be accurately approximated by the Euler-Maclaurin formula [2], or retrieved from a pre-computed table.\" This is problematic because:\n  - If approximation is used, it introduces an additional layer of error that should be characterized\n  - If pre-computed tables are used, this significantly increases memory requirements\n  - Algorithm 1 should explicitly include these details in the pseudocode and acknowledge any limitations. \n- For experiments, the most relevant baseline—hard-label weighted kNN-Shapley by Wang et al. [1]—is omitted with insufficient justification. The authors claim it \"fails to finish within 5 hours on small datasets,\" but after reviewing [1] I do not think this explanation is sufficient: \n  - Runtime of hard-label WKNN-Shapley can be controlled by adjusting discretization bits for weights\n  - [1] also offers a deterministic approximation algorithm with sub-quadratic complexity (Section 4.2 of [1])\n\n[1] Wang, Jiachen T., Prateek Mittal, and Ruoxi Jia. \"Efficient data shapley for weighted nearest neighbor algorithms.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024. https://arxiv.org/pdf/2401.11103", "was_revised": true, "final_justification": "The technical contribution lies on the low end, but this won't be a reason to reject the paper. I appreciate the additional algorithm details and experiments. Overall, I think it's a nice paper on KNN-Shapley that is worth sharing with the NeurIPS community. Therefore, I recommend accept.", "rebuttal": "We thank the reviewer for the thorough review, and the constructive suggestions on improving the presentation of the paper.\nWe answer your questions below.\n\n\n**Q1**:\nI feel the theoretical contribution falls on the low end. For example, Proposition 2 appears to be a\nstraightforward observation. Theorem 3 merely restates standard Shapley axioms with minor adaptation.\n\n**A1**: Our main idea about data duplication is indeed a simple one, but it is effective and has been overlooked by prior work.\nOther reviewers consider the simplicity of our approach as a strength with clear benefits (e.g., see Reviewer KFsJ).\nBesides, we propose techniques to avoid the computational burden caused by data duplication, and provide theoretical analysis of the difference from other approaches.\nWe believe these contributions together establish a complete theoretical and practical foundation for our proposed approach.\n\n\n\n**Q2**:\nTheorem 6's runtime analysis omits the dependency on $K'$, with only a brief mention that \"partial sum of the\nharmonic series can be accurately approximated by the Euler-Maclaurin formula [2], or retrieved from a precomputed table.\" This is problematic because:\nIf approximation is used, it introduces an additional layer of error that should be characterized\nIf pre-computed tables are used, this significantly increases memory requirements\nAlgorithm 1 should explicitly include these details in the pseudocode and acknowledge any limitations.\n\n**A2**: We thank the reviewer for pointing out the missing details. \nAsymptotically, the Euler-Maclaurin formula $F(j)$ below converges to the harmonic series $H_j = \\sum_{i=1}^{j} \\frac{1}{i}$ as $j \\to \\infty$.\n$$\nF(j) = \\ln(j) + \\gamma + \\frac{1}{2j} - \\frac{1}{12j^2},\n$$\nwhere $\\gamma \\approx 0.5772156649$ is the Euler-Mascheroni constant.\nIn practice, we adopt the following more accurate approximation scheme.\nWhen $j$ is a small constant (e.g., $j \\le 1000$), we can afford to compute $H_j$ exactly.\nOtherwise, we use $F(j) - F(1000) + H_{1000}$ as an approximation (in $O(1)$ time where $H_{1000}$ is pre-computed) to eliminate the noticeable error when $j$ is relatively small.\nWe verify the absolute error is at most $4.167 \\times 10^{-8}$ for $j$ up to 1 million and continues to decrease as $j$ increases.\nWe believe this approximation is sufficient for our purpose.\n\n\n\n\n**Q3**:\nFor experiments, the most relevant baseline—hard-label weighted kNN-Shapley by Wang et al. [1]—is omitted\nwith insufficient justification. The authors claim it \"fails to finish within 5 hours on small datasets,\" but after\nreviewing [1] I do not think this explanation is sufficient:\nRuntime of hard-label WKNN-Shapley can be controlled by adjusting discretization bits for weights.\n[1] also offers a deterministic approximation algorithm with sub-quadratic complexity (Section 4.2 of [1]).\n\n**A3**: In our experiments, we use the default discretization bits ($n_{bits}=3$) for this baseline, which only enables at most 8 different weight values.\nWe believe no significant saving in time can be expected when using fewer bits.\n\nInstead of resorting to the approximate version, we choose to compare with the exact version over small datasets.\nWe set the data size to be 300 by randomly sampling from the original datasets.\nVery surprisingly, the hard-label WKNN-Shapley is only slightly better than random guessing, and is far behind the performance of the unweighted kNN-Shapley and our method.\nTo make sure this is not caused by bugs in the code, we further verify that its values are indeed consistent with those by Monte-Carlo sampling with a hard-label utility function.\n\nAfter careful inspection, we identify the key reason: a hard-label utility function is not suitable for the task of noisy label detection.\nUnlike the soft-label utility, it is unable to capture the fine-grained contribution of a data point.\nIt requires the noisy point to be a game changer for the prediction of its neighbors in order to be considered harmful, which is not the case for most mislabeled points.\nA mislabeled point is often surrounded by well-labeled points, and its ability to change the prediction of its neighbors is often negligible.\nNote that resorting to a hard-label utility function is the key modification that enables the DP algorithm in [1] to work.\n\nWe thank the reviewer for suggesting further comparison with this baseline, which leads to insightful observations. \nWe will add this comparison in the revised version of the paper.\nWe hope the reviewer will consider raising the score."}, {"review_id": "Zq9yG9P99V", "reviewer": "Reviewer_WDF7", "summary": "To address the issue of lacking fast Shapley values calculation methods in weighted kNN algorithms, this paper proposes duplication-based kNN-SV (dup). The algorithm applies data duplication to convert weighted kNN into unweighted kNN, and exploits efficient algorithms to compute Shapley values. At the same time, it reduces the complexity to near-linear time in the original data size. Experimental results on 11 datasets validate the effectiveness of dup.", "questions": "Please refer to the weaknesses above.", "limitations": "YES", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength：\n\n1.This paper proposes a new algorithm duplication-based kNN-SV (dup) that employs a duplication-based technique to efficiently reduce the weighted case to the unweighted setting.\n\n2.The proposed algorithm not only preserves the weighted characteristics of kNN but also retains the desirable axiomatic properties of Shapley values while enabling computationally efficient estimation.\n\n3.The experimental evaluation more or less demonstrated the effectiveness of the computationally efficient algorithm dup in noisy label detection. \n\nWeakness：\n\n1. In section 4, the authors assume weights are integral. This is a severe restriction, as weights are typically numerical. The authors mention that assumptions could be removed through weight scaling, but do not provide the specific operation.\n\n2.In section 7, the comparison of the algorithms is insufficient. To further verify the effectiveness of the proposed algorithm, the authors should incorporate additional comparison algorithms about noisy label detection.\n\n3. In section 7, the experimemtal results present standard deviation values but lack the significance test. This leads to the inability to confirm whether the performance differences between algorithms are statistically significant.\n\n4.  In section 7, the datasets used in the experiments are not sourced. This makes me confused about the reason why the authors chose these datasets.", "was_revised": true, "final_justification": "After reading the authors' rebuttal. I have decided to maintain my current score.", "rebuttal": "We thank the reviewer for reviewing our paper.\nWe answer your questions below.\n\n\n**Q1**: In section 4, the authors assume weights are integral. This is a severe restriction, as weights are typically numerical. The authors mention that assumptions could be removed through weight scaling, but do not provide the specific operation.\n\n**A1**: We want to emphasize that the assumption of integral weights is made without loss of generality.\nWe now explain how to do weight scaling in detail.\nSuppose the weights are real numbers $w_1, \\ldots, w_n$.\nWe can scale the weights to integers by multiplying a constant factor $c$ such that $c w_i$ is an integer for all $i$.\nNote that since real-valued weights are stored in the computer with finite precision, such an integer $c$ always exists, and the scaling does not change the prediction or the utility function of the $k$-NN classifier.\nIn practice, we set $c$ to a sufficiently large numeric integer and perform rounding afterwards.\n\n\n**Q2**: In section 7, the comparison of the algorithms is insufficient. To further verify the effectiveness of the proposed algorithm, the authors should incorporate additional comparison algorithms about noisy label detection.\n\n**A2**: We understand the reviewer's concern.\nHowever, the main goal of this paper is not to claim that kNN-Shapley is the best approach for noisy label detection.\nInstead, we aim to show that the proposed weighted kNN-Shapley method is effective in comparison to the unweighted counterpart and other kNN-based approaches.\nWe hope the reviewer will agree that we have made sufficient comparisons for this purpose.\n\n\n**Q3**: In section 7, the experimental results present standard deviation values but lack the significance test. This leads to the inability to confirm whether the performance differences between algorithms are statistically significant.\n\n**A3**: Following the advice of the reviewer, we added a significance test to the experimental results.\nWe choose the Wilcoxon signed-rank test, which is a non-parametric test that does not assume a normal distribution of the F1 scores.\nTaking the F1 scores of each method over 11 datasets as input and using a significance level of 0.05, the performance of our weighted kNN-Shapley method is statistically significantly better than all baselines except for the unweighted kNN-Shapley method and the Monte Carlo sampling method with 1000 samples.\nHowever, if we slightly raise the significance level to 0.06, our method outperforms the unweighted kNN-Shapley method in the test.\nNote that it is not expected that our method can defeat the Monte Carlo sampling method with a large number of samples, because the latter is also based on weighted kNN-Shapley, but is much slower.\nWe hope that this test helps to justify the effectiveness of our method.\n\n\n\n**Q4**: In section 7, the datasets used in the experiments are not sourced. This makes me confused about the reason why the authors chose these datasets.\n\n**A4**: \nWe adopt most datasets that are used in the previous work [29,30] on kNN-Shapley.\nWe added a few new datasets with a larger size (e.g., poker), which is a popular dataset available in UCI Machine Learning Repository."}, {"review_id": "4v0lgmuW6M", "reviewer": "Reviewer_GPEG", "summary": "The paper proposed an efficient algorithm to tackle computing data Shapley for weighted KNN models, extending previously established work on unweighted KNN-Shapley by Jia et al. The authors related the solution concept to Owen values and demonstrate although their algorithm might result in solution concept that are not exactly Shapley, it still satisfies some other rationality constraints.", "questions": "How would your work extend to regression settings? I suppose you might have to bin the differences between y_obs and y_tests in order to still use the counting trick? Do you have any other smarter ideas on this?", "limitations": "It's only works for classification problems but this is a very minor problem given the significant improvement in computational speed.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strength: Many. The paper is beautifully written, the ideas are clear, contributions are clear, comparison to existing works are clear. \n\nWeakness:\n- Not a serious one but should you still call your method data Shapley in this case? Just like how Jia's other work on Data Banzhaf, isn't your work some kind of Data Owen that's trying to approximate Data Shapley for weighted KNN?\n\nVery minor: in lline 140 I suppose you wanted to say you treat the weights as \"integers\" rather than \"integrals\"?", "was_revised": true, "final_justification": "I don’t have further concerns. The rebuttal addressed most of my concerns. I remain very positive about this submission.", "rebuttal": "We thank the reviewer for reviewing our paper, and recognizing our contributions.\nWe also thank the reviewer for pointing out the typo in line 140.\nWe answer your questions below.\n\n\n**Q1**: \nNot a serious one but should you still call your method data Shapley in this case? Just like how Jia's other work on Data Banzhaf, isn't your work some kind of Data Owen that's trying to approximate Data Shapley for weighted KNN?\n\n**A1**: While it is popular to create new names for proposed methods for easy recognition, we didn't make an effort to do so.\nThank you for suggesting a candidate, and we are thinking of using \"kNN-GroupShapley\" if a name is needed.\n\n\n**Q2**:\nHow would your work extend to regression settings? I suppose you might have to bin the differences between y_obs and y_tests in order to still use the counting trick? Do you have any other smarter ideas on this?\n\n**A2**: Extending to regression is exactly one of the possible future works we mentioned in the conclusion.\nIf the reviewer is interested in this, we recommend taking a look at Section E.1 of [13], where they define a utility function for regression with unweighted kNN as the negative mean squared error, and develop a similar recurrence relation for the Shapley values."}]

Author rebuttal:

Meta-review: This work proposed a new variant of the Shapley value for k-nearest-neighbor classifiers that can be efficiently computed, improving the previous quadratic complexity to (near) linear complexity. The reviewers praised the presentation of the paper and the simplicity (and effectiveness) of the idea. The authors' response addressed most of the reviewers' questions and resulted in a uniformly positive recommendation, which I concur. 

Some extra comments for the authors to consider incorporating: 

- The abstract, unlike the introduction, did not make clear the proposed method is a variant of knn-Shapley. Thus, technically speaking, this work did not bridge the gap of the quadratic complexity of knn-Shapley. 

- The paper should make clear that only **rational** weights are dealt with. The authors in the rebuttal mentioned that 
  > Suppose the weights $w_i$ are real numbers. We can scale the weights to integers by multiplying a constant factor $c$ such that $c w_i$ is an integer for all i. 

  This is incorrect: let $a\ne 0$ be rational and $b$ be irrational. We can easily prove that there does not exist $c\ne 0$ such that $ac$ and $bc$ are both rational. 

  Of course, in practice numbers are represented in finite-precision, making them effectively rational. However, it is best to be clear about what is being dealt with in theory and then comment on the practical effectiveness.
Decision: Accept (poster)