Localized Data Shapley: Accelerating Valuation for Nearest Neighbor Algorithms
Authors: Guangyi Zhang
Yanhao Wang
Chengliang Chai
Qiyu Liu
Wei Wang
Venue: NeurIPS 2025 poster ()
Keywords: Data valuation
Shapley values
k-Nearest Neighbors
Clustering
Primary area: general_machine_learning
TL;DR: We introduce a localized data Shapley framework for KNN models that significantly accelerates data valuation over a test dataset with provable speedups.

Abstract: Data Shapley values provide a principled approach for quantifying the contribution of individual training examples to machine learning models. However, computing these values often requires computational complexity that is exponential in the data size, and this has led researchers to pursue efficient algorithms tailored to specific machine learning models. Building on the prior success of the Shapley valuation for $K$-nearest neighbor (KNN) models, in this paper, we introduce a localized data Shapley framework that significantly accelerates the valuation of data points. Our approach leverages the distance-based local structure in the data space to decompose the global valuation problem into smaller, localized computations. Our primary contribution is an efficient valuation algorithm for a threshold-based KNN variant and shows that it provides provable speedups over the baseline under mild assumptions. Extensive experiments on real-life datasets demonstrate that our methods achieve a substantial speedup compared to previous approaches.

Localized Data Shapley: Accelerating Valuation for Nearest Neighbor Algorithms
Guangyi Zhang Shenzhen Technology University zhangguangyi wistgggyyssstut edu. en
Yanhao Wang" East China Normal University yhwangodase ecnu. edu. en
Chengliang Chai
Qiyu Liu
Wei Wang" HKUST(GZZ) and HKUST weiwcsEust.htt
Beijing Institute of Technology ccl@bit.. edu. cn
Southwest University qyliu. cs@gmail. com
Abstract
Data Shapley values provide a principled approach for quantifying the contribution of individual training examples to machine learning models. However, computing these values often requires computational complexity that is exponential in the data size, and this has led researchers pursue efficient algorithms tailored specific machine learning models. Building on the prior success of the Shapley valuation for -nneaeest neighbor (KNN) models, in this paper, we introduce a localized data Shapley framework that significantly accelerates the valuation of data points. Our approach leverages the distance-bais based local structure in the data space to decompose the global valuation problem into smaller, localized computations. Our primary contribution an efficient valuation algorithm for a threshold breshold-based KNN variant and shows that it provides provable speedups over the baseline under mild assumptions. Extensive experiments on real-life datasets demonstrate that our methods achieve a substantial speedup compared to previous approaches.
1 Introduction
Data has emerged the new oil of the digital economy, driving advances across various fields such as artificial intelligence, healthcare, finance, and beyond. The rapid growth data collection has created unprecedented opportunities for building powerful machine learning models that solve complex problems. As organizations increasingly rely on data-driven decision making, the quality and relevance of training data have become critical factor that determines the success of machine learning applications and consequently impacts different aspects of our daily lives D. This paradigm shift has highlighted the fundamental importance of data a valuable resource that requires careful management, curation, and valuation
Despite the widespread recognition of the importance of data, significant challenge remains: how to systematically, fairly, and efficiently value individual data points within large datasets. This question is increasingly relevant due to the emergence of data marketplaces, the evolution of privacy regulations, and the development data-centric AL. Data valuation serves multiple purposes, including compensating data contributors equitably, identifying high-value data for acquisition, and removing harmful or misleading examples (35)
The Shapley value (SV), originating from cooperative game theory, is principled and theoretically grounded approach to addressing the challenge of data valuation [ Shapley values provide
"Corresponding authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1200
test ratio=0.001
ratio-0.010
1000
800
Frequency
400
200
0.000
0.001
0.002
Shapley values
Figure 1: Illustration of the distribution of Shapley values computed for different test data ratios.
mechanism for fairly distributing the collective value of a coalition among its members. When applied to machine learning, data Shapley values 7 g measure the contribution of each training example to model performance by considering its marginal value across all possible subsets of the dataset. This approach satisfies important properties such as fairness, additivity, and symmetry, making it a reliable measure for data valuation tasks. Note that it differs from the attribution methods such SHAP [9]. where Shapley values are computed for each feature of given data point.
However, the computation of data Shapley value is expensive, as requires enumerating all possible subsets of data points. In fact, it has been shown to be #a- in certain games [10] A recent breakthrough by Jia et al. [I]] exploits the structure unweighted K-nearest neighbor models (also known KNN models) efficiently compute the exact data Shapley values. KNN models are family of classic machine learning models that predict the label data point based on the labels of its K nearest neighbors. KNN models can be adapted to modern neural networks by using their learned embeddings as the feature space. The KNN-based Shapley value (KNN-SV) has quickly become of the leading data valuation techniques 15)
Although KNN-SV offers significant speed improvements over the naive approach, still struggles with large datasets due to its linear dependence on the test data size. In KNN-SV, value attributed to each test data point is distributed among all training examples based on their contribution to the prediction. Owing to the local nature of KNN models, average contribution over sufficient number of test points is required for an accurate valuation. See Fig. [ for an illustration of the data values computed for different numbers of test points real dataset. When the number of test points is small, the Shapley values have a more dispersed distribution, indicating that the values are less stable and more extreme. Hence, it is desirable of magnitude as the training set size, but this will result in quadratic overall time complexity.
number of test points that is of the same order
In this paper, we address this key limitation of prior KNN-SV approaches and propose more efficient algorithm. Our algorithm leverages the distance-based local structure in the data space to decompose the global valuation problem into smaller, localized computations. For threshold-basee KNN variant, our algorithm provides provable speedups over the baseline under mild assumptions. We validate the proposed algorithm through experiments on real-world datasets, demonstrating practical improvements over existing methods.
The remainder of the paper is organized as follows. We first review the preliminaries in Section 2 and present baseline method that computes KNN-SV by recursion in Section 3 We then present our proposed methods by starting with landmark-basee near neighbor search in Section a building block and introducing a fast method for threshold-based KNN Section The experimental setup and results are outlined in Section We conclude the whole paper in Section

---

2
Preliminaries
In this section, we introduce the framework for data valuation based on the Shapley value (SV) and establish our notation for applying this concept to K-nearest neighbor (KNN) models.
2.1 Cooperative Game Theory and Shapley Value
The concept of data valuation can be elegantly formalized through the lens of cooperative game theory. In this framework, we consider a collection of players who can form coalitions to generate collective utility. Formally, cooperative game consists of pair v), where T {1, (1..... n) represents the set of players and v - is a utility function that assigns a real value to each possible coalition.
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 time-tested solution to this problem. For each player i, the Shapley value si) represents the average marginal contribution across all possible coalition formations, i.e.,
1 Σ SCAVO)
1n=1)
n [S]
s(i)
v(S)).
(1)
The Shapley value uniquely satisfies the following four desirable properties, which makes it par- ticularly suitable for data valuation. That is, there does not exist any other value function that can simultaneously satisfy all of them. (1) Efficiency: The total utility is completely distributed among
all players, i.e., v(T) = Eier s(i). (2) Symmetry: Players with identical marginal contributions receive equal value, i.e., if eS U {+)) = v(S U (j)) for all S S / \ (i,j), then s(i) = s()). (3) Null Player: Players who contribute nothing to any coalition receive zero value, i.c., si) =
vS)) for all S C I {i}. (4) Linearity: Values under multiple utility functions sum to the value under the combined utility, i.c., So, (i) + Sog (i) = Se1 +02 (i) for all i E I.
In the context of machine learning, we can reinterpret players as individual data points in the training set and the utility function as a performance measure of models trained on different subsets of the data. This naturally leads to framework for quantifying the contribution of each training data point to the overall model performance.
2.2 KNN-Based Shapley Value (KNN-SV)
In this subsection, we introduce the KNN-based Shapley values with respect to two different utility functions, one for the standard KNN classifier and the other for threshold-based KNN classifier. These utility functions are specifically targeted for a single test data point, and we conclude with a discussion on how to extend them to multiple test points, which are required for an accurate and balanced valuation.
Given a dataset D of size n, where = (z,y) E D with Rd, y V, and y is the label space, we want to compute the Shapley value s(2 Z of z with respect to a test point (Thea; Meea). Let the weight of be w(z ziea) E R4 that indicates the proximity between and Tresa or is simply constant in the case of an unweighted KNN. Following the formulation in [1 let u be the weighted KNN utility function. We have
Min
v(S) = Σ w(Za((S) (ess) ((Nxx = Brest):
where a; (S) is the index of the i-th closest element of to Trest and we call the rank of (S) in S. When w(z Zwa) constant, e.g., w(2 21est) 1/ K, the utility function derived from the standard unweighted KNN classifier. On the other hand, if we write the distance as d(z, || x'||, and let the weight of z be the Gaussian kernel as
w<2 2rea) K(d(2, Rvaa)) = exp(-d(z, Zuea (eeu))/20²))
where measures the width of the Gaussian kernel, the utility function is derived from the weighted KNN classifier instead. Note that one is free to use other metric distances other than the Fuclidean distance.
3

---

We further consider a similar utility function e for variant of the standard KNN classifier, where the utility of a subset takes into account only the nearest K points Ziest that are within ball of radius T centered at Tesst Formally, the utility function is defined as
min([Sr|,KK)
((S)
Σ w(Zo,18,) Eieat) (Voa,(S)) = Vlest) 1=1
(3)
where a;; is the index of the i-th closest element of S to Piests (Zee) = fa E S d(z, Ziea) S T) and we write S, = (Z(e)) for short. This variant is derived from more robust threshold-bisg based KNN classifier (TKNN) [14 I7. where point that too far away from 2estt always has zero influence Frest- It has been shown that this variant possesses additional desirable privacy-friendly properties [1].
With the utility functions defined above, the definition of the Shapley value of a data point = E D is straightforward. following Eq. (I]. Formally, the Shapley value of data point e with respect to a given test point zest is defined as
s | Zeest) =
Σ SED-=
n (-1)
|S| 1
[o(S+2)
+ -
(4)
where we write D - D {z} and S + S U {=} for convenience.
In practice, accurately measuring data values requires multiple test points, which typically increases proportionally with the size of the dataset, n. Suppose that there are Neat test points Dust and the data Shapley value of data point can be naturally extended the average over all test points, i.e.
Σ
s(2 Zresa) ) Trest
(5)
3 Baseline: KNN-SV by Recursion
In this section, we introduce the analytical solution to the data Shapley values for KNN models, introduced in [Л]] and extend it to the utility functions in Eqs. (2) and B3. This results in dramatic improvement in time complexity, from O(2") to Onn log n) for single test point, over the naive approach that enumerates all possible subsets S of the dataset D.
We consider fixed test point Sest throughout this section. Given subset S C D, recall that (5( is the index of the i-th closest element of S to zwst When the context is clear, for simplicity, we write (n) as 2, and w (Z) Ews) as wi Similarly, we denote by s; the Shapley value s(2, Z for the data point
We first restate known result about the pairwise difference of the KNN Shapley values in the following lemma.
Lemma (Jia et al.
Fixing test point, for any i,j, we have
uSS + 21) v(S (($++2 +2)
Σ
8:
T1
SCD-a--3
Based on Lemmal we can develop recursive formula for s; in the following theorem.
Theorem 2. Fixing test point, for any i < n, we have
8141 + min(K,)) w:1(y Breat) wi+ (1141 Yrest) and
K 8n w,, 1, (ynn Vrest).
See prool in Appendix A. In summary, in order to compute the Shapley values of all data points in the dataset D, we start with s, for the farthest data point and then iteratively apply the recursive formula in Theorem to compute the values of sn.1...., S1, in decreasing order of their distance to the test point, one data point at time.
It is easy to see that the recursive formula formed by Theorem 2 also works for threshold-based KNN models. The only difference is that the recursion applied to the set of data points that are within the radius J of the test point, instead of the entire dataset D.

---

Time Complexity. We have described a recursive formula for the data Shapley values when there is only a single test point. The calculation requires no more than one sorting of the data points by their distance to the test point, which takes O(dn n log n) time. This is drastic improvement over the naive approach that enumerates all possible subsets of D, whose time complexity is (2")).
However, when considering multiple test points, whose size Rhest is often in proportion to the size of the dataset n, i.e., fltstt (n)), one sorting for each test point amounts to a time complexity of Ol + Tt log n²), which becomes quadratic in the size of the dataset. This is clearly too slow for large-scale applications, especially when Thest large.
Landmark-based Near Neighbor Search
In this section, we introduce core building block for our proposed methods, namely landmark-based near neighbor search, which allows to effectively and efficiently shrink the search space of the near neighbors in data Shapley computation. Unlike other near neighbor search methods, our method exhibits several merits: It is inexpensive in indexing, simple to implement, capable of providing lower bound of the distance to the query point for unvisited points, and, last but not least, amenable to analysis as we will see in the subsequent sections.
The main idea is to pick an arbitrary point 2mark the landmark point, and sort all data points D U Dest by their distances from Smark in ascending order. Denote by T'ark (2) the rank of point in the sorted list and by (z(Zwa) S D the set of points in D whose differences in rank from that of Fres are within i, i.e.,
Bi(Erest) = {z E D [Tmark Tmark (Frss)) S i}.
We call the length of the ball (2eess). We also distinguish the left and right halves of the ball, i.c., B, (Zrex) and B, (2res), where
BR (Ziea) E F'mark (Fnea)) - S l'murk (2) T'arr (Zieat): ))
and
Br (Zrea)= E Fimark Fimar(( (Zrea)
<
Fmurr (2) S T'ank (Zrest) + i].
The motivation of using landmark points that for any test point Ziea, a data point z around zest along the sorted list is likely to be its near neighbor. More importantly, it is possible to derive a lower bound of d(2, Zrea) by only considering the distances the landmark point Zmark. That is, by triangle inequality,
d(z, 2rest) 2 Id(z, Zmark) - d( d(žmark, Prest)
(6)
This is particularly useful. For example, as the ball B, (Zrea) expands, the distance d(z, kmark) is non-increasing, and thus d(z, ztess) is also non-decreasing, which gives us valuable information about d(2, 2ws) for any 2 B, (Erea) even without actually visiting them. The case for B, (Rrea) is similar.
4.1 Optimized Landmark Selection
The tightness of the lower bound of d(2, 2eest) ) in Eq. (6) is highly dependent on the distance d( ². That is, the quality of our bounds can be significantly improved if the test points are close to the chosen landmark point. Therefore, we propose to strategically select multiple landmark points and assign each test point to its nearest landmark point.
More specifically, we propose to select n landmark points D maark S Drest with goal of minimizing the maximum distance of any test point to its nearest landmark point, i.e.,
min Drack Dree
min d(2ucst Zmark).
Pize E Dics Anmt E Drark
The landmark points Dmar defined above align exactly with our intention and naturally create clustering structure through their associated regions of influence, where each region contains points closer to its landmark than to any other landmark. This is also known as the Voroni partition induced by the landmark points. In subsequent sections, we will show that landmark-indun partitions can effectively reveal inherent structures in the data.
5

---

The above optimization problem turns out to be the well-studied metric k-center problem, which is known to be NP -arh Worse still, this problem impossible approximate within a factor of unless P NP 18
Fortunately, there exists a simple greedy algorithm that achieves the best possible approximation ratio 2 in the worst case. This algorithm is called farthest-first traversal (FFT) [9] which as the name suggests, starts from an arbitrary point and iteratively selects the farthest point from the current set of landmark points until n landmark points are selected. In other words, the next chosen landmark point & maximizes the distance against the current set of landmark points, i...
d22, mank)
min d(z, Fmnark). Smart Erork
straightforward implementation of the FFT algorithm takes (fnesnnf d) time, which may be too slow when b is large.
To speed up the FFT algorithm, we first notice that d(z, Dmark) is non-increasing as Dmark grows. Thus, we can reduce a factor of nz in the running time by bookkeeping d(z, D Dmark) for each point and updating it upon the selection of every new landmark point 2mark- That is,
d(z, D D(i mark) min =mark), d(z, D( )a
where D mark the set of landmark points selected before the i-th iteration and ((++1)
D
mark mark
(#mark] J. This avoids scanning the entire set of landmark points when computing dz, D mark) for each point z. Based on this observation, the running time is reduced to O (.
Fast Data Shapley Value Computation for Threshold-based KNN
As discussed previously, given Best test points, the baseline approach in Section 3 computes the data Shapley values for all test points in Odd + nea log n) time. In this section, we propose fast algorithm to compute the data Shapley values for threshold-basee KNN in provably less time.
Our main idea is exploit the truncated structure of the threshold-based KNN classifier. We leverage the landmark-based near neighbor search introduced in Section 4 to shrink the search space of the near neighbors, and it turns out that the size of the search space for any test point can be effectively bounded when the dataset exhibits a stable clustering structure. In the remainder of this section, we first describe the proposed algorithm and then analyze its theoretical properties.
5.1 Algorithm Description
We have introduced the landmark- based near neighbor search in Section and in this section, we show how to utilize it to compute data Shapley values efficiently.
First of all, we need to slightly adjust the FFT algorithm for our purpose. We denote by (Zmark) the cluster of points that are closer to mmar than any other landmark point. The radius of C(Zmark) is the maximum distance from zmark to any point in C(zmak)). ). In addition, we let TDuus be the maximum radius of all clusters induced by the landmark points in D D Note that TD..t is non- noon-nnceeasing as the number of landmark points increases. We make two adjustments to the original FFT algorithm. First, we run FFT over Diest U D instead of Drest Second, we require that Trmas S T. which can be easily achieved by continuing the iterative process of FFT until the condition is met. This also means that it is not required to specify the number of landmark points in advance.
Since the threshold-bard based KNN classifier only considers data points within a distance of 7 from each test point, an intuitive idea is to explore the search space provided by the landmark-based near neighbor search until we can certify that all remaining unvisited points are beyond a distance of from the test point. More specifically, we gradually expand the left half of the ball B, (2ess) centered at each test point Ses until the first point 2 such that
[d Smark) ((2mark: Zrest] >
This immediately implies that the distance d(2. 2, 21est) from any 2 to Ziest outside the left half is least We also apply this process to the right half of the ball. Afterwards, we collect into S all points in
'Recall that an algorithm is called y-approximation if it returns solutions that in the worst case have cost no more than y times than the cost of the optimum solution.

---

Algorithm 1: Fast Data Shapley Value Computation for Threshold- breesh KNN
Input:
Integer K, radius T, datasets D and Diest
Output: Data Shapley values {s(2)) )ED
Select landmark points mark from D U Diest by FFT such that TDma S T;
2
Assign each point in Diett to its nearest point in Dmarki
for Zmark E mark do
4 Sort DU Drest by their distances to mmark in ascending order;
5 Initialize s(2) with a default value of 0 for each : E D;
for Zten -Dest do
7
Let 2mark be the landmark point associated with 2iesti
8
Expand the ball (Zees) until the first point 2 such that ( Zreat - d(2, Zmark) T;
9
Expand the ball B* (Zes) until the first point 2 such that d2z, 4mark) - d( (Zmarki 2test) > T;
10
S + {= E B (Zies) U B B+ (Ates) Zte,) < <>;;
+|s] be the points in S sorted by their distances to Fest in ascending order; Let 21 K [
Zrest) ( (1ais = =
[8]
13
for i = |S| ...... do
6z Pz,-1 + min( K.a) (wi w(+1), where ut w(2 2 (y)
V
s=)) f- s(z) + dz for each E S;
16 s(z) t / for each 2 E D;
17 return JED)
the ball that are within a distance of T from Rrest Finally, we compute the data Shapley values for all the points in S using the recursive formula in Theorem The detailed procedure is described in Algorithm !
To show that Algorithm I can be provably faster than the baseline approach, need to show that for any test point, the total number of points visited in the ball is strictly smaller than n. In the next subsection, show that this is indeed the case under mild conditions.
5.2 Perturbation Resilience
Before we analyze the theoretical guarantee of Algorithm 1 we introduce technical notion of perturbation resilience to help us precisely characterize the structure that exists in a dataset.
Worst-case analysis has been criticized for its over- wer-pessimism and conservatism that fail to capture the real performance of many algorithms in practice. In particular, it ignores the structure that exists in real-world datasets. Therefore, in recent years, there is an active trend of beyond worst-case analysis in the literature to provide more realistic performance guarantees 20) One notable example the notion of perturbation resilience proposed by Bilu and Linial (21, which describes the stability of the clustering structure of a dataset under small perturbations.
We first define the notion of perturbation, which distorts the original distance function d(.,.) -) by factor of most & 2
Definition (Perturbation). Given a clustering instance (D,d), a E-perturbation of is a new distance function d' such that [zz y) d' d'(x, I Ed(z, y) for all x, E D.
Note that the É-perturbation of d may no longer be metric distance. As E increases, larger perturbation is allowed. Then, we say that a clustering instance is perturbation resilient if its optimal clustering remains unchanged up to such small perturbation of d.
Definition (Perturbation Resilience (PR)). clustering instance (D. d) is said to be E-perturbation resilient if the optimal clustering remains unchanged up to E-perturbation of d.
Here, the optimal clustering depends on the specific clustering objective. For example, in the metric k-center clustering, the optimal clustering is the one that minimizes the maximum cluster radius for specific number of clusters k.
7

---

Intuitively, a clustering instance is & p-erturbation resilient if the optimal clustering is stable. Con- versely, if the optimal clustering can easily change under a small perturbation, then it less meaning- ful to study the clustering structure of the dataset in the first place. Note that perturbation resilience does not mean that the clustering will necessarily become easy. In fact, as indicated (22,, no polynomial-time algorithm can solve the metric k-center clustering problem for E-perturbation re- silient instances with any & < 2 unless RP = NP. Although the worst-case approximation ratio of FFT for metric k-center clustering is at least 2, it turns out that it can recover the optimal clusters in a clustering instance it is 2-perturbation resilient.
Theorem 3 (Balcan et al. (22). Let (D,d) d) be a clustering instance. If (D.d) is 2-perturbation resilient, then FFT recovers the optimal clusters of (D, d).
Furthermore, Theorem can be extended to show that any x-approximation solution can optimally recover the clusters under any 7-perturbation of d. Theorem 3 opens up a new avenue for analyzing the performance of our landmark- based near neighbor search, and in turn, of Algorithm
5.3 Theoretical Analysis
In this subsection, show that Algorithm iss provably faster than the baseline approach if the dataset exhibits perturbation resilience. We first point out that our landmark- near neighbor search can be seen soft version of the k-center clustering. Then, we show that perturbation resilience provides sufficient separation between clusters to restrict the computation of the data Shapley values within each cluster, which leads provable speedup.
If we can treat landmark points as the selected centers of the k-center clustering, then they virtually partition the dataset into R2 clusters. Given a landmark point zmark and the sorted list of D U Diest by their distances to 2mark in ascending order, we hope that the points from its cluster C (2marr) are ranked before the points in other clusters.
The next challenge is how to ensure that every point that is within a distance of T from Ziest is in the same cluster as Siest- Note that this is non-trivial because Ses may not be landmark point (i.e., center), and there no guarantee that any two arbitrary points with a distance less than will be in the same cluster, that overlap with each other and two points that lie in the overlapping region. This is crucial for the algorithm to restrict the computation of every test point within the cluster to which it belongs.
matter what size the cluster radius is. For example, consider two clusters
We discover that perturbation resilience provides sufficient separation between clusters to address the above challenges. Formally, we prove the following theorem.
Theorem 4. Let (D U Diest: d) be a clustering instance with nlgsst = On)). If it is 3-perturbation resilient for metric k-center with respect to a cluster number k* and maximum cluster radius T" 2 T, then Algorithm 7 with nt, k-" returns the exact data Shapley values of each point in D in On + n) + Rb + log 8)) time, where is the size of the largest optimal cluster.
See proof in Appendix A When k < n,,, we will show in Appendix A that the same time complexity as Theorem still holds, albeit with a slightly larger 4-perturbation. The above results show that Algorithm provides provable speed-up for wide range of numbers of clusters ri-- For example, let Nust = [n), and we can expect a running time of O 1.5 (d + log n)) with n = /n when the sizes of the clusters are comparable. This improves over the previous O(n + log n)) time.
6 Experiments
In this section, we evaluate the performance of the proposed methods on synthetic and real-world datasets. We aim answer the following two research questions: (1) What are the effects of the parameters and design choices on the performance of the fast algorithm for threshold based KNN (Algorithm [h? (Section(6.1) (2) How much faster do the proposed methods compute the data Shapley values compared to the baseline approach in Section 3 (Section 6.2h Our source code is published for reproducibility? [3]
Datasets. We used both synthetic and well-woldd datasets in the experiments. The former allows us to experiment freely with a wide range of data characteristics. We select a collection of real-world
httpp://github wtw.auuw...oo/uaagg....... Baaiiaaagyyy-Zaaag/taaaa Zwwnnattaannnneeeeee data- shapley
8

---

datasets as listed in Table A1 The dataset size [D] ranges from 10K to M. and we set [ to be 0.2%-1% 1% of DI. Thus, the total size of DI |Deu is up the order of 10
Experimental Environment. All algorithms were implemented in Python 3.11. All experiments carried out Linux server equipped with 64 CPUs of Intel(R) Xeon(R) Platinum 8358P CPU @ 2.60 GHz and 1511 GB RAM.
6.1 Effects of Parameters and Design Choices
In this subsection, we investigate the effects of the parameters and design choices the performance of Algorithm The default values for the parameters are K = 5, n2 = 50, r/d = 0.2, o = 0.1, and FFT for landmark selection. Note that since the data features normalized to be in the range of [0. 1]. the value of 7 measures the maximum proportion features of a data point that can deviate arbitrarily from test point, while the point remains be considered as neighbor in threshold-basee KNN models.
2dplanes
2dplanes
running time (s)
30
running
25
100
10
10a
0.1 0.2
0.5
#landmarks (log)
radius dim
(a) Effect nz
(b) Effect of T/d
Figure 2: Effect of parameters nt. and 7/d on the performance of Algorithm
Effect of the Number of Landmark Points ny. We vary the number of landmark points nz from 1 to 100, and plot the corresponding rumning time the 2dplanes dataset in Fig. [a] As shown, the rumning time of Fig. 2a first decreases and then increases when more landmark points are selected. This is because every test point can be assigned to landmark point that is closer to it, and the total number of data points encountered during the ball expansion for a test point effectively reduced when there
landmark points. However, the running time increases later when this benefit is outweighed by the high overhead of preprocessing the landmark points. Recall that it is necessary to sort all the data points in Dress for each landmark point.
Effect of the Ratio Radius and Dimension d. We vary the value of of from to 0.5, and plot the corresponding rumning time the 2dplanes dataset in Fig. 2b It is expected that the running time increases as the radius 7 grows, because a larger 7 allows more data points to be considered as neighbors of test point. But fortunately, a small is enough in practice due to the localized nature of KNN models.
6.2 Performance Comparison
In this subsection, we compare the performance of the proposed methods with the baseline approach in Section 3 and the state-of-the- threshold- based approach TNN by Wang et al. [14] Note that the baseline approach has sort all the data points in 1) for each test point, regardless of the radius value т. We report the average running time and standard deviation over three runs in Table [ where the fastest running time is highlighted in bold. We also compare their performance for popular downstream task of mislabel detection; see Appendix C.T for more details. The default values for the parameters are K n2 50, and FFT for landmark selection.
Based on the results Table we observe that our proposed methods consistently outperform baseline approach across all datasets. The speedup is substantial, with our fastest method running up to 25x faster than the baseline and faster than TNN. The performance advantage of our methods becomes more pronounced as the dataset size increases.

---

Table 1: Running time (in seconds) comparison of different methods.
Buseline
Algorithm
TNN
Dataset
N/A
7/d 0.05
7/d 0.1
r/d 0.2
r/d
0.05
magic
7.05 +: 6.48
2.68 +: 0.02
0.05
4.70 1.201
1.29
2dplanes
85.83 3.00
8.44 0.15
11.59 0.24
26.75+00..
27.28 25.13
cifar10
148.60 0.61
75.83 0.50
86.57 2.35
144.05 +.67
48.16 44.94
dota2
445.44 4.89
249.36 1.74
267.76 7.24
436.65
142.52
132.03
skin
2035.00 142.90
156.88 1.90
159.37 126.42
243.79
207.22
228.59 2.52
covtype
10324.36
131.70
1918.74
16.94
4135.27 27.07
9107.61
323.44
5009.56 + 10.33
emnist
6090.47 = 19.04
2508.41 = 73.36
3558.89 +:2 130.26
5988.33 384.80
3221.94 7.48
poker
12289.43 + 41.26
488.95 4.73
983.97 0.91
3012.10 46.34
5542.69 + 23.88
Algorithm I excels on lower-dimensional datasets (see controlled experiment in Appendix C.2) such as 2dplanes and poker, where it achieves the fastest runtime when the radius is small. As expected, the performance of Algorithm degrades degrrades as the radius increases. However, the running time never exceeds that of the baseline approach, even when r/d is as large as 0.2. Actually, its worst-case rumning time is about the same as that of the baseline approach, with the negligible overhead of preprocessing a few landmark points. When the dataset shows well-defined clusters, its running time can be provably better. These results confirm that the proposed algorithm significantly accelerates the computation of data Shapley values, while retaining robust worst-case running time that is at least fast as the baseline approach.
7 Conclusion
In this paper, we addressed the challenge of efficiently computing data Shapley values for nearest neighbor algorithms. We leveraged the distance-based local structure in the data space to decom- pose the global valuation problem into smaller, localized computations. For threshold-based KNN classification, we proposed algorithm with provable speedups under mild assumptions compared to existing methods. Our comprehensive empirical evaluation on synthetic and real-world datasets verifies the significant speed-ups ups offered by our proposed methods.
We acknowledge several limitations of our work. The perturbation resilience condition is hard to verify in practice. The landmark-based near neighbor search may suffer from the curse of dimensionality. Potential future research directions include extending our approach to regression tasks, exploring alternative utility functions, and investigating fast algorithms for more general KNN models.
Acknowledgments and Disclosure of Funding
G. Zhang was supported by the Guangdong Provincial College Youth Innovative Talent Project (Grant No. 2025KQNCX075), Natural Science Foundation of Top Talent of SZTU (Grant No. GDRC202520), SZTU University Research Project (No. 2025 106 10110000)). Y. Wang was supported by the National Natural Science Foundation of China (Grant No. 62202169), C. Chai was supported by the NSF of China (62472031), the National Key Research and Development Program of China 2004YYC3308200), Beijing Nova Program, CCF-Baidu Open Fund BCC--aaidu202402. Q. Liu was supported by fundamental research funds for the central universities of Ministry of Education of China SSWU-KR240433 W. Wang was supported by Guangdong Provincial Key Lab of Integrated Communication, Sensing and Computation for Ubiquitous Internet of Things (No.2023B 121 22100 $1.2023A031009334) Guangzhou Municipal Science and Technology Project (No. 2023A0310003,, 2023A03J0013 and 2024A03J0621).
References
[1] Weixin Liang, Girmaw Abebe Tadesse, Daniel Ho, Li Fei-Fei, Matei Zaharia, Ce Zhang, and James Zou. Advances, challenges and opportunities in creating data for trustworthy AI. Nat. Mach. Intell, 4(8):669-677, 2022.
[2] Rachael Hwee Ling Sim, Xinyi Xu, and Bryan Kian Hsiang Low. Data valuation in machine learning: "ingredients", strategics, and open challenges. In Proceedings of the Thirty-First
10

---

International Joint Conference on Artificial Intelligence, IJCA1-22, pages 5607-5614, IJCAI Organization,, 2022.
[3] Zayd Hammoudeh and Daniel Lowd. Training data influence analysis and estimation: survey. Mach. Learn., 1 (13(5):3351-2403 2024.
[4] Kevin Fu Jiang, Weixin Liang, James Y. Zou, and Yongchan Kwon. OpenData Val: unified benchmark for data valuation. Advances in Neural Information Processing Systems, 36:28624- 28647. 2023.
[5] Mark Mazumder, Colby R. Banbury, Xiaozhe Yao, et al. DataPerf: Benchmarks for data-centric Al development. Advances in Neural Information Processing Systems, 36:5320-5347, 2023,
[6] Lloyd S. Shapley. A value for n-person games. In Contributions the Theory of Games, Volume II, pages 307-318. Princeton University Press, Princeton, NJ, USA, 1953.
[7] 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.
[8] 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 Proceedings of the Twenty-Secon Second International Conference on Artificial Intelligence and Statistics, pages 1167-1176. PMLR, 2019.
[9] Scott Lundberg and Su-in Lee. A unified approach to interpreting model predictions. Advances in Neural Information Processing Systems, 30:4765-4443 47744, 2017.
[10] Xiaotie Deng and Christos H. Papadimitriou. On the complexity of cooperative solution concepts. Math. Oper. Res., 19(2):257-266, 1994.
[11] 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(1 1610-163,, 2019.
[12] Konstantin D. Pandl, Fabian Feiland, Scott Thiebes, and Ali Sunyaev. Trustworthy machine learning for health care: scalable data valuation with the Shapley value. In Proceedings of the Conference on Health, Inference, and Learning, pages 47-57, Association for Computing Machinery, 2021.
[13] Jiachen T. Wang and Ruoxi Jia. A note on "efficient task-specific data valuation for nearest neighbor algorithms". arXiv:2204.004 044558.4 2023.
[14] Jiachen T. Wang, Yuqing Zhu, Yu-Xiang Wang, Ruoxi Jia, and Prateek Mittal. A privacy- friendly approach data valuation. Advances Neural Information Processing Systems, 36: 40429-60467, 2023.
[15] Jiachen T. Wang. Prateek Mittal, and Ruoxi Jia. Efficient data Shapley for weighted near- est neighbor algorithms. In Proceedings of The 27th International Conference on Artificial Intelligncce and Statistics, pages 2557-2565. PMLR, 2024.
[16] Jon L. Bentley. A survey of techniques for fixed radius near neighbor searching. Technical Report STAN-CS-75-513, Stanford University, Stanford, CA, USA, 1975.
[17] Yuqing Zhu, Xuandong Zhao, Chuan Guo, and Yu-Xiang Wang. Private prediction strikes back! Private kernelized nearest neighbors with individual Rényi filter. In Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, pages 2586-2596. PMLR, 2023.
[18) Dorit S. Hochbaum. Approximation algorithms for NP-hard problems. SIGACT News, 28(2): 40-52, 1997.
[19] Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theor: Comput. Sci., 38:293-3066 1985.
[20] Tim Roughgarden. Beyond the Worst-Case Analysis of Algorithmss Cambridge University Press, Cambridge, UK, 2021.
[21] Yonatan Bilu and Nathan Linial. Are stable instances easy? Comb. Probab. Comput., 21(5):
643-660, 2012.
[22] Maria-Florina Balean, Nika Haghtalab, and Colin White. k-center clustering under perturbation resilience. ACM Trans. Algorithms, 16(2):22:1-22:3, 2020.

---

[23]
Chandra Chekuri and Shalmoli Gupta. Perturbation resilient clustering for k-center and related problems via LP relaxations. In Approximation, Randomization, and Combinatorial Optimiza- lion. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 Princeton, NJ, USA, pages 9:1-9:16. Schloss Dagstuhl LeibnizzZeentrum für Informatik, 2018.
[24]
Alvin E. Roth. The Shapley Value: Essays in Honor of Lloyd Shapley. Cambridge University Press, Cambridge, UK, 1988.
[25] S. Shaheen Fatima, Michael J. Wooldridge, and Nicholas R. Jennings. A linear approximation method for the Shapley value. Artif. Intell.,
2008.
[26] Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the Shapley value based on sampling. Comput. Oper. Res., 36(5):1726-1730) 2009.
[27] Sasan Maleki, Long Tran-Thanh, Greg Hines, Talal Rahwan, and Alex Rogers. Bounding the estimation error of sampling-basee based Shapley value approximation. arXiv:1306.422: 4265, 2013.
[28] David Liwen-Nowell, Alexa Sharp, Tom Wexler, and Kevin M. Woods. Computing Shapley value in supermodular coalitional games. In Computing and Combinatorics 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20-22, 2012. Proceedings, pages 568-579. Springer, 2012.
[29] Yongchan Kwon and James Zou. Beta Shapley: a 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.
[30] Jiachen T. Wang and Ruoxi Jia. Data Banzhaf: A robust data valuation framework for machine learning. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, pages 6388 0421.64211122 PMLR, 2023.
[31] 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):575--5759, 2021.
[32] Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing Systems, 33:
2881-2891 2020.
[33] Andrew Ilyas, 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 Machine Learning, pages 9525-9587, PMLR, 2022.
[34] 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.
[35] 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.
[36] Andrea Schioppa, Polina Zablotskaia, David Vilar, and Artem Sokolov. Scaling up influence functions. Proceedings of the AAAI Conference on Artificial Intelligence, 36(8):8179-8 8166, 2022.
[37] R. Dennis Cook and Sanford Weisberg. Residuals and Influence Regression. Chapman and Hall, New York, NY, USA, 1982.
[38] Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation stability. Inf. Process. Leu.. 1 12(1-2))49-54, 2012.
[39] Haris Angelidakis. Konstantin Makarychev, and Yury Makarychev. Algorithms for stable and perturbation-resilien problems. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 438-451 451. Association for Computing Machinery, 2017.
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: The main claims made in the abstract and introduction accurately specify the contributions and scope of 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:
We discuss the limitations of the work in Section 7
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 provide the full set of assumptions and complete (and correct) proof for each theoretical result in the paper.
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 provide all the information needed to reproduce the main experimental results of the paper, including the code and data.
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

---

reproducible, they Question: 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?
Answer: [Yes]
Justification: We provide open access to the code, with sufficient instructions to faithfully reproduce the main experimental results. All the data 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/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is 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 NeurIPS code and data submission guidelines (https
/
Cooee//mdeeeSbmmmcia ssi onPolicy) 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 should state which ones are omitted from the script and why.
At submission time, to 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 is 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 specify all the training and test details necessary understand the results in the paper.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to 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 of the key results in Table T
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, or 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 provide sufficient information on the computer resources needed to repro- duce the experiments in Section 6
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 ' 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
Answer:
[Yes]
Justification:
We conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The proposed data valuation framework can used to value data in a more transparent and fair way, which naturally leads to positive societal impacts. Our framework is not tied to any particular application, and there does not exist a direct path to any negative applications to the best of our knowledge.
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 data or models 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 properly credit and respect the license and terms of use of the assets used in the paper.
Guidelines:
The answer NA means that the paper does not 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 provide detailed description of the code released in the paper.
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 2. Fixing test point. for any i < n, we have
8441 + min(K,)))) w; Vtess) wi+1 (Vi+1 Bress)
K w,, wn1( yreat).
and 8n
Proof of Theorem 2
For S2, i.c., the Shapley value of the farthest data point, it is easy to see that
K
1
Σ
eS + 2n. v(S)
0=0
SCD
K
Σ
Wn (11 Ihea))
SCD
Win (1/n yeea)
(7)
n
Since for any S such that |S| 2 k 2n will not make it into the top-k and thus v(S + 2,) - v(5) 0.
Suppose that we have already computed s.+1...., Sn, and now we want to compute st. By Lemma | we only need to pay attention to S C D 2g 21+1. Divide S into two parts: S sn 21, ................................ 2,-1
K, v(S + z:) v(S + zi-1) vSS). Therefore, we only need to consider the case when |S|| K. We have
and S2 S n ( }. Notice that if S >
8:
8:+1
Σ
0S + 21) v(S + z1+1)
11
|
Σ
wy w/+11
11
| S
min(k (K 11,))
w
w
1 1)
n i-11 1)
Σ
kj
k1
k=0
K1=0
w/ w//1 min( K, i)(n 1)
n1 n-1
i
min(K,) () (wr w/+1):
where w/, w:1(M ). See for more details the identity in the second to last step.
Theorem 4. Let (D Drest: d) be a clustering instance with Thesst = O().. If it is 3-perturbation resilient for metric k-center with respect to a cluster number k* and maximum cluster radius T" 2 r, then Algorithm 0 with n, = k" returns the exact data Shapley values of each point in D in O(nnn(d + log + s log s)) time, where is the size of the largest optimal cluster.
Proof of Theorem 4
We first prove that 3-perturbation resilience guarantees a useful technical lemma.
Lemma 5. Given a center Zmark and any point z from different cluster than that of zmarko we have d(2, ) > 2r".
Proof. Assume for contradiction that d(z, #mark) < 2T* We can create a 3-perturbation of such that set of centers Dmark Amark + yield 3-approximation of the k-center clustering. This contradicts the assumption since any 3-approximation solution recovers the optimal clustering, following Theorem 3
The 3-perturbation given follows.
d' d'(z, v) = [min(3r*, 3d(x,y)) if = and y E ((mmak): [3d(z,)) y)
otherwise.
20

---

It is easy to verify that d' is 3-perturbation of d. Besides, assigning every point x: E (z to the new center 2 respects the inequality
d(z, 2) S d kmark) + d( 2mark: 2) S 3T
The assignments for other data points are either intact or better. Thus, the new centers indeed yield 3-approximation, completing the proof.
also need the help from another lemma.
Lemma 6 (Chekuri and Gupta 23 Under 2-perturbation resilience, for any two different optimal
clusters C₁ C3. we have
d dxr,y) d(x, z)
and 7² < d(a, 2)
for any I, E C. and 2 E Cj.
As result, when k- = nr,, the clusters induced by Dmark recover the optimal clusters by Theorem This implies that the points assigned to the optimal cluster of Zmark will be ranked before the points in other clusters, following Lemma What is more, by Lemma the subset S for each test point Fesst associated with 2mark in Algorithm
will collect only points from the optimal cluster Zest belongs to, T* for any from a different cluster. This verifies the
because (d(2, 2mark) d( mmarks Zrest) stated time complexity.
What is left to show is the correctness, i.e., every point that is within distance of from 2iet must stay the same optimal cluster as 2estt which directly follows from Lemma and T² 2 т, and they will be collected into the subset S as [d(z, zmark) d((mark. Rea)) is lower bound of d(z, 2 This completes the proof.
When 1s n,, slightly larger 4-perturbation.
show that the same time complexity in Theorem 4 still holds, albeit with
Theorem 7. Let (D U Dreas d) be clustering instance with Thest = On). If (D Dreat d) is perturbation resilient for metric k-center with respect to a cluster number k and a maximum cluster radius T 2 T, then Algorithm 7 returns the exact data Shapley values of each data point in D in time (n + log n) + S log s)), where is the size of the largest optimal cluster.
Proof. We first show stronger lemma than Lemma 5 under perturrbation. We omit the proof since it is similar to that of Lemma[5]
Lemma 8. Given a optimal center and any point from different cluster than that of c, we have d(z,c) > 3r
Lemma g iimplie stronger variant Lemma 6
Lemma 9. (D, d) is 2-perturbation resilient, then for any two different optimal clusters Ct Cj. we have 2T* < d(x, 2) for any x E C; and z E Cý.
Proof. Let e be the optimal center of Cy. By triangle inequality, we have
d(z, 2) 2 |d c) - d(c, 2)1 > 27"
As result of Lemma we can relax the requirement that every landmark point has to correspond to an optimal center, and let be any point instead. The statement can proved by similar arguments as in the proof of Theorem 4
21

---

B Expanded Related Work
B.1 Shapley Values
Shapley values [6] originated in cooperative game theory as a method for fairly distributing gains among players based their marginal contributions and have been widely adopted in various domains such as economics [24]. In machine learning, the most well-known application attribution methods such as SHAP 2 where Shapley values are computed for each feature of given data point as form of feature importance scores. Recently, Shapley values have been adapted to quantify the
contribution of individual training examples model performance 77. Computing exact Shapley values is well-known to be expensive and has been shown to be # #--hard in certain games [T]. Such a computational challenge has motivated various approximation techniques. including mostly Monte Carlo sampling [7 and specialized algorithms for specific games [28]. Our work falls into the latter category.
B.2 Data Valuation
Data valuation aims to assign importance scores to training examples, with the hope of identifying valuable harmful data points 2 4 The dominant approaches are based the concept of leave- one-out (LOO), which measures the marginal contribution of a data point to the utility function when it is removed from the training procedure. In classification settings, common choice for the utility function is the test accuracy of a model trained on the input. Data Shapley 77] and its variants such as Beta Shapley (29]. Data Banzhaf R0), and least core [31]. are all based on the L.00 principle, but differ the way marginal contributions are aggregated.
Beyond Shapley values, there exist other approaches, and we discuss some notable ones below, Feldman and Zhang [32] simulate the data values by LOO retraining albeit constrained on a small sample of training data, while DataModels [3] sacrifice the exactness of LOO to achieve better scalability by model predictions. Another line of popular methods are gradient-
TracIn [34] estimates the importance of training example by tracing the change in test loss caused by the example during the training process. Variations of influence functions [35] 36] have their roots in robust statistics
37 and offer gradient-base based approximation of LOO values.
B.3 KNN Shapley Values
The KNN model provides a unique opportunity for efficient computation of data Shapley values. Jia et al. [ are the first to discover an efficient algorithm for computing unweighted KNN Shapley values with a complexity of (dn + Reen log n). This a significant improvement over general Shapley computation methods, making it feasible for datasets of moderate size. Wang and Jia 13 provide refinements to the unweighted KNN utility function. Building on this foundation, Wang et al. [15] tackle the weighted KNN case, which turns out to be more challenging due to the normalization factor in the utility function. They propose dynamic programming algorithm for a hard-label weighted KNN utility function. Furthermore, Wang et al. [14] addressed privacy concerns in computing KNN Shapley values and offered formal privacy guarantees for a threshold- based KNN utility function. Note that in their utility function, all near neighbors within the ball around test point are equal. Our work focuses on accelerating the computation KNN Shapley values.
B.4 Clustering and Perturbation Resilience
Clustering is a common technique to exploit the structure of a dataset. Among many clustering methods, the k-center clustering is one of the most popular. It is well-known that the k-center clustering problem is Na-hard, and FFT is proved to be 2-approximate in the worst case. To overcome the over-pessimism and conservatism of worst-case analysis, recent years, beyond worst-case analysis (BWCA) has received increasing attention. One popular BWCA approach for clustering problems is to define notion of stability, and perturbation resilience is one classic stability measure [21] It has been shown that multiple clustering problems admit polynomial-tine -ime algorithms under some degree of perturbation resilience [8 39 Balcan et al. (2 analyze the FFT algorithm as robust solution in BWCA scenarios. Chekuri and Gupta 23 study k-center clustering in the presence of outliers. Our work leverages these existing understandings about perturbation resilience to provably accelerate the computation of KNN Shapley values.
22

---

Table A1: Statistics of datasets used in the experiments.
Dataset
[D]
Deal
d
[D
[Dreal d
magic
15 063
153
10
23 046 390
2dplanes
40 360
408
10
164 668 800
citar10
49 500
500
512
12672 000 000
dota2
722
927
125
10 286 750
skin
194 084
1961
3
1 141 796 172
covtype
578 106
2906
54
90 718 705 944
emnist
696 536
1396
512
497 850 499 072
poker
998 000
2000
10
19 90960000000 000
Additional Experimental Results
C.1 Mislabel Detection
We adopt the popular downstream task of mislabel detection, where 5% of the training points are randomly mislabeled, and we try to detect them using the data points with the lowest data values. We use the Fl score to evaluate the performance of valuation methods. The score of our method slightly worse than that of the un-thresholded baseline (no more than 1% worse), which is unsurprising given their similar formulations. The Fl score of TNN is 20-50% worse than the others in most datasets. This is most likely due to the fact that TNN does not utilize the ranking signal among neighborhood points. We tune the radius on a validation set sampled from the noisy training set. We use the implementation of TNN by its authors [14]
C.2 Curse of Dimensionality
We conduct a controlled experiment to isolate the "curse dimensionality" effect. We perform projections by Gaussian random matrix on the cifar10 dataset to reduce its dimensionality to 10, and use the same ratio of T/d /d as before. The baseline takes 16ss (148s previously) and our method with r/d 0.05 takes 13s (75s previously). The running time of all methods decreases, due to the smaller overhead for distance computation, but the ratio of the running time of the baseline to ours increases. Therefore, it is indeed helpful to reduce the dimensionality by random projections.
23


Reviews:
[{"review_id": "qVklsvJUcZ", "reviewer": "Reviewer_x6A4", "summary": "The article addresses the problem of computing Shapley values for data valuation in K-nearest neighbor (KNN) models. By introducing a landmark-based near-neighbor search, the authors reduce the search space and significantly improve the computational efficiency of Data Shapley for threshold-based KNN. They analyze the theoretical complexity of their algorithm under a perturbation resilience assumption and support their findings with empirical validation on both synthetic and real-world datasets. The results demonstrate that the proposed methodology offers substantial improvements over classical KNN-based Shapley value computations.", "questions": "1. Are there known scenarios where perturbation resilience does not hold? If so, does your method still outperform the baseline in those cases?\n2. You report improvements in execution time, but do not present any accuracy comparisons. How accurate is your method in approximating the Shapley values compared to the baseline?\n3. How does your method perform against other state-of-the-art data valuation techniques—both in terms of computation time and accuracy?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The article is clearly written and well-structured.\n- The addressed problem—efficiently computing data Shapley values for KNN models—is relevant.\n- The work is mathematically solid and theoretically grounded.\n- The authors analyze the theoretical complexity of their method and provide sufficient conditions under which it improves upon existing time bounds in the literature.\n- The proposed method shows strong empirical performance, outperforming the classical KNN Shapley approach.\n\nWeaknesses\n- The theoretical assumption on perturbation resilience is difficult to verify in practice.\n- The empirical evaluation compares the proposed method only to the classical baseline, without including other competitive data valuation methods. Moreover, comparisons are done only with respect to execution time.", "was_revised": true, "final_justification": "The article is good and the authors replied to all my concerns during the rebuttals. I've dediced to keep my good score.", "rebuttal": "We thank the reviewer for the time and effort in reviewing our paper.\nWe answer your questions below.\n\n**Q1**:\nAre there known scenarios where perturbation resilience does not hold? If so, does your method still outperform the baseline in those cases?\n\n**A1**: \nYes, perturbation resilience fails in scenarios such as (1) datasets with overlapping clusters where small perturbations can change cluster assignments, (2) high-dimensional data (i.e., curse of dimensionality) where distance-based clustering becomes ineffective, and (3) datasets with insufficient separation between clusters. \nHowever, even in these cases, our method still outperforms the baseline, though inevitably with a smaller speed-up.\nFor example, see the results on high-dimensional datasets like CIFAR-10 and EMNIST in our experiments.\nNote that our worst-case complexity equals the baseline with negligible preprocessing overhead.\n\n\n**Q2**:\nYou report improvements in execution time, but do not present any accuracy comparisons. How accurate is your method in approximating the Shapley values compared to the baseline?\n\n**A2**: \nWe have added additional experiments about the accuracy of a popular downstream task.\nThe short answer is that there is little difference between the accuracy of our method and that of the baseline kNN-Shapley.\nWe refer the reviewer to our answer to reviewer WTuj for more details.\n\n\n\n**Q3**:\nHow does your method perform against other state-of-the-art data valuation techniques—both in terms of computation time and accuracy?\n\n**A3**: \nThe main focus of the paper is to accelerate the computation of kNN-Shapley, and to make the first attempt to address its scalability issue with respect to the number of test examples.\nWe hope to stick to this goal and provide more focused comparisons for our purpose.\nThe accuracy of our method is almost identical to the baseline kNN-Shapley, which should be unsurprising given their similar formulations.\nWe refer readers to for example, the reference [19] for more comprehensive comparisons with other state-of-the-art data valuation techniques."}, {"review_id": "NdzMcL2uF6", "reviewer": "Reviewer_dXW1", "summary": "This paper considers the problem of efficiently computing Shapley values for a special class of functions. In general, Shapley values have $2^n$ terms, where $n$ is the number of Shapley values. However, for restricted classes of functions $v$, we can hope to compute the Shapley values more efficiently. Work by Jia et al. shows how to compute the Shapley value with respect to one test point for $k$ nearest neighbors in time $O(dn + n log n)$ where $d$ is the dimension of the points. However, scaling this calculation to $n$ test points would naively take $O(dnn + n^2 log n)$.\n\nIn this work, the authors build a \"landmark\" data structures that enables faster computation when the dataset is \"stable\" in a technical sense. They find experimentally that this method can perform better than prior works for computing the Shapley values.", "questions": "In table 1, each row corresponds to a different dataset. The baseline only has $\\tau/d=.05$ but Algorithm 1 has $\\tau/d =.05, .1, .2$. If you're going to vary $\\tau/d$, it seems fair to also vary it for the baseline approach. Can you please run these experiments?\n\nRegarding your discussion after Theorem 4, let's imagine $n_test \\approx n$, and let's assume that the partitions are roughly equally sized so that $s \\approx n / n_L$ (you could make this formal under the right distributional assumption with some log factors). Ignoring log factors, your bound is $O(n_L n d + n n/ n_L d)$. Optimizing over $n_L$, we would choose $n_L = \\sqrt{n}$, then your bound is $O(n^{1.5 d})$. Would you present your result in this way? I think it makes the guarantee more digestible (with some mild assumptions), and makes it clear that you're getting a reasonable speed up from $n^2 d$ to $n^{1.5} d$.\n\nCould you run experiments where you plot baseline vs algorithm 1 performance by size of dataset? It's hard to tell from the raw numbers how the *rate* of the difference is changing.\n\nIf a plot looks persuasive and you present your guarantee this way, I could change my opinion on the \"marginal\" impact of your work, and increase my score.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n* *Very* nice presentation of the method. The main ideas were all clearly and accessibly discussed.\n\n* The main result that Shapley values can be more efficiently computed under a stability assumption is quite nice.\n\n* The theoretical analysis and guarantees is a nice application of \"perturbation resilience.\"\n\nWeaknesses:\n\n* The speed up seems somewhat marginal in practice? This could be an issue with the presentation, please see below in the question.\n\n* To me, perhaps because I don't work in this exact space, the application of this work is somewhat limited.", "was_revised": true, "final_justification": "My concerns have been addressed about the speedup of their work. I'm not sure about the breadth of their impact, but the ideas are quite nice, and the algorithm works really well!", "rebuttal": "We thank the reviewer for the time and effort in reviewing our paper.\nWe answer your questions below.\n\n**Q1**:\nIn Table 1, each row corresponds to a different dataset. The baseline only has $\\tau/d=0.05$ but Algorithm 1 has $\\tau/d=0.05, 0.1, 0.2$. If you're going to vary $\\tau/d$, it seems fair to also vary it for the baseline approach. Can you please run these experiments?\n\n**A1**: \nWe didn't vary the parameter $\\tau$ for the baseline because the running time of the baseline is less sensitive to $\\tau/d$.\nMore specifically, the baseline has to go through all the training points for each test point, regardless of the radius value $\\tau$.\nThus, its running time is at least $O(n_{train} \\cdot n_{test})$, which is quadratic if the number of test points is large.\nDue to the space limit, we fix the radius $\\tau$ to be the smallest value for the baseline in our experiments, which gives it an advantage over our method but not the other way around.\nWe are happy to run these experiments with varying $\\tau$ for the baseline, and include them in the appendix of the revised paper.\n\n\n**Q2**:\nRegarding your discussion after Theorem 4, let's imagine $n_{test} \\approx n$, and let's assume that the partitions are roughly equally sized so that $s \\approx n/n_L$ (you could make this formal under the right distributional assumption with some log factors). Ignoring log factors, your bound is $O(n_L nd + nn/n_L d)$. Optimizing over $n_L$, we would choose $n_L = \\sqrt{n}$, then your bound is $O(n^{1.5} d)$.\nWould you present your result in this way? I think it makes the guarantee more digestible (with some mild assumptions), and makes it clear that you're getting a reasonable speedup $n^2$ to $n^{1.5}$.\n\n**A2**: \nSure, it sounds more logical to present the result in this way.\nWe are happy to revise the paper accordingly.\nThanks for the suggestion!\n\n\n\n**Q3**:\nCould you run experiments where you plot baseline vs algorithm 1 performance by size of dataset? It's hard to tell from the raw numbers how the rate of the difference is changing.\nIf a plot looks persuasive and you present your guarantee this way, I could change my opinion on the \"marginal\" impact of your work, and increase my score.\n\n**A3**: \nIt is true, and we should have done this to help the readers digest the result.\nUnfortunately, we are not allowed to present images or external links during the rebuttal process.\nWe have plotted the running time of the baseline and our method by the size of dataset ($n_{train} \\cdot n_{test}$).\nBasically, the baseline is represented by a straight line that scales linearly with the size, while our method has ups and downs depending on the difficulty of the datasets.\nThe line of our method is far below the baseline, and scales sublinearly with the size."}, {"review_id": "NPLB4z0T91", "reviewer": "Reviewer_VE8S", "summary": "The paper tackles the high cost of computing data Shapley values for KNN. \nIt introduces a “localized data Shapley” algorithm that limits valuation complexity to points within a small radius around each test example, found quickly via landmark-based clustering and a thresholded KNN search. The authors prove that, under mild perturbation-resilience assumptions, this strategy returns the exact Shapley values while cutting the runtime from quadratic to (nearly) linear in dataset size, and they show up to 25 times speed-ups on real datasets with up to a million points.", "questions": "1. Table 1 suggests mixed results on CIFAR-10/EMNIST (512-D). Could you add a controlled sweep over dimensionality (e.g., random projections) to isolate the “curse of dimensionality” effect?\n2. Any practical heuristics for choosing τ in high dimensional spaces?\n3. The paper focuses on thresholded KNN; can the landmark-based trick extend to weighted or learned-metric KNN (cv. Wang & Jia ’24)? A short discussion or a negative result would help.\n4. How often does a real-world dataset satisfy the 3- (or 4-) perturbation-resilient k-center condition?\n5. Could you include an empirical proxy (e.g., ratio of inter- to intra-cluster distances) or a stress-test that shows the algorithm’s degradation when the assumption is violated?", "limitations": "Authors noted some technical limits, for example:\n- Perturbation-resilience is hard to verify, but the authors justify it theoretically and show the method remains correct, falling back to baseline runtime if unmet.\n- They note efficiency may taper in high dimensions => showed through results on CIFAR-10/EMNIST (512-D) datasets.\n- They address τ and nL sensitivity with ablation plots and suggest using the “knee” point for tuning.\n\nIt would be nice to add a short section on how automated Shapley scores might exacerbate data-market inequities or enable privacy inference, and propose concrete safeguards (e.g., DP noise, audit trails).\nAlso discuss whether landmark clustering could leak sensitive structural info and how that risk can be mitigated in practice can show the depth of authors understanding of the potential impact of their works.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength\n- Authors addressed a well-motivated and increasingly relevant problem: scalable data valuation.\n- Introduced a novel algorithm combining threshold-based KNN with landmark-based clustering—both theoretically grounded and practically impactful.\n- Offered a provable runtime guarantees under realistic structural assumptions (perturbation resilience).\n- The empirical results showing up to 25× speedups over prior methods which was nice to have. However, I didn't have time to run their code, I might do that during the response period. \n\nWeaknesses \n- Some limitations in verifying perturbation resilience in practice are acknowledged, but not fully explored.\n- Algorithm may degrade in high-dimensional settings due to curse of dimensionality—this isn’t deeply discussed.\n- Slightly incremental in the sense that it builds heavily on prior KNN Shapley work, though the localization idea is novel. \n– While the authors provide strong theoretical contributions, the experimental section could benefit from deeper analysis and broader exploration of dataset characteristics and more complex dataset to better demonstrate practical impact. Since the paper is submitted under general ML (not theory), a more robust experimental design is expected.\n\nNot a weakness just a friendly suggestion: the citations currently start from [22] at the beginning of the paper, and it might be helpful to renumber them starting from [1]. This would make it easier to follow and track the references as we read through the paper.", "was_revised": true, "final_justification": "I reviewed the authors’ responses to my questions and comments, as well as to those from other reviewers, and have adjusted my rating accordingly.", "rebuttal": "We thank the reviewer for reviewing our paper and many constructive comments.\n\n\n**Q1**:\nTable 1 suggests mixed results on CIFAR-10/EMNIST (512-D). Could you add a controlled sweep over dimensionality (e.g., random projections) to isolate the “curse of dimensionality”\neffect?\n\n**A1**: \nWe perform projections by a Gaussian random matrix on the CIFAR-10 dataset to reduce its dimensionality to 10, and\nuse the same ratio of $\\tau/d$ as before.\nThe baseline takes 116s (148s previously) and our method with $\\tau/d=0.05$ takes 13s (75s previously).\nThe running time of all methods decreases, due to the smaller overhead for distance computation, but the ratio of the running time of the baseline to ours increases.\nIt seems effective to reduce the dimensionality by random projections.\nWe thank the reviewer for the suggestion, and will add this discussion to the revised paper.\n\n\n\n**Q2**:\nAny practical heuristics for choosing τ in high dimensional spaces?\n\n**A2**: \nWe are not aware of any good strategies for choosing $\\tau$ in high-dimensional spaces.\nA general approach to choose $\\tau$ is to tune it on a validation set for the task at hand (e.g., classification accuracy).\nWe report simple statistics of the tuned ratio $\\tau/d$ for datasets in our experiments for your reference.\nThe unsurprising rule is that a larger $\\tau$ usually leads to better accuracy.\nHowever, the marginal gain of increasing $\\tau/d$ saturates at $0.05$ for 3/8 of the datasets (all large datasets) and at $0.2$ for all.\n\n\n**Q3**:\nThe paper focuses on thresholded KNN; can the landmark-based trick extend to weighted or learned-metric KNN (cv. Wang & Jia ’24)? A short discussion or a negative result would\nhelp.\n\n**A3**: \nIt is an interesting question about extending the technique to [JW24].\nAs far as we know, they apply a very different dynamic programming (DP) technique to compute the kNN-Shapley values with respect to a \"hard-label\" utility function.\nBasically, they use DP to do counting of pivotal subsets for each data point.\nIt seems possible to extend our technique to their setting by restricting the counting among data points whose distance to the test point is less than the radius $\\tau$.\nWe will explore this direction in the future, and thank you for your question.\n\n\n**Q4**:\nHow often does a real-world dataset satisfy the 3- (or 4-) perturbation-resilient k-center condition?\n\n**A4**: \nUnfortunately, this condition rarely perfectly holds in real-world datasets.\nThis is mostly due to the noise in the real-world data.\nFor example, given two well-separated clusters with the majority of their data points satisfying the condition, there may be a small portion of outliers in each cluster that violate the condition.\nThis is why we design the ball-expansion technique that searches for all data points within the radius $\\tau$.\nIt starts with the most likely data points and uses lightweight bounds to prune the search space, which allows it to adapt gracefully to the violations.\n\n\n**Q5**:\nCould you include an empirical proxy (e.g., ratio of inter- to intra-cluster distances) or a stress-test that shows the algorithm’s degradation when the assumption is violated?\n\n**A5**: \nWe design a stress test with a random dataset.\nThe dataset consists of two fixed centers surrounded by 5000 points each, which are created by sampling from a Gaussian distribution with the center being the mean.\nWe gradually increase the variance to make the clusters less separated.\nThen, we run our method and monitor the change in its running time.\nIt turns out that the running time of our method decreases.\nThis is counter-intuitive to us at first sight.\nLater, we figure out that it can be beneficial to threshold-based KNN when the clusters become dispersed,\nas less points need to be considered during the landmark-based search.\nThis is an interesting observation, and we thank the reviewer for the suggestion."}, {"review_id": "GucxkNQGDJ", "reviewer": "Reviewer_WTuj", "summary": "The paper presents a new technique to calculate the Data Shapley values for KNN models. The proposed method addresses the significant computational cost of existing KNN-Shapley when applied to large test sets. The evaluation shows some promising efficient improvements.", "questions": "1. Compare with TKNN-Shapley in terms of compute efficiency.\n2. Evaluate the utility of proposed data values on popular downstream tasks.\n3. Discuss the online test query setting.\n\nI'm happy to raise my scores if the weaknesses are addressed.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1. The technique proposed is novel, and appears to be an interesting addition to the line of work on the Shapley value for KNN models.\n2. The evaluation shows promising efficiency gains.\n\nWeaknesses: \n1. It is important to point out that the utility function underlying the Shapley value that the paper is focused on is a different utility function from the original KNN-Shapley value. Specifically, the paper considers the utility for some distance-weighted threshold-based KNN. The original paper of KNN-Shapely just considered the standard unweighted KNN. If one is allowed to change the utility function, then Wang et al. [1] considers the unweighted threshold-based KNN and the computation complexity of this method is only linear in both training and test size, getting rid of the log N factor. The paper should compare the computational efficiency with this method. \n2. On a related note, since the paper changes the utility function, it is crucial to examine whether the resulting Shapely value can still detect the data quality differences as effectively as KNN-Shapley and TKNN-Shapley [1].\n[1] Wang et al. Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation\n3. The proposed algorithm requires to sort all data points in training and test sets  for each landmark point, which results in a complexity of O((N_train+N_test)log(N_train+N_test) N_landmark). If the test points are coming on the fly, this computation cost would be problematic as we need to re-do the sorting whenever a new test point arrives. Yet KNN-Shapley does not have this landmark building setup and circumvents the costs. The paper lacks some discussion on how this landmark building costs would affect the overall efficiency in different contexts.", "was_revised": true, "final_justification": "The technique proposed is a novel addition to the line of work on the Shapley value for KNN models. During the rebuttal, the authors have addressed the concerns regarding the comparison with literature and potential extension to online settings. Given the current shape, the paper is a solid contribution.", "rebuttal": "We thank the reviewer for the time and effort in reviewing our paper.\nWe answer your questions below.\n\n**Q1**:\nCompare with TKNN-Shapley in terms of compute efficiency, and evaluate the utility of proposed data values on popular downstream tasks.\n\n**A1**: \nFirst of all, we believe it is more suitable to call this method \"TNN-Shapley\" instead of \"TKNN-Shapley\", which highlights that fact that it does not require a parameter $K$.\nBasically, TNN does not perform any ranking over the neighbors of the test point, which is why it only cost $O(n)$ time instead of $O(n \\log n)$ time.\nIt fetches all neighbors that are within the radius $\\tau$ (in $O(n)$ time) and derives a value from the counts of these neighbors in each class.\nThus, it should not be surprising that it tends to result in worse accuracy than methods with KNN formulations (see below).\n\nWe adopt the popular downstream task of mislabel detection, where 5% of the training points are randomly mislabeled, and we try to detect them using the data points with the lowest data values.\nWe use the F1 score to evaluate the performance of valuation methods.\nThe F1 score of our method is slightly worse than that of the \nun-thresholded kNN-Shapley (no more than 1% worse).\nThe F1 score of TNN is 20-50% worse than the others in 9 out of 11 datasets.\nThat is, if our F1 score is 70%, TNN's F1 score is at most 50%.\nWe tune the radius $\\tau$ on a validation set sampled from the noisy training set.\nWe use the implementation of TNN by its authors.\n\nIn terms of efficiency, TNN is indeed faster than the baseline KNN-Shapley.\nThe complexity of TNN is $O(n_{test} \\cdot n_{train})$ instead of $O(n_{test} \\cdot n_{train} \\log n_{train})$, but still quadratic if the number of test points is large.\nThus, it is slower than our method, especially over large datasets.\nFor example, its running time is 5542.69 ($\\pm$ 23.88) seconds for the Poker dataset, which is about 11$\\times$ slower than ours.\n\nWe will add this comparison to the revised paper.\n\n\n\n**Q2**:\nDiscuss the online test query setting.\n\n**A2**: \nExtending the technique to the online test query setting is an interesting and challenging direction.\nWe are afraid that this challenge may be out of the scope of this paper, because online settings are significantly different from what we consider in the paper.\nHowever, the first idea that comes to mind is to resort to dynamic clustering techniques for our landmark building.\nDue to the time constraint, we are unable to dive deep into the investigation.\nWe thank the reviewer for bringing up this interesting direction, and we will explore it in the future.\n\nWe hope that the reviewer will consider increasing the score."}, {"review_id": "pTreGFRWW0", "reviewer": "Reviewer_JeLY", "summary": "This paper introduces a localized data Shapley framework to accelerate the valuation of data points for K-nearest neighbor (KNN) models. The authors leverage distance-based local structure to decompose the global valuation problem into smaller computations. They propose an efficient algorithm for threshold-based KNN that achieves provable speedups under perturbation resilience assumptions, with experiments showing up to 25x speedup compared to baseline methods.", "questions": "- Could you provide some practical guidance on estimating $k^\\*$ or choosing $n_L$ for a new dataset where the clustering structure is unknown?\n- In line 217, you mention that $\\tau_{D_{\\textrm{mark}}} \\le \\tau$ is \"easily achieved by continuing the iterative process of FFT.\" How many landmarks does this typically require in practice? Does this ever result in $n_L > k^\\*$?", "limitations": "See weaknesses above.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- Clear presentation and solid theoretical foundation. The paper is really well-written with a logical flow from preliminaries (Section 2) through the baseline approach (Section 3) to the proposed methods. The mathematical notation is consistent, and the recursive formula in Theorem 2 provides a nice foundation for understanding how Shapley values can be computed efficiently for KNN models.\n- Practical algorithm design with theoretical guarantees. The landmark selection using farthest-first traversal (FFT) is a smart choice that balances theoretical guarantees with practical efficiency. The algorithm gracefully handles the worst case.\n- Novel use of perturbation resilience for algorithm analysis. The connection between perturbation resilience (Definition 2) and the efficiency of landmark-based near neighbor search is creative. The authors cleverly show that 3-perturbation resilient instances allow Algorithm 1 to restrict computations within clusters, leading to the complexity in Theorem 4.\n- Impressive empirical performance gains. The experimental results in Table 1 are quite compelling - the proposed Algorithm 1 achieves speedups up to 25x across different datasets.\n\n### Weaknesses\n- Limited discussion on determining $k^\\*$. While the paper assumes knowledge of the optimal cluster number $k^\\*$ for the theoretical analysis, there is insufficient guidance on how to determine or estimate this value in practice. The authors mention that \"perturbation resilience condition is hard to verify in practice\" (line 353), but don't provide any heuristics or methods to estimate $k^\\*$ for real datasets, which limits the practical applicability of the theoretical guarantees.\n- Missing ablation study on $n_L$ in final experiments. Section 6.1 shows the effect of $n_L$ on the 2dplanes dataset (Figure 1a), but Section 6.2 only reports results with a fixed $n_L = 50$ for all datasets. Given that the theoretical speedup depends heavily on $n_L$ and the paper claims \"significant speedup even when $n_L$ is as large as $\\sqrt{n}$\" (line 293), it would strengthen the paper to show how performance varies with different $n_L$ values across all datasets in Table 1.\n- Restrictive threshold-based KNN variant. The main algorithm focuses on threshold-based KNN (TKNN), which has \"additional desirable privacy-friendly properties\" (line 114), but this variant is less commonly used than standard KNN. While the authors claim TKNN is \"more robust\" (line 112), they don't provide empirical evidence comparing the actual prediction performance of TKNN vs standard KNN, making it unclear whether users would want to adopt this variant just for faster Shapley computation.", "was_revised": true, "final_justification": "The author answered my questions while my concerns about weakness were still valid. Thus, I will not raise my score and keep my original rating.", "rebuttal": "We thank the reviewer for the time and effort in reviewing our paper.\nWe answer your questions below.\n\n**Q1**:\nCould you provide some practical guidance on estimating $k^*$ or choosing $n_L$ for a new dataset where the clustering structure is unknown?\n\n**A1**: \nDeciding the number of landmarks $n_L$, or in general, the number of clusters $k^*$ for geometric clustering, is a long-standing challenging problem.\nWhat we did in Section 6.1 is essentially the most popular heuristic for this problem, which is also known as the Elbow method.\nThat is, to test the metric of interest (e.g., the clustering error or running time in our context) with varying $n_L$, and choose the $n_L$ that gives the best performance.\n\n\n**Q2**:\nIn line 217, you mention that $\\tau_{D_{mark}} \\le \\tau$ is \"easily achieved by continuing the iterative process of FFT.\" How many landmarks does this typically require in practice? Does this ever result in $n_L > k^*$?\n\n**A2**: \nUnfortunately, it is unlikely that we can find the optimal value of $k^*$ for general datasets.\nWe do test the number of landmarks $n_L$ by running the FFT algorithm on the datasets in our experiments.\nWe found that typically it takes up to hundreds of landmarks to achieve $\\tau_{D_{mark}} \\le \\tau$ for a small $\\tau$.\nThis may result in a larger overhead in practice.\nThus, in practice, we recommend using the Elbow method (see Figure 1) to fix some small number of landmarks."}]

Author rebuttal:

Meta-review: This paper looks at the fundamental question of data-valuation, using the Shapley value, which is not tractable in the general case. As a consequence, an important line of work consists in looking at subcases, with additional assumptions, and to derive algorithms that can perform it (or at least approximate the value with enough precision).

This paper does this, and all the reviewers, and myself, are rather positive about this paper, the writing and the contribution.

As a consequence, I am happy to recommend acceptance.
Decision: Accept (poster)